* vm_map_findspace: * * Find the first fit (lowest VM address) for "length" free bytes * beginning at address >= start in the given map. * * In a vm_map_entry, "max_free" is the maximum amount of * contiguous free space between an entry in its subtree and a * neighbor of that entry. This allows finding a free region in * one path down the tree, so O(log n) amortized with splay * trees.
| 1881 | * vm_map_max(map)-length+1 if insufficient space. |
| 1882 | */ |
| 1883 | vm_offset_t |
| 1884 | vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length) |
| 1885 | { |
| 1886 | vm_map_entry_t header, llist, rlist, root, y; |
| 1887 | vm_size_t left_length, max_free_left, max_free_right; |
| 1888 | vm_offset_t gap_end; |
| 1889 | |
| 1890 | VM_MAP_ASSERT_LOCKED(map); |
| 1891 | |
| 1892 | /* |
| 1893 | * Request must fit within min/max VM address and must avoid |
| 1894 | * address wrap. |
| 1895 | */ |
| 1896 | start = MAX(start, vm_map_min(map)); |
| 1897 | if (start >= vm_map_max(map) || length > vm_map_max(map) - start) |
| 1898 | return (vm_map_max(map) - length + 1); |
| 1899 | |
| 1900 | /* Empty tree means wide open address space. */ |
| 1901 | if (map->root == NULL) |
| 1902 | return (start); |
| 1903 | |
| 1904 | /* |
| 1905 | * After splay_split, if start is within an entry, push it to the start |
| 1906 | * of the following gap. If rlist is at the end of the gap containing |
| 1907 | * start, save the end of that gap in gap_end to see if the gap is big |
| 1908 | * enough; otherwise set gap_end to start skip gap-checking and move |
| 1909 | * directly to a search of the right subtree. |
| 1910 | */ |
| 1911 | header = &map->header; |
| 1912 | root = vm_map_splay_split(map, start, length, &llist, &rlist); |
| 1913 | gap_end = rlist->start; |
| 1914 | if (root != NULL) { |
| 1915 | start = root->end; |
| 1916 | if (root->right != rlist) |
| 1917 | gap_end = start; |
| 1918 | max_free_left = vm_map_splay_merge_left(header, root, llist); |
| 1919 | max_free_right = vm_map_splay_merge_right(header, root, rlist); |
| 1920 | } else if (rlist != header) { |
| 1921 | root = rlist; |
| 1922 | rlist = root->left; |
| 1923 | max_free_left = vm_map_splay_merge_pred(header, root, llist); |
| 1924 | max_free_right = vm_map_splay_merge_right(header, root, rlist); |
| 1925 | } else { |
| 1926 | root = llist; |
| 1927 | llist = root->right; |
| 1928 | max_free_left = vm_map_splay_merge_left(header, root, llist); |
| 1929 | max_free_right = vm_map_splay_merge_succ(header, root, rlist); |
| 1930 | } |
| 1931 | root->max_free = vm_size_max(max_free_left, max_free_right); |
| 1932 | map->root = root; |
| 1933 | VM_MAP_ASSERT_CONSISTENT(map); |
| 1934 | if (length <= gap_end - start) |
| 1935 | return (start); |
| 1936 | |
| 1937 | /* With max_free, can immediately tell if no solution. */ |
| 1938 | if (root->right == header || length > root->right->max_free) |
| 1939 | return (vm_map_max(map) - length + 1); |
| 1940 |
no test coverage detected