Page MenuHomeFreeBSD

Change from red-black to wavl balancing for RB trees
Needs ReviewPublic

Authored by dougm on Fri, Jun 26, 10:20 PM.

Details

Reviewers
markj
Summary

"Rank-balanced trees" by Haeupler, Sen and Tarjan defines a framework for kinds of balanced tree methods that encompasses red-black and AVL trees, among others. They introduce a new method in this framework called "weak AVL", or "wavl" trees that combine the best aspects of red-black and AVL trees.

This patch takes "RB_" to denote "rank-balanced" and changes the balancing method from "red-black" to "wavl" for the RB macros.

Diff Detail

Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

dougm requested review of this revision.Fri, Jun 26, 10:20 PM
dougm created this revision.

Oh, the irony. :)

Please give me a few days to read up on WAVL trees, I haven't encountered them before. (I know I usually take a few days anyway, sorry about that.)

Oh, the irony. :)

Please give me a few days to read up on WAVL trees, I haven't encountered them before. (I know I usually take a few days anyway, sorry about that.)

Take your time.

In case you ever wonder about the rebalance-after-delete single rotation case, in figure 3, when the rank difference between y and v is 2, and why I did that differently that is depicted, it is because the nodes x and v could both be null, and doing exactly what the picture shows would create a leaf with rank 1, an no-no. So, I'm demoting z to keep that from happening.

pho added a comment.Sat, Jun 27, 5:44 AM

A r362642 kernel with D25480.73723.diff applied does not compile.

dougm updated this revision to Diff 73750.Sat, Jun 27, 6:14 AM

Assuming that the failure to compile is because of the RB_AUGMENT call not within a loop, change to put it within a trivial loop. I've been testing with non-null augmentation so that this problem was not apparent.

pho added a comment.Sat, Jun 27, 6:29 AM

Diff 73750 seems to only contain the man changes?

dougm updated this revision to Diff 73751.Sat, Jun 27, 6:31 AM

Restoring the missing tree.h changes.

pho added a comment.Sat, Jun 27, 12:38 PM

Yes, this compiles nicely.

20200627 14:23:01 all (21/723): nullfs9.sh

Fatal trap 12: page fault while in kernel mode
cpuid = 19; apic id = 27
fault virtual address   = 0x10
fault code              = supervisor read data, page not present
instruction pointer     = 0x20:0xffffffff8234315d
stack pointer           = 0x28:0xfffffe01389757c8
frame pointer           = 0x28:0xfffffe01389757d0
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         = 26930 (rm)
trap number             = 12
panic: page fault
cpuid = 19
time = 1593260584
KDB: stack backtrace:
db_trace_self_wrapper() at db_trace_self_wrapper+0x2b/frame 0xfffffe0138975470
vpanic() at vpanic+0x182/frame 0xfffffe01389754c0
panic() at panic+0x43/frame 0xfffffe0138975520
trap_fatal() at trap_fatal+0x387/frame 0xfffffe0138975580
trap_pfault() at trap_pfault+0x99/frame 0xfffffe01389755e0
trap() at trap+0x2a5/frame 0xfffffe01389756f0
calltrap() at calltrap+0x8/frame 0xfffffe01389756f0
--- trap 0xc, rip = 0xffffffff8234315d, rsp = 0xfffffe01389757c8, rbp = 0xfffffe01389757d0 ---
tmpfs_dir_RB_REMOVE() at tmpfs_dir_RB_REMOVE+0xfd/frame 0xfffffe01389757d0
tmpfs_dir_detach() at tmpfs_dir_detach+0x7a/frame 0xfffffe0138975800
tmpfs_remove() at tmpfs_remove+0x107/frame 0xfffffe0138975850
VOP_REMOVE_APV() at VOP_REMOVE_APV+0x79/frame 0xfffffe0138975870
kern_funlinkat() at kern_funlinkat+0x298/frame 0xfffffe0138975ab0
sys_unlink() at sys_unlink+0x28/frame 0xfffffe0138975ad0
amd64_syscall() at amd64_syscall+0x159/frame 0xfffffe0138975bf0
fast_syscall_common() at fast_syscall_common+0x101/frame 0xfffffe0138975bf0
--- syscall (10, FreeBSD ELF64, sys_unlink), rip = 0x8004219fa, rsp = 0x7fffffffe388, rbp = 0x7fffffffe4a0 ---
KDB: enter: panic
[ thread pid 26930 tid 100290 ]
Stopped at      kdb_enter+0x37: movq    $0,0x10c4dc6(%rip)
db>

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

dougm updated this revision to Diff 73783.Sat, Jun 27, 5:50 PM

Add checking for null parent in RB_REMOVE.

dougm updated this revision to Diff 73795.Sun, Jun 28, 1:10 AM

Simplify RB_REMOVE. Let RB_REMOVE_COLOR do more of the color changing.

dougm updated this revision to Diff 73797.Sun, Jun 28, 6:38 AM

Move the handling of the deleting-a-leaf special coloring case from RB_REMOVE to RB_REMOVE_COLOR, to avoid entangling rebalancing with augmentation.

pho added a comment.Mon, Jun 29, 7:44 AM

I have started a full test of D25480.73797.diff.

dougm updated this revision to Diff 73926.Tue, Jun 30, 8:26 PM

Optimize the color-changing code in RB_INSERT_COLOR and RB_REMOVE_COLOR by allowing both colors to be set to red, or not-red, at once, in some cases.

pho added a comment.Wed, Jul 1, 4:37 PM

I ran tests on D25480.73926.diff for 12 hours without seeing any problems.