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

Annotation of OpenXM_contrib2/asir2000/gc/allchblk.c, Revision 1.6

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

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