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 * Don't inline this cruft. Here are some nice properties to exploit here. The
115 * BSD API does not allow a listening sock to specify the remote port nor the
116 * remote address for the connection. So always assume those are both
117 * wildcarded during the search since they can never be otherwise.
119 static struct sock *inet_lookup_listener_slow(struct net *net,
120 const struct hlist_head *head,
122 const unsigned short hnum,
125 struct sock *result = NULL, *sk;
126 const struct hlist_node *node;
129 sk_for_each(sk, node, head) {
130 const struct inet_sock *inet = inet_sk(sk);
132 if (net_eq(sock_net(sk), net) && inet->num == hnum &&
133 !ipv6_only_sock(sk)) {
134 const __be32 rcv_saddr = inet->rcv_saddr;
135 int score = sk->sk_family == PF_INET ? 1 : 0;
138 if (rcv_saddr != daddr)
142 if (sk->sk_bound_dev_if) {
143 if (sk->sk_bound_dev_if != dif)
149 if (score > hiscore) {
158 /* Optimize the common listener case. */
159 struct sock *__inet_lookup_listener(struct net *net,
160 struct inet_hashinfo *hashinfo,
161 const __be32 daddr, const unsigned short hnum,
164 struct sock *sk = NULL;
165 struct inet_listen_hashbucket *ilb;
167 ilb = &hashinfo->listening_hash[inet_lhashfn(net, hnum)];
168 spin_lock(&ilb->lock);
169 if (!hlist_empty(&ilb->head)) {
170 const struct inet_sock *inet = inet_sk((sk = __sk_head(&ilb->head)));
172 if (inet->num == hnum && !sk->sk_node.next &&
173 (!inet->rcv_saddr || inet->rcv_saddr == daddr) &&
174 (sk->sk_family == PF_INET || !ipv6_only_sock(sk)) &&
175 !sk->sk_bound_dev_if && net_eq(sock_net(sk), net))
177 sk = inet_lookup_listener_slow(net, &ilb->head, daddr, hnum, dif);
183 spin_unlock(&ilb->lock);
186 EXPORT_SYMBOL_GPL(__inet_lookup_listener);
188 struct sock * __inet_lookup_established(struct net *net,
189 struct inet_hashinfo *hashinfo,
190 const __be32 saddr, const __be16 sport,
191 const __be32 daddr, const u16 hnum,
194 INET_ADDR_COOKIE(acookie, saddr, daddr)
195 const __portpair ports = INET_COMBINED_PORTS(sport, hnum);
197 const struct hlist_nulls_node *node;
198 /* Optimize here for direct hit, only listening connections can
199 * have wildcards anyways.
201 unsigned int hash = inet_ehashfn(net, daddr, hnum, saddr, sport);
202 unsigned int slot = hash & (hashinfo->ehash_size - 1);
203 struct inet_ehash_bucket *head = &hashinfo->ehash[slot];
207 sk_nulls_for_each_rcu(sk, node, &head->chain) {
208 if (INET_MATCH(sk, net, hash, acookie,
209 saddr, daddr, ports, dif)) {
210 if (unlikely(!atomic_inc_not_zero(&sk->sk_refcnt)))
212 if (unlikely(!INET_MATCH(sk, net, hash, acookie,
213 saddr, daddr, ports, dif))) {
221 * if the nulls value we got at the end of this lookup is
222 * not the expected one, we must restart lookup.
223 * We probably met an item that was moved to another chain.
225 if (get_nulls_value(node) != slot)
229 /* Must check for a TIME_WAIT'er before going to listener hash. */
230 sk_nulls_for_each_rcu(sk, node, &head->twchain) {
231 if (INET_TW_MATCH(sk, net, hash, acookie,
232 saddr, daddr, ports, dif)) {
233 if (unlikely(!atomic_inc_not_zero(&sk->sk_refcnt))) {
237 if (unlikely(!INET_TW_MATCH(sk, net, hash, acookie,
238 saddr, daddr, ports, dif))) {
246 * if the nulls value we got at the end of this lookup is
247 * not the expected one, we must restart lookup.
248 * We probably met an item that was moved to another chain.
250 if (get_nulls_value(node) != slot)
257 EXPORT_SYMBOL_GPL(__inet_lookup_established);
259 /* called with local bh disabled */
260 static int __inet_check_established(struct inet_timewait_death_row *death_row,
261 struct sock *sk, __u16 lport,
262 struct inet_timewait_sock **twp)
264 struct inet_hashinfo *hinfo = death_row->hashinfo;
265 struct inet_sock *inet = inet_sk(sk);
266 __be32 daddr = inet->rcv_saddr;
267 __be32 saddr = inet->daddr;
268 int dif = sk->sk_bound_dev_if;
269 INET_ADDR_COOKIE(acookie, saddr, daddr)
270 const __portpair ports = INET_COMBINED_PORTS(inet->dport, lport);
271 struct net *net = sock_net(sk);
272 unsigned int hash = inet_ehashfn(net, daddr, lport, saddr, inet->dport);
273 struct inet_ehash_bucket *head = inet_ehash_bucket(hinfo, hash);
274 rwlock_t *lock = inet_ehash_lockp(hinfo, hash);
276 const struct hlist_nulls_node *node;
277 struct inet_timewait_sock *tw;
279 prefetch(head->chain.first);
282 /* Check TIME-WAIT sockets first. */
283 sk_nulls_for_each(sk2, node, &head->twchain) {
286 if (INET_TW_MATCH(sk2, net, hash, acookie,
287 saddr, daddr, ports, dif)) {
288 if (twsk_unique(sk, sk2, twp))
296 /* And established part... */
297 sk_nulls_for_each(sk2, node, &head->chain) {
298 if (INET_MATCH(sk2, net, hash, acookie,
299 saddr, daddr, ports, dif))
304 /* Must record num and sport now. Otherwise we will see
305 * in hash table socket with a funny identity. */
307 inet->sport = htons(lport);
309 WARN_ON(!sk_unhashed(sk));
310 __sk_nulls_add_node_rcu(sk, &head->chain);
311 sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
316 NET_INC_STATS_BH(net, LINUX_MIB_TIMEWAITRECYCLED);
318 /* Silly. Should hash-dance instead... */
319 inet_twsk_deschedule(tw, death_row);
320 NET_INC_STATS_BH(net, LINUX_MIB_TIMEWAITRECYCLED);
329 return -EADDRNOTAVAIL;
332 static inline u32 inet_sk_port_offset(const struct sock *sk)
334 const struct inet_sock *inet = inet_sk(sk);
335 return secure_ipv4_port_ephemeral(inet->rcv_saddr, inet->daddr,
339 void __inet_hash_nolisten(struct sock *sk)
341 struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
342 struct hlist_nulls_head *list;
344 struct inet_ehash_bucket *head;
346 WARN_ON(!sk_unhashed(sk));
348 sk->sk_hash = inet_sk_ehashfn(sk);
349 head = inet_ehash_bucket(hashinfo, sk->sk_hash);
351 lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
354 __sk_nulls_add_node_rcu(sk, list);
355 sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
358 EXPORT_SYMBOL_GPL(__inet_hash_nolisten);
360 static void __inet_hash(struct sock *sk)
362 struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
363 struct inet_listen_hashbucket *ilb;
365 if (sk->sk_state != TCP_LISTEN) {
366 __inet_hash_nolisten(sk);
370 WARN_ON(!sk_unhashed(sk));
371 ilb = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)];
373 spin_lock(&ilb->lock);
374 __sk_add_node(sk, &ilb->head);
375 sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
376 spin_unlock(&ilb->lock);
379 void inet_hash(struct sock *sk)
381 if (sk->sk_state != TCP_CLOSE) {
387 EXPORT_SYMBOL_GPL(inet_hash);
389 void inet_unhash(struct sock *sk)
391 struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
396 if (sk->sk_state == TCP_LISTEN) {
397 struct inet_listen_hashbucket *ilb;
399 ilb = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)];
400 spin_lock_bh(&ilb->lock);
401 if (__sk_del_node_init(sk))
402 sock_prot_inuse_add(sock_net(sk), sk->sk_prot, -1);
403 spin_unlock_bh(&ilb->lock);
405 rwlock_t *lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
408 if (__sk_nulls_del_node_init_rcu(sk))
409 sock_prot_inuse_add(sock_net(sk), sk->sk_prot, -1);
410 write_unlock_bh(lock);
413 EXPORT_SYMBOL_GPL(inet_unhash);
415 int __inet_hash_connect(struct inet_timewait_death_row *death_row,
416 struct sock *sk, u32 port_offset,
417 int (*check_established)(struct inet_timewait_death_row *,
418 struct sock *, __u16, struct inet_timewait_sock **),
419 void (*hash)(struct sock *sk))
421 struct inet_hashinfo *hinfo = death_row->hashinfo;
422 const unsigned short snum = inet_sk(sk)->num;
423 struct inet_bind_hashbucket *head;
424 struct inet_bind_bucket *tb;
426 struct net *net = sock_net(sk);
429 int i, remaining, low, high, port;
431 u32 offset = hint + port_offset;
432 struct hlist_node *node;
433 struct inet_timewait_sock *tw = NULL;
435 inet_get_local_port_range(&low, &high);
436 remaining = (high - low) + 1;
439 for (i = 1; i <= remaining; i++) {
440 port = low + (i + offset) % remaining;
441 head = &hinfo->bhash[inet_bhashfn(net, port,
443 spin_lock(&head->lock);
445 /* Does not bother with rcv_saddr checks,
446 * because the established check is already
449 inet_bind_bucket_for_each(tb, node, &head->chain) {
450 if (ib_net(tb) == net && tb->port == port) {
451 WARN_ON(hlist_empty(&tb->owners));
452 if (tb->fastreuse >= 0)
454 if (!check_established(death_row, sk,
461 tb = inet_bind_bucket_create(hinfo->bind_bucket_cachep,
464 spin_unlock(&head->lock);
471 spin_unlock(&head->lock);
475 return -EADDRNOTAVAIL;
480 /* Head lock still held and bh's disabled */
481 inet_bind_hash(sk, tb, port);
482 if (sk_unhashed(sk)) {
483 inet_sk(sk)->sport = htons(port);
486 spin_unlock(&head->lock);
489 inet_twsk_deschedule(tw, death_row);
497 head = &hinfo->bhash[inet_bhashfn(net, snum, hinfo->bhash_size)];
498 tb = inet_csk(sk)->icsk_bind_hash;
499 spin_lock_bh(&head->lock);
500 if (sk_head(&tb->owners) == sk && !sk->sk_bind_node.next) {
502 spin_unlock_bh(&head->lock);
505 spin_unlock(&head->lock);
506 /* No definite answer... Walk to established hash table */
507 ret = check_established(death_row, sk, snum, NULL);
515 * Bind a port for a connect operation and hash it.
517 int inet_hash_connect(struct inet_timewait_death_row *death_row,
520 return __inet_hash_connect(death_row, sk, inet_sk_port_offset(sk),
521 __inet_check_established, __inet_hash_nolisten);
524 EXPORT_SYMBOL_GPL(inet_hash_connect);
526 void inet_hashinfo_init(struct inet_hashinfo *h)
530 for (i = 0; i < INET_LHTABLE_SIZE; i++)
531 spin_lock_init(&h->listening_hash[i].lock);
534 EXPORT_SYMBOL_GPL(inet_hashinfo_init);