Changeset 013a5d7 in mainline for uspace/lib/c/generic/malloc.c


Ignore:
Timestamp:
2011-05-17T15:13:00Z (14 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
38c773e7
Parents:
f414851
Message:

add proper heap shrinking implementation
add malloc3 test (a derivative of malloc1 which forces the allocator to create multiple heap areas)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/c/generic/malloc.c

    rf414851 r013a5d7  
    6565#define BASE_ALIGN  16
    6666
     67/** Heap shrink granularity
     68 *
     69 * Try not to pump and stress the heap to much
     70 * by shrinking and enlarging it too often.
     71 * A heap area won't shrunk if it the released
     72 * free block is smaller than this constant.
     73 *
     74 */
     75#define SHRINK_GRANULARITY  (64 * PAGE_SIZE)
     76
    6777/** Overhead of each heap block. */
    6878#define STRUCT_OVERHEAD \
    … …  
    8696 *
    8797 */
    88 #define AREA_FIRST_BLOCK(area) \
     98#define AREA_FIRST_BLOCK_HEAD(area) \
    8999        (ALIGN_UP(((uintptr_t) (area)) + sizeof(heap_area_t), BASE_ALIGN))
     100
     101/** Get last block in heap area.
     102 *
     103 */
     104#define AREA_LAST_BLOCK_FOOT(area) \
     105        (((uintptr_t) (area)->end) - sizeof(heap_block_foot_t))
     106
     107/** Get header in heap block.
     108 *
     109 */
     110#define BLOCK_HEAD(foot) \
     111        ((heap_block_head_t *) \
     112            (((uintptr_t) (foot)) + sizeof(heap_block_foot_t) - (foot)->size))
    90113
    91114/** Get footer in heap block.
    … …  
    94117#define BLOCK_FOOT(head) \
    95118        ((heap_block_foot_t *) \
    96             (((uintptr_t) head) + head->size - sizeof(heap_block_foot_t)))
     119            (((uintptr_t) (head)) + (head)->size - sizeof(heap_block_foot_t)))
    97120
    98121/** Heap area.
    … …  
    115138        void *end;
    116139       
     140        /** Previous heap area */
     141        struct heap_area *prev;
     142       
    117143        /** Next heap area */
    118144        struct heap_area *next;
    … …  
    212238/** Check a heap area structure
    213239 *
     240 * Should be called only inside the critical section.
     241 *
    214242 * @param addr Address of the heap area.
    215243 *
    … …  
    220248       
    221249        assert(area->magic == HEAP_AREA_MAGIC);
     250        assert(addr == area->start);
    222251        assert(area->start < area->end);
    223252        assert(((uintptr_t) area->start % PAGE_SIZE) == 0);
    … …  
    227256/** Create new heap area
    228257 *
    229  * @param start Preffered starting address of the new area.
    230  * @param size  Size of the area.
     258 * Should be called only inside the critical section.
     259 *
     260 * @param size Size of the area.
    231261 *
    232262 */
    … …  
    248278       
    249279        area->start = astart;
    250         area->end = (void *)
    251             ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN);
     280        area->end = (void *) ((uintptr_t) astart + asize);
     281        area->prev = NULL;
    252282        area->next = NULL;
    253283        area->magic = HEAP_AREA_MAGIC;
    254284       
    255         void *block = (void *) AREA_FIRST_BLOCK(area);
     285        void *block = (void *) AREA_FIRST_BLOCK_HEAD(area);
    256286        size_t bsize = (size_t) (area->end - block);
    257287       
    … …  
    262292                last_heap_area = area;
    263293        } else {
     294                area->prev = last_heap_area;
    264295                last_heap_area->next = area;
    265296                last_heap_area = area;
    … …  
    271302/** Try to enlarge a heap area
    272303 *
     304 * Should be called only inside the critical section.
     305 *
    273306 * @param area Heap area to grow.
    274  * @param size Gross size of item to allocate (bytes).
     307 * @param size Gross size to grow (bytes).
     308 *
     309 * @return True if successful.
    275310 *
    276311 */
    … …  
    282317        area_check(area);
    283318       
    284         size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size,
    285             PAGE_SIZE);
    286        
    287319        /* New heap area size */
    288         void *end = (void *)
    289             ALIGN_DOWN((uintptr_t) area->start + asize, BASE_ALIGN);
     320        size_t gross_size = (size_t) (area->end - area->start) + size;
     321        size_t asize = ALIGN_UP(gross_size, PAGE_SIZE);
     322        void *end = (void *) ((uintptr_t) area->start + asize);
    290323       
    291324        /* Check for overflow */
    … …  
    299332       
    300333        /* Add new free block */
    301         block_init(area->end, (size_t) (end - area->end), true, area);
     334        size_t net_size = (size_t) (end - area->end);
     335        if (net_size > 0)
     336                block_init(area->end, net_size, true, area);
    302337       
    303338        /* Update heap area parameters */
    … …  
    309344/** Try to enlarge any of the heap areas
    310345 *
     346 * Should be called only inside the critical section.
     347 *
    311348 * @param size Gross size of item to allocate (bytes).
    312349 *
    … …  
    318355       
    319356        /* First try to enlarge some existing area */
    320         heap_area_t *area;
    321         for (area = first_heap_area; area != NULL; area = area->next) {
     357        for (heap_area_t *area = first_heap_area; area != NULL;
     358            area = area->next) {
    322359                if (area_grow(area, size))
    323360                        return true;
    … …  
    325362       
    326363        /* Eventually try to create a new area */
    327         return area_create(AREA_FIRST_BLOCK(size));
    328 }
    329 
    330 /** Try to shrink heap space
    331  *
     364        return area_create(AREA_FIRST_BLOCK_HEAD(size));
     365}
     366
     367/** Try to shrink heap
     368 *
     369 * Should be called only inside the critical section.
    332370 * In all cases the next pointer is reset.
    333371 *
    334  */
    335 static void heap_shrink(void)
    336 {
     372 * @param area Last modified heap area.
     373 *
     374 */
     375static void heap_shrink(heap_area_t *area)
     376{
     377        area_check(area);
     378       
     379        heap_block_foot_t *last_foot =
     380            (heap_block_foot_t *) AREA_LAST_BLOCK_FOOT(area);
     381        heap_block_head_t *last_head = BLOCK_HEAD(last_foot);
     382       
     383        block_check((void *) last_head);
     384        assert(last_head->area == area);
     385       
     386        if (last_head->free) {
     387                /*
     388                 * The last block of the heap area is
     389                 * unused. The area might be potentially
     390                 * shrunk.
     391                 */
     392               
     393                heap_block_head_t *first_head =
     394                    (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(area);
     395               
     396                block_check((void *) first_head);
     397                assert(first_head->area == area);
     398               
     399                if (first_head == last_head) {
     400                        /*
     401                         * The entire heap area consists of a single
     402                         * free heap block. This means we can get rid
     403                         * of it entirely.
     404                         */
     405                       
     406                        heap_area_t *prev = area->prev;
     407                        heap_area_t *next = area->next;
     408                       
     409                        if (prev != NULL) {
     410                                area_check(prev);
     411                                prev->next = next;
     412                        } else
     413                                first_heap_area = next;
     414                       
     415                        if (next != NULL) {
     416                                area_check(next);
     417                                next->prev = prev;
     418                        } else
     419                                last_heap_area = prev;
     420                       
     421                        as_area_destroy(area->start);
     422                } else if (last_head->size >= SHRINK_GRANULARITY) {
     423                        /*
     424                         * Make sure that we always shrink the area
     425                         * by a multiple of page size and update
     426                         * the block layout accordingly.
     427                         */
     428                       
     429                        size_t shrink_size = ALIGN_DOWN(last_head->size, PAGE_SIZE);
     430                        size_t asize = (size_t) (area->end - area->start) - shrink_size;
     431                        void *end = (void *) ((uintptr_t) area->start + asize);
     432                       
     433                        /* Resize the address space area */
     434                        int ret = as_area_resize(area->start, asize, 0);
     435                        if (ret != EOK)
     436                                abort();
     437                       
     438                        /* Update heap area parameters */
     439                        area->end = end;
     440                       
     441                        /* Update block layout */
     442                        void *last = (void *) last_head;
     443                        size_t excess = (size_t) (area->end - last);
     444                       
     445                        if (excess > 0) {
     446                                if (excess >= STRUCT_OVERHEAD) {
     447                                        /*
     448                                         * The previous block cannot be free and there
     449                                         * is enough free space left in the area to
     450                                         * create a new free block.
     451                                         */
     452                                        block_init(last, excess, true, area);
     453                                } else {
     454                                        /*
     455                                         * The excess is small. Therefore just enlarge
     456                                         * the previous block.
     457                                         */
     458                                        heap_block_foot_t *prev_foot = (heap_block_foot_t *)
     459                                            (((uintptr_t) last_head) - sizeof(heap_block_foot_t));
     460                                        heap_block_head_t *prev_head = BLOCK_HEAD(prev_foot);
     461                                       
     462                                        block_check((void *) prev_head);
     463                                       
     464                                        block_init(prev_head, prev_head->size + excess,
     465                                            prev_head->free, area);
     466                                }
     467                        }
     468                       
     469                       
     470                }
     471        }
     472       
    337473        next = NULL;
    338474}
    … …  
    398534{
    399535        area_check((void *) area);
    400         assert((void *) first_block >= (void *) AREA_FIRST_BLOCK(area));
     536        assert((void *) first_block >= (void *) AREA_FIRST_BLOCK_HEAD(area));
    401537        assert((void *) first_block < area->end);
    402538       
    403         heap_block_head_t *cur;
    404         for (cur = first_block; (void *) cur < area->end;
     539        for (heap_block_head_t *cur = first_block; (void *) cur < area->end;
    405540            cur = (heap_block_head_t *) (((void *) cur) + cur->size)) {
    406541                block_check(cur);
    … …  
    436571                                         * data in (including alignment).
    437572                                         */
    438                                         if ((void *) cur > (void *) AREA_FIRST_BLOCK(area)) {
     573                                        if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(area)) {
    439574                                                /*
    440575                                                 * There is a block before the current block.
    … …  
    496631                                                        size_t reduced_size = cur->size - excess;
    497632                                                        cur = (heap_block_head_t *)
    498                                                             (AREA_FIRST_BLOCK(area) + excess);
     633                                                            (AREA_FIRST_BLOCK_HEAD(area) + excess);
    499634                                                       
    500                                                         block_init((void *) AREA_FIRST_BLOCK(area), excess,
    501                                                             true, area);
     635                                                        block_init((void *) AREA_FIRST_BLOCK_HEAD(area),
     636                                                            excess, true, area);
    502637                                                        block_init(cur, reduced_size, true, area);
    503638                                                        split_mark(cur, real_size);
    … …  
    552687       
    553688        /* Search the entire heap */
    554         heap_area_t *area;
    555         for (area = first_heap_area; area != NULL; area = area->next) {
     689        for (heap_area_t *area = first_heap_area; area != NULL;
     690            area = area->next) {
    556691                heap_block_head_t *first = (heap_block_head_t *)
    557                     AREA_FIRST_BLOCK(area);
     692                    AREA_FIRST_BLOCK_HEAD(area);
    558693               
    559694                void *addr = malloc_area(area, first, split, real_size,
    … …  
    657792       
    658793        area_check(area);
    659         assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));
     794        assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));
    660795        assert((void *) head < area->end);
    661796       
    … …  
    675810                        block_init((void *) head + real_size,
    676811                            orig_size - real_size, true, area);
    677                         heap_shrink();
     812                        heap_shrink(area);
    678813                }
    679814               
    … …  
    734869       
    735870        area_check(area);
    736         assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));
     871        assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));
    737872        assert((void *) head < area->end);
    738873       
    … …  
    751886       
    752887        /* Look at the previous block. If it is free, merge the two. */
    753         if ((void *) head > (void *) AREA_FIRST_BLOCK(area)) {
     888        if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) {
    754889                heap_block_foot_t *prev_foot =
    755890                    (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t));
    … …  
    765900        }
    766901       
    767         heap_shrink();
     902        heap_shrink(area);
    768903       
    769904        futex_up(&malloc_futex);
Note: See TracChangeset for help on using the changeset viewer.