Page MenuHomeFreeBSD

rb_tree: test rank balance
ClosedPublic

Authored by dougm on Sep 7 2022, 6:21 PM.
Tags
None
Referenced Files
Unknown Object (File)
Mon, Nov 18, 9:59 AM
Unknown Object (File)
Sat, Nov 16, 6:28 PM
Unknown Object (File)
Fri, Nov 15, 11:36 AM
Unknown Object (File)
Fri, Nov 15, 11:34 AM
Unknown Object (File)
Fri, Nov 15, 10:54 AM
Unknown Object (File)
Fri, Nov 15, 10:42 AM
Unknown Object (File)
Fri, Nov 15, 10:22 AM
Unknown Object (File)
Fri, Nov 15, 9:06 AM
Subscribers

Details

Summary

With DIAGNOSTIC defined, provide an RB_RANK method to compute the rank of a node in an rb-tree, if the subtree rooted at that node is rank-balanced, and -1 otherwise.

In rb_test, rewrite a bit to avoid malloc/free and nondeterministic running times because of randomness. Allocate all the nodes on the stack, and shuffle a set of keys to get randomness for the testing.

Add a rank-balance check for the completed tree.

Add something to the makefile that seems likely to define DIAGNOSTIC for rb_test.

Test Plan

The kernel compiles.

The code added here has been tested elsewhere and copied into this test framework. I'm not sure how to test in this framework.

Diff Detail

Repository
rG FreeBSD src repository
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

dougm requested review of this revision.Sep 7 2022, 6:21 PM
dougm created this revision.

Prefix name## to RB_RANK calls. Which suggests that DIAGNOSTIC hasn't been defined for building the test.

sys/sys/tree.h
434

tree.h is used outside of the kernel, so this check is sensitive to any definition of DIAGNOSTIC. An improvement would be to test _RB_DIAGNOSTIC instead and have

#if defined(_KERNEL) && defined(DIAGNOSTIC)
#define _RB_DIAGNOSTIC 1
#endif
tests/sys/sys/rb_test.c
99–100

Wouldn't it be more useful to validate RB_MIN/MAX in each iteration of the preceding loop?

Accept suggestions. Fix errors.

Take out the #include of my own personal tree.h copy.

I'm not sure how to test in this framework.

It's rather clunky, but something like the following works:

  • install tree.h to /usr/include: # cp /usr/src/sys/sys/tree.h /usr/include/sys
  • build tests: # make -C /usr/src/tests/sys/sys
    • you can build just rb_test by specifying it as a target, but I don't know how to install just rb_test
  • install tests to /usr/tests/sys/sys: # make -C /usr/src/tests/sys/sys install
  • run RB tree tests: $ cd /usr/tests/sys/sys && kyua test rb_test
markj@nuc> cd /usr/tests/sys/sys && kyua test rb_test
rb_test:rb_test  ->  passed  [0.005s]

Results file id is usr_tests_sys_sys.20220907-214805-984250
Results saved to /home/markj/.kyua/store/results.usr_tests_sys_sys.20220907-214805-984250.db

1/1 passed (0 failed)
This revision is now accepted and ready to land.Sep 7 2022, 9:51 PM
This revision was automatically updated to reflect the committed changes.