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