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