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