]>
Commit | Line | Data |
---|---|---|
73ffefd0 TT |
1 | /* |
2 | * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers | |
20bbd3cd TT |
3 | * Copyright (c) 1991-1996 by Xerox Corporation. All rights reserved. |
4 | * Copyright (c) 1998 by Silicon Graphics. All rights reserved. | |
5 | * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved. | |
73ffefd0 TT |
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 | */ | |
73ffefd0 TT |
17 | |
18 | ||
9110a741 | 19 | # include "private/gc_priv.h" |
73ffefd0 TT |
20 | |
21 | # include <stdio.h> | |
9110a741 | 22 | # if !defined(MACOS) && !defined(MSWINCE) |
73ffefd0 TT |
23 | # include <signal.h> |
24 | # include <sys/types.h> | |
25 | # endif | |
26 | ||
27 | /* | |
28 | * Separate free lists are maintained for different sized objects | |
29 | * up to MAXOBJSZ. | |
30 | * The call GC_allocobj(i,k) ensures that the freelist for | |
31 | * kind k objects of size i points to a non-empty | |
32 | * free list. It returns a pointer to the first entry on the free list. | |
33 | * In a single-threaded world, GC_allocobj may be called to allocate | |
34 | * an object of (small) size i as follows: | |
35 | * | |
36 | * opp = &(GC_objfreelist[i]); | |
37 | * if (*opp == 0) GC_allocobj(i, NORMAL); | |
38 | * ptr = *opp; | |
39 | * *opp = obj_link(ptr); | |
40 | * | |
41 | * Note that this is very fast if the free list is non-empty; it should | |
42 | * only involve the execution of 4 or 5 simple instructions. | |
43 | * All composite objects on freelists are cleared, except for | |
44 | * their first word. | |
45 | */ | |
46 | ||
47 | /* | |
48 | * The allocator uses GC_allochblk to allocate large chunks of objects. | |
49 | * These chunks all start on addresses which are multiples of | |
50 | * HBLKSZ. Each allocated chunk has an associated header, | |
51 | * which can be located quickly based on the address of the chunk. | |
52 | * (See headers.c for details.) | |
53 | * This makes it possible to check quickly whether an | |
54 | * arbitrary address corresponds to an object administered by the | |
55 | * allocator. | |
56 | */ | |
57 | ||
58 | word GC_non_gc_bytes = 0; /* Number of bytes not intended to be collected */ | |
59 | ||
60 | word GC_gc_no = 0; | |
61 | ||
20bbd3cd | 62 | #ifndef SMALL_CONFIG |
9110a741 | 63 | int GC_incremental = 0; /* By default, stop the world. */ |
20bbd3cd TT |
64 | #endif |
65 | ||
9110a741 BM |
66 | int GC_parallel = FALSE; /* By default, parallel GC is off. */ |
67 | ||
20bbd3cd TT |
68 | int GC_full_freq = 19; /* Every 20th collection is a full */ |
69 | /* collection, whether we need it */ | |
70 | /* or not. */ | |
71 | ||
72 | GC_bool GC_need_full_gc = FALSE; | |
73 | /* Need full GC do to heap growth. */ | |
73ffefd0 | 74 | |
20bbd3cd | 75 | word GC_used_heap_size_after_full = 0; |
73ffefd0 TT |
76 | |
77 | char * GC_copyright[] = | |
78 | {"Copyright 1988,1989 Hans-J. Boehm and Alan J. Demers ", | |
79 | "Copyright (c) 1991-1995 by Xerox Corporation. All rights reserved. ", | |
20bbd3cd | 80 | "Copyright (c) 1996-1998 by Silicon Graphics. All rights reserved. ", |
9110a741 | 81 | "Copyright (c) 1999-2000 by Hewlett-Packard Company. All rights reserved. ", |
73ffefd0 TT |
82 | "THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY", |
83 | " EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK.", | |
84 | "See source code for details." }; | |
85 | ||
86 | # include "version.h" | |
87 | ||
88 | /* some more variables */ | |
89 | ||
90 | extern signed_word GC_mem_found; /* Number of reclaimed longwords */ | |
91 | /* after garbage collection */ | |
92 | ||
93 | GC_bool GC_dont_expand = 0; | |
94 | ||
20bbd3cd | 95 | word GC_free_space_divisor = 3; |
73ffefd0 TT |
96 | |
97 | extern GC_bool GC_collection_in_progress(); | |
20bbd3cd | 98 | /* Collection is in progress, or was abandoned. */ |
73ffefd0 TT |
99 | |
100 | int GC_never_stop_func GC_PROTO((void)) { return(0); } | |
101 | ||
20bbd3cd TT |
102 | CLOCK_TYPE GC_start_time; /* Time at which we stopped world. */ |
103 | /* used only in GC_timeout_stop_func. */ | |
73ffefd0 | 104 | |
20bbd3cd TT |
105 | int GC_n_attempts = 0; /* Number of attempts at finishing */ |
106 | /* collection within TIME_LIMIT */ | |
107 | ||
108 | #ifdef SMALL_CONFIG | |
109 | # define GC_timeout_stop_func GC_never_stop_func | |
110 | #else | |
111 | int GC_timeout_stop_func GC_PROTO((void)) | |
112 | { | |
73ffefd0 TT |
113 | CLOCK_TYPE current_time; |
114 | static unsigned count = 0; | |
115 | unsigned long time_diff; | |
116 | ||
117 | if ((count++ & 3) != 0) return(0); | |
1530be84 | 118 | #ifndef NO_CLOCK |
73ffefd0 TT |
119 | GET_TIME(current_time); |
120 | time_diff = MS_TIME_DIFF(current_time,GC_start_time); | |
121 | if (time_diff >= TIME_LIMIT) { | |
9110a741 BM |
122 | # ifdef CONDPRINT |
123 | if (GC_print_stats) { | |
73ffefd0 | 124 | GC_printf0("Abandoning stopped marking after "); |
20bbd3cd TT |
125 | GC_printf1("%lu msecs", (unsigned long)time_diff); |
126 | GC_printf1("(attempt %d)\n", (unsigned long) GC_n_attempts); | |
9110a741 | 127 | } |
73ffefd0 TT |
128 | # endif |
129 | return(1); | |
130 | } | |
1530be84 | 131 | #endif |
73ffefd0 | 132 | return(0); |
20bbd3cd TT |
133 | } |
134 | #endif /* !SMALL_CONFIG */ | |
73ffefd0 TT |
135 | |
136 | /* Return the minimum number of words that must be allocated between */ | |
137 | /* collections to amortize the collection cost. */ | |
138 | static word min_words_allocd() | |
139 | { | |
140 | # ifdef THREADS | |
141 | /* We punt, for now. */ | |
142 | register signed_word stack_size = 10000; | |
143 | # else | |
144 | int dummy; | |
145 | register signed_word stack_size = (ptr_t)(&dummy) - GC_stackbottom; | |
146 | # endif | |
20bbd3cd | 147 | word total_root_size; /* includes double stack size, */ |
73ffefd0 TT |
148 | /* since the stack is expensive */ |
149 | /* to scan. */ | |
20bbd3cd TT |
150 | word scan_size; /* Estimate of memory to be scanned */ |
151 | /* during normal GC. */ | |
73ffefd0 TT |
152 | |
153 | if (stack_size < 0) stack_size = -stack_size; | |
154 | total_root_size = 2 * stack_size + GC_root_size; | |
20bbd3cd TT |
155 | scan_size = BYTES_TO_WORDS(GC_heapsize - GC_large_free_bytes |
156 | + (GC_large_free_bytes >> 2) | |
157 | /* use a bit more of large empty heap */ | |
158 | + total_root_size); | |
73ffefd0 | 159 | if (GC_incremental) { |
20bbd3cd | 160 | return scan_size / (2 * GC_free_space_divisor); |
73ffefd0 | 161 | } else { |
20bbd3cd | 162 | return scan_size / GC_free_space_divisor; |
73ffefd0 TT |
163 | } |
164 | } | |
165 | ||
166 | /* Return the number of words allocated, adjusted for explicit storage */ | |
167 | /* management, etc.. This number is used in deciding when to trigger */ | |
168 | /* collections. */ | |
169 | word GC_adj_words_allocd() | |
170 | { | |
171 | register signed_word result; | |
172 | register signed_word expl_managed = | |
173 | BYTES_TO_WORDS((long)GC_non_gc_bytes | |
174 | - (long)GC_non_gc_bytes_at_gc); | |
175 | ||
176 | /* Don't count what was explicitly freed, or newly allocated for */ | |
177 | /* explicit management. Note that deallocating an explicitly */ | |
178 | /* managed object should not alter result, assuming the client */ | |
179 | /* is playing by the rules. */ | |
180 | result = (signed_word)GC_words_allocd | |
181 | - (signed_word)GC_mem_freed - expl_managed; | |
182 | if (result > (signed_word)GC_words_allocd) { | |
183 | result = GC_words_allocd; | |
184 | /* probably client bug or unfortunate scheduling */ | |
185 | } | |
186 | result += GC_words_finalized; | |
187 | /* We count objects enqueued for finalization as though they */ | |
188 | /* had been reallocated this round. Finalization is user */ | |
189 | /* visible progress. And if we don't count this, we have */ | |
190 | /* stability problems for programs that finalize all objects. */ | |
191 | result += GC_words_wasted; | |
192 | /* This doesn't reflect useful work. But if there is lots of */ | |
193 | /* new fragmentation, the same is probably true of the heap, */ | |
194 | /* and the collection will be correspondingly cheaper. */ | |
195 | if (result < (signed_word)(GC_words_allocd >> 3)) { | |
196 | /* Always count at least 1/8 of the allocations. We don't want */ | |
197 | /* to collect too infrequently, since that would inhibit */ | |
198 | /* coalescing of free storage blocks. */ | |
199 | /* This also makes us partially robust against client bugs. */ | |
200 | return(GC_words_allocd >> 3); | |
201 | } else { | |
202 | return(result); | |
203 | } | |
204 | } | |
205 | ||
206 | ||
207 | /* Clear up a few frames worth of garbage left at the top of the stack. */ | |
208 | /* This is used to prevent us from accidentally treating garbade left */ | |
209 | /* on the stack by other parts of the collector as roots. This */ | |
210 | /* differs from the code in misc.c, which actually tries to keep the */ | |
211 | /* stack clear of long-lived, client-generated garbage. */ | |
212 | void GC_clear_a_few_frames() | |
213 | { | |
214 | # define NWORDS 64 | |
215 | word frames[NWORDS]; | |
216 | register int i; | |
217 | ||
218 | for (i = 0; i < NWORDS; i++) frames[i] = 0; | |
219 | } | |
220 | ||
221 | /* Have we allocated enough to amortize a collection? */ | |
222 | GC_bool GC_should_collect() | |
223 | { | |
224 | return(GC_adj_words_allocd() >= min_words_allocd()); | |
225 | } | |
226 | ||
20bbd3cd | 227 | |
73ffefd0 TT |
228 | void GC_notify_full_gc() |
229 | { | |
9110a741 | 230 | if (GC_start_call_back != (void (*) GC_PROTO((void)))0) { |
73ffefd0 TT |
231 | (*GC_start_call_back)(); |
232 | } | |
233 | } | |
234 | ||
20bbd3cd TT |
235 | GC_bool GC_is_full_gc = FALSE; |
236 | ||
73ffefd0 TT |
237 | /* |
238 | * Initiate a garbage collection if appropriate. | |
239 | * Choose judiciously | |
240 | * between partial, full, and stop-world collections. | |
241 | * Assumes lock held, signals disabled. | |
242 | */ | |
243 | void GC_maybe_gc() | |
244 | { | |
245 | static int n_partial_gcs = 0; | |
20bbd3cd | 246 | |
73ffefd0 TT |
247 | if (GC_should_collect()) { |
248 | if (!GC_incremental) { | |
249 | GC_notify_full_gc(); | |
250 | GC_gcollect_inner(); | |
251 | n_partial_gcs = 0; | |
252 | return; | |
20bbd3cd | 253 | } else if (GC_need_full_gc || n_partial_gcs >= GC_full_freq) { |
9110a741 BM |
254 | # ifdef CONDPRINT |
255 | if (GC_print_stats) { | |
256 | GC_printf2( | |
257 | "***>Full mark for collection %lu after %ld allocd bytes\n", | |
258 | (unsigned long) GC_gc_no+1, | |
259 | (long)WORDS_TO_BYTES(GC_words_allocd)); | |
260 | } | |
73ffefd0 TT |
261 | # endif |
262 | GC_promote_black_lists(); | |
9110a741 BM |
263 | # ifdef PARALLEL_MARK |
264 | GC_wait_for_reclaim(); | |
265 | # endif | |
73ffefd0 TT |
266 | (void)GC_reclaim_all((GC_stop_func)0, TRUE); |
267 | GC_clear_marks(); | |
268 | n_partial_gcs = 0; | |
269 | GC_notify_full_gc(); | |
20bbd3cd | 270 | GC_is_full_gc = TRUE; |
73ffefd0 TT |
271 | } else { |
272 | n_partial_gcs++; | |
273 | } | |
274 | /* We try to mark with the world stopped. */ | |
275 | /* If we run out of time, this turns into */ | |
276 | /* incremental marking. */ | |
1530be84 | 277 | #ifndef NO_CLOCK |
73ffefd0 | 278 | GET_TIME(GC_start_time); |
1530be84 | 279 | #endif |
73ffefd0 TT |
280 | if (GC_stopped_mark(GC_timeout_stop_func)) { |
281 | # ifdef SAVE_CALL_CHAIN | |
282 | GC_save_callers(GC_last_stack); | |
283 | # endif | |
284 | GC_finish_collection(); | |
20bbd3cd TT |
285 | } else { |
286 | if (!GC_is_full_gc) { | |
287 | /* Count this as the first attempt */ | |
288 | GC_n_attempts++; | |
289 | } | |
290 | } | |
73ffefd0 TT |
291 | } |
292 | } | |
293 | ||
294 | ||
295 | /* | |
296 | * Stop the world garbage collection. Assumes lock held, signals disabled. | |
297 | * If stop_func is not GC_never_stop_func, then abort if stop_func returns TRUE. | |
298 | */ | |
299 | GC_bool GC_try_to_collect_inner(stop_func) | |
300 | GC_stop_func stop_func; | |
301 | { | |
20bbd3cd | 302 | if (GC_incremental && GC_collection_in_progress()) { |
9110a741 BM |
303 | # ifdef CONDPRINT |
304 | if (GC_print_stats) { | |
73ffefd0 TT |
305 | GC_printf0( |
306 | "GC_try_to_collect_inner: finishing collection in progress\n"); | |
9110a741 BM |
307 | } |
308 | # endif /* CONDPRINT */ | |
73ffefd0 TT |
309 | /* Just finish collection already in progress. */ |
310 | while(GC_collection_in_progress()) { | |
311 | if (stop_func()) return(FALSE); | |
312 | GC_collect_a_little_inner(1); | |
313 | } | |
314 | } | |
9110a741 BM |
315 | # ifdef CONDPRINT |
316 | if (GC_print_stats) { | |
73ffefd0 TT |
317 | GC_printf2( |
318 | "Initiating full world-stop collection %lu after %ld allocd bytes\n", | |
319 | (unsigned long) GC_gc_no+1, | |
320 | (long)WORDS_TO_BYTES(GC_words_allocd)); | |
9110a741 | 321 | } |
73ffefd0 TT |
322 | # endif |
323 | GC_promote_black_lists(); | |
324 | /* Make sure all blocks have been reclaimed, so sweep routines */ | |
325 | /* don't see cleared mark bits. */ | |
326 | /* If we're guaranteed to finish, then this is unnecessary. */ | |
9110a741 BM |
327 | /* In the find_leak case, we have to finish to guarantee that */ |
328 | /* previously unmarked objects are not reported as leaks. */ | |
329 | # ifdef PARALLEL_MARK | |
330 | GC_wait_for_reclaim(); | |
331 | # endif | |
332 | if ((GC_find_leak || stop_func != GC_never_stop_func) | |
73ffefd0 TT |
333 | && !GC_reclaim_all(stop_func, FALSE)) { |
334 | /* Aborted. So far everything is still consistent. */ | |
335 | return(FALSE); | |
336 | } | |
337 | GC_invalidate_mark_state(); /* Flush mark stack. */ | |
338 | GC_clear_marks(); | |
339 | # ifdef SAVE_CALL_CHAIN | |
340 | GC_save_callers(GC_last_stack); | |
341 | # endif | |
20bbd3cd | 342 | GC_is_full_gc = TRUE; |
73ffefd0 TT |
343 | if (!GC_stopped_mark(stop_func)) { |
344 | if (!GC_incremental) { | |
345 | /* We're partially done and have no way to complete or use */ | |
346 | /* current work. Reestablish invariants as cheaply as */ | |
347 | /* possible. */ | |
348 | GC_invalidate_mark_state(); | |
349 | GC_unpromote_black_lists(); | |
350 | } /* else we claim the world is already still consistent. We'll */ | |
351 | /* finish incrementally. */ | |
352 | return(FALSE); | |
353 | } | |
354 | GC_finish_collection(); | |
355 | return(TRUE); | |
356 | } | |
357 | ||
358 | ||
359 | ||
360 | /* | |
361 | * Perform n units of garbage collection work. A unit is intended to touch | |
20bbd3cd TT |
362 | * roughly GC_RATE pages. Every once in a while, we do more than that. |
363 | * This needa to be a fairly large number with our current incremental | |
364 | * GC strategy, since otherwise we allocate too much during GC, and the | |
365 | * cleanup gets expensive. | |
73ffefd0 | 366 | */ |
20bbd3cd TT |
367 | # define GC_RATE 10 |
368 | # define MAX_PRIOR_ATTEMPTS 1 | |
369 | /* Maximum number of prior attempts at world stop marking */ | |
370 | /* A value of 1 means that we finish the seconf time, no matter */ | |
371 | /* how long it takes. Doesn't count the initial root scan */ | |
372 | /* for a full GC. */ | |
73ffefd0 TT |
373 | |
374 | int GC_deficit = 0; /* The number of extra calls to GC_mark_some */ | |
375 | /* that we have made. */ | |
73ffefd0 TT |
376 | |
377 | void GC_collect_a_little_inner(n) | |
378 | int n; | |
379 | { | |
380 | register int i; | |
381 | ||
20bbd3cd | 382 | if (GC_incremental && GC_collection_in_progress()) { |
73ffefd0 | 383 | for (i = GC_deficit; i < GC_RATE*n; i++) { |
20bbd3cd | 384 | if (GC_mark_some((ptr_t)0)) { |
73ffefd0 TT |
385 | /* Need to finish a collection */ |
386 | # ifdef SAVE_CALL_CHAIN | |
387 | GC_save_callers(GC_last_stack); | |
388 | # endif | |
20bbd3cd TT |
389 | if (GC_n_attempts < MAX_PRIOR_ATTEMPTS) { |
390 | GET_TIME(GC_start_time); | |
391 | if (!GC_stopped_mark(GC_timeout_stop_func)) { | |
392 | GC_n_attempts++; | |
393 | break; | |
394 | } | |
395 | } else { | |
396 | (void)GC_stopped_mark(GC_never_stop_func); | |
397 | } | |
73ffefd0 TT |
398 | GC_finish_collection(); |
399 | break; | |
400 | } | |
401 | } | |
402 | if (GC_deficit > 0) GC_deficit -= GC_RATE*n; | |
20bbd3cd | 403 | if (GC_deficit < 0) GC_deficit = 0; |
73ffefd0 TT |
404 | } else { |
405 | GC_maybe_gc(); | |
406 | } | |
407 | } | |
408 | ||
409 | int GC_collect_a_little GC_PROTO(()) | |
410 | { | |
411 | int result; | |
412 | DCL_LOCK_STATE; | |
413 | ||
414 | DISABLE_SIGNALS(); | |
415 | LOCK(); | |
416 | GC_collect_a_little_inner(1); | |
417 | result = (int)GC_collection_in_progress(); | |
418 | UNLOCK(); | |
419 | ENABLE_SIGNALS(); | |
420 | return(result); | |
421 | } | |
422 | ||
423 | /* | |
424 | * Assumes lock is held, signals are disabled. | |
425 | * We stop the world. | |
20bbd3cd | 426 | * If stop_func() ever returns TRUE, we may fail and return FALSE. |
73ffefd0 TT |
427 | * Increment GC_gc_no if we succeed. |
428 | */ | |
429 | GC_bool GC_stopped_mark(stop_func) | |
430 | GC_stop_func stop_func; | |
431 | { | |
432 | register int i; | |
20bbd3cd | 433 | int dummy; |
9110a741 | 434 | # ifdef PRINTTIMES |
73ffefd0 TT |
435 | CLOCK_TYPE start_time, current_time; |
436 | # endif | |
437 | ||
438 | STOP_WORLD(); | |
9110a741 | 439 | # ifdef PRINTTIMES |
73ffefd0 | 440 | GET_TIME(start_time); |
9110a741 BM |
441 | # endif |
442 | # ifdef CONDPRINT | |
443 | if (GC_print_stats) { | |
73ffefd0 TT |
444 | GC_printf1("--> Marking for collection %lu ", |
445 | (unsigned long) GC_gc_no + 1); | |
446 | GC_printf2("after %lu allocd bytes + %lu wasted bytes\n", | |
447 | (unsigned long) WORDS_TO_BYTES(GC_words_allocd), | |
448 | (unsigned long) WORDS_TO_BYTES(GC_words_wasted)); | |
9110a741 | 449 | } |
73ffefd0 TT |
450 | # endif |
451 | ||
452 | /* Mark from all roots. */ | |
453 | /* Minimize junk left in my registers and on the stack */ | |
454 | GC_clear_a_few_frames(); | |
455 | GC_noop(0,0,0,0,0,0); | |
456 | GC_initiate_gc(); | |
457 | for(i = 0;;i++) { | |
458 | if ((*stop_func)()) { | |
9110a741 BM |
459 | # ifdef CONDPRINT |
460 | if (GC_print_stats) { | |
73ffefd0 TT |
461 | GC_printf0("Abandoned stopped marking after "); |
462 | GC_printf1("%lu iterations\n", | |
463 | (unsigned long)i); | |
9110a741 | 464 | } |
73ffefd0 TT |
465 | # endif |
466 | GC_deficit = i; /* Give the mutator a chance. */ | |
467 | START_WORLD(); | |
468 | return(FALSE); | |
469 | } | |
20bbd3cd | 470 | if (GC_mark_some((ptr_t)(&dummy))) break; |
73ffefd0 TT |
471 | } |
472 | ||
473 | GC_gc_no++; | |
474 | # ifdef PRINTSTATS | |
475 | GC_printf2("Collection %lu reclaimed %ld bytes", | |
476 | (unsigned long) GC_gc_no - 1, | |
477 | (long)WORDS_TO_BYTES(GC_mem_found)); | |
9110a741 BM |
478 | # else |
479 | # ifdef CONDPRINT | |
480 | if (GC_print_stats) { | |
481 | GC_printf1("Collection %lu finished", (unsigned long) GC_gc_no - 1); | |
482 | } | |
483 | # endif | |
484 | # endif /* !PRINTSTATS */ | |
485 | # ifdef CONDPRINT | |
486 | if (GC_print_stats) { | |
487 | GC_printf1(" ---> heapsize = %lu bytes\n", | |
488 | (unsigned long) GC_heapsize); | |
489 | /* Printf arguments may be pushed in funny places. Clear the */ | |
490 | /* space. */ | |
491 | GC_printf0(""); | |
492 | } | |
493 | # endif /* CONDPRINT */ | |
73ffefd0 TT |
494 | |
495 | /* Check all debugged objects for consistency */ | |
496 | if (GC_debugging_started) { | |
497 | (*GC_check_heap)(); | |
498 | } | |
499 | ||
500 | # ifdef PRINTTIMES | |
501 | GET_TIME(current_time); | |
502 | GC_printf1("World-stopped marking took %lu msecs\n", | |
503 | MS_TIME_DIFF(current_time,start_time)); | |
504 | # endif | |
505 | START_WORLD(); | |
506 | return(TRUE); | |
507 | } | |
508 | ||
509 | ||
510 | /* Finish up a collection. Assumes lock is held, signals are disabled, */ | |
511 | /* but the world is otherwise running. */ | |
512 | void GC_finish_collection() | |
513 | { | |
514 | # ifdef PRINTTIMES | |
515 | CLOCK_TYPE start_time; | |
516 | CLOCK_TYPE finalize_time; | |
517 | CLOCK_TYPE done_time; | |
518 | ||
519 | GET_TIME(start_time); | |
520 | finalize_time = start_time; | |
521 | # endif | |
522 | ||
523 | # ifdef GATHERSTATS | |
524 | GC_mem_found = 0; | |
9110a741 BM |
525 | # endif |
526 | # if defined(LINUX) && defined(__ELF__) && !defined(SMALL_CONFIG) | |
527 | if (getenv("GC_PRINT_ADDRESS_MAP") != 0) { | |
528 | GC_print_address_map(); | |
529 | } | |
73ffefd0 | 530 | # endif |
20bbd3cd | 531 | if (GC_find_leak) { |
73ffefd0 TT |
532 | /* Mark all objects on the free list. All objects should be */ |
533 | /* marked when we're done. */ | |
534 | { | |
535 | register word size; /* current object size */ | |
536 | register ptr_t p; /* pointer to current object */ | |
537 | register struct hblk * h; /* pointer to block containing *p */ | |
538 | register hdr * hhdr; | |
539 | register int word_no; /* "index" of *p in *q */ | |
540 | int kind; | |
541 | ||
542 | for (kind = 0; kind < GC_n_kinds; kind++) { | |
543 | for (size = 1; size <= MAXOBJSZ; size++) { | |
544 | for (p= GC_obj_kinds[kind].ok_freelist[size]; | |
545 | p != 0; p=obj_link(p)){ | |
546 | h = HBLKPTR(p); | |
547 | hhdr = HDR(h); | |
548 | word_no = (((word *)p) - ((word *)h)); | |
549 | set_mark_bit_from_hdr(hhdr, word_no); | |
550 | } | |
551 | } | |
552 | } | |
553 | } | |
73ffefd0 | 554 | GC_start_reclaim(TRUE); |
20bbd3cd TT |
555 | /* The above just checks; it doesn't really reclaim anything. */ |
556 | } | |
557 | ||
558 | GC_finalize(); | |
559 | # ifdef STUBBORN_ALLOC | |
560 | GC_clean_changing_list(); | |
561 | # endif | |
73ffefd0 | 562 | |
20bbd3cd TT |
563 | # ifdef PRINTTIMES |
564 | GET_TIME(finalize_time); | |
565 | # endif | |
566 | ||
567 | /* Clear free list mark bits, in case they got accidentally marked */ | |
568 | /* Note: HBLKPTR(p) == pointer to head of block containing *p */ | |
569 | /* (or GC_find_leak is set and they were intentionally marked.) */ | |
570 | /* Also subtract memory remaining from GC_mem_found count. */ | |
571 | /* Note that composite objects on free list are cleared. */ | |
572 | /* Thus accidentally marking a free list is not a problem; only */ | |
573 | /* objects on the list itself will be marked, and that's fixed here. */ | |
73ffefd0 TT |
574 | { |
575 | register word size; /* current object size */ | |
576 | register ptr_t p; /* pointer to current object */ | |
577 | register struct hblk * h; /* pointer to block containing *p */ | |
578 | register hdr * hhdr; | |
579 | register int word_no; /* "index" of *p in *q */ | |
580 | int kind; | |
581 | ||
582 | for (kind = 0; kind < GC_n_kinds; kind++) { | |
583 | for (size = 1; size <= MAXOBJSZ; size++) { | |
584 | for (p= GC_obj_kinds[kind].ok_freelist[size]; | |
585 | p != 0; p=obj_link(p)){ | |
586 | h = HBLKPTR(p); | |
587 | hhdr = HDR(h); | |
588 | word_no = (((word *)p) - ((word *)h)); | |
589 | clear_mark_bit_from_hdr(hhdr, word_no); | |
590 | # ifdef GATHERSTATS | |
591 | GC_mem_found -= size; | |
592 | # endif | |
593 | } | |
594 | } | |
595 | } | |
596 | } | |
597 | ||
598 | ||
20bbd3cd | 599 | # ifdef PRINTSTATS |
73ffefd0 TT |
600 | GC_printf1("Bytes recovered before sweep - f.l. count = %ld\n", |
601 | (long)WORDS_TO_BYTES(GC_mem_found)); | |
20bbd3cd | 602 | # endif |
73ffefd0 | 603 | /* Reconstruct free lists to contain everything not marked */ |
20bbd3cd TT |
604 | GC_start_reclaim(FALSE); |
605 | if (GC_is_full_gc) { | |
606 | GC_used_heap_size_after_full = USED_HEAP_SIZE; | |
607 | GC_need_full_gc = FALSE; | |
608 | } else { | |
609 | GC_need_full_gc = | |
610 | BYTES_TO_WORDS(USED_HEAP_SIZE - GC_used_heap_size_after_full) | |
611 | > min_words_allocd(); | |
612 | } | |
73ffefd0 TT |
613 | |
614 | # ifdef PRINTSTATS | |
615 | GC_printf2( | |
20bbd3cd | 616 | "Immediately reclaimed %ld bytes in heap of size %lu bytes", |
73ffefd0 TT |
617 | (long)WORDS_TO_BYTES(GC_mem_found), |
618 | (unsigned long)GC_heapsize); | |
20bbd3cd TT |
619 | # ifdef USE_MUNMAP |
620 | GC_printf1("(%lu unmapped)", GC_unmapped_bytes); | |
621 | # endif | |
622 | GC_printf2( | |
623 | "\n%lu (atomic) + %lu (composite) collectable bytes in use\n", | |
624 | (unsigned long)WORDS_TO_BYTES(GC_atomic_in_use), | |
625 | (unsigned long)WORDS_TO_BYTES(GC_composite_in_use)); | |
73ffefd0 TT |
626 | # endif |
627 | ||
20bbd3cd TT |
628 | GC_n_attempts = 0; |
629 | GC_is_full_gc = FALSE; | |
73ffefd0 TT |
630 | /* Reset or increment counters for next cycle */ |
631 | GC_words_allocd_before_gc += GC_words_allocd; | |
632 | GC_non_gc_bytes_at_gc = GC_non_gc_bytes; | |
633 | GC_words_allocd = 0; | |
634 | GC_words_wasted = 0; | |
635 | GC_mem_freed = 0; | |
636 | ||
20bbd3cd TT |
637 | # ifdef USE_MUNMAP |
638 | GC_unmap_old(); | |
639 | # endif | |
73ffefd0 TT |
640 | # ifdef PRINTTIMES |
641 | GET_TIME(done_time); | |
642 | GC_printf2("Finalize + initiate sweep took %lu + %lu msecs\n", | |
643 | MS_TIME_DIFF(finalize_time,start_time), | |
644 | MS_TIME_DIFF(done_time,finalize_time)); | |
645 | # endif | |
646 | } | |
647 | ||
648 | /* Externally callable routine to invoke full, stop-world collection */ | |
649 | # if defined(__STDC__) || defined(__cplusplus) | |
650 | int GC_try_to_collect(GC_stop_func stop_func) | |
651 | # else | |
652 | int GC_try_to_collect(stop_func) | |
653 | GC_stop_func stop_func; | |
654 | # endif | |
655 | { | |
656 | int result; | |
657 | DCL_LOCK_STATE; | |
658 | ||
659 | GC_INVOKE_FINALIZERS(); | |
660 | DISABLE_SIGNALS(); | |
661 | LOCK(); | |
662 | ENTER_GC(); | |
663 | if (!GC_is_initialized) GC_init_inner(); | |
664 | /* Minimize junk left in my registers */ | |
665 | GC_noop(0,0,0,0,0,0); | |
666 | result = (int)GC_try_to_collect_inner(stop_func); | |
667 | EXIT_GC(); | |
668 | UNLOCK(); | |
669 | ENABLE_SIGNALS(); | |
670 | if(result) GC_INVOKE_FINALIZERS(); | |
671 | return(result); | |
672 | } | |
673 | ||
674 | void GC_gcollect GC_PROTO(()) | |
675 | { | |
676 | GC_notify_full_gc(); | |
677 | (void)GC_try_to_collect(GC_never_stop_func); | |
678 | } | |
679 | ||
680 | word GC_n_heap_sects = 0; /* Number of sections currently in heap. */ | |
681 | ||
682 | /* | |
20bbd3cd | 683 | * Use the chunk of memory starting at p of size bytes as part of the heap. |
73ffefd0 TT |
684 | * Assumes p is HBLKSIZE aligned, and bytes is a multiple of HBLKSIZE. |
685 | */ | |
686 | void GC_add_to_heap(p, bytes) | |
687 | struct hblk *p; | |
688 | word bytes; | |
689 | { | |
690 | word words; | |
20bbd3cd | 691 | hdr * phdr; |
73ffefd0 TT |
692 | |
693 | if (GC_n_heap_sects >= MAX_HEAP_SECTS) { | |
694 | ABORT("Too many heap sections: Increase MAXHINCR or MAX_HEAP_SECTS"); | |
695 | } | |
93002327 BM |
696 | phdr = GC_install_header(p); |
697 | if (0 == phdr) { | |
73ffefd0 TT |
698 | /* This is extremely unlikely. Can't add it. This will */ |
699 | /* almost certainly result in a 0 return from the allocator, */ | |
700 | /* which is entirely appropriate. */ | |
701 | return; | |
702 | } | |
703 | GC_heap_sects[GC_n_heap_sects].hs_start = (ptr_t)p; | |
704 | GC_heap_sects[GC_n_heap_sects].hs_bytes = bytes; | |
705 | GC_n_heap_sects++; | |
9110a741 | 706 | words = BYTES_TO_WORDS(bytes); |
20bbd3cd | 707 | phdr -> hb_sz = words; |
9110a741 | 708 | phdr -> hb_map = (unsigned char *)1; /* A value != GC_invalid_map */ |
20bbd3cd | 709 | phdr -> hb_flags = 0; |
73ffefd0 TT |
710 | GC_freehblk(p); |
711 | GC_heapsize += bytes; | |
9110a741 | 712 | if ((ptr_t)p <= (ptr_t)GC_least_plausible_heap_addr |
73ffefd0 | 713 | || GC_least_plausible_heap_addr == 0) { |
9110a741 | 714 | GC_least_plausible_heap_addr = (GC_PTR)((ptr_t)p - sizeof(word)); |
73ffefd0 TT |
715 | /* Making it a little smaller than necessary prevents */ |
716 | /* us from getting a false hit from the variable */ | |
717 | /* itself. There's some unintentional reflection */ | |
718 | /* here. */ | |
719 | } | |
9110a741 BM |
720 | if ((ptr_t)p + bytes >= (ptr_t)GC_greatest_plausible_heap_addr) { |
721 | GC_greatest_plausible_heap_addr = (GC_PTR)((ptr_t)p + bytes); | |
73ffefd0 TT |
722 | } |
723 | } | |
724 | ||
73ffefd0 TT |
725 | # if !defined(NO_DEBUGGING) |
726 | void GC_print_heap_sects() | |
727 | { | |
728 | register unsigned i; | |
729 | ||
730 | GC_printf1("Total heap size: %lu\n", (unsigned long) GC_heapsize); | |
731 | for (i = 0; i < GC_n_heap_sects; i++) { | |
732 | unsigned long start = (unsigned long) GC_heap_sects[i].hs_start; | |
733 | unsigned long len = (unsigned long) GC_heap_sects[i].hs_bytes; | |
734 | struct hblk *h; | |
735 | unsigned nbl = 0; | |
736 | ||
737 | GC_printf3("Section %ld from 0x%lx to 0x%lx ", (unsigned long)i, | |
738 | start, (unsigned long)(start + len)); | |
739 | for (h = (struct hblk *)start; h < (struct hblk *)(start + len); h++) { | |
740 | if (GC_is_black_listed(h, HBLKSIZE)) nbl++; | |
741 | } | |
742 | GC_printf2("%lu/%lu blacklisted\n", (unsigned long)nbl, | |
743 | (unsigned long)(len/HBLKSIZE)); | |
744 | } | |
745 | } | |
746 | # endif | |
747 | ||
9110a741 BM |
748 | GC_PTR GC_least_plausible_heap_addr = (GC_PTR)ONES; |
749 | GC_PTR GC_greatest_plausible_heap_addr = 0; | |
73ffefd0 TT |
750 | |
751 | ptr_t GC_max(x,y) | |
752 | ptr_t x, y; | |
753 | { | |
754 | return(x > y? x : y); | |
755 | } | |
756 | ||
757 | ptr_t GC_min(x,y) | |
758 | ptr_t x, y; | |
759 | { | |
760 | return(x < y? x : y); | |
761 | } | |
762 | ||
763 | # if defined(__STDC__) || defined(__cplusplus) | |
764 | void GC_set_max_heap_size(GC_word n) | |
765 | # else | |
766 | void GC_set_max_heap_size(n) | |
767 | GC_word n; | |
768 | # endif | |
769 | { | |
770 | GC_max_heapsize = n; | |
771 | } | |
772 | ||
773 | GC_word GC_max_retries = 0; | |
774 | ||
775 | /* | |
776 | * this explicitly increases the size of the heap. It is used | |
777 | * internally, but may also be invoked from GC_expand_hp by the user. | |
778 | * The argument is in units of HBLKSIZE. | |
779 | * Tiny values of n are rounded up. | |
780 | * Returns FALSE on failure. | |
781 | */ | |
782 | GC_bool GC_expand_hp_inner(n) | |
783 | word n; | |
784 | { | |
785 | word bytes; | |
786 | struct hblk * space; | |
787 | word expansion_slop; /* Number of bytes by which we expect the */ | |
788 | /* heap to expand soon. */ | |
789 | ||
790 | if (n < MINHINCR) n = MINHINCR; | |
791 | bytes = n * HBLKSIZE; | |
792 | /* Make sure bytes is a multiple of GC_page_size */ | |
793 | { | |
794 | word mask = GC_page_size - 1; | |
795 | bytes += mask; | |
796 | bytes &= ~mask; | |
797 | } | |
798 | ||
799 | if (GC_max_heapsize != 0 && GC_heapsize + bytes > GC_max_heapsize) { | |
800 | /* Exceeded self-imposed limit */ | |
801 | return(FALSE); | |
802 | } | |
803 | space = GET_MEM(bytes); | |
804 | if( space == 0 ) { | |
9110a741 BM |
805 | # ifdef CONDPRINT |
806 | if (GC_print_stats) { | |
807 | GC_printf1("Failed to expand heap by %ld bytes\n", | |
808 | (unsigned long)bytes); | |
809 | } | |
810 | # endif | |
73ffefd0 TT |
811 | return(FALSE); |
812 | } | |
9110a741 BM |
813 | # ifdef CONDPRINT |
814 | if (GC_print_stats) { | |
73ffefd0 TT |
815 | GC_printf2("Increasing heap size by %lu after %lu allocated bytes\n", |
816 | (unsigned long)bytes, | |
817 | (unsigned long)WORDS_TO_BYTES(GC_words_allocd)); | |
818 | # ifdef UNDEFINED | |
819 | GC_printf1("Root size = %lu\n", GC_root_size); | |
820 | GC_print_block_list(); GC_print_hblkfreelist(); | |
821 | GC_printf0("\n"); | |
822 | # endif | |
9110a741 | 823 | } |
73ffefd0 TT |
824 | # endif |
825 | expansion_slop = 8 * WORDS_TO_BYTES(min_words_allocd()); | |
826 | if (5 * HBLKSIZE * MAXHINCR > expansion_slop) { | |
827 | expansion_slop = 5 * HBLKSIZE * MAXHINCR; | |
828 | } | |
829 | if (GC_last_heap_addr == 0 && !((word)space & SIGNB) | |
830 | || GC_last_heap_addr != 0 && GC_last_heap_addr < (ptr_t)space) { | |
831 | /* Assume the heap is growing up */ | |
832 | GC_greatest_plausible_heap_addr = | |
833 | GC_max(GC_greatest_plausible_heap_addr, | |
834 | (ptr_t)space + bytes + expansion_slop); | |
835 | } else { | |
836 | /* Heap is growing down */ | |
837 | GC_least_plausible_heap_addr = | |
838 | GC_min(GC_least_plausible_heap_addr, | |
839 | (ptr_t)space - expansion_slop); | |
840 | } | |
841 | GC_prev_heap_addr = GC_last_heap_addr; | |
842 | GC_last_heap_addr = (ptr_t)space; | |
843 | GC_add_to_heap(space, bytes); | |
844 | return(TRUE); | |
845 | } | |
846 | ||
847 | /* Really returns a bool, but it's externally visible, so that's clumsy. */ | |
848 | /* Arguments is in bytes. */ | |
849 | # if defined(__STDC__) || defined(__cplusplus) | |
850 | int GC_expand_hp(size_t bytes) | |
851 | # else | |
852 | int GC_expand_hp(bytes) | |
853 | size_t bytes; | |
854 | # endif | |
855 | { | |
856 | int result; | |
857 | DCL_LOCK_STATE; | |
858 | ||
859 | DISABLE_SIGNALS(); | |
860 | LOCK(); | |
861 | if (!GC_is_initialized) GC_init_inner(); | |
862 | result = (int)GC_expand_hp_inner(divHBLKSZ((word)bytes)); | |
93002327 | 863 | if (result) GC_requested_heapsize += bytes; |
73ffefd0 TT |
864 | UNLOCK(); |
865 | ENABLE_SIGNALS(); | |
866 | return(result); | |
867 | } | |
868 | ||
869 | unsigned GC_fail_count = 0; | |
870 | /* How many consecutive GC/expansion failures? */ | |
871 | /* Reset by GC_allochblk. */ | |
872 | ||
873 | GC_bool GC_collect_or_expand(needed_blocks, ignore_off_page) | |
874 | word needed_blocks; | |
875 | GC_bool ignore_off_page; | |
876 | { | |
93002327 BM |
877 | if (!GC_incremental && !GC_dont_gc && |
878 | (GC_dont_expand && GC_words_allocd > 0 || GC_should_collect())) { | |
73ffefd0 TT |
879 | GC_notify_full_gc(); |
880 | GC_gcollect_inner(); | |
881 | } else { | |
882 | word blocks_to_get = GC_heapsize/(HBLKSIZE*GC_free_space_divisor) | |
883 | + needed_blocks; | |
884 | ||
885 | if (blocks_to_get > MAXHINCR) { | |
886 | word slop; | |
887 | ||
888 | if (ignore_off_page) { | |
889 | slop = 4; | |
890 | } else { | |
891 | slop = 2*divHBLKSZ(BL_LIMIT); | |
892 | if (slop > needed_blocks) slop = needed_blocks; | |
893 | } | |
894 | if (needed_blocks + slop > MAXHINCR) { | |
895 | blocks_to_get = needed_blocks + slop; | |
896 | } else { | |
897 | blocks_to_get = MAXHINCR; | |
898 | } | |
899 | } | |
900 | if (!GC_expand_hp_inner(blocks_to_get) | |
901 | && !GC_expand_hp_inner(needed_blocks)) { | |
902 | if (GC_fail_count++ < GC_max_retries) { | |
903 | WARN("Out of Memory! Trying to continue ...\n", 0); | |
904 | GC_notify_full_gc(); | |
905 | GC_gcollect_inner(); | |
906 | } else { | |
9110a741 BM |
907 | # if !defined(AMIGA) || !defined(GC_AMIGA_FASTALLOC) |
908 | WARN("Out of Memory! Returning NIL!\n", 0); | |
909 | # endif | |
73ffefd0 TT |
910 | return(FALSE); |
911 | } | |
20bbd3cd | 912 | } else { |
9110a741 BM |
913 | # ifdef CONDPRINT |
914 | if (GC_fail_count && GC_print_stats) { | |
20bbd3cd TT |
915 | GC_printf0("Memory available again ...\n"); |
916 | } | |
73ffefd0 TT |
917 | # endif |
918 | } | |
919 | } | |
920 | return(TRUE); | |
921 | } | |
922 | ||
923 | /* | |
924 | * Make sure the object free list for sz is not empty. | |
925 | * Return a pointer to the first object on the free list. | |
926 | * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER. | |
927 | * Assumes we hold the allocator lock and signals are disabled. | |
928 | * | |
929 | */ | |
930 | ptr_t GC_allocobj(sz, kind) | |
931 | word sz; | |
932 | int kind; | |
933 | { | |
934 | register ptr_t * flh = &(GC_obj_kinds[kind].ok_freelist[sz]); | |
935 | ||
936 | if (sz == 0) return(0); | |
937 | ||
938 | while (*flh == 0) { | |
939 | ENTER_GC(); | |
940 | /* Do our share of marking work */ | |
941 | if(GC_incremental && !GC_dont_gc) GC_collect_a_little_inner(1); | |
942 | /* Sweep blocks for objects of this size */ | |
943 | GC_continue_reclaim(sz, kind); | |
944 | EXIT_GC(); | |
945 | if (*flh == 0) { | |
946 | GC_new_hblk(sz, kind); | |
947 | } | |
948 | if (*flh == 0) { | |
949 | ENTER_GC(); | |
950 | if (!GC_collect_or_expand((word)1,FALSE)) { | |
951 | EXIT_GC(); | |
952 | return(0); | |
953 | } | |
954 | EXIT_GC(); | |
955 | } | |
956 | } | |
957 | ||
958 | return(*flh); | |
959 | } |