Replace the rb_color field in an rb_node with a tag in the parent's pointer to the rb_node

[dougm]

Summary

To reduce the size of an rb_node, drop the color field. Set the least significant bit in the pointer to the node from its parent to indicate that the node is red. Have the tree rotation macros leave the old-parent/new-child node red and the new-parent/old-child node black.

This change makes RB_LEFT and RB_RIGHT no longer assignable, and RB_COLOR no longer defined. Any code that modifies the tree or examines a node color would have to be modified after this change.

[pho]

This is the first problem I ran into:

cc -c -O2 -pipe -fno-strict-aliasing  -g -nostdinc  -I. -I../../.. -I../../../contrib/ck/include -I../../../contrib/libfdt -D_KERNEL -DHAVE_KERNEL_OPTION_HEADERS -include opt_global.h -fno-common    -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer -MD  -MF.depend.if_an.o -MTif_an.o -fdebug-prefix-map=./machine=/usr/src/sys/amd64/include -fdebug-prefix-map=./x86=/usr/src/sys/x86/include -mcmodel=kernel -mno-red-zone -mno-mmx -mno-sse -msoft-float  -fno-asynchronous-unwind-tables -ffreestanding -fwrapv -fstack-protector -gdwarf-2 -Wall -Wredundant-decls -Wnested-externs -Wstrict-prototypes -Wmissing-prototypes -Wpointer-arith -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-address-of-packed-member -Wno-format-zero-length   -mno-aes -mno-avx  -std=iso9899:1999 -Werror  ../../../dev/an/if_an.c
In file included from ../../../dev/an/if_an.c:129:
In file included from ../../../netinet/in_var.h:53:
../../../sys/tree.h:323:10: error: 'stdint.h' file not found with <angled> include; use "quotes" instead
#include <stdint.h>
         ^~~~~~~~~~
         "stdint.h"
1 error generated.
*** Error code 1

[pho]

I booted with your patch after fixing a few obvious errors and got:

20200602 21:05:31 all (268/714): tmpfs10.sh                                                                                                                                                                                                                                  [15/1814]
                                                                     
 Fatal trap 12: page fault while in kernel mode                                                                                             
cpuid = 3; apic id = 03                                                                                                                    
fault virtual address   = 0x0                                       
fault code              = supervisor read data, page not present                                                           
                                                                                                                                           
Fatal trap 12: page fault while in kernel mode                                                                                             
cpuid = 7; apic id = 07
fault virtual address   = 0x0  
instruction pointer     = 0x20:0xffffffff8253e210         
stack pointer           = 0x28:0xfffffe02fd0bb7c0


Fatal trap 12: page fault while in kernel mode
Fatal trap 12: page fault while in kernel mode
cpuid = 9; apic id = 09
fault virtual address   = 0x0
frame pointer           = 0x28:0xfffffe02fd0bb7d0
cpuid = 1; 


Fatal trap 12: page fault while in kernel mode
cpuid = 10; Fatal trap 12: page fault while in kernel mode
fault code              = supervisor read data, page not present
cpuid = 5; apic id = 01
fault virtual address   = 0x0
fault code              = supervisor read data, page not present
instruction pointer     = 0x20:0xffffffff8253e210
stack pointer           = 0x28:0xfffffe00ed5387c0
fault code              = supervisor read data, page not present
apic id = 0a
code segment            = base 0x0, limit 0xfffff, type 0x1b
instruction pointer     = 0x20:0xffffffff8253e210
apic id = 05
fault virtual address   = 0x0
fault code              = supervisor read data, page not present
instruction pointer     = 0x20:0xffffffff8253e210
fault virtual address   = 0x0
stack pointer           = 0x28:0xfffffe02fcfad7c0
frame pointer           = 0x28:0xfffffe00ed5387d0
frame pointer           = 0x28:0xfffffe02fcfad7d0
                        = DPL 0, pres 1, long 1, def32 0, gran 1
processor eflags        = interrupt enabled, resume, IOPL = 0
stack pointer           = 0x28:0xfffffe00f23567c0
instruction pointer     = 0x20:0xffffffff8253e210
code segment            = base 0x0, limit 0xfffff, type 0x1b
fault code              = supervisor read data, page not present
instruction pointer     = 0x20:0xffffffff8253e210
stack pointer           = 0x28:0xfffffe00ed55b7c0
frame pointer           = 0x28:0xfffffe00ed55b7d0
code segment            = base 0x0, limit 0xfffff, type 0x1b
frame pointer           = 0x28:0xfffffe00f23567d0
stack pointer           = 0x28:0xfffffe02fcf947c0
current process         = 39475 (tmpfs10)
                        = DPL 0, pres 1, long 1, def32 0, gran 1
