1/*
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.
5 *
6 *		Generic INET transport hashtables
7 *
8 * Authors:	Lotsa people, from code originally in tcp
9 *
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.
14 */
15
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
22#include <net/inet_connection_sock.h>
23#include <net/inet_hashtables.h>
24#include <net/secure_seq.h>
25#include <net/ip.h>
26
27static u32 inet_ehashfn(const struct net *net, const __be32 laddr,
28			const __u16 lport, const __be32 faddr,
29			const __be16 fport)
30{
31	static u32 inet_ehash_secret __read_mostly;
32
33	net_get_random_once(&inet_ehash_secret, sizeof(inet_ehash_secret));
34
35	return __inet_ehashfn(laddr, lport, faddr, fport,
36			      inet_ehash_secret + net_hash_mix(net));
37}
38
39/* This function handles inet_sock, but also timewait and request sockets
40 * for IPv4/IPv6.
41 */
42u32 sk_ehashfn(const struct sock *sk)
43{
44#if IS_ENABLED(CONFIG_IPV6)
45	if (sk->sk_family == AF_INET6 &&
46	    !ipv6_addr_v4mapped(&sk->sk_v6_daddr))
47		return inet6_ehashfn(sock_net(sk),
48				     &sk->sk_v6_rcv_saddr, sk->sk_num,
49				     &sk->sk_v6_daddr, sk->sk_dport);
50#endif
51	return inet_ehashfn(sock_net(sk),
52			    sk->sk_rcv_saddr, sk->sk_num,
53			    sk->sk_daddr, sk->sk_dport);
54}
55
56/*
57 * Allocate and initialize a new local port bind bucket.
58 * The bindhash mutex for snum's hash chain must be held here.
59 */
60struct inet_bind_bucket *inet_bind_bucket_create(struct kmem_cache *cachep,
61						 struct net *net,
62						 struct inet_bind_hashbucket *head,
63						 const unsigned short snum)
64{
65	struct inet_bind_bucket *tb = kmem_cache_alloc(cachep, GFP_ATOMIC);
66
67	if (tb) {
68		write_pnet(&tb->ib_net, net);
69		tb->port      = snum;
70		tb->fastreuse = 0;
71		tb->fastreuseport = 0;
72		tb->num_owners = 0;
73		INIT_HLIST_HEAD(&tb->owners);
74		hlist_add_head(&tb->node, &head->chain);
75	}
76	return tb;
77}
78
79/*
80 * Caller must hold hashbucket lock for this tb with local BH disabled
81 */
82void inet_bind_bucket_destroy(struct kmem_cache *cachep, struct inet_bind_bucket *tb)
83{
84	if (hlist_empty(&tb->owners)) {
85		__hlist_del(&tb->node);
86		kmem_cache_free(cachep, tb);
87	}
88}
89
90void inet_bind_hash(struct sock *sk, struct inet_bind_bucket *tb,
91		    const unsigned short snum)
92{
93	struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
94
95	atomic_inc(&hashinfo->bsockets);
96
97	inet_sk(sk)->inet_num = snum;
98	sk_add_bind_node(sk, &tb->owners);
99	tb->num_owners++;
100	inet_csk(sk)->icsk_bind_hash = tb;
101}
102
103/*
104 * Get rid of any references to a local port held by the given sock.
105 */
106static void __inet_put_port(struct sock *sk)
107{
108	struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
109	const int bhash = inet_bhashfn(sock_net(sk), inet_sk(sk)->inet_num,
110			hashinfo->bhash_size);
111	struct inet_bind_hashbucket *head = &hashinfo->bhash[bhash];
112	struct inet_bind_bucket *tb;
113
114	atomic_dec(&hashinfo->bsockets);
115
116	spin_lock(&head->lock);
117	tb = inet_csk(sk)->icsk_bind_hash;
118	__sk_del_bind_node(sk);
119	tb->num_owners--;
120	inet_csk(sk)->icsk_bind_hash = NULL;
121	inet_sk(sk)->inet_num = 0;
122	inet_bind_bucket_destroy(hashinfo->bind_bucket_cachep, tb);
123	spin_unlock(&head->lock);
124}
125
126void inet_put_port(struct sock *sk)
127{
128	local_bh_disable();
129	__inet_put_port(sk);
130	local_bh_enable();
131}
132EXPORT_SYMBOL(inet_put_port);
133
134int __inet_inherit_port(struct sock *sk, struct sock *child)
135{
136	struct inet_hashinfo *table = sk->sk_prot->h.hashinfo;
137	unsigned short port = inet_sk(child)->inet_num;
138	const int bhash = inet_bhashfn(sock_net(sk), port,
139			table->bhash_size);
140	struct inet_bind_hashbucket *head = &table->bhash[bhash];
141	struct inet_bind_bucket *tb;
142
143	spin_lock(&head->lock);
144	tb = inet_csk(sk)->icsk_bind_hash;
145	if (tb->port != port) {
146		/* NOTE: using tproxy and redirecting skbs to a proxy
147		 * on a different listener port breaks the assumption
148		 * that the listener socket's icsk_bind_hash is the same
149		 * as that of the child socket. We have to look up or
150		 * create a new bind bucket for the child here. */
151		inet_bind_bucket_for_each(tb, &head->chain) {
152			if (net_eq(ib_net(tb), sock_net(sk)) &&
153			    tb->port == port)
154				break;
155		}
156		if (!tb) {
157			tb = inet_bind_bucket_create(table->bind_bucket_cachep,
158						     sock_net(sk), head, port);
159			if (!tb) {
160				spin_unlock(&head->lock);
161				return -ENOMEM;
162			}
163		}
164	}
165	inet_bind_hash(child, tb, port);
166	spin_unlock(&head->lock);
167
168	return 0;
169}
170EXPORT_SYMBOL_GPL(__inet_inherit_port);
171
172static inline int compute_score(struct sock *sk, struct net *net,
173				const unsigned short hnum, const __be32 daddr,
174				const int dif)
175{
176	int score = -1;
177	struct inet_sock *inet = inet_sk(sk);
178
179	if (net_eq(sock_net(sk), net) && inet->inet_num == hnum &&
180			!ipv6_only_sock(sk)) {
181		__be32 rcv_saddr = inet->inet_rcv_saddr;
182		score = sk->sk_family == PF_INET ? 2 : 1;
183		if (rcv_saddr) {
184			if (rcv_saddr != daddr)
185				return -1;
186			score += 4;
187		}
188		if (sk->sk_bound_dev_if) {
189			if (sk->sk_bound_dev_if != dif)
190				return -1;
191			score += 4;
192		}
193	}
194	return score;
195}
196
197/*
198 * Don't inline this cruft. Here are some nice properties to exploit here. The
199 * BSD API does not allow a listening sock to specify the remote port nor the
200 * remote address for the connection. So always assume those are both
201 * wildcarded during the search since they can never be otherwise.
202 */
203
204
205struct sock *__inet_lookup_listener(struct net *net,
206				    struct inet_hashinfo *hashinfo,
207				    const __be32 saddr, __be16 sport,
208				    const __be32 daddr, const unsigned short hnum,
209				    const int dif)
210{
211	struct sock *sk, *result;
212	struct hlist_nulls_node *node;
213	unsigned int hash = inet_lhashfn(net, hnum);
214	struct inet_listen_hashbucket *ilb = &hashinfo->listening_hash[hash];
215	int score, hiscore, matches = 0, reuseport = 0;
216	u32 phash = 0;
217
218	rcu_read_lock();
219begin:
220	result = NULL;
221	hiscore = 0;
222	sk_nulls_for_each_rcu(sk, node, &ilb->head) {
223		score = compute_score(sk, net, hnum, daddr, dif);
224		if (score > hiscore) {
225			result = sk;
226			hiscore = score;
227			reuseport = sk->sk_reuseport;
228			if (reuseport) {
229				phash = inet_ehashfn(net, daddr, hnum,
230						     saddr, sport);
231				matches = 1;
232			}
233		} else if (score == hiscore && reuseport) {
234			matches++;
235			if (reciprocal_scale(phash, matches) == 0)
236				result = sk;
237			phash = next_pseudo_random32(phash);
238		}
239	}
240	/*
241	 * if the nulls value we got at the end of this lookup is
242	 * not the expected one, we must restart lookup.
243	 * We probably met an item that was moved to another chain.
244	 */
245	if (get_nulls_value(node) != hash + LISTENING_NULLS_BASE)
246		goto begin;
247	if (result) {
248		if (unlikely(!atomic_inc_not_zero(&result->sk_refcnt)))
249			result = NULL;
250		else if (unlikely(compute_score(result, net, hnum, daddr,
251				  dif) < hiscore)) {
252			sock_put(result);
253			goto begin;
254		}
255	}
256	rcu_read_unlock();
257	return result;
258}
259EXPORT_SYMBOL_GPL(__inet_lookup_listener);
260
261/* All sockets share common refcount, but have different destructors */
262void sock_gen_put(struct sock *sk)
263{
264	if (!atomic_dec_and_test(&sk->sk_refcnt))
265		return;
266
267	if (sk->sk_state == TCP_TIME_WAIT)
268		inet_twsk_free(inet_twsk(sk));
269	else if (sk->sk_state == TCP_NEW_SYN_RECV)
270		reqsk_free(inet_reqsk(sk));
271	else
272		sk_free(sk);
273}
274EXPORT_SYMBOL_GPL(sock_gen_put);
275
276void sock_edemux(struct sk_buff *skb)
277{
278	sock_gen_put(skb->sk);
279}
280EXPORT_SYMBOL(sock_edemux);
281
282struct sock *__inet_lookup_established(struct net *net,
283				  struct inet_hashinfo *hashinfo,
284				  const __be32 saddr, const __be16 sport,
285				  const __be32 daddr, const u16 hnum,
286				  const int dif)
287{
288	INET_ADDR_COOKIE(acookie, saddr, daddr);
289	const __portpair ports = INET_COMBINED_PORTS(sport, hnum);
290	struct sock *sk;
291	const struct hlist_nulls_node *node;
292	/* Optimize here for direct hit, only listening connections can
293	 * have wildcards anyways.
294	 */
295	unsigned int hash = inet_ehashfn(net, daddr, hnum, saddr, sport);
296	unsigned int slot = hash & hashinfo->ehash_mask;
297	struct inet_ehash_bucket *head = &hashinfo->ehash[slot];
298
299	rcu_read_lock();
300begin:
301	sk_nulls_for_each_rcu(sk, node, &head->chain) {
302		if (sk->sk_hash != hash)
303			continue;
304		if (likely(INET_MATCH(sk, net, acookie,
305				      saddr, daddr, ports, dif))) {
306			if (unlikely(!atomic_inc_not_zero(&sk->sk_refcnt)))
307				goto out;
308			if (unlikely(!INET_MATCH(sk, net, acookie,
309						 saddr, daddr, ports, dif))) {
310				sock_gen_put(sk);
311				goto begin;
312			}
313			goto found;
314		}
315	}
316	/*
317	 * if the nulls value we got at the end of this lookup is
318	 * not the expected one, we must restart lookup.
319	 * We probably met an item that was moved to another chain.
320	 */
321	if (get_nulls_value(node) != slot)
322		goto begin;
323out:
324	sk = NULL;
325found:
326	rcu_read_unlock();
327	return sk;
328}
329EXPORT_SYMBOL_GPL(__inet_lookup_established);
330
331/* called with local bh disabled */
332static int __inet_check_established(struct inet_timewait_death_row *death_row,
333				    struct sock *sk, __u16 lport,
334				    struct inet_timewait_sock **twp)
335{
336	struct inet_hashinfo *hinfo = death_row->hashinfo;
337	struct inet_sock *inet = inet_sk(sk);
338	__be32 daddr = inet->inet_rcv_saddr;
339	__be32 saddr = inet->inet_daddr;
340	int dif = sk->sk_bound_dev_if;
341	INET_ADDR_COOKIE(acookie, saddr, daddr);
342	const __portpair ports = INET_COMBINED_PORTS(inet->inet_dport, lport);
343	struct net *net = sock_net(sk);
344	unsigned int hash = inet_ehashfn(net, daddr, lport,
345					 saddr, inet->inet_dport);
346	struct inet_ehash_bucket *head = inet_ehash_bucket(hinfo, hash);
347	spinlock_t *lock = inet_ehash_lockp(hinfo, hash);
348	struct sock *sk2;
349	const struct hlist_nulls_node *node;
350	struct inet_timewait_sock *tw = NULL;
351	int twrefcnt = 0;
352
353	spin_lock(lock);
354
355	sk_nulls_for_each(sk2, node, &head->chain) {
356		if (sk2->sk_hash != hash)
357			continue;
358
359		if (likely(INET_MATCH(sk2, net, acookie,
360					 saddr, daddr, ports, dif))) {
361			if (sk2->sk_state == TCP_TIME_WAIT) {
362				tw = inet_twsk(sk2);
363				if (twsk_unique(sk, sk2, twp))
364					break;
365			}
366			goto not_unique;
367		}
368	}
369
370	/* Must record num and sport now. Otherwise we will see
371	 * in hash table socket with a funny identity.
372	 */
373	inet->inet_num = lport;
374	inet->inet_sport = htons(lport);
375	sk->sk_hash = hash;
376	WARN_ON(!sk_unhashed(sk));
377	__sk_nulls_add_node_rcu(sk, &head->chain);
378	if (tw) {
379		twrefcnt = inet_twsk_unhash(tw);
380		NET_INC_STATS_BH(net, LINUX_MIB_TIMEWAITRECYCLED);
381	}
382	spin_unlock(lock);
383	if (twrefcnt)
384		inet_twsk_put(tw);
385	sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
386
387	if (twp) {
388		*twp = tw;
389	} else if (tw) {
390		/* Silly. Should hash-dance instead... */
391		inet_twsk_deschedule(tw);
392
393		inet_twsk_put(tw);
394	}
395	return 0;
396
397not_unique:
398	spin_unlock(lock);
399	return -EADDRNOTAVAIL;
400}
401
402static inline u32 inet_sk_port_offset(const struct sock *sk)
403{
404	const struct inet_sock *inet = inet_sk(sk);
405	return secure_ipv4_port_ephemeral(inet->inet_rcv_saddr,
406					  inet->inet_daddr,
407					  inet->inet_dport);
408}
409
410int __inet_hash_nolisten(struct sock *sk, struct inet_timewait_sock *tw)
411{
412	struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
413	struct hlist_nulls_head *list;
414	struct inet_ehash_bucket *head;
415	spinlock_t *lock;
416	int twrefcnt = 0;
417
418	WARN_ON(!sk_unhashed(sk));
419
420	sk->sk_hash = sk_ehashfn(sk);
421	head = inet_ehash_bucket(hashinfo, sk->sk_hash);
422	list = &head->chain;
423	lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
424
425	spin_lock(lock);
426	__sk_nulls_add_node_rcu(sk, list);
427	if (tw) {
428		WARN_ON(sk->sk_hash != tw->tw_hash);
429		twrefcnt = inet_twsk_unhash(tw);
430	}
431	spin_unlock(lock);
432	sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
433	return twrefcnt;
434}
435EXPORT_SYMBOL_GPL(__inet_hash_nolisten);
436
437int __inet_hash(struct sock *sk, struct inet_timewait_sock *tw)
438{
439	struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
440	struct inet_listen_hashbucket *ilb;
441
442	if (sk->sk_state != TCP_LISTEN)
443		return __inet_hash_nolisten(sk, tw);
444
445	WARN_ON(!sk_unhashed(sk));
446	ilb = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)];
447
448	spin_lock(&ilb->lock);
449	__sk_nulls_add_node_rcu(sk, &ilb->head);
450	sock_prot_inuse_add(sock_net(sk), sk->sk_prot, 1);
451	spin_unlock(&ilb->lock);
452	return 0;
453}
454EXPORT_SYMBOL(__inet_hash);
455
456void inet_hash(struct sock *sk)
457{
458	if (sk->sk_state != TCP_CLOSE) {
459		local_bh_disable();
460		__inet_hash(sk, NULL);
461		local_bh_enable();
462	}
463}
464EXPORT_SYMBOL_GPL(inet_hash);
465
466void inet_unhash(struct sock *sk)
467{
468	struct inet_hashinfo *hashinfo = sk->sk_prot->h.hashinfo;
469	spinlock_t *lock;
470	int done;
471
472	if (sk_unhashed(sk))
473		return;
474
475	if (sk->sk_state == TCP_LISTEN)
476		lock = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)].lock;
477	else
478		lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
479
480	spin_lock_bh(lock);
481	done = __sk_nulls_del_node_init_rcu(sk);
482	if (done)
483		sock_prot_inuse_add(sock_net(sk), sk->sk_prot, -1);
484	spin_unlock_bh(lock);
485}
486EXPORT_SYMBOL_GPL(inet_unhash);
487
488int __inet_hash_connect(struct inet_timewait_death_row *death_row,
489		struct sock *sk, u32 port_offset,
490		int (*check_established)(struct inet_timewait_death_row *,
491			struct sock *, __u16, struct inet_timewait_sock **))
492{
493	struct inet_hashinfo *hinfo = death_row->hashinfo;
494	const unsigned short snum = inet_sk(sk)->inet_num;
495	struct inet_bind_hashbucket *head;
496	struct inet_bind_bucket *tb;
497	int ret;
498	struct net *net = sock_net(sk);
499	int twrefcnt = 1;
500
501	if (!snum) {
502		int i, remaining, low, high, port;
503		static u32 hint;
504		u32 offset = hint + port_offset;
505		struct inet_timewait_sock *tw = NULL;
506
507		inet_get_local_port_range(net, &low, &high);
508		remaining = (high - low) + 1;
509
510		local_bh_disable();
511		for (i = 1; i <= remaining; i++) {
512			port = low + (i + offset) % remaining;
513			if (inet_is_local_reserved_port(net, port))
514				continue;
515			head = &hinfo->bhash[inet_bhashfn(net, port,
516					hinfo->bhash_size)];
517			spin_lock(&head->lock);
518
519			/* Does not bother with rcv_saddr checks,
520			 * because the established check is already
521			 * unique enough.
522			 */
523			inet_bind_bucket_for_each(tb, &head->chain) {
524				if (net_eq(ib_net(tb), net) &&
525				    tb->port == port) {
526					if (tb->fastreuse >= 0 ||
527					    tb->fastreuseport >= 0)
528						goto next_port;
529					WARN_ON(hlist_empty(&tb->owners));
530					if (!check_established(death_row, sk,
531								port, &tw))
532						goto ok;
533					goto next_port;
534				}
535			}
536
537			tb = inet_bind_bucket_create(hinfo->bind_bucket_cachep,
538					net, head, port);
539			if (!tb) {
540				spin_unlock(&head->lock);
541				break;
542			}
543			tb->fastreuse = -1;
544			tb->fastreuseport = -1;
545			goto ok;
546
547		next_port:
548			spin_unlock(&head->lock);
549		}
550		local_bh_enable();
551
552		return -EADDRNOTAVAIL;
553
554ok:
555		hint += i;
556
557		/* Head lock still held and bh's disabled */
558		inet_bind_hash(sk, tb, port);
559		if (sk_unhashed(sk)) {
560			inet_sk(sk)->inet_sport = htons(port);
561			twrefcnt += __inet_hash_nolisten(sk, tw);
562		}
563		if (tw)
564			twrefcnt += inet_twsk_bind_unhash(tw, hinfo);
565		spin_unlock(&head->lock);
566
567		if (tw) {
568			inet_twsk_deschedule(tw);
569			while (twrefcnt) {
570				twrefcnt--;
571				inet_twsk_put(tw);
572			}
573		}
574
575		ret = 0;
576		goto out;
577	}
578
579	head = &hinfo->bhash[inet_bhashfn(net, snum, hinfo->bhash_size)];
580	tb  = inet_csk(sk)->icsk_bind_hash;
581	spin_lock_bh(&head->lock);
582	if (sk_head(&tb->owners) == sk && !sk->sk_bind_node.next) {
583		__inet_hash_nolisten(sk, NULL);
584		spin_unlock_bh(&head->lock);
585		return 0;
586	} else {
587		spin_unlock(&head->lock);
588		/* No definite answer... Walk to established hash table */
589		ret = check_established(death_row, sk, snum, NULL);
590out:
591		local_bh_enable();
592		return ret;
593	}
594}
595
596/*
597 * Bind a port for a connect operation and hash it.
598 */
599int inet_hash_connect(struct inet_timewait_death_row *death_row,
600		      struct sock *sk)
601{
602	return __inet_hash_connect(death_row, sk, inet_sk_port_offset(sk),
603				   __inet_check_established);
604}
605EXPORT_SYMBOL_GPL(inet_hash_connect);
606
607void inet_hashinfo_init(struct inet_hashinfo *h)
608{
609	int i;
610
611	atomic_set(&h->bsockets, 0);
612	for (i = 0; i < INET_LHTABLE_SIZE; i++) {
613		spin_lock_init(&h->listening_hash[i].lock);
614		INIT_HLIST_NULLS_HEAD(&h->listening_hash[i].head,
615				      i + LISTENING_NULLS_BASE);
616		}
617}
618EXPORT_SYMBOL_GPL(inet_hashinfo_init);
619