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

Changeset 6454db5e in mainline


Ignore:
Timestamp:
2018-11-07T17:44:51Z (3 years ago)
Author:
GitHub <noreply@…>
Branches:
lfn, master
Children:
b294126
Parents:
4a8d0dd1 (diff), 6785b88b (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.
git-author:
jxsvoboda <5887334+jxsvoboda@…> (2018-11-07 17:44:51)
git-committer:
GitHub <noreply@…> (2018-11-07 17:44:51)
Message:

Merge pull request #51 from jxsvoboda/master

Replace as_area_btree with ordered dictionary.

Location:
kernel/generic
Files:
6 edited

Legend:

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

    r4a8d0dd1 r6454db5e  
    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 r6454db5e  
    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 r6454db5e  
    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 r6454db5e  
    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 */
     327NO_TRACE static bool area_is_conflicting(uintptr_t addr,
     328    size_t count, bool guarded, as_area_t *area)
     329{
     330        assert((addr % PAGE_SIZE) == 0);
     331
     332        size_t gsize = P2SZ(count);
     333        size_t agsize = P2SZ(area->pages);
     334
     335        /*
     336         * A guarded area has one guard page before, one page after.
     337         * What we do here is: if either area is guarded, we add
     338         * PAGE_SIZE to the size of both areas. That guarantees
     339         * they will be spaced at least one page apart.
     340         */
     341        if (guarded || (area->flags & AS_AREA_GUARD) != 0) {
     342                /* Add guard page size unless area is at the end of VA domain */
     343                if (!overflows(addr, P2SZ(count)))
     344                        gsize += PAGE_SIZE;
     345
     346                /* Add guard page size unless area is at the end of VA domain */
     347                if (!overflows(area->base, P2SZ(area->pages)))
     348                        agsize += PAGE_SIZE;
     349        }
     350
     351        return overlaps(addr, gsize, area->base, agsize);
     352
     353}
     354
    285355/** Check area conflicts with other areas.
    286356 *
     
    289359 * @param count   Number of pages in the area being tested.
    290360 * @param guarded True if the area being tested is protected by guard pages.
    291  * @param avoid   Do not touch this area.
     361 * @param avoid   Do not touch this area. I.e. this area is not considered
     362 *                as presenting a conflict.
    292363 *
    293364 * @return True if there is no conflict, false otherwise.
     
    314385
    315386        /*
    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];
     387         * To determine if we overlap with another area, we just need
     388         * to look at overlap with the last area with base address <=
     389         * to ours and on the first area with base address > than ours.
     390         *
     391         * First find last area with <= base address.
     392         */
     393        odlink_t *odlink = odict_find_leq(&as->as_areas, &addr, NULL);
     394        if (odlink != NULL) {
     395                as_area_t *area = odict_get_instance(odlink, as_area_t,
     396                    las_areas);
    335397
    336398                if (area != avoid) {
    337399                        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))) {
     400                        if (area_is_conflicting(addr, count, guarded, area)) {
    356401                                mutex_unlock(&area->lock);
    357402                                return false;
     
    360405                        mutex_unlock(&area->lock);
    361406                }
    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];
     407
     408                /* Next area */
     409                odlink = odict_next(odlink, &as->as_areas);
     410        }
     411
     412        /*
     413         * Next area, if any, is the first with base > than our base address.
     414         * If there was no area with <= base, we need to look at the first area.
     415         */
     416        if (odlink == NULL)
     417                odlink = odict_first(&as->as_areas);
     418
     419        if (odlink != NULL) {
     420                as_area_t *area = odict_get_instance(odlink, as_area_t,
     421                    las_areas);
    367422
    368423                if (area != avoid) {
    369                         int gp;
    370 
    371424                        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))) {
     425                        if (area_is_conflicting(addr, count, guarded, area)) {
    386426                                mutex_unlock(&area->lock);
    387427                                return false;
     
    390430                        mutex_unlock(&area->lock);
    391431                }
    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);
    424432        }
    425433
     
    488496
    489497        /* 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                 }
     498        as_area_t *area = as_area_first(as);
     499        while (area != NULL) {
     500                mutex_lock(&area->lock);
     501
     502                addr = area->base + P2SZ(area->pages);
     503
     504                if (guarded || area->flags & AS_AREA_GUARD) {
     505                        /*
     506                         * We must leave an unmapped page
     507                         * between the two areas.
     508                         */
     509                        addr += P2SZ(1);
     510                }
     511
     512                bool avail =
     513                    ((addr >= bound) && (addr >= area->base) &&
     514                    (check_area_conflicts(as, addr, pages, guarded, area)));
     515
     516                mutex_unlock(&area->lock);
     517
     518                if (avail)
     519                        return addr;
     520
     521                area = as_area_next(area);
    517522        }
    518523
     
    629634
    630635        area->as = as;
     636        odlink_initialize(&area->las_areas);
    631637        area->flags = flags;
    632638        area->attributes = attrs;
     
    686692
    687693        btree_create(&area->used_space);
    688         btree_insert(&as->as_area_btree, *base, (void *) area,
    689             NULL);
     694        odict_insert(&area->las_areas, &as->as_areas, NULL);
    690695
    691696        mutex_unlock(&as->lock);
     
    707712        assert(mutex_locked(&as->lock));
    708713
    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);
     714        odlink_t *odlink = odict_find_leq(&as->as_areas, &va, NULL);
     715        if (odlink == NULL)
     716                return NULL;
     717
     718        as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);
     719        mutex_lock(&area->lock);
     720
     721        assert(area->base <= va);
     722
     723        if (va <= area->base + (P2SZ(area->pages) - 1))
    715724                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 
     725
     726        mutex_unlock(&area->lock);
    756727        return NULL;
    757728}
     
    991962                area->backend->destroy(area);
    992963
    993         uintptr_t base = area->base;
    994 
    995964        page_table_lock(as, false);
    996965
     
    10591028         * Remove the empty area from address space.
    10601029         */
    1061         btree_remove(&as->as_area_btree, base, NULL);
     1030        odict_remove(&area->las_areas);
    10621031
    10631032        free(area);
     
    16141583
    16151584        return area_flags_to_page_flags(area->flags);
     1585}
     1586
     1587/** Get key function for the @c as_t.as_areas ordered dictionary.
     1588 *
     1589 * @param odlink Link
     1590 * @return Pointer to task ID cast as 'void *'
     1591 */
     1592static void *as_areas_getkey(odlink_t *odlink)
     1593{
     1594        as_area_t *area = odict_get_instance(odlink, as_area_t, las_areas);
     1595        return (void *) &area->base;
     1596}
     1597
     1598/** Key comparison function for the @c as_t.as_areas ordered dictionary.
     1599 *
     1600 * @param a Pointer to area A base
     1601 * @param b Pointer to area B base
     1602 * @return -1, 0, 1 iff base of A is lower than, equal to, higher than B
     1603 */
     1604static int as_areas_cmp(void *a, void *b)
     1605{
     1606        uintptr_t base_a = *(uintptr_t *)a;
     1607        uintptr_t base_b = *(uintptr_t *)b;
     1608
     1609        if (base_a < base_b)
     1610                return -1;
     1611        else if (base_a == base_b)
     1612                return 0;
     1613        else
     1614                return +1;
    16161615}
    16171616
     
    22482247        mutex_lock(&as->lock);
    22492248
    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         }
     2249        /* Count number of areas. */
     2250        size_t area_cnt = odict_count(&as->as_areas);
    22582251
    22592252        size_t isize = area_cnt * sizeof(as_area_info_t);
    22602253        as_area_info_t *info = nfmalloc(isize);
    22612254
    2262         /* Second pass, record data. */
     2255        /* Record area data. */
    22632256
    22642257        size_t area_idx = 0;
    22652258
    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                 }
     2259        as_area_t *area = as_area_first(as);
     2260        while (area != NULL) {
     2261                assert(area_idx < area_cnt);
     2262                mutex_lock(&area->lock);
     2263
     2264                info[area_idx].start_addr = area->base;
     2265                info[area_idx].size = P2SZ(area->pages);
     2266                info[area_idx].flags = area->flags;
     2267                ++area_idx;
     2268
     2269                mutex_unlock(&area->lock);
     2270                area = as_area_next(area);
    22832271        }
    22842272
     
    22992287
    23002288        /* 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                 }
     2289        as_area_t *area = as_area_first(as);
     2290        while (area != NULL) {
     2291                mutex_lock(&area->lock);
     2292                printf("as_area: %p, base=%p, pages=%zu"
     2293                    " (%p - %p)\n", area, (void *) area->base,
     2294                    area->pages, (void *) area->base,
     2295                    (void *) (area->base + P2SZ(area->pages)));
     2296                mutex_unlock(&area->lock);
     2297
     2298                area = as_area_next(area);
    23152299        }
    23162300
  • kernel/generic/src/proc/task.c

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