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