Annotation of OpenXM_contrib2/asir2000/gc5.3/reclaim.c, Revision 1.1
1.1 ! noro 1: /*
! 2: * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
! 3: * Copyright (c) 1991-1996 by Xerox Corporation. All rights reserved.
! 4: * Copyright (c) 1996-1999 by Silicon Graphics. All rights reserved.
! 5: * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved.
! 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: #include <stdio.h>
! 18: #include "gc_priv.h"
! 19:
! 20: void GC_timerstart(), GC_timerstop();
! 21:
! 22: signed_word GC_mem_found = 0;
! 23: /* Number of words of memory reclaimed */
! 24:
! 25: static void report_leak(p, sz)
! 26: ptr_t p;
! 27: word sz;
! 28: {
! 29: if (HDR(p) -> hb_obj_kind == PTRFREE) {
! 30: GC_err_printf0("Leaked atomic object at ");
! 31: } else {
! 32: GC_err_printf0("Leaked composite object at ");
! 33: }
! 34: GC_print_heap_obj(p);
! 35: GC_err_printf0("\n");
! 36: }
! 37:
! 38: # define FOUND_FREE(hblk, word_no) \
! 39: { \
! 40: report_leak((ptr_t)hblk + WORDS_TO_BYTES(word_no), \
! 41: HDR(hblk) -> hb_sz); \
! 42: }
! 43:
! 44: /*
! 45: * reclaim phase
! 46: *
! 47: */
! 48:
! 49:
! 50: /*
! 51: * Test whether a block is completely empty, i.e. contains no marked
! 52: * objects. This does not require the block to be in physical
! 53: * memory.
! 54: */
! 55:
! 56: GC_bool GC_block_empty(hhdr)
! 57: register hdr * hhdr;
! 58: {
! 59: register word *p = (word *)(&(hhdr -> hb_marks[0]));
! 60: register word * plim =
! 61: (word *)(&(hhdr -> hb_marks[MARK_BITS_SZ]));
! 62: while (p < plim) {
! 63: if (*p++) return(FALSE);
! 64: }
! 65: return(TRUE);
! 66: }
! 67:
! 68: /* The following functions sometimes return a DONT_KNOW value. */
! 69: #define DONT_KNOW 2
! 70:
! 71: #ifdef SMALL_CONFIG
! 72: # define GC_block_nearly_full1(hhdr, pat1) DONT_KNOW
! 73: # define GC_block_nearly_full3(hhdr, pat1, pat2) DONT_KNOW
! 74: # define GC_block_nearly_full(hhdr) DONT_KNOW
! 75: #else
! 76:
! 77: /*
! 78: * Test whether nearly all of the mark words consist of the same
! 79: * repeating pattern.
! 80: */
! 81: #define FULL_THRESHOLD (MARK_BITS_SZ/16)
! 82:
! 83: GC_bool GC_block_nearly_full1(hhdr, pat1)
! 84: hdr *hhdr;
! 85: word pat1;
! 86: {
! 87: unsigned i;
! 88: unsigned misses = 0;
! 89: GC_ASSERT((MARK_BITS_SZ & 1) == 0);
! 90: for (i = 0; i < MARK_BITS_SZ; ++i) {
! 91: if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
! 92: if (++misses > FULL_THRESHOLD) return FALSE;
! 93: }
! 94: }
! 95: return TRUE;
! 96: }
! 97:
! 98: /*
! 99: * Test whether the same repeating 3 word pattern occurs in nearly
! 100: * all the mark bit slots.
! 101: * This is used as a heuristic, so we're a bit sloppy and ignore
! 102: * the last one or two words.
! 103: */
! 104: GC_bool GC_block_nearly_full3(hhdr, pat1, pat2, pat3)
! 105: hdr *hhdr;
! 106: word pat1, pat2, pat3;
! 107: {
! 108: unsigned i;
! 109: unsigned misses = 0;
! 110:
! 111: if (MARK_BITS_SZ < 4) {
! 112: return DONT_KNOW;
! 113: }
! 114: for (i = 0; i < MARK_BITS_SZ - 2; i += 3) {
! 115: if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
! 116: if (++misses > FULL_THRESHOLD) return FALSE;
! 117: }
! 118: if ((hhdr -> hb_marks[i+1] | ~pat2) != ONES) {
! 119: if (++misses > FULL_THRESHOLD) return FALSE;
! 120: }
! 121: if ((hhdr -> hb_marks[i+2] | ~pat3) != ONES) {
! 122: if (++misses > FULL_THRESHOLD) return FALSE;
! 123: }
! 124: }
! 125: return TRUE;
! 126: }
! 127:
! 128: /* Check whether a small object block is nearly full by looking at only */
! 129: /* the mark bits. */
! 130: /* We manually precomputed the mark bit patterns that need to be */
! 131: /* checked for, and we give up on the ones that are unlikely to occur, */
! 132: /* or have period > 3. */
! 133: /* This would be a lot easier with a mark bit per object instead of per */
! 134: /* word, but that would rewuire computing object numbers in the mark */
! 135: /* loop, which would require different data structures ... */
! 136: GC_bool GC_block_nearly_full(hhdr)
! 137: hdr *hhdr;
! 138: {
! 139: int sz = hhdr -> hb_sz;
! 140:
! 141: # if CPP_WORDSZ != 32 && CPP_WORDSZ != 64
! 142: return DONT_KNOW; /* Shouldn't be used in any standard config. */
! 143: # endif
! 144: if (0 != HDR_WORDS) return DONT_KNOW;
! 145: /* Also shouldn't happen */
! 146: # if CPP_WORDSZ == 32
! 147: switch(sz) {
! 148: case 1:
! 149: return GC_block_nearly_full1(hhdr, 0xffffffffl);
! 150: case 2:
! 151: return GC_block_nearly_full1(hhdr, 0x55555555l);
! 152: case 4:
! 153: return GC_block_nearly_full1(hhdr, 0x11111111l);
! 154: case 6:
! 155: return GC_block_nearly_full3(hhdr, 0x41041041l,
! 156: 0x10410410l,
! 157: 0x04104104l);
! 158: case 8:
! 159: return GC_block_nearly_full1(hhdr, 0x01010101l);
! 160: case 12:
! 161: return GC_block_nearly_full3(hhdr, 0x01001001l,
! 162: 0x10010010l,
! 163: 0x00100100l);
! 164: case 16:
! 165: return GC_block_nearly_full1(hhdr, 0x00010001l);
! 166: case 32:
! 167: return GC_block_nearly_full1(hhdr, 0x00000001l);
! 168: default:
! 169: return DONT_KNOW;
! 170: }
! 171: # endif
! 172: # if CPP_WORDSZ == 64
! 173: switch(sz) {
! 174: case 1:
! 175: return GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
! 176: case 2:
! 177: return GC_block_nearly_full1(hhdr, 0x5555555555555555l);
! 178: case 4:
! 179: return GC_block_nearly_full1(hhdr, 0x1111111111111111l);
! 180: case 6:
! 181: return GC_block_nearly_full3(hhdr, 0x1041041041041041l,
! 182: 0x4104104104104104l,
! 183: 0x0410410410410410l);
! 184: case 8:
! 185: return GC_block_nearly_full1(hhdr, 0x0101010101010101l);
! 186: case 12:
! 187: return GC_block_nearly_full3(hhdr, 0x1001001001001001l,
! 188: 0x0100100100100100l,
! 189: 0x0010010010010010l);
! 190: case 16:
! 191: return GC_block_nearly_full1(hhdr, 0x0001000100010001l);
! 192: case 32:
! 193: return GC_block_nearly_full1(hhdr, 0x0000000100000001l);
! 194: default:
! 195: return DONT_KNOW;
! 196: }
! 197: # endif
! 198: }
! 199: #endif /* !SMALL_CONFIG */
! 200:
! 201: # ifdef GATHERSTATS
! 202: # define INCR_WORDS(sz) n_words_found += (sz)
! 203: # else
! 204: # define INCR_WORDS(sz)
! 205: # endif
! 206: /*
! 207: * Restore unmarked small objects in h of size sz to the object
! 208: * free list. Returns the new list.
! 209: * Clears unmarked objects.
! 210: */
! 211: /*ARGSUSED*/
! 212: ptr_t GC_reclaim_clear(hbp, hhdr, sz, list)
! 213: register struct hblk *hbp; /* ptr to current heap block */
! 214: register hdr * hhdr;
! 215: register ptr_t list;
! 216: register word sz;
! 217: {
! 218: register int word_no;
! 219: register word *p, *q, *plim;
! 220: # ifdef GATHERSTATS
! 221: register int n_words_found = 0;
! 222: # endif
! 223:
! 224: p = (word *)(hbp->hb_body);
! 225: word_no = HDR_WORDS;
! 226: plim = (word *)((((word)hbp) + HBLKSIZE)
! 227: - WORDS_TO_BYTES(sz));
! 228:
! 229: /* go through all words in block */
! 230: while( p <= plim ) {
! 231: if( mark_bit_from_hdr(hhdr, word_no) ) {
! 232: p += sz;
! 233: } else {
! 234: INCR_WORDS(sz);
! 235: /* object is available - put on list */
! 236: obj_link(p) = list;
! 237: list = ((ptr_t)p);
! 238: /* Clear object, advance p to next object in the process */
! 239: q = p + sz;
! 240: p++; /* Skip link field */
! 241: while (p < q) {
! 242: *p++ = 0;
! 243: }
! 244: }
! 245: word_no += sz;
! 246: }
! 247: # ifdef GATHERSTATS
! 248: GC_mem_found += n_words_found;
! 249: # endif
! 250: return(list);
! 251: }
! 252:
! 253: #ifndef SMALL_CONFIG
! 254:
! 255: /*
! 256: * A special case for 2 word composite objects (e.g. cons cells):
! 257: */
! 258: /*ARGSUSED*/
! 259: ptr_t GC_reclaim_clear2(hbp, hhdr, list)
! 260: register struct hblk *hbp; /* ptr to current heap block */
! 261: hdr * hhdr;
! 262: register ptr_t list;
! 263: {
! 264: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
! 265: register word *p, *plim;
! 266: # ifdef GATHERSTATS
! 267: register int n_words_found = 0;
! 268: # endif
! 269: register word mark_word;
! 270: register int i;
! 271: # define DO_OBJ(start_displ) \
! 272: if (!(mark_word & ((word)1 << start_displ))) { \
! 273: p[start_displ] = (word)list; \
! 274: list = (ptr_t)(p+start_displ); \
! 275: p[start_displ+1] = 0; \
! 276: INCR_WORDS(2); \
! 277: }
! 278:
! 279: p = (word *)(hbp->hb_body);
! 280: plim = (word *)(((word)hbp) + HBLKSIZE);
! 281:
! 282: /* go through all words in block */
! 283: while( p < plim ) {
! 284: mark_word = *mark_word_addr++;
! 285: for (i = 0; i < WORDSZ; i += 8) {
! 286: DO_OBJ(0);
! 287: DO_OBJ(2);
! 288: DO_OBJ(4);
! 289: DO_OBJ(6);
! 290: p += 8;
! 291: mark_word >>= 8;
! 292: }
! 293: }
! 294: # ifdef GATHERSTATS
! 295: GC_mem_found += n_words_found;
! 296: # endif
! 297: return(list);
! 298: # undef DO_OBJ
! 299: }
! 300:
! 301: /*
! 302: * Another special case for 4 word composite objects:
! 303: */
! 304: /*ARGSUSED*/
! 305: ptr_t GC_reclaim_clear4(hbp, hhdr, list)
! 306: register struct hblk *hbp; /* ptr to current heap block */
! 307: hdr * hhdr;
! 308: register ptr_t list;
! 309: {
! 310: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
! 311: register word *p, *plim;
! 312: # ifdef GATHERSTATS
! 313: register int n_words_found = 0;
! 314: # endif
! 315: register word mark_word;
! 316: # define DO_OBJ(start_displ) \
! 317: if (!(mark_word & ((word)1 << start_displ))) { \
! 318: p[start_displ] = (word)list; \
! 319: list = (ptr_t)(p+start_displ); \
! 320: p[start_displ+1] = 0; \
! 321: CLEAR_DOUBLE(p + start_displ + 2); \
! 322: INCR_WORDS(4); \
! 323: }
! 324:
! 325: p = (word *)(hbp->hb_body);
! 326: plim = (word *)(((word)hbp) + HBLKSIZE);
! 327:
! 328: /* go through all words in block */
! 329: while( p < plim ) {
! 330: mark_word = *mark_word_addr++;
! 331: DO_OBJ(0);
! 332: DO_OBJ(4);
! 333: DO_OBJ(8);
! 334: DO_OBJ(12);
! 335: DO_OBJ(16);
! 336: DO_OBJ(20);
! 337: DO_OBJ(24);
! 338: DO_OBJ(28);
! 339: # if CPP_WORDSZ == 64
! 340: DO_OBJ(32);
! 341: DO_OBJ(36);
! 342: DO_OBJ(40);
! 343: DO_OBJ(44);
! 344: DO_OBJ(48);
! 345: DO_OBJ(52);
! 346: DO_OBJ(56);
! 347: DO_OBJ(60);
! 348: # endif
! 349: p += WORDSZ;
! 350: }
! 351: # ifdef GATHERSTATS
! 352: GC_mem_found += n_words_found;
! 353: # endif
! 354: return(list);
! 355: # undef DO_OBJ
! 356: }
! 357:
! 358: #endif /* !SMALL_CONFIG */
! 359:
! 360: /* The same thing, but don't clear objects: */
! 361: /*ARGSUSED*/
! 362: ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list)
! 363: register struct hblk *hbp; /* ptr to current heap block */
! 364: register hdr * hhdr;
! 365: register ptr_t list;
! 366: register word sz;
! 367: {
! 368: register int word_no;
! 369: register word *p, *plim;
! 370: # ifdef GATHERSTATS
! 371: register int n_words_found = 0;
! 372: # endif
! 373:
! 374: p = (word *)(hbp->hb_body);
! 375: word_no = HDR_WORDS;
! 376: plim = (word *)((((word)hbp) + HBLKSIZE)
! 377: - WORDS_TO_BYTES(sz));
! 378:
! 379: /* go through all words in block */
! 380: while( p <= plim ) {
! 381: if( !mark_bit_from_hdr(hhdr, word_no) ) {
! 382: INCR_WORDS(sz);
! 383: /* object is available - put on list */
! 384: obj_link(p) = list;
! 385: list = ((ptr_t)p);
! 386: }
! 387: p += sz;
! 388: word_no += sz;
! 389: }
! 390: # ifdef GATHERSTATS
! 391: GC_mem_found += n_words_found;
! 392: # endif
! 393: return(list);
! 394: }
! 395:
! 396: /* Don't really reclaim objects, just check for unmarked ones: */
! 397: /*ARGSUSED*/
! 398: void GC_reclaim_check(hbp, hhdr, sz)
! 399: register struct hblk *hbp; /* ptr to current heap block */
! 400: register hdr * hhdr;
! 401: register word sz;
! 402: {
! 403: register int word_no;
! 404: register word *p, *plim;
! 405: # ifdef GATHERSTATS
! 406: register int n_words_found = 0;
! 407: # endif
! 408:
! 409: p = (word *)(hbp->hb_body);
! 410: word_no = HDR_WORDS;
! 411: plim = (word *)((((word)hbp) + HBLKSIZE)
! 412: - WORDS_TO_BYTES(sz));
! 413:
! 414: /* go through all words in block */
! 415: while( p <= plim ) {
! 416: if( !mark_bit_from_hdr(hhdr, word_no) ) {
! 417: FOUND_FREE(hbp, word_no);
! 418: }
! 419: p += sz;
! 420: word_no += sz;
! 421: }
! 422: }
! 423:
! 424: #ifndef SMALL_CONFIG
! 425: /*
! 426: * Another special case for 2 word atomic objects:
! 427: */
! 428: /*ARGSUSED*/
! 429: ptr_t GC_reclaim_uninit2(hbp, hhdr, list)
! 430: register struct hblk *hbp; /* ptr to current heap block */
! 431: hdr * hhdr;
! 432: register ptr_t list;
! 433: {
! 434: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
! 435: register word *p, *plim;
! 436: # ifdef GATHERSTATS
! 437: register int n_words_found = 0;
! 438: # endif
! 439: register word mark_word;
! 440: register int i;
! 441: # define DO_OBJ(start_displ) \
! 442: if (!(mark_word & ((word)1 << start_displ))) { \
! 443: p[start_displ] = (word)list; \
! 444: list = (ptr_t)(p+start_displ); \
! 445: INCR_WORDS(2); \
! 446: }
! 447:
! 448: p = (word *)(hbp->hb_body);
! 449: plim = (word *)(((word)hbp) + HBLKSIZE);
! 450:
! 451: /* go through all words in block */
! 452: while( p < plim ) {
! 453: mark_word = *mark_word_addr++;
! 454: for (i = 0; i < WORDSZ; i += 8) {
! 455: DO_OBJ(0);
! 456: DO_OBJ(2);
! 457: DO_OBJ(4);
! 458: DO_OBJ(6);
! 459: p += 8;
! 460: mark_word >>= 8;
! 461: }
! 462: }
! 463: # ifdef GATHERSTATS
! 464: GC_mem_found += n_words_found;
! 465: # endif
! 466: return(list);
! 467: # undef DO_OBJ
! 468: }
! 469:
! 470: /*
! 471: * Another special case for 4 word atomic objects:
! 472: */
! 473: /*ARGSUSED*/
! 474: ptr_t GC_reclaim_uninit4(hbp, hhdr, list)
! 475: register struct hblk *hbp; /* ptr to current heap block */
! 476: hdr * hhdr;
! 477: register ptr_t list;
! 478: {
! 479: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
! 480: register word *p, *plim;
! 481: # ifdef GATHERSTATS
! 482: register int n_words_found = 0;
! 483: # endif
! 484: register word mark_word;
! 485: # define DO_OBJ(start_displ) \
! 486: if (!(mark_word & ((word)1 << start_displ))) { \
! 487: p[start_displ] = (word)list; \
! 488: list = (ptr_t)(p+start_displ); \
! 489: INCR_WORDS(4); \
! 490: }
! 491:
! 492: p = (word *)(hbp->hb_body);
! 493: plim = (word *)(((word)hbp) + HBLKSIZE);
! 494:
! 495: /* go through all words in block */
! 496: while( p < plim ) {
! 497: mark_word = *mark_word_addr++;
! 498: DO_OBJ(0);
! 499: DO_OBJ(4);
! 500: DO_OBJ(8);
! 501: DO_OBJ(12);
! 502: DO_OBJ(16);
! 503: DO_OBJ(20);
! 504: DO_OBJ(24);
! 505: DO_OBJ(28);
! 506: # if CPP_WORDSZ == 64
! 507: DO_OBJ(32);
! 508: DO_OBJ(36);
! 509: DO_OBJ(40);
! 510: DO_OBJ(44);
! 511: DO_OBJ(48);
! 512: DO_OBJ(52);
! 513: DO_OBJ(56);
! 514: DO_OBJ(60);
! 515: # endif
! 516: p += WORDSZ;
! 517: }
! 518: # ifdef GATHERSTATS
! 519: GC_mem_found += n_words_found;
! 520: # endif
! 521: return(list);
! 522: # undef DO_OBJ
! 523: }
! 524:
! 525: /* Finally the one word case, which never requires any clearing: */
! 526: /*ARGSUSED*/
! 527: ptr_t GC_reclaim1(hbp, hhdr, list)
! 528: register struct hblk *hbp; /* ptr to current heap block */
! 529: hdr * hhdr;
! 530: register ptr_t list;
! 531: {
! 532: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
! 533: register word *p, *plim;
! 534: # ifdef GATHERSTATS
! 535: register int n_words_found = 0;
! 536: # endif
! 537: register word mark_word;
! 538: register int i;
! 539: # define DO_OBJ(start_displ) \
! 540: if (!(mark_word & ((word)1 << start_displ))) { \
! 541: p[start_displ] = (word)list; \
! 542: list = (ptr_t)(p+start_displ); \
! 543: INCR_WORDS(1); \
! 544: }
! 545:
! 546: p = (word *)(hbp->hb_body);
! 547: plim = (word *)(((word)hbp) + HBLKSIZE);
! 548:
! 549: /* go through all words in block */
! 550: while( p < plim ) {
! 551: mark_word = *mark_word_addr++;
! 552: for (i = 0; i < WORDSZ; i += 4) {
! 553: DO_OBJ(0);
! 554: DO_OBJ(1);
! 555: DO_OBJ(2);
! 556: DO_OBJ(3);
! 557: p += 4;
! 558: mark_word >>= 4;
! 559: }
! 560: }
! 561: # ifdef GATHERSTATS
! 562: GC_mem_found += n_words_found;
! 563: # endif
! 564: return(list);
! 565: # undef DO_OBJ
! 566: }
! 567:
! 568: #endif /* !SMALL_CONFIG */
! 569:
! 570: /*
! 571: * Restore unmarked small objects in the block pointed to by hbp
! 572: * to the appropriate object free list.
! 573: * If entirely empty blocks are to be completely deallocated, then
! 574: * caller should perform that check.
! 575: */
! 576: void GC_reclaim_small_nonempty_block(hbp, report_if_found)
! 577: register struct hblk *hbp; /* ptr to current heap block */
! 578: int report_if_found; /* Abort if a reclaimable object is found */
! 579: {
! 580: hdr * hhdr;
! 581: word sz; /* size of objects in current block */
! 582: struct obj_kind * ok;
! 583: ptr_t * flh;
! 584: int kind;
! 585: GC_bool full;
! 586:
! 587: hhdr = HDR(hbp);
! 588: sz = hhdr -> hb_sz;
! 589: hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
! 590: kind = hhdr -> hb_obj_kind;
! 591: ok = &GC_obj_kinds[kind];
! 592: flh = &(ok -> ok_freelist[sz]);
! 593:
! 594: if (report_if_found) {
! 595: GC_reclaim_check(hbp, hhdr, sz);
! 596: } else if (ok -> ok_init) {
! 597: switch(sz) {
! 598: # ifndef SMALL_CONFIG
! 599: case 1:
! 600: # if CPP_WORDSZ == 64
! 601: full = GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
! 602: # else
! 603: full = GC_block_nearly_full1(hhdr, 0xffffffffl);
! 604: # endif
! 605: if (TRUE == full) goto out;
! 606: if (FALSE == full) GC_write_hint(hbp);
! 607: /* In the DONT_KNOW case, we let reclaim fault. */
! 608: *flh = GC_reclaim1(hbp, hhdr, *flh);
! 609: break;
! 610: case 2:
! 611: # if CPP_WORDSZ == 64
! 612: full = GC_block_nearly_full1(hhdr, 0x5555555555555555l);
! 613: # else
! 614: full = GC_block_nearly_full1(hhdr, 0x55555555l);
! 615: # endif
! 616: if (TRUE == full) goto out;
! 617: if (FALSE == full) GC_write_hint(hbp);
! 618: *flh = GC_reclaim_clear2(hbp, hhdr, *flh);
! 619: break;
! 620: case 4:
! 621: # if CPP_WORDSZ == 64
! 622: full = GC_block_nearly_full1(hhdr, 0x1111111111111111l);
! 623: # else
! 624: full = GC_block_nearly_full1(hhdr, 0x11111111l);
! 625: # endif
! 626: if (TRUE == full) goto out;
! 627: if (FALSE == full) GC_write_hint(hbp);
! 628: *flh = GC_reclaim_clear4(hbp, hhdr, *flh);
! 629: break;
! 630: # endif
! 631: default:
! 632: full = GC_block_nearly_full(hhdr);
! 633: if (TRUE == full) goto out;
! 634: if (FALSE == full) GC_write_hint(hbp);
! 635: *flh = GC_reclaim_clear(hbp, hhdr, sz, *flh);
! 636: break;
! 637: }
! 638: } else {
! 639: switch(sz) {
! 640: # ifndef SMALL_CONFIG
! 641: case 1:
! 642: # if CPP_WORDSZ == 64
! 643: full = GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
! 644: # else
! 645: full = GC_block_nearly_full1(hhdr, 0xffffffffl);
! 646: # endif
! 647: if (TRUE == full) goto out;
! 648: if (FALSE == full) GC_write_hint(hbp);
! 649: *flh = GC_reclaim1(hbp, hhdr, *flh);
! 650: break;
! 651: case 2:
! 652: # if CPP_WORDSZ == 64
! 653: full = GC_block_nearly_full1(hhdr, 0x5555555555555555l);
! 654: # else
! 655: full = GC_block_nearly_full1(hhdr, 0x55555555l);
! 656: # endif
! 657: if (TRUE == full) goto out;
! 658: if (FALSE == full) GC_write_hint(hbp);
! 659: *flh = GC_reclaim_uninit2(hbp, hhdr, *flh);
! 660: break;
! 661: case 4:
! 662: # if CPP_WORDSZ == 64
! 663: full = GC_block_nearly_full1(hhdr, 0x1111111111111111l);
! 664: # else
! 665: full = GC_block_nearly_full1(hhdr, 0x11111111l);
! 666: # endif
! 667: if (TRUE == full) goto out;
! 668: if (FALSE == full) GC_write_hint(hbp);
! 669: *flh = GC_reclaim_uninit4(hbp, hhdr, *flh);
! 670: break;
! 671: # endif
! 672: default:
! 673: full = GC_block_nearly_full(hhdr);
! 674: if (TRUE == full) goto out;
! 675: if (FALSE == full) GC_write_hint(hbp);
! 676: *flh = GC_reclaim_uninit(hbp, hhdr, sz, *flh);
! 677: break;
! 678: }
! 679: }
! 680: out:
! 681: if (IS_UNCOLLECTABLE(kind)) GC_set_hdr_marks(hhdr);
! 682: }
! 683:
! 684: /*
! 685: * Restore an unmarked large object or an entirely empty blocks of small objects
! 686: * to the heap block free list.
! 687: * Otherwise enqueue the block for later processing
! 688: * by GC_reclaim_small_nonempty_block.
! 689: * If report_if_found is TRUE, then process any block immediately, and
! 690: * simply report free objects; do not actually reclaim them.
! 691: */
! 692: void GC_reclaim_block(hbp, report_if_found)
! 693: register struct hblk *hbp; /* ptr to current heap block */
! 694: word report_if_found; /* Abort if a reclaimable object is found */
! 695: {
! 696: register hdr * hhdr;
! 697: register word sz; /* size of objects in current block */
! 698: register struct obj_kind * ok;
! 699: struct hblk ** rlh;
! 700:
! 701: hhdr = HDR(hbp);
! 702: sz = hhdr -> hb_sz;
! 703: ok = &GC_obj_kinds[hhdr -> hb_obj_kind];
! 704:
! 705: if( sz > MAXOBJSZ ) { /* 1 big object */
! 706: if( !mark_bit_from_hdr(hhdr, HDR_WORDS) ) {
! 707: if (report_if_found) {
! 708: FOUND_FREE(hbp, HDR_WORDS);
! 709: } else {
! 710: # ifdef GATHERSTATS
! 711: GC_mem_found += sz;
! 712: # endif
! 713: GC_freehblk(hbp);
! 714: }
! 715: }
! 716: } else {
! 717: GC_bool empty = GC_block_empty(hhdr);
! 718: if (report_if_found) {
! 719: GC_reclaim_small_nonempty_block(hbp, (int)report_if_found);
! 720: } else if (empty) {
! 721: # ifdef GATHERSTATS
! 722: GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
! 723: # endif
! 724: GC_freehblk(hbp);
! 725: } else {
! 726: /* group of smaller objects, enqueue the real work */
! 727: rlh = &(ok -> ok_reclaim_list[sz]);
! 728: hhdr -> hb_next = *rlh;
! 729: *rlh = hbp;
! 730: }
! 731: }
! 732: }
! 733:
! 734: #if !defined(NO_DEBUGGING)
! 735: /* Routines to gather and print heap block info */
! 736: /* intended for debugging. Otherwise should be called */
! 737: /* with lock. */
! 738: static size_t number_of_blocks;
! 739: static size_t total_bytes;
! 740:
! 741: /* Number of set bits in a word. Not performance critical. */
! 742: static int set_bits(n)
! 743: word n;
! 744: {
! 745: register word m = n;
! 746: register int result = 0;
! 747:
! 748: while (m > 0) {
! 749: if (m & 1) result++;
! 750: m >>= 1;
! 751: }
! 752: return(result);
! 753: }
! 754:
! 755: /* Return the number of set mark bits in the given header */
! 756: int GC_n_set_marks(hhdr)
! 757: hdr * hhdr;
! 758: {
! 759: register int result = 0;
! 760: register int i;
! 761:
! 762: for (i = 0; i < MARK_BITS_SZ; i++) {
! 763: result += set_bits(hhdr -> hb_marks[i]);
! 764: }
! 765: return(result);
! 766: }
! 767:
! 768: /*ARGSUSED*/
! 769: void GC_print_block_descr(h, dummy)
! 770: struct hblk *h;
! 771: word dummy;
! 772: {
! 773: register hdr * hhdr = HDR(h);
! 774: register size_t bytes = WORDS_TO_BYTES(hhdr -> hb_sz);
! 775:
! 776: GC_printf3("(%lu:%lu,%lu)", (unsigned long)(hhdr -> hb_obj_kind),
! 777: (unsigned long)bytes,
! 778: (unsigned long)(GC_n_set_marks(hhdr)));
! 779: bytes += HDR_BYTES + HBLKSIZE-1;
! 780: bytes &= ~(HBLKSIZE-1);
! 781: total_bytes += bytes;
! 782: number_of_blocks++;
! 783: }
! 784:
! 785: void GC_print_block_list()
! 786: {
! 787: GC_printf0("(kind(0=ptrfree,1=normal,2=unc.,3=stubborn):size_in_bytes, #_marks_set)\n");
! 788: number_of_blocks = 0;
! 789: total_bytes = 0;
! 790: GC_apply_to_all_blocks(GC_print_block_descr, (word)0);
! 791: GC_printf2("\nblocks = %lu, bytes = %lu\n",
! 792: (unsigned long)number_of_blocks,
! 793: (unsigned long)total_bytes);
! 794: }
! 795:
! 796: #endif /* NO_DEBUGGING */
! 797:
! 798: /*
! 799: * Perform GC_reclaim_block on the entire heap, after first clearing
! 800: * small object free lists (if we are not just looking for leaks).
! 801: */
! 802: void GC_start_reclaim(report_if_found)
! 803: int report_if_found; /* Abort if a GC_reclaimable object is found */
! 804: {
! 805: int kind;
! 806:
! 807: /* Clear reclaim- and free-lists */
! 808: for (kind = 0; kind < GC_n_kinds; kind++) {
! 809: register ptr_t *fop;
! 810: register ptr_t *lim;
! 811: register struct hblk ** rlp;
! 812: register struct hblk ** rlim;
! 813: register struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
! 814:
! 815: if (rlist == 0) continue; /* This kind not used. */
! 816: if (!report_if_found) {
! 817: lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
! 818: for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
! 819: *fop = 0;
! 820: }
! 821: } /* otherwise free list objects are marked, */
! 822: /* and its safe to leave them */
! 823: rlim = rlist + MAXOBJSZ+1;
! 824: for( rlp = rlist; rlp < rlim; rlp++ ) {
! 825: *rlp = 0;
! 826: }
! 827: }
! 828:
! 829: # ifdef PRINTBLOCKS
! 830: GC_printf0("GC_reclaim: current block sizes:\n");
! 831: GC_print_block_list();
! 832: # endif
! 833:
! 834: /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
! 835: /* or enqueue the block for later processing. */
! 836: GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
! 837:
! 838: # ifdef EAGER_SWEEP
! 839: /* This is a very stupid thing to do. We make it possible anyway, */
! 840: /* so that you can convince yourself that it really is very stupid. */
! 841: GC_reclaim_all((GC_stop_func)0, FALSE);
! 842: # endif
! 843:
! 844: }
! 845:
! 846: /*
! 847: * Sweep blocks of the indicated object size and kind until either the
! 848: * appropriate free list is nonempty, or there are no more blocks to
! 849: * sweep.
! 850: */
! 851: void GC_continue_reclaim(sz, kind)
! 852: word sz; /* words */
! 853: int kind;
! 854: {
! 855: register hdr * hhdr;
! 856: register struct hblk * hbp;
! 857: register struct obj_kind * ok = &(GC_obj_kinds[kind]);
! 858: struct hblk ** rlh = ok -> ok_reclaim_list;
! 859: ptr_t *flh = &(ok -> ok_freelist[sz]);
! 860:
! 861: if (rlh == 0) return; /* No blocks of this kind. */
! 862: rlh += sz;
! 863: #if 0
! 864: GC_timerstart();
! 865: #endif
! 866: while ((hbp = *rlh) != 0) {
! 867: hhdr = HDR(hbp);
! 868: *rlh = hhdr -> hb_next;
! 869: GC_reclaim_small_nonempty_block(hbp, FALSE);
! 870: if (*flh != 0) break;
! 871: }
! 872: #if 0
! 873: GC_timerstop();
! 874: #endif
! 875: }
! 876:
! 877: /*
! 878: * Reclaim all small blocks waiting to be reclaimed.
! 879: * Abort and return FALSE when/if (*stop_func)() returns TRUE.
! 880: * If this returns TRUE, then it's safe to restart the world
! 881: * with incorrectly cleared mark bits.
! 882: * If ignore_old is TRUE, then reclaim only blocks that have been
! 883: * recently reclaimed, and discard the rest.
! 884: * Stop_func may be 0.
! 885: */
! 886: GC_bool GC_reclaim_all(stop_func, ignore_old)
! 887: GC_stop_func stop_func;
! 888: GC_bool ignore_old;
! 889: {
! 890: register word sz;
! 891: register int kind;
! 892: register hdr * hhdr;
! 893: register struct hblk * hbp;
! 894: register struct obj_kind * ok;
! 895: struct hblk ** rlp;
! 896: struct hblk ** rlh;
! 897: # ifdef PRINTTIMES
! 898: CLOCK_TYPE start_time;
! 899: CLOCK_TYPE done_time;
! 900:
! 901: GET_TIME(start_time);
! 902: # endif
! 903:
! 904: GC_timerstart();
! 905: for (kind = 0; kind < GC_n_kinds; kind++) {
! 906: ok = &(GC_obj_kinds[kind]);
! 907: rlp = ok -> ok_reclaim_list;
! 908: if (rlp == 0) continue;
! 909: for (sz = 1; sz <= MAXOBJSZ; sz++) {
! 910: rlh = rlp + sz;
! 911: while ((hbp = *rlh) != 0) {
! 912: if (stop_func != (GC_stop_func)0 && (*stop_func)()) {
! 913: return(FALSE);
! 914: }
! 915: hhdr = HDR(hbp);
! 916: *rlh = hhdr -> hb_next;
! 917: if (!ignore_old || hhdr -> hb_last_reclaimed == GC_gc_no - 1) {
! 918: /* It's likely we'll need it this time, too */
! 919: /* It's been touched recently, so this */
! 920: /* shouldn't trigger paging. */
! 921: GC_reclaim_small_nonempty_block(hbp, FALSE);
! 922: }
! 923: }
! 924: }
! 925: }
! 926: GC_timerstop();
! 927: # ifdef PRINTTIMES
! 928: GET_TIME(done_time);
! 929: GC_printf1("Disposing of reclaim lists took %lu msecs\n",
! 930: MS_TIME_DIFF(done_time,start_time));
! 931: # endif
! 932: return(TRUE);
! 933: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>