summaryrefslogtreecommitdiff
path: root/libc/stdlib/malloc
diff options
context:
space:
mode:
authorMiles Bader <miles@lsi.nec.co.jp>2002-10-09 10:27:56 +0000
committerMiles Bader <miles@lsi.nec.co.jp>2002-10-09 10:27:56 +0000
commit306eedf9ae04d3bde9be48bda0d387432d530a73 (patch)
tree087b8fcb7a4c9a6522cb131ed4dd4dcd13be6180 /libc/stdlib/malloc
parent79a790a53f60ff71cf5b77d7afe4ff3d7731edde (diff)
* Add support for uClinux's broken munmap, contingent on
__UCLIBC_UCLINUX_BROKEN_MUNMAP__ (which is currently not defined anywhere). This makes other cases a tiny bit less efficient too. * Move the malloc lock into the heap structure (locking is still done at the malloc level though, not by the heap functions). * Initialize the malloc heap to contain a tiny initial static free-area so that programs that only do a very little allocation won't ever call mmap.
Diffstat (limited to 'libc/stdlib/malloc')
-rw-r--r--libc/stdlib/malloc/free.c120
-rw-r--r--libc/stdlib/malloc/heap.h46
-rw-r--r--libc/stdlib/malloc/malloc.c86
-rw-r--r--libc/stdlib/malloc/malloc.h41
4 files changed, 264 insertions, 29 deletions
diff --git a/libc/stdlib/malloc/free.c b/libc/stdlib/malloc/free.c
index c8c687964..6c3211360 100644
--- a/libc/stdlib/malloc/free.c
+++ b/libc/stdlib/malloc/free.c
@@ -19,12 +19,11 @@
#include "heap.h"
-void
-free (void *mem)
+static void
+free_to_heap (void *mem, struct heap *heap)
{
size_t size;
struct heap_free_area *fa;
- struct heap *heap = &__malloc_heap;
/* Check for special cases. */
if (unlikely (! mem))
@@ -38,7 +37,7 @@ free (void *mem)
size = MALLOC_SIZE (mem);
mem = MALLOC_BASE (mem);
- __malloc_lock ();
+ __heap_lock (heap);
/* Put MEM back in the heap, and get the free-area it was placed in. */
fa = __heap_free (heap, mem, size);
@@ -47,15 +46,20 @@ free (void *mem)
unmapped. */
if (HEAP_FREE_AREA_SIZE (fa) < MALLOC_UNMAP_THRESHOLD)
/* Nope, nothing left to do, just release the lock. */
- __malloc_unlock ();
+ __heap_unlock (heap);
else
/* Yup, try to unmap FA. */
{
unsigned long start = (unsigned long)HEAP_FREE_AREA_START (fa);
unsigned long end = (unsigned long)HEAP_FREE_AREA_END (fa);
#ifndef MALLOC_USE_SBRK
+# ifdef __UCLIBC_UCLINUX_BROKEN_MUNMAP__
+ struct malloc_mmb *mmb, *prev_mmb;
+ unsigned long mmb_start, mmb_end;
+# else /* !__UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
unsigned long unmap_start, unmap_end;
-#endif
+# endif /* __UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
+#endif /* !MALLOC_USE_SBRK */
#ifdef MALLOC_USE_SBRK
/* Get the sbrk lock so that the two possible calls to sbrk below
@@ -75,7 +79,7 @@ free (void *mem)
MALLOC_DEBUG (" not unmapping: 0x%lx - 0x%lx (%ld bytes)\n",
start, end, end - start);
__malloc_unlock_sbrk ();
- __malloc_unlock ();
+ __heap_unlock (heap);
return;
}
#endif
@@ -102,7 +106,7 @@ free (void *mem)
#ifdef MALLOC_USE_SBRK
/* Release the main lock; we're still holding the sbrk lock. */
- __malloc_unlock ();
+ __heap_unlock (heap);
/* Lower the brk. */
sbrk (start - end);
/* Release the sbrk lock too; now we hold no locks. */
@@ -110,6 +114,94 @@ free (void *mem)
#else /* !MALLOC_USE_SBRK */
+# ifdef __UCLIBC_UCLINUX_BROKEN_MUNMAP__
+ /* Using the uClinux broken munmap, we have to only munmap blocks
+ exactly as we got them from mmap, so scan through our list of
+ mmapped blocks, and return them in order. */
+
+ MALLOC_MMB_DEBUG (" walking mmb list for region 0x%x[%d]...\n", start, end - start);
+
+ prev_mmb = 0;
+ mmb = __malloc_mmapped_blocks;
+ while (mmb
+ && ((mmb_end = (mmb_start = (unsigned long)mmb->mem) + mmb->size)
+ <= end))
+ {
+ MALLOC_MMB_DEBUG (" considering mmb at 0x%x: 0x%x[%d]\n",
+ (unsigned)mmb, mmb_start, mmb_end - mmb_start);
+
+ if (mmb_start >= start
+ /* If the space between START and MMB_START is non-zero, but
+ too small to return to the heap, we can't unmap MMB. */
+ && (start == mmb_start
+ || mmb_start - start > HEAP_MIN_FREE_AREA_SIZE))
+ {
+ struct malloc_mmb *next_mmb = mmb->next;
+
+ if (mmb_end != end && mmb_end + HEAP_MIN_FREE_AREA_SIZE > end)
+ /* There's too little space left at the end to deallocate
+ this block, so give up. */
+ break;
+
+ MALLOC_MMB_DEBUG (" unmapping mmb at 0x%x: 0x%x[%d]\n",
+ (unsigned)mmb, mmb_start, mmb_end - mmb_start);
+
+ if (mmb_start != start)
+ /* We're going to unmap a part of the heap that begins after
+ start, so put the intervening region back into the heap. */
+ {
+ MALLOC_MMB_DEBUG (" putting intervening region back into heap: 0x%x[%d]\n",
+ start, mmb_start - start);
+ __heap_free (heap, (void *)start, mmb_start - start);
+ }
+
+ /* Unlink MMB from the list. */
+ if (prev_mmb)
+ prev_mmb->next = next_mmb;
+ else
+ __malloc_mmapped_blocks = next_mmb;
+
+ /* Release the descriptor block we used. */
+ free_to_heap (mmb, &__malloc_mmb_heap);
+
+ /* Do the actual munmap. */
+ __heap_unlock (heap);
+ munmap ((void *)mmb_start, mmb_end - mmb_start);
+ __heap_lock (heap);
+
+ /* Start searching again from the end of that block. */
+ start = mmb_end;
+
+# ifdef __UCLIBC_HAS_THREADS__
+ /* In a multi-threaded program, it's possible that PREV_MMB has
+ been invalidated by another thread when we released the
+ heap lock to do the munmap system call, so just start over
+ from the beginning of the list. It sucks, but oh well;
+ it's probably not worth the bother to do better. */
+ prev_mmb = 0;
+ mmb = __malloc_mmapped_blocks;
+# else
+ mmb = next_mmb;
+# endif
+ }
+ else
+ {
+ prev_mmb = mmb;
+ mmb = mmb->next;
+ }
+ }
+
+ if (start != end)
+ /* Hmm, well there's something we couldn't unmap, so put it back
+ into the heap. */
+ {
+ MALLOC_MMB_DEBUG (" putting tail region back into heap: 0x%x[%d]\n",
+ start, end - start);
+ __heap_free (heap, (void *)start, end - start);
+ }
+
+# else /* !__UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
+
/* MEM/LEN may not be page-aligned, so we have to page-align them,
and return any left-over bits on the end to the heap. */
unmap_start = MALLOC_ROUND_UP_TO_PAGE_SIZE (start);
@@ -133,13 +225,21 @@ free (void *mem)
__heap_free (heap, (void *)unmap_end, end - unmap_end);
}
- /* Release the malloc lock before we do the system call. */
- __malloc_unlock ();
+ /* Release the heap lock before we do the system call. */
+ __heap_unlock (heap);
if (unmap_end > unmap_start)
/* Finally, actually unmap the memory. */
munmap ((void *)unmap_start, unmap_end - unmap_start);
+# endif /* __UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
+
#endif /* MALLOC_USE_SBRK */
}
}
+
+void
+free (void *mem)
+{
+ free_to_heap (mem, &__malloc_heap);
+}
diff --git a/libc/stdlib/malloc/heap.h b/libc/stdlib/malloc/heap.h
index d8e8335b6..42cde5227 100644
--- a/libc/stdlib/malloc/heap.h
+++ b/libc/stdlib/malloc/heap.h
@@ -14,6 +14,13 @@
#include <features.h>
+/* On multi-threaded systems, the heap includes a lock. */
+#ifdef __UCLIBC_HAS_THREADS__
+# include <pthread.h>
+# define HEAP_USE_LOCKING
+#endif
+
+
/* The heap allocates in multiples of, and aligned to, HEAP_GRANULARITY.
HEAP_GRANULARITY must be a power of 2. Malloc depends on this being the
same as MALLOC_ALIGNMENT. */
@@ -26,9 +33,26 @@ struct heap
{
/* A list of memory in the heap available for allocation. */
struct heap_free_area *free_areas;
+
+#ifdef HEAP_USE_LOCKING
+ /* A lock that can be used by callers to control access to the heap.
+ The heap code _does not_ use this lock, it's merely here for the
+ convenience of users! */
+ extern heap_mutex_t lock;
+#endif
};
-#define HEAP_INIT { 0 }
+/* The HEAP_INIT macro can be used as a static initializer for a heap
+ variable. The HEAP_INIT_WITH_FA variant is used to initialize a heap
+ with an initial static free-area; its argument FA should be declared
+ using HEAP_DECLARE_STATIC_FREE_AREA. */
+#ifdef HEAP_USE_LOCKING
+# define HEAP_INIT { 0, PTHREAD_MUTEX_INITIALIZER }
+# define HEAP_INIT_WITH_FA(fa) { &fa._fa, PTHREAD_MUTEX_INITIALIZER }
+#else
+# define HEAP_INIT { 0 }
+# define HEAP_INIT_WITH_FA(fa) { &fa._fa }
+#endif
/* A free-list area `header'. These are actually stored at the _ends_ of
free areas (to make allocating from the beginning of the area simpler),
@@ -47,6 +71,16 @@ struct heap_free_area
/* Return the size of the frea area FA. */
#define HEAP_FREE_AREA_SIZE(fa) ((fa)->size)
+/* This rather clumsy macro allows one to declare a static free-area for
+ passing to HEAP_INIT_WITH_FA initializer macro. This is only use for
+ which NAME is allowed. */
+#define HEAP_DECLARE_STATIC_FREE_AREA(name, size) \
+ static struct \
+ { \
+ char space[(size) - sizeof (struct heap_free_area)]; \
+ struct heap_free_area _fa; \
+ } name = { "", { (size), 0, 0 } }
+
/* Rounds SZ up to be a multiple of HEAP_GRANULARITY. */
#define HEAP_ADJUST_SIZE(sz) \
@@ -97,6 +131,16 @@ extern void __heap_dump (struct heap *heap, const char *str);
extern void __heap_check (struct heap *heap, const char *str);
+#ifdef HEAP_USE_LOCKING
+# define __heap_lock(heap) pthread_mutex_lock (&(heap)->lock)
+# define __heap_unlock(heap) pthread_mutex_unlock (&(heap)->lock)
+#else /* !__UCLIBC_HAS_THREADS__ */
+/* Without threads, mutex operations are a nop. */
+# define __heap_lock(heap) (void)0
+# define __heap_unlock(heap) (void)0
+#endif /* HEAP_USE_LOCKING */
+
+
/* Delete the free-area FA from HEAP. */
extern inline void
__heap_delete (struct heap *heap, struct heap_free_area *fa)
diff --git a/libc/stdlib/malloc/malloc.c b/libc/stdlib/malloc/malloc.c
index 021ed3a24..f6dd3099d 100644
--- a/libc/stdlib/malloc/malloc.c
+++ b/libc/stdlib/malloc/malloc.c
@@ -19,35 +19,49 @@
#include "heap.h"
-/* The malloc heap. */
-struct heap __malloc_heap = HEAP_INIT;
+/* The malloc heap. We provide a bit of initial static space so that
+ programs can do a little mallocing without mmaping in more space. */
+HEAP_DECLARE_STATIC_FREE_AREA (initial_fa, 256);
+struct heap __malloc_heap = HEAP_INIT_WITH_FA (initial_fa);
-#ifdef MALLOC_USE_LOCKING
-/* A lock protecting the malloc heap. */
-malloc_mutex_t __malloc_lock;
-# ifdef MALLOC_USE_SBRK
+#if defined(MALLOC_USE_LOCKING) && defined(MALLOC_USE_SBRK)
/* A lock protecting our use of sbrk. */
malloc_mutex_t __malloc_sbrk_lock;
-# endif /* MALLOC_USE_SBRK */
-#endif /* MALLOC_USE_LOCKING */
+#endif /* MALLOC_USE_LOCKING && MALLOC_USE_SBRK */
#ifdef MALLOC_DEBUGGING
int __malloc_debug = 0;
#endif
-void *
-malloc (size_t size)
+#ifdef __UCLIBC_UCLINUX_BROKEN_MUNMAP__
+/* A list of all malloc_mmb structures describing blocsk that
+ malloc has mmapped, ordered by the block address. */
+struct malloc_mmb *__malloc_mmapped_blocks = 0;
+
+/* A heap used for allocating malloc_mmb structures. We could allocate
+ them from the main heap, but that tends to cause heap fragmentation in
+ annoying ways. */
+HEAP_DECLARE_STATIC_FREE_AREA (initial_mmb_fa, 48); /* enough for 3 mmbs */
+struct heap __malloc_mmb_heap = HEAP_INIT_WITH_FA (initial_mmb_fa);
+
+# ifdef MALLOC_MMB_DEBUGGING
+int __malloc_mmb_debug = 0;
+# endif
+#endif /* __UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
+
+
+static void *
+malloc_from_heap (size_t size, struct heap *heap)
{
void *mem;
- struct heap *heap = &__malloc_heap;
MALLOC_DEBUG ("malloc: %d bytes\n", size);
/* Include extra space to record the size of the allocated block. */
size += MALLOC_HEADER_SIZE;
- __malloc_lock ();
+ __heap_lock (heap);
/* First try to get memory that's already in our heap. */
mem = __heap_alloc (heap, &size);
@@ -65,14 +79,14 @@ malloc (size_t size)
: MALLOC_ROUND_UP_TO_PAGE_SIZE (size));
#ifdef MALLOC_USE_SBRK
- /* Get the sbrk lock while we've still got the main lock. */
+ /* Get the sbrk lock while we've still got the heap lock. */
__malloc_lock_sbrk ();
#endif
- /* Don't hold the main lock during the syscall, so that small
+ /* Don't hold the heap lock during the syscall, so that small
allocations in a different thread may succeed while we're
blocked. */
- __malloc_unlock ();
+ __heap_unlock (heap);
/* Allocate the new heap block. */
#ifdef MALLOC_USE_SBRK
@@ -106,23 +120,53 @@ malloc (size_t size)
#endif /* MALLOC_USE_SBRK */
- /* Get back the main lock. */
- __malloc_lock ();
+ /* Get back the heap lock. */
+ __heap_lock (heap);
if (likely (block != (void *)-1))
{
+#if !defined(MALLOC_USE_SBRK) && defined(__UCLIBC_UCLINUX_BROKEN_MUNMAP__)
+ struct malloc_mmb *mmb, *prev_mmb, *new_mmb;
+#endif /* !MALLOC_USE_SBRK && __UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
+
MALLOC_DEBUG (" adding memory: 0x%lx - 0x%lx (%d bytes)\n",
(long)block, (long)block + block_size, block_size);
/* Put BLOCK into the heap. */
__heap_free (heap, block, block_size);
+#if !defined(MALLOC_USE_SBRK) && defined(__UCLIBC_UCLINUX_BROKEN_MUNMAP__)
+ /* Insert a record of this allocation in sorted order into the
+ __malloc_mmapped_blocks list. */
+
+ for (prev_mmb = 0, mmb = __malloc_mmapped_blocks;
+ mmb;
+ prev_mmb = mmb, mmb = mmb->next)
+ if (block < mmb->mem)
+ break;
+
+ new_mmb = malloc_from_heap (sizeof *new_mmb, &__malloc_mmb_heap);
+ new_mmb->next = mmb;
+ new_mmb->mem = block;
+ new_mmb->size = block_size;
+
+ MALLOC_MMB_DEBUG (" new mmb at 0x%x: 0x%x[%d]\n",
+ (unsigned)new_mmb,
+ (unsigned)new_mmb->mem, block_size);
+
+ if (prev_mmb)
+ prev_mmb->next = new_mmb;
+ else
+ __malloc_mmapped_blocks = new_mmb;
+
+#endif /* !MALLOC_USE_SBRK && __UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
+
/* Try again to allocate. */
mem = __heap_alloc (heap, &size);
}
}
- __malloc_unlock ();
+ __heap_unlock (heap);
if (likely (mem))
/* Record the size of the block and get the user address. */
@@ -135,3 +179,9 @@ malloc (size_t size)
return mem;
}
+
+void *
+malloc (size_t size)
+{
+ return malloc_from_heap (size, &__malloc_heap);
+}
diff --git a/libc/stdlib/malloc/malloc.h b/libc/stdlib/malloc/malloc.h
index 4071a4ffb..9c7f047d3 100644
--- a/libc/stdlib/malloc/malloc.h
+++ b/libc/stdlib/malloc/malloc.h
@@ -48,6 +48,47 @@
#endif
+/* The current implementation of munmap in uClinux doesn't work correctly:
+ it requires that ever call to munmap exactly match a corresponding call
+ to mmap (that is, it doesn't allow you to unmap only part of a
+ previously allocated block, or to unmap two contiguous blocks with a
+ single call to munmap). This behavior is broken, and uClinux should be
+ fixed; however, until it is, we add code to work around the problem in
+ malloc. */
+#ifdef __UCLIBC_UCLINUX_BROKEN_MUNMAP__
+
+/* A structure recording a block of memory mmapped by malloc. */
+struct malloc_mmb
+{
+ void *mem; /* the mmapped block */
+ size_t size; /* its size */
+ struct malloc_mmb *next;
+};
+
+/* A list of all malloc_mmb structures describing blocsk that malloc has
+ mmapped, ordered by the block address. */
+extern struct malloc_mmb *__malloc_mmapped_blocks;
+
+/* A heap used for allocating malloc_mmb structures. We could allocate
+ them from the main heap, but that tends to cause heap fragmentation in
+ annoying ways. */
+extern struct heap __malloc_mmb_heap;
+
+/* Define MALLOC_MMB_DEBUGGING to cause malloc to emit debugging info about
+ about mmap block allocation/freeing by the `uclinux broken munmap' code
+ to stderr, when the variable __malloc_mmb_debug is set to true. */
+#ifdef MALLOC_MMB_DEBUGGING
+#include <stdio.h>
+extern int __malloc_mmb_debug;
+#define MALLOC_MMB_DEBUG(fmt, args...) \
+ (__malloc_mmb_debug ? fprintf (stderr, fmt , ##args) : 0)
+#else /* !MALLOC_MMB_DEBUGGING */
+#define MALLOC_MMB_DEBUG(fmt, args...) (void)0
+#endif /* MALLOC_MMB_DEBUGGING */
+
+#endif /* __UCLIBC_UCLINUX_BROKEN_MUNMAP__ */
+
+
/* The size of a malloc allocation is stored in a size_t word
MALLOC_ALIGNMENT bytes prior to the start address of the allocation: