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