Mercurial > emacs
comparison gc/headers.c @ 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 1988, 1989 Hans-J. Boehm, Alan J. Demers | |
3 * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. | |
4 * Copyright (c) 1996 by Silicon Graphics. All rights reserved. | |
5 * | |
6 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED | |
7 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. | |
8 * | |
9 * Permission is hereby granted to use or copy this program | |
10 * for any purpose, provided the above notices are retained on all copies. | |
11 * Permission to modify the code and to distribute modified code is granted, | |
12 * provided the above notices are retained, and a notice that the code was | |
13 * modified is included with the above copyright notice. | |
14 */ | |
15 | |
16 /* | |
17 * This implements: | |
18 * 1. allocation of heap block headers | |
19 * 2. A map from addresses to heap block addresses to heap block headers | |
20 * | |
21 * Access speed is crucial. We implement an index structure based on a 2 | |
22 * level tree. | |
23 */ | |
24 | |
25 # include "private/gc_priv.h" | |
26 | |
27 bottom_index * GC_all_bottom_indices = 0; | |
28 /* Pointer to first (lowest addr) */ | |
29 /* bottom_index. */ | |
30 | |
31 bottom_index * GC_all_bottom_indices_end = 0; | |
32 /* Pointer to last (highest addr) */ | |
33 /* bottom_index. */ | |
34 | |
35 /* Non-macro version of header location routine */ | |
36 hdr * GC_find_header(h) | |
37 ptr_t h; | |
38 { | |
39 # ifdef HASH_TL | |
40 register hdr * result; | |
41 GET_HDR(h, result); | |
42 return(result); | |
43 # else | |
44 return(HDR_INNER(h)); | |
45 # endif | |
46 } | |
47 | |
48 /* Routines to dynamically allocate collector data structures that will */ | |
49 /* never be freed. */ | |
50 | |
51 static ptr_t scratch_free_ptr = 0; | |
52 | |
53 /* GC_scratch_last_end_ptr is end point of last obtained scratch area. */ | |
54 /* GC_scratch_end_ptr is end point of current scratch area. */ | |
55 | |
56 ptr_t GC_scratch_alloc(bytes) | |
57 register word bytes; | |
58 { | |
59 register ptr_t result = scratch_free_ptr; | |
60 | |
61 # ifdef ALIGN_DOUBLE | |
62 # define GRANULARITY (2 * sizeof(word)) | |
63 # else | |
64 # define GRANULARITY sizeof(word) | |
65 # endif | |
66 bytes += GRANULARITY-1; | |
67 bytes &= ~(GRANULARITY-1); | |
68 scratch_free_ptr += bytes; | |
69 if (scratch_free_ptr <= GC_scratch_end_ptr) { | |
70 return(result); | |
71 } | |
72 { | |
73 word bytes_to_get = MINHINCR * HBLKSIZE; | |
74 | |
75 if (bytes_to_get <= bytes) { | |
76 /* Undo the damage, and get memory directly */ | |
77 bytes_to_get = bytes; | |
78 # ifdef USE_MMAP | |
79 bytes_to_get += GC_page_size - 1; | |
80 bytes_to_get &= ~(GC_page_size - 1); | |
81 # endif | |
82 result = (ptr_t)GET_MEM(bytes_to_get); | |
83 scratch_free_ptr -= bytes; | |
84 GC_scratch_last_end_ptr = result + bytes; | |
85 return(result); | |
86 } | |
87 result = (ptr_t)GET_MEM(bytes_to_get); | |
88 if (result == 0) { | |
89 # ifdef PRINTSTATS | |
90 GC_printf0("Out of memory - trying to allocate less\n"); | |
91 # endif | |
92 scratch_free_ptr -= bytes; | |
93 bytes_to_get = bytes; | |
94 # ifdef USE_MMAP | |
95 bytes_to_get += GC_page_size - 1; | |
96 bytes_to_get &= ~(GC_page_size - 1); | |
97 # endif | |
98 return((ptr_t)GET_MEM(bytes_to_get)); | |
99 } | |
100 scratch_free_ptr = result; | |
101 GC_scratch_end_ptr = scratch_free_ptr + bytes_to_get; | |
102 GC_scratch_last_end_ptr = GC_scratch_end_ptr; | |
103 return(GC_scratch_alloc(bytes)); | |
104 } | |
105 } | |
106 | |
107 static hdr * hdr_free_list = 0; | |
108 | |
109 /* Return an uninitialized header */ | |
110 static hdr * alloc_hdr() | |
111 { | |
112 register hdr * result; | |
113 | |
114 if (hdr_free_list == 0) { | |
115 result = (hdr *) GC_scratch_alloc((word)(sizeof(hdr))); | |
116 } else { | |
117 result = hdr_free_list; | |
118 hdr_free_list = (hdr *) (result -> hb_next); | |
119 } | |
120 return(result); | |
121 } | |
122 | |
123 static void free_hdr(hhdr) | |
124 hdr * hhdr; | |
125 { | |
126 hhdr -> hb_next = (struct hblk *) hdr_free_list; | |
127 hdr_free_list = hhdr; | |
128 } | |
129 | |
130 hdr * GC_invalid_header; | |
131 | |
132 #ifdef USE_HDR_CACHE | |
133 word GC_hdr_cache_hits = 0; | |
134 word GC_hdr_cache_misses = 0; | |
135 #endif | |
136 | |
137 void GC_init_headers() | |
138 { | |
139 register unsigned i; | |
140 | |
141 GC_all_nils = (bottom_index *)GC_scratch_alloc((word)sizeof(bottom_index)); | |
142 BZERO(GC_all_nils, sizeof(bottom_index)); | |
143 for (i = 0; i < TOP_SZ; i++) { | |
144 GC_top_index[i] = GC_all_nils; | |
145 } | |
146 GC_invalid_header = alloc_hdr(); | |
147 GC_invalidate_map(GC_invalid_header); | |
148 } | |
149 | |
150 /* Make sure that there is a bottom level index block for address addr */ | |
151 /* Return FALSE on failure. */ | |
152 static GC_bool get_index(addr) | |
153 word addr; | |
154 { | |
155 word hi = (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); | |
156 bottom_index * r; | |
157 bottom_index * p; | |
158 bottom_index ** prev; | |
159 bottom_index *pi; | |
160 | |
161 # ifdef HASH_TL | |
162 unsigned i = TL_HASH(hi); | |
163 bottom_index * old; | |
164 | |
165 old = p = GC_top_index[i]; | |
166 while(p != GC_all_nils) { | |
167 if (p -> key == hi) return(TRUE); | |
168 p = p -> hash_link; | |
169 } | |
170 r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index))); | |
171 if (r == 0) return(FALSE); | |
172 BZERO(r, sizeof (bottom_index)); | |
173 r -> hash_link = old; | |
174 GC_top_index[i] = r; | |
175 # else | |
176 if (GC_top_index[hi] != GC_all_nils) return(TRUE); | |
177 r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index))); | |
178 if (r == 0) return(FALSE); | |
179 GC_top_index[hi] = r; | |
180 BZERO(r, sizeof (bottom_index)); | |
181 # endif | |
182 r -> key = hi; | |
183 /* Add it to the list of bottom indices */ | |
184 prev = &GC_all_bottom_indices; /* pointer to p */ | |
185 pi = 0; /* bottom_index preceding p */ | |
186 while ((p = *prev) != 0 && p -> key < hi) { | |
187 pi = p; | |
188 prev = &(p -> asc_link); | |
189 } | |
190 r -> desc_link = pi; | |
191 if (0 == p) { | |
192 GC_all_bottom_indices_end = r; | |
193 } else { | |
194 p -> desc_link = r; | |
195 } | |
196 r -> asc_link = p; | |
197 *prev = r; | |
198 return(TRUE); | |
199 } | |
200 | |
201 /* Install a header for block h. */ | |
202 /* The header is uninitialized. */ | |
203 /* Returns the header or 0 on failure. */ | |
204 struct hblkhdr * GC_install_header(h) | |
205 register struct hblk * h; | |
206 { | |
207 hdr * result; | |
208 | |
209 if (!get_index((word) h)) return(FALSE); | |
210 result = alloc_hdr(); | |
211 SET_HDR(h, result); | |
212 # ifdef USE_MUNMAP | |
213 result -> hb_last_reclaimed = GC_gc_no; | |
214 # endif | |
215 return(result); | |
216 } | |
217 | |
218 /* Set up forwarding counts for block h of size sz */ | |
219 GC_bool GC_install_counts(h, sz) | |
220 register struct hblk * h; | |
221 register word sz; /* bytes */ | |
222 { | |
223 register struct hblk * hbp; | |
224 register int i; | |
225 | |
226 for (hbp = h; (char *)hbp < (char *)h + sz; hbp += BOTTOM_SZ) { | |
227 if (!get_index((word) hbp)) return(FALSE); | |
228 } | |
229 if (!get_index((word)h + sz - 1)) return(FALSE); | |
230 for (hbp = h + 1; (char *)hbp < (char *)h + sz; hbp += 1) { | |
231 i = HBLK_PTR_DIFF(hbp, h); | |
232 SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i)); | |
233 } | |
234 return(TRUE); | |
235 } | |
236 | |
237 /* Remove the header for block h */ | |
238 void GC_remove_header(h) | |
239 register struct hblk * h; | |
240 { | |
241 hdr ** ha; | |
242 | |
243 GET_HDR_ADDR(h, ha); | |
244 free_hdr(*ha); | |
245 *ha = 0; | |
246 } | |
247 | |
248 /* Remove forwarding counts for h */ | |
249 void GC_remove_counts(h, sz) | |
250 register struct hblk * h; | |
251 register word sz; /* bytes */ | |
252 { | |
253 register struct hblk * hbp; | |
254 | |
255 for (hbp = h+1; (char *)hbp < (char *)h + sz; hbp += 1) { | |
256 SET_HDR(hbp, 0); | |
257 } | |
258 } | |
259 | |
260 /* Apply fn to all allocated blocks */ | |
261 /*VARARGS1*/ | |
262 void GC_apply_to_all_blocks(fn, client_data) | |
263 void (*fn) GC_PROTO((struct hblk *h, word client_data)); | |
264 word client_data; | |
265 { | |
266 register int j; | |
267 register bottom_index * index_p; | |
268 | |
269 for (index_p = GC_all_bottom_indices; index_p != 0; | |
270 index_p = index_p -> asc_link) { | |
271 for (j = BOTTOM_SZ-1; j >= 0;) { | |
272 if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) { | |
273 if (index_p->index[j]->hb_map != GC_invalid_map) { | |
274 (*fn)(((struct hblk *) | |
275 (((index_p->key << LOG_BOTTOM_SZ) + (word)j) | |
276 << LOG_HBLKSIZE)), | |
277 client_data); | |
278 } | |
279 j--; | |
280 } else if (index_p->index[j] == 0) { | |
281 j--; | |
282 } else { | |
283 j -= (word)(index_p->index[j]); | |
284 } | |
285 } | |
286 } | |
287 } | |
288 | |
289 /* Get the next valid block whose address is at least h */ | |
290 /* Return 0 if there is none. */ | |
291 struct hblk * GC_next_used_block(h) | |
292 struct hblk * h; | |
293 { | |
294 register bottom_index * bi; | |
295 register word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); | |
296 | |
297 GET_BI(h, bi); | |
298 if (bi == GC_all_nils) { | |
299 register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); | |
300 bi = GC_all_bottom_indices; | |
301 while (bi != 0 && bi -> key < hi) bi = bi -> asc_link; | |
302 j = 0; | |
303 } | |
304 while(bi != 0) { | |
305 while (j < BOTTOM_SZ) { | |
306 hdr * hhdr = bi -> index[j]; | |
307 if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { | |
308 j++; | |
309 } else { | |
310 if (hhdr->hb_map != GC_invalid_map) { | |
311 return((struct hblk *) | |
312 (((bi -> key << LOG_BOTTOM_SZ) + j) | |
313 << LOG_HBLKSIZE)); | |
314 } else { | |
315 j += divHBLKSZ(hhdr -> hb_sz); | |
316 } | |
317 } | |
318 } | |
319 j = 0; | |
320 bi = bi -> asc_link; | |
321 } | |
322 return(0); | |
323 } | |
324 | |
325 /* Get the last (highest address) block whose address is */ | |
326 /* at most h. Return 0 if there is none. */ | |
327 /* Unlike the above, this may return a free block. */ | |
328 struct hblk * GC_prev_block(h) | |
329 struct hblk * h; | |
330 { | |
331 register bottom_index * bi; | |
332 register signed_word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); | |
333 | |
334 GET_BI(h, bi); | |
335 if (bi == GC_all_nils) { | |
336 register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); | |
337 bi = GC_all_bottom_indices_end; | |
338 while (bi != 0 && bi -> key > hi) bi = bi -> desc_link; | |
339 j = BOTTOM_SZ - 1; | |
340 } | |
341 while(bi != 0) { | |
342 while (j >= 0) { | |
343 hdr * hhdr = bi -> index[j]; | |
344 if (0 == hhdr) { | |
345 --j; | |
346 } else if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { | |
347 j -= (signed_word)hhdr; | |
348 } else { | |
349 return((struct hblk *) | |
350 (((bi -> key << LOG_BOTTOM_SZ) + j) | |
351 << LOG_HBLKSIZE)); | |
352 } | |
353 } | |
354 j = BOTTOM_SZ - 1; | |
355 bi = bi -> desc_link; | |
356 } | |
357 return(0); | |
358 } |