Changes in uspace/lib/c/generic/malloc.c [47b7006:207533f] in mainline

File:

• uspace/lib/c/generic/malloc.c (modified) (18 diffs)

uspace/lib/c/generic/malloc.c

@@ -44 +44 @@
 #include <mem.h>
 #include <futex.h>
+#include <stdlib.h>
 #include <adt/gcdlcm.h>
 #include "private/malloc.h"
 
-/* Magic used in heap headers. */
-#define HEAP_BLOCK_HEAD_MAGIC  0xBEEF0101
-
-/* Magic used in heap footers. */
-#define HEAP_BLOCK_FOOT_MAGIC  0xBEEF0202
-
-/** Allocation alignment (this also covers the alignment of fields
-    in the heap header and footer) */
+/** Magic used in heap headers. */
+#define HEAP_BLOCK_HEAD_MAGIC  UINT32_C(0xBEEF0101)
+
+/** Magic used in heap footers. */
+#define HEAP_BLOCK_FOOT_MAGIC  UINT32_C(0xBEEF0202)
+
+/** Magic used in heap descriptor. */
+#define HEAP_AREA_MAGIC  UINT32_C(0xBEEFCAFE)
+
+/** Allocation alignment.
+ *
+ * This also covers the alignment of fields
+ * in the heap header and footer.
+ *
+ */
 #define BASE_ALIGN  16
 
-/**
- * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures
- */
-#define MAX_HEAP_SIZE  (sizeof(uintptr_t) << 28)
-
-/**
- *
- */
-#define STRUCT_OVERHEAD  (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t))
-
-/**
- * Calculate real size of a heap block (with header and footer)
+/** Heap shrink granularity
+ *
+ * Try not to pump and stress the heap to much
+ * by shrinking and enlarging it too often.
+ * A heap area won't shrunk if it the released
+ * free block is smaller than this constant.
+ *
+ */
+#define SHRINK_GRANULARITY  (64 * PAGE_SIZE)
+
+/** Overhead of each heap block. */
+#define STRUCT_OVERHEAD \
+        (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t))
+
+/** Overhead of each area. */
+#define AREA_OVERHEAD(size) \
+        (ALIGN_UP(size + sizeof(heap_area_t), BASE_ALIGN))
+
+/** Calculate real size of a heap block.
+ *
+ * Add header and footer size.
+ *
  */
 #define GROSS_SIZE(size)  ((size) + STRUCT_OVERHEAD)
 
-/**
- * Calculate net size of a heap block (without header and footer)
+/** Calculate net size of a heap block.
+ *
+ * Subtract header and footer size.
+ *
  */
 #define NET_SIZE(size)  ((size) - STRUCT_OVERHEAD)
+
+/** Get first block in heap area.
+ *
+ */
+#define AREA_FIRST_BLOCK_HEAD(area) \
+        (ALIGN_UP(((uintptr_t) (area)) + sizeof(heap_area_t), BASE_ALIGN))
+
+/** Get last block in heap area.
+ *
+ */
+#define AREA_LAST_BLOCK_FOOT(area) \
+        (((uintptr_t) (area)->end) - sizeof(heap_block_foot_t))
+
+/** Get header in heap block.
+ *
+ */
+#define BLOCK_HEAD(foot) \
+        ((heap_block_head_t *) \
+            (((uintptr_t) (foot)) + sizeof(heap_block_foot_t) - (foot)->size))
+
+/** Get footer in heap block.
+ *
+ */
+#define BLOCK_FOOT(head) \
+        ((heap_block_foot_t *) \
+            (((uintptr_t) (head)) + (head)->size - sizeof(heap_block_foot_t)))
+
+/** Heap area.
+ *
+ * The memory managed by the heap allocator is divided into
+ * multiple discontinuous heaps. Each heap is represented
+ * by a separate address space area which has this structure
+ * at its very beginning.
+ *
+ */
+typedef struct heap_area {
+        /** Start of the heap area (including this structure)
+         *
+         * Aligned on page boundary.
+         *
+         */
+        void *start;
+        
+        /** End of the heap area (aligned on page boundary) */
+        void *end;
+        
+        /** Previous heap area */
+        struct heap_area *prev;
+        
+        /** Next heap area */
+        struct heap_area *next;
+        
+        /** A magic value */
+        uint32_t magic;
+} heap_area_t;
 
 /** Header of a heap block
@@ -87 +162 @@
         bool free;
         
+        /** Heap area this block belongs to */
+        heap_area_t *area;
+        
         /* A magic value to detect overwrite of heap header */
         uint32_t magic;
