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>