Annotation of OpenXM_contrib/gc/allchblk.c, Revision 1.1.1.2
1.1 maekawa 1: /*
2: * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3: * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
1.1.1.2 ! maekawa 4: * Copyright (c) 1998-1999 by Silicon Graphics. All rights reserved.
! 5: * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved.
1.1 maekawa 6: *
7: * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8: * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
9: *
10: * Permission is hereby granted to use or copy this program
11: * for any purpose, provided the above notices are retained on all copies.
12: * Permission to modify the code and to distribute modified code is granted,
13: * provided the above notices are retained, and a notice that the code was
14: * modified is included with the above copyright notice.
15: */
16:
17: #define DEBUG
18: #undef DEBUG
19: #include <stdio.h>
20: #include "gc_priv.h"
21:
22:
23: /*
1.1.1.2 ! maekawa 24: * Free heap blocks are kept on one of several free lists,
! 25: * depending on the size of the block. Each free list is doubly linked.
! 26: * Adjacent free blocks are coalesced.
1.1 maekawa 27: */
28:
29:
30: # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
31: /* largest block we will allocate starting on a black */
32: /* listed block. Must be >= HBLKSIZE. */
33:
34:
1.1.1.2 ! maekawa 35: # define UNIQUE_THRESHOLD 32
! 36: /* Sizes up to this many HBLKs each have their own free list */
! 37: # define HUGE_THRESHOLD 256
! 38: /* Sizes of at least this many heap blocks are mapped to a */
! 39: /* single free list. */
! 40: # define FL_COMPRESSION 8
! 41: /* In between sizes map this many distinct sizes to a single */
! 42: /* bin. */
! 43:
! 44: # define N_HBLK_FLS (HUGE_THRESHOLD - UNIQUE_THRESHOLD)/FL_COMPRESSION \
! 45: + UNIQUE_THRESHOLD
! 46:
! 47: struct hblk * GC_hblkfreelist[N_HBLK_FLS+1] = { 0 };
! 48:
! 49: /* Map a number of blocks to the appropriate large block free list index. */
! 50: int GC_hblk_fl_from_blocks(blocks_needed)
! 51: word blocks_needed;
! 52: {
! 53: if (blocks_needed <= UNIQUE_THRESHOLD) return blocks_needed;
! 54: if (blocks_needed >= HUGE_THRESHOLD) return N_HBLK_FLS;
! 55: return (blocks_needed - UNIQUE_THRESHOLD)/FL_COMPRESSION
! 56: + UNIQUE_THRESHOLD;
! 57:
! 58: }
! 59:
! 60: # define HBLK_IS_FREE(hdr) ((hdr) -> hb_map == GC_invalid_map)
! 61: # define PHDR(hhdr) HDR(hhdr -> hb_prev)
! 62: # define NHDR(hhdr) HDR(hhdr -> hb_next)
! 63:
! 64: # ifdef USE_MUNMAP
! 65: # define IS_MAPPED(hhdr) (((hhdr) -> hb_flags & WAS_UNMAPPED) == 0)
! 66: # else /* !USE_MMAP */
! 67: # define IS_MAPPED(hhdr) 1
! 68: # endif /* USE_MUNMAP */
1.1 maekawa 69:
70: # if !defined(NO_DEBUGGING)
71: void GC_print_hblkfreelist()
72: {
1.1.1.2 ! maekawa 73: struct hblk * h;
1.1 maekawa 74: word total_free = 0;
1.1.1.2 ! maekawa 75: hdr * hhdr;
1.1 maekawa 76: word sz;
1.1.1.2 ! maekawa 77: int i;
1.1 maekawa 78:
1.1.1.2 ! maekawa 79: for (i = 0; i <= N_HBLK_FLS; ++i) {
! 80: h = GC_hblkfreelist[i];
! 81: if (0 != h) GC_printf1("Free list %ld:\n", (unsigned long)i);
! 82: while (h != 0) {
! 83: hhdr = HDR(h);
1.1 maekawa 84: sz = hhdr -> hb_sz;
1.1.1.2 ! maekawa 85: GC_printf2("\t0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
1.1 maekawa 86: total_free += sz;
87: if (GC_is_black_listed(h, HBLKSIZE) != 0) {
88: GC_printf0("start black listed\n");
89: } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
90: GC_printf0("partially black listed\n");
91: } else {
92: GC_printf0("not black listed\n");
93: }
94: h = hhdr -> hb_next;
1.1.1.2 ! maekawa 95: }
! 96: }
! 97: if (total_free != GC_large_free_bytes) {
! 98: GC_printf1("GC_large_free_bytes = %lu (INCONSISTENT!!)\n",
! 99: (unsigned long) GC_large_free_bytes);
1.1 maekawa 100: }
101: GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
102: }
103:
1.1.1.2 ! maekawa 104: /* Return the free list index on which the block described by the header */
! 105: /* appears, or -1 if it appears nowhere. */
! 106: int free_list_index_of(wanted)
! 107: hdr * wanted;
! 108: {
! 109: struct hblk * h;
! 110: hdr * hhdr;
! 111: int i;
! 112:
! 113: for (i = 0; i <= N_HBLK_FLS; ++i) {
! 114: h = GC_hblkfreelist[i];
! 115: while (h != 0) {
! 116: hhdr = HDR(h);
! 117: if (hhdr == wanted) return i;
! 118: h = hhdr -> hb_next;
! 119: }
! 120: }
! 121: return -1;
! 122: }
! 123:
! 124: void GC_dump_regions()
! 125: {
! 126: unsigned i;
! 127: ptr_t start, end;
! 128: ptr_t p;
! 129: size_t bytes;
! 130: hdr *hhdr;
! 131: for (i = 0; i < GC_n_heap_sects; ++i) {
! 132: start = GC_heap_sects[i].hs_start;
! 133: bytes = GC_heap_sects[i].hs_bytes;
! 134: end = start + bytes;
! 135: /* Merge in contiguous sections. */
! 136: while (i+1 < GC_n_heap_sects && GC_heap_sects[i+1].hs_start == end) {
! 137: ++i;
! 138: end = GC_heap_sects[i].hs_start + GC_heap_sects[i].hs_bytes;
! 139: }
! 140: GC_printf2("***Section from 0x%lx to 0x%lx\n", start, end);
! 141: for (p = start; p < end;) {
! 142: hhdr = HDR(p);
! 143: GC_printf1("\t0x%lx ", (unsigned long)p);
! 144: if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
! 145: GC_printf1("Missing header!!\n", hhdr);
! 146: p += HBLKSIZE;
! 147: continue;
! 148: }
! 149: if (HBLK_IS_FREE(hhdr)) {
! 150: int correct_index = GC_hblk_fl_from_blocks(
! 151: divHBLKSZ(hhdr -> hb_sz));
! 152: int actual_index;
! 153:
! 154: GC_printf1("\tfree block of size 0x%lx bytes",
! 155: (unsigned long)(hhdr -> hb_sz));
! 156: if (IS_MAPPED(hhdr)) {
! 157: GC_printf0("\n");
! 158: } else {
! 159: GC_printf0("(unmapped)\n");
! 160: }
! 161: actual_index = free_list_index_of(hhdr);
! 162: if (-1 == actual_index) {
! 163: GC_printf1("\t\tBlock not on free list %ld!!\n",
! 164: correct_index);
! 165: } else if (correct_index != actual_index) {
! 166: GC_printf2("\t\tBlock on list %ld, should be on %ld!!\n",
! 167: actual_index, correct_index);
! 168: }
! 169: p += hhdr -> hb_sz;
! 170: } else {
! 171: GC_printf1("\tused for blocks of size 0x%lx bytes\n",
! 172: (unsigned long)WORDS_TO_BYTES(hhdr -> hb_sz));
! 173: p += HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
! 174: }
! 175: }
! 176: }
! 177: }
! 178:
1.1 maekawa 179: # endif /* NO_DEBUGGING */
180:
181: /* Initialize hdr for a block containing the indicated size and */
182: /* kind of objects. */
183: /* Return FALSE on failure. */
184: static GC_bool setup_header(hhdr, sz, kind, flags)
185: register hdr * hhdr;
186: word sz; /* object size in words */
187: int kind;
188: unsigned char flags;
189: {
190: register word descr;
191:
192: /* Add description of valid object pointers */
193: if (!GC_add_map_entry(sz)) return(FALSE);
194: hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
195:
196: /* Set size, kind and mark proc fields */
197: hhdr -> hb_sz = sz;
198: hhdr -> hb_obj_kind = kind;
199: hhdr -> hb_flags = flags;
200: descr = GC_obj_kinds[kind].ok_descriptor;
201: if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
202: hhdr -> hb_descr = descr;
203:
204: /* Clear mark bits */
205: GC_clear_hdr_marks(hhdr);
206:
207: hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
208: return(TRUE);
209: }
210:
1.1.1.2 ! maekawa 211: #define FL_UNKNOWN -1
! 212: /*
! 213: * Remove hhdr from the appropriate free list.
! 214: * We assume it is on the nth free list, or on the size
! 215: * appropriate free list if n is FL_UNKNOWN.
! 216: */
! 217: void GC_remove_from_fl(hhdr, n)
! 218: hdr * hhdr;
! 219: int n;
! 220: {
! 221: GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
! 222: if (hhdr -> hb_prev == 0) {
! 223: int index;
! 224: if (FL_UNKNOWN == n) {
! 225: index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
! 226: } else {
! 227: index = n;
! 228: }
! 229: GC_ASSERT(HDR(GC_hblkfreelist[index]) == hhdr);
! 230: GC_hblkfreelist[index] = hhdr -> hb_next;
! 231: } else {
! 232: PHDR(hhdr) -> hb_next = hhdr -> hb_next;
! 233: }
! 234: if (0 != hhdr -> hb_next) {
! 235: GC_ASSERT(!IS_FORWARDING_ADDR_OR_NIL(NHDR(hhdr)));
! 236: NHDR(hhdr) -> hb_prev = hhdr -> hb_prev;
! 237: }
! 238: }
! 239:
! 240: /*
! 241: * Return a pointer to the free block ending just before h, if any.
! 242: */
! 243: struct hblk * GC_free_block_ending_at(h)
! 244: struct hblk *h;
! 245: {
! 246: struct hblk * p = h - 1;
! 247: hdr * phdr = HDR(p);
! 248:
! 249: while (0 != phdr && IS_FORWARDING_ADDR_OR_NIL(phdr)) {
! 250: p = FORWARDED_ADDR(p,phdr);
! 251: phdr = HDR(p);
! 252: }
! 253: if (0 != phdr && HBLK_IS_FREE(phdr)) return p;
! 254: p = GC_prev_block(h - 1);
! 255: if (0 != p) {
! 256: phdr = HDR(p);
! 257: if (HBLK_IS_FREE(phdr) && (ptr_t)p + phdr -> hb_sz == (ptr_t)h) {
! 258: return p;
! 259: }
! 260: }
! 261: return 0;
! 262: }
! 263:
! 264: /*
! 265: * Add hhdr to the appropriate free list.
! 266: * We maintain individual free lists sorted by address.
! 267: */
! 268: void GC_add_to_fl(h, hhdr)
! 269: struct hblk *h;
! 270: hdr * hhdr;
! 271: {
! 272: int index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
! 273: struct hblk *second = GC_hblkfreelist[index];
! 274: # ifdef GC_ASSERTIONS
! 275: struct hblk *next = (struct hblk *)((word)h + hhdr -> hb_sz);
! 276: hdr * nexthdr = HDR(next);
! 277: struct hblk *prev = GC_free_block_ending_at(h);
! 278: hdr * prevhdr = HDR(prev);
! 279: GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr) || !IS_MAPPED(nexthdr));
! 280: GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr) || !IS_MAPPED(prevhdr));
! 281: # endif
! 282: GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
! 283: GC_hblkfreelist[index] = h;
! 284: hhdr -> hb_next = second;
! 285: hhdr -> hb_prev = 0;
! 286: if (0 != second) HDR(second) -> hb_prev = h;
! 287: GC_invalidate_map(hhdr);
! 288: }
! 289:
! 290: #ifdef USE_MUNMAP
1.1 maekawa 291:
1.1.1.2 ! maekawa 292: /* Unmap blocks that haven't been recently touched. This is the only way */
! 293: /* way blocks are ever unmapped. */
! 294: void GC_unmap_old(void)
! 295: {
! 296: struct hblk * h;
! 297: hdr * hhdr;
! 298: word sz;
! 299: unsigned short last_rec, threshold;
! 300: int i;
! 301: # define UNMAP_THRESHOLD 6
! 302:
! 303: for (i = 0; i <= N_HBLK_FLS; ++i) {
! 304: for (h = GC_hblkfreelist[i]; 0 != h; h = hhdr -> hb_next) {
! 305: hhdr = HDR(h);
! 306: if (!IS_MAPPED(hhdr)) continue;
! 307: threshold = (unsigned short)(GC_gc_no - UNMAP_THRESHOLD);
! 308: last_rec = hhdr -> hb_last_reclaimed;
! 309: if (last_rec > GC_gc_no
! 310: || last_rec < threshold && threshold < GC_gc_no
! 311: /* not recently wrapped */) {
! 312: sz = hhdr -> hb_sz;
! 313: GC_unmap((ptr_t)h, sz);
! 314: hhdr -> hb_flags |= WAS_UNMAPPED;
! 315: }
! 316: }
! 317: }
! 318: }
! 319:
! 320: /* Merge all unmapped blocks that are adjacent to other free */
! 321: /* blocks. This may involve remapping, since all blocks are either */
! 322: /* fully mapped or fully unmapped. */
! 323: void GC_merge_unmapped(void)
! 324: {
! 325: struct hblk * h, *next;
! 326: hdr * hhdr, *nexthdr;
! 327: word size, nextsize;
! 328: int i;
! 329:
! 330: for (i = 0; i <= N_HBLK_FLS; ++i) {
! 331: h = GC_hblkfreelist[i];
! 332: while (h != 0) {
! 333: hhdr = HDR(h);
! 334: size = hhdr->hb_sz;
! 335: next = (struct hblk *)((word)h + size);
! 336: nexthdr = HDR(next);
! 337: /* Coalesce with successor, if possible */
! 338: if (0 != nexthdr && HBLK_IS_FREE(nexthdr)) {
! 339: nextsize = nexthdr -> hb_sz;
! 340: if (IS_MAPPED(hhdr)) {
! 341: GC_ASSERT(!IS_MAPPED(nexthdr));
! 342: /* make both consistent, so that we can merge */
! 343: if (size > nextsize) {
! 344: GC_remap((ptr_t)next, nextsize);
! 345: } else {
! 346: GC_unmap((ptr_t)h, size);
! 347: hhdr -> hb_flags |= WAS_UNMAPPED;
! 348: }
! 349: } else if (IS_MAPPED(nexthdr)) {
! 350: GC_ASSERT(!IS_MAPPED(hhdr));
! 351: if (size > nextsize) {
! 352: GC_unmap((ptr_t)next, nextsize);
! 353: } else {
! 354: GC_remap((ptr_t)h, size);
! 355: hhdr -> hb_flags &= ~WAS_UNMAPPED;
! 356: }
! 357: } else {
! 358: /* Unmap any gap in the middle */
! 359: GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nexthdr -> hb_sz);
! 360: }
! 361: /* If they are both unmapped, we merge, but leave unmapped. */
! 362: GC_remove_from_fl(hhdr, i);
! 363: GC_remove_from_fl(nexthdr, FL_UNKNOWN);
! 364: hhdr -> hb_sz += nexthdr -> hb_sz;
! 365: GC_remove_header(next);
! 366: GC_add_to_fl(h, hhdr);
! 367: /* Start over at beginning of list */
! 368: h = GC_hblkfreelist[i];
! 369: } else /* not mergable with successor */ {
! 370: h = hhdr -> hb_next;
! 371: }
! 372: } /* while (h != 0) ... */
! 373: } /* for ... */
! 374: }
! 375:
! 376: #endif /* USE_MUNMAP */
! 377:
! 378: /*
! 379: * Return a pointer to a block starting at h of length bytes.
! 380: * Memory for the block is mapped.
! 381: * Remove the block from its free list, and return the remainder (if any)
! 382: * to its appropriate free list.
! 383: * May fail by returning 0.
! 384: * The header for the returned block must be set up by the caller.
! 385: * If the return value is not 0, then hhdr is the header for it.
! 386: */
! 387: struct hblk * GC_get_first_part(h, hhdr, bytes, index)
! 388: struct hblk *h;
! 389: hdr * hhdr;
! 390: word bytes;
! 391: int index;
! 392: {
! 393: word total_size = hhdr -> hb_sz;
! 394: struct hblk * rest;
! 395: hdr * rest_hdr;
! 396:
! 397: GC_ASSERT((total_size & (HBLKSIZE-1)) == 0);
! 398: GC_remove_from_fl(hhdr, index);
! 399: if (total_size == bytes) return h;
! 400: rest = (struct hblk *)((word)h + bytes);
! 401: if (!GC_install_header(rest)) return(0);
! 402: rest_hdr = HDR(rest);
! 403: rest_hdr -> hb_sz = total_size - bytes;
! 404: rest_hdr -> hb_flags = 0;
! 405: # ifdef GC_ASSERTIONS
! 406: // Mark h not free, to avoid assertion about adjacent free blocks.
! 407: hhdr -> hb_map = 0;
! 408: # endif
! 409: GC_add_to_fl(rest, rest_hdr);
! 410: return h;
! 411: }
! 412:
! 413: /*
! 414: * H is a free block. N points at an address inside it.
! 415: * A new header for n has already been set up. Fix up h's header
! 416: * to reflect the fact that it is being split, move it to the
! 417: * appropriate free list.
! 418: * N replaces h in the original free list.
! 419: *
! 420: * Nhdr is not completely filled in, since it is about to allocated.
! 421: * It may in fact end up on the wrong free list for its size.
! 422: * (Hence adding it to a free list is silly. But this path is hopefully
! 423: * rare enough that it doesn't matter. The code is cleaner this way.)
! 424: */
! 425: void GC_split_block(h, hhdr, n, nhdr, index)
! 426: struct hblk *h;
! 427: hdr * hhdr;
! 428: struct hblk *n;
! 429: hdr * nhdr;
! 430: int index; /* Index of free list */
! 431: {
! 432: word total_size = hhdr -> hb_sz;
! 433: word h_size = (word)n - (word)h;
! 434: struct hblk *prev = hhdr -> hb_prev;
! 435: struct hblk *next = hhdr -> hb_next;
! 436:
! 437: /* Replace h with n on its freelist */
! 438: nhdr -> hb_prev = prev;
! 439: nhdr -> hb_next = next;
! 440: nhdr -> hb_sz = total_size - h_size;
! 441: nhdr -> hb_flags = 0;
! 442: if (0 != prev) {
! 443: HDR(prev) -> hb_next = n;
! 444: } else {
! 445: GC_hblkfreelist[index] = n;
! 446: }
! 447: if (0 != next) {
! 448: HDR(next) -> hb_prev = n;
! 449: }
! 450: # ifdef GC_ASSERTIONS
! 451: nhdr -> hb_map = 0; /* Don't fail test for consecutive */
! 452: /* free blocks in GC_add_to_fl. */
! 453: # endif
! 454: # ifdef USE_MUNMAP
! 455: hhdr -> hb_last_reclaimed = GC_gc_no;
! 456: # endif
! 457: hhdr -> hb_sz = h_size;
! 458: GC_add_to_fl(h, hhdr);
! 459: GC_invalidate_map(nhdr);
! 460: }
1.1 maekawa 461:
1.1.1.2 ! maekawa 462: struct hblk * GC_allochblk_nth();
! 463:
1.1 maekawa 464: /*
465: * Allocate (and return pointer to) a heap block
1.1.1.2 ! maekawa 466: * for objects of size sz words, searching the nth free list.
1.1 maekawa 467: *
468: * NOTE: We set obj_map field in header correctly.
1.1.1.2 ! maekawa 469: * Caller is responsible for building an object freelist in block.
1.1 maekawa 470: *
471: * We clear the block if it is destined for large objects, and if
472: * kind requires that newly allocated objects be cleared.
473: */
474: struct hblk *
475: GC_allochblk(sz, kind, flags)
476: word sz;
477: int kind;
478: unsigned char flags; /* IGNORE_OFF_PAGE or 0 */
479: {
1.1.1.2 ! maekawa 480: int start_list = GC_hblk_fl_from_blocks(OBJ_SZ_TO_BLOCKS(sz));
! 481: int i;
! 482: for (i = start_list; i <= N_HBLK_FLS; ++i) {
! 483: struct hblk * result = GC_allochblk_nth(sz, kind, flags, i);
! 484: if (0 != result) return result;
! 485: }
! 486: return 0;
! 487: }
! 488: /*
! 489: * The same, but with search restricted to nth free list.
! 490: */
! 491: struct hblk *
! 492: GC_allochblk_nth(sz, kind, flags, n)
! 493: word sz;
! 494: int kind;
! 495: unsigned char flags; /* IGNORE_OFF_PAGE or 0 */
! 496: int n;
! 497: {
1.1 maekawa 498: register struct hblk *hbp;
499: register hdr * hhdr; /* Header corr. to hbp */
1.1.1.2 ! maekawa 500: register struct hblk *thishbp;
! 501: register hdr * thishdr; /* Header corr. to hbp */
1.1 maekawa 502: signed_word size_needed; /* number of bytes in requested objects */
503: signed_word size_avail; /* bytes available in this block */
504:
505: size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
506:
507: /* search for a big enough block in free list */
1.1.1.2 ! maekawa 508: hbp = GC_hblkfreelist[n];
1.1 maekawa 509: hhdr = HDR(hbp);
1.1.1.2 ! maekawa 510: for(; 0 != hbp; hbp = hhdr -> hb_next, hhdr = HDR(hbp)) {
1.1 maekawa 511: size_avail = hhdr->hb_sz;
512: if (size_avail < size_needed) continue;
513: # ifdef PRESERVE_LAST
514: if (size_avail != size_needed
1.1.1.2 ! maekawa 515: && !GC_incremental && GC_should_collect()) {
1.1 maekawa 516: continue;
517: }
518: # endif
519: /* If the next heap block is obviously better, go on. */
520: /* This prevents us from disassembling a single large block */
521: /* to get tiny blocks. */
522: {
523: signed_word next_size;
524:
525: thishbp = hhdr -> hb_next;
1.1.1.2 ! maekawa 526: if (thishbp != 0) {
! 527: thishdr = HDR(thishbp);
! 528: next_size = (signed_word)(thishdr -> hb_sz);
! 529: if (next_size < size_avail
1.1 maekawa 530: && next_size >= size_needed
531: && !GC_is_black_listed(thishbp, (word)size_needed)) {
532: continue;
1.1.1.2 ! maekawa 533: }
1.1 maekawa 534: }
535: }
536: if ( !IS_UNCOLLECTABLE(kind) &&
537: (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
538: struct hblk * lasthbp = hbp;
539: ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
540: signed_word orig_avail = size_avail;
541: signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
542: HBLKSIZE
543: : size_needed);
544:
545:
546: while ((ptr_t)lasthbp <= search_end
547: && (thishbp = GC_is_black_listed(lasthbp,
548: (word)eff_size_needed))) {
549: lasthbp = thishbp;
550: }
551: size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
552: thishbp = lasthbp;
553: if (size_avail >= size_needed) {
554: if (thishbp != hbp && GC_install_header(thishbp)) {
1.1.1.2 ! maekawa 555: /* Make sure it's mapped before we mangle it. */
! 556: # ifdef USE_MUNMAP
! 557: if (!IS_MAPPED(hhdr)) {
! 558: GC_remap((ptr_t)hbp, size_avail);
! 559: hhdr -> hb_flags &= ~WAS_UNMAPPED;
! 560: }
! 561: # endif
1.1 maekawa 562: /* Split the block at thishbp */
563: thishdr = HDR(thishbp);
1.1.1.2 ! maekawa 564: GC_split_block(hbp, hhdr, thishbp, thishdr, n);
1.1 maekawa 565: /* Advance to thishbp */
566: hbp = thishbp;
567: hhdr = thishdr;
1.1.1.2 ! maekawa 568: /* We must now allocate thishbp, since it may */
! 569: /* be on the wrong free list. */
1.1 maekawa 570: }
571: } else if (size_needed > (signed_word)BL_LIMIT
572: && orig_avail - size_needed
573: > (signed_word)BL_LIMIT) {
574: /* Punt, since anything else risks unreasonable heap growth. */
575: WARN("Needed to allocate blacklisted block at 0x%lx\n",
576: (word)hbp);
577: size_avail = orig_avail;
1.1.1.2 ! maekawa 578: } else if (size_avail == 0 && size_needed == HBLKSIZE
! 579: && IS_MAPPED(hhdr)) {
! 580: if (!GC_find_leak) {
1.1 maekawa 581: static unsigned count = 0;
582:
583: /* The block is completely blacklisted. We need */
584: /* to drop some such blocks, since otherwise we spend */
585: /* all our time traversing them if pointerfree */
586: /* blocks are unpopular. */
587: /* A dropped block will be reconsidered at next GC. */
588: if ((++count & 3) == 0) {
589: /* Allocate and drop the block in small chunks, to */
590: /* maximize the chance that we will recover some */
591: /* later. */
1.1.1.2 ! maekawa 592: word total_size = hhdr -> hb_sz;
! 593: struct hblk * limit = hbp + divHBLKSZ(total_size);
1.1 maekawa 594: struct hblk * h;
1.1.1.2 ! maekawa 595: struct hblk * prev = hhdr -> hb_prev;
1.1 maekawa 596:
1.1.1.2 ! maekawa 597: GC_words_wasted += total_size;
! 598: GC_large_free_bytes -= total_size;
! 599: GC_remove_from_fl(hhdr, n);
1.1 maekawa 600: for (h = hbp; h < limit; h++) {
601: if (h == hbp || GC_install_header(h)) {
602: hhdr = HDR(h);
603: (void) setup_header(
604: hhdr,
605: BYTES_TO_WORDS(HBLKSIZE - HDR_BYTES),
606: PTRFREE, 0); /* Cant fail */
607: if (GC_debugging_started) {
1.1.1.2 ! maekawa 608: BZERO(h + HDR_BYTES, HBLKSIZE - HDR_BYTES);
1.1 maekawa 609: }
610: }
611: }
612: /* Restore hbp to point at free block */
1.1.1.2 ! maekawa 613: hbp = prev;
! 614: if (0 == hbp) {
! 615: return GC_allochblk_nth(sz, kind, flags, n);
! 616: }
! 617: hhdr = HDR(hbp);
1.1 maekawa 618: }
1.1.1.2 ! maekawa 619: }
1.1 maekawa 620: }
621: }
622: if( size_avail >= size_needed ) {
1.1.1.2 ! maekawa 623: # ifdef USE_MUNMAP
! 624: if (!IS_MAPPED(hhdr)) {
! 625: GC_remap((ptr_t)hbp, size_avail);
! 626: hhdr -> hb_flags &= ~WAS_UNMAPPED;
! 627: }
! 628: # endif
! 629: /* hbp may be on the wrong freelist; the parameter n */
! 630: /* is important. */
! 631: hbp = GC_get_first_part(hbp, hhdr, size_needed, n);
1.1 maekawa 632: break;
633: }
634: }
1.1.1.2 ! maekawa 635:
! 636: if (0 == hbp) return 0;
1.1 maekawa 637:
638: /* Notify virtual dirty bit implementation that we are about to write. */
1.1.1.2 ! maekawa 639: GC_write_hint(hbp);
1.1 maekawa 640:
641: /* Add it to map of valid blocks */
1.1.1.2 ! maekawa 642: if (!GC_install_counts(hbp, (word)size_needed)) return(0);
1.1 maekawa 643: /* This leaks memory under very rare conditions. */
644:
645: /* Set up header */
1.1.1.2 ! maekawa 646: if (!setup_header(hhdr, sz, kind, flags)) {
! 647: GC_remove_counts(hbp, (word)size_needed);
1.1 maekawa 648: return(0); /* ditto */
649: }
650:
651: /* Clear block if necessary */
652: if (GC_debugging_started
653: || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
1.1.1.2 ! maekawa 654: BZERO(hbp + HDR_BYTES, size_needed - HDR_BYTES);
1.1 maekawa 655: }
656:
657: /* We just successfully allocated a block. Restart count of */
658: /* consecutive failures. */
659: {
660: extern unsigned GC_fail_count;
661:
662: GC_fail_count = 0;
663: }
1.1.1.2 ! maekawa 664:
! 665: GC_large_free_bytes -= size_needed;
1.1 maekawa 666:
1.1.1.2 ! maekawa 667: GC_ASSERT(IS_MAPPED(hhdr));
! 668: return( hbp );
1.1 maekawa 669: }
670:
671: struct hblk * GC_freehblk_ptr = 0; /* Search position hint for GC_freehblk */
672:
673: /*
674: * Free a heap block.
675: *
676: * Coalesce the block with its neighbors if possible.
677: *
678: * All mark words are assumed to be cleared.
679: */
680: void
1.1.1.2 ! maekawa 681: GC_freehblk(hbp)
! 682: struct hblk *hbp;
1.1 maekawa 683: {
1.1.1.2 ! maekawa 684: struct hblk *next, *prev;
! 685: hdr *hhdr, *prevhdr, *nexthdr;
! 686: signed_word size;
1.1 maekawa 687:
688:
689: hhdr = HDR(hbp);
1.1.1.2 ! maekawa 690: size = hhdr->hb_sz;
! 691: size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
! 692: GC_remove_counts(hbp, (word)size);
! 693: hhdr->hb_sz = size;
1.1 maekawa 694:
695: /* Check for duplicate deallocation in the easy case */
1.1.1.2 ! maekawa 696: if (HBLK_IS_FREE(hhdr)) {
1.1 maekawa 697: GC_printf1("Duplicate large block deallocation of 0x%lx\n",
1.1.1.2 ! maekawa 698: (unsigned long) hbp);
1.1 maekawa 699: }
700:
1.1.1.2 ! maekawa 701: GC_ASSERT(IS_MAPPED(hhdr));
! 702: GC_invalidate_map(hhdr);
! 703: next = (struct hblk *)((word)hbp + size);
! 704: nexthdr = HDR(next);
! 705: prev = GC_free_block_ending_at(hbp);
1.1 maekawa 706: /* Coalesce with successor, if possible */
1.1.1.2 ! maekawa 707: if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)) {
! 708: GC_remove_from_fl(nexthdr, FL_UNKNOWN);
! 709: hhdr -> hb_sz += nexthdr -> hb_sz;
! 710: GC_remove_header(next);
! 711: }
! 712: /* Coalesce with predecessor, if possible. */
! 713: if (0 != prev) {
! 714: prevhdr = HDR(prev);
! 715: if (IS_MAPPED(prevhdr)) {
! 716: GC_remove_from_fl(prevhdr, FL_UNKNOWN);
! 717: prevhdr -> hb_sz += hhdr -> hb_sz;
! 718: GC_remove_header(hbp);
! 719: hbp = prev;
! 720: hhdr = prevhdr;
! 721: }
1.1 maekawa 722: }
723:
1.1.1.2 ! maekawa 724: GC_large_free_bytes += size;
! 725: GC_add_to_fl(hbp, hhdr);
1.1 maekawa 726: }
727:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to allchblk.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gc