Date: Sat, 22 Jul 1995 15:06:25 -0700 (PDT) From: Poul-Henning Kamp <phk> To: hackers@freebsd.org Subject: Please try this new malloc(3) Message-ID: <199507222206.PAA06101@freefall.cdrom.com>
next in thread | raw e-mail | index | archive | help
Hi Gang,
Here is a new (old actually) malloc that I have made. I belive it is
fully working and functional.
The performance seems to be comparable to the gnu malloc, (generally
marginally better I think :-) and the copyright is a lot more permissive.
In particular I'm interested in hearing what it does to a X-server, and
any problems it causes there or other places.
It doesn't use sbrk(2) to get memory, but rather mmap(2), since this
allows pages to be returned to the kernel's freepool again. This means
less memory consumed, less paging and so on. (this also means that
you cannot call sbrk/brk too destructively, and that's why I emulate them.)
Please send me all your results, so I can see if this holds water.
I need to make sure that all the comments make sense, so don't be surprised
if they say something weird.
If people generally don't complain, then I think it is a suitable
replacement for the current malloc in freebsd, which it runs circles
around.
Poul-Henning
/*
* ----------------------------------------------------------------------------
* "THE BEER-WARE LICENSE" (Revision 42):
* <phk@login.dknet.dk> 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
#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
# define __inline /* */
#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
*/
#ifdef malloc_pagesize
#define malloc_pagemask ((malloc_pagesize)-1)
#define malloc_maxsize ((malloc_pagesize)>>1)
#else
static unsigned malloc_pagesize;
#endif /* malloc_pagesize */
/*
* Bitmask to find offset in page
*/
#ifndef malloc_pagemask
static unsigned malloc_pagemask;
#endif /* malloc_pagemask */
/*
* malloc_pagesize == 1 << malloc_pageshift
*/
#ifndef malloc_pageshift
static unsigned malloc_pageshift;
#endif /* malloc_pageshift */
/*
* The smallest allocation we bother about.
* See comments in malloc_init() for details.
* 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 page we care about.
* This is also the "brk()/sbrk()" point
*/
static u_long malloc_lastpage;
/*
* 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
#define NFP 10
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 %ld x %ld @ %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",malloc_lastpage,malloc_lastpage << malloc_pageshift);
fprintf(fd,"Break\t%ld\n",(u_long)sbrk(0) >> malloc_pageshift);
}
#endif /* DEBUG */
/*
* Allocate a number of pages from the OS
*/
static __inline caddr_t
map_pages(void *where, int pages)
{
caddr_t result;
if (!where) {
where = (void*)(malloc_lastpage << malloc_pageshift);
malloc_lastpage += pages;
}
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 __inline 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);
}
/*
* Set entry in page directory.
* Extend page directory if need be.
*/
static __inline 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);
page_dir[index] = info;
return 1;
}
/*
* Initialize the world
*/
static void
malloc_init ()
{
int i;
extern char end;
#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_pagemask
/* and how many bits are left */
malloc_pagemask = malloc_pagesize - 1;
#endif /* malloc_pagemask */
#ifndef malloc_maxsize
/* we will allocate whole pages if bigger than: */
malloc_maxsize = malloc_pagesize >> 1;
#endif /* malloc_maxsize */
#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 */
malloc_lastpage = ((u_long)&end + malloc_pagesize-1) >> malloc_pageshift;
/* 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 + (malloc_lastpage - malloc_origo);
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 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;
#ifdef SANITY
if (bp->size < malloc_minsize || bp->size > malloc_maxsize)
wrterror("sanity: chunk has abnormal size.\n");
#endif /* SANITY */
/* 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 __inline *
malloc_bytes(size_t size)
{
int j;
/* Find the right bucket */
if (size < malloc_minsize)
size = malloc_minsize;
j = fls((size)-1);
#ifdef EXTRA_SANITY
if (size > (1<<j))
wrterror("extra sanity: choose to small chunk\n");
else if (size < (1<<(j-1)))
wrterror("extra sanity: choose to big chunk\n");
#endif
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;
}
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 && ptr) {
if (osize < size)
memcpy(p,ptr,osize);
else
memcpy(p,ptr,size);
free(ptr);
}
return p;
}
static void
free_pages(void *ptr)
{
u_long page;
int i,j,index;
#ifdef SANITY
if ((u_long)ptr & malloc_pagemask)
wrterror("sanity: freeing messed up page pointer.\n");
#endif /* SANITY */
page = (u_long)ptr >> malloc_pageshift;
index = page - malloc_origo;
/* Count how many pages it is */
for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++)
;
#ifdef NFP
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;
}
void
free(void *ptr)
{
u_long page;
struct pginfo *info;
int i,index;
struct pginfo **mp;
if (!initialized)
malloc_init();
page = (u_long)ptr >> malloc_pageshift;
index = page - malloc_origo;
info = page_dir[index];
if (info == MALLOC_FIRST)
return free_pages(ptr);
#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: bit already set.\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_pages(info->page);
} else {
free_pages(info->page);
free(info);
}
}
char *
brk(const char *ptr)
{
if (!initialized)
malloc_init();
wrterror("botch: somebody called brk(). (Don't!)\n");
return 0;
}
#ifndef NOSBRK
char *
sbrk(int delta)
{
if (!initialized)
malloc_init();
if (delta)
wrterror("botch: somebody called sbrk(!=0). (Don't)\n");
return (void*) (malloc_lastpage << malloc_pageshift);
}
#endif /* NOSBRK */
#ifdef MAIN
/* TEST STUFF */
#define NBUCKETS 2000
#define NOPS 1000000
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]) {
/*
printf("%6d F [%4d] %8p\n",i,j,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);
/*
printf("%6d M [%4d] %8p %d\n",i,j,foo[j],k);
*/
}
}
for (j = 0 ; j < NBUCKETS ; j++) {
if (foo[j]) {
/*
printf("%6d F [%4d] %8p\n",i,j+malloc_origo,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?199507222206.PAA06101>