Page MenuHomeFreeBSD

add map header sentinel to vm_map search tree
Needs ReviewPublic

Authored by dougm_rice.edu on Jan 20 2018, 7:09 PM.

Details

Reviewers
alc
Summary

Make the map->header sentinel a part of the initial vm_map binary search tree. Change the order of search tree comparisons so that the end field is tested before the start field, so that the map->header sentinel will always be the leftmost member of the search tree. Change the method of handling search failure in splay so that the new tree root after failure always becomes the largest map entry less than the address sought; such an entry must exist because the sentinel is less than any address sought. Have splay handle tree insertions and deletions. Have splay work on maps, rather than map entries. Change the splay code to eliminate duplicated comparisons. Rename vm_map_entry_splay to vm_map_splay.

Test Plan

I request that Peter Holm apply his robustness tests to this patch.

Diff Detail

Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

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

I'm not sure what a previous message about 'rc problems' refers to, so I'm unlikely to have fixed them here.

pho added a comment.Jan 22 2018, 9:27 PM

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

I'm not sure what a previous message about 'rc problems' refers to, so I'm unlikely to have fixed them here.

The rc problems can be seen in https://people.freebsd.org/~pho/stress/log/dougm003.txt
I'll try this version.

pho added a comment.Jan 22 2018, 9:55 PM

This version boots, but scripts in /etc/rc.d fails as can be seen here: https://people.freebsd.org/~pho/stress/log/dougm004.txt

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

pho added a comment.Jan 23 2018, 7:57 AM

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

Yes, that boots without any problems on both i386 and amd64.

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.

pho added a comment.Jan 23 2018, 10:00 AM

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.

FreeBSD 12.0-CURRENT #1 r328277M: Tue Jan 23 10:55:42 CET 2018
    pho@x4.osted.lan:/usr/src/sys/i386/compile/PHO i386
FreeBSD clang version 6.0.0 (branches/release_60 321788) (based on LLVM 6.0.0)
WARNING: WITNESS option enabled, expect reduced performance.
WARNING: DIAGNOSTIC option enabled, expect reduced performance.
kernel trap 12 with interrupts disabled


Fatal trap 12: page fault while in kernel mode
cpuid = 0; apic id = 00
fault virtual address   = 0x14
fault code              = supervisor read, page not present
instruction pointer     = 0x20:0xc0fbcfa1
stack pointer           = 0x28:0xc2022c38
frame pointer           = 0x28:0xc2022c54
code segment            = base 0x0, limit 0xfffff, type 0x1b
                        = DPL 0, pres 1, def32 1, gran 1
processor eflags        = resume, IOPL = 0
current process         = 0 ()
[ thread pid 0 tid 0 ]
Stopped at      vm_map_lookup_entry+0xa1:       cmpl    %esi,0x14(%edi)
db> bt
Tracing pid 0 tid 0 td 0xc1be0940
vm_map_lookup_entry(c237e000,bfeff000,c2022c74,4c8,c237e058,...) at vm_map_lookup_entry+0xa1/frame 0xc2022c54
vm_map_insert(c237e000,0,0,0,bfeff000,...) at vm_map_insert+0xe4/frame 0xc2022cb0
kmem_init(c66ef000,fffff000,c12accbb,c2022d0c,c2022d0c,...) at kmem_init+0x8e/frame 0xc2022ce4
vm_mem_init(0,0,0,0,c1865550,...) at vm_mem_init+0x45/frame 0xc2022d10
mi_startup() at mi_startup+0xf7/frame 0xc2022d38
begin() at begin+0x2f
db>

Fix the broken binary search.

pho added a comment.Jan 23 2018, 4:53 PM

Fix the broken binary search.

Yes, it boots. The first test I ran however triggered this:

