[BACK]Return to allchblk.c CVS log [TXT][DIR] Up to [local] / OpenXM_contrib / gc

Annotation of OpenXM_contrib/gc/allchblk.c, Revision 1.1.1.3

1.1       maekawa     1: /*
                      2:  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
                      3:  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
1.1.1.2   maekawa     4:  * Copyright (c) 1998-1999 by Silicon Graphics.  All rights reserved.
                      5:  * Copyright (c) 1999 by Hewlett-Packard Company. All rights reserved.
1.1       maekawa     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: #define DEBUG
                     18: #undef DEBUG
                     19: #include <stdio.h>
                     20: #include "gc_priv.h"
                     21:
1.1.1.3 ! maekawa    22: GC_bool GC_use_entire_heap = 0;
1.1       maekawa    23:
                     24: /*
1.1.1.2   maekawa    25:  * Free heap blocks are kept on one of several free lists,
                     26:  * depending on the size of the block.  Each free list is doubly linked.
                     27:  * Adjacent free blocks are coalesced.
1.1       maekawa    28:  */
                     29:
                     30:
                     31: # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
                     32:                /* largest block we will allocate starting on a black   */
                     33:                /* listed block.  Must be >= HBLKSIZE.                  */
                     34:
                     35:
1.1.1.2   maekawa    36: # define UNIQUE_THRESHOLD 32
                     37:        /* Sizes up to this many HBLKs each have their own free list    */
                     38: # define HUGE_THRESHOLD 256
                     39:        /* Sizes of at least this many heap blocks are mapped to a      */
                     40:        /* single free list.                                            */
                     41: # define FL_COMPRESSION 8
                     42:        /* In between sizes map this many distinct sizes to a single    */
                     43:        /* bin.                                                         */
                     44:
                     45: # define N_HBLK_FLS (HUGE_THRESHOLD - UNIQUE_THRESHOLD)/FL_COMPRESSION \
                     46:                                 + UNIQUE_THRESHOLD
                     47:
                     48: struct hblk * GC_hblkfreelist[N_HBLK_FLS+1] = { 0 };
                     49:
                     50: /* Map a number of blocks to the appropriate large block free list index. */
                     51: int GC_hblk_fl_from_blocks(blocks_needed)
                     52: word blocks_needed;
                     53: {
                     54:     if (blocks_needed <= UNIQUE_THRESHOLD) return blocks_needed;
                     55:     if (blocks_needed >= HUGE_THRESHOLD) return N_HBLK_FLS;
                     56:     return (blocks_needed - UNIQUE_THRESHOLD)/FL_COMPRESSION
                     57:                                        + UNIQUE_THRESHOLD;
                     58:
                     59: }
                     60:
                     61: # define HBLK_IS_FREE(hdr) ((hdr) -> hb_map == GC_invalid_map)
                     62: # define PHDR(hhdr) HDR(hhdr -> hb_prev)
                     63: # define NHDR(hhdr) HDR(hhdr -> hb_next)
                     64:
                     65: # ifdef USE_MUNMAP
                     66: #   define IS_MAPPED(hhdr) (((hhdr) -> hb_flags & WAS_UNMAPPED) == 0)
                     67: # else  /* !USE_MMAP */
                     68: #   define IS_MAPPED(hhdr) 1
                     69: # endif /* USE_MUNMAP */
1.1       maekawa    70:
                     71: # if !defined(NO_DEBUGGING)
                     72: void GC_print_hblkfreelist()
                     73: {
1.1.1.2   maekawa    74:     struct hblk * h;
1.1       maekawa    75:     word total_free = 0;
1.1.1.2   maekawa    76:     hdr * hhdr;
1.1       maekawa    77:     word sz;
1.1.1.2   maekawa    78:     int i;
1.1       maekawa    79:
1.1.1.2   maekawa    80:     for (i = 0; i <= N_HBLK_FLS; ++i) {
                     81:       h = GC_hblkfreelist[i];
                     82:       if (0 != h) GC_printf1("Free list %ld:\n", (unsigned long)i);
                     83:       while (h != 0) {
                     84:         hhdr = HDR(h);
1.1       maekawa    85:         sz = hhdr -> hb_sz;
1.1.1.2   maekawa    86:        GC_printf2("\t0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
1.1       maekawa    87:        total_free += sz;
                     88:         if (GC_is_black_listed(h, HBLKSIZE) != 0) {
                     89:              GC_printf0("start black listed\n");
                     90:         } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
                     91:              GC_printf0("partially black listed\n");
                     92:         } else {
                     93:              GC_printf0("not black listed\n");
                     94:         }
                     95:         h = hhdr -> hb_next;
1.1.1.2   maekawa    96:       }
                     97:     }
                     98:     if (total_free != GC_large_free_bytes) {
                     99:        GC_printf1("GC_large_free_bytes = %lu (INCONSISTENT!!)\n",
                    100:                   (unsigned long) GC_large_free_bytes);
1.1       maekawa   101:     }
                    102:     GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
                    103: }
                    104:
