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

Changeset 88cc71c0 in mainline


Ignore:
Timestamp:
2018-11-06T09:39:24Z (3 years ago)
Author:
Jiri Svoboda <jiri@…>
Branches:
lfn, master
Children:
d9d0088
Parents:
4a8d0dd1
git-author:
Jiri Svoboda <jiri@…> (2018-10-05 18:38:50)
git-committer:
Jiri Svoboda <jiri@…> (2018-11-06 09:39:24)
Message:

Replace as_area_btree with ordered dictionary.

Location:
kernel/generic
Files:
6 edited

Legend:

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

    r4a8d0dd1 r88cc71c0  
    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

    r4a8d0dd1 r88cc71c0  
    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

    r4a8d0dd1 r88cc71c0  
    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

    r4a8d0dd1 r88cc71c0  
    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{
     
    156160        (void) as_create_arch(as, 0);
    157161
    158         btree_create(&as->as_area_btree);
     162        odict_initialize(&as->as_areas, as_areas_getkey, as_areas_cmp);
    159163
    160164        if (flags & FLAG_AS_KERNEL)
     
    230234        /*
    231235         * Destroy address space areas of the address space.
    232          * The B+tree must be walked carefully because it is
    233          * also being destroyed.
    234          */
    235         bool cond = true;
    236         while (cond) {
    237                 assert(!list_empty(&as->as_area_btree.leaf_list));
    238 
    239                 btree_node_t *node =
    240                     list_get_instance(list_first(&as->as_area_btree.leaf_list),
    241                     btree_node_t, leaf_link);
    242 
    243                 if ((cond = node->keys))
    244                         as_area_destroy(as, node->key[0]);
    245         }
    246 
    247         btree_destroy(&as->as_area_btree);
     236         * Need to start from the beginning each time since we are destroying
     237         * the areas.
     238         */
     239        as_area_t *area = as_area_first(as);
     240        while (area != NULL) {
     241                /*
     242                 * XXX We already have as_area_t, but as_area_destroy will
     243                 * have to search for it. This could be made faster.
     244                 */
     245                as_area_destroy(as, area->base);
     246                area = as_area_first(as);
     247        }
     248
     249        odict_finalize(&as->as_areas);
    248250
    249251#ifdef AS_PAGE_TABLE
     
    283285}
    284286
     287/** Return first address space area.
     288 *
     289 * @param as Address space
     290 * @return First area in @a as (i.e. area with the lowest base address)
     291 *         or @c NULL if there is none
     292 */
     293as_area_t *as_area_first(as_t *as)
     294{
     295        odlink_t *odlink = odict_first(&as->as_areas);
     296        if (odlink == NULL)
     297                return NULL;
     298
     299        return odict_get_instance(odlink, as_area_t, las_areas);
     300}
     301
     302/** Return next address space area.
     303 *
     304 * @param cur Current area
     305 * @return Next area in the same address space or @c NULL if @a cur is the
     306 *         last area.
     307 */
     308as_area_t *as_area_next(as_area_t *cur)
     309{
     310        odlink_t *odlink = odict_next(&cur->las_areas, &cur->as->as_areas);
     311        if (odlink == NULL)
     312                return NULL;
     313
     314        return odict_get_instance(odlink, as_area_t, las_areas);
     315}
     316
     317/** Determine if area with specified parameters would conflict with
     318 * a specific existing address space area.
     319 *
     320 * @param addr    Starting virtual address of the area being tested.
     321 * @param count   Number of pages in the area being tested.
     322 * @param guarded True if the area being tested is protected by guard pages.
     323 * @param area    Area against which we are testing.
     324 *
     325 * @return True if the two areas conflict, false otherwise.
     326 *
     327 */
     328NO_TRACE static bool area_is_conflicting(uintptr_t addr,
     329    size_t count, bool guarded, as_area_t *area)
     330{
     331        assert((addr % PAGE_SIZE) == 0);
     332
     333        /* Add guard page size unless area is at the end of VA domain */
     334        size_t gsize = P2SZ(count);
     335        if (guarded && !overflows(addr, P2SZ(count)))
     336                gsize += PAGE_SIZE;
     337
     338        /* Add guard page size unless area is at the end of VA domain */
     339        size_t agsize = P2SZ(area->pages);
     340        if ((area->flags & AS_AREA_GUARD) != 0 &&
     341            !overflows(area->base, P2SZ(area->pages)))
     342                agsize += PAGE_SIZE;
     343
     344        return overlaps(addr, gsize, area->base, agsize);
     345
     346}
     347
    285348/** Check area conflicts with other areas.
    286349 *
     
    289352 * @param count   Number of pages in the area being tested.
    290353 * @param guarded True if the area being tested is protected by guard pages.
    291  * @param avoid   Do not touch this area.
     354 * @param avoid   Do not touch this area. I.e. this area is not considered
     355 *                as presenting a conflict.
    292356 *
    293357 * @return True if there is no conflict, false otherwise.
     
    314378
    315379        /*
    316          * The leaf node is found in O(log n), where n is proportional to
    317          * the number of address space areas belonging to as.
    318          * The check for conflicts is then attempted on the rightmost
    319          * record in the left neighbour, the leftmost record in the right
    320          * neighbour and all records in the leaf node itself.
    321          */
    322         btree_node_t *leaf;
    323         as_area_t *area =
    324             (as_area_t *) btree_search(&as->as_area_btree, addr, &leaf);
    325         if (area) {
    326                 if (area != avoid)
    327                         return false;
    328         }
    329 
    330         /* First, check the two border cases. */
    331         btree_node_t *node =
    332             btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
    333         if (node) {
    334                 area = (as_area_t *) node->value[node->keys - 1];
     380         * To determine if we overlap with another area, we just need
     381         * to look at overlap with the last area with base address <=
     382         * to ours and on the first area with base address > than ours.
     383         *
     384         * First find last area with <= base address.
     385         */
     386        odlink_t *odlink = odict_find_leq(&as->as_areas, &addr, NULL);
     387        if (odlink != NULL) {
     388                as_area_t *area = odict_get_instance(odlink, as_area_t,
     389                    las_areas);
    335390
    336391                if (area != avoid) {
    337392                        mutex_lock(&area->lock);
    338 
    339                         /*
    340                          * If at least one of the two areas are protected
    341                          * by the AS_AREA_GUARD flag then we must be sure
    342                          * that they are separated by at least one unmapped
    343                          * page.
    344                          */
    345                         int const gp = (guarded ||
    346                             (area->flags & AS_AREA_GUARD)) ? 1 : 0;
    347 
    348                         /*
    349                          * The area comes from the left neighbour node, which
    350                          * means that there already are some areas in the leaf
    351                          * node, which in turn means that adding gp is safe and
    352                          * will not cause an integer overflow.
    353                          */
    354                         if (overlaps(addr, P2SZ(count), area->base,
    355                             P2SZ(area->pages + gp))) {
     393                        if (area_is_conflicting(addr, count, guarded, area)) {
    356394                                mutex_unlock(&area->lock);
    357395                                return false;
     
    360398                        mutex_unlock(&area->lock);
    361399                }
    362         }
    363 
    364         node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf);
    365         if (node) {
    366                 area = (as_area_t *) node->value[0];
     400
     401                /* Next area */
     402                odlink = odict_next(odlink, &as->as_areas);
     403        }
     404
     405        /* Next area, if any, is the first with base > than our base address */
     406        if (odlink != NULL) {
     407                as_area_t *area = odict_get_instance(odlink, as_area_t,
     408                    las_areas);
    367409
    368410                if (area != avoid) {
    369                         int gp;
    370 
    371411                        mutex_lock(&area->lock);
    372 
    373                         gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0;
    374                         if (gp && overflows(addr, P2SZ(count))) {
    375                                 /*
    376                                  * Guard page not needed if the supposed area
    377                                  * is adjacent to the end of the address space.
    378                                  * We already know that the following test is
    379                                  * going to fail...
    380                                  */
    381                                 gp--;
    382                         }
    383 
    384                         if (overlaps(addr, P2SZ(count + gp), area->base,
    385                             P2SZ(area->pages))) {
     412                        if (area_is_conflicting(addr, count, guarded, area)) {
    386413                                mutex_unlock(&area->lock);
    387414                                return false;
     
    390417                        mutex_unlock(&area->lock);
    391418                }
    392         }
    393 
    394         /* Second, check the leaf node. */
    395         btree_key_t i;
    396         for (i = 0; i < leaf->keys; i++) {
    397                 area = (as_area_t *) leaf->value[i];
    398                 int agp;
    399                 int gp;
    400 
    401                 if (area == avoid)
    402                         continue;
    403 
    404                 mutex_lock(&area->lock);
    405 
    406                 gp = (guarded || (area->flags & AS_AREA_GUARD)) ? 1 : 0;
    407                 agp = gp;
    408 
    409                 /*
    410                  * Sanitize the two possible unsigned integer overflows.
    411                  */
    412                 if (gp && overflows(addr, P2SZ(count)))
    413                         gp--;
    414                 if (agp && overflows(area->base, P2SZ(area->pages)))
    415                         agp--;
    416 
    417                 if (overlaps(addr, P2SZ(count + gp), area->base,
    418                     P2SZ(area->pages + agp))) {
    419                         mutex_unlock(&area->lock);
    420                         return false;
    421                 }
    422 
    423                 mutex_unlock(&area->lock);
    424419        }
    425420
     
    488483
    489484        /* Eventually check the addresses behind each area */
    490         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t, node) {
    491 
    492                 for (btree_key_t i = 0; i < node->keys; i++) {
    493                         as_area_t *area = (as_area_t *) node->value[i];
    494 
    495                         mutex_lock(&area->lock);
    496 
    497                         addr =
    498                             ALIGN_UP(area->base + P2SZ(area->pages), PAGE_SIZE);
    499 
    500                         if (guarded || area->flags & AS_AREA_GUARD) {
    501                                 /*
    502                                  * We must leave an unmapped page
    503                                  * between the two areas.
    504                                  */
    505                                 addr += P2SZ(1);
    506                         }
    507 
    508                         bool avail =
    509                             ((addr >= bound) && (addr >= area->base) &&
    510                             (check_area_conflicts(as, addr, pages, guarded, area)));
    511 
    512                         mutex_unlock(&area->lock);
    513 
    514                         if (avail)
    515                                 return addr;
    516                 }
     485        as_area_t *area = as_area_first(as);
     486        while (area != NULL) {
     487                mutex_lock(&area->lock);
     488
     489                addr = ALIGN_UP(area->base + P2SZ(area->pages), PAGE_SIZE);
     490
     491                if (guarded || area->flags & AS_AREA_GUARD) {
     492                        /*
     493                         * We must leave an unmapped page
     494                         * between the two areas.
     495                         */
     496                        addr += P2SZ(1);
     497                }
     498
     499                bool avail =
     500                    ((addr >= bound) && (addr >= area->base) &&
     501                    (check_area_conflicts(as, addr, pages, guarded, area)));
     502
     503                mutex_unlock(&area->lock);
     504
     505                if (avail)
     506                        return addr;
     507
     508                area = as_area_next(area);
    517509        }
    518510
     
    629621
    630622        area->as = as;
     623        odlink_initialize(&area->las_areas);
    631624        area->flags = flags;
    632625        area->attributes = attrs;
     
    686679
    687680        btree_create(&area->used_space);
    688         btree_insert(&as->as_area_btree, *base, (void *) area,
    689             NULL);
     681        odict_insert(&area->las_areas, &as->as_areas, NULL);
    690682
    691683        mutex_unlock(&as->lock);
     
    707699        assert(mutex_locked(&as->lock));
    708700
    709         btree_node_t *leaf;
    710         as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va,
    711             &leaf);
    712         if (area) {
    713                 /* va is the base address of an address space area */
    714                 mutex_lock(&area->lock);
     701        odlink_t *odlink = odict_find_leq(&as->as_areas, &va, NULL);
     702        if (odlink == NULL)
     703                return NULL;
     704
     705        as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);
     706        mutex_lock(&area->lock);
     707
     708        assert(area->base <= va);
     709
     710        if (va <= area->base + (P2SZ(area->pages) - 1))
    715711                return area;
    716         }
    717 
    718         /*
    719          * Search the leaf node and the rightmost record of its left neighbour
    720          * to find out whether this is a miss or va belongs to an address
    721          * space area found there.
    722          */
    723 
    724         /* First, search the leaf node itself. */
    725         btree_key_t i;
    726 
    727         for (i = 0; i < leaf->keys; i++) {
    728                 area = (as_area_t *) leaf->value[i];
    729 
    730                 mutex_lock(&area->lock);
    731 
    732                 if ((area->base <= va) &&
    733                     (va <= area->base + (P2SZ(area->pages) - 1)))
    734                         return area;
    735 
    736                 mutex_unlock(&area->lock);
    737         }
    738 
    739         /*
    740          * Second, locate the left neighbour and test its last record.
    741          * Because of its position in the B+tree, it must have base < va.
    742          */
    743         btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree,
    744             leaf);
    745         if (lnode) {
    746                 area = (as_area_t *) lnode->value[lnode->keys - 1];
    747 
    748                 mutex_lock(&area->lock);
    749 
    750                 if (va <= area->base + (P2SZ(area->pages) - 1))
    751                         return area;
    752 
    753                 mutex_unlock(&area->lock);
    754         }
    755 
     712
     713        mutex_unlock(&area->lock);
    756714        return NULL;
    757715}
     
    991949                area->backend->destroy(area);
    992950
    993         uintptr_t base = area->base;
    994 
    995951        page_table_lock(as, false);
    996952
     
    10591015         * Remove the empty area from address space.
    10601016         */
    1061         btree_remove(&as->as_area_btree, base, NULL);
     1017        odict_remove(&area->las_areas);
    10621018
    10631019        free(area);
     
    16141570
    16151571        return area_flags_to_page_flags(area->flags);
     1572}
     1573
     1574/** Get key function for the @c as_t.as_areas ordered dictionary.
     1575 *
     1576 * @param odlink Link
     1577 * @return Pointer to task ID cast as 'void *'
     1578 */
     1579static void *as_areas_getkey(odlink_t *odlink)
     1580{
     1581        as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);
     1582        return (void *) &area->base;
     1583}
     1584
     1585/** Key comparison function for the @c as_t.as_areas ordered dictionary.
     1586 *
     1587 * @param a Pointer to area A base
     1588 * @param b Pointer to area B base
     1589 * @return -1, 0, 1 iff base of A is lower than, equal to, higher than B
     1590 */
     1591static int as_areas_cmp(void *a, void *b)
     1592{
     1593        uintptr_t base_a = *(uintptr_t *)a;
     1594        uintptr_t base_b = *(uintptr_t *)b;
     1595
     1596        if (base_a < base_b)
     1597                return -1;
     1598        else if (base_a == base_b)
     1599                return 0;
     1600        else
     1601                return +1;
    16161602}
    16171603
     
    22482234        mutex_lock(&as->lock);
    22492235
    2250         /* First pass, count number of areas. */
    2251 
    2252         size_t area_cnt = 0;
    2253 
    2254         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
    2255             node) {
    2256                 area_cnt += node->keys;
    2257         }
     2236        /* Count number of areas. */
     2237        size_t area_cnt = odict_count(&as->as_areas);
    22582238
    22592239        size_t isize = area_cnt * sizeof(as_area_info_t);
    22602240        as_area_info_t *info = nfmalloc(isize);
    22612241
    2262         /* Second pass, record data. */
     2242        /* Record area data. */
    22632243
    22642244        size_t area_idx = 0;
    22652245
    2266         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
    2267             node) {
    2268                 btree_key_t i;
    2269 
    2270                 for (i = 0; i < node->keys; i++) {
    2271                         as_area_t *area = node->value[i];
    2272 
    2273                         assert(area_idx < area_cnt);
    2274                         mutex_lock(&area->lock);
    2275 
    2276                         info[area_idx].start_addr = area->base;
    2277                         info[area_idx].size = P2SZ(area->pages);
    2278                         info[area_idx].flags = area->flags;
    2279                         ++area_idx;
    2280 
    2281                         mutex_unlock(&area->lock);
    2282                 }
     2246        as_area_t *area = as_area_first(as);
     2247        while (area != NULL) {
     2248                assert(area_idx < area_cnt);
     2249                mutex_lock(&area->lock);
     2250
     2251                info[area_idx].start_addr = area->base;
     2252                info[area_idx].size = P2SZ(area->pages);
     2253                info[area_idx].flags = area->flags;
     2254                ++area_idx;
     2255
     2256                mutex_unlock(&area->lock);
     2257                area = as_area_next(area);
    22832258        }
    22842259
     
    22992274
    23002275        /* Print out info about address space areas */
    2301         list_foreach(as->as_area_btree.leaf_list, leaf_link, btree_node_t,
    2302             node) {
    2303                 btree_key_t i;
    2304 
    2305                 for (i = 0; i < node->keys; i++) {
    2306                         as_area_t *area = node->value[i];
    2307 
    2308                         mutex_lock(&area->lock);
    2309                         printf("as_area: %p, base=%p, pages=%zu"
    2310                             " (%p - %p)\n", area, (void *) area->base,
    2311                             area->pages, (void *) area->base,
    2312                             (void *) (area->base + P2SZ(area->pages)));
    2313                         mutex_unlock(&area->lock);
    2314                 }
     2276        as_area_t *area = as_area_first(as);
     2277        while (area != NULL) {
     2278                mutex_lock(&area->lock);
     2279                printf("as_area: %p, base=%p, pages=%zu"
     2280                    " (%p - %p)\n", area, (void *) area->base,
     2281                    area->pages, (void *) area->base,
     2282                    (void *) (area->base + P2SZ(area->pages)));
     2283                mutex_unlock(&area->lock);
     2284
     2285                area = as_area_next(area);
    23152286        }
    23162287
  • kernel/generic/src/proc/task.c

    r4a8d0dd1 r88cc71c0  
    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

    r4a8d0dd1 r88cc71c0  
    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.