1 /*
2 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
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.
6 *
7 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
9 *
10 * Permission is hereby granted to use or copy this program
11 * for any purpose, provided the above notices are retained on all copies.
12 * Permission to modify the code and to distribute modified code is granted,
13 * provided the above notices are retained, and a notice that the code was
14 * modified is included with the above copyright notice.
15 */
16
17 #include <stdio.h>
18 #include "private/gc_priv.h"
19
20 signed_word GC_mem_found = 0;
21 /* Number of words of memory reclaimed */
22
23 #if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
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
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
GC_add_leaked(leaked)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. */
GC_print_all_errors()53 void GC_print_all_errors ()
54 {
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;
76 }
77 GC_n_leaked = 0;
78 printing_errors = FALSE;
79 }
80
81
82 # define FOUND_FREE(hblk, word_no) \
83 { \
84 GC_add_leaked((ptr_t)hblk + WORDS_TO_BYTES(word_no)); \
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
GC_block_empty(hhdr)99 GC_bool GC_block_empty(hhdr)
100 register hdr * hhdr;
101 {
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. */
105 register word *p = (word *)(&(hhdr -> hb_marks[0]));
106 register word * plim =
107 (word *)(&(hhdr -> hb_marks[MARK_BITS_SZ]));
108 while (p < plim) {
109 if (*p++) return(FALSE);
110 }
111 return(TRUE);
112 }
113
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
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
GC_block_nearly_full(hhdr)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)
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
GC_block_nearly_full1(hhdr,pat1)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 */
GC_block_nearly_full3(hhdr,pat1,pat2,pat3)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 ... */
GC_block_nearly_full(hhdr)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 }
281 #endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
282
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)
288 # define INCR_WORDS(sz) n_words_found += (sz)
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
295 # else
296 # define INCR_WORDS(sz)
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
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*/
310 ptr_t GC_reclaim_clear(hbp, hhdr, sz, list COUNT_PARAM)
311 register struct hblk *hbp; /* ptr to current heap block */
312 register hdr * hhdr;
313 register ptr_t list;
314 register word sz;
315 COUNT_DECL
316 {
317 register int word_no;
318 register word *p, *q, *plim;
319 NWORDS_DECL
320
321 GC_ASSERT(hhdr == GC_find_header((ptr_t)hbp));
322 p = (word *)(hbp->hb_body);
323 word_no = 0;
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;
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) {
350 *p++ = 0;
351 }
352 # endif
353 }
354 word_no += sz;
355 }
356 COUNT_UPDATE
357 return(list);
358 }
359
360 #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
361
362 /*
363 * A special case for 2 word composite objects (e.g. cons cells):
364 */
365 /*ARGSUSED*/
366 ptr_t GC_reclaim_clear2(hbp, hhdr, list COUNT_PARAM)
367 register struct hblk *hbp; /* ptr to current heap block */
368 hdr * hhdr;
369 register ptr_t list;
370 COUNT_DECL
371 {
372 register word * mark_word_addr = &(hhdr->hb_marks[0]);
373 register word *p, *plim;
374 register word mark_word;
375 register int i;
376 NWORDS_DECL
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 }
400 COUNT_UPDATE
401 return(list);
402 # undef DO_OBJ
403 }
404
405 /*
406 * Another special case for 4 word composite objects:
407 */
408 /*ARGSUSED*/
409 ptr_t GC_reclaim_clear4(hbp, hhdr, list COUNT_PARAM)
410 register struct hblk *hbp; /* ptr to current heap block */
411 hdr * hhdr;
412 register ptr_t list;
413 COUNT_DECL
414 {
415 register word * mark_word_addr = &(hhdr->hb_marks[0]);
416 register word *p, *plim;
417 register word mark_word;
418 NWORDS_DECL
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; \
424 CLEAR_DOUBLE(p + start_displ + 2); \
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 }
454 COUNT_UPDATE
455 return(list);
456 # undef DO_OBJ
457 }
458
459 #endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
460
461 /* The same thing, but don't clear objects: */
462 /*ARGSUSED*/
463 ptr_t GC_reclaim_uninit(hbp, hhdr, sz, list COUNT_PARAM)
464 register struct hblk *hbp; /* ptr to current heap block */
465 register hdr * hhdr;
466 register ptr_t list;
467 register word sz;
468 COUNT_DECL
469 {
470 register int word_no = 0;
471 register word *p, *plim;
472 NWORDS_DECL
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 }
489 COUNT_UPDATE
490 return(list);
491 }
492
493 /* Don't really reclaim objects, just check for unmarked ones: */
494 /*ARGSUSED*/
GC_reclaim_check(hbp,hhdr,sz)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 {
500 register int word_no = 0;
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
520 #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
521 /*
522 * Another special case for 2 word atomic objects:
523 */
524 /*ARGSUSED*/
525 ptr_t GC_reclaim_uninit2(hbp, hhdr, list COUNT_PARAM)
526 register struct hblk *hbp; /* ptr to current heap block */
527 hdr * hhdr;
528 register ptr_t list;
529 COUNT_DECL
530 {
531 register word * mark_word_addr = &(hhdr->hb_marks[0]);
532 register word *p, *plim;
533 register word mark_word;
534 register int i;
535 NWORDS_DECL
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 }
558 COUNT_UPDATE
559 return(list);
560 # undef DO_OBJ
561 }
562
563 /*
564 * Another special case for 4 word atomic objects:
565 */
566 /*ARGSUSED*/
567 ptr_t GC_reclaim_uninit4(hbp, hhdr, list COUNT_PARAM)
568 register struct hblk *hbp; /* ptr to current heap block */
569 hdr * hhdr;
570 register ptr_t list;
571 COUNT_DECL
572 {
573 register word * mark_word_addr = &(hhdr->hb_marks[0]);
574 register word *p, *plim;
575 register word mark_word;
576 NWORDS_DECL
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 }
610 COUNT_UPDATE
611 return(list);
612 # undef DO_OBJ
613 }
614
615 /* Finally the one word case, which never requires any clearing: */
616 /*ARGSUSED*/
617 ptr_t GC_reclaim1(hbp, hhdr, list COUNT_PARAM)
618 register struct hblk *hbp; /* ptr to current heap block */
619 hdr * hhdr;
620 register ptr_t list;
621 COUNT_DECL
622 {
623 register word * mark_word_addr = &(hhdr->hb_marks[0]);
624 register word *p, *plim;
625 register word mark_word;
626 register int i;
627 NWORDS_DECL
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 }
650 COUNT_UPDATE
651 return(list);
652 # undef DO_OBJ
653 }
654
655 #endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
656
657 /*
658 * Generic procedure to rebuild a free list in hbp.
659 * Also called directly from GC_malloc_many.
660 */
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
668 {
669 ptr_t result = list;
670
671 GC_ASSERT(GC_find_header((ptr_t)hbp) == hhdr);
672 GC_remove_protection(hbp, 1, (hhdr)->hb_descr == 0 /* Pointer-free? */);
673 if (init) {
674 switch(sz) {
675 # if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
676 case 1:
677 /* We now issue the hint even if GC_nearly_full returned */
678 /* DONT_KNOW. */
679 result = GC_reclaim1(hbp, hhdr, list COUNT_ARG);
680 break;
681 case 2:
682 result = GC_reclaim_clear2(hbp, hhdr, list COUNT_ARG);
683 break;
684 case 4:
685 result = GC_reclaim_clear4(hbp, hhdr, list COUNT_ARG);
686 break;
687 # endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
688 default:
689 result = GC_reclaim_clear(hbp, hhdr, sz, list COUNT_ARG);
690 break;
691 }
692 } else {
693 GC_ASSERT((hhdr)->hb_descr == 0 /* Pointer-free block */);
694 switch(sz) {
695 # if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
696 case 1:
697 result = GC_reclaim1(hbp, hhdr, list COUNT_ARG);
698 break;
699 case 2:
700 result = GC_reclaim_uninit2(hbp, hhdr, list COUNT_ARG);
701 break;
702 case 4:
703 result = GC_reclaim_uninit4(hbp, hhdr, list COUNT_ARG);
704 break;
705 # endif /* !SMALL_CONFIG && !USE_MARK_BYTES */
706 default:
707 result = GC_reclaim_uninit(hbp, hhdr, sz, list COUNT_ARG);
708 break;
709 }
710 }
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 {
737 *flh = GC_reclaim_generic(hbp, hhdr, sz,
738 (ok -> ok_init || GC_debugging_started),
739 *flh MEM_FOUND_ADDR);
740 }
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.
748 * If report_if_found is TRUE, then process any block immediately, and
749 * simply report free objects; do not actually reclaim them.
750 */
751 # if defined(__STDC__) || defined(__cplusplus)
GC_reclaim_block(register struct hblk * hbp,word report_if_found)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
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 */
769 if( !mark_bit_from_hdr(hhdr, 0) ) {
770 if (report_if_found) {
771 FOUND_FREE(hbp, 0);
772 } else {
773 word blocks = OBJ_SZ_TO_BLOCKS(sz);
774 if (blocks > 1) {
775 GC_large_allocd_bytes -= blocks * HBLKSIZE;
776 }
777 # ifdef GATHERSTATS
778 GC_mem_found += sz;
779 # endif
780 GC_freehblk(hbp);
781 }
782 }
783 } else {
784 GC_bool empty = GC_block_empty(hhdr);
785 if (report_if_found) {
786 GC_reclaim_small_nonempty_block(hbp, (int)report_if_found
787 MEM_FOUND_ADDR);
788 } else if (empty) {
789 # ifdef GATHERSTATS
790 GC_mem_found += BYTES_TO_WORDS(HBLKSIZE);
791 # endif
792 GC_freehblk(hbp);
793 } else if (TRUE != GC_block_nearly_full(hhdr)){
794 /* group of smaller objects, enqueue the real work */
795 rlh = &(ok -> ok_reclaim_list[sz]);
796 hhdr -> hb_next = *rlh;
797 *rlh = hbp;
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. */
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. */
810
811 struct Print_stats
812 {
813 size_t number_of_blocks;
814 size_t total_bytes;
815 };
816
817 #ifdef USE_MARK_BYTES
818
819 /* Return the number of set mark bits in the given header */
GC_n_set_marks(hhdr)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
834 /* Number of set bits in a word. Not performance critical. */
set_bits(n)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 */
GC_n_set_marks(hhdr)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
861 #endif /* !USE_MARK_BYTES */
862
863 /*ARGSUSED*/
864 # if defined(__STDC__) || defined(__cplusplus)
GC_print_block_descr(struct hblk * h,word dummy)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
871 {
872 register hdr * hhdr = HDR(h);
873 register size_t bytes = WORDS_TO_BYTES(hhdr -> hb_sz);
874 struct Print_stats *ps;
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)));
879 bytes += HBLKSIZE-1;
880 bytes &= ~(HBLKSIZE-1);
881
882 ps = (struct Print_stats *)dummy;
883 ps->total_bytes += bytes;
884 ps->number_of_blocks++;
885 }
886
GC_print_block_list()887 void GC_print_block_list()
888 {
889 struct Print_stats pstats;
890
891 GC_printf1("(kind(0=ptrfree,1=normal,2=unc.,%lu=stubborn):size_in_bytes, #_marks_set)\n", STUBBORN);
892 pstats.number_of_blocks = 0;
893 pstats.total_bytes = 0;
894 GC_apply_to_all_blocks(GC_print_block_descr, (word)&pstats);
895 GC_printf2("\nblocks = %lu, bytes = %lu\n",
896 (unsigned long)pstats.number_of_blocks,
897 (unsigned long)pstats.total_bytes);
898 }
899
900 #endif /* NO_DEBUGGING */
901
902 /*
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.
907 * It may help for other pointer-containing objects.
908 */
GC_clear_fl_links(flp)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 /*
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).
924 */
GC_start_reclaim(report_if_found)925 void GC_start_reclaim(report_if_found)
926 int report_if_found; /* Abort if a GC_reclaimable object is found */
927 {
928 int kind;
929
930 # if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
931 GC_ASSERT(0 == GC_fl_builder_count);
932 # endif
933 /* Clear reclaim- and free-lists */
934 for (kind = 0; kind < GC_n_kinds; kind++) {
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);
941
942 if (rlist == 0) continue; /* This kind not used. */
943 if (!report_if_found) {
944 lim = &(GC_obj_kinds[kind].ok_freelist[MAXOBJSZ+1]);
945 for( fop = GC_obj_kinds[kind].ok_freelist; fop < lim; fop++ ) {
946 if (*fop != 0) {
947 if (should_clobber) {
948 GC_clear_fl_links(fop);
949 } else {
950 *fop = 0;
951 }
952 }
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. */
969 GC_apply_to_all_blocks(GC_reclaim_block, (word)report_if_found);
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
976 # if defined(PARALLEL_MARK) || defined(THREAD_LOCAL_ALLOC)
977 GC_ASSERT(0 == GC_fl_builder_count);
978 # endif
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 */
GC_continue_reclaim(sz,kind)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;
1002 GC_reclaim_small_nonempty_block(hbp, FALSE MEM_FOUND_ADDR);
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.
1012 * If ignore_old is TRUE, then reclaim only blocks that have been
1013 * recently reclaimed, and discard the rest.
1014 * Stop_func may be 0.
1015 */
GC_reclaim_all(stop_func,ignore_old)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
1033
1034 for (kind = 0; kind < GC_n_kinds; kind++) {
1035 ok = &(GC_obj_kinds[kind]);
1036 rlp = ok -> ok_reclaim_list;
1037 if (rlp == 0) continue;
1038 for (sz = 1; sz <= MAXOBJSZ; sz++) {
1039 rlh = rlp + sz;
1040 while ((hbp = *rlh) != 0) {
1041 if (stop_func != (GC_stop_func)0 && (*stop_func)()) {
1042 return(FALSE);
1043 }
1044 hhdr = HDR(hbp);
1045 *rlh = hhdr -> hb_next;
1046 if (!ignore_old || hhdr -> hb_last_reclaimed == GC_gc_no - 1) {
1047 /* It's likely we'll need it this time, too */
1048 /* It's been touched recently, so this */
1049 /* shouldn't trigger paging. */
1050 GC_reclaim_small_nonempty_block(hbp, FALSE MEM_FOUND_ADDR);
1051 }
1052 }
1053 }
1054 }
1055 # ifdef PRINTTIMES
1056 GET_TIME(done_time);
1057 GC_printf1("Disposing of reclaim lists took %lu msecs\n",
1058 MS_TIME_DIFF(done_time,start_time));
1059 # endif
1060 return(TRUE);
1061 }
1062