Make entry simplification one-way

[dougm]

Summary

vm_map_simplify_entry considers merging an entry with its two neighbors, and is used in a way so that if entries a and b cannot be merged, we consider them twice, first not-merging a with its successor b, and then not-merging b with its predecessor a. This change would mostly replace vm_map_simplify_entry with a new function that compares two adjacent entries only, and uses it to avoid duplicated merge-checks.

Change loops that use vm_map_simplify_entry to use vm_map_try_merge_entries instead.
Change other vm_map_simplify_entry calls to use a pair of vm_map_merge_entry calls.

Test Plan

Compiles, boots, passes simple tests. Stress testing by Peter Holm was performed on a much different patch, and those tests need to be repeated.

A performance test

mprotector.c752 BDownload

run 10 times with and without this change produces these results.

Without:
time 0.31
time 0.26
time 0.26
time 0.26
time 0.27
time 0.30
time 0.28
time 0.30
time 0.28
time 0.28

With:
time 0.27
time 0.27
time 0.26
time 0.25
time 0.26
time 0.26
time 0.26
time 0.26
time 0.27
time 0.26

[pho]

20190701 07:18:49 all (2/70): mmap10.sh
panic: _vm_map_clip_start: invalid clip of entry 0xfffff801496d34d0
cpuid = 9
time = 1561958339
KDB: stack backtrace:
db_trace_self_wrapper() at db_trace_self_wrapper+0x2b/frame 0xfffffe00ad7307a0
vpanic() at vpanic+0x19d/frame 0xfffffe00ad7307f0
panic() at panic+0x43/frame 0xfffffe00ad730850
_vm_map_clip_start() at _vm_map_clip_start+0x81/frame 0xfffffe00ad730890
vm_map_unwire() at vm_map_unwire+0x350/frame 0xfffffe00ad730960
sys_munlockall() at sys_munlockall+0x71/frame 0xfffffe00ad730990
amd64_syscall() at amd64_syscall+0x291/frame 0xfffffe00ad730ab0
fast_syscall_common() at fast_syscall_common+0x101/frame 0xfffffe00ad730ab0

https://people.freebsd.org/~pho/stress/log/dougm043.txt

PS
Just a *very* minor point: When you generate diffs, would it be possible to always generate it from the top of the SVN or git tree?

[dougm]

Drop all the changes related to wiring and unwiring.

[dougm]

Code formatting and comment changes.

[pho]

I ran a brief 4 hour test with this patch.

[markj]

sys/vm/vm_map.c

2598 ↗

