]>
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 | * 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 "gc_priv.h" | |
26 | ||
27 | bottom_index * GC_all_bottom_indices = 0; | |
20bbd3cd TT |
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. */ | |
73ffefd0 TT |
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 | ptr_t GC_scratch_end_ptr = 0; | |
54 | ||
55 | ptr_t GC_scratch_last_end_ptr = 0; | |
56 | /* End point of last obtained scratch area */ | |
57 | ||
58 | ptr_t GC_scratch_alloc(bytes) | |
59 | register word bytes; | |
60 | { | |
61 | register ptr_t result = scratch_free_ptr; | |
73ffefd0 TT |
62 | |
63 | # ifdef ALIGN_DOUBLE | |
64 | # define GRANULARITY (2 * sizeof(word)) | |
65 | # else | |
66 | # define GRANULARITY sizeof(word) | |
67 | # endif | |
68 | bytes += GRANULARITY-1; | |
69 | bytes &= ~(GRANULARITY-1); | |
70 | scratch_free_ptr += bytes; | |
71 | if (scratch_free_ptr <= GC_scratch_end_ptr) { | |
72 | return(result); | |
73 | } | |
74 | { | |
75 | word bytes_to_get = MINHINCR * HBLKSIZE; | |
76 | ||
77 | if (bytes_to_get <= bytes) { | |
78 | /* Undo the damage, and get memory directly */ | |
79 | bytes_to_get = bytes; | |
80 | # ifdef USE_MMAP | |
81 | bytes_to_get += GC_page_size - 1; | |
82 | bytes_to_get &= ~(GC_page_size - 1); | |
83 | # endif | |
84 | result = (ptr_t)GET_MEM(bytes_to_get); | |
85 | scratch_free_ptr -= bytes; | |
86 | GC_scratch_last_end_ptr = result + bytes; | |
87 | return(result); | |
88 | } | |
89 | result = (ptr_t)GET_MEM(bytes_to_get); | |
90 | if (result == 0) { | |
91 | # ifdef PRINTSTATS | |
92 | GC_printf0("Out of memory - trying to allocate less\n"); | |
93 | # endif | |
94 | scratch_free_ptr -= bytes; | |
95 | bytes_to_get = bytes; | |
96 | # ifdef USE_MMAP | |
97 | bytes_to_get += GC_page_size - 1; | |
20bbd3cd | 98 | bytes_to_get &= ~(GC_page_size - 1); |
73ffefd0 TT |
99 | # endif |
100 | return((ptr_t)GET_MEM(bytes_to_get)); | |
101 | } | |
102 | scratch_free_ptr = result; | |
103 | GC_scratch_end_ptr = scratch_free_ptr + bytes_to_get; | |
104 | GC_scratch_last_end_ptr = GC_scratch_end_ptr; | |
105 | return(GC_scratch_alloc(bytes)); | |
106 | } | |
107 | } | |
108 | ||
109 | static hdr * hdr_free_list = 0; | |
110 | ||
111 | /* Return an uninitialized header */ | |
112 | static hdr * alloc_hdr() | |
113 | { | |
114 | register hdr * result; | |
115 | ||
116 | if (hdr_free_list == 0) { | |
117 | result = (hdr *) GC_scratch_alloc((word)(sizeof(hdr))); | |
118 | } else { | |
119 | result = hdr_free_list; | |
120 | hdr_free_list = (hdr *) (result -> hb_next); | |
121 | } | |
122 | return(result); | |
123 | } | |
124 | ||
125 | static void free_hdr(hhdr) | |
126 | hdr * hhdr; | |
127 | { | |
128 | hhdr -> hb_next = (struct hblk *) hdr_free_list; | |
129 | hdr_free_list = hhdr; | |
130 | } | |
131 | ||
132 | void GC_init_headers() | |
133 | { | |
20bbd3cd | 134 | register unsigned i; |
73ffefd0 TT |
135 | |
136 | GC_all_nils = (bottom_index *)GC_scratch_alloc((word)sizeof(bottom_index)); | |
137 | BZERO(GC_all_nils, sizeof(bottom_index)); | |
138 | for (i = 0; i < TOP_SZ; i++) { | |
139 | GC_top_index[i] = GC_all_nils; | |
140 | } | |
141 | } | |
142 | ||
143 | /* Make sure that there is a bottom level index block for address addr */ | |
144 | /* Return FALSE on failure. */ | |
145 | static GC_bool get_index(addr) | |
20bbd3cd | 146 | word addr; |
73ffefd0 | 147 | { |
20bbd3cd TT |
148 | word hi = (word)(addr) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); |
149 | bottom_index * r; | |
150 | bottom_index * p; | |
151 | bottom_index ** prev; | |
152 | bottom_index *pi; | |
153 | ||
73ffefd0 | 154 | # ifdef HASH_TL |
20bbd3cd TT |
155 | unsigned i = TL_HASH(hi); |
156 | bottom_index * old; | |
73ffefd0 TT |
157 | |
158 | old = p = GC_top_index[i]; | |
159 | while(p != GC_all_nils) { | |
160 | if (p -> key == hi) return(TRUE); | |
161 | p = p -> hash_link; | |
162 | } | |
163 | r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index))); | |
164 | if (r == 0) return(FALSE); | |
165 | BZERO(r, sizeof (bottom_index)); | |
166 | r -> hash_link = old; | |
167 | GC_top_index[i] = r; | |
168 | # else | |
169 | if (GC_top_index[hi] != GC_all_nils) return(TRUE); | |
170 | r = (bottom_index*)GC_scratch_alloc((word)(sizeof (bottom_index))); | |
171 | if (r == 0) return(FALSE); | |
172 | GC_top_index[hi] = r; | |
173 | BZERO(r, sizeof (bottom_index)); | |
20bbd3cd | 174 | # endif |
73ffefd0 TT |
175 | r -> key = hi; |
176 | /* Add it to the list of bottom indices */ | |
20bbd3cd TT |
177 | prev = &GC_all_bottom_indices; /* pointer to p */ |
178 | pi = 0; /* bottom_index preceding p */ | |
179 | while ((p = *prev) != 0 && p -> key < hi) { | |
180 | pi = p; | |
181 | prev = &(p -> asc_link); | |
182 | } | |
183 | r -> desc_link = pi; | |
184 | if (0 == p) { | |
185 | GC_all_bottom_indices_end = r; | |
186 | } else { | |
187 | p -> desc_link = r; | |
188 | } | |
73ffefd0 TT |
189 | r -> asc_link = p; |
190 | *prev = r; | |
191 | return(TRUE); | |
192 | } | |
193 | ||
194 | /* Install a header for block h. */ | |
195 | /* The header is uninitialized. */ | |
196 | /* Returns FALSE on failure. */ | |
197 | GC_bool GC_install_header(h) | |
198 | register struct hblk * h; | |
199 | { | |
200 | hdr * result; | |
201 | ||
202 | if (!get_index((word) h)) return(FALSE); | |
203 | result = alloc_hdr(); | |
204 | SET_HDR(h, result); | |
20bbd3cd TT |
205 | # ifdef USE_MUNMAP |
206 | result -> hb_last_reclaimed = GC_gc_no; | |
207 | # endif | |
73ffefd0 TT |
208 | return(result != 0); |
209 | } | |
210 | ||
211 | /* Set up forwarding counts for block h of size sz */ | |
212 | GC_bool GC_install_counts(h, sz) | |
213 | register struct hblk * h; | |
214 | register word sz; /* bytes */ | |
215 | { | |
216 | register struct hblk * hbp; | |
217 | register int i; | |
218 | ||
219 | for (hbp = h; (char *)hbp < (char *)h + sz; hbp += BOTTOM_SZ) { | |
220 | if (!get_index((word) hbp)) return(FALSE); | |
221 | } | |
222 | if (!get_index((word)h + sz - 1)) return(FALSE); | |
223 | for (hbp = h + 1; (char *)hbp < (char *)h + sz; hbp += 1) { | |
224 | i = HBLK_PTR_DIFF(hbp, h); | |
225 | SET_HDR(hbp, (hdr *)(i > MAX_JUMP? MAX_JUMP : i)); | |
226 | } | |
227 | return(TRUE); | |
228 | } | |
229 | ||
230 | /* Remove the header for block h */ | |
231 | void GC_remove_header(h) | |
232 | register struct hblk * h; | |
233 | { | |
234 | hdr ** ha; | |
235 | ||
236 | GET_HDR_ADDR(h, ha); | |
237 | free_hdr(*ha); | |
238 | *ha = 0; | |
239 | } | |
240 | ||
241 | /* Remove forwarding counts for h */ | |
242 | void GC_remove_counts(h, sz) | |
243 | register struct hblk * h; | |
244 | register word sz; /* bytes */ | |
245 | { | |
246 | register struct hblk * hbp; | |
247 | ||
248 | for (hbp = h+1; (char *)hbp < (char *)h + sz; hbp += 1) { | |
249 | SET_HDR(hbp, 0); | |
250 | } | |
251 | } | |
252 | ||
253 | /* Apply fn to all allocated blocks */ | |
254 | /*VARARGS1*/ | |
255 | void GC_apply_to_all_blocks(fn, client_data) | |
256 | void (*fn)(/* struct hblk *h, word client_data */); | |
257 | word client_data; | |
258 | { | |
259 | register int j; | |
260 | register bottom_index * index_p; | |
261 | ||
262 | for (index_p = GC_all_bottom_indices; index_p != 0; | |
263 | index_p = index_p -> asc_link) { | |
264 | for (j = BOTTOM_SZ-1; j >= 0;) { | |
265 | if (!IS_FORWARDING_ADDR_OR_NIL(index_p->index[j])) { | |
266 | if (index_p->index[j]->hb_map != GC_invalid_map) { | |
267 | (*fn)(((struct hblk *) | |
268 | (((index_p->key << LOG_BOTTOM_SZ) + (word)j) | |
269 | << LOG_HBLKSIZE)), | |
270 | client_data); | |
271 | } | |
272 | j--; | |
273 | } else if (index_p->index[j] == 0) { | |
274 | j--; | |
275 | } else { | |
276 | j -= (word)(index_p->index[j]); | |
277 | } | |
278 | } | |
279 | } | |
280 | } | |
281 | ||
282 | /* Get the next valid block whose address is at least h */ | |
283 | /* Return 0 if there is none. */ | |
20bbd3cd | 284 | struct hblk * GC_next_used_block(h) |
73ffefd0 TT |
285 | struct hblk * h; |
286 | { | |
287 | register bottom_index * bi; | |
288 | register word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); | |
289 | ||
290 | GET_BI(h, bi); | |
291 | if (bi == GC_all_nils) { | |
292 | register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); | |
293 | bi = GC_all_bottom_indices; | |
294 | while (bi != 0 && bi -> key < hi) bi = bi -> asc_link; | |
295 | j = 0; | |
296 | } | |
297 | while(bi != 0) { | |
298 | while (j < BOTTOM_SZ) { | |
20bbd3cd TT |
299 | hdr * hhdr = bi -> index[j]; |
300 | if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { | |
73ffefd0 TT |
301 | j++; |
302 | } else { | |
20bbd3cd | 303 | if (hhdr->hb_map != GC_invalid_map) { |
73ffefd0 TT |
304 | return((struct hblk *) |
305 | (((bi -> key << LOG_BOTTOM_SZ) + j) | |
306 | << LOG_HBLKSIZE)); | |
307 | } else { | |
20bbd3cd | 308 | j += divHBLKSZ(hhdr -> hb_sz); |
73ffefd0 TT |
309 | } |
310 | } | |
311 | } | |
312 | j = 0; | |
313 | bi = bi -> asc_link; | |
314 | } | |
315 | return(0); | |
316 | } | |
20bbd3cd TT |
317 | |
318 | /* Get the last (highest address) block whose address is */ | |
319 | /* at most h. Return 0 if there is none. */ | |
320 | /* Unlike the above, this may return a free block. */ | |
321 | struct hblk * GC_prev_block(h) | |
322 | struct hblk * h; | |
323 | { | |
324 | register bottom_index * bi; | |
325 | register signed_word j = ((word)h >> LOG_HBLKSIZE) & (BOTTOM_SZ-1); | |
326 | ||
327 | GET_BI(h, bi); | |
328 | if (bi == GC_all_nils) { | |
329 | register word hi = (word)h >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); | |
330 | bi = GC_all_bottom_indices_end; | |
331 | while (bi != 0 && bi -> key > hi) bi = bi -> desc_link; | |
332 | j = BOTTOM_SZ - 1; | |
333 | } | |
334 | while(bi != 0) { | |
335 | while (j >= 0) { | |
336 | hdr * hhdr = bi -> index[j]; | |
337 | if (0 == hhdr) { | |
338 | --j; | |
339 | } else if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) { | |
340 | j -= (signed_word)hhdr; | |
341 | } else { | |
342 | return((struct hblk *) | |
343 | (((bi -> key << LOG_BOTTOM_SZ) + j) | |
344 | << LOG_HBLKSIZE)); | |
345 | } | |
346 | } | |
347 | j = BOTTOM_SZ - 1; | |
348 | bi = bi -> desc_link; | |
349 | } | |
350 | return(0); | |
351 | } |