Skip to content

Commit 30fff92

Browse files
Eric Dumazetdavem330
Eric Dumazet
authored and
davem330
committed
udp: bind() optimisation
UDP bind() can be O(N^2) in some pathological cases. Thanks to secondary hash tables, we can make it O(N) Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> Signed-off-by: David S. Miller <davem@davemloft.net>
1 parent 0ab365f commit 30fff92

File tree

4 files changed

+80
-16
lines changed

4 files changed

+80
-16
lines changed

‎include/linux/udp.h

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,12 @@ static inline struct udp_sock *udp_sk(const struct sock *sk)
8888
return (struct udp_sock *)sk;
8989
}
9090

91+
#define udp_portaddr_for_each_entry(__sk, node, list) \
92+
hlist_nulls_for_each_entry(__sk, node, list, __sk_common.skc_portaddr_node)
93+
94+
#define udp_portaddr_for_each_entry_rcu(__sk, node, list) \
95+
hlist_nulls_for_each_entry_rcu(__sk, node, list, __sk_common.skc_portaddr_node)
96+
9197
#define IS_UDPLITE(__sk) (udp_sk(__sk)->pcflag)
9298

9399
#endif

‎include/net/udp.h

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -158,7 +158,8 @@ static inline void udp_lib_close(struct sock *sk, long timeout)
158158
}
159159

160160
extern int udp_lib_get_port(struct sock *sk, unsigned short snum,
161-
int (*)(const struct sock*,const struct sock*));
161+
int (*)(const struct sock *,const struct sock *),
162+
unsigned int hash2_nulladdr);
162163

