Replace RB color field with tag bits in the parent pointer

[dougm]

Summary

Eliminate the color field from the RB element struct. Identify the color of a node (or, really, the color of the link from the parent to the node) by using one of the last two bits of the parent pointer in that parent node. Adjust rebalancing methods to account for where colors are stored, and the fact that null children have a color too.

Adjust RB_PARENT and RB_SET_PARENT to account for this change.

Test Plan

I've run hours of random insertions and deletions on a tree, verifying its correctness after every step, but not tested it as part of the kernel.

[dougm]

Clean up RB_SET_PARENT.

[pho]

Unfortunately a kernel with D25418.73541.diff applied does not compile.

[dougm]

Fixup RB_SET_PARENT after a hasty cut and paste.

[pho]

20200624 09:12:49 all (32/724): seekdir.sh

Fatal trap 12: page fault while in kernel mode
cpuid = 22; apic id = 2a
fault virtual address   = 0x10
fault code              = supervisor read data, page not present
instruction pointer     = 0x20:0xffffffff8235e190
stack pointer           = 0x28:0xfffffe013b20b7d0
frame pointer           = 0x28:0xfffffe013b20b7d0
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         = 32457 (seekdir)
trap number             = 12
panic: page fault
cpuid = 22
time = 1592982773
KDB: stack backtrace:
db_trace_self_wrapper() at db_trace_self_wrapper+0x2b/frame 0xfffffe013b20b480
vpanic() at vpanic+0x182/frame 0xfffffe013b20b4d0
panic() at panic+0x43/frame 0xfffffe013b20b530
trap_fatal() at trap_fatal+0x387/frame 0xfffffe013b20b590
trap_pfault() at trap_pfault+0x99/frame 0xfffffe013b20b5f0
trap() at trap+0x2a5/frame 0xfffffe013b20b700
calltrap() at calltrap+0x8/frame 0xfffffe013b20b700
--- trap 0xc, rip = 0xffffffff8235e190, rsp = 0xfffffe013b20b7d0, rbp = 0xfffffe013b20b7d0 ---
tmpfs_dir_RB_REMOVE() at tmpfs_dir_RB_REMOVE+0x180/frame 0xfffffe013b20b7d0
tmpfs_dir_detach() at tmpfs_dir_detach+0x7a/frame 0xfffffe013b20b800
tmpfs_remove() at tmpfs_remove+0x107/frame 0xfffffe013b20b850
VOP_REMOVE_APV() at VOP_REMOVE_APV+0x79/frame 0xfffffe013b20b870
kern_funlinkat() at kern_funlinkat+0x298/frame 0xfffffe013b20bab0
sys_unlink() at sys_unlink+0x28/frame 0xfffffe013b20bad0
amd64_syscall() at amd64_syscall+0x159/frame 0xfffffe013b20bbf0
fast_syscall_common() at fast_syscall_common+0x101/frame 0xfffffe013b20bbf0
--- syscall (10, FreeBSD ELF64, sys_unlink), rip = 0x800420d7a, rsp = 0x7fffffffe198, rbp = 0x7fffffffe590 ---
KDB: enter: panic
[ thread pid 32457 tid 100787 ]
Stopped at      kdb_enter+0x37: movq    $0,0x10c4c36(%rip)
db>

[pho]

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

[dougm]

In RB_REMOVE_COLOR, treat the null parent-of-root as red, to avoid having the next iteration with a null parent pointer.

[• hselasky]

With the latest version of this patch, my quick test seems to pass for mlx5en and mlx4en.

--HPS

[pho]

I ran a preliminary two hour test followed by a buildworld. No problems seen.

[markj]

sys/sys/tree.h

323

RB_RED_MASK would be a clearer name in my opinion.

329

I would suggest adding a comment explaining the information being encoded here.

332

Similarly here I think it's worth briefly explaining why we don't use the native bool type.

[dougm]

Apply reviewer suggestions.

[markj]

sys/sys/tree.h

341

s/it's/its/

[pho]

I ran tests with this patch for 21 hours (633 tests out of 718) without seeing any issues.