Changeset 7be8d4d in mainline for kernel/generic/src/mm/as.c
- Timestamp:
- 2018-12-08T23:32:55Z (5 years ago)
- 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)
- File:
-
- 1 edited
-
kernel/generic/src/mm/as.c (modified) (16 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/mm/as.c
rde0af3a r7be8d4d 63 63 #include <synch/mutex.h> 64 64 #include <adt/list.h> 65 #include <adt/btree.h>66 65 #include <proc/task.h> 67 66 #include <proc/thread.h> … … 95 94 static slab_cache_t *as_page_mapping_cache; 96 95 96 /** Cache for used_space_ival_t objects */ 97 static slab_cache_t *used_space_ival_cache; 98 97 99 /** ASID subsystem lock. 98 100 * … … 117 119 static int as_areas_cmp(void *, void *); 118 120 121 static void used_space_initialize(used_space_t *); 122 static void used_space_finalize(used_space_t *); 123 static void *used_space_getkey(odlink_t *); 124 static int used_space_cmp(void *, void *); 125 static used_space_ival_t *used_space_last(used_space_t *); 126 static void used_space_remove_ival(used_space_ival_t *); 127 static void used_space_shorten_ival(used_space_ival_t *, size_t); 128 119 129 NO_TRACE static errno_t as_constructor(void *obj, unsigned int flags) 120 130 { … … 142 152 as_page_mapping_cache = slab_cache_create("as_page_mapping_t", 143 153 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); 144 157 145 158 AS_KERNEL = as_create(FLAG_AS_KERNEL); … … 548 561 * @param b Pointer to virtual address cast as @c void * 549 562 * @return <0, =0, >0 if virtual address a is less than, equal to, or 550 * greater -than b, respectively.563 * greater than b, respectively. 551 564 */ 552 565 static int as_pagemap_cmp(void *a, void *b) … … 778 791 area->attributes = attrs; 779 792 area->pages = pages; 780 area->resident = 0;781 793 area->base = *base; 782 794 area->backend = backend; … … 831 843 } 832 844 833 btree_create(&area->used_space);845 used_space_initialize(&area->used_space); 834 846 odict_insert(&area->las_areas, &as->as_areas, NULL); 835 847 … … 939 951 940 952 /* 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 /* 941 961 * Remove frames belonging to used space starting from 942 962 * 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. 946 964 */ 947 965 bool cond = true; 948 966 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) { 973 979 /* 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. 977 982 */ 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; 992 984 } 993 985 994 986 /* 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. 1004 990 */ 1005 991 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)); 1028 1021 } 1029 1022 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)); 1046 1024 } 1025 1047 1026 } 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 1048 1045 page_table_unlock(as, false); 1049 1046 } else { … … 1104 1101 1105 1102 page_table_lock(as, false); 1106 1107 1103 /* 1108 1104 * Start TLB shootdown sequence. … … 1112 1108 1113 1109 /* 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)); 1142 1131 } 1132 1133 page_mapping_remove(as, ptr + P2SZ(size)); 1143 1134 } 1135 1136 used_space_remove_ival(ival); 1137 ival = used_space_first(&area->used_space); 1144 1138 } 1145 1139 … … 1159 1153 page_table_unlock(as, false); 1160 1154 1161 btree_destroy(&area->used_space); 1162 1155 used_space_finalize(&area->used_space); 1163 1156 area->attributes |= AS_AREA_ATTR_PARTIAL; 1164 1165 1157 sh_info_remove_reference(area->sh_info); 1166 1158 … … 1399 1391 1400 1392 /* 1401 * Compute total number of used pages in the used_space B+tree1393 * Compute total number of used pages 1402 1394 */ 1403 1395 size_t used_pages = 0; 1404 1396 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); 1411 1401 } 1412 1402 … … 1433 1423 size_t frame_idx = 0; 1434 1424 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)); 1458 1444 } 1445 1446 ival = used_space_next(ival); 1459 1447 } 1460 1448 … … 1486 1474 frame_idx = 0; 1487 1475 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); 1505 1489 } 1490 1491 ival = used_space_next(ival); 1506 1492 } 1507 1493 … … 1867 1853 } 1868 1854 1855 /** Initialize used space map. 1856 * 1857 * @param used_space Used space map 1858 */ 1859 static 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 */ 1869 static 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 */ 1880 used_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 */ 1895 used_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 */ 1911 static 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 */ 1929 used_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 */ 1973 static 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 */ 1987 static 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 */ 2004 static 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 */ 2016 static 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 1869 2025 /** Mark portion of address space area as used. 1870 2026 * 1871 2027 * The address space area must be already locked. 1872 2028 * 1873 * @param area Address space area.1874 * @param page 2029 * @param used_space Used space map 2030 * @param page First page to be marked. 1875 2031 * @param count Number of page to be marked. 1876 2032 * … … 1878 2034 * 1879 2035 */ 1880 bool used_space_insert(as_area_t *area, uintptr_t page, size_t count) 1881 { 1882 assert(mutex_locked(&area->lock)); 2036 bool 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 1883 2045 assert(IS_ALIGNED(page, PAGE_SIZE)); 1884 2046 assert(count); 1885 2047 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))) 1892 2060 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))) 2237 2064 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; 2335 2095 return true; 2336 2096 }
Note:
See TracChangeset
for help on using the changeset viewer.
