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