gc/reclaim.c

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