boehm-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     GC_remove_protection(hbp, 1, (hhdr)->hb_descr == 0 /* Pointer-free? */);
 635     if (init) {
 636       switch(sz) {
 637 #      if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
 638         case 1:
 639             /* We now issue the hint even if GC_nearly_full returned    */
 640             /* DONT_KNOW.                                               */
 641             result = GC_reclaim1(hbp, hhdr, list COUNT_ARG);
 642             break;
 643         case 2:
 644             result = GC_reclaim_clear2(hbp, hhdr, list COUNT_ARG);
 645             break;
 646         case 4:
 647             result = GC_reclaim_clear4(hbp, hhdr, list COUNT_ARG);
 648             break;
 649 #      endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
 650         default:
 651             result = GC_reclaim_clear(hbp, hhdr, sz, list COUNT_ARG);
 652             break;
 653       }
 654     } else {
 655       GC_ASSERT((hhdr)->hb_descr == 0 /* Pointer-free block */);
 656       switch(sz) {
 657 #      if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
 658         case 1:
 659             result = GC_reclaim1(hbp, hhdr, list COUNT_ARG);
 660             break;
 661         case 2:
 662             result = GC_reclaim_uninit2(hbp, hhdr, list COUNT_ARG);
 663             break;
 664         case 4:
 665             result = GC_reclaim_uninit4(hbp, hhdr, list COUNT_ARG);
 666             break;
 667 #      endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
 668         default:
 669             result = GC_reclaim_uninit(hbp, hhdr, sz, list COUNT_ARG);
 670             break;
 671       }
 672     }
 673     if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) GC_set_hdr_marks(hhdr);
 674     return result;
 675 }
 676
 677 /*
 678  * Restore unmarked small objects in the block pointed to by hbp
 679  * to the appropriate object free list.
 680  * If entirely empty blocks are to be completely deallocated, then
 681  * caller should perform that check.
 682  */
 683 void GC_reclaim_small_nonempty_block(hbp, report_if_found COUNT_PARAM)
 684 register struct hblk *hbp;      /* ptr to current heap block            */
 685 int report_if_found;            /* Abort if a reclaimable object is found */
 686 COUNT_DECL
 687 {
 688     hdr *hhdr = HDR(hbp);
 689     word sz = hhdr -> hb_sz;
 690     int kind = hhdr -> hb_obj_kind;
 691     struct obj_kind * ok = &GC_obj_kinds[kind];
 692     ptr_t * flh = &(ok -> ok_freelist[sz]);
 693
 694     hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
 695
 696     if (report_if_found) {
 697         GC_reclaim_check(hbp, hhdr, sz);
 698     } else {
 699         *flh = GC_reclaim_generic(hbp, hhdr, sz,
 700                                   (ok -> ok_init || GC_debugging_started),
 701                                   *flh MEM_FOUND_ADDR);
 702     }
 703 }
 704
 705 /*
 706  * Restore an unmarked large object or an entirely empty blocks of small objects
 707  * to the heap block free list.
 708  * Otherwise enqueue the block for later processing
 709  * by GC_reclaim_small_nonempty_block.
 710  * If report_if_found is TRUE, then process any block immediately, and
 711  * simply report free objects; do not actually reclaim them.
 712  */
 713 # if defined(__STDC__) || defined(__cplusplus)
 714     void GC_reclaim_block(register struct hblk *hbp, word report_if_found)
 715 # else
 716     void GC_reclaim_block(hbp, report_if_found)
 717     register struct hblk *hbp;  /* ptr to current heap block            */
 718     word report_if_found;       /* Abort if a reclaimable object is found */
 719 # endif
 720 {
 721     register hdr * hhdr;
 722     register word sz;           /* size of objects in current block     */
 723     register struct obj_kind * ok;
 724     struct hblk ** rlh;
 725
 726     hhdr = HDR(hbp);
 727     sz = hhdr -> hb_sz;
 728     ok = &GC_obj_kinds[hhdr -> hb_obj_kind];
 729
 730     if( sz > MAXOBJSZ ) {  /* 1 big object */
 731         if( !mark_bit_from_hdr(hhdr, 0) ) {
 732             if (report_if_found) {
 733               FOUND_FREE(hbp, 0);
 734             } else {
 735               word blocks = OBJ_SZ_TO_BLOCKS(sz);
 736               if (blocks > 1) {
 737                 GC_large_allocd_bytes -= blocks * HBLKSIZE;
 738               }
 739 #             ifdef GATHERSTATS
 740                 GC_mem_found += sz;
 741 #             endif
 742               GC_freehblk(hbp);
 743             }
 744         }
 745     } else {
 746         GC_bool empty = GC_block_empty(hhdr);
 747         if (report_if_found) {
 748           GC_reclaim_small_nonempty_block(hbp, (int)report_if_found
 749                                           MEM_FOUND_ADDR);
 750         } else if (empty) {
 751 #         ifdef GATHERSTATS
 752             GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
 753 #         endif
 754           GC_freehblk(hbp);
 755         } else if (TRUE != GC_block_nearly_full(hhdr)){
 756           /* group of smaller objects, enqueue the real work */
 757           rlh = &(ok -> ok_reclaim_list[sz]);
 758           hhdr -> hb_next = *rlh;
 759           *rlh = hbp;
 760         } /* else not worth salvaging. */
 761         /* We used to do the nearly_full check later, but we    */
 762         /* already have the right cache context here.  Also     */
 763         /* doing it here avoids some silly lock contention in   */
 764         /* GC_malloc_many.                                      */
 765     }
 766 }
 767
 768 #if !defined(NO_DEBUGGING)
 769 /* Routines to gather and print heap block info         */
 770 /* intended for debugging.  Otherwise should be called  */
 771 /* with lock.                                           */
 772
 773 struct Print_stats
 774 {
 775         size_t number_of_blocks;
 776         size_t total_bytes;
 777 };
 778
 779 #ifdef USE_MARK_BYTES
 780
 781 /* Return the number of set mark bits in the given header       */
 782 int GC_n_set_marks(hhdr)
 783 hdr * hhdr;
 784 {
 785     register int result = 0;
 786     register int i;
 787
 788     for (i = 0; i < MARK_BITS_SZ; i++) {
 789         result += hhdr -> hb_marks[i];
 790     }
 791     return(result);
 792 }
 793
 794 #else
 795
 796 /* Number of set bits in a word.  Not performance critical.     */
 797 static int set_bits(n)
 798 word n;
 799 {
 800     register word m = n;
 801     register int result = 0;
 802
 803     while (m > 0) {
 804         if (m & 1) result++;
 805         m >>= 1;
 806     }
 807     return(result);
 808 }
 809
 810 /* Return the number of set mark bits in the given header       */
 811 int GC_n_set_marks(hhdr)
 812 hdr * hhdr;
 813 {
 814     register int result = 0;
 815     register int i;
 816
 817     for (i = 0; i < MARK_BITS_SZ; i++) {
 818         result += set_bits(hhdr -> hb_marks[i]);
 819     }
 820     return(result);
 821 }
 822
 823 #endif /* !USE_MARK_BYTES  */
 824
 825 /*ARGSUSED*/
 826 # if defined(__STDC__) || defined(__cplusplus)
 827     void GC_print_block_descr(struct hblk *h, word dummy)
 828 # else
 829     void GC_print_block_descr(h, dummy)
 830     struct hblk *h;
 831     word dummy;
 832 # endif
 833 {
 834     register hdr * hhdr = HDR(h);
 835     register size_t bytes = WORDS_TO_BYTES(hhdr -> hb_sz);
 836     struct Print_stats *ps;
 837
 838     GC_printf3("(%lu:%lu,%lu)", (unsigned long)(hhdr -> hb_obj_kind),
 839                                 (unsigned long)bytes,
 840                                 (unsigned long)(GC_n_set_marks(hhdr)));
 841     bytes += HBLKSIZE-1;
 842     bytes &= ~(HBLKSIZE-1);
 843
 844     ps = (struct Print_stats *)dummy;
 845     ps->total_bytes += bytes;
 846     ps->number_of_blocks++;
 847 }
 848
 849 void GC_print_block_list()
 850 {
 851     struct Print_stats pstats;
 852
 853     GC_printf0("(kind(0=ptrfree,1=normal,2=unc.,3=stubborn):size_in_bytes, #_marks_set)\n");
 854     pstats.number_of_blocks = 0;
 855     pstats.total_bytes = 0;
 856     GC_apply_to_all_blocks(GC_print_block_descr, (word)&pstats);
 857     GC_printf2("\nblocks = %lu, bytes = %lu\n",
 858                (unsigned long)pstats.number_of_blocks,
 859                (unsigned long)pstats.total_bytes);
 860 }
 861
 862 #endif /* NO_DEBUGGING */
 863
 864 /*
 865  * Clear all obj_link pointers in the list of free objects *flp.
 866  * Clear *flp.
 867  * This must be done before dropping a list of free gcj-style objects,
 868  * since may otherwise end up with dangling "descriptor" pointers.
 869  * It may help for other pointer-containg objects.
 870  */
 871 void GC_clear_fl_links(flp)
 872 ptr_t *flp;
 873 {
 874     ptr_t next = *flp;
 875
 876     while (0 != next) {
 877        *flp = 0;
 878        flp = &(obj_link(next));
 879        next = *flp;
 880     }
 881 }
 882
 883 /*
 884  * Perform GC_reclaim_block on the entire heap, after first clearing
 885  * small object free lists (if we are not just looking for leaks).
 886  */
 887 void GC_start_reclaim(report_if_found)
 888 int report_if_found;            /* Abort if a GC_reclaimable object is found */
 889 {
 890     int kind;
 891
 892 #   if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
 893       GC_ASSERT(0 == GC_fl_builder_count);
 894 #   endif
 895     /* Clear reclaim- and free-lists */
 896       for (kind = 0; kind < GC_n_kinds; kind++) {
 897         ptr_t *fop;
 898         ptr_t *lim;
 899         struct hblk ** rlp;
 900         struct hblk ** rlim;
 901         struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
 902         GC_bool should_clobber = (GC_obj_kinds[kind].ok_descriptor != 0);
 903
 904         if (rlist == 0) continue;       /* This kind not used.  */
 905         if (!report_if_found) {
 906             lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
 907             for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
 908               if (*fop != 0) {
 909                 if (should_clobber) {
 910                   GC_clear_fl_links(fop);
 911                 } else {
 912                   *fop = 0;
 913                 }
 914               }
 915             }
 916         } /* otherwise free list objects are marked,    */
 917           /* and its safe to leave them                 */
 918         rlim = rlist + MAXOBJSZ+1;
 919         for( rlp = rlist; rlp < rlim; rlp++ ) {
 920             *rlp = 0;
 921         }
 922       }
 923
 924 #   ifdef PRINTBLOCKS
 925         GC_printf0("GC_reclaim: current block sizes:\n");
 926         GC_print_block_list();
 927 #   endif
 928
 929   /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
 930   /* or enqueue the block for later processing.                            */
 931     GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
 932
 933 # ifdef EAGER_SWEEP
 934     /* This is a very stupid thing to do.  We make it possible anyway,  */
 935     /* so that you can convince yourself that it really is very stupid. */
 936     GC_reclaim_all((GC_stop_func)0, FALSE);
 937 # endif
 938 # if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
 939     GC_ASSERT(0 == GC_fl_builder_count);
 940 # endif
 941
 942 }
 943
 944 /*
 945  * Sweep blocks of the indicated object size and kind until either the
 946  * appropriate free list is nonempty, or there are no more blocks to
 947  * sweep.
 948  */
 949 void GC_continue_reclaim(sz, kind)
 950 word sz;        /* words */
 951 int kind;
 952 {
 953     register hdr * hhdr;
 954     register struct hblk * hbp;
 955     register struct obj_kind * ok = &(GC_obj_kinds[kind]);
 956     struct hblk ** rlh = ok -> ok_reclaim_list;
 957     ptr_t *flh = &(ok -> ok_freelist[sz]);
 958
 959     if (rlh == 0) return;       /* No blocks of this kind.      */
 960     rlh += sz;
 961     while ((hbp = *rlh) != 0) {
 962         hhdr = HDR(hbp);
 963         *rlh = hhdr -> hb_next;
 964         GC_reclaim_small_nonempty_block(hbp, FALSE MEM_FOUND_ADDR);
 965         if (*flh != 0) break;
 966     }
 967 }
 968
 969 /*
 970  * Reclaim all small blocks waiting to be reclaimed.
 971  * Abort and return FALSE when/if (*stop_func)() returns TRUE.
 972  * If this returns TRUE, then it's safe to restart the world
 973  * with incorrectly cleared mark bits.
 974  * If ignore_old is TRUE, then reclaim only blocks that have been
 975  * recently reclaimed, and discard the rest.
 976  * Stop_func may be 0.
 977  */
 978 GC_bool GC_reclaim_all(stop_func, ignore_old)
 979 GC_stop_func stop_func;
 980 GC_bool ignore_old;
 981 {
 982     register word sz;
 983     register int kind;
 984     register hdr * hhdr;
 985     register struct hblk * hbp;
 986     register struct obj_kind * ok;
 987     struct hblk ** rlp;
 988     struct hblk ** rlh;
 989 #   ifdef PRINTTIMES
 990         CLOCK_TYPE start_time;
 991         CLOCK_TYPE done_time;
 992
 993         GET_TIME(start_time);
 994 #   endif
 995
 996     for (kind = 0; kind < GC_n_kinds; kind++) {
 997         ok = &(GC_obj_kinds[kind]);
 998         rlp = ok -> ok_reclaim_list;
 999         if (rlp == 0) continue;
1000         for (sz = 1; sz <= MAXOBJSZ; sz++) {
1001             rlh = rlp + sz;
1002             while ((hbp = *rlh) != 0) {
1003                 if (stop_func != (GC_stop_func)0 && (*stop_func)()) {
1004                     return(FALSE);
1005                 }
1006                 hhdr = HDR(hbp);
1007                 *rlh = hhdr -> hb_next;
1008                 if (!ignore_old || hhdr -> hb_last_reclaimed == GC_gc_no - 1) {
1009                     /* It's likely we'll need it this time, too */
1010                     /* It's been touched recently, so this      */
1011                     /* shouldn't trigger paging.                */
1012                     GC_reclaim_small_nonempty_block(hbp, FALSE MEM_FOUND_ADDR);
1013                 }
1014             }
1015         }
1016     }
1017 #   ifdef PRINTTIMES
1018         GET_TIME(done_time);
1019         GC_printf1("Disposing of reclaim lists took %lu msecs\n",
1020                    MS_TIME_DIFF(done_time,start_time));
1021 #   endif
1022     return(TRUE);
1023 }