summaryrefslogtreecommitdiff
path: root/include/net/inetpeer.h
diff options
context:
space:
mode:
authorEric Dumazet <edumazet@google.com>2017-07-17 12:56:10 +0300
committerDavid S. Miller <davem@davemloft.net>2017-07-17 18:59:01 +0300
commitb145425f269a17ed344d737f746b844dfac60c82 (patch)
tree685eb81f8bbcc86147208e73f880c9649364027f /include/net/inetpeer.h
parent27eac47b00789522ba00501b0838026e1ecb6f05 (diff)
downloadlinux-b145425f269a17ed344d737f746b844dfac60c82.tar.xz
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>
Diffstat (limited to 'include/net/inetpeer.h')
-rw-r--r--include/net/inetpeer.h11
1 files changed, 2 insertions, 9 deletions
diff --git a/include/net/inetpeer.h b/include/net/inetpeer.h
index f2a215fc78e4..950ed182f62f 100644
--- a/include/net/inetpeer.h
+++ b/include/net/inetpeer.h
@@ -33,18 +33,12 @@ struct inetpeer_addr {
};
struct inet_peer {
- /* group together avl_left,avl_right,v4daddr to speedup lookups */
- struct inet_peer __rcu *avl_left, *avl_right;
+ struct rb_node rb_node;
struct inetpeer_addr daddr;
- __u32 avl_height;
u32 metrics[RTAX_MAX];
u32 rate_tokens; /* rate limiting for ICMP */
unsigned long rate_last;
- union {
- struct list_head gc_list;
- struct rcu_head gc_rcu;
- };
/*
* Once inet_peer is queued for deletion (refcnt == 0), following field
* is not available: rid
@@ -55,7 +49,6 @@ struct inet_peer {
atomic_t rid; /* Frag reception counter */
};
struct rcu_head rcu;
- struct inet_peer *gc_next;
};
/* following fields might be frequently dirtied */
@@ -64,7 +57,7 @@ struct inet_peer {
};
struct inet_peer_base {
- struct inet_peer __rcu *root;
+ struct rb_root rb_root;
seqlock_t lock;
int total;
};