Fatal trap 12: page fault while in kernel mode
cpuid = 2; apic id = 02
fault virtual address = 0x5b5f5e44
fault code = supervisor read, page not present
instruction pointer = 0x20:0xc0fbf4ab
stack pointer = 0x28:0xcb0b8b90
frame pointer = 0x28:0xcb0b8bc8
code segment = base 0x0, limit 0xfffff, type 0x1b
DPL 0, pres 1, def32 1, gran 1
processor eflags = interrupt enabled, resume, IOPL = 0
current process = 33157 (tmprotect)
...
I can not break into the debugger and do not have NMI on this box.
I'll try to see if I can get some more info on a host with amd64.

...

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

pho added a comment.Jan 23 2018, 8:03 PM

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

This looks promising. Uptime is 1:40 hours.

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

pho added a comment.Jan 24 2018, 6:18 AM

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

The startup fails with this patch.

Mounting late filesystems:.
echo: write error on stdout
echo: write error on stdout
echo: write error on stdout
echo: write error on stdout
echo: write error on stdout
echo: write error on stdout
Starting ntpd.
Starting powerd.
Starting saslauthd.
Jan 24 07:13:39 t1 saslauthd[771]: detach_tty : could not write success result to startup pipe
saslauthd[770] :detach_tty : Cannot start saslauthd
saslauthd[770] :detach_tty : could not read from startup_pipe
/etc/rc: WARNING: failed to start saslauthd
Jan 24 07:13:39 t1 saslauthd[770]: detach_tty : Cannot start saslauthd
Jan 24 07:13:39 t1 saslauthd[770]: detach_tty : could not read from startup_pipe
Configuring syscons: keymap blanktime.
echo: write error on stdout
echo: write error on stdout
echo: write error on stdout
echo: write error on stdout
echo: write error on stdout

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

pho added a comment.Jan 24 2018, 9:14 AM

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

Yes, that fixed the boot issue!

pho added a comment.Jan 24 2018, 2:58 PM
In D13999#294509, @pho wrote:

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

Yes, that fixed the boot issue!

I ran tests for 6 hours without finding any problems. I can run the full test set once your patch is ready for commit.

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.

Reduce the size of the diff a bit.

dougm_rice.edu edited the summary of this revision. (Show Details)Jan 25 2018, 4:05 AM

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

dougm_rice.edu edited the summary of this revision. (Show Details)Jan 25 2018, 5:28 AM

Update a comment.

pho added a comment.Jan 25 2018, 8:40 AM

Update a comment.

And I thought we were all done :)

FreeBSD 12.0-CURRENT #2 r328332M: Thu Jan 25 09:26:26 CET 2018
    pho@x4.osted.lan:/usr/src/sys/i386/compile/PHO i386
FreeBSD clang version 6.0.0 (branches/release_60 321788) (based on LLVM 6.0.0)
WARNING: WITNESS option enabled, expect reduced performance.
WARNING: DIAGNOSTIC option enabled, expect reduced performance.
kernel trap 12 with interrupts disabled
panic: _mtx_lock_sleep: recursed on non-recursive mutex vm map (system) @ ../../../vm/vm_map.c:4093

