Debian Codegraph @

gc/allchblk.c

raw
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) 1998-1999 by Silicon Graphics. All rights reserved.
5 * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved.
6 *
7 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
8 * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
9 *
10 * Permission is hereby granted to use or copy this program
11 * for any purpose, provided the above notices are retained on all copies.
12 * Permission to modify the code and to distribute modified code is granted,
13 * provided the above notices are retained, and a notice that the code was
14 * modified is included with the above copyright notice.
15 */
16
17 #include "private/gc_priv.h"
18
19 #include <stdio.h>
20
21 #ifdef GC_USE_ENTIRE_HEAP
22 int GC_use_entire_heap = TRUE;
23 #else
24 int GC_use_entire_heap = FALSE;
25 #endif
26
27 /*
28 * Free heap blocks are kept on one of several free lists,
29 * depending on the size of the block. Each free list is doubly linked.
30 * Adjacent free blocks are coalesced.
31 */
32
33
34 # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
35 /* largest block we will allocate starting on a black */
36 /* listed block. Must be >= HBLKSIZE. */
37
38
39 # define UNIQUE_THRESHOLD 32
40 /* Sizes up to this many HBLKs each have their own free list */
41 # define HUGE_THRESHOLD 256
42 /* Sizes of at least this many heap blocks are mapped to a */
43 /* single free list. */
44 # define FL_COMPRESSION 8
45 /* In between sizes map this many distinct sizes to a single */
46 /* bin. */
47
48 # define N_HBLK_FLS ((HUGE_THRESHOLD - UNIQUE_THRESHOLD) / FL_COMPRESSION \
49 + UNIQUE_THRESHOLD)
50
51 #ifndef GC_GCJ_SUPPORT
52 STATIC
53 #endif
54 struct hblk * GC_hblkfreelist[N_HBLK_FLS+1] = { 0 };
55 /* List of completely empty heap blocks */
56 /* Linked through hb_next field of */
57 /* header structure associated with */
58 /* block. Remains externally visible */
59 /* as used by GNU GCJ currently. */
60
61 #ifndef GC_GCJ_SUPPORT
62 STATIC
63 #endif
64 word GC_free_bytes[N_HBLK_FLS+1] = { 0 };
65 /* Number of free bytes on each list. Remains visible to GCJ. */
66
67 /* Return the largest n such that the number of free bytes on lists */
68 /* n .. N_HBLK_FLS is greater or equal to GC_max_large_allocd_bytes */
69 /* minus GC_large_allocd_bytes. If there is no such n, return 0. */
70 GC_INLINE int GC_enough_large_bytes_left(void)
71 {
72 int n;
73 word bytes = GC_large_allocd_bytes;
74
75 GC_ASSERT(GC_max_large_allocd_bytes <= GC_heapsize);
76 for (n = N_HBLK_FLS; n >= 0; --n) {
77 bytes += GC_free_bytes[n];
78 if (bytes >= GC_max_large_allocd_bytes) return n;
79 }
80 return 0;
81 }
82
83 /* Map a number of blocks to the appropriate large block free list index. */
84 STATIC int GC_hblk_fl_from_blocks(word blocks_needed)
85 {
86 if (blocks_needed <= UNIQUE_THRESHOLD) return (int)blocks_needed;
87 if (blocks_needed >= HUGE_THRESHOLD) return N_HBLK_FLS;
88 return (int)(blocks_needed - UNIQUE_THRESHOLD)/FL_COMPRESSION
89 + UNIQUE_THRESHOLD;
90
91 }
92
93 # define PHDR(hhdr) HDR((hhdr) -> hb_prev)
94 # define NHDR(hhdr) HDR((hhdr) -> hb_next)
95
96 # ifdef USE_MUNMAP
97 # define IS_MAPPED(hhdr) (((hhdr) -> hb_flags & WAS_UNMAPPED) == 0)
98 # else
99 # define IS_MAPPED(hhdr) TRUE
100 # endif /* !USE_MUNMAP */
101
102 #if !defined(NO_DEBUGGING) || defined(GC_ASSERTIONS)
103 /* Should return the same value as GC_large_free_bytes. */
104 GC_INNER word GC_compute_large_free_bytes(void)
105 {
106 word total_free = 0;
107 unsigned i;
108
109 for (i = 0; i <= N_HBLK_FLS; ++i) {
110 struct hblk * h;
111 hdr * hhdr;
112
113 for (h = GC_hblkfreelist[i]; h != 0; h = hhdr->hb_next) {
114 hhdr = HDR(h);
115 total_free += hhdr->hb_sz;
116 }
117 }
118 return total_free;
119 }
120 #endif /* !NO_DEBUGGING || GC_ASSERTIONS */
121
122 # if !defined(NO_DEBUGGING)
123 void GC_print_hblkfreelist(void)
124 {
125 unsigned i;
126 word total;
127
128 for (i = 0; i <= N_HBLK_FLS; ++i) {
129 struct hblk * h = GC_hblkfreelist[i];
130
131 if (0 != h) GC_printf("Free list %u (total size %lu):\n",
132 i, (unsigned long)GC_free_bytes[i]);
133 while (h /* != NULL */) { /* CPPCHECK */
134 hdr * hhdr = HDR(h);
135
136 GC_printf("\t%p size %lu %s black listed\n",
137 (void *)h, (unsigned long) hhdr -> hb_sz,
138 GC_is_black_listed(h, HBLKSIZE) != 0 ? "start" :
139 GC_is_black_listed(h, hhdr -> hb_sz) != 0 ? "partially" :
140 "not");
141 h = hhdr -> hb_next;
142 }
143 }
144 GC_printf("GC_large_free_bytes: %lu\n",
145 (unsigned long)GC_large_free_bytes);
146
147 if ((total = GC_compute_large_free_bytes()) != GC_large_free_bytes)
148 GC_err_printf("GC_large_free_bytes INCONSISTENT!! Should be: %lu\n",
149 (unsigned long)total);
150 }
151
152 /* Return the free list index on which the block described by the header */
153 /* appears, or -1 if it appears nowhere. */
154 static int free_list_index_of(hdr *wanted)
155 {
156 int i;
157
158 for (i = 0; i <= N_HBLK_FLS; ++i) {
159 struct hblk * h;
160 hdr * hhdr;
161
162 for (h = GC_hblkfreelist[i]; h != 0; h = hhdr -> hb_next) {
163 hhdr = HDR(h);
164 if (hhdr == wanted) return i;
165 }
166 }
167 return -1;
168 }
169
170 GC_API void GC_CALL GC_dump_regions(void)
171 {
172 unsigned i;
173
174 for (i = 0; i < GC_n_heap_sects; ++i) {
175 ptr_t start = GC_heap_sects[i].hs_start;
176 size_t bytes = GC_heap_sects[i].hs_bytes;
177 ptr_t end = start + bytes;
178 ptr_t p;
179
180 /* Merge in contiguous sections. */
181 while (i+1 < GC_n_heap_sects && GC_heap_sects[i+1].hs_start == end) {
182 ++i;
183 end = GC_heap_sects[i].hs_start + GC_heap_sects[i].hs_bytes;
184 }
185 GC_printf("***Section from %p to %p\n", (void *)start, (void *)end);
186 for (p = start; (word)p < (word)end; ) {
187 hdr *hhdr = HDR(p);
188
189 if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
190 GC_printf("\t%p Missing header!!(%p)\n",
191 (void *)p, (void *)hhdr);
192 p += HBLKSIZE;
193 continue;
194 }
195 if (HBLK_IS_FREE(hhdr)) {
196 int correct_index = GC_hblk_fl_from_blocks(
197 divHBLKSZ(hhdr -> hb_sz));
198 int actual_index;
199
200 GC_printf("\t%p\tfree block of size 0x%lx bytes%s\n",
201 (void *)p, (unsigned long)(hhdr -> hb_sz),
202 IS_MAPPED(hhdr) ? "" : " (unmapped)");
203 actual_index = free_list_index_of(hhdr);
204 if (-1 == actual_index) {
205 GC_printf("\t\tBlock not on free list %d!!\n",
206 correct_index);
207 } else if (correct_index != actual_index) {
208 GC_printf("\t\tBlock on list %d, should be on %d!!\n",
209 actual_index, correct_index);
210 }
211 p += hhdr -> hb_sz;
212 } else {
213 GC_printf("\t%p\tused for blocks of size 0x%lx bytes\n",
214 (void *)p, (unsigned long)(hhdr -> hb_sz));
215 p += HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
216 }
217 }
218 }
219 }
220
221 # endif /* NO_DEBUGGING */
222
223 /* Initialize hdr for a block containing the indicated size and */
224 /* kind of objects. */
225 /* Return FALSE on failure. */
226 static GC_bool setup_header(hdr * hhdr, struct hblk *block, size_t byte_sz,
227 int kind, unsigned flags)
228 {
229 word descr;
230
231 # ifdef MARK_BIT_PER_GRANULE
232 if (byte_sz > MAXOBJBYTES)
233 flags |= LARGE_BLOCK;
234 # endif
235 # ifdef ENABLE_DISCLAIM
236 if (GC_obj_kinds[kind].ok_disclaim_proc)
237 flags |= HAS_DISCLAIM;
238 if (GC_obj_kinds[kind].ok_mark_unconditionally)
239 flags |= MARK_UNCONDITIONALLY;
240 # endif
241
242 /* Set size, kind and mark proc fields */
243 hhdr -> hb_sz = byte_sz;
244 hhdr -> hb_obj_kind = (unsigned char)kind;
245 hhdr -> hb_flags = (unsigned char)flags;
246 hhdr -> hb_block = block;
247 descr = GC_obj_kinds[kind].ok_descriptor;
248 if (GC_obj_kinds[kind].ok_relocate_descr) descr += byte_sz;
249 hhdr -> hb_descr = descr;
250
251 # ifdef MARK_BIT_PER_OBJ
252 /* Set hb_inv_sz as portably as possible. */
253 /* We set it to the smallest value such that sz * inv_sz >= 2**32 */
254 /* This may be more precision than necessary. */
255 if (byte_sz > MAXOBJBYTES) {
256 hhdr -> hb_inv_sz = LARGE_INV_SZ;
257 } else {
258 word inv_sz;
259
260 # if CPP_WORDSZ == 64
261 inv_sz = ((word)1 << 32)/byte_sz;
262 if (((inv_sz*byte_sz) >> 32) == 0) ++inv_sz;
263 # else /* 32 bit words */
264 GC_ASSERT(byte_sz >= 4);
265 inv_sz = ((unsigned)1 << 31)/byte_sz;
266 inv_sz *= 2;
267 while (inv_sz*byte_sz > byte_sz) ++inv_sz;
268 # endif
269 # ifdef INV_SZ_COMPUTATION_CHECK
270 GC_ASSERT(((1ULL << 32) + byte_sz - 1) / byte_sz == inv_sz);
271 # endif
272 hhdr -> hb_inv_sz = inv_sz;
273 }
274 # endif
275 # ifdef MARK_BIT_PER_GRANULE
276 {
277 size_t granules = BYTES_TO_GRANULES(byte_sz);
278
279 if (EXPECT(!GC_add_map_entry(granules), FALSE)) {
280 /* Make it look like a valid block. */
281 hhdr -> hb_sz = HBLKSIZE;
282 hhdr -> hb_descr = 0;
283 hhdr -> hb_flags |= LARGE_BLOCK;
284 hhdr -> hb_map = 0;
285 return FALSE;
286 }
287 hhdr -> hb_map = GC_obj_map[(hhdr -> hb_flags & LARGE_BLOCK) != 0 ?
288 0 : granules];
289 }
290 # endif /* MARK_BIT_PER_GRANULE */
291
292 /* Clear mark bits */
293 GC_clear_hdr_marks(hhdr);
294
295 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
296 return(TRUE);
297 }
298
299 /* Remove hhdr from the free list (it is assumed to specified by index). */
300 STATIC void GC_remove_from_fl_at(hdr *hhdr, int index)
301 {
302 GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
303 if (hhdr -> hb_prev == 0) {
304 GC_ASSERT(HDR(GC_hblkfreelist[index]) == hhdr);
305 GC_hblkfreelist[index] = hhdr -> hb_next;
306 } else {
307 hdr *phdr;
308 GET_HDR(hhdr -> hb_prev, phdr);
309 phdr -> hb_next = hhdr -> hb_next;
310 }
311 /* We always need index to maintain free counts. */
312 GC_ASSERT(GC_free_bytes[index] >= hhdr -> hb_sz);
313 GC_free_bytes[index] -= hhdr -> hb_sz;
314 if (0 != hhdr -> hb_next) {
315 hdr * nhdr;
316 GC_ASSERT(!IS_FORWARDING_ADDR_OR_NIL(NHDR(hhdr)));
317 GET_HDR(hhdr -> hb_next, nhdr);
318 nhdr -> hb_prev = hhdr -> hb_prev;
319 }
320 }
321
322 /* Remove hhdr from the appropriate free list (we assume it is on the */
323 /* size-appropriate free list). */
324 GC_INLINE void GC_remove_from_fl(hdr *hhdr)
325 {
326 GC_remove_from_fl_at(hhdr, GC_hblk_fl_from_blocks(divHBLKSZ(hhdr->hb_sz)));
327 }
328
329 /* Return a pointer to the block ending just before h, if any. */
330 static struct hblk * get_block_ending_at(struct hblk *h)
331 {
332 struct hblk * p = h - 1;
333 hdr * phdr;
334
335 GET_HDR(p, phdr);
336 while (0 != phdr && IS_FORWARDING_ADDR_OR_NIL(phdr)) {
337 p = FORWARDED_ADDR(p,phdr);
338 phdr = HDR(p);
339 }
340 if (0 != phdr) {
341 return p;
342 }
343 p = GC_prev_block(h - 1);
344 if (p) {
345 phdr = HDR(p);
346 if ((ptr_t)p + phdr -> hb_sz == (ptr_t)h) {
347 return p;
348 }
349 }
350 return NULL;
351 }
352
353 /* Return a pointer to the free block ending just before h, if any. */
354 STATIC struct hblk * GC_free_block_ending_at(struct hblk *h)
355 {
356 struct hblk * p = get_block_ending_at(h);
357
358 if (p /* != NULL */) { /* CPPCHECK */
359 hdr * phdr = HDR(p);
360
361 if (HBLK_IS_FREE(phdr)) {
362 return p;
363 }
364 }
365 return 0;
366 }
367
368 /* Add hhdr to the appropriate free list. */
369 /* We maintain individual free lists sorted by address. */
370 STATIC void GC_add_to_fl(struct hblk *h, hdr *hhdr)
371 {
372 int index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
373 struct hblk *second = GC_hblkfreelist[index];
374 # if defined(GC_ASSERTIONS) && !defined(USE_MUNMAP)
375 struct hblk *next = (struct hblk *)((word)h + hhdr -> hb_sz);
376 hdr * nexthdr = HDR(next);
377 struct hblk *prev = GC_free_block_ending_at(h);
378 hdr * prevhdr = HDR(prev);
379
380 GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr)
381 || (GC_heapsize & SIGNB) != 0);
382 /* In the last case, blocks may be too large to merge. */
383 GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr)
384 || (GC_heapsize & SIGNB) != 0);
385 # endif
386 GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
387 GC_hblkfreelist[index] = h;
388 GC_free_bytes[index] += hhdr -> hb_sz;
389 GC_ASSERT(GC_free_bytes[index] <= GC_large_free_bytes);
390 hhdr -> hb_next = second;
391 hhdr -> hb_prev = 0;
392 if (second /* != NULL */) { /* CPPCHECK */
393 hdr * second_hdr;
394
395 GET_HDR(second, second_hdr);
396 second_hdr -> hb_prev = h;
397 }
398 hhdr -> hb_flags |= FREE_BLK;
399 }
400
401 #ifdef USE_MUNMAP
402
403 # ifndef MUNMAP_THRESHOLD
404 # define MUNMAP_THRESHOLD 6
405 # endif
406
407 GC_INNER int GC_unmap_threshold = MUNMAP_THRESHOLD;
408
409 #ifdef COUNT_UNMAPPED_REGIONS
410 /* GC_unmap_old will avoid creating more than this many unmapped regions, */
411 /* but an unmapped region may be split again so exceeding the limit. */
412
413 /* Return the change in number of unmapped regions if the block h swaps */
414 /* from its current state of mapped/unmapped to the opposite state. */
415 static int calc_num_unmapped_regions_delta(struct hblk *h, hdr *hhdr)
416 {
417 struct hblk * prev = get_block_ending_at(h);
418 struct hblk * next;
419 GC_bool prev_unmapped = FALSE;
420 GC_bool next_unmapped = FALSE;
421
422 next = GC_next_block((struct hblk *)((ptr_t)h + hhdr->hb_sz), TRUE);
423 /* Ensure next is contiguous with h. */
424 if ((ptr_t)next != GC_unmap_end((ptr_t)h, (size_t)hhdr->hb_sz)) {
425 next = NULL;
426 }
427 if (prev != NULL) {
428 hdr * prevhdr = HDR(prev);
429 prev_unmapped = !IS_MAPPED(prevhdr);
430 }
431 if (next != NULL) {
432 hdr * nexthdr = HDR(next);
433 next_unmapped = !IS_MAPPED(nexthdr);
434 }
435
436 if (prev_unmapped && next_unmapped) {
437 /* If h unmapped, merge two unmapped regions into one. */
438 /* If h remapped, split one unmapped region into two. */
439 return IS_MAPPED(hhdr) ? -1 : 1;
440 }
441 if (!prev_unmapped && !next_unmapped) {
442 /* If h unmapped, create an isolated unmapped region. */
443 /* If h remapped, remove it. */
444 return IS_MAPPED(hhdr) ? 1 : -1;
445 }
446 /* If h unmapped, merge it with previous or next unmapped region. */
447 /* If h remapped, reduce either previous or next unmapped region. */
448 /* In either way, no change to the number of unmapped regions. */
449 return 0;
450 }
451 #endif /* COUNT_UNMAPPED_REGIONS */
452
453 /* Update GC_num_unmapped_regions assuming the block h changes */
454 /* from its current state of mapped/unmapped to the opposite state. */
455 GC_INLINE void GC_adjust_num_unmapped(struct hblk *h GC_ATTR_UNUSED,
456 hdr *hhdr GC_ATTR_UNUSED)
457 {
458 # ifdef COUNT_UNMAPPED_REGIONS
459 GC_num_unmapped_regions += calc_num_unmapped_regions_delta(h, hhdr);
460 # endif
461 }
462
463 /* Unmap blocks that haven't been recently touched. This is the only */
464 /* way blocks are ever unmapped. */
465 GC_INNER void GC_unmap_old(void)
466 {
467 int i;
468
469 if (GC_unmap_threshold == 0)
470 return; /* unmapping disabled */
471 # ifdef COUNT_UNMAPPED_REGIONS
472 /* Skip unmapping if we have already exceeded the soft limit. */
473 /* This forgoes any opportunities to merge unmapped regions though. */
474 if (GC_num_unmapped_regions >= GC_UNMAPPED_REGIONS_SOFT_LIMIT)
475 return;
476 # endif
477
478 for (i = 0; i <= N_HBLK_FLS; ++i) {
479 struct hblk * h;
480 hdr * hhdr;
481
482 for (h = GC_hblkfreelist[i]; 0 != h; h = hhdr -> hb_next) {
483 hhdr = HDR(h);
484 if (!IS_MAPPED(hhdr)) continue;
485
486 /* Check that the interval is larger than the threshold (the */
487 /* truncated counter value wrapping is handled correctly). */
488 if ((unsigned short)(GC_gc_no - hhdr->hb_last_reclaimed) >
489 (unsigned short)GC_unmap_threshold) {
490 # ifdef COUNT_UNMAPPED_REGIONS
491 /* Continue with unmapping the block only if it will not */
492 /* create too many unmapped regions, or if unmapping */
493 /* reduces the number of regions. */
494 int delta = calc_num_unmapped_regions_delta(h, hhdr);
495 signed_word regions = GC_num_unmapped_regions + delta;
496
497 if (delta >= 0 && regions >= GC_UNMAPPED_REGIONS_SOFT_LIMIT) {
498 GC_COND_LOG_PRINTF("Unmapped regions limit reached!\n");
499 return;
500 }
501 GC_num_unmapped_regions = regions;
502 # endif
503 GC_unmap((ptr_t)h, (size_t)hhdr->hb_sz);
504 hhdr -> hb_flags |= WAS_UNMAPPED;
505 }
506 }
507 }
508 }
509
510 /* Merge all unmapped blocks that are adjacent to other free */
511 /* blocks. This may involve remapping, since all blocks are either */
512 /* fully mapped or fully unmapped. */
513 GC_INNER void GC_merge_unmapped(void)
514 {
515 int i;
516
517 for (i = 0; i <= N_HBLK_FLS; ++i) {
518 struct hblk *h = GC_hblkfreelist[i];
519
520 while (h != 0) {
521 struct hblk *next;
522 hdr *hhdr, *nexthdr;
523 word size, nextsize;
524
525 GET_HDR(h, hhdr);
526 size = hhdr->hb_sz;
527 next = (struct hblk *)((word)h + size);
528 GET_HDR(next, nexthdr);
529 /* Coalesce with successor, if possible */
530 if (0 != nexthdr && HBLK_IS_FREE(nexthdr)
531 && (signed_word) (size + (nextsize = nexthdr->hb_sz)) > 0
532 /* no pot. overflow */) {
533 /* Note that we usually try to avoid adjacent free blocks */
534 /* that are either both mapped or both unmapped. But that */
535 /* isn't guaranteed to hold since we remap blocks when we */
536 /* split them, and don't merge at that point. It may also */
537 /* not hold if the merged block would be too big. */
538 if (IS_MAPPED(hhdr) && !IS_MAPPED(nexthdr)) {
539 /* make both consistent, so that we can merge */
540 if (size > nextsize) {
541 GC_adjust_num_unmapped(next, nexthdr);
542 GC_remap((ptr_t)next, nextsize);
543 } else {
544 GC_adjust_num_unmapped(h, hhdr);
545 GC_unmap((ptr_t)h, size);
546 GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nextsize);
547 hhdr -> hb_flags |= WAS_UNMAPPED;
548 }
549 } else if (IS_MAPPED(nexthdr) && !IS_MAPPED(hhdr)) {
550 if (size > nextsize) {
551 GC_adjust_num_unmapped(next, nexthdr);
552 GC_unmap((ptr_t)next, nextsize);
553 GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nextsize);
554 } else {
555 GC_adjust_num_unmapped(h, hhdr);
556 GC_remap((ptr_t)h, size);
557 hhdr -> hb_flags &= ~WAS_UNMAPPED;
558 hhdr -> hb_last_reclaimed = nexthdr -> hb_last_reclaimed;
559 }
560 } else if (!IS_MAPPED(hhdr) && !IS_MAPPED(nexthdr)) {
561 /* Unmap any gap in the middle */
562 GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nextsize);
563 }
564 /* If they are both unmapped, we merge, but leave unmapped. */
565 GC_remove_from_fl_at(hhdr, i);
566 GC_remove_from_fl(nexthdr);
567 hhdr -> hb_sz += nexthdr -> hb_sz;
568 GC_remove_header(next);
569 GC_add_to_fl(h, hhdr);
570 /* Start over at beginning of list */
571 h = GC_hblkfreelist[i];
572 } else /* not mergeable with successor */ {
573 h = hhdr -> hb_next;
574 }
575 } /* while (h != 0) ... */
576 } /* for ... */
577 }
578
579 #endif /* USE_MUNMAP */
580
581 /*
582 * Return a pointer to a block starting at h of length bytes.
583 * Memory for the block is mapped.
584 * Remove the block from its free list, and return the remainder (if any)
585 * to its appropriate free list.
586 * May fail by returning 0.
587 * The header for the returned block must be set up by the caller.
588 * If the return value is not 0, then hhdr is the header for it.
589 */
590 STATIC struct hblk * GC_get_first_part(struct hblk *h, hdr *hhdr,
591 size_t bytes, int index)
592 {
593 word total_size = hhdr -> hb_sz;
594 struct hblk * rest;
595 hdr * rest_hdr;
596
597 GC_ASSERT((total_size & (HBLKSIZE-1)) == 0);
598 GC_remove_from_fl_at(hhdr, index);
599 if (total_size == bytes) return h;
600 rest = (struct hblk *)((word)h + bytes);
601 rest_hdr = GC_install_header(rest);
602 if (0 == rest_hdr) {
603 /* FIXME: This is likely to be very bad news ... */
604 WARN("Header allocation failed: dropping block\n", 0);
605 return(0);
606 }
607 rest_hdr -> hb_sz = total_size - bytes;
608 rest_hdr -> hb_flags = 0;
609 # ifdef GC_ASSERTIONS
610 /* Mark h not free, to avoid assertion about adjacent free blocks. */
611 hhdr -> hb_flags &= ~FREE_BLK;
612 # endif
613 GC_add_to_fl(rest, rest_hdr);
614 return h;
615 }
616
617 /*
618 * H is a free block. N points at an address inside it.
619 * A new header for n has already been set up. Fix up h's header
620 * to reflect the fact that it is being split, move it to the
621 * appropriate free list.
622 * N replaces h in the original free list.
623 *
624 * Nhdr is not completely filled in, since it is about to be allocated.
625 * It may in fact end up on the wrong free list for its size.
626 * That's not a disaster, since n is about to be allocated
627 * by our caller.
628 * (Hence adding it to a free list is silly. But this path is hopefully
629 * rare enough that it doesn't matter. The code is cleaner this way.)
630 */
631 STATIC void GC_split_block(struct hblk *h, hdr *hhdr, struct hblk *n,
632 hdr *nhdr, int index /* Index of free list */)
633 {
634 word total_size = hhdr -> hb_sz;
635 word h_size = (word)n - (word)h;
636 struct hblk *prev = hhdr -> hb_prev;
637 struct hblk *next = hhdr -> hb_next;
638
639 /* Replace h with n on its freelist */
640 nhdr -> hb_prev = prev;
641 nhdr -> hb_next = next;
642 nhdr -> hb_sz = total_size - h_size;
643 nhdr -> hb_flags = 0;
644 if (prev /* != NULL */) { /* CPPCHECK */
645 HDR(prev) -> hb_next = n;
646 } else {
647 GC_hblkfreelist[index] = n;
648 }
649 if (next /* != NULL */) {
650 HDR(next) -> hb_prev = n;
651 }
652 GC_ASSERT(GC_free_bytes[index] > h_size);
653 GC_free_bytes[index] -= h_size;
654 # ifdef USE_MUNMAP
655 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
656 # endif
657 hhdr -> hb_sz = h_size;
658 GC_add_to_fl(h, hhdr);
659 nhdr -> hb_flags |= FREE_BLK;
660 }
661
662 STATIC struct hblk *
663 GC_allochblk_nth(size_t sz /* bytes */, int kind, unsigned flags, int n,
664 int may_split);
665 #define AVOID_SPLIT_REMAPPED 2
666
667 /*
668 * Allocate (and return pointer to) a heap block
669 * for objects of size sz bytes, searching the nth free list.
670 *
671 * NOTE: We set obj_map field in header correctly.
672 * Caller is responsible for building an object freelist in block.
673 *
674 * The client is responsible for clearing the block, if necessary.
675 */
676 GC_INNER struct hblk *
677 GC_allochblk(size_t sz, int kind, unsigned flags/* IGNORE_OFF_PAGE or 0 */)
678 {
679 word blocks;
680 int start_list;
681 struct hblk *result;
682 int may_split;
683 int split_limit; /* Highest index of free list whose blocks we */
684 /* split. */
685
686 GC_ASSERT(I_HOLD_LOCK());
687 GC_ASSERT((sz & (GRANULE_BYTES - 1)) == 0);
688 blocks = OBJ_SZ_TO_BLOCKS_CHECKED(sz);
689 if ((signed_word)(blocks * HBLKSIZE) < 0) {
690 return 0;
691 }
692 start_list = GC_hblk_fl_from_blocks(blocks);
693 /* Try for an exact match first. */
694 result = GC_allochblk_nth(sz, kind, flags, start_list, FALSE);
695 if (0 != result) return result;
696
697 may_split = TRUE;
698 if (GC_use_entire_heap || GC_dont_gc
699 || USED_HEAP_SIZE < GC_requested_heapsize
700 || GC_incremental || !GC_should_collect()) {
701 /* Should use more of the heap, even if it requires splitting. */
702 split_limit = N_HBLK_FLS;
703 } else if (GC_finalizer_bytes_freed > (GC_heapsize >> 4)) {
704 /* If we are deallocating lots of memory from */
705 /* finalizers, fail and collect sooner rather */
706 /* than later. */
707 split_limit = 0;
708 } else {
709 /* If we have enough large blocks left to cover any */
710 /* previous request for large blocks, we go ahead */
711 /* and split. Assuming a steady state, that should */
712 /* be safe. It means that we can use the full */
713 /* heap if we allocate only small objects. */
714 split_limit = GC_enough_large_bytes_left();
715 # ifdef USE_MUNMAP
716 if (split_limit > 0)
717 may_split = AVOID_SPLIT_REMAPPED;
718 # endif
719 }
720 if (start_list < UNIQUE_THRESHOLD) {
721 /* No reason to try start_list again, since all blocks are exact */
722 /* matches. */
723 ++start_list;
724 }
725 for (; start_list <= split_limit; ++start_list) {
726 result = GC_allochblk_nth(sz, kind, flags, start_list, may_split);
727 if (0 != result)
728 break;
729 }
730 return result;
731 }
732
733 STATIC long GC_large_alloc_warn_suppressed = 0;
734 /* Number of warnings suppressed so far. */
735
736 /* The same, but with search restricted to nth free list. Flags is */
737 /* IGNORE_OFF_PAGE or zero. sz is in bytes. The may_split flag */
738 /* indicates whether it is OK to split larger blocks (if set to */
739 /* AVOID_SPLIT_REMAPPED then memory remapping followed by splitting */
740 /* should be generally avoided). */
741 STATIC struct hblk *
742 GC_allochblk_nth(size_t sz, int kind, unsigned flags, int n, int may_split)
743 {
744 struct hblk *hbp;
745 hdr * hhdr; /* Header corr. to hbp */
746 struct hblk *thishbp;
747 hdr * thishdr; /* Header corr. to thishbp */
748 signed_word size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS_CHECKED(sz);
749 /* number of bytes in requested objects */
750
751 /* search for a big enough block in free list */
752 for (hbp = GC_hblkfreelist[n];; hbp = hhdr -> hb_next) {
753 signed_word size_avail; /* bytes available in this block */
754
755 if (hbp /* != NULL */) {
756 /* CPPCHECK */
757 } else {
758 return NULL;
759 }
760 GET_HDR(hbp, hhdr); /* set hhdr value */
761 size_avail = (signed_word)hhdr->hb_sz;
762 if (size_avail < size_needed) continue;
763 if (size_avail != size_needed) {
764 if (!may_split) continue;
765 /* If the next heap block is obviously better, go on. */
766 /* This prevents us from disassembling a single large */
767 /* block to get tiny blocks. */
768 thishbp = hhdr -> hb_next;
769 if (thishbp /* != NULL */) { /* CPPCHECK */
770 signed_word next_size;
771
772 GET_HDR(thishbp, thishdr);
773 next_size = (signed_word)(thishdr -> hb_sz);
774 if (next_size < size_avail
775 && next_size >= size_needed
776 && !GC_is_black_listed(thishbp, (word)size_needed)) {
777 continue;
778 }
779 }
780 }
781 if (!IS_UNCOLLECTABLE(kind) && (kind != PTRFREE
782 || size_needed > (signed_word)MAX_BLACK_LIST_ALLOC)) {
783 struct hblk * lasthbp = hbp;
784 ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
785 signed_word orig_avail = size_avail;
786 signed_word eff_size_needed = (flags & IGNORE_OFF_PAGE) != 0 ?
787 (signed_word)HBLKSIZE
788 : size_needed;
789
790 while ((word)lasthbp <= (word)search_end
791 && (thishbp = GC_is_black_listed(lasthbp,
792 (word)eff_size_needed)) != 0) {
793 lasthbp = thishbp;
794 }
795 size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
796 thishbp = lasthbp;
797 if (size_avail >= size_needed) {
798 if (thishbp != hbp) {
799 # ifdef USE_MUNMAP
800 /* Avoid remapping followed by splitting. */
801 if (may_split == AVOID_SPLIT_REMAPPED && !IS_MAPPED(hhdr))
802 continue;
803 # endif
804 thishdr = GC_install_header(thishbp);
805 if (0 != thishdr) {
806 /* Make sure it's mapped before we mangle it. */
807 # ifdef USE_MUNMAP
808 if (!IS_MAPPED(hhdr)) {
809 GC_adjust_num_unmapped(hbp, hhdr);
810 GC_remap((ptr_t)hbp, (size_t)hhdr->hb_sz);
811 hhdr -> hb_flags &= ~WAS_UNMAPPED;
812 }
813 # endif
814 /* Split the block at thishbp */
815 GC_split_block(hbp, hhdr, thishbp, thishdr, n);
816 /* Advance to thishbp */
817 hbp = thishbp;
818 hhdr = thishdr;
819 /* We must now allocate thishbp, since it may */
820 /* be on the wrong free list. */
821 }
822 }
823 } else if (size_needed > (signed_word)BL_LIMIT
824 && orig_avail - size_needed
825 > (signed_word)BL_LIMIT) {
826 /* Punt, since anything else risks unreasonable heap growth. */
827 if (++GC_large_alloc_warn_suppressed
828 >= GC_large_alloc_warn_interval) {
829 WARN("Repeated allocation of very large block "
830 "(appr. size %" WARN_PRIuPTR " KiB):\n"
831 "\tMay lead to memory leak and poor performance\n",
832 (word)size_needed >> 10);
833 GC_large_alloc_warn_suppressed = 0;
834 }
835 size_avail = orig_avail;
836 } else if (size_avail == 0
837 && size_needed == (signed_word)HBLKSIZE
838 && IS_MAPPED(hhdr)) {
839 if (!GC_find_leak) {
840 static unsigned count = 0;
841
842 /* The block is completely blacklisted. We need */
843 /* to drop some such blocks, since otherwise we spend */
844 /* all our time traversing them if pointer-free */
845 /* blocks are unpopular. */
846 /* A dropped block will be reconsidered at next GC. */
847 if ((++count & 3) == 0) {
848 /* Allocate and drop the block in small chunks, to */
849 /* maximize the chance that we will recover some */
850 /* later. */
851 word total_size = hhdr -> hb_sz;
852 struct hblk * limit = hbp + divHBLKSZ(total_size);
853 struct hblk * h;
854 struct hblk * prev = hhdr -> hb_prev;
855
856 GC_large_free_bytes -= total_size;
857 GC_bytes_dropped += total_size;
858 GC_remove_from_fl_at(hhdr, n);
859 for (h = hbp; (word)h < (word)limit; h++) {
860 if (h != hbp) {
861 hhdr = GC_install_header(h);
862 }
863 if (NULL != hhdr) {
864 (void)setup_header(hhdr, h, HBLKSIZE, PTRFREE, 0);
865 /* Can't fail. */
866 if (GC_debugging_started) {
867 BZERO(h, HBLKSIZE);
868 }
869 }
870 }
871 /* Restore hbp to point at free block */
872 hbp = prev;
873 if (0 == hbp) {
874 return GC_allochblk_nth(sz, kind, flags, n, may_split);
875 }
876 hhdr = HDR(hbp);
877 }
878 }
879 }
880 }
881 if( size_avail >= size_needed ) {
882 # ifdef USE_MUNMAP
883 if (!IS_MAPPED(hhdr)) {
884 GC_adjust_num_unmapped(hbp, hhdr);
885 GC_remap((ptr_t)hbp, (size_t)hhdr->hb_sz);
886 hhdr -> hb_flags &= ~WAS_UNMAPPED;
887 /* Note: This may leave adjacent, mapped free blocks. */
888 }
889 # endif
890 /* hbp may be on the wrong freelist; the parameter n */
891 /* is important. */
892 hbp = GC_get_first_part(hbp, hhdr, size_needed, n);
893 break;
894 }
895 }
896
897 if (0 == hbp) return 0;
898
899 /* Add it to map of valid blocks */
900 if (!GC_install_counts(hbp, (word)size_needed)) return(0);
901 /* This leaks memory under very rare conditions. */
902
903 /* Set up header */
904 if (!setup_header(hhdr, hbp, sz, kind, flags)) {
905 GC_remove_counts(hbp, (word)size_needed);
906 return(0); /* ditto */
907 }
908 # ifndef GC_DISABLE_INCREMENTAL
909 /* Notify virtual dirty bit implementation that we are about to */
910 /* write. Ensure that pointer-free objects are not protected */
911 /* if it is avoidable. This also ensures that newly allocated */
912 /* blocks are treated as dirty. Necessary since we don't */
913 /* protect free blocks. */
914 GC_ASSERT((size_needed & (HBLKSIZE-1)) == 0);
915 GC_remove_protection(hbp, divHBLKSZ(size_needed),
916 (hhdr -> hb_descr == 0) /* pointer-free */);
917 # endif
918 /* We just successfully allocated a block. Restart count of */
919 /* consecutive failures. */
920 GC_fail_count = 0;
921
922 GC_large_free_bytes -= size_needed;
923 GC_ASSERT(IS_MAPPED(hhdr));
924 return( hbp );
925 }
926
927 /*
928 * Free a heap block.
929 *
930 * Coalesce the block with its neighbors if possible.
931 *
932 * All mark words are assumed to be cleared.
933 */
934 GC_INNER void GC_freehblk(struct hblk *hbp)
935 {
936 struct hblk *next, *prev;
937 hdr *hhdr, *prevhdr, *nexthdr;
938 word size;
939
940 GET_HDR(hbp, hhdr);
941 size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr->hb_sz);
942 if ((size & SIGNB) != 0)
943 ABORT("Deallocating excessively large block. Too large an allocation?");
944 /* Probably possible if we try to allocate more than half the address */
945 /* space at once. If we don't catch it here, strange things happen */
946 /* later. */
947 GC_remove_counts(hbp, size);
948 hhdr->hb_sz = size;
949 # ifdef USE_MUNMAP
950 hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
951 # endif
952
953 /* Check for duplicate deallocation in the easy case */
954 if (HBLK_IS_FREE(hhdr)) {
955 ABORT_ARG1("Duplicate large block deallocation",
956 " of %p", (void *)hbp);
957 }
958
959 GC_ASSERT(IS_MAPPED(hhdr));
960 hhdr -> hb_flags |= FREE_BLK;
961 next = (struct hblk *)((ptr_t)hbp + size);
962 GET_HDR(next, nexthdr);
963 prev = GC_free_block_ending_at(hbp);
964 /* Coalesce with successor, if possible */
965 if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)
966 && (signed_word)(hhdr -> hb_sz + nexthdr -> hb_sz) > 0
967 /* no overflow */) {
968 GC_remove_from_fl(nexthdr);
969 hhdr -> hb_sz += nexthdr -> hb_sz;
970 GC_remove_header(next);
971 }
972 /* Coalesce with predecessor, if possible. */
973 if (prev /* != NULL */) { /* CPPCHECK */
974 prevhdr = HDR(prev);
975 if (IS_MAPPED(prevhdr)
976 && (signed_word)(hhdr -> hb_sz + prevhdr -> hb_sz) > 0) {
977 GC_remove_from_fl(prevhdr);
978 prevhdr -> hb_sz += hhdr -> hb_sz;
979 # ifdef USE_MUNMAP
980 prevhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
981 # endif
982 GC_remove_header(hbp);
983 hbp = prev;
984 hhdr = prevhdr;
985 }
986 }
987 /* FIXME: It is not clear we really always want to do these merges */
988 /* with USE_MUNMAP, since it updates ages and hence prevents */
989 /* unmapping. */
990
991 GC_large_free_bytes += size;
992 GC_add_to_fl(hbp, hhdr);
993 }