inet_hashtables.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448
  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. __acquires(hashinfo->lhash_lock)
  89. {
  90. write_lock(&hashinfo->lhash_lock);
  91. if (atomic_read(&hashinfo->lhash_users)) {
  92. DEFINE_WAIT(wait);
  93. for (;;) {
  94. prepare_to_wait_exclusive(&hashinfo->lhash_wait,
  95. &wait, TASK_UNINTERRUPTIBLE);
  96. if (!atomic_read(&hashinfo->lhash_users))
  97. break;
  98. write_unlock_bh(&hashinfo->lhash_lock);
  99. schedule();
  100. write_lock_bh(&hashinfo->lhash_lock);
  101. }
  102. finish_wait(&hashinfo->lhash_wait, &wait);
  103. }
  104. }
  105. EXPORT_SYMBOL(inet_listen_wlock);
  106. /*
  107. * Don't inline this cruft. Here are some nice properties to exploit here. The
  108. * BSD API does not allow a listening sock to specify the remote port nor the
  109. * remote address for the connection. So always assume those are both
  110. * wildcarded during the search since they can never be otherwise.
  111. */
  112. static struct sock *inet_lookup_listener_slow(const struct hlist_head *head,
  113. const __be32 daddr,
  114. const unsigned short hnum,
  115. const int dif)
  116. {
  117. struct sock *result = NULL, *sk;
  118. const struct hlist_node *node;
  119. int hiscore = -1;
  120. sk_for_each(sk, node, head) {
  121. const struct inet_sock *inet = inet_sk(sk);
  122. if (inet->num == hnum && !ipv6_only_sock(sk)) {
  123. const __be32 rcv_saddr = inet->rcv_saddr;
  124. int score = sk->sk_family == PF_INET ? 1 : 0;
  125. if (rcv_saddr) {
  126. if (rcv_saddr != daddr)
  127. continue;
  128. score += 2;
  129. }
  130. if (sk->sk_bound_dev_if) {
  131. if (sk->sk_bound_dev_if != dif)
  132. continue;
  133. score += 2;
  134. }
  135. if (score == 5)
  136. return sk;
  137. if (score > hiscore) {
  138. hiscore = score;
  139. result = sk;
  140. }
  141. }
  142. }
  143. return result;
  144. }
  145. /* Optimize the common listener case. */
  146. struct sock *__inet_lookup_listener(struct inet_hashinfo *hashinfo,
  147. const __be32 daddr, const unsigned short hnum,
  148. const int dif)
  149. {
  150. struct sock *sk = NULL;
  151. const struct hlist_head *head;
  152. read_lock(&hashinfo->lhash_lock);
  153. head = &hashinfo->listening_hash[inet_lhashfn(hnum)];
  154. if (!hlist_empty(head)) {
  155. const struct inet_sock *inet = inet_sk((sk = __sk_head(head)));
  156. if (inet->num == hnum && !sk->sk_node.next &&
  157. (!inet->rcv_saddr || inet->rcv_saddr == daddr) &&
  158. (sk->sk_family == PF_INET || !ipv6_only_sock(sk)) &&
  159. !sk->sk_bound_dev_if)
  160. goto sherry_cache;
  161. sk = inet_lookup_listener_slow(head, daddr, hnum, dif);
  162. }
  163. if (sk) {
  164. sherry_cache:
  165. sock_hold(sk);
  166. }
  167. read_unlock(&hashinfo->lhash_lock);
  168. return sk;
  169. }
  170. EXPORT_SYMBOL_GPL(__inet_lookup_listener);
  171. struct sock * __inet_lookup_established(struct inet_hashinfo *hashinfo,
  172. const __be32 saddr, const __be16 sport,
  173. const __be32 daddr, const u16 hnum,
  174. const int dif)
  175. {
  176. INET_ADDR_COOKIE(acookie, saddr, daddr)
  177. const __portpair ports = INET_COMBINED_PORTS(sport, hnum);
  178. struct sock *sk;
  179. const struct hlist_node *node;
  180. /* Optimize here for direct hit, only listening connections can
  181. * have wildcards anyways.
  182. */
  183. unsigned int hash = inet_ehashfn(daddr, hnum, saddr, sport);
  184. struct inet_ehash_bucket *head = inet_ehash_bucket(hashinfo, hash);
  185. rwlock_t *lock = inet_ehash_lockp(hashinfo, hash);
  186. prefetch(head->chain.first);
  187. read_lock(lock);
  188. sk_for_each(sk, node, &head->chain) {
  189. if (INET_MATCH(sk, hash, acookie, saddr, daddr, ports, dif))
  190. goto hit; /* You sunk my battleship! */
  191. }
  192. /* Must check for a TIME_WAIT'er before going to listener hash. */
  193. sk_for_each(sk, node, &head->twchain) {
  194. if (INET_TW_MATCH(sk, hash, acookie, saddr, daddr, ports, dif))
  195. goto hit;
  196. }
  197. sk = NULL;
  198. out:
  199. read_unlock(lock);
  200. return sk;
  201. hit:
  202. sock_hold(sk);
  203. goto out;
  204. }
  205. EXPORT_SYMBOL_GPL(__inet_lookup_established);
  206. /* called with local bh disabled */
  207. static int __inet_check_established(struct inet_timewait_death_row *death_row,
  208. struct sock *sk, __u16 lport,
  209. struct inet_timewait_sock **twp)
  210. {
  211. struct inet_hashinfo *hinfo = death_row->hashinfo;
  212. struct inet_sock *inet = inet_sk(sk);
  213. __be32 daddr = inet->rcv_saddr;
  214. __be32 saddr = inet->daddr;
  215. int dif = sk->sk_bound_dev_if;
  216. INET_ADDR_COOKIE(acookie, saddr, daddr)
  217. const __portpair ports = INET_COMBINED_PORTS(inet->dport, lport);
  218. unsigned int hash = inet_ehashfn(daddr, lport, saddr, inet->dport);
  219. struct inet_ehash_bucket *head = inet_ehash_bucket(hinfo, hash);
  220. rwlock_t *lock = inet_ehash_lockp(hinfo, hash);
  221. struct sock *sk2;
  222. const struct hlist_node *node;
  223. struct inet_timewait_sock *tw;
  224. prefetch(head->chain.first);
  225. write_lock(lock);
  226. /* Check TIME-WAIT sockets first. */
  227. sk_for_each(sk2, node, &head->twchain) {
  228. tw = inet_twsk(sk2);
  229. if (INET_TW_MATCH(sk2, hash, acookie, saddr, daddr, ports, dif)) {
  230. if (twsk_unique(sk, sk2, twp))
  231. goto unique;
  232. else
  233. goto not_unique;
  234. }
  235. }
  236. tw = NULL;
  237. /* And established part... */
  238. sk_for_each(sk2, node, &head->chain) {
  239. if (INET_MATCH(sk2, hash, acookie, saddr, daddr, ports, dif))
  240. goto not_unique;
  241. }
  242. unique:
  243. /* Must record num and sport now. Otherwise we will see
  244. * in hash table socket with a funny identity. */
  245. inet->num = lport;
  246. inet->sport = htons(lport);
  247. sk->sk_hash = hash;
  248. BUG_TRAP(sk_unhashed(sk));
  249. __sk_add_node(sk, &head->chain);
  250. sock_prot_inuse_add(sk->sk_prot, 1);
  251. write_unlock(lock);
  252. if (twp) {
  253. *twp = tw;
  254. NET_INC_STATS_BH(LINUX_MIB_TIMEWAITRECYCLED);
  255. } else if (tw) {
  256. /* Silly. Should hash-dance instead... */
  257. inet_twsk_deschedule(tw, death_row);
  258. NET_INC_STATS_BH(LINUX_MIB_TIMEWAITRECYCLED);
  259. inet_twsk_put(tw);
  260. }
  261. return 0;
  262. not_unique:
  263. write_unlock(lock);
  264. return -EADDRNOTAVAIL;
  265. }
  266. static inline u32 inet_sk_port_offset(const struct sock *sk)
  267. {
  268. const struct inet_sock *inet = inet_sk(sk);
  269. return secure_ipv4_port_ephemeral(inet->rcv_saddr, inet->daddr,
  270. inet->dport);
  271. }
  272. void __inet_hash_nolisten(struct inet_hashinfo *hashinfo, struct sock *sk)
  273. {
  274. struct hlist_head *list;
  275. rwlock_t *lock;
  276. struct inet_ehash_bucket *head;
  277. BUG_TRAP(sk_unhashed(sk));
  278. sk->sk_hash = inet_sk_ehashfn(sk);
  279. head = inet_ehash_bucket(hashinfo, sk->sk_hash);
  280. list = &head->chain;
  281. lock = inet_ehash_lockp(hashinfo, sk->sk_hash);
  282. write_lock(lock);
  283. __sk_add_node(sk, list);
  284. sock_prot_inuse_add(sk->sk_prot, 1);
  285. write_unlock(lock);
  286. }
  287. EXPORT_SYMBOL_GPL(__inet_hash_nolisten);
  288. void __inet_hash(struct inet_hashinfo *hashinfo, struct sock *sk)
  289. {
  290. struct hlist_head *list;
  291. rwlock_t *lock;
  292. if (sk->sk_state != TCP_LISTEN) {
  293. __inet_hash_nolisten(hashinfo, sk);
  294. return;
  295. }
  296. BUG_TRAP(sk_unhashed(sk));
  297. list = &hashinfo->listening_hash[inet_sk_listen_hashfn(sk)];
  298. lock = &hashinfo->lhash_lock;
  299. inet_listen_wlock(hashinfo);
  300. __sk_add_node(sk, list);
  301. sock_prot_inuse_add(sk->sk_prot, 1);
  302. write_unlock(lock);
  303. wake_up(&hashinfo->lhash_wait);
  304. }
  305. EXPORT_SYMBOL_GPL(__inet_hash);
  306. /*
  307. * Bind a port for a connect operation and hash it.
  308. */
  309. int inet_hash_connect(struct inet_timewait_death_row *death_row,
  310. struct sock *sk)
  311. {
  312. struct inet_hashinfo *hinfo = death_row->hashinfo;
  313. const unsigned short snum = inet_sk(sk)->num;
  314. struct inet_bind_hashbucket *head;
  315. struct inet_bind_bucket *tb;
  316. int ret;
  317. if (!snum) {
  318. int i, remaining, low, high, port;
  319. static u32 hint;
  320. u32 offset = hint + inet_sk_port_offset(sk);
  321. struct hlist_node *node;
  322. struct inet_timewait_sock *tw = NULL;
  323. inet_get_local_port_range(&low, &high);
  324. remaining = (high - low) + 1;
  325. local_bh_disable();
  326. for (i = 1; i <= remaining; i++) {
  327. port = low + (i + offset) % remaining;
  328. head = &hinfo->bhash[inet_bhashfn(port, hinfo->bhash_size)];
  329. spin_lock(&head->lock);
  330. /* Does not bother with rcv_saddr checks,
  331. * because the established check is already
  332. * unique enough.
  333. */
  334. inet_bind_bucket_for_each(tb, node, &head->chain) {
  335. if (tb->port == port) {
  336. BUG_TRAP(!hlist_empty(&tb->owners));
  337. if (tb->fastreuse >= 0)
  338. goto next_port;
  339. if (!__inet_check_established(death_row,
  340. sk, port,
  341. &tw))
  342. goto ok;
  343. goto next_port;
  344. }
  345. }
  346. tb = inet_bind_bucket_create(hinfo->bind_bucket_cachep, head, port);
  347. if (!tb) {
  348. spin_unlock(&head->lock);
  349. break;
  350. }
  351. tb->fastreuse = -1;
  352. goto ok;
  353. next_port:
  354. spin_unlock(&head->lock);
  355. }
  356. local_bh_enable();
  357. return -EADDRNOTAVAIL;
  358. ok:
  359. hint += i;
  360. /* Head lock still held and bh's disabled */
  361. inet_bind_hash(sk, tb, port);
  362. if (sk_unhashed(sk)) {
  363. inet_sk(sk)->sport = htons(port);
  364. __inet_hash_nolisten(hinfo, sk);
  365. }
  366. spin_unlock(&head->lock);
  367. if (tw) {
  368. inet_twsk_deschedule(tw, death_row);
  369. inet_twsk_put(tw);
  370. }
  371. ret = 0;
  372. goto out;
  373. }
  374. head = &hinfo->bhash[inet_bhashfn(snum, hinfo->bhash_size)];
  375. tb = inet_csk(sk)->icsk_bind_hash;
  376. spin_lock_bh(&head->lock);
  377. if (sk_head(&tb->owners) == sk && !sk->sk_bind_node.next) {
  378. __inet_hash_nolisten(hinfo, sk);
  379. spin_unlock_bh(&head->lock);
  380. return 0;
  381. } else {
  382. spin_unlock(&head->lock);
  383. /* No definite answer... Walk to established hash table */
  384. ret = __inet_check_established(death_row, sk, snum, NULL);
  385. out:
  386. local_bh_enable();
  387. return ret;
  388. }
  389. }
  390. EXPORT_SYMBOL_GPL(inet_hash_connect);