Page MenuHomeFreeBSD

Make entry simplification one-way
ClosedPublic

Authored by dougm on Jul 1 2019, 4:10 AM.

Details

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

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

Diff Detail

Repository
rS FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

dougm created this revision.Jul 1 2019, 4:10 AM
pho added a comment.Jul 1 2019, 5:39 AM
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 removed a reviewer: alc.Jul 6 2019, 6:30 PM
dougm updated this revision to Diff 59739.Jul 14 2019, 5:00 PM

Drop all the changes related to wiring and unwiring.

dougm updated this revision to Diff 59945.Jul 19 2019, 9:19 PM

Code formatting and comment changes.

pho added a comment.Jul 21 2019, 3:59 PM

I ran a brief 4 hour test with this patch.

dougm edited the summary of this revision. (Show Details)Jul 21 2019, 4:32 PM
dougm edited the test plan for this revision. (Show Details)
dougm added reviewers: markj, kib.
markj added inline comments.Jul 23 2019, 2:47 PM
sys/vm/vm_map.c
2598 ↗(On Diff #59945)

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

markj added inline comments.Jul 23 2019, 3:19 PM
sys/vm/vm_map.c
2598 ↗(On Diff #59945)

Sorry, never mind.

markj added inline comments.Jul 23 2019, 3:26 PM
sys/vm/vm_map.c
2088 ↗(On Diff #59945)

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

dougm added inline comments.Jul 23 2019, 3:26 PM
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 updated this revision to Diff 60048.Jul 23 2019, 3:38 PM

Rename vm_map_merge_entries to vm_map_try_merge_entries.

markj accepted this revision.Jul 24 2019, 3:30 PM
This revision is now accepted and ready to land.Jul 24 2019, 3:30 PM
dougm added a subscriber: alc.Jul 24 2019, 3:40 PM
alc added a comment.Jul 25 2019, 10:40 PM

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 updated this revision to Diff 60157.Jul 26 2019, 4:23 AM

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

This revision now requires review to proceed.Jul 26 2019, 4:23 AM
dougm edited the test plan for this revision. (Show Details)Jul 26 2019, 4:28 AM
dougm added inline comments.Jul 26 2019, 4:33 AM
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 edited the test plan for this revision. (Show Details)Jul 26 2019, 4:38 AM
dougm updated this revision to Diff 60178.Jul 26 2019, 9:40 PM
dougm edited the summary of this revision. (Show Details)

Use vm_map_try_merge_entries instead of vm_simplify_entry in vm_map_inherit.

pho added a comment.Jul 27 2019, 11:35 AM

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

dougm added a reviewer: alc.Jul 27 2019, 3:57 PM
dougm removed a subscriber: alc.
dougm edited the test plan for this revision. (Show Details)Jul 28 2019, 6:11 PM
dougm updated this revision to Diff 60315.Jul 31 2019, 5:16 AM

Get rid of the remaining uses of vm_map_simplify_entry.

Request retest from Peter Holm.

dougm edited the summary of this revision. (Show Details)Jul 31 2019, 5:17 AM
pho added a comment.Jul 31 2019, 2:48 PM

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 updated this revision to Diff 60322.Jul 31 2019, 2:58 PM

Don't unlock on early exit from map_wire_locked.

pho added a comment.Jul 31 2019, 5:51 PM

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 updated this revision to Diff 60344.Jul 31 2019, 9:37 PM

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

pho added a comment.Aug 1 2019, 6:57 PM

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

dougm added a comment.Aug 16 2019, 6:53 PM

Ready for review....

kib added inline comments.Aug 17 2019, 11:31 AM
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 updated this revision to Diff 60950.Aug 17 2019, 5:39 PM

Apply reviewer suggestions.

alc added a comment.Aug 17 2019, 6:20 PM

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 updated this revision to Diff 60954.Aug 17 2019, 7:20 PM

Simplify the patch.

alc added a comment.Aug 21 2019, 4:00 PM

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 updated this revision to Diff 61081.Aug 21 2019, 4:27 PM

Apply reviewer directives.

alc accepted this revision.Aug 22 2019, 9:52 PM

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.

This revision is now accepted and ready to land.Aug 22 2019, 9:52 PM
dougm edited the test plan for this revision. (Show Details)Aug 23 2019, 3:14 AM
dougm edited the summary of this revision. (Show Details)Aug 23 2019, 3:20 AM
pho added a comment.Aug 23 2019, 4:58 AM

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

pho added a comment.Aug 25 2019, 7:00 AM

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

This revision was automatically updated to reflect the committed changes.