inet_hashtables.c 15 KB

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