Changeset 7aafdb86 in mainline for uspace/lib/c/generic/malloc.c

Timestamp:

2012-07-23T04:22:12Z (12 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

e7c3fa0

Parents:

76c07e4

git-author:

Jiri Zarevucky <zarevucky.jiri@…> (2012-07-23 04:22:12)

git-committer:

Jakub Jermar <jakub@…> (2012-07-23 04:22:12)

Message:

When growing heap to satisfy an allocation request of s bytes aligned to
an a-byte boundary, the heap needs to be grown by at least a + s bytes.

When growing heap, try the subsequent allocation on the area which has
been grown to avoid unnecessary search of a suitable area.

(Thanks to Jiri Zarevucky.)

File:

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

uspace/lib/c/generic/malloc.c

@@ -109 +109 @@
         (((uintptr_t) (area)->end) - sizeof(heap_block_foot_t))
 
+#define AREA_LAST_BLOCK_HEAD(area) \
+        ((uintptr_t) BLOCK_HEAD(((heap_block_foot_t *)AREA_LAST_BLOCK_FOOT(area))))
+
 /** Get header in heap block.
  *
@@ -346 +349 @@
                 return false;
         
-        /* 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);
+        heap_block_head_t *last_head = (heap_block_head_t *) AREA_LAST_BLOCK_HEAD(area);
+        
+        if (last_head->free) {
+                /* Add the new space to the last block. */
+                size_t net_size = (size_t) (end - area->end) + last_head->size;
+                malloc_assert(net_size > 0);
+                block_init(last_head, net_size, true, area);
+        } else {
+                /* 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 */
@@ -355 +367 @@
         
         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;
-        
-        /* 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));
 }
 
@@ -661 +650 @@
 }
 
+/** Try to enlarge any of the heap areas.
+ *  If successful, allocate block of the given size in the area.
+ *
+ * Should be called only inside the critical section.
+ *
+ * @param size Gross size of item to allocate (bytes).
+ * @param align Memory address alignment.
+ *
+ */
+static void *heap_grow_and_alloc(size_t size, size_t align)
+{
+        if (size == 0)
+                return NULL;
+                
+        /* 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 + align)) {
+                        heap_block_head_t *first = (heap_block_head_t *) AREA_LAST_BLOCK_HEAD(area);
+                        
+                        void *addr = malloc_area(area, first, NULL, size, align);
+                        malloc_assert(addr != NULL);
+                        return addr;
+                }
+        }
+        
+        /* Eventually try to create a new area */
+        if (area_create(AREA_OVERHEAD(size + align))) {
+                heap_block_head_t *first = (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(last_heap_area);
+                
+                void *addr = malloc_area(last_heap_area, first, NULL, size, align);
+                malloc_assert(addr != NULL);
+                return addr;
+        }
+        
+        return NULL;
+}
+
 /** Allocate a memory block
  *
@@ -679 +707 @@
         
         size_t falign = lcm(align, BASE_ALIGN);
-        size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
-        
-        bool retry = false;
+        size_t gross_size = GROSS_SIZE(size);
+        
         heap_block_head_t *split;
-        
-loop:
         
         /* Try the next fit approach */
@@ -690 +715 @@
         
         if (split != NULL) {
-                void *addr = malloc_area(split->area, split, NULL, real_size,
+                void *addr = malloc_area(split->area, split, NULL, gross_size,
                     falign);
                 
@@ -703 +728 @@
                     AREA_FIRST_BLOCK_HEAD(area);
                 
-                void *addr = malloc_area(area, first, split, real_size,
+                void *addr = malloc_area(area, first, split, gross_size,
                     falign);
                 
@@ -710 +735 @@
         }
         
-        if (!retry) {
-                /* Try to grow the heap space */
-                if (heap_grow(real_size)) {
-                        retry = true;
-                        goto loop;
-                }
-        }
-        
-        return NULL;
+        /* Finally, try to grow heap space and allocate in the new area. */
+        return heap_grow_and_alloc(gross_size, falign);
 }