Skip to content

Commit b145425

Browse files
edumazetdavem330
authored andcommitted
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>
1 parent 27eac47 commit b145425

File tree

2 files changed

+92
-347
lines changed

2 files changed

+92
-347
lines changed

include/net/inetpeer.h

Lines changed: 2 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -33,18 +33,12 @@ struct inetpeer_addr {
3333
};
3434

3535
struct inet_peer {
36-
/* group together avl_left,avl_right,v4daddr to speedup lookups */
37-
struct inet_peer __rcu *avl_left, *avl_right;
36+
struct rb_node rb_node;
3837
struct inetpeer_addr daddr;
39-
__u32 avl_height;
4038

4139
u32 metrics[RTAX_MAX];
4240
u32 rate_tokens; /* rate limiting for ICMP */
4341
unsigned long rate_last;
44-
union {
45-
struct list_head gc_list;
46-
struct rcu_head gc_rcu;
47-
};
4842
/*
4943
* Once inet_peer is queued for deletion (refcnt == 0), following field
5044
* is not available: rid
@@ -55,7 +49,6 @@ struct inet_peer {
5549
atomic_t rid; /* Frag reception counter */
5650
};
5751
struct rcu_head rcu;
58-
struct inet_peer *gc_next;
5952
};
6053

6154
/* following fields might be frequently dirtied */
@@ -64,7 +57,7 @@ struct inet_peer {
6457
};
6558

6659
struct inet_peer_base {
67-
struct inet_peer __rcu *root;
60+
struct rb_root rb_root;
6861
seqlock_t lock;
6962
int total;
7063
};

0 commit comments

Comments
 (0)