Synopsis - Cross-Reference
File: /src/Synopsis/gc/headers.c1/* 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/* 17 * This implements: 18 * 1. allocation of heap block headers 19 * 2. A map from addresses to heap block addresses to heap block headers 20 * 21 * Access speed is crucial. We implement an index structure based on a 2 22 * level tree. 23 */ 24 25# include "private/gc_priv.h" 26 27bottom_index * GC_all_bottom_indices = 0; 28 /* Pointer to first (lowest addr) */ 29 /* bottom_index. */ 30 31bottom_index * GC_all_bottom_indices_end = 0; 32 /* Pointer to last (highest addr) */ 33 /* bottom_index. */ 34 35/* Non-macro version of header location routine */ 36hdr * GC_find_header(ptr_t h) 37{ 38# ifdef HASH_TL 39 hdr * result; 40 GET_HDR(h, result); 41 return(result); 42# else 43 return(HDR_INNER(h)); 44# endif 45} 46 47/* Handle a header cache miss. Returns a pointer to the */ 48/* header corresponding to p, if p can possibly be a valid */ 49/* object pointer, and 0 otherwise. */ 50/* GUARANTEED to return 0 for a pointer past the first page */ 51/* of an object unless both GC_all_interior_pointers is set */ 52/* and p is in fact a valid object pointer. */ 53#ifdef PRINT_BLACK_LIST 54 hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce, ptr_t source) 55#else 56 hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce) 57#endif 58{ 59 hdr *hhdr; 60 HC_MISS(); 61 GET_HDR(p, hhdr); 62 if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { 63 if (GC_all_interior_pointers) { 64 if (hhdr != 0) { 65 ptr_t current = p; 66 67 current = (ptr_t)HBLKPTR(current); 68 do { 69 current = current - HBLKSIZE*(word)hhdr; 70 hhdr = HDR(current); 71 } while(IS_FORWARDING_ADDR_OR_NIL(hhdr)); 72 /* current points to near the start of the large object */ 73 if (hhdr -> hb_flags & IGNORE_OFF_PAGE 74 || HBLK_IS_FREE(hhdr)) 75 return 0; 76 if (p - current >= (ptrdiff_t)(hhdr->hb_sz)) { 77 GC_ADD_TO_BLACK_LIST_NORMAL(p, source); 78 /* Pointer past the end of the block */ 79 return 0; 80 } 81 } else { 82 GC_ADD_TO_BLACK_LIST_NORMAL(p, source); 83 } 84 return hhdr; 85 /* Pointers past the first page are probably too rare */ 86 /* to add them to the cache. We don't. */ 87 /* And correctness relies on the fact that we don't. */ 88 } else { 89 if (hhdr == 0) { 90 GC_ADD_TO_BLACK_LIST_NORMAL(p, source); 91 } 92 return 0; 93 } 94 } else { 95 if (HBLK_IS_FREE(hhdr)) { 96 GC_ADD_TO_BLACK_LIST_NORMAL(p, source); 97 return 0; 98 } else { 99 hce -> block_addr = (word)(p) >> LOG_HBLKSIZE; 100 hce -> hce_hdr = hhdr; 101 return hhdr; 102 } 103 } 104} 105 106/* Routines to dynamically allocate collector data structures that will */ 107/* never be freed. */ 108 109static ptr_t scratch_free_ptr = 0; 110 111/* GC_scratch_last_end_ptr is end point of last obtained scratch area. */ 112/* GC_scratch_end_ptr is end point of current scratch area. */ 113 114ptr_t GC_scratch_alloc(size_t bytes) 115{ 116 register ptr_t result = scratch_free_ptr; 117 118 bytes += GRANULE_BYTES-1; 119 bytes &= ~(GRANULE_BYTES-1); 120 scratch_free_ptr += bytes; 121 if (scratch_free_ptr <= GC_scratch_end_ptr) { 122 return(result); 123 } 124 { 125 word bytes_to_get = MINHINCR * HBLKSIZE; 126 127 if (bytes_to_get <= bytes) { 128 /* Undo the damage, and get memory directly */ 129 bytes_to_get = bytes; 130# ifdef USE_MMAP 131 bytes_to_get += GC_page_size - 1; 132 bytes_to_get &= ~(GC_page_size - 1); 133# endif 134 result = (ptr_t)GET_MEM(bytes_to_get); 135 scratch_free_ptr -= bytes; 136 GC_scratch_last_end_ptr = result + bytes; 137 return(result); 138 } 139 result = (ptr_t)GET_MEM(bytes_to_get); 140 if (result == 0) { 141 if (GC_print_stats) 142 GC_printf("Out of memory - trying to allocate less\n"); 143 scratch_free_ptr -= bytes; 144 bytes_to_get = bytes; 145# ifdef USE_MMAP 146 bytes_to_get += GC_page_size - 1; 147 bytes_to_get &= ~(GC_page_size - 1); 148# endif 149 return((ptr_t)GET_MEM(bytes_to_get)); 150 } 151 scratch_free_ptr = result; 152 GC_scratch_end_ptr = scratch_free_ptr + bytes_to_get; 153 GC_scratch_last_end_ptr = GC_scratch_end_ptr; 154 return(GC_scratch_alloc(bytes)); 155 } 156} 157 158static hdr * hdr_free_list = 0; 159 160/* Return an uninitialized header */ 161static hdr * alloc_hdr(void) 162{ 163 register hdr * result; 164 165 if (hdr_free_list == 0) { 166 result = (hdr *) GC_scratch_alloc((word)(sizeof(hdr))); 167 } else { 168 result = hdr_free_list; 169 hdr_free_list = (hdr *) (result -> hb_next); 170 } 171 return(result); 172} 173 174static void free_hdr(hdr * hhdr) 175{ 176 hhdr -> hb_next = (struct hblk *) hdr_free_list; 177 hdr_free_list = hhdr; 178} 179 180#ifdef USE_HDR_CACHE 181 word GC_hdr_cache_hits = 0; 182 word GC_hdr_cache_misses = 0; 183#endif 184 185void GC_init_headers(void) 186{ 187 register unsigned i; 188 189 GC_all_nils = (bottom_index *)GC_scratch_alloc((word)sizeof(bottom_index)); 190 BZERO(GC_all_nils, sizeof(bottom_index)); 191 for (i = 0; i < TOP_SZ; i++) { 192 GC_top_index[i] = GC_all_nils; 193 } 194} 195 196/* Make sure that there is a bottom level index block for address addr */ 197/* Return FALSE on failure. */ 198static GC_bool get_index(word addr) 199{ 200 word hi = (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); 201 bottom_index * r; 202 bottom_index * p; 203 bottom_index ** prev; 204 bottom_index *pi; 205 206# ifdef HASH_TL 207 word i = TL_HASH(hi); 208 bottom_index * old; 209 210 old = p = GC_top_index[i]; 211 while(p != GC_all_nils) { 212 if (p -> key == hi) return(TRUE); 213 p = p -> hash_link; 214 } 215 r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index))); 216 if (r == 0) return(FALSE); 217 BZERO(r, sizeof (bottom_index)); 218 r -> hash_link = old; 219 GC_top_index[i] = r; 220# else 221 if (GC_top_index[hi] != GC_all_nils) return(TRUE); 222 r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index))); 223 if (r == 0) return(FALSE); 224 GC_top_index[hi] = r; 225 BZERO(r, sizeof (bottom_index)); 226# endif 227 r -> key = hi; 228 /* Add it to the list of bottom indices */ 229 prev = &GC_all_bottom_indices; /* pointer to p */ 230 pi = 0; /* bottom_index preceding p */ 231 while ((p = *prev) != 0 && p -> key < hi) { 232 pi = p; 233 prev = &(p -> asc_link); 234 } 235 r -> desc_link = pi; 236 if (0 == p) { 237 GC_all_bottom_indices_end = r; 238 } else { 239 p -> desc_link = r; 240 } 241 r -> asc_link = p; 242 *prev = r; 243 return(TRUE); 244} 245 246/* Install a header for block h. */ 247/* The header is uninitialized. */ 248/* Returns the header or 0 on failure. */ 249struct hblkhdr * GC_install_header(struct hblk *h) 250{ 251 hdr * result; 252 253 if (!get_index((word) h)) return(0); 254 result = alloc_hdr(); 255 SET_HDR(h, result); 256# ifdef USE_MUNMAP 257 result -> hb_last_reclaimed = (unsigned short)GC_gc_no; 258# endif 259 return(result); 260} 261 262/* Set up forwarding counts for block h of size sz */ 263GC_bool GC_install_counts(struct hblk *h, size_t sz/* bytes */) 264{ 265 struct hblk * hbp; 266 word i; 267 268 for (hbp = h; (char *)hbp < (char *)h + sz; hbp += BOTTOM_SZ) { 269 if (!get_index((word) hbp)) return(FALSE); 270 } 271 if (!get_index((word)h + sz - 1)) return(FALSE); 272 for (hbp = h + 1; (char *)hbp < (char *)h + sz; hbp += 1) { 273 i = HBLK_PTR_DIFF(hbp, h); 274 SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i)); 275 } 276 return(TRUE); 277} 278 279/* Remove the header for block h */ 280void GC_remove_header(struct hblk *h) 281{ 282 hdr ** ha; 283 284 GET_HDR_ADDR(h, ha); 285 free_hdr(*ha); 286 *ha = 0; 287} 288 289/* Remove forwarding counts for h */ 290void GC_remove_counts(struct hblk *h, size_t sz/* bytes */) 291{ 292 register struct hblk * hbp; 293 294 for (hbp = h+1; (char *)hbp < (char *)h + sz; hbp += 1) { 295 SET_HDR(hbp, 0); 296 } 297} 298 299/* Apply fn to all allocated blocks */ 300/*VARARGS1*/ 301void GC_apply_to_all_blocks(void (*fn)(struct hblk *h, word client_data), 302 word client_data) 303{ 304 signed_word j; 305 bottom_index * index_p; 306 307 for (index_p = GC_all_bottom_indices; index_p != 0; 308 index_p = index_p -> asc_link) { 309 for (j = BOTTOM_SZ-1; j >= 0;) { 310 if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) { 311 if (!HBLK_IS_FREE(index_p->index[j])) { 312 (*fn)(((struct hblk *) 313 (((index_p->key << LOG_BOTTOM_SZ) + (word)j) 314 << LOG_HBLKSIZE)), 315 client_data); 316 } 317 j--; 318 } else if (index_p->index[j] == 0) { 319 j--; 320 } else { 321 j -= (signed_word)(index_p->index[j]); 322 } 323 } 324 } 325} 326 327/* Get the next valid block whose address is at least h */ 328/* Return 0 if there is none. */ 329struct hblk * GC_next_used_block(struct hblk *h) 330{ 331 register bottom_index * bi; 332 register word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); 333 334 GET_BI(h, bi); 335 if (bi == GC_all_nils) { 336 register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); 337 bi = GC_all_bottom_indices; 338 while (bi != 0 && bi -> key < hi) bi = bi -> asc_link; 339 j = 0; 340 } 341 while(bi != 0) { 342 while (j < BOTTOM_SZ) { 343 hdr * hhdr = bi -> index[j]; 344 if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { 345 j++; 346 } else { 347 if (!HBLK_IS_FREE(hhdr)) { 348 return((struct hblk *) 349 (((bi -> key << LOG_BOTTOM_SZ) + j) 350 << LOG_HBLKSIZE)); 351 } else { 352 j += divHBLKSZ(hhdr -> hb_sz); 353 } 354 } 355 } 356 j = 0; 357 bi = bi -> asc_link; 358 } 359 return(0); 360} 361 362/* Get the last (highest address) block whose address is */ 363/* at most h. Return 0 if there is none. */ 364/* Unlike the above, this may return a free block. */ 365struct hblk * GC_prev_block(struct hblk *h) 366{ 367 register bottom_index * bi; 368 register signed_word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); 369 370 GET_BI(h, bi); 371 if (bi == GC_all_nils) { 372 register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); 373 bi = GC_all_bottom_indices_end; 374 while (bi != 0 && bi -> key > hi) bi = bi -> desc_link; 375 j = BOTTOM_SZ - 1; 376 } 377 while(bi != 0) { 378 while (j >= 0) { 379 hdr * hhdr = bi -> index[j]; 380 if (0 == hhdr) { 381 --j; 382 } else if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { 383 j -= (signed_word)hhdr; 384 } else { 385 return((struct hblk *) 386 (((bi -> key << LOG_BOTTOM_SZ) + j) 387 << LOG_HBLKSIZE)); 388 } 389 } 390 j = BOTTOM_SZ - 1; 391 bi = bi -> desc_link; 392 } 393 return(0); 394}