2 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
5 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
6 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
8 * Permission is hereby granted to use or copy this program
9 * for any purpose, provided the above notices are retained on all copies.
10 * Permission to modify the code and to distribute modified code is granted,
11 * provided the above notices are retained, and a notice that the code was
12 * modified is included with the above copyright notice.
14 /* Boehm, February 15, 1996 2:41 pm PST */
19 signed_word GC_mem_found = 0;
20 /* Number of words of memory reclaimed */
22 static void report_leak(p, sz)
26 if (HDR(p) -> hb_obj_kind == PTRFREE) {
27 GC_err_printf0("Leaked atomic object at ");
29 GC_err_printf0("Leaked composite object at ");
31 if (GC_debugging_started && GC_has_debug_info(p)) {
34 GC_err_printf2("0x%lx (appr. size = %ld)\n",
36 (unsigned long)WORDS_TO_BYTES(sz));
40 # define FOUND_FREE(hblk, word_no) \
42 report_leak((ptr_t)hblk + WORDS_TO_BYTES(word_no), \
43 HDR(hblk) -> hb_sz); \
53 * Test whether a block is completely empty, i.e. contains no marked
54 * objects. This does not require the block to be in physical
58 GC_bool GC_block_empty(hhdr)
61 register word *p = (word *)(&(hhdr -> hb_marks[0]));
62 register word * plim =
63 (word *)(&(hhdr -> hb_marks[MARK_BITS_SZ]));
65 if (*p++) return(FALSE);
71 # define INCR_WORDS(sz) n_words_found += (sz)
73 # define INCR_WORDS(sz)
76 * Restore unmarked small objects in h of size sz to the object
77 * free list. Returns the new list.
78 * Clears unmarked objects.
81 ptr_t GC_reclaim_clear(hbp, hhdr, sz, list)
82 register struct hblk *hbp; /* ptr to current heap block */
88 register word *p, *q, *plim;
90 register int n_words_found = 0;
93 p = (word *)(hbp->hb_body);
95 plim = (word *)((((word)hbp) + HBLKSIZE)
96 - WORDS_TO_BYTES(sz));
98 /* go through all words in block */
100 if( mark_bit_from_hdr(hhdr, word_no) ) {
104 /* object is available - put on list */
107 /* Clear object, advance p to next object in the process */
109 p++; /* Skip link field */
117 GC_mem_found += n_words_found;
125 * A special case for 2 word composite objects (e.g. cons cells):
128 ptr_t GC_reclaim_clear2(hbp, hhdr, list)
129 register struct hblk *hbp; /* ptr to current heap block */
133 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
134 register word *p, *plim;
136 register int n_words_found = 0;
138 register word mark_word;
140 # define DO_OBJ(start_displ) \
141 if (!(mark_word & ((word)1 << start_displ))) { \
142 p[start_displ] = (word)list; \
143 list = (ptr_t)(p+start_displ); \
144 p[start_displ+1] = 0; \
148 p = (word *)(hbp->hb_body);
149 plim = (word *)(((word)hbp) + HBLKSIZE);
151 /* go through all words in block */
153 mark_word = *mark_word_addr++;
154 for (i = 0; i < WORDSZ; i += 8) {
164 GC_mem_found += n_words_found;
171 * Another special case for 4 word composite objects:
174 ptr_t GC_reclaim_clear4(hbp, hhdr, list)
175 register struct hblk *hbp; /* ptr to current heap block */
179 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
180 register word *p, *plim;
182 register int n_words_found = 0;
184 register word mark_word;
185 # define DO_OBJ(start_displ) \
186 if (!(mark_word & ((word)1 << start_displ))) { \
187 p[start_displ] = (word)list; \
188 list = (ptr_t)(p+start_displ); \
189 p[start_displ+1] = 0; \
190 p[start_displ+2] = 0; \
191 p[start_displ+3] = 0; \
195 p = (word *)(hbp->hb_body);
196 plim = (word *)(((word)hbp) + HBLKSIZE);
198 /* go through all words in block */
200 mark_word = *mark_word_addr++;
209 # if CPP_WORDSZ == 64
222 GC_mem_found += n_words_found;
228 #endif /* !SMALL_CONFIG */
230 /* The same thing, but don't clear objects: */
232 ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list)
233 register struct hblk *hbp; /* ptr to current heap block */
238 register int word_no;
239 register word *p, *plim;
241 register int n_words_found = 0;
244 p = (word *)(hbp->hb_body);
246 plim = (word *)((((word)hbp) + HBLKSIZE)
247 - WORDS_TO_BYTES(sz));
249 /* go through all words in block */
251 if( !mark_bit_from_hdr(hhdr, word_no) ) {
253 /* object is available - put on list */
261 GC_mem_found += n_words_found;
266 /* Don't really reclaim objects, just check for unmarked ones: */
268 void GC_reclaim_check(hbp, hhdr, sz)
269 register struct hblk *hbp; /* ptr to current heap block */
273 register int word_no;
274 register word *p, *plim;
276 register int n_words_found = 0;
279 p = (word *)(hbp->hb_body);
281 plim = (word *)((((word)hbp) + HBLKSIZE)
282 - WORDS_TO_BYTES(sz));
284 /* go through all words in block */
286 if( !mark_bit_from_hdr(hhdr, word_no) ) {
287 FOUND_FREE(hbp, word_no);
296 * Another special case for 2 word atomic objects:
299 ptr_t GC_reclaim_uninit2(hbp, hhdr, list)
300 register struct hblk *hbp; /* ptr to current heap block */
304 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
305 register word *p, *plim;
307 register int n_words_found = 0;
309 register word mark_word;
311 # define DO_OBJ(start_displ) \
312 if (!(mark_word & ((word)1 << start_displ))) { \
313 p[start_displ] = (word)list; \
314 list = (ptr_t)(p+start_displ); \
318 p = (word *)(hbp->hb_body);
319 plim = (word *)(((word)hbp) + HBLKSIZE);
321 /* go through all words in block */
323 mark_word = *mark_word_addr++;
324 for (i = 0; i < WORDSZ; i += 8) {
334 GC_mem_found += n_words_found;
341 * Another special case for 4 word atomic objects:
344 ptr_t GC_reclaim_uninit4(hbp, hhdr, list)
345 register struct hblk *hbp; /* ptr to current heap block */
349 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
350 register word *p, *plim;
352 register int n_words_found = 0;
354 register word mark_word;
355 # define DO_OBJ(start_displ) \
356 if (!(mark_word & ((word)1 << start_displ))) { \
357 p[start_displ] = (word)list; \
358 list = (ptr_t)(p+start_displ); \
362 p = (word *)(hbp->hb_body);
363 plim = (word *)(((word)hbp) + HBLKSIZE);
365 /* go through all words in block */
367 mark_word = *mark_word_addr++;
376 # if CPP_WORDSZ == 64
389 GC_mem_found += n_words_found;
395 /* Finally the one word case, which never requires any clearing: */
397 ptr_t GC_reclaim1(hbp, hhdr, list)
398 register struct hblk *hbp; /* ptr to current heap block */
402 register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
403 register word *p, *plim;
405 register int n_words_found = 0;
407 register word mark_word;
409 # define DO_OBJ(start_displ) \
410 if (!(mark_word & ((word)1 << start_displ))) { \
411 p[start_displ] = (word)list; \
412 list = (ptr_t)(p+start_displ); \
416 p = (word *)(hbp->hb_body);
417 plim = (word *)(((word)hbp) + HBLKSIZE);
419 /* go through all words in block */
421 mark_word = *mark_word_addr++;
422 for (i = 0; i < WORDSZ; i += 4) {
432 GC_mem_found += n_words_found;
438 #endif /* !SMALL_CONFIG */
441 * Restore unmarked small objects in the block pointed to by hbp
442 * to the appropriate object free list.
443 * If entirely empty blocks are to be completely deallocated, then
444 * caller should perform that check.
446 void GC_reclaim_small_nonempty_block(hbp, report_if_found)
447 register struct hblk *hbp; /* ptr to current heap block */
448 int report_if_found; /* Abort if a reclaimable object is found */
451 register word sz; /* size of objects in current block */
452 register struct obj_kind * ok;
453 register ptr_t * flh;
458 hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
459 kind = hhdr -> hb_obj_kind;
460 ok = &GC_obj_kinds[kind];
461 flh = &(ok -> ok_freelist[sz]);
464 if (report_if_found) {
465 GC_reclaim_check(hbp, hhdr, sz);
466 } else if (ok -> ok_init) {
468 # ifndef SMALL_CONFIG
470 *flh = GC_reclaim1(hbp, hhdr, *flh);
473 *flh = GC_reclaim_clear2(hbp, hhdr, *flh);
476 *flh = GC_reclaim_clear4(hbp, hhdr, *flh);
480 *flh = GC_reclaim_clear(hbp, hhdr, sz, *flh);
485 # ifndef SMALL_CONFIG
487 *flh = GC_reclaim1(hbp, hhdr, *flh);
490 *flh = GC_reclaim_uninit2(hbp, hhdr, *flh);
493 *flh = GC_reclaim_uninit4(hbp, hhdr, *flh);
497 *flh = GC_reclaim_uninit(hbp, hhdr, sz, *flh);
501 if (IS_UNCOLLECTABLE(kind)) GC_set_hdr_marks(hhdr);
505 * Restore an unmarked large object or an entirely empty blocks of small objects
506 * to the heap block free list.
507 * Otherwise enqueue the block for later processing
508 * by GC_reclaim_small_nonempty_block.
509 * If report_if_found is TRUE, then process any block immediately, and
510 * simply report free objects; do not actually reclaim them.
512 void GC_reclaim_block(hbp, report_if_found)
513 register struct hblk *hbp; /* ptr to current heap block */
514 word report_if_found; /* Abort if a reclaimable object is found */
517 register word sz; /* size of objects in current block */
518 register struct obj_kind * ok;
523 ok = &GC_obj_kinds[hhdr -> hb_obj_kind];
525 if( sz > MAXOBJSZ ) { /* 1 big object */
526 if( !mark_bit_from_hdr(hhdr, HDR_WORDS) ) {
527 if (report_if_found) {
528 FOUND_FREE(hbp, HDR_WORDS);
537 GC_bool empty = GC_block_empty(hhdr);
538 if (report_if_found) {
539 GC_reclaim_small_nonempty_block(hbp, (int)report_if_found);
542 GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
546 /* group of smaller objects, enqueue the real work */
547 rlh = &(ok -> ok_reclaim_list[sz]);
548 hhdr -> hb_next = *rlh;
554 #if !defined(NO_DEBUGGING)
555 /* Routines to gather and print heap block info */
556 /* intended for debugging. Otherwise should be called */
558 static size_t number_of_blocks;
559 static size_t total_bytes;
561 /* Number of set bits in a word. Not performance critical. */
562 static int set_bits(n)
566 register int result = 0;
575 /* Return the number of set mark bits in the given header */
576 int GC_n_set_marks(hhdr)
579 register int result = 0;
582 for (i = 0; i < MARK_BITS_SZ; i++) {
583 result += set_bits(hhdr -> hb_marks[i]);
589 void GC_print_block_descr(h, dummy)
593 register hdr * hhdr = HDR(h);
594 register size_t bytes = WORDS_TO_BYTES(hhdr -> hb_sz);
596 GC_printf3("(%lu:%lu,%lu)", (unsigned long)(hhdr -> hb_obj_kind),
597 (unsigned long)bytes,
598 (unsigned long)(GC_n_set_marks(hhdr)));
599 bytes += HDR_BYTES + HBLKSIZE-1;
600 bytes &= ~(HBLKSIZE-1);
601 total_bytes += bytes;
605 void GC_print_block_list()
607 GC_printf0("(kind(0=ptrfree,1=normal,2=unc.,3=stubborn):size_in_bytes, #_marks_set)\n");
608 number_of_blocks = 0;
610 GC_apply_to_all_blocks(GC_print_block_descr, (word)0);
611 GC_printf2("\nblocks = %lu, bytes = %lu\n",
612 (unsigned long)number_of_blocks,
613 (unsigned long)total_bytes);
616 #endif /* NO_DEBUGGING */
619 * Perform GC_reclaim_block on the entire heap, after first clearing
620 * small object free lists (if we are not just looking for leaks).
622 void GC_start_reclaim(report_if_found)
623 int report_if_found; /* Abort if a GC_reclaimable object is found */
627 /* Clear reclaim- and free-lists */
628 for (kind = 0; kind < GC_n_kinds; kind++) {
631 register struct hblk ** rlp;
632 register struct hblk ** rlim;
633 register struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
635 if (rlist == 0) continue; /* This kind not used. */
636 if (!report_if_found) {
637 lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
638 for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
641 } /* otherwise free list objects are marked, */
642 /* and its safe to leave them */
643 rlim = rlist + MAXOBJSZ+1;
644 for( rlp = rlist; rlp < rlim; rlp++ ) {
650 GC_printf0("GC_reclaim: current block sizes:\n");
651 GC_print_block_list();
654 /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
655 /* or enqueue the block for later processing. */
656 GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
661 * Sweep blocks of the indicated object size and kind until either the
662 * appropriate free list is nonempty, or there are no more blocks to
665 void GC_continue_reclaim(sz, kind)
670 register struct hblk * hbp;
671 register struct obj_kind * ok = &(GC_obj_kinds[kind]);
672 struct hblk ** rlh = ok -> ok_reclaim_list;
673 ptr_t *flh = &(ok -> ok_freelist[sz]);
675 if (rlh == 0) return; /* No blocks of this kind. */
677 while ((hbp = *rlh) != 0) {
679 *rlh = hhdr -> hb_next;
680 GC_reclaim_small_nonempty_block(hbp, FALSE);
681 if (*flh != 0) break;
686 * Reclaim all small blocks waiting to be reclaimed.
687 * Abort and return FALSE when/if (*stop_func)() returns TRUE.
688 * If this returns TRUE, then it's safe to restart the world
689 * with incorrectly cleared mark bits.
690 * If ignore_old is TRUE, then reclain only blocks that have been
691 * recently reclaimed, and discard the rest.
692 * Stop_func may be 0.
694 GC_bool GC_reclaim_all(stop_func, ignore_old)
695 GC_stop_func stop_func;
701 register struct hblk * hbp;
702 register struct obj_kind * ok;
706 CLOCK_TYPE start_time;
707 CLOCK_TYPE done_time;
709 GET_TIME(start_time);
712 for (kind = 0; kind < GC_n_kinds; kind++) {
713 ok = &(GC_obj_kinds[kind]);
714 rlp = ok -> ok_reclaim_list;
715 if (rlp == 0) continue;
716 for (sz = 1; sz <= MAXOBJSZ; sz++) {
718 while ((hbp = *rlh) != 0) {
719 if (stop_func != (GC_stop_func)0 && (*stop_func)()) {
723 *rlh = hhdr -> hb_next;
724 if (!ignore_old || hhdr -> hb_last_reclaimed == GC_gc_no - 1) {
725 /* It's likely we'll need it this time, too */
726 /* It's been touched recently, so this */
727 /* shouldn't trigger paging. */
728 GC_reclaim_small_nonempty_block(hbp, FALSE);
735 GC_printf1("Disposing of reclaim lists took %lu msecs\n",
736 MS_TIME_DIFF(done_time,start_time));