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
));
42 INIT_HLIST_HEAD(&tb
->owners
);
43 hlist_add_head(&tb
->node
, &head
->chain
);
49 * Caller must hold hashbucket lock for this tb with local BH disabled
51 void inet_bind_bucket_destroy(struct kmem_cache
*cachep
, struct inet_bind_bucket
*tb
)
53 if (hlist_empty(&tb
->owners
)) {
54 __hlist_del(&tb
->node
);
55 release_net(ib_net(tb
));
56 kmem_cache_free(cachep
, tb
);
60 void inet_bind_hash(struct sock
*sk
, struct inet_bind_bucket
*tb
,
61 const unsigned short snum
)
63 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
65 atomic_inc(&hashinfo
->bsockets
);
67 inet_sk(sk
)->inet_num
= snum
;
68 sk_add_bind_node(sk
, &tb
->owners
);
70 inet_csk(sk
)->icsk_bind_hash
= tb
;
74 * Get rid of any references to a local port held by the given sock.
76 static void __inet_put_port(struct sock
*sk
)
78 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
79 const int bhash
= inet_bhashfn(sock_net(sk
), inet_sk(sk
)->inet_num
,
80 hashinfo
->bhash_size
);
81 struct inet_bind_hashbucket
*head
= &hashinfo
->bhash
[bhash
];
82 struct inet_bind_bucket
*tb
;
84 atomic_dec(&hashinfo
->bsockets
);
86 spin_lock(&head
->lock
);
87 tb
= inet_csk(sk
)->icsk_bind_hash
;
88 __sk_del_bind_node(sk
);
90 inet_csk(sk
)->icsk_bind_hash
= NULL
;
91 inet_sk(sk
)->inet_num
= 0;
92 inet_bind_bucket_destroy(hashinfo
->bind_bucket_cachep
, tb
);
93 spin_unlock(&head
->lock
);
96 void inet_put_port(struct sock
*sk
)
103 EXPORT_SYMBOL(inet_put_port
);
105 void __inet_inherit_port(struct sock
*sk
, struct sock
*child
)
107 struct inet_hashinfo
*table
= sk
->sk_prot
->h
.hashinfo
;
108 const int bhash
= inet_bhashfn(sock_net(sk
), inet_sk(child
)->inet_num
,
110 struct inet_bind_hashbucket
*head
= &table
->bhash
[bhash
];
111 struct inet_bind_bucket
*tb
;
113 spin_lock(&head
->lock
);
114 tb
= inet_csk(sk
)->icsk_bind_hash
;
115 sk_add_bind_node(child
, &tb
->owners
);
116 inet_csk(child
)->icsk_bind_hash
= tb
;
117 spin_unlock(&head
->lock
);
120 EXPORT_SYMBOL_GPL(__inet_inherit_port
);
122 static inline int compute_score(struct sock
*sk
, struct net
*net
,
123 const unsigned short hnum
, const __be32 daddr
,
127 struct inet_sock
*inet
= inet_sk(sk
);
129 if (net_eq(sock_net(sk
), net
) && inet
->inet_num
== hnum
&&
130 !ipv6_only_sock(sk
)) {
131 __be32 rcv_saddr
= inet
->inet_rcv_saddr
;
132 score
= sk
->sk_family
== PF_INET
? 1 : 0;
134 if (rcv_saddr
!= daddr
)
138 if (sk
->sk_bound_dev_if
) {
139 if (sk
->sk_bound_dev_if
!= dif
)
148 * Don't inline this cruft. Here are some nice properties to exploit here. The
149 * BSD API does not allow a listening sock to specify the remote port nor the
150 * remote address for the connection. So always assume those are both
151 * wildcarded during the search since they can never be otherwise.
155 struct sock
*__inet_lookup_listener(struct net
*net
,
156 struct inet_hashinfo
*hashinfo
,
157 const __be32 daddr
, const unsigned short hnum
,
160 struct sock
*sk
, *result
;
161 struct hlist_nulls_node
*node
;
162 unsigned int hash
= inet_lhashfn(net
, hnum
);
163 struct inet_listen_hashbucket
*ilb
= &hashinfo
->listening_hash
[hash
];
170 sk_nulls_for_each_rcu(sk
, node
, &ilb
->head
) {
171 score
= compute_score(sk
, net
, hnum
, daddr
, dif
);
172 if (score
> hiscore
) {
178 * if the nulls value we got at the end of this lookup is
179 * not the expected one, we must restart lookup.
180 * We probably met an item that was moved to another chain.
182 if (get_nulls_value(node
) != hash
+ LISTENING_NULLS_BASE
)
185 if (unlikely(!atomic_inc_not_zero(&result
->sk_refcnt
)))
187 else if (unlikely(compute_score(result
, net
, hnum
, daddr
,
196 EXPORT_SYMBOL_GPL(__inet_lookup_listener
);
198 struct sock
* __inet_lookup_established(struct net
*net
,
199 struct inet_hashinfo
*hashinfo
,
200 const __be32 saddr
, const __be16 sport
,
201 const __be32 daddr
, const u16 hnum
,
204 INET_ADDR_COOKIE(acookie
, saddr
, daddr
)
205 const __portpair ports
= INET_COMBINED_PORTS(sport
, hnum
);
207 const struct hlist_nulls_node
*node
;
208 /* Optimize here for direct hit, only listening connections can
209 * have wildcards anyways.
211 unsigned int hash
= inet_ehashfn(net
, daddr
, hnum
, saddr
, sport
);
212 unsigned int slot
= hash
& hashinfo
->ehash_mask
;
213 struct inet_ehash_bucket
*head
= &hashinfo
->ehash
[slot
];
217 sk_nulls_for_each_rcu(sk
, node
, &head
->chain
) {
218 if (INET_MATCH(sk
, net
, hash
, acookie
,
219 saddr
, daddr
, ports
, dif
)) {
220 if (unlikely(!atomic_inc_not_zero(&sk
->sk_refcnt
)))
222 if (unlikely(!INET_MATCH(sk
, net
, hash
, acookie
,
223 saddr
, daddr
, ports
, dif
))) {
231 * if the nulls value we got at the end of this lookup is
232 * not the expected one, we must restart lookup.
233 * We probably met an item that was moved to another chain.
235 if (get_nulls_value(node
) != slot
)
239 /* Must check for a TIME_WAIT'er before going to listener hash. */
240 sk_nulls_for_each_rcu(sk
, node
, &head
->twchain
) {
241 if (INET_TW_MATCH(sk
, net
, hash
, acookie
,
242 saddr
, daddr
, ports
, dif
)) {
243 if (unlikely(!atomic_inc_not_zero(&sk
->sk_refcnt
))) {
247 if (unlikely(!INET_TW_MATCH(sk
, net
, hash
, acookie
,
248 saddr
, daddr
, ports
, dif
))) {
256 * if the nulls value we got at the end of this lookup is
257 * not the expected one, we must restart lookup.
258 * We probably met an item that was moved to another chain.
260 if (get_nulls_value(node
) != slot
)
267 EXPORT_SYMBOL_GPL(__inet_lookup_established
);
269 /* called with local bh disabled */
270 static int __inet_check_established(struct inet_timewait_death_row
*death_row
,
271 struct sock
*sk
, __u16 lport
,
272 struct inet_timewait_sock
**twp
)
274 struct inet_hashinfo
*hinfo
= death_row
->hashinfo
;
275 struct inet_sock
*inet
= inet_sk(sk
);
276 __be32 daddr
= inet
->inet_rcv_saddr
;
277 __be32 saddr
= inet
->inet_daddr
;
278 int dif
= sk
->sk_bound_dev_if
;
279 INET_ADDR_COOKIE(acookie
, saddr
, daddr
)
280 const __portpair ports
= INET_COMBINED_PORTS(inet
->inet_dport
, lport
);
281 struct net
*net
= sock_net(sk
);
282 unsigned int hash
= inet_ehashfn(net
, daddr
, lport
,
283 saddr
, inet
->inet_dport
);
284 struct inet_ehash_bucket
*head
= inet_ehash_bucket(hinfo
, hash
);
285 spinlock_t
*lock
= inet_ehash_lockp(hinfo
, hash
);
287 const struct hlist_nulls_node
*node
;
288 struct inet_timewait_sock
*tw
;
292 /* Check TIME-WAIT sockets first. */
293 sk_nulls_for_each(sk2
, node
, &head
->twchain
) {
296 if (INET_TW_MATCH(sk2
, net
, hash
, acookie
,
297 saddr
, daddr
, ports
, dif
)) {
298 if (twsk_unique(sk
, sk2
, twp
))
306 /* And established part... */
307 sk_nulls_for_each(sk2
, node
, &head
->chain
) {
308 if (INET_MATCH(sk2
, net
, hash
, acookie
,
309 saddr
, daddr
, ports
, dif
))
314 /* Must record num and sport now. Otherwise we will see
315 * in hash table socket with a funny identity. */
316 inet
->inet_num
= lport
;
317 inet
->inet_sport
= htons(lport
);
319 WARN_ON(!sk_unhashed(sk
));
320 __sk_nulls_add_node_rcu(sk
, &head
->chain
);
322 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
326 NET_INC_STATS_BH(net
, LINUX_MIB_TIMEWAITRECYCLED
);
328 /* Silly. Should hash-dance instead... */
329 inet_twsk_deschedule(tw
, death_row
);
330 NET_INC_STATS_BH(net
, LINUX_MIB_TIMEWAITRECYCLED
);
339 return -EADDRNOTAVAIL
;
342 static inline u32
inet_sk_port_offset(const struct sock
*sk
)
344 const struct inet_sock
*inet
= inet_sk(sk
);
345 return secure_ipv4_port_ephemeral(inet
->inet_rcv_saddr
,
350 void __inet_hash_nolisten(struct sock
*sk
)
352 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
353 struct hlist_nulls_head
*list
;
355 struct inet_ehash_bucket
*head
;
357 WARN_ON(!sk_unhashed(sk
));
359 sk
->sk_hash
= inet_sk_ehashfn(sk
);
360 head
= inet_ehash_bucket(hashinfo
, sk
->sk_hash
);
362 lock
= inet_ehash_lockp(hashinfo
, sk
->sk_hash
);
365 __sk_nulls_add_node_rcu(sk
, list
);
367 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
369 EXPORT_SYMBOL_GPL(__inet_hash_nolisten
);
371 static void __inet_hash(struct sock
*sk
)
373 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
374 struct inet_listen_hashbucket
*ilb
;
376 if (sk
->sk_state
!= TCP_LISTEN
) {
377 __inet_hash_nolisten(sk
);
381 WARN_ON(!sk_unhashed(sk
));
382 ilb
= &hashinfo
->listening_hash
[inet_sk_listen_hashfn(sk
)];
384 spin_lock(&ilb
->lock
);
385 __sk_nulls_add_node_rcu(sk
, &ilb
->head
);
386 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
387 spin_unlock(&ilb
->lock
);
390 void inet_hash(struct sock
*sk
)
392 if (sk
->sk_state
!= TCP_CLOSE
) {
398 EXPORT_SYMBOL_GPL(inet_hash
);
400 void inet_unhash(struct sock
*sk
)
402 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
409 if (sk
->sk_state
== TCP_LISTEN
)
410 lock
= &hashinfo
->listening_hash
[inet_sk_listen_hashfn(sk
)].lock
;
412 lock
= inet_ehash_lockp(hashinfo
, sk
->sk_hash
);
415 done
=__sk_nulls_del_node_init_rcu(sk
);
417 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, -1);
418 spin_unlock_bh(lock
);
420 EXPORT_SYMBOL_GPL(inet_unhash
);
422 int __inet_hash_connect(struct inet_timewait_death_row
*death_row
,
423 struct sock
*sk
, u32 port_offset
,
424 int (*check_established
)(struct inet_timewait_death_row
*,
425 struct sock
*, __u16
, struct inet_timewait_sock
**),
426 void (*hash
)(struct sock
*sk
))
428 struct inet_hashinfo
*hinfo
= death_row
->hashinfo
;
429 const unsigned short snum
= inet_sk(sk
)->inet_num
;
430 struct inet_bind_hashbucket
*head
;
431 struct inet_bind_bucket
*tb
;
433 struct net
*net
= sock_net(sk
);
436 int i
, remaining
, low
, high
, port
;
438 u32 offset
= hint
+ port_offset
;
439 struct hlist_node
*node
;
440 struct inet_timewait_sock
*tw
= NULL
;
442 inet_get_local_port_range(&low
, &high
);
443 remaining
= (high
- low
) + 1;
446 for (i
= 1; i
<= remaining
; i
++) {
447 port
= low
+ (i
+ offset
) % remaining
;
448 head
= &hinfo
->bhash
[inet_bhashfn(net
, port
,
450 spin_lock(&head
->lock
);
452 /* Does not bother with rcv_saddr checks,
453 * because the established check is already
456 inet_bind_bucket_for_each(tb
, node
, &head
->chain
) {
457 if (ib_net(tb
) == net
&& tb
->port
== port
) {
458 if (tb
->fastreuse
>= 0)
460 WARN_ON(hlist_empty(&tb
->owners
));
461 if (!check_established(death_row
, sk
,
468 tb
= inet_bind_bucket_create(hinfo
->bind_bucket_cachep
,
471 spin_unlock(&head
->lock
);
478 spin_unlock(&head
->lock
);
482 return -EADDRNOTAVAIL
;
487 /* Head lock still held and bh's disabled */
488 inet_bind_hash(sk
, tb
, port
);
489 if (sk_unhashed(sk
)) {
490 inet_sk(sk
)->inet_sport
= htons(port
);
493 spin_unlock(&head
->lock
);
496 inet_twsk_deschedule(tw
, death_row
);
504 head
= &hinfo
->bhash
[inet_bhashfn(net
, snum
, hinfo
->bhash_size
)];
505 tb
= inet_csk(sk
)->icsk_bind_hash
;
506 spin_lock_bh(&head
->lock
);
507 if (sk_head(&tb
->owners
) == sk
&& !sk
->sk_bind_node
.next
) {
509 spin_unlock_bh(&head
->lock
);
512 spin_unlock(&head
->lock
);
513 /* No definite answer... Walk to established hash table */
514 ret
= check_established(death_row
, sk
, snum
, NULL
);
522 * Bind a port for a connect operation and hash it.
524 int inet_hash_connect(struct inet_timewait_death_row
*death_row
,
527 return __inet_hash_connect(death_row
, sk
, inet_sk_port_offset(sk
),
528 __inet_check_established
, __inet_hash_nolisten
);
531 EXPORT_SYMBOL_GPL(inet_hash_connect
);
533 void inet_hashinfo_init(struct inet_hashinfo
*h
)
537 atomic_set(&h
->bsockets
, 0);
538 for (i
= 0; i
< INET_LHTABLE_SIZE
; i
++) {
539 spin_lock_init(&h
->listening_hash
[i
].lock
);
540 INIT_HLIST_NULLS_HEAD(&h
->listening_hash
[i
].head
,
541 i
+ LISTENING_NULLS_BASE
);
545 EXPORT_SYMBOL_GPL(inet_hashinfo_init
);