From owner-freebsd-hackers  Mon Jul 24 03:32:04 1995
Return-Path: hackers-owner
Received: (from majordom@localhost)
          by freefall.cdrom.com (8.6.11/8.6.6) id DAA14626
          for hackers-outgoing; Mon, 24 Jul 1995 03:32:04 -0700
Received: (from phk@localhost)
          by freefall.cdrom.com (8.6.11/8.6.6) id DAA14618
          for hackers@freebsd.org; Mon, 24 Jul 1995 03:32:03 -0700
From: Poul-Henning Kamp <phk>
Message-Id: <199507241032.DAA14618@freefall.cdrom.com>
Subject: new malloc.c please test
To: hackers@freebsd.org
Date: Mon, 24 Jul 1995 03:32:03 -0700 (PDT)
X-Mailer: ELM [version 2.4 PL24]
Content-Type: text
Content-Length: 18823     
Sender: hackers-owner@freebsd.org
Precedence: bulk


OK, here is the next version of my "new" malloc.c  This one is running
in my libc right now, and giving no problems so far.

Please give it a whirl:
	cp malloc.c /usr/src/lib/libc/stdlib
	cd /usr/src/lib/libc
	make all install

In particular I am very interested in data regarding performance, time and
resource wise compared to the regular malloc in libc, -lgnumalloc and so
on.  If some of you could roll it into a Xserver I would be very interested
in the results, and likewise what impact it has on "make world" kind of 
things.

If you compile with -DSANITY it will core-dump the program if it detects 
bad pointers or metadata.

If you have time, you can try to fiddle with the "NFP" definition, and
see what it buys you.

Please email all results to me.

Poul-Henning

/*

/*
 * ----------------------------------------------------------------------------
 * "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
    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 ?