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.
7 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
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.
20 signed_word GC_mem_found = 0;
21 /* Number of words of memory reclaimed */
23 static void report_leak(p, sz)
27 if (HDR(p) -> hb_obj_kind == PTRFREE) {
28 GC_err_printf0("Leaked atomic object at ");
30 GC_err_printf0("Leaked composite object at ");
36 # define FOUND_FREE(hblk, word_no) \
38 report_leak((ptr_t)hblk + WORDS_TO_BYTES(word_no), \
39 HDR(hblk) -> hb_sz); \
49 * Test whether a block is completely empty, i.e. contains no marked
50 * objects. This does not require the block to be in physical
54 GC_bool GC_block_empty(hhdr)
57 register word *p = (word *)(&(hhdr -> hb_marks[0]));
58 register word * plim =
59 (word *)(&(hhdr -> hb_marks[MARK_BITS_SZ]));
61 if (*p++) return(FALSE);
66 /* The following functions sometimes return a DONT_KNOW value. */
70 # define GC_block_nearly_full1(hhdr, pat1) DONT_KNOW
71 # define GC_block_nearly_full3(hhdr, pat1, pat2) DONT_KNOW
72 # define GC_block_nearly_full(hhdr) DONT_KNOW
76 * Test whether nearly all of the mark words consist of the same
79 #define FULL_THRESHOLD (MARK_BITS_SZ/16)
81 GC_bool GC_block_nearly_full1(hhdr, pat1)
87 GC_ASSERT((MARK_BITS_SZ & 1) == 0);
88 for (i = 0; i < MARK_BITS_SZ; ++i) {
89 if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
90 if (++misses > FULL_THRESHOLD) return FALSE;
97 * Test whether the same repeating 3 word pattern occurs in nearly
98 * all the mark bit slots.
99 * This is used as a heuristic, so we're a bit sloppy and ignore
100 * the last one or two words.
102 GC_bool GC_block_nearly_full3(hhdr, pat1, pat2, pat3)
104 word pat1, pat2, pat3;
109 if (MARK_BITS_SZ < 4) {
112 for (i = 0; i < MARK_BITS_SZ - 2; i += 3) {
113 if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
114 if (++misses > FULL_THRESHOLD) return FALSE;
116 if ((hhdr -> hb_marks[i+1] | ~pat2) != ONES) {
117 if (++misses > FULL_THRESHOLD) return FALSE;
119 if ((hhdr -> hb_marks[i+2] | ~pat3) != ONES) {
120 if (++misses > FULL_THRESHOLD) return FALSE;
126 /* Check whether a small object block is nearly full by looking at only */
128 /* We manually precomputed the mark bit patterns that need to be */
129 /* checked for, and we give up on the ones that are unlikely to occur, */
130 /* or have period > 3. */
131 /* This would be a lot easier with a mark bit per object instead of per */
132 /* word, but that would rewuire computing object numbers in the mark */
133 /* loop, which would require different data structures ... */
134 GC_bool GC_block_nearly_full(hhdr)
137 int sz = hhdr -> hb_sz;
139 # if CPP_WORDSZ != 32 && CPP_WORDSZ != 64
140 return DONT_KNOW; /* Shouldn't be used in any standard config. */
142 if (0 != HDR_WORDS) return DONT_KNOW;
143 /* Also shouldn't happen */
144 # if CPP_WORDSZ == 32
147 return GC_block_nearly_full1(hhdr, 0xffffffffl);
149 return GC_block_nearly_full1(hhdr, 0x55555555l);
151 return GC_block_nearly_full1(hhdr, 0x11111111l);
153 return GC_block_nearly_full3(hhdr, 0x41041041l,
157 return GC_block_nearly_full1(hhdr, 0x01010101l);
159 return GC_block_nearly_full3(hhdr, 0x01001001l,
163 return GC_block_nearly_full1(hhdr, 0x00010001l);
165 return GC_block_nearly_full1(hhdr, 0x00000001l);
170 # if CPP_WORDSZ == 64
173 return GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
175 return GC_block_nearly_full1(hhdr, 0x5555555555555555l);
177 return GC_block_nearly_full1(hhdr, 0x1111111111111111l);
179 return GC_block_nearly_full3(hhdr, 0x1041041041041041l,
181 0x0410410410410410l);
183 return GC_block_nearly_full1(hhdr, 0x0101010101010101l);
185 return GC_block_nearly_full3(hhdr, 0x1001001001001001l,
187 0x0010010010010010l);
189 return GC_block_nearly_full1(hhdr, 0x0001000100010001l);
191 return GC_block_nearly_full1(hhdr, 0x0000000100000001l);
197 #endif /* !SMALL_CONFIG */
200 # define INCR_WORDS(sz) n_words_found += (sz)
202 # define INCR_WORDS(sz)
205 * Restore unmarked small objects in h of size sz to the object
206 * free list. Returns the new list.
207 * Clears unmarked objects.
210 ptr_t GC_reclaim_clear(hbp, hhdr, sz, list)
211 register struct hblk *hbp; /* ptr to current heap block */
216 register int word_no;
217 register word *p, *q, *plim;
219 register int n_words_found = 0;
222 p = (word *)(hbp->hb_body);
224 plim = (word *)((((word)hbp) + HBLKSIZE)
225 - WORDS_TO_BYTES(sz));
227 /* go through all words in block */
229 if( mark_bit_from_hdr(hhdr, word_no) ) {
233 /* object is available - put on list */
236 /* Clear object, advance p to next object in the process */
238 p++; /* Skip link field */
246 GC_mem_found += n_words_found;
254 * A special case for 2 word composite objects (e.g. cons cells):
257 ptr_t GC_reclaim_clear2(hbp, hhdr, list)
258 register struct hblk *hbp; /* ptr to current heap block */
262 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
263 register word *p, *plim;
265 register int n_words_found = 0;
267 register word mark_word;
269 # define DO_OBJ(start_displ) \
270 if (!(mark_word & ((word)1 << start_displ))) { \
271 p[start_displ] = (word)list; \
272 list = (ptr_t)(p+start_displ); \
273 p[start_displ+1] = 0; \
277 p = (word *)(hbp->hb_body);
278 plim = (word *)(((word)hbp) + HBLKSIZE);
280 /* go through all words in block */
282 mark_word = *mark_word_addr++;
283 for (i = 0; i < WORDSZ; i += 8) {
293 GC_mem_found += n_words_found;
300 * Another special case for 4 word composite objects:
303 ptr_t GC_reclaim_clear4(hbp, hhdr, list)
304 register struct hblk *hbp; /* ptr to current heap block */
308 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
309 register word *p, *plim;
311 register int n_words_found = 0;
313 register word mark_word;
314 # define DO_OBJ(start_displ) \
315 if (!(mark_word & ((word)1 << start_displ))) { \
316 p[start_displ] = (word)list; \
317 list = (ptr_t)(p+start_displ); \
318 p[start_displ+1] = 0; \
319 CLEAR_DOUBLE(p + start_displ + 2); \
323 p = (word *)(hbp->hb_body);
324 plim = (word *)(((word)hbp) + HBLKSIZE);
326 /* go through all words in block */
328 mark_word = *mark_word_addr++;
337 # if CPP_WORDSZ == 64
350 GC_mem_found += n_words_found;
356 #endif /* !SMALL_CONFIG */
358 /* The same thing, but don't clear objects: */
360 ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list)
361 register struct hblk *hbp; /* ptr to current heap block */
366 register int word_no;
367 register word *p, *plim;
369 register int n_words_found = 0;
372 p = (word *)(hbp->hb_body);
374 plim = (word *)((((word)hbp) + HBLKSIZE)
375 - WORDS_TO_BYTES(sz));
377 /* go through all words in block */
379 if( !mark_bit_from_hdr(hhdr, word_no) ) {
381 /* object is available - put on list */
389 GC_mem_found += n_words_found;
394 /* Don't really reclaim objects, just check for unmarked ones: */
396 void GC_reclaim_check(hbp, hhdr, sz)
397 register struct hblk *hbp; /* ptr to current heap block */
401 register int word_no;
402 register word *p, *plim;
404 register int n_words_found = 0;
407 p = (word *)(hbp->hb_body);
409 plim = (word *)((((word)hbp) + HBLKSIZE)
410 - WORDS_TO_BYTES(sz));
412 /* go through all words in block */
414 if( !mark_bit_from_hdr(hhdr, word_no) ) {
415 FOUND_FREE(hbp, word_no);
424 * Another special case for 2 word atomic objects:
427 ptr_t GC_reclaim_uninit2(hbp, hhdr, list)
428 register struct hblk *hbp; /* ptr to current heap block */
432 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
433 register word *p, *plim;
435 register int n_words_found = 0;
437 register word mark_word;
439 # define DO_OBJ(start_displ) \
440 if (!(mark_word & ((word)1 << start_displ))) { \
441 p[start_displ] = (word)list; \
442 list = (ptr_t)(p+start_displ); \
446 p = (word *)(hbp->hb_body);
447 plim = (word *)(((word)hbp) + HBLKSIZE);
449 /* go through all words in block */
451 mark_word = *mark_word_addr++;
452 for (i = 0; i < WORDSZ; i += 8) {
462 GC_mem_found += n_words_found;
469 * Another special case for 4 word atomic objects:
472 ptr_t GC_reclaim_uninit4(hbp, hhdr, list)
473 register struct hblk *hbp; /* ptr to current heap block */
477 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
478 register word *p, *plim;
480 register int n_words_found = 0;
482 register word mark_word;
483 # define DO_OBJ(start_displ) \
484 if (!(mark_word & ((word)1 << start_displ))) { \
485 p[start_displ] = (word)list; \
486 list = (ptr_t)(p+start_displ); \
490 p = (word *)(hbp->hb_body);
491 plim = (word *)(((word)hbp) + HBLKSIZE);
493 /* go through all words in block */
495 mark_word = *mark_word_addr++;
504 # if CPP_WORDSZ == 64
517 GC_mem_found += n_words_found;
523 /* Finally the one word case, which never requires any clearing: */
525 ptr_t GC_reclaim1(hbp, hhdr, list)
526 register struct hblk *hbp; /* ptr to current heap block */
530 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
531 register word *p, *plim;
533 register int n_words_found = 0;
535 register word mark_word;
537 # define DO_OBJ(start_displ) \
538 if (!(mark_word & ((word)1 << start_displ))) { \
539 p[start_displ] = (word)list; \
540 list = (ptr_t)(p+start_displ); \
544 p = (word *)(hbp->hb_body);
545 plim = (word *)(((word)hbp) + HBLKSIZE);
547 /* go through all words in block */
549 mark_word = *mark_word_addr++;
550 for (i = 0; i < WORDSZ; i += 4) {
560 GC_mem_found += n_words_found;
566 #endif /* !SMALL_CONFIG */
569 * Restore unmarked small objects in the block pointed to by hbp
570 * to the appropriate object free list.
571 * If entirely empty blocks are to be completely deallocated, then
572 * caller should perform that check.
574 void GC_reclaim_small_nonempty_block(hbp, report_if_found)
575 register struct hblk *hbp; /* ptr to current heap block */
576 int report_if_found; /* Abort if a reclaimable object is found */
579 word sz; /* size of objects in current block */
580 struct obj_kind * ok;
587 hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
588 kind = hhdr -> hb_obj_kind;
589 ok = &GC_obj_kinds[kind];
590 flh = &(ok -> ok_freelist[sz]);
592 if (report_if_found) {
593 GC_reclaim_check(hbp, hhdr, sz);
594 } else if (ok -> ok_init) {
596 # ifndef SMALL_CONFIG
598 # if CPP_WORDSZ == 64
599 full = GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
601 full = GC_block_nearly_full1(hhdr, 0xffffffffl);
603 if (TRUE == full) goto out;
604 if (FALSE == full) GC_write_hint(hbp);
605 /* In the DONT_KNOW case, we let reclaim fault. */
606 *flh = GC_reclaim1(hbp, hhdr, *flh);
609 # if CPP_WORDSZ == 64
610 full = GC_block_nearly_full1(hhdr, 0x5555555555555555l);
612 full = GC_block_nearly_full1(hhdr, 0x55555555l);
614 if (TRUE == full) goto out;
615 if (FALSE == full) GC_write_hint(hbp);
616 *flh = GC_reclaim_clear2(hbp, hhdr, *flh);
619 # if CPP_WORDSZ == 64
620 full = GC_block_nearly_full1(hhdr, 0x1111111111111111l);
622 full = GC_block_nearly_full1(hhdr, 0x11111111l);
624 if (TRUE == full) goto out;
625 if (FALSE == full) GC_write_hint(hbp);
626 *flh = GC_reclaim_clear4(hbp, hhdr, *flh);
630 full = GC_block_nearly_full(hhdr);
631 if (TRUE == full) goto out;
632 if (FALSE == full) GC_write_hint(hbp);
633 *flh = GC_reclaim_clear(hbp, hhdr, sz, *flh);
638 # ifndef SMALL_CONFIG
640 # if CPP_WORDSZ == 64
641 full = GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
643 full = GC_block_nearly_full1(hhdr, 0xffffffffl);
645 if (TRUE == full) goto out;
646 if (FALSE == full) GC_write_hint(hbp);
647 *flh = GC_reclaim1(hbp, hhdr, *flh);
650 # if CPP_WORDSZ == 64
651 full = GC_block_nearly_full1(hhdr, 0x5555555555555555l);
653 full = GC_block_nearly_full1(hhdr, 0x55555555l);
655 if (TRUE == full) goto out;
656 if (FALSE == full) GC_write_hint(hbp);
657 *flh = GC_reclaim_uninit2(hbp, hhdr, *flh);
660 # if CPP_WORDSZ == 64
661 full = GC_block_nearly_full1(hhdr, 0x1111111111111111l);
663 full = GC_block_nearly_full1(hhdr, 0x11111111l);
665 if (TRUE == full) goto out;
666 if (FALSE == full) GC_write_hint(hbp);
667 *flh = GC_reclaim_uninit4(hbp, hhdr, *flh);
671 full = GC_block_nearly_full(hhdr);
672 if (TRUE == full) goto out;
673 if (FALSE == full) GC_write_hint(hbp);
674 *flh = GC_reclaim_uninit(hbp, hhdr, sz, *flh);
679 if (IS_UNCOLLECTABLE(kind)) GC_set_hdr_marks(hhdr);
683 * Restore an unmarked large object or an entirely empty blocks of small objects
684 * to the heap block free list.
685 * Otherwise enqueue the block for later processing
686 * by GC_reclaim_small_nonempty_block.
687 * If report_if_found is TRUE, then process any block immediately, and
688 * simply report free objects; do not actually reclaim them.
690 void GC_reclaim_block(hbp, report_if_found)
691 register struct hblk *hbp; /* ptr to current heap block */
692 word report_if_found; /* Abort if a reclaimable object is found */
695 register word sz; /* size of objects in current block */
696 register struct obj_kind * ok;
701 ok = &GC_obj_kinds[hhdr -> hb_obj_kind];
703 if( sz > MAXOBJSZ ) { /* 1 big object */
704 if( !mark_bit_from_hdr(hhdr, HDR_WORDS) ) {
705 if (report_if_found) {
706 FOUND_FREE(hbp, HDR_WORDS);
715 GC_bool empty = GC_block_empty(hhdr);
716 if (report_if_found) {
717 GC_reclaim_small_nonempty_block(hbp, (int)report_if_found);
720 GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
724 /* group of smaller objects, enqueue the real work */
725 rlh = &(ok -> ok_reclaim_list[sz]);
726 hhdr -> hb_next = *rlh;
732 #if !defined(NO_DEBUGGING)
733 /* Routines to gather and print heap block info */
734 /* intended for debugging. Otherwise should be called */
736 static size_t number_of_blocks;
737 static size_t total_bytes;
739 /* Number of set bits in a word. Not performance critical. */
740 static int set_bits(n)
744 register int result = 0;
753 /* Return the number of set mark bits in the given header */
754 int GC_n_set_marks(hhdr)
757 register int result = 0;
760 for (i = 0; i < MARK_BITS_SZ; i++) {
761 result += set_bits(hhdr -> hb_marks[i]);
767 void GC_print_block_descr(h, dummy)
771 register hdr * hhdr = HDR(h);
772 register size_t bytes = WORDS_TO_BYTES(hhdr -> hb_sz);
774 GC_printf3("(%lu:%lu,%lu)", (unsigned long)(hhdr -> hb_obj_kind),
775 (unsigned long)bytes,
776 (unsigned long)(GC_n_set_marks(hhdr)));
777 bytes += HDR_BYTES + HBLKSIZE-1;
778 bytes &= ~(HBLKSIZE-1);
779 total_bytes += bytes;
783 void GC_print_block_list()
785 GC_printf0("(kind(0=ptrfree,1=normal,2=unc.,3=stubborn):size_in_bytes, #_marks_set)\n");
786 number_of_blocks = 0;
788 GC_apply_to_all_blocks(GC_print_block_descr, (word)0);
789 GC_printf2("\nblocks = %lu, bytes = %lu\n",
790 (unsigned long)number_of_blocks,
791 (unsigned long)total_bytes);
794 #endif /* NO_DEBUGGING */
797 * Perform GC_reclaim_block on the entire heap, after first clearing
798 * small object free lists (if we are not just looking for leaks).
800 void GC_start_reclaim(report_if_found)
801 int report_if_found; /* Abort if a GC_reclaimable object is found */
805 /* Clear reclaim- and free-lists */
806 for (kind = 0; kind < GC_n_kinds; kind++) {
809 register struct hblk ** rlp;
810 register struct hblk ** rlim;
811 register struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
813 if (rlist == 0) continue; /* This kind not used. */
814 if (!report_if_found) {
815 lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
816 for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
819 } /* otherwise free list objects are marked, */
820 /* and its safe to leave them */
821 rlim = rlist + MAXOBJSZ+1;
822 for( rlp = rlist; rlp < rlim; rlp++ ) {
828 GC_printf0("GC_reclaim: current block sizes:\n");
829 GC_print_block_list();
832 /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
833 /* or enqueue the block for later processing. */
834 GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
837 /* This is a very stupid thing to do. We make it possible anyway, */
838 /* so that you can convince yourself that it really is very stupid. */
839 GC_reclaim_all((GC_stop_func)0, FALSE);
845 * Sweep blocks of the indicated object size and kind until either the
846 * appropriate free list is nonempty, or there are no more blocks to
849 void GC_continue_reclaim(sz, kind)
854 register struct hblk * hbp;
855 register struct obj_kind * ok = &(GC_obj_kinds[kind]);
856 struct hblk ** rlh = ok -> ok_reclaim_list;
857 ptr_t *flh = &(ok -> ok_freelist[sz]);
859 if (rlh == 0) return; /* No blocks of this kind. */
861 while ((hbp = *rlh) != 0) {
863 *rlh = hhdr -> hb_next;
864 GC_reclaim_small_nonempty_block(hbp, FALSE);
865 if (*flh != 0) break;
870 * Reclaim all small blocks waiting to be reclaimed.
871 * Abort and return FALSE when/if (*stop_func)() returns TRUE.
872 * If this returns TRUE, then it's safe to restart the world
873 * with incorrectly cleared mark bits.
874 * If ignore_old is TRUE, then reclaim only blocks that have been
875 * recently reclaimed, and discard the rest.
876 * Stop_func may be 0.
878 GC_bool GC_reclaim_all(stop_func, ignore_old)
879 GC_stop_func stop_func;
885 register struct hblk * hbp;
886 register struct obj_kind * ok;
890 CLOCK_TYPE start_time;
891 CLOCK_TYPE done_time;
893 GET_TIME(start_time);
896 for (kind = 0; kind < GC_n_kinds; kind++) {
897 ok = &(GC_obj_kinds[kind]);
898 rlp = ok -> ok_reclaim_list;
899 if (rlp == 0) continue;
900 for (sz = 1; sz <= MAXOBJSZ; sz++) {
902 while ((hbp = *rlh) != 0) {
903 if (stop_func != (GC_stop_func)0 && (*stop_func)()) {
907 *rlh = hhdr -> hb_next;
908 if (!ignore_old || hhdr -> hb_last_reclaimed == GC_gc_no - 1) {
909 /* It's likely we'll need it this time, too */
910 /* It's been touched recently, so this */
911 /* shouldn't trigger paging. */
912 GC_reclaim_small_nonempty_block(hbp, FALSE);
919 GC_printf1("Disposing of reclaim lists took %lu msecs\n",
920 MS_TIME_DIFF(done_time,start_time));