inet_hashtables.c 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367
  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/ip.h>
  23. /*
  24. * Allocate and initialize a new local port bind bucket.
  25. * The bindhash mutex for snum's hash chain must be held here.
  26. */
  27. struct inet_bind_bucket *inet_bind_bucket_create(struct kmem_cache *cachep,
  28. struct inet_bind_hashbucket *head,
  29. const unsigned short snum)
  30. {
  31. struct inet_bind_bucket *tb = kmem_cache_alloc(cachep, GFP_ATOMIC);
  32. if (tb != NULL) {
  33. tb->port = snum;
  34. tb->fastreuse = 0;
  35. INIT_HLIST_HEAD(&tb->owners);
  36. hlist_add_head(&tb->node, &head->chain);
  37. }
  38. return tb;
  39. }
  40. /*
  41. * Caller must hold hashbucket lock for this tb with local BH disabled
  42. */
  43. void inet_bind_bucket_destroy(struct kmem_cache *cachep, struct inet_bind_bucket *tb)
  44. {
  45. if (hlist_empty(&tb->owners)) {
  46. __hlist_del(&tb->node);
  47. kmem_cache_free(cachep, tb);
  48. }
  49. }
  50. void inet_bind_hash(struct sock *sk, struct inet_bind_bucket *tb,
  51. const unsigned short snum)
  52. {
  53. inet_sk(sk)->num = snum;
  54. sk_add_bind_node(sk, &tb->owners);
  55. inet_csk(sk)->icsk_bind_hash = tb;
  56. }
  57. /*
  58. * Get rid of any references to a local port held by the given sock.
  59. */
  60. static void __inet_put_port(struct inet_hashinfo *hashinfo, struct sock *sk)
  61. {
  62. const int bhash = inet_bhashfn(inet_sk(sk)->num, hashinfo->bhash_size);
  63. struct inet_bind_hashbucket *head = &hashinfo->bhash[bhash];
  64. struct inet_bind_bucket *tb;
  65. spin_lock(&head->lock);
  66. tb = inet_csk(sk)->icsk_bind_hash;
  67. __sk_del_bind_node(sk);
  68. inet_csk(sk)->icsk_bind_hash = NULL;
  69. inet_sk(sk)->num = 0;
  70. inet_bind_bucket_destroy(hashinfo->bind_bucket_cachep, tb);
  71. spin_unlock(&head->lock);
  72. }
  73. void inet_put_port(struct inet_hashinfo *hashinfo, struct sock *sk)
  74. {
  75. local_bh_disable();
  76. __inet_put_port(hashinfo, sk);
  77. local_bh_enable();
  78. }
  79. EXPORT_SYMBOL(inet_put_port);
  80. /*
  81. * This lock without WQ_FLAG_EXCLUSIVE is good on UP and it can be very bad on SMP.
  82. * Look, when several writers sleep and reader wakes them up, all but one
  83. * immediately hit write lock and grab all the cpus. Exclusive sleep solves
  84. * this, _but_ remember, it adds useless work on UP machines (wake up each
  85. * exclusive lock release). It should be ifdefed really.
  86. */
  87. void inet_listen_wlock(struct inet_hashinfo *hashinfo)
  88. {
  89. write_lock(&hashinfo->lhash_lock);
  90. if (atomic_read(&hashinfo->lhash_users)) {
  91. DEFINE_WAIT(wait);
  92. for (;;) {
  93. prepare_to_wait_exclusive(&hashinfo->lhash_wait,
  94. &wait, TASK_UNINTERRUPTIBLE);
  95. if (!atomic_read(&hashinfo->lhash_users))
  96. break;
  97. write_unlock_bh(&hashinfo->lhash_lock);
  98. schedule();
  99. write_lock_bh(&hashinfo->lhash_lock);
  100. }
  101. finish_wait(&hashinfo->lhash_wait, &wait);
  102. }
  103. }
  104. EXPORT_SYMBOL(inet_listen_wlock);
  105. /*
  106. * Don't inline this cruft. Here are some nice properties to exploit here. The
  107. * BSD API does not allow a listening sock to specify the remote port nor the
  108. * remote address for the connection. So always assume those are both
  109. * wildcarded during the search since they can never be otherwise.
  110. */
  111. static struct sock *inet_lookup_listener_slow(const struct hlist_head *head,
  112. const __be32 daddr,
  113. const unsigned short hnum,
  114. const int dif)
  115. {
  116. struct sock *result = NULL, *sk;
  117. const struct hlist_node *node;
  118. int hiscore = -1;
  119. sk_for_each(sk, node, head) {
  120. const struct inet_sock *inet = inet_sk(sk);
  121. if (inet->num == hnum && !ipv6_only_sock(sk)) {
  122. const __be32 rcv_saddr = inet->rcv_saddr;
  123. int score = sk->sk_family == PF_INET ? 1 : 0;
  124. if (rcv_saddr) {
  125. if (rcv_saddr != daddr)
  126. continue;
  127. score += 2;
  128. }
  129. if (sk->sk_bound_dev_if) {
  130. if (sk->sk_bound_dev_if != dif)
  131. continue;
  132. score += 2;
  133. }
  134. if (score == 5)
  135. return sk;
  136. if (score > hiscore) {
  137. hiscore = score;
  138. result = sk;
  139. }
  140. }
  141. }
  142. return result;
  143. }
  144. /* Optimize the common listener case. */
  145. struct sock *__inet_lookup_listener(struct inet_hashinfo *hashinfo,
  146. const __be32 daddr, const unsigned short hnum,
  147. const int dif)
  148. {
  149. struct sock *sk = NULL;
  150. const struct hlist_head *head;
  151. read_lock(&hashinfo->lhash_lock);
  152. head = &hashinfo->listening_hash[inet_lhashfn(hnum)];
  153. if (!hlist_empty(head)) {
  154. const struct inet_sock *inet = inet_sk((sk = __sk_head(head)));
  155. if (inet->num == hnum && !sk->sk_node.next &&
  156. (!inet->rcv_saddr || inet->rcv_saddr == daddr) &&
  157. (sk->sk_family == PF_INET || !ipv6_only_sock(sk)) &&
  158. !sk->sk_bound_dev_if)
  159. goto sherry_cache;
  160. sk = inet_lookup_listener_slow(head, daddr, hnum, dif);
  161. }
  162. if (sk) {
  163. sherry_cache:
  164. sock_hold(sk);
  165. }
  166. read_unlock(&hashinfo->lhash_lock);
  167. return sk;
  168. }
  169. EXPORT_SYMBOL_GPL(__inet_lookup_listener);
  170. /* called with local bh disabled */
  171. static int __inet_check_established(struct inet_timewait_death_row *death_row,
  172. struct sock *sk, __u16 lport,
  173. struct inet_timewait_sock **twp)
  174. {
  175. struct inet_hashinfo *hinfo = death_row->hashinfo;
  176. struct inet_sock *inet = inet_sk(sk);
  177. __be32 daddr = inet->rcv_saddr;
  178. __be32 saddr = inet->daddr;
  179. int dif = sk->sk_bound_dev_if;
  180. INET_ADDR_COOKIE(acookie, saddr, daddr)
  181. const __portpair ports = INET_COMBINED_PORTS(inet->dport, lport);
  182. unsigned int hash = inet_ehashfn(daddr, lport, saddr, inet->dport);
  183. struct inet_ehash_bucket *head = inet_ehash_bucket(hinfo, hash);
  184. struct sock *sk2;
  185. const struct hlist_node *node;
  186. struct inet_timewait_sock *tw;
  187. prefetch(head->chain.first);
  188. write_lock(&head->lock);
  189. /* Check TIME-WAIT sockets first. */
  190. sk_for_each(sk2, node, &head->twchain) {
  191. tw = inet_twsk(sk2);
  192. if (INET_TW_MATCH(sk2, hash, acookie, saddr, daddr, ports, dif)) {
  193. if (twsk_unique(sk, sk2, twp))
  194. goto unique;
  195. else
  196. goto not_unique;
  197. }
  198. }
  199. tw = NULL;
  200. /* And established part... */
  201. sk_for_each(sk2, node, &head->chain) {
  202. if (INET_MATCH(sk2, hash, acookie, saddr, daddr, ports, dif))
  203. goto not_unique;
  204. }
  205. unique:
  206. /* Must record num and sport now. Otherwise we will see
  207. * in hash table socket with a funny identity. */
  208. inet->num = lport;
  209. inet->sport = htons(lport);
  210. sk->sk_hash = hash;
  211. BUG_TRAP(sk_unhashed(sk));
  212. __sk_add_node(sk, &head->chain);
  213. sock_prot_inc_use(sk->sk_prot);
  214. write_unlock(&head->lock);
  215. if (twp) {
  216. *twp = tw;
  217. NET_INC_STATS_BH(LINUX_MIB_TIMEWAITRECYCLED);
  218. } else if (tw) {
  219. /* Silly. Should hash-dance instead... */
  220. inet_twsk_deschedule(tw, death_row);
  221. NET_INC_STATS_BH(LINUX_MIB_TIMEWAITRECYCLED);
  222. inet_twsk_put(tw);
  223. }
  224. return 0;
  225. not_unique:
  226. write_unlock(&head->lock);
  227. return -EADDRNOTAVAIL;
  228. }
  229. static inline u32 inet_sk_port_offset(const struct sock *sk)
  230. {
  231. const struct inet_sock *inet = inet_sk(sk);
  232. return secure_ipv4_port_ephemeral(inet->rcv_saddr, inet->daddr,
  233. inet->dport);
  234. }
  235. /*
  236. * Bind a port for a connect operation and hash it.
  237. */
  238. int inet_hash_connect(struct inet_timewait_death_row *death_row,
  239. struct sock *sk)
  240. {
  241. struct inet_hashinfo *hinfo = death_row->hashinfo;
  242. const unsigned short snum = inet_sk(sk)->num;
  243. struct inet_bind_hashbucket *head;
  244. struct inet_bind_bucket *tb;
  245. int ret;
  246. if (!snum) {
  247. int low = sysctl_local_port_range[0];
  248. int high = sysctl_local_port_range[1];
  249. int range = high - low;
  250. int i;
  251. int port;
  252. static u32 hint;
  253. u32 offset = hint + inet_sk_port_offset(sk);
  254. struct hlist_node *node;
  255. struct inet_timewait_sock *tw = NULL;
  256. local_bh_disable();
  257. for (i = 1; i <= range; i++) {
  258. port = low + (i + offset) % range;
  259. head = &hinfo->bhash[inet_bhashfn(port, hinfo->bhash_size)];
  260. spin_lock(&head->lock);
  261. /* Does not bother with rcv_saddr checks,
  262. * because the established check is already
  263. * unique enough.
  264. */
  265. inet_bind_bucket_for_each(tb, node, &head->chain) {
  266. if (tb->port == port) {
  267. BUG_TRAP(!hlist_empty(&tb->owners));
  268. if (tb->fastreuse >= 0)
  269. goto next_port;
  270. if (!__inet_check_established(death_row,
  271. sk, port,
  272. &tw))
  273. goto ok;
  274. goto next_port;
  275. }
  276. }
  277. tb = inet_bind_bucket_create(hinfo->bind_bucket_cachep, head, port);
  278. if (!tb) {
  279. spin_unlock(&head->lock);
  280. break;
  281. }
  282. tb->fastreuse = -1;
  283. goto ok;
  284. next_port:
  285. spin_unlock(&head->lock);
  286. }
  287. local_bh_enable();
  288. return -EADDRNOTAVAIL;
  289. ok:
  290. hint += i;
  291. /* Head lock still held and bh's disabled */
  292. inet_bind_hash(sk, tb, port);
  293. if (sk_unhashed(sk)) {
  294. inet_sk(sk)->sport = htons(port);
  295. __inet_hash(hinfo, sk, 0);
  296. }
  297. spin_unlock(&head->lock);
  298. if (tw) {
  299. inet_twsk_deschedule(tw, death_row);
  300. inet_twsk_put(tw);
  301. }
  302. ret = 0;
  303. goto out;
  304. }
  305. head = &hinfo->bhash[inet_bhashfn(snum, hinfo->bhash_size)];
  306. tb = inet_csk(sk)->icsk_bind_hash;
  307. spin_lock_bh(&head->lock);
  308. if (sk_head(&tb->owners) == sk && !sk->sk_bind_node.next) {
  309. __inet_hash(hinfo, sk, 0);
  310. spin_unlock_bh(&head->lock);
  311. return 0;
  312. } else {
  313. spin_unlock(&head->lock);
  314. /* No definite answer... Walk to established hash table */
  315. ret = __inet_check_established(death_row, sk, snum, NULL);
  316. out:
  317. local_bh_enable();
  318. return ret;
  319. }
  320. }
  321. EXPORT_SYMBOL_GPL(inet_hash_connect);