@@ -102 +180 @@
 } heap_block_foot_t;
 
-/** Linker heap symbol */
-extern char _heap;
+/** First heap area */
+static heap_area_t *first_heap_area = NULL;
+
+/** Last heap area */
+static heap_area_t *last_heap_area = NULL;
+
+/** Next heap block to examine (next fit algorithm) */
+static heap_block_head_t *next_fit = NULL;
 
 /** Futex for thread-safe heap manipulation */
 static futex_t malloc_futex = FUTEX_INITIALIZER;
 
-/** Address of heap start */
-static void *heap_start = 0;
-
-/** Address of heap end */
-static void *heap_end = 0;
-
-/** Maximum heap size */
-static size_t max_heap_size = (size_t) -1;
-
-/** Current number of pages of heap area */
-static size_t heap_pages = 0;
+#ifndef NDEBUG
+
+#define malloc_assert(expr) \
+        do { \
+                if (!(expr)) {\
+                        futex_up(&malloc_futex); \
+                        assert_abort(#expr, __FILE__, __LINE__); \
+                } \
+        } while (0)
+
+#else /* NDEBUG */
+
+#define malloc_assert(expr)
+
+#endif /* NDEBUG */
 
 /** Initialize a heap block
  *
- * Fills in the structures related to a heap block.
+ * Fill in the structures related to a heap block.
  * Should be called only inside the critical section.
  *
@@ -128 +216 @@
  * @param size Size of the block including the header and the footer.
  * @param free Indication of a free block.
- *
- */
-static void block_init(void *addr, size_t size, bool free)
+ * @param area Heap area the block belongs to.
+ *
+ */
+static void block_init(void *addr, size_t size, bool free, heap_area_t *area)
 {
         /* Calculate the position of the header and the footer */
         heap_block_head_t *head = (heap_block_head_t *) addr;
-        heap_block_foot_t *foot =
-            (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t));
         
         head->size = size;
         head->free = free;
+        head->area = area;
         head->magic = HEAP_BLOCK_HEAD_MAGIC;
+        
+        heap_block_foot_t *foot = BLOCK_FOOT(head);
         
         foot->size = size;
@@ -158 +248 @@
         heap_block_head_t *head = (heap_block_head_t *) addr;
         
-        assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);
-        
-        heap_block_foot_t *foot =
-            (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t));
-        
-        assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);
-        assert(head->size == foot->size);
-}
-
-/** Increase the heap area size
+        malloc_assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);
+        
+        heap_block_foot_t *foot = BLOCK_FOOT(head);
+        
+        malloc_assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);
+        malloc_assert(head->size == foot->size);
+}
+
+/** Check a heap area structure
  *
  * Should be called only inside the critical section.
  *
- * @param size Number of bytes to grow the heap by.
- *
- */
-static bool grow_heap(size_t size)
+ * @param addr Address of the heap area.
+ *
+ */
+static void area_check(void *addr)
+{
+        heap_area_t *area = (heap_area_t *) addr;
+        
+        malloc_assert(area->magic == HEAP_AREA_MAGIC);
+        malloc_assert(addr == area->start);
+        malloc_assert(area->start < area->end);
+        malloc_assert(((uintptr_t) area->start % PAGE_SIZE) == 0);
+        malloc_assert(((uintptr_t) area->end % PAGE_SIZE) == 0);
+}
+
+/** Create new heap area
+ *
+ * Should be called only inside the critical section.
+ *
+ * @param size Size of the area.
+ *
+ */
+static bool area_create(size_t size)
+{
+        void *start = as_get_mappable_page(size);
+        if (start == NULL)
+                return false;
+        
+        /* Align the heap area on page boundary */
+        void *astart = (void *) ALIGN_UP((uintptr_t) start, PAGE_SIZE);
+        size_t asize = ALIGN_UP(size, PAGE_SIZE);
+        
+        astart = as_area_create(astart, asize, AS_AREA_WRITE | AS_AREA_READ);
+        if (astart == (void *) -1)
+                return false;
+        
+        heap_area_t *area = (heap_area_t *) astart;
+        
+        area->start = astart;
+        area->end = (void *) ((uintptr_t) astart + asize);
+        area->prev = NULL;
+        area->next = NULL;
+        area->magic = HEAP_AREA_MAGIC;
+        
+        void *block = (void *) AREA_FIRST_BLOCK_HEAD(area);
+        size_t bsize = (size_t) (area->end - block);
+        
+        block_init(block, bsize, true, area);
+        
+        if (last_heap_area == NULL) {
+                first_heap_area = area;
+                last_heap_area = area;
+        } else {
+                area->prev = last_heap_area;
+                last_heap_area->next = area;
+                last_heap_area = area;
+        }
+        
+        return true;
+}
+
+/** Try to enlarge a heap area
+ *
+ * Should be called only inside the critical section.
+ *
+ * @param area Heap area to grow.
+ * @param size Gross size to grow (bytes).
+ *
+ * @return True if successful.
+ *
+ */
+static bool area_grow(heap_area_t *area, size_t size)
 {
         if (size == 0)
+                return true;
+        
+        area_check(area);
+        
+        /* New heap area size */
+        size_t gross_size = (size_t) (area->end - area->start) + size;
+        size_t asize = ALIGN_UP(gross_size, PAGE_SIZE);
+        void *end = (void *) ((uintptr_t) area->start + asize);
+        
+        /* Check for overflow */
+        if (end < area->start)
                 return false;
-
-        if ((heap_start + size < heap_start) || (heap_end + size < heap_end))
+        
+        /* Resize the address space area */
+        int ret = as_area_resize(area->start, asize, 0);
+        if (ret != EOK)
                 return false;
         
-        size_t heap_size = (size_t) (heap_end - heap_start);
-        
-        if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size))
-                return false;
-        
-        size_t pages = (size - 1) / PAGE_SIZE + 1;
-        
-        if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0)
-            == EOK) {
-                void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) +
-                    (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN);
-                block_init(heap_end, end - heap_end, true);
-                heap_pages += pages;
-                heap_end = end;
+        /* Add new free block */
+        size_t net_size = (size_t) (end - area->end);
+        if (net_size > 0)
+                block_init(area->end, net_size, true, area);
+        
+        /* Update heap area parameters */
+        area->end = end;
+        
+        return true;
+}
+
+/** Try to enlarge any of the heap areas
+ *
+ * Should be called only inside the critical section.
+ *
+ * @param size Gross size of item to allocate (bytes).
+ *
+ */
+static bool heap_grow(size_t size)
+{
+        if (size == 0)
                 return true;
-        }
-        
-        return false;
-}
-
-/** Decrease the heap area
+        
+        /* First try to enlarge some existing area */
+        for (heap_area_t *area = first_heap_area; area != NULL;
+            area = area->next) {
+                if (area_grow(area, size))
+                        return true;
+        }
+        
+        /* Eventually try to create a new area */
+        return area_create(AREA_OVERHEAD(size));
+}
+
+/** Try to shrink heap
  *
  * Should be called only inside the critical section.
- *
- * @param size Number of bytes to shrink the heap by.
- *
- */
-static void shrink_heap(void)
-{
-        // TODO
+ * In all cases the next pointer is reset.
+ *
+ * @param area Last modified heap area.
+ *
+ */
+static void heap_shrink(heap_area_t *area)
+{
+        area_check(area);
+        
+        heap_block_foot_t *last_foot =
+            (heap_block_foot_t *) AREA_LAST_BLOCK_FOOT(area);
+        heap_block_head_t *last_head = BLOCK_HEAD(last_foot);
+        
+        block_check((void *) last_head);
+        malloc_assert(last_head->area == area);
+        
+        if (last_head->free) {
+                /*
+                 * The last block of the heap area is
+                 * unused. The area might be potentially
+                 * shrunk.
+                 */
+                
+                heap_block_head_t *first_head =
+                    (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(area);
+                
+                block_check((void *) first_head);
+                malloc_assert(first_head->area == area);
+                
+                size_t shrink_size = ALIGN_DOWN(last_head->size, PAGE_SIZE);
+                
+                if (first_head == last_head) {
+                        /*
+                         * The entire heap area consists of a single
+                         * free heap block. This means we can get rid
+                         * of it entirely.
+                         */
+                        
+                        heap_area_t *prev = area->prev;
+                        heap_area_t *next = area->next;
+                        
+                        if (prev != NULL) {
+                                area_check(prev);
+                                prev->next = next;
+                        } else
+                                first_heap_area = next;
+                        
+                        if (next != NULL) {
+                                area_check(next);
+                                next->prev = prev;
+                        } else
+                                last_heap_area = prev;
+                        
+                        as_area_destroy(area->start);
+                } else if (shrink_size >= SHRINK_GRANULARITY) {
+                        /*
+                         * Make sure that we always shrink the area
+                         * by a multiple of page size and update
+                         * the block layout accordingly.
+                         */
+                        
+                        size_t asize = (size_t) (area->end - area->start) - shrink_size;
+                        void *end = (void *) ((uintptr_t) area->start + asize);
+                        
+                        /* Resize the address space area */
+                        int ret = as_area_resize(area->start, asize, 0);
+                        if (ret != EOK)
+                                abort();
+                        
+                        /* Update heap area parameters */
+                        area->end = end;
+                        size_t excess = ((size_t) area->end) - ((size_t) last_head);
+                        
+                        if (excess > 0) {
+                                if (excess >= STRUCT_OVERHEAD) {
+                                        /*
+                                         * The previous block cannot be free and there
+                                         * is enough free space left in the area to
+                                         * create a new free block.
+                                         */
+                                        block_init((void *) last_head, excess, true, area);
+                                } else {
+                                        /*
+                                         * The excess is small. Therefore just enlarge
+                                         * the previous block.
+                                         */
+                                        heap_block_foot_t *prev_foot = (heap_block_foot_t *)
+                                            (((uintptr_t) last_head) - sizeof(heap_block_foot_t));
+                                        heap_block_head_t *prev_head = BLOCK_HEAD(prev_foot);
+                                        
+                                        block_check((void *) prev_head);
+                                        
+                                        block_init(prev_head, prev_head->size + excess,
+                                            prev_head->free, area);
+                                }
+                        }
+                }
+        }
+        
+        next_fit = NULL;
 }
 
@@ -223 +499 @@
 void __malloc_init(void)
 {
-        if (!as_area_create((void *) &_heap, PAGE_SIZE,
-            AS_AREA_WRITE | AS_AREA_READ))
+        if (!area_create(PAGE_SIZE))
                 abort();
-        
-        heap_pages = 1;
-        heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN);
-        heap_end =
-            (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN);
-        
-        /* Make the entire area one large block. */
-        block_init(heap_start, heap_end - heap_start, true);
-}
-
-/** Get maximum heap address
- *
- */
-uintptr_t get_max_heap_addr(void)
-{
-        futex_down(&malloc_futex);
-        
-        if (max_heap_size == (size_t) -1)
-                max_heap_size =
-                    max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE);
-        
-        uintptr_t max_heap_addr = (uintptr_t) heap_start + max_heap_size;
-        
-        futex_up(&malloc_futex);
-        
-        return max_heap_addr;
 }
 
