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