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

Changeset 7be8d4d in mainline


Ignore:
Timestamp:
2018-12-08T23:32:55Z (19 months ago)
Author:
Jiri Svoboda <jiri@…>
Children:
dd74b5b
Parents:
de0af3a
git-author:
Jiri Svoboda <jiri@…> (2018-12-05 18:39:06)
git-committer:
Jiri Svoboda <jiri@…> (2018-12-08 23:32:55)
Message:

Replace B+tree with ordered dict. for used space

Replace the use of B+tree with ordered dictionary for used space,
adding a little bit more abstraction around used space tracking.
This allows performing TLB shootdown while shrinking an area
in a single sequence. A generic used_space_remove() is no longer
needed.

Location:
kernel/generic
Files:
7 edited

Legend:

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

    rde0af3a r7be8d4d  
    4545#include <synch/mutex.h>
    4646#include <adt/list.h>
    47 #include <adt/btree.h>
    4847#include <adt/odict.h>
    4948#include <lib/elf.h>
     
    158157} as_pagemap_t;
    159158
     159/** Used space interval */
     160typedef struct {
     161        /** Containing used_space structure */
     162        struct used_space *used_space;
     163        /** Link to @c used_space->ivals */
     164        odlink_t lused_space;
     165        /** First page address */
     166        uintptr_t page;
     167        /** Count of pages */
     168        size_t count;
     169} used_space_ival_t;
     170
     171/** Map of used space in an address space area */
     172typedef struct used_space {
     173        /**
     174         * Dictionary of intervals by start address.
     175         * Members are of type @c used_space_ival_t.
     176         */
     177        odict_t ivals;
     178        /** Total number of used pages. */
     179        size_t pages;
     180} used_space_t;
     181
    160182/**
    161183 * This structure contains information associated with the shared address space
     
    240262        size_t pages;
    241263
    242         /** Number of resident pages in the area. */
    243         size_t resident;
    244 
    245264        /** Base address of this area. */
    246265        uintptr_t base;
    247266
    248267        /** Map of used space. */
    249         btree_t used_space;
     268        used_space_t used_space;
    250269
    251270        /**
     
    313332extern bool as_area_check_access(as_area_t *, pf_access_t);
    314333extern size_t as_area_get_size(uintptr_t);
    315 extern bool used_space_insert(as_area_t *, uintptr_t, size_t);
    316 extern bool used_space_remove(as_area_t *, uintptr_t, size_t);
     334extern used_space_ival_t *used_space_first(used_space_t *);
     335extern used_space_ival_t *used_space_next(used_space_ival_t *);
     336extern used_space_ival_t *used_space_find_gteq(used_space_t *, uintptr_t);
     337extern bool used_space_insert(used_space_t *, uintptr_t, size_t);
    317338
    318339/* Interface to be implemented by architectures. */
  • kernel/generic/src/mm/as.c

    rde0af3a r7be8d4d  
    6363#include <synch/mutex.h>
    6464#include <adt/list.h>
    65 #include <adt/btree.h>
    6665#include <proc/task.h>
    6766#include <proc/thread.h>
     
    9594static slab_cache_t *as_page_mapping_cache;
    9695
     96/** Cache for used_space_ival_t objects */
     97static slab_cache_t *used_space_ival_cache;
     98
    9799/** ASID subsystem lock.
    98100 *
     
    117119static int as_areas_cmp(void *, void *);
    118120
     121static void used_space_initialize(used_space_t *);
     122static void used_space_finalize(used_space_t *);
     123static void *used_space_getkey(odlink_t *);
     124static int used_space_cmp(void *, void *);
     125static used_space_ival_t *used_space_last(used_space_t *);
     126static void used_space_remove_ival(used_space_ival_t *);
     127static void used_space_shorten_ival(used_space_ival_t *, size_t);
     128
    119129NO_TRACE static errno_t as_constructor(void *obj, unsigned int flags)
    120130{
     
    142152        as_page_mapping_cache = slab_cache_create("as_page_mapping_t",
    143153            sizeof(as_page_mapping_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
     154
     155        used_space_ival_cache = slab_cache_create("used_space_ival_t",
     156            sizeof(used_space_ival_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
    144157
    145158        AS_KERNEL = as_create(FLAG_AS_KERNEL);
     
    548561 * @param b Pointer to virtual address cast as @c void *
    549562 * @return <0, =0, >0 if virtual address a is less than, equal to, or
    550  *         greater-than b, respectively.
     563 *         greater than b, respectively.
    551564 */
    552565static int as_pagemap_cmp(void *a, void *b)
     
    778791        area->attributes = attrs;
    779792        area->pages = pages;
    780         area->resident = 0;
    781793        area->base = *base;
    782794        area->backend = backend;
     
    831843        }
    832844
    833         btree_create(&area->used_space);
     845        used_space_initialize(&area->used_space);
    834846        odict_insert(&area->las_areas, &as->as_areas, NULL);
    835847
     
    939951
    940952                /*
     953                 * Start TLB shootdown sequence.
     954                 */
     955
     956                ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES,
     957                    as->asid, area->base + P2SZ(pages),
     958                    area->pages - pages);
     959
     960                /*
    941961                 * Remove frames belonging to used space starting from
    942962                 * the highest addresses downwards until an overlap with
    943                  * the resized address space area is found. Note that this
    944                  * is also the right way to remove part of the used_space
    945                  * B+tree leaf list.
     963                 * the resized address space area is found.
    946964                 */
    947965                bool cond = true;
    948966                while (cond) {
    949                         assert(!list_empty(&area->used_space.leaf_list));
    950 
    951                         btree_node_t *node =
    952                             list_get_instance(list_last(&area->used_space.leaf_list),
    953                             btree_node_t, leaf_link);
    954 
    955                         if ((cond = (node->keys != 0))) {
    956                                 uintptr_t ptr = node->key[node->keys - 1];
    957                                 size_t node_size =
    958                                     (size_t) node->value[node->keys - 1];
    959                                 size_t i = 0;
    960 
    961                                 if (overlaps(ptr, P2SZ(node_size), area->base,
    962                                     P2SZ(pages))) {
    963 
    964                                         if (ptr + P2SZ(node_size) <= start_free) {
    965                                                 /*
    966                                                  * The whole interval fits
    967                                                  * completely in the resized
    968                                                  * address space area.
    969                                                  */
    970                                                 break;
    971                                         }
    972 
     967                        used_space_ival_t *ival =
     968                            used_space_last(&area->used_space);
     969                        assert(ival != NULL);
     970
     971                        uintptr_t ptr = ival->page;
     972                        size_t pcount = ival->count;
     973                        size_t i = 0;
     974
     975                        if (overlaps(ptr, P2SZ(pcount), area->base,
     976                            P2SZ(pages))) {
     977
     978                                if (ptr + P2SZ(pcount) <= start_free) {
    973979                                        /*
    974                                          * Part of the interval corresponding
    975                                          * to b and c overlaps with the resized
    976                                          * address space area.
     980                                         * The whole interval fits completely
     981                                         * in the resized address space area.
    977982                                         */
    978 
    979                                         /* We are almost done */
    980                                         cond = false;
    981                                         i = (start_free - ptr) >> PAGE_WIDTH;
    982                                         if (!used_space_remove(area, start_free,
    983                                             node_size - i))
    984                                                 panic("Cannot remove used space.");
    985                                 } else {
    986                                         /*
    987                                          * The interval of used space can be
    988                                          * completely removed.
    989                                          */
    990                                         if (!used_space_remove(area, ptr, node_size))
    991                                                 panic("Cannot remove used space.");
     983                                        break;
    992984                                }
    993985
    994986                                /*
    995                                  * Start TLB shootdown sequence.
    996                                  *
    997                                  * The sequence is rather short and can be
    998                                  * repeated multiple times. The reason is that
    999                                  * we don't want to have used_space_remove()
    1000                                  * inside the sequence as it may use a blocking
    1001                                  * memory allocation for its B+tree. Blocking
    1002                                  * while holding the tlblock spinlock is
    1003                                  * forbidden and would hit a kernel assertion.
     987                                 * Part of the interval corresponding to b and
     988                                 * c overlaps with the resized address space
     989                                 * area.
    1004990                                 */
    1005991
    1006                                 ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES,
    1007                                     as->asid, area->base + P2SZ(pages),
    1008                                     area->pages - pages);
    1009 
    1010                                 for (; i < node_size; i++) {
    1011                                         pte_t pte;
    1012                                         bool found = page_mapping_find(as,
    1013                                             ptr + P2SZ(i), false, &pte);
    1014 
    1015                                         (void) found;
    1016                                         assert(found);
    1017                                         assert(PTE_VALID(&pte));
    1018                                         assert(PTE_PRESENT(&pte));
    1019 
    1020                                         if ((area->backend) &&
    1021                                             (area->backend->frame_free)) {
    1022                                                 area->backend->frame_free(area,
    1023                                                     ptr + P2SZ(i),
    1024                                                     PTE_GET_FRAME(&pte));
    1025                                         }
    1026 
    1027                                         page_mapping_remove(as, ptr + P2SZ(i));
     992                                /* We are almost done */
     993                                cond = false;
     994                                i = (start_free - ptr) >> PAGE_WIDTH;
     995
     996                                /* Shorten the interval to @c i pages */
     997                                used_space_shorten_ival(ival, i);
     998                        } else {
     999                                /*
     1000                                 * The interval of used space can be completely
     1001                                 * removed.
     1002                                 */
     1003                                used_space_remove_ival(ival);
     1004                        }
     1005
     1006                        for (; i < pcount; i++) {
     1007                                pte_t pte;
     1008                                bool found = page_mapping_find(as,
     1009                                    ptr + P2SZ(i), false, &pte);
     1010
     1011                                (void) found;
     1012                                assert(found);
     1013                                assert(PTE_VALID(&pte));
     1014                                assert(PTE_PRESENT(&pte));
     1015
     1016                                if ((area->backend) &&
     1017                                    (area->backend->frame_free)) {
     1018                                        area->backend->frame_free(area,
     1019                                            ptr + P2SZ(i),
     1020                                            PTE_GET_FRAME(&pte));
    10281021                                }
    10291022
    1030                                 /*
    1031                                  * Finish TLB shootdown sequence.
    1032                                  */
    1033 
    1034                                 tlb_invalidate_pages(as->asid,
    1035                                     area->base + P2SZ(pages),
    1036                                     area->pages - pages);
    1037 
    1038                                 /*
    1039                                  * Invalidate software translation caches
    1040                                  * (e.g. TSB on sparc64, PHT on ppc32).
    1041                                  */
    1042                                 as_invalidate_translation_cache(as,
    1043                                     area->base + P2SZ(pages),
    1044                                     area->pages - pages);
    1045                                 tlb_shootdown_finalize(ipl);
     1023                                page_mapping_remove(as, ptr + P2SZ(i));
    10461024                        }
     1025
    10471026                }
     1027
     1028                /*
     1029                 * Finish TLB shootdown sequence.
     1030                 */
     1031
     1032                tlb_invalidate_pages(as->asid,
     1033                    area->base + P2SZ(pages),
     1034                    area->pages - pages);
     1035
     1036                /*
     1037                 * Invalidate software translation caches
     1038                 * (e.g. TSB on sparc64, PHT on ppc32).
     1039                 */
     1040                as_invalidate_translation_cache(as,
     1041                    area->base + P2SZ(pages),
     1042                    area->pages - pages);
     1043                tlb_shootdown_finalize(ipl);
     1044
    10481045                page_table_unlock(as, false);
    10491046        } else {
     
    11041101
    11051102        page_table_lock(as, false);
    1106 
    11071103        /*
    11081104         * Start TLB shootdown sequence.
     
    11121108
    11131109        /*
    1114          * Visit only the pages mapped by used_space B+tree.
    1115          */
    1116         list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t,
    1117             node) {
    1118                 btree_key_t i;
    1119 
    1120                 for (i = 0; i < node->keys; i++) {
    1121                         uintptr_t ptr = node->key[i];
    1122                         size_t size;
    1123 
    1124                         for (size = 0; size < (size_t) node->value[i]; size++) {
    1125                                 pte_t pte;
    1126                                 bool found = page_mapping_find(as,
    1127                                     ptr + P2SZ(size), false, &pte);
    1128 
    1129                                 (void) found;
    1130                                 assert(found);
    1131                                 assert(PTE_VALID(&pte));
    1132                                 assert(PTE_PRESENT(&pte));
    1133 
    1134                                 if ((area->backend) &&
    1135                                     (area->backend->frame_free)) {
    1136                                         area->backend->frame_free(area,
    1137                                             ptr + P2SZ(size),
    1138                                             PTE_GET_FRAME(&pte));
    1139                                 }
    1140 
    1141                                 page_mapping_remove(as, ptr + P2SZ(size));
     1110         * Visit only the pages mapped by used_space.
     1111         */
     1112        used_space_ival_t *ival = used_space_first(&area->used_space);
     1113        while (ival != NULL) {
     1114                uintptr_t ptr = ival->page;
     1115
     1116                for (size_t size = 0; size < ival->count; size++) {
     1117                        pte_t pte;
     1118                        bool found = page_mapping_find(as,
     1119                            ptr + P2SZ(size), false, &pte);
     1120
     1121                        (void) found;
     1122                        assert(found);
     1123                        assert(PTE_VALID(&pte));
     1124                        assert(PTE_PRESENT(&pte));
     1125
     1126                        if ((area->backend) &&
     1127                            (area->backend->frame_free)) {
     1128                                area->backend->frame_free(area,
     1129                                    ptr + P2SZ(size),
     1130                                    PTE_GET_FRAME(&pte));
    11421131                        }
     1132
     1133                        page_mapping_remove(as, ptr + P2SZ(size));
    11431134                }
     1135
     1136                used_space_remove_ival(ival);
     1137                ival = used_space_first(&area->used_space);
    11441138        }
    11451139
     
    11591153        page_table_unlock(as, false);
    11601154
    1161         btree_destroy(&area->used_space);
    1162 
     1155        used_space_finalize(&area->used_space);
    11631156        area->attributes |= AS_AREA_ATTR_PARTIAL;
    1164 
    11651157        sh_info_remove_reference(area->sh_info);
    11661158
     
    13991391
    14001392        /*
    1401          * Compute total number of used pages in the used_space B+tree
     1393         * Compute total number of used pages
    14021394         */
    14031395        size_t used_pages = 0;
    14041396
    1405         list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t,
    1406             node) {
    1407                 btree_key_t i;
    1408 
    1409                 for (i = 0; i < node->keys; i++)
    1410                         used_pages += (size_t) node->value[i];
     1397        used_space_ival_t *ival = used_space_first(&area->used_space);
     1398        while (ival != NULL) {
     1399                used_pages += ival->count;
     1400                ival = used_space_next(ival);
    14111401        }
    14121402
     
    14331423        size_t frame_idx = 0;
    14341424
    1435         list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t,
    1436             node) {
    1437                 btree_key_t i;
    1438 
    1439                 for (i = 0; i < node->keys; i++) {
    1440                         uintptr_t ptr = node->key[i];
    1441                         size_t size;
    1442 
    1443                         for (size = 0; size < (size_t) node->value[i]; size++) {
    1444                                 pte_t pte;
    1445                                 bool found = page_mapping_find(as,
    1446                                     ptr + P2SZ(size), false, &pte);
    1447 
    1448                                 (void) found;
    1449                                 assert(found);
    1450                                 assert(PTE_VALID(&pte));
    1451                                 assert(PTE_PRESENT(&pte));
    1452 
    1453                                 old_frame[frame_idx++] = PTE_GET_FRAME(&pte);
    1454 
    1455                                 /* Remove old mapping */
    1456                                 page_mapping_remove(as, ptr + P2SZ(size));
    1457                         }
     1425        ival = used_space_first(&area->used_space);
     1426        while (ival != NULL) {
     1427                uintptr_t ptr = ival->page;
     1428                size_t size;
     1429
     1430                for (size = 0; size < ival->count; size++) {
     1431                        pte_t pte;
     1432                        bool found = page_mapping_find(as, ptr + P2SZ(size),
     1433                            false, &pte);
     1434
     1435                        (void) found;
     1436                        assert(found);
     1437                        assert(PTE_VALID(&pte));
     1438                        assert(PTE_PRESENT(&pte));
     1439
     1440                        old_frame[frame_idx++] = PTE_GET_FRAME(&pte);
     1441
     1442                        /* Remove old mapping */
     1443                        page_mapping_remove(as, ptr + P2SZ(size));
    14581444                }
     1445
     1446                ival = used_space_next(ival);
    14591447        }
    14601448
     
    14861474        frame_idx = 0;
    14871475
    1488         list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t,
    1489             node) {
    1490                 btree_key_t i;
    1491 
    1492                 for (i = 0; i < node->keys; i++) {
    1493                         uintptr_t ptr = node->key[i];
    1494                         size_t size;
    1495 
    1496                         for (size = 0; size < (size_t) node->value[i]; size++) {
    1497                                 page_table_lock(as, false);
    1498 
    1499                                 /* Insert the new mapping */
    1500                                 page_mapping_insert(as, ptr + P2SZ(size),
    1501                                     old_frame[frame_idx++], page_flags);
    1502 
    1503                                 page_table_unlock(as, false);
    1504                         }
     1476        ival = used_space_first(&area->used_space);
     1477        while (ival != NULL) {
     1478                uintptr_t ptr = ival->page;
     1479                size_t size;
     1480
     1481                for (size = 0; size < ival->count; size++) {
     1482                        page_table_lock(as, false);
     1483
     1484                        /* Insert the new mapping */
     1485                        page_mapping_insert(as, ptr + P2SZ(size),
     1486                            old_frame[frame_idx++], page_flags);
     1487
     1488                        page_table_unlock(as, false);
    15051489                }
     1490
     1491                ival = used_space_next(ival);
    15061492        }
    15071493
     
    18671853}
    18681854
     1855/** Initialize used space map.
     1856 *
     1857 * @param used_space Used space map
     1858 */
     1859static void used_space_initialize(used_space_t *used_space)
     1860{
     1861        odict_initialize(&used_space->ivals, used_space_getkey, used_space_cmp);
     1862        used_space->pages = 0;
     1863}
     1864
     1865/** Finalize used space map.
     1866 *
     1867 * @param used_space Used space map
     1868 */
     1869static void used_space_finalize(used_space_t *used_space)
     1870{
     1871        assert(odict_empty(&used_space->ivals));
     1872        odict_finalize(&used_space->ivals);
     1873}
     1874
     1875/** Get first interval of used space.
     1876 *
     1877 * @param used_space Used space map
     1878 * @return First interval or @c NULL if there are none
     1879 */
     1880used_space_ival_t *used_space_first(used_space_t *used_space)
     1881{
     1882        odlink_t *odlink = odict_first(&used_space->ivals);
     1883
     1884        if (odlink == NULL)
     1885                return NULL;
     1886
     1887        return odict_get_instance(odlink, used_space_ival_t, lused_space);
     1888}
     1889
     1890/** Get next interval of used space.
     1891 *
     1892 * @param cur Current interval
     1893 * @return Next interval or @c NULL if there are none
     1894 */
     1895used_space_ival_t *used_space_next(used_space_ival_t *cur)
     1896{
     1897        odlink_t *odlink = odict_next(&cur->lused_space,
     1898            &cur->used_space->ivals);
     1899
     1900        if (odlink == NULL)
     1901                return NULL;
     1902
     1903        return odict_get_instance(odlink, used_space_ival_t, lused_space);
     1904}
     1905
     1906/** Get last interval of used space.
     1907 *
     1908 * @param used_space Used space map
     1909 * @return First interval or @c NULL if there are none
     1910 */
     1911static used_space_ival_t *used_space_last(used_space_t *used_space)
     1912{
     1913        odlink_t *odlink = odict_last(&used_space->ivals);
     1914
     1915        if (odlink == NULL)
     1916                return NULL;
     1917
     1918        return odict_get_instance(odlink, used_space_ival_t, lused_space);
     1919}
     1920
     1921/** Find the first interval that contains addresses greater than or equal to
     1922 * @a ptr.
     1923 *
     1924 * @param used_space Used space map
     1925 * @param ptr Virtual address
     1926 *
     1927 * @return Used space interval or @c NULL if none matches
     1928 */
     1929used_space_ival_t *used_space_find_gteq(used_space_t *used_space, uintptr_t ptr)
     1930{
     1931        odlink_t *odlink;
     1932        used_space_ival_t *ival;
     1933
     1934        /* Find last interval to start at address less than @a ptr */
     1935        odlink = odict_find_lt(&used_space->ivals, &ptr, NULL);
     1936        if (odlink != NULL) {
     1937                ival = odict_get_instance(odlink, used_space_ival_t,
     1938                    lused_space);
     1939
     1940                /* If the interval extends above @a ptr, return it */
     1941                if (ival->page + P2SZ(ival->count) > ptr)
     1942                        return ival;
     1943
     1944                /*
     1945                 * Otherwise, if a next interval exists, it must match
     1946                 * the criteria.
     1947                 */
     1948                odlink = odict_next(&ival->lused_space, &used_space->ivals);
     1949        } else {
     1950                /*
     1951                 * No interval with lower base address, so if there is any
     1952                 * interval at all, it must match the criteria
     1953                 */
     1954                odlink = odict_first(&used_space->ivals);
     1955        }
     1956
     1957        if (odlink != NULL) {
     1958                ival = odict_get_instance(odlink, used_space_ival_t,
     1959                    lused_space);
     1960                return ival;
     1961        }
     1962
     1963        return NULL;
     1964}
     1965
     1966/** Get key function for used space ordered dictionary.
     1967 *
     1968 * The key is the virtual address of the first page
     1969 *
     1970 * @param odlink Ordered dictionary link (used_space_ival_t.lused_space)
     1971 * @return Pointer to virtual address of first page cast as @c void *.
     1972 */
     1973static void *used_space_getkey(odlink_t *odlink)
     1974{
     1975        used_space_ival_t *ival = odict_get_instance(odlink, used_space_ival_t,
     1976            lused_space);
     1977        return (void *) &ival->page;
     1978}
     1979
     1980/** Compare function for used space ordered dictionary.
     1981 *
     1982 * @param a Pointer to virtual address of first page cast as @c void *
     1983 * @param b Pointer to virtual address of first page cast as @c void *
     1984 * @return Less than zero, zero, greater than zero if virtual address @a a
     1985 *         is less than, equal to, greater than virtual address b, respectively.
     1986 */
     1987static int used_space_cmp(void *a, void *b)
     1988{
     1989        uintptr_t va = *(uintptr_t *) a;
     1990        uintptr_t vb = *(uintptr_t *) b;
     1991
     1992        if (va < vb)
     1993                return -1;
     1994        else if (va == vb)
     1995                return 0;
     1996        else
     1997                return +1;
     1998}
     1999
     2000/** Remove used space interval.
     2001 *
     2002 * @param ival Used space interval
     2003 */
     2004static void used_space_remove_ival(used_space_ival_t *ival)
     2005{
     2006        ival->used_space->pages -= ival->count;
     2007        odict_remove(&ival->lused_space);
     2008        slab_free(used_space_ival_cache, ival);
     2009}
     2010
     2011/** Shorten used space interval.
     2012 *
     2013 * @param ival Used space interval
     2014 * @param count New number of pages in the interval
     2015 */
     2016static void used_space_shorten_ival(used_space_ival_t *ival, size_t count)
     2017{
     2018        assert(count > 0);
     2019        assert(count < ival->count);
     2020
     2021        ival->used_space->pages -= ival->count - count;
     2022        ival->count = count;
     2023}
     2024
    18692025/** Mark portion of address space area as used.
    18702026 *
    18712027 * The address space area must be already locked.
    18722028 *
    1873  * @param area  Address space area.
    1874  * @param page  First page to be marked.
     2029 * @param used_space Used space map
     2030 * @param page First page to be marked.
    18752031 * @param count Number of page to be marked.
    18762032 *
     
    18782034 *
    18792035 */
    1880 bool used_space_insert(as_area_t *area, uintptr_t page, size_t count)
    1881 {
    1882         assert(mutex_locked(&area->lock));
     2036bool used_space_insert(used_space_t *used_space, uintptr_t page, size_t count)
     2037{
     2038        used_space_ival_t *a;
     2039        used_space_ival_t *b;
     2040        bool adj_a;
     2041        bool adj_b;
     2042        odlink_t *odlink;
     2043        used_space_ival_t *ival;
     2044
    18832045        assert(IS_ALIGNED(page, PAGE_SIZE));
    18842046        assert(count);
    18852047
    1886         btree_node_t *leaf = NULL;
    1887         size_t pages = (size_t) btree_search(&area->used_space, page, &leaf);
    1888         if (pages) {
    1889                 /*
    1890                  * We hit the beginning of some used space.
    1891                  */
     2048        /* Interval to the left */
     2049        odlink = odict_find_lt(&used_space->ivals, &page, NULL);
     2050        a = (odlink != NULL) ?
     2051            odict_get_instance(odlink, used_space_ival_t, lused_space) :
     2052            NULL;
     2053
     2054        /* Interval to the right */
     2055        b = (a != NULL) ? used_space_next(a) :
     2056            used_space_first(used_space);
     2057
     2058        /* Check for conflict with left interval */
     2059        if (a != NULL && overlaps(a->page, P2SZ(a->count), page, P2SZ(count)))
    18922060                return false;
    1893         }
    1894 
    1895         assert(leaf != NULL);
    1896 
    1897         if (!leaf->keys) {
    1898                 btree_insert(&area->used_space, page, (void *) count, leaf);
    1899                 goto success;
    1900         }
    1901 
    1902         btree_node_t *node = btree_leaf_node_left_neighbour(&area->used_space, leaf);
    1903         if (node) {
    1904                 uintptr_t left_pg = node->key[node->keys - 1];
    1905                 uintptr_t right_pg = leaf->key[0];
    1906                 size_t left_cnt = (size_t) node->value[node->keys - 1];
    1907                 size_t right_cnt = (size_t) leaf->value[0];
    1908 
    1909                 /*
    1910                  * Examine the possibility that the interval fits
    1911                  * somewhere between the rightmost interval of
    1912                  * the left neigbour and the first interval of the leaf.
    1913                  */
    1914 
    1915                 if (page >= right_pg) {
    1916                         /* Do nothing. */
    1917                 } else if (overlaps(page, P2SZ(count), left_pg,
    1918                     P2SZ(left_cnt))) {
    1919                         /* The interval intersects with the left interval. */
    1920                         return false;
    1921                 } else if (overlaps(page, P2SZ(count), right_pg,
    1922                     P2SZ(right_cnt))) {
    1923                         /* The interval intersects with the right interval. */
    1924                         return false;
    1925                 } else if ((page == left_pg + P2SZ(left_cnt)) &&
    1926                     (page + P2SZ(count) == right_pg)) {
    1927                         /*
    1928                          * The interval can be added by merging the two already
    1929                          * present intervals.
    1930                          */
    1931                         node->value[node->keys - 1] += count + right_cnt;
    1932                         btree_remove(&area->used_space, right_pg, leaf);
    1933                         goto success;
    1934                 } else if (page == left_pg + P2SZ(left_cnt)) {
    1935                         /*
    1936                          * The interval can be added by simply growing the left
    1937                          * interval.
    1938                          */
    1939                         node->value[node->keys - 1] += count;
    1940                         goto success;
    1941                 } else if (page + P2SZ(count) == right_pg) {
    1942                         /*
    1943                          * The interval can be addded by simply moving base of
    1944                          * the right interval down and increasing its size
    1945                          * accordingly.
    1946                          */
    1947                         leaf->value[0] += count;
    1948                         leaf->key[0] = page;
    1949                         goto success;
    1950                 } else {
    1951                         /*
    1952                          * The interval is between both neigbouring intervals,
    1953                          * but cannot be merged with any of them.
    1954                          */
    1955                         btree_insert(&area->used_space, page, (void *) count,
    1956                             leaf);
    1957                         goto success;
    1958                 }
    1959         } else if (page < leaf->key[0]) {
    1960                 uintptr_t right_pg = leaf->key[0];
    1961                 size_t right_cnt = (size_t) leaf->value[0];
    1962 
    1963                 /*
    1964                  * Investigate the border case in which the left neighbour does
    1965                  * not exist but the interval fits from the left.
    1966                  */
    1967 
    1968                 if (overlaps(page, P2SZ(count), right_pg, P2SZ(right_cnt))) {
    1969                         /* The interval intersects with the right interval. */
    1970                         return false;
    1971                 } else if (page + P2SZ(count) == right_pg) {
    1972                         /*
    1973                          * The interval can be added by moving the base of the
    1974                          * right interval down and increasing its size
    1975                          * accordingly.
    1976                          */
    1977                         leaf->key[0] = page;
    1978                         leaf->value[0] += count;
    1979                         goto success;
    1980                 } else {
    1981                         /*
    1982                          * The interval doesn't adjoin with the right interval.
    1983                          * It must be added individually.
    1984                          */
    1985                         btree_insert(&area->used_space, page, (void *) count,
    1986                             leaf);
    1987                         goto success;
    1988                 }
    1989         }
    1990 
    1991         node = btree_leaf_node_right_neighbour(&area->used_space, leaf);
    1992         if (node) {
    1993                 uintptr_t left_pg = leaf->key[leaf->keys - 1];
    1994                 uintptr_t right_pg = node->key[0];
    1995                 size_t left_cnt = (size_t) leaf->value[leaf->keys - 1];
    1996                 size_t right_cnt = (size_t) node->value[0];
    1997 
    1998                 /*
    1999                  * Examine the possibility that the interval fits
    2000                  * somewhere between the leftmost interval of
    2001                  * the right neigbour and the last interval of the leaf.
    2002                  */
    2003 
    2004                 if (page < left_pg) {
    2005                         /* Do nothing. */
    2006                 } else if (overlaps(page, P2SZ(count), left_pg,
    2007                     P2SZ(left_cnt))) {
    2008                         /* The interval intersects with the left interval. */
    2009                         return false;
    2010                 } else if (overlaps(page, P2SZ(count), right_pg,
    2011                     P2SZ(right_cnt))) {
    2012                         /* The interval intersects with the right interval. */
    2013                         return false;
    2014                 } else if ((page == left_pg + P2SZ(left_cnt)) &&
    2015                     (page + P2SZ(count) == right_pg)) {
    2016                         /*
    2017                          * The interval can be added by merging the two already
    2018                          * present intervals.
    2019                          */
    2020                         leaf->value[leaf->keys - 1] += count + right_cnt;
    2021                         btree_remove(&area->used_space, right_pg, node);
    2022                         goto success;
    2023                 } else if (page == left_pg + P2SZ(left_cnt)) {
    2024                         /*
    2025                          * The interval can be added by simply growing the left
    2026                          * interval.
    2027                          */
    2028                         leaf->value[leaf->keys - 1] += count;
    2029                         goto success;
    2030                 } else if (page + P2SZ(count) == right_pg) {
    2031                         /*
    2032                          * The interval can be addded by simply moving base of
    2033                          * the right interval down and increasing its size
    2034                          * accordingly.
    2035                          */
    2036                         node->value[0] += count;
    2037                         node->key[0] = page;
    2038                         goto success;
    2039                 } else {
    2040                         /*
    2041                          * The interval is between both neigbouring intervals,
    2042                          * but cannot be merged with any of them.
    2043                          */
    2044                         btree_insert(&area->used_space, page, (void *) count,
    2045                             leaf);
    2046                         goto success;
    2047                 }
    2048         } else if (page >= leaf->key[leaf->keys - 1]) {
    2049                 uintptr_t left_pg = leaf->key[leaf->keys - 1];
    2050                 size_t left_cnt = (size_t) leaf->value[leaf->keys - 1];
    2051 
    2052                 /*
    2053                  * Investigate the border case in which the right neighbour
    2054                  * does not exist but the interval fits from the right.
    2055                  */
    2056 
    2057                 if (overlaps(page, P2SZ(count), left_pg, P2SZ(left_cnt))) {
    2058                         /* The interval intersects with the left interval. */
    2059                         return false;
    2060                 } else if (left_pg + P2SZ(left_cnt) == page) {
    2061                         /*
    2062                          * The interval can be added by growing the left
    2063                          * interval.
    2064                          */
    2065                         leaf->value[leaf->keys - 1] += count;
    2066                         goto success;
    2067                 } else {
    2068                         /*
    2069                          * The interval doesn't adjoin with the left interval.
    2070                          * It must be added individually.
    2071                          */
    2072                         btree_insert(&area->used_space, page, (void *) count,
    2073                             leaf);
    2074                         goto success;
    2075                 }
    2076         }
    2077 
    2078         /*
    2079          * Note that if the algorithm made it thus far, the interval can fit
    2080          * only between two other intervals of the leaf. The two border cases
    2081          * were already resolved.
    2082          */
    2083         btree_key_t i;
    2084         for (i = 1; i < leaf->keys; i++) {
    2085                 if (page < leaf->key[i]) {
    2086                         uintptr_t left_pg = leaf->key[i - 1];
    2087                         uintptr_t right_pg = leaf->key[i];
    2088                         size_t left_cnt = (size_t) leaf->value[i - 1];
    2089                         size_t right_cnt = (size_t) leaf->value[i];
    2090 
    2091                         /*
    2092                          * The interval fits between left_pg and right_pg.
    2093                          */
    2094 
    2095                         if (overlaps(page, P2SZ(count), left_pg,
    2096                             P2SZ(left_cnt))) {
    2097                                 /*
    2098                                  * The interval intersects with the left
    2099                                  * interval.
    2100                                  */
    2101                                 return false;
    2102                         } else if (overlaps(page, P2SZ(count), right_pg,
    2103                             P2SZ(right_cnt))) {
    2104                                 /*
    2105                                  * The interval intersects with the right
    2106                                  * interval.
    2107                                  */
    2108                                 return false;
    2109                         } else if ((page == left_pg + P2SZ(left_cnt)) &&
    2110                             (page + P2SZ(count) == right_pg)) {
    2111                                 /*
    2112                                  * The interval can be added by merging the two
    2113                                  * already present intervals.
    2114                                  */
    2115                                 leaf->value[i - 1] += count + right_cnt;
    2116                                 btree_remove(&area->used_space, right_pg, leaf);
    2117                                 goto success;
    2118                         } else if (page == left_pg + P2SZ(left_cnt)) {
    2119                                 /*
    2120                                  * The interval can be added by simply growing
    2121                                  * the left interval.
    2122                                  */
    2123                                 leaf->value[i - 1] += count;
    2124                                 goto success;
    2125                         } else if (page + P2SZ(count) == right_pg) {
    2126                                 /*
    2127                                  * The interval can be addded by simply moving
    2128                                  * base of the right interval down and
    2129                                  * increasing its size accordingly.
    2130                                  */
    2131                                 leaf->value[i] += count;
    2132                                 leaf->key[i] = page;
    2133                                 goto success;
    2134                         } else {
    2135                                 /*
    2136                                  * The interval is between both neigbouring
    2137                                  * intervals, but cannot be merged with any of
    2138                                  * them.
    2139                                  */
    2140                                 btree_insert(&area->used_space, page,
    2141                                     (void *) count, leaf);
    2142                                 goto success;
    2143                         }
    2144                 }
    2145         }
    2146 
    2147         panic("Inconsistency detected while adding %zu pages of used "
    2148             "space at %p.", count, (void *) page);
    2149 
    2150 success:
    2151         area->resident += count;
    2152         return true;
    2153 }
    2154 
    2155 /** Mark portion of address space area as unused.
    2156  *
    2157  * The address space area must be already locked.
    2158  *
    2159  * @param area  Address space area.
    2160  * @param page  First page to be marked.
    2161  * @param count Number of page to be marked.
    2162  *
    2163  * @return False on failure or true on success.
    2164  *
    2165  */
    2166 bool used_space_remove(as_area_t *area, uintptr_t page, size_t count)
    2167 {
    2168         assert(mutex_locked(&area->lock));
    2169         assert(IS_ALIGNED(page, PAGE_SIZE));
    2170         assert(count);
    2171 
    2172         btree_node_t *leaf;
    2173         size_t pages = (size_t) btree_search(&area->used_space, page, &leaf);
    2174         if (pages) {
    2175                 /*
    2176                  * We are lucky, page is the beginning of some interval.
    2177                  */
    2178                 if (count > pages) {
    2179                         return false;
    2180                 } else if (count == pages) {
    2181                         btree_remove(&area->used_space, page, leaf);
    2182                         goto success;
    2183                 } else {
    2184                         /*
    2185                          * Find the respective interval.
    2186                          * Decrease its size and relocate its start address.
    2187                          */
    2188                         btree_key_t i;
    2189                         for (i = 0; i < leaf->keys; i++) {
    2190                                 if (leaf->key[i] == page) {
    2191                                         leaf->key[i] += P2SZ(count);
    2192                                         leaf->value[i] -= count;
    2193                                         goto success;
    2194                                 }
    2195                         }
    2196 
    2197                         goto error;
    2198                 }
    2199         }
    2200 
    2201         btree_node_t *node = btree_leaf_node_left_neighbour(&area->used_space,
    2202             leaf);
    2203         if ((node) && (page < leaf->key[0])) {
    2204                 uintptr_t left_pg = node->key[node->keys - 1];
    2205                 size_t left_cnt = (size_t) node->value[node->keys - 1];
    2206 
    2207                 if (overlaps(left_pg, P2SZ(left_cnt), page, P2SZ(count))) {
    2208                         if (page + P2SZ(count) == left_pg + P2SZ(left_cnt)) {
    2209                                 /*
    2210                                  * The interval is contained in the rightmost
    2211                                  * interval of the left neighbour and can be
    2212                                  * removed by updating the size of the bigger
    2213                                  * interval.
    2214                                  */
    2215                                 node->value[node->keys - 1] -= count;
    2216                                 goto success;
    2217                         } else if (page + P2SZ(count) <
    2218                             left_pg + P2SZ(left_cnt)) {
    2219                                 size_t new_cnt;
    2220 
    2221                                 /*
    2222                                  * The interval is contained in the rightmost
    2223                                  * interval of the left neighbour but its
    2224                                  * removal requires both updating the size of
    2225                                  * the original interval and also inserting a
    2226                                  * new interval.
    2227                                  */
    2228                                 new_cnt = ((left_pg + P2SZ(left_cnt)) -
    2229                                     (page + P2SZ(count))) >> PAGE_WIDTH;
    2230                                 node->value[node->keys - 1] -= count + new_cnt;
    2231                                 btree_insert(&area->used_space, page +
    2232                                     P2SZ(count), (void *) new_cnt, leaf);
    2233                                 goto success;
    2234                         }
    2235                 }
    2236 
     2061
     2062        /* Check for conflict with right interval */
     2063        if (b != NULL && overlaps(page, P2SZ(count), b->page, P2SZ(b->count)))
    22372064                return false;
    2238         } else if (page < leaf->key[0])
    2239                 return false;
    2240 
    2241         if (page > leaf->key[leaf->keys - 1]) {
    2242                 uintptr_t left_pg = leaf->key[leaf->keys - 1];
    2243                 size_t left_cnt = (size_t) leaf->value[leaf->keys - 1];
    2244 
    2245                 if (overlaps(left_pg, P2SZ(left_cnt), page, P2SZ(count))) {
    2246                         if (page + P2SZ(count) == left_pg + P2SZ(left_cnt)) {
    2247                                 /*
    2248                                  * The interval is contained in the rightmost
    2249                                  * interval of the leaf and can be removed by
    2250                                  * updating the size of the bigger interval.
    2251                                  */
    2252                                 leaf->value[leaf->keys - 1] -= count;
    2253                                 goto success;
    2254                         } else if (page + P2SZ(count) < left_pg +
    2255                             P2SZ(left_cnt)) {
    2256                                 size_t new_cnt;
    2257 
    2258                                 /*
    2259                                  * The interval is contained in the rightmost
    2260                                  * interval of the leaf but its removal
    2261                                  * requires both updating the size of the
    2262                                  * original interval and also inserting a new
    2263                                  * interval.
    2264                                  */
    2265                                 new_cnt = ((left_pg + P2SZ(left_cnt)) -
    2266                                     (page + P2SZ(count))) >> PAGE_WIDTH;
    2267                                 leaf->value[leaf->keys - 1] -= count + new_cnt;
    2268                                 btree_insert(&area->used_space, page +
    2269                                     P2SZ(count), (void *) new_cnt, leaf);
    2270                                 goto success;
    2271                         }
    2272                 }
    2273 
    2274                 return false;
    2275         }
    2276 
    2277         /*
    2278          * The border cases have been already resolved.
    2279          * Now the interval can be only between intervals of the leaf.
    2280          */
    2281         btree_key_t i;
    2282         for (i = 1; i < leaf->keys - 1; i++) {
    2283                 if (page < leaf->key[i]) {
    2284                         uintptr_t left_pg = leaf->key[i - 1];
    2285                         size_t left_cnt = (size_t) leaf->value[i - 1];
    2286 
    2287                         /*
    2288                          * Now the interval is between intervals corresponding
    2289                          * to (i - 1) and i.
    2290                          */
    2291                         if (overlaps(left_pg, P2SZ(left_cnt), page,
    2292                             P2SZ(count))) {
    2293                                 if (page + P2SZ(count) ==
    2294                                     left_pg + P2SZ(left_cnt)) {
    2295                                         /*
    2296                                          * The interval is contained in the
    2297                                          * interval (i - 1) of the leaf and can
    2298                                          * be removed by updating the size of
    2299                                          * the bigger interval.
    2300                                          */
    2301                                         leaf->value[i - 1] -= count;
    2302                                         goto success;
    2303                                 } else if (page + P2SZ(count) <
    2304                                     left_pg + P2SZ(left_cnt)) {
    2305                                         size_t new_cnt;
    2306 
    2307                                         /*
    2308                                          * The interval is contained in the
    2309                                          * interval (i - 1) of the leaf but its
    2310                                          * removal requires both updating the
    2311                                          * size of the original interval and
    2312                                          * also inserting a new interval.
    2313                                          */
    2314                                         new_cnt = ((left_pg + P2SZ(left_cnt)) -
    2315                                             (page + P2SZ(count))) >>
    2316                                             PAGE_WIDTH;
    2317                                         leaf->value[i - 1] -= count + new_cnt;
    2318                                         btree_insert(&area->used_space, page +
    2319                                             P2SZ(count), (void *) new_cnt,
    2320                                             leaf);
    2321                                         goto success;
    2322                                 }
    2323                         }
    2324 
    2325                         return false;
    2326                 }
    2327         }
    2328 
    2329 error:
    2330         panic("Inconsistency detected while removing %zu pages of used "
    2331             "space from %p.", count, (void *) page);
    2332 
    2333 success:
    2334         area->resident -= count;
     2065
     2066        /* Check if A is adjacent to the new interval */
     2067        adj_a = (a != NULL) && (a->page + P2SZ(a->count) == page);
     2068        /* Check if the new interval is adjacent to B*/
     2069        adj_b = (b != NULL) && page + P2SZ(count) == b->page;
     2070
     2071        if (adj_a && adj_b) {
     2072                /* Fuse into a single interval */
     2073                a->count += count + b->count;
     2074                used_space_remove_ival(b);
     2075        } else if (adj_a) {
     2076                /* Append to A */
     2077                a->count += count;
     2078        } else if (adj_b) {
     2079                /* Prepend to B */
     2080                b->page = page;
     2081                b->count += count;
     2082        } else {
     2083                /* Create new interval */
     2084                ival = slab_alloc(used_space_ival_cache, 0);
     2085                ival->used_space = used_space;
     2086                odlink_initialize(&ival->lused_space);
     2087                ival->page = page;
     2088                ival->count = count;
     2089
     2090                odict_insert(&ival->lused_space, &used_space->ivals,
     2091                    NULL);
     2092        }
     2093
     2094        used_space->pages += count;
    23352095        return true;
    23362096}
  • kernel/generic/src/mm/backend_anon.c

    rde0af3a r7be8d4d  
    4848#include <synch/mutex.h>
    4949#include <adt/list.h>
    50 #include <adt/btree.h>
    5150#include <errno.h>
    5251#include <typedefs.h>
     
    122121         */
    123122        mutex_lock(&area->sh_info->lock);
    124         list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t,
    125             node) {
    126                 unsigned int i;
    127 
    128                 for (i = 0; i < node->keys; i++) {
    129                         uintptr_t base = node->key[i];
    130                         size_t count = (size_t) node->value[i];
    131                         unsigned int j;
    132 
    133                         for (j = 0; j < count; j++) {
    134                                 pte_t pte;
    135                                 bool found;
    136 
    137                                 page_table_lock(area->as, false);
    138                                 found = page_mapping_find(area->as,
    139                                     base + P2SZ(j), false, &pte);
    140 
    141                                 (void)found;
    142                                 assert(found);
    143                                 assert(PTE_VALID(&pte));
    144                                 assert(PTE_PRESENT(&pte));
    145 
    146                                 as_pagemap_insert(&area->sh_info->pagemap,
    147                                     (base + P2SZ(j)) - area->base,
    148                                     PTE_GET_FRAME(&pte));
    149                                 page_table_unlock(area->as, false);
    150 
    151                                 pfn_t pfn = ADDR2PFN(PTE_GET_FRAME(&pte));
    152                                 frame_reference_add(pfn);
    153                         }
    154 
     123        used_space_ival_t *ival = used_space_first(&area->used_space);
     124        while (ival != NULL) {
     125                uintptr_t base = ival->page;
     126                size_t count = ival->count;
     127                unsigned int j;
     128
     129                for (j = 0; j < count; j++) {
     130                        pte_t pte;
     131                        bool found;
     132
     133                        page_table_lock(area->as, false);
     134                        found = page_mapping_find(area->as, base + P2SZ(j),
     135                            false, &pte);
     136
     137                        (void)found;
     138                        assert(found);
     139                        assert(PTE_VALID(&pte));
     140                        assert(PTE_PRESENT(&pte));
     141
     142                        as_pagemap_insert(&area->sh_info->pagemap,
     143                            (base + P2SZ(j)) - area->base, PTE_GET_FRAME(&pte));
     144                        page_table_unlock(area->as, false);
     145
     146                        pfn_t pfn = ADDR2PFN(PTE_GET_FRAME(&pte));
     147                        frame_reference_add(pfn);
    155148                }
     149
     150                ival = used_space_next(ival);
    156151        }
    157152        mutex_unlock(&area->sh_info->lock);
     
    264259         */
    265260        page_mapping_insert(AS, upage, frame, as_area_get_flags(area));
    266         if (!used_space_insert(area, upage, 1))
     261        if (!used_space_insert(&area->used_space, upage, 1))
    267262                panic("Cannot insert used space.");
    268263
  • kernel/generic/src/mm/backend_elf.c

    rde0af3a r7be8d4d  
    153153{
    154154        elf_segment_header_t *entry = area->backend_data.segment;
    155         link_t *cur;
    156         btree_node_t *leaf, *node;
     155        used_space_ival_t *start;
     156        used_space_ival_t *cur;
    157157        uintptr_t start_anon = entry->p_vaddr + entry->p_filesz;
    158158
     
    164164         */
    165165        if (area->flags & AS_AREA_WRITE) {
    166                 node = list_get_instance(list_first(&area->used_space.leaf_list),
    167                     btree_node_t, leaf_link);
     166                start = used_space_first(&area->used_space);
    168167        } else {
    169                 (void) btree_search(&area->used_space, start_anon, &leaf);
    170                 node = btree_leaf_node_left_neighbour(&area->used_space, leaf);
    171                 if (!node)
    172                         node = leaf;
     168                /* Find first interval containing addresses >= start_anon */
     169                start = used_space_find_gteq(&area->used_space, start_anon);
    173170        }
    174171
     
    177174         */
    178175        mutex_lock(&area->sh_info->lock);
    179         for (cur = &node->leaf_link; cur != &area->used_space.leaf_list.head;
    180             cur = cur->next) {
     176        cur = start;
     177        while (cur != NULL) {
     178                uintptr_t base = cur->page;
     179                size_t count = cur->count;
    181180                unsigned int i;
    182181
    183                 node = list_get_instance(cur, btree_node_t, leaf_link);
    184 
    185                 for (i = 0; i < node->keys; i++) {
    186                         uintptr_t base = node->key[i];
    187                         size_t count = (size_t) node->value[i];
    188                         unsigned int j;
     182                /*
     183                 * Skip read-only areas of used space that are backed
     184                 * by the ELF image.
     185                 */
     186                if (!(area->flags & AS_AREA_WRITE))
     187                        if (base >= entry->p_vaddr &&
     188                            base + P2SZ(count) <= start_anon)
     189                                continue;
     190
     191                for (i = 0; i < count; i++) {
     192                        pte_t pte;
     193                        bool found;
    189194
    190195                        /*
    191                          * Skip read-only areas of used space that are backed
    192                          * by the ELF image.
     196                         * Skip read-only pages that are backed by the
     197                         * ELF image.
    193198                         */
    194199                        if (!(area->flags & AS_AREA_WRITE))
    195200                                if (base >= entry->p_vaddr &&
    196                                     base + P2SZ(count) <= start_anon)
     201                                    base + P2SZ(i + 1) <= start_anon)
    197202                                        continue;
    198203
    199                         for (j = 0; j < count; j++) {
    200                                 pte_t pte;
    201                                 bool found;
    202 
    203                                 /*
    204                                  * Skip read-only pages that are backed by the
    205                                  * ELF image.
    206                                  */
    207                                 if (!(area->flags & AS_AREA_WRITE))
    208                                         if (base >= entry->p_vaddr &&
    209                                             base + P2SZ(j + 1) <= start_anon)
    210                                                 continue;
    211 
    212                                 page_table_lock(area->as, false);
    213                                 found = page_mapping_find(area->as,
    214                                     base + P2SZ(j), false, &pte);
    215 
    216                                 (void) found;
    217                                 assert(found);
    218                                 assert(PTE_VALID(&pte));
    219                                 assert(PTE_PRESENT(&pte));
    220 
    221                                 as_pagemap_insert(&area->sh_info->pagemap,
    222                                     (base + P2SZ(j)) - area->base,
    223                                     PTE_GET_FRAME(&pte));
    224                                 page_table_unlock(area->as, false);
    225 
    226                                 pfn_t pfn = ADDR2PFN(PTE_GET_FRAME(&pte));
    227                                 frame_reference_add(pfn);
    228                         }
    229 
     204                        page_table_lock(area->as, false);
     205                        found = page_mapping_find(area->as,
     206                            base + P2SZ(i), false, &pte);
     207
     208                        (void) found;
     209                        assert(found);
     210                        assert(PTE_VALID(&pte));
     211                        assert(PTE_PRESENT(&pte));
     212
     213                        as_pagemap_insert(&area->sh_info->pagemap,
     214                            (base + P2SZ(i)) - area->base,
     215                            PTE_GET_FRAME(&pte));
     216                        page_table_unlock(area->as, false);
     217
     218                        pfn_t pfn = ADDR2PFN(PTE_GET_FRAME(&pte));
     219                        frame_reference_add(pfn);
    230220                }
    231         }
     221
     222                cur = used_space_next(cur);
     223        }
     224
    232225        mutex_unlock(&area->sh_info->lock);
    233226}
     
    310303                        page_mapping_insert(AS, upage, frame,
    311304                            as_area_get_flags(area));
    312                         if (!used_space_insert(area, upage, 1))
     305                        if (!used_space_insert(&area->used_space, upage, 1))
    313306                                panic("Cannot insert used space.");
    314307                        mutex_unlock(&area->sh_info->lock);
     
    405398
    406399        page_mapping_insert(AS, upage, frame, as_area_get_flags(area));
    407         if (!used_space_insert(area, upage, 1))
     400        if (!used_space_insert(&area->used_space, upage, 1))
    408401                panic("Cannot insert used space.");
    409402
  • kernel/generic/src/mm/backend_phys.c

    rde0af3a r7be8d4d  
    143143            as_area_get_flags(area));
    144144
    145         if (!used_space_insert(area, upage, 1))
     145        if (!used_space_insert(&area->used_space, upage, 1))
    146146                panic("Cannot insert used space.");
    147147
  • kernel/generic/src/mm/backend_user.c

    rde0af3a r7be8d4d  
    147147        uintptr_t frame = IPC_GET_ARG1(data);
    148148        page_mapping_insert(AS, upage, frame, as_area_get_flags(area));
    149         if (!used_space_insert(area, upage, 1))
     149        if (!used_space_insert(&area->used_space, upage, 1))
    150150                panic("Cannot insert used space.");
    151151
  • kernel/generic/src/sysinfo/stats.c

    rde0af3a r7be8d4d  
    189189                        continue;
    190190
    191                 pages += area->resident;
     191                pages += area->used_space.pages;
    192192                mutex_unlock(&area->lock);
    193193                area = as_area_next(area);
Note: See TracChangeset for help on using the changeset viewer.