Changeset de0af3a in mainline


Ignore:
Timestamp:
2018-12-03T18:29:53Z (6 years ago)
Author:
jxsvoboda <5887334+jxsvoboda@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
0777a933, 7be8d4d
Parents:
a0765f6
git-author:
Jiri Svoboda <jiri@…> (2018-12-03 16:53:27)
git-committer:
jxsvoboda <5887334+jxsvoboda@…> (2018-12-03 18:29:53)
Message:

Use ordered dictionary for pagemap instead of B+tree

At the same time we add a little bit more abstraction around the pagemap.

Location:
kernel/generic
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/include/mm/as.h

    ra0765f6 rde0af3a  
    137137} as_operations_t;
    138138
     139/** Single anonymous page mapping. */
     140typedef struct {
     141        /** Containing pagemap structure */
     142        struct as_pagemap *pagemap;
     143        /** Link to @c shinfo->pagemap ordered dictionary */
     144        odlink_t lpagemap;
     145        /** Virtual address */
     146        uintptr_t vaddr;
     147        /** Physical frame address */
     148        uintptr_t frame;
     149} as_page_mapping_t;
     150
     151/** Map of anonymous pages in a shared area. */
     152typedef struct as_pagemap {
     153        /**
     154         * Dictionary ordered by virtual address. Members are of type
     155         * as_page_mapping_t
     156         */
     157        odict_t map;
     158} as_pagemap_t;
     159
    139160/**
    140161 * This structure contains information associated with the shared address space
    … …  
    150171        bool shared;
    151172
    152         /**
    153          * B+tree containing complete map of anonymous pages of the shared area.
    154          */
    155         btree_t pagemap;
     173        /** Complete map of anonymous pages of the shared area. */
     174        as_pagemap_t pagemap;
    156175
    157176        /** Address space area backend. */
    … …  
    283302extern as_area_t *as_area_next(as_area_t *);
    284303
     304extern void as_pagemap_initialize(as_pagemap_t *);
     305extern void as_pagemap_finalize(as_pagemap_t *);
     306extern as_page_mapping_t *as_pagemap_first(as_pagemap_t *);
     307extern as_page_mapping_t *as_pagemap_next(as_page_mapping_t *);
     308extern errno_t as_pagemap_find(as_pagemap_t *, uintptr_t, uintptr_t *);
     309extern void as_pagemap_insert(as_pagemap_t *, uintptr_t, uintptr_t);
     310extern void as_pagemap_remove(as_page_mapping_t *);
     311
    285312extern unsigned int as_area_get_flags(as_area_t *);
    286313extern bool as_area_check_access(as_area_t *, pf_access_t);

  • kernel/generic/src/mm/as.c

    ra0765f6 rde0af3a  
    8989as_operations_t *as_operations = NULL;
    9090
    91 /** Slab for as_t objects.
    92  *
    93  */
     91/** Cache for as_t objects */
    9492static slab_cache_t *as_cache;
     93
     94/** Cache for as_page_mapping_t objects */
     95static slab_cache_t *as_page_mapping_cache;
    9596
    9697/** ASID subsystem lock.
    … …  
    138139        as_cache = slab_cache_create("as_t", sizeof(as_t), 0,
    139140            as_constructor, as_destructor, SLAB_CACHE_MAGDEFERRED);
     141
     142        as_page_mapping_cache = slab_cache_create("as_page_mapping_t",
     143            sizeof(as_page_mapping_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
    140144
    141145        AS_KERNEL = as_create(FLAG_AS_KERNEL);
    … …  
    524528}
    525529
     530/** Get key function for pagemap ordered dictionary.
     531 *
     532 * The key is the virtual address of the page (as_page_mapping_t.vaddr)
     533 *
     534 * @param odlink Link to as_pagemap_t.map ordered dictionary
     535 * @return Pointer to virtual address cast as @c void *
     536 */
     537static void *as_pagemap_getkey(odlink_t *odlink)
     538{
     539        as_page_mapping_t *mapping;
     540
     541        mapping = odict_get_instance(odlink, as_page_mapping_t, lpagemap);
     542        return (void *) &mapping->vaddr;
     543}
     544
     545/** Comparison function for pagemap ordered dictionary.
     546 *
     547 * @param a Pointer to virtual address cast as @c void *
     548 * @param b Pointer to virtual address cast as @c void *
     549 * @return <0, =0, >0 if virtual address a is less than, equal to, or
     550 *         greater-than b, respectively.
     551 */
     552static int as_pagemap_cmp(void *a, void *b)
     553{
     554        uintptr_t va = *(uintptr_t *)a;
     555        uintptr_t vb = *(uintptr_t *)b;
     556
     557        return va - vb;
     558}
     559
     560/** Initialize pagemap.
     561 *
     562 * @param pagemap Pagemap
     563 */
     564NO_TRACE void as_pagemap_initialize(as_pagemap_t *pagemap)
     565{
     566        odict_initialize(&pagemap->map, as_pagemap_getkey, as_pagemap_cmp);
     567}
     568
     569/** Finalize pagemap.
     570 *
     571 * Destroy any entries in the pagemap.
     572 *
     573 * @param pagemap Pagemap
     574 */
     575NO_TRACE void as_pagemap_finalize(as_pagemap_t *pagemap)
     576{
     577        as_page_mapping_t *mapping = as_pagemap_first(pagemap);
     578        while (mapping != NULL) {
     579                as_pagemap_remove(mapping);
     580                mapping = as_pagemap_first(pagemap);
     581        }
     582        odict_finalize(&pagemap->map);
     583}
     584
     585/** Get first page mapping.
     586 *
     587 * @param pagemap Pagemap
     588 * @return First mapping or @c NULL if there is none
     589 */
     590NO_TRACE as_page_mapping_t *as_pagemap_first(as_pagemap_t *pagemap)
     591{
     592        odlink_t *odlink;
     593
     594        odlink = odict_first(&pagemap->map);
     595        if (odlink == NULL)
     596                return NULL;
     597
     598        return odict_get_instance(odlink, as_page_mapping_t, lpagemap);
     599}
     600
     601/** Get next page mapping.
     602 *
     603 * @param cur Current mapping
     604 * @return Next mapping or @c NULL if @a cur is the last one
     605 */
     606NO_TRACE as_page_mapping_t *as_pagemap_next(as_page_mapping_t *cur)
     607{
     608        odlink_t *odlink;
     609
     610        odlink = odict_next(&cur->lpagemap, &cur->pagemap->map);
     611        if (odlink == NULL)
     612                return NULL;
     613
     614        return odict_get_instance(odlink, as_page_mapping_t, lpagemap);
     615}
     616
     617/** Find frame by virtual address.
     618 *
     619 * @param pagemap Pagemap
     620 * @param vaddr Virtual address of page
     621 * @param rframe Place to store physical frame address
     622 * @return EOK on succcess or ENOENT if no mapping found
     623 */
     624NO_TRACE errno_t as_pagemap_find(as_pagemap_t *pagemap, uintptr_t vaddr,
     625    uintptr_t *rframe)
     626{
     627        odlink_t *odlink;
     628        as_page_mapping_t *mapping;
     629
     630        odlink = odict_find_eq(&pagemap->map, &vaddr, NULL);
     631        if (odlink == NULL)
     632                return ENOENT;
     633
     634        mapping = odict_get_instance(odlink, as_page_mapping_t, lpagemap);
     635        *rframe = mapping->frame;
     636        return EOK;
     637}
     638
     639/** Insert new page mapping.
     640 *
     641 * This function can block to allocate kernel memory.
     642 *
     643 * @param pagemap Pagemap
     644 * @param vaddr Virtual page address
     645 * @param frame Physical frame address
     646 */
     647NO_TRACE void as_pagemap_insert(as_pagemap_t *pagemap, uintptr_t vaddr,
     648    uintptr_t frame)
     649{
     650        as_page_mapping_t *mapping;
     651
     652        mapping = slab_alloc(as_page_mapping_cache, 0);
     653        mapping->pagemap = pagemap;
     654        odlink_initialize(&mapping->lpagemap);
     655        mapping->vaddr = vaddr;
     656        mapping->frame = frame;
     657        odict_insert(&mapping->lpagemap, &pagemap->map, NULL);
     658}
     659
     660/** Remove page mapping.
     661 *
     662 * @param mapping Mapping
     663 */
     664NO_TRACE void as_pagemap_remove(as_page_mapping_t *mapping)
     665{
     666        odict_remove(&mapping->lpagemap);
     667        slab_free(as_page_mapping_cache, mapping);
     668}
     669
    526670/** Remove reference to address space area share info.
    527671 *
    … …  
    545689                 * reference from all frames found there.
    546690                 */
    547                 list_foreach(sh_info->pagemap.leaf_list, leaf_link,
    548                     btree_node_t, node) {
    549                         btree_key_t i;
    550 
    551                         for (i = 0; i < node->keys; i++)
    552                                 frame_free((uintptr_t) node->value[i], 1);
     691                as_page_mapping_t *mapping = as_pagemap_first(&sh_info->pagemap);
     692                while (mapping != NULL) {
     693                        frame_free(mapping->frame, 1);
     694                        mapping = as_pagemap_next(mapping);
    553695                }
    554696
    … …  
    561703                            sh_info->backend_shared_data);
    562704                }
    563                 btree_destroy(&sh_info->pagemap);
     705                as_pagemap_finalize(&sh_info->pagemap);
    564706                free(sh_info);
    565707        }
    … …  
    665807                si->backend_shared_data = NULL;
    666808                si->backend = backend;
    667                 btree_create(&si->pagemap);
     809                as_pagemap_initialize(&si->pagemap);
    668810
    669811                area->sh_info = si;

  • kernel/generic/src/mm/backend_anon.c

    ra0765f6 rde0af3a  
    144144                                assert(PTE_PRESENT(&pte));
    145145
    146                                 btree_insert(&area->sh_info->pagemap,
     146                                as_pagemap_insert(&area->sh_info->pagemap,
    147147                                    (base + P2SZ(j)) - area->base,
    148                                     (void *) PTE_GET_FRAME(&pte), NULL);
     148                                    PTE_GET_FRAME(&pte));
    149149                                page_table_unlock(area->as, false);
    150150
    … …  
    201201        mutex_lock(&area->sh_info->lock);
    202202        if (area->sh_info->shared) {
    203                 btree_node_t *leaf;
    204 
    205203                /*
    206204                 * The area is shared, chances are that the mapping can be found
    … …  
    210208                 * mapping, a new frame is allocated and the mapping is created.
    211209                 */
    212                 frame = (uintptr_t) btree_search(&area->sh_info->pagemap,
    213                     upage - area->base, &leaf);
    214                 if (!frame) {
    215                         bool allocate = true;
    216                         unsigned int i;
     210                errno_t rc = as_pagemap_find(&area->sh_info->pagemap,
     211                    upage - area->base, &frame);
     212                if (rc != EOK) {
     213                        /* Need to allocate the frame */
     214                        kpage = km_temporary_page_get(&frame,
     215                            FRAME_NO_RESERVE);
     216                        memsetb((void *) kpage, PAGE_SIZE, 0);
     217                        km_temporary_page_put(kpage);
    217218
    218219                        /*
    219                          * Zero can be returned as a valid frame address.
    220                          * Just a small workaround.
     220                         * Insert the address of the newly allocated
     221                         * frame to the pagemap.
    221222                         */
    222                         for (i = 0; i < leaf->keys; i++) {
    223                                 if (leaf->key[i] == upage - area->base) {
    224                                         allocate = false;
    225                                         break;
    226                                 }
    227                         }
    228                         if (allocate) {
    229                                 kpage = km_temporary_page_get(&frame,
    230                                     FRAME_NO_RESERVE);
    231                                 memsetb((void *) kpage, PAGE_SIZE, 0);
    232                                 km_temporary_page_put(kpage);
    233 
    234                                 /*
    235                                  * Insert the address of the newly allocated
    236                                  * frame to the pagemap.
    237                                  */
    238                                 btree_insert(&area->sh_info->pagemap,
    239                                     upage - area->base, (void *) frame, leaf);
    240                         }
     223                        as_pagemap_insert(&area->sh_info->pagemap,
     224                            upage - area->base, frame);
    241225                }
    242226                frame_reference_add(ADDR2PFN(frame));

  • kernel/generic/src/mm/backend_elf.c

    ra0765f6 rde0af3a  
    219219                                assert(PTE_PRESENT(&pte));
    220220
    221                                 btree_insert(&area->sh_info->pagemap,
     221                                as_pagemap_insert(&area->sh_info->pagemap,
    222222                                    (base + P2SZ(j)) - area->base,
    223                                     (void *) PTE_GET_FRAME(&pte), NULL);
     223                                    PTE_GET_FRAME(&pte));
    224224                                page_table_unlock(area->as, false);
    225225
    … …  
    267267        elf_header_t *elf = area->backend_data.elf;
    268268        elf_segment_header_t *entry = area->backend_data.segment;
    269         btree_node_t *leaf;
    270269        uintptr_t base;
    271270        uintptr_t frame;
    … …  
    301300        mutex_lock(&area->sh_info->lock);
    302301        if (area->sh_info->shared) {
    303                 bool found = false;
    304 
    305302                /*
    306303                 * The address space area is shared.
    307304                 */
    308305
    309                 frame = (uintptr_t) btree_search(&area->sh_info->pagemap,
    310                     upage - area->base, &leaf);
    311                 if (!frame) {
    312                         unsigned int i;
    313 
    314                         /*
    315                          * Workaround for valid NULL address.
    316                          */
    317 
    318                         for (i = 0; i < leaf->keys; i++) {
    319                                 if (leaf->key[i] == upage - area->base) {
    320                                         found = true;
    321                                         break;
    322                                 }
    323                         }
    324                 }
    325                 if (frame || found) {
     306                errno_t rc = as_pagemap_find(&area->sh_info->pagemap,
     307                    upage - area->base, &frame);
     308                if (rc == EOK) {
    326309                        frame_reference_add(ADDR2PFN(frame));
    327310                        page_mapping_insert(AS, upage, frame,
    … …  
    415398        if (dirty && area->sh_info->shared) {
    416399                frame_reference_add(ADDR2PFN(frame));
    417                 btree_insert(&area->sh_info->pagemap, upage - area->base,
    418                     (void *) frame, leaf);
     400                as_pagemap_insert(&area->sh_info->pagemap, upage - area->base,
     401                    frame);
    419402        }
    420403
Note: See TracChangeset for help on using the changeset viewer.