| 1 |
/* |
| 2 |
* Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers |
| 3 |
* Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. |
| 4 |
* Copyright (c) 1996 by Silicon Graphics. All rights reserved. |
| 5 |
* |
| 6 |
* THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED |
| 7 |
* OR IMPLIED. ANY USE IS AT YOUR OWN RISK. |
| 8 |
* |
| 9 |
* Permission is hereby granted to use or copy this program |
| 10 |
* for any purpose, provided the above notices are retained on all copies. |
| 11 |
* Permission to modify the code and to distribute modified code is granted, |
| 12 |
* provided the above notices are retained, and a notice that the code was |
| 13 |
* modified is included with the above copyright notice. |
| 14 |
*/ |
| 15 |
|
| 16 |
#include "private/gc_priv.h" |
| 17 |
|
| 18 |
/* |
| 19 |
* This implements: |
| 20 |
* 1. allocation of heap block headers |
| 21 |
* 2. A map from addresses to heap block addresses to heap block headers |
| 22 |
* |
| 23 |
* Access speed is crucial. We implement an index structure based on a 2 |
| 24 |
* level tree. |
| 25 |
*/ |
| 26 |
|
| 27 |
/* Non-macro version of header location routine */ |
| 28 |
GC_INNER hdr * GC_find_header(ptr_t h) |
| 29 |
{ |
| 30 |
# ifdef HASH_TL |
| 31 |
hdr * result; |
| 32 |
GET_HDR(h, result); |
| 33 |
return(result); |
| 34 |
# else |
| 35 |
return(HDR_INNER(h)); |
| 36 |
# endif |
| 37 |
} |
| 38 |
|
| 39 |
/* Handle a header cache miss. Returns a pointer to the */ |
| 40 |
/* header corresponding to p, if p can possibly be a valid */ |
| 41 |
/* object pointer, and 0 otherwise. */ |
| 42 |
/* GUARANTEED to return 0 for a pointer past the first page */ |
| 43 |
/* of an object unless both GC_all_interior_pointers is set */ |
| 44 |
/* and p is in fact a valid object pointer. */ |
| 45 |
/* Never returns a pointer to a free hblk. */ |
| 46 |
GC_INNER hdr * |
| 47 |
#ifdef PRINT_BLACK_LIST |
| 48 |
GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce, ptr_t source) |
| 49 |
#else |
| 50 |
GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce) |
| 51 |
#endif |
| 52 |
{ |
| 53 |
hdr *hhdr; |
| 54 |
HC_MISS(); |
| 55 |
GET_HDR(p, hhdr); |
| 56 |
if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { |
| 57 |
if (GC_all_interior_pointers) { |
| 58 |
if (hhdr != 0) { |
| 59 |
ptr_t current = p; |
| 60 |
|
| 61 |
current = (ptr_t)HBLKPTR(current); |
| 62 |
do { |
| 63 |
current = current - HBLKSIZE*(word)hhdr; |
| 64 |
hhdr = HDR(current); |
| 65 |
} while(IS_FORWARDING_ADDR_OR_NIL(hhdr)); |
| 66 |
/* current points to near the start of the large object */ |
| 67 |
if (hhdr -> hb_flags & IGNORE_OFF_PAGE) |
| 68 |
return 0; |
| 69 |
if (HBLK_IS_FREE(hhdr) |
| 70 |
|| p - current >= (ptrdiff_t)(hhdr->hb_sz)) { |
| 71 |
GC_ADD_TO_BLACK_LIST_NORMAL(p, source); |
| 72 |
/* Pointer past the end of the block */ |
| 73 |
return 0; |
| 74 |
} |
| 75 |
} else { |
| 76 |
GC_ADD_TO_BLACK_LIST_NORMAL(p, source); |
| 77 |
/* And return zero: */ |
| 78 |
} |
| 79 |
GC_ASSERT(hhdr == 0 || !HBLK_IS_FREE(hhdr)); |
| 80 |
return hhdr; |
| 81 |
/* Pointers past the first page are probably too rare */ |
| 82 |
/* to add them to the cache. We don't. */ |
| 83 |
/* And correctness relies on the fact that we don't. */ |
| 84 |
} else { |
| 85 |
if (hhdr == 0) { |
| 86 |
GC_ADD_TO_BLACK_LIST_NORMAL(p, source); |
| 87 |
} |
| 88 |
return 0; |
| 89 |
} |
| 90 |
} else { |
| 91 |
if (HBLK_IS_FREE(hhdr)) { |
| 92 |
GC_ADD_TO_BLACK_LIST_NORMAL(p, source); |
| 93 |
return 0; |
| 94 |
} else { |
| 95 |
hce -> block_addr = (word)(p) >> LOG_HBLKSIZE; |
| 96 |
hce -> hce_hdr = hhdr; |
| 97 |
return hhdr; |
| 98 |
} |
| 99 |
} |
| 100 |
} |
| 101 |
|
| 102 |
/* Routines to dynamically allocate collector data structures that will */ |
| 103 |
/* never be freed. */ |
| 104 |
|
| 105 |
GC_INNER ptr_t GC_scratch_alloc(size_t bytes) |
| 106 |
{ |
| 107 |
ptr_t result = GC_scratch_free_ptr; |
| 108 |
size_t bytes_to_get; |
| 109 |
|
| 110 |
bytes = ROUNDUP_GRANULE_SIZE(bytes); |
| 111 |
for (;;) { |
| 112 |
GC_ASSERT((word)GC_scratch_end_ptr >= (word)result); |
| 113 |
if (bytes <= (word)GC_scratch_end_ptr - (word)result) { |
| 114 |
/* Unallocated space of scratch buffer has enough size. */ |
| 115 |
GC_scratch_free_ptr = result + bytes; |
| 116 |
return result; |
| 117 |
} |
| 118 |
|
| 119 |
GC_ASSERT(GC_page_size != 0); |
| 120 |
if (bytes >= MINHINCR * HBLKSIZE) { |
| 121 |
bytes_to_get = ROUNDUP_PAGESIZE_IF_MMAP(bytes); |
| 122 |
result = (ptr_t)GET_MEM(bytes_to_get); |
| 123 |
if (result != NULL) { |
| 124 |
GC_add_to_our_memory(result, bytes_to_get); |
| 125 |
/* No update of scratch free area pointer; */ |
| 126 |
/* get memory directly. */ |
| 127 |
# ifdef USE_SCRATCH_LAST_END_PTR |
| 128 |
/* Update end point of last obtained area (needed only */ |
| 129 |
/* by GC_register_dynamic_libraries for some targets). */ |
| 130 |
GC_scratch_last_end_ptr = result + bytes; |
| 131 |
# endif |
| 132 |
} |
| 133 |
return result; |
| 134 |
} |
| 135 |
|
| 136 |
bytes_to_get = ROUNDUP_PAGESIZE_IF_MMAP(MINHINCR * HBLKSIZE); |
| 137 |
/* round up for safety */ |
| 138 |
result = (ptr_t)GET_MEM(bytes_to_get); |
| 139 |
if (EXPECT(NULL == result, FALSE)) { |
| 140 |
WARN("Out of memory - trying to allocate requested amount" |
| 141 |
" (%" WARN_PRIuPTR " bytes)...\n", bytes); |
| 142 |
bytes_to_get = ROUNDUP_PAGESIZE_IF_MMAP(bytes); |
| 143 |
result = (ptr_t)GET_MEM(bytes_to_get); |
| 144 |
if (result != NULL) { |
| 145 |
GC_add_to_our_memory(result, bytes_to_get); |
| 146 |
# ifdef USE_SCRATCH_LAST_END_PTR |
| 147 |
GC_scratch_last_end_ptr = result + bytes; |
| 148 |
# endif |
| 149 |
} |
| 150 |
return result; |
| 151 |
} |
| 152 |
|
| 153 |
GC_add_to_our_memory(result, bytes_to_get); |
| 154 |
/* TODO: some amount of unallocated space may remain unused forever */ |
| 155 |
/* Update scratch area pointers and retry. */ |
| 156 |
GC_scratch_free_ptr = result; |
| 157 |
GC_scratch_end_ptr = GC_scratch_free_ptr + bytes_to_get; |
| 158 |
# ifdef USE_SCRATCH_LAST_END_PTR |
| 159 |
GC_scratch_last_end_ptr = GC_scratch_end_ptr; |
| 160 |
# endif |
| 161 |
} |
| 162 |
} |
| 163 |
|
| 164 |
/* Return an uninitialized header */ |
| 165 |
static hdr * alloc_hdr(void) |
| 166 |
{ |
| 167 |
hdr * result; |
| 168 |
|
| 169 |
if (NULL == GC_hdr_free_list) { |
| 170 |
result = (hdr *)GC_scratch_alloc(sizeof(hdr)); |
| 171 |
} else { |
| 172 |
result = GC_hdr_free_list; |
| 173 |
GC_hdr_free_list = (hdr *) result -> hb_next; |
| 174 |
} |
| 175 |
return(result); |
| 176 |
} |
| 177 |
|
| 178 |
GC_INLINE void free_hdr(hdr * hhdr) |
| 179 |
{ |
| 180 |
hhdr -> hb_next = (struct hblk *) GC_hdr_free_list; |
| 181 |
GC_hdr_free_list = hhdr; |
| 182 |
} |
| 183 |
|
| 184 |
#ifdef COUNT_HDR_CACHE_HITS |
| 185 |
/* Used for debugging/profiling (the symbols are externally visible). */ |
| 186 |
word GC_hdr_cache_hits = 0; |
| 187 |
word GC_hdr_cache_misses = 0; |
| 188 |
#endif |
| 189 |
|
| 190 |
GC_INNER void GC_init_headers(void) |
| 191 |
{ |
| 192 |
unsigned i; |
| 193 |
|
| 194 |
GC_ASSERT(NULL == GC_all_nils); |
| 195 |
GC_all_nils = (bottom_index *)GC_scratch_alloc(sizeof(bottom_index)); |
| 196 |
if (GC_all_nils == NULL) { |
| 197 |
GC_err_printf("Insufficient memory for GC_all_nils\n"); |
| 198 |
EXIT(); |
| 199 |
} |
| 200 |
BZERO(GC_all_nils, sizeof(bottom_index)); |
| 201 |
for (i = 0; i < TOP_SZ; i++) { |
| 202 |
GC_top_index[i] = GC_all_nils; |
| 203 |
} |
| 204 |
} |
| 205 |
|
| 206 |
/* Make sure that there is a bottom level index block for address addr. */ |
| 207 |
/* Return FALSE on failure. */ |
| 208 |
static GC_bool get_index(word addr) |
| 209 |
{ |
| 210 |
word hi = (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); |
| 211 |
bottom_index * r; |
| 212 |
bottom_index * p; |
| 213 |
bottom_index ** prev; |
| 214 |
bottom_index *pi; /* old_p */ |
| 215 |
word i; |
| 216 |
|
| 217 |
GC_ASSERT(I_HOLD_LOCK()); |
| 218 |
# ifdef HASH_TL |
| 219 |
i = TL_HASH(hi); |
| 220 |
|
| 221 |
pi = p = GC_top_index[i]; |
| 222 |
while(p != GC_all_nils) { |
| 223 |
if (p -> key == hi) return(TRUE); |
| 224 |
p = p -> hash_link; |
| 225 |
} |
| 226 |
# else |
| 227 |
if (GC_top_index[hi] != GC_all_nils) |
| 228 |
return TRUE; |
| 229 |
i = hi; |
| 230 |
# endif |
| 231 |
r = (bottom_index *)GC_scratch_alloc(sizeof(bottom_index)); |
| 232 |
if (EXPECT(NULL == r, FALSE)) |
| 233 |
return FALSE; |
| 234 |
BZERO(r, sizeof(bottom_index)); |
| 235 |
r -> key = hi; |
| 236 |
# ifdef HASH_TL |
| 237 |
r -> hash_link = pi; |
| 238 |
# endif |
| 239 |
|
| 240 |
/* Add it to the list of bottom indices */ |
| 241 |
prev = &GC_all_bottom_indices; /* pointer to p */ |
| 242 |
pi = 0; /* bottom_index preceding p */ |
| 243 |
while ((p = *prev) != 0 && p -> key < hi) { |
| 244 |
pi = p; |
| 245 |
prev = &(p -> asc_link); |
| 246 |
} |
| 247 |
r -> desc_link = pi; |
| 248 |
if (0 == p) { |
| 249 |
GC_all_bottom_indices_end = r; |
| 250 |
} else { |
| 251 |
p -> desc_link = r; |
| 252 |
} |
| 253 |
r -> asc_link = p; |
| 254 |
*prev = r; |
| 255 |
|
| 256 |
GC_top_index[i] = r; |
| 257 |
return(TRUE); |
| 258 |
} |
| 259 |
|
| 260 |
/* Install a header for block h. */ |
| 261 |
/* The header is uninitialized. */ |
| 262 |
/* Returns the header or 0 on failure. */ |
| 263 |
GC_INNER struct hblkhdr * GC_install_header(struct hblk *h) |
| 264 |
{ |
| 265 |
hdr * result; |
| 266 |
|
| 267 |
if (!get_index((word) h)) return(0); |
| 268 |
result = alloc_hdr(); |
| 269 |
if (result) { |
| 270 |
SET_HDR(h, result); |
| 271 |
# ifdef USE_MUNMAP |
| 272 |
result -> hb_last_reclaimed = (unsigned short)GC_gc_no; |
| 273 |
# endif |
| 274 |
} |
| 275 |
return(result); |
| 276 |
} |
| 277 |
|
| 278 |
/* Set up forwarding counts for block h of size sz */ |
| 279 |
GC_INNER GC_bool GC_install_counts(struct hblk *h, size_t sz/* bytes */) |
| 280 |
{ |
| 281 |
struct hblk * hbp; |
| 282 |
|
| 283 |
for (hbp = h; (word)hbp < (word)h + sz; hbp += BOTTOM_SZ) { |
| 284 |
if (!get_index((word)hbp)) |
| 285 |
return FALSE; |
| 286 |
if ((word)hbp > GC_WORD_MAX - (word)BOTTOM_SZ * HBLKSIZE) |
| 287 |
break; /* overflow of hbp+=BOTTOM_SZ is expected */ |
| 288 |
} |
| 289 |
if (!get_index((word)h + sz - 1)) |
| 290 |
return FALSE; |
| 291 |
for (hbp = h + 1; (word)hbp < (word)h + sz; hbp += 1) { |
| 292 |
word i = HBLK_PTR_DIFF(hbp, h); |
| 293 |
|
| 294 |
SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i)); |
| 295 |
} |
| 296 |
return TRUE; |
| 297 |
} |
| 298 |
|
| 299 |
/* Remove the header for block h */ |
| 300 |
GC_INNER void GC_remove_header(struct hblk *h) |
| 301 |
{ |
| 302 |
hdr **ha; |
| 303 |
GET_HDR_ADDR(h, ha); |
| 304 |
free_hdr(*ha); |
| 305 |
*ha = 0; |
| 306 |
} |
| 307 |
|
| 308 |
/* Remove forwarding counts for h */ |
| 309 |
GC_INNER void GC_remove_counts(struct hblk *h, size_t sz/* bytes */) |
| 310 |
{ |
| 311 |
struct hblk * hbp; |
| 312 |
|
| 313 |
if (sz <= HBLKSIZE) return; |
| 314 |
if (HDR(h+1) == 0) { |
| 315 |
# ifdef GC_ASSERTIONS |
| 316 |
for (hbp = h+2; (word)hbp < (word)h + sz; hbp++) |
| 317 |
GC_ASSERT(HDR(hbp) == 0); |
| 318 |
# endif |
| 319 |
return; |
| 320 |
} |
| 321 |
|
| 322 |
for (hbp = h+1; (word)hbp < (word)h + sz; hbp += 1) { |
| 323 |
SET_HDR(hbp, 0); |
| 324 |
} |
| 325 |
} |
| 326 |
|
| 327 |
/* Apply fn to all allocated blocks. It is the caller responsibility */ |
| 328 |
/* to avoid data race during the function execution (e.g. by holding */ |
| 329 |
/* the allocation lock). */ |
| 330 |
void GC_apply_to_all_blocks(void (*fn)(struct hblk *h, word client_data), |
| 331 |
word client_data) |
| 332 |
{ |
| 333 |
signed_word j; |
| 334 |
bottom_index * index_p; |
| 335 |
|
| 336 |
for (index_p = GC_all_bottom_indices; index_p != 0; |
| 337 |
index_p = index_p -> asc_link) { |
| 338 |
for (j = BOTTOM_SZ-1; j >= 0;) { |
| 339 |
if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) { |
| 340 |
if (!HBLK_IS_FREE(index_p->index[j])) { |
| 341 |
(*fn)(((struct hblk *) |
| 342 |
(((index_p->key << LOG_BOTTOM_SZ) + (word)j) |
| 343 |
<< LOG_HBLKSIZE)), |
| 344 |
client_data); |
| 345 |
} |
| 346 |
j--; |
| 347 |
} else if (index_p->index[j] == 0) { |
| 348 |
j--; |
| 349 |
} else { |
| 350 |
j -= (signed_word)(index_p->index[j]); |
| 351 |
} |
| 352 |
} |
| 353 |
} |
| 354 |
} |
| 355 |
|
| 356 |
GC_INNER struct hblk * GC_next_block(struct hblk *h, GC_bool allow_free) |
| 357 |
{ |
| 358 |
REGISTER bottom_index * bi; |
| 359 |
REGISTER word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); |
| 360 |
|
| 361 |
GC_ASSERT(I_HOLD_LOCK()); |
| 362 |
GET_BI(h, bi); |
| 363 |
if (bi == GC_all_nils) { |
| 364 |
REGISTER word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); |
| 365 |
|
| 366 |
bi = GC_all_bottom_indices; |
| 367 |
while (bi != 0 && bi -> key < hi) bi = bi -> asc_link; |
| 368 |
j = 0; |
| 369 |
} |
| 370 |
|
| 371 |
while (bi != 0) { |
| 372 |
while (j < BOTTOM_SZ) { |
| 373 |
hdr * hhdr = bi -> index[j]; |
| 374 |
if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { |
| 375 |
j++; |
| 376 |
} else { |
| 377 |
if (allow_free || !HBLK_IS_FREE(hhdr)) { |
| 378 |
return ((struct hblk *) |
| 379 |
(((bi -> key << LOG_BOTTOM_SZ) + j) |
| 380 |
<< LOG_HBLKSIZE)); |
| 381 |
} else { |
| 382 |
j += divHBLKSZ(hhdr -> hb_sz); |
| 383 |
} |
| 384 |
} |
| 385 |
} |
| 386 |
j = 0; |
| 387 |
bi = bi -> asc_link; |
| 388 |
} |
| 389 |
return(0); |
| 390 |
} |
| 391 |
|
| 392 |
GC_INNER struct hblk * GC_prev_block(struct hblk *h) |
| 393 |
{ |
| 394 |
bottom_index * bi; |
| 395 |
signed_word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); |
| 396 |
|
| 397 |
GC_ASSERT(I_HOLD_LOCK()); |
| 398 |
GET_BI(h, bi); |
| 399 |
if (bi == GC_all_nils) { |
| 400 |
word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); |
| 401 |
bi = GC_all_bottom_indices_end; |
| 402 |
while (bi != 0 && bi -> key > hi) bi = bi -> desc_link; |
| 403 |
j = BOTTOM_SZ - 1; |
| 404 |
} |
| 405 |
while(bi != 0) { |
| 406 |
while (j >= 0) { |
| 407 |
hdr * hhdr = bi -> index[j]; |
| 408 |
if (0 == hhdr) { |
| 409 |
--j; |
| 410 |
} else if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { |
| 411 |
j -= (signed_word)hhdr; |
| 412 |
} else { |
| 413 |
return((struct hblk *) |
| 414 |
(((bi -> key << LOG_BOTTOM_SZ) + j) |
| 415 |
<< LOG_HBLKSIZE)); |
| 416 |
} |
| 417 |
} |
| 418 |
j = BOTTOM_SZ - 1; |
| 419 |
bi = bi -> desc_link; |
| 420 |
} |
| 421 |
return(0); |
| 422 |
} |