Changeset 98e4507 in mainline for uspace/lib/c/generic/malloc.c


Ignore:
Timestamp:
2011-05-20T01:13:40Z (13 years ago)
Author:
Petr Koupy <petr.koupy@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
5c460cc
Parents:
a0bb65af (diff), 326bf65 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge mainline changes.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    ra0bb65af r98e4507  
    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                size_t shrink_size = ALIGN_DOWN(last_head->size, PAGE_SIZE);
     400               
     401                if (first_head == last_head) {
     402                        /*
     403                         * The entire heap area consists of a single
     404                         * free heap block. This means we can get rid
     405                         * of it entirely.
     406                         */
     407                       
     408                        heap_area_t *prev = area->prev;
     409                        heap_area_t *next = area->next;
     410                       
     411                        if (prev != NULL) {
     412                                area_check(prev);
     413                                prev->next = next;
     414                        } else
     415                                first_heap_area = next;
     416                       
     417                        if (next != NULL) {
     418                                area_check(next);
     419                                next->prev = prev;
     420                        } else
     421                                last_heap_area = prev;
     422                       
     423                        as_area_destroy(area->start);
     424                } else if (shrink_size >= SHRINK_GRANULARITY) {
     425                        /*
     426                         * Make sure that we always shrink the area
     427                         * by a multiple of page size and update
     428                         * the block layout accordingly.
     429                         */
     430                       
     431                        size_t asize = (size_t) (area->end - area->start) - shrink_size;
     432                        void *end = (void *) ((uintptr_t) area->start + asize);
     433                       
     434                        /* Resize the address space area */
     435                        int ret = as_area_resize(area->start, asize, 0);
     436                        if (ret != EOK)
     437                                abort();
     438                       
     439                        /* Update heap area parameters */
     440                        area->end = end;
     441                       
     442                        /* Update block layout */
     443                        void *last = (void *) last_head;
     444                        size_t excess = (size_t) (area->end - last);
     445                       
     446                        if (excess > 0) {
     447                                if (excess >= STRUCT_OVERHEAD) {
     448                                        /*
     449                                         * The previous block cannot be free and there
     450                                         * is enough free space left in the area to
     451                                         * create a new free block.
     452                                         */
     453                                        block_init(last, excess, true, area);
     454                                } else {
     455                                        /*
     456                                         * The excess is small. Therefore just enlarge
     457                                         * the previous block.
     458                                         */
     459                                        heap_block_foot_t *prev_foot = (heap_block_foot_t *)
     460                                            (((uintptr_t) last_head) - sizeof(heap_block_foot_t));
     461                                        heap_block_head_t *prev_head = BLOCK_HEAD(prev_foot);
     462                                       
     463                                        block_check((void *) prev_head);
     464                                       
     465                                        block_init(prev_head, prev_head->size + excess,
     466                                            prev_head->free, area);
     467                                }
     468                        }
     469                }
     470        }
     471       
    337472        next = NULL;
    338473}
    … …  
    398533{
    399534        area_check((void *) area);
    400         assert((void *) first_block >= (void *) AREA_FIRST_BLOCK(area));
     535        assert((void *) first_block >= (void *) AREA_FIRST_BLOCK_HEAD(area));
    401536        assert((void *) first_block < area->end);
    402537       
    403         heap_block_head_t *cur;
    404         for (cur = first_block; (void *) cur < area->end;
     538        for (heap_block_head_t *cur = first_block; (void *) cur < area->end;
    405539            cur = (heap_block_head_t *) (((void *) cur) + cur->size)) {
    406540                block_check(cur);
    … …  
    436570                                         * data in (including alignment).
    437571                                         */
    438                                         if ((void *) cur > (void *) AREA_FIRST_BLOCK(area)) {
     572                                        if ((void *) cur > (void *) AREA_FIRST_BLOCK_HEAD(area)) {
    439573                                                /*
    440574                                                 * There is a block before the current block.
    … …  
    496630                                                        size_t reduced_size = cur->size - excess;
    497631                                                        cur = (heap_block_head_t *)
    498                                                             (AREA_FIRST_BLOCK(area) + excess);
     632                                                            (AREA_FIRST_BLOCK_HEAD(area) + excess);
    499633                                                       
    500                                                         block_init((void *) AREA_FIRST_BLOCK(area), excess,
    501                                                             true, area);
     634                                                        block_init((void *) AREA_FIRST_BLOCK_HEAD(area),
     635                                                            excess, true, area);
    502636                                                        block_init(cur, reduced_size, true, area);
    503637                                                        split_mark(cur, real_size);
    … …  
    552686       
    553687        /* Search the entire heap */
    554         heap_area_t *area;
    555         for (area = first_heap_area; area != NULL; area = area->next) {
     688        for (heap_area_t *area = first_heap_area; area != NULL;
     689            area = area->next) {
    556690                heap_block_head_t *first = (heap_block_head_t *)
    557                     AREA_FIRST_BLOCK(area);
     691                    AREA_FIRST_BLOCK_HEAD(area);
    558692               
    559693                void *addr = malloc_area(area, first, split, real_size,
    … …  
    657791       
    658792        area_check(area);
    659         assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));
     793        assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));
    660794        assert((void *) head < area->end);
    661795       
    … …  
    675809                        block_init((void *) head + real_size,
    676810                            orig_size - real_size, true, area);
    677                         heap_shrink();
     811                        heap_shrink(area);
    678812                }
    679813               
    … …  
    734868       
    735869        area_check(area);
    736         assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));
     870        assert((void *) head >= (void *) AREA_FIRST_BLOCK_HEAD(area));
    737871        assert((void *) head < area->end);
    738872       
    … …  
    751885       
    752886        /* Look at the previous block. If it is free, merge the two. */
    753         if ((void *) head > (void *) AREA_FIRST_BLOCK(area)) {
     887        if ((void *) head > (void *) AREA_FIRST_BLOCK_HEAD(area)) {
    754888                heap_block_foot_t *prev_foot =
    755889                    (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t));
    … …  
    765899        }
    766900       
    767         heap_shrink();
     901        heap_shrink(area);
    768902       
    769903        futex_up(&malloc_futex);
Note: See TracChangeset for help on using the changeset viewer.