163164
/* net/ipv4/udp.c */
164165
extern int udp_get_port(struct sock *sk, unsigned short snum,

‎net/ipv4/udp.c

Lines changed: 65 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -152,16 +152,49 @@ static int udp_lib_lport_inuse(struct net *net, __u16 num,
152152
return 0;
153153
}
154154

155+
/*
156+
* Note: we still hold spinlock of primary hash chain, so no other writer
157+
* can insert/delete a socket with local_port == num
158+
*/
159+
static int udp_lib_lport_inuse2(struct net *net, __u16 num,
160+
struct udp_hslot *hslot2,
161+
struct sock *sk,
162+
int (*saddr_comp)(const struct sock *sk1,
163+
const struct sock *sk2))
164+
{
165+
struct sock *sk2;
166+
struct hlist_nulls_node *node;
167+
int res = 0;
168+
169+
spin_lock(&hslot2->lock);
170+
udp_portaddr_for_each_entry(sk2, node, &hslot2->head)
171+
if (net_eq(sock_net(sk2), net) &&
172+
sk2 != sk &&
173+
(udp_sk(sk2)->udp_port_hash == num) &&
174+
(!sk2->sk_reuse || !sk->sk_reuse) &&
175+
(!sk2->sk_bound_dev_if || !sk->sk_bound_dev_if
176+
|| sk2->sk_bound_dev_if == sk->sk_bound_dev_if) &&
177+
(*saddr_comp)(sk, sk2)) {
178+
res = 1;
179+
break;
180+
}
181+
spin_unlock(&hslot2->lock);
182+
return res;
183+
}
184+
155185
/**
156186
* udp_lib_get_port - UDP/-Lite port lookup for IPv4 and IPv6
157187
*
158188
* @sk: socket struct in question
159189
* @snum: port number to look up
160190
* @saddr_comp: AF-dependent comparison of bound local IP addresses
191+
* @hash2_nulladdr: AF-dependant hash value in secondary hash chains,
192+
* with NULL address
161193
*/
162194
int udp_lib_get_port(struct sock *sk, unsigned short snum,
163195
int (*saddr_comp)(const struct sock *sk1,
164-
const struct sock *sk2))
196+
const struct sock *sk2),
197+
unsigned int hash2_nulladdr)
165198
{
166199
struct udp_hslot *hslot, *hslot2;
167200
struct udp_table *udptable = sk->sk_prot->h.udp_table;
@@ -210,6 +243,30 @@ int udp_lib_get_port(struct sock *sk, unsigned short snum,
210243
} else {
211244
hslot = udp_hashslot(udptable, net, snum);
212245
spin_lock_bh(&hslot->lock);
246+
if (hslot->count > 10) {
247+
int exist;
248+
unsigned int slot2 = udp_sk(sk)->udp_portaddr_hash ^ snum;
249+
250+
slot2 &= udptable->mask;
251+
hash2_nulladdr &= udptable->mask;
252+
253+
hslot2 = udp_hashslot2(udptable, slot2);
254+
if (hslot->count < hslot2->count)
255+
goto scan_primary_hash;
256+
257+
exist = udp_lib_lport_inuse2(net, snum, hslot2,
258+
sk, saddr_comp);
259+
if (!exist && (hash2_nulladdr != slot2)) {
260+
hslot2 = udp_hashslot2(udptable, hash2_nulladdr);
261+
exist = udp_lib_lport_inuse2(net, snum, hslot2,
262+
sk, saddr_comp);
263+
}
264+
if (exist)
265+
goto fail_unlock;
266+
else
267+
goto found;
268+
}
269+
scan_primary_hash:
213270
if (udp_lib_lport_inuse(net, snum, hslot, NULL, sk,
214271
saddr_comp, 0))
215272
goto fail_unlock;
@@ -255,12 +312,14 @@ static unsigned int udp4_portaddr_hash(struct net *net, __be32 saddr,
255312

256313
int udp_v4_get_port(struct sock *sk, unsigned short snum)
257314
{
315+
unsigned int hash2_nulladdr =
316+
udp4_portaddr_hash(sock_net(sk), INADDR_ANY, snum);
317+
unsigned int hash2_partial =
318+
udp4_portaddr_hash(sock_net(sk), inet_sk(sk)->inet_rcv_saddr, 0);
319+
258320
/* precompute partial secondary hash */
259-
udp_sk(sk)->udp_portaddr_hash =
260-
udp4_portaddr_hash(sock_net(sk),
261-
inet_sk(sk)->inet_rcv_saddr,
262-
0);
263-
return udp_lib_get_port(sk, snum, ipv4_rcv_saddr_equal);
321+
udp_sk(sk)->udp_portaddr_hash = hash2_partial;
322+
return udp_lib_get_port(sk, snum, ipv4_rcv_saddr_equal, hash2_nulladdr);
264323
}
265324

266325
static inline int compute_score(struct sock *sk, struct net *net, __be32 saddr,
@@ -336,8 +395,6 @@ static inline int compute_score2(struct sock *sk, struct net *net,
336395
return score;
337396
}
338397

339-
#define udp_portaddr_for_each_entry_rcu(__sk, node, list) \
340-
hlist_nulls_for_each_entry_rcu(__sk, node, list, __sk_common.skc_portaddr_node)
341398

342399
/* called with read_rcu_lock() */
343400
static struct sock *udp4_lib_lookup2(struct net *net,

‎net/ipv6/udp.c

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -100,12 +100,14 @@ static unsigned int udp6_portaddr_hash(struct net *net,
100100

101101
int udp_v6_get_port(struct sock *sk, unsigned short snum)
102102
{
103+
unsigned int hash2_nulladdr =
104+
udp6_portaddr_hash(sock_net(sk), &in6addr_any, snum);
105+
unsigned int hash2_partial =
106+
udp6_portaddr_hash(sock_net(sk), &inet6_sk(sk)->rcv_saddr, 0);
107+
103108
/* precompute partial secondary hash */
104-
udp_sk(sk)->udp_portaddr_hash =
105-
udp6_portaddr_hash(sock_net(sk),
106-
&inet6_sk(sk)->rcv_saddr,
107-
0);
108-
return udp_lib_get_port(sk, snum, ipv6_rcv_saddr_equal);
109+
udp_sk(sk)->udp_portaddr_hash = hash2_partial;
110+
return udp_lib_get_port(sk, snum, ipv6_rcv_saddr_equal, hash2_nulladdr);
109111
}
110112

111113
static inline int compute_score(struct sock *sk, struct net *net,
@@ -181,8 +183,6 @@ static inline int compute_score2(struct sock *sk, struct net *net,
181183
return score;
182184
}
183185

184-
#define udp_portaddr_for_each_entry_rcu(__sk, node, list) \
185-
hlist_nulls_for_each_entry_rcu(__sk, node, list, __sk_common.skc_portaddr_node)
186186

187187
/* called with read_rcu_lock() */
188188
static struct sock *udp6_lib_lookup2(struct net *net,

0 commit comments

Comments
 (0)