Annotation of OpenXM_contrib/gc/reclaim.c, Revision 1.1.1.2
1.1 maekawa 1: /*
2: * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
1.1.1.2 ! maekawa 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.
1.1 maekawa 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 "gc_priv.h"
19:
20: signed_word GC_mem_found = 0;
21: /* Number of words of memory reclaimed */
22:
23: static void report_leak(p, sz)
24: ptr_t p;
25: word sz;
26: {
27: if (HDR(p) -> hb_obj_kind == PTRFREE) {
28: GC_err_printf0("Leaked atomic object at ");
29: } else {
30: GC_err_printf0("Leaked composite object at ");
31: }
32: if (GC_debugging_started && GC_has_debug_info(p)) {
33: GC_print_obj(p);
34: } else {
35: GC_err_printf2("0x%lx (appr. size = %ld)\n",
36: (unsigned long)p,
37: (unsigned long)WORDS_TO_BYTES(sz));
38: }
39: }
40:
41: # define FOUND_FREE(hblk, word_no) \
1.1.1.2 ! maekawa 42: { \
1.1 maekawa 43: report_leak((ptr_t)hblk + WORDS_TO_BYTES(word_no), \
44: HDR(hblk) -> hb_sz); \
45: }
46:
47: /*
48: * reclaim phase
49: *
50: */
51:
52:
53: /*
54: * Test whether a block is completely empty, i.e. contains no marked
55: * objects. This does not require the block to be in physical
56: * memory.
57: */
58:
59: GC_bool GC_block_empty(hhdr)
60: register hdr * hhdr;
61: {
62: register word *p = (word *)(&(hhdr -> hb_marks[0]));
63: register word * plim =
64: (word *)(&(hhdr -> hb_marks[MARK_BITS_SZ]));
65: while (p < plim) {
66: if (*p++) return(FALSE);
67: }
68: return(TRUE);
69: }
70:
1.1.1.2 ! maekawa 71: /* The following functions sometimes return a DONT_KNOW value. */
! 72: #define DONT_KNOW 2
! 73:
! 74: #ifdef SMALL_CONFIG
! 75: # define GC_block_nearly_full1(hhdr, pat1) DONT_KNOW
! 76: # define GC_block_nearly_full3(hhdr, pat1, pat2) DONT_KNOW
! 77: # define GC_block_nearly_full(hhdr) DONT_KNOW
! 78: #else
! 79:
! 80: /*
! 81: * Test whether nearly all of the mark words consist of the same
! 82: * repeating pattern.
! 83: */
! 84: #define FULL_THRESHOLD (MARK_BITS_SZ/16)
! 85:
! 86: GC_bool GC_block_nearly_full1(hhdr, pat1)
! 87: hdr *hhdr;
! 88: word pat1;
! 89: {
! 90: unsigned i;
! 91: unsigned misses = 0;
! 92: GC_ASSERT((MARK_BITS_SZ & 1) == 0);
! 93: for (i = 0; i < MARK_BITS_SZ; ++i) {
! 94: if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
! 95: if (++misses > FULL_THRESHOLD) return FALSE;
! 96: }
! 97: }
! 98: return TRUE;
! 99: }
! 100:
! 101: /*
! 102: * Test whether the same repeating 3 word pattern occurs in nearly
! 103: * all the mark bit slots.
! 104: * This is used as a heuristic, so we're a bit sloppy and ignore
! 105: * the last one or two words.
! 106: */
! 107: GC_bool GC_block_nearly_full3(hhdr, pat1, pat2, pat3)
! 108: hdr *hhdr;
! 109: word pat1, pat2, pat3;
! 110: {
! 111: unsigned i;
! 112: unsigned misses = 0;
! 113:
! 114: if (MARK_BITS_SZ < 4) {
! 115: return DONT_KNOW;
! 116: }
! 117: for (i = 0; i < MARK_BITS_SZ - 2; i += 3) {
! 118: if ((hhdr -> hb_marks[i] | ~pat1) != ONES) {
! 119: if (++misses > FULL_THRESHOLD) return FALSE;
! 120: }
! 121: if ((hhdr -> hb_marks[i+1] | ~pat2) != ONES) {
! 122: if (++misses > FULL_THRESHOLD) return FALSE;
! 123: }
! 124: if ((hhdr -> hb_marks[i+2] | ~pat3) != ONES) {
! 125: if (++misses > FULL_THRESHOLD) return FALSE;
! 126: }
! 127: }
! 128: return TRUE;
! 129: }
! 130:
! 131: /* Check whether a small object block is nearly full by looking at only */
! 132: /* the mark bits. */
! 133: /* We manually precomputed the mark bit patterns that need to be */
! 134: /* checked for, and we give up on the ones that are unlikely to occur, */
! 135: /* or have period > 3. */
! 136: /* This would be a lot easier with a mark bit per object instead of per */
! 137: /* word, but that would rewuire computing object numbers in the mark */
! 138: /* loop, which would require different data structures ... */
! 139: GC_bool GC_block_nearly_full(hhdr)
! 140: hdr *hhdr;
! 141: {
! 142: int sz = hhdr -> hb_sz;
! 143:
! 144: # if CPP_WORDSZ != 32 && CPP_WORDSZ != 64
! 145: return DONT_KNOW; /* Shouldn't be used in any standard config. */
! 146: # endif
! 147: if (0 != HDR_WORDS) return DONT_KNOW;
! 148: /* Also shouldn't happen */
! 149: # if CPP_WORDSZ == 32
! 150: switch(sz) {
! 151: case 1:
! 152: return GC_block_nearly_full1(hhdr, 0xffffffffl);
! 153: case 2:
! 154: return GC_block_nearly_full1(hhdr, 0x55555555l);
! 155: case 4:
! 156: return GC_block_nearly_full1(hhdr, 0x11111111l);
! 157: case 6:
! 158: return GC_block_nearly_full3(hhdr, 0x41041041l,
! 159: 0x10410410l,
! 160: 0x04104104l);
! 161: case 8:
! 162: return GC_block_nearly_full1(hhdr, 0x01010101l);
! 163: case 12:
! 164: return GC_block_nearly_full3(hhdr, 0x01001001l,
! 165: 0x10010010l,
! 166: 0x00100100l);
! 167: case 16:
! 168: return GC_block_nearly_full1(hhdr, 0x00010001l);
! 169: case 32:
! 170: return GC_block_nearly_full1(hhdr, 0x00000001l);
! 171: default:
! 172: return DONT_KNOW;
! 173: }
! 174: # endif
! 175: # if CPP_WORDSZ == 64
! 176: switch(sz) {
! 177: case 1:
! 178: return GC_block_nearly_full1(hhdr, 0xffffffffffffffffl);
! 179: case 2:
! 180: return GC_block_nearly_full1(hhdr, 0x5555555555555555l);
! 181: case 4:
! 182: return GC_block_nearly_full1(hhdr, 0x1111111111111111l);
! 183: case 6:
! 184: return GC_block_nearly_full3(hhdr, 0x1041041041041041l,
! 185: 0x4104104104104104l,
! 186: 0x0410410410410410l);
! 187: case 8:
! 188: return GC_block_nearly_full1(hhdr, 0x0101010101010101l);
! 189: case 12:
! 190: return GC_block_nearly_full3(hhdr, 0x1001001001001001l,
! 191: 0x0100100100100100l,
! 192: 0x0010010010010010l);
! 193: case 16:
! 194: return GC_block_nearly_full1(hhdr, 0x0001000100010001l);
! 195: case 32:
! 196: return GC_block_nearly_full1(hhdr, 0x0000000100000001l);
! 197: default:
! 198: return DONT_KNOW;
! 199: }
! 200: # endif
! 201: }
! 202: #endif /* !SMALL_CONFIG */
! 203:
1.1 maekawa 204: # ifdef GATHERSTATS
205: # define INCR_WORDS(sz) n_words_found += (sz)
206: # else
207: # define INCR_WORDS(sz)
208: # endif
209: /*
210: * Restore unmarked small objects in h of size sz to the object
211: * free list. Returns the new list.
212: * Clears unmarked objects.
213: */
214: /*ARGSUSED*/
1.1.1.2 ! maekawa 215: ptr_t GC_reclaim_clear(hbp, hhdr, sz, list)
1.1 maekawa 216: register struct hblk *hbp; /* ptr to current heap block */
217: register hdr * hhdr;
218: register ptr_t list;
219: register word sz;
220: {
221: register int word_no;
222: register word *p, *q, *plim;
223: # ifdef GATHERSTATS
224: register int n_words_found = 0;
225: # endif
226:
227: p = (word *)(hbp->hb_body);
228: word_no = HDR_WORDS;
229: plim = (word *)((((word)hbp) + HBLKSIZE)
230: - WORDS_TO_BYTES(sz));
231:
232: /* go through all words in block */
233: while( p <= plim ) {
234: if( mark_bit_from_hdr(hhdr, word_no) ) {
235: p += sz;
236: } else {
237: INCR_WORDS(sz);
238: /* object is available - put on list */
239: obj_link(p) = list;
240: list = ((ptr_t)p);
241: /* Clear object, advance p to next object in the process */
242: q = p + sz;
243: p++; /* Skip link field */
244: while (p < q) {
245: *p++ = 0;
246: }
247: }
248: word_no += sz;
249: }
250: # ifdef GATHERSTATS
251: GC_mem_found += n_words_found;
252: # endif
253: return(list);
254: }
255:
256: #ifndef SMALL_CONFIG
257:
258: /*
259: * A special case for 2 word composite objects (e.g. cons cells):
260: */
261: /*ARGSUSED*/
1.1.1.2 ! maekawa 262: ptr_t GC_reclaim_clear2(hbp, hhdr, list)
1.1 maekawa 263: register struct hblk *hbp; /* ptr to current heap block */
264: hdr * hhdr;
265: register ptr_t list;
266: {
267: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
268: register word *p, *plim;
269: # ifdef GATHERSTATS
270: register int n_words_found = 0;
271: # endif
272: register word mark_word;
273: register int i;
274: # define DO_OBJ(start_displ) \
275: if (!(mark_word & ((word)1 << start_displ))) { \
276: p[start_displ] = (word)list; \
277: list = (ptr_t)(p+start_displ); \
278: p[start_displ+1] = 0; \
279: INCR_WORDS(2); \
280: }
281:
282: p = (word *)(hbp->hb_body);
283: plim = (word *)(((word)hbp) + HBLKSIZE);
284:
285: /* go through all words in block */
286: while( p < plim ) {
287: mark_word = *mark_word_addr++;
288: for (i = 0; i < WORDSZ; i += 8) {
289: DO_OBJ(0);
290: DO_OBJ(2);
291: DO_OBJ(4);
292: DO_OBJ(6);
293: p += 8;
294: mark_word >>= 8;
295: }
296: }
297: # ifdef GATHERSTATS
298: GC_mem_found += n_words_found;
299: # endif
300: return(list);
301: # undef DO_OBJ
302: }
303:
304: /*
305: * Another special case for 4 word composite objects:
306: */
307: /*ARGSUSED*/
1.1.1.2 ! maekawa 308: ptr_t GC_reclaim_clear4(hbp, hhdr, list)
1.1 maekawa 309: register struct hblk *hbp; /* ptr to current heap block */
310: hdr * hhdr;
311: register ptr_t list;
312: {
313: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
314: register word *p, *plim;
315: # ifdef GATHERSTATS
316: register int n_words_found = 0;
317: # endif
318: register word mark_word;
319: # define DO_OBJ(start_displ) \
320: if (!(mark_word & ((word)1 << start_displ))) { \
321: p[start_displ] = (word)list; \
322: list = (ptr_t)(p+start_displ); \
323: p[start_displ+1] = 0; \
324: p[start_displ+2] = 0; \
325: p[start_displ+3] = 0; \
326: INCR_WORDS(4); \
327: }
328:
329: p = (word *)(hbp->hb_body);
330: plim = (word *)(((word)hbp) + HBLKSIZE);
331:
332: /* go through all words in block */
333: while( p < plim ) {
334: mark_word = *mark_word_addr++;
335: DO_OBJ(0);
336: DO_OBJ(4);
337: DO_OBJ(8);
338: DO_OBJ(12);
339: DO_OBJ(16);
340: DO_OBJ(20);
341: DO_OBJ(24);
342: DO_OBJ(28);
343: # if CPP_WORDSZ == 64
344: DO_OBJ(32);
345: DO_OBJ(36);
346: DO_OBJ(40);
347: DO_OBJ(44);
348: DO_OBJ(48);
349: DO_OBJ(52);
350: DO_OBJ(56);
351: DO_OBJ(60);
352: # endif
353: p += WORDSZ;
354: }
355: # ifdef GATHERSTATS
356: GC_mem_found += n_words_found;
357: # endif
358: return(list);
359: # undef DO_OBJ
360: }
361:
362: #endif /* !SMALL_CONFIG */
363:
364: /* The same thing, but don't clear objects: */
365: /*ARGSUSED*/
1.1.1.2 ! maekawa 366: ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list)
1.1 maekawa 367: register struct hblk *hbp; /* ptr to current heap block */
368: register hdr * hhdr;
369: register ptr_t list;
370: register word sz;
371: {
372: register int word_no;
373: register word *p, *plim;
374: # ifdef GATHERSTATS
375: register int n_words_found = 0;
376: # endif
377:
378: p = (word *)(hbp->hb_body);
379: word_no = HDR_WORDS;
380: plim = (word *)((((word)hbp) + HBLKSIZE)
381: - WORDS_TO_BYTES(sz));
382:
383: /* go through all words in block */
384: while( p <= plim ) {
385: if( !mark_bit_from_hdr(hhdr, word_no) ) {
386: INCR_WORDS(sz);
387: /* object is available - put on list */
388: obj_link(p) = list;
389: list = ((ptr_t)p);
390: }
391: p += sz;
392: word_no += sz;
393: }
394: # ifdef GATHERSTATS
395: GC_mem_found += n_words_found;
396: # endif
397: return(list);
398: }
399:
1.1.1.2 ! maekawa 400: /* Don't really reclaim objects, just check for unmarked ones: */
! 401: /*ARGSUSED*/
! 402: void GC_reclaim_check(hbp, hhdr, sz)
! 403: register struct hblk *hbp; /* ptr to current heap block */
! 404: register hdr * hhdr;
! 405: register word sz;
! 406: {
! 407: register int word_no;
! 408: register word *p, *plim;
! 409: # ifdef GATHERSTATS
! 410: register int n_words_found = 0;
! 411: # endif
! 412:
! 413: p = (word *)(hbp->hb_body);
! 414: word_no = HDR_WORDS;
! 415: plim = (word *)((((word)hbp) + HBLKSIZE)
! 416: - WORDS_TO_BYTES(sz));
! 417:
! 418: /* go through all words in block */
! 419: while( p <= plim ) {
! 420: if( !mark_bit_from_hdr(hhdr, word_no) ) {
! 421: FOUND_FREE(hbp, word_no);
! 422: }
! 423: p += sz;
! 424: word_no += sz;
! 425: }
! 426: }
! 427:
1.1 maekawa 428: #ifndef SMALL_CONFIG
429: /*
430: * Another special case for 2 word atomic objects:
431: */
432: /*ARGSUSED*/
1.1.1.2 ! maekawa 433: ptr_t GC_reclaim_uninit2(hbp, hhdr, list)
1.1 maekawa 434: register struct hblk *hbp; /* ptr to current heap block */
435: hdr * hhdr;
436: register ptr_t list;
437: {
438: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
439: register word *p, *plim;
440: # ifdef GATHERSTATS
441: register int n_words_found = 0;
442: # endif
443: register word mark_word;
444: register int i;
445: # define DO_OBJ(start_displ) \
446: if (!(mark_word & ((word)1 << start_displ))) { \
447: p[start_displ] = (word)list; \
448: list = (ptr_t)(p+start_displ); \
449: INCR_WORDS(2); \
450: }
451:
452: p = (word *)(hbp->hb_body);
453: plim = (word *)(((word)hbp) + HBLKSIZE);
454:
455: /* go through all words in block */
456: while( p < plim ) {
457: mark_word = *mark_word_addr++;
458: for (i = 0; i < WORDSZ; i += 8) {
459: DO_OBJ(0);
460: DO_OBJ(2);
461: DO_OBJ(4);
462: DO_OBJ(6);
463: p += 8;
464: mark_word >>= 8;
465: }
466: }
467: # ifdef GATHERSTATS
468: GC_mem_found += n_words_found;
469: # endif
470: return(list);
471: # undef DO_OBJ
472: }
473:
474: /*
475: * Another special case for 4 word atomic objects:
476: */
477: /*ARGSUSED*/
1.1.1.2 ! maekawa 478: ptr_t GC_reclaim_uninit4(hbp, hhdr, list)
1.1 maekawa 479: register struct hblk *hbp; /* ptr to current heap block */
480: hdr * hhdr;
481: register ptr_t list;
482: {
483: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
484: register word *p, *plim;
485: # ifdef GATHERSTATS
486: register int n_words_found = 0;
487: # endif
488: register word mark_word;
489: # define DO_OBJ(start_displ) \
490: if (!(mark_word & ((word)1 << start_displ))) { \
491: p[start_displ] = (word)list; \
492: list = (ptr_t)(p+start_displ); \
493: INCR_WORDS(4); \
494: }
495:
496: p = (word *)(hbp->hb_body);
497: plim = (word *)(((word)hbp) + HBLKSIZE);
498:
499: /* go through all words in block */
500: while( p < plim ) {
501: mark_word = *mark_word_addr++;
502: DO_OBJ(0);
503: DO_OBJ(4);
504: DO_OBJ(8);
505: DO_OBJ(12);
506: DO_OBJ(16);
507: DO_OBJ(20);
508: DO_OBJ(24);
509: DO_OBJ(28);
510: # if CPP_WORDSZ == 64
511: DO_OBJ(32);
512: DO_OBJ(36);
513: DO_OBJ(40);
514: DO_OBJ(44);
515: DO_OBJ(48);
516: DO_OBJ(52);
517: DO_OBJ(56);
518: DO_OBJ(60);
519: # endif
520: p += WORDSZ;
521: }
522: # ifdef GATHERSTATS
523: GC_mem_found += n_words_found;
524: # endif
525: return(list);
526: # undef DO_OBJ
527: }
528:
529: /* Finally the one word case, which never requires any clearing: */
530: /*ARGSUSED*/
1.1.1.2 ! maekawa 531: ptr_t GC_reclaim1(hbp, hhdr, list)
1.1 maekawa 532: register struct hblk *hbp; /* ptr to current heap block */
533: hdr * hhdr;
534: register ptr_t list;
535: {
536: register word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
537: register word *p, *plim;
538: # ifdef GATHERSTATS
539: register int n_words_found = 0;
540: # endif
541: register word mark_word;
542: register int i;
543: # define DO_OBJ(start_displ) \
544: if (!(mark_word & ((word)1 << start_displ))) { \
545: p[start_displ] = (word)list; \
546: list = (ptr_t)(p+start_displ); \
547: INCR_WORDS(1); \
548: }
549:
550: p = (word *)(hbp->hb_body);
551: plim = (word *)(((word)hbp) + HBLKSIZE);
552:
553: /* go through all words in block */
554: while( p < plim ) {
555: mark_word = *mark_word_addr++;
556: for (i = 0; i < WORDSZ; i += 4) {
557: DO_OBJ(0);
558: DO_OBJ(1);
559: DO_OBJ(2);
560: DO_OBJ(3);
561: p += 4;
562: mark_word >>= 4;
563: }
564: }
565: # ifdef GATHERSTATS
566: GC_mem_found += n_words_found;
567: # endif
568: return(list);
569: # undef DO_OBJ
570: }
571:
572: #endif /* !SMALL_CONFIG */
573:
574: /*
575: * Restore unmarked small objects in the block pointed to by hbp
576: * to the appropriate object free list.
577: * If entirely empty blocks are to be completely deallocated, then
578: * caller should perform that check.
579: */
1.1.1.2 ! maekawa 580: void GC_reclaim_small_nonempty_block(hbp, report_if_found)
1.1 maekawa 581: register struct hblk *hbp; /* ptr to current heap block */
1.1.1.2 ! maekawa 582: int report_if_found; /* Abort if a reclaimable object is found */
1.1 maekawa 583: {
584: hdr * hhdr;
1.1.1.2 ! maekawa 585: word sz; /* size of objects in current block */
! 586: struct obj_kind * ok;
! 587: ptr_t * flh;
! 588: int kind;
! 589: GC_bool full;
1.1 maekawa 590:
591: hhdr = HDR(hbp);
592: sz = hhdr -> hb_sz;
593: hhdr -> hb_last_reclaimed = (unsigned short) GC_gc_no;
594: kind = hhdr -> hb_obj_kind;
595: ok = &GC_obj_kinds[kind];
596: flh = &(ok -> ok_freelist[sz]);
597:
1.1.1.2 ! maekawa 598: if (report_if_found) {
! 599: GC_reclaim_check(hbp, hhdr, sz);
! 600: } else if (ok -> ok_init) {
1.1 maekawa 601: switch(sz) {
602: # ifndef SMALL_CONFIG
603: case 1:
1.1.1.2 ! maekawa 604: full = GC_block_nearly_full1(hhdr, 0xffffffffl);
! 605: if (TRUE == full) goto out;
! 606: if (FALSE == full) GC_write_hint(hbp);
! 607: /* In the DONT_KNOW case, we let reclaim fault. */
! 608: *flh = GC_reclaim1(hbp, hhdr, *flh);
1.1 maekawa 609: break;
610: case 2:
1.1.1.2 ! maekawa 611: full = GC_block_nearly_full1(hhdr, 0x55555555l);
! 612: if (TRUE == full) goto out;
! 613: if (FALSE == full) GC_write_hint(hbp);
! 614: *flh = GC_reclaim_clear2(hbp, hhdr, *flh);
1.1 maekawa 615: break;
616: case 4:
1.1.1.2 ! maekawa 617: full = GC_block_nearly_full1(hhdr, 0x11111111l);
! 618: if (TRUE == full) goto out;
! 619: if (FALSE == full) GC_write_hint(hbp);
! 620: *flh = GC_reclaim_clear4(hbp, hhdr, *flh);
1.1 maekawa 621: break;
622: # endif
623: default:
1.1.1.2 ! maekawa 624: full = GC_block_nearly_full(hhdr);
! 625: if (TRUE == full) goto out;
! 626: if (FALSE == full) GC_write_hint(hbp);
! 627: *flh = GC_reclaim_clear(hbp, hhdr, sz, *flh);
1.1 maekawa 628: break;
629: }
630: } else {
631: switch(sz) {
632: # ifndef SMALL_CONFIG
633: case 1:
1.1.1.2 ! maekawa 634: full = GC_block_nearly_full1(hhdr, 0xffffffffl);
! 635: if (TRUE == full) goto out;
! 636: if (FALSE == full) GC_write_hint(hbp);
! 637: *flh = GC_reclaim1(hbp, hhdr, *flh);
1.1 maekawa 638: break;
639: case 2:
1.1.1.2 ! maekawa 640: full = GC_block_nearly_full1(hhdr, 0x55555555l);
! 641: if (TRUE == full) goto out;
! 642: if (FALSE == full) GC_write_hint(hbp);
! 643: *flh = GC_reclaim_uninit2(hbp, hhdr, *flh);
1.1 maekawa 644: break;
645: case 4:
1.1.1.2 ! maekawa 646: full = GC_block_nearly_full1(hhdr, 0x11111111l);
! 647: if (TRUE == full) goto out;
! 648: if (FALSE == full) GC_write_hint(hbp);
! 649: *flh = GC_reclaim_uninit4(hbp, hhdr, *flh);
1.1 maekawa 650: break;
651: # endif
652: default:
1.1.1.2 ! maekawa 653: full = GC_block_nearly_full(hhdr);
! 654: if (TRUE == full) goto out;
! 655: if (FALSE == full) GC_write_hint(hbp);
! 656: *flh = GC_reclaim_uninit(hbp, hhdr, sz, *flh);
1.1 maekawa 657: break;
658: }
659: }
1.1.1.2 ! maekawa 660: out:
1.1 maekawa 661: if (IS_UNCOLLECTABLE(kind)) GC_set_hdr_marks(hhdr);
662: }
663:
664: /*
665: * Restore an unmarked large object or an entirely empty blocks of small objects
666: * to the heap block free list.
667: * Otherwise enqueue the block for later processing
668: * by GC_reclaim_small_nonempty_block.
1.1.1.2 ! maekawa 669: * If report_if_found is TRUE, then process any block immediately, and
! 670: * simply report free objects; do not actually reclaim them.
1.1 maekawa 671: */
1.1.1.2 ! maekawa 672: void GC_reclaim_block(hbp, report_if_found)
1.1 maekawa 673: register struct hblk *hbp; /* ptr to current heap block */
1.1.1.2 ! maekawa 674: word report_if_found; /* Abort if a reclaimable object is found */
1.1 maekawa 675: {
676: register hdr * hhdr;
677: register word sz; /* size of objects in current block */
678: register struct obj_kind * ok;
679: struct hblk ** rlh;
680:
681: hhdr = HDR(hbp);
682: sz = hhdr -> hb_sz;
683: ok = &GC_obj_kinds[hhdr -> hb_obj_kind];
684:
685: if( sz > MAXOBJSZ ) { /* 1 big object */
686: if( !mark_bit_from_hdr(hhdr, HDR_WORDS) ) {
1.1.1.2 ! maekawa 687: if (report_if_found) {
! 688: FOUND_FREE(hbp, HDR_WORDS);
! 689: } else {
! 690: # ifdef GATHERSTATS
1.1 maekawa 691: GC_mem_found += sz;
1.1.1.2 ! maekawa 692: # endif
! 693: GC_freehblk(hbp);
! 694: }
1.1 maekawa 695: }
696: } else {
697: GC_bool empty = GC_block_empty(hhdr);
1.1.1.2 ! maekawa 698: if (report_if_found) {
! 699: GC_reclaim_small_nonempty_block(hbp, (int)report_if_found);
1.1 maekawa 700: } else if (empty) {
701: # ifdef GATHERSTATS
702: GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
703: # endif
704: GC_freehblk(hbp);
705: } else {
706: /* group of smaller objects, enqueue the real work */
707: rlh = &(ok -> ok_reclaim_list[sz]);
708: hhdr -> hb_next = *rlh;
709: *rlh = hbp;
710: }
711: }
712: }
713:
714: #if !defined(NO_DEBUGGING)
715: /* Routines to gather and print heap block info */
716: /* intended for debugging. Otherwise should be called */
717: /* with lock. */
718: static size_t number_of_blocks;
719: static size_t total_bytes;
720:
721: /* Number of set bits in a word. Not performance critical. */
722: static int set_bits(n)
723: word n;
724: {
725: register word m = n;
726: register int result = 0;
727:
728: while (m > 0) {
729: if (m & 1) result++;
730: m >>= 1;
731: }
732: return(result);
733: }
734:
735: /* Return the number of set mark bits in the given header */
736: int GC_n_set_marks(hhdr)
737: hdr * hhdr;
738: {
739: register int result = 0;
740: register int i;
741:
742: for (i = 0; i < MARK_BITS_SZ; i++) {
743: result += set_bits(hhdr -> hb_marks[i]);
744: }
745: return(result);
746: }
747:
748: /*ARGSUSED*/
749: void GC_print_block_descr(h, dummy)
750: struct hblk *h;
751: word dummy;
752: {
753: register hdr * hhdr = HDR(h);
754: register size_t bytes = WORDS_TO_BYTES(hhdr -> hb_sz);
755:
756: GC_printf3("(%lu:%lu,%lu)", (unsigned long)(hhdr -> hb_obj_kind),
757: (unsigned long)bytes,
758: (unsigned long)(GC_n_set_marks(hhdr)));
759: bytes += HDR_BYTES + HBLKSIZE-1;
760: bytes &= ~(HBLKSIZE-1);
761: total_bytes += bytes;
762: number_of_blocks++;
763: }
764:
765: void GC_print_block_list()
766: {
767: GC_printf0("(kind(0=ptrfree,1=normal,2=unc.,3=stubborn):size_in_bytes, #_marks_set)\n");
768: number_of_blocks = 0;
769: total_bytes = 0;
770: GC_apply_to_all_blocks(GC_print_block_descr, (word)0);
771: GC_printf2("\nblocks = %lu, bytes = %lu\n",
772: (unsigned long)number_of_blocks,
773: (unsigned long)total_bytes);
774: }
775:
776: #endif /* NO_DEBUGGING */
777:
778: /*
1.1.1.2 ! maekawa 779: * Perform GC_reclaim_block on the entire heap, after first clearing
! 780: * small object free lists (if we are not just looking for leaks).
1.1 maekawa 781: */
1.1.1.2 ! maekawa 782: void GC_start_reclaim(report_if_found)
! 783: int report_if_found; /* Abort if a GC_reclaimable object is found */
1.1 maekawa 784: {
785: int kind;
786:
787: /* Clear reclaim- and free-lists */
788: for (kind = 0; kind < GC_n_kinds; kind++) {
789: register ptr_t *fop;
790: register ptr_t *lim;
791: register struct hblk ** rlp;
792: register struct hblk ** rlim;
793: register struct hblk ** rlist = GC_obj_kinds[kind].ok_reclaim_list;
794:
795: if (rlist == 0) continue; /* This kind not used. */
1.1.1.2 ! maekawa 796: if (!report_if_found) {
1.1 maekawa 797: lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
798: for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
799: *fop = 0;
800: }
801: } /* otherwise free list objects are marked, */
802: /* and its safe to leave them */
803: rlim = rlist + MAXOBJSZ+1;
804: for( rlp = rlist; rlp < rlim; rlp++ ) {
805: *rlp = 0;
806: }
807: }
808:
809: # ifdef PRINTBLOCKS
810: GC_printf0("GC_reclaim: current block sizes:\n");
811: GC_print_block_list();
812: # endif
813:
814: /* Go through all heap blocks (in hblklist) and reclaim unmarked objects */
815: /* or enqueue the block for later processing. */
1.1.1.2 ! maekawa 816: GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
1.1 maekawa 817:
818: }
819:
820: /*
821: * Sweep blocks of the indicated object size and kind until either the
822: * appropriate free list is nonempty, or there are no more blocks to
823: * sweep.
824: */
825: void GC_continue_reclaim(sz, kind)
826: word sz; /* words */
827: int kind;
828: {
829: register hdr * hhdr;
830: register struct hblk * hbp;
831: register struct obj_kind * ok = &(GC_obj_kinds[kind]);
832: struct hblk ** rlh = ok -> ok_reclaim_list;
833: ptr_t *flh = &(ok -> ok_freelist[sz]);
834:
835: if (rlh == 0) return; /* No blocks of this kind. */
836: rlh += sz;
837: while ((hbp = *rlh) != 0) {
838: hhdr = HDR(hbp);
839: *rlh = hhdr -> hb_next;
840: GC_reclaim_small_nonempty_block(hbp, FALSE);
841: if (*flh != 0) break;
842: }
843: }
844:
845: /*
846: * Reclaim all small blocks waiting to be reclaimed.
847: * Abort and return FALSE when/if (*stop_func)() returns TRUE.
848: * If this returns TRUE, then it's safe to restart the world
849: * with incorrectly cleared mark bits.
850: * If ignore_old is TRUE, then reclain only blocks that have been
851: * recently reclaimed, and discard the rest.
852: * Stop_func may be 0.
853: */
854: GC_bool GC_reclaim_all(stop_func, ignore_old)
855: GC_stop_func stop_func;
856: GC_bool ignore_old;
857: {
858: register word sz;
859: register int kind;
860: register hdr * hhdr;
861: register struct hblk * hbp;
862: register struct obj_kind * ok;
863: struct hblk ** rlp;
864: struct hblk ** rlh;
865: # ifdef PRINTTIMES
866: CLOCK_TYPE start_time;
867: CLOCK_TYPE done_time;
868:
869: GET_TIME(start_time);
870: # endif
871:
872: for (kind = 0; kind < GC_n_kinds; kind++) {
873: ok = &(GC_obj_kinds[kind]);
874: rlp = ok -> ok_reclaim_list;
875: if (rlp == 0) continue;
876: for (sz = 1; sz <= MAXOBJSZ; sz++) {
877: rlh = rlp + sz;
878: while ((hbp = *rlh) != 0) {
879: if (stop_func != (GC_stop_func)0 && (*stop_func)()) {
880: return(FALSE);
881: }
882: hhdr = HDR(hbp);
883: *rlh = hhdr -> hb_next;
884: if (!ignore_old || hhdr -> hb_last_reclaimed == GC_gc_no - 1) {
885: /* It's likely we'll need it this time, too */
886: /* It's been touched recently, so this */
887: /* shouldn't trigger paging. */
888: GC_reclaim_small_nonempty_block(hbp, FALSE);
889: }
890: }
891: }
892: }
893: # ifdef PRINTTIMES
894: GET_TIME(done_time);
895: GC_printf1("Disposing of reclaim lists took %lu msecs\n",
896: MS_TIME_DIFF(done_time,start_time));
897: # endif
898: return(TRUE);
899: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to reclaim.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gc