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