Index: sys/vm/vm_map.c =================================================================== --- sys/vm/vm_map.c +++ sys/vm/vm_map.c @@ -898,23 +898,24 @@ } /* - * vm_map_entry_set_max_free: + * maxfree_{left,right} * - * Set the max_free field in a vm_map_entry. + * Compute the size of the largest free gap between two entries, + * one the root of a tree and the other the entry that lies on + * the other side of the tree. */ -static inline void -vm_map_entry_set_max_free(vm_map_entry_t entry) -{ - vm_map_entry_t child; - vm_size_t max_left, max_right; - child = entry->left; - max_left = (child != NULL) ? child->max_free : - entry->start - entry->prev->end; - child = entry->right; - max_right = (child != NULL) ? child->max_free : - entry->next->start - entry->end; - entry->max_free = MAX(max_left, max_right); +static inline size_t +maxfree_left(vm_map_entry_t root, vm_map_entry_t y) +{ + return (root->left != NULL ? + root->left->max_free : root->start - y->end); +} +static inline size_t +maxfree_right(vm_map_entry_t root, vm_map_entry_t y) +{ + return (root->right != NULL ? + root->right->max_free : y->start - root->end); } #define SPLAY_LEFT_STEP(root, y, rlist, test) do { \ @@ -923,11 +924,15 @@ /* Rotate right and make y root. */ \ root->left = y->right; \ y->right = root; \ - vm_map_entry_set_max_free(root); \ + if (root->max_free == y->max_free) \ + root->max_free = MAX( \ + maxfree_left(root, y), \ + maxfree_right(root, rlist));\ root = y; \ y = root->left; \ } \ /* Put root on rlist. */ \ + root->max_free = maxfree_right(root, rlist); \ root->left = rlist; \ rlist = root; \ root = y; \ @@ -939,11 +944,15 @@ /* Rotate left and make y root. */ \ root->right = y->left; \ y->left = root; \ - vm_map_entry_set_max_free(root); \ + if (root->max_free == y->max_free) \ + root->max_free = MAX( \ + maxfree_left(root, llist), \ + maxfree_right(root, y)); \ root = y; \ y = root->right; \ } \ /* Put root on llist. */ \ + root->max_free = maxfree_left(root, llist); \ root->right = llist; \ llist = root; \ root = y; \ @@ -959,13 +968,13 @@ */ static vm_map_entry_t vm_map_splay_split(vm_offset_t addr, vm_size_t length, - vm_map_entry_t root, vm_map_entry_t *out_llist, vm_map_entry_t *out_rlist) + vm_map_entry_t root, vm_map_entry_t *io_llist, vm_map_entry_t *io_rlist) { vm_map_entry_t llist, rlist; vm_map_entry_t y; - llist = NULL; - rlist = NULL; + llist = *io_llist; + rlist = *io_rlist; while (root != NULL && root->max_free >= length) { if (addr < root->start) { SPLAY_LEFT_STEP(root, y, rlist, @@ -976,8 +985,8 @@ } else break; } - *out_llist = llist; - *out_rlist = rlist; + *io_llist = llist; + *io_rlist = rlist; return (root); } @@ -1009,36 +1018,43 @@ * Walk back up the two spines, flip the pointers and set max_free. The * subtrees of the root go at the bottom of llist and rlist. */ -static vm_map_entry_t +static void vm_map_splay_merge(vm_map_entry_t root, - vm_map_entry_t llist, vm_map_entry_t rlist, - vm_map_entry_t ltree, vm_map_entry_t rtree) + vm_map_entry_t llist, vm_map_entry_t rlist) { - vm_map_entry_t y; + vm_map_entry_t tree, y; + vm_size_t max_free; - while (llist != NULL) { + tree = root->left; + if ((llist->eflags & MAP_ENTRY_HEADER) == 0) + max_free = maxfree_left(root, llist); + while ((llist->eflags & MAP_ENTRY_HEADER) == 0) { y = llist->right; - llist->right = ltree; - vm_map_entry_set_max_free(llist); - ltree = llist; + llist->right = tree; + if (llist->max_free < max_free) + llist->max_free = max_free; + else + max_free = llist->max_free; + tree = llist; llist = y; } - while (rlist != NULL) { + root->left = tree; + tree = root->right; + if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) + max_free = maxfree_right(root, rlist); + while ((rlist->eflags & MAP_ENTRY_HEADER) == 0) { y = rlist->left; - rlist->left = rtree; - vm_map_entry_set_max_free(rlist); - rtree = rlist; + rlist->left = tree; + if (rlist->max_free < max_free) + rlist->max_free = max_free; + else + max_free = rlist->max_free; + tree = rlist; rlist = y; } - - /* - * Final assembly: add ltree and rtree as subtrees of root. - */ - root->left = ltree; - root->right = rtree; - vm_map_entry_set_max_free(root); - - return (root); + root->right = tree; + root->max_free = + MAX(maxfree_left(root, llist), maxfree_right(root, rlist)); } /* @@ -1059,14 +1075,15 @@ * Returns: the new root. */ static vm_map_entry_t -vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root) +vm_map_entry_splay(vm_offset_t addr, vm_map_t map) { - vm_map_entry_t llist, rlist; + vm_map_entry_t llist, rlist, root; - root = vm_map_splay_split(addr, 0, root, &llist, &rlist); + llist = rlist = &map->header; + root = vm_map_splay_split(addr, 0, map->root, &llist, &rlist); if (root != NULL) { /* do nothing */ - } else if (llist != NULL) { + } else if ((llist->eflags & MAP_ENTRY_HEADER) == 0) { /* * Recover the greatest node in the left * subtree and make it the root. @@ -1074,7 +1091,7 @@ root = llist; llist = root->right; root->right = NULL; - } else if (rlist != NULL) { + } else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) { /* * Recover the least node in the right * subtree and make it the root. @@ -1086,8 +1103,8 @@ /* There is no root. */ return (NULL); } - return (vm_map_splay_merge(root, llist, rlist, - root->left, root->right)); + vm_map_splay_merge(root, llist, rlist); + return (root); } /* @@ -1099,21 +1116,42 @@ vm_map_entry_link(vm_map_t map, vm_map_entry_t entry) { - vm_map_entry_t llist, rlist, root; + vm_map_entry_t llist, rlist, root, y; CTR3(KTR_VM, "vm_map_entry_link: map %p, nentries %d, entry %p", map, map->nentries, entry); VM_MAP_ASSERT_LOCKED(map); + VM_MAP_ASSERT_CONSISTENT(map); map->nentries++; - root = map->root; - root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); - KASSERT(root == NULL, - ("vm_map_entry_link: link object already mapped")); - entry->prev = (llist == NULL) ? &map->header : llist; - entry->next = (rlist == NULL) ? &map->header : rlist; - entry->prev->next = entry->next->prev = entry; - root = vm_map_splay_merge(entry, llist, rlist, NULL, NULL); + llist = rlist = &map->header; + root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist); + if (root == NULL) + entry->left = entry->right = NULL; + else if (entry->start == root->start) { + KASSERT(entry->end < root->end, + ("vm_map_entry_link: new entry overflows")); + entry->right = NULL; + entry->left = root->left; + root->left = NULL; + root->offset += (entry->end - root->start); + root->start = entry->end; + SPLAY_LEFT_STEP(root, y, rlist, false); + } else if (root->end == entry->end) { + KASSERT(entry->start > root->start, + ("vm_map_entry_link: new entry overflows")); + entry->left = NULL; + entry->right = root->right; + root->right = NULL; + root->end = entry->start; + SPLAY_RIGHT_STEP(root, y, llist, false); + } else + KASSERT(true, + ("vm_map_entry_link: mismatched endpoints")); + entry->prev = llist; + entry->next = rlist; + llist->next = rlist->prev = entry; + vm_map_splay_merge(entry, llist, rlist); map->root = entry; VM_MAP_ASSERT_CONSISTENT(map); } @@ -1132,12 +1170,9 @@ vm_map_entry_t llist, rlist, root, y; VM_MAP_ASSERT_LOCKED(map); - llist = entry->prev; - rlist = entry->next; - llist->next = rlist; - rlist->prev = llist; - root = map->root; - root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); + VM_MAP_ASSERT_CONSISTENT(map); + llist = rlist = &map->header; + root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist); KASSERT(root != NULL, ("vm_map_entry_unlink: unlink object not mapped")); @@ -1162,11 +1197,11 @@ case UNLINK_MERGE_NONE: vm_map_splay_findprev(root, &llist); vm_map_splay_findnext(root, &rlist); - if (llist != NULL) { + if ((llist->eflags & MAP_ENTRY_HEADER) == 0) { root = llist; llist = root->right; root->right = NULL; - } else if (rlist != NULL) { + } else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) { root = rlist; rlist = root->left; root->left = NULL; @@ -1174,9 +1209,11 @@ root = NULL; break; } + y = entry->next; + y->prev = entry->prev; + y->prev->next = y; if (root != NULL) - root = vm_map_splay_merge(root, llist, rlist, - root->left, root->right); + vm_map_splay_merge(root, llist, rlist); map->root = root; VM_MAP_ASSERT_CONSISTENT(map); map->nentries--; @@ -1195,19 +1232,21 @@ * The map must be locked, and leaves it so. */ static void -vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry) +vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry, size_t grow_amount) { vm_map_entry_t llist, rlist, root; VM_MAP_ASSERT_LOCKED(map); - root = map->root; - root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist); + VM_MAP_ASSERT_CONSISTENT(map); + llist = rlist = &map->header; + root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist); KASSERT(root != NULL, ("vm_map_entry_resize_free: resize_free object not mapped")); vm_map_splay_findnext(root, &rlist); root->right = NULL; - map->root = vm_map_splay_merge(root, llist, rlist, - root->left, root->right); + entry->end += grow_amount; + vm_map_splay_merge(root, llist, rlist); + map->root = root; VM_MAP_ASSERT_CONSISTENT(map); CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map, map->nentries, entry); @@ -1253,7 +1292,8 @@ * change the map. Thus, the map's timestamp need not change * on a temporary upgrade. */ - map->root = cur = vm_map_entry_splay(address, cur); + VM_MAP_ASSERT_CONSISTENT(map); + map->root = cur = vm_map_entry_splay(address, map); VM_MAP_ASSERT_CONSISTENT(map); if (!locked) sx_downgrade(&map->lock); @@ -1427,8 +1467,8 @@ prev_entry)); if ((prev_entry->eflags & MAP_ENTRY_GUARD) == 0) map->size += end - prev_entry->end; - prev_entry->end = end; - vm_map_entry_resize_free(map, prev_entry); + vm_map_entry_resize_free(map, prev_entry, + end - prev_entry->end); vm_map_simplify_entry(map, prev_entry); return (KERN_SUCCESS); } @@ -1538,11 +1578,12 @@ * After splay, if start comes before root node, then there * must be a gap from start to the root. */ - root = vm_map_splay_split(start, length, map->root, - &llist, &rlist); + VM_MAP_ASSERT_CONSISTENT(map); + llist = rlist = &map->header; + root = vm_map_splay_split(start, length, map->root, &llist, &rlist); if (root != NULL) start = root->end; - else if (rlist != NULL) { + else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) { root = rlist; rlist = root->left; root->left = NULL; @@ -1551,8 +1592,8 @@ llist = root->right; root->right = NULL; } - map->root = vm_map_splay_merge(root, llist, rlist, - root->left, root->right); + vm_map_splay_merge(root, llist, rlist); + map->root = root; VM_MAP_ASSERT_CONSISTENT(map); if (start + length <= root->start) return (start); @@ -1573,39 +1614,32 @@ /* * Splay for the least large-enough gap in the right subtree. */ - llist = NULL; - rlist = NULL; + llist = rlist = &map->header; for (left_length = 0; ; - left_length = root->left != NULL ? - root->left->max_free : root->start - llist->end) { + left_length = maxfree_left(root, llist)) { if (length <= left_length) SPLAY_LEFT_STEP(root, y, rlist, - length <= (y->left != NULL ? - y->left->max_free : y->start - llist->end)); + length <= maxfree_left(y, llist)); else SPLAY_RIGHT_STEP(root, y, llist, - length > (y->left != NULL ? - y->left->max_free : y->start - root->end)); + length > maxfree_left(y, root)); if (root == NULL) break; } root = llist; llist = root->right; - if ((y = rlist) == NULL) + if (rlist == &map->header) root->right = NULL; else { + y = rlist; rlist = y->left; y->left = NULL; - root->right = y->right; - } - root = vm_map_splay_merge(root, llist, rlist, - root->left, root->right); - if (y != NULL) { - y->right = root->right; - vm_map_entry_set_max_free(y); + vm_map_splay_merge(y, &map->header, rlist); + y->max_free = MAX(y->start - root->end, + maxfree_right(y, &map->header)); root->right = y; - vm_map_entry_set_max_free(root); } + vm_map_splay_merge(root, llist, &map->header); map->root = root; VM_MAP_ASSERT_CONSISTENT(map); return (root->end); @@ -2068,8 +2102,6 @@ *new_entry = *entry; new_entry->end = start; - entry->offset += (start - entry->start); - entry->start = start; if (new_entry->cred != NULL) crhold(entry->cred); @@ -2150,7 +2182,7 @@ new_entry = vm_map_entry_create(map); *new_entry = *entry; - new_entry->start = entry->end = end; + new_entry->start = end; new_entry->offset += (end - entry->start); if (new_entry->cred != NULL) crhold(entry->cred); @@ -4181,25 +4213,20 @@ gap_deleted = true; } else { MPASS(gap_entry->start < gap_entry->end - grow_amount); - gap_entry->end -= grow_amount; - vm_map_entry_resize_free(map, gap_entry); + vm_map_entry_resize_free(map, gap_entry, -grow_amount); gap_deleted = false; } rv = vm_map_insert(map, NULL, 0, grow_start, grow_start + grow_amount, stack_entry->protection, stack_entry->max_protection, MAP_STACK_GROWS_DOWN); - if (rv != KERN_SUCCESS) { - if (gap_deleted) { - rv1 = vm_map_insert(map, NULL, 0, gap_start, - gap_end, VM_PROT_NONE, VM_PROT_NONE, - MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN); - MPASS(rv1 == KERN_SUCCESS); - } else { - gap_entry->end += grow_amount; - vm_map_entry_resize_free(map, gap_entry); - } - } + if (rv != KERN_SUCCESS && gap_deleted) { + rv1 = vm_map_insert(map, NULL, 0, gap_start, + gap_end, VM_PROT_NONE, VM_PROT_NONE, + MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN); + MPASS(rv1 == KERN_SUCCESS); + } else if (rv != KERN_SUCCESS) + vm_map_entry_resize_free(map, gap_entry, grow_amount); } else { grow_start = stack_entry->end; cred = stack_entry->cred; @@ -4213,13 +4240,14 @@ stack_entry->offset, (vm_size_t)(stack_entry->end - stack_entry->start), (vm_size_t)grow_amount, cred != NULL)) { - if (gap_entry->start + grow_amount == gap_entry->end) + if (gap_entry->start + grow_amount == gap_entry->end) { vm_map_entry_delete(map, gap_entry); - else + vm_map_entry_resize_free(map, stack_entry, grow_amount); + } else { gap_entry->start += grow_amount; - stack_entry->end += grow_amount; + stack_entry += grow_amount; + } map->size += grow_amount; - vm_map_entry_resize_free(map, stack_entry); rv = KERN_SUCCESS; } else rv = KERN_FAILURE;