processor eflags        = frame pointer         = 0x28:0xfffffe02fcf947d0
code segment            = base 0x0, limit 0xfffff, type 0x1b
interrupt enabled, code segment         = base 0x0, limit 0xfffff, type 0x1b
trap number             = 12
panic: page fault
cpuid = 3
time = 1591124734
KDB: stack backtrace:
db_trace_self_wrapper() at db_trace_self_wrapper+0x2b/frame 0xfffffe02fd0bb470
vpanic() at vpanic+0x182/frame 0xfffffe02fd0bb4c0
panic() at panic+0x43/frame 0xfffffe02fd0bb520
trap_fatal() at trap_fatal+0x387/frame 0xfffffe02fd0bb580
trap_pfault() at trap_pfault+0x99/frame 0xfffffe02fd0bb5e0
trap() at trap+0x2a5/frame 0xfffffe02fd0bb6f0
calltrap() at calltrap+0x8/frame 0xfffffe02fd0bb6f0
--- trap 0xc, rip = 0xffffffff8253e210, rsp = 0xfffffe02fd0bb7c0, rbp = 0xfffffe02fd0bb7d0 ---
tmpfs_dir_RB_REMOVE() at tmpfs_dir_RB_REMOVE+0x220/frame 0xfffffe02fd0bb7d0
tmpfs_dir_detach() at tmpfs_dir_detach+0x7a/frame 0xfffffe02fd0bb800
tmpfs_remove() at tmpfs_remove+0x107/frame 0xfffffe02fd0bb850
VOP_REMOVE_APV() at VOP_REMOVE_APV+0x79/frame 0xfffffe02fd0bb870
kern_funlinkat() at kern_funlinkat+0x298/frame 0xfffffe02fd0bbab0
sys_unlink() at sys_unlink+0x28/frame 0xfffffe02fd0bbad0
amd64_syscall() at amd64_syscall+0x159/frame 0xfffffe02fd0bbbf0
fast_syscall_common() at fast_syscall_common+0x101/frame 0xfffffe02fd0bbbf0
--- syscall (10, FreeBSD ELF64, sys_unlink), rip = 0x800420dba, rsp = 0x7fffffffe558, rbp = 0x7fffffffe680 ---
KDB: enter: panic
[ thread pid 39475 tid 101529 ]
Stopped at      kdb_enter+0x37: movq    $0,0x10c6ed6(%rip)
db>

[dougm]

Correct an error in determining the redness of the successor of an interior node being deleted.

[pho]

===> linuxkpi (all)
cc  -O2 -pipe -fno-common  -fno-strict-aliasing -Werror -D_KERNEL -DKLD_MODULE -DKLD_TIED -nostdinc  -I/usr/src/sys/compat/linuxkpi/common/include -I/usr/src/sys/contrib/ck/include -DHAVE_KERNEL_OPTION_HEADERS -include /usr/src/sys/amd64/compile/PHO/opt_global.h -I. -I/usr/src/sys -I/usr/src/sys/contrib/ck/include -fno-common -g -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer -fdebug-prefix-map=./machine=/usr/src/sys/amd64/include -fdebug-prefix-map=./x86=/usr/src/sys/x86/include -I/usr/src/sys/amd64/compile/PHO     -MD  -MF.depend.linux_compat.o -MTlinux_compat.o -mcmodel=kernel -mno-red-zone -mno-mmx -mno-sse -msoft-float  -fno-asynchronous-unwind-tables -ffreestanding -fwrapv -fstack-protector -gdwarf-2 -Wall -Wredundant-decls -Wnested-externs -Wstrict-prototypes -Wmissing-prototypes -Wpointer-arith -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-address-of-packed-member -Wno-format-zero-length   -mno-aes -mno-avx  -std=iso9899:1999 -c /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c -o linux_compat.o
In file included from /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c:103:
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:2: error: implicit declaration of function 'RB_COLOR' is invalid in C99 [-Werror,-Wimplicit-function-declaration]
        rb_set_color(node, RB_RED);
        ^
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:64:28: note: expanded from macro 'rb_set_color'
#define rb_set_color(r, c)      rb_color((r)) = (c)
                                ^
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:60:21: note: expanded from macro 'rb_color'
#define rb_color(r)     RB_COLOR(r, __entry)
                        ^
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:2: error: use of undeclared identifier '__entry'
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:64:28: note: expanded from macro 'rb_set_color'
#define rb_set_color(r, c)      rb_color((r)) = (c)
                                ^
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:60:33: note: expanded from macro 'rb_color'
#define rb_color(r)     RB_COLOR(r, __entry)
                                    ^
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:21: error: use of undeclared identifier 'RB_RED'
        rb_set_color(node, RB_RED);
                           ^
3 errors generated.
*** Error code 1

sys/sys/tree.h

331 ↗

