This is allochblk.c in view mode; [Download] [Up]
/*
* Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
* Copyright (c) 1991 by Xerox Corporation. All rights reserved.
*
* THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
* OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
*
* Permission is hereby granted to copy this garbage collector for any purpose,
* provided the above notices are retained on all copies.
*/
#define DEBUG
#undef DEBUG
#include <stdio.h>
#include "gc_private.h"
/**/
/* allocate/free routines for heap blocks
/* Note that everything called from outside the garbage collector
/* should be prepared to abort at any point as the result of a signal.
/**/
/*
* Free heap blocks are kept on a list sorted by address.
* The hb_hdr.hbh_sz field of a free heap block contains the length
* (in bytes) of the entire block.
* Neighbors are coalesced.
*/
# define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
/* largest block we will allocate starting on a black */
/* listed block. Must be >= HBLKSIZE. */
struct hblk * GC_hblkfreelist = 0;
struct hblk *GC_savhbp = (struct hblk *)0; /* heap block preceding next */
/* block to be examined by */
/* GC_allochblk. */
void GC_print_hblkfreelist()
{
struct hblk * h = GC_hblkfreelist;
word total_free = 0;
hdr * hhdr = HDR(h);
word sz;
while (h != 0) {
sz = hhdr -> hb_sz;
GC_printf2("0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
total_free += sz;
if (GC_is_black_listed(h, HBLKSIZE) != 0) {
GC_printf0("start black listed\n");
} else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
GC_printf0("partially black listed\n");
} else {
GC_printf0("not black listed\n");
}
h = hhdr -> hb_next;
hhdr = HDR(h);
}
GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
}
/* Initialize hdr for a block containing the indicated size and */
/* kind of objects. */
/* Return FALSE on failure. */
static bool setup_header(hhdr, sz, kind)
register hdr * hhdr;
word sz; /* object size in words */
int kind;
{
/* Add description of valid object pointers */
if (!GC_add_map_entry(sz)) return(FALSE);
hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
/* Set size, kind and mark proc fields */
hhdr -> hb_sz = sz;
hhdr -> hb_obj_kind = kind;
hhdr -> hb_mark_proc = GC_obj_kinds[kind].ok_mark_proc;
/* Clear mark bits */
GC_clear_hdr_marks(hhdr);
hhdr -> hb_last_reclaimed = GC_gc_no;
return(TRUE);
}
/*
* Allocate (and return pointer to) a heap block
* for objects of size |sz| words.
*
* NOTE: We set obj_map field in header correctly.
* Caller is resposnsible for building an object freelist in block.
*
* We clear the block if it is destined for large objects, and if
* kind requires that newly allocated objects be cleared.
*/
struct hblk *
GC_allochblk(sz, kind)
word sz;
int kind;
{
register struct hblk *thishbp;
register hdr * thishdr; /* Header corr. to thishbp */
register struct hblk *hbp;
register hdr * hhdr; /* Header corr. to hbp */
struct hblk *prevhbp;
register hdr * phdr; /* Header corr. to prevhbp */
signed_word size_needed; /* number of bytes in requested objects */
signed_word size_avail; /* bytes available in this block */
bool first_time = TRUE;
size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
/* search for a big enough block in free list */
hbp = GC_savhbp;
hhdr = HDR(hbp);
for(;;) {
prevhbp = hbp;
phdr = hhdr;
hbp = (prevhbp == 0? GC_hblkfreelist : phdr->hb_next);
hhdr = HDR(hbp);
if( prevhbp == GC_savhbp && !first_time) {
return(0);
}
first_time = FALSE;
if( hbp == 0 ) continue;
size_avail = hhdr->hb_sz;
if (size_avail < size_needed) continue;
/* If the next heap block is obviously better, go on. */
/* This prevents us from disassembling a single large block */
/* to get tiny blocks. */
{
word next_size;
thishbp = hhdr -> hb_next;
if (thishbp == 0) thishbp = GC_hblkfreelist;
thishdr = HDR(thishbp);
next_size = thishdr -> hb_sz;
if (next_size < size_avail
&& next_size >= size_needed
&& !GC_is_black_listed(thishbp, (word)size_needed)) {
continue;
}
}
if ( kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC) {
struct hblk * lasthbp = hbp;
ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
while ((ptr_t)lasthbp <= search_end
&& (thishbp = GC_is_black_listed(lasthbp,
(word)size_needed))) {
lasthbp = thishbp;
}
size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
thishbp = lasthbp;
if (size_avail >= size_needed && thishbp != hbp
&& GC_install_header(thishbp)) {
/* Split the block at thishbp */
thishdr = HDR(thishbp);
/* GC_invalidate_map not needed, since we will */
/* allocate this block. */
thishdr -> hb_next = hhdr -> hb_next;
thishdr -> hb_sz = size_avail;
hhdr -> hb_sz = (ptr_t)thishbp - (ptr_t)hbp;
hhdr -> hb_next = thishbp;
/* Advance to thishbp */
prevhbp = hbp;
phdr = hhdr;
hbp = thishbp;
hhdr = thishdr;
} else if (size_avail == 0
&& size_needed == HBLKSIZE
&& prevhbp != 0) {
# ifndef FIND_LEAK
static unsigned count = 0;
/* The block is completely blacklisted. We need */
/* to drop some such blocks, since otherwise we spend */
/* all our time traversing them if pointerfree */
/* blocks are unpopular. */
/* A dropped block will be reconsidered at next GC. */
if ((++count & 3) == 0) {
/* Allocate and drop the block */
if (GC_install_counts(hbp, hhdr->hb_sz)) {
phdr -> hb_next = hhdr -> hb_next;
(void) setup_header(
hhdr,
BYTES_TO_WORDS(hhdr->hb_sz - HDR_BYTES),
PTRFREE); /* Cant fail */
if (GC_debugging_started) {
bzero((char *)hbp + HDR_BYTES,
(int)(hhdr->hb_sz - HDR_BYTES));
}
if (GC_savhbp == hbp) GC_savhbp = prevhbp;
}
/* Restore hbp to point at free block */
hbp = prevhbp;
hhdr = phdr;
if (hbp == GC_savhbp) first_time = TRUE;
}
# endif
}
}
if( size_avail >= size_needed ) {
/* found a big enough block */
/* let thishbp --> the block */
/* set prevhbp, hbp to bracket it */
thishbp = hbp;
thishdr = hhdr;
if( size_avail == size_needed ) {
hbp = hhdr->hb_next;
hhdr = HDR(hbp);
} else {
hbp = (struct hblk *)
(((word)thishbp) + size_needed);
if (!GC_install_header(hbp)) continue;
hhdr = HDR(hbp);
GC_invalidate_map(hhdr);
hhdr->hb_next = thishdr->hb_next;
hhdr->hb_sz = size_avail - size_needed;
}
/* remove *thishbp from hblk freelist */
if( prevhbp == 0 ) {
GC_hblkfreelist = hbp;
} else {
phdr->hb_next = hbp;
}
/* save current list search position */
GC_savhbp = hbp;
break;
}
}
/* Notify virtual dirty bit implementation that we are about to write. */
GC_write_hint(thishbp);
/* Add it to map of valid blocks */
if (!GC_install_counts(thishbp, (word)size_needed)) return(0);
/* This leaks memory under very rare conditions. */
/* Set up header */
if (!setup_header(thishdr, sz, kind)) {
GC_remove_counts(thishbp, (word)size_needed);
return(0); /* ditto */
}
/* Clear block if necessary */
if (GC_debugging_started
|| sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
bzero((char *)thishbp + HDR_BYTES, (int)(size_needed - HDR_BYTES));
}
return( thishbp );
}
struct hblk * GC_freehblk_ptr = 0; /* Search position hint for GC_freehblk */
/*
* Free a heap block.
*
* Coalesce the block with its neighbors if possible.
*
* All mark words are assumed to be cleared.
*/
void
GC_freehblk(p)
register struct hblk *p;
{
register hdr *phdr; /* Header corresponding to p */
register struct hblk *hbp, *prevhbp;
register hdr *hhdr, *prevhdr;
register signed_word size;
/* GC_savhbp may become invalid due to coalescing. Clear it. */
GC_savhbp = (struct hblk *)0;
phdr = HDR(p);
size = phdr->hb_sz;
size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
GC_remove_counts(p, (word)size);
phdr->hb_sz = size;
GC_invalidate_map(phdr);
prevhbp = 0;
/* The following optimization was suggested by David Detlefs. */
/* Note that the header cannot be NIL, since there cannot be an */
/* intervening call to GC_freehblk without resetting */
/* GC_freehblk_ptr. */
if (GC_freehblk_ptr != 0 &&
HDR(GC_freehblk_ptr)->hb_map == GC_invalid_map &&
(ptr_t)GC_freehblk_ptr < (ptr_t)p) {
hbp = GC_freehblk_ptr;
} else {
hbp = GC_hblkfreelist;
};
hhdr = HDR(hbp);
while( (hbp != 0) && (hbp < p) ) {
prevhbp = hbp;
prevhdr = hhdr;
hbp = hhdr->hb_next;
hhdr = HDR(hbp);
}
GC_freehblk_ptr = prevhbp;
/* Check for duplicate deallocation in the easy case */
if (hbp != 0 && (ptr_t)p + size > (ptr_t)hbp
|| prevhbp != 0 && (ptr_t)prevhbp + prevhdr->hb_sz > (ptr_t)p) {
GC_printf1("Duplicate large block deallocation of 0x%lx\n",
(unsigned long) p);
GC_printf2("Surrounding free blocks are 0x%lx and 0x%lx\n",
(unsigned long) prevhbp, (unsigned long) hbp);
}
/* Coalesce with successor, if possible */
if( (((word)p)+size) == ((word)hbp) ) {
phdr->hb_next = hhdr->hb_next;
phdr->hb_sz += hhdr->hb_sz;
GC_remove_header(hbp);
} else {
phdr->hb_next = hbp;
}
if( prevhbp == 0 ) {
GC_hblkfreelist = p;
} else if( (((word)prevhbp) + prevhdr->hb_sz)
== ((word)p) ) {
/* Coalesce with predecessor */
prevhdr->hb_next = phdr->hb_next;
prevhdr->hb_sz += phdr->hb_sz;
GC_remove_header(p);
} else {
prevhdr->hb_next = p;
}
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.