1.1.1.2   maekawa   105: /* Return the free list index on which the block described by the header */
                    106: /* appears, or -1 if it appears nowhere.                                */
                    107: int free_list_index_of(wanted)
                    108: hdr * wanted;
                    109: {
                    110:     struct hblk * h;
                    111:     hdr * hhdr;
                    112:     int i;
                    113:
                    114:     for (i = 0; i <= N_HBLK_FLS; ++i) {
                    115:       h = GC_hblkfreelist[i];
                    116:       while (h != 0) {
                    117:         hhdr = HDR(h);
                    118:        if (hhdr == wanted) return i;
                    119:         h = hhdr -> hb_next;
                    120:       }
                    121:     }
                    122:     return -1;
                    123: }
                    124:
                    125: void GC_dump_regions()
                    126: {
                    127:     unsigned i;
                    128:     ptr_t start, end;
                    129:     ptr_t p;
                    130:     size_t bytes;
                    131:     hdr *hhdr;
                    132:     for (i = 0; i < GC_n_heap_sects; ++i) {
                    133:        start = GC_heap_sects[i].hs_start;
                    134:        bytes = GC_heap_sects[i].hs_bytes;
                    135:        end = start + bytes;
                    136:        /* Merge in contiguous sections.        */
                    137:          while (i+1 < GC_n_heap_sects && GC_heap_sects[i+1].hs_start == end) {
                    138:            ++i;
                    139:            end = GC_heap_sects[i].hs_start + GC_heap_sects[i].hs_bytes;
                    140:          }
                    141:        GC_printf2("***Section from 0x%lx to 0x%lx\n", start, end);
                    142:        for (p = start; p < end;) {
                    143:            hhdr = HDR(p);
                    144:            GC_printf1("\t0x%lx ", (unsigned long)p);
                    145:            if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
                    146:                GC_printf1("Missing header!!\n", hhdr);
                    147:                p += HBLKSIZE;
                    148:                continue;
                    149:            }
                    150:            if (HBLK_IS_FREE(hhdr)) {
                    151:                 int correct_index = GC_hblk_fl_from_blocks(
                    152:                                        divHBLKSZ(hhdr -> hb_sz));
                    153:                int actual_index;
                    154:
                    155:                GC_printf1("\tfree block of size 0x%lx bytes",
                    156:                           (unsigned long)(hhdr -> hb_sz));
                    157:                if (IS_MAPPED(hhdr)) {
                    158:                    GC_printf0("\n");
                    159:                } else {
                    160:                    GC_printf0("(unmapped)\n");
                    161:                }
                    162:                actual_index = free_list_index_of(hhdr);
                    163:                if (-1 == actual_index) {
                    164:                    GC_printf1("\t\tBlock not on free list %ld!!\n",
                    165:                                correct_index);
                    166:                } else if (correct_index != actual_index) {
                    167:                    GC_printf2("\t\tBlock on list %ld, should be on %ld!!\n",
                    168:                               actual_index, correct_index);
                    169:                }
                    170:                p += hhdr -> hb_sz;
                    171:            } else {
                    172:                GC_printf1("\tused for blocks of size 0x%lx bytes\n",
                    173:                           (unsigned long)WORDS_TO_BYTES(hhdr -> hb_sz));
                    174:                p += HBLKSIZE * OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
                    175:            }
                    176:        }
                    177:     }
                    178: }
                    179:
1.1       maekawa   180: # endif /* NO_DEBUGGING */
                    181:
                    182: /* Initialize hdr for a block containing the indicated size and        */
                    183: /* kind of objects.                                                    */
                    184: /* Return FALSE on failure.                                            */
                    185: static GC_bool setup_header(hhdr, sz, kind, flags)
                    186: register hdr * hhdr;
                    187: word sz;       /* object size in words */
                    188: int kind;
                    189: unsigned char flags;
                    190: {
                    191:     register word descr;
                    192:
                    193:     /* Add description of valid object pointers */
                    194:       if (!GC_add_map_entry(sz)) return(FALSE);
                    195:       hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
                    196:
                    197:     /* Set size, kind and mark proc fields */
                    198:       hhdr -> hb_sz = sz;
                    199:       hhdr -> hb_obj_kind = kind;
                    200:       hhdr -> hb_flags = flags;
                    201:       descr = GC_obj_kinds[kind].ok_descriptor;
                    202:       if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
                    203:       hhdr -> hb_descr = descr;
                    204:
                    205:     /* Clear mark bits */
                    206:       GC_clear_hdr_marks(hhdr);
                    207:
                    208:     hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
                    209:     return(TRUE);
                    210: }
                    211:
