Changeset 0b37882 in mainline


Ignore:
Timestamp:
2011-02-03T21:14:23Z (14 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
17aca1c, 6a343bdf, cf2af94
Parents:
d88218b (diff), ae6f303 (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:

memory management work

  • implement as_get_mappable_page() as a new syscall (SYS_AS_GET_UNMAPPED_AREA), the kernel has a full knowledge of the address space areas, there is no need to duplicate this management in uspace)
  • make sure all address space/address space area manipulating functions use proper page alignment on base addresses and sizes (discrepancy with respect to this caused inconsistent behaviour, although no fatal bugs were probably present)
  • add forgotten tests (area != avoid) to check_area_conflicts()
  • unify size/page conversions (use always use bitwise shifts by PAGE_WIDTH)
  • new uspace heap allocator
    • basic next fit algorithm for better scalability (there is still space for optimizations)
    • support for multiple discontinuous heap areas (inspired by Jiri Tlach's implementation in lp:~jiri-tlach/helenos/nommu, but independent)
    • the "_heap" linker script symbol has been removed, the initial heap area is allocated according to as_get_mappable_page() (which uses the address of entry as the lower bound of the address space area base)
    • the hardwired 1 GB (4 GB respectivelly) heap size limit has been removed
    • the heap areas can be freely intermixed with other address space areas (e.g. mapped physical memory of devices, shared memory, etc.), the address space holes can be reused later (but still merging of adjunct address space areas is missing)
  • minor cstyle changes
Files:
27 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/include/mm/as.h

    rd88218b r0b37882  
    313313extern sysarg_t sys_as_area_change_flags(uintptr_t, unsigned int);
    314314extern sysarg_t sys_as_area_destroy(uintptr_t);
     315extern sysarg_t sys_as_get_unmapped_area(uintptr_t, size_t);
    315316
    316317/* Introspection functions. */
  • kernel/generic/include/syscall/syscall.h

    rd88218b r0b37882  
    5959        SYS_AS_AREA_CHANGE_FLAGS,
    6060        SYS_AS_AREA_DESTROY,
     61        SYS_AS_GET_UNMAPPED_AREA,
    6162       
    6263        SYS_IPC_CALL_SYNC_FAST,
  • kernel/generic/src/mm/as.c

    rd88218b r0b37882  
    7171#include <memstr.h>
    7272#include <macros.h>
     73#include <bitops.h>
    7374#include <arch.h>
    7475#include <errno.h>
     
    288289/** Check area conflicts with other areas.
    289290 *
    290  * @param as         Address space.
    291  * @param va         Starting virtual address of the area being tested.
    292  * @param size       Size of the area being tested.
    293  * @param avoid_area Do not touch this area.
     291 * @param as    Address space.
     292 * @param addr  Starting virtual address of the area being tested.
     293 * @param count Number of pages in the area being tested.
     294 * @param avoid Do not touch this area.
    294295 *
    295296 * @return True if there is no conflict, false otherwise.
    296297 *
    297298 */
    298 NO_TRACE static bool check_area_conflicts(as_t *as, uintptr_t va, size_t size,
    299     as_area_t *avoid_area)
    300 {
     299NO_TRACE static bool check_area_conflicts(as_t *as, uintptr_t addr,
     300    size_t count, as_area_t *avoid)
     301{
     302        ASSERT((addr % PAGE_SIZE) == 0);
    301303        ASSERT(mutex_locked(&as->lock));
    302304       
     
    304306         * We don't want any area to have conflicts with NULL page.
    305307         */
    306         if (overlaps(va, size, (uintptr_t) NULL, PAGE_SIZE))
     308        if (overlaps(addr, count << PAGE_WIDTH, (uintptr_t) NULL, PAGE_SIZE))
    307309                return false;
    308310       
     
    316318        btree_node_t *leaf;
    317319        as_area_t *area =
    318             (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
     320            (as_area_t *) btree_search(&as->as_area_btree, addr, &leaf);
    319321        if (area) {
    320                 if (area != avoid_area)
     322                if (area != avoid)
    321323                        return false;
    322324        }
     
    328330                area = (as_area_t *) node->value[node->keys - 1];
    329331               
    330                 mutex_lock(&area->lock);
    331                
    332                 if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
     332                if (area != avoid) {
     333                        mutex_lock(&area->lock);
     334                       
     335                        if (overlaps(addr, count << PAGE_WIDTH,
     336                            area->base, area->pages << PAGE_WIDTH)) {
     337                                mutex_unlock(&area->lock);
     338                                return false;
     339                        }
     340                       
    333341                        mutex_unlock(&area->lock);
    334                         return false;
    335                 }
    336                
    337                 mutex_unlock(&area->lock);
     342                }
    338343        }
    339344       
     
    342347                area = (as_area_t *) node->value[0];
    343348               
    344                 mutex_lock(&area->lock);
    345                
    346                 if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
     349                if (area != avoid) {
     350                        mutex_lock(&area->lock);
     351                       
     352                        if (overlaps(addr, count << PAGE_WIDTH,
     353                            area->base, area->pages << PAGE_WIDTH)) {
     354                                mutex_unlock(&area->lock);
     355                                return false;
     356                        }
     357                       
    347358                        mutex_unlock(&area->lock);
    348                         return false;
    349                 }
    350                
    351                 mutex_unlock(&area->lock);
     359                }
    352360        }
    353361       
     
    357365                area = (as_area_t *) leaf->value[i];
    358366               
    359                 if (area == avoid_area)
     367                if (area == avoid)
    360368                        continue;
    361369               
    362370                mutex_lock(&area->lock);
    363371               
    364                 if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
     372                if (overlaps(addr, count << PAGE_WIDTH,
     373                    area->base, area->pages << PAGE_WIDTH)) {
    365374                        mutex_unlock(&area->lock);
    366375                        return false;
     
    375384         */
    376385        if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
    377                 return !overlaps(va, size,
     386                return !overlaps(addr, count << PAGE_WIDTH,
    378387                    KERNEL_ADDRESS_SPACE_START,
    379388                    KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START);
     
    402411    mem_backend_data_t *backend_data)
    403412{
    404         if (base % PAGE_SIZE)
     413        if ((base % PAGE_SIZE) != 0)
    405414                return NULL;
    406415       
    407         if (!size)
     416        if (size == 0)
    408417                return NULL;
     418       
     419        size_t pages = SIZE2FRAMES(size);
    409420       
    410421        /* Writeable executable areas are not supported. */
     
    414425        mutex_lock(&as->lock);
    415426       
    416         if (!check_area_conflicts(as, base, size, NULL)) {
     427        if (!check_area_conflicts(as, base, pages, NULL)) {
    417428                mutex_unlock(&as->lock);
    418429                return NULL;
     
    426437        area->flags = flags;
    427438        area->attributes = attrs;
    428         area->pages = SIZE2FRAMES(size);
     439        area->pages = pages;
    429440        area->resident = 0;
    430441        area->base = base;
     
    480491                mutex_lock(&area->lock);
    481492               
    482                 if ((area->base <= va) && (va < area->base + area->pages * PAGE_SIZE))
     493                if ((area->base <= va) &&
     494                    (va < area->base + (area->pages << PAGE_WIDTH)))
    483495                        return area;
    484496               
     
    496508                mutex_lock(&area->lock);
    497509               
    498                 if (va < area->base + area->pages * PAGE_SIZE)
     510                if (va < area->base + (area->pages << PAGE_WIDTH))
    499511                        return area;
    500512               
     
    561573       
    562574        if (pages < area->pages) {
    563                 uintptr_t start_free = area->base + pages * PAGE_SIZE;
     575                uintptr_t start_free = area->base + (pages << PAGE_WIDTH);
    564576               
    565577                /*
     
    574586                 */
    575587                ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES, as->asid,
    576                     area->base + pages * PAGE_SIZE, area->pages - pages);
     588                    area->base + (pages << PAGE_WIDTH), area->pages - pages);
    577589               
    578590                /*
     
    597609                                size_t i = 0;
    598610                               
    599                                 if (overlaps(ptr, size * PAGE_SIZE, area->base,
    600                                     pages * PAGE_SIZE)) {
     611                                if (overlaps(ptr, size << PAGE_WIDTH, area->base,
     612                                    pages << PAGE_WIDTH)) {
    601613                                       
    602                                         if (ptr + size * PAGE_SIZE <= start_free) {
     614                                        if (ptr + (size << PAGE_WIDTH) <= start_free) {
    603615                                                /*
    604616                                                 * The whole interval fits
     
    632644                                for (; i < size; i++) {
    633645                                        pte_t *pte = page_mapping_find(as, ptr +
    634                                             i * PAGE_SIZE);
     646                                            (i << PAGE_WIDTH));
    635647                                       
    636648                                        ASSERT(pte);
     
    641653                                            (area->backend->frame_free)) {
    642654                                                area->backend->frame_free(area,
    643                                                     ptr + i * PAGE_SIZE,
     655                                                    ptr + (i << PAGE_WIDTH),
    644656                                                    PTE_GET_FRAME(pte));
    645657                                        }
    646658                                       
    647659                                        page_mapping_remove(as, ptr +
    648                                             i * PAGE_SIZE);
     660                                            (i << PAGE_WIDTH));
    649661                                }
    650662                        }
     
    655667                 */
    656668               
    657                 tlb_invalidate_pages(as->asid, area->base + pages * PAGE_SIZE,
     669                tlb_invalidate_pages(as->asid, area->base + (pages << PAGE_WIDTH),
    658670                    area->pages - pages);
    659671               
     
    662674                 */
    663675                as_invalidate_translation_cache(as, area->base +
    664                     pages * PAGE_SIZE, area->pages - pages);
     676                    (pages << PAGE_WIDTH), area->pages - pages);
    665677                tlb_shootdown_finalize(ipl);
    666678               
     
    671683                 * Check for overlaps with other address space areas.
    672684                 */
    673                 if (!check_area_conflicts(as, address, pages * PAGE_SIZE,
    674                     area)) {
     685                if (!check_area_conflicts(as, address, pages, area)) {
    675686                        mutex_unlock(&area->lock);
    676687                        mutex_unlock(&as->lock);
     
    771782                       
    772783                        for (size = 0; size < (size_t) node->value[i]; size++) {
    773                                 pte_t *pte = page_mapping_find(as, ptr + size * PAGE_SIZE);
     784                                pte_t *pte =
     785                                    page_mapping_find(as, ptr + (size << PAGE_WIDTH));
    774786                               
    775787                                ASSERT(pte);
     
    780792                                    (area->backend->frame_free)) {
    781793                                        area->backend->frame_free(area,
    782                                             ptr + size * PAGE_SIZE, PTE_GET_FRAME(pte));
     794                                            ptr + (size << PAGE_WIDTH), PTE_GET_FRAME(pte));
    783795                                }
    784796                               
    785                                 page_mapping_remove(as, ptr + size * PAGE_SIZE);
     797                                page_mapping_remove(as, ptr + (size << PAGE_WIDTH));
    786798                        }
    787799                }
     
    870882        }
    871883       
    872         size_t src_size = src_area->pages * PAGE_SIZE;
     884        size_t src_size = src_area->pages << PAGE_WIDTH;
    873885        unsigned int src_flags = src_area->flags;
    874886        mem_backend_t *src_backend = src_area->backend;
     
    10761088                       
    10771089                        for (size = 0; size < (size_t) node->value[i]; size++) {
    1078                                 pte_t *pte = page_mapping_find(as, ptr + size * PAGE_SIZE);
     1090                                pte_t *pte =
     1091                                    page_mapping_find(as, ptr + (size << PAGE_WIDTH));
    10791092                               
    10801093                                ASSERT(pte);
     
    10851098                               
    10861099                                /* Remove old mapping */
    1087                                 page_mapping_remove(as, ptr + size * PAGE_SIZE);
     1100                                page_mapping_remove(as, ptr + (size << PAGE_WIDTH));
    10881101                        }
    10891102                }
     
    11311144                               
    11321145                                /* Insert the new mapping */
    1133                                 page_mapping_insert(as, ptr + size * PAGE_SIZE,
     1146                                page_mapping_insert(as, ptr + (size << PAGE_WIDTH),
    11341147                                    old_frame[frame_idx++], page_flags);
    11351148                               
     
    14531466       
    14541467        if (src_area) {
    1455                 size = src_area->pages * PAGE_SIZE;
     1468                size = src_area->pages << PAGE_WIDTH;
    14561469                mutex_unlock(&src_area->lock);
    14571470        } else
     
    15081521                if (page >= right_pg) {
    15091522                        /* Do nothing. */
    1510                 } else if (overlaps(page, count * PAGE_SIZE, left_pg,
    1511                     left_cnt * PAGE_SIZE)) {
     1523                } else if (overlaps(page, count << PAGE_WIDTH, left_pg,
     1524                    left_cnt << PAGE_WIDTH)) {
    15121525                        /* The interval intersects with the left interval. */
    15131526                        return false;
    1514                 } else if (overlaps(page, count * PAGE_SIZE, right_pg,
    1515                     right_cnt * PAGE_SIZE)) {
     1527                } else if (overlaps(page, count << PAGE_WIDTH, right_pg,
     1528                    right_cnt << PAGE_WIDTH)) {
    15161529                        /* The interval intersects with the right interval. */
    15171530                        return false;
    1518                 } else if ((page == left_pg + left_cnt * PAGE_SIZE) &&
    1519                     (page + count * PAGE_SIZE == right_pg)) {
     1531                } else if ((page == left_pg + (left_cnt << PAGE_WIDTH)) &&
     1532                    (page + (count << PAGE_WIDTH) == right_pg)) {
    15201533                        /*
    15211534                         * The interval can be added by merging the two already
     
    15251538                        btree_remove(&area->used_space, right_pg, leaf);
    15261539                        goto success;
    1527                 } else if (page == left_pg + left_cnt * PAGE_SIZE) {
     1540                } else if (page == left_pg + (left_cnt << PAGE_WIDTH)) {
    15281541                        /*
    15291542                         * The interval can be added by simply growing the left
     
    15321545                        node->value[node->keys - 1] += count;
    15331546                        goto success;
    1534                 } else if (page + count * PAGE_SIZE == right_pg) {
     1547                } else if (page + (count << PAGE_WIDTH) == right_pg) {
    15351548                        /*
    15361549                         * The interval can be addded by simply moving base of
     
    15591572                 */
    15601573               
    1561                 if (overlaps(page, count * PAGE_SIZE, right_pg,
    1562                     right_cnt * PAGE_SIZE)) {
     1574                if (overlaps(page, count << PAGE_WIDTH, right_pg,
     1575                    right_cnt << PAGE_WIDTH)) {
    15631576                        /* The interval intersects with the right interval. */
    15641577                        return false;
    1565                 } else if (page + count * PAGE_SIZE == right_pg) {
     1578                } else if (page + (count << PAGE_WIDTH) == right_pg) {
    15661579                        /*
    15671580                         * The interval can be added by moving the base of the
     
    15981611                if (page < left_pg) {
    15991612                        /* Do nothing. */
    1600                 } else if (overlaps(page, count * PAGE_SIZE, left_pg,
    1601                     left_cnt * PAGE_SIZE)) {
     1613                } else if (overlaps(page, count << PAGE_WIDTH, left_pg,
     1614                    left_cnt << PAGE_WIDTH)) {
    16021615                        /* The interval intersects with the left interval. */
    16031616                        return false;
    1604                 } else if (overlaps(page, count * PAGE_SIZE, right_pg,
    1605                     right_cnt * PAGE_SIZE)) {
     1617                } else if (overlaps(page, count << PAGE_WIDTH, right_pg,
     1618                    right_cnt << PAGE_WIDTH)) {
    16061619                        /* The interval intersects with the right interval. */
    16071620                        return false;
    1608                 } else if ((page == left_pg + left_cnt * PAGE_SIZE) &&
    1609                     (page + count * PAGE_SIZE == right_pg)) {
     1621                } else if ((page == left_pg + (left_cnt << PAGE_WIDTH)) &&
     1622                    (page + (count << PAGE_WIDTH) == right_pg)) {
    16101623                        /*
    16111624                         * The interval can be added by merging the two already
     
    16151628                        btree_remove(&area->used_space, right_pg, node);
    16161629                        goto success;
    1617                 } else if (page == left_pg + left_cnt * PAGE_SIZE) {
     1630                } else if (page == left_pg + (left_cnt << PAGE_WIDTH)) {
    16181631                        /*
    16191632                         * The interval can be added by simply growing the left
     
    16221635                        leaf->value[leaf->keys - 1] += count;
    16231636                        goto success;
    1624                 } else if (page + count * PAGE_SIZE == right_pg) {
     1637                } else if (page + (count << PAGE_WIDTH) == right_pg) {
    16251638                        /*
    16261639                         * The interval can be addded by simply moving base of
     
    16491662                 */
    16501663               
    1651                 if (overlaps(page, count * PAGE_SIZE, left_pg,
    1652                     left_cnt * PAGE_SIZE)) {
     1664                if (overlaps(page, count << PAGE_WIDTH, left_pg,
     1665                    left_cnt << PAGE_WIDTH)) {
    16531666                        /* The interval intersects with the left interval. */
    16541667                        return false;
    1655                 } else if (left_pg + left_cnt * PAGE_SIZE == page) {
     1668                } else if (left_pg + (left_cnt << PAGE_WIDTH) == page) {
    16561669                        /*
    16571670                         * The interval can be added by growing the left
     
    16881701                         */
    16891702                       
    1690                         if (overlaps(page, count * PAGE_SIZE, left_pg,
    1691                             left_cnt * PAGE_SIZE)) {
     1703                        if (overlaps(page, count << PAGE_WIDTH, left_pg,
     1704                            left_cnt << PAGE_WIDTH)) {
    16921705                                /*
    16931706                                 * The interval intersects with the left
     
    16951708                                 */
    16961709                                return false;
    1697                         } else if (overlaps(page, count * PAGE_SIZE, right_pg,
    1698                             right_cnt * PAGE_SIZE)) {
     1710                        } else if (overlaps(page, count << PAGE_WIDTH, right_pg,
     1711                            right_cnt << PAGE_WIDTH)) {
    16991712                                /*
    17001713                                 * The interval intersects with the right
     
    17021715                                 */
    17031716                                return false;
    1704                         } else if ((page == left_pg + left_cnt * PAGE_SIZE) &&
    1705                             (page + count * PAGE_SIZE == right_pg)) {
     1717                        } else if ((page == left_pg + (left_cnt << PAGE_WIDTH)) &&
     1718                            (page + (count << PAGE_WIDTH) == right_pg)) {
    17061719                                /*
    17071720                                 * The interval can be added by merging the two
     
    17111724                                btree_remove(&area->used_space, right_pg, leaf);
    17121725                                goto success;
    1713                         } else if (page == left_pg + left_cnt * PAGE_SIZE) {
     1726                        } else if (page == left_pg + (left_cnt << PAGE_WIDTH)) {
    17141727                                /*
    17151728                                 * The interval can be added by simply growing
     
    17181731                                leaf->value[i - 1] += count;
    17191732                                goto success;
    1720                         } else if (page + count * PAGE_SIZE == right_pg) {
     1733                        } else if (page + (count << PAGE_WIDTH) == right_pg) {
    17211734                                /*
    17221735                                 * The interval can be addded by simply moving
     
    17841797                        for (i = 0; i < leaf->keys; i++) {
    17851798                                if (leaf->key[i] == page) {
    1786                                         leaf->key[i] += count * PAGE_SIZE;
     1799                                        leaf->key[i] += count << PAGE_WIDTH;
    17871800                                        leaf->value[i] -= count;
    17881801                                        goto success;
     
    17991812                size_t left_cnt = (size_t) node->value[node->keys - 1];
    18001813               
    1801                 if (overlaps(left_pg, left_cnt * PAGE_SIZE, page,
    1802                     count * PAGE_SIZE)) {
    1803                         if (page + count * PAGE_SIZE ==
    1804                             left_pg + left_cnt * PAGE_SIZE) {
     1814                if (overlaps(left_pg, left_cnt << PAGE_WIDTH, page,
     1815                    count << PAGE_WIDTH)) {
     1816                        if (page + (count << PAGE_WIDTH) ==
     1817                            left_pg + (left_cnt << PAGE_WIDTH)) {
    18051818                                /*
    18061819                                 * The interval is contained in the rightmost
     
    18111824                                node->value[node->keys - 1] -= count;
    18121825                                goto success;
    1813                         } else if (page + count * PAGE_SIZE <
    1814                             left_pg + left_cnt*PAGE_SIZE) {
     1826                        } else if (page + (count << PAGE_WIDTH) <
     1827                            left_pg + (left_cnt << PAGE_WIDTH)) {
    18151828                                /*
    18161829                                 * The interval is contained in the rightmost
     
    18201833                                 * new interval.
    18211834                                 */
    1822                                 size_t new_cnt = ((left_pg + left_cnt * PAGE_SIZE) -
    1823                                     (page + count*PAGE_SIZE)) >> PAGE_WIDTH;
     1835                                size_t new_cnt = ((left_pg + (left_cnt << PAGE_WIDTH)) -
     1836                                    (page + (count << PAGE_WIDTH))) >> PAGE_WIDTH;
    18241837                                node->value[node->keys - 1] -= count + new_cnt;
    18251838                                btree_insert(&area->used_space, page +
    1826                                     count * PAGE_SIZE, (void *) new_cnt, leaf);
     1839                                    (count << PAGE_WIDTH), (void *) new_cnt, leaf);
    18271840                                goto success;
    18281841                        }
     
    18371850                size_t left_cnt = (size_t) leaf->value[leaf->keys - 1];
    18381851               
    1839                 if (overlaps(left_pg, left_cnt * PAGE_SIZE, page,
    1840                     count * PAGE_SIZE)) {
    1841                         if (page + count * PAGE_SIZE ==
    1842                             left_pg + left_cnt * PAGE_SIZE) {
     1852                if (overlaps(left_pg, left_cnt << PAGE_WIDTH, page,
     1853                    count << PAGE_WIDTH)) {
     1854                        if (page + (count << PAGE_WIDTH) ==
     1855                            left_pg + (left_cnt << PAGE_WIDTH)) {
    18431856                                /*
    18441857                                 * The interval is contained in the rightmost
     
    18481861                                leaf->value[leaf->keys - 1] -= count;
    18491862                                goto success;
    1850                         } else if (page + count * PAGE_SIZE < left_pg +
    1851                             left_cnt * PAGE_SIZE) {
     1863                        } else if (page + (count << PAGE_WIDTH) < left_pg +
     1864                            (left_cnt << PAGE_WIDTH)) {
    18521865                                /*
    18531866                                 * The interval is contained in the rightmost
     
    18571870                                 * interval.
    18581871                                 */
    1859                                 size_t new_cnt = ((left_pg + left_cnt * PAGE_SIZE) -
    1860                                     (page + count * PAGE_SIZE)) >> PAGE_WIDTH;
     1872                                size_t new_cnt = ((left_pg + (left_cnt << PAGE_WIDTH)) -
     1873                                    (page + (count << PAGE_WIDTH))) >> PAGE_WIDTH;
    18611874                                leaf->value[leaf->keys - 1] -= count + new_cnt;
    18621875                                btree_insert(&area->used_space, page +
    1863                                     count * PAGE_SIZE, (void *) new_cnt, leaf);
     1876                                    (count << PAGE_WIDTH), (void *) new_cnt, leaf);
    18641877                                goto success;
    18651878                        }
     
    18831896                         * to (i - 1) and i.
    18841897                         */
    1885                         if (overlaps(left_pg, left_cnt * PAGE_SIZE, page,
    1886                             count * PAGE_SIZE)) {
    1887                                 if (page + count * PAGE_SIZE ==
    1888                                     left_pg + left_cnt*PAGE_SIZE) {
     1898                        if (overlaps(left_pg, left_cnt << PAGE_WIDTH, page,
     1899                            count << PAGE_WIDTH)) {
     1900                                if (page + (count << PAGE_WIDTH) ==
     1901                                    left_pg + (left_cnt << PAGE_WIDTH)) {
    18891902                                        /*
    18901903                                         * The interval is contained in the
     
    18951908                                        leaf->value[i - 1] -= count;
    18961909                                        goto success;
    1897                                 } else if (page + count * PAGE_SIZE <
    1898                                     left_pg + left_cnt * PAGE_SIZE) {
     1910                                } else if (page + (count << PAGE_WIDTH) <
     1911                                    left_pg + (left_cnt << PAGE_WIDTH)) {
    18991912                                        /*
    19001913                                         * The interval is contained in the
     
    19051918                                         */
    19061919                                        size_t new_cnt = ((left_pg +
    1907                                             left_cnt * PAGE_SIZE) -
    1908                                             (page + count * PAGE_SIZE)) >>
     1920                                            (left_cnt << PAGE_WIDTH)) -
     1921                                            (page + (count << PAGE_WIDTH))) >>
    19091922                                            PAGE_WIDTH;
    19101923                                        leaf->value[i - 1] -= count + new_cnt;
    19111924                                        btree_insert(&area->used_space, page +
    1912                                             count * PAGE_SIZE, (void *) new_cnt,
     1925                                            (count << PAGE_WIDTH), (void *) new_cnt,
    19131926                                            leaf);
    19141927                                        goto success;
     
    19611974}
    19621975
     1976/** Return pointer to unmapped address space area
     1977 *
     1978 * @param base Lowest address bound.
     1979 * @param size Requested size of the allocation.
     1980 *
     1981 * @return Pointer to the beginning of unmapped address space area.
     1982 *
     1983 */
     1984sysarg_t sys_as_get_unmapped_area(uintptr_t base, size_t size)
     1985{
     1986        if (size == 0)
     1987                return 0;
     1988       
     1989        /*
     1990         * Make sure we allocate from page-aligned
     1991         * address. Check for possible overflow in
     1992         * each step.
     1993         */
     1994       
     1995        size_t pages = SIZE2FRAMES(size);
     1996        uintptr_t ret = 0;
     1997       
     1998        /*
     1999         * Find the lowest unmapped address aligned on the sz
     2000         * boundary, not smaller than base and of the required size.
     2001         */
     2002       
     2003        mutex_lock(&AS->lock);
     2004       
     2005        /* First check the base address itself */
     2006        uintptr_t addr = ALIGN_UP(base, PAGE_SIZE);
     2007        if ((addr >= base) &&
     2008            (check_area_conflicts(AS, addr, pages, NULL)))
     2009                ret = addr;
     2010       
     2011        /* Eventually check the addresses behind each area */
     2012        link_t *cur;
     2013        for (cur = AS->as_area_btree.leaf_head.next;
     2014            (ret == 0) && (cur != &AS->as_area_btree.leaf_head);
     2015            cur = cur->next) {
     2016                btree_node_t *node =
     2017                    list_get_instance(cur, btree_node_t, leaf_link);
     2018               
     2019                btree_key_t i;
     2020                for (i = 0; (ret == 0) && (i < node->keys); i++) {
     2021                        as_area_t *area = (as_area_t *) node->value[i];
     2022                       
     2023                        mutex_lock(&area->lock);
     2024                       
     2025                        uintptr_t addr =
     2026                            ALIGN_UP(area->base + (area->pages << PAGE_WIDTH),
     2027                            PAGE_SIZE);
     2028                       
     2029                        if ((addr >= base) && (addr >= area->base) &&
     2030                            (check_area_conflicts(AS, addr, pages, area)))
     2031                                ret = addr;
     2032                       
     2033                        mutex_unlock(&area->lock);
     2034                }
     2035        }
     2036       
     2037        mutex_unlock(&AS->lock);
     2038       
     2039        return (sysarg_t) ret;
     2040}
     2041
    19632042/** Get list of adress space areas.
    19642043 *
     
    20272106        mutex_lock(&as->lock);
    20282107       
    2029         /* print out info about address space areas */
     2108        /* Print out info about address space areas */
    20302109        link_t *cur;
    20312110        for (cur = as->as_area_btree.leaf_head.next;
  • kernel/generic/src/syscall/syscall.c

    rd88218b r0b37882  
    143143        (syshandler_t) sys_as_area_change_flags,
    144144        (syshandler_t) sys_as_area_destroy,
     145        (syshandler_t) sys_as_get_unmapped_area,
    145146       
    146147        /* IPC related syscalls. */
  • uspace/lib/c/arch/abs32le/_link.ld.in

    rd88218b r0b37882  
    4444        } :data
    4545       
    46         . = ALIGN(0x1000);
    47        
    48         _heap = .;
    49        
    5046        /DISCARD/ : {
    5147                *(*);
  • uspace/lib/c/arch/amd64/_link.ld.in

    rd88218b r0b37882  
    4242        } :data
    4343       
    44         . = ALIGN(0x1000);
    45         _heap = .;
    46        
    4744#ifdef CONFIG_LINE_DEBUG
    4845        .comment 0 : { *(.comment); } :debug
     
    6158                *(*);
    6259        }
    63 
    6460}
  • uspace/lib/c/arch/arm32/_link.ld.in

    rd88218b r0b37882  
    99SECTIONS {
    1010        . = 0x1000 + SIZEOF_HEADERS;
    11 
     11       
    1212        .init : {
    1313                *(.init);
    14         } : text
     14        } :text
     15       
    1516        .text : {
    1617                *(.text);
    17         *(.rodata*);
     18                *(.rodata*);
    1819        } :text
    19 
     20       
    2021        . = . + 0x1000;
    21 
     22       
    2223        .data : {
    2324                *(.opd);
     
    2526                *(.sdata);
    2627        } :data
     28       
    2729        .tdata : {
    2830                _tdata_start = .;
     
    3335                _tbss_end = .;
    3436        } :data
     37       
    3538        _tls_alignment = ALIGNOF(.tdata);
     39       
    3640        .bss : {
    3741                *(.sbss);
    3842                *(.scommon);
    39         *(COMMON);
    40         *(.bss);
     43                *(COMMON);
     44                *(.bss);
    4145        } :data
    42        
    43         . = ALIGN(0x1000);
    44         _heap = .;
    4546       
    4647        /DISCARD/ : {
    4748                *(*);
    4849        }
    49 
    5050}
  • uspace/lib/c/arch/ia32/_link.ld.in

    rd88218b r0b37882  
    4343        } :data
    4444       
    45         . = ALIGN(0x1000);
    46         _heap = .;
    47        
    4845#ifdef CONFIG_LINE_DEBUG
    4946        .comment 0 : { *(.comment); } :debug
  • uspace/lib/c/arch/ia64/_link.ld.in

    rd88218b r0b37882  
    99SECTIONS {
    1010        . = 0x4000 + SIZEOF_HEADERS;
    11 
     11       
    1212        .init : {
    1313                *(.init);
    14         } : text
     14        } :text
     15       
    1516        .text : {
    1617                *(.text);
    1718                *(.rodata*);
    1819        } :text
    19 
     20       
    2021        . = . + 0x4000;
    21 
     22       
    2223        .got : {
    2324                _gp = .;
    2425                *(.got*);
    25         } :data
     26        } :data
     27       
    2628        .data : {
    2729                *(.opd);
     
    2931                *(.sdata);
    3032        } :data
     33       
    3134        .tdata : {
    3235                _tdata_start = .;
     
    3740                _tbss_end = .;
    3841        } :data
     42       
    3943        _tls_alignment = ALIGNOF(.tdata);
     44       
    4045        .bss : {
    4146                *(.sbss);
     
    4449                *(.bss);
    4550        } :data
    46 
    47         . = ALIGN(0x4000);
    48         _heap = .;
    49  
     51       
    5052        /DISCARD/ : {
    5153                *(*);
    52         }
     54        }
    5355}
  • uspace/lib/c/arch/mips32/_link.ld.in

    rd88218b r0b37882  
    1313                *(.init);
    1414        } :text
     15       
    1516        .text : {
    16                 *(.text);
     17                *(.text);
    1718                *(.rodata*);
    1819        } :text
    19 
     20       
    2021        . = . + 0x4000;
    21 
     22       
    2223        .data : {
    2324                *(.data);
    2425                *(.data.rel*);
    2526        } :data
    26 
     27       
    2728        .got : {
    2829                _gp = .;
    2930                *(.got);
    3031        } :data
    31 
     32       
    3233        .tdata : {
    3334                _tdata_start = .;
    3435                *(.tdata);
    3536                _tdata_end = .;
     37        } :data
     38       
     39        .tbss : {
    3640                _tbss_start = .;
    3741                *(.tbss);
    3842                _tbss_end = .;
    3943        } :data
    40         _tls_alignment = ALIGNOF(.tdata);
    41 
     44       
     45        _tls_alignment = MAX(ALIGNOF(.tdata), ALIGNOF(.tbss));
     46       
    4247        .sbss : {
    4348                *(.scommon);
    4449                *(.sbss);
    45         }       
     50        }
     51       
    4652        .bss : {
    4753                *(.bss);
    4854                *(COMMON);
    4955        } :data
    50 
    51         . = ALIGN(0x4000);
    52         _heap = .;
    53 
     56       
    5457        /DISCARD/ : {
    5558                *(*);
  • uspace/lib/c/arch/mips32/src/entry.s

    rd88218b r0b37882  
    2929.text
    3030.section .init, "ax"
     31
    3132.global __entry
    32 .global __entry_driver
     33
    3334.set noreorder
    3435.option pic2
     
    5758        nop
    5859.end
    59 
    60 # Alignment of output section data to 0x4000
    61 .section .data
    62 .align 14
  • uspace/lib/c/arch/ppc32/_link.ld.in

    rd88218b r0b37882  
    99SECTIONS {
    1010        . = 0x1000 + SIZEOF_HEADERS;
    11 
     11       
    1212        .init : {
    1313                *(.init);
    1414        } :text
     15       
    1516        .text : {
    1617                *(.text);
    1718                *(.rodata*);
    1819        } :text
    19 
     20       
    2021        . = . + 0x1000;
    21 
     22       
    2223        .data : {
    2324                *(.data);
    2425                *(.sdata);
    2526        } :data
     27       
    2628        .tdata : {
    2729                _tdata_start = .;
     
    3234                _tbss_end = .;
    3335        } :data
     36       
    3437        _tls_alignment = ALIGNOF(.tdata);
     38       
    3539        .bss : {
    3640                *(.sbss);
     
    3842                *(.bss);
    3943        } :data
    40 
    41         . = ALIGN(0x1000);
    42         _heap = .;
    4344       
    4445        /DISCARD/ : {
    4546                *(*);
    4647        }
    47 
    4848}
  • uspace/lib/c/arch/sparc64/_link.ld.in

    rd88218b r0b37882  
    99SECTIONS {
    1010        . = 0x4000 + SIZEOF_HEADERS;
    11 
     11       
    1212        .init : {
    1313                *(.init);
    1414        } :text
     15       
    1516        .text : {
    1617                *(.text);
    1718                *(.rodata*);
    1819        } :text
    19 
     20       
    2021        . = . + 0x4000;
    21 
     22       
    2223        .got : {
    2324                 _gp = .;
    2425                 *(.got*);
    2526        } :data
     27       
    2628        .data : {
    2729                *(.data);
    2830                *(.sdata);
    2931        } :data
     32       
    3033        .tdata : {
    3134                _tdata_start = .;
     
    3639                _tbss_end = .;
    3740        } :data
     41       
    3842        _tls_alignment = ALIGNOF(.tdata);
     43       
    3944        .bss : {
    4045                *(.sbss);
     
    4247                *(.bss);
    4348        } :data
    44 
    45         . = ALIGN(0x4000);
    46         _heap = .;
    4749       
    4850        /DISCARD/ : {
    4951                *(*);
    5052        }
    51 
    5253}
  • uspace/lib/c/generic/as.c

    rd88218b r0b37882  
    4040#include <bitops.h>
    4141#include <malloc.h>
    42 
    43 /** Last position allocated by as_get_mappable_page */
    44 static uintptr_t last_allocated = 0;
     42#include "private/libc.h"
    4543
    4644/** Create address space area.
     
    103101}
    104102
    105 /** Return pointer to some unmapped area, where fits new as_area
     103/** Return pointer to unmapped address space area
    106104 *
    107105 * @param size Requested size of the allocation.
    108106 *
    109  * @return pointer to the beginning
     107 * @return Pointer to the beginning of unmapped address space area.
    110108 *
    111109 */
    112110void *as_get_mappable_page(size_t size)
    113111{
    114         if (size == 0)
    115                 return NULL;
    116        
    117         size_t sz = 1 << (fnzb(size - 1) + 1);
    118         if (last_allocated == 0)
    119                 last_allocated = get_max_heap_addr();
    120        
    121         /*
    122          * Make sure we allocate from naturally aligned address.
    123          */
    124         uintptr_t res = ALIGN_UP(last_allocated, sz);
    125         last_allocated = res + ALIGN_UP(size, PAGE_SIZE);
    126        
    127         return ((void *) res);
     112        return (void *) __SYSCALL2(SYS_AS_GET_UNMAPPED_AREA,
     113            (sysarg_t) __entry, (sysarg_t) size);
    128114}
    129115
  • uspace/lib/c/generic/malloc.c

    rd88218b r0b37882  
    4747#include "private/malloc.h"
    4848
    49 /* Magic used in heap headers. */
    50 #define HEAP_BLOCK_HEAD_MAGIC  0xBEEF0101
    51 
    52 /* Magic used in heap footers. */
    53 #define HEAP_BLOCK_FOOT_MAGIC  0xBEEF0202
    54 
    55 /** Allocation alignment (this also covers the alignment of fields
    56     in the heap header and footer) */
     49/** Magic used in heap headers. */
     50#define HEAP_BLOCK_HEAD_MAGIC  UINT32_C(0xBEEF0101)
     51
     52/** Magic used in heap footers. */
     53#define HEAP_BLOCK_FOOT_MAGIC  UINT32_C(0xBEEF0202)
     54
     55/** Magic used in heap descriptor. */
     56#define HEAP_AREA_MAGIC  UINT32_C(0xBEEFCAFE)
     57
     58/** Allocation alignment.
     59 *
     60 * This also covers the alignment of fields
     61 * in the heap header and footer.
     62 *
     63 */
    5764#define BASE_ALIGN  16
    5865
    59 /**
    60  * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures
    61  */
    62 #define MAX_HEAP_SIZE  (sizeof(uintptr_t) << 28)
    63 
    64 /**
    65  *
    66  */
    67 #define STRUCT_OVERHEAD  (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t))
    68 
    69 /**
    70  * Calculate real size of a heap block (with header and footer)
     66/** Overhead of each heap block. */
     67#define STRUCT_OVERHEAD \
     68        (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t))
     69
     70/** Calculate real size of a heap block.
     71 *
     72 * Add header and footer size.
     73 *
    7174 */
    7275#define GROSS_SIZE(size)  ((size) + STRUCT_OVERHEAD)
    7376
    74 /**
    75  * Calculate net size of a heap block (without header and footer)
     77/** Calculate net size of a heap block.
     78 *
     79 * Subtract header and footer size.
     80 *
    7681 */
    7782#define NET_SIZE(size)  ((size) - STRUCT_OVERHEAD)
     83
     84/** Get first block in heap area.
     85 *
     86 */
     87#define AREA_FIRST_BLOCK(area) \
     88        (ALIGN_UP(((uintptr_t) (area)) + sizeof(heap_area_t), BASE_ALIGN))
     89
     90/** Get footer in heap block.
     91 *
     92 */
     93#define BLOCK_FOOT(head) \
     94        ((heap_block_foot_t *) \
     95            (((uintptr_t) head) + head->size - sizeof(heap_block_foot_t)))
     96
     97/** Heap area.
     98 *
     99 * The memory managed by the heap allocator is divided into
     100 * multiple discontinuous heaps. Each heap is represented
     101 * by a separate address space area which has this structure
     102 * at its very beginning.
     103 *
     104 */
     105typedef struct heap_area {
     106        /** Start of the heap area (including this structure)
     107         *
     108         * Aligned on page boundary.
     109         *
     110         */
     111        void *start;
     112       
     113        /** End of the heap area (aligned on page boundary) */
     114        void *end;
     115       
     116        /** Next heap area */
     117        struct heap_area *next;
     118       
     119        /** A magic value */
     120        uint32_t magic;
     121} heap_area_t;
    78122
    79123/** Header of a heap block
     
    87131        bool free;
    88132       
     133        /** Heap area this block belongs to */
     134        heap_area_t *area;
     135       
    89136        /* A magic value to detect overwrite of heap header */
    90137        uint32_t magic;
     
    102149} heap_block_foot_t;
    103150
    104 /** Linker heap symbol */
    105 extern char _heap;
     151/** First heap area */
     152static heap_area_t *first_heap_area = NULL;
     153
     154/** Last heap area */
     155static heap_area_t *last_heap_area = NULL;
     156
     157/** Next heap block to examine (next fit algorithm) */
     158static heap_block_head_t *next = NULL;
    106159
    107160/** Futex for thread-safe heap manipulation */
    108161static futex_t malloc_futex = FUTEX_INITIALIZER;
    109162
    110 /** Address of heap start */
    111 static void *heap_start = 0;
    112 
    113 /** Address of heap end */
    114 static void *heap_end = 0;
    115 
    116 /** Maximum heap size */
    117 static size_t max_heap_size = (size_t) -1;
    118 
    119 /** Current number of pages of heap area */
    120 static size_t heap_pages = 0;
    121 
    122163/** Initialize a heap block
    123164 *
    124  * Fills in the structures related to a heap block.
     165 * Fill in the structures related to a heap block.
    125166 * Should be called only inside the critical section.
    126167 *
     
    128169 * @param size Size of the block including the header and the footer.
    129170 * @param free Indication of a free block.
    130  *
    131  */
    132 static void block_init(void *addr, size_t size, bool free)
     171 * @param area Heap area the block belongs to.
     172 *
     173 */
     174static void block_init(void *addr, size_t size, bool free, heap_area_t *area)
    133175{
    134176        /* Calculate the position of the header and the footer */
    135177        heap_block_head_t *head = (heap_block_head_t *) addr;
    136         heap_block_foot_t *foot =
    137             (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t));
    138178       
    139179        head->size = size;
    140180        head->free = free;
     181        head->area = area;
    141182        head->magic = HEAP_BLOCK_HEAD_MAGIC;
     183       
     184        heap_block_foot_t *foot = BLOCK_FOOT(head);
    142185       
    143186        foot->size = size;
     
    160203        assert(head->magic == HEAP_BLOCK_HEAD_MAGIC);
    161204       
    162         heap_block_foot_t *foot =
    163             (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t));
     205        heap_block_foot_t *foot = BLOCK_FOOT(head);
    164206       
    165207        assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC);
     
    167209}
    168210
    169 /** Increase the heap area size
    170  *
    171  * Should be called only inside the critical section.
    172  *
    173  * @param size Number of bytes to grow the heap by.
    174  *
    175  */
    176 static bool grow_heap(size_t size)
     211/** Check a heap area structure
     212 *
     213 * @param addr Address of the heap area.
     214 *
     215 */
     216static void area_check(void *addr)
     217{
     218        heap_area_t *area = (heap_area_t *) addr;
     219       
     220        assert(area->magic == HEAP_AREA_MAGIC);
     221        assert(area->start < area->end);
     222        assert(((uintptr_t) area->start % PAGE_SIZE) == 0);
     223        assert(((uintptr_t) area->end % PAGE_SIZE) == 0);
     224}
     225
     226/** Create new heap area
     227 *
     228 * @param start Preffered starting address of the new area.
     229 * @param size  Size of the area.
     230 *
     231 */
     232static bool area_create(size_t size)
     233{
     234        void *start = as_get_mappable_page(size);
     235        if (start == NULL)
     236                return false;
     237       
     238        /* Align the heap area on page boundary */
     239        void *astart = (void *) ALIGN_UP((uintptr_t) start, PAGE_SIZE);
     240        size_t asize = ALIGN_UP(size, PAGE_SIZE);
     241       
     242        astart = as_area_create(astart, asize, AS_AREA_WRITE | AS_AREA_READ);
     243        if (astart == (void *) -1)
     244                return false;
     245       
     246        heap_area_t *area = (heap_area_t *) astart;
     247       
     248        area->start = astart;
     249        area->end = (void *)
     250            ALIGN_DOWN((uintptr_t) astart + asize, BASE_ALIGN);
     251        area->next = NULL;
     252        area->magic = HEAP_AREA_MAGIC;
     253       
     254        void *block = (void *) AREA_FIRST_BLOCK(area);
     255        size_t bsize = (size_t) (area->end - block);
     256       
     257        block_init(block, bsize, true, area);
     258       
     259        if (last_heap_area == NULL) {
     260                first_heap_area = area;
     261                last_heap_area = area;
     262        } else {
     263                last_heap_area->next = area;
     264                last_heap_area = area;
     265        }
     266       
     267        return true;
     268}
     269
     270/** Try to enlarge a heap area
     271 *
     272 * @param area Heap area to grow.
     273 * @param size Gross size of item to allocate (bytes).
     274 *
     275 */
     276static bool area_grow(heap_area_t *area, size_t size)
    177277{
    178278        if (size == 0)
     279                return true;
     280       
     281        area_check(area);
     282       
     283        size_t asize = ALIGN_UP((size_t) (area->end - area->start) + size,
     284            PAGE_SIZE);
     285       
     286        /* New heap area size */
     287        void *end = (void *)
     288            ALIGN_DOWN((uintptr_t) area->start + asize, BASE_ALIGN);
     289       
     290        /* Check for overflow */
     291        if (end < area->start)
    179292                return false;
    180 
    181         if ((heap_start + size < heap_start) || (heap_end + size < heap_end))
     293       
     294        /* Resize the address space area */
     295        int ret = as_area_resize(area->start, asize, 0);
     296        if (ret != EOK)
    182297                return false;
    183298       
    184         size_t heap_size = (size_t) (heap_end - heap_start);
    185        
    186         if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size))
    187                 return false;
    188        
    189         size_t pages = (size - 1) / PAGE_SIZE + 1;
    190        
    191         if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0)
    192             == EOK) {
    193                 void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) +
    194                     (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN);
    195                 block_init(heap_end, end - heap_end, true);
    196                 heap_pages += pages;
    197                 heap_end = end;
     299        /* Add new free block */
     300        block_init(area->end, (size_t) (end - area->end), true, area);
     301       
     302        /* Update heap area parameters */
     303        area->end = end;
     304       
     305        return true;
     306}
     307
     308/** Try to enlarge any of the heap areas
     309 *
     310 * @param size Gross size of item to allocate (bytes).
     311 *
     312 */
     313static bool heap_grow(size_t size)
     314{
     315        if (size == 0)
    198316                return true;
    199         }
    200        
    201         return false;
    202 }
    203 
    204 /** Decrease the heap area
    205  *
    206  * Should be called only inside the critical section.
    207  *
    208  * @param size Number of bytes to shrink the heap by.
    209  *
    210  */
    211 static void shrink_heap(void)
    212 {
    213         // TODO
     317       
     318        /* First try to enlarge some existing area */
     319        heap_area_t *area;
     320        for (area = first_heap_area; area != NULL; area = area->next) {
     321                if (area_grow(area, size))
     322                        return true;
     323        }
     324       
     325        /* Eventually try to create a new area */
     326        return area_create(AREA_FIRST_BLOCK(size));
     327}
     328
     329/** Try to shrink heap space
     330 *
     331 * In all cases the next pointer is reset.
     332 *
     333 */
     334static void heap_shrink(void)
     335{
     336        next = NULL;
    214337}
    215338
     
    223346void __malloc_init(void)
    224347{
    225         if (!as_area_create((void *) &_heap, PAGE_SIZE,
    226             AS_AREA_WRITE | AS_AREA_READ))
     348        if (!area_create(PAGE_SIZE))
    227349                abort();
    228        
    229         heap_pages = 1;
    230         heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN);
    231         heap_end =
    232             (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN);
    233        
    234         /* Make the entire area one large block. */
    235         block_init(heap_start, heap_end - heap_start, true);
    236 }
    237 
    238 /** Get maximum heap address
    239  *
    240  */
    241 uintptr_t get_max_heap_addr(void)
    242 {
    243         futex_down(&malloc_futex);
    244        
    245         if (max_heap_size == (size_t) -1)
    246                 max_heap_size =
    247                     max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE);
    248        
    249         uintptr_t max_heap_addr = (uintptr_t) heap_start + max_heap_size;
    250        
    251         futex_up(&malloc_futex);
    252        
    253         return max_heap_addr;
    254350}
    255351
     
    273369                /* Block big enough -> split. */
    274370                void *next = ((void *) cur) + size;
    275                 block_init(next, cur->size - size, true);
    276                 block_init(cur, size, false);
     371                block_init(next, cur->size - size, true, cur->area);
     372                block_init(cur, size, false, cur->area);
    277373        } else {
    278374                /* Block too small -> use as is. */
     
    281377}
    282378
    283 /** Allocate a memory block
     379/** Allocate memory from heap area starting from given block
    284380 *
    285381 * Should be called only inside the critical section.
    286  *
    287  * @param size  The size of the block to allocate.
    288  * @param align Memory address alignment.
    289  *
    290  * @return the address of the block or NULL when not enough memory.
    291  *
    292  */
    293 static void *malloc_internal(const size_t size, const size_t align)
    294 {
    295         if (align == 0)
    296                 return NULL;
    297        
    298         size_t falign = lcm(align, BASE_ALIGN);
    299         size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
    300        
    301         bool grown = false;
    302         void *result;
    303        
    304 loop:
    305         result = NULL;
    306         heap_block_head_t *cur = (heap_block_head_t *) heap_start;
    307        
    308         while ((result == NULL) && ((void *) cur < heap_end)) {
     382 * As a side effect this function also sets the current
     383 * pointer on successful allocation.
     384 *
     385 * @param area        Heap area where to allocate from.
     386 * @param first_block Starting heap block.
     387 * @param final_block Heap block where to finish the search
     388 *                    (may be NULL).
     389 * @param real_size   Gross number of bytes to allocate.
     390 * @param falign      Physical alignment of the block.
     391 *
     392 * @return Address of the allocated block or NULL on not enough memory.
     393 *
     394 */
     395static void *malloc_area(heap_area_t *area, heap_block_head_t *first_block,
     396    heap_block_head_t *final_block, size_t real_size, size_t falign)
     397{
     398        area_check((void *) area);
     399        assert((void *) first_block >= (void *) AREA_FIRST_BLOCK(area));
     400        assert((void *) first_block < area->end);
     401       
     402        heap_block_head_t *cur;
     403        for (cur = first_block; (void *) cur < area->end;
     404            cur = (heap_block_head_t *) (((void *) cur) + cur->size)) {
    309405                block_check(cur);
     406               
     407                /* Finish searching on the final block */
     408                if ((final_block != NULL) && (cur == final_block))
     409                        break;
    310410               
    311411                /* Try to find a block that is free and large enough. */
    312412                if ((cur->free) && (cur->size >= real_size)) {
    313                         /* We have found a suitable block.
    314                            Check for alignment properties. */
    315                         void *addr = ((void *) cur) + sizeof(heap_block_head_t);
    316                         void *aligned = (void *) ALIGN_UP(addr, falign);
     413                        /*
     414                         * We have found a suitable block.
     415                         * Check for alignment properties.
     416                         */
     417                        void *addr = (void *)
     418                            ((uintptr_t) cur + sizeof(heap_block_head_t));
     419                        void *aligned = (void *)
     420                            ALIGN_UP((uintptr_t) addr, falign);
    317421                       
    318422                        if (addr == aligned) {
    319423                                /* Exact block start including alignment. */
    320424                                split_mark(cur, real_size);
    321                                 result = addr;
     425                               
     426                                next = cur;
     427                                return addr;
    322428                        } else {
    323429                                /* Block start has to be aligned */
     
    325431                               
    326432                                if (cur->size >= real_size + excess) {
    327                                         /* The current block is large enough to fit
    328                                            data in including alignment */
    329                                         if ((void *) cur > heap_start) {
    330                                                 /* There is a block before the current block.
    331                                                    This previous block can be enlarged to compensate
    332                                                    for the alignment excess */
    333                                                 heap_block_foot_t *prev_foot =
    334                                                     ((void *) cur) - sizeof(heap_block_foot_t);
     433                                        /*
     434                                         * The current block is large enough to fit
     435                                         * data in (including alignment).
     436                                         */
     437                                        if ((void *) cur > (void *) AREA_FIRST_BLOCK(area)) {
     438                                                /*
     439                                                 * There is a block before the current block.
     440                                                 * This previous block can be enlarged to
     441                                                 * compensate for the alignment excess.
     442                                                 */
     443                                                heap_block_foot_t *prev_foot = (heap_block_foot_t *)
     444                                                    ((void *) cur - sizeof(heap_block_foot_t));
    335445                                               
    336                                                 heap_block_head_t *prev_head =
    337                                                     (heap_block_head_t *) (((void *) cur) - prev_foot->size);
     446                                                heap_block_head_t *prev_head = (heap_block_head_t *)
     447                                                    ((void *) cur - prev_foot->size);
    338448                                               
    339449                                                block_check(prev_head);
     
    342452                                                heap_block_head_t *next_head = ((void *) cur) + excess;
    343453                                               
    344                                                 if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) {
    345                                                         /* The previous block is not free and there is enough
    346                                                            space to fill in a new free block between the previous
    347                                                            and current block */
    348                                                         block_init(cur, excess, true);
     454                                                if ((!prev_head->free) &&
     455                                                    (excess >= STRUCT_OVERHEAD)) {
     456                                                        /*
     457                                                         * The previous block is not free and there
     458                                                         * is enough free space left to fill in
     459                                                         * a new free block between the previous
     460                                                         * and current block.
     461                                                         */
     462                                                        block_init(cur, excess, true, area);
    349463                                                } else {
    350                                                         /* The previous block is free (thus there is no need to
    351                                                            induce additional fragmentation to the heap) or the
    352                                                            excess is small, thus just enlarge the previous block */
    353                                                         block_init(prev_head, prev_head->size + excess, prev_head->free);
     464                                                        /*
     465                                                         * The previous block is free (thus there
     466                                                         * is no need to induce additional
     467                                                         * fragmentation to the heap) or the
     468                                                         * excess is small. Therefore just enlarge
     469                                                         * the previous block.
     470                                                         */
     471                                                        block_init(prev_head, prev_head->size + excess,
     472                                                            prev_head->free, area);
    354473                                                }
    355474                                               
    356                                                 block_init(next_head, reduced_size, true);
     475                                                block_init(next_head, reduced_size, true, area);
    357476                                                split_mark(next_head, real_size);
    358                                                 result = aligned;
    359                                                 cur = next_head;
     477                                               
     478                                                next = next_head;
     479                                                return aligned;
    360480                                        } else {
    361                                                 /* The current block is the first block on the heap.
    362                                                    We have to make sure that the alignment excess
    363                                                    is large enough to fit a new free block just
    364                                                    before the current block */
     481                                                /*
     482                                                 * The current block is the first block
     483                                                 * in the heap area. We have to make sure
     484                                                 * that the alignment excess is large enough
     485                                                 * to fit a new free block just before the
     486                                                 * current block.
     487                                                 */
    365488                                                while (excess < STRUCT_OVERHEAD) {
    366489                                                        aligned += falign;
     
    371494                                                if (cur->size >= real_size + excess) {
    372495                                                        size_t reduced_size = cur->size - excess;
    373                                                         cur = (heap_block_head_t *) (heap_start + excess);
     496                                                        cur = (heap_block_head_t *)
     497                                                            (AREA_FIRST_BLOCK(area) + excess);
    374498                                                       
    375                                                         block_init(heap_start, excess, true);
    376                                                         block_init(cur, reduced_size, true);
     499                                                        block_init((void *) AREA_FIRST_BLOCK(area), excess,
     500                                                            true, area);
     501                                                        block_init(cur, reduced_size, true, area);
    377502                                                        split_mark(cur, real_size);
    378                                                         result = aligned;
     503                                                       
     504                                                        next = cur;
     505                                                        return aligned;
    379506                                                }
    380507                                        }
     
    382509                        }
    383510                }
    384                
    385                 /* Advance to the next block. */
    386                 cur = (heap_block_head_t *) (((void *) cur) + cur->size);
    387         }
    388        
    389         if ((result == NULL) && (!grown)) {
    390                 if (grow_heap(real_size)) {
    391                         grown = true;
     511        }
     512       
     513        return NULL;
     514}
     515
     516/** Allocate a memory block
     517 *
     518 * Should be called only inside the critical section.
     519 *
     520 * @param size  The size of the block to allocate.
     521 * @param align Memory address alignment.
     522 *
     523 * @return Address of the allocated block or NULL on not enough memory.
     524 *
     525 */
     526static void *malloc_internal(const size_t size, const size_t align)
     527{
     528        assert(first_heap_area != NULL);
     529       
     530        if (align == 0)
     531                return NULL;
     532       
     533        size_t falign = lcm(align, BASE_ALIGN);
     534        size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
     535       
     536        bool retry = false;
     537        heap_block_head_t *split;
     538       
     539loop:
     540       
     541        /* Try the next fit approach */
     542        split = next;
     543       
     544        if (split != NULL) {
     545                void *addr = malloc_area(split->area, split, NULL, real_size,
     546                    falign);
     547               
     548                if (addr != NULL)
     549                        return addr;
     550        }
     551       
     552        /* Search the entire heap */
     553        heap_area_t *area;
     554        for (area = first_heap_area; area != NULL; area = area->next) {
     555                heap_block_head_t *first = (heap_block_head_t *)
     556                    AREA_FIRST_BLOCK(area);
     557               
     558                void *addr = malloc_area(area, first, split, real_size,
     559                    falign);
     560               
     561                if (addr != NULL)
     562                        return addr;
     563        }
     564       
     565        if (!retry) {
     566                /* Try to grow the heap space */
     567                if (heap_grow(real_size)) {
     568                        retry = true;
    392569                        goto loop;
    393570                }
    394571        }
    395572       
    396         return result;
     573        return NULL;
    397574}
    398575
     
    473650            (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
    474651       
    475         assert((void *) head >= heap_start);
    476         assert((void *) head < heap_end);
    477        
    478652        block_check(head);
    479653        assert(!head->free);
     654       
     655        heap_area_t *area = head->area;
     656       
     657        area_check(area);
     658        assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));
     659        assert((void *) head < area->end);
    480660       
    481661        void *ptr = NULL;
     
    487667                /* Shrink */
    488668                if (orig_size - real_size >= STRUCT_OVERHEAD) {
    489                         /* Split the original block to a full block
    490                            and a trailing free block */
    491                         block_init((void *) head, real_size, false);
     669                        /*
     670                         * Split the original block to a full block
     671                         * and a trailing free block.
     672                         */
     673                        block_init((void *) head, real_size, false, area);
    492674                        block_init((void *) head + real_size,
    493                             orig_size - real_size, true);
    494                         shrink_heap();
     675                            orig_size - real_size, true, area);
     676                        heap_shrink();
    495677                }
    496678               
    497679                ptr = ((void *) head) + sizeof(heap_block_head_t);
    498680        } else {
    499                 /* Look at the next block. If it is free and the size is
    500                    sufficient then merge the two. Otherwise just allocate
    501                    a new block, copy the original data into it and
    502                    free the original block. */
     681                /*
     682                 * Look at the next block. If it is free and the size is
     683                 * sufficient then merge the two. Otherwise just allocate
     684                 * a new block, copy the original data into it and
     685                 * free the original block.
     686                 */
    503687                heap_block_head_t *next_head =
    504688                    (heap_block_head_t *) (((void *) head) + head->size);
    505689               
    506                 if (((void *) next_head < heap_end) &&
     690                if (((void *) next_head < area->end) &&
    507691                    (head->size + next_head->size >= real_size) &&
    508692                    (next_head->free)) {
    509693                        block_check(next_head);
    510                         block_init(head, head->size + next_head->size, false);
     694                        block_init(head, head->size + next_head->size, false, area);
    511695                        split_mark(head, real_size);
    512696                       
    513697                        ptr = ((void *) head) + sizeof(heap_block_head_t);
     698                        next = NULL;
    514699                } else
    515700                        reloc = true;
     
    542727            = (heap_block_head_t *) (addr - sizeof(heap_block_head_t));
    543728       
    544         assert((void *) head >= heap_start);
    545         assert((void *) head < heap_end);
    546        
    547729        block_check(head);
    548730        assert(!head->free);
     731       
     732        heap_area_t *area = head->area;
     733       
     734        area_check(area);
     735        assert((void *) head >= (void *) AREA_FIRST_BLOCK(area));
     736        assert((void *) head < area->end);
    549737       
    550738        /* Mark the block itself as free. */
     
    555743            = (heap_block_head_t *) (((void *) head) + head->size);
    556744       
    557         if ((void *) next_head < heap_end) {
     745        if ((void *) next_head < area->end) {
    558746                block_check(next_head);
    559747                if (next_head->free)
    560                         block_init(head, head->size + next_head->size, true);
     748                        block_init(head, head->size + next_head->size, true, area);
    561749        }
    562750       
    563751        /* Look at the previous block. If it is free, merge the two. */
    564         if ((void *) head > heap_start) {
     752        if ((void *) head > (void *) AREA_FIRST_BLOCK(area)) {
    565753                heap_block_foot_t *prev_foot =
    566754                    (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t));
     
    572760               
    573761                if (prev_head->free)
    574                         block_init(prev_head, prev_head->size + head->size, true);
    575         }
    576        
    577         shrink_heap();
     762                        block_init(prev_head, prev_head->size + head->size, true,
     763                            area);
     764        }
     765       
     766        heap_shrink();
    578767       
    579768        futex_up(&malloc_futex);
  • uspace/lib/c/generic/private/libc.h

    rd88218b r0b37882  
    3636#define LIBC_PRIVATE_LIBC_H_
    3737
     38extern void __entry(void);
     39extern void __main(void *) __attribute__((noreturn));
    3840extern int main(int, char *[]);
    39 extern void __main(void *) __attribute__((noreturn));
    4041
    4142#endif
  • uspace/lib/c/include/as.h

    rd88218b r0b37882  
    4141#include <libarch/config.h>
    4242
     43static inline size_t SIZE2PAGES(size_t size)
     44{
     45        if (size == 0)
     46                return 0;
     47       
     48        return (size_t) ((size - 1) >> PAGE_WIDTH) + 1;
     49}
     50
     51static inline size_t PAGES2SIZE(size_t pages)
     52{
     53        return (size_t) (pages << PAGE_WIDTH);
     54}
     55
    4356extern void *as_area_create(void *address, size_t size, int flags);
    4457extern int as_area_resize(void *address, size_t size, int flags);
  • uspace/lib/c/include/malloc.h

    rd88218b r0b37882  
    3838#include <sys/types.h>
    3939
    40 extern uintptr_t get_max_heap_addr(void);
    41 
    4240extern void *malloc(const size_t size)
    4341    __attribute__((malloc));
  • uspace/lib/c/include/unistd.h

    rd88218b r0b37882  
    4444#endif
    4545
    46 #define getpagesize()  (PAGE_SIZE)
    47 
    4846#ifndef SEEK_SET
    4947        #define SEEK_SET  0
     
    5755        #define SEEK_END  2
    5856#endif
     57
     58#define getpagesize()  (PAGE_SIZE)
    5959
    6060extern int dup2(int oldfd, int newfd);
  • uspace/srv/loader/arch/abs32le/_link.ld.in

    rd88218b r0b37882  
    33 * is the base address and the special interp section.
    44 */
     5
    56STARTUP(LIBC_PREFIX/arch/UARCH/src/entry.o)
    67ENTRY(__entry)
     
    5455        } :data
    5556       
    56         . = ALIGN(0x1000);
    57        
    58         _heap = .;
    59        
    6057        /DISCARD/ : {
    6158                *(*);
  • uspace/srv/loader/arch/amd64/_link.ld.in

    rd88218b r0b37882  
    5454        } :data
    5555       
    56         . = ALIGN(0x1000);
    57         _heap = .;
    58        
    5956#ifdef CONFIG_LINE_DEBUG
    6057        .comment 0 : { *(.comment); } :debug
  • uspace/srv/loader/arch/arm32/_link.ld.in

    rd88218b r0b37882  
    33 * is the base address.
    44 */
     5
    56STARTUP(LIBC_PREFIX/arch/UARCH/src/entry.o)
    67ENTRY(__entry)
     
    1617                *(.interp);
    1718        } : interp
    18 
     19       
    1920        . = 0x70001000;
    20 
     21       
    2122        .init ALIGN(0x1000): SUBALIGN(0x1000) {
    2223                *(.init);
    23         } : text
     24        } :text
     25       
    2426        .text : {
    2527                *(.text);
    26         *(.rodata*);
     28                *(.rodata*);
    2729        } :text
    2830       
     
    3234                *(.sdata);
    3335        } :data
     36       
    3437        .tdata : {
    3538                _tdata_start = .;
     
    3740                _tdata_end = .;
    3841        } :data
     42       
    3943        .tbss : {
    4044                _tbss_start = .;
     
    4246                _tbss_end = .;
    4347        } :data
     48       
    4449        _tls_alignment = MAX(ALIGNOF(.tdata), ALIGNOF(.tbss));
     50       
    4551        .bss : {
    4652                *(.sbss);
    4753                *(.scommon);
    48         *(COMMON);
    49         *(.bss);
     54                *(COMMON);
     55                *(.bss);
    5056        } :data
    51        
    52         . = ALIGN(0x1000);
    53         _heap = .;
    5457       
    5558        /DISCARD/ : {
    5659                *(*);
    5760        }
    58 
    5961}
  • uspace/srv/loader/arch/ia32/_link.ld.in

    rd88218b r0b37882  
    5454        } :data
    5555       
    56         . = ALIGN(0x1000);
    57         _heap = .;
    58        
    5956#ifdef CONFIG_LINE_DEBUG
    6057        .comment 0 : { *(.comment); } :debug
  • uspace/srv/loader/arch/ia64/_link.ld.in

    rd88218b r0b37882  
    1212                *(.interp);
    1313        } :interp
    14 
     14       
    1515        /* On Itanium code sections must be aligned to 16 bytes. */
    1616        . = ALIGN(0x800000000 + SIZEOF_HEADERS, 16);
    17 
     17       
    1818        .init : {
    1919                *(.init);
    20         } : text
     20        } :text
     21       
    2122        .text : {
    2223                *(.text);
    2324                *(.rodata*);
    2425        } :text
    25 
     26       
    2627        . = . + 0x4000;
    27 
     28       
    2829        .got : {
    2930                _gp = .;
    3031                *(.got*);
    31         } :data
     32        } :data
     33       
    3234        .data : {
    3335                *(.opd);
     
    3537                *(.sdata);
    3638        } :data
     39       
    3740        .tdata : {
    3841                _tdata_start = .;
     
    4043                _tdata_end = .;
    4144        } :data
     45       
    4246        .tbss : {
    4347                _tbss_start = .;
     
    4549                _tbss_end = .;
    4650        } :data
     51       
    4752        _tls_alignment = MAX(ALIGNOF(.tdata), ALIGNOF(.tbss));
     53       
    4854        .bss : {
    4955                *(.sbss);
     
    5258                *(.bss);
    5359        } :data
    54 
    55         . = ALIGN(0x4000);
    56         _heap = .;
    57  
     60       
    5861        /DISCARD/ : {
    5962                *(*);
    60         }
     63        }
    6164}
  • uspace/srv/loader/arch/mips32/_link.ld.in

    rd88218b r0b37882  
    33 * is the base address.
    44 */
     5
    56STARTUP(LIBC_PREFIX/arch/UARCH/src/entry.o)
    67ENTRY(__entry)
     
    1617                *(.interp);
    1718        } :interp
    18 
     19       
    1920        . = 0x70004000;
    2021       
     
    2223                *(.init);
    2324        } :text
     25       
    2426        .text : {
    25                 *(.text);
     27                *(.text);
    2628                *(.rodata*);
    2729        } :text
    28 
     30       
     31        . = . + 0x4000;
     32       
    2933        .data : {
    3034                *(.data);
    3135                *(.data.rel*);
    3236        } :data
    33 
     37       
    3438        .got : {
    3539                _gp = .;
    3640                *(.got);
    3741        } :data
    38 
     42       
    3943        .tdata : {
    4044                _tdata_start = .;
     
    4246                _tdata_end = .;
    4347        } :data
     48       
    4449        .tbss : {
    4550                _tbss_start = .;
     
    4752                _tbss_end = .;
    4853        } :data
     54       
    4955        _tls_alignment = MAX(ALIGNOF(.tdata), ALIGNOF(.tbss));
    50 
     56       
    5157        .sbss : {
    5258                *(.scommon);
    5359                *(.sbss);
    54         }       
     60        }
     61       
    5562        .bss : {
    5663                *(.bss);
    5764                *(COMMON);
    5865        } :data
    59 
    60         . = ALIGN(0x4000);
    61         _heap = .;
    62 
     66       
    6367        /DISCARD/ : {
    6468                *(*);
  • uspace/srv/loader/arch/ppc32/_link.ld.in

    rd88218b r0b37882  
    33 * is the base address.
    44 */
     5
    56STARTUP(LIBC_PREFIX/arch/UARCH/src/entry.o)
    67ENTRY(__entry)
     
    1617                *(.interp);
    1718        } :interp
    18 
     19       
    1920        . = 0x70001000;
    20 
     21       
    2122        .init ALIGN(0x1000) : SUBALIGN(0x1000) {
    2223                *(.init);
    2324        } :text
     25       
    2426        .text : {
    2527                *(.text);
     
    3133                *(.sdata);
    3234        } :data
     35       
    3336        .tdata : {
    3437                _tdata_start = .;
     
    3639                _tdata_end = .;
    3740        } :data
     41       
    3842        .tbss : {
    3943                _tbss_start = .;
     
    4145                _tbss_end = .;
    4246        } :data
     47       
    4348        _tls_alignment = MAX(ALIGNOF(.tdata), ALIGNOF(.tbss));
     49       
    4450        .bss : {
    4551                *(.sbss);
     
    4753                *(.bss);
    4854        } :data
    49 
    50         . = ALIGN(0x1000);
    51         _heap = .;
    5255       
    5356        /DISCARD/ : {
    5457                *(*);
    5558        }
    56 
    5759}
  • uspace/srv/loader/arch/sparc64/_link.ld.in

    rd88218b r0b37882  
    1212                *(.interp);
    1313        } :interp
    14 
     14       
    1515        . = 0x70004000 + SIZEOF_HEADERS;
    16 
     16       
    1717        .init : {
    1818                *(.init);
    1919        } :text
     20       
    2021        .text : {
    2122                *(.text);
    2223                *(.rodata*);
    2324        } :text
    24 
     25       
    2526        . = . + 0x4000;
    26 
     27       
    2728        .got : {
    2829                 _gp = .;
    2930                 *(.got*);
    3031        } :data
     32       
    3133        .data : {
    3234                *(.data);
    3335                *(.sdata);
    3436        } :data
     37       
    3538        .tdata : {
    3639                _tdata_start = .;
     
    3841                _tdata_end = .;
    3942        } :data
     43       
    4044        .tbss : {
    4145                _tbss_start = .;
     
    4347                _tbss_end = .;
    4448        } :data
     49       
    4550        _tls_alignment = MAX(ALIGNOF(.tdata), ALIGNOF(.tbss));
     51       
    4652        .bss : {
    4753                *(.sbss);
     
    4955                *(.bss);
    5056        } :data
    51 
    52         . = ALIGN(0x4000);
    53         _heap = .;
    5457       
    5558        /DISCARD/ : {
    5659                *(*);
    5760        }
    58 
    5961}
Note: See TracChangeset for help on using the changeset viewer.