Changeset d851f597 in mainline for uspace/lib/libc/generic/malloc.c

Timestamp:

2009-07-02T14:51:09Z (15 years ago)

Author:

Martin Decky <martin@…>

Branches:

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

Children:

271283b

Parents:

9c40f88

Message:

small allocator optimization
add some comments

File:

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

uspace/lib/libc/generic/malloc.c

@@ -277 +277 @@
                                 result = addr;
                         } else {
-                                /* Block start has to be aligned, thus
-                                   the previous block needs to be enlarged */
+                                /* Block start has to be aligned */
                                 size_t excess = (size_t) (aligned - addr);
                                 
                                 if (cur->size >= real_size + excess) {
+                                        /* The current block is large enought to fit
+                                           data in including alignment */
                                         if ((void *) cur > heap_start) {
-                                                // TODO: This can be optimized further in case
-                                                // of expanding a previous allocated block if the
-                                                // excess is large enought to put another free
-                                                // block in between
+                                                /* 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);
@@ -296 +296 @@
                                                 
                                                 size_t reduced_size = cur->size - excess;
-                                                cur = ((void *) cur) + excess;
-                                                
-                                                block_init(prev_head, prev_head->size + excess, prev_head->free);
-                                                block_init(cur, reduced_size, true);
-                                                split_mark(cur, real_size);
+                                                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 enought
+                                                           space to fill in a new free block between the previous
+                                                           and current block */
+                                                        block_init(cur, excess, true);
+                                                } 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);
+                                                }
+                                                
+                                                block_init(next_head, reduced_size, true);
+                                                split_mark(next_head, real_size);
                                                 result = aligned;
+                                                cur = next_head;
                                         } else {
+                                                /* The current block is the first block on the heap.
+                                                   We have to make sure that the alignment excess
+                                                   is large enought to fit a new free block just
+                                                   before the current block */
                                                 while (excess < STRUCT_OVERHEAD) {
                                                         aligned += falign;
@@ -308 +324 @@
                                                 }
                                                 
+                                                /* Check for current block size again */
                                                 if (cur->size >= real_size + excess) {
                                                         size_t reduced_size = cur->size - excess;