#ifdef MALLOC_bibopmalloc
/*
**
** This is a special purpose malloc for lpmud.
** It is geared towards the special needs of the game driver:
** - most allocations (>98%) are of small objects (<100 byte)
** - very few allocations (< 0.03%) are large (>64k)
**
** This has lead to a malloc using three different strategies:
** small, medium, and large.
** All allocation is based on pages (typical page size is 32K).
** Pages are allocated on pages boundaries. This makes it possible
** to store information about a page and its objects just at the
** beginning of a page. Given a pointer in the middle of a page
** the address is just masked to page boundary and the page information
** is available there.
**
** Small objects:
** Objects with a size smaller than a threshold will
** be allocated in BIBOP (big bag of pages) style.
** A page consists of some information about the page in the
** beginning followed by a bitmap indicating the usage
** of objects and an array of objects. Within a page
** all objects have the same size.
** To get to the information given a pointer to an
** object you mask off the lower part of the address.
** This method gives a very small space overhead (<2 bits) per object.
**
** Medium objects:
** Medium sized objects are allocated within a page.
** All the pages are linked, and the objects are linked
** within a page. All free space is linked into doubly
** linked lists. There are a number of list headers for different
** sizes of the free object. The allocation uses best fit
** among the headers, and first fit in the doubly linked list.
** Free objects are coalesced when being freed.
**
** Large objects:
** Large objects are given several consecutive pages.
** Large requests are always rounded to a multiple of
** pages.
**
** Free pages (from freeing large or medium requests) are kept
** on a free list where best fit is used to do allocation.
**
** The current tuning of the allocation parameters seems to indicate
** that the space overhead is around 15%.
*/
/*#define BIBOP_DEBUG */
/*#define FREESTAT*/
#define PARANOIA
#include <stdio.h>
#include "config.h"
#include <math.h>
#ifdef __alpha
#define SMALL_SIZE 96 /* smaller than this is uses bibop */
#define PAGE_SIZE 0x10000 /* 64k pages MUST!! be a power of 2 */
#define SIZE_SLOP 96 /* don't split a free space if leftover is less than this */
#else
#define SMALL_SIZE 56 /* smaller than this is uses bibop */
#define PAGE_SIZE 0x8000 /* 32k pages MUST!! be a power of 2 */
#define SIZE_SLOP 56 /* don't split a free space if leftover is less than this */
#endif
#define NFREE 20 /* number of headers for medium blocks */
typedef double aligntype;
#define ALIGNMENT (sizeof(aligntype)) /* alignment requirement for this platform */
typedef unsigned long mapword; /* should be the largest possible unsigned type */
#define BITS_PER_BYTE 8 /* bits per unit in sizeof */
#define CEIL(x) (((x)+ALIGNMENT-1) & ~(ALIGNMENT-1))
#define PAGEMASK (~(PAGE_SIZE-1))
#define PTR_SIZE (sizeof(void *))
#define BITS_PER_MAPWORD (sizeof(mapword) * BITS_PER_BYTE)
struct bibop {
int objsize; /* Size of the objects (rounded) */
int objfree; /* Number of free objects */
int maxobjfree; /* Maximum objects that fit on the page */
mapword *freemap; /* Bitmap for free objects */
int nextfree; /* (Cached) index to look for free object */
int maxfree; /* Max index into freemap */
void *objs; /* Pointer to first object */
};
#define BIBOPMAGIC 0x55AA5A01
static int p_bibop, m_bibop, f_bibop;
static long s_bibop;
struct medium {
#if 0
int freecnt; /* number of free objects in this page */
int maxfree; /* largest free object, or 0 if unknown */
#endif
aligntype data;
};
#define ALLOCMAGIC 0x55AA5A02
static int p_alloc, m_alloc, f_alloc;
static long s_alloc;
#define OBJSIZE(cur) ((char *)cur->next - (char *)OBJ_TO_DATA(cur))
struct freeblk {
struct freeblk *fwd, *bwd;
#ifdef FREESTAT
struct freehead *head;
#endif
};
struct freehead {
struct freeblk h;
int maxsize;
int nalloc, nreal, nsplit, nfree, njoin, njoin1, njoin2, ndrop, nwhy, nskip;
};
static struct freehead freehead[NFREE];
#define FDEL(p) (p)->bwd->fwd = (p)->fwd, (p)->fwd->bwd = (p)->bwd
#define FINS(p, q) (p)->fwd = (q)->fwd, (q)->fwd = (p), (p)->bwd = (q), (p)->fwd->bwd = (p)
struct big {
int npages;
aligntype data;
};
#define BIGMAGIC 0x55AA5A03
static int p_big, m_big, f_big;
static long s_big;
struct descr {
int magic; /* magic number for different page types */
struct descr *dnext; /* next page in whatever list it happens to be in */
union {
struct bibop bibop;
struct medium medium;
struct big big;
} u;
};
#ifdef USE_SWAP
extern int used_memory; /* for the swap to know */
#endif
static struct descr *bibops[(SMALL_SIZE+ALIGNMENT-1)/ALIGNMENT]; /* start of bibop chains */
static struct descr *newbibop();
static struct descr *firstpage;
typedef unsigned long PTR; /* same size as a pointer */
static struct descr *freepage = 0;
static int p_free;
struct block {
#ifdef BIBOP_DEBUG
int bmagic;
#endif
int busy;
struct block *next;
union {
aligntype data;
struct freeblk fb;
} u;
};
#define DATA_TO_OBJ(p) ((struct block *)( (char *)p - (long)&((struct block *)0)->u.data ))
#define OBJ_TO_DATA(p) ((void *)&p->u.data)
#define BMAGIC 0x19930921
static char *nextpage, *firstsbrk;
static int initdone = 0;
extern void *sbrk();
#define OFFSET(t,f) ((long) &(((t *)0)->f))
/* Insert pages on free list, coalescing pages if possible */
static void
insertfreepage(struct descr *p)
{
struct descr **fp;
#ifdef BIBOP_DEBUG
fprintf(stderr, "freeing %d pages at %lx", p->u.big.npages, p);
#endif
/* find position */
for(fp = &freepage; *fp && p > *fp; fp = &(*fp)->dnext)
;
/* insert into chain */
p->dnext = *fp;
*fp = p;
/* check for adjecent following page */
if ((char *)p->dnext == (char *)p + p->u.big.npages * PAGE_SIZE) {
p->u.big.npages += p->dnext->u.big.npages;
p->dnext = p->dnext->dnext;
#ifdef BIBOP_DEBUG
fprintf(stderr, ", join with next block");
#endif
}
/* check for adjecent preceding page */
if (fp != &freepage) {
struct descr *q;
q = (struct descr *)((char *)fp - OFFSET(struct descr, dnext));
if ((char *)q->dnext == (char *)q + q->u.big.npages * PAGE_SIZE) {
q->u.big.npages += q->dnext->u.big.npages;
q->dnext = q->dnext->dnext;
#ifdef BIBOP_DEBUG
fprintf(stderr, ", join with previous block");
#endif
}
}
#ifdef BIBOP_DEBUG
{
struct descr *f;
fprintf(stderr, "\nfree page list (nextpage=%lx):\n", nextpage);
for(f = freepage; f; f = f->dnext) {
fprintf(stderr, " %lx (%lx) %d\n", f, (char *)f + f->u.big.npages * PAGE_SIZE, f->u.big.npages);
}
}
#endif
}
/* Allocate n pages. */
static void *
pages(unsigned int n)
{
void *r;
#ifdef BIBOP_DEBUG
fprintf(stderr, "allocating %d pages", n);
#endif
if (freepage) {
/* try to find something on the free list */
/* use best fit, slower but better */
struct descr **p, **last, **best = 0, *b;
for(p = &freepage; *p; last = p, p = &(*p)->dnext) {
if ((*p)->u.big.npages == n) {
best = p;
break;
} else if ((*p)->u.big.npages > n) {
if (!best || (*p)->u.big.npages < (*best)->u.big.npages)
best = p;
}
}
if (!best) {
/* couldn't find anything, try extending last block */
if ((char *)(*last) + (*last)->u.big.npages * PAGE_SIZE == nextpage) {
int k = n - (*last)->u.big.npages;
r = sbrk(k*PAGE_SIZE);
if (!r || r == (void *)-1) {
fprintf(stderr, "sbrk failed %ld\n", nextpage - firstsbrk);
return 0;
}
nextpage += k*PAGE_SIZE;
(*last)->u.big.npages += k;
best = last;
p_free += k;
#ifdef BIBOP_DEBUG
fprintf(stderr, ", extending %d", k);
#endif
} else
goto notfound;
}
#ifdef BIBOP_DEBUG
fprintf(stderr, ", from free list");
#endif
/* best points at something usable */
b = *best;
r = b;
if (b->u.big.npages > n) {
/* split the block */
*best = (struct descr *)((char *)b + n * PAGE_SIZE);
(*best)->magic = b->magic;
(*best)->u.big.npages = b->u.big.npages - n;
(*best)->dnext = b->dnext;
#ifdef BIBOP_DEBUG
fprintf(stderr, ", split it %d %d", b->u.big.npages, n);
#endif
} else {
*best = b->dnext; /* remove block */
}
p_free -= n;
#ifdef BIBOP_DEBUG
{
struct descr *f;
fprintf(stderr, "\nfree page list (nextpage=%lx):\n", nextpage);
for(f = freepage; f; f = f->dnext) {
fprintf(stderr, " %lx (%lx) %d\n", f, (char *)f + f->u.big.npages * PAGE_SIZE, f->u.big.npages);
}
}
#endif
return r;
}
notfound:
#ifdef BIBOP_DEBUG
fprintf(stderr, " fresh\n");
#endif
r = sbrk(n*PAGE_SIZE);
if (!r || r == (void *)-1) {
fprintf(stderr, "sbrk failed %ld\n", nextpage - firstsbrk);
return 0;
}
if (!(nextpage - PAGE_SIZE <= (char *)r && (char *)r <= nextpage + PAGE_SIZE)) { fprintf(stderr, "bad sbrk %lx %lx\n", r, nextpage); }
r = nextpage;
nextpage += n*PAGE_SIZE;
return r;
}
/* Insert a (medium) block into the appropriate free list */
static void
insfree(struct block *b, int how)
{
int s = OBJSIZE(b);
int i;
for(i = 0; i < NFREE && freehead[i].maxsize <= s; i++)
;
#ifdef PARANOIA
if (i == NFREE) {
fprintf(stderr, "insfree %d\n", s);
abort();
}
#endif
FINS(&b->u.fb, &freehead[i].h);
#ifdef FREESTAT
if (how == 1) freehead[i].nsplit++;
if (how == 2) freehead[i].nfree++;
if (how == 3) freehead[i].njoin++;
b->u.fb.head = &freehead[i];
#endif
}
/* Initialize a new medium page */
static void
init_allocpage(struct descr *p)
{
struct block *first, *last;
p->magic = ALLOCMAGIC;
#if 0
p->u.medium.freecnt = 1; /* one free block after init */
#endif
p->dnext = 0;
first = (struct block *)&p->u.medium.data;
last = (struct block *)((char *)p + PAGE_SIZE - sizeof(struct block));
#ifdef BIBOP_DEBUG
first->bmagic = BMAGIC;
last->bmagic = BMAGIC;
#endif
first->busy = 0;
first->next = last;
last->busy = 0;
last->next = 0;
insfree(first, 0);
#if 0
p->u.medium.maxfree = OBJSIZE(first);
#endif
}
/* Do a non-small allocation */
static void *
bigmalloc(unsigned int size)
{
struct descr *p;
struct block *cur, *next;
int cursize;
if (size > PAGE_SIZE - sizeof(struct descr) - ALIGNMENT - PTR_SIZE) {
/* really big! */
int n = (size + sizeof(struct descr) + PAGE_SIZE - 1) / PAGE_SIZE;
struct descr *bigp = pages(n);
if (!bigp)
return 0;
#ifdef USE_SWAP
used_memory += n * PAGE_SIZE; /* for the swap to know */
#endif
p_big += n;
bigp->magic = BIGMAGIC;
bigp->u.big.npages = n;
m_big++;
s_big += size;
return (void *)&bigp->u.big.data;
}
#if 0
/* find first page with enough space */
for(p = firstpage; p; p = p->next) {
if (p->u.medium.freecnt == 0 || p->u.medium.maxfree && p->u.medium.maxfree < size)
continue;
for(cur = (struct block *)&p->u.medium.data; cur->next; cur = cur->next) {
if (cur->busy)
continue;
next = cur->next;
cursize = OBJSIZE(cur);
if (cursize > p->u.medium.maxfree)
p->u.medium.maxfree = cursize;
if (cursize >= size)
goto found;
}
}
#else
{
/* find first block which is big enough */
int i;
for(i = 0; i < NFREE; i++) {
if (freehead[i].maxsize > size) {
struct freeblk *fp;
for(fp = freehead[i].h.fwd; fp != &freehead[i].h; fp = fp->fwd) {
cur = DATA_TO_OBJ(fp);
cursize = OBJSIZE(cur);
if (cursize >= size) {
p = (struct descr *)((PTR)cur & PAGEMASK);
goto found;
}
}
freehead[i].nskip++;
}
}
}
#endif
/* No page had a block that was big enough, get a new one. */
p = pages(1);
if (!p)
return 0;
p_alloc++;
init_allocpage(p);
p->dnext = firstpage;
firstpage = p;
cur = (struct block *)&p->u.medium.data;
cursize = OBJSIZE(cur);
found:
#ifdef BIBOP_DEBUG
if (cur->bmagic != BMAGIC) {
fprintf(stderr, "bad magic 2\n");
abort();
}
#endif
#if 0
p->u.medium.freecnt--; /* used one free */
#endif
FDEL(&cur->u.fb); /* remove from free lists */
#ifdef FREESTAT
cur->u.fb.head->nalloc++;
{
int i;
for(i = 0; i < NFREE && freehead[i].maxsize < size; i++)
;
#ifdef PARANOIA
if (i == NFREE)
abort();
#endif
freehead[i].nreal++;
if (cur == (struct block *)&p->u.medium.data && cur->next->next == 0)
freehead[i].nwhy++;
}
#endif
if (size + SIZE_SLOP < cursize) {
/* we have to split the current block */
next = (struct block *)((char *)cur + size + sizeof(struct block));
#ifdef BIBOP_DEBUG
next->bmagic = BMAGIC;
#endif
next->busy = 0;
#ifdef PARANOIA
if ((struct descr *)((PTR)cur->next & PAGEMASK) != p)
abort();
#endif
next->next = cur->next;
cur->next = next;
#ifdef PARANOIA
if ((struct descr *)((PTR)cur->next & PAGEMASK) != p)
abort();
#endif
#if 0
p->u.medium.freecnt++; /* split one into two */
if (p->u.medium.maxfree == cursize)
p->u.medium.maxfree = OBJSIZE(next);
#endif
insfree(next, 1); /* insert second half */
}
cur->busy = 1;
m_alloc++;
s_alloc += size;
#if 0
if (p->u.medium.maxfree == cursize)
p->u.medium.maxfree = 0;
#endif
#ifdef USE_SWAP
used_memory += OBJSIZE(cur); /* for the swap to know */
#endif
return (void *)&cur->u.data;
}
/* Table of the bit number of the last bit set in a byte. */
static int flsb[] = {
-1,0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
};
/* External interface */
void *
malloc(unsigned int size)
{
register struct descr *bp;
register int i, j;
register mapword m;
size = CEIL(size);
if (!initdone) {
/* Fake it if this is an early malloc. */
return sbrk(size);
}
if (size >= SMALL_SIZE)
return bigmalloc(size);
for(bp = bibops[size/ALIGNMENT - 1]; bp && bp->u.bibop.objfree == 0; bp = bp->dnext)
;
if (!bp) {
/* Add a new page */
bp = newbibop(size);
if (!bp)
return 0;
bp->dnext = bibops[size/ALIGNMENT - 1];
bibops[size/ALIGNMENT - 1] = bp;
}
/* locate word with free block */
for(i = bp->u.bibop.nextfree; ;) {
m = bp->u.bibop.freemap[i];
if (m)
break;
if (++i >= bp->u.bibop.maxfree)
i = 0;
#ifdef PARANOIA
if (i == bp->u.bibop.nextfree) {
/* Help! We've wrapped around without finding the promised free block! */
fprintf(stderr, "bmalloc wrapped around, size = %d\n", size);
abort();
}
#endif
}
bp->u.bibop.nextfree = i;
/* locate bit within the word */
#define ONES (~(mapword)0)
j = 0;
if ((m & (ONES >> (BITS_PER_MAPWORD/2))) == 0)
j += BITS_PER_MAPWORD/2, m >>= BITS_PER_MAPWORD/2;
else
m &= (ONES >> (BITS_PER_MAPWORD/2));
if ((m & (ONES >> (3*BITS_PER_MAPWORD/4))) == 0)
j += BITS_PER_MAPWORD/4, m >>= BITS_PER_MAPWORD/4;
else
m &= (ONES >> (3*BITS_PER_MAPWORD/4));
if ((m & (ONES >> (7*BITS_PER_MAPWORD/8))) == 0)
j += BITS_PER_MAPWORD/8, m >>= BITS_PER_MAPWORD/8;
else
m &= (ONES >> (7*BITS_PER_MAPWORD/8));
/* We're down to at most 8 bits now (if there are <= 64 bits in a word).
Use a table to look up the last bit set.
*/
j += flsb[m];
bp->u.bibop.freemap[i] &= ~ ((mapword)1<<j); /* mark as allocated */
bp->u.bibop.objfree--; /* one less free */
#ifdef USE_SWAP
used_memory += bp->u.bibop.objsize;
#endif
m_bibop++;
s_bibop += size;
return (void *) ((char *)bp->u.bibop.objs + (i * BITS_PER_MAPWORD + j) * size);
}
/* External interface */
void
free(void *ptr)
{
register struct descr *bp;
register unsigned int size, offs;
int i, j;
if (!initdone)
return;
bp = (struct descr *)((PTR)ptr & PAGEMASK);
if (bp->magic == BIGMAGIC) {
/* freeing really big block, stuff all pages on free list */
int n = bp->u.big.npages;
#ifdef USE_SWAP
used_memory -= n * PAGE_SIZE; /* for the swap to know */
#endif
insertfreepage(bp);
f_big++;
p_big -= n;
p_free += n;
} else if (bp->magic == ALLOCMAGIC) {
/* freeing part of a page */
struct block *this, *cur, *next;
int cursize;
#ifdef USE_SWAP
used_memory -= OBJSIZE(DATA_TO_OBJ(ptr)); /* for the swap to know */
#endif
#ifdef BIBOP_DEBUG
if (DATA_TO_OBJ(ptr)->bmagic != BMAGIC) {
fprintf(stderr, "bad magic 3\n");
abort();
}
#endif
this = DATA_TO_OBJ(ptr);
this->busy = 0;
#if 0
bp->u.medium.freecnt++; /* another free */
#endif
insfree(this, 2);
/* coalescing is tedious since we don't have back pointers */
for(cur = (struct block *)&bp->u.medium.data; cur->next; cur = cur->next)
if (cur == this || cur->next == this && !cur->busy)
break;
#ifdef PARANOIA
if (!cur->next || cur->busy)
abort();
#endif
/* coalesce free blocks (max 3) */
for(;;) {
next = cur->next;
#ifdef BIBOP_DEBUG
if (next->bmagic != BMAGIC) {
fprintf(stderr, "bad magic 1\n");
abort();
}
#endif
if (!next->next || next->busy)
break;
cur->next = next->next;
#ifdef BIBOP_DEBUG
next->bmagic = 0;
#endif
#ifdef PARANOIA
if ((struct descr *)((PTR)cur->next & PAGEMASK) != bp)
abort();
#endif
#if 0
bp->u.medium.freecnt--; /* joined two free into one */
#endif
#ifdef FREESTAT
cur->u.fb.head->njoin1++;
next->u.fb.head->njoin2++;
#endif
FDEL(&cur->u.fb);
FDEL(&next->u.fb);
insfree(cur, 3);
}
cursize = OBJSIZE(cur);
#if 0
if (cursize > bp->u.medium.maxfree)
bp->u.medium.maxfree = cursize;
#endif
if (((struct block *)&bp->u.medium.data)->next->next == 0) {
/* The whole page is free now, move it to free list */
struct descr **p;
struct block *blk = (struct block *)&bp->u.medium.data;
FDEL(&blk->u.fb);
#ifdef FREESTAT
blk->u.fb.head->ndrop++;
#endif
for(p = &firstpage; *p != bp; p = &(*p)->dnext)
;
*p = (*p)->dnext;
bp->u.big.npages = 1;
insertfreepage(bp);
p_free++;
p_alloc--;
}
f_alloc++;
} else if (bp->magic == BIBOPMAGIC) {
offs = ((char *)ptr - (char *)bp->u.bibop.objs) / bp->u.bibop.objsize; /* block offset from first block */
i = offs / BITS_PER_MAPWORD;
j = offs % BITS_PER_MAPWORD;
bp->u.bibop.freemap[i] |= (mapword)1<<j; /* mark as free */
bp->u.bibop.nextfree = i; /* we have a free block here */
bp->u.bibop.objfree++; /* one more free */
f_bibop++;
#ifdef USE_SWAP
used_memory -= bp->u.bibop.objsize;
#endif
} else {
/* Happens when freeing prematurely allocated objects. */
fprintf(stderr, "Warning, bad magic number in free %x\n", bp->magic);
}
}
/* Figure out (maximum) object size. */
static unsigned int
objsize(void *ptr)
{
register struct descr *bp;
bp = (struct descr *)((PTR)ptr & PAGEMASK);
if (bp->magic == BIGMAGIC) {
return bp->u.big.npages * PAGE_SIZE;
} else if (bp->magic == ALLOCMAGIC) {
return OBJSIZE(DATA_TO_OBJ(ptr));
} else if (bp->magic == BIBOPMAGIC) {
return bp->u.bibop.objsize;
} else {
return -1;
}
}
/* External interface */
void *
realloc(void *old, unsigned int size)
{
void *new;
int osize;
struct descr *bp;
bp = (struct descr *)((PTR)old & PAGEMASK);
switch (bp->magic)
{
case BIGMAGIC:
osize = bp->u.big.npages * PAGE_SIZE;
break;
case ALLOCMAGIC:
osize = OBJSIZE(DATA_TO_OBJ(old));
break;
case BIBOPMAGIC:
osize = bp->u.bibop.objsize;
break;
default:
fprintf(stderr, "Bad magic number in free %x\n", bp->magic);
}
if (osize > size)
osize = size;
/* Always assume the worst and allocate© */
new = malloc(size);
if (!new)
return 0;
memcpy(new, old, osize);
free(old);
return new;
}
/* Allocate and initialize a new bibop page. */
static struct descr *
newbibop(size)
unsigned int size;
{
struct descr *bp;
int nobj, nmap, nnmap;
int i, j;
/* fprintf(stderr, "newbibop %d\n", size);*/
bp = pages(1);
if (!bp)
return 0;
p_bibop++;
/* I'm to lazy to figure out the exact formula. Iterate at runtime instead. */
for(nmap = 0, nnmap = -1; nmap != nnmap;) {
nobj = (PAGE_SIZE - sizeof(struct descr) - nmap * sizeof(mapword) - 2 * ALIGNMENT) / size;
nnmap = nmap;
nmap = (nobj + BITS_PER_MAPWORD - 1) / BITS_PER_MAPWORD;
}
bp->magic = BIBOPMAGIC;
bp->u.bibop.objsize = size;
bp->u.bibop.objfree = nobj;
bp->u.bibop.maxobjfree = nobj;
bp->u.bibop.freemap = (void *) ((char *)bp + CEIL(sizeof(struct descr)));
bp->u.bibop.nextfree = 0;
bp->u.bibop.maxfree = nmap;
bp->u.bibop.objs = (void *) ((char *)bp->u.bibop.freemap + CEIL(nmap * sizeof(mapword)));
bp->dnext = 0;
/* fill the freemap */
for(i = 0; i < nmap-1; i++)
bp->u.bibop.freemap[i] = ~0;
j = nobj % BITS_PER_MAPWORD; /* no of bits needed in last word, or 0 all are needed */
if (j)
bp->u.bibop.freemap[i] = ((mapword)~0) >> (BITS_PER_MAPWORD - j);
else
bp->u.bibop.freemap[i] = ~0;
return bp;
}
/* External interface. Should be called before first malloc. */
void
bibop_init()
{
int mins, maxs;
double sfact, smult, s;
int i;
initdone++;
/* set up nextpage to point to space at a page boundary */
firstsbrk = nextpage = (char *)( ( (PTR)sbrk(PAGE_SIZE+1) & PAGEMASK) + PAGE_SIZE );
mins = SMALL_SIZE;
maxs = PAGE_SIZE;
sfact = (double)maxs / mins;
smult = exp(log(sfact) / NFREE);
for(s = smult, i = 0; i < NFREE; i++, s *= smult) {
freehead[i].h.fwd = &freehead[i].h;
freehead[i].h.bwd = &freehead[i].h;
freehead[i].maxsize = (int) (mins * s);
/*fprintf(stderr, "bucket %d holds size <%d\n", i, freehead[i].maxsize);*/
#ifdef FREESTAT
freehead[i].h.head = &freehead[i];
#endif
}
}
/* External interface. Show statistics. */
char *
dump_malloc_data()
{
static char mbuf[3000];
int u_bibop, u_alloc, u_big, n_bibop, n_alloc, n_big, a_bibop, a_alloc, a_big;
struct descr *p;
int i, n;
u_bibop = u_alloc = u_big = n_bibop = n_alloc = n_big = a_bibop = a_alloc = a_big = 0;
for(i = 0; i < (SMALL_SIZE+ALIGNMENT-1)/ALIGNMENT; i++) {
for(p = bibops[i]; p; p = p->dnext) {
n = p->u.bibop.objfree * p->u.bibop.objsize;
n_bibop += n;
u_bibop += PAGE_SIZE - n;
a_bibop += p->u.bibop.objfree;
}
}
for(p = firstpage; p; p = p->dnext) {
struct block *q;
for(q = (struct block *)&p->u.medium.data; q->next; q = q->next) {
if (q->busy)
u_alloc += OBJSIZE(q);
else
n_alloc += OBJSIZE(q), a_alloc++;
}
}
u_big = PAGE_SIZE * p_big;
sprintf(mbuf, "\
%-17s %10s %10s %10s %10s\n\
%-17s %10d %10d %10d %10d\n\
%-17s %10d %10d %10d %10d (%d in free pages)\n\
%-17s %10d %10d %10d %10d\n\
%-17s %10d %10d %10d %10d\n\
%-17s %10d %10d %10d %10d (%d free) = %d bytes (page=%d)\n\
\n\
%-17s %10d %10d %10d %10d\n\
%-17s %10d %10d %10d %10d\n\
%-17s %10ld %10ld %10ld %10ld\n\
\n\
sbrk requests: %d %d (a) \n\
",
"", "small", "medium", "large", "total",
"used memory", u_bibop, u_alloc, u_big, u_bibop+u_alloc+u_big,
"free memory", n_bibop, n_alloc, n_big, n_bibop+n_alloc+n_big+p_free*PAGE_SIZE, p_free*PAGE_SIZE,
"used blocks", m_bibop-f_bibop, m_alloc-f_alloc, m_big-f_big, m_bibop+m_alloc+m_big-(f_bibop+f_alloc+f_big),
"free blocks", a_bibop, a_alloc, a_big, a_bibop + a_alloc + a_big,
"allocated pages", p_bibop, p_alloc, p_big, p_bibop+p_alloc+p_big+p_free+1, p_free, (p_bibop+p_alloc+p_big+p_free+1)*PAGE_SIZE, PAGE_SIZE,
"# of malloc()", m_bibop, m_alloc, m_big, m_bibop+m_alloc+m_big,
"# of free()", f_bibop, f_alloc, f_big, f_bibop+f_alloc+f_big,
"total allocation", s_bibop, s_alloc, s_big, s_bibop+s_alloc+s_big,
p_bibop+p_alloc+p_big+p_free+1, (p_bibop+p_alloc+p_big+p_free+1)*PAGE_SIZE);
#ifdef FREESTAT
{
char xxxxx[2000];
int k, tf;
strcpy(xxxxx, "medium sizes:\n size unus split free join alloc join1 join2 drop real why skip\n");
for(tf = 0, k = 0; k < NFREE; k++) {
struct freeblk *p;
int s;
for(s = 0, p = freehead[k].h.fwd; p != &freehead[k].h; p = p->fwd, s++)
;
sprintf(xxxxx+strlen(xxxxx), "%5d %4d %6d %6d %6d %6d %5d %5d %4d %5d %3d %5d\n",
freehead[k].maxsize, s,
freehead[k].nsplit, freehead[k].nfree, freehead[k].njoin,
freehead[k].nalloc, freehead[k].njoin1, freehead[k].njoin2, freehead[k].ndrop,
freehead[k].nreal, freehead[k].nwhy, freehead[k].nskip);
tf += s;
}
sprintf(xxxxx+strlen(xxxxx), "tot=%d(%d)\n", tf, a_alloc);
strcat(mbuf, xxxxx);
}
#endif
return mbuf;
}
#endif /* MALLOC_bibop */