Index: sys/vm/vm_map.c =================================================================== --- sys/vm/vm_map.c +++ sys/vm/vm_map.c @@ -923,10 +923,20 @@ /* 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( \ + (root->left != NULL) ? \ + root->left->max_free : \ + root->start - y->end, \ + (root->right != NULL) ? \ + root->right->max_free : \ + rlist->start - root->end); \ root = y; \ y = root->left; \ } \ + root->max_free = (root->right != NULL) ? \ + root->right->max_free : \ + rlist->start - root->end; \ /* Put root on rlist. */ \ root->left = rlist; \ rlist = root; \ @@ -939,10 +949,20 @@ /* 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( \ + (root->left != NULL) ? \ + root->left->max_free : \ + root->start - llist->end, \ + (root->right != NULL) ? \ + root->right->max_free : \ + y->start - root->end); \ root = y; \ y = root->right; \ } \ + root->max_free = (root->left != NULL) ? \ + root->left->max_free : \ + root->start - llist->end; \ /* Put root on llist. */ \ root->right = llist; \ llist = root; \ @@ -959,13 +979,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 +996,8 @@ } else break; } - *out_llist = llist; - *out_rlist = rlist; + *io_llist = llist; + *io_rlist = rlist; return (root); } @@ -1015,18 +1035,31 @@ vm_map_entry_t ltree, vm_map_entry_t rtree) { vm_map_entry_t y; + vm_size_t max_free; - while (llist != NULL) { + if ((llist->eflags & MAP_ENTRY_HEADER) == 0) + max_free = (ltree != NULL) ? ltree->max_free : + root->start - llist->end; + while ((llist->eflags & MAP_ENTRY_HEADER) == 0) { y = llist->right; llist->right = ltree; - vm_map_entry_set_max_free(llist); + if (llist->max_free < max_free) + llist->max_free = max_free; + else + max_free = llist->max_free; ltree = llist; llist = y; } - while (rlist != NULL) { + if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) + max_free = (rtree != NULL) ? rtree->max_free : + rlist->start - root->end; + while ((rlist->eflags & MAP_ENTRY_HEADER) == 0) { y = rlist->left; rlist->left = rtree; - vm_map_entry_set_max_free(rlist); + if (rlist->max_free < max_free) + rlist->max_free = max_free; + else + max_free = rlist->max_free; rtree = rlist; rlist = y; } @@ -1059,14 +1092,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 +1108,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. @@ -1105,13 +1139,14 @@ "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); + llist = rlist = &map->header; + root = vm_map_splay_split(entry->start, 0, map->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 = llist; + entry->next = rlist; entry->prev->next = entry->next->prev = entry; root = vm_map_splay_merge(entry, llist, rlist, NULL, NULL); map->root = entry; @@ -1132,12 +1167,8 @@ 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); + 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 +1193,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,6 +1205,9 @@ 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); @@ -1185,31 +1219,41 @@ } /* - * vm_map_entry_resize_free: + * vm_map_entry_resize: * - * Recompute the amount of free space following a modified vm_map_entry - * and propagate those values up the tree. Call this function after - * resizing a map entry in-place by changing the end value, without a + * Recompute the amount of free space around a modified vm_map_entry and + * propagate those values up the tree. Call this function to resize a + * map entry in-place by changing the start and end values, without a * call to vm_map_entry_link() or _unlink(). * * 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(vm_map_t map, vm_map_entry_t entry, + vm_offset_t start, vm_offset_t end) { 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); + 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; + ("vm_map_entry_resize: resize_free object not mapped")); + if (entry->start != start) { + vm_map_splay_findprev(root, &llist); + root->left = NULL; + entry->offset += start - entry->start; + entry->start = start; + } + if (entry->end != end) { + vm_map_splay_findnext(root, &rlist); + root->right = NULL; + entry->end = end; + } map->root = vm_map_splay_merge(root, llist, rlist, root->left, root->right); VM_MAP_ASSERT_CONSISTENT(map); - CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map, + CTR3(KTR_VM, "vm_map_entry_resize: map %p, nentries %d, entry %p", map, map->nentries, entry); } @@ -1253,7 +1297,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 +1472,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(map, prev_entry, + prev_entry->start, end); vm_map_simplify_entry(map, prev_entry); return (KERN_SUCCESS); } @@ -1538,11 +1583,11 @@ * 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); + 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; @@ -2068,8 +2113,7 @@ *new_entry = *entry; new_entry->end = start; - entry->offset += (start - entry->start); - entry->start = start; + vm_map_entry_resize(map, entry, start, entry->end); if (new_entry->cred != NULL) crhold(entry->cred); @@ -2150,7 +2194,8 @@ new_entry = vm_map_entry_create(map); *new_entry = *entry; - new_entry->start = entry->end = end; + vm_map_entry_resize(map, entry, entry->start, end); + new_entry->start = end; new_entry->offset += (end - entry->start); if (new_entry->cred != NULL) crhold(entry->cred); @@ -4181,25 +4226,22 @@ 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(map, gap_entry, + gap_entry->start, gap_entry->end - 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(map, gap_entry, + gap_entry->start, gap_entry->end + grow_amount); } else { grow_start = stack_entry->end; cred = stack_entry->cred; @@ -4213,13 +4255,16 @@ 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(map, stack_entry, + stack_entry->start, + stack_entry->end + grow_amount); + } else { gap_entry->start += grow_amount; - stack_entry->end += grow_amount; + stack_entry->end += grow_amount; + } map->size += grow_amount; - vm_map_entry_resize_free(map, stack_entry); rv = KERN_SUCCESS; } else rv = KERN_FAILURE;