51
51
word GC_free_bytes[N_HBLK_FLS+1] = { 0 };
52
52
/* Number of free bytes on each list. */
54
/* Is bytes + the number of free bytes on lists n .. N_HBLK_FLS */
55
/* > GC_max_large_allocd_bytes? */
54
/* Return the largest n such that */
55
/* Is GC_large_allocd_bytes + the number of free bytes on lists */
56
/* n .. N_HBLK_FLS > GC_max_large_allocd_bytes. */
57
/* If there is no such n, return 0. */
59
static GC_bool GC_enough_large_bytes_left(bytes,n)
61
static int GC_enough_large_bytes_left(void)
64
for (i = N_HBLK_FLS; i >= n; --i) {
65
bytes += GC_free_bytes[i];
66
if (bytes > GC_max_large_allocd_bytes) return TRUE;
64
word bytes = GC_large_allocd_bytes;
66
GC_ASSERT(GC_max_large_allocd_bytes <= GC_heapsize);
67
for (n = N_HBLK_FLS; n >= 0; --n) {
68
bytes += GC_free_bytes[n];
69
if (bytes >= GC_max_large_allocd_bytes) return n;
71
74
# define INCR_FREE_BYTES(n, b) GC_free_bytes[n] += (b);
106
108
word total_free = 0;
111
113
for (i = 0; i <= N_HBLK_FLS; ++i) {
112
114
h = GC_hblkfreelist[i];
113
115
# ifdef USE_MUNMAP
114
if (0 != h) GC_printf1("Free list %ld:\n",
116
if (0 != h) GC_printf("Free list %ld:\n",
117
if (0 != h) GC_printf2("Free list %ld (Total size %ld):\n",
119
(unsigned long)GC_free_bytes[i]);
119
if (0 != h) GC_printf("Free list %lu (Total size %lu):\n",
120
i, (unsigned long)GC_free_bytes[i]);
123
124
sz = hhdr -> hb_sz;
124
GC_printf2("\t0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
125
GC_printf("\t%p size %lu ", h, (unsigned long)sz);
125
126
total_free += sz;
126
127
if (GC_is_black_listed(h, HBLKSIZE) != 0) {
127
GC_printf0("start black listed\n");
128
GC_printf("start black listed\n");
128
129
} else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
129
GC_printf0("partially black listed\n");
130
GC_printf("partially black listed\n");
131
GC_printf0("not black listed\n");
132
GC_printf("not black listed\n");
133
134
h = hhdr -> hb_next;
136
137
# ifndef USE_MUNMAP
137
138
if (total_free != GC_large_free_bytes) {
138
GC_printf1("GC_large_free_bytes = %lu (INCONSISTENT!!)\n",
139
(unsigned long) GC_large_free_bytes);
139
GC_printf("GC_large_free_bytes = %lu (INCONSISTENT!!)\n",
140
(unsigned long) GC_large_free_bytes);
142
GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
143
GC_printf("Total of %lu bytes on free list\n", (unsigned long)total_free);
145
146
/* Return the free list index on which the block described by the header */
146
147
/* appears, or -1 if it appears nowhere. */
147
int free_list_index_of(wanted)
148
int free_list_index_of(hdr *wanted)
192
192
divHBLKSZ(hhdr -> hb_sz));
193
193
int actual_index;
195
GC_printf1("\tfree block of size 0x%lx bytes",
196
(unsigned long)(hhdr -> hb_sz));
195
GC_printf("\tfree block of size 0x%lx bytes",
196
(unsigned long)(hhdr -> hb_sz));
197
197
if (IS_MAPPED(hhdr)) {
200
GC_printf0("(unmapped)\n");
200
GC_printf("(unmapped)\n");
202
202
actual_index = free_list_index_of(hhdr);
203
203
if (-1 == actual_index) {
204
GC_printf1("\t\tBlock not on free list %ld!!\n",
204
GC_printf("\t\tBlock not on free list %d!!\n",
206
206
} else if (correct_index != actual_index) {
207
GC_printf2("\t\tBlock on list %ld, should be on %ld!!\n",
208
actual_index, correct_index);
207
GC_printf("\t\tBlock on list %d, should be on %d!!\n",
208
actual_index, correct_index);
210
210
p += hhdr -> hb_sz;
212
GC_printf1("\tused for blocks of size 0x%lx bytes\n",
213
(unsigned long)WORDS_TO_BYTES(hhdr -> hb_sz));
212
GC_printf("\tused for blocks of size 0x%lx bytes\n",
213
(unsigned long)(hhdr -> hb_sz));
214
214
p += HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
222
222
/* Initialize hdr for a block containing the indicated size and */
223
223
/* kind of objects. */
224
224
/* Return FALSE on failure. */
225
static GC_bool setup_header(hhdr, sz, kind, flags)
227
word sz; /* object size in words */
225
static GC_bool setup_header(hdr * hhdr, struct hblk *block, size_t byte_sz,
226
int kind, unsigned flags)
233
/* Add description of valid object pointers */
234
if (!GC_add_map_entry(sz)) return(FALSE);
235
hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
237
231
/* Set size, kind and mark proc fields */
239
hhdr -> hb_obj_kind = kind;
240
hhdr -> hb_flags = flags;
232
hhdr -> hb_sz = byte_sz;
233
hhdr -> hb_obj_kind = (unsigned char)kind;
234
hhdr -> hb_flags = (unsigned char)flags;
235
hhdr -> hb_block = block;
241
236
descr = GC_obj_kinds[kind].ok_descriptor;
242
if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
237
if (GC_obj_kinds[kind].ok_relocate_descr) descr += byte_sz;
243
238
hhdr -> hb_descr = descr;
240
# ifdef MARK_BIT_PER_OBJ
241
/* Set hb_inv_sz as portably as possible. */
242
/* We set it to the smallest value such that sz * inv_sz > 2**32 */
243
/* This may be more precision than necessary. */
244
if (byte_sz > MAXOBJBYTES) {
245
hhdr -> hb_inv_sz = LARGE_INV_SZ;
249
# if CPP_WORDSZ == 64
250
inv_sz = ((word)1 << 32)/byte_sz;
251
if (((inv_sz*byte_sz) >> 32) == 0) ++inv_sz;
252
# else /* 32 bit words */
253
GC_ASSERT(byte_sz >= 4);
254
inv_sz = ((unsigned)1 << 31)/byte_sz;
256
while (inv_sz*byte_sz > byte_sz) ++inv_sz;
258
hhdr -> hb_inv_sz = inv_sz;
260
# else /* MARK_BIT_PER_GRANULE */
261
hhdr -> hb_large_block = (unsigned char)(byte_sz > MAXOBJBYTES);
262
granules = BYTES_TO_GRANULES(byte_sz);
263
if (EXPECT(!GC_add_map_entry(granules), FALSE)) {
264
/* Make it look like a valid block. */
265
hhdr -> hb_sz = HBLKSIZE;
266
hhdr -> hb_descr = 0;
267
hhdr -> hb_large_block = TRUE;
271
size_t index = (hhdr -> hb_large_block? 0 : granules);
272
hhdr -> hb_map = GC_obj_map[index];
274
# endif /* MARK_BIT_PER_GRANULE */
245
276
/* Clear mark bits */
246
277
GC_clear_hdr_marks(hhdr);
330
358
* Add hhdr to the appropriate free list.
331
359
* We maintain individual free lists sorted by address.
333
void GC_add_to_fl(h, hhdr)
361
void GC_add_to_fl(struct hblk *h, hdr *hhdr)
337
363
int index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
338
364
struct hblk *second = GC_hblkfreelist[index];
339
365
hdr * second_hdr;
340
# ifdef GC_ASSERTIONS
366
# if defined(GC_ASSERTIONS) && !defined(USE_MUNMAP)
341
367
struct hblk *next = (struct hblk *)((word)h + hhdr -> hb_sz);
342
368
hdr * nexthdr = HDR(next);
343
369
struct hblk *prev = GC_free_block_ending_at(h);
344
370
hdr * prevhdr = HDR(prev);
345
GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr) || !IS_MAPPED(nexthdr));
346
GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr) || !IS_MAPPED(prevhdr));
371
GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr)
372
|| (signed_word)GC_heapsize < 0);
373
/* In the last case, blocks may be too large to merge. */
374
GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr)
375
|| (signed_word)GC_heapsize < 0);
348
377
GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
349
378
GC_hblkfreelist[index] = h;
534
560
hhdr -> hb_sz = h_size;
535
561
GC_add_to_fl(h, hhdr);
536
GC_invalidate_map(nhdr);
562
nhdr -> hb_flags |= FREE_BLK;
539
struct hblk * GC_allochblk_nth();
566
GC_allochblk_nth(size_t sz/* bytes */, int kind, unsigned flags, int n,
542
570
* Allocate (and return pointer to) a heap block
543
* for objects of size sz words, searching the nth free list.
571
* for objects of size sz bytes, searching the nth free list.
545
573
* NOTE: We set obj_map field in header correctly.
546
574
* Caller is responsible for building an object freelist in block.
548
* Unlike older versions of the collectors, the client is responsible
549
* for clearing the block, if necessary.
576
* The client is responsible for clearing the block, if necessary.
552
GC_allochblk(sz, kind, flags)
555
unsigned flags; /* IGNORE_OFF_PAGE or 0 */
579
GC_allochblk(size_t sz, int kind, unsigned flags/* IGNORE_OFF_PAGE or 0 */)
557
word blocks = OBJ_SZ_TO_BLOCKS(sz);
558
int start_list = GC_hblk_fl_from_blocks(blocks);
560
for (i = start_list; i <= N_HBLK_FLS; ++i) {
561
struct hblk * result = GC_allochblk_nth(sz, kind, flags, i);
585
int split_limit; /* Highest index of free list whose blocks we */
588
GC_ASSERT((sz & (GRANULE_BYTES - 1)) == 0);
589
blocks = OBJ_SZ_TO_BLOCKS(sz);
590
if ((signed_word)(blocks * HBLKSIZE) < 0) {
593
start_list = GC_hblk_fl_from_blocks(blocks);
594
/* Try for an exact match first. */
595
result = GC_allochblk_nth(sz, kind, flags, start_list, FALSE);
596
if (0 != result) return result;
597
if (GC_use_entire_heap || GC_dont_gc
598
|| USED_HEAP_SIZE < GC_requested_heapsize
599
|| TRUE_INCREMENTAL || !GC_should_collect()) {
600
/* Should use more of the heap, even if it requires splitting. */
601
split_limit = N_HBLK_FLS;
604
/* avoid splitting, since that might require remapping */
607
if (GC_finalizer_bytes_freed > (GC_heapsize >> 4)) {
608
/* If we are deallocating lots of memory from */
609
/* finalizers, fail and collect sooner rather */
613
/* If we have enough large blocks left to cover any */
614
/* previous request for large blocks, we go ahead */
615
/* and split. Assuming a steady state, that should */
616
/* be safe. It means that we can use the full */
617
/* heap if we allocate only small objects. */
618
split_limit = GC_enough_large_bytes_left();
622
if (start_list < UNIQUE_THRESHOLD) {
623
/* No reason to try start_list again, since all blocks are exact */
627
for (i = start_list; i <= split_limit; ++i) {
628
struct hblk * result = GC_allochblk_nth(sz, kind, flags, i, TRUE);
629
if (0 != result) return result;
569
634
* The same, but with search restricted to nth free list.
635
* Flags is IGNORE_OFF_PAGE or zero.
636
* Unlike the above, sz is in bytes.
637
* The may_split flag indicates whether it's OK to split larger blocks.
572
GC_allochblk_nth(sz, kind, flags, n)
575
unsigned char flags; /* IGNORE_OFF_PAGE or 0 */
640
GC_allochblk_nth(size_t sz, int kind, unsigned flags, int n, GC_bool may_split)
578
register struct hblk *hbp;
579
register hdr * hhdr; /* Header corr. to hbp */
580
register struct hblk *thishbp;
581
register hdr * thishdr; /* Header corr. to hbp */
643
hdr * hhdr; /* Header corr. to hbp */
644
/* Initialized after loop if hbp !=0 */
645
/* Gcc uninitialized use warning is bogus. */
646
struct hblk *thishbp;
647
hdr * thishdr; /* Header corr. to hbp */
582
648
signed_word size_needed; /* number of bytes in requested objects */
583
649
signed_word size_avail; /* bytes available in this block */
590
656
GET_HDR(hbp, hhdr);
591
657
size_avail = hhdr->hb_sz;
592
658
if (size_avail < size_needed) continue;
593
if (size_avail != size_needed
594
&& !GC_use_entire_heap
596
&& USED_HEAP_SIZE >= GC_requested_heapsize
597
&& !TRUE_INCREMENTAL && GC_should_collect()) {
601
/* If we have enough large blocks left to cover any */
602
/* previous request for large blocks, we go ahead */
603
/* and split. Assuming a steady state, that should */
604
/* be safe. It means that we can use the full */
605
/* heap if we allocate only small objects. */
606
if (!GC_enough_large_bytes_left(GC_large_allocd_bytes, n)) {
609
/* If we are deallocating lots of memory from */
610
/* finalizers, fail and collect sooner rather */
612
if (WORDS_TO_BYTES(GC_finalizer_mem_freed)
613
> (GC_heapsize >> 4)) {
616
# endif /* !USE_MUNMAP */
618
/* If the next heap block is obviously better, go on. */
619
/* This prevents us from disassembling a single large block */
620
/* to get tiny blocks. */
659
if (size_avail != size_needed) {
622
660
signed_word next_size;
662
if (!may_split) continue;
663
/* If the next heap block is obviously better, go on. */
664
/* This prevents us from disassembling a single large block */
665
/* to get tiny blocks. */
624
666
thishbp = hhdr -> hb_next;
625
667
if (thishbp != 0) {
626
GET_HDR(thishbp, thishdr);
668
GET_HDR(thishbp, thishdr);
627
669
next_size = (signed_word)(thishdr -> hb_sz);
628
670
if (next_size < size_avail
629
&& next_size >= size_needed
630
&& !GC_is_black_listed(thishbp, (word)size_needed)) {
671
&& next_size >= size_needed
672
&& !GC_is_black_listed(thishbp, (word)size_needed)) {
799
846
/* Check for duplicate deallocation in the easy case */
800
847
if (HBLK_IS_FREE(hhdr)) {
801
GC_printf1("Duplicate large block deallocation of 0x%lx\n",
802
(unsigned long) hbp);
848
GC_printf("Duplicate large block deallocation of %p\n", hbp);
803
849
ABORT("Duplicate large block deallocation");
806
852
GC_ASSERT(IS_MAPPED(hhdr));
807
GC_invalidate_map(hhdr);
853
hhdr -> hb_flags |= FREE_BLK;
808
854
next = (struct hblk *)((word)hbp + size);
809
855
GET_HDR(next, nexthdr);
810
856
prev = GC_free_block_ending_at(hbp);
811
857
/* Coalesce with successor, if possible */
812
if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)) {
858
if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)
859
&& (signed_word)(hhdr -> hb_sz + nexthdr -> hb_sz) > 0
813
861
GC_remove_from_fl(nexthdr, FL_UNKNOWN);
814
862
hhdr -> hb_sz += nexthdr -> hb_sz;
815
863
GC_remove_header(next);