Avoid function call in MERGE_NONE case.

Add missing max_free update to MERGE_NEXT case.

Add a KASSERT to vm_map_mergeable_neighbors. Exploit the fact that some adj_free field is 0 in vm_map_entry_unlink neighbor-merging to avoid some calculation.

Apply reviewer suggestions.

Fix cut-and-paste error. Drop prevsize. Reformat comment. Add merge parameter to vm_entry_map_delete, so that deleting a gap entry can happen without a call to vm_map_entry_resize_free.

The concerns that this change would address will be addressed elsewhere.

Rename pesky 'neighbor' functions. Pass the unlink_merge_type to the function that disposes of things.

Address reviewer comments.

Rewrite to avoid changing start/end values before splaying, by adding an argument to unlink telling it which "neighbor", if any, that the unlinking item is being merged with.

Add 'simplify' to 'neighbor' function names.

Update the diff to match the updated title of this change.

Back-up to a version that worked once, and hope that it still does.

Fix a problem recently introduced that breaks an insert of a new last item.

Update to adjust to recent changes in adjacent code.

Accept reviewer style suggestions.

Apply recommended style changes.

Fix CTR3 compilation error.

Drop unneeded argument to vm_map_entry_link. Drop unnecessary calls to vm_map_entry_resize_free from vm_map_simplify_entry, by setting start/end fields before removing neighbor. Reduce number of uses of 'prev' member when iterating through consecutive map entries.

Thanks to Peter Holm for point out necessary changes to this patch on account of changes elsewhere. min_offset and max_offset fields have been renamed.

The patch hasn't changed since February, but some of the context around it has, so updating to deal with conflicts.

The only difference between this and what was posted in January is that that patch discarded code that has recently been found to be buggy, and this patch discards the fixed code.

Add parens, as requested.

Apply reviewer-recommended changes.

Alphabetically order variable definitions. Introduce standard whitespace before block comment.

Replace another conditional freerange with a KASSERT, as instructed.

Add KASSERT on swap_pager_meta_build return value. Use a 'continue' to allow a big indented block to be outdented.

Accept a suggestion to remove an unnecessary conditional 'continue'.

Rewrite the splay root-picking code a bit to eliminate a few redundant writes.

In D13999#296096, @kib wrote:

In D13999#295781, @dougm_rice.edu wrote:

In D13999#295780, @kib wrote:

Is there an assert somewhere that the map header is never returned by a lookup ?

Without this change, it is possible that vm_map_lookup_entry will return with *entry == &map->header, when the root is null or when a binary search is made for an address smaller than any in the tree. So there's no assertion to fail on that condition, and it would be incorrect to add one.

That will still be possible after this change, so that there's no cause to add an assertion.

Ok. I looked at the consumers, and either they explicitly check for the lookup address falling into the map range, or do found_entry->next if result is false.

I mean that with your previous and this changes, the header map entry looks more and more as the normal entry, which might make some futher code change erroneously fail to skip it. I want to have some protection and diagnostic for that error.

In D13999#295780, @kib wrote:

Is there an assert somewhere that the map header is never returned by a lookup ?

Punctuate comments.

Endeavor to properly delete a tree node with no left child.

Throw everything back in.

Null the children of the item being inserted.

Fix function name.

Missing *

Let splay() do the insertion of a new node.

Small changes to splay and unlink that I expect to break nothing.

Back up to where I think things last worked, to start a search for where things broke again.

Update a comment.

The changed behavior of the splay function merits a renaming, to vm_map_splay from vm_map_entry_splay.

Reduce the size of the diff a bit.

Move all tree manipulation into the splay function, by passing a map argument instead of a pointer to root, and a supplementary argument to control whether an item is inserted, or deleted, or neither. Add a assertion on splay that the address is within map bounds.

Perhaps I found a problem with linking a new entry at the beginning. Perhaps I fixed it.

Put everything back in, including a fix for the failure to initialize *entry on an out-of-bounds lookup, and await news.

Returning early cannot mean leaving the *entry value uninitialized.

Drop the early exit for out-of-range addresses, which leaves *entry uninitialized.

Fix the broken binary search.

The map is not an argument to vm_map_entry_splay, so the range data is not available to form an assertion.

Restore the modifications to the tree search, and restore the range check to lookup_entry, and wait to see if those changes can be blamed for what's wrong in the big patch.

The origin of this patch is that I am developing changes to vm_map_entry_splay that require the address to lie within the map range, and a Peter Holm test reveals that not to be the case in at least one instance:

Throw out everything except the changes to the splay function, to see if a problem regarding rc scripts resides there.

Fix another error from rushed editting. I'm surprised that it compiled.

Avoid duplicated comparisons in splay.

Have lookup_entry check that address is within map range before splaying.

Try again to fix the right-right problem, without compilation errors. Thanks again, Peter.

Remember to compare to end before comparing to start in the case when the first splay step is to the right and we have to consider whether the next splay step is also to the right.

Provide more debug information when a splay assertion fails.

Initialize map->header.max_free too.

Initialize map->header.adj_free in _vm_map_init.

Fix a compilation error that I'm embarrassed to have included in the previous version.

Apply suggested changes to indentation.

I have addressed the comments (made offline) from alc. He has stated that he has no objections to the resulting patch, but that I will have to rely on someone else to give it final approval and checkin. I'd appreciate that help from somebody, please.

Add a comment regarding the use of sentinel values.

Make recommended formatting changes to a couple of loops.

Add recommended space to one comment.

Apply reviewer suggestions.

Peter Holm, can you please stress test this patch at your convenience?