Page MenuHomeFreeBSD
Differential D23712

Correct use of UMA_ZONE_VM
ClosedPublic
Actions

Authored by jeff on Feb 16 2020, 9:25 AM.
Tags
None
Referenced Files
Unknown Object (File)
Sun, Mar 23, 6:53 AM
Unknown Object (File)
Mon, Mar 10, 2:00 AM
Unknown Object (File)
Sat, Mar 8, 8:12 AM
Unknown Object (File)
Jan 11 2025, 2:05 PM
Unknown Object (File)
Jan 9 2025, 5:55 AM
Unknown Object (File)
Jan 7 2025, 2:30 PM
Unknown Object (File)
Jan 7 2025, 11:39 AM
Unknown Object (File)
Jan 4 2025, 2:00 AM
View All 58 Files
Subscribers
imp

Details

Reviewers
kib
markj
rlibby
Commits
rS358097: Eliminate some unnecessary uses of UMA_ZONE_VM. Only zones involved in
Summary

UMA_ZONE_VM is only for consumers that are involved in the KVA or page allocation path. Setting this restricts layout and prevents the allocation of pages for buckets. It should be used sparingly. It really doesn't have anything to do with low memory handling. If we're low on pages we already will avoid allocating buckets for any zone.

I would actually like it if all zones were able to allocate buckets from pages. It is almost safe on radix for direct map architectures. I may need a per-thread recursion flag to resolve that.

Test Plan

stress2 on amd64. I have asked pho to run on 32bit.

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

