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>
24 #include <net/secure_seq.h>
27 static unsigned int inet_ehashfn(struct net
*net
, const __be32 laddr
,
28 const __u16 lport
, const __be32 faddr
,
31 static u32 inet_ehash_secret __read_mostly
;
33 net_get_random_once(&inet_ehash_secret
, sizeof(inet_ehash_secret
));
35 return __inet_ehashfn(laddr
, lport
, faddr
, fport
,
36 inet_ehash_secret
+ net_hash_mix(net
));
40 static unsigned int inet_sk_ehashfn(const struct sock
*sk
)
42 const struct inet_sock
*inet
= inet_sk(sk
);
43 const __be32 laddr
= inet
->inet_rcv_saddr
;
44 const __u16 lport
= inet
->inet_num
;
45 const __be32 faddr
= inet
->inet_daddr
;
46 const __be16 fport
= inet
->inet_dport
;
47 struct net
*net
= sock_net(sk
);
49 return inet_ehashfn(net
, laddr
, lport
, faddr
, fport
);
53 * Allocate and initialize a new local port bind bucket.
54 * The bindhash mutex for snum's hash chain must be held here.
56 struct inet_bind_bucket
*inet_bind_bucket_create(struct kmem_cache
*cachep
,
58 struct inet_bind_hashbucket
*head
,
59 const unsigned short snum
)
61 struct inet_bind_bucket
*tb
= kmem_cache_alloc(cachep
, GFP_ATOMIC
);
64 write_pnet(&tb
->ib_net
, net
);
67 tb
->fastreuseport
= 0;
69 INIT_HLIST_HEAD(&tb
->owners
);
70 hlist_add_head(&tb
->node
, &head
->chain
);
76 * Caller must hold hashbucket lock for this tb with local BH disabled
78 void inet_bind_bucket_destroy(struct kmem_cache
*cachep
, struct inet_bind_bucket
*tb
)
80 if (hlist_empty(&tb
->owners
)) {
81 __hlist_del(&tb
->node
);
82 kmem_cache_free(cachep
, tb
);
86 void inet_bind_hash(struct sock
*sk
, struct inet_bind_bucket
*tb
,
87 const unsigned short snum
)
89 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
91 atomic_inc(&hashinfo
->bsockets
);
93 inet_sk(sk
)->inet_num
= snum
;
94 sk_add_bind_node(sk
, &tb
->owners
);
96 inet_csk(sk
)->icsk_bind_hash
= tb
;
100 * Get rid of any references to a local port held by the given sock.
102 static void __inet_put_port(struct sock
*sk
)
104 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
105 const int bhash
= inet_bhashfn(sock_net(sk
), inet_sk(sk
)->inet_num
,
106 hashinfo
->bhash_size
);
107 struct inet_bind_hashbucket
*head
= &hashinfo
->bhash
[bhash
];
108 struct inet_bind_bucket
*tb
;
110 atomic_dec(&hashinfo
->bsockets
);
112 spin_lock(&head
->lock
);
113 tb
= inet_csk(sk
)->icsk_bind_hash
;
114 __sk_del_bind_node(sk
);
116 inet_csk(sk
)->icsk_bind_hash
= NULL
;
117 inet_sk(sk
)->inet_num
= 0;
118 inet_bind_bucket_destroy(hashinfo
->bind_bucket_cachep
, tb
);
119 spin_unlock(&head
->lock
);
122 void inet_put_port(struct sock
*sk
)
128 EXPORT_SYMBOL(inet_put_port
);
130 int __inet_inherit_port(struct sock
*sk
, struct sock
*child
)
132 struct inet_hashinfo
*table
= sk
->sk_prot
->h
.hashinfo
;
133 unsigned short port
= inet_sk(child
)->inet_num
;
134 const int bhash
= inet_bhashfn(sock_net(sk
), port
,
136 struct inet_bind_hashbucket
*head
= &table
->bhash
[bhash
];
137 struct inet_bind_bucket
*tb
;
139 spin_lock(&head
->lock
);
140 tb
= inet_csk(sk
)->icsk_bind_hash
;
141 if (tb
->port
!= port
) {
142 /* NOTE: using tproxy and redirecting skbs to a proxy
143 * on a different listener port breaks the assumption
144 * that the listener socket's icsk_bind_hash is the same
145 * as that of the child socket. We have to look up or
146 * create a new bind bucket for the child here. */
147 inet_bind_bucket_for_each(tb
, &head
->chain
) {
148 if (net_eq(ib_net(tb
), sock_net(sk
)) &&
153 tb
= inet_bind_bucket_create(table
->bind_bucket_cachep
,
154 sock_net(sk
), head
, port
);
156 spin_unlock(&head
->lock
);
161 inet_bind_hash(child
, tb
, port
);
162 spin_unlock(&head
->lock
);
166 EXPORT_SYMBOL_GPL(__inet_inherit_port
);
168 static inline int compute_score(struct sock
*sk
, struct net
*net
,
169 const unsigned short hnum
, const __be32 daddr
,
173 struct inet_sock
*inet
= inet_sk(sk
);
175 if (net_eq(sock_net(sk
), net
) && inet
->inet_num
== hnum
&&
176 !ipv6_only_sock(sk
)) {
177 __be32 rcv_saddr
= inet
->inet_rcv_saddr
;
178 score
= sk
->sk_family
== PF_INET
? 2 : 1;
180 if (rcv_saddr
!= daddr
)
184 if (sk
->sk_bound_dev_if
) {
185 if (sk
->sk_bound_dev_if
!= dif
)
194 * Don't inline this cruft. Here are some nice properties to exploit here. The
195 * BSD API does not allow a listening sock to specify the remote port nor the
196 * remote address for the connection. So always assume those are both
197 * wildcarded during the search since they can never be otherwise.
201 struct sock
*__inet_lookup_listener(struct net
*net
,
202 struct inet_hashinfo
*hashinfo
,
203 const __be32 saddr
, __be16 sport
,
204 const __be32 daddr
, const unsigned short hnum
,
207 struct sock
*sk
, *result
;
208 struct hlist_nulls_node
*node
;
209 unsigned int hash
= inet_lhashfn(net
, hnum
);
210 struct inet_listen_hashbucket
*ilb
= &hashinfo
->listening_hash
[hash
];
211 int score
, hiscore
, matches
= 0, reuseport
= 0;
218 sk_nulls_for_each_rcu(sk
, node
, &ilb
->head
) {
219 score
= compute_score(sk
, net
, hnum
, daddr
, dif
);
220 if (score
> hiscore
) {
223 reuseport
= sk
->sk_reuseport
;
225 phash
= inet_ehashfn(net
, daddr
, hnum
,
229 } else if (score
== hiscore
&& reuseport
) {
231 if (reciprocal_scale(phash
, matches
) == 0)
233 phash
= next_pseudo_random32(phash
);
237 * if the nulls value we got at the end of this lookup is
238 * not the expected one, we must restart lookup.
239 * We probably met an item that was moved to another chain.
241 if (get_nulls_value(node
) != hash
+ LISTENING_NULLS_BASE
)
244 if (unlikely(!atomic_inc_not_zero(&result
->sk_refcnt
)))
246 else if (unlikely(compute_score(result
, net
, hnum
, daddr
,
255 EXPORT_SYMBOL_GPL(__inet_lookup_listener
);
257 /* All sockets share common refcount, but have different destructors */
258 void sock_gen_put(struct sock
*sk
)
260 if (!atomic_dec_and_test(&sk
->sk_refcnt
))
263 if (sk
->sk_state
== TCP_TIME_WAIT
)
264 inet_twsk_free(inet_twsk(sk
));
265 else if (sk
->sk_state
== TCP_NEW_SYN_RECV
)
266 reqsk_free(inet_reqsk(sk
));
270 EXPORT_SYMBOL_GPL(sock_gen_put
);
272 void sock_edemux(struct sk_buff
*skb
)
274 sock_gen_put(skb
->sk
);
276 EXPORT_SYMBOL(sock_edemux
);
278 struct sock
*__inet_lookup_established(struct net
*net
,
279 struct inet_hashinfo
*hashinfo
,
280 const __be32 saddr
, const __be16 sport
,
281 const __be32 daddr
, const u16 hnum
,
284 INET_ADDR_COOKIE(acookie
, saddr
, daddr
);
285 const __portpair ports
= INET_COMBINED_PORTS(sport
, hnum
);
287 const struct hlist_nulls_node
*node
;
288 /* Optimize here for direct hit, only listening connections can
289 * have wildcards anyways.
291 unsigned int hash
= inet_ehashfn(net
, daddr
, hnum
, saddr
, sport
);
292 unsigned int slot
= hash
& hashinfo
->ehash_mask
;
293 struct inet_ehash_bucket
*head
= &hashinfo
->ehash
[slot
];
297 sk_nulls_for_each_rcu(sk
, node
, &head
->chain
) {
298 if (sk
->sk_hash
!= hash
)
300 if (likely(INET_MATCH(sk
, net
, acookie
,
301 saddr
, daddr
, ports
, dif
))) {
302 if (unlikely(!atomic_inc_not_zero(&sk
->sk_refcnt
)))
304 if (unlikely(!INET_MATCH(sk
, net
, acookie
,
305 saddr
, daddr
, ports
, dif
))) {
313 * if the nulls value we got at the end of this lookup is
314 * not the expected one, we must restart lookup.
315 * We probably met an item that was moved to another chain.
317 if (get_nulls_value(node
) != slot
)
325 EXPORT_SYMBOL_GPL(__inet_lookup_established
);
327 /* called with local bh disabled */
328 static int __inet_check_established(struct inet_timewait_death_row
*death_row
,
329 struct sock
*sk
, __u16 lport
,
330 struct inet_timewait_sock
**twp
)
332 struct inet_hashinfo
*hinfo
= death_row
->hashinfo
;
333 struct inet_sock
*inet
= inet_sk(sk
);
334 __be32 daddr
= inet
->inet_rcv_saddr
;
335 __be32 saddr
= inet
->inet_daddr
;
336 int dif
= sk
->sk_bound_dev_if
;
337 INET_ADDR_COOKIE(acookie
, saddr
, daddr
);
338 const __portpair ports
= INET_COMBINED_PORTS(inet
->inet_dport
, lport
);
339 struct net
*net
= sock_net(sk
);
340 unsigned int hash
= inet_ehashfn(net
, daddr
, lport
,
341 saddr
, inet
->inet_dport
);
342 struct inet_ehash_bucket
*head
= inet_ehash_bucket(hinfo
, hash
);
343 spinlock_t
*lock
= inet_ehash_lockp(hinfo
, hash
);
345 const struct hlist_nulls_node
*node
;
346 struct inet_timewait_sock
*tw
= NULL
;
351 sk_nulls_for_each(sk2
, node
, &head
->chain
) {
352 if (sk2
->sk_hash
!= hash
)
355 if (likely(INET_MATCH(sk2
, net
, acookie
,
356 saddr
, daddr
, ports
, dif
))) {
357 if (sk2
->sk_state
== TCP_TIME_WAIT
) {
359 if (twsk_unique(sk
, sk2
, twp
))
366 /* Must record num and sport now. Otherwise we will see
367 * in hash table socket with a funny identity.
369 inet
->inet_num
= lport
;
370 inet
->inet_sport
= htons(lport
);
372 WARN_ON(!sk_unhashed(sk
));
373 __sk_nulls_add_node_rcu(sk
, &head
->chain
);
375 twrefcnt
= inet_twsk_unhash(tw
);
376 NET_INC_STATS_BH(net
, LINUX_MIB_TIMEWAITRECYCLED
);
381 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
386 /* Silly. Should hash-dance instead... */
387 inet_twsk_deschedule(tw
, death_row
);
395 return -EADDRNOTAVAIL
;
398 static inline u32
inet_sk_port_offset(const struct sock
*sk
)
400 const struct inet_sock
*inet
= inet_sk(sk
);
401 return secure_ipv4_port_ephemeral(inet
->inet_rcv_saddr
,
406 int __inet_hash_nolisten(struct sock
*sk
, struct inet_timewait_sock
*tw
)
408 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
409 struct hlist_nulls_head
*list
;
411 struct inet_ehash_bucket
*head
;
414 WARN_ON(!sk_unhashed(sk
));
416 sk
->sk_hash
= inet_sk_ehashfn(sk
);
417 head
= inet_ehash_bucket(hashinfo
, sk
->sk_hash
);
419 lock
= inet_ehash_lockp(hashinfo
, sk
->sk_hash
);
422 __sk_nulls_add_node_rcu(sk
, list
);
424 WARN_ON(sk
->sk_hash
!= tw
->tw_hash
);
425 twrefcnt
= inet_twsk_unhash(tw
);
428 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
431 EXPORT_SYMBOL_GPL(__inet_hash_nolisten
);
433 static void __inet_hash(struct sock
*sk
)
435 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
436 struct inet_listen_hashbucket
*ilb
;
438 if (sk
->sk_state
!= TCP_LISTEN
) {
439 __inet_hash_nolisten(sk
, NULL
);
443 WARN_ON(!sk_unhashed(sk
));
444 ilb
= &hashinfo
->listening_hash
[inet_sk_listen_hashfn(sk
)];
446 spin_lock(&ilb
->lock
);
447 __sk_nulls_add_node_rcu(sk
, &ilb
->head
);
448 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
449 spin_unlock(&ilb
->lock
);
452 void inet_hash(struct sock
*sk
)
454 if (sk
->sk_state
!= TCP_CLOSE
) {
460 EXPORT_SYMBOL_GPL(inet_hash
);
462 void inet_unhash(struct sock
*sk
)
464 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
471 if (sk
->sk_state
== TCP_LISTEN
)
472 lock
= &hashinfo
->listening_hash
[inet_sk_listen_hashfn(sk
)].lock
;
474 lock
= inet_ehash_lockp(hashinfo
, sk
->sk_hash
);
477 done
= __sk_nulls_del_node_init_rcu(sk
);
479 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, -1);
480 spin_unlock_bh(lock
);
482 EXPORT_SYMBOL_GPL(inet_unhash
);
484 int __inet_hash_connect(struct inet_timewait_death_row
*death_row
,
485 struct sock
*sk
, u32 port_offset
,
486 int (*check_established
)(struct inet_timewait_death_row
*,
487 struct sock
*, __u16
, struct inet_timewait_sock
**),
488 int (*hash
)(struct sock
*sk
, struct inet_timewait_sock
*twp
))
490 struct inet_hashinfo
*hinfo
= death_row
->hashinfo
;
491 const unsigned short snum
= inet_sk(sk
)->inet_num
;
492 struct inet_bind_hashbucket
*head
;
493 struct inet_bind_bucket
*tb
;
495 struct net
*net
= sock_net(sk
);
499 int i
, remaining
, low
, high
, port
;
501 u32 offset
= hint
+ port_offset
;
502 struct inet_timewait_sock
*tw
= NULL
;
504 inet_get_local_port_range(net
, &low
, &high
);
505 remaining
= (high
- low
) + 1;
508 for (i
= 1; i
<= remaining
; i
++) {
509 port
= low
+ (i
+ offset
) % remaining
;
510 if (inet_is_local_reserved_port(net
, port
))
512 head
= &hinfo
->bhash
[inet_bhashfn(net
, port
,
514 spin_lock(&head
->lock
);
516 /* Does not bother with rcv_saddr checks,
517 * because the established check is already
520 inet_bind_bucket_for_each(tb
, &head
->chain
) {
521 if (net_eq(ib_net(tb
), net
) &&
523 if (tb
->fastreuse
>= 0 ||
524 tb
->fastreuseport
>= 0)
526 WARN_ON(hlist_empty(&tb
->owners
));
527 if (!check_established(death_row
, sk
,
534 tb
= inet_bind_bucket_create(hinfo
->bind_bucket_cachep
,
537 spin_unlock(&head
->lock
);
541 tb
->fastreuseport
= -1;
545 spin_unlock(&head
->lock
);
549 return -EADDRNOTAVAIL
;
554 /* Head lock still held and bh's disabled */
555 inet_bind_hash(sk
, tb
, port
);
556 if (sk_unhashed(sk
)) {
557 inet_sk(sk
)->inet_sport
= htons(port
);
558 twrefcnt
+= hash(sk
, tw
);
561 twrefcnt
+= inet_twsk_bind_unhash(tw
, hinfo
);
562 spin_unlock(&head
->lock
);
565 inet_twsk_deschedule(tw
, death_row
);
576 head
= &hinfo
->bhash
[inet_bhashfn(net
, snum
, hinfo
->bhash_size
)];
577 tb
= inet_csk(sk
)->icsk_bind_hash
;
578 spin_lock_bh(&head
->lock
);
579 if (sk_head(&tb
->owners
) == sk
&& !sk
->sk_bind_node
.next
) {
581 spin_unlock_bh(&head
->lock
);
584 spin_unlock(&head
->lock
);
585 /* No definite answer... Walk to established hash table */
586 ret
= check_established(death_row
, sk
, snum
, NULL
);
594 * Bind a port for a connect operation and hash it.
596 int inet_hash_connect(struct inet_timewait_death_row
*death_row
,
599 return __inet_hash_connect(death_row
, sk
, inet_sk_port_offset(sk
),
600 __inet_check_established
, __inet_hash_nolisten
);
602 EXPORT_SYMBOL_GPL(inet_hash_connect
);
604 void inet_hashinfo_init(struct inet_hashinfo
*h
)
608 atomic_set(&h
->bsockets
, 0);
609 for (i
= 0; i
< INET_LHTABLE_SIZE
; i
++) {
610 spin_lock_init(&h
->listening_hash
[i
].lock
);
611 INIT_HLIST_NULLS_HEAD(&h
->listening_hash
[i
].head
,
612 i
+ LISTENING_NULLS_BASE
);
615 EXPORT_SYMBOL_GPL(inet_hashinfo_init
);