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>
21 #include <linux/vmalloc.h>
23 #include <net/inet_connection_sock.h>
24 #include <net/inet_hashtables.h>
25 #include <net/secure_seq.h>
28 static u32
inet_ehashfn(const struct net
*net
, const __be32 laddr
,
29 const __u16 lport
, const __be32 faddr
,
32 static u32 inet_ehash_secret __read_mostly
;
34 net_get_random_once(&inet_ehash_secret
, sizeof(inet_ehash_secret
));
36 return __inet_ehashfn(laddr
, lport
, faddr
, fport
,
37 inet_ehash_secret
+ net_hash_mix(net
));
40 /* This function handles inet_sock, but also timewait and request sockets
43 u32
sk_ehashfn(const struct sock
*sk
)
45 #if IS_ENABLED(CONFIG_IPV6)
46 if (sk
->sk_family
== AF_INET6
&&
47 !ipv6_addr_v4mapped(&sk
->sk_v6_daddr
))
48 return inet6_ehashfn(sock_net(sk
),
49 &sk
->sk_v6_rcv_saddr
, sk
->sk_num
,
50 &sk
->sk_v6_daddr
, sk
->sk_dport
);
52 return inet_ehashfn(sock_net(sk
),
53 sk
->sk_rcv_saddr
, sk
->sk_num
,
54 sk
->sk_daddr
, sk
->sk_dport
);
58 * Allocate and initialize a new local port bind bucket.
59 * The bindhash mutex for snum's hash chain must be held here.
61 struct inet_bind_bucket
*inet_bind_bucket_create(struct kmem_cache
*cachep
,
63 struct inet_bind_hashbucket
*head
,
64 const unsigned short snum
)
66 struct inet_bind_bucket
*tb
= kmem_cache_alloc(cachep
, GFP_ATOMIC
);
69 write_pnet(&tb
->ib_net
, net
);
72 tb
->fastreuseport
= 0;
74 INIT_HLIST_HEAD(&tb
->owners
);
75 hlist_add_head(&tb
->node
, &head
->chain
);
81 * Caller must hold hashbucket lock for this tb with local BH disabled
83 void inet_bind_bucket_destroy(struct kmem_cache
*cachep
, struct inet_bind_bucket
*tb
)
85 if (hlist_empty(&tb
->owners
)) {
86 __hlist_del(&tb
->node
);
87 kmem_cache_free(cachep
, tb
);
91 void inet_bind_hash(struct sock
*sk
, struct inet_bind_bucket
*tb
,
92 const unsigned short snum
)
94 inet_sk(sk
)->inet_num
= snum
;
95 sk_add_bind_node(sk
, &tb
->owners
);
97 inet_csk(sk
)->icsk_bind_hash
= tb
;
101 * Get rid of any references to a local port held by the given sock.
103 static void __inet_put_port(struct sock
*sk
)
105 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
106 const int bhash
= inet_bhashfn(sock_net(sk
), inet_sk(sk
)->inet_num
,
107 hashinfo
->bhash_size
);
108 struct inet_bind_hashbucket
*head
= &hashinfo
->bhash
[bhash
];
109 struct inet_bind_bucket
*tb
;
111 spin_lock(&head
->lock
);
112 tb
= inet_csk(sk
)->icsk_bind_hash
;
113 __sk_del_bind_node(sk
);
115 inet_csk(sk
)->icsk_bind_hash
= NULL
;
116 inet_sk(sk
)->inet_num
= 0;
117 inet_bind_bucket_destroy(hashinfo
->bind_bucket_cachep
, tb
);
118 spin_unlock(&head
->lock
);
121 void inet_put_port(struct sock
*sk
)
127 EXPORT_SYMBOL(inet_put_port
);
129 int __inet_inherit_port(struct sock
*sk
, struct sock
*child
)
131 struct inet_hashinfo
*table
= sk
->sk_prot
->h
.hashinfo
;
132 unsigned short port
= inet_sk(child
)->inet_num
;
133 const int bhash
= inet_bhashfn(sock_net(sk
), port
,
135 struct inet_bind_hashbucket
*head
= &table
->bhash
[bhash
];
136 struct inet_bind_bucket
*tb
;
138 spin_lock(&head
->lock
);
139 tb
= inet_csk(sk
)->icsk_bind_hash
;
140 if (tb
->port
!= port
) {
141 /* NOTE: using tproxy and redirecting skbs to a proxy
142 * on a different listener port breaks the assumption
143 * that the listener socket's icsk_bind_hash is the same
144 * as that of the child socket. We have to look up or
145 * create a new bind bucket for the child here. */
146 inet_bind_bucket_for_each(tb
, &head
->chain
) {
147 if (net_eq(ib_net(tb
), sock_net(sk
)) &&
152 tb
= inet_bind_bucket_create(table
->bind_bucket_cachep
,
153 sock_net(sk
), head
, port
);
155 spin_unlock(&head
->lock
);
160 inet_bind_hash(child
, tb
, port
);
161 spin_unlock(&head
->lock
);
165 EXPORT_SYMBOL_GPL(__inet_inherit_port
);
167 static inline int compute_score(struct sock
*sk
, struct net
*net
,
168 const unsigned short hnum
, const __be32 daddr
,
172 struct inet_sock
*inet
= inet_sk(sk
);
174 if (net_eq(sock_net(sk
), net
) && inet
->inet_num
== hnum
&&
175 !ipv6_only_sock(sk
)) {
176 __be32 rcv_saddr
= inet
->inet_rcv_saddr
;
177 score
= sk
->sk_family
== PF_INET
? 2 : 1;
179 if (rcv_saddr
!= daddr
)
183 if (sk
->sk_bound_dev_if
) {
184 if (sk
->sk_bound_dev_if
!= dif
)
193 * Don't inline this cruft. Here are some nice properties to exploit here. The
194 * BSD API does not allow a listening sock to specify the remote port nor the
195 * remote address for the connection. So always assume those are both
196 * wildcarded during the search since they can never be otherwise.
200 struct sock
*__inet_lookup_listener(struct net
*net
,
201 struct inet_hashinfo
*hashinfo
,
202 const __be32 saddr
, __be16 sport
,
203 const __be32 daddr
, const unsigned short hnum
,
206 struct sock
*sk
, *result
;
207 struct hlist_nulls_node
*node
;
208 unsigned int hash
= inet_lhashfn(net
, hnum
);
209 struct inet_listen_hashbucket
*ilb
= &hashinfo
->listening_hash
[hash
];
210 int score
, hiscore
, matches
= 0, reuseport
= 0;
217 sk_nulls_for_each_rcu(sk
, node
, &ilb
->head
) {
218 score
= compute_score(sk
, net
, hnum
, daddr
, dif
);
219 if (score
> hiscore
) {
222 reuseport
= sk
->sk_reuseport
;
224 phash
= inet_ehashfn(net
, daddr
, hnum
,
228 } else if (score
== hiscore
&& reuseport
) {
230 if (reciprocal_scale(phash
, matches
) == 0)
232 phash
= next_pseudo_random32(phash
);
236 * if the nulls value we got at the end of this lookup is
237 * not the expected one, we must restart lookup.
238 * We probably met an item that was moved to another chain.
240 if (get_nulls_value(node
) != hash
+ LISTENING_NULLS_BASE
)
243 if (unlikely(!atomic_inc_not_zero(&result
->sk_refcnt
)))
245 else if (unlikely(compute_score(result
, net
, hnum
, daddr
,
254 EXPORT_SYMBOL_GPL(__inet_lookup_listener
);
256 /* All sockets share common refcount, but have different destructors */
257 void sock_gen_put(struct sock
*sk
)
259 if (!atomic_dec_and_test(&sk
->sk_refcnt
))
262 if (sk
->sk_state
== TCP_TIME_WAIT
)
263 inet_twsk_free(inet_twsk(sk
));
264 else if (sk
->sk_state
== TCP_NEW_SYN_RECV
)
265 reqsk_free(inet_reqsk(sk
));
269 EXPORT_SYMBOL_GPL(sock_gen_put
);
271 void sock_edemux(struct sk_buff
*skb
)
273 sock_gen_put(skb
->sk
);
275 EXPORT_SYMBOL(sock_edemux
);
277 struct sock
*__inet_lookup_established(struct net
*net
,
278 struct inet_hashinfo
*hashinfo
,
279 const __be32 saddr
, const __be16 sport
,
280 const __be32 daddr
, const u16 hnum
,
283 INET_ADDR_COOKIE(acookie
, saddr
, daddr
);
284 const __portpair ports
= INET_COMBINED_PORTS(sport
, hnum
);
286 const struct hlist_nulls_node
*node
;
287 /* Optimize here for direct hit, only listening connections can
288 * have wildcards anyways.
290 unsigned int hash
= inet_ehashfn(net
, daddr
, hnum
, saddr
, sport
);
291 unsigned int slot
= hash
& hashinfo
->ehash_mask
;
292 struct inet_ehash_bucket
*head
= &hashinfo
->ehash
[slot
];
296 sk_nulls_for_each_rcu(sk
, node
, &head
->chain
) {
297 if (sk
->sk_hash
!= hash
)
299 if (likely(INET_MATCH(sk
, net
, acookie
,
300 saddr
, daddr
, ports
, dif
))) {
301 if (unlikely(!atomic_inc_not_zero(&sk
->sk_refcnt
)))
303 if (unlikely(!INET_MATCH(sk
, net
, acookie
,
304 saddr
, daddr
, ports
, dif
))) {
312 * if the nulls value we got at the end of this lookup is
313 * not the expected one, we must restart lookup.
314 * We probably met an item that was moved to another chain.
316 if (get_nulls_value(node
) != slot
)
324 EXPORT_SYMBOL_GPL(__inet_lookup_established
);
326 /* called with local bh disabled */
327 static int __inet_check_established(struct inet_timewait_death_row
*death_row
,
328 struct sock
*sk
, __u16 lport
,
329 struct inet_timewait_sock
**twp
)
331 struct inet_hashinfo
*hinfo
= death_row
->hashinfo
;
332 struct inet_sock
*inet
= inet_sk(sk
);
333 __be32 daddr
= inet
->inet_rcv_saddr
;
334 __be32 saddr
= inet
->inet_daddr
;
335 int dif
= sk
->sk_bound_dev_if
;
336 INET_ADDR_COOKIE(acookie
, saddr
, daddr
);
337 const __portpair ports
= INET_COMBINED_PORTS(inet
->inet_dport
, lport
);
338 struct net
*net
= sock_net(sk
);
339 unsigned int hash
= inet_ehashfn(net
, daddr
, lport
,
340 saddr
, inet
->inet_dport
);
341 struct inet_ehash_bucket
*head
= inet_ehash_bucket(hinfo
, hash
);
342 spinlock_t
*lock
= inet_ehash_lockp(hinfo
, hash
);
344 const struct hlist_nulls_node
*node
;
345 struct inet_timewait_sock
*tw
= NULL
;
349 sk_nulls_for_each(sk2
, node
, &head
->chain
) {
350 if (sk2
->sk_hash
!= hash
)
353 if (likely(INET_MATCH(sk2
, net
, acookie
,
354 saddr
, daddr
, ports
, dif
))) {
355 if (sk2
->sk_state
== TCP_TIME_WAIT
) {
357 if (twsk_unique(sk
, sk2
, twp
))
364 /* Must record num and sport now. Otherwise we will see
365 * in hash table socket with a funny identity.
367 inet
->inet_num
= lport
;
368 inet
->inet_sport
= htons(lport
);
370 WARN_ON(!sk_unhashed(sk
));
371 __sk_nulls_add_node_rcu(sk
, &head
->chain
);
373 sk_nulls_del_node_init_rcu((struct sock
*)tw
);
374 NET_INC_STATS_BH(net
, LINUX_MIB_TIMEWAITRECYCLED
);
377 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
382 /* Silly. Should hash-dance instead... */
383 inet_twsk_deschedule(tw
);
390 return -EADDRNOTAVAIL
;
393 static u32
inet_sk_port_offset(const struct sock
*sk
)
395 const struct inet_sock
*inet
= inet_sk(sk
);
397 return secure_ipv4_port_ephemeral(inet
->inet_rcv_saddr
,
402 void __inet_hash_nolisten(struct sock
*sk
, struct sock
*osk
)
404 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
405 struct hlist_nulls_head
*list
;
406 struct inet_ehash_bucket
*head
;
409 WARN_ON(!sk_unhashed(sk
));
411 sk
->sk_hash
= sk_ehashfn(sk
);
412 head
= inet_ehash_bucket(hashinfo
, sk
->sk_hash
);
414 lock
= inet_ehash_lockp(hashinfo
, sk
->sk_hash
);
417 __sk_nulls_add_node_rcu(sk
, list
);
419 WARN_ON(sk
->sk_hash
!= osk
->sk_hash
);
420 sk_nulls_del_node_init_rcu(osk
);
423 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
425 EXPORT_SYMBOL_GPL(__inet_hash_nolisten
);
427 void __inet_hash(struct sock
*sk
, struct sock
*osk
)
429 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
430 struct inet_listen_hashbucket
*ilb
;
432 if (sk
->sk_state
!= TCP_LISTEN
)
433 return __inet_hash_nolisten(sk
, osk
);
435 WARN_ON(!sk_unhashed(sk
));
436 ilb
= &hashinfo
->listening_hash
[inet_sk_listen_hashfn(sk
)];
438 spin_lock(&ilb
->lock
);
439 __sk_nulls_add_node_rcu(sk
, &ilb
->head
);
440 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, 1);
441 spin_unlock(&ilb
->lock
);
443 EXPORT_SYMBOL(__inet_hash
);
445 void inet_hash(struct sock
*sk
)
447 if (sk
->sk_state
!= TCP_CLOSE
) {
449 __inet_hash(sk
, NULL
);
453 EXPORT_SYMBOL_GPL(inet_hash
);
455 void inet_unhash(struct sock
*sk
)
457 struct inet_hashinfo
*hashinfo
= sk
->sk_prot
->h
.hashinfo
;
464 if (sk
->sk_state
== TCP_LISTEN
)
465 lock
= &hashinfo
->listening_hash
[inet_sk_listen_hashfn(sk
)].lock
;
467 lock
= inet_ehash_lockp(hashinfo
, sk
->sk_hash
);
470 done
= __sk_nulls_del_node_init_rcu(sk
);
472 sock_prot_inuse_add(sock_net(sk
), sk
->sk_prot
, -1);
473 spin_unlock_bh(lock
);
475 EXPORT_SYMBOL_GPL(inet_unhash
);
477 int __inet_hash_connect(struct inet_timewait_death_row
*death_row
,
478 struct sock
*sk
, u32 port_offset
,
479 int (*check_established
)(struct inet_timewait_death_row
*,
480 struct sock
*, __u16
, struct inet_timewait_sock
**))
482 struct inet_hashinfo
*hinfo
= death_row
->hashinfo
;
483 const unsigned short snum
= inet_sk(sk
)->inet_num
;
484 struct inet_bind_hashbucket
*head
;
485 struct inet_bind_bucket
*tb
;
487 struct net
*net
= sock_net(sk
);
490 int i
, remaining
, low
, high
, port
;
492 u32 offset
= hint
+ port_offset
;
493 struct inet_timewait_sock
*tw
= NULL
;
495 inet_get_local_port_range(net
, &low
, &high
);
496 remaining
= (high
- low
) + 1;
498 /* By starting with offset being an even number,
499 * we tend to leave about 50% of ports for other uses,
505 for (i
= 0; i
< remaining
; i
++) {
506 port
= low
+ (i
+ offset
) % remaining
;
507 if (inet_is_local_reserved_port(net
, port
))
509 head
= &hinfo
->bhash
[inet_bhashfn(net
, port
,
511 spin_lock(&head
->lock
);
513 /* Does not bother with rcv_saddr checks,
514 * because the established check is already
517 inet_bind_bucket_for_each(tb
, &head
->chain
) {
518 if (net_eq(ib_net(tb
), net
) &&
520 if (tb
->fastreuse
>= 0 ||
521 tb
->fastreuseport
>= 0)
523 WARN_ON(hlist_empty(&tb
->owners
));
524 if (!check_established(death_row
, sk
,
531 tb
= inet_bind_bucket_create(hinfo
->bind_bucket_cachep
,
534 spin_unlock(&head
->lock
);
538 tb
->fastreuseport
= -1;
542 spin_unlock(&head
->lock
);
546 return -EADDRNOTAVAIL
;
549 hint
+= (i
+ 2) & ~1;
551 /* Head lock still held and bh's disabled */
552 inet_bind_hash(sk
, tb
, port
);
553 if (sk_unhashed(sk
)) {
554 inet_sk(sk
)->inet_sport
= htons(port
);
555 __inet_hash_nolisten(sk
, (struct sock
*)tw
);
558 inet_twsk_bind_unhash(tw
, hinfo
);
559 spin_unlock(&head
->lock
);
562 inet_twsk_deschedule(tw
);
570 head
= &hinfo
->bhash
[inet_bhashfn(net
, snum
, hinfo
->bhash_size
)];
571 tb
= inet_csk(sk
)->icsk_bind_hash
;
572 spin_lock_bh(&head
->lock
);
573 if (sk_head(&tb
->owners
) == sk
&& !sk
->sk_bind_node
.next
) {
574 __inet_hash_nolisten(sk
, NULL
);
575 spin_unlock_bh(&head
->lock
);
578 spin_unlock(&head
->lock
);
579 /* No definite answer... Walk to established hash table */
580 ret
= check_established(death_row
, sk
, snum
, NULL
);
588 * Bind a port for a connect operation and hash it.
590 int inet_hash_connect(struct inet_timewait_death_row
*death_row
,
595 if (!inet_sk(sk
)->inet_num
)
596 port_offset
= inet_sk_port_offset(sk
);
597 return __inet_hash_connect(death_row
, sk
, port_offset
,
598 __inet_check_established
);
600 EXPORT_SYMBOL_GPL(inet_hash_connect
);
602 void inet_hashinfo_init(struct inet_hashinfo
*h
)
606 for (i
= 0; i
< INET_LHTABLE_SIZE
; i
++) {
607 spin_lock_init(&h
->listening_hash
[i
].lock
);
608 INIT_HLIST_NULLS_HEAD(&h
->listening_hash
[i
].head
,
609 i
+ LISTENING_NULLS_BASE
);
612 EXPORT_SYMBOL_GPL(inet_hashinfo_init
);
614 int inet_ehash_locks_alloc(struct inet_hashinfo
*hashinfo
)
616 unsigned int i
, nblocks
= 1;
618 if (sizeof(spinlock_t
) != 0) {
619 /* allocate 2 cache lines or at least one spinlock per cpu */
620 nblocks
= max_t(unsigned int,
621 2 * L1_CACHE_BYTES
/ sizeof(spinlock_t
),
623 nblocks
= roundup_pow_of_two(nblocks
* num_possible_cpus());
625 /* no more locks than number of hash buckets */
626 nblocks
= min(nblocks
, hashinfo
->ehash_mask
+ 1);
628 hashinfo
->ehash_locks
= kmalloc_array(nblocks
, sizeof(spinlock_t
),
629 GFP_KERNEL
| __GFP_NOWARN
);
630 if (!hashinfo
->ehash_locks
)
631 hashinfo
->ehash_locks
= vmalloc(nblocks
* sizeof(spinlock_t
));
633 if (!hashinfo
->ehash_locks
)
636 for (i
= 0; i
< nblocks
; i
++)
637 spin_lock_init(&hashinfo
->ehash_locks
[i
]);
639 hashinfo
->ehash_locks_mask
= nblocks
- 1;
642 EXPORT_SYMBOL_GPL(inet_ehash_locks_alloc
);