1.1.1.2   maekawa   212: #define FL_UNKNOWN -1
                    213: /*
                    214:  * Remove hhdr from the appropriate free list.
                    215:  * We assume it is on the nth free list, or on the size
                    216:  * appropriate free list if n is FL_UNKNOWN.
                    217:  */
                    218: void GC_remove_from_fl(hhdr, n)
                    219: hdr * hhdr;
                    220: int n;
                    221: {
                    222:     GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
                    223:     if (hhdr -> hb_prev == 0) {
                    224:         int index;
                    225:        if (FL_UNKNOWN == n) {
                    226:             index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
                    227:        } else {
                    228:            index = n;
                    229:        }
                    230:        GC_ASSERT(HDR(GC_hblkfreelist[index]) == hhdr);
                    231:        GC_hblkfreelist[index] = hhdr -> hb_next;
                    232:     } else {
1.1.1.3 ! maekawa   233:        hdr *phdr;
        !           234:        GET_HDR(hhdr -> hb_prev, phdr);
        !           235:        phdr -> hb_next = hhdr -> hb_next;
1.1.1.2   maekawa   236:     }
                    237:     if (0 != hhdr -> hb_next) {
1.1.1.3 ! maekawa   238:        hdr * nhdr;
1.1.1.2   maekawa   239:        GC_ASSERT(!IS_FORWARDING_ADDR_OR_NIL(NHDR(hhdr)));
1.1.1.3 ! maekawa   240:        GET_HDR(hhdr -> hb_next, nhdr);
        !           241:        nhdr -> hb_prev = hhdr -> hb_prev;
1.1.1.2   maekawa   242:     }
                    243: }
                    244:
                    245: /*
                    246:  * Return a pointer to the free block ending just before h, if any.
                    247:  */
                    248: struct hblk * GC_free_block_ending_at(h)
                    249: struct hblk *h;
                    250: {
                    251:     struct hblk * p = h - 1;
1.1.1.3 ! maekawa   252:     hdr * phdr;
1.1.1.2   maekawa   253:
1.1.1.3 ! maekawa   254:     GET_HDR(p, phdr);
1.1.1.2   maekawa   255:     while (0 != phdr && IS_FORWARDING_ADDR_OR_NIL(phdr)) {
                    256:        p = FORWARDED_ADDR(p,phdr);
                    257:        phdr = HDR(p);
                    258:     }
1.1.1.3 ! maekawa   259:     if (0 != phdr) {
        !           260:         if(HBLK_IS_FREE(phdr)) {
        !           261:            return p;
        !           262:        } else {
        !           263:            return 0;
        !           264:        }
        !           265:     }
1.1.1.2   maekawa   266:     p = GC_prev_block(h - 1);
                    267:     if (0 != p) {
                    268:       phdr = HDR(p);
                    269:       if (HBLK_IS_FREE(phdr) && (ptr_t)p + phdr -> hb_sz == (ptr_t)h) {
                    270:        return p;
                    271:       }
                    272:     }
                    273:     return 0;
                    274: }
                    275:
                    276: /*
                    277:  * Add hhdr to the appropriate free list.
                    278:  * We maintain individual free lists sorted by address.
                    279:  */
                    280: void GC_add_to_fl(h, hhdr)
                    281: struct hblk *h;
                    282: hdr * hhdr;
                    283: {
                    284:     int index = GC_hblk_fl_from_blocks(divHBLKSZ(hhdr -> hb_sz));
                    285:     struct hblk *second = GC_hblkfreelist[index];
1.1.1.3 ! maekawa   286:     hdr * second_hdr;
1.1.1.2   maekawa   287: #   ifdef GC_ASSERTIONS
                    288:       struct hblk *next = (struct hblk *)((word)h + hhdr -> hb_sz);
                    289:       hdr * nexthdr = HDR(next);
                    290:       struct hblk *prev = GC_free_block_ending_at(h);
                    291:       hdr * prevhdr = HDR(prev);
                    292:       GC_ASSERT(nexthdr == 0 || !HBLK_IS_FREE(nexthdr) || !IS_MAPPED(nexthdr));
                    293:       GC_ASSERT(prev == 0 || !HBLK_IS_FREE(prevhdr) || !IS_MAPPED(prevhdr));
                    294: #   endif
                    295:     GC_ASSERT(((hhdr -> hb_sz) & (HBLKSIZE-1)) == 0);
                    296:     GC_hblkfreelist[index] = h;
                    297:     hhdr -> hb_next = second;
                    298:     hhdr -> hb_prev = 0;
1.1.1.3 ! maekawa   299:     if (0 != second) {
        !           300:       GET_HDR(second, second_hdr);
        !           301:       second_hdr -> hb_prev = h;
        !           302:     }
1.1.1.2   maekawa   303:     GC_invalidate_map(hhdr);
                    304: }
                    305:
                    306: #ifdef USE_MUNMAP
