]> git.puffer.fish Git - matthieu/frr.git/commit
lib: RB-tree copy-paste error (Coverity 1446184)
authorF. Aragon <paco@voltanet.io>
Fri, 28 Sep 2018 18:07:43 +0000 (20:07 +0200)
committerF. Aragon <paco@voltanet.io>
Fri, 28 Sep 2018 18:37:27 +0000 (20:37 +0200)
commit01faf8f42769325b1b6e55128714d5c55616fd83
treefceb9f12b232988d0140578841d93faf53b2ee59
parent979ee884911aeeda2b1dd0942e07d68d4b32e955
lib: RB-tree copy-paste error (Coverity 1446184)

Overview:

Coverity points a copy-paste error in the Red-Black tree implementation. The
RB tree code is based on the OpenBSD implementation, so at first glance, it
is a strong point for thinking twice before touching anything.

Details:

The code is an augmented RB tree implementation [1], which adds to RB trees
the possibility of using a callback on every node update for updating per-node
associated metainformation. The bug is clear once checking other places where
the callback is called.

Impact:

- FRR: no impact, because the "augmented" capability is not being used.
- OpenBSD [2]: it seems there is no impact, at least in the 'src' repository.

Additional observations:

- If the "augmented" capability is not used, the code could run faster (at
  every operation on a node the callback is checked for not being NULL). May
  be branch prediction could be enough for those extra operations being
  negligible on most processors in use.

[1] http://kaba.hilvi.org/pastel-1.3.0/pastel/sys/redblacktree.htm
[2] GH mirror: https://github.com/openbsd/src/blob/master/sys/kern/subr_tree.c

Signed-off-by: F. Aragon <paco@voltanet.io>
lib/openbsd-tree.c