From 056f9d98941eb98e453bf4fa308f28b892525baf Mon Sep 17 00:00:00 2001 From: Miles Bader Date: Thu, 25 Jul 2002 01:58:57 +0000 Subject: Redo the locking, so that it may actually work. Now locking is done at the malloc/free level, not within the heap abstraction, and there's a separate lock to control sbrk access. Also, get rid of the separate `unmap_free_area' function in free.c, and just put the code in the `free' function directly, which saves a bunch of space (even compared to using an inline function) for some reason. --- libc/stdlib/malloc/free.c | 193 ++++++++++++++++++++----------------- libc/stdlib/malloc/heap.h | 19 +--- libc/stdlib/malloc/heap_alloc.c | 4 - libc/stdlib/malloc/heap_alloc_at.c | 4 - libc/stdlib/malloc/heap_free.c | 6 +- libc/stdlib/malloc/malloc.c | 49 ++++++++-- libc/stdlib/malloc/malloc.h | 38 +++++++- libc/stdlib/malloc/realloc.c | 3 + 8 files changed, 186 insertions(+), 130 deletions(-) diff --git a/libc/stdlib/malloc/free.c b/libc/stdlib/malloc/free.c index 4aa21cb84..f7d8fc18d 100644 --- a/libc/stdlib/malloc/free.c +++ b/libc/stdlib/malloc/free.c @@ -18,93 +18,6 @@ #include "malloc.h" #include "heap.h" - -/* Try to release the free-area FA in HEAP back to the system. */ -static void -unmap_free_area (struct heap *heap, struct heap_free_area *fa) -{ - unsigned long start, end; -#ifndef MALLOC_USE_SBRK - unsigned long unmap_start, unmap_end; -#endif - - end = (unsigned long)HEAP_FREE_AREA_END (fa); - -#ifdef MALLOC_USE_SBRK - /* When using sbrk, we only shrink the heap from the end. It would be - possible to allow _both_ -- shrinking via sbrk when possible, and - otherwise shrinking via munmap, but this results in holes in memory - that prevent the brk from every growing back down; since we only ever - grow the heap via sbrk, this tends to produce a continuously growing - brk (though the actual memory is unmapped), which could eventually run - out of address space. Note that `sbrk(0)' shouldn't normally do a - system call, so this test is reasonably cheap. */ - if ((void *)end != sbrk (0)) - { - MALLOC_DEBUG (" not unmapping: 0x%lx - 0x%lx (%d bytes)\n", - (unsigned long)HEAP_FREE_AREA_START (fa), - (unsigned long)HEAP_FREE_AREA_END (fa), - fa->size); - return; - } -#endif - - start = (unsigned long)HEAP_FREE_AREA_START (fa); - - MALLOC_DEBUG (" unmapping: 0x%lx - 0x%lx (%ld bytes)\n", - start, end, end - start); - - /* Remove FA from the heap. */ - __heap_unlink_free_area (heap, fa); - - if (!fa->next && !fa->prev) - /* We want to avoid the heap from losing all memory, so reserve a bit. - This test is only a heuristic -- the existance of another free area, - even if it's smaller than MALLOC_MIN_SIZE, will cause us not to - reserve anything. */ - { - /* Put the reserved memory back in the heap; we asssume that - MALLOC_UNMAP_THRESHOLD is greater than MALLOC_MIN_SIZE, so we use - the latter unconditionally here. */ - __heap_free (heap, (void *)start, MALLOC_MIN_SIZE); - start += MALLOC_MIN_SIZE; - } - -#ifdef MALLOC_USE_SBRK - - sbrk (start - end); - -#else /* !MALLOC_USE_SBRK */ - - /* 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); - unmap_end = MALLOC_ROUND_DOWN_TO_PAGE_SIZE (end); - - /* We have to be careful that any left-over bits are large enough to - return. Note that we _don't check_ to make sure there's room to - grow/shrink the start/end by another page, we just assume that the - unmap threshold is high enough so that this is always safe (i.e., it - should probably be at least 3 pages). */ - if (unmap_start > start) - { - if (unmap_start - start < HEAP_MIN_FREE_AREA_SIZE) - unmap_start += MALLOC_PAGE_SIZE; - __heap_free (heap, (void *)start, unmap_start - start); - } - if (end > unmap_end) - { - if (end - unmap_end < HEAP_MIN_FREE_AREA_SIZE) - unmap_end -= MALLOC_PAGE_SIZE; - __heap_free (heap, (void *)unmap_end, end - unmap_end); - } - - if (unmap_end > unmap_start) - munmap ((void *)unmap_start, unmap_end - unmap_start); - -#endif /* MALLOC_USE_SBRK */ -} - void free (void *mem) @@ -120,12 +33,112 @@ free (void *mem) MALLOC_DEBUG ("free: 0x%lx (base = 0x%lx, total_size = %d)\n", (long)mem + MALLOC_ALIGNMENT, (long)mem, size); + __malloc_lock (); + fa = __heap_free (&__malloc_heap, mem, size); /* Now we check to see if FA has grown big enough that it should be unmapped. */ - if (HEAP_FREE_AREA_SIZE (fa) >= MALLOC_UNMAP_THRESHOLD) - /* Get rid of it. */ - unmap_free_area (&__malloc_heap, fa); + if (HEAP_FREE_AREA_SIZE (fa) < MALLOC_UNMAP_THRESHOLD) + /* Nothing left to do, just release the lock. */ + __malloc_unlock (); + else + /* Try to unmap FA. */ + { + unsigned long start, end; +#ifndef MALLOC_USE_SBRK + unsigned long unmap_start, unmap_end; +#endif + + end = (unsigned long)HEAP_FREE_AREA_END (fa); + +#ifdef MALLOC_USE_SBRK + /* Get the sbrk lock so that the two possible calls to sbrk below + are guaranteed to be contiguous. */ + __malloc_lock_sbrk (); + /* When using sbrk, we only shrink the heap from the end. It would + be possible to allow _both_ -- shrinking via sbrk when possible, + and otherwise shrinking via munmap, but this results in holes in + memory that prevent the brk from every growing back down; since + we only ever grow the heap via sbrk, this tends to produce a + continuously growing brk (though the actual memory is unmapped), + which could eventually run out of address space. Note that + `sbrk(0)' shouldn't normally do a system call, so this test is + reasonably cheap. */ + if ((void *)end != sbrk (0)) + { + MALLOC_DEBUG (" not unmapping: 0x%lx - 0x%lx (%d bytes)\n", + (unsigned long)HEAP_FREE_AREA_START (fa), + (unsigned long)HEAP_FREE_AREA_END (fa), + fa->size); + __malloc_unlock_sbrk (); + __malloc_unlock (); + return; + } +#endif + + start = (unsigned long)HEAP_FREE_AREA_START (fa); + + MALLOC_DEBUG (" unmapping: 0x%lx - 0x%lx (%ld bytes)\n", + start, end, end - start); + + /* Remove FA from the heap. */ + __heap_unlink_free_area (&__malloc_heap, fa); + + if (!fa->next && !fa->prev) + /* We want to avoid the heap from losing all memory, so reserve + a bit. This test is only a heuristic -- the existance of + another free area, even if it's smaller than + MALLOC_MIN_SIZE, will cause us not to reserve anything. */ + { + /* Put the reserved memory back in the heap; we asssume that + MALLOC_UNMAP_THRESHOLD is greater than MALLOC_MIN_SIZE, so + we use the latter unconditionally here. */ + __heap_free (&__malloc_heap, (void *)start, MALLOC_MIN_SIZE); + start += MALLOC_MIN_SIZE; + } + +#ifdef MALLOC_USE_SBRK + + /* Release the main lock; we're still holding the sbrk lock. */ + __malloc_unlock (); + /* Lower the brk. */ + sbrk (start - end); + /* Release the sbrk lock too; now we hold no locks. */ + __malloc_unlock_sbrk (); + +#else /* !MALLOC_USE_SBRK */ + + /* 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); + unmap_end = MALLOC_ROUND_DOWN_TO_PAGE_SIZE (end); + + /* We have to be careful that any left-over bits are large enough to + return. Note that we _don't check_ to make sure there's room to + grow/shrink the start/end by another page, we just assume that + the unmap threshold is high enough so that this is always safe + (i.e., it should probably be at least 3 pages). */ + if (unmap_start > start) + { + if (unmap_start - start < HEAP_MIN_FREE_AREA_SIZE) + unmap_start += MALLOC_PAGE_SIZE; + __heap_free (&__malloc_heap, (void *)start, unmap_start - start); + } + if (end > unmap_end) + { + if (end - unmap_end < HEAP_MIN_FREE_AREA_SIZE) + unmap_end -= MALLOC_PAGE_SIZE; + __heap_free (&__malloc_heap, (void *)unmap_end, end - unmap_end); + } + + /* Release the malloc lock before we do the system call. */ + __malloc_unlock (); + + if (unmap_end > unmap_start) + munmap ((void *)unmap_start, unmap_end - unmap_start); + +#endif /* MALLOC_USE_SBRK */ + } } } diff --git a/libc/stdlib/malloc/heap.h b/libc/stdlib/malloc/heap.h index 5207afe8e..445b012ce 100644 --- a/libc/stdlib/malloc/heap.h +++ b/libc/stdlib/malloc/heap.h @@ -14,21 +14,6 @@ #include -#ifdef __UCLIBC_HAS_THREADS__ -#include -typedef pthread_mutex_t heap_mutex_t; -# define HEAP_MUTEX_INIT PTHREAD_MUTEX_INITIALIZER -# define __heap_lock(heap) pthread_mutex_lock (&(heap)->lock) -# define __heap_unlock(heap) pthread_mutex_unlock (&(heap)->lock); -#else -/* Without threads, Mutex operations are a nop. */ -typedef int heap_mutex_t; -# define HEAP_MUTEX_INIT 0 -# define __heap_lock(heap) -# define __heap_unlock(heap) -#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. */ @@ -41,10 +26,8 @@ struct heap { /* A list of memory in the heap available for allocation. */ struct heap_free_area *free_areas; - - heap_mutex_t lock; }; -#define HEAP_INIT { 0, HEAP_MUTEX_INIT } +#define HEAP_INIT { 0 } /* A free-list area `header'. These are actually stored at the _ends_ of diff --git a/libc/stdlib/malloc/heap_alloc.c b/libc/stdlib/malloc/heap_alloc.c index d0e1d752a..8a6c7842e 100644 --- a/libc/stdlib/malloc/heap_alloc.c +++ b/libc/stdlib/malloc/heap_alloc.c @@ -33,8 +33,6 @@ __heap_alloc (struct heap *heap, size_t *size) we must make sure that every allocated block can hold one. */ _size = HEAP_ADJUST_SIZE (sizeof (struct heap_free_area)); - __heap_lock (heap); - HEAP_DEBUG (heap, "before __heap_alloc"); /* Look for a free area that can contain _SIZE bytes. */ @@ -49,7 +47,5 @@ __heap_alloc (struct heap *heap, size_t *size) HEAP_DEBUG (heap, "after __heap_alloc"); - __heap_unlock (heap); - return mem; } diff --git a/libc/stdlib/malloc/heap_alloc_at.c b/libc/stdlib/malloc/heap_alloc_at.c index 4047697c5..de84e99ee 100644 --- a/libc/stdlib/malloc/heap_alloc_at.c +++ b/libc/stdlib/malloc/heap_alloc_at.c @@ -26,8 +26,6 @@ __heap_alloc_at (struct heap *heap, void *mem, size_t size) size = HEAP_ADJUST_SIZE (size); - __heap_lock (heap); - HEAP_DEBUG (heap, "before __heap_alloc_at"); /* Look for a free area that can contain SIZE bytes. */ @@ -45,7 +43,5 @@ __heap_alloc_at (struct heap *heap, void *mem, size_t size) HEAP_DEBUG (heap, "after __heap_alloc_at"); - __heap_unlock (heap); - return alloced; } diff --git a/libc/stdlib/malloc/heap_free.c b/libc/stdlib/malloc/heap_free.c index e958f920d..6084b43c3 100644 --- a/libc/stdlib/malloc/heap_free.c +++ b/libc/stdlib/malloc/heap_free.c @@ -23,8 +23,6 @@ __heap_free (struct heap *heap, void *mem, size_t size) struct heap_free_area *prev_fa, *fa; void *end = (char *)mem + size; - __heap_lock (heap); - HEAP_DEBUG (heap, "before __heap_free"); /* Find an adjacent free-list entry. */ @@ -59,8 +57,8 @@ __heap_free (struct heap *heap, void *mem, size_t size) /* See if FA can now be merged with its successor. */ if (next_fa && mem + size == HEAP_FREE_AREA_START (next_fa)) + /* Yup; merge FA's info into NEXT_FA. */ { - /* Yup; merge FA's info into NEXT_FA. */ fa_size += next_fa->size; __heap_link_free_area_after (heap, next_fa, prev_fa); fa = next_fa; @@ -92,7 +90,5 @@ __heap_free (struct heap *heap, void *mem, size_t size) done: HEAP_DEBUG (heap, "after __heap_free"); - __heap_unlock (heap); - return fa; } diff --git a/libc/stdlib/malloc/malloc.c b/libc/stdlib/malloc/malloc.c index 049a3e003..e6b9c0d66 100644 --- a/libc/stdlib/malloc/malloc.c +++ b/libc/stdlib/malloc/malloc.c @@ -22,6 +22,15 @@ /* The malloc heap. */ struct heap __malloc_heap = HEAP_INIT; +#ifdef MALLOC_USE_LOCKING +/* A lock protecting the malloc heap. */ +malloc_mutex_t __malloc_lock; +# ifdef MALLOC_USE_SBRK +/* A lock protecting our use of sbrk. */ +malloc_mutex_t __malloc_sbrk_lock; +# endif /* MALLOC_USE_SBRK */ +#endif /* MALLOC_USE_LOCKING */ + void * malloc (size_t size) @@ -33,6 +42,8 @@ malloc (size_t size) /* Include extra space to record the size of the allocated block. */ size += MALLOC_ROUND_UP (sizeof (size_t), MALLOC_ALIGNMENT); + __malloc_lock (); + mem = __heap_alloc (&__malloc_heap, &size); if (! mem) /* We couldn't allocate from the heap, so get some more memory @@ -40,24 +51,30 @@ malloc (size_t size) { /* If we're trying to allocate a block bigger than the default MALLOC_HEAP_EXTEND_SIZE, make sure we get enough to hold it. */ + void *block; size_t block_size = (size < MALLOC_HEAP_EXTEND_SIZE ? MALLOC_HEAP_EXTEND_SIZE : MALLOC_ROUND_UP_TO_PAGE_SIZE (size)); + +#ifdef MALLOC_USE_SBRK + /* Get the sbrk lock while we've still got the main lock. */ + __malloc_lock_sbrk (); +#endif + + /* Don't hold the main lock during the syscall, so that small + allocations in a different thread may succeed while we're + blocked. */ + __malloc_unlock (); + /* Allocate the new heap block. */ #ifdef MALLOC_USE_SBRK + /* Use sbrk we can, as it's faster than mmap, and guarantees contiguous allocation. */ - void *block = sbrk (block_size); -#else - /* Otherwise, use mmap. */ - void *block = mmap (0, block_size, PROT_READ | PROT_WRITE, - MAP_SHARED | MAP_ANONYMOUS, 0, 0); -#endif - + block = sbrk (block_size); if (block != (void *)-1) { -#ifdef MALLOC_USE_SBRK /* Because sbrk can return results of arbitrary alignment, align the result to a MALLOC_ALIGNMENT boundary. */ long aligned_block = MALLOC_ROUND_UP ((long)block, MALLOC_ALIGNMENT); @@ -71,8 +88,22 @@ malloc (size_t size) sbrk (aligned_block - (long)block); block = (void *)aligned_block; } + } + __malloc_unlock_sbrk (); + +#else /* !MALLOC_USE_SBRK */ + + /* Otherwise, use mmap. */ + block = mmap (0, block_size, PROT_READ | PROT_WRITE, + MAP_SHARED | MAP_ANONYMOUS, 0, 0); + #endif /* MALLOC_USE_SBRK */ + /* Get back the main lock. */ + __malloc_lock (); + + if (block != (void *)-1) + { MALLOC_DEBUG (" adding memory: 0x%lx - 0x%lx (%d bytes)\n", (long)block, (long)block + block_size, block_size); @@ -84,6 +115,8 @@ malloc (size_t size) } } + __malloc_unlock (); + if (mem) /* Record the size of this block just before the returned address. */ { diff --git a/libc/stdlib/malloc/malloc.h b/libc/stdlib/malloc/malloc.h index 0cab1dba2..f01484368 100644 --- a/libc/stdlib/malloc/malloc.h +++ b/libc/stdlib/malloc/malloc.h @@ -38,10 +38,46 @@ mmap/munmap, and guarantees contiguous allocation, but is also less flexible, and causes the heap to only be shrinkable from the end. */ #ifdef __UCLIBC_HAS_MMU__ -#define MALLOC_USE_SBRK +# define MALLOC_USE_SBRK #endif +#ifdef __UCLIBC_HAS_THREADS__ + +# include + +# define MALLOC_USE_LOCKING + +typedef pthread_mutex_t malloc_mutex_t; +# define MALLOC_MUTEX_INIT PTHREAD_MUTEX_INITIALIZER + +/* The main malloc lock. This must be hold while accessing __malloc_heap, + and in order to gain __malloc_sbrk_lock. */ +extern malloc_mutex_t __malloc_lock; +# define __malloc_lock() pthread_mutex_lock (&__malloc_lock) +# define __malloc_unlock() pthread_mutex_unlock (&__malloc_lock) + +# ifdef MALLOC_USE_SBRK +/* This lock is used to serialize uses of the `sbrk' function (in both + malloc and free, sbrk may be used several times in succession, and + things will break if these multiple calls are interleaved with another + thread's use of sbrk!). */ +extern malloc_mutex_t __malloc_sbrk_lock; +# define __malloc_lock_sbrk() pthread_mutex_lock (&__malloc_sbrk_lock) +# define __malloc_unlock_sbrk() pthread_mutex_unlock (&__malloc_sbrk_lock) +# endif /* MALLOC_USE_SBRK */ + +#else /* !__UCLIBC_HAS_THREADS__ */ + +/* Without threads, mutex operations are a nop. */ +# define __malloc_lock() (void)0 +# define __malloc_unlock() (void)0 +# define __malloc_lock_sbrk() (void)0 +# define __malloc_unlock_sbrk() (void)0 + +#endif /* __UCLIBC_HAS_THREADS__ */ + + /* Change this to `#if 1' to cause malloc to emit debugging info to stderr. */ #if 0 #include diff --git a/libc/stdlib/malloc/realloc.c b/libc/stdlib/malloc/realloc.c index 7d8227aff..7a89712e3 100644 --- a/libc/stdlib/malloc/realloc.c +++ b/libc/stdlib/malloc/realloc.c @@ -39,7 +39,10 @@ realloc (void *mem, size_t new_size) size_t ext_size = new_size - size; void *ext_addr = (char *)base_mem + ext_size; + __malloc_lock (); ext_size = __heap_alloc_at (&__malloc_heap, ext_addr, ext_size); + __malloc_unlock (); + if (! ext_size) /* Our attempts to extend MEM in place failed, just allocate-and-copy. */ -- cgit v1.2.3