Date: Mon, 24 Jul 1995 03:36:39 -0700 (PDT) From: Poul-Henning Kamp <phk> To: phk@freefall.cdrom.com (Poul-Henning Kamp) Cc: hackers@freebsd.org Subject: Re: new malloc.c please test Message-ID: <199507241036.DAA14811@freefall.cdrom.com> In-Reply-To: <199507241032.DAA14618@freefall.cdrom.com> from "Poul-Henning Kamp" at Jul 24, 95 03:32:03 am
next in thread | previous in thread | raw e-mail | index | archive | help
I hate it when this happens,
Here is the right file:
/*
* ----------------------------------------------------------------------------
* "THE BEER-WARE LICENSE" (Revision 42):
* <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
* can do whatever you want with this stuff. If we meet some day, and you think
* this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
* ----------------------------------------------------------------------------
*
* $Id$
*
*/
#if defined(__i386__) && defined(__FreeBSD__)
# warning FreeBSD i386 constants hardcoded.
/* If these weren't defined here, they would be calculated on the fly */
# define malloc_pagesize 4096U
# define malloc_pageshift 12U
# define malloc_minsize 16U
/* Keep this many empty pages around before returning pages to the kernel */
# define NFP 10
/* Save a sbrk(0) call every now and then */
#define curbrk _curbrk
extern char * _curbrk asm ("curbrk");
#endif /* __i386__ && __FreeBSD__ */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <memory.h>
#include <err.h>
#include <sys/types.h>
#include <sys/mman.h>
#ifdef MAIN
# define SANITY
# define DEBUG
#endif /* MAIN */
/*
* This structure describes a page's worth of chunks.
*/
struct pginfo {
struct pginfo *next; /* next on the free list */
void *page; /* Pointer to the page */
u_short size; /* size of this page's chunks */
u_short shift; /* How far to shift for this size chunks */
u_short free; /* How many free chunks */
u_short total; /* How many chunk */
u_long bits[1]; /* Which chunks are free */
};
/*
* How many bits per u_long in the bitmap.
* Change only if not 8 bits/byte
*/
#define MALLOC_BITS (8*sizeof(u_long))
/*
* Magic values to put in the page_directory
*/
#define MALLOC_NOT_MINE ((struct pginfo*) 0)
#define MALLOC_FREE ((struct pginfo*) 1)
#define MALLOC_FIRST ((struct pginfo*) 2)
#define MALLOC_FOLLOW ((struct pginfo*) 3)
#define MALLOC_MAGIC ((struct pginfo*) 4)
/*
* The i386 architecture has some very convenient instructions.
* We might as well use them.
*/
#ifdef __i386__
# warning i386 inline assembly used.
#define ffs _ffs
static __inline int
_ffs(unsigned input)
{
int result;
asm("bsfl %1,%0" : "=r" (result) : "r" (input));
return result+1;
}
#define fls _fls
static __inline int
_fls(unsigned input)
{
int result;
asm("bsrl %1,%0" : "=r" (result) : "r" (input));
return result+1;
}
#define set_bit _set_bit
static __inline void
_set_bit(struct pginfo *pi, int bit)
{
asm("btsl %0,(%1)" :
: "r" (bit & (MALLOC_BITS-1)), "r" (pi->bits+(bit/MALLOC_BITS)));
}
#define clr_bit _clr_bit
static __inline void
_clr_bit(struct pginfo *pi, int bit)
{
asm("btcl %0,(%1)" :
: "r" (bit & (MALLOC_BITS-1)), "r" (pi->bits+(bit/MALLOC_BITS)));
}
#endif __i386__
/*
* Set to one when malloc_init has been called
*/
static unsigned initialized;
/*
* The size of a page.
* Must be a integral multiplum of the granularity of mmap(2).
* Your toes will curl if it isn't a power of two
*/
#define malloc_pagemask ((malloc_pagesize)-1)
/*
* The size of the largest chunk.
* Half a page.
*/
#define malloc_maxsize ((malloc_pagesize)>>1)
/*
* malloc_pagesize == 1 << malloc_pageshift
*/
#ifndef malloc_pageshift
static unsigned malloc_pageshift;
#endif /* malloc_pageshift */
/*
* The smallest allocation we bother about.
* Must be power of two
*/
#ifndef malloc_minsize
static unsigned malloc_minsize;
#endif /* malloc_minsize */
/*
* The largest chunk we care about.
* Must be smaller than pagesize
* Must be power of two
*/
#ifndef malloc_maxsize
static unsigned malloc_maxsize;
#endif /* malloc_maxsize */
/*
* The offset from pagenumber to index into the page directory
*/
static u_long malloc_origo;
/*
* The last index in the page directory we care about
*/
static u_long last_index;
/*
* Pointer to page directory.
* Allocated "as if with" malloc
*/
static struct pginfo **page_dir;
/*
* How many slots in the page directory
*/
static unsigned malloc_ninfo;
/*
* A small cache of pages so we don't call mmap/munmap too much
*/
#ifdef NFP
static void *freepage[NFP];
#endif /* NFP */
static set_pgdir(void *, struct pginfo *);
/*
* Write something to stderr without all the luggage of stdio
*/
static void
wrterror(char *p)
{
char *q = "malloc(): ";
write(2,q,strlen(q));
write(2,p,strlen(p));
abort();
}
#ifdef DEBUG
void
malloc_dump(FILE *fd)
{
struct pginfo **pd;
int i,j;
pd = page_dir;
/* find last touched page */
for(i=malloc_ninfo-1;i>=0;i--)
if (pd[i])
break;
/* print out all the pages */
for(j=0;j<=i;j++) {
fprintf(fd,"%08lx %5d ",(j+malloc_origo) << malloc_pageshift,j);
if (pd[j] == MALLOC_NOT_MINE) {
for(j++;j<=i && pd[j] == MALLOC_NOT_MINE;j++)
;
j--;
fprintf(fd,".. %5d not mine\n", j);
} else if (pd[j] == MALLOC_FREE) {
for(j++;j<=i && pd[j] == MALLOC_FREE;j++)
;
j--;
fprintf(fd,".. %5d free\n", j);
} else if (pd[j] == MALLOC_FIRST) {
for(j++;j<=i && pd[j] == MALLOC_FOLLOW;j++)
;
j--;
fprintf(fd,".. %5d in use\n", j);
} else if (pd[j] < MALLOC_MAGIC) {
fprintf(fd,"(%d)\n", j);
} else {
fprintf(fd,"%p %d x %d @ %p\n",
pd[j],pd[j]->free, pd[j]->size, pd[j]->page);
}
}
/* print out various info */
fprintf(fd,"Minsize\t%d\n",malloc_minsize);
fprintf(fd,"Maxsize\t%d\n",malloc_maxsize);
fprintf(fd,"Pagesize\t%d\n",malloc_pagesize);
fprintf(fd,"Pageshift\t%d\n",malloc_pageshift);
fprintf(fd,"FirstPage\t%ld\n",malloc_origo);
fprintf(fd,"LastPage\t%ld %lx\n",last_index,last_index << malloc_pageshift);
fprintf(fd,"Break\t%ld\n",(u_long)sbrk(0) >> malloc_pageshift);
}
#endif /* DEBUG */
#ifndef curbrk
#define curbrk sbrk(0);
#endif
/*
* Allocate a number of pages from the OS
*/
static caddr_t
map_pages(void *where, int pages)
{
caddr_t result;
if (!where) {
result = curbrk + malloc_pagemask - 1;
result = (caddr_t) ((u_long)result & ~malloc_pagemask);
if (!brk(result + (pages << malloc_pageshift))) {
last_index = ((u_long)result >> malloc_pageshift) - malloc_origo;
return result;
}
} else {
result = mmap(where, pages << malloc_pageshift,
PROT_READ | PROT_WRITE | PROT_EXEC, MAP_ANON, -1, 0);
if (result != (caddr_t) -1)
return result;
}
return 0;
}
/*
* Return pages to the OS if we can
*/
static void
unmap_pages(caddr_t ptr, int pages)
{
if (munmap(ptr, pages << malloc_pageshift))
wrterror("botch: munmap failed. (wild pointer ?)\n");
}
/*
* Set a bit in the bitmap
*/
#ifndef set_bit
static __inline void
set_bit(struct pginfo *pi, int bit)
{
pi->bits[bit/MALLOC_BITS] |= 1<<(bit%MALLOC_BITS);
}
#endif /* set_bit */
/*
* Clear a bit in the bitmap
*/
#ifndef clr_bit
static __inline void
clr_bit(struct pginfo *pi, int bit)
{
pi->bits[bit/MALLOC_BITS] &= ~(1<<(bit%MALLOC_BITS));
}
#endif /* clr_bit */
#ifdef SANITY
#ifndef tst_bit
/*
* Test a bit in the bitmap
*/
static __inline int
tst_bit(struct pginfo *pi, int bit)
{
return pi->bits[bit/MALLOC_BITS] & (1<<(bit%MALLOC_BITS));
}
#endif /* tst_bit */
#endif /* SANITY */
/*
* Find last bit
*/
#ifndef fls
static __inline int
fls(int size)
{
int i = 1;
while (size >>= 1)
i++;
return i;
}
#endif /* fls */
/*
* Extend page directory
*/
static int
extend_page_directory(u_long index)
{
struct pginfo **new,**old;
int i;
/* Make it this many pages */
i = index * sizeof *page_dir;
i /= malloc_pagesize;
i += 2;
/* Get new pages, if you used this much mem you don't care :-) */
new = (struct pginfo**) map_pages(0,i);
if (!new)
return 0;
/* Copy the old stuff */
memset(new, 0, i * malloc_pagesize);
memcpy(new, page_dir,
malloc_ninfo * sizeof *page_dir);
/* register the new size */
malloc_ninfo = i * malloc_pagesize / sizeof *page_dir;
/* swap the pointers */
old = page_dir;
page_dir = new;
/* Mark the pages */
set_pgdir(new,MALLOC_FIRST);
while (--i) {
new += malloc_pagesize;
set_pgdir(new,MALLOC_FOLLOW);
}
/* Now free the old stuff */
free(old);
return 1;
}
/*
* Set entry in page directory.
* Extend page directory if need be.
*/
static int
set_pgdir(void *ptr, struct pginfo *info)
{
u_long index = ((u_long)ptr >> malloc_pageshift) - malloc_origo;
if (index >= malloc_ninfo && !extend_page_directory(index))
return 0;
page_dir[index] = info;
return 1;
}
/*
* Initialize the world
*/
static void
malloc_init ()
{
int i;
#ifndef malloc_pagesize
/* determine our pagesize */
malloc_pagesize = getpagesize();
#endif /* malloc_pagesize */
#ifndef malloc_pageshift
/* determine how much we shift by to get there */
for (i = malloc_pagesize; i > 1; i >>= 1)
malloc_pageshift++;
#endif /* malloc_pageshift */
#ifndef malloc_minsize
/*
* find the smallest size allocation we will bother about.
* this is determined as the smallest allocation that can hold
* it's own pginfo;
*/
i = 2;
for(;;) {
int j;
/* Figure out the size of the bits */
j = malloc_pagesize/i;
j /= 8;
if (j < sizeof(u_long))
j = sizeof (u_long);
if (sizeof(struct pginfo) + j - sizeof (u_long) <= i)
break;
i += i;
}
malloc_minsize = i;
#endif /* malloc_minsize */
/* Allocate one page for the page directory */
page_dir = (struct pginfo **) map_pages(0,1);
if (!page_dir)
wrterror("fatal: my first mmap failed. (check limits ?)\n");
/*
* We need a maximum of malloc_pageshift buckets, steal these from the
* front of the page_directory;
*/
malloc_origo = (u_long) page_dir >> malloc_pageshift;
malloc_origo -= malloc_pageshift;
/* Clear it */
memset(page_dir,0,malloc_pagesize);
/* Find out how much it tells us */
malloc_ninfo = malloc_pagesize / sizeof *page_dir;
/* Plug the page directory into itself */
i = set_pgdir(page_dir,MALLOC_FIRST);
if (!i)
wrterror("fatal: couldn't set myself in the page directory\n");
/* Been here, done that */
initialized++;
}
/*
* Allocate a number of complete pages
*/
void *
malloc_pages(size_t size)
{
void *p,*q;
int i;
struct pginfo **pi,**pe;
/* How many pages ? */
size += (malloc_pagesize-1);
size >>= malloc_pageshift;
/* Look for free pages before asking for more */
pi = page_dir + malloc_pageshift;
pe = page_dir + last_index;
p = 0;
if (size == 1) {
#ifdef NFP
for(i=0;i<NFP;i++)
if (freepage[i]) {
p = freepage[i];
freepage[i] = 0;
goto found;
}
#endif /* NFP */
/* Optimise this case since it's so common */
for (; pi < pe; pi++) {
if (*pi == MALLOC_FREE) {
/* Found a page, now find the pointer to it */
p = (void*)((pi - page_dir + malloc_origo)
<< malloc_pageshift);
break;
}
}
} else {
for (; pi < pe; pi++) {
if (pi[0] != MALLOC_FREE)
continue;
if (pi[size-1] != MALLOC_FREE) {
/* If the last one isn't OK, just move on, nothing in
* between will be any good then */
pi += (size-1);
continue;
}
for(i=1;i<size;i++)
if (pi[i] != MALLOC_FREE) {
pi += i;
goto miss;
}
/* Found the pages we need, now find the pointer to them */
p = (void*)((pi - page_dir + malloc_origo)
<< malloc_pageshift);
break;
miss:
}
}
/* Map the pages again */
p = map_pages(p,size);
/* ENOLUCK */
if (!p)
return 0;
#ifdef NFP
found:
#endif /* NFP */
/* Mark the pages in the directory */
i = set_pgdir(p,MALLOC_FIRST);
if (!i)
return 0;
for (q=p; --size; ) {
q += malloc_pagesize;
i = set_pgdir(q,MALLOC_FOLLOW);
if (!i)
return 0;
}
return p;
}
/*
* Allocate a page of fragments
*/
static __inline int
malloc_make_chunks(int bits)
{
struct pginfo *bp;
void *pp;
int i,k,l;
/* Allocate a new bucket */
pp = malloc_pages(malloc_pagesize);
if (!pp)
return 0;
l = sizeof *bp - sizeof(u_long);
l += sizeof(u_long) *
(((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS);
if ((1<<(bits-1)) <= l) {
bp = (struct pginfo *)pp;
l += (1<<bits);
l--;
l >>= bits;
} else {
bp = (struct pginfo *)malloc(l);
l = 0;
}
if (!bp)
return 0;
i = set_pgdir(pp,bp);
if (!i)
return 0;
bp->size = (1<<bits);
bp->shift = bits;
bp->total = bp->free = malloc_pagesize >> bits;
bp->next = 0;
bp->page = pp;
/* We can safely assume that there is nobody in this chain */
page_dir[bits] = bp;
/* set all valid bits in the bits */
k = bp->total;
i = 0;
for(;k-i >= MALLOC_BITS; i += MALLOC_BITS)
bp->bits[i / MALLOC_BITS] = ~0;
for(; i < k; i++)
set_bit(bp,i);
/* We may have used the first ones already */
for(i=0;i<l;i++) {
clr_bit(bp,i);
bp->free--;
bp->total--;
}
return 1;
}
/*
* Allocate a fragment
*/
static void *
malloc_bytes(size_t size)
{
int j;
/* Find the right bucket */
if (size < malloc_minsize)
size = malloc_minsize;
j = fls((size)-1);
while(1) {
struct pginfo *bp;
bp = page_dir[j];
if (bp) {
register int k;
register u_long *lp = bp->bits;
for (; !*lp; lp++)
;
k = ffs(*lp) - 1;
*lp ^= 1<<k;
bp->free--;
if (!bp->free) {
page_dir[j] = bp->next;
bp->next = 0;
}
k += (lp-bp->bits)*MALLOC_BITS;
return bp->page + (k << bp->shift);
}
if (!malloc_make_chunks(j))
return 0;
}
}
void *
malloc(size_t size)
{
if (!initialized)
malloc_init();
if (size <= malloc_maxsize)
return malloc_bytes(size);
return malloc_pages(size);
}
void *
realloc(void *ptr, size_t size)
{
void *p;
u_long osize;
struct pginfo **mp;
if (!initialized)
malloc_init();
if (ptr && !size) {
free(ptr);
return 0;
}
if (!ptr)
return malloc(size);
mp = &page_dir[((u_long)ptr >> malloc_pageshift) - malloc_origo];
if (*mp == MALLOC_FIRST) {
osize = malloc_pagesize;
while (mp[1] == MALLOC_FOLLOW) {
osize += malloc_pagesize;
mp++;
}
} else {
osize = (*mp)->size;
}
p = malloc(size);
if (p) {
if (osize < size)
memcpy(p,ptr,osize);
else
memcpy(p,ptr,size);
free(ptr);
}
return p;
}
static __inline void
free_pages(void *ptr,u_long page, int index, struct pginfo *info)
{
int i;
#ifdef SANITY
if (info == MALLOC_FREE)
wrterror("sanity: freeing free page.\n");
if (info != MALLOC_FIRST)
wrterror("sanity: freeing wrong page.\n");
if ((u_long)ptr & malloc_pagemask)
wrterror("sanity: freeing messed up page pointer.\n");
#endif /* SANITY */
/* Count how many pages it is */
for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
;
#ifdef NFP
{
int j;
for(j=0;j<NFP;j++)
if (!freepage[j]) {
freepage[j] = ptr;
page_dir[index++] = MALLOC_FREE;
if (!--i)
return;
ptr += malloc_pagesize;
}
}
#endif /* NFP */
/* Hand 'em back to the good 'ol OS */
unmap_pages(ptr,i);
/* Now update the directory */
while(i--)
page_dir[index++] = MALLOC_FREE;
}
static __inline void
free_bytes(void *ptr,u_long page, int index, struct pginfo *info)
{
int i;
struct pginfo **mp;
#ifdef SANITY
if (info <= MALLOC_MAGIC)
wrterror("sanity: freeing something wrong.\n");
if ((u_long)ptr & (info->size - 1))
wrterror("sanity: freeing messed up chunk pointer\n");
#endif /* SANITY */
i = ((u_long)ptr & malloc_pagemask) >> info->shift;
#ifdef SANITY
if (tst_bit(info,i))
wrterror("sanity: freeing free chunk.\n");
#endif /* SANITY */
set_bit(info,i);
info->free++;
mp = page_dir + info->shift;
if (info->free == 1) {
/* Link in front of chain */
info->next = *mp;
*mp = info;
return;
}
if (info->free != info->total)
return;
/*
* This keeps at least one index-page around for each size.
* The benefit is decent considering the overhead (7 pages)
*/
if (!info->next && (page_dir[info->shift] == info))
return;
while (*mp != info)
mp = &((*mp)->next);
*mp = info->next;
set_pgdir(info->page,MALLOC_FIRST);
if((void*)info->page == (void*)info) {
free(info->page);
} else {
free(info->page);
free(info);
}
}
void
free(void *ptr)
{
u_long page;
struct pginfo *info;
int index;
if (!initialized)
malloc_init();
page = (u_long)ptr >> malloc_pageshift;
index = page - malloc_origo;
info = page_dir[index];
if (info < MALLOC_MAGIC)
return free_pages(ptr,page,index,info);
return free_bytes(ptr,page,index,info);
}
#ifdef MAIN
/* TEST STUFF */
#define NBUCKETS 2000
#define NOPS 500000
void *foo[NBUCKETS];
int
main()
{
int i,j,k;
void *bar;
setbuf(stdout,0);
setbuf(stderr,0);
bar = malloc(1);
malloc_dump(stderr);
free(bar);
malloc_dump(stderr);
for (i = 0 ; i < NOPS ; i++) {
j = rand() % NBUCKETS;
if (foo[j]) {
free(foo[j]);
foo[j] = 0;
} else {
k = rand() % malloc_maxsize;
foo[j] = malloc(k);
if (!foo[j])
printf("%6d M [%4d] %8p %d\n",i,j,foo[j],k);
}
}
for (j = 0 ; j < NBUCKETS ; j++) {
if (foo[j]) {
free(foo[j]);
foo[j] = 0;
}
}
malloc_dump(stderr);
for (i = 0 ; i < NOPS ; i++) {
j = rand() % NBUCKETS;
if (foo[j]) {
free(foo[j]);
foo[j] = 0;
} else {
k = rand() % malloc_maxsize;
foo[j] = malloc(k);
if (!foo[j])
printf("%6d M [%4d] %8p %d\n",i,j,foo[j],k);
}
}
for (j = 0 ; j < NBUCKETS ; j++) {
if (foo[j]) {
free(foo[j]);
foo[j] = 0;
}
}
malloc_dump(stderr);
return 0;
}
#endif /* MAIN */
--
Poul-Henning Kamp | phk@FreeBSD.ORG FreeBSD Core-team.
http://www.freebsd.org/~phk | phk@login.dknet.dk Private mailbox.
whois: [PHK] | phk@ref.tfs.com TRW Financial Systems, Inc.
Just that: dried leaves in boiling water ?
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199507241036.DAA14811>