Changes in kernel/generic/src/mm/as.c [ca4c5596:ca21f1e2] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/mm/as.c (modified) (19 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/mm/as.c
rca4c5596 rca21f1e2 63 63 #include <synch/mutex.h> 64 64 #include <adt/list.h> 65 #include <adt/btree.h> 65 66 #include <proc/task.h> 66 67 #include <proc/thread.h> … … 88 89 as_operations_t *as_operations = NULL; 89 90 90 /** Cache for as_t objects */ 91 /** Slab for as_t objects. 92 * 93 */ 91 94 static slab_cache_t *as_cache; 92 93 /** Cache for as_page_mapping_t objects */94 static slab_cache_t *as_page_mapping_cache;95 96 /** Cache for used_space_ival_t objects */97 static slab_cache_t *used_space_ival_cache;98 95 99 96 /** ASID subsystem lock. … … 119 116 static int as_areas_cmp(void *, void *); 120 117 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 129 118 NO_TRACE static errno_t as_constructor(void *obj, unsigned int flags) 130 119 { … … 149 138 as_cache = slab_cache_create("as_t", sizeof(as_t), 0, 150 139 as_constructor, as_destructor, SLAB_CACHE_MAGDEFERRED); 151 152 as_page_mapping_cache = slab_cache_create("as_page_mapping_t",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);157 140 158 141 AS_KERNEL = as_create(FLAG_AS_KERNEL); … … 541 524 } 542 525 543 /** Get key function for pagemap ordered dictionary.544 *545 * The key is the virtual address of the page (as_page_mapping_t.vaddr)546 *547 * @param odlink Link to as_pagemap_t.map ordered dictionary548 * @return Pointer to virtual address cast as @c void *549 */550 static void *as_pagemap_getkey(odlink_t *odlink)551 {552 as_page_mapping_t *mapping;553 554 mapping = odict_get_instance(odlink, as_page_mapping_t, lpagemap);555 return (void *) &mapping->vaddr;556 }557 558 /** Comparison function for pagemap ordered dictionary.559 *560 * @param a Pointer to virtual address cast as @c void *561 * @param b Pointer to virtual address cast as @c void *562 * @return <0, =0, >0 if virtual address a is less than, equal to, or563 * greater than b, respectively.564 */565 static int as_pagemap_cmp(void *a, void *b)566 {567 uintptr_t va = *(uintptr_t *)a;568 uintptr_t vb = *(uintptr_t *)b;569 570 if (va < vb)571 return -1;572 else if (va == vb)573 return 0;574 else575 return +1;576 }577 578 /** Initialize pagemap.579 *580 * @param pagemap Pagemap581 */582 NO_TRACE void as_pagemap_initialize(as_pagemap_t *pagemap)583 {584 odict_initialize(&pagemap->map, as_pagemap_getkey, as_pagemap_cmp);585 }586 587 /** Finalize pagemap.588 *589 * Destroy any entries in the pagemap.590 *591 * @param pagemap Pagemap592 */593 NO_TRACE void as_pagemap_finalize(as_pagemap_t *pagemap)594 {595 as_page_mapping_t *mapping = as_pagemap_first(pagemap);596 while (mapping != NULL) {597 as_pagemap_remove(mapping);598 mapping = as_pagemap_first(pagemap);599 }600 odict_finalize(&pagemap->map);601 }602 603 /** Get first page mapping.604 *605 * @param pagemap Pagemap606 * @return First mapping or @c NULL if there is none607 */608 NO_TRACE as_page_mapping_t *as_pagemap_first(as_pagemap_t *pagemap)609 {610 odlink_t *odlink;611 612 odlink = odict_first(&pagemap->map);613 if (odlink == NULL)614 return NULL;615 616 return odict_get_instance(odlink, as_page_mapping_t, lpagemap);617 }618 619 /** Get next page mapping.620 *621 * @param cur Current mapping622 * @return Next mapping or @c NULL if @a cur is the last one623 */624 NO_TRACE as_page_mapping_t *as_pagemap_next(as_page_mapping_t *cur)625 {626 odlink_t *odlink;627 628 odlink = odict_next(&cur->lpagemap, &cur->pagemap->map);629 if (odlink == NULL)630 return NULL;631 632 return odict_get_instance(odlink, as_page_mapping_t, lpagemap);633 }634 635 /** Find frame by virtual address.636 *637 * @param pagemap Pagemap638 * @param vaddr Virtual address of page639 * @param rframe Place to store physical frame address640 * @return EOK on succcess or ENOENT if no mapping found641 */642 NO_TRACE errno_t as_pagemap_find(as_pagemap_t *pagemap, uintptr_t vaddr,643 uintptr_t *rframe)644 {645 odlink_t *odlink;646 as_page_mapping_t *mapping;647 648 odlink = odict_find_eq(&pagemap->map, &vaddr, NULL);649 if (odlink == NULL)650 return ENOENT;651 652 mapping = odict_get_instance(odlink, as_page_mapping_t, lpagemap);653 *rframe = mapping->frame;654 return EOK;655 }656 657 /** Insert new page mapping.658 *659 * This function can block to allocate kernel memory.660 *661 * @param pagemap Pagemap662 * @param vaddr Virtual page address663 * @param frame Physical frame address664 */665 NO_TRACE void as_pagemap_insert(as_pagemap_t *pagemap, uintptr_t vaddr,666 uintptr_t frame)667 {668 as_page_mapping_t *mapping;669 670 mapping = slab_alloc(as_page_mapping_cache, 0);671 mapping->pagemap = pagemap;672 odlink_initialize(&mapping->lpagemap);673 mapping->vaddr = vaddr;674 mapping->frame = frame;675 odict_insert(&mapping->lpagemap, &pagemap->map, NULL);676 }677 678 /** Remove page mapping.679 *680 * @param mapping Mapping681 */682 NO_TRACE void as_pagemap_remove(as_page_mapping_t *mapping)683 {684 odict_remove(&mapping->lpagemap);685 slab_free(as_page_mapping_cache, mapping);686 }687 688 526 /** Remove reference to address space area share info. 689 527 * … … 703 541 dealloc = true; 704 542 705 as_page_mapping_t *mapping = as_pagemap_first(&sh_info->pagemap); 706 while (mapping != NULL) { 707 frame_free(mapping->frame, 1); 708 mapping = as_pagemap_next(mapping); 543 /* 544 * Now walk carefully the pagemap B+tree and free/remove 545 * reference from all frames found there. 546 */ 547 list_foreach(sh_info->pagemap.leaf_list, leaf_link, 548 btree_node_t, node) { 549 btree_key_t i; 550 551 for (i = 0; i < node->keys; i++) 552 frame_free((uintptr_t) node->value[i], 1); 709 553 } 710 554 … … 717 561 sh_info->backend_shared_data); 718 562 } 719 as_pagemap_finalize(&sh_info->pagemap);563 btree_destroy(&sh_info->pagemap); 720 564 free(sh_info); 721 565 } … … 792 636 area->attributes = attrs; 793 637 area->pages = pages; 638 area->resident = 0; 794 639 area->base = *base; 795 640 area->backend = backend; … … 820 665 si->backend_shared_data = NULL; 821 666 si->backend = backend; 822 as_pagemap_initialize(&si->pagemap);667 btree_create(&si->pagemap); 823 668 824 669 area->sh_info = si; … … 844 689 } 845 690 846 used_space_initialize(&area->used_space);691 btree_create(&area->used_space); 847 692 odict_insert(&area->las_areas, &as->as_areas, NULL); 848 693 … … 952 797 953 798 /* 954 * Start TLB shootdown sequence.955 */956 957 ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES,958 as->asid, area->base + P2SZ(pages),959 area->pages - pages);960 961 /*962 799 * Remove frames belonging to used space starting from 963 800 * the highest addresses downwards until an overlap with 964 * the resized address space area is found. 801 * the resized address space area is found. Note that this 802 * is also the right way to remove part of the used_space 803 * B+tree leaf list. 965 804 */ 966 805 bool cond = true; 967 806 while (cond) { 968 used_space_ival_t *ival = 969 used_space_last(&area->used_space); 970 assert(ival != NULL); 971 972 uintptr_t ptr = ival->page; 973 size_t pcount = ival->count; 974 size_t i = 0; 975 976 if (overlaps(ptr, P2SZ(pcount), area->base, 977 P2SZ(pages))) { 978 979 if (ptr + P2SZ(pcount) <= start_free) { 807 assert(!list_empty(&area->used_space.leaf_list)); 808 809 btree_node_t *node = 810 list_get_instance(list_last(&area->used_space.leaf_list), 811 btree_node_t, leaf_link); 812 813 if ((cond = (node->keys != 0))) { 814 uintptr_t ptr = node->key[node->keys - 1]; 815 size_t node_size = 816 (size_t) node->value[node->keys - 1]; 817 size_t i = 0; 818 819 if (overlaps(ptr, P2SZ(node_size), area->base, 820 P2SZ(pages))) { 821 822 if (ptr + P2SZ(node_size) <= start_free) { 823 /* 824 * The whole interval fits 825 * completely in the resized 826 * address space area. 827 */ 828 break; 829 } 830 980 831 /* 981 * The whole interval fits completely 982 * in the resized address space area. 832 * Part of the interval corresponding 833 * to b and c overlaps with the resized 834 * address space area. 983 835 */ 984 break; 836 837 /* We are almost done */ 838 cond = false; 839 i = (start_free - ptr) >> PAGE_WIDTH; 840 if (!used_space_remove(area, start_free, 841 node_size - i)) 842 panic("Cannot remove used space."); 843 } else { 844 /* 845 * The interval of used space can be 846 * completely removed. 847 */ 848 if (!used_space_remove(area, ptr, node_size)) 849 panic("Cannot remove used space."); 985 850 } 986 851 987 852 /* 988 * Part of the interval corresponding to b and 989 * c overlaps with the resized address space 990 * area. 853 * Start TLB shootdown sequence. 854 * 855 * The sequence is rather short and can be 856 * repeated multiple times. The reason is that 857 * we don't want to have used_space_remove() 858 * inside the sequence as it may use a blocking 859 * memory allocation for its B+tree. Blocking 860 * while holding the tlblock spinlock is 861 * forbidden and would hit a kernel assertion. 991 862 */ 992 863 993 /* We are almost done */ 994 cond = false; 995 i = (start_free - ptr) >> PAGE_WIDTH; 996 997 /* Shorten the interval to @c i pages */ 998 used_space_shorten_ival(ival, i); 999 } else { 864 ipl_t ipl = tlb_shootdown_start(TLB_INVL_PAGES, 865 as->asid, area->base + P2SZ(pages), 866 area->pages - pages); 867 868 for (; i < node_size; i++) { 869 pte_t pte; 870 bool found = page_mapping_find(as, 871 ptr + P2SZ(i), false, &pte); 872 873 (void) found; 874 assert(found); 875 assert(PTE_VALID(&pte)); 876 assert(PTE_PRESENT(&pte)); 877 878 if ((area->backend) && 879 (area->backend->frame_free)) { 880 area->backend->frame_free(area, 881 ptr + P2SZ(i), 882 PTE_GET_FRAME(&pte)); 883 } 884 885 page_mapping_remove(as, ptr + P2SZ(i)); 886 } 887 1000 888 /* 1001 * The interval of used space can be completely 1002 * removed. 889 * Finish TLB shootdown sequence. 1003 890 */ 1004 used_space_remove_ival(ival); 891 892 tlb_invalidate_pages(as->asid, 893 area->base + P2SZ(pages), 894 area->pages - pages); 895 896 /* 897 * Invalidate software translation caches 898 * (e.g. TSB on sparc64, PHT on ppc32). 899 */ 900 as_invalidate_translation_cache(as, 901 area->base + P2SZ(pages), 902 area->pages - pages); 903 tlb_shootdown_finalize(ipl); 1005 904 } 1006 1007 for (; i < pcount; i++) { 1008 pte_t pte; 1009 bool found = page_mapping_find(as, 1010 ptr + P2SZ(i), false, &pte); 1011 1012 (void) found; 1013 assert(found); 1014 assert(PTE_VALID(&pte)); 1015 assert(PTE_PRESENT(&pte)); 1016 1017 if ((area->backend) && 1018 (area->backend->frame_free)) { 1019 area->backend->frame_free(area, 1020 ptr + P2SZ(i), 1021 PTE_GET_FRAME(&pte)); 1022 } 1023 1024 page_mapping_remove(as, ptr + P2SZ(i)); 1025 } 1026 1027 } 1028 1029 /* 1030 * Finish TLB shootdown sequence. 1031 */ 1032 1033 tlb_invalidate_pages(as->asid, 1034 area->base + P2SZ(pages), 1035 area->pages - pages); 1036 1037 /* 1038 * Invalidate software translation caches 1039 * (e.g. TSB on sparc64, PHT on ppc32). 1040 */ 1041 as_invalidate_translation_cache(as, 1042 area->base + P2SZ(pages), 1043 area->pages - pages); 1044 tlb_shootdown_finalize(ipl); 1045 905 } 1046 906 page_table_unlock(as, false); 1047 907 } else { … … 1102 962 1103 963 page_table_lock(as, false); 964 1104 965 /* 1105 966 * Start TLB shootdown sequence. … … 1109 970 1110 971 /* 1111 * Visit only the pages mapped by used_space. 1112 */ 1113 used_space_ival_t *ival = used_space_first(&area->used_space); 1114 while (ival != NULL) { 1115 uintptr_t ptr = ival->page; 1116 1117 for (size_t size = 0; size < ival->count; size++) { 1118 pte_t pte; 1119 bool found = page_mapping_find(as, 1120 ptr + P2SZ(size), false, &pte); 1121 1122 (void) found; 1123 assert(found); 1124 assert(PTE_VALID(&pte)); 1125 assert(PTE_PRESENT(&pte)); 1126 1127 if ((area->backend) && 1128 (area->backend->frame_free)) { 1129 area->backend->frame_free(area, 1130 ptr + P2SZ(size), 1131 PTE_GET_FRAME(&pte)); 972 * Visit only the pages mapped by used_space B+tree. 973 */ 974 list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t, 975 node) { 976 btree_key_t i; 977 978 for (i = 0; i < node->keys; i++) { 979 uintptr_t ptr = node->key[i]; 980 size_t size; 981 982 for (size = 0; size < (size_t) node->value[i]; size++) { 983 pte_t pte; 984 bool found = page_mapping_find(as, 985 ptr + P2SZ(size), false, &pte); 986 987 (void) found; 988 assert(found); 989 assert(PTE_VALID(&pte)); 990 assert(PTE_PRESENT(&pte)); 991 992 if ((area->backend) && 993 (area->backend->frame_free)) { 994 area->backend->frame_free(area, 995 ptr + P2SZ(size), 996 PTE_GET_FRAME(&pte)); 997 } 998 999 page_mapping_remove(as, ptr + P2SZ(size)); 1132 1000 } 1133 1134 page_mapping_remove(as, ptr + P2SZ(size)); 1135 } 1136 1137 used_space_remove_ival(ival); 1138 ival = used_space_first(&area->used_space); 1001 } 1139 1002 } 1140 1003 … … 1154 1017 page_table_unlock(as, false); 1155 1018 1156 used_space_finalize(&area->used_space); 1019 btree_destroy(&area->used_space); 1020 1157 1021 area->attributes |= AS_AREA_ATTR_PARTIAL; 1022 1158 1023 sh_info_remove_reference(area->sh_info); 1159 1024 … … 1391 1256 mutex_unlock(&area->sh_info->lock); 1392 1257 1258 /* 1259 * Compute total number of used pages in the used_space B+tree 1260 */ 1261 size_t used_pages = 0; 1262 1263 list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t, 1264 node) { 1265 btree_key_t i; 1266 1267 for (i = 0; i < node->keys; i++) 1268 used_pages += (size_t) node->value[i]; 1269 } 1270 1393 1271 /* An array for storing frame numbers */ 1394 uintptr_t *old_frame = malloc(area->used_space.pages * 1395 sizeof(uintptr_t)); 1272 uintptr_t *old_frame = malloc(used_pages * sizeof(uintptr_t)); 1396 1273 if (!old_frame) { 1397 1274 mutex_unlock(&area->lock); … … 1414 1291 size_t frame_idx = 0; 1415 1292 1416 used_space_ival_t *ival = used_space_first(&area->used_space); 1417 while (ival != NULL) { 1418 uintptr_t ptr = ival->page; 1419 size_t size; 1420 1421 for (size = 0; size < ival->count; size++) { 1422 pte_t pte; 1423 bool found = page_mapping_find(as, ptr + P2SZ(size), 1424 false, &pte); 1425 1426 (void) found; 1427 assert(found); 1428 assert(PTE_VALID(&pte)); 1429 assert(PTE_PRESENT(&pte)); 1430 1431 old_frame[frame_idx++] = PTE_GET_FRAME(&pte); 1432 1433 /* Remove old mapping */ 1434 page_mapping_remove(as, ptr + P2SZ(size)); 1435 } 1436 1437 ival = used_space_next(ival); 1293 list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t, 1294 node) { 1295 btree_key_t i; 1296 1297 for (i = 0; i < node->keys; i++) { 1298 uintptr_t ptr = node->key[i]; 1299 size_t size; 1300 1301 for (size = 0; size < (size_t) node->value[i]; size++) { 1302 pte_t pte; 1303 bool found = page_mapping_find(as, 1304 ptr + P2SZ(size), false, &pte); 1305 1306 (void) found; 1307 assert(found); 1308 assert(PTE_VALID(&pte)); 1309 assert(PTE_PRESENT(&pte)); 1310 1311 old_frame[frame_idx++] = PTE_GET_FRAME(&pte); 1312 1313 /* Remove old mapping */ 1314 page_mapping_remove(as, ptr + P2SZ(size)); 1315 } 1316 } 1438 1317 } 1439 1318 … … 1465 1344 frame_idx = 0; 1466 1345 1467 ival = used_space_first(&area->used_space); 1468 while (ival != NULL) { 1469 uintptr_t ptr = ival->page; 1470 size_t size; 1471 1472 for (size = 0; size < ival->count; size++) { 1473 page_table_lock(as, false); 1474 1475 /* Insert the new mapping */ 1476 page_mapping_insert(as, ptr + P2SZ(size), 1477 old_frame[frame_idx++], page_flags); 1478 1479 page_table_unlock(as, false); 1480 } 1481 1482 ival = used_space_next(ival); 1346 list_foreach(area->used_space.leaf_list, leaf_link, btree_node_t, 1347 node) { 1348 btree_key_t i; 1349 1350 for (i = 0; i < node->keys; i++) { 1351 uintptr_t ptr = node->key[i]; 1352 size_t size; 1353 1354 for (size = 0; size < (size_t) node->value[i]; size++) { 1355 page_table_lock(as, false); 1356 1357 /* Insert the new mapping */ 1358 page_mapping_insert(as, ptr + P2SZ(size), 1359 old_frame[frame_idx++], page_flags); 1360 1361 page_table_unlock(as, false); 1362 } 1363 } 1483 1364 } 1484 1365 … … 1844 1725 } 1845 1726 1846 /** Initialize used space map.1847 *1848 * @param used_space Used space map1849 */1850 static void used_space_initialize(used_space_t *used_space)1851 {1852 odict_initialize(&used_space->ivals, used_space_getkey, used_space_cmp);1853 used_space->pages = 0;1854 }1855 1856 /** Finalize used space map.1857 *1858 * @param used_space Used space map1859 */1860 static void used_space_finalize(used_space_t *used_space)1861 {1862 assert(odict_empty(&used_space->ivals));1863 odict_finalize(&used_space->ivals);1864 }1865 1866 /** Get first interval of used space.1867 *1868 * @param used_space Used space map1869 * @return First interval or @c NULL if there are none1870 */1871 used_space_ival_t *used_space_first(used_space_t *used_space)1872 {1873 odlink_t *odlink = odict_first(&used_space->ivals);1874 1875 if (odlink == NULL)1876 return NULL;1877 1878 return odict_get_instance(odlink, used_space_ival_t, lused_space);1879 }1880 1881 /** Get next interval of used space.1882 *1883 * @param cur Current interval1884 * @return Next interval or @c NULL if there are none1885 */1886 used_space_ival_t *used_space_next(used_space_ival_t *cur)1887 {1888 odlink_t *odlink = odict_next(&cur->lused_space,1889 &cur->used_space->ivals);1890 1891 if (odlink == NULL)1892 return NULL;1893 1894 return odict_get_instance(odlink, used_space_ival_t, lused_space);1895 }1896 1897 /** Get last interval of used space.1898 *1899 * @param used_space Used space map1900 * @return First interval or @c NULL if there are none1901 */1902 static used_space_ival_t *used_space_last(used_space_t *used_space)1903 {1904 odlink_t *odlink = odict_last(&used_space->ivals);1905 1906 if (odlink == NULL)1907 return NULL;1908 1909 return odict_get_instance(odlink, used_space_ival_t, lused_space);1910 }1911 1912 /** Find the first interval that contains addresses greater than or equal to1913 * @a ptr.1914 *1915 * @param used_space Used space map1916 * @param ptr Virtual address1917 *1918 * @return Used space interval or @c NULL if none matches1919 */1920 used_space_ival_t *used_space_find_gteq(used_space_t *used_space, uintptr_t ptr)1921 {1922 odlink_t *odlink;1923 used_space_ival_t *ival;1924 1925 /* Find last interval to start at address less than @a ptr */1926 odlink = odict_find_lt(&used_space->ivals, &ptr, NULL);1927 if (odlink != NULL) {1928 ival = odict_get_instance(odlink, used_space_ival_t,1929 lused_space);1930 1931 /* If the interval extends above @a ptr, return it */1932 if (ival->page + P2SZ(ival->count) > ptr)1933 return ival;1934 1935 /*1936 * Otherwise, if a next interval exists, it must match1937 * the criteria.1938 */1939 odlink = odict_next(&ival->lused_space, &used_space->ivals);1940 } else {1941 /*1942 * No interval with lower base address, so if there is any1943 * interval at all, it must match the criteria1944 */1945 odlink = odict_first(&used_space->ivals);1946 }1947 1948 if (odlink != NULL) {1949 ival = odict_get_instance(odlink, used_space_ival_t,1950 lused_space);1951 return ival;1952 }1953 1954 return NULL;1955 }1956 1957 /** Get key function for used space ordered dictionary.1958 *1959 * The key is the virtual address of the first page1960 *1961 * @param odlink Ordered dictionary link (used_space_ival_t.lused_space)1962 * @return Pointer to virtual address of first page cast as @c void *.1963 */1964 static void *used_space_getkey(odlink_t *odlink)1965 {1966 used_space_ival_t *ival = odict_get_instance(odlink, used_space_ival_t,1967 lused_space);1968 return (void *) &ival->page;1969 }1970 1971 /** Compare function for used space ordered dictionary.1972 *1973 * @param a Pointer to virtual address of first page cast as @c void *1974 * @param b Pointer to virtual address of first page cast as @c void *1975 * @return Less than zero, zero, greater than zero if virtual address @a a1976 * is less than, equal to, greater than virtual address b, respectively.1977 */1978 static int used_space_cmp(void *a, void *b)1979 {1980 uintptr_t va = *(uintptr_t *) a;1981 uintptr_t vb = *(uintptr_t *) b;1982 1983 if (va < vb)1984 return -1;1985 else if (va == vb)1986 return 0;1987 else1988 return +1;1989 }1990 1991 /** Remove used space interval.1992 *1993 * @param ival Used space interval1994 */1995 static void used_space_remove_ival(used_space_ival_t *ival)1996 {1997 ival->used_space->pages -= ival->count;1998 odict_remove(&ival->lused_space);1999 slab_free(used_space_ival_cache, ival);2000 }2001 2002 /** Shorten used space interval.2003 *2004 * @param ival Used space interval2005 * @param count New number of pages in the interval2006 */2007 static void used_space_shorten_ival(used_space_ival_t *ival, size_t count)2008 {2009 assert(count > 0);2010 assert(count < ival->count);2011 2012 ival->used_space->pages -= ival->count - count;2013 ival->count = count;2014 }2015 2016 1727 /** Mark portion of address space area as used. 2017 1728 * 2018 1729 * The address space area must be already locked. 2019 1730 * 2020 * @param used_space Used space map2021 * @param page First page to be marked.1731 * @param area Address space area. 1732 * @param page First page to be marked. 2022 1733 * @param count Number of page to be marked. 2023 1734 * … … 2025 1736 * 2026 1737 */ 2027 bool used_space_insert(used_space_t *used_space, uintptr_t page, size_t count) 2028 { 2029 used_space_ival_t *a; 2030 used_space_ival_t *b; 2031 bool adj_a; 2032 bool adj_b; 2033 odlink_t *odlink; 2034 used_space_ival_t *ival; 2035 1738 bool used_space_insert(as_area_t *area, uintptr_t page, size_t count) 1739 { 1740 assert(mutex_locked(&area->lock)); 2036 1741 assert(IS_ALIGNED(page, PAGE_SIZE)); 2037 1742 assert(count); 2038 1743 2039 /* Interval to the left */ 2040 odlink = odict_find_lt(&used_space->ivals, &page, NULL); 2041 a = (odlink != NULL) ? 2042 odict_get_instance(odlink, used_space_ival_t, lused_space) : 2043 NULL; 2044 2045 /* Interval to the right */ 2046 b = (a != NULL) ? used_space_next(a) : 2047 used_space_first(used_space); 2048 2049 /* Check for conflict with left interval */ 2050 if (a != NULL && overlaps(a->page, P2SZ(a->count), page, P2SZ(count))) 1744 btree_node_t *leaf = NULL; 1745 size_t pages = (size_t) btree_search(&area->used_space, page, &leaf); 1746 if (pages) { 1747 /* 1748 * We hit the beginning of some used space. 1749 */ 2051 1750 return false; 2052 2053 /* Check for conflict with right interval */ 2054 if (b != NULL && overlaps(page, P2SZ(count), b->page, P2SZ(b->count))) 1751 } 1752 1753 assert(leaf != NULL); 1754 1755 if (!leaf->keys) { 1756 btree_insert(&area->used_space, page, (void *) count, leaf); 1757 goto success; 1758 } 1759 1760 btree_node_t *node = btree_leaf_node_left_neighbour(&area->used_space, leaf); 1761 if (node) { 1762 uintptr_t left_pg = node->key[node->keys - 1]; 1763 uintptr_t right_pg = leaf->key[0]; 1764 size_t left_cnt = (size_t) node->value[node->keys - 1]; 1765 size_t right_cnt = (size_t) leaf->value[0]; 1766 1767 /* 1768 * Examine the possibility that the interval fits 1769 * somewhere between the rightmost interval of 1770 * the left neigbour and the first interval of the leaf. 1771 */ 1772 1773 if (page >= right_pg) { 1774 /* Do nothing. */ 1775 } else if (overlaps(page, P2SZ(count), left_pg, 1776 P2SZ(left_cnt))) { 1777 /* The interval intersects with the left interval. */ 1778 return false; 1779 } else if (overlaps(page, P2SZ(count), right_pg, 1780 P2SZ(right_cnt))) { 1781 /* The interval intersects with the right interval. */ 1782 return false; 1783 } else if ((page == left_pg + P2SZ(left_cnt)) && 1784 (page + P2SZ(count) == right_pg)) { 1785 /* 1786 * The interval can be added by merging the two already 1787 * present intervals. 1788 */ 1789 node->value[node->keys - 1] += count + right_cnt; 1790 btree_remove(&area->used_space, right_pg, leaf); 1791 goto success; 1792 } else if (page == left_pg + P2SZ(left_cnt)) { 1793 /* 1794 * The interval can be added by simply growing the left 1795 * interval. 1796 */ 1797 node->value[node->keys - 1] += count; 1798 goto success; 1799 } else if (page + P2SZ(count) == right_pg) { 1800 /* 1801 * The interval can be addded by simply moving base of 1802 * the right interval down and increasing its size 1803 * accordingly. 1804 */ 1805 leaf->value[0] += count; 1806 leaf->key[0] = page; 1807 goto success; 1808 } else { 1809 /* 1810 * The interval is between both neigbouring intervals, 1811 * but cannot be merged with any of them. 1812 */ 1813 btree_insert(&area->used_space, page, (void *) count, 1814 leaf); 1815 goto success; 1816 } 1817 } else if (page < leaf->key[0]) { 1818 uintptr_t right_pg = leaf->key[0]; 1819 size_t right_cnt = (size_t) leaf->value[0]; 1820 1821 /* 1822 * Investigate the border case in which the left neighbour does 1823 * not exist but the interval fits from the left. 1824 */ 1825 1826 if (overlaps(page, P2SZ(count), right_pg, P2SZ(right_cnt))) { 1827 /* The interval intersects with the right interval. */ 1828 return false; 1829 } else if (page + P2SZ(count) == right_pg) { 1830 /* 1831 * The interval can be added by moving the base of the 1832 * right interval down and increasing its size 1833 * accordingly. 1834 */ 1835 leaf->key[0] = page; 1836 leaf->value[0] += count; 1837 goto success; 1838 } else { 1839 /* 1840 * The interval doesn't adjoin with the right interval. 1841 * It must be added individually. 1842 */ 1843 btree_insert(&area->used_space, page, (void *) count, 1844 leaf); 1845 goto success; 1846 } 1847 } 1848 1849 node = btree_leaf_node_right_neighbour(&area->used_space, leaf); 1850 if (node) { 1851 uintptr_t left_pg = leaf->key[leaf->keys - 1]; 1852 uintptr_t right_pg = node->key[0]; 1853 size_t left_cnt = (size_t) leaf->value[leaf->keys - 1]; 1854 size_t right_cnt = (size_t) node->value[0]; 1855 1856 /* 1857 * Examine the possibility that the interval fits 1858 * somewhere between the leftmost interval of 1859 * the right neigbour and the last interval of the leaf. 1860 */ 1861 1862 if (page < left_pg) { 1863 /* Do nothing. */ 1864 } else if (overlaps(page, P2SZ(count), left_pg, 1865 P2SZ(left_cnt))) { 1866 /* The interval intersects with the left interval. */ 1867 return false; 1868 } else if (overlaps(page, P2SZ(count), right_pg, 1869 P2SZ(right_cnt))) { 1870 /* The interval intersects with the right interval. */ 1871 return false; 1872 } else if ((page == left_pg + P2SZ(left_cnt)) && 1873 (page + P2SZ(count) == right_pg)) { 1874 /* 1875 * The interval can be added by merging the two already 1876 * present intervals. 1877 */ 1878 leaf->value[leaf->keys - 1] += count + right_cnt; 1879 btree_remove(&area->used_space, right_pg, node); 1880 goto success; 1881 } else if (page == left_pg + P2SZ(left_cnt)) { 1882 /* 1883 * The interval can be added by simply growing the left 1884 * interval. 1885 */ 1886 leaf->value[leaf->keys - 1] += count; 1887 goto success; 1888 } else if (page + P2SZ(count) == right_pg) { 1889 /* 1890 * The interval can be addded by simply moving base of 1891 * the right interval down and increasing its size 1892 * accordingly. 1893 */ 1894 node->value[0] += count; 1895 node->key[0] = page; 1896 goto success; 1897 } else { 1898 /* 1899 * The interval is between both neigbouring intervals, 1900 * but cannot be merged with any of them. 1901 */ 1902 btree_insert(&area->used_space, page, (void *) count, 1903 leaf); 1904 goto success; 1905 } 1906 } else if (page >= leaf->key[leaf->keys - 1]) { 1907 uintptr_t left_pg = leaf->key[leaf->keys - 1]; 1908 size_t left_cnt = (size_t) leaf->value[leaf->keys - 1]; 1909 1910 /* 1911 * Investigate the border case in which the right neighbour 1912 * does not exist but the interval fits from the right. 1913 */ 1914 1915 if (overlaps(page, P2SZ(count), left_pg, P2SZ(left_cnt))) { 1916 /* The interval intersects with the left interval. */ 1917 return false; 1918 } else if (left_pg + P2SZ(left_cnt) == page) { 1919 /* 1920 * The interval can be added by growing the left 1921 * interval. 1922 */ 1923 leaf->value[leaf->keys - 1] += count; 1924 goto success; 1925 } else { 1926 /* 1927 * The interval doesn't adjoin with the left interval. 1928 * It must be added individually. 1929 */ 1930 btree_insert(&area->used_space, page, (void *) count, 1931 leaf); 1932 goto success; 1933 } 1934 } 1935 1936 /* 1937 * Note that if the algorithm made it thus far, the interval can fit 1938 * only between two other intervals of the leaf. The two border cases 1939 * were already resolved. 1940 */ 1941 btree_key_t i; 1942 for (i = 1; i < leaf->keys; i++) { 1943 if (page < leaf->key[i]) { 1944 uintptr_t left_pg = leaf->key[i - 1]; 1945 uintptr_t right_pg = leaf->key[i]; 1946 size_t left_cnt = (size_t) leaf->value[i - 1]; 1947 size_t right_cnt = (size_t) leaf->value[i]; 1948 1949 /* 1950 * The interval fits between left_pg and right_pg. 1951 */ 1952 1953 if (overlaps(page, P2SZ(count), left_pg, 1954 P2SZ(left_cnt))) { 1955 /* 1956 * The interval intersects with the left 1957 * interval. 1958 */ 1959 return false; 1960 } else if (overlaps(page, P2SZ(count), right_pg, 1961 P2SZ(right_cnt))) { 1962 /* 1963 * The interval intersects with the right 1964 * interval. 1965 */ 1966 return false; 1967 } else if ((page == left_pg + P2SZ(left_cnt)) && 1968 (page + P2SZ(count) == right_pg)) { 1969 /* 1970 * The interval can be added by merging the two 1971 * already present intervals. 1972 */ 1973 leaf->value[i - 1] += count + right_cnt; 1974 btree_remove(&area->used_space, right_pg, leaf); 1975 goto success; 1976 } else if (page == left_pg + P2SZ(left_cnt)) { 1977 /* 1978 * The interval can be added by simply growing 1979 * the left interval. 1980 */ 1981 leaf->value[i - 1] += count; 1982 goto success; 1983 } else if (page + P2SZ(count) == right_pg) { 1984 /* 1985 * The interval can be addded by simply moving 1986 * base of the right interval down and 1987 * increasing its size accordingly. 1988 */ 1989 leaf->value[i] += count; 1990 leaf->key[i] = page; 1991 goto success; 1992 } else { 1993 /* 1994 * The interval is between both neigbouring 1995 * intervals, but cannot be merged with any of 1996 * them. 1997 */ 1998 btree_insert(&area->used_space, page, 1999 (void *) count, leaf); 2000 goto success; 2001 } 2002 } 2003 } 2004 2005 panic("Inconsistency detected while adding %zu pages of used " 2006 "space at %p.", count, (void *) page); 2007 2008 success: 2009 area->resident += count; 2010 return true; 2011 } 2012 2013 /** Mark portion of address space area as unused. 2014 * 2015 * The address space area must be already locked. 2016 * 2017 * @param area Address space area. 2018 * @param page First page to be marked. 2019 * @param count Number of page to be marked. 2020 * 2021 * @return False on failure or true on success. 2022 * 2023 */ 2024 bool used_space_remove(as_area_t *area, uintptr_t page, size_t count) 2025 { 2026 assert(mutex_locked(&area->lock)); 2027 assert(IS_ALIGNED(page, PAGE_SIZE)); 2028 assert(count); 2029 2030 btree_node_t *leaf; 2031 size_t pages = (size_t) btree_search(&area->used_space, page, &leaf); 2032 if (pages) { 2033 /* 2034 * We are lucky, page is the beginning of some interval. 2035 */ 2036 if (count > pages) { 2037 return false; 2038 } else if (count == pages) { 2039 btree_remove(&area->used_space, page, leaf); 2040 goto success; 2041 } else { 2042 /* 2043 * Find the respective interval. 2044 * Decrease its size and relocate its start address. 2045 */ 2046 btree_key_t i; 2047 for (i = 0; i < leaf->keys; i++) { 2048 if (leaf->key[i] == page) { 2049 leaf->key[i] += P2SZ(count); 2050 leaf->value[i] -= count; 2051 goto success; 2052 } 2053 } 2054 2055 goto error; 2056 } 2057 } 2058 2059 btree_node_t *node = btree_leaf_node_left_neighbour(&area->used_space, 2060 leaf); 2061 if ((node) && (page < leaf->key[0])) { 2062 uintptr_t left_pg = node->key[node->keys - 1]; 2063 size_t left_cnt = (size_t) node->value[node->keys - 1]; 2064 2065 if (overlaps(left_pg, P2SZ(left_cnt), page, P2SZ(count))) { 2066 if (page + P2SZ(count) == left_pg + P2SZ(left_cnt)) { 2067 /* 2068 * The interval is contained in the rightmost 2069 * interval of the left neighbour and can be 2070 * removed by updating the size of the bigger 2071 * interval. 2072 */ 2073 node->value[node->keys - 1] -= count; 2074 goto success; 2075 } else if (page + P2SZ(count) < 2076 left_pg + P2SZ(left_cnt)) { 2077 size_t new_cnt; 2078 2079 /* 2080 * The interval is contained in the rightmost 2081 * interval of the left neighbour but its 2082 * removal requires both updating the size of 2083 * the original interval and also inserting a 2084 * new interval. 2085 */ 2086 new_cnt = ((left_pg + P2SZ(left_cnt)) - 2087 (page + P2SZ(count))) >> PAGE_WIDTH; 2088 node->value[node->keys - 1] -= count + new_cnt; 2089 btree_insert(&area->used_space, page + 2090 P2SZ(count), (void *) new_cnt, leaf); 2091 goto success; 2092 } 2093 } 2094 2055 2095 return false; 2056 2057 /* Check if A is adjacent to the new interval */ 2058 adj_a = (a != NULL) && (a->page + P2SZ(a->count) == page); 2059 /* Check if the new interval is adjacent to B*/ 2060 adj_b = (b != NULL) && page + P2SZ(count) == b->page; 2061 2062 if (adj_a && adj_b) { 2063 /* Fuse into a single interval */ 2064 a->count += count + b->count; 2065 used_space_remove_ival(b); 2066 } else if (adj_a) { 2067 /* Append to A */ 2068 a->count += count; 2069 } else if (adj_b) { 2070 /* Prepend to B */ 2071 b->page = page; 2072 b->count += count; 2073 } else { 2074 /* Create new interval */ 2075 ival = slab_alloc(used_space_ival_cache, 0); 2076 ival->used_space = used_space; 2077 odlink_initialize(&ival->lused_space); 2078 ival->page = page; 2079 ival->count = count; 2080 2081 odict_insert(&ival->lused_space, &used_space->ivals, 2082 NULL); 2083 } 2084 2085 used_space->pages += count; 2096 } else if (page < leaf->key[0]) 2097 return false; 2098 2099 if (page > leaf->key[leaf->keys - 1]) { 2100 uintptr_t left_pg = leaf->key[leaf->keys - 1]; 2101 size_t left_cnt = (size_t) leaf->value[leaf->keys - 1]; 2102 2103 if (overlaps(left_pg, P2SZ(left_cnt), page, P2SZ(count))) { 2104 if (page + P2SZ(count) == left_pg + P2SZ(left_cnt)) { 2105 /* 2106 * The interval is contained in the rightmost 2107 * interval of the leaf and can be removed by 2108 * updating the size of the bigger interval. 2109 */ 2110 leaf->value[leaf->keys - 1] -= count; 2111 goto success; 2112 } else if (page + P2SZ(count) < left_pg + 2113 P2SZ(left_cnt)) { 2114 size_t new_cnt; 2115 2116 /* 2117 * The interval is contained in the rightmost 2118 * interval of the leaf but its removal 2119 * requires both updating the size of the 2120 * original interval and also inserting a new 2121 * interval. 2122 */ 2123 new_cnt = ((left_pg + P2SZ(left_cnt)) - 2124 (page + P2SZ(count))) >> PAGE_WIDTH; 2125 leaf->value[leaf->keys - 1] -= count + new_cnt; 2126 btree_insert(&area->used_space, page + 2127 P2SZ(count), (void *) new_cnt, leaf); 2128 goto success; 2129 } 2130 } 2131 2132 return false; 2133 } 2134 2135 /* 2136 * The border cases have been already resolved. 2137 * Now the interval can be only between intervals of the leaf. 2138 */ 2139 btree_key_t i; 2140 for (i = 1; i < leaf->keys - 1; i++) { 2141 if (page < leaf->key[i]) { 2142 uintptr_t left_pg = leaf->key[i - 1]; 2143 size_t left_cnt = (size_t) leaf->value[i - 1]; 2144 2145 /* 2146 * Now the interval is between intervals corresponding 2147 * to (i - 1) and i. 2148 */ 2149 if (overlaps(left_pg, P2SZ(left_cnt), page, 2150 P2SZ(count))) { 2151 if (page + P2SZ(count) == 2152 left_pg + P2SZ(left_cnt)) { 2153 /* 2154 * The interval is contained in the 2155 * interval (i - 1) of the leaf and can 2156 * be removed by updating the size of 2157 * the bigger interval. 2158 */ 2159 leaf->value[i - 1] -= count; 2160 goto success; 2161 } else if (page + P2SZ(count) < 2162 left_pg + P2SZ(left_cnt)) { 2163 size_t new_cnt; 2164 2165 /* 2166 * The interval is contained in the 2167 * interval (i - 1) of the leaf but its 2168 * removal requires both updating the 2169 * size of the original interval and 2170 * also inserting a new interval. 2171 */ 2172 new_cnt = ((left_pg + P2SZ(left_cnt)) - 2173 (page + P2SZ(count))) >> 2174 PAGE_WIDTH; 2175 leaf->value[i - 1] -= count + new_cnt; 2176 btree_insert(&area->used_space, page + 2177 P2SZ(count), (void *) new_cnt, 2178 leaf); 2179 goto success; 2180 } 2181 } 2182 2183 return false; 2184 } 2185 } 2186 2187 error: 2188 panic("Inconsistency detected while removing %zu pages of used " 2189 "space from %p.", count, (void *) page); 2190 2191 success: 2192 area->resident -= count; 2086 2193 return true; 2087 2194 }
Note:
See TracChangeset
for help on using the changeset viewer.
