Details

Reviewers

markj
kib
alc

Commits

rS351476: vm_map_simplify_entry considers merging an entry with its two

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

Diff Detail

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

dougm created this revision.Jul 1 2019, 4:10 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

Drop all the changes related to wiring and unwiring.

Code formatting and comment changes.

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
2570–2571	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
2570–2571	Sorry, never mind.

markj added inline comments.Jul 23 2019, 3:26 PM

sys/vm/vm_map.c
2088	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
2570–2571	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?

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

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
2464–2469	What happens here when "start == 0"?

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
2464–2469	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

Use vm_map_try_merge_entries instead of vm_simplify_entry in vm_map_inherit.

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

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

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

Don't unlock on early exit from map_wire_locked.

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

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

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

Ready for review....

kib added inline comments.Aug 17 2019, 11:31 AM

sys/vm/vm_map.c
2090	Assert that the map is exclusively locked.
2468	extra ()
2989	This pattern repeats more than once. Might be it makes sense to create a helper, e.g. vm_map_lookup_entry_and_prev() ?

Apply reviewer suggestions.

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.

Simplify the patch.

In D20814#463451, @dougm wrote:

Simplify the patch.

Thank you.

sys/security/mac/mac_process.c
267–269	This case didn't get simplified.
353	(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–2084	The clause beginning with "and" seems wrong. Specifically, it has the "direction" of the merge backwards.

Apply reviewer directives.

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

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

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

Closed by commit rS351476: vm_map_simplify_entry considers merging an entry with its two (authored by dougm). · Explain WhyAug 25 2019, 7:07 AM

This revision was automatically updated to reflect the committed changes.

dougm added a commit: rS351476: vm_map_simplify_entry considers merging an entry with its two.

Herald added a subscriber: imp. · View Herald TranscriptAug 25 2019, 7:07 AM

Make entry simplification one-way
ClosedPublic
Actions

Details

Diff Detail

Event Timeline

Revision Contents
Changeset List

Diff 60344

sys/security/mac/mac_process.c

sys/vm/vm_map.h

sys/vm/vm_map.c

Make entry simplification one-wayClosedPublicActions

Details

Diff Detail

Event Timeline

Revision ContentsChangeset List

Diff 60344

sys/security/mac/mac_process.c

sys/vm/vm_map.h

sys/vm/vm_map.c

Make entry simplification one-way
ClosedPublic
Actions

Revision Contents
Changeset List