Mercurial > emacs
comparison gc/include/private/gc_pmark.h @ 51488:5de98dce4bd1
*** empty log message ***
author | Dave Love <fx@gnu.org> |
---|---|
date | Thu, 05 Jun 2003 17:49:22 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
51487:01d68b199093 | 51488:5de98dce4bd1 |
---|---|
1 /* | |
2 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. | |
3 * Copyright (c) 2001 by Hewlett-Packard Company. 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 */ | |
15 | |
16 /* Private declarations of GC marker data structures and macros */ | |
17 | |
18 /* | |
19 * Declarations of mark stack. Needed by marker and client supplied mark | |
20 * routines. Transitively include gc_priv.h. | |
21 * (Note that gc_priv.h should not be included before this, since this | |
22 * includes dbg_mlc.h, which wants to include gc_priv.h AFTER defining | |
23 * I_HIDE_POINTERS.) | |
24 */ | |
25 #ifndef GC_PMARK_H | |
26 # define GC_PMARK_H | |
27 | |
28 # if defined(KEEP_BACK_PTRS) || defined(PRINT_BLACK_LIST) | |
29 # include "dbg_mlc.h" | |
30 # endif | |
31 # ifndef GC_MARK_H | |
32 # include "../gc_mark.h" | |
33 # endif | |
34 # ifndef GC_PRIVATE_H | |
35 # include "gc_priv.h" | |
36 # endif | |
37 | |
38 /* The real declarations of the following is in gc_priv.h, so that */ | |
39 /* we can avoid scanning the following table. */ | |
40 /* | |
41 extern mark_proc GC_mark_procs[MAX_MARK_PROCS]; | |
42 */ | |
43 | |
44 /* | |
45 * Mark descriptor stuff that should remain private for now, mostly | |
46 * because it's hard to export WORDSZ without including gcconfig.h. | |
47 */ | |
48 # define BITMAP_BITS (WORDSZ - GC_DS_TAG_BITS) | |
49 # define PROC(descr) \ | |
50 (GC_mark_procs[((descr) >> GC_DS_TAG_BITS) & (GC_MAX_MARK_PROCS-1)]) | |
51 # define ENV(descr) \ | |
52 ((descr) >> (GC_DS_TAG_BITS + GC_LOG_MAX_MARK_PROCS)) | |
53 # define MAX_ENV \ | |
54 (((word)1 << (WORDSZ - GC_DS_TAG_BITS - GC_LOG_MAX_MARK_PROCS)) - 1) | |
55 | |
56 | |
57 extern word GC_n_mark_procs; | |
58 | |
59 /* Number of mark stack entries to discard on overflow. */ | |
60 #define GC_MARK_STACK_DISCARDS (INITIAL_MARK_STACK_SIZE/8) | |
61 | |
62 typedef struct GC_ms_entry { | |
63 GC_word * mse_start; /* First word of object */ | |
64 GC_word mse_descr; /* Descriptor; low order two bits are tags, */ | |
65 /* identifying the upper 30 bits as one of the */ | |
66 /* following: */ | |
67 } mse; | |
68 | |
69 extern word GC_mark_stack_size; | |
70 | |
71 extern mse * GC_mark_stack_limit; | |
72 | |
73 #ifdef PARALLEL_MARK | |
74 extern mse * VOLATILE GC_mark_stack_top; | |
75 #else | |
76 extern mse * GC_mark_stack_top; | |
77 #endif | |
78 | |
79 extern mse * GC_mark_stack; | |
80 | |
81 #ifdef PARALLEL_MARK | |
82 /* | |
83 * Allow multiple threads to participate in the marking process. | |
84 * This works roughly as follows: | |
85 * The main mark stack never shrinks, but it can grow. | |
86 * | |
87 * The initiating threads holds the GC lock, and sets GC_help_wanted. | |
88 * | |
89 * Other threads: | |
90 * 1) update helper_count (while holding mark_lock.) | |
91 * 2) allocate a local mark stack | |
92 * repeatedly: | |
93 * 3) Steal a global mark stack entry by atomically replacing | |
94 * its descriptor with 0. | |
95 * 4) Copy it to the local stack. | |
96 * 5) Mark on the local stack until it is empty, or | |
97 * it may be profitable to copy it back. | |
98 * 6) If necessary, copy local stack to global one, | |
99 * holding mark lock. | |
100 * 7) Stop when the global mark stack is empty. | |
101 * 8) decrement helper_count (holding mark_lock). | |
102 * | |
103 * This is an experiment to see if we can do something along the lines | |
104 * of the University of Tokyo SGC in a less intrusive, though probably | |
105 * also less performant, way. | |
106 */ | |
107 void GC_do_parallel_mark(); | |
108 /* inititate parallel marking. */ | |
109 | |
110 extern GC_bool GC_help_wanted; /* Protected by mark lock */ | |
111 extern unsigned GC_helper_count; /* Number of running helpers. */ | |
112 /* Protected by mark lock */ | |
113 extern unsigned GC_active_count; /* Number of active helpers. */ | |
114 /* Protected by mark lock */ | |
115 /* May increase and decrease */ | |
116 /* within each mark cycle. But */ | |
117 /* once it returns to 0, it */ | |
118 /* stays zero for the cycle. */ | |
119 /* GC_mark_stack_top is also protected by mark lock. */ | |
120 extern mse * VOLATILE GC_first_nonempty; | |
121 /* Lowest entry on mark stack */ | |
122 /* that may be nonempty. */ | |
123 /* Updated only by initiating */ | |
124 /* thread. */ | |
125 /* | |
126 * GC_notify_all_marker() is used when GC_help_wanted is first set, | |
127 * when the last helper becomes inactive, | |
128 * when something is added to the global mark stack, and just after | |
129 * GC_mark_no is incremented. | |
130 * This could be split into multiple CVs (and probably should be to | |
131 * scale to really large numbers of processors.) | |
132 */ | |
133 #endif /* PARALLEL_MARK */ | |
134 | |
135 /* Return a pointer to within 1st page of object. */ | |
136 /* Set *new_hdr_p to corr. hdr. */ | |
137 #ifdef __STDC__ | |
138 # ifdef PRINT_BLACK_LIST | |
139 ptr_t GC_find_start(ptr_t current, hdr *hhdr, hdr **new_hdr_p, | |
140 word source); | |
141 # else | |
142 ptr_t GC_find_start(ptr_t current, hdr *hhdr, hdr **new_hdr_p); | |
143 # endif | |
144 #else | |
145 ptr_t GC_find_start(); | |
146 #endif | |
147 | |
148 mse * GC_signal_mark_stack_overflow GC_PROTO((mse *msp)); | |
149 | |
150 # ifdef GATHERSTATS | |
151 # define ADD_TO_ATOMIC(sz) GC_atomic_in_use += (sz) | |
152 # define ADD_TO_COMPOSITE(sz) GC_composite_in_use += (sz) | |
153 # else | |
154 # define ADD_TO_ATOMIC(sz) | |
155 # define ADD_TO_COMPOSITE(sz) | |
156 # endif | |
157 | |
158 /* Push the object obj with corresponding heap block header hhdr onto */ | |
159 /* the mark stack. */ | |
160 # define PUSH_OBJ(obj, hhdr, mark_stack_top, mark_stack_limit) \ | |
161 { \ | |
162 register word _descr = (hhdr) -> hb_descr; \ | |
163 \ | |
164 if (_descr == 0) { \ | |
165 ADD_TO_ATOMIC((hhdr) -> hb_sz); \ | |
166 } else { \ | |
167 ADD_TO_COMPOSITE((hhdr) -> hb_sz); \ | |
168 mark_stack_top++; \ | |
169 if (mark_stack_top >= mark_stack_limit) { \ | |
170 mark_stack_top = GC_signal_mark_stack_overflow(mark_stack_top); \ | |
171 } \ | |
172 mark_stack_top -> mse_start = (obj); \ | |
173 mark_stack_top -> mse_descr = _descr; \ | |
174 } \ | |
175 } | |
176 | |
177 /* Push the contents of current onto the mark stack if it is a valid */ | |
178 /* ptr to a currently unmarked object. Mark it. */ | |
179 /* If we assumed a standard-conforming compiler, we could probably */ | |
180 /* generate the exit_label transparently. */ | |
181 # define PUSH_CONTENTS(current, mark_stack_top, mark_stack_limit, \ | |
182 source, exit_label) \ | |
183 { \ | |
184 hdr * my_hhdr; \ | |
185 ptr_t my_current = current; \ | |
186 \ | |
187 GET_HDR(my_current, my_hhdr); \ | |
188 if (IS_FORWARDING_ADDR_OR_NIL(my_hhdr)) { \ | |
189 hdr * new_hdr = GC_invalid_header; \ | |
190 my_current = GC_find_start(my_current, my_hhdr, &new_hdr); \ | |
191 my_hhdr = new_hdr; \ | |
192 } \ | |
193 PUSH_CONTENTS_HDR(my_current, mark_stack_top, mark_stack_limit, \ | |
194 source, exit_label, my_hhdr); \ | |
195 exit_label: ; \ | |
196 } | |
197 | |
198 /* As above, but use header cache for header lookup. */ | |
199 # define HC_PUSH_CONTENTS(current, mark_stack_top, mark_stack_limit, \ | |
200 source, exit_label) \ | |
201 { \ | |
202 hdr * my_hhdr; \ | |
203 ptr_t my_current = current; \ | |
204 \ | |
205 HC_GET_HDR(my_current, my_hhdr, source); \ | |
206 PUSH_CONTENTS_HDR(my_current, mark_stack_top, mark_stack_limit, \ | |
207 source, exit_label, my_hhdr); \ | |
208 exit_label: ; \ | |
209 } | |
210 | |
211 /* Set mark bit, exit if it was already set. */ | |
212 | |
213 # ifdef USE_MARK_BYTES | |
214 /* Unlike the mark bit case, there is a race here, and we may set */ | |
215 /* the bit twice in the concurrent case. This can result in the */ | |
216 /* object being pushed twice. But that's only a performance issue. */ | |
217 # define SET_MARK_BIT_EXIT_IF_SET(hhdr,displ,exit_label) \ | |
218 { \ | |
219 register VOLATILE char * mark_byte_addr = \ | |
220 hhdr -> hb_marks + ((displ) >> 1); \ | |
221 register char mark_byte = *mark_byte_addr; \ | |
222 \ | |
223 if (mark_byte) goto exit_label; \ | |
224 *mark_byte_addr = 1; \ | |
225 } | |
226 # else | |
227 # define SET_MARK_BIT_EXIT_IF_SET(hhdr,displ,exit_label) \ | |
228 { \ | |
229 register word * mark_word_addr = hhdr -> hb_marks + divWORDSZ(displ); \ | |
230 \ | |
231 OR_WORD_EXIT_IF_SET(mark_word_addr, (word)1 << modWORDSZ(displ), \ | |
232 exit_label); \ | |
233 } | |
234 # endif /* USE_MARK_BYTES */ | |
235 | |
236 /* If the mark bit corresponding to current is not set, set it, and */ | |
237 /* push the contents of the object on the mark stack. For a small */ | |
238 /* object we assume that current is the (possibly interior) pointer */ | |
239 /* to the object. For large objects we assume that current points */ | |
240 /* to somewhere inside the first page of the object. If */ | |
241 /* GC_all_interior_pointers is set, it may have been previously */ | |
242 /* adjusted to make that true. */ | |
243 # define PUSH_CONTENTS_HDR(current, mark_stack_top, mark_stack_limit, \ | |
244 source, exit_label, hhdr) \ | |
245 { \ | |
246 int displ; /* Displacement in block; first bytes, then words */ \ | |
247 int map_entry; \ | |
248 \ | |
249 displ = HBLKDISPL(current); \ | |
250 map_entry = MAP_ENTRY((hhdr -> hb_map), displ); \ | |
251 displ = BYTES_TO_WORDS(displ); \ | |
252 if (map_entry > CPP_MAX_OFFSET) { \ | |
253 if (map_entry == OFFSET_TOO_BIG) { \ | |
254 map_entry = displ % (hhdr -> hb_sz); \ | |
255 displ -= map_entry; \ | |
256 if (displ + (hhdr -> hb_sz) > BYTES_TO_WORDS(HBLKSIZE)) { \ | |
257 GC_ADD_TO_BLACK_LIST_NORMAL((word)current, source); \ | |
258 goto exit_label; \ | |
259 } \ | |
260 } else { \ | |
261 GC_ADD_TO_BLACK_LIST_NORMAL((word)current, source); goto exit_label; \ | |
262 } \ | |
263 } else { \ | |
264 displ -= map_entry; \ | |
265 } \ | |
266 GC_ASSERT(displ >= 0 && displ < MARK_BITS_PER_HBLK); \ | |
267 SET_MARK_BIT_EXIT_IF_SET(hhdr, displ, exit_label); \ | |
268 GC_STORE_BACK_PTR((ptr_t)source, (ptr_t)HBLKPTR(current) \ | |
269 + WORDS_TO_BYTES(displ)); \ | |
270 PUSH_OBJ(((word *)(HBLKPTR(current)) + displ), hhdr, \ | |
271 mark_stack_top, mark_stack_limit) \ | |
272 } | |
273 | |
274 #if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS) | |
275 # define PUSH_ONE_CHECKED_STACK(p, source) \ | |
276 GC_mark_and_push_stack(p, (ptr_t)(source)) | |
277 #else | |
278 # define PUSH_ONE_CHECKED_STACK(p, source) \ | |
279 GC_mark_and_push_stack(p) | |
280 #endif | |
281 | |
282 /* | |
283 * Push a single value onto mark stack. Mark from the object pointed to by p. | |
284 * Invoke FIXUP_POINTER(p) before any further processing. | |
285 * P is considered valid even if it is an interior pointer. | |
286 * Previously marked objects are not pushed. Hence we make progress even | |
287 * if the mark stack overflows. | |
288 */ | |
289 | |
290 # if NEED_FIXUP_POINTER | |
291 /* Try both the raw version and the fixed up one. */ | |
292 # define GC_PUSH_ONE_STACK(p, source) \ | |
293 if ((ptr_t)(p) >= (ptr_t)GC_least_plausible_heap_addr \ | |
294 && (ptr_t)(p) < (ptr_t)GC_greatest_plausible_heap_addr) { \ | |
295 PUSH_ONE_CHECKED_STACK(p, source); \ | |
296 } \ | |
297 FIXUP_POINTER(p); \ | |
298 if ((ptr_t)(p) >= (ptr_t)GC_least_plausible_heap_addr \ | |
299 && (ptr_t)(p) < (ptr_t)GC_greatest_plausible_heap_addr) { \ | |
300 PUSH_ONE_CHECKED_STACK(p, source); \ | |
301 } | |
302 # else /* !NEED_FIXUP_POINTER */ | |
303 # define GC_PUSH_ONE_STACK(p, source) \ | |
304 if ((ptr_t)(p) >= (ptr_t)GC_least_plausible_heap_addr \ | |
305 && (ptr_t)(p) < (ptr_t)GC_greatest_plausible_heap_addr) { \ | |
306 PUSH_ONE_CHECKED_STACK(p, source); \ | |
307 } | |
308 # endif | |
309 | |
310 | |
311 /* | |
312 * As above, but interior pointer recognition as for | |
313 * normal for heap pointers. | |
314 */ | |
315 # define GC_PUSH_ONE_HEAP(p,source) \ | |
316 FIXUP_POINTER(p); \ | |
317 if ((ptr_t)(p) >= (ptr_t)GC_least_plausible_heap_addr \ | |
318 && (ptr_t)(p) < (ptr_t)GC_greatest_plausible_heap_addr) { \ | |
319 GC_mark_stack_top = GC_mark_and_push( \ | |
320 (GC_PTR)(p), GC_mark_stack_top, \ | |
321 GC_mark_stack_limit, (GC_PTR *)(source)); \ | |
322 } | |
323 | |
324 /* Mark starting at mark stack entry top (incl.) down to */ | |
325 /* mark stack entry bottom (incl.). Stop after performing */ | |
326 /* about one page worth of work. Return the new mark stack */ | |
327 /* top entry. */ | |
328 mse * GC_mark_from GC_PROTO((mse * top, mse * bottom, mse *limit)); | |
329 | |
330 #define MARK_FROM_MARK_STACK() \ | |
331 GC_mark_stack_top = GC_mark_from(GC_mark_stack_top, \ | |
332 GC_mark_stack, \ | |
333 GC_mark_stack + GC_mark_stack_size); | |
334 | |
335 /* | |
336 * Mark from one finalizable object using the specified | |
337 * mark proc. May not mark the object pointed to by | |
338 * real_ptr. That is the job of the caller, if appropriate | |
339 */ | |
340 # define GC_MARK_FO(real_ptr, mark_proc) \ | |
341 { \ | |
342 (*(mark_proc))(real_ptr); \ | |
343 while (!GC_mark_stack_empty()) MARK_FROM_MARK_STACK(); \ | |
344 if (GC_mark_state != MS_NONE) { \ | |
345 GC_set_mark_bit(real_ptr); \ | |
346 while (!GC_mark_some((ptr_t)0)) {} \ | |
347 } \ | |
348 } | |
349 | |
350 extern GC_bool GC_mark_stack_too_small; | |
351 /* We need a larger mark stack. May be */ | |
352 /* set by client supplied mark routines.*/ | |
353 | |
354 typedef int mark_state_t; /* Current state of marking, as follows:*/ | |
355 /* Used to remember where we are during */ | |
356 /* concurrent marking. */ | |
357 | |
358 /* We say something is dirty if it was */ | |
359 /* written since the last time we */ | |
360 /* retrieved dirty bits. We say it's */ | |
361 /* grungy if it was marked dirty in the */ | |
362 /* last set of bits we retrieved. */ | |
363 | |
364 /* Invariant I: all roots and marked */ | |
365 /* objects p are either dirty, or point */ | |
366 /* to objects q that are either marked */ | |
367 /* or a pointer to q appears in a range */ | |
368 /* on the mark stack. */ | |
369 | |
370 # define MS_NONE 0 /* No marking in progress. I holds. */ | |
371 /* Mark stack is empty. */ | |
372 | |
373 # define MS_PUSH_RESCUERS 1 /* Rescuing objects are currently */ | |
374 /* being pushed. I holds, except */ | |
375 /* that grungy roots may point to */ | |
376 /* unmarked objects, as may marked */ | |
377 /* grungy objects above scan_ptr. */ | |
378 | |
379 # define MS_PUSH_UNCOLLECTABLE 2 | |
380 /* I holds, except that marked */ | |
381 /* uncollectable objects above scan_ptr */ | |
382 /* may point to unmarked objects. */ | |
383 /* Roots may point to unmarked objects */ | |
384 | |
385 # define MS_ROOTS_PUSHED 3 /* I holds, mark stack may be nonempty */ | |
386 | |
387 # define MS_PARTIALLY_INVALID 4 /* I may not hold, e.g. because of M.S. */ | |
388 /* overflow. However marked heap */ | |
389 /* objects below scan_ptr point to */ | |
390 /* marked or stacked objects. */ | |
391 | |
392 # define MS_INVALID 5 /* I may not hold. */ | |
393 | |
394 extern mark_state_t GC_mark_state; | |
395 | |
396 #endif /* GC_PMARK_H */ | |
397 |