]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(ptr_t h) | |
37 | { | |
38 | # ifdef HASH_TL | |
39 | hdr * result; | |
40 | GET_HDR(h, result); | |
41 | return(result); | |
42 | # else | |
43 | return(HDR_INNER(h)); | |
44 | # endif | |
45 | } | |
46 | ||
47 | /* Handle a header cache miss. Returns a pointer to the */ | |
48 | /* header corresponding to p, if p can possibly be a valid */ | |
49 | /* object pointer, and 0 otherwise. */ | |
50 | /* GUARANTEED to return 0 for a pointer past the first page */ | |
51 | /* of an object unless both GC_all_interior_pointers is set */ | |
52 | /* and p is in fact a valid object pointer. */ | |
53 | #ifdef PRINT_BLACK_LIST | |
54 | hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce, ptr_t source) | |
55 | #else | |
56 | hdr * GC_header_cache_miss(ptr_t p, hdr_cache_entry *hce) | |
57 | #endif | |
58 | { | |
59 | hdr *hhdr; | |
60 | HC_MISS(); | |
61 | GET_HDR(p, hhdr); | |
62 | if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { | |
63 | if (GC_all_interior_pointers) { | |
64 | if (hhdr != 0) { | |
65 | ptr_t current = p; | |
66 | ||
67 | current = (ptr_t)HBLKPTR(current); | |
68 | do { | |
69 | current = current - HBLKSIZE*(word)hhdr; | |
70 | hhdr = HDR(current); | |
71 | } while(IS_FORWARDING_ADDR_OR_NIL(hhdr)); | |
72 | /* current points to near the start of the large object */ | |
73 | if (hhdr -> hb_flags & IGNORE_OFF_PAGE | |
74 | || HBLK_IS_FREE(hhdr)) | |
75 | return 0; | |
76 | if (p - current >= (ptrdiff_t)(hhdr->hb_sz)) { | |
77 | GC_ADD_TO_BLACK_LIST_NORMAL(p, source); | |
78 | /* Pointer past the end of the block */ | |
79 | return 0; | |
80 | } | |
81 | } else { | |
82 | GC_ADD_TO_BLACK_LIST_NORMAL(p, source); | |
83 | } | |
84 | return hhdr; | |
85 | /* Pointers past the first page are probably too rare */ | |
86 | /* to add them to the cache. We don't. */ | |
87 | /* And correctness relies on the fact that we don't. */ | |
88 | } else { | |
89 | if (hhdr == 0) { | |
90 | GC_ADD_TO_BLACK_LIST_NORMAL(p, source); | |
91 | } | |
92 | return 0; | |
93 | } | |
94 | } else { | |
95 | if (HBLK_IS_FREE(hhdr)) { | |
96 | GC_ADD_TO_BLACK_LIST_NORMAL(p, source); | |
97 | return 0; | |
98 | } else { | |
99 | hce -> block_addr = (word)(p) >> LOG_HBLKSIZE; | |
100 | hce -> hce_hdr = hhdr; | |
101 | return hhdr; | |
102 | } | |
103 | } | |
104 | } | |
105 | ||
106 | /* Routines to dynamically allocate collector data structures that will */ | |
107 | /* never be freed. */ | |
108 | ||
109 | static ptr_t scratch_free_ptr = 0; | |
110 | ||
111 | /* GC_scratch_last_end_ptr is end point of last obtained scratch area. */ | |
112 | /* GC_scratch_end_ptr is end point of current scratch area. */ | |
113 | ||
114 | ptr_t GC_scratch_alloc(size_t bytes) | |
115 | { | |
116 | register ptr_t result = scratch_free_ptr; | |
117 | ||
118 | bytes += GRANULE_BYTES-1; | |
119 | bytes &= ~(GRANULE_BYTES-1); | |
120 | scratch_free_ptr += bytes; | |
121 | if (scratch_free_ptr <= GC_scratch_end_ptr) { | |
122 | return(result); | |
123 | } | |
124 | { | |
125 | word bytes_to_get = MINHINCR * HBLKSIZE; | |
126 | ||
127 | if (bytes_to_get <= bytes) { | |
128 | /* Undo the damage, and get memory directly */ | |
129 | bytes_to_get = bytes; | |
130 | # ifdef USE_MMAP | |
131 | bytes_to_get += GC_page_size - 1; | |
132 | bytes_to_get &= ~(GC_page_size - 1); | |
133 | # endif | |
134 | result = (ptr_t)GET_MEM(bytes_to_get); | |
135 | scratch_free_ptr -= bytes; | |
136 | GC_scratch_last_end_ptr = result + bytes; | |
137 | return(result); | |
138 | } | |
139 | result = (ptr_t)GET_MEM(bytes_to_get); | |
140 | if (result == 0) { | |
141 | if (GC_print_stats) | |
142 | GC_printf("Out of memory - trying to allocate less\n"); | |
143 | scratch_free_ptr -= bytes; | |
144 | bytes_to_get = bytes; | |
145 | # ifdef USE_MMAP | |
146 | bytes_to_get += GC_page_size - 1; | |
147 | bytes_to_get &= ~(GC_page_size - 1); | |
148 | # endif | |
149 | return((ptr_t)GET_MEM(bytes_to_get)); | |
150 | } | |
151 | scratch_free_ptr = result; | |
152 | GC_scratch_end_ptr = scratch_free_ptr + bytes_to_get; | |
153 | GC_scratch_last_end_ptr = GC_scratch_end_ptr; | |
154 | return(GC_scratch_alloc(bytes)); | |
155 | } | |
156 | } | |
157 | ||
158 | static hdr * hdr_free_list = 0; | |
159 | ||
160 | /* Return an uninitialized header */ | |
161 | static hdr * alloc_hdr(void) | |
162 | { | |
163 | register hdr * result; | |
164 | ||
165 | if (hdr_free_list == 0) { | |
166 | result = (hdr *) GC_scratch_alloc((word)(sizeof(hdr))); | |
167 | } else { | |
168 | result = hdr_free_list; | |
169 | hdr_free_list = (hdr *) (result -> hb_next); | |
170 | } | |
171 | return(result); | |
172 | } | |
173 | ||
174 | static void free_hdr(hdr * hhdr) | |
175 | { | |
176 | hhdr -> hb_next = (struct hblk *) hdr_free_list; | |
177 | hdr_free_list = hhdr; | |
178 | } | |
179 | ||
180 | #ifdef USE_HDR_CACHE | |
181 | word GC_hdr_cache_hits = 0; | |
182 | word GC_hdr_cache_misses = 0; | |
183 | #endif | |
184 | ||
185 | void GC_init_headers(void) | |
186 | { | |
187 | register unsigned i; | |
188 | ||
189 | GC_all_nils = (bottom_index *)GC_scratch_alloc((word)sizeof(bottom_index)); | |
190 | BZERO(GC_all_nils, sizeof(bottom_index)); | |
191 | for (i = 0; i < TOP_SZ; i++) { | |
192 | GC_top_index[i] = GC_all_nils; | |
193 | } | |
194 | } | |
195 | ||
196 | /* Make sure that there is a bottom level index block for address addr */ | |
197 | /* Return FALSE on failure. */ | |
198 | static GC_bool get_index(word addr) | |
199 | { | |
200 | word hi = (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); | |
201 | bottom_index * r; | |
202 | bottom_index * p; | |
203 | bottom_index ** prev; | |
204 | bottom_index *pi; | |
205 | ||
206 | # ifdef HASH_TL | |
207 | word i = TL_HASH(hi); | |
208 | bottom_index * old; | |
209 | ||
210 | old = p = GC_top_index[i]; | |
211 | while(p != GC_all_nils) { | |
212 | if (p -> key == hi) return(TRUE); | |
213 | p = p -> hash_link; | |
214 | } | |
215 | r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index))); | |
216 | if (r == 0) return(FALSE); | |
217 | BZERO(r, sizeof (bottom_index)); | |
218 | r -> hash_link = old; | |
219 | GC_top_index[i] = r; | |
220 | # else | |
221 | if (GC_top_index[hi] != GC_all_nils) return(TRUE); | |
222 | r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index))); | |
223 | if (r == 0) return(FALSE); | |
224 | GC_top_index[hi] = r; | |
225 | BZERO(r, sizeof (bottom_index)); | |
226 | # endif | |
227 | r -> key = hi; | |
228 | /* Add it to the list of bottom indices */ | |
229 | prev = &GC_all_bottom_indices; /* pointer to p */ | |
230 | pi = 0; /* bottom_index preceding p */ | |
231 | while ((p = *prev) != 0 && p -> key < hi) { | |
232 | pi = p; | |
233 | prev = &(p -> asc_link); | |
234 | } | |
235 | r -> desc_link = pi; | |
236 | if (0 == p) { | |
237 | GC_all_bottom_indices_end = r; | |
238 | } else { | |
239 | p -> desc_link = r; | |
240 | } | |
241 | r -> asc_link = p; | |
242 | *prev = r; | |
243 | return(TRUE); | |
244 | } | |
245 | ||
246 | /* Install a header for block h. */ | |
247 | /* The header is uninitialized. */ | |
248 | /* Returns the header or 0 on failure. */ | |
249 | struct hblkhdr * GC_install_header(struct hblk *h) | |
250 | { | |
251 | hdr * result; | |
252 | ||
253 | if (!get_index((word) h)) return(0); | |
254 | result = alloc_hdr(); | |
255 | SET_HDR(h, result); | |
256 | # ifdef USE_MUNMAP | |
257 | result -> hb_last_reclaimed = (unsigned short)GC_gc_no; | |
258 | # endif | |
259 | return(result); | |
260 | } | |
261 | ||
262 | /* Set up forwarding counts for block h of size sz */ | |
263 | GC_bool GC_install_counts(struct hblk *h, size_t sz/* bytes */) | |
264 | { | |
265 | struct hblk * hbp; | |
266 | word i; | |
267 | ||
268 | for (hbp = h; (char *)hbp < (char *)h + sz; hbp += BOTTOM_SZ) { | |
269 | if (!get_index((word) hbp)) return(FALSE); | |
270 | } | |
271 | if (!get_index((word)h + sz - 1)) return(FALSE); | |
272 | for (hbp = h + 1; (char *)hbp < (char *)h + sz; hbp += 1) { | |
273 | i = HBLK_PTR_DIFF(hbp, h); | |
274 | SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i)); | |
275 | } | |
276 | return(TRUE); | |
277 | } | |
278 | ||
279 | /* Remove the header for block h */ | |
280 | void GC_remove_header(struct hblk *h) | |
281 | { | |
282 | hdr ** ha; | |
283 | ||
284 | GET_HDR_ADDR(h, ha); | |
285 | free_hdr(*ha); | |
286 | *ha = 0; | |
287 | } | |
288 | ||
289 | /* Remove forwarding counts for h */ | |
290 | void GC_remove_counts(struct hblk *h, size_t sz/* bytes */) | |
291 | { | |
292 | register struct hblk * hbp; | |
293 | ||
294 | for (hbp = h+1; (char *)hbp < (char *)h + sz; hbp += 1) { | |
295 | SET_HDR(hbp, 0); | |
296 | } | |
297 | } | |
298 | ||
299 | /* Apply fn to all allocated blocks */ | |
300 | /*VARARGS1*/ | |
301 | void GC_apply_to_all_blocks(void (*fn)(struct hblk *h, word client_data), | |
302 | word client_data) | |
303 | { | |
304 | signed_word j; | |
305 | bottom_index * index_p; | |
306 | ||
307 | for (index_p = GC_all_bottom_indices; index_p != 0; | |
308 | index_p = index_p -> asc_link) { | |
309 | for (j = BOTTOM_SZ-1; j >= 0;) { | |
310 | if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) { | |
311 | if (!HBLK_IS_FREE(index_p->index[j])) { | |
312 | (*fn)(((struct hblk *) | |
313 | (((index_p->key << LOG_BOTTOM_SZ) + (word)j) | |
314 | << LOG_HBLKSIZE)), | |
315 | client_data); | |
316 | } | |
317 | j--; | |
318 | } else if (index_p->index[j] == 0) { | |
319 | j--; | |
320 | } else { | |
321 | j -= (signed_word)(index_p->index[j]); | |
322 | } | |
323 | } | |
324 | } | |
325 | } | |
326 | ||
327 | /* Get the next valid block whose address is at least h */ | |
328 | /* Return 0 if there is none. */ | |
329 | struct hblk * GC_next_used_block(struct hblk *h) | |
330 | { | |
331 | register bottom_index * bi; | |
332 | register 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; | |
338 | while (bi != 0 && bi -> key < hi) bi = bi -> asc_link; | |
339 | j = 0; | |
340 | } | |
341 | while(bi != 0) { | |
342 | while (j < BOTTOM_SZ) { | |
343 | hdr * hhdr = bi -> index[j]; | |
344 | if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { | |
345 | j++; | |
346 | } else { | |
347 | if (!HBLK_IS_FREE(hhdr)) { | |
348 | return((struct hblk *) | |
349 | (((bi -> key << LOG_BOTTOM_SZ) + j) | |
350 | << LOG_HBLKSIZE)); | |
351 | } else { | |
352 | j += divHBLKSZ(hhdr -> hb_sz); | |
353 | } | |
354 | } | |
355 | } | |
356 | j = 0; | |
357 | bi = bi -> asc_link; | |
358 | } | |
359 | return(0); | |
360 | } | |
361 | ||
362 | /* Get the last (highest address) block whose address is */ | |
363 | /* at most h. Return 0 if there is none. */ | |
364 | /* Unlike the above, this may return a free block. */ | |
365 | struct hblk * GC_prev_block(struct hblk *h) | |
366 | { | |
367 | register bottom_index * bi; | |
368 | register signed_word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); | |
369 | ||
370 | GET_BI(h, bi); | |
371 | if (bi == GC_all_nils) { | |
372 | register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); | |
373 | bi = GC_all_bottom_indices_end; | |
374 | while (bi != 0 && bi -> key > hi) bi = bi -> desc_link; | |
375 | j = BOTTOM_SZ - 1; | |
376 | } | |
377 | while(bi != 0) { | |
378 | while (j >= 0) { | |
379 | hdr * hhdr = bi -> index[j]; | |
380 | if (0 == hhdr) { | |
381 | --j; | |
382 | } else if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { | |
383 | j -= (signed_word)hhdr; | |
384 | } else { | |
385 | return((struct hblk *) | |
386 | (((bi -> key << LOG_BOTTOM_SZ) + j) | |
387 | << LOG_HBLKSIZE)); | |
388 | } | |
389 | } | |
390 | j = BOTTOM_SZ - 1; | |
391 | bi = bi -> desc_link; | |
392 | } | |
393 | return(0); | |
394 | } |