1.1       maekawa   307:
1.1.1.2   maekawa   308: /* Unmap blocks that haven't been recently touched.  This is the only way */
                    309: /* way blocks are ever unmapped.                                         */
                    310: void GC_unmap_old(void)
                    311: {
                    312:     struct hblk * h;
                    313:     hdr * hhdr;
                    314:     word sz;
                    315:     unsigned short last_rec, threshold;
                    316:     int i;
                    317: #   define UNMAP_THRESHOLD 6
                    318:
                    319:     for (i = 0; i <= N_HBLK_FLS; ++i) {
                    320:       for (h = GC_hblkfreelist[i]; 0 != h; h = hhdr -> hb_next) {
                    321:         hhdr = HDR(h);
                    322:        if (!IS_MAPPED(hhdr)) continue;
                    323:        threshold = (unsigned short)(GC_gc_no - UNMAP_THRESHOLD);
                    324:        last_rec = hhdr -> hb_last_reclaimed;
                    325:        if (last_rec > GC_gc_no
                    326:            || last_rec < threshold && threshold < GC_gc_no
                    327:                                       /* not recently wrapped */) {
                    328:           sz = hhdr -> hb_sz;
                    329:          GC_unmap((ptr_t)h, sz);
                    330:          hhdr -> hb_flags |= WAS_UNMAPPED;
                    331:        }
                    332:       }
                    333:     }
                    334: }
                    335:
                    336: /* Merge all unmapped blocks that are adjacent to other free           */
                    337: /* blocks.  This may involve remapping, since all blocks are either    */
                    338: /* fully mapped or fully unmapped.                                     */
                    339: void GC_merge_unmapped(void)
                    340: {
                    341:     struct hblk * h, *next;
                    342:     hdr * hhdr, *nexthdr;
                    343:     word size, nextsize;
                    344:     int i;
                    345:
                    346:     for (i = 0; i <= N_HBLK_FLS; ++i) {
                    347:       h = GC_hblkfreelist[i];
                    348:       while (h != 0) {
1.1.1.3 ! maekawa   349:        GET_HDR(h, hhdr);
1.1.1.2   maekawa   350:        size = hhdr->hb_sz;
                    351:        next = (struct hblk *)((word)h + size);
1.1.1.3 ! maekawa   352:        GET_HDR(next, nexthdr);
1.1.1.2   maekawa   353:        /* Coalesce with successor, if possible */
                    354:          if (0 != nexthdr && HBLK_IS_FREE(nexthdr)) {
                    355:            nextsize = nexthdr -> hb_sz;
                    356:            if (IS_MAPPED(hhdr)) {
                    357:              GC_ASSERT(!IS_MAPPED(nexthdr));
                    358:              /* make both consistent, so that we can merge */
                    359:                if (size > nextsize) {
                    360:                  GC_remap((ptr_t)next, nextsize);
                    361:                } else {
                    362:                  GC_unmap((ptr_t)h, size);
                    363:                  hhdr -> hb_flags |= WAS_UNMAPPED;
                    364:                }
                    365:            } else if (IS_MAPPED(nexthdr)) {
                    366:              GC_ASSERT(!IS_MAPPED(hhdr));
                    367:              if (size > nextsize) {
                    368:                GC_unmap((ptr_t)next, nextsize);
                    369:              } else {
                    370:                GC_remap((ptr_t)h, size);
                    371:                hhdr -> hb_flags &= ~WAS_UNMAPPED;
                    372:              }
                    373:            } else {
                    374:              /* Unmap any gap in the middle */
                    375:                GC_unmap_gap((ptr_t)h, size, (ptr_t)next, nexthdr -> hb_sz);
                    376:            }
                    377:            /* If they are both unmapped, we merge, but leave unmapped. */
                    378:            GC_remove_from_fl(hhdr, i);
                    379:            GC_remove_from_fl(nexthdr, FL_UNKNOWN);
                    380:            hhdr -> hb_sz += nexthdr -> hb_sz;
                    381:            GC_remove_header(next);
                    382:            GC_add_to_fl(h, hhdr);
                    383:            /* Start over at beginning of list */
                    384:            h = GC_hblkfreelist[i];
                    385:          } else /* not mergable with successor */ {
                    386:            h = hhdr -> hb_next;
                    387:          }
                    388:       } /* while (h != 0) ... */
                    389:     } /* for ... */
                    390: }
                    391:
                    392: #endif /* USE_MUNMAP */
                    393:
                    394: /*
                    395:  * Return a pointer to a block starting at h of length bytes.
                    396:  * Memory for the block is mapped.
                    397:  * Remove the block from its free list, and return the remainder (if any)
                    398:  * to its appropriate free list.
                    399:  * May fail by returning 0.
                    400:  * The header for the returned block must be set up by the caller.
                    401:  * If the return value is not 0, then hhdr is the header for it.
                    402:  */
                    403: struct hblk * GC_get_first_part(h, hhdr, bytes, index)
                    404: struct hblk *h;
                    405: hdr * hhdr;
                    406: word bytes;
                    407: int index;
                    408: {
                    409:     word total_size = hhdr -> hb_sz;
                    410:     struct hblk * rest;
                    411:     hdr * rest_hdr;
                    412:
                    413:     GC_ASSERT((total_size & (HBLKSIZE-1)) == 0);
                    414:     GC_remove_from_fl(hhdr, index);
                    415:     if (total_size == bytes) return h;
                    416:     rest = (struct hblk *)((word)h + bytes);
1.1.1.3 ! maekawa   417:     rest_hdr = GC_install_header(rest);
        !           418:     if (0 == rest_hdr) return(0);
1.1.1.2   maekawa   419:     rest_hdr -> hb_sz = total_size - bytes;
                    420:     rest_hdr -> hb_flags = 0;
                    421: #   ifdef GC_ASSERTIONS
                    422:       // Mark h not free, to avoid assertion about adjacent free blocks.
                    423:         hhdr -> hb_map = 0;
                    424: #   endif
                    425:     GC_add_to_fl(rest, rest_hdr);
                    426:     return h;
                    427: }
                    428:
                    429: /*
                    430:  * H is a free block.  N points at an address inside it.
                    431:  * A new header for n has already been set up.  Fix up h's header
                    432:  * to reflect the fact that it is being split, move it to the
                    433:  * appropriate free list.
                    434:  * N replaces h in the original free list.
                    435:  *
                    436:  * Nhdr is not completely filled in, since it is about to allocated.
                    437:  * It may in fact end up on the wrong free list for its size.
                    438:  * (Hence adding it to a free list is silly.  But this path is hopefully
                    439:  * rare enough that it doesn't matter.  The code is cleaner this way.)
                    440:  */
                    441: void GC_split_block(h, hhdr, n, nhdr, index)
                    442: struct hblk *h;
                    443: hdr * hhdr;
                    444: struct hblk *n;
                    445: hdr * nhdr;
                    446: int index;     /* Index of free list */
                    447: {
                    448:     word total_size = hhdr -> hb_sz;
                    449:     word h_size = (word)n - (word)h;
                    450:     struct hblk *prev = hhdr -> hb_prev;
                    451:     struct hblk *next = hhdr -> hb_next;
                    452:
                    453:     /* Replace h with n on its freelist */
                    454:       nhdr -> hb_prev = prev;
                    455:       nhdr -> hb_next = next;
                    456:       nhdr -> hb_sz = total_size - h_size;
                    457:       nhdr -> hb_flags = 0;
                    458:       if (0 != prev) {
                    459:        HDR(prev) -> hb_next = n;
                    460:       } else {
                    461:         GC_hblkfreelist[index] = n;
                    462:       }
                    463:       if (0 != next) {
                    464:        HDR(next) -> hb_prev = n;
                    465:       }
                    466: #     ifdef GC_ASSERTIONS
                    467:        nhdr -> hb_map = 0;     /* Don't fail test for consecutive      */
                    468:                                /* free blocks in GC_add_to_fl.         */
                    469: #     endif
                    470: #   ifdef USE_MUNMAP
                    471:       hhdr -> hb_last_reclaimed = GC_gc_no;
                    472: #   endif
                    473:     hhdr -> hb_sz = h_size;
                    474:     GC_add_to_fl(h, hhdr);
                    475:     GC_invalidate_map(nhdr);
                    476: }
