Annotation of OpenXM_contrib/gc/allchblk.c, Revision 1.1
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.
! 4: * Copyright (c) 1998 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: /* Boehm, August 9, 1995 5:08 pm PDT */
! 16:
! 17: #define DEBUG
! 18: #undef DEBUG
! 19: #include <stdio.h>
! 20: #include "gc_priv.h"
! 21:
! 22:
! 23: /*
! 24: * allocate/free routines for heap blocks
! 25: * Note that everything called from outside the garbage collector
! 26: * should be prepared to abort at any point as the result of a signal.
! 27: */
! 28:
! 29: /*
! 30: * Free heap blocks are kept on a list sorted by address.
! 31: * The hb_hdr.hbh_sz field of a free heap block contains the length
! 32: * (in bytes) of the entire block.
! 33: * Neighbors are coalesced.
! 34: */
! 35:
! 36: # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
! 37: /* largest block we will allocate starting on a black */
! 38: /* listed block. Must be >= HBLKSIZE. */
! 39:
! 40: struct hblk * GC_hblkfreelist = 0;
! 41:
! 42: struct hblk *GC_savhbp = (struct hblk *)0; /* heap block preceding next */
! 43: /* block to be examined by */
! 44: /* GC_allochblk. */
! 45:
! 46: # if !defined(NO_DEBUGGING)
! 47: void GC_print_hblkfreelist()
! 48: {
! 49: struct hblk * h = GC_hblkfreelist;
! 50: word total_free = 0;
! 51: hdr * hhdr = HDR(h);
! 52: word sz;
! 53:
! 54: while (h != 0) {
! 55: sz = hhdr -> hb_sz;
! 56: GC_printf2("0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
! 57: total_free += sz;
! 58: if (GC_is_black_listed(h, HBLKSIZE) != 0) {
! 59: GC_printf0("start black listed\n");
! 60: } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
! 61: GC_printf0("partially black listed\n");
! 62: } else {
! 63: GC_printf0("not black listed\n");
! 64: }
! 65: h = hhdr -> hb_next;
! 66: hhdr = HDR(h);
! 67: }
! 68: GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
! 69: }
! 70:
! 71: # endif /* NO_DEBUGGING */
! 72:
! 73: /* Initialize hdr for a block containing the indicated size and */
! 74: /* kind of objects. */
! 75: /* Return FALSE on failure. */
! 76: static GC_bool setup_header(hhdr, sz, kind, flags)
! 77: register hdr * hhdr;
! 78: word sz; /* object size in words */
! 79: int kind;
! 80: unsigned char flags;
! 81: {
! 82: register word descr;
! 83:
! 84: /* Add description of valid object pointers */
! 85: if (!GC_add_map_entry(sz)) return(FALSE);
! 86: hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
! 87:
! 88: /* Set size, kind and mark proc fields */
! 89: hhdr -> hb_sz = sz;
! 90: hhdr -> hb_obj_kind = kind;
! 91: hhdr -> hb_flags = flags;
! 92: descr = GC_obj_kinds[kind].ok_descriptor;
! 93: if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
! 94: hhdr -> hb_descr = descr;
! 95:
! 96: /* Clear mark bits */
! 97: GC_clear_hdr_marks(hhdr);
! 98:
! 99: hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
! 100: return(TRUE);
! 101: }
! 102:
! 103: #ifdef EXACT_FIRST
! 104: # define LAST_TRIP 2
! 105: #else
! 106: # define LAST_TRIP 1
! 107: #endif
! 108:
! 109: word GC_max_hblk_size = HBLKSIZE;
! 110:
! 111: /*
! 112: * Allocate (and return pointer to) a heap block
! 113: * for objects of size sz words.
! 114: *
! 115: * NOTE: We set obj_map field in header correctly.
! 116: * Caller is resposnsible for building an object freelist in block.
! 117: *
! 118: * We clear the block if it is destined for large objects, and if
! 119: * kind requires that newly allocated objects be cleared.
! 120: */
! 121: struct hblk *
! 122: GC_allochblk(sz, kind, flags)
! 123: word sz;
! 124: int kind;
! 125: unsigned char flags; /* IGNORE_OFF_PAGE or 0 */
! 126: {
! 127: register struct hblk *thishbp;
! 128: register hdr * thishdr; /* Header corr. to thishbp */
! 129: register struct hblk *hbp;
! 130: register hdr * hhdr; /* Header corr. to hbp */
! 131: struct hblk *prevhbp;
! 132: register hdr * phdr; /* Header corr. to prevhbp */
! 133: signed_word size_needed; /* number of bytes in requested objects */
! 134: signed_word size_avail; /* bytes available in this block */
! 135: int trip_count = 0;
! 136:
! 137: size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
! 138: if ((word)size_needed > GC_max_hblk_size)
! 139: GC_max_hblk_size = size_needed;
! 140:
! 141: /* search for a big enough block in free list */
! 142: hbp = GC_savhbp;
! 143: hhdr = HDR(hbp);
! 144: for(;;) {
! 145:
! 146: prevhbp = hbp;
! 147: phdr = hhdr;
! 148: hbp = (prevhbp == 0? GC_hblkfreelist : phdr->hb_next);
! 149: hhdr = HDR(hbp);
! 150:
! 151: if( prevhbp == GC_savhbp) {
! 152: if (trip_count == LAST_TRIP) return(0);
! 153: ++trip_count;
! 154: }
! 155:
! 156: if( hbp == 0 ) continue;
! 157:
! 158: size_avail = hhdr->hb_sz;
! 159: # ifdef EXACT_FIRST
! 160: if (trip_count <= 1 && size_avail != size_needed) continue;
! 161: # endif
! 162: if (size_avail < size_needed) continue;
! 163: # ifdef PRESERVE_LAST
! 164: if (size_avail != size_needed
! 165: && !GC_incremental
! 166: && (word)size_needed <= GC_max_hblk_size/2
! 167: && GC_in_last_heap_sect((ptr_t)hbp)
! 168: && GC_should_collect()) {
! 169: continue;
! 170: }
! 171: # endif
! 172: /* If the next heap block is obviously better, go on. */
! 173: /* This prevents us from disassembling a single large block */
! 174: /* to get tiny blocks. */
! 175: {
! 176: signed_word next_size;
! 177:
! 178: thishbp = hhdr -> hb_next;
! 179: if (thishbp == 0) thishbp = GC_hblkfreelist;
! 180: thishdr = HDR(thishbp);
! 181: next_size = (signed_word)(thishdr -> hb_sz);
! 182: if (next_size < size_avail
! 183: && next_size >= size_needed
! 184: && !GC_is_black_listed(thishbp, (word)size_needed)) {
! 185: continue;
! 186: }
! 187: }
! 188: if ( !IS_UNCOLLECTABLE(kind) &&
! 189: (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
! 190: struct hblk * lasthbp = hbp;
! 191: ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
! 192: signed_word orig_avail = size_avail;
! 193: signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
! 194: HBLKSIZE
! 195: : size_needed);
! 196:
! 197:
! 198: while ((ptr_t)lasthbp <= search_end
! 199: && (thishbp = GC_is_black_listed(lasthbp,
! 200: (word)eff_size_needed))) {
! 201: lasthbp = thishbp;
! 202: }
! 203: size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
! 204: thishbp = lasthbp;
! 205: if (size_avail >= size_needed) {
! 206: if (thishbp != hbp && GC_install_header(thishbp)) {
! 207: /* Split the block at thishbp */
! 208: thishdr = HDR(thishbp);
! 209: /* GC_invalidate_map not needed, since we will */
! 210: /* allocate this block. */
! 211: thishdr -> hb_next = hhdr -> hb_next;
! 212: thishdr -> hb_sz = size_avail;
! 213: hhdr -> hb_sz = (ptr_t)thishbp - (ptr_t)hbp;
! 214: hhdr -> hb_next = thishbp;
! 215: /* Advance to thishbp */
! 216: prevhbp = hbp;
! 217: phdr = hhdr;
! 218: hbp = thishbp;
! 219: hhdr = thishdr;
! 220: }
! 221: } else if (size_needed > (signed_word)BL_LIMIT
! 222: && orig_avail - size_needed
! 223: > (signed_word)BL_LIMIT) {
! 224: /* Punt, since anything else risks unreasonable heap growth. */
! 225: WARN("Needed to allocate blacklisted block at 0x%lx\n",
! 226: (word)hbp);
! 227: thishbp = hbp;
! 228: size_avail = orig_avail;
! 229: } else if (size_avail == 0
! 230: && size_needed == HBLKSIZE
! 231: && prevhbp != 0) {
! 232: # ifndef FIND_LEAK
! 233: static unsigned count = 0;
! 234:
! 235: /* The block is completely blacklisted. We need */
! 236: /* to drop some such blocks, since otherwise we spend */
! 237: /* all our time traversing them if pointerfree */
! 238: /* blocks are unpopular. */
! 239: /* A dropped block will be reconsidered at next GC. */
! 240: if ((++count & 3) == 0) {
! 241: /* Allocate and drop the block in small chunks, to */
! 242: /* maximize the chance that we will recover some */
! 243: /* later. */
! 244: struct hblk * limit = hbp + (hhdr->hb_sz/HBLKSIZE);
! 245: struct hblk * h;
! 246:
! 247: GC_words_wasted += hhdr->hb_sz;
! 248: phdr -> hb_next = hhdr -> hb_next;
! 249: for (h = hbp; h < limit; h++) {
! 250: if (h == hbp || GC_install_header(h)) {
! 251: hhdr = HDR(h);
! 252: (void) setup_header(
! 253: hhdr,
! 254: BYTES_TO_WORDS(HBLKSIZE - HDR_BYTES),
! 255: PTRFREE, 0); /* Cant fail */
! 256: if (GC_debugging_started) {
! 257: BZERO(hbp + HDR_BYTES, HBLKSIZE - HDR_BYTES);
! 258: }
! 259: }
! 260: }
! 261: /* Restore hbp to point at free block */
! 262: if (GC_savhbp == hbp) GC_savhbp = prevhbp;
! 263: hbp = prevhbp;
! 264: hhdr = phdr;
! 265: if (hbp == GC_savhbp) --trip_count;
! 266: }
! 267: # endif
! 268: }
! 269: }
! 270: if( size_avail >= size_needed ) {
! 271: /* found a big enough block */
! 272: /* let thishbp --> the block */
! 273: /* set prevhbp, hbp to bracket it */
! 274: thishbp = hbp;
! 275: thishdr = hhdr;
! 276: if( size_avail == size_needed ) {
! 277: hbp = hhdr->hb_next;
! 278: hhdr = HDR(hbp);
! 279: } else {
! 280: hbp = (struct hblk *)
! 281: (((word)thishbp) + size_needed);
! 282: if (!GC_install_header(hbp)) {
! 283: hbp = thishbp;
! 284: continue;
! 285: }
! 286: hhdr = HDR(hbp);
! 287: GC_invalidate_map(hhdr);
! 288: hhdr->hb_next = thishdr->hb_next;
! 289: hhdr->hb_sz = size_avail - size_needed;
! 290: }
! 291: /* remove *thishbp from hblk freelist */
! 292: if( prevhbp == 0 ) {
! 293: GC_hblkfreelist = hbp;
! 294: } else {
! 295: phdr->hb_next = hbp;
! 296: }
! 297: /* save current list search position */
! 298: GC_savhbp = hbp;
! 299: break;
! 300: }
! 301: }
! 302:
! 303: /* Notify virtual dirty bit implementation that we are about to write. */
! 304: GC_write_hint(thishbp);
! 305: /* This should deal better with large blocks. */
! 306:
! 307: /* Add it to map of valid blocks */
! 308: if (!GC_install_counts(thishbp, (word)size_needed)) return(0);
! 309: /* This leaks memory under very rare conditions. */
! 310:
! 311: /* Set up header */
! 312: if (!setup_header(thishdr, sz, kind, flags)) {
! 313: GC_remove_counts(thishbp, (word)size_needed);
! 314: return(0); /* ditto */
! 315: }
! 316:
! 317: /* Clear block if necessary */
! 318: if (GC_debugging_started
! 319: || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
! 320: BZERO(thishbp + HDR_BYTES, size_needed - HDR_BYTES);
! 321: }
! 322:
! 323: /* We just successfully allocated a block. Restart count of */
! 324: /* consecutive failures. */
! 325: {
! 326: extern unsigned GC_fail_count;
! 327:
! 328: GC_fail_count = 0;
! 329: }
! 330:
! 331: return( thishbp );
! 332: }
! 333:
! 334: struct hblk * GC_freehblk_ptr = 0; /* Search position hint for GC_freehblk */
! 335:
! 336: /*
! 337: * Free a heap block.
! 338: *
! 339: * Coalesce the block with its neighbors if possible.
! 340: *
! 341: * All mark words are assumed to be cleared.
! 342: */
! 343: void
! 344: GC_freehblk(p)
! 345: register struct hblk *p;
! 346: {
! 347: register hdr *phdr; /* Header corresponding to p */
! 348: register struct hblk *hbp, *prevhbp;
! 349: register hdr *hhdr, *prevhdr;
! 350: register signed_word size;
! 351:
! 352: /* GC_savhbp may become invalid due to coalescing. Clear it. */
! 353: GC_savhbp = (struct hblk *)0;
! 354:
! 355: phdr = HDR(p);
! 356: size = phdr->hb_sz;
! 357: size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
! 358: GC_remove_counts(p, (word)size);
! 359: phdr->hb_sz = size;
! 360: GC_invalidate_map(phdr);
! 361: prevhbp = 0;
! 362:
! 363: /* The following optimization was suggested by David Detlefs. */
! 364: /* Note that the header cannot be NIL, since there cannot be an */
! 365: /* intervening call to GC_freehblk without resetting */
! 366: /* GC_freehblk_ptr. */
! 367: if (GC_freehblk_ptr != 0 &&
! 368: HDR(GC_freehblk_ptr)->hb_map == GC_invalid_map &&
! 369: (ptr_t)GC_freehblk_ptr < (ptr_t)p) {
! 370: hbp = GC_freehblk_ptr;
! 371: } else {
! 372: hbp = GC_hblkfreelist;
! 373: };
! 374: hhdr = HDR(hbp);
! 375:
! 376: while( (hbp != 0) && (hbp < p) ) {
! 377: prevhbp = hbp;
! 378: prevhdr = hhdr;
! 379: hbp = hhdr->hb_next;
! 380: hhdr = HDR(hbp);
! 381: }
! 382: GC_freehblk_ptr = prevhbp;
! 383:
! 384: /* Check for duplicate deallocation in the easy case */
! 385: if (hbp != 0 && (ptr_t)p + size > (ptr_t)hbp
! 386: || prevhbp != 0 && (ptr_t)prevhbp + prevhdr->hb_sz > (ptr_t)p) {
! 387: GC_printf1("Duplicate large block deallocation of 0x%lx\n",
! 388: (unsigned long) p);
! 389: GC_printf2("Surrounding free blocks are 0x%lx and 0x%lx\n",
! 390: (unsigned long) prevhbp, (unsigned long) hbp);
! 391: }
! 392:
! 393: /* Coalesce with successor, if possible */
! 394: if( (((word)p)+size) == ((word)hbp) ) {
! 395: phdr->hb_next = hhdr->hb_next;
! 396: phdr->hb_sz += hhdr->hb_sz;
! 397: GC_remove_header(hbp);
! 398: } else {
! 399: phdr->hb_next = hbp;
! 400: }
! 401:
! 402:
! 403: if( prevhbp == 0 ) {
! 404: GC_hblkfreelist = p;
! 405: } else if( (((word)prevhbp) + prevhdr->hb_sz)
! 406: == ((word)p) ) {
! 407: /* Coalesce with predecessor */
! 408: prevhdr->hb_next = phdr->hb_next;
! 409: prevhdr->hb_sz += phdr->hb_sz;
! 410: GC_remove_header(p);
! 411: } else {
! 412: prevhdr->hb_next = p;
! 413: }
! 414: }
! 415:
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