Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changes in / [ac9e79d:b294126] in mainline


Ignore:
Location:
kernel/generic
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/include/adt/odict.h

    rac9e79d rb294126  
    4545
    4646extern void odict_initialize(odict_t *, odgetkey_t, odcmp_t);
     47extern void odict_finalize(odict_t *);
    4748extern void odlink_initialize(odlink_t *);
    4849extern void odict_insert(odlink_t *, odict_t *, odlink_t *);
  • kernel/generic/include/mm/as.h

    rac9e79d rb294126  
    4646#include <adt/list.h>
    4747#include <adt/btree.h>
     48#include <adt/odict.h>
    4849#include <lib/elf.h>
    4950#include <arch.h>
     
    115116        mutex_t lock;
    116117
    117         /** B+tree of address space areas. */
    118         btree_t as_area_btree;
     118        /** Address space areas in this address space by base address.
     119         *
     120         * Members are of type as_area_t.
     121         */
     122        odict_t as_areas;
    119123
    120124        /** Non-generic content. */
     
    204208        as_t *as;
    205209
     210        /** Link to @c as->as_areas */
     211        odlink_t las_areas;
     212
    206213        /** Memory flags. */
    207214        unsigned int flags;
     
    273280    uintptr_t *, uintptr_t);
    274281extern errno_t as_area_change_flags(as_t *, unsigned int, uintptr_t);
     282extern as_area_t *as_area_first(as_t *);
     283extern as_area_t *as_area_next(as_area_t *);
    275284
    276285extern unsigned int as_area_get_flags(as_area_t *);
  • kernel/generic/src/adt/odict.c

    rac9e79d rb294126  
    204204        odict->getkey = getkey;
    205205        odict->cmp = cmp;
     206}
     207
     208/** Finalize ordered dictionary.
     209 *
     210 * @param odict Ordered dictionary (must be empty)
     211 */
     212void odict_finalize(odict_t *odict)
     213{
     214        assert(odict->root == NULL);
    206215}
    207216
  • kernel/generic/src/mm/as.c

    rac9e79d rb294126  
    11/*
    22 * Copyright (c) 2010 Jakub Jermar
     3 * Copyright (c) 2018 Jiri Svoboda
    34 * All rights reserved.
    45 *
     
    111112as_t *AS_KERNEL = NULL;
    112113
     114static void *as_areas_getkey(odlink_t *);
     115static int as_areas_cmp(void *, void *);
     116
    113117NO_TRACE static errno_t as_constructor(void *obj, unsigned int flags)
    114118{
     
    150154        (void) as_create_arch(as, 0);
    151155
    152         btree_create(&as->as_area_btree);
     156        odict_initialize(&as->as_areas, as_areas_getkey, as_areas_cmp);
    153157
    154158        if (flags & FLAG_AS_KERNEL)
     
    224228        /*
    225229         * Destroy address space areas of the address space.
    226          * The B+tree must be walked carefully because it is
    227          * also being destroyed.
    228          */
    229         bool cond = true;
    230         while (cond) {
    231                 assert(!list_empty(&as->as_area_btree.leaf_list));
    232 
    233                 btree_node_t *node =
    234                     list_get_instance(list_first(&as->as_area_btree.leaf_list),
    235                     btree_node_t, leaf_link);
    236 
    237                 if ((cond = node->keys))
    238                         as_area_destroy(as, node->key[0]);
    239         }
    240 
    241         btree_destroy(&as->as_area_btree);
     230         * Need to start from the beginning each time since we are destroying
     231         * the areas.
     232         */
     233        as_area_t *area = as_area_first(as);
     234        while (area != NULL) {
     235                /*
     236                 * XXX We already have as_area_t, but as_area_destroy will
     237                 * have to search for it. This could be made faster.
     238                 */
     239                as_area_destroy(as, area->base);
     240                area = as_area_first(as);
     241        }
     242
     243        odict_finalize(&as->as_areas);
    242244
    243245#ifdef AS_PAGE_TABLE
     
    277279}
    278280
     281/** Return first address space area.
     282 *
     283 * @param as Address space
     284 * @return First area in @a as (i.e. area with the lowest base address)
     285 *         or @c NULL if there is none
     286 */
     287as_area_t *as_area_first(as_t *as)
     288{
     289        odlink_t *odlink = odict_first(&as->as_areas);
     290        if (odlink == NULL)
     291                return NULL;
     292
     293        return odict_get_instance(odlink, as_area_t, las_areas);
     294}
     295
     296/** Return next address space area.
     297 *
     298 * @param cur Current area
     299 * @return Next area in the same address space or @c NULL if @a cur is the
     300 *         last area.
     301 */
     302as_area_t *as_area_next(as_area_t *cur)
     303{
     304        odlink_t *odlink = odict_next(&cur->las_areas, &cur->as->as_areas);
     305        if (odlink == NULL)
     306                return NULL;
     307
     308        return odict_get_instance(odlink, as_area_t, las_areas);
     309}
     310
     311/** Determine if area with specified parameters would conflict with
     312 * a specific existing address space area.
     313 *
     314 * @param addr    Starting virtual address of the area being tested.
     315 * @param count   Number of pages in the area being tested.
     316 * @param guarded True if the area being tested is protected by guard pages.
     317 * @param area    Area against which we are testing.
     318 *
     319 * @return True if the two areas conflict, false otherwise.
     320 */
     321NO_TRACE static bool area_is_conflicting(uintptr_t addr,
     322    size_t count, bool guarded, as_area_t *area)
     323{
     324        assert((addr % PAGE_SIZE) == 0);
     325
     326        size_t gsize = P2SZ(count);
     327        size_t agsize = P2SZ(area->pages);
     328
     329        /*
     330         * A guarded area has one guard page before, one page after.
     331         * What we do here is: if either area is guarded, we add
     332         * PAGE_SIZE to the size of both areas. That guarantees
     333         * they will be spaced at least one page apart.
     334         */
     335        if (guarded || (area->flags & AS_AREA_GUARD) != 0) {
     336                /* Add guard page size unless area is at the end of VA domain */
     337                if (!overflows(addr, P2SZ(count)))
     338                        gsize += PAGE_SIZE;
     339
     340                /* Add guard page size unless area is at the end of VA domain */
     341                if (!overflows(area->base, P2SZ(area->pages)))
     342                        agsize += PAGE_SIZE;
     343        }
     344
     345        return overlaps(addr, gsize, area->base, agsize);
     346
     347}
     348
    279349/** Check area conflicts with other areas.
    280350 *
     
    283353 * @param count   Number of pages in the area being tested.
    284354 * @param guarded True if the area being tested is protected by guard pages.
    285  * @param avoid   Do not touch this area.
     355 * @param avoid   Do not touch this area. I.e. this area is not considered
     356 *                as presenting a conflict.
    286357 *
    287358 * @return True if there is no conflict, false otherwise.
     
    308379
    309380        /*
    310          * The leaf node is found in O(log n), where n is proportional to
    311          * the number of address space areas belonging to as.
    312          * The check for conflicts is then attempted on the rightmost
    313          * record in the left neighbour, the leftmost record in the right
    314          * neighbour and all records in the leaf node itself.
    315          */
    316         btree_node_t *leaf;
    317         as_area_t *area =
    318             (as_area_t *) btree_search(&as->as_area_btree, addr, &leaf);
    319         if (area) {
    320                 if (area != avoid)
    321                         return false;
    322         }
    323 
    324         /* First, check the two border cases. */
    325         btree_node_t *node =
    326             btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
    327         if (node) {
    328                 area = (as_area_t *) node->value[node->keys - 1];
     381         * To determine if we overlap with another area, we just need
     382         * to look at overlap with the last area with base address <=
     383         * to ours and on the first area with base address > than ours.
     384         *
     385         * First find last area with <= base address.
     386         */
     387        odlink_t *odlink = odict_find_leq(&as->as_areas, &addr, NULL);
     388        if (odlink != NULL) {
     389                as_area_t *area = odict_get_instance(odlink, as_area_t,
     390                    las_areas);
    329391
    330392                if (area != avoid) {
    331393                        mutex_lock(&area->lock);
    332 
    333                         /*
    334                          * If at least one of the two areas are protected
    335                          * by the AS_AREA_GUARD flag then we must be sure
    336                          * that they are separated by at least one unmapped
    337                          * page.
    338                          */
    339                         int const gp = (guarded ||
    340                             (area->flags & AS_AREA_GUARD)) ? 1 : 0;
    341 
    342                         /*
    343                          * The area comes from the left neighbour node, which
    344                          * means that there already are some areas in the leaf
    345                          * node, which in turn means that adding gp is safe and
    346                          * will not cause an integer overflow.
    347                          */
    348                         if (overlaps(addr, P2SZ(count), area->base,
    349                             P2SZ(area->pages + gp))) {
     394                        if (area_is_conflicting(addr, count, guarded, area)) {
    350395                                mutex_unlock(&area->lock);
    351396                                return false;
     
    354399                        mutex_unlock(&area->lock);
    355400                }
    356         }
    357 
    358         node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf);
    359         if (node) {
    360                 area = (as_area_t *) node->value[0];
     401
     402                /* Next area */
     403                odlink = odict_next(odlink, &as->as_areas);
     404        }
     405
     406        /*
     407         * Next area, if any, is the first with base > than our base address.
     408         * If there was no area with <= base, we need to look at the first area.
     409         */
     410        if (odlink == NULL)
     411                odlink = odict_first(&as->as_areas);
     412
     413        if (odlink != NULL) {
     414                as_area_t *area = odict_get_instance(odlink, as_area_t,
     415                    las_areas);
    361416
    362417                if (area != avoid) {
    363                         int gp;
    364 
    365418                        mutex_lock(&area->lock);
    366 
    367                         gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0;
    368                         if (gp && overflows(addr, P2SZ(count))) {
    369                                 /*
    370                                  * Guard page not needed if the supposed area
    371                                  * is adjacent to the end of the address space.
    372                                  * We already know that the following test is
    373                                  * going to fail...
    374                                  */
    375                                 gp--;
    376                         }
    377 
    378                         if (overlaps(addr, P2SZ(count + gp), area->base,
    379                             P2SZ(area->pages))) {
     419                        if (area_is_conflicting(addr, count, guarded, area)) {
    380420                                mutex_unlock(&area->lock);
    381421                                return false;
     
    384424                        mutex_unlock(&area->lock);
    385425                }
    386         }
    387 
    388         /* Second, check the leaf node. */
    389         btree_key_t i;
    390         for (i = 0; i < leaf->keys; i++) {
    391                 area = (as_area_t *) leaf->value[i];
    392                 int agp;
    393                 int gp;
    394 
    395                 if (area == avoid)
    396                         continue;
    397 
    398                 mutex_lock(&area->lock);
    399 
    400                 gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0;
    401                 agp = gp;
    402 
    403                 /*
    404                  * Sanitize the two possible unsigned integer overflows.
    405                  */
    406                 if (gp && overflows(addr, P2SZ(count)))
    407                         gp--;
    408                 if (agp && overflows(area->base, P2SZ(area->pages)))
    409                         agp--;
    410 
    411                 if (overlaps(addr, P2SZ(count + gp), area->base,
    412                     P2SZ(area->pages + agp))) {
    413                         mutex_unlock(&area->lock);
    414                         return false;
    415                 }
    416 
    417                 mutex_unlock(&area->lock);
    418426        }
    419427
     
    482490
    483491        /* Eventually check the addresses behind each area */
    484         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, node) {
    485 
    486                 for (btree_key_t i = 0; i < node->keys; i++) {
    487                         as_area_t *area = (as_area_t *) node->value[i];
    488 
    489                         mutex_lock(&area->lock);
    490 
    491                         addr =
    492                             ALIGN_UP(area->base + P2SZ(area->pages), PAGE_SIZE);
    493 
    494                         if (guarded || area->flags & AS_AREA_GUARD) {
    495                                 /*
    496                                  * We must leave an unmapped page
    497                                  * between the two areas.
    498                                  */
    499                                 addr += P2SZ(1);
    500                         }
    501 
    502                         bool avail =
    503                             ((addr >= bound) && (addr >= area->base) &&
    504                             (check_area_conflicts(as, addr, pages, guarded, area)));
    505 
    506                         mutex_unlock(&area->lock);
    507 
    508                         if (avail)
    509                                 return addr;
    510                 }
     492        as_area_t *area = as_area_first(as);
     493        while (area != NULL) {
     494                mutex_lock(&area->lock);
     495
     496                addr = area->base + P2SZ(area->pages);
     497
     498                if (guarded || area->flags & AS_AREA_GUARD) {
     499                        /*
     500                         * We must leave an unmapped page
     501                         * between the two areas.
     502                         */
     503                        addr += P2SZ(1);
     504                }
     505
     506                bool avail =
     507                    ((addr >= bound) && (addr >= area->base) &&
     508                    (check_area_conflicts(as, addr, pages, guarded, area)));
     509
     510                mutex_unlock(&area->lock);
     511
     512                if (avail)
     513                        return addr;
     514
     515                area = as_area_next(area);
    511516        }
    512517
     
    623628
    624629        area->as = as;
     630        odlink_initialize(&area->las_areas);
    625631        area->flags = flags;
    626632        area->attributes = attrs;
     
    680686
    681687        btree_create(&area->used_space);
    682         btree_insert(&as->as_area_btree, *base, (void *) area,
    683             NULL);
     688        odict_insert(&area->las_areas, &as->as_areas, NULL);
    684689
    685690        mutex_unlock(&as->lock);
     
    701706        assert(mutex_locked(&as->lock));
    702707
    703         btree_node_t *leaf;
    704         as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va,
    705             &leaf);
    706         if (area) {
    707                 /* va is the base address of an address space area */
    708                 mutex_lock(&area->lock);
     708        odlink_t *odlink = odict_find_leq(&as->as_areas, &va, NULL);
     709        if (odlink == NULL)
     710                return NULL;
     711
     712        as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);
     713        mutex_lock(&area->lock);
     714
     715        assert(area->base <= va);
     716
     717        if (va <= area->base + (P2SZ(area->pages) - 1))
    709718                return area;
    710         }
    711 
    712         /*
    713          * Search the leaf node and the rightmost record of its left neighbour
    714          * to find out whether this is a miss or va belongs to an address
    715          * space area found there.
    716          */
    717 
    718         /* First, search the leaf node itself. */
    719         btree_key_t i;
    720 
    721         for (i = 0; i < leaf->keys; i++) {
    722                 area = (as_area_t *) leaf->value[i];
    723 
    724                 mutex_lock(&area->lock);
    725 
    726                 if ((area->base <= va) &&
    727                     (va <= area->base + (P2SZ(area->pages) - 1)))
    728                         return area;
    729 
    730                 mutex_unlock(&area->lock);
    731         }
    732 
    733         /*
    734          * Second, locate the left neighbour and test its last record.
    735          * Because of its position in the B+tree, it must have base < va.
    736          */
    737         btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree,
    738             leaf);
    739         if (lnode) {
    740                 area = (as_area_t *) lnode->value[lnode->keys - 1];
    741 
    742                 mutex_lock(&area->lock);
    743 
    744                 if (va <= area->base + (P2SZ(area->pages) - 1))
    745                         return area;
    746 
    747                 mutex_unlock(&area->lock);
    748         }
    749 
     719
     720        mutex_unlock(&area->lock);
    750721        return NULL;
    751722}
     
    985956                area->backend->destroy(area);
    986957
    987         uintptr_t base = area->base;
    988 
    989958        page_table_lock(as, false);
    990959
     
    10531022         * Remove the empty area from address space.
    10541023         */
    1055         btree_remove(&as->as_area_btree, base, NULL);
     1024        odict_remove(&area->las_areas);
    10561025
    10571026        free(area);
     
    16081577
    16091578        return area_flags_to_page_flags(area->flags);
     1579}
     1580
     1581/** Get key function for the @c as_t.as_areas ordered dictionary.
     1582 *
     1583 * @param odlink Link
     1584 * @return Pointer to task ID cast as 'void *'
     1585 */
     1586static void *as_areas_getkey(odlink_t *odlink)
     1587{
     1588        as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);
     1589        return (void *) &area->base;
     1590}
     1591
     1592/** Key comparison function for the @c as_t.as_areas ordered dictionary.
     1593 *
     1594 * @param a Pointer to area A base
     1595 * @param b Pointer to area B base
     1596 * @return -1, 0, 1 iff base of A is lower than, equal to, higher than B
     1597 */
     1598static int as_areas_cmp(void *a, void *b)
     1599{
     1600        uintptr_t base_a = *(uintptr_t *)a;
     1601        uintptr_t base_b = *(uintptr_t *)b;
     1602
     1603        if (base_a < base_b)
     1604                return -1;
     1605        else if (base_a == base_b)
     1606                return 0;
     1607        else
     1608                return +1;
    16101609}
    16111610
     
    22422241        mutex_lock(&as->lock);
    22432242
    2244         /* First pass, count number of areas. */
    2245 
    2246         size_t area_cnt = 0;
    2247 
    2248         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
    2249             node) {
    2250                 area_cnt += node->keys;
    2251         }
     2243        /* Count number of areas. */
     2244        size_t area_cnt = odict_count(&as->as_areas);
    22522245
    22532246        size_t isize = area_cnt * sizeof(as_area_info_t);
    22542247        as_area_info_t *info = nfmalloc(isize);
    22552248
    2256         /* Second pass, record data. */
     2249        /* Record area data. */
    22572250
    22582251        size_t area_idx = 0;
    22592252
    2260         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
    2261             node) {
    2262                 btree_key_t i;
    2263 
    2264                 for (i = 0; i < node->keys; i++) {
    2265                         as_area_t *area = node->value[i];
    2266 
    2267                         assert(area_idx < area_cnt);
    2268                         mutex_lock(&area->lock);
    2269 
    2270                         info[area_idx].start_addr = area->base;
    2271                         info[area_idx].size = P2SZ(area->pages);
    2272                         info[area_idx].flags = area->flags;
    2273                         ++area_idx;
    2274 
    2275                         mutex_unlock(&area->lock);
    2276                 }
     2253        as_area_t *area = as_area_first(as);
     2254        while (area != NULL) {
     2255                assert(area_idx < area_cnt);
     2256                mutex_lock(&area->lock);
     2257
     2258                info[area_idx].start_addr = area->base;
     2259                info[area_idx].size = P2SZ(area->pages);
     2260                info[area_idx].flags = area->flags;
     2261                ++area_idx;
     2262
     2263                mutex_unlock(&area->lock);
     2264                area = as_area_next(area);
    22772265        }
    22782266
     
    22932281
    22942282        /* Print out info about address space areas */
    2295         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
    2296             node) {
    2297                 btree_key_t i;
    2298 
    2299                 for (i = 0; i < node->keys; i++) {
    2300                         as_area_t *area = node->value[i];
    2301 
    2302                         mutex_lock(&area->lock);
    2303                         printf("as_area: %p, base=%p, pages=%zu"
    2304                             " (%p - %p)\n", area, (void *) area->base,
    2305                             area->pages, (void *) area->base,
    2306                             (void *) (area->base + P2SZ(area->pages)));
    2307                         mutex_unlock(&area->lock);
    2308                 }
     2283        as_area_t *area = as_area_first(as);
     2284        while (area != NULL) {
     2285                mutex_lock(&area->lock);
     2286                printf("as_area: %p, base=%p, pages=%zu"
     2287                    " (%p - %p)\n", area, (void *) area->base,
     2288                    area->pages, (void *) area->base,
     2289                    (void *) (area->base + P2SZ(area->pages)));
     2290                mutex_unlock(&area->lock);
     2291
     2292                area = as_area_next(area);
    23092293        }
    23102294
  • kernel/generic/src/proc/task.c

    rac9e79d rb294126  
    6464IRQ_SPINLOCK_INITIALIZE(tasks_lock);
    6565
    66 /** Ordered dictionary of active tasks.
     66/** Ordered dictionary of active tasks by task ID.
     67 *
     68 * Members are task_t structures.
    6769 *
    6870 * The task is guaranteed to exist after it was found in the @c tasks
  • kernel/generic/src/sysinfo/stats.c

    rac9e79d rb294126  
    145145        size_t pages = 0;
    146146
    147         /* Walk the B+ tree and count pages */
    148         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
    149             node) {
    150                 unsigned int i;
    151                 for (i = 0; i < node->keys; i++) {
    152                         as_area_t *area = node->value[i];
    153 
    154                         if (mutex_trylock(&area->lock) != EOK)
    155                                 continue;
    156 
    157                         pages += area->pages;
    158                         mutex_unlock(&area->lock);
    159                 }
     147        /* Walk areas in the address space and count pages */
     148        as_area_t *area = as_area_first(as);
     149        while (area != NULL) {
     150                if (mutex_trylock(&area->lock) != EOK)
     151                        continue;
     152
     153                pages += area->pages;
     154                mutex_unlock(&area->lock);
     155                area = as_area_next(area);
    160156        }
    161157
     
    186182        size_t pages = 0;
    187183
    188         /* Walk the B+ tree and count pages */
    189         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, node) {
    190                 unsigned int i;
    191                 for (i = 0; i < node->keys; i++) {
    192                         as_area_t *area = node->value[i];
    193 
    194                         if (mutex_trylock(&area->lock) != EOK)
    195                                 continue;
    196 
    197                         pages += area->resident;
    198                         mutex_unlock(&area->lock);
    199                 }
     184        /* Walk areas in the address space and count pages */
     185        as_area_t *area = as_area_first(as);
     186        while (area != NULL) {
     187                if (mutex_trylock(&area->lock) != EOK)
     188                        continue;
     189
     190                pages += area->resident;
     191                mutex_unlock(&area->lock);
     192                area = as_area_next(area);
    200193        }
    201194
Note: See TracChangeset for help on using the changeset viewer.