Changes in kernel/generic/src/mm/as.c [ca21f1e2:ca4c5596] in mainline
- File:
-
- 1 edited
-
kernel/generic/src/mm/as.c (modified) (19 diffs)
Legend:
- Unmodified
- Added
- Removed
-
kernel/generic/src/mm/as.c
rca21f1e2 rca4c5596 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> … … 89 88 as_operations_t *as_operations = NULL; 90 89 91 /** Slab for as_t objects. 92 * 93 */ 90 /** Cache for as_t objects */ 94 91 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; 95 98 96 99 /** ASID subsystem lock. … … 116 119 static int as_areas_cmp(void *, void *); 117 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 118 129 NO_TRACE static errno_t as_constructor(void *obj, unsigned int flags) 119 130 { … … 138 149 as_cache = slab_cache_create("as_t", sizeof(as_t), 0, 139 150 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); 140 157 141 158 AS_KERNEL = as_create(FLAG_AS_KERNEL); … … 524 541 } 525 542 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 dictionary 548 * @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, or 563 * 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 else 575 return +1; 576 } 577 578 /** Initialize pagemap. 579 * 580 * @param pagemap Pagemap 581 */ 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 Pagemap 592 */ 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 Pagemap 606 * @return First mapping or @c NULL if there is none 607 */ 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 mapping 622 * @return Next mapping or @c NULL if @a cur is the last one 623 */ 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 Pagemap 638 * @param vaddr Virtual address of page 639 * @param rframe Place to store physical frame address 640 * @return EOK on succcess or ENOENT if no mapping found 641 */ 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 Pagemap 662 * @param vaddr Virtual page address 663 * @param frame Physical frame address 664 */ 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 Mapping 681 */ 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 526 688 /** Remove reference to address space area share info. 527 689 * … … 541 703 dealloc = true; 542 704 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); 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); 553 709 } 554 710 … … 561 717 sh_info->backend_shared_data); 562 718 } 563 btree_destroy(&sh_info->pagemap);719 as_pagemap_finalize(&sh_info->pagemap); 564 720 free(sh_info); 565 721 } … … 636 792 area->attributes = attrs; 637 793 area->pages = pages; 638 area->resident = 0;639 794 area->base = *base; 640 795 area->backend = backend; … … 665 820 si->backend_shared_data = NULL; 666 821 si->backend = backend; 667 btree_create(&si->pagemap);822 as_pagemap_initialize(&si->pagemap); 668 823 669 824 area->sh_info = si; … … 689 844 } 690 845 691 btree_create(&area->used_space);846 used_space_initialize(&area->used_space); 692 847 odict_insert(&area->las_areas, &as->as_areas, NULL); 693 848 … … 797 952 798 953 /* 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 /* 799 962 * Remove frames belonging to used space starting from 800 963 * the highest addresses downwards until an overlap with 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. 964 * the resized address space area is found. 804 965 */ 805 966 bool cond = true; 806 967 while (cond) { 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 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) { 831 980 /* 832 * Part of the interval corresponding 833 * to b and c overlaps with the resized 834 * address space area. 981 * The whole interval fits completely 982 * in the resized address space area. 835 983 */ 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."); 984 break; 850 985 } 851 986 852 987 /* 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. 988 * Part of the interval corresponding to b and 989 * c overlaps with the resized address space 990 * area. 862 991 */ 863 992 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)); 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 { 1000 /* 1001 * The interval of used space can be completely 1002 * removed. 1003 */ 1004 used_space_remove_ival(ival); 1005 } 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)); 886 1022 } 887 1023 888 /* 889 * Finish TLB shootdown sequence. 890 */ 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); 1024 page_mapping_remove(as, ptr + P2SZ(i)); 904 1025 } 1026 905 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 906 1046 page_table_unlock(as, false); 907 1047 } else { … … 962 1102 963 1103 page_table_lock(as, false); 964 965 1104 /* 966 1105 * Start TLB shootdown sequence. … … 970 1109 971 1110 /* 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)); 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)); 1000 1132 } 1133 1134 page_mapping_remove(as, ptr + P2SZ(size)); 1001 1135 } 1136 1137 used_space_remove_ival(ival); 1138 ival = used_space_first(&area->used_space); 1002 1139 } 1003 1140 … … 1017 1154 page_table_unlock(as, false); 1018 1155 1019 btree_destroy(&area->used_space); 1020 1156 used_space_finalize(&area->used_space); 1021 1157 area->attributes |= AS_AREA_ATTR_PARTIAL; 1022 1023 1158 sh_info_remove_reference(area->sh_info); 1024 1159 … … 1256 1391 mutex_unlock(&area->sh_info->lock); 1257 1392 1258 /*1259 * Compute total number of used pages in the used_space B+tree1260 */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 1271 1393 /* An array for storing frame numbers */ 1272 uintptr_t *old_frame = malloc(used_pages * sizeof(uintptr_t)); 1394 uintptr_t *old_frame = malloc(area->used_space.pages * 1395 sizeof(uintptr_t)); 1273 1396 if (!old_frame) { 1274 1397 mutex_unlock(&area->lock); … … 1291 1414 size_t frame_idx = 0; 1292 1415 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 } 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)); 1316 1435 } 1436 1437 ival = used_space_next(ival); 1317 1438 } 1318 1439 … … 1344 1465 frame_idx = 0; 1345 1466 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 } 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); 1363 1480 } 1481 1482 ival = used_space_next(ival); 1364 1483 } 1365 1484 … … 1725 1844 } 1726 1845 1846 /** Initialize used space map. 1847 * 1848 * @param used_space Used space map 1849 */ 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 map 1859 */ 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 map 1869 * @return First interval or @c NULL if there are none 1870 */ 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 interval 1884 * @return Next interval or @c NULL if there are none 1885 */ 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 map 1900 * @return First interval or @c NULL if there are none 1901 */ 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 to 1913 * @a ptr. 1914 * 1915 * @param used_space Used space map 1916 * @param ptr Virtual address 1917 * 1918 * @return Used space interval or @c NULL if none matches 1919 */ 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 match 1937 * 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 any 1943 * interval at all, it must match the criteria 1944 */ 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 page 1960 * 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 a 1976 * 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 else 1988 return +1; 1989 } 1990 1991 /** Remove used space interval. 1992 * 1993 * @param ival Used space interval 1994 */ 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 interval 2005 * @param count New number of pages in the interval 2006 */ 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 1727 2016 /** Mark portion of address space area as used. 1728 2017 * 1729 2018 * The address space area must be already locked. 1730 2019 * 1731 * @param area Address space area.1732 * @param page 2020 * @param used_space Used space map 2021 * @param page First page to be marked. 1733 2022 * @param count Number of page to be marked. 1734 2023 * … … 1736 2025 * 1737 2026 */ 1738 bool used_space_insert(as_area_t *area, uintptr_t page, size_t count) 1739 { 1740 assert(mutex_locked(&area->lock)); 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 1741 2036 assert(IS_ALIGNED(page, PAGE_SIZE)); 1742 2037 assert(count); 1743 2038 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 */ 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))) 1750 2051 return false; 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 2052 2053 /* Check for conflict with right interval */ 2054 if (b != NULL && overlaps(page, P2SZ(count), b->page, P2SZ(b->count))) 2095 2055 return false; 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; 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; 2193 2086 return true; 2194 2087 }
Note:
See TracChangeset
for help on using the changeset viewer.
