inetpeer: remove AVL implementation in favor of RB tree
authorEric Dumazet <edumazet@google.com>
Mon, 17 Jul 2017 09:56:10 +0000 (02:56 -0700)
committerDavid S. Miller <davem@davemloft.net>
Mon, 17 Jul 2017 15:59:01 +0000 (08:59 -0700)
commitb145425f269a17ed344d737f746b844dfac60c82
tree685eb81f8bbcc86147208e73f880c9649364027f
parent27eac47b00789522ba00501b0838026e1ecb6f05
inetpeer: remove AVL implementation in favor of RB tree

As discussed in Faro during Netfilter Workshop 2017, RB trees can be
used with RCU, using a seqlock.

Note that net/rxrpc/conn_service.c is already using this.

This patch converts inetpeer from AVL tree to RB tree, since it allows
to remove private AVL implementation in favor of shared RB code.

$ size net/ipv4/inetpeer.before net/ipv4/inetpeer.after
   text    data     bss     dec     hex filename
   3195      40     128    3363     d23 net/ipv4/inetpeer.before
   1562      24       0    1586     632 net/ipv4/inetpeer.after

The same technique can be used to speed up
net/netfilter/nft_set_rbtree.c (removing rwlock contention in fast path)

Signed-off-by: Eric Dumazet <edumazet@google.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
include/net/inetpeer.h
net/ipv4/inetpeer.c