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.
6 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
7 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
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.
18 * 1. allocation of heap block headers
19 * 2. A map from addresses to heap block addresses to heap block headers
21 * Access speed is crucial. We implement an index structure based on a 2
25 # include "private/gc_priv.h"
27 bottom_index
* GC_all_bottom_indices
= 0;
28 /* Pointer to first (lowest addr) */
31 bottom_index
* GC_all_bottom_indices_end
= 0;
32 /* Pointer to last (highest addr) */
35 /* Non-macro version of header location routine */
36 hdr
* GC_find_header(ptr_t h
)
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
)
56 hdr
* GC_header_cache_miss(ptr_t p
, hdr_cache_entry
*hce
)
62 if (IS_FORWARDING_ADDR_OR_NIL(hhdr
)) {
63 if (GC_all_interior_pointers
) {
67 current
= (ptr_t
)HBLKPTR(current
);
69 current
= current
- HBLKSIZE
*(word
)hhdr
;
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
))
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 */
82 GC_ADD_TO_BLACK_LIST_NORMAL(p
, source
);
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. */
90 GC_ADD_TO_BLACK_LIST_NORMAL(p
, source
);
95 if (HBLK_IS_FREE(hhdr
)) {
96 GC_ADD_TO_BLACK_LIST_NORMAL(p
, source
);
99 hce
-> block_addr
= (word
)(p
) >> LOG_HBLKSIZE
;
100 hce
-> hce_hdr
= hhdr
;
106 /* Routines to dynamically allocate collector data structures that will */
107 /* never be freed. */
109 static ptr_t scratch_free_ptr
= 0;
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. */
114 ptr_t
GC_scratch_alloc(size_t bytes
)
116 register ptr_t result
= scratch_free_ptr
;
118 bytes
+= GRANULE_BYTES
-1;
119 bytes
&= ~(GRANULE_BYTES
-1);
120 scratch_free_ptr
+= bytes
;
121 if (scratch_free_ptr
<= GC_scratch_end_ptr
) {
125 word bytes_to_get
= MINHINCR
* HBLKSIZE
;
127 if (bytes_to_get
<= bytes
) {
128 /* Undo the damage, and get memory directly */
129 bytes_to_get
= bytes
;
131 bytes_to_get
+= GC_page_size
- 1;
132 bytes_to_get
&= ~(GC_page_size
- 1);
134 result
= (ptr_t
)GET_MEM(bytes_to_get
);
135 scratch_free_ptr
-= bytes
;
136 GC_scratch_last_end_ptr
= result
+ bytes
;
139 result
= (ptr_t
)GET_MEM(bytes_to_get
);
142 GC_printf("Out of memory - trying to allocate less\n");
143 scratch_free_ptr
-= bytes
;
144 bytes_to_get
= bytes
;
146 bytes_to_get
+= GC_page_size
- 1;
147 bytes_to_get
&= ~(GC_page_size
- 1);
149 return((ptr_t
)GET_MEM(bytes_to_get
));
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
));
158 static hdr
* hdr_free_list
= 0;
160 /* Return an uninitialized header */
161 static hdr
* alloc_hdr(void)
163 register hdr
* result
;
165 if (hdr_free_list
== 0) {
166 result
= (hdr
*) GC_scratch_alloc((word
)(sizeof(hdr
)));
168 result
= hdr_free_list
;
169 hdr_free_list
= (hdr
*) (result
-> hb_next
);
174 static void free_hdr(hdr
* hhdr
)
176 hhdr
-> hb_next
= (struct hblk
*) hdr_free_list
;
177 hdr_free_list
= hhdr
;
181 word GC_hdr_cache_hits
= 0;
182 word GC_hdr_cache_misses
= 0;
185 void GC_init_headers(void)
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
;
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
)
200 word hi
= (word
)(addr
) >> (LOG_BOTTOM_SZ
+ LOG_HBLKSIZE
);
203 bottom_index
** prev
;
207 word i
= TL_HASH(hi
);
210 old
= p
= GC_top_index
[i
];
211 while(p
!= GC_all_nils
) {
212 if (p
-> key
== hi
) return(TRUE
);
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
;
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
));
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
) {
233 prev
= &(p
-> asc_link
);
237 GC_all_bottom_indices_end
= r
;
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
)
253 if (!get_index((word
) h
)) return(0);
254 result
= alloc_hdr();
257 result
-> hb_last_reclaimed
= (unsigned short)GC_gc_no
;
262 /* Set up forwarding counts for block h of size sz */
263 GC_bool
GC_install_counts(struct hblk
*h
, size_t sz
/* bytes */)
268 for (hbp
= h
; (char *)hbp
< (char *)h
+ sz
; hbp
+= BOTTOM_SZ
) {
269 if (!get_index((word
) hbp
)) return(FALSE
);
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
));
279 /* Remove the header for block h */
280 void GC_remove_header(struct hblk
*h
)
289 /* Remove forwarding counts for h */
290 void GC_remove_counts(struct hblk
*h
, size_t sz
/* bytes */)
292 register struct hblk
* hbp
;
294 for (hbp
= h
+1; (char *)hbp
< (char *)h
+ sz
; hbp
+= 1) {
299 /* Apply fn to all allocated blocks */
301 void GC_apply_to_all_blocks(void (*fn
)(struct hblk
*h
, word client_data
),
305 bottom_index
* index_p
;
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
)
318 } else if (index_p
->index
[j
] == 0) {
321 j
-= (signed_word
)(index_p
->index
[j
]);
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
)
331 register bottom_index
* bi
;
332 register word j
= ((word
)h
>> LOG_HBLKSIZE
) & (BOTTOM_SZ
-1);
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
;
342 while (j
< BOTTOM_SZ
) {
343 hdr
* hhdr
= bi
-> index
[j
];
344 if (IS_FORWARDING_ADDR_OR_NIL(hhdr
)) {
347 if (!HBLK_IS_FREE(hhdr
)) {
348 return((struct hblk
*)
349 (((bi
-> key
<< LOG_BOTTOM_SZ
) + j
)
352 j
+= divHBLKSZ(hhdr
-> hb_sz
);
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
)
367 register bottom_index
* bi
;
368 register signed_word j
= ((word
)h
>> LOG_HBLKSIZE
) & (BOTTOM_SZ
-1);
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
;
379 hdr
* hhdr
= bi
-> index
[j
];
382 } else if (IS_FORWARDING_ADDR_OR_NIL(hhdr
)) {
383 j
-= (signed_word
)hhdr
;
385 return((struct hblk
*)
386 (((bi
-> key
<< LOG_BOTTOM_SZ
) + j
)
391 bi
= bi
-> desc_link
;