(On Diff #72592)

Shouldn't this be "__typeof"?

[dougm]

Restore COLOR in a way that linux compatibilty headers demand.

This leaves the root permanently black, which is should be.

[dougm]

Replace "typeof" with "__typeof".

[pho]

Your patch still doesn't compile:

===> linuxkpi (all)
cc  -O2 -pipe -fno-common  -fno-strict-aliasing -Werror -D_KERNEL -DKLD_MODULE -DKLD_TIED -nostdinc  -I/usr/src/sys/compat/linuxkpi/common/include -I/usr/src/sys/contrib/ck/include -DHAVE_KERNEL_OPTION_HEADERS -include /usr/src/sys/amd64/compile/PHO/opt_global.h -I. -I/usr/src/sys -I/usr/src/sys/contrib/ck/include -fno-common -g -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer -fdebug-prefix-map=./machine=/usr/src/sys/amd64/include -fdebug-prefix-map=./x86=/usr/src/sys/x86/include -I/usr/src/sys/amd64/compile/PHO     -MD  -MF.depend.linux_compat.o -MTlinux_compat.o -mcmodel=kernel -mno-red-zone -mno-mmx -mno-sse -msoft-float  -fno-asynchronous-unwind-tables -ffreestanding -fwrapv -fstack-protector -gdwarf-2 -Wall -Wredundant-decls -Wnested-externs -Wstrict-prototypes -Wmissing-prototypes -Wpointer-arith -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-address-of-packed-member -Wno-format-zero-length   -mno-aes -mno-avx  -std=iso9899:1999 -c /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c -o linux_compat.o
In file included from /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c:103:
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:21: error: expected identifier
        rb_set_color(node, RB_RED);
                           ^
/usr/src/sys/sys/tree.h:344:17: note: expanded from macro 'RB_RED'
#define RB_RED          1
                        ^
In file included from /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c:103:
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:21: error: expected identifier
/usr/src/sys/sys/tree.h:344:17: note: expanded from macro 'RB_RED'
#define RB_RED          1
                        ^
In file included from /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c:103:
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:21: error: expected identifier
/usr/src/sys/sys/tree.h:344:17: note: expanded from macro 'RB_RED'
#define RB_RED          1
                        ^
In file included from /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c:103:
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:21: error: expected identifier
/usr/src/sys/sys/tree.h:344:17: note: expanded from macro 'RB_RED'
#define RB_RED          1
                        ^
In file included from /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c:103:
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:21: error: expected identifier
/usr/src/sys/sys/tree.h:344:17: note: expanded from macro 'RB_RED'
#define RB_RED          1
                        ^
In file included from /usr/src/sys/compat/linuxkpi/common/src/linux_compat.c:103:
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:85:2: error: use of undeclared identifier '__entry'
        rb_set_color(node, RB_RED);
        ^
/usr/src/sys/compat/linuxkpi/common/include/linux/rbtree.h:64:47: note: expanded from macro 'rb_set_color'
#define rb_set_color(r, c)      RB_SET_COLOR(r, c, __entry)
                                                   ^

I installed the kernel and ran tests for 17 hours. Looks OK, except for this (probably) unrelated panic:
https://people.freebsd.org/~pho/stress/log/mjguzik027.txt
I have not been able to reproduce this one.

[dougm]

Fix order of arguments in the RB_SET_COLOR invocation in rbtree.h.

[pho]

D25105.72656.diff builds without any issues.
I ran stress2 tests for 12 hours followed by a buildkernel and a buildworld.
No problems seen.

[markj]

sys/compat/linuxkpi/common/include/linux/rbtree.h

87 ↗

(On Diff #72656)

Won't this assignment always clobber the colour bit?

sys/sys/tree.h

341 ↗

(On Diff #72656)

I note that rb_set_color is only used by the LinuxKPI itself, in rb_link_node. In other words, if rb_link_node can be implemented using the standard API or some extension of it, then there is no need for compatibility macros. Linux itself does not have rb_set_color.

358 ↗

(On Diff #72656)

This line is misindented.

[dougm]

Fix color in rb_link_node.
Fix indentation.

Who uses this rb_tree stuff, exactly?

[markj]

In D25105#554166, @dougm wrote:

Fix color in rb_link_node.
Fix indentation.

Who uses this rb_tree stuff, exactly?

Looks like it is mostly the Infiniband code, which was ported from Linux. cm_insert_listen(), from sys/ofed/drivers/infiniband/core/ib_cm.c, for example.

[dougm]

This change makes a newly inserted node black, not red, and lets RB_INSERT_COLOR make it red if it needs to be. So rb_link_node no longer needs to be concerned with redness - the default black color is correct. Nowhere else in sys/ is code that depend on rb_color, rb_is_red or rb_is_black, so delete them and the tree.h macros that had been defined to enable them.

[dougm]

Remove redundant assignments.

[markj]

Thanks. There is some out-of-tree code (graphics drivers, ported from Linux) that also makes use of the linuxkpi. I verified that it compiles with this diff applied. Just for completeness I started a build and will test the drivers on my desktop.

[markj]

sys/sys/tree.h

320 ↗

(On Diff #72766)

This makes libc fail to compile, because include/rpcsvc/yp_prot.h typedefs "bool". :(

Since this header is widely used and embedded in userspace projects, I would suggest trying to minimize external dependencies as much as possible. In this case we can replace uses of "bool" with "int".

[dougm]

Don't depend on anyone else's bool type.

[markj]

I didn't observe any problems running this patch on my desktop, sorry for the delay.

[pho]

I completed a full stress2 test with D25105.72798.diff.