summaryrefslogtreecommitdiff
path: root/libc/stdlib/malloc/malloc.c
diff options
context:
space:
mode:
authorEric Andersen <andersen@codepoet.org>2002-07-18 15:00:07 +0000
committerEric Andersen <andersen@codepoet.org>2002-07-18 15:00:07 +0000
commit35d29fcb08fadaf006561a058746b0fce76a6a74 (patch)
treeb42a59394f8ee7dc7c11f71ae2d45b1e1beb834b /libc/stdlib/malloc/malloc.c
parent3b1e82407a02aed6319c6686c5b06c2051a20cca (diff)
Miles Bader implemented a new mmap based malloc which is much
smarter than the old "malloc-simple", and actually works, unlike the old "malloc". So kill the old "malloc-simple" and the old "malloc" and replace them with Miles' new malloc implementation. Update Config files to match. Thanks Miles!
Diffstat (limited to 'libc/stdlib/malloc/malloc.c')
-rw-r--r--libc/stdlib/malloc/malloc.c961
1 files changed, 94 insertions, 867 deletions
diff --git a/libc/stdlib/malloc/malloc.c b/libc/stdlib/malloc/malloc.c
index 9a3bbb332..317b10840 100644
--- a/libc/stdlib/malloc/malloc.c
+++ b/libc/stdlib/malloc/malloc.c
@@ -1,880 +1,107 @@
/*
- malloc - 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 *malloc(size_t size);
-
- Allocates `size` bytes
- returns NULL if no free memory available
-
- void *calloc(size_t unit, size_t quantity);
-
- Allocates `quantity*unit` zeroed bytes via internal malloc call
-
- void *realloc(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 *_realloc_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 free(void *ptr);
-
- Frees already allocated block, if `ptr` is incorrect one nothing will
- happen.
-*/
-
-/*
- * Manuel Novoa III Jan 2001
+ * libc/stdlib/malloc-zarg/malloc.c -- malloc function
+ *
+ * Copyright (C) 2002 NEC Corporation
+ * Copyright (C) 2002 Miles Bader <miles@gnu.org>
*
- * Modified to decrease object sizes.
- * Broke into independent object files.
- * Converted INIT_BLOCK() and FREE_MEM_DEL_BLOCK() from macros to functions.
+ * This file is subject to the terms and conditions of the GNU Lesser
+ * General Public License. See the file COPYING.LIB in the main
+ * directory of this archive for more details.
+ *
+ * Written by Miles Bader <miles@gnu.org>
*/
-#include <features.h>
-#ifndef _XOPEN_SOURCE
-#define _XOPEN_SOURCE
-#endif
-#include <sys/types.h>
-#include <unistd.h>
-#include <limits.h>
-#include <sys/time.h>
-#include <asm/page.h>
-#include <unistd.h>
+#include <stdlib.h>
#include <sys/mman.h>
-#include <string.h>
-#include "malloc.h"
-#include <stdio.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
-//static mutex_t malloc_lock = MUTEX_INITIALIZER;
-#endif
-
-extern int __malloc_initialized;
-
-#ifdef L__malloc_init
-int __malloc_initialized = -1;
-
- /* -1 == uninitialized, 0 == initializing, 1 == initialized */
-#endif
-
-#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 */
-#define M_PAGESIZE getpagesize()
-
-/* 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 */
-};
-
-#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))
-
-extern Hunk_t *__free_h[HUNK_MAXSIZE + 1];
-extern int __total_h[HUNK_MAXSIZE + 1];
-
-#ifdef L__malloc_init
-Hunk_t *__free_h[HUNK_MAXSIZE + 1]; /* free hash */
-int __total_h[HUNK_MAXSIZE + 1]; /* Hunk_t's `total` member */
-#endif
-
-extern void *__hunk_alloc(int size);
-
-#ifdef L_malloc
-/* __hunk_alloc allocates <= HUNK_MAXSIZE blocks */
-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,
-#ifdef __UCLIBC_HAS_MMU__
- MAP_PRIVATE | MAP_ANONYMOUS
-#else
- MAP_SHARED | MAP_ANONYMOUS
-#endif
- , 0, 0)) == (Hunk_t *) MAP_FAILED)
- // {
- // printf("hunk_alloc failed: %d, %d\n", size, errno);
- 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 */
-
- /* First find a word where not all the bits are set */
- for (cpl = (unsigned long *) usagemap(p); *cpl == 0xFFFFFFFF; cpl++);
-
- /* Remember the byte position of that word */
- i = ((unsigned char *) cpl) - usagemap(p);
-
- /* Now find find a free bit in the word using binary search */
- if (*(unsigned short *) cpl != 0xFFFF) {
-
- if (*(unsigned char *) cpl == 0xFF) {
- c = *(((unsigned char *) cpl) + 1);
- i++;
- }
- else
- {
- c = *(unsigned char *) cpl;
- }
- } else {
- i += 2;
- c = *(((unsigned char *) cpl) + 2);
- if (c == 0xFF) {
- c = *(((unsigned char *) cpl) + 3);
- i++;
- }
- }
-
- /*
- * Multiply i by 8 for the bit position
- * Further down, we divide by 8 again to find the byte position
- */
- EMUL8(i);
-
- /* If bottom nibble is set, shift down the top nibble */
- if ((c & 0xF) == 0xF) {
- c >>= 4;
- i += 4;
- }
-
- /* If bottom 2 bits are set, shift down the top two */
- if ((c & 0x3) == 0x3) {
- c >>= 2;
- i += 2;
- }
-
- /* Check which one of the two bits is set */
- 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;
- }
-
- // fprintf(stderr, "hunk_alloc: i=%d, p->size=%d, p=%p\n", i, p->size, p);
- return hunk_ptr(p) + i * p->size;
-}
-#endif /* L_malloc */
-
-extern void __hunk_free(char *ptr);
-
-#ifdef L__free_support
-/* __hunk_free frees blocks allocated by __hunk_alloc */
-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);
-}
-#endif /* L__free_support */
-
-/* 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 */
-/* { */
- signed char bal_free_mem:8; /* balance of <free_mem> subtree */
- signed 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 */
-/* } */
-};
-
-extern Block_t *__bl_last; /* last mmapped block */
-
-#ifdef L__malloc_init
-Block_t *__bl_last; /* last mmapped block */
-#endif
-
-#define bl_get() __hunk_alloc(sizeof(Block_t))
-#define bl_rel(p) __hunk_free((char*)p)
-
-extern Block_t *__Avl_Block_tfree_mem_tree;
-extern Block_t *__free_mem_ins(Block_t * data);
-extern void __free_mem_del(Block_t * data);
-extern void __free_mem_replace(Block_t * data);
-extern Block_t *__Avl_Block_tptrs_tree;
-extern Block_t *__ptrs_ins(Block_t * data);
-extern void __ptrs_del(Block_t * data);
-
-extern void __bl_uncommit(Block_t * b);
-extern void __bl_free(Block_t * b);
-
-/* like C++ templates ;-) */
-#include "avlmacro.h"
-
-#define FREE_MEM_COMPARE(i,a,b) \
-{ \
- if ( (a)->size < (b)->size ) { \
- i = -1; \
- } else if ( (a)->size > (b)->size ) { \
- i = 1; \
- } else { \
- i = 0; \
- } \
-}
-
-#define PTRS_COMPARE(i,a,b) \
-{ \
- if ( (a)->ptr < (b)->ptr ) { \
- i = -1; \
- } else if ( (a)->ptr > (b)->ptr ) { \
- i = 1; \
- } else { \
- i = 0; \
- } \
-}
-
-#ifdef L__avl_support
-Avl_Tree(free_mem, Block_t, free_mem, FREE_MEM_COMPARE)
- Avl_Tree_no_replace(ptrs, Block_t, ptrs, PTRS_COMPARE)
-#endif
-#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,p) {p = __free_mem_del_block(pp,p);}
-extern Block_t *__free_mem_del_block(Block_t * pp, Block_t * p);
-
-#ifdef L_malloc
-Block_t *__free_mem_del_block(Block_t * pp, Block_t * p)
-{
- 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;
- }
- return p;
-}
-#endif /* L_malloc */
-
-#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) { p = __init_block(b, pppp, sz); }
-
-extern Block_t *__init_block(Block_t * b, char *pppp, size_t sz);
-
-#ifdef L_malloc
-Block_t *__init_block(Block_t * b, char *pppp, size_t sz)
-{
- Block_t *p;
-
- memset(b, 0, sizeof(Block_t));
- b->ptr = pppp;
- b->size = sz;
- __ptrs_ins(b);
- FREE_MEM_INS_BLOCK(b);
- return p;
-}
-#endif /* L_malloc */
-
-/* `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,p); \
- pp->ptr = b->ptr + sz; \
- pp->size += b->size - sz; \
- b->size = sz; \
- FREE_MEM_INS_BLOCK(pp); \
- __bl_uncommit(pp); \
-}
-
-#ifdef L_malloc
-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,
-#ifdef __UCLIBC_HAS_MMU__
- MAP_PRIVATE | MAP_ANONYMOUS
-#else
- MAP_SHARED | MAP_ANONYMOUS
-#endif
- , 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;
-}
-
-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,
-#ifdef __UCLIBC_HAS_MMU__
- MAP_PRIVATE | MAP_ANONYMOUS |MAP_FIXED
-#else
- MAP_SHARED | MAP_ANONYMOUS |MAP_FIXED
-#endif
- , 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, p);
- 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;
-}
-#endif /* L_malloc */
-
-#ifdef L__free_support
-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, p)
- COMBINE_BLOCKS(b, bl_next)
- }
-
- if (bl_prev && !b->broken && !bl_prev->used) {
- FREE_MEM_DEL_BLOCK(bl_prev, p)
- COMBINE_BLOCKS(bl_prev, b)
- b = bl_prev;
- }
-
- b->used = 0;
- FREE_MEM_INS_BLOCK(b)
- __bl_uncommit(b);
-}
-#endif /* L__free_support */
-
-extern void __malloc_init(void);
-
-#ifdef L__malloc_init
-void __malloc_init(void)
-{
- int i, mapsize, x, old_x, gcount;
-
- mapsize = M_PAGESIZE;
-
- __malloc_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);
- __malloc_initialized = 1;
- // fprintf(stderr, "malloc_init: hunk_t=%d\n", sizeof(Hunk_t));
-}
-#endif /* L__malloc_init */
-
-#ifdef L_malloc
-void *malloc(size_t size)
-{
- void *p;
-
- if (size == 0)
- return NULL;
-
- if (__malloc_initialized < 0)
- __malloc_init();
- if (__malloc_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 (__malloc_initialized)
- mutex_unlock(&malloc_lock);
-
- // fprintf(stderr, "malloc returning: s=%d, p=%p\n", size, p);
- return p;
-}
-#endif /* L_malloc */
-
-#ifdef L_free
-void free(void *ptr)
-{
- Block_t *p, *best;
-
- if (__malloc_initialized < 0)
- return;
- if (__malloc_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 (__malloc_initialized)
- mutex_unlock(&malloc_lock);
- return;
- }
-
- __bl_free(best);
-
- if (__malloc_initialized)
- mutex_unlock(&malloc_lock);
-}
-#endif /* L_free */
-
-extern void *_realloc_no_move(void *ptr, size_t size);
-
-#ifdef L__realloc_no_move
-void *_realloc_no_move(void *ptr, size_t size)
-{
- Block_t *p, *best, *next;
-
- if (size <= HUNK_MAXSIZE)
- return NULL;
-
- if (__malloc_initialized <= 0)
- return malloc(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, p);
- 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;
-}
-#endif /* L__realloc_no_move */
-
-#ifdef L_realloc
-void *realloc(void *ptr, size_t size)
-{
- void *tmp;
-
- tmp = _realloc_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;
+#include "malloc.h"
+#include "heap.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 = malloc(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 malloc(size);
- }
- mutex_unlock(&malloc_lock);
+/* When we give memory to the heap, start this many bytes after the
+ beginning of the mmaped block. This is because we must ensure that
+ malloc return values are aligned to MALLOC_ALIGNMENT, but since we need
+ to use one word _before_ the beginning of that, we actually want the heap
+ to return values that are MALLOC_ALIGNMENT aligned - sizeof (size_t).
+ Since the heap always allocates in multiples of HEAP_GRANULARITY, we can
+ do this by (1) ensuring that HEAP_GRANULARITY is a multiple of
+ MALLOC_ALIGNMENT, and (2) making sure that the heap's free areas start
+ sizeof(size_t) bytes before our required alignment. */
+#define MALLOC_HEAP_BLOCK_SHIM (MALLOC_ALIGNMENT - sizeof (size_t))
- /* copy whole block */
- if ((tmp = malloc(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;
-}
-#endif /* L_realloc */
+/* The heap used for small allocations. */
+struct heap __malloc_heap = HEAP_INIT;
-#ifdef L_calloc
-void *calloc(size_t unit, size_t quantity)
+
+void *malloc (size_t size)
{
- void *p;
-
- unit *= quantity;
-
- if ((p = malloc(unit)) == NULL)
- return NULL;
- memset(p, 0, unit);
- return p;
+ void *mem;
+
+ MALLOC_DEBUG ("malloc: %d bytes\n", size);
+
+ /* Include an extra word to record the size of the allocated block. */
+ size += sizeof (size_t);
+
+ if (size >= MALLOC_MMAP_THRESHOLD)
+ /* Use mmap for large allocations. */
+ {
+ /* Make sure we request enough memory to align the result correctly,
+ and that SIZE reflects that mmap hands back whole pages. */
+ size += MALLOC_ROUND_UP_TO_PAGE_SIZE (MALLOC_ALIGNMENT - sizeof(size_t));
+
+ mem = mmap (0, size, PROT_READ | PROT_WRITE,
+ MAP_SHARED | MAP_ANONYMOUS, 0, 0);
+ if (mem == MAP_FAILED)
+ return 0;
+ }
+ else
+ /* Use the heap for small allocations. */
+ {
+ mem = __heap_alloc (&__malloc_heap, &size);
+
+ if (! mem)
+ /* We couldn't allocate from the heap, so get some more memory
+ from the system, add it to the heap, and try again. */
+ {
+ /* If we're trying to allocate a block bigger than the default
+ MALLOC_HEAP_EXTEND_SIZE, make sure we get enough to hold it. */
+ size_t block_size = (size < MALLOC_HEAP_EXTEND_SIZE
+ ? MALLOC_HEAP_EXTEND_SIZE
+ : MALLOC_ROUND_UP_TO_PAGE_SIZE (size));
+ /* Allocate the new heap block. */
+ void *block = mmap (0, block_size,
+ PROT_READ | PROT_WRITE,
+ MAP_SHARED | MAP_ANONYMOUS, 0, 0);
+
+ if (block != MAP_FAILED)
+ {
+ /* Put BLOCK into the heap. We first try to append BLOCK to
+ an existing free area, which is more efficient because it
+ doesn't require using a `shim' at the beginning (which
+ would prevent merging free-areas); since mmap often returns
+ contiguous areas, this is worth it. */
+ if (! __heap_append_free (&__malloc_heap, block, block_size))
+ /* Couldn't append, just add BLOCK as a new free-area. */
+ __heap_free (&__malloc_heap,
+ block + MALLOC_HEAP_BLOCK_SHIM,
+ block_size - MALLOC_HEAP_BLOCK_SHIM);
+
+ /* Try again to allocate. */
+ mem = __heap_alloc (&__malloc_heap, &size);
+ }
+ }
+ }
+
+ if (mem)
+ /* Record the size of this block just before the returned address. */
+ {
+ *(size_t *)mem = size;
+ mem = (size_t *)mem + 1;
+
+ MALLOC_DEBUG (" malloc: returning 0x%lx (base:0x%lx, total_size:%d)\n",
+ (long)mem, (long)mem - sizeof (size_t), size);
+ }
+
+ return mem;
}
-#endif /* L_calloc */