1.1       maekawa   477:
1.1.1.2   maekawa   478: struct hblk * GC_allochblk_nth();
                    479:
1.1       maekawa   480: /*
                    481:  * Allocate (and return pointer to) a heap block
1.1.1.2   maekawa   482:  *   for objects of size sz words, searching the nth free list.
1.1       maekawa   483:  *
                    484:  * NOTE: We set obj_map field in header correctly.
1.1.1.2   maekawa   485:  *       Caller is responsible for building an object freelist in block.
1.1       maekawa   486:  *
                    487:  * We clear the block if it is destined for large objects, and if
                    488:  * kind requires that newly allocated objects be cleared.
                    489:  */
                    490: struct hblk *
                    491: GC_allochblk(sz, kind, flags)
                    492: word sz;
                    493: int kind;
                    494: unsigned char flags;  /* IGNORE_OFF_PAGE or 0 */
                    495: {
1.1.1.2   maekawa   496:     int start_list = GC_hblk_fl_from_blocks(OBJ_SZ_TO_BLOCKS(sz));
                    497:     int i;
                    498:     for (i = start_list; i <= N_HBLK_FLS; ++i) {
                    499:        struct hblk * result = GC_allochblk_nth(sz, kind, flags, i);
                    500:        if (0 != result) return result;
                    501:     }
                    502:     return 0;
                    503: }
                    504: /*
                    505:  * The same, but with search restricted to nth free list.
                    506:  */
                    507: struct hblk *
                    508: GC_allochblk_nth(sz, kind, flags, n)
                    509: word sz;
                    510: int kind;
                    511: unsigned char flags;  /* IGNORE_OFF_PAGE or 0 */
                    512: int n;
                    513: {
1.1       maekawa   514:     register struct hblk *hbp;
                    515:     register hdr * hhdr;               /* Header corr. to hbp */
1.1.1.2   maekawa   516:     register struct hblk *thishbp;
                    517:     register hdr * thishdr;            /* Header corr. to hbp */
1.1       maekawa   518:     signed_word size_needed;    /* number of bytes in requested objects */
                    519:     signed_word size_avail;    /* bytes available in this block        */
                    520:
                    521:     size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
                    522:
                    523:     /* search for a big enough block in free list */
1.1.1.2   maekawa   524:        hbp = GC_hblkfreelist[n];
1.1.1.3 ! maekawa   525:        for(; 0 != hbp; hbp = hhdr -> hb_next) {
        !           526:            GET_HDR(hbp, hhdr);
1.1       maekawa   527:            size_avail = hhdr->hb_sz;
                    528:            if (size_avail < size_needed) continue;
1.1.1.3 ! maekawa   529:            if (!GC_use_entire_heap) {
1.1       maekawa   530:                if (size_avail != size_needed
1.1.1.3 ! maekawa   531:                    && USED_HEAP_SIZE >= GC_requested_heapsize
1.1.1.2   maekawa   532:                    && !GC_incremental && GC_should_collect()) {
1.1       maekawa   533:                    continue;
                    534:                }
1.1.1.3 ! maekawa   535:            }
1.1       maekawa   536:            /* If the next heap block is obviously better, go on.       */
                    537:            /* This prevents us from disassembling a single large block */
                    538:            /* to get tiny blocks.                                      */
                    539:            {
                    540:              signed_word next_size;
                    541:
                    542:              thishbp = hhdr -> hb_next;
1.1.1.2   maekawa   543:              if (thishbp != 0) {
1.1.1.3 ! maekawa   544:                GET_HDR(thishbp, thishdr);
1.1.1.2   maekawa   545:                next_size = (signed_word)(thishdr -> hb_sz);
                    546:                if (next_size < size_avail
1.1       maekawa   547:                  && next_size >= size_needed
                    548:                  && !GC_is_black_listed(thishbp, (word)size_needed)) {
                    549:                  continue;
1.1.1.2   maekawa   550:                }
1.1       maekawa   551:              }
                    552:            }
                    553:            if ( !IS_UNCOLLECTABLE(kind) &&
                    554:                 (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
                    555:              struct hblk * lasthbp = hbp;
                    556:              ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
                    557:              signed_word orig_avail = size_avail;
                    558:              signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
                    559:                                                HBLKSIZE
                    560:                                                : size_needed);
                    561:
                    562:
                    563:              while ((ptr_t)lasthbp <= search_end
                    564:                     && (thishbp = GC_is_black_listed(lasthbp,
                    565:                                                      (word)eff_size_needed))) {
                    566:                lasthbp = thishbp;
                    567:              }
                    568:              size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
                    569:              thishbp = lasthbp;
                    570:              if (size_avail >= size_needed) {
1.1.1.3 ! maekawa   571:                if (thishbp != hbp &&
        !           572:                    0 != (thishdr = GC_install_header(thishbp))) {
1.1.1.2   maekawa   573:                  /* Make sure it's mapped before we mangle it. */
                    574: #                  ifdef USE_MUNMAP
                    575:                      if (!IS_MAPPED(hhdr)) {
1.1.1.3 ! maekawa   576:                        GC_remap((ptr_t)hbp, hhdr -> hb_sz);
1.1.1.2   maekawa   577:                        hhdr -> hb_flags &= ~WAS_UNMAPPED;
                    578:                      }
                    579: #                  endif
1.1       maekawa   580:                  /* Split the block at thishbp */
1.1.1.2   maekawa   581:                      GC_split_block(hbp, hhdr, thishbp, thishdr, n);
1.1       maekawa   582:                  /* Advance to thishbp */
                    583:                      hbp = thishbp;
                    584:                      hhdr = thishdr;
1.1.1.2   maekawa   585:                      /* We must now allocate thishbp, since it may     */
                    586:                      /* be on the wrong free list.                     */
1.1       maekawa   587:                }
                    588:              } else if (size_needed > (signed_word)BL_LIMIT
                    589:                         && orig_avail - size_needed
                    590:                            > (signed_word)BL_LIMIT) {
                    591:                /* Punt, since anything else risks unreasonable heap growth. */
                    592:                WARN("Needed to allocate blacklisted block at 0x%lx\n",
                    593:                     (word)hbp);
                    594:                size_avail = orig_avail;
1.1.1.2   maekawa   595:              } else if (size_avail == 0 && size_needed == HBLKSIZE
                    596:                         && IS_MAPPED(hhdr)) {
                    597:                if (!GC_find_leak) {
1.1       maekawa   598:                  static unsigned count = 0;
                    599:
                    600:                  /* The block is completely blacklisted.  We need      */
                    601:                  /* to drop some such blocks, since otherwise we spend */
                    602:                  /* all our time traversing them if pointerfree        */
                    603:                  /* blocks are unpopular.                              */
                    604:                  /* A dropped block will be reconsidered at next GC.   */
                    605:                  if ((++count & 3) == 0) {
                    606:                    /* Allocate and drop the block in small chunks, to  */
                    607:                    /* maximize the chance that we will recover some    */
                    608:                    /* later.                                           */
1.1.1.2   maekawa   609:                      word total_size = hhdr -> hb_sz;
                    610:                      struct hblk * limit = hbp + divHBLKSZ(total_size);
1.1       maekawa   611:                      struct hblk * h;
1.1.1.2   maekawa   612:                      struct hblk * prev = hhdr -> hb_prev;
1.1       maekawa   613:
1.1.1.2   maekawa   614:                      GC_words_wasted += total_size;
                    615:                      GC_large_free_bytes -= total_size;
                    616:                      GC_remove_from_fl(hhdr, n);
1.1       maekawa   617:                      for (h = hbp; h < limit; h++) {
1.1.1.3 ! maekawa   618:                        if (h == hbp || 0 != (hhdr = GC_install_header(h))) {
1.1       maekawa   619:                          (void) setup_header(
                    620:                                  hhdr,
                    621:                                  BYTES_TO_WORDS(HBLKSIZE - HDR_BYTES),
                    622:                                  PTRFREE, 0); /* Cant fail */
                    623:                          if (GC_debugging_started) {
1.1.1.2   maekawa   624:                            BZERO(h + HDR_BYTES, HBLKSIZE - HDR_BYTES);
1.1       maekawa   625:                          }
                    626:                        }
                    627:                      }
                    628:                    /* Restore hbp to point at free block */
1.1.1.2   maekawa   629:                      hbp = prev;
                    630:                      if (0 == hbp) {
                    631:                        return GC_allochblk_nth(sz, kind, flags, n);
                    632:                      }
                    633:                      hhdr = HDR(hbp);
1.1       maekawa   634:                  }
1.1.1.2   maekawa   635:                }
1.1       maekawa   636:              }
                    637:            }
                    638:            if( size_avail >= size_needed ) {
1.1.1.2   maekawa   639: #              ifdef USE_MUNMAP
                    640:                  if (!IS_MAPPED(hhdr)) {
1.1.1.3 ! maekawa   641:                    GC_remap((ptr_t)hbp, hhdr -> hb_sz);
1.1.1.2   maekawa   642:                    hhdr -> hb_flags &= ~WAS_UNMAPPED;
                    643:                  }
                    644: #              endif
                    645:                /* hbp may be on the wrong freelist; the parameter n    */
                    646:                /* is important.                                        */
                    647:                hbp = GC_get_first_part(hbp, hhdr, size_needed, n);
1.1       maekawa   648:                break;
                    649:            }
                    650:        }
1.1.1.2   maekawa   651:
                    652:     if (0 == hbp) return 0;
1.1       maekawa   653:
                    654:     /* Notify virtual dirty bit implementation that we are about to write. */
1.1.1.2   maekawa   655:        GC_write_hint(hbp);
1.1       maekawa   656:
                    657:     /* Add it to map of valid blocks */
1.1.1.2   maekawa   658:        if (!GC_install_counts(hbp, (word)size_needed)) return(0);
1.1       maekawa   659:        /* This leaks memory under very rare conditions. */
                    660:
                    661:     /* Set up header */
1.1.1.2   maekawa   662:         if (!setup_header(hhdr, sz, kind, flags)) {
                    663:             GC_remove_counts(hbp, (word)size_needed);
1.1       maekawa   664:             return(0); /* ditto */
                    665:         }
                    666:
                    667:     /* Clear block if necessary */
                    668:        if (GC_debugging_started
                    669:            || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
1.1.1.2   maekawa   670:            BZERO(hbp + HDR_BYTES,  size_needed - HDR_BYTES);
1.1       maekawa   671:        }
                    672:
                    673:     /* We just successfully allocated a block.  Restart count of       */
                    674:     /* consecutive failures.                                           */
                    675:     {
                    676:        extern unsigned GC_fail_count;
                    677:
                    678:        GC_fail_count = 0;
                    679:     }
1.1.1.2   maekawa   680:
                    681:     GC_large_free_bytes -= size_needed;
1.1       maekawa   682:
1.1.1.2   maekawa   683:     GC_ASSERT(IS_MAPPED(hhdr));
                    684:     return( hbp );
1.1       maekawa   685: }
                    686:
                    687: struct hblk * GC_freehblk_ptr = 0;  /* Search position hint for GC_freehblk */
                    688:
                    689: /*
                    690:  * Free a heap block.
                    691:  *
                    692:  * Coalesce the block with its neighbors if possible.
                    693:  *
                    694:  * All mark words are assumed to be cleared.
                    695:  */
                    696: void
