]>
Commit | Line | Data |
---|---|---|
73ffefd0 TT |
1 | /* |
2 | * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers | |
3 | * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. | |
4 | * | |
5 | * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED | |
6 | * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. | |
7 | * | |
8 | * Permission is hereby granted to use or copy this program | |
9 | * for any purpose, provided the above notices are retained on all copies. | |
10 | * Permission to modify the code and to distribute modified code is granted, | |
11 | * provided the above notices are retained, and a notice that the code was | |
12 | * modified is included with the above copyright notice. | |
13 | */ | |
14 | /* Boehm, October 9, 1995 1:06 pm PDT */ | |
15 | # include <stdio.h> | |
16 | # include "gc_priv.h" | |
17 | ||
73ffefd0 TT |
18 | /* Data structure for list of root sets. */ |
19 | /* We keep a hash table, so that we can filter out duplicate additions. */ | |
20 | /* Under Win32, we need to do a better job of filtering overlaps, so */ | |
21 | /* we resort to sequential search, and pay the price. */ | |
20bbd3cd | 22 | /* This is really declared in gc_priv.h: |
73ffefd0 TT |
23 | struct roots { |
24 | ptr_t r_start; | |
25 | ptr_t r_end; | |
20bbd3cd | 26 | # ifndef MSWIN32 |
73ffefd0 | 27 | struct roots * r_next; |
20bbd3cd | 28 | # endif |
73ffefd0 | 29 | GC_bool r_tmp; |
20bbd3cd | 30 | -- Delete before registering new dynamic libraries |
73ffefd0 TT |
31 | }; |
32 | ||
20bbd3cd TT |
33 | struct roots GC_static_roots[MAX_ROOT_SETS]; |
34 | */ | |
73ffefd0 TT |
35 | |
36 | static int n_root_sets = 0; | |
37 | ||
20bbd3cd | 38 | /* GC_static_roots[0..n_root_sets) contains the valid root sets. */ |
73ffefd0 TT |
39 | |
40 | # if !defined(NO_DEBUGGING) | |
41 | /* For debugging: */ | |
42 | void GC_print_static_roots() | |
43 | { | |
44 | register int i; | |
45 | size_t total = 0; | |
46 | ||
47 | for (i = 0; i < n_root_sets; i++) { | |
48 | GC_printf2("From 0x%lx to 0x%lx ", | |
20bbd3cd TT |
49 | (unsigned long) GC_static_roots[i].r_start, |
50 | (unsigned long) GC_static_roots[i].r_end); | |
51 | if (GC_static_roots[i].r_tmp) { | |
73ffefd0 TT |
52 | GC_printf0(" (temporary)\n"); |
53 | } else { | |
54 | GC_printf0("\n"); | |
55 | } | |
20bbd3cd | 56 | total += GC_static_roots[i].r_end - GC_static_roots[i].r_start; |
73ffefd0 TT |
57 | } |
58 | GC_printf1("Total size: %ld\n", (unsigned long) total); | |
59 | if (GC_root_size != total) { | |
60 | GC_printf1("GC_root_size incorrect: %ld!!\n", | |
61 | (unsigned long) GC_root_size); | |
62 | } | |
63 | } | |
64 | # endif /* NO_DEBUGGING */ | |
65 | ||
66 | /* Primarily for debugging support: */ | |
67 | /* Is the address p in one of the registered static */ | |
68 | /* root sections? */ | |
69 | GC_bool GC_is_static_root(p) | |
70 | ptr_t p; | |
71 | { | |
72 | static int last_root_set = 0; | |
73 | register int i; | |
74 | ||
75 | ||
20bbd3cd TT |
76 | if (p >= GC_static_roots[last_root_set].r_start |
77 | && p < GC_static_roots[last_root_set].r_end) return(TRUE); | |
73ffefd0 | 78 | for (i = 0; i < n_root_sets; i++) { |
20bbd3cd TT |
79 | if (p >= GC_static_roots[i].r_start |
80 | && p < GC_static_roots[i].r_end) { | |
73ffefd0 TT |
81 | last_root_set = i; |
82 | return(TRUE); | |
83 | } | |
84 | } | |
85 | return(FALSE); | |
86 | } | |
87 | ||
88 | #ifndef MSWIN32 | |
20bbd3cd | 89 | /* |
73ffefd0 | 90 | # define LOG_RT_SIZE 6 |
20bbd3cd | 91 | # define RT_SIZE (1 << LOG_RT_SIZE) -- Power of 2, may be != MAX_ROOT_SETS |
73ffefd0 | 92 | |
20bbd3cd TT |
93 | struct roots * GC_root_index[RT_SIZE]; |
94 | -- Hash table header. Used only to check whether a range is | |
95 | -- already present. | |
96 | -- really defined in gc_priv.h | |
97 | */ | |
73ffefd0 TT |
98 | |
99 | static int rt_hash(addr) | |
100 | char * addr; | |
101 | { | |
102 | word result = (word) addr; | |
103 | # if CPP_WORDSZ > 8*LOG_RT_SIZE | |
104 | result ^= result >> 8*LOG_RT_SIZE; | |
105 | # endif | |
106 | # if CPP_WORDSZ > 4*LOG_RT_SIZE | |
107 | result ^= result >> 4*LOG_RT_SIZE; | |
108 | # endif | |
109 | result ^= result >> 2*LOG_RT_SIZE; | |
110 | result ^= result >> LOG_RT_SIZE; | |
111 | result &= (RT_SIZE-1); | |
112 | return(result); | |
113 | } | |
114 | ||
115 | /* Is a range starting at b already in the table? If so return a */ | |
116 | /* pointer to it, else NIL. */ | |
117 | struct roots * GC_roots_present(b) | |
118 | char *b; | |
119 | { | |
120 | register int h = rt_hash(b); | |
20bbd3cd | 121 | register struct roots *p = GC_root_index[h]; |
73ffefd0 TT |
122 | |
123 | while (p != 0) { | |
124 | if (p -> r_start == (ptr_t)b) return(p); | |
125 | p = p -> r_next; | |
126 | } | |
127 | return(FALSE); | |
128 | } | |
129 | ||
130 | /* Add the given root structure to the index. */ | |
131 | static void add_roots_to_index(p) | |
132 | struct roots *p; | |
133 | { | |
134 | register int h = rt_hash(p -> r_start); | |
135 | ||
20bbd3cd TT |
136 | p -> r_next = GC_root_index[h]; |
137 | GC_root_index[h] = p; | |
73ffefd0 TT |
138 | } |
139 | ||
140 | # else /* MSWIN32 */ | |
141 | ||
142 | # define add_roots_to_index(p) | |
143 | ||
144 | # endif | |
145 | ||
146 | ||
147 | ||
148 | ||
149 | word GC_root_size = 0; | |
150 | ||
151 | void GC_add_roots(b, e) | |
152 | char * b; char * e; | |
153 | { | |
154 | DCL_LOCK_STATE; | |
155 | ||
156 | DISABLE_SIGNALS(); | |
157 | LOCK(); | |
158 | GC_add_roots_inner(b, e, FALSE); | |
159 | UNLOCK(); | |
160 | ENABLE_SIGNALS(); | |
161 | } | |
162 | ||
163 | ||
164 | /* Add [b,e) to the root set. Adding the same interval a second time */ | |
165 | /* is a moderately fast noop, and hence benign. We do not handle */ | |
166 | /* different but overlapping intervals efficiently. (We do handle */ | |
167 | /* them correctly.) */ | |
168 | /* Tmp specifies that the interval may be deleted before */ | |
169 | /* reregistering dynamic libraries. */ | |
170 | void GC_add_roots_inner(b, e, tmp) | |
171 | char * b; char * e; | |
172 | GC_bool tmp; | |
173 | { | |
174 | struct roots * old; | |
175 | ||
176 | # ifdef MSWIN32 | |
177 | /* Spend the time to ensure that there are no overlapping */ | |
178 | /* or adjacent intervals. */ | |
179 | /* This could be done faster with e.g. a */ | |
180 | /* balanced tree. But the execution time here is */ | |
181 | /* virtually guaranteed to be dominated by the time it */ | |
182 | /* takes to scan the roots. */ | |
183 | { | |
184 | register int i; | |
185 | ||
186 | for (i = 0; i < n_root_sets; i++) { | |
20bbd3cd | 187 | old = GC_static_roots + i; |
73ffefd0 TT |
188 | if ((ptr_t)b <= old -> r_end && (ptr_t)e >= old -> r_start) { |
189 | if ((ptr_t)b < old -> r_start) { | |
190 | old -> r_start = (ptr_t)b; | |
191 | GC_root_size += (old -> r_start - (ptr_t)b); | |
192 | } | |
193 | if ((ptr_t)e > old -> r_end) { | |
194 | old -> r_end = (ptr_t)e; | |
195 | GC_root_size += ((ptr_t)e - old -> r_end); | |
196 | } | |
197 | old -> r_tmp &= tmp; | |
198 | break; | |
199 | } | |
200 | } | |
201 | if (i < n_root_sets) { | |
202 | /* merge other overlapping intervals */ | |
203 | struct roots *other; | |
204 | ||
205 | for (i++; i < n_root_sets; i++) { | |
20bbd3cd | 206 | other = GC_static_roots + i; |
73ffefd0 TT |
207 | b = (char *)(other -> r_start); |
208 | e = (char *)(other -> r_end); | |
209 | if ((ptr_t)b <= old -> r_end && (ptr_t)e >= old -> r_start) { | |
210 | if ((ptr_t)b < old -> r_start) { | |
211 | old -> r_start = (ptr_t)b; | |
212 | GC_root_size += (old -> r_start - (ptr_t)b); | |
213 | } | |
214 | if ((ptr_t)e > old -> r_end) { | |
215 | old -> r_end = (ptr_t)e; | |
216 | GC_root_size += ((ptr_t)e - old -> r_end); | |
217 | } | |
218 | old -> r_tmp &= other -> r_tmp; | |
219 | /* Delete this entry. */ | |
220 | GC_root_size -= (other -> r_end - other -> r_start); | |
20bbd3cd TT |
221 | other -> r_start = GC_static_roots[n_root_sets-1].r_start; |
222 | other -> r_end = GC_static_roots[n_root_sets-1].r_end; | |
73ffefd0 TT |
223 | n_root_sets--; |
224 | } | |
225 | } | |
226 | return; | |
227 | } | |
228 | } | |
229 | # else | |
230 | old = GC_roots_present(b); | |
231 | if (old != 0) { | |
232 | if ((ptr_t)e <= old -> r_end) /* already there */ return; | |
233 | /* else extend */ | |
234 | GC_root_size += (ptr_t)e - old -> r_end; | |
235 | old -> r_end = (ptr_t)e; | |
236 | return; | |
237 | } | |
238 | # endif | |
239 | if (n_root_sets == MAX_ROOT_SETS) { | |
240 | ABORT("Too many root sets\n"); | |
241 | } | |
20bbd3cd TT |
242 | GC_static_roots[n_root_sets].r_start = (ptr_t)b; |
243 | GC_static_roots[n_root_sets].r_end = (ptr_t)e; | |
244 | GC_static_roots[n_root_sets].r_tmp = tmp; | |
73ffefd0 | 245 | # ifndef MSWIN32 |
20bbd3cd | 246 | GC_static_roots[n_root_sets].r_next = 0; |
73ffefd0 | 247 | # endif |
20bbd3cd | 248 | add_roots_to_index(GC_static_roots + n_root_sets); |
73ffefd0 TT |
249 | GC_root_size += (ptr_t)e - (ptr_t)b; |
250 | n_root_sets++; | |
251 | } | |
252 | ||
253 | void GC_clear_roots GC_PROTO((void)) | |
254 | { | |
255 | DCL_LOCK_STATE; | |
256 | ||
257 | DISABLE_SIGNALS(); | |
258 | LOCK(); | |
259 | n_root_sets = 0; | |
260 | GC_root_size = 0; | |
261 | # ifndef MSWIN32 | |
262 | { | |
263 | register int i; | |
264 | ||
20bbd3cd | 265 | for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0; |
73ffefd0 TT |
266 | } |
267 | # endif | |
268 | UNLOCK(); | |
269 | ENABLE_SIGNALS(); | |
270 | } | |
271 | ||
272 | /* Internal use only; lock held. */ | |
273 | void GC_remove_tmp_roots() | |
274 | { | |
275 | register int i; | |
276 | ||
277 | for (i = 0; i < n_root_sets; ) { | |
20bbd3cd TT |
278 | if (GC_static_roots[i].r_tmp) { |
279 | GC_root_size -= | |
280 | (GC_static_roots[i].r_end - GC_static_roots[i].r_start); | |
281 | GC_static_roots[i].r_start = GC_static_roots[n_root_sets-1].r_start; | |
282 | GC_static_roots[i].r_end = GC_static_roots[n_root_sets-1].r_end; | |
283 | GC_static_roots[i].r_tmp = GC_static_roots[n_root_sets-1].r_tmp; | |
73ffefd0 TT |
284 | n_root_sets--; |
285 | } else { | |
286 | i++; | |
287 | } | |
288 | } | |
289 | # ifndef MSWIN32 | |
290 | { | |
291 | register int i; | |
292 | ||
20bbd3cd TT |
293 | for (i = 0; i < RT_SIZE; i++) GC_root_index[i] = 0; |
294 | for (i = 0; i < n_root_sets; i++) | |
295 | add_roots_to_index(GC_static_roots + i); | |
73ffefd0 TT |
296 | } |
297 | # endif | |
298 | ||
299 | } | |
300 | ||
301 | ptr_t GC_approx_sp() | |
302 | { | |
303 | word dummy; | |
304 | ||
305 | return((ptr_t)(&dummy)); | |
306 | } | |
307 | ||
308 | /* | |
309 | * Data structure for excluded static roots. | |
20bbd3cd TT |
310 | * Real declaration is in gc_priv.h. |
311 | ||
73ffefd0 TT |
312 | struct exclusion { |
313 | ptr_t e_start; | |
314 | ptr_t e_end; | |
315 | }; | |
316 | ||
20bbd3cd TT |
317 | struct exclusion GC_excl_table[MAX_EXCLUSIONS]; |
318 | -- Array of exclusions, ascending | |
319 | -- address order. | |
320 | */ | |
321 | ||
322 | size_t GC_excl_table_entries = 0; /* Number of entries in use. */ | |
73ffefd0 TT |
323 | |
324 | /* Return the first exclusion range that includes an address >= start_addr */ | |
325 | /* Assumes the exclusion table contains at least one entry (namely the */ | |
326 | /* GC data structures). */ | |
327 | struct exclusion * GC_next_exclusion(start_addr) | |
328 | ptr_t start_addr; | |
329 | { | |
330 | size_t low = 0; | |
20bbd3cd | 331 | size_t high = GC_excl_table_entries - 1; |
73ffefd0 TT |
332 | size_t mid; |
333 | ||
334 | while (high > low) { | |
335 | mid = (low + high) >> 1; | |
336 | /* low <= mid < high */ | |
20bbd3cd | 337 | if ((word) GC_excl_table[mid].e_end <= (word) start_addr) { |
73ffefd0 TT |
338 | low = mid + 1; |
339 | } else { | |
340 | high = mid; | |
341 | } | |
342 | } | |
20bbd3cd TT |
343 | if ((word) GC_excl_table[low].e_end <= (word) start_addr) return 0; |
344 | return GC_excl_table + low; | |
73ffefd0 TT |
345 | } |
346 | ||
347 | void GC_exclude_static_roots(start, finish) | |
348 | GC_PTR start; | |
349 | GC_PTR finish; | |
350 | { | |
351 | struct exclusion * next; | |
352 | size_t next_index, i; | |
353 | ||
20bbd3cd | 354 | if (0 == GC_excl_table_entries) { |
73ffefd0 TT |
355 | next = 0; |
356 | } else { | |
357 | next = GC_next_exclusion(start); | |
358 | } | |
359 | if (0 != next) { | |
360 | if ((word)(next -> e_start) < (word) finish) { | |
361 | /* incomplete error check. */ | |
362 | ABORT("exclusion ranges overlap"); | |
363 | } | |
364 | if ((word)(next -> e_start) == (word) finish) { | |
365 | /* extend old range backwards */ | |
366 | next -> e_start = (ptr_t)start; | |
367 | return; | |
368 | } | |
20bbd3cd TT |
369 | next_index = next - GC_excl_table; |
370 | for (i = GC_excl_table_entries; i > next_index; --i) { | |
371 | GC_excl_table[i] = GC_excl_table[i-1]; | |
73ffefd0 TT |
372 | } |
373 | } else { | |
20bbd3cd | 374 | next_index = GC_excl_table_entries; |
73ffefd0 | 375 | } |
20bbd3cd TT |
376 | if (GC_excl_table_entries == MAX_EXCLUSIONS) ABORT("Too many exclusions"); |
377 | GC_excl_table[next_index].e_start = (ptr_t)start; | |
378 | GC_excl_table[next_index].e_end = (ptr_t)finish; | |
379 | ++GC_excl_table_entries; | |
73ffefd0 TT |
380 | } |
381 | ||
382 | /* Invoke push_conditional on ranges that are not excluded. */ | |
383 | void GC_push_conditional_with_exclusions(bottom, top, all) | |
384 | ptr_t bottom; | |
385 | ptr_t top; | |
386 | int all; | |
387 | { | |
388 | struct exclusion * next; | |
389 | ptr_t excl_start; | |
390 | ||
391 | while (bottom < top) { | |
392 | next = GC_next_exclusion(bottom); | |
393 | if (0 == next || (excl_start = next -> e_start) >= top) { | |
394 | GC_push_conditional(bottom, top, all); | |
395 | return; | |
396 | } | |
397 | if (excl_start > bottom) GC_push_conditional(bottom, excl_start, all); | |
398 | bottom = next -> e_end; | |
399 | } | |
400 | } | |
401 | ||
20bbd3cd TT |
402 | /* |
403 | * In the absence of threads, push the stack contents. | |
404 | * In the presence of threads, push enough of the current stack | |
405 | * to ensure that callee-save registers saved in collector frames have been | |
406 | * seen. | |
407 | */ | |
408 | void GC_push_current_stack(cold_gc_frame) | |
409 | ptr_t cold_gc_frame; | |
410 | { | |
411 | # if defined(THREADS) | |
412 | if (0 == cold_gc_frame) return; | |
413 | # ifdef STACK_GROWS_DOWN | |
414 | GC_push_all_eager(GC_approx_sp(), cold_gc_frame); | |
93002327 BM |
415 | /* For IA64, the register stack backing store is handled */ |
416 | /* in the thread-specific code. */ | |
20bbd3cd TT |
417 | # else |
418 | GC_push_all_eager( cold_gc_frame, GC_approx_sp() ); | |
419 | # endif | |
420 | # else | |
421 | # ifdef STACK_GROWS_DOWN | |
422 | GC_push_all_stack_partially_eager( GC_approx_sp(), GC_stackbottom, | |
423 | cold_gc_frame ); | |
424 | # ifdef IA64 | |
425 | /* We also need to push the register stack backing store. */ | |
426 | /* This should really be done in the same way as the */ | |
427 | /* regular stack. For now we fudge it a bit. */ | |
428 | /* Note that the backing store grows up, so we can't use */ | |
429 | /* GC_push_all_stack_partially_eager. */ | |
430 | { | |
431 | extern word GC_save_regs_ret_val; | |
432 | /* Previously set to backing store pointer. */ | |
433 | ptr_t bsp = (ptr_t) GC_save_regs_ret_val; | |
434 | ptr_t cold_gc_bs_pointer; | |
435 | # ifdef ALL_INTERIOR_POINTERS | |
436 | cold_gc_bs_pointer = bsp - 2048; | |
437 | if (cold_gc_bs_pointer < BACKING_STORE_BASE) { | |
438 | cold_gc_bs_pointer = BACKING_STORE_BASE; | |
439 | } | |
440 | GC_push_all(BACKING_STORE_BASE, cold_gc_bs_pointer); | |
441 | # else | |
442 | cold_gc_bs_pointer = BACKING_STORE_BASE; | |
443 | # endif | |
444 | GC_push_all_eager(cold_gc_bs_pointer, bsp); | |
445 | /* All values should be sufficiently aligned that we */ | |
446 | /* dont have to worry about the boundary. */ | |
447 | } | |
448 | # endif | |
449 | # else | |
450 | GC_push_all_stack_partially_eager( GC_stackbottom, GC_approx_sp(), | |
451 | cold_gc_frame ); | |
452 | # endif | |
453 | # endif /* !THREADS */ | |
454 | } | |
455 | ||
73ffefd0 TT |
456 | /* |
457 | * Call the mark routines (GC_tl_push for a single pointer, GC_push_conditional | |
458 | * on groups of pointers) on every top level accessible pointer. | |
459 | * If all is FALSE, arrange to push only possibly altered values. | |
20bbd3cd TT |
460 | * Cold_gc_frame is an address inside a GC frame that |
461 | * remains valid until all marking is complete. | |
462 | * A zero value indicates that it's OK to miss some | |
463 | * register values. | |
73ffefd0 | 464 | */ |
20bbd3cd | 465 | void GC_push_roots(all, cold_gc_frame) |
73ffefd0 | 466 | GC_bool all; |
20bbd3cd | 467 | ptr_t cold_gc_frame; |
73ffefd0 TT |
468 | { |
469 | register int i; | |
470 | ||
471 | /* | |
472 | * push registers - i.e., call GC_push_one(r) for each | |
473 | * register contents r. | |
474 | */ | |
20bbd3cd TT |
475 | # ifdef USE_GENERIC_PUSH_REGS |
476 | GC_generic_push_regs(cold_gc_frame); | |
477 | # else | |
73ffefd0 | 478 | GC_push_regs(); /* usually defined in machine_dep.c */ |
20bbd3cd | 479 | # endif |
73ffefd0 TT |
480 | |
481 | /* | |
482 | * Next push static data. This must happen early on, since it's | |
483 | * not robust against mark stack overflow. | |
484 | */ | |
485 | /* Reregister dynamic libraries, in case one got added. */ | |
486 | # if (defined(DYNAMIC_LOADING) || defined(MSWIN32) || defined(PCR)) \ | |
487 | && !defined(SRC_M3) | |
488 | GC_remove_tmp_roots(); | |
489 | GC_register_dynamic_libraries(); | |
490 | # endif | |
491 | /* Mark everything in static data areas */ | |
492 | for (i = 0; i < n_root_sets; i++) { | |
493 | GC_push_conditional_with_exclusions( | |
20bbd3cd TT |
494 | GC_static_roots[i].r_start, |
495 | GC_static_roots[i].r_end, all); | |
73ffefd0 TT |
496 | } |
497 | ||
498 | /* | |
499 | * Now traverse stacks. | |
500 | */ | |
20bbd3cd TT |
501 | # if !defined(USE_GENERIC_PUSH_REGS) |
502 | GC_push_current_stack(cold_gc_frame); | |
503 | /* IN the threads case, this only pushes collector frames. */ | |
504 | /* In the USE_GENERIC_PUSH_REGS case, this is done inside */ | |
505 | /* GC_push_regs, so that we catch callee-save registers saved */ | |
506 | /* inside the GC_push_regs frame. */ | |
93002327 BM |
507 | /* In the case of linux threads on Ia64, the hot section of */ |
508 | /* the main stack is marked here, but the register stack */ | |
509 | /* backing store is handled in the threads-specific code. */ | |
73ffefd0 TT |
510 | # endif |
511 | if (GC_push_other_roots != 0) (*GC_push_other_roots)(); | |
512 | /* In the threads case, this also pushes thread stacks. */ | |
513 | } | |
514 |