cpuid = 0
time = 1
KDB: stack backtrace:
db_trace_self_wrapper(c1653848,20296d65,2e2e2040,2f2e2e2f,762f2e2e,...) at db_trace_self_wrapper+0x2a/frame 0xc2022678
kdb_backtrace(c164d8f7,1,0,c2022744,0,...) at kdb_backtrace+0x2d/frame 0xc20226e0
vpanic(c164a42a,c2022744,c164a42a,c2022744,c2022744,...) at vpanic+0x133/frame 0xc2022714
kassert_panic(c164a42a,c16581be,c16a13be,ffd,c1be5040,...) at kassert_panic+0xd9/frame 0xc2022738
__mtx_lock_sleep(c237e068,c1be5040,0,c16a13be,ffd,...) at __mtx_lock_sleep+0x420/frame 0xc20227a4
__mtx_lock_flags(c237e068,0,c16a13be,ffd,ff000000,...) at __mtx_lock_flags+0x107/frame 0xc20227d4
_vm_map_lock_read(c237e000,c16a13be,ffd,ff000000,c20227d6,...) at _vm_map_lock_read+0x52/frame 0xc2022808
vm_map_lookup(c20228f8,deadc000,11,c20228fc,c20228ec,...) at vm_map_lookup+0x6f/frame 0xc20228a8
vm_fault_hold(c237e000,deadc000,1,0,0,...) at vm_fault_hold+0xd1/frame 0xc2022988
vm_fault(c237e000,deadc000,1,0,0,...) at vm_fault+0x83/frame 0xc20229b0
trap_pfault(deadc0fe,c,c0c53e97,c237f000,8,...) at trap_pfault+0x109/frame 0xc20229f8
trap(c2022afc) at trap+0x3c2/frame 0xc2022af0
calltrap() at calltrap+0x6/frame 0xc2022af0
trap 0xc, eip = 0xc0fc811a, esp = 0xc2022b3c, ebp = 0xc2022b40 ---
vm_map_entry_set_max_free(c237e000,c2379e10,c1be5040,c2380000,0,...) at vm_map_entry_set_max_free+0x5a/frame 0xc2022b40
vm_map_splay(bfeff000,c237e000,c2022bf8,1,c66ef000,bfeff000,c2022be8,436,c237e000,c237e000,c2380000) at vm_map_splay+0x3dc/frame 0xc2022ba8
vm_map_entry_link(c237e000,c237e000,0,2,20,...) at vm_map_entry_link+0x170/frame 0xc2022be8
vm_map_insert(c237e000,0,0,0,bfeff000,...) at vm_map_insert+0xa47/frame 0xc2022cb0
kmem_init(c66ef000,fffff000,c12b137b,c2022d0c,c2022d0c,...) at kmem_init+0x8e/frame 0xc2022ce4
vm_mem_init(0,0,0,0,c1869c50,...) at vm_mem_init+0x45/frame 0xc2022d10
mi_startup() at mi_startup+0xf7/frame 0xc2022d38
begin() at begin+0x2f
KDB: enter: panic
[ thread pid 0 tid 0 ]
Stopped at      kdb_enter+0x3a: movl    $0,kdb_why
db>

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

pho added a comment.Jan 25 2018, 10:01 AM

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

38440 boots.

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

pho added a comment.Jan 25 2018, 4:58 PM

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

Right. 38452 boots.

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

pho added a comment.Jan 25 2018, 6:36 PM

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

