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