diff options
author | Eric Dumazet <eric.dumazet@gmail.com> | 2009-11-09 00:26:33 -0500 |
---|---|---|
committer | David S. Miller <davem@davemloft.net> | 2009-11-10 23:54:38 -0500 |
commit | 30fff9231fad757c061285e347b33c5149c2c2e4 (patch) | |
tree | 79d07aba4b8de4367090442292e412d1ccf961ef /net/ipv4/udp.c | |
parent | 0ab365f463b9c5c8b76476a1808dfde1c38f6f19 (diff) |
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>
Diffstat (limited to 'net/ipv4/udp.c')
-rw-r--r-- | net/ipv4/udp.c | 73 |
1 files changed, 65 insertions, 8 deletions
diff --git a/net/ipv4/udp.c b/net/ipv4/udp.c index d73e9170536b..1eaf57567ebf 100644 --- a/net/ipv4/udp.c +++ b/net/ipv4/udp.c | |||
@@ -152,16 +152,49 @@ static int udp_lib_lport_inuse(struct net *net, __u16 num, | |||
152 | return 0; | 152 | return 0; |
153 | } | 153 | } |
154 | 154 | ||
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 | |||
155 | /** | 185 | /** |
156 | * udp_lib_get_port - UDP/-Lite port lookup for IPv4 and IPv6 | 186 | * udp_lib_get_port - UDP/-Lite port lookup for IPv4 and IPv6 |
157 | * | 187 | * |
158 | * @sk: socket struct in question | 188 | * @sk: socket struct in question |
159 | * @snum: port number to look up | 189 | * @snum: port number to look up |
160 | * @saddr_comp: AF-dependent comparison of bound local IP addresses | 190 | * @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 | ||
161 | */ | 193 | */ |
162 | int udp_lib_get_port(struct sock *sk, unsigned short snum, | 194 | int udp_lib_get_port(struct sock *sk, unsigned short snum, |
163 | int (*saddr_comp)(const struct sock *sk1, | 195 | int (*saddr_comp)(const struct sock *sk1, |
164 | const struct sock *sk2)) | 196 | const struct sock *sk2), |
197 | unsigned int hash2_nulladdr) | ||
165 | { | 198 | { |
166 | struct udp_hslot *hslot, *hslot2; | 199 | struct udp_hslot *hslot, *hslot2; |
167 | struct udp_table *udptable = sk->sk_prot->h.udp_table; | 200 | 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, | |||
210 | } else { | 243 | } else { |
211 | hslot = udp_hashslot(udptable, net, snum); | 244 | hslot = udp_hashslot(udptable, net, snum); |
212 | spin_lock_bh(&hslot->lock); | 245 | 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: | ||
213 | if (udp_lib_lport_inuse(net, snum, hslot, NULL, sk, | 270 | if (udp_lib_lport_inuse(net, snum, hslot, NULL, sk, |
214 | saddr_comp, 0)) | 271 | saddr_comp, 0)) |
215 | goto fail_unlock; | 272 | goto fail_unlock; |
@@ -255,12 +312,14 @@ static unsigned int udp4_portaddr_hash(struct net *net, __be32 saddr, | |||
255 | 312 | ||
256 | int udp_v4_get_port(struct sock *sk, unsigned short snum) | 313 | int udp_v4_get_port(struct sock *sk, unsigned short snum) |
257 | { | 314 | { |
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 | |||
258 | /* precompute partial secondary hash */ | 320 | /* precompute partial secondary hash */ |
259 | udp_sk(sk)->udp_portaddr_hash = | 321 | udp_sk(sk)->udp_portaddr_hash = hash2_partial; |
260 | udp4_portaddr_hash(sock_net(sk), | 322 | return udp_lib_get_port(sk, snum, ipv4_rcv_saddr_equal, hash2_nulladdr); |
261 | inet_sk(sk)->inet_rcv_saddr, | ||
262 | 0); | ||
263 | return udp_lib_get_port(sk, snum, ipv4_rcv_saddr_equal); | ||
264 | } | 323 | } |
265 | 324 | ||
266 | static inline int compute_score(struct sock *sk, struct net *net, __be32 saddr, | 325 | 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, | |||
336 | return score; | 395 | return score; |
337 | } | 396 | } |
338 | 397 | ||
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) | ||
341 | 398 | ||
342 | /* called with read_rcu_lock() */ | 399 | /* called with read_rcu_lock() */ |
343 | static struct sock *udp4_lib_lookup2(struct net *net, | 400 | static struct sock *udp4_lib_lookup2(struct net *net, |