gc_hdrs.h 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215
  1. /*
  2. * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3. * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
  4. *
  5. * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6. * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
  7. *
  8. * Permission is hereby granted to use or copy this program
  9. * for any purpose, provided the above notices are retained on all copies.
  10. * Permission to modify the code and to distribute modified code is granted,
  11. * provided the above notices are retained, and a notice that the code was
  12. * modified is included with the above copyright notice.
  13. */
  14. #ifndef GC_HEADERS_H
  15. #define GC_HEADERS_H
  16. #if CPP_WORDSZ != 32 && CPP_WORDSZ < 36 && !defined(CPPCHECK)
  17. # error Get a real machine
  18. #endif
  19. EXTERN_C_BEGIN
  20. typedef struct hblkhdr hdr;
  21. /*
  22. * The 2 level tree data structure that is used to find block headers.
  23. * If there are more than 32 bits in a pointer, the top level is a hash
  24. * table.
  25. *
  26. * This defines HDR, GET_HDR, and SET_HDR, the main macros used to
  27. * retrieve and set object headers.
  28. *
  29. * We take advantage of a header lookup
  30. * cache. This is a locally declared direct mapped cache, used inside
  31. * the marker. The HC_GET_HDR macro uses and maintains this
  32. * cache. Assuming we get reasonable hit rates, this shaves a few
  33. * memory references from each pointer validation.
  34. */
  35. #if CPP_WORDSZ > 32
  36. # define HASH_TL
  37. #endif
  38. /* Define appropriate out-degrees for each of the two tree levels */
  39. #if defined(LARGE_CONFIG) || !defined(SMALL_CONFIG)
  40. # define LOG_BOTTOM_SZ 10
  41. #else
  42. # define LOG_BOTTOM_SZ 11
  43. /* Keep top index size reasonable with smaller blocks. */
  44. #endif
  45. #define BOTTOM_SZ (1 << LOG_BOTTOM_SZ)
  46. #ifndef HASH_TL
  47. # define LOG_TOP_SZ (WORDSZ - LOG_BOTTOM_SZ - LOG_HBLKSIZE)
  48. #else
  49. # define LOG_TOP_SZ 11
  50. #endif
  51. #define TOP_SZ (1 << LOG_TOP_SZ)
  52. /* #define COUNT_HDR_CACHE_HITS */
  53. #ifdef COUNT_HDR_CACHE_HITS
  54. extern word GC_hdr_cache_hits; /* used for debugging/profiling */
  55. extern word GC_hdr_cache_misses;
  56. # define HC_HIT() (void)(++GC_hdr_cache_hits)
  57. # define HC_MISS() (void)(++GC_hdr_cache_misses)
  58. #else
  59. # define HC_HIT() /* empty */
  60. # define HC_MISS() /* empty */
  61. #endif
  62. typedef struct hce {
  63. word block_addr; /* right shifted by LOG_HBLKSIZE */
  64. hdr * hce_hdr;
  65. } hdr_cache_entry;
  66. #define HDR_CACHE_SIZE 8 /* power of 2 */
  67. #define DECLARE_HDR_CACHE \
  68. hdr_cache_entry hdr_cache[HDR_CACHE_SIZE]
  69. #define INIT_HDR_CACHE BZERO(hdr_cache, sizeof(hdr_cache))
  70. #define HCE(h) \
  71. (hdr_cache + (((word)(h) >> LOG_HBLKSIZE) & (HDR_CACHE_SIZE-1)))
  72. #define HCE_VALID_FOR(hce, h) ((hce) -> block_addr == \
  73. ((word)(h) >> LOG_HBLKSIZE))
  74. #define HCE_HDR(h) ((hce) -> hce_hdr)
  75. #ifdef PRINT_BLACK_LIST
  76. GC_INNER hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce,
  77. ptr_t source);
  78. # define HEADER_CACHE_MISS(p, hce, source) \
  79. GC_header_cache_miss(p, hce, source)
  80. #else
  81. GC_INNER hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce);
  82. # define HEADER_CACHE_MISS(p, hce, source) GC_header_cache_miss(p, hce)
  83. #endif
  84. /* Set hhdr to the header for p. Analogous to GET_HDR below, */
  85. /* except that in the case of large objects, it gets the header for */
  86. /* the object beginning if GC_all_interior_pointers is set. */
  87. /* Returns zero if p points to somewhere other than the first page */
  88. /* of an object, and it is not a valid pointer to the object. */
  89. #define HC_GET_HDR(p, hhdr, source) \
  90. { /* cannot use do-while(0) here */ \
  91. hdr_cache_entry * hce = HCE(p); \
  92. if (EXPECT(HCE_VALID_FOR(hce, p), TRUE)) { \
  93. HC_HIT(); \
  94. hhdr = hce -> hce_hdr; \
  95. } else { \
  96. hhdr = HEADER_CACHE_MISS(p, hce, source); \
  97. if (NULL == hhdr) break; /* go to the enclosing loop end */ \
  98. } \
  99. }
  100. typedef struct bi {
  101. hdr * index[BOTTOM_SZ];
  102. /*
  103. * The bottom level index contains one of three kinds of values:
  104. * 0 means we're not responsible for this block,
  105. * or this is a block other than the first one in a free block.
  106. * 1 < (long)X <= MAX_JUMP means the block starts at least
  107. * X * HBLKSIZE bytes before the current address.
  108. * A valid pointer points to a hdr structure. (The above can't be
  109. * valid pointers due to the GET_MEM return convention.)
  110. */
  111. struct bi * asc_link; /* All indices are linked in */
  112. /* ascending order... */
  113. struct bi * desc_link; /* ... and in descending order. */
  114. word key; /* high order address bits. */
  115. # ifdef HASH_TL
  116. struct bi * hash_link; /* Hash chain link. */
  117. # endif
  118. } bottom_index;
  119. /* bottom_index GC_all_nils; - really part of GC_arrays */
  120. /* extern bottom_index * GC_top_index []; - really part of GC_arrays */
  121. /* Each entry points to a bottom_index. */
  122. /* On a 32 bit machine, it points to */
  123. /* the index for a set of high order */
  124. /* bits equal to the index. For longer */
  125. /* addresses, we hash the high order */
  126. /* bits to compute the index in */
  127. /* GC_top_index, and each entry points */
  128. /* to a hash chain. */
  129. /* The last entry in each chain is */
  130. /* GC_all_nils. */
  131. #define MAX_JUMP (HBLKSIZE - 1)
  132. #define HDR_FROM_BI(bi, p) \
  133. ((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)])
  134. #ifndef HASH_TL
  135. # define BI(p) (GC_top_index \
  136. [(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)])
  137. # define HDR_INNER(p) HDR_FROM_BI(BI(p),p)
  138. # ifdef SMALL_CONFIG
  139. # define HDR(p) GC_find_header((ptr_t)(p))
  140. # else
  141. # define HDR(p) HDR_INNER(p)
  142. # endif
  143. # define GET_BI(p, bottom_indx) (void)((bottom_indx) = BI(p))
  144. # define GET_HDR(p, hhdr) (void)((hhdr) = HDR(p))
  145. # define SET_HDR(p, hhdr) (void)(HDR_INNER(p) = (hhdr))
  146. # define GET_HDR_ADDR(p, ha) (void)((ha) = &HDR_INNER(p))
  147. #else /* hash */
  148. /* Hash function for tree top level */
  149. # define TL_HASH(hi) ((hi) & (TOP_SZ - 1))
  150. /* Set bottom_indx to point to the bottom index for address p */
  151. # define GET_BI(p, bottom_indx) \
  152. do { \
  153. REGISTER word hi = (word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \
  154. REGISTER bottom_index * _bi = GC_top_index[TL_HASH(hi)]; \
  155. while (_bi -> key != hi && _bi != GC_all_nils) \
  156. _bi = _bi -> hash_link; \
  157. (bottom_indx) = _bi; \
  158. } while (0)
  159. # define GET_HDR_ADDR(p, ha) \
  160. do { \
  161. REGISTER bottom_index * bi; \
  162. GET_BI(p, bi); \
  163. (ha) = &HDR_FROM_BI(bi, p); \
  164. } while (0)
  165. # define GET_HDR(p, hhdr) \
  166. do { \
  167. REGISTER hdr ** _ha; \
  168. GET_HDR_ADDR(p, _ha); \
  169. (hhdr) = *_ha; \
  170. } while (0)
  171. # define SET_HDR(p, hhdr) \
  172. do { \
  173. REGISTER hdr ** _ha; \
  174. GET_HDR_ADDR(p, _ha); \
  175. *_ha = (hhdr); \
  176. } while (0)
  177. # define HDR(p) GC_find_header((ptr_t)(p))
  178. #endif
  179. /* Is the result a forwarding address to someplace closer to the */
  180. /* beginning of the block or NULL? */
  181. #define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((size_t) (hhdr) <= MAX_JUMP)
  182. /* Get an HBLKSIZE aligned address closer to the beginning of the block */
  183. /* h. Assumes hhdr == HDR(h) and IS_FORWARDING_ADDR(hhdr). */
  184. #define FORWARDED_ADDR(h, hhdr) ((struct hblk *)(h) - (size_t)(hhdr))
  185. EXTERN_C_END
  186. #endif /* GC_HEADERS_H */