1.1.1.2   maekawa   697: GC_freehblk(hbp)
                    698: struct hblk *hbp;
1.1       maekawa   699: {
1.1.1.2   maekawa   700: struct hblk *next, *prev;
                    701: hdr *hhdr, *prevhdr, *nexthdr;
                    702: signed_word size;
1.1       maekawa   703:
                    704:
1.1.1.3 ! maekawa   705:     GET_HDR(hbp, hhdr);
1.1.1.2   maekawa   706:     size = hhdr->hb_sz;
                    707:     size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
                    708:     GC_remove_counts(hbp, (word)size);
                    709:     hhdr->hb_sz = size;
1.1       maekawa   710:
                    711:     /* Check for duplicate deallocation in the easy case */
1.1.1.2   maekawa   712:       if (HBLK_IS_FREE(hhdr)) {
1.1       maekawa   713:         GC_printf1("Duplicate large block deallocation of 0x%lx\n",
1.1.1.2   maekawa   714:                   (unsigned long) hbp);
1.1       maekawa   715:       }
                    716:
1.1.1.2   maekawa   717:     GC_ASSERT(IS_MAPPED(hhdr));
                    718:     GC_invalidate_map(hhdr);
                    719:     next = (struct hblk *)((word)hbp + size);
1.1.1.3 ! maekawa   720:     GET_HDR(next, nexthdr);
1.1.1.2   maekawa   721:     prev = GC_free_block_ending_at(hbp);
1.1       maekawa   722:     /* Coalesce with successor, if possible */
1.1.1.2   maekawa   723:       if(0 != nexthdr && HBLK_IS_FREE(nexthdr) && IS_MAPPED(nexthdr)) {
                    724:        GC_remove_from_fl(nexthdr, FL_UNKNOWN);
                    725:        hhdr -> hb_sz += nexthdr -> hb_sz;
                    726:        GC_remove_header(next);
                    727:       }
                    728:     /* Coalesce with predecessor, if possible. */
                    729:       if (0 != prev) {
                    730:        prevhdr = HDR(prev);
                    731:        if (IS_MAPPED(prevhdr)) {
                    732:          GC_remove_from_fl(prevhdr, FL_UNKNOWN);
                    733:          prevhdr -> hb_sz += hhdr -> hb_sz;
                    734:          GC_remove_header(hbp);
                    735:          hbp = prev;
                    736:          hhdr = prevhdr;
                    737:        }
1.1       maekawa   738:       }
                    739:
1.1.1.2   maekawa   740:     GC_large_free_bytes += size;
                    741:     GC_add_to_fl(hbp, hhdr);
1.1       maekawa   742: }
                    743:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>