diff options
Diffstat (limited to 'libc/stdlib/malloc/malloc.c')
| -rw-r--r-- | libc/stdlib/malloc/malloc.c | 765 |
1 files changed, 765 insertions, 0 deletions
diff --git a/libc/stdlib/malloc/malloc.c b/libc/stdlib/malloc/malloc.c new file mode 100644 index 000000000..1a0b61aa5 --- /dev/null +++ b/libc/stdlib/malloc/malloc.c @@ -0,0 +1,765 @@ +/* + mmalloc - heap manager based on heavy use of virtual memory management. + Copyright (C) 1998 Valery Shchedrin + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + MA 02111-1307, USA + + Public Functions: + + void *mmalloc(size_t size); + + Allocates `size` bytes + returns NULL if no free memory available + + void *mcalloc(size_t unit, size_t quantity); + + Allocates `quantity*unit` zeroed bytes via internal malloc call + + void *mrealloc(void *ptr, size_t size); + + Reallocates already allocated block `ptr`, if `ptr` is not valid block + then it works as malloc. NULL is returned if no free memory available + + void *mrealloc_no_move(void *ptr, size_t size); + + Reallocates already allocated block `ptr`, if `ptr` is not valid block + or if reallocation can't be done with shrinking/expanding already + allocated block NULL is returned + + void mfree(void *ptr); + + Frees already allocated block, if `ptr` is incorrect one nothing will + happen. +*/ + +#define _POSIX_SOURCE +#define _XOPEN_SOURCE +#include <sys/types.h> +#include <unistd.h> +#include <limits.h> +#include <sys/time.h> +#include <asm/page.h> +#include <unistd.h> +#include <sys/mman.h> +#include <string.h> +#include "malloc.h" + + +#define M_DOTRIMMING 1 +#define M_MULTITHREADED 0 + +#define VALLOC_MSTART ((void*)0x1c000000) +#define LARGE_MSTART ((void*)0x19000000) +#define HUNK_MSTART ((void*)0x18000000) +#define HUNK_MSIZE M_PAGESIZE +#define HUNK_ID 0x99171713 + +/* alignment of allocations > HUNK_THRESHOLD */ +#define MALLOC_ALIGN 4 + +/* allocations < HUNK_THRESHOLD will not be aligned */ +#define HUNK_THRESHOLD 4 + +/*up to HUNK_MAXSIZE blocks will be joined together to decrease memory waste*/ +#define HUNK_MAXSIZE 128 + +/* returns value not less than size, aligned to MALLOC_ALIGN */ +#define ALIGN(size) (((size)+(MALLOC_ALIGN)-1)&(~((MALLOC_ALIGN)-1))) + +/* aligns s or p to page boundaries */ +#define PAGE_ALIGN(s) (((s)+M_PAGESIZE-1)&(~(M_PAGESIZE-1))) +#define PAGE_ALIGNP(p) ((char*)PAGE_ALIGN((unsigned)(p))) +#define PAGE_DOWNALIGNP(p) ((char*)(((unsigned)(p))&(~(M_PAGESIZE-1)))) + +/* returns v * 2 for your machine (speed-up) */ +#define MUL2(v) ((v)*2) + +/* does v *= 8 for your machine (speed-up) */ +#define EMUL8(v) v*=8 + +/* does v/8 for your machind (speed-up) */ +#define DIV8(v) ((v)/8) + +#if M_MULTITHREADED +#error This version does not support threads +#else +typedef int mutex_t; +#define mutex_lock(x) +#define mutex_unlock(x) +#define mutex_init(x) +#define MUTEX_INITIALIZER 0 +#endif + +static int mmalloc_initialized = -1; + /* -1 == uninitialized, 0 == initializing, 1 == initialized */ + +static mutex_t malloc_lock = MUTEX_INITIALIZER; + +#ifndef MAP_FAILED +#define MAP_FAILED ((void*)-1) +#endif + +#if defined(MAP_ANONYMOUS) && !defined(MAP_ANON) +#define MAP_ANON MAP_ANONYMOUS +#endif + +#ifndef NULL +#define NULL ((void*)0) +#endif + +/* guess pagesize */ +#ifndef M_PAGESIZE + #ifdef _SC_PAGESIZE + #ifndef _SC_PAGE_SIZE + #define _SC_PAGE_SIZE _SC_PAGESIZE + #endif + #endif + #ifdef _SC_PAGE_SIZE + #define M_PAGESIZE sysconf(_SC_PAGE_SIZE) + #else /* !_SC_PAGESIZE */ + #if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE) + extern size_t getpagesize(); + #define M_PAGESIZE getpagesize() + #else /* !HAVE_GETPAGESIZE */ + #include <sys/param.h> + #ifdef EXEC_PAGESIZE + #define M_PAGESIZE EXEC_PAGESIZE + #else /* !EXEC_PAGESIZE */ + #ifdef NBPG + #ifndef CLSIZE + #define M_PAGESIZE NBPG + #else /* !CLSIZE */ + #define M_PAGESIZE (NBPG*CLSIZE) + #endif /* CLSIZE */ + #else + #ifdef NBPC + #define M_PAGESIZE NBPC + #else /* !NBPC */ + #ifdef PAGESIZE + #define M_PAGESIZE PAGESIZE + #else /* !PAGESIZE */ + #define M_PAGESIZE 4096 + #endif /* PAGESIZE */ + #endif /* NBPC */ + #endif /* NBPG */ + #endif /* EXEC_PAGESIZE */ + #endif /* HAVE_GETPAGESIZE */ + #endif /* _SC_PAGE_SIZE */ +#endif /* defined(M_PAGESIZE) */ + +/* HUNK MANAGER */ + +typedef struct Hunk_s Hunk_t; + +struct Hunk_s { /* Hunked block - 8 byte overhead */ + int id; /* unique id */ + unsigned int total:12, used:12, size : 8; + Hunk_t *next; /* next free in free_h */ +}; + +static Hunk_t *free_h[HUNK_MAXSIZE+1]; /* free hash */ +int total_h[HUNK_MAXSIZE+1]; /* Hunk_t's `total` member */ + +#define usagemap(h) (((unsigned char *)(h))+sizeof(Hunk_t)) +#define hunk_ptr(h) (((char*)(h))+sizeof(Hunk_t)+ALIGN(DIV8(h->total+7))) +#define hunk(h) ((Hunk_t*)(h)) + +/* hunk_alloc allocates <= HUNK_MAXSIZE blocks */ +static void *hunk_alloc(int size) +{ + Hunk_t *p; + unsigned long *cpl; + int i, c; + + if (size >= HUNK_THRESHOLD) size = ALIGN(size); + + /* Look for already allocated hunkblocks */ + if ((p = free_h[size]) == NULL) + { + if ((p = (Hunk_t*)mmap(HUNK_MSTART,HUNK_MSIZE,PROT_READ|PROT_WRITE, + MAP_PRIVATE|MAP_ANON,0,0)) == (Hunk_t*)MAP_FAILED) + return NULL; + memset(p,0,HUNK_MSIZE); + p->id = HUNK_ID; + p->total = total_h[size]; + /* p->used = 0; */ + p->size = size; + /* p->next = (Hunk_t*)NULL; */ + /* memset(usagemap(p), 0, bound); */ + free_h[size] = p; + } + + /* Locate free point in usagemap */ + for (cpl=(unsigned long*)usagemap(p);*cpl==0xFFFFFFFF;cpl++); + i = ((unsigned char *)cpl) - usagemap(p); + if (*(unsigned short*)cpl != 0xFFFF) { + if (*(unsigned char*)cpl == 0xFF) { + c = *(int*)(((unsigned char *)cpl)+1); i++; + } else c = *(int*)(unsigned char *)cpl; + } else { + i+=2; c = *(((unsigned char *)cpl)+2); + if (c == 0xFF) { c = *(int*)(((unsigned char *)cpl)+3); i++; } + } + EMUL8(i); + if ((c & 0xF) == 0xF) { c >>= 4; i+=4; } + if ((c & 0x3) == 0x3) { c >>= 2; i+=2; } + if (c & 1) i++; + + usagemap(p)[DIV8(i)] |= (1 << (i & 7)); /* set bit */ + + /* Increment counter and update hashes */ + if (++p->used == p->total) + { + free_h[p->size] = p->next; + p->next = NULL; + } + return hunk_ptr(p)+i*p->size; +} + +/* hunk_free frees blocks allocated by hunk_alloc */ +static void hunk_free(char *ptr) +{ + unsigned char *up; + int i, v; + Hunk_t *h; + + if (!ptr) return; + + h = (Hunk_t*)PAGE_DOWNALIGNP(ptr); + + /* Validate `ptr` */ + if (h->id != HUNK_ID) return; + v = ptr - hunk_ptr(h); + i = v / h->size; + if (v % h->size != 0 || i < 0 || i >= h->total) return; + + /* Update `usagemap` */ + up = &(usagemap(h)[DIV8(i)]); + i = 1 << (i&7); + if (!(*up & i)) return; + *up ^= i; + + /* Update hunk counters */ + if (h->used == h->total) + { + if (--h->used) + { /* insert into free_h */ + h->next = free_h[h->size]; + free_h[h->size] = h; + } /* else - it will be unmapped */ + } + else + { + if (!--h->used) + { /* delete from free_h - will be bl_freed*/ + Hunk_t *p, *pp; + for (p=free_h[h->size],pp=NULL;p!=h;pp=p,p=p->next); + if (!pp) + free_h[h->size] = p->next; + else + pp->next = p->next; + } + } + + /* Unmap empty Hunk_t */ + if (!h->used) munmap((void*)h,HUNK_MSIZE); +} + +/* BLOCK MANAGER */ + +typedef struct Block_s Block_t; + +struct Block_s /* 32-bytes long control structure (if 4-byte aligned) */ +{ + char *ptr; /* pointer to related data */ + Block_t *next; /* next in free_mem list */ + Block_t *l_free_mem, *r_free_mem; /* left & right subtrees of <free_mem> */ + Block_t *l_ptrs, *r_ptrs; /* left & right subtrees of <ptrs> */ + size_t size; /* size - divided by align */ + + /* packed 4-byte attributes */ +/* { */ + char bal_free_mem : 8; /* balance of <free_mem> subtree */ + char bal_ptrs : 8; /* balance of <ptrs> subtree */ + unsigned int used : 1; /* used/free state of the block */ + unsigned int broken : 1; /* 1 if previous block can't be merged with it */ +/* } */ +}; + +static Block_t *bl_last; /* last mmapped block */ + +#define bl_get() hunk_alloc(sizeof(Block_t)) +#define bl_rel(p) hunk_free((char*)p) + +/* like C++ templates ;-) */ + +#include "avlmacro.h" + +#define FREE_MEM_COMPARE(i,a,b) { i = (a)->size - (b)->size; } +#define PTRS_COMPARE(i,a,b) { i = (a)->ptr - (b)->ptr; } + +Avl_Tree(free_mem,Block_t,free_mem,FREE_MEM_COMPARE) +Avl_Tree(ptrs,Block_t,ptrs,PTRS_COMPARE) + +#define free_mem_root Avl_Root(Block_t, free_mem) +#define ptrs_root Avl_Root(Block_t, ptrs) + +/* pp is freed block */ +#define FREE_MEM_DEL_BLOCK(pp) \ +{ \ + for (p = free_mem_root;;) \ + if (p->size > pp->size) p = p->l_free_mem; \ + else if (p->size < pp->size) p = p->r_free_mem; \ + else break; \ + if (p == pp) \ + { \ + if (pp->next) free_mem_replace(pp->next); \ + else free_mem_del(pp); \ + } \ + else \ + { \ + for (;p->next != pp; p = p->next); \ + p->next = pp->next; \ + } \ +} + +#define FREE_MEM_INS_BLOCK(pp) \ +{ \ + if ((p = free_mem_ins(pp)) != NULL)\ + {\ + pp->next = p->next;\ + p->next = pp;\ + }\ + else pp->next = NULL; \ +} + +/* `b` is current block, `pp` is next block */ +#define COMBINE_BLOCKS(b,pp) \ +{\ + ptrs_del(pp); \ + b->size += pp->size; \ + if (pp == bl_last) bl_last = b; \ + bl_rel(pp); \ +} + +/* initializes new block b */ +#define INIT_BLOCK(b, pppp, sz) \ +{ \ + memset(b, 0, sizeof(Block_t)); \ + b->ptr = pppp; \ + b->size = sz; \ + ptrs_ins(b); \ + FREE_MEM_INS_BLOCK(b); \ +} + +/* `b` is current block, `sz` its new size */ +/* block `b` will be splitted to one busy & one free block */ +#define SPLIT_BLOCK(b,sz) \ +{\ + Block_t *bt; \ + bt = bl_get(); \ + INIT_BLOCK(bt, b->ptr + sz, b->size - sz); \ + b->size = sz; \ + if (bl_last == b) bl_last = bt; \ + bl_uncommit(bt);\ +} + +/* `b` is current block, `pp` is next free block, `sz` is needed size */ +#define SHRINK_BLOCK(b,pp,sz) \ +{\ + FREE_MEM_DEL_BLOCK(pp); \ + pp->ptr = b->ptr + sz; \ + pp->size += b->size - sz; \ + b->size = sz; \ + FREE_MEM_INS_BLOCK(pp); \ + bl_uncommit(pp); \ +} + +static Block_t *bl_mapnew(size_t size) +{ + size_t map_size; + Block_t *pp, *p; + void *pt; + + map_size = PAGE_ALIGN(size); + pt = mmap(LARGE_MSTART,map_size,PROT_READ|PROT_WRITE|PROT_EXEC, + MAP_PRIVATE|MAP_ANON,0,0); + if (pt == MAP_FAILED) return (Block_t*)NULL; + + bl_last = pp = bl_get(); + INIT_BLOCK(pp, (char*)pt, map_size); + pp->broken = 1; + + return pp; +} + +static void bl_uncommit(Block_t *b) +{ + char *u_start, *u_end; + + u_start = PAGE_ALIGNP(b->ptr); + u_end = PAGE_DOWNALIGNP(b->ptr+b->size); + if (u_end <= u_start) return; + +#if M_DOTRIMMING + mmap(u_start,u_end-u_start,PROT_READ|PROT_WRITE|PROT_EXEC, + MAP_PRIVATE|MAP_ANON|MAP_FIXED,0,0); +#endif +} + +/* requested size must be aligned to ALIGNMENT */ +static Block_t *bl_alloc(size_t size) +{ + Block_t *p, *pp; + + /* try to find needed space in existing memory */ + for (p = free_mem_root, pp = NULL;p;) + { + if (p->size > size) { pp = p; p = p->l_free_mem; } + else if (p->size < size) p = p->r_free_mem; + else { pp = p; break; } + } + + if (!pp) + { /* map some memory */ + if (!bl_last) + { /* just do initial mmap */ + pp = bl_mapnew(size); + if (!pp) return NULL; + } + else if (!bl_last->used) + { /* try growing last unused */ + if (mremap(PAGE_DOWNALIGNP(bl_last->ptr), + PAGE_ALIGNP(bl_last->ptr+bl_last->size) - PAGE_DOWNALIGNP(bl_last->ptr), + PAGE_ALIGNP(bl_last->ptr+size)-PAGE_DOWNALIGNP(bl_last->ptr), + 0) == MAP_FAILED) + { /* unable to grow -- initiate new block */ + pp = bl_mapnew(size); + if (!pp) return NULL; + } + else + { + pp = bl_last; + FREE_MEM_DEL_BLOCK(pp); + pp->size = PAGE_ALIGNP(pp->ptr+size) - pp->ptr; + FREE_MEM_INS_BLOCK(pp); + } + } + else + { /* bl_last is used block */ + if (mremap(PAGE_DOWNALIGNP(bl_last->ptr), +PAGE_ALIGNP(bl_last->ptr+bl_last->size)-PAGE_DOWNALIGNP(bl_last->ptr), +PAGE_ALIGNP(bl_last->ptr+bl_last->size+size) - PAGE_DOWNALIGNP(bl_last->ptr), + 0) == MAP_FAILED) + { + pp = bl_mapnew(size); + if (!pp) return NULL; + } + else + { + pp = bl_get(); + INIT_BLOCK(pp,bl_last->ptr+bl_last->size, + PAGE_ALIGNP(bl_last->ptr+bl_last->size+size)-bl_last->ptr-bl_last->size); + bl_last = pp; + } + } + } + + /* just delete this node from free_mem tree */ + if (pp->next) free_mem_replace(pp->next); else free_mem_del(pp); + pp->used = 1; + + if (pp->size - size > MALLOC_ALIGN) + { /* this block can be splitted (it is unused,not_broken) */ + SPLIT_BLOCK(pp,size); + } + + return pp; +} + +static void bl_free(Block_t *b) +{ + Block_t *p, *bl_next, *bl_prev; + + /* Look for blocks before & after `b` */ + for (p = ptrs_root, bl_next = NULL, bl_prev = NULL; p;) + { + if (p->ptr > b->ptr) { bl_next = p; p = p->l_ptrs; } + else if (p->ptr < b->ptr) { bl_prev = p; p = p->r_ptrs; } + else break; + } + if (b->l_ptrs) + for (bl_prev = b->l_ptrs; bl_prev->r_ptrs; bl_prev = bl_prev->r_ptrs); + if (b->r_ptrs) + for (bl_next = b->r_ptrs; bl_next->l_ptrs; bl_next = bl_next->l_ptrs); + + if (bl_next && !bl_next->broken && !bl_next->used) + { + FREE_MEM_DEL_BLOCK(bl_next) + COMBINE_BLOCKS(b,bl_next) + } + + if (bl_prev && !b->broken && !bl_prev->used) + { + FREE_MEM_DEL_BLOCK(bl_prev) + COMBINE_BLOCKS(bl_prev,b) + b = bl_prev; + } + + b->used = 0; + FREE_MEM_INS_BLOCK(b) + bl_uncommit(b); +} + +static void malloc_init(void) +{ + int i, mapsize, x, old_x, gcount; + + mapsize = M_PAGESIZE; + + mmalloc_initialized = 0; + bl_last = NULL; + free_mem_root = NULL; + ptrs_root = NULL; + mapsize -= sizeof(Hunk_t); + for (i = 1; i <= HUNK_MAXSIZE; i++) + { + free_h[i] = (Hunk_t*)NULL; + for (x = mapsize/i, gcount = 0, old_x = 0; old_x != x;) + { + old_x = x; + x = (mapsize - ALIGN(DIV8(old_x+7)))/i; + if (gcount > 1 && x*i + ALIGN(DIV8(x+7)) <= mapsize) break; + if (x*i + ALIGN(DIV8(x+7)) > mapsize) gcount++; + } + total_h[i] = x; + } + mutex_init(&malloc_lock); + mmalloc_initialized = 1; +} + +static void *mmalloc(size_t size) +{ + void *p; + + if (size == 0) return NULL; + + if (mmalloc_initialized < 0) malloc_init(); + if (mmalloc_initialized) mutex_lock(&malloc_lock); + + if (size <= HUNK_MAXSIZE) + p = hunk_alloc(size); + else + { + if ((p = bl_alloc(ALIGN(size))) != NULL) + p = ((Block_t*)p)->ptr; + } + + if (mmalloc_initialized) mutex_unlock(&malloc_lock); + + return p; +} + +static void mfree(void *ptr) +{ + Block_t *p, *best; + + if (mmalloc_initialized < 0) return; + if (mmalloc_initialized) mutex_lock(&malloc_lock); + + for (p = ptrs_root, best = NULL;p;) + { + if (p->ptr > (char*)ptr) p = p->l_ptrs; + else { best = p; p = p->r_ptrs; } + } + + if (!best || !best->used || best->ptr != (char*)ptr) + { + hunk_free(ptr); + if (mmalloc_initialized) mutex_unlock(&malloc_lock); + return; + } + + bl_free(best); + + if (mmalloc_initialized) mutex_unlock(&malloc_lock); +} + +static void *mrealloc_no_move(void *ptr, size_t size) +{ + Block_t *p, *best, *next; + + if (size <= HUNK_MAXSIZE) return NULL; + + if (mmalloc_initialized <= 0) return mmalloc(size); + + mutex_lock(&malloc_lock); + + /* Locate block */ + for (p = ptrs_root, best = NULL;p;) + { + if (p->ptr > (char*)ptr) p = p->l_ptrs; + else { best = p; p = p->r_ptrs; } + } + + if (!best || !best->used || best->ptr != (char*)ptr) + { + mutex_unlock(&malloc_lock); + return NULL; + } + + size = ALIGN(size); + + if (size == best->size) + { + mutex_unlock(&malloc_lock); + return ptr; + } + + if (best->r_ptrs) /* get block just after */ + for (next = best->r_ptrs; next->l_ptrs; next = next->l_ptrs); + else + for (p = ptrs_root, next = NULL;p;) + { + if (p->ptr > best->ptr) { next = p; p = p->l_ptrs; } + else if (p->ptr < best->ptr) p = p->r_ptrs; + else break; + } + + if (size < best->size) + { /* shrink block */ + if (!next || next->used || next->broken) + { + if (best->size - size > MALLOC_ALIGN) + { /* do split */ + SPLIT_BLOCK(best,size); + } + } + else + { /* just move border of next block */ + SHRINK_BLOCK(best,next,size); + } + } + else if (next && !next->broken && !next->used) + { /* can expand */ + if (best->size + next->size > size + HUNK_MAXSIZE) + { /* shrink next free block */ + SHRINK_BLOCK(best,next,size); + } + else if (best->size + next->size >= size) + { /* combine blocks (eat next one) */ + FREE_MEM_DEL_BLOCK(next); + COMBINE_BLOCKS(best,next); + } + else + { /* not enough memory in next block */ + mutex_unlock(&malloc_lock); + return NULL; + } + } + else + { /* no next block */ + mutex_unlock(&malloc_lock); + return NULL; + } + mutex_unlock(&malloc_lock); + return best->ptr; +} + +static void *mrealloc(void *ptr, size_t size) +{ + void *tmp; + + tmp = mrealloc_no_move(ptr, size); + + if (!tmp) + { + Block_t *p, *best; + + mutex_lock(&malloc_lock); + + for (p = ptrs_root, best = NULL;p;) + { + if (p->ptr > (char*)ptr) p = p->l_ptrs; + else { best = p; p = p->r_ptrs; } + } + + if (!best || !best->used || best->ptr != (char*)ptr) + { + if (ptr) + { + Hunk_t *h; + h = (Hunk_t*)PAGE_DOWNALIGNP(ptr); + if (h->id == HUNK_ID) + { + mutex_unlock(&malloc_lock); + if ((size >= HUNK_THRESHOLD && ALIGN(size) == h->size) || + size == h->size) return ptr; + if ((tmp = mmalloc(size)) == NULL) return NULL; + mutex_lock(&malloc_lock); + memcpy(tmp,ptr,((size<h->size)?size:h->size)); + hunk_free(ptr); + mutex_unlock(&malloc_lock); + return tmp; + } + } + mutex_unlock(&malloc_lock); + return mmalloc(size); + } + + mutex_unlock(&malloc_lock); + + /* copy whole block */ + if ((tmp = mmalloc(size)) == NULL) return NULL; + memcpy(tmp,ptr,((size<best->size)?size:best->size)); + + mutex_lock(&malloc_lock); + bl_free(best); + mutex_unlock(&malloc_lock); + } + return tmp; +} + +static void *mcalloc(size_t unit, size_t quantity) +{ + void *p; + + unit *= quantity; + + if ((p = mmalloc(unit)) == NULL) return NULL; + memset(p,0,unit); + return p; +} + +/* PUBLIC functions */ + +void *malloc(size_t size) { + return mmalloc(size); +} + +void *calloc(size_t unit, size_t quantity) { + return mcalloc(unit,quantity); +} + +void *realloc(void *ptr, size_t size) { + return mrealloc(ptr,size); +} + +void free(void *ptr) { + return mfree(ptr); +} + + |