Page MenuHomeFreeBSD

Make vm_map a threaded tree
Needs ReviewPublic

Authored by dougm on Thu, Oct 10, 4:47 AM.

Details

Reviewers
alc
markj
kib
Summary

Change the vm_map tree so that it is threaded; where a NULL pointer appears as a left child now, point to the previous item, and where a NULL pointer appears as a right child, point to the next item. Where there is no previous or next item, point to the map header.

Remove the prev pointer, and use a simple walk - of expected length 2 - to find it using left and right pointers. Take more opportunities to keep trailing pointers when iterating forward, to avoid unnecessary calculation.

Remove the next pointer. Where it is used to keep a deferred list of map entries, use the right field instead. Where it is used to find the next entry in the ordered set, use a function to calculate that entry.

The change reduces the size of vm_map_entry, obviously. On a pair of tests that do nothing but create and free map entries, it reduces running time and data cache miss counts slightly.


Modified
time, dc-misses, 5 tests
18.469429 612149521
18.513463 626840441
18.493864 606433178
18.436925 612354290
18.500854 610673693

Original
time, dc-misses, 5 tests
18.919835 664324381
19.31932 681685132
18.940139 665389818
18.917524 675577608
18.922143 652591840


Modified
time, dc-misses, 5 tests
17.633731 580057420
17.709786 599025250
17.681210 579837458
17.617679 567257058
17.720645 566887599

Original
time, dc-misses, 5 tests
18.44355 629452843
18.184409 626960073
18.199191 633834727
17.992720 625547426
17.986247 619292654

On a test that mostly just walks the list of entries, performance is slightly reduced, since there is no precomputed 'next' pointer to follow.


Modified, times, 10 samples
0.31
0.32
0.31
0.30
0.31
0.30
0.31
0.31
0.30
0.31

Original times, 10 samples
0.30
0.28
0.27
0.27
0.29
0.27
0.29
0.27
0.26
0.28

Diff Detail

Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

dougm created this revision.Thu, Oct 10, 4:47 AM
pho added a comment.Thu, Oct 10, 11:24 AM
startup_alloc from "UMA Zones", 4 boot pages left
startup_alloc from "UMA Zones", 3 boot pages left
startup_alloc from "UMA Hash", 2 boot pages left
startup_alloc from "UMA Zones", 1 boot pages left
Entering uma_startup1 with 0 boot pages left
panic: map 0xfffff80003002000 max = 7d8df000, max_left = 1ff80000000, max_right = 7d8df000
cpuid = 0
time = 1
KDB: stack backtrace:
db_trace_self_wrapper() at db_trace_self_wrapper+0x2b/frame 0xffffffff824ef830
vpanic() at vpanic+0x19d/frame 0xffffffff824ef880
panic() at panic+0x43/frame 0xffffffff824ef8e0
_vm_map_assert_consistent() at _vm_map_assert_consistent+0x3e1/frame 0xffffffff824ef940
vm_map_splay() at vm_map_splay+0x176/frame 0xffffffff824ef9a0
vm_map_lookup_entry() at vm_map_lookup_entry+0xc7/frame 0xffffffff824ef9f0
vm_map_insert() at vm_map_insert+0x1b5/frame 0xffffffff824efae0
kmem_init() at kmem_init+0xab/frame 0xffffffff824efb10
vm_mem_init() at vm_mem_init+0x51/frame 0xffffffff824efb20
mi_startup() at mi_startup+0x210/frame 0xffffffff824efb70
btext() at btext+0x2c
KDB: enter: panic
[ thread pid 0 tid 0 ]
Stopped at      kdb_enter+0x3b: movq    $0,kdb_why
db> x/s version
version:        FreeBSD 13.0-CURRENT #1 r353388M: Thu Oct 10 12:56:20 CEST 2019\012    pho@mercat1.netperf.freebsd.org:/usr/src/sys/amd64/compile/PHO\012
db>
dougm updated this revision to Diff 63130.Thu, Oct 10, 6:38 PM
pho added a comment.Sat, Oct 12, 7:13 PM

I ran all of the stress2 test on 63130. I found one problem, which to me looks unrelated.
https://people.freebsd.org/~pho/stress/log/quota10-2.txt

kib added a comment.Sun, Oct 13, 3:19 PM

What do you mean by idle map entries ? The deferred list ?

sys/vm/vm_map.c
977

Isn't this a do/while loop ? You use do/while in most other places.

5011

Can you commit just the move of vm_map_assert_consistent so that any changes are visible ?

dougm edited the summary of this revision. (Show Details)Mon, Oct 14, 5:21 PM
dougm updated this revision to Diff 63259.Mon, Oct 14, 5:24 PM
dougm marked 2 inline comments as done.

Reformat vm_map_entry_{pred,succ}.

Incorporate changes just checked in to move the vm_map validation code.

alc added a comment.Mon, Oct 14, 5:36 PM
In D21964#480590, @pho wrote:

I ran all of the stress2 test on 63130. I found one problem, which to me looks unrelated.
https://people.freebsd.org/~pho/stress/log/quota10-2.txt

Peter,

Are you setting debug.vmmap_check to 1?

dougm updated this revision to Diff 63267.Mon, Oct 14, 6:26 PM

Restore the invariant-checking code that fell out of the last patch.

pho added a comment.Mon, Oct 14, 6:41 PM
In D21964#481052, @alc wrote:
In D21964#480590, @pho wrote:

I ran all of the stress2 test on 63130. I found one problem, which to me looks unrelated.
https://people.freebsd.org/~pho/stress/log/quota10-2.txt

Peter,
Are you setting debug.vmmap_check to 1?

Thank you for reminding me. I'll do that with the test of Diff 63267.

pho added a comment.Tue, Oct 15, 8:17 AM

With debug.vmmap_check=1 I saw this problem:
https://people.freebsd.org/~pho/stress/log/dougm056.txt