@@ -265 +514 @@
 static void split_mark(heap_block_head_t *cur, const size_t size)
 {
-        assert(cur->size >= size);
+        malloc_assert(cur->size >= size);
         
         /* See if we should split the block. */
@@ -273 +522 @@
                 /* Block big enough -> split. */
                 void *next = ((void *) cur) + size;
-                block_init(next, cur->size - size, true);
-                block_init(cur, size, false);
+                block_init(next, cur->size - size, true, cur->area);
+                block_init(cur, size, false, cur->area);
         } else {
                 /* Block too small -> use as is. */
@@ -281 +530 @@
 }
 
-/** Allocate a memory block
+/** Allocate memory from heap area starting from given block
  *
  * Should be called only inside the critical section.
- *
- * @param size  The size of the block to allocate.
- * @param align Memory address alignment.
- *
- * @return the address of the block or NULL when not enough memory.
- *
- */
-static void *malloc_internal(const size_t size, const size_t align)
-{
-        if (align == 0)
-                return NULL;
-        
-        size_t falign = lcm(align, BASE_ALIGN);
-        size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
-        
-        bool grown = false;
-        void *result;
-        
-loop:
-        result = NULL;
-        heap_block_head_t *cur = (heap_block_head_t *) heap_start;
-        
-        while ((result == NULL) && ((void *) cur < heap_end)) {
+ * As a side effect this function also sets the current
+ * pointer on successful allocation.
+ *
+ * @param area        Heap area where to allocate from.
+ * @param first_block Starting heap block.
+ * @param final_block Heap block where to finish the search
+ *                    (may be NULL).
+ * @param real_size   Gross number of bytes to allocate.
+ * @param falign      Physical alignment of the block.
+ *
+ * @return Address of the allocated block or NULL on not enough memory.
+ *
+ */
+static void *malloc_area(heap_area_t *area, heap_block_head_t *first_block,
+    heap_block_head_t *final_block, size_t real_size, size_t falign)
+{
+        area_check((void *) area);
+        malloc_assert((void *) first_block >= (void *) AREA_FIRST_BLOCK_HEAD(area));
+        malloc_assert((void *) first_block < area->end);
+        
+        for (heap_block_head_t *cur = first_block; (void *) cur < area->end;
+            cur = (heap_block_head_t *) (((void *) cur) + cur->size)) {
                 block_check(cur);
+                
+                /* Finish searching on the final block */
+                if ((final_block != NULL) && (cur == final_block))
+                        break;
                 
                 /* Try to find a block that is free and large enough. */
                 if ((cur->free) && (cur->size >= real_size)) {
-                        /* We have found a suitable block.
-                           Check for alignment properties. */
-                        void *addr = ((void *) cur) + sizeof(heap_block_head_t);
-                        void *aligned = (void *) ALIGN_UP(addr, falign);
+                        /*
+                         * We have found a suitable block.
+                         * Check for alignment properties.
+                         */
+                        void *addr = (void *)
+                            ((uintptr_t) cur + sizeof(heap_block_head_t));
+                        void *aligned = (void *)
+                            ALIGN_UP((uintptr_t) addr, falign);
                         
                         if (addr == aligned) {
                                 /* Exact block start including alignment. */
                                 split_mark(cur, real_size);
-                                result = addr;
+                                
+                                next_fit = cur;
+                                return addr;
                         } else {
                                 /* Block start has to be aligned */
@@ -325 +583 @@
                                 
                                 if (cur->size >= real_size + excess) {
-                                        /* The current block is large enough to fit
-                                           data in including alignment */
-                                        if ((void *) cur > heap_start) {
-                                                /* There is a block before the current block.
-                                                   This previous block can be enlarged to compensate
-                                                   for the alignment excess */
-                                                heap_block_foot_t *prev_foot =
-                                                    ((void *) cur) - sizeof(heap_block_foot_t);
+                                        /*
+                                         * The current block is large enough to fit
+                                         * data in (including alignment).
+                                         */
+                                        if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(area)) {
+                                                /*
+                                                 * There is a block before the current block.
+                                                 * This previous block can be enlarged to
+                                                 * compensate for the alignment excess.
+                                                 */
+                                                heap_block_foot_t *prev_foot = (heap_block_foot_t *)
+                                                    ((void *) cur - sizeof(heap_block_foot_t));
                                                 
-                                                heap_block_head_t *prev_head =
-                                                    (heap_block_head_t *) (((void *) cur) - prev_foot->size);
+                                                heap_block_head_t *prev_head = (heap_block_head_t *)
+                                                    ((void *) cur - prev_foot->size);
                                                 
                                                 block_check(prev_head);
@@ -342 +604 @@
                                                 heap_block_head_t *next_head = ((void *) cur) + excess;
                                                 
-                                                if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) {
-                                                        /* The previous block is not free and there is enough
-                                                           space to fill in a new free block between the previous
-                                                           and current block */
-                                                        block_init(cur, excess, true);
+                                                if ((!prev_head->free) &&
+                                                    (excess >= STRUCT_OVERHEAD)) {
+                                                        /*
+                                                         * The previous block is not free and there
+                                                         * is enough free space left to fill in
+                                                         * a new free block between the previous
+                                                         * and current block.
+                                                         */
+                                                        block_init(cur, excess, true, area);
                                                 } else {
-                                                        /* The previous block is free (thus there is no need to
-                                                           induce additional fragmentation to the heap) or the
-                                                           excess is small, thus just enlarge the previous block */
-                                                        block_init(prev_head, prev_head->size + excess, prev_head->free);
+                                                        /*
+                                                         * The previous block is free (thus there
+                                                         * is no need to induce additional
+                                                         * fragmentation to the heap) or the
+                                                         * excess is small. Therefore just enlarge
+                                                         * the previous block.
+                                                         */
+                                                        block_init(prev_head, prev_head->size + excess,
+                                                            prev_head->free, area);
                                                 }
                                                 
-                                                block_init(next_head, reduced_size, true);
+                                                block_init(next_head, reduced_size, true, area);
                                                 split_mark(next_head, real_size);
-                                                result = aligned;
-                                                cur = next_head;
+                                                
+                                                next_fit = next_head;
+                                                return aligned;
                                         } else {
-                                                /* The current block is the first block on the heap.
-                                                   We have to make sure that the alignment excess
-                                                   is large enough to fit a new free block just
-                                                   before the current block */
+                                                /*
+                                                 * The current block is the first block
+                                                 * in the heap area. We have to make sure
+                                                 * that the alignment excess is large enough
+                                                 * to fit a new free block just before the
+                                                 * current block.
+                                                 */
                                                 while (excess < STRUCT_OVERHEAD) {
                                                         aligned += falign;
@@ -371 +646 @@
                                                 if (cur->size >= real_size + excess) {
                                                         size_t reduced_size = cur->size - excess;
-                                                        cur = (heap_block_head_t *) (heap_start + excess);
+                                                        cur = (heap_block_head_t *)
+                                                            (AREA_FIRST_BLOCK_HEAD(area) + excess);
                                                         
-                                                        block_init(heap_start, excess, true);
-                                                        block_init(cur, reduced_size, true);
+                                                        block_init((void *) AREA_FIRST_BLOCK_HEAD(area),
+                                                            excess, true, area);
+                                                        block_init(cur, reduced_size, true, area);
                                                         split_mark(cur, real_size);
-                                                        result = aligned;
+                                                        
+                                                        next_fit = cur;
+                                                        return aligned;
                                                 }
                                         }
@@ -382 +661 @@
                         }
                 }
-                
-                /* Advance to the next block. */
-                cur = (heap_block_head_t *) (((void *) cur) + cur->size);
-        }
-        
-        if ((result == NULL) && (!grown)) {
-                if (grow_heap(real_size)) {
-                        grown = true;
+        }
+        
+        return NULL;
+}
+
+/** Allocate a memory block
+ *
+ * Should be called only inside the critical section.
+ *
+ * @param size  The size of the block to allocate.
+ * @param align Memory address alignment.
+ *
+ * @return Address of the allocated block or NULL on not enough memory.
+ *
+ */
+static void *malloc_internal(const size_t size, const size_t align)
+{
+        malloc_assert(first_heap_area != NULL);
+        
+        if (align == 0)
+                return NULL;
+        
+        size_t falign = lcm(align, BASE_ALIGN);
+        size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
+        
+        bool retry = false;
+        heap_block_head_t *split;
+        
+loop:
+        
+        /* Try the next fit approach */
+        split = next_fit;
+        
+        if (split != NULL) {
+                void *addr = malloc_area(split->area, split, NULL, real_size,
+                    falign);
+                
+                if (addr != NULL)
+                        return addr;
+        }
+        
+        /* Search the entire heap */
+        for (heap_area_t *area = first_heap_area; area != NULL;
+            area = area->next) {
+                heap_block_head_t *first = (heap_block_head_t *)
+                    AREA_FIRST_BLOCK_HEAD(area);
+                
+                void *addr = malloc_area(area, first, split, real_size,
+                    falign);
+                
+                if (addr != NULL)
+                        return addr;
+        }
+        
+        if (!retry) {
+                /* Try to grow the heap space */
+                if (heap_grow(real_size)) {
+                        retry = true;
                         goto loop;
                 }
         }
         
-        return result;
+        return NULL;
 }
 
@@ -473 +802 @@
             (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
         
-        assert((void *) head >= heap_start);
-        assert((void *) head < heap_end);
-        
         block_check(head);
-        assert(!head->free);
+        malloc_assert(!head->free);
+        
+        heap_area_t *area = head->area;
+        
+        area_check(area);
+        malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));
+        malloc_assert((void *) head < area->end);
         
         void *ptr = NULL;
@@ -487 +819 @@
                 /* Shrink */
                 if (orig_size - real_size >= STRUCT_OVERHEAD) {
-                        /* Split the original block to a full block
-                           and a trailing free block */
-                        block_init((void *) head, real_size, false);
+                        /*
+                         * Split the original block to a full block
+                         * and a trailing free block.
+                         */
+                        block_init((void *) head, real_size, false, area);
                         block_init((void *) head + real_size,
-                            orig_size - real_size, true);
-                        shrink_heap();
+                            orig_size - real_size, true, area);
+                        heap_shrink(area);
                 }
                 
                 ptr = ((void *) head) + sizeof(heap_block_head_t);
         } else {
-                /* Look at the next block. If it is free and the size is
-                   sufficient then merge the two. Otherwise just allocate
-                   a new block, copy the original data into it and
-                   free the original block. */
+                /*
+                 * Look at the next block. If it is free and the size is
+                 * sufficient then merge the two. Otherwise just allocate
+                 * a new block, copy the original data into it and
+                 * free the original block.
+                 */
                 heap_block_head_t *next_head =
                     (heap_block_head_t *) (((void *) head) + head->size);
                 
-                if (((void *) next_head < heap_end) &&
+                if (((void *) next_head < area->end) &&
                     (head->size + next_head->size >= real_size) &&
                     (next_head->free)) {
                         block_check(next_head);
-                        block_init(head, head->size + next_head->size, false);
+                        block_init(head, head->size + next_head->size, false, area);
                         split_mark(head, real_size);
                         
                         ptr = ((void *) head) + sizeof(heap_block_head_t);
+                        next_fit = NULL;
                 } else
                         reloc = true;
@@ -542 +879 @@
             = (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
         
-        assert((void *) head >= heap_start);
-        assert((void *) head < heap_end);
-        
         block_check(head);
-        assert(!head->free);
+        malloc_assert(!head->free);
+        
+        heap_area_t *area = head->area;
+        
+        area_check(area);
+        malloc_assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));
+        malloc_assert((void *) head < area->end);
         
         /* Mark the block itself as free. */
@@ -555 +895 @@
             = (heap_block_head_t *) (((void *) head) + head->size);
         
-        if ((void *) next_head < heap_end) {
+        if ((void *) next_head < area->end) {
                 block_check(next_head);
                 if (next_head->free)
-                        block_init(head, head->size + next_head->size, true);
+                        block_init(head, head->size + next_head->size, true, area);
         }
         
         /* Look at the previous block. If it is free, merge the two. */
-        if ((void *) head > heap_start) {
+        if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) {
                 heap_block_foot_t *prev_foot =
                     (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t));
@@ -572 +912 @@
                 
                 if (prev_head->free)
-                        block_init(prev_head, prev_head->size + head->size, true);
-        }
-        
-        shrink_heap();
+                        block_init(prev_head, prev_head->size + head->size, true,
+                            area);
+        }
+        
+        heap_shrink(area);
         
         futex_up(&malloc_futex);
 }
 
+void *heap_check(void)
+{
+        futex_down(&malloc_futex);
+        
+        if (first_heap_area == NULL) {
+                futex_up(&malloc_futex);
+                return (void *) -1;
+        }
+        
+        /* Walk all heap areas */
+        for (heap_area_t *area = first_heap_area; area != NULL;
+            area = area->next) {
+                
+                /* Check heap area consistency */
+                if ((area->magic != HEAP_AREA_MAGIC) ||
+                    ((void *) area != area->start) ||
+                    (area->start >= area->end) ||
+                    (((uintptr_t) area->start % PAGE_SIZE) != 0) ||
+                    (((uintptr_t) area->end % PAGE_SIZE) != 0)) {
+                        futex_up(&malloc_futex);
+                        return (void *) area;
+                }
+                
+                /* Walk all heap blocks */
+                for (heap_block_head_t *head = (heap_block_head_t *)
+                    AREA_FIRST_BLOCK_HEAD(area); (void *) head < area->end;
+                    head = (heap_block_head_t *) (((void *) head) + head->size)) {
+                        
+                        /* Check heap block consistency */
+                        if (head->magic != HEAP_BLOCK_HEAD_MAGIC) {
+                                futex_up(&malloc_futex);
+                                return (void *) head;
+                        }
+                        
+                        heap_block_foot_t *foot = BLOCK_FOOT(head);
+                        
+                        if ((foot->magic != HEAP_BLOCK_FOOT_MAGIC) ||
+                            (head->size != foot->size)) {
+                                futex_up(&malloc_futex);
+                                return (void *) foot;
+                        }
+                }
+        }
+        
+        futex_up(&malloc_futex);
+        
+        return NULL;
+}
+
 /** @}
  */