../../../vm/vm_map.c:988:17: error: invalid operands to binary expression ('struct vm_map_entry' and 'void *')

} else if (*io != NULL && root == NULL) {
           ~~~ ^  ~~~~

../../../vm/vm_map.c:990:8: error: assigning to 'vm_map_entry_t' (aka 'struct vm_map_entry *') from incompatible type 'struct vm_map_entry'; remove *

root = *io;
     ^ ~~~

../../../vm/vm_map.c:991:7: error: assigning to 'struct vm_map_entry' from incompatible type 'void *'

*io = NULL;
    ^ ~~~~

../../../vm/vm_map.c:1055:14: error: implicit declaration of function 'vm_map_splay' is invalid in C99 [-Werror,-Wimplicit-function-declaration]

map->root = vm_map_splay(entry->start, map->root, &entry);
            ^

../../../vm/vm_map.c:1055:14: note: did you mean 'vm_map_pmap'?
../../../vm/vm_map.h:222:1: note: 'vm_map_pmap' declared here
vm_map_pmap(vm_map_t map)
^
../../../vm/vm_map.c:1055:14: error: this function declaration is not a prototype [-Werror,-Wstrict-prototypes]

map->root = vm_map_splay(entry->start, map->root, &entry);
            ^

../../../vm/vm_map.c:1055:12: error: incompatible integer to pointer conversion assigning to 'vm_map_entry_t' (aka 'struct vm_map_entry *') from 'int'

[-Werror,-Wint-conversion]
  map->root = vm_map_splay(entry->start, map->root, &entry);
            ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

...

pho added a comment.Jan 25 2018, 7:32 PM

Missing *

$ cc -c -O0 -pipe  -g -nostdinc  -I. -I../../.. -I../../../contrib/libfdt -D_KERNEL -DHAVE_KERNEL_OPTION_HEADERS -include opt_global.h  -MD  -MF.depend.vm_map.o -MTvm_map.o -mno-mmx -mno-sse -msoft-float -ffreestanding -fwrapv -fstack-protector -gdwarf-2 -Wall -Wredundant-decls -Wnested-externs -Wstrict-prototypes -Wmissing-prototypes -Wpointer-arith -Winline -Wcast-qual -Wundef -Wno-pointer-sign -D__printf__=__freebsd_kprintf__ -Wmissing-include-dirs -fdiagnostics-show-option -Wno-unknown-pragmas -Wno-error-tautological-compare -Wno-error-empty-body -Wno-error-parentheses-equality -Wno-error-unused-function -Wno-error-pointer-sign -Wno-error-shift-negative-value -Wno-error-address-of-packed-member  -mno-aes -mno-avx  -std=iso9899:1999 -Werror  ../../../vm/vm_map.c
../../../vm/vm_map.c:1055:14: error: implicit declaration of function 'vm_map_splay' is invalid in C99 [-Werror,-Wimplicit-function-declaration]
        map->root = vm_map_splay(entry->start, map->root, &entry);
                    ^
../../../vm/vm_map.c:1055:14: note: did you mean 'vm_map_pmap'?
../../../vm/vm_map.h:222:1: note: 'vm_map_pmap' declared here
vm_map_pmap(vm_map_t map)
^
../../../vm/vm_map.c:1055:14: error: this function declaration is not a prototype [-Werror,-Wstrict-prototypes]
        map->root = vm_map_splay(entry->start, map->root, &entry);
                    ^
../../../vm/vm_map.c:1055:12: error: incompatible integer to pointer conversion assigning to 'vm_map_entry_t' (aka 'struct vm_map_entry *') from 'int'
      [-Werror,-Wint-conversion]
        map->root = vm_map_splay(entry->start, map->root, &entry);
                  ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3 errors generated.
$

Fix function name.

pho added a comment.Jan 25 2018, 8:45 PM

Fix function name.

WARNING: DIAGNOSTIC option enabled, expect reduced performance.
kernel trap 12 with interrupts disabled
panic: _mtx_lock_sleep: recursed on non-recursive mutex vm map (system) @ ../../../vm/vm_map.c:4059

cpuid = 0
time = 1
KDB: stack backtrace:
db_trace_self_wrapper(c1653768,20296d65,2e2e2040,2f2e2e2f,762f2e2e,...) at db_trace_self_wrapper+0x2a/frame 0xc20226b0
kdb_backtrace(c164d817,1,0,c202277c,0,...) at kdb_backtrace+0x2d/frame 0xc2022718
vpanic(c164a34a,c202277c,c164a34a,c202277c,c202277c,...) at vpanic+0x133/frame 0xc202274c
kassert_panic(c164a34a,c16580de,c16a12de,fdb,c1be4f40,...) at kassert_panic+0xd9/frame 0xc2022770
__mtx_lock_sleep(c237e068,c1be4f40,0,c16a12de,fdb,...) at __mtx_lock_sleep+0x420/frame 0xc20227dc
__mtx_lock_flags(c237e068,0,c16a12de,fdb,0,...) at __mtx_lock_flags+0x107/frame 0xc202280c
_vm_map_lock_read(c237e000,c16a12de,fdb,0,c202280e,...) at _vm_map_lock_read+0x52/frame 0xc2022840
vm_map_lookup(c2022930,deadc000,11,c2022934,c2022924,...) at vm_map_lookup+0x6f/frame 0xc20228e0
vm_fault_hold(c237e000,deadc000,1,0,0,...) at vm_fault_hold+0xd1/frame 0xc20229c0
vm_fault(c237e000,deadc000,1,0,0,...) at vm_fault+0x83/frame 0xc20229e8
trap_pfault(deadc0fe,c,0,c169fe87,41a,...) at trap_pfault+0x109/frame 0xc2022a30
trap(c2022b34) at trap+0x3c2/frame 0xc2022b28
calltrap() at calltrap+0x6/frame 0xc2022b28
--- trap 0xc, eip = 0xc0fc802a, esp = 0xc2022b74, ebp = 0xc2022b78 ---
vm_map_entry_set_max_free(c237e000,bfeff000,c237e000,c2022bf8,0,...) at vm_map_entry_set_max_free+0x5a/frame 0xc2022b78
vm_map_entry_splay(bfeff000,c2380000,c2022bf8,1,c66ef000,...) at vm_map_entry_splay+0x281/frame 0xc2022ba8
vm_map_entry_link(c237e000,c237e000,0,2,20,...) at vm_map_entry_link+0x173/frame 0xc2022be8
vm_map_insert(c237e000,0,0,0,bfeff000,...) at vm_map_insert+0xa47/frame 0xc2022cb0
kmem_init(c66ef000,fffff000,c12b129b,c2022d0c,c2022d0c,...) at kmem_init+0x8e/frame 0xc2022ce4
vm_mem_init(0,0,0,0,c1869b30,...) at vm_mem_init+0x45/frame 0xc2022d10
mi_startup() at mi_startup+0xf7/frame 0xc2022d38
begin() at begin+0x2f
KDB: enter: panic
[ thread pid 0 tid 0 ]
Stopped at      kdb_enter+0x3a: movl    $0,kdb_why
db>

Null the children of the item being inserted.

pho added a comment.Jan 26 2018, 5:34 AM

Null the children of the item being inserted.

D13999.38458 looks good. Uptime is 5 hours.

Throw everything back in.

pho added a comment.Jan 26 2018, 9:13 AM

Throw everything back in.

uhub4: 2 ports with 2 removable, self powered
uhub5: 2 ports with 2 removable, self powered
WARNING: / was not properly dismounted


Fatal trap 12: page fault while in kernel mode
cpuid = 3; apic id = 03
fault virtual address   = 0xc
fault code              = supervisor read, page not present
instruction pointer     = 0x20:0xc0fbef60
stack pointer           = 0x28:0xd49009a0
frame pointer           = 0x28:0xd4900a00
code segment            = base 0x0, limit 0xfffff, type 0x1b
                        = DPL 0, pres 1, def32 1, gran 1
processor eflags        = interrupt enabled, resume, IOPL = 0
current process         = 1 (init)
[ thread pid 1 tid 100002 ]
Stopped at      vm_map_splay+0x300:     movl    0xc(%eax),%eax
db> bt
Tracing pid 1 tid 100002 td 0xd60f9a80
vm_map_splay(bfbfe000,d6102804,d4900a20,44f,d6102804,...) at vm_map_splay+0x300/frame 0xd4900a00
vm_map_entry_unlink(d6102804,d84931dc,c1942b00,c1942b10,c16a2f0f,...) at vm_map_entry_unlink+0x90/frame 0xd4900a30
vm_map_entry_delete(d6102804,d84931dc,bfbff000,c8f,0,...) at vm_map_entry_delete+0x2f/frame 0xd4900acc
vm_map_delete(d6102804,0,bfc00000,d4900b88,bfc00000,...) at vm_map_delete+0x291/frame 0xd4900b2c
vm_map_remove(d6102804,0,bfc00000,ffffffff,d6102804,...) at vm_map_remove+0xbf/frame 0xd4900b6c
vmspace_dofree(d6102804,1,c16a131b,ffffffff,0,0,5,d6102804) at vmspace_dofree+0x36/frame 0xd4900b88
vmspace_free(d6102804,0,0,3,fffffffe,...) at vmspace_free+0x90/frame 0xd4900bb4
post_execve(d60f9a80,fffffffe,d6102804,bfbfefe4,0,...) at post_execve+0xbb/frame 0xd4900bd8
sys_execve(d60f9a80,d4900c90,0,0,d4900c80,...) at sys_execve+0x80/frame 0xd4900c40
start_init(0,d4900ce8,c1644afc,407,0,...) at start_init+0x2ae/frame 0xd4900cac
fork_exit(c0c0a390,0,d4900ce8) at fork_exit+0x7e/frame 0xd4900cd4
fork_trampoline() at fork_trampoline+0x8/frame 0xd4900cd4
--- trap 0, eip = 0, esp = 0xd4900d20, ebp = 0 ---
db> dump
Cannot dump: no dump device specified.
db> show registers
cs                0x20
ds                0x28
es                0x28
fs                 0x8
gs                0x3b
ss                0x28
eax                  0
ecx         0xd4900a20
edx         0xd6102801
ebx         0xd6102804
esp         0xd49009a0
ebp         0xd4900a00
esi              0x44f
edi         0xd6102804
eip         0xc0fbef60  vm_map_splay+0x300
efl            0x10282
vm_map_splay+0x300:     movl    0xc(%eax),%eax
db> 
(kgdb) l *vm_map_splay+0x300
0xc0fbef60 is in vm_map_splay (../../../vm/vm_map.c:1008).
1003                    root->left = NULL;
1004                    *io = root;
1005                    root = ltree;
1006                    for (;;) {
1007                            /* root is never NULL in here. */
1008                            y = root->right;
1009                            if (y == NULL)
1010                                    break;
1011                            x = root;
1012                            root = y->right;
(kgdb)

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

pho added a comment.Jan 26 2018, 10:57 AM

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

Yes, that boots. Starting tests right now.

Punctuate comments.

kib added a comment.Jan 28 2018, 9:59 AM

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

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.

kib added a comment.Jan 29 2018, 12:30 PM
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#296096, @kib 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.

The previous change made the header map entry look less like a normal entry, since normal entries have start < end, and the header map entry did too, before the change, which is why extra checks were needed in handling it. By making it less normal, with end < start for that node only, it is now harder to mistake for a normal entry.

This change modifies tree-related fields, left and right, and adj_free/max_free, which are modified in tree manipulation. Outside tree-manipulation code here, left and right are not examined. Outside of this file, adj_free and max_free are not examined. So I don't see the big impact globally from this change. The only functions that can return &map->header after this change are the one's that could return it already.

I'm not sure how to apply the protection and diagnostic changes you seek, other than by putting back in all the &map->header tests I took out of loop bound checks in the previous change, because they were no longer necessary. I'd welcome an example of the sort of change you're looking for.

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

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

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.

pho added a comment.Sep 20 2018, 6:18 AM

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.

I have tested this patch with all of the stress2 tests. I also ran a buildworld / installworld. No problems seen.

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.

kib added a comment.Thu, Oct 18, 1:09 PM

Can you extract the helpers functions into separate review ?

sys/vm/vm_map.c
1669

Change the return type to bool ?

1675

Almost all () there and below are excessive, and no need in space before the excessive '(' at this line.

1678

No need in additional space for indent.

1692

Blank line is needed before start of multi-line comment.

1706

!= NULL

Fix CTR3 compilation error.

Apply recommended style changes.

dougm_rice.edu marked 5 inline comments as done.Thu, Oct 18, 5:07 PM

Update to adjust to recent changes in adjacent code.

pho added a comment.Sun, Oct 21, 6:36 AM

Update to adjust to recent changes in adjacent code.

startup_alloc from "UMA Zones", 12 boot pages left
startup_alloc from "UMA Zones", 8 boot pages left
startup_alloc from "UMA Zones", 4 boot pages left
kernel trap 12 with interrupts disabled
Kernel page fault with the following non-sleepable locks held:
exclusive sleep mutex vm map (system) (vm map (system)) r = 0 (0xfffff80100001098) locked @ vm/vm_kern.c:730
stack backtrace:
#0 0xffffffff80bf9563 at ??+0
#1 0xffffffff80bfa4af at ??+0
#2 0xffffffff81069063 at ??+0
#3 0xffffffff8106869a at ??+0
#4 0xffffffff81043185 at ??+0
#5 0xffffffff80ed2843 at ??+0
#6 0xffffffff80ed0aa2 at ??+0
#7 0xffffffff80ecf717 at ??+0
#8 0xffffffff80b27ba8 at ??+0
#9 0xffffffff8034502c at ??+0


Fatal trap 12: page fault while in kernel mode
cpuid = 0; apic id = 00
fault virtual address   = 0x0
fault code              = supervisor write data, page not present
instruction pointer     = 0x20:0xffffffff80ed21c8
stack pointer           = 0x28:0xffffffff8270e2d0
frame pointer           = 0x28:0xffffffff8270e2f0
code segment            = base 0x0, limit 0xfffff, type 0x1b
                        = DPL 0, pres 1, long 1, def32 0, gran 1
processor eflags        = resume, IOPL = 0
current process         = 0 ()
[ thread pid 0 tid 0 ]
Stopped at      vm_map_splay+0x1c8:     movq    %r11,(%r9)
db> bt
Tracing pid 0 tid 0 td 0xffffffff8208e100
vm_map_splay() at vm_map_splay+0x1c8/frame 0xffffffff8270e2f0
vm_map_insert() at vm_map_insert+0x453/frame 0xffffffff8270e390
kmem_init() at kmem_init+0x72/frame 0xffffffff8270e3c0
vm_mem_init() at vm_mem_init+0x47/frame 0xffffffff8270e3d0
mi_startup() at mi_startup+0x118/frame 0xffffffff8270e3f0
btext() at btext+0x2c
db> x/s version
version:        FreeBSD 13.0-CURRENT #0 r339523M: Sun Oct 21 08:17:58 CEST 2018\012    pho@flix1a.net

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

pho added a comment.Sun, Oct 21, 8:20 AM

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

start_init: trying /sbin/init
Expensive timeout(9) function: 0xffffffff80a01180(0xffffffff81af3bd0) 0.010507480 s


Fatal trap 9: general protection fault while in kernel mode
cpuid = 32; apic id = 26
instruction pointer     = 0x20:0xffffffff80ed205d
stack pointer           = 0x28:0xfffffe00edb16fc0
frame pointer           = 0x28:0xfffffe00edb16fe0
code segment            = base 0x0, limit 0xfffff, type 0x1b
                        = DPL 0, pres 1, long 1, def32 0, gran 1
processor eflags        = interrupt enabled, resume, IOPL = 0
current process         = 132 (ifconfig)
[ thread pid 132 tid 100753 ]
Stopped at      vm_map_splay+0x5d:      cmpq    %r8,ll+0x7(%rcx)
db> bt
Tracing pid 132 tid 100753 td 0xfffff8010f80d580
vm_map_splay() at vm_map_splay+0x5d/frame 0xfffffe00edb16fe0
vm_map_simplify_entry() at vm_map_simplify_entry+0x1c1/frame 0xfffffe00edb17010
vm_map_unwire() at vm_map_unwire+0x4b3/frame 0xfffffe00edb170a0
userland_sysctl() at userland_sysctl+0x20b/frame 0xfffffe00edb17150
sys___sysctl() at sys___sysctl+0x5f/frame 0xfffffe00edb17200
amd64_syscall() at amd64_syscall+0x293/frame 0xfffffe00edb17330
fast_syscall_common() at fast_syscall_common+0x101/frame 0xfffffe00edb17330
--- syscall (202, FreeBSD ELF64, sys___sysctl), rip = 0x80047bfda, rsp = 0x7fffffffe418, rbp = 0x7fffffffe450 ---
db> x/s version
version:        FreeBSD 13.0-CURRENT #2 r339523M: Sun Oct 21 09:50:31 CEST 2018\012    pho@flix1a.netperf.freebsd.org:/usr/src/sys/amd64/compile/PHO\012
db>

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

pho added a comment.Sun, Oct 21, 9:26 AM

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

Yes, this boots.

Updating to adapt changes to surrounding code. Hoping that this code still works.