(On Diff #59945)

Don't we want to attempt simplification after updating current->protection?

[markj]

sys/vm/vm_map.c

2598 ↗

(On Diff #59945)

Sorry, never mind.

[markj]

sys/vm/vm_map.c

2088 ↗

(On Diff #59945)

I'd suggest a name like vm_map_try_merge_entries() instead.

[dougm]

sys/vm/vm_map.c

2598 ↗

(On Diff #59945)

We do. We are now. After this change, we still would be.

Is this a suggestion about correctness or style - that, do you just want to move the simplification to line before "For user wired map entries...." to make clearer why we're simplifying, or are you suggesting that something gets broken here?

[dougm]

Rename vm_map_merge_entries to vm_map_try_merge_entries.

[alc]

I would suggest writing a microbenchmark to demonstrate that this change can reduce the execution time for one of the affected functions. For example, write a program that mmap(MAP_ANON)'s a gigabyte of PROT_WRITE virtual address space, iterates over that space removing PROT_WRITE on every other page, and then measure the time to perform a single mprotect() restoring PROT_WRITE to the entire gigabyte of virtual address space.

sys/vm/vm_map.c

2495–2496 ↗

(On Diff #60048)

What happens here when "start == 0"?

[dougm]

In looking for the map entry that includes the page before page 0, use &map->header explicitly instead of using vm_map_lookup_entry.

[dougm]

sys/vm/vm_map.c

2495–2496 ↗

(On Diff #60048)

We get prev==&map->header. Before the most recent change, something bad would have happened.

[dougm]

Use vm_map_try_merge_entries instead of vm_simplify_entry in vm_map_inherit.

[pho]

I tested D20814.60178.diff for 13 hours on amd64 without seeing any problems.

[dougm]

Get rid of the remaining uses of vm_map_simplify_entry.

Request retest from Peter Holm.

[pho]

D20814.60315.diff

20190731 16:18:08 all (17/73): mmap10.sh
panic: Lock vm map (user) not exclusively locked @ ../../../vm/vm_map.c:3102
cpuid = 12
time = 1564582693
KDB: stack backtrace:
db_trace_self_wrapper() at db_trace_self_wrapper+0x2b/frame 0xfffffe00c7c80800
vpanic() at vpanic+0x19d/frame 0xfffffe00c7c80850
panic() at panic+0x43/frame 0xfffffe00c7c808b0
_sx_xunlock() at _sx_xunlock+0xab/frame 0xfffffe00c7c808d0
_vm_map_unlock() at _vm_map_unlock+0x75/frame 0xfffffe00c7c80900
vm_map_wire() at vm_map_wire+0x58/frame 0xfffffe00c7c80930
kern_mlock() at kern_mlock+0x179/frame 0xfffffe00c7c80980
amd64_syscall() at amd64_syscall+0x2d6/frame 0xfffffe00c7c80ab0

https://people.freebsd.org/~pho/stress/log/dougm054.txt

[dougm]

Don't unlock on early exit from map_wire_locked.

[pho]

With D20814.60322.diff I got:

20190731 19:27:23 all (1/1): mmap10.sh
panic: vm_map_unwire: lookup failed
cpuid = 12
time = 1564594061
KDB: stack backtrace:
db_trace_self_wrapper() at db_trace_self_wrapper+0x2b/frame 0xfffffe00c96c5790
vpanic() at vpanic+0x19d/frame 0xfffffe00c96c57e0
panic() at panic+0x43/frame 0xfffffe00c96c5840
vm_map_wire_locked() at vm_map_wire_locked+0x69d/frame 0xfffffe00c96c5900
vm_map_wire() at vm_map_wire+0x40/frame 0xfffffe00c96c5930
kern_mlock() at kern_mlock+0x179/frame 0xfffffe00c96c5980
amd64_syscall() at amd64_syscall+0x2d6/frame 0xfffffe00c96c5ab0
fast_syscall_common() at fast_syscall_common+0x101/frame 0xfffffe00c96c5ab0

https://people.freebsd.org/~pho/stress/log/dougm055.txt

[dougm]

Fix function naming mismatches in KASSERTS. In wire/unwire, make sure to clip after first entry found in transition.

[pho]

I ran tests for 15 hours on D20814.60344.diff without seeing any problems.

[dougm]

Ready for review....

[kib]

sys/vm/vm_map.c

2090 ↗

(On Diff #60344)

Assert that the map is exclusively locked.

2468 ↗

(On Diff #60344)

extra ()

2989 ↗

(On Diff #60344)

This pattern repeats more than once. Might be it makes sense to create a helper, e.g. vm_map_lookup_entry_and_prev() ?

[dougm]

Apply reviewer suggestions.

[alc]

My major concern with this change is that it is doing two things at once, and I would ask that these two things be done separately, so that they can be individually evaluated. As the title says, this change is making simplification one way. However, most of this change is actually about decommissioning the "prev" pointer in the map entry.

A change that simply makes simplification one way doesn't require changing the loops over the map to maintain a local "prev" pointer. Internally, the one-way simplification function could simply use the map entry's "prev" pointer rather than having to modify every caller to pass it in. Moreover, making the callers maintain a local "prev" pointer rather than fetching it in the one-way simplification function isn't necessarily an optimization. In complex callers, especially where helper functions are being called, the "prev" pointer is probably winding up on the stack rather than being held in a register.

In summary, a change to make simplification one-way can be a lot simpler than what is presented here, and the change to eliminate the "prev" pointer really needs to be "atomic", i.e., it needs to be separate and complete, to properly evaluate it.

[dougm]

Simplify the patch.

[alc]

In D20814#463451, @dougm wrote:

Simplify the patch.

Thank you.

sys/security/mac/mac_process.c

267–268 ↗

(On Diff #60954)

This case didn't get simplified.

353 ↗

(On Diff #60954)

(This comment is unrelated to the patch.) This looks like a bug to me, albeit an arguably innocuous one. If mac_mmap_revocation_via_cow is false, we should not be making the map entry COW.

sys/vm/vm_map.c

2081–2082 ↗

(On Diff #60954)

The clause beginning with "and" seems wrong. Specifically, it has the "direction" of the merge backwards.

[dougm]

Apply reviewer directives.

[alc]

This looks good. Can you please repeat the performance test with and without this patch.

A different variation on your performance test that exercises minherit() in a similar way would probably show an even greater speedup.

[pho]

I should be able to free up some test hardware later today.

[pho]

I ran the full stress2 test with D20814.61081.diff on amd64. LGTM.