2 * INET An implementation of the TCP/IP protocol suite for the LINUX
3 * operating system. INET is implemented using the BSD Socket
4 * interface as the means of communication with the user level.
6 * Generic INET transport hashtables
8 * Authors: Lotsa people, from code originally in tcp
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version
13 * 2 of the License, or (at your option) any later version.
16 #include <linux/module.h>
17 #include <linux/random.h>
18 #include <linux/sched.h>
19 #include <linux/slab.h>
20 #include <linux/wait.h>
22 #include <net/inet_connection_sock.h>
23 #include <net/inet_hashtables.h>
27 * Allocate and initialize a new local port bind bucket.
28 * The bindhash mutex for snum's hash chain must be held here.
30 struct inet_bind_bucket
*inet_bind_bucket_create(struct kmem_cache
*cachep
,
32 struct inet_bind_hashbucket
*head
,
33 const unsigned short snum
)
35 struct inet_bind_bucket
*tb
= kmem_cache_alloc(cachep
, GFP_ATOMIC
);
38 write_pnet(&tb
->ib_net
, hold_net(net
));
41 INIT_HLIST_HEAD(&tb
->owners
);
42 hlist_add_head(&tb
->node
, &head
->chain
);
48 * Caller must hold hashbucket lock for this tb with local BH disabled
50 void inet_bind_bucket_destroy(struct kmem_cache
*cachep
, struct inet_bind_bucket
*tb
)
52 if (hlist_empty(&tb
->owners
)) {
53 __hlist_del(&tb
->node
);
54 release_net(ib_net(tb
));
55 kmem_cache_free(cachep
, tb
);
59 void inet_bind_hash(struct sock
*sk
, struct inet_bind_bucket
*tb
,
60 const unsigned short snum
)
62 inet_sk(sk
)->num
= snum
;
63 sk_add_bind_node(sk
, &tb
->owners
);
64 inet_csk(sk
)->icsk_bind_hash
= tb
;
68 * Get rid of any references to a local port held by the given sock.
70 static void __inet_put_port(struct sock
*sk
)
72 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
73 const int bhash
= inet_bhashfn(sock_net(sk
), inet_sk(sk
)->num
,
74 hashinfo
->bhash_size
);
75 struct inet_bind_hashbucket
*head
= &hashinfo
->bhash
[bhash
];
76 struct inet_bind_bucket
*tb
;
78 spin_lock(&head
->lock
);
79 tb
= inet_csk(sk
)->icsk_bind_hash
;
80 __sk_del_bind_node(sk
);
81 inet_csk(sk
)->icsk_bind_hash
= NULL
;
83 inet_bind_bucket_destroy(hashinfo
->bind_bucket_cachep
, tb
);
84 spin_unlock(&head
->lock
);
87 void inet_put_port(struct sock
*sk
)
94 EXPORT_SYMBOL(inet_put_port
);
96 void __inet_inherit_port(struct sock
*sk
, struct sock
*child
)
98 struct inet_hashinfo
*table
= sk
->sk_prot
->h
.hashinfo
;
99 const int bhash
= inet_bhashfn(sock_net(sk
), inet_sk(child
)->num
,
101 struct inet_bind_hashbucket
*head
= &table
->bhash
[bhash
];
102 struct inet_bind_bucket
*tb
;
104 spin_lock(&head
->lock
);
105 tb
= inet_csk(sk
)->icsk_bind_hash
;
106 sk_add_bind_node(child
, &tb
->owners
);
107 inet_csk(child
)->icsk_bind_hash
= tb
;
108 spin_unlock(&head
->lock
);
111 EXPORT_SYMBOL_GPL(__inet_inherit_port
);
114 * This lock without WQ_FLAG_EXCLUSIVE is good on UP and it can be very bad on SMP.
115 * Look, when several writers sleep and reader wakes them up, all but one
116 * immediately hit write lock and grab all the cpus. Exclusive sleep solves
117 * this, _but_ remember, it adds useless work on UP machines (wake up each
118 * exclusive lock release). It should be ifdefed really.
120 void inet_listen_wlock(struct inet_hashinfo
*hashinfo
)
121 __acquires(hashinfo
->lhash_lock
)
123 write_lock(&hashinfo
->lhash_lock
);
125 if (atomic_read(&hashinfo
->lhash_users
)) {
129 prepare_to_wait_exclusive(&hashinfo
->lhash_wait
,
130 &wait
, TASK_UNINTERRUPTIBLE
);
131 if (!atomic_read(&hashinfo
->lhash_users
))
133 write_unlock_bh(&hashinfo
->lhash_lock
);
135 write_lock_bh(&hashinfo
->lhash_lock
);
138 finish_wait(&hashinfo
->lhash_wait
, &wait
);
143 * Don't inline this cruft. Here are some nice properties to exploit here. The
144 * BSD API does not allow a listening sock to specify the remote port nor the
145 * remote address for the connection. So always assume those are both
146 * wildcarded during the search since they can never be otherwise.
148 static struct sock
*inet_lookup_listener_slow(struct net
*net
,
149 const struct hlist_head
*head
,
151 const unsigned short hnum
,
154 struct sock
*result
= NULL
, *sk
;
155 const struct hlist_node
*node
;
158 sk_for_each(sk
, node
, head
) {
159 const struct inet_sock
*inet
= inet_sk(sk
);
161 if (net_eq(sock_net(sk
), net
) && inet
->num
== hnum
&&
162 !ipv6_only_sock(sk
)) {
163 const __be32 rcv_saddr
= inet
->rcv_saddr
;
164 int score
= sk
->sk_family
== PF_INET
? 1 : 0;
167 if (rcv_saddr
!= daddr
)
171 if (sk
->sk_bound_dev_if
) {
172 if (sk
->sk_bound_dev_if
!= dif
)
178 if (score
> hiscore
) {
187 /* Optimize the common listener case. */
188 struct sock
*__inet_lookup_listener(struct net
*net
,
189 struct inet_hashinfo
*hashinfo
,
190 const __be32 daddr
, const unsigned short hnum
,
193 struct sock
*sk
= NULL
;
194 const struct hlist_head
*head
;
196 read_lock(&hashinfo
->lhash_lock
);
197 head
= &hashinfo
->listening_hash
[inet_lhashfn(net
, hnum
)];
198 if (!hlist_empty(head
)) {
199 const struct inet_sock
*inet
= inet_sk((sk
= __sk_head(head
)));
201 if (inet
->num
== hnum
&& !sk
->sk_node
.next
&&
202 (!inet
->rcv_saddr
|| inet
->rcv_saddr
== daddr
) &&
203 (sk
->sk_family
== PF_INET
|| !ipv6_only_sock(sk
)) &&
204 !sk
->sk_bound_dev_if
&& net_eq(sock_net(sk
), net
))
206 sk
= inet_lookup_listener_slow(net
, head
, daddr
, hnum
, dif
);
212 read_unlock(&hashinfo
->lhash_lock
);
215 EXPORT_SYMBOL_GPL(__inet_lookup_listener
);
217 struct sock
* __inet_lookup_established(struct net
*net
,
218 struct inet_hashinfo
*hashinfo
,
219 const __be32 saddr
, const __be16 sport
,
220 const __be32 daddr
, const u16 hnum
,
223 INET_ADDR_COOKIE(acookie
, saddr
, daddr
)
224 const __portpair ports
= INET_COMBINED_PORTS(sport
, hnum
);
226 const struct hlist_nulls_node
*node
;
227 /* Optimize here for direct hit, only listening connections can
228 * have wildcards anyways.
230 unsigned int hash
= inet_ehashfn(net
, daddr
, hnum
, saddr
, sport
);
231 unsigned int slot
= hash
& (hashinfo
->ehash_size
- 1);
232 struct inet_ehash_bucket
*head
= &hashinfo
->ehash
[slot
];
236 sk_nulls_for_each_rcu(sk
, node
, &head
->chain
) {
237 if (INET_MATCH(sk
, net
, hash
, acookie
,
238 saddr
, daddr
, ports
, dif
)) {
239 if (unlikely(!atomic_inc_not_zero(&sk
->sk_refcnt
)))
241 if (unlikely(!INET_MATCH(sk
, net
, hash
, acookie
,
242 saddr
, daddr
, ports
, dif
))) {
250 * if the nulls value we got at the end of this lookup is
251 * not the expected one, we must restart lookup.
252 * We probably met an item that was moved to another chain.
254 if (get_nulls_value(node
) != slot
)
258 /* Must check for a TIME_WAIT'er before going to listener hash. */
259 sk_nulls_for_each_rcu(sk
, node
, &head
->twchain
) {
260 if (INET_TW_MATCH(sk
, net
, hash
, acookie
,
261 saddr
, daddr
, ports
, dif
)) {
262 if (unlikely(!atomic_inc_not_zero(&sk
->sk_refcnt
))) {
266 if (unlikely(!INET_TW_MATCH(sk
, net
, hash
, acookie
,
267 saddr
, daddr
, ports
, dif
))) {
275 * if the nulls value we got at the end of this lookup is
276 * not the expected one, we must restart lookup.
277 * We probably met an item that was moved to another chain.
279 if (get_nulls_value(node
) != slot
)
286 EXPORT_SYMBOL_GPL(__inet_lookup_established
);
288 /* called with local bh disabled */
289 static int __inet_check_established(struct inet_timewait_death_row
*death_row
,
290 struct sock
*sk
, __u16 lport
,
291 struct inet_timewait_sock
**twp
)
293 struct inet_hashinfo
*hinfo
= death_row
->hashinfo
;
294 struct inet_sock
*inet
= inet_sk(sk
);
295 __be32 daddr
= inet
->rcv_saddr
;
296 __be32 saddr
= inet
->daddr
;
297 int dif
= sk
->sk_bound_dev_if
;
298 INET_ADDR_COOKIE(acookie
, saddr
, daddr
)
299 const __portpair ports
= INET_COMBINED_PORTS(inet
->dport
, lport
);
300 struct net
*net
= sock_net(sk
);
301 unsigned int hash
= inet_ehashfn(net
, daddr
, lport
, saddr
, inet
->dport
);
302 struct inet_ehash_bucket
*head
= inet_ehash_bucket(hinfo
, hash
);
303 rwlock_t
*lock
= inet_ehash_lockp(hinfo
, hash
);
305 const struct hlist_nulls_node
*node
;
306 struct inet_timewait_sock
*tw
;
308 prefetch(head
->chain
.first
);
311 /* Check TIME-WAIT sockets first. */
312 sk_nulls_for_each(sk2
, node
, &head
->twchain
) {
315 if (INET_TW_MATCH(sk2
, net
, hash
, acookie
,
316 saddr
, daddr
, ports
, dif
)) {
317 if (twsk_unique(sk
, sk2
, twp
))
325 /* And established part... */
326 sk_nulls_for_each(sk2
, node
, &head
->chain
) {
327 if (INET_MATCH(sk2
, net
, hash
, acookie
,
328 saddr
, daddr
, ports
, dif
))
333 /* Must record num and sport now. Otherwise we will see
334 * in hash table socket with a funny identity. */
336 inet
->sport
= htons(lport
);
338 WARN_ON(!sk_unhashed(sk
));
339 __sk_nulls_add_node_rcu(sk
, &head
->chain
);
340 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
345 NET_INC_STATS_BH(net
, LINUX_MIB_TIMEWAITRECYCLED
);
347 /* Silly. Should hash-dance instead... */
348 inet_twsk_deschedule(tw
, death_row
);
349 NET_INC_STATS_BH(net
, LINUX_MIB_TIMEWAITRECYCLED
);
358 return -EADDRNOTAVAIL
;
361 static inline u32
inet_sk_port_offset(const struct sock
*sk
)
363 const struct inet_sock
*inet
= inet_sk(sk
);
364 return secure_ipv4_port_ephemeral(inet
->rcv_saddr
, inet
->daddr
,
368 void __inet_hash_nolisten(struct sock
*sk
)
370 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
371 struct hlist_nulls_head
*list
;
373 struct inet_ehash_bucket
*head
;
375 WARN_ON(!sk_unhashed(sk
));
377 sk
->sk_hash
= inet_sk_ehashfn(sk
);
378 head
= inet_ehash_bucket(hashinfo
, sk
->sk_hash
);
380 lock
= inet_ehash_lockp(hashinfo
, sk
->sk_hash
);
383 __sk_nulls_add_node_rcu(sk
, list
);
384 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
387 EXPORT_SYMBOL_GPL(__inet_hash_nolisten
);
389 static void __inet_hash(struct sock
*sk
)
391 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
392 struct hlist_head
*list
;
395 if (sk
->sk_state
!= TCP_LISTEN
) {
396 __inet_hash_nolisten(sk
);
400 WARN_ON(!sk_unhashed(sk
));
401 list
= &hashinfo
->listening_hash
[inet_sk_listen_hashfn(sk
)];
402 lock
= &hashinfo
->lhash_lock
;
404 inet_listen_wlock(hashinfo
);
405 __sk_add_node(sk
, list
);
406 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
408 wake_up(&hashinfo
->lhash_wait
);
411 void inet_hash(struct sock
*sk
)
413 if (sk
->sk_state
!= TCP_CLOSE
) {
419 EXPORT_SYMBOL_GPL(inet_hash
);
421 void inet_unhash(struct sock
*sk
)
424 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
429 if (sk
->sk_state
== TCP_LISTEN
) {
431 inet_listen_wlock(hashinfo
);
432 lock
= &hashinfo
->lhash_lock
;
433 if (__sk_del_node_init(sk
))
434 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, -1);
436 lock
= inet_ehash_lockp(hashinfo
, sk
->sk_hash
);
438 if (__sk_nulls_del_node_init_rcu(sk
))
439 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, -1);
442 write_unlock_bh(lock
);
444 if (sk
->sk_state
== TCP_LISTEN
)
445 wake_up(&hashinfo
->lhash_wait
);
447 EXPORT_SYMBOL_GPL(inet_unhash
);
449 int __inet_hash_connect(struct inet_timewait_death_row
*death_row
,
450 struct sock
*sk
, u32 port_offset
,
451 int (*check_established
)(struct inet_timewait_death_row
*,
452 struct sock
*, __u16
, struct inet_timewait_sock
**),
453 void (*hash
)(struct sock
*sk
))
455 struct inet_hashinfo
*hinfo
= death_row
->hashinfo
;
456 const unsigned short snum
= inet_sk(sk
)->num
;
457 struct inet_bind_hashbucket
*head
;
458 struct inet_bind_bucket
*tb
;
460 struct net
*net
= sock_net(sk
);
463 int i
, remaining
, low
, high
, port
;
465 u32 offset
= hint
+ port_offset
;
466 struct hlist_node
*node
;
467 struct inet_timewait_sock
*tw
= NULL
;
469 inet_get_local_port_range(&low
, &high
);
470 remaining
= (high
- low
) + 1;
473 for (i
= 1; i
<= remaining
; i
++) {
474 port
= low
+ (i
+ offset
) % remaining
;
475 head
= &hinfo
->bhash
[inet_bhashfn(net
, port
,
477 spin_lock(&head
->lock
);
479 /* Does not bother with rcv_saddr checks,
480 * because the established check is already
483 inet_bind_bucket_for_each(tb
, node
, &head
->chain
) {
484 if (ib_net(tb
) == net
&& tb
->port
== port
) {
485 WARN_ON(hlist_empty(&tb
->owners
));
486 if (tb
->fastreuse
>= 0)
488 if (!check_established(death_row
, sk
,
495 tb
= inet_bind_bucket_create(hinfo
->bind_bucket_cachep
,
498 spin_unlock(&head
->lock
);
505 spin_unlock(&head
->lock
);
509 return -EADDRNOTAVAIL
;
514 /* Head lock still held and bh's disabled */
515 inet_bind_hash(sk
, tb
, port
);
516 if (sk_unhashed(sk
)) {
517 inet_sk(sk
)->sport
= htons(port
);
520 spin_unlock(&head
->lock
);
523 inet_twsk_deschedule(tw
, death_row
);
531 head
= &hinfo
->bhash
[inet_bhashfn(net
, snum
, hinfo
->bhash_size
)];
532 tb
= inet_csk(sk
)->icsk_bind_hash
;
533 spin_lock_bh(&head
->lock
);
534 if (sk_head(&tb
->owners
) == sk
&& !sk
->sk_bind_node
.next
) {
536 spin_unlock_bh(&head
->lock
);
539 spin_unlock(&head
->lock
);
540 /* No definite answer... Walk to established hash table */
541 ret
= check_established(death_row
, sk
, snum
, NULL
);
549 * Bind a port for a connect operation and hash it.
551 int inet_hash_connect(struct inet_timewait_death_row
*death_row
,
554 return __inet_hash_connect(death_row
, sk
, inet_sk_port_offset(sk
),
555 __inet_check_established
, __inet_hash_nolisten
);
558 EXPORT_SYMBOL_GPL(inet_hash_connect
);