jeff created this revision.Feb 16 2020, 9:25 AM
Harbormaster completed remote builds in B29419: Diff 68397.Feb 16 2020, 9:26 AM
jeff edited the summary of this revision. (Show Details)Feb 16 2020, 9:29 AM
jeff edited the test plan for this revision. (Show Details)
jeff added reviewers: kib, markj, rlibby.
jeff set the repository for this revision to rS FreeBSD src repository - subversion.
Herald added a subscriber: imp. · View Herald TranscriptFeb 16 2020, 9:29 AM
jeff added inline comments.Feb 16 2020, 9:36 AM
sys/kern/subr_vmem.c
565 ↗(On Diff #68397)

We don't use this for kernel_vmem

674 ↗(On Diff #68397)

I don't know why this was nofree. We have an allocator that works.

sys/kern/vfs_subr.c
674 ↗(On Diff #68397)

This is nofree for ugly reasons but it does not need to be ZONE_VM.

sys/vm/vm_page.c
1981 ↗(On Diff #68397)

I like this being more explicitly associated with the zalloc. This allows me to loosen the definition of ZONE_VM without making the page cache recurse into itself.

markj accepted this revision.Feb 17 2020, 2:22 PM
markj added inline comments.
sys/kern/vfs_subr.c
674 ↗(On Diff #68397)

Could you add a comment explaining the nofree? I presume it's to ensure that the preallocation doesn't get reclaimed, but I'm not sure.

This revision is now accepted and ready to land.Feb 17 2020, 2:22 PM
jeff added a comment.Feb 17 2020, 2:28 PM

I have tested this off and on for several days without issue.

sys/kern/vfs_subr.c
674 ↗(On Diff #68397)

There is a comment above uma_zcreate() that describes it already.

  • Preallocate enough nodes to support one-per buf so that
  • we can not fail an insert. reassignbuf() callers can not
  • tolerate the insertion failure.

We bdirty()/bundirty() in bufdone() which is an ithread. You would have to do something like pmap does to reclaim pv entries if you really wanted this to work. Since the preallocation happens at boot it's not really contributing to fragmentation. It is unfortunate but we also limit the buf zone to a fraction of memory so it's not as bad as the radix for pages.

markj added inline comments.Feb 17 2020, 2:42 PM
sys/kern/vfs_subr.c
674 ↗(On Diff #68397)

I just mean that that comment doesn't directly explain why it's nofree. It looks like it's referring to the uma_prealloc() call. Someone might presume that we also rely on type-stability of the trie nodes somewhere.

Closed by commit rS358097: Eliminate some unnecessary uses of UMA_ZONE_VM. Only zones involved in (authored by jeff). · Explain WhyFeb 19 2020, 8:17 AM
This revision was automatically updated to reflect the committed changes.
jeff added a commit: rS358097: Eliminate some unnecessary uses of UMA_ZONE_VM. Only zones involved in.

Revision Contents
Changeset List

PathSize
head/
sys/
kern/
7 lines
2 lines
vm/
4 lines
4 lines
2 lines

Diff 68521

View Options

head/sys/kern/subr_vmem.c

Context not available.
static inline void static inline void
vm_map_entry_set_behavior(vm_map_entry_t entry, u_char behavior) vm_map_entry_set_behavior(vm_map_entry_t entry, u_char behavior)
{ {
entry->eflags = (entry->eflags & ~MAP_ENTRY_BEHAV_MASK) | entry->eflags = (entry->eflags & ~MAP_ENTRY_BEHAV_MASK) |
(behavior & MAP_ENTRY_BEHAV_MASK); (behavior & MAP_ENTRY_BEHAV_MASK);
} }
/* /*
* vm_map_entry_set_max_free: * vm_map_entry_set_max_free:
* *
* Set the max_free field in a vm_map_entry. * Set the max_free field in a vm_map_entry.
*/ */
static inline void static inline void
vm_map_entry_set_max_free(vm_map_entry_t entry) vm_map_entry_set_max_free(vm_map_entry_t entry)
{ {
vm_map_entry_t child;
entry->max_free = entry->adj_free; vm_size_t max_left, max_right;
if (entry->left != NULL && entry->left->max_free > entry->max_free)
entry->max_free = entry->left->max_free; child = entry->left;
if (entry->right != NULL && entry->right->max_free > entry->max_free) max_left = (child != NULL) ? child->max_free :
entry->max_free = entry->right->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);
} }
/* /*
* vm_map_entry_splay: * Walk down the tree until we find addr or a NULL pointer where addr would go,
* * breaking off left and right subtrees of nodes less than, or greater than
* The Sleator and Tarjan top-down splay algorithm with the * addr. llist and rlist are the two sides in reverse order (bottom-up), with
* following variation. Max_free must be computed bottom-up, so * llist linked by the right pointer and rlist linked by the left pointer in the
* on the downward pass, maintain the left and right spines in * vm_map_entry.
* reverse order. Then, make a second pass up each side to fix
* the pointers and compute max_free. The time bound is O(log n)
* amortized.
*
* The new root is the vm_map_entry containing "addr", or else an
* adjacent entry (lower or higher) if addr is not in the tree.
*
* The map must be locked, and leaves it so.
*
* Returns: the new root.
*/ */
static vm_map_entry_t static vm_map_entry_t
vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root) vm_map_entry_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 llist, rlist; vm_map_entry_t llist, rlist;
vm_map_entry_t ltree, rtree;
vm_map_entry_t y; vm_map_entry_t y;
/* Special case of empty tree. */
if (root == NULL)
return (root);
/*
* Pass One: Splay down the tree until we find addr or a NULL
* pointer where addr would go. llist and rlist are the two
* sides in reverse order (bottom-up), with llist linked by
* the right pointer and rlist linked by the left pointer in
* the vm_map_entry. Wait until Pass Two to set max_free on
* the two spines.
*/
llist = NULL; llist = NULL;
rlist = NULL; rlist = NULL;
for (;;) { while (root != NULL && root->max_free >= length) {
/* root is never NULL in here. */
if (addr < root->start) { if (addr < root->start) {
y = root->left; y = root->left;
if (y == NULL) if (y != NULL && y->max_free >= length &&
break; addr < y->start) {
if (addr < y->start && y->left != NULL) { /* Rotate right and make y root. */
/* Rotate right and put y on rlist. */
root->left = y->right; root->left = y->right;
y->right = root; y->right = root;
vm_map_entry_set_max_free(root); vm_map_entry_set_max_free(root);
root = y->left;
y->left = rlist;
rlist = y;
} else {
/* Put root on rlist. */
root->left = rlist;
rlist = root;
root = y; root = y;
y = root->left;
} }
/* Put root on rlist. */
root->left = rlist;
rlist = root;
root = y;
} else if (addr >= root->end) { } else if (addr >= root->end) {
y = root->right; y = root->right;
if (y == NULL) if (y != NULL && y->max_free >= length &&
break; addr >= y->end) {
if (addr >= y->end && y->right != NULL) { /* Rotate left and make y root. */
/* Rotate left and put y on llist. */
root->right = y->left; root->right = y->left;
y->left = root; y->left = root;
vm_map_entry_set_max_free(root); vm_map_entry_set_max_free(root);
root = y->right;
y->right = llist;
llist = y;
} else {
/* Put root on llist. */
root->right = llist;
llist = root;
root = y; root = y;
y = root->right;
kibUnsubmitted
Done
Inline Actions

The split and merge in the name of this function and the function below refer to the llist and rlist, and not to the split of some entry ? It sounds strange to name them vm_map_entry_something.

kib: The split and merge in the name of this function and the function below refer to the llist and…
dougmAuthorUnsubmitted
Done
Inline Actions

The split function divides the tree into an llist of nodes less than addr, an rlist of nodes greater than addr, and a root (possibly NULL) that contains addr, with left and right children less than and greater than addr.

I'm trying to follow convention with the naming. I don't object to dropping 'entry' from the names of the new functions, if that's what people want.

dougm: The split function divides the tree into an llist of nodes less than addr, an rlist of nodes…
} }
/* Put root on llist. */
root->right = llist;
llist = root;
root = y;
} else } else
break; break;
} }
*out_llist = llist;
*out_rlist = rlist;
return (root);
}
static void
vm_map_entry_splay_walk_left_spine(vm_map_entry_t root, vm_map_entry_t *io_list)
{
vm_map_entry_t list, tree, y;
tree = root->left;
list = *io_list;
while (tree != NULL) {
if ((y = tree->right) != NULL) {
/* Rotate left. */
tree->right = y->left;
y->left = tree;
vm_map_entry_set_max_free(tree);
tree = y;
y = tree->right;
}
/* Put tree on list. */
tree->right = list;
list = tree;
tree = y;
}
*io_list = list;
}
static void
vm_map_entry_splay_walk_right_spine(vm_map_entry_t root, vm_map_entry_t *io_list)
{
vm_map_entry_t list, tree, y;
tree = root->right;
list = *io_list;
while (tree != NULL) {
if ((y = tree->left) != NULL) {
/* Rotate right. */
tree->left = y->right;
y->right = tree;
vm_map_entry_set_max_free(tree);
tree = y;
y = tree->left;
}
/* Put tree on list. */
tree->left = list;
list = tree;
tree = y;
}
*io_list = list;
}
/*
* 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
vm_map_entry_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 y;
/*
* Pass Two: 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.
*/
ltree = root->left;
while (llist != NULL) { while (llist != NULL) {
y = llist->right; y = llist->right;
llist->right = ltree; llist->right = ltree;
vm_map_entry_set_max_free(llist); vm_map_entry_set_max_free(llist);
ltree = llist; ltree = llist;
llist = y; llist = y;
} }
rtree = root->right;
while (rlist != NULL) { while (rlist != NULL) {
y = rlist->left; y = rlist->left;
rlist->left = rtree; rlist->left = rtree;
vm_map_entry_set_max_free(rlist); vm_map_entry_set_max_free(rlist);
rtree = rlist; rtree = rlist;
rlist = y; rlist = y;
} }
/* /*
* Final assembly: add ltree and rtree as subtrees of root. * Final assembly: add ltree and rtree as subtrees of root.
*/ */
root->left = ltree; root->left = ltree;
root->right = rtree; root->right = rtree;
vm_map_entry_set_max_free(root); vm_map_entry_set_max_free(root);
return (root); return (root);
} }
/*
* vm_map_entry_splay:
*
* The Sleator and Tarjan top-down splay algorithm with the
* following variation. Max_free must be computed bottom-up, so
* on the downward pass, maintain the left and right spines in
* reverse order. Then, make a second pass up each side to fix
* the pointers and compute max_free. The time bound is O(log n)
* amortized.
*
* The new root is the vm_map_entry containing "addr", or else an
* adjacent entry (lower if possible) if addr is not in the tree.
*
* The map must be locked, and leaves it so.
*
* 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_t llist, rlist;
root = vm_map_entry_splay_split(addr, 0, root, &llist, &rlist);
if (root != NULL) {
/* do nothing */
} else if (llist != NULL) {
/*
* Recover the greatest node in the left
* subtree and make it the root.
*/
root = llist;
llist = root->right;
root->right = NULL;
} else if (rlist != NULL) {
/*
* Recover the least node in the right
* subtree and make it the root.
*/
root = rlist;
rlist = root->left;
root->left = NULL;
} else {
/* There is no root. */
return (NULL);
}
return (vm_map_entry_splay_merge(root, llist, rlist,
root->left, root->right));
}
/* /*
* vm_map_entry_{un,}link: * vm_map_entry_{un,}link:
* *
* Insert/remove entries from maps. * Insert/remove entries from maps.
*/ */
static void static void
vm_map_entry_link(vm_map_t map, vm_map_entry_link(vm_map_t map,
vm_map_entry_t after_where,
vm_map_entry_t entry) vm_map_entry_t entry)
{ {
vm_map_entry_t llist, rlist, root;
CTR4(KTR_VM, CTR3(KTR_VM,
"vm_map_entry_link: map %p, nentries %d, entry %p, after %p", map, "vm_map_entry_link: map %p, nentries %d, entry %p", map,
map->nentries, entry, after_where); map->nentries, entry);
VM_MAP_ASSERT_LOCKED(map); VM_MAP_ASSERT_LOCKED(map);
KASSERT(after_where->end <= entry->start,
("vm_map_entry_link: prev end %jx new start %jx overlap",
(uintmax_t)after_where->end, (uintmax_t)entry->start));
KASSERT(entry->end <= after_where->next->start,
("vm_map_entry_link: new end %jx next start %jx overlap",
(uintmax_t)entry->end, (uintmax_t)after_where->next->start));
map->nentries++; map->nentries++;
entry->prev = after_where; root = map->root;
entry->next = after_where->next; root = vm_map_entry_splay_split(entry->start, 0, root, &llist, &rlist);
entry->next->prev = entry; KASSERT(root == NULL,
after_where->next = entry; ("vm_map_entry_link: link object already mapped"));
entry->prev = (llist == NULL) ? &map->header : llist;
if (after_where != &map->header) { entry->next = (rlist == NULL) ? &map->header : rlist;
if (after_where != map->root) entry->prev->next = entry->next->prev = entry;
vm_map_entry_splay(after_where->start, map->root); root = vm_map_entry_splay_merge(entry, llist, rlist, NULL, NULL);
entry->right = after_where->right;
entry->left = after_where;
after_where->right = NULL;
after_where->adj_free = entry->start - after_where->end;
vm_map_entry_set_max_free(after_where);
} else {
entry->right = map->root;
entry->left = NULL;
}
entry->adj_free = entry->next->start - entry->end;
vm_map_entry_set_max_free(entry);
map->root = entry; map->root = entry;
} }
static void static void
vm_map_entry_unlink(vm_map_t map, vm_map_entry_unlink(vm_map_t map,
vm_map_entry_t entry) vm_map_entry_t entry)
{ {
vm_map_entry_t next, prev, root; vm_map_entry_t llist, rlist, root;
VM_MAP_ASSERT_LOCKED(map); VM_MAP_ASSERT_LOCKED(map);
if (entry != map->root) llist = entry->prev;
vm_map_entry_splay(entry->start, map->root); rlist = entry->next;
if (entry->left == NULL) llist->next = rlist;
root = entry->right; rlist->prev = llist;
else { root = map->root;
root = vm_map_entry_splay(entry->start, entry->left); root = vm_map_entry_splay_split(entry->start, 0, root, &llist, &rlist);
root->right = entry->right; KASSERT(root != NULL,
root->adj_free = entry->next->start - root->end; ("vm_map_entry_unlink: unlink object not mapped"));
vm_map_entry_set_max_free(root); vm_map_entry_splay_walk_left_spine(root, &llist);
} vm_map_entry_splay_walk_right_spine(root, &rlist);
if (llist != NULL) {
/* New root is predecessor of found node. */
root = llist;
llist = root->right;
root->right = NULL;
} else if (rlist != NULL) {
/* New root is successor of found node. */
root = rlist;
rlist = root->left;
root->left = NULL;
} else
root = NULL;
if (root != NULL)
kibUnsubmitted
Done
Inline Actions

Why do you need two switches ? I.e, why cannot the code from the second switch cases go straight into the cases of the first switch ? I understand that you do separate llist/rlists and root calculations, but I do not quite get the separation.

kib: Why do you need two switches ? I.e, why cannot the code from the second switch cases go…
dougmAuthorUnsubmitted
Done
Inline Actions

I can get by with only one switch, but then a have to duplicate each of the three-line code snippets that start with resetting the new root value. Note that the NONE case in the first switch is likely to alter the value of 'op', so that some other case is taken in the second switch.

dougm: I can get by with only one switch, but then a have to duplicate each of the three-line code…
root = vm_map_entry_splay_merge(root, llist, rlist,
root->left, root->right);
map->root = root; map->root = root;
prev = entry->prev;
next = entry->next;
next->prev = prev;
prev->next = next;
map->nentries--; map->nentries--;
CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map, CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
map->nentries, entry); map->nentries, entry);
} }
/* /*
* vm_map_entry_resize_free: * vm_map_entry_resize_free:
* *
* Recompute the amount of free space following a vm_map_entry * Recompute the amount of free space next to a vm_map_entry
* and propagate that value up the tree. Call this function after * and propagate those values up the tree. Call this function after
* resizing a map entry in-place, that is, without a call to * resizing a map entry in-place, that is, without a call to
* vm_map_entry_link() or _unlink(). * vm_map_entry_link() or _unlink().
* *
* The map must be locked, and leaves it so. * The map must be locked, and leaves it so.
*/ */
static void 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, bool newStart)
{ {
vm_map_entry_t llist, rlist, root;
/* VM_MAP_ASSERT_LOCKED(map);
* Using splay trees without parent pointers, propagating root = map->root;
* max_free up the tree is done by moving the entry to the root = vm_map_entry_splay_split(entry->start, 0, root, &llist, &rlist);
* root and making the change there. KASSERT(root != NULL,
*/ ("vm_map_entry_resize_free: resize_free object not mapped"));
if (entry != map->root) if (newStart) {
map->root = vm_map_entry_splay(entry->start, map->root); vm_map_entry_splay_walk_left_spine(root, &llist);
root->left = NULL;
entry->adj_free = entry->next->start - entry->end; } else {
vm_map_entry_set_max_free(entry); vm_map_entry_splay_walk_right_spine(root, &rlist);
root->right = NULL;
}
map->root = vm_map_entry_splay_merge(root, llist, rlist,
root->left, root->right);
CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map,
map->nentries, entry);
} }
/* /*
* vm_map_lookup_entry: [ internal use only ] * vm_map_lookup_entry: [ internal use only ]
* *
* Finds the map entry containing (or * Finds the map entry containing (or
* immediately preceding) the specified address * immediately preceding) the specified address
* in the given map; the entry is returned * in the given map; the entry is returned
* in the "entry" parameter. The boolean * in the "entry" parameter. The boolean
* result indicates whether the address is * result indicates whether the address is
* actually contained in the map. * actually contained in the map.
*/ */
boolean_t boolean_t
vm_map_lookup_entry( vm_map_lookup_entry(
vm_map_t map, vm_map_t map,
vm_offset_t address, vm_offset_t address,
vm_map_entry_t *entry) /* OUT */ vm_map_entry_t *entry) /* OUT */
{ {
vm_map_entry_t cur; vm_map_entry_t cur, lbound;
boolean_t locked; boolean_t locked;
/* /*
* If the map is empty, then the map entry immediately preceding * If the map is empty, then the map entry immediately preceding
* "address" is the map's header. * "address" is the map's header.
*/ */
cur = map->root; cur = map->root;
if (cur == NULL) if (cur == NULL) {
*entry = &map->header; *entry = &map->header;
else if (address >= cur->start && cur->end > address) { return (FALSE);
}
if (address >= cur->start && cur->end > address) {
*entry = cur; *entry = cur;
return (TRUE); return (TRUE);
} else if ((locked = vm_map_locked(map)) || }
if ((locked = vm_map_locked(map)) ||
sx_try_upgrade(&map->lock)) { sx_try_upgrade(&map->lock)) {
/* /*
* Splay requires a write lock on the map. However, it only * Splay requires a write lock on the map. However, it only
* restructures the binary search tree; it does not otherwise * restructures the binary search tree; it does not otherwise
* change the map. Thus, the map's timestamp need not change * change the map. Thus, the map's timestamp need not change
* on a temporary upgrade. * on a temporary upgrade.
*/ */
map->root = cur = vm_map_entry_splay(address, cur); map->root = cur = vm_map_entry_splay(address, cur);
if (!locked) if (!locked)
sx_downgrade(&map->lock); sx_downgrade(&map->lock);
/* /*
* If "address" is contained within a map entry, the new root * If "address" is contained within a map entry, the new root
* is that map entry. Otherwise, the new root is a map entry * is that map entry. Otherwise, the new root is a map entry
* immediately before or after "address". * immediately before or after "address".
*/ */
if (address >= cur->start) { if (address < cur->start) {
*entry = &map->header;
return (FALSE);
}
*entry = cur;
return (address < cur->end);
}
/*
* Since the map is only locked for read access, perform a
* standard binary search tree lookup for "address".
*/
lbound = &map->header;
do {
if (address < cur->start) {
cur = cur->left;
} else if (cur->end <= address) {
lbound = cur;
cur = cur->right;
} else {
*entry = cur; *entry = cur;
if (cur->end > address) return (TRUE);
return (TRUE);
} else
*entry = cur->prev;
} else
/*
* Since the map is only locked for read access, perform a
* standard binary search tree lookup for "address".
*/
for (;;) {
if (address < cur->start) {
if (cur->left == NULL) {
*entry = cur->prev;
break;
}
cur = cur->left;
} else if (cur->end > address) {
*entry = cur;
return (TRUE);
} else {
if (cur->right == NULL) {
*entry = cur;
break;
}
cur = cur->right;
}
} }
} while (cur != NULL);
*entry = lbound;
return (FALSE); return (FALSE);
} }
/* /*
* vm_map_insert: * vm_map_insert:
* *
* Inserts the given whole VM object into the target * Inserts the given whole VM object into the target
* map at the specified address range. The object's * map at the specified address range. The object's
Show All 14 Lines
prev_entry->max_protection == max && prev_entry->max_protection == max &&
prev_entry->wired_count == 0) { prev_entry->wired_count == 0) {
KASSERT((prev_entry->eflags & MAP_ENTRY_USER_WIRED) == KASSERT((prev_entry->eflags & MAP_ENTRY_USER_WIRED) ==
0, ("prev_entry %p has incoherent wiring", 0, ("prev_entry %p has incoherent wiring",
prev_entry)); prev_entry));
if ((prev_entry->eflags & MAP_ENTRY_GUARD) == 0) if ((prev_entry->eflags & MAP_ENTRY_GUARD) == 0)
map->size += end - prev_entry->end; map->size += end - prev_entry->end;
prev_entry->end = end; prev_entry->end = end;
vm_map_entry_resize_free(map, prev_entry); vm_map_entry_resize_free(map, prev_entry, false);
vm_map_simplify_entry(map, prev_entry); vm_map_simplify_entry(map, prev_entry);
return (KERN_SUCCESS); return (KERN_SUCCESS);
} }
/* /*
* If we can extend the object but cannot extend the * If we can extend the object but cannot extend the
* map entry, we have to create a new map entry. We * map entry, we have to create a new map entry. We
* must bump the ref count on the extended object to * must bump the ref count on the extended object to
Show All 14 Lines
KASSERT(cred == NULL || !ENTRY_CHARGED(new_entry), KASSERT(cred == NULL || !ENTRY_CHARGED(new_entry),
("overcommit: vm_map_insert leaks vm_map %p", new_entry)); ("overcommit: vm_map_insert leaks vm_map %p", new_entry));
new_entry->cred = cred; new_entry->cred = cred;
/* /*
* Insert the new entry into the list * Insert the new entry into the list
*/ */
vm_map_entry_link(map, prev_entry, new_entry); vm_map_entry_link(map, new_entry);
if ((new_entry->eflags & MAP_ENTRY_GUARD) == 0) if ((new_entry->eflags & MAP_ENTRY_GUARD) == 0)
map->size += new_entry->end - new_entry->start; map->size += new_entry->end - new_entry->start;
/* /*
* Try to coalesce the new entry with both the previous and next * Try to coalesce the new entry with both the previous and next
* entries in the list. Previously, we only attempted to coalesce * entries in the list. Previously, we only attempted to coalesce
* with the previous entry when object is NULL. Here, we handle the * with the previous entry when object is NULL. Here, we handle the
* other cases, which are less common. * other cases, which are less common.
Show All 9 Lines
} }
/* /*
* vm_map_findspace: * vm_map_findspace:
* *
* Find the first fit (lowest VM address) for "length" free bytes * Find the first fit (lowest VM address) for "length" free bytes
* beginning at address >= start in the given map. * beginning at address >= start in the given map.
* *
* In a vm_map_entry, "adj_free" is the amount of free space * In a vm_map_entry, "max_free" is the maximum amount of
* adjacent (higher address) to this entry, and "max_free" is the * contiguous free space between an entry in its subtree and a
* maximum amount of contiguous free space in its subtree. This * neighbor of that entry. This allows finding a free region in
* allows finding a free region in one path down the tree, so * one path down the tree, so O(log n) amortized with splay
* O(log n) amortized with splay trees. * trees.
* *
* The map must be locked, and leaves it so. * The map must be locked, and leaves it so.
* *
* Returns: 0 on success, and starting address in *addr, * Returns: 0 on success, and starting address in *addr,
* 1 if insufficient space. * 1 if insufficient space.
*/ */
int int
vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length, vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length,
vm_offset_t *addr) /* OUT */ vm_offset_t *addr) /* OUT */
{ {
vm_map_entry_t entry; vm_map_entry_t llist, rlist, root, y;
vm_offset_t st;
/* /*
* Request must fit within min/max VM address and must avoid * Request must fit within min/max VM address and must avoid
* address wrap. * address wrap.
*/ */
start = MAX(start, vm_map_min(map)); start = MAX(start, vm_map_min(map));
if (start + length > vm_map_max(map) || start + length < start) if (start + length > vm_map_max(map) || start + length < start)
return (1); return (1);
kibUnsubmitted
Done
Inline Actions

Perhaps change the return type of the function to bool ? It got almost complete rewrite anyway.

kib: Perhaps change the return type of the function to bool ? It got almost complete rewrite anyway.
dougmAuthorUnsubmitted
Done
Inline Actions

If we're talking about changing the interface, how would you feel about changing the return type to vm_offset_t, eliminating the addr parameter, returning the addr, and returning the vm_map_max value for the failure case?

dougm: If we're talking about changing the interface, how would you feel about changing the return…
/* Empty tree means wide open address space. */ /* Empty tree means wide open address space. */
if (map->root == NULL) { if (map->root == NULL) {
*addr = start; *addr = start;
return (0); return (0);
} }
/* /*
* After splay, if start comes before root node, then there * After splay, if start comes before root node, then there
* must be a gap from start to the root. * must be a gap from start to the root.
*/ */
map->root = vm_map_entry_splay(start, map->root); root = vm_map_entry_splay_split(start, length, map->root, &llist, &rlist);
if (start + length <= map->root->start) { if (root != NULL)
start = root->end;
else if (rlist != NULL) {
root = rlist;
rlist = root->left;
root->left = NULL;
} else {
root = llist;
llist = root->right;
root->right = NULL;
}
map->root = vm_map_entry_splay_merge(root, llist, rlist,
root->left, root->right);
if (start + length <= root->start) {
*addr = start; *addr = start;
return (0); return (0);
} }
/* /*
* Root is the last node that might begin its gap before * Entry is the last node that might begin its gap before
* start, and this is the last comparison where address * start, and this is the last comparison where address
* wrap might be a problem. * wrap might be a problem.
*/ */
st = (start > map->root->end) ? start : map->root->end; llist = root;
if (length <= map->root->end + map->root->adj_free - st) { rlist = NULL;
*addr = st; root = root->right;
if (root == NULL &&
start + length <= vm_map_max(map)) {
*addr = start;
return (0); return (0);
} }
/* With max_free, can immediately tell if no solution. */ /* With max_free, can immediately tell if no solution. */
entry = map->root->right; if (root == NULL || length > root->max_free)
if (entry == NULL || length > entry->max_free)
return (1); return (1);
/* /*
* Search the right subtree in the order: left subtree, root, * Splay for the least large-enough gap in the right subtree.
* right subtree (first fit). The previous splay implies that
* all regions in the right subtree have addresses > start.
*/ */
while (entry != NULL) { while (root != NULL) {
if (entry->left != NULL && entry->left->max_free >= length) y = root->left;
entry = entry->left; if (length <= (y != NULL ?
else if (entry->adj_free >= length) { y->max_free : root->start - llist->end)) {
*addr = entry->end; if (y != NULL &&
return (0); (length <= (y->left != NULL ?
} else y->left->max_free : y->start - llist->end))) {
entry = entry->right; /* Rotate right and make y root. */
root->left = y->right;
y->right = root;
vm_map_entry_set_max_free(root);
root = y;
y = root->left;
}
/* Put root on rlist. */
root->left = rlist;
rlist = root;
root = y;
} else {
y = root->right;
if (y != NULL &&
(length > (y->left != NULL ?
y->left->max_free : y->start - root->end))) {
/* Rotate left and make y root. */
root->right = y->left;
y->left = root;
vm_map_entry_set_max_free(root);
root = y;
y = root->right;
}
/* Put root on llist. */
root->right = llist;
llist = root;
root = y;
}
} }
root = llist;
/* Can't get here, so panic if we do. */ llist = root->right;
panic("vm_map_findspace: max_free corrupt"); root->right = NULL;
map->root = vm_map_entry_splay_merge(root, llist, rlist,
root->left, root->right);
*addr = root->end;
return (0);
} }
int int
vm_map_fixed(vm_map_t map, vm_object_t object, vm_ooffset_t offset, vm_map_fixed(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
vm_offset_t start, vm_size_t length, vm_prot_t prot, vm_offset_t start, vm_size_t length, vm_prot_t prot,
vm_prot_t max, int cow) vm_prot_t max, int cow)
{ {
vm_offset_t end; vm_offset_t end;
Show All 14 Lines
vm_offset_t *addr, vm_size_t length, vm_offset_t max_addr, vm_offset_t *addr, vm_size_t length, vm_offset_t max_addr,
vm_offset_t alignment) vm_offset_t alignment)
{ {
vm_offset_t aligned_addr, free_addr; vm_offset_t aligned_addr, free_addr;
VM_MAP_ASSERT_LOCKED(map); VM_MAP_ASSERT_LOCKED(map);
free_addr = *addr; free_addr = *addr;
KASSERT(!vm_map_findspace(map, free_addr, length, addr) && KASSERT(!vm_map_findspace(map, free_addr, length, addr) &&
free_addr == *addr, ("caller provided insufficient free space")); free_addr == *addr,
("caller failed to provide space %d at address %p",
(int)length, (void*)free_addr));
for (;;) { for (;;) {
/* /*
* At the start of every iteration, the free space at address * At the start of every iteration, the free space at address
* "*addr" is at least "length" bytes. * "*addr" is at least "length" bytes.
*/ */
if (alignment == 0) if (alignment == 0)
pmap_align_superpage(object, offset, addr, length); pmap_align_superpage(object, offset, addr, length);
else if ((*addr & (alignment - 1)) != 0) { else if ((*addr & (alignment - 1)) != 0) {
Show All 14 Lines
if ((entry->eflags & MAP_ENTRY_NOMERGE_MASK) != 0) if ((entry->eflags & MAP_ENTRY_NOMERGE_MASK) != 0)
return; return;
prev = entry->prev; prev = entry->prev;
if (vm_map_mergeable_neighbors(prev, entry)) { if (vm_map_mergeable_neighbors(prev, entry)) {
vm_map_entry_unlink(map, prev); vm_map_entry_unlink(map, prev);
entry->start = prev->start; entry->start = prev->start;
entry->offset = prev->offset; entry->offset = prev->offset;
if (entry->prev != &map->header) vm_map_entry_resize_free(map, entry, true);
vm_map_entry_resize_free(map, entry->prev);
vm_map_merged_neighbor_dispose(map, prev); vm_map_merged_neighbor_dispose(map, prev);
} }
next = entry->next; next = entry->next;
if (vm_map_mergeable_neighbors(entry, next)) { if (vm_map_mergeable_neighbors(entry, next)) {
vm_map_entry_unlink(map, next); vm_map_entry_unlink(map, next);
entry->end = next->end; entry->end = next->end;
vm_map_entry_resize_free(map, entry); vm_map_entry_resize_free(map, entry, false);
vm_map_merged_neighbor_dispose(map, next); vm_map_merged_neighbor_dispose(map, next);
} }
} }
/* /*
* vm_map_clip_start: [ internal use only ] * vm_map_clip_start: [ internal use only ]
* *
* Asserts that the given entry begins at or after * Asserts that the given entry begins at or after
Show All 14 Lines
*new_entry = *entry; *new_entry = *entry;
new_entry->end = start; new_entry->end = start;
entry->offset += (start - entry->start); entry->offset += (start - entry->start);
entry->start = start; entry->start = start;
if (new_entry->cred != NULL) if (new_entry->cred != NULL)
crhold(entry->cred); crhold(entry->cred);
vm_map_entry_link(map, entry->prev, new_entry); vm_map_entry_link(map, new_entry);
if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) { if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
vm_object_reference(new_entry->object.vm_object); vm_object_reference(new_entry->object.vm_object);
/* /*
* The object->un_pager.vnp.writemappings for the * The object->un_pager.vnp.writemappings for the
* object of MAP_ENTRY_VN_WRITECNT type entry shall be * object of MAP_ENTRY_VN_WRITECNT type entry shall be
* kept as is here. The virtual pages are * kept as is here. The virtual pages are
* re-distributed among the clipped entries, so the sum is * re-distributed among the clipped entries, so the sum is
Show All 14 Lines
new_entry = vm_map_entry_create(map); new_entry = vm_map_entry_create(map);
*new_entry = *entry; *new_entry = *entry;
new_entry->start = entry->end = end; new_entry->start = entry->end = end;
new_entry->offset += (end - entry->start); new_entry->offset += (end - entry->start);
if (new_entry->cred != NULL) if (new_entry->cred != NULL)
crhold(entry->cred); crhold(entry->cred);
vm_map_entry_link(map, entry, new_entry); vm_map_entry_link(map, new_entry);
if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) { if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
vm_object_reference(new_entry->object.vm_object); vm_object_reference(new_entry->object.vm_object);
} }
} }
/* /*
* vm_map_submap: [ kernel use only ] * vm_map_submap: [ kernel use only ]
Show All 14 Lines
vnode_pager_update_writecount(object, vnode_pager_update_writecount(object,
new_entry->start, new_entry->end); new_entry->start, new_entry->end);
} }
/* /*
* Insert the entry into the new map -- we know we're * Insert the entry into the new map -- we know we're
* inserting at the end of the new map. * inserting at the end of the new map.
*/ */
vm_map_entry_link(new_map, new_map->header.prev, vm_map_entry_link(new_map, new_entry);
new_entry);
vmspace_map_entry_forked(vm1, vm2, new_entry); vmspace_map_entry_forked(vm1, vm2, new_entry);
/* /*
* Update the physical map * Update the physical map
*/ */
pmap_copy(new_map->pmap, old_map->pmap, pmap_copy(new_map->pmap, old_map->pmap,
new_entry->start, new_entry->start,
(old_entry->end - old_entry->start), (old_entry->end - old_entry->start),
Show All 10 Lines
* Copied entry is COW over the old object. * Copied entry is COW over the old object.
*/ */
new_entry->eflags &= ~(MAP_ENTRY_USER_WIRED | new_entry->eflags &= ~(MAP_ENTRY_USER_WIRED |
MAP_ENTRY_IN_TRANSITION | MAP_ENTRY_VN_WRITECNT); MAP_ENTRY_IN_TRANSITION | MAP_ENTRY_VN_WRITECNT);
new_entry->wiring_thread = NULL; new_entry->wiring_thread = NULL;
new_entry->wired_count = 0; new_entry->wired_count = 0;
new_entry->object.vm_object = NULL; new_entry->object.vm_object = NULL;
new_entry->cred = NULL; new_entry->cred = NULL;
vm_map_entry_link(new_map, new_map->header.prev, vm_map_entry_link(new_map, new_entry);
new_entry);
vmspace_map_entry_forked(vm1, vm2, new_entry); vmspace_map_entry_forked(vm1, vm2, new_entry);
vm_map_copy_entry(old_map, new_map, old_entry, vm_map_copy_entry(old_map, new_map, old_entry,
new_entry, fork_charge); new_entry, fork_charge);
break; break;
case VM_INHERIT_ZERO: case VM_INHERIT_ZERO:
/* /*
* Create a new anonymous mapping entry modelled from * Create a new anonymous mapping entry modelled from
* the old one. * the old one.
*/ */
new_entry = vm_map_entry_create(new_map); new_entry = vm_map_entry_create(new_map);
memset(new_entry, 0, sizeof(*new_entry)); memset(new_entry, 0, sizeof(*new_entry));
new_entry->start = old_entry->start; new_entry->start = old_entry->start;
new_entry->end = old_entry->end; new_entry->end = old_entry->end;
new_entry->eflags = old_entry->eflags & new_entry->eflags = old_entry->eflags &
~(MAP_ENTRY_USER_WIRED | MAP_ENTRY_IN_TRANSITION | ~(MAP_ENTRY_USER_WIRED | MAP_ENTRY_IN_TRANSITION |
MAP_ENTRY_VN_WRITECNT); MAP_ENTRY_VN_WRITECNT);
new_entry->protection = old_entry->protection; new_entry->protection = old_entry->protection;
new_entry->max_protection = old_entry->max_protection; new_entry->max_protection = old_entry->max_protection;
new_entry->inheritance = VM_INHERIT_ZERO; new_entry->inheritance = VM_INHERIT_ZERO;
vm_map_entry_link(new_map, new_map->header.prev, vm_map_entry_link(new_map, new_entry);
new_entry);
vmspace_map_entry_forked(vm1, vm2, new_entry); vmspace_map_entry_forked(vm1, vm2, new_entry);
new_entry->cred = curthread->td_ucred; new_entry->cred = curthread->td_ucred;
crhold(new_entry->cred); crhold(new_entry->cred);
*fork_charge += (new_entry->end - new_entry->start); *fork_charge += (new_entry->end - new_entry->start);
break; break;
} }
Show All 14 Lines
if (gap_entry->start + grow_amount == gap_entry->end) { if (gap_entry->start + grow_amount == gap_entry->end) {
gap_start = gap_entry->start; gap_start = gap_entry->start;
gap_end = gap_entry->end; gap_end = gap_entry->end;
vm_map_entry_delete(map, gap_entry); vm_map_entry_delete(map, gap_entry);
gap_deleted = true; gap_deleted = true;
} else { } else {
MPASS(gap_entry->start < gap_entry->end - grow_amount); MPASS(gap_entry->start < gap_entry->end - grow_amount);
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, false);
gap_deleted = false; gap_deleted = false;
} }
rv = vm_map_insert(map, NULL, 0, grow_start, rv = vm_map_insert(map, NULL, 0, grow_start,
grow_start + grow_amount, grow_start + grow_amount,
stack_entry->protection, stack_entry->max_protection, stack_entry->protection, stack_entry->max_protection,
MAP_STACK_GROWS_DOWN); MAP_STACK_GROWS_DOWN);
if (rv != KERN_SUCCESS) { if (rv != KERN_SUCCESS) {
if (gap_deleted) { if (gap_deleted) {
rv1 = vm_map_insert(map, NULL, 0, gap_start, rv1 = vm_map_insert(map, NULL, 0, gap_start,
gap_end, VM_PROT_NONE, VM_PROT_NONE, gap_end, VM_PROT_NONE, VM_PROT_NONE,
MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN); MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN);
MPASS(rv1 == KERN_SUCCESS); MPASS(rv1 == KERN_SUCCESS);
} else { } else {
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, false);
} }
} }
} else { } else {
grow_start = stack_entry->end; grow_start = stack_entry->end;
cred = stack_entry->cred; cred = stack_entry->cred;
if (cred == NULL && stack_entry->object.vm_object != NULL) if (cred == NULL && stack_entry->object.vm_object != NULL)
cred = stack_entry->object.vm_object->cred; cred = stack_entry->object.vm_object->cred;
if (cred != NULL && !swap_reserve_by_cred(grow_amount, cred)) if (cred != NULL && !swap_reserve_by_cred(grow_amount, cred))
rv = KERN_NO_SPACE; rv = KERN_NO_SPACE;
/* Grow the underlying object if applicable. */ /* Grow the underlying object if applicable. */
else if (stack_entry->object.vm_object == NULL || else if (stack_entry->object.vm_object == NULL ||
vm_object_coalesce(stack_entry->object.vm_object, vm_object_coalesce(stack_entry->object.vm_object,
stack_entry->offset, stack_entry->offset,
(vm_size_t)(stack_entry->end - stack_entry->start), (vm_size_t)(stack_entry->end - stack_entry->start),
(vm_size_t)grow_amount, cred != NULL)) { (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); vm_map_entry_delete(map, gap_entry);
else else
gap_entry->start += grow_amount; gap_entry->start += grow_amount;
stack_entry->end += grow_amount; stack_entry->end += grow_amount;
map->size += grow_amount; map->size += grow_amount;
vm_map_entry_resize_free(map, stack_entry); vm_map_entry_resize_free(map, stack_entry, false);
rv = KERN_SUCCESS; rv = KERN_SUCCESS;
} else } else
rv = KERN_FAILURE; rv = KERN_FAILURE;
} }
if (rv == KERN_SUCCESS && is_procstack) if (rv == KERN_SUCCESS && is_procstack)
vm->vm_ssize += btoc(grow_amount); vm->vm_ssize += btoc(grow_amount);
/* /*
* Heed the MAP_WIREFUTURE flag if it was set for this process. * Heed the MAP_WIREFUTURE flag if it was set for this process.
*/ */
if (rv == KERN_SUCCESS && (map->flags & MAP_WIREFUTURE) != 0) { if (rv == KERN_SUCCESS && (map->flags & MAP_WIREFUTURE) != 0) {
vm_map_unlock(map); vm_map_unlock(map);
vm_map_wire(map, grow_start, grow_start + grow_amount, vm_map_wire(map, grow_start, grow_start + grow_amount,
VM_MAP_WIRE_USER | VM_MAP_WIRE_NOHOLES); VM_MAP_WIRE_USER | VM_MAP_WIRE_NOHOLES);
vm_map_lock_read(map); vm_map_lock_read(map);
Context not available.
View Options

head/sys/kern/vfs_subr.c

Loading...
View Options

head/sys/vm/swap_pager.c

Loading...
View Options

head/sys/vm/vm_page.c

Loading...
View Options

head/sys/vm/vm_pager.c

Loading...