net/ipv4/tcp_minisocks.c

   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  *              Implementation of the Transmission Control Protocol(TCP).
   7  *
   8  * Version:     $Id: tcp_minisocks.c,v 1.15 2002/02/01 22:01:04 davem Exp $
   9  *
  10  * Authors:     Ross Biro, <bir7@leland.Stanford.Edu>
  11  *              Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG>
  12  *              Mark Evans, <evansmp@uhura.aston.ac.uk>
  13  *              Corey Minyard <wf-rch!minyard@relay.EU.net>
  14  *              Florian La Roche, <flla@stud.uni-sb.de>
  15  *              Charles Hedrick, <hedrick@klinzhai.rutgers.edu>
  16  *              Linus Torvalds, <torvalds@cs.helsinki.fi>
  17  *              Alan Cox, <gw4pts@gw4pts.ampr.org>
  18  *              Matthew Dillon, <dillon@apollo.west.oic.com>
  19  *              Arnt Gulbrandsen, <agulbra@nvg.unit.no>
  20  *              Jorge Cwik, <jorge@laser.satlink.net>
  21  */
  22
  23 #include <linux/config.h>
  24 #include <linux/mm.h>
  25 #include <linux/module.h>
  26 #include <linux/sysctl.h>
  27 #include <linux/workqueue.h>
  28 #include <net/tcp.h>
  29 #include <net/inet_common.h>
  30 #include <net/xfrm.h>
  31
  32 #ifdef CONFIG_SYSCTL
  33 #define SYNC_INIT 0 /* let the user enable it */
  34 #else
  35 #define SYNC_INIT 1
  36 #endif
  37
  38 int sysctl_tcp_tw_recycle;
  39 int sysctl_tcp_max_tw_buckets = NR_FILE*2;
  40
  41 int sysctl_tcp_syncookies = SYNC_INIT;
  42 int sysctl_tcp_abort_on_overflow;
  43
  44 static __inline__ int tcp_in_window(u32 seq, u32 end_seq, u32 s_win, u32 e_win)
  45 {
  46         if (seq == s_win)
  47                 return 1;
  48         if (after(end_seq, s_win) && before(seq, e_win))
  49                 return 1;
  50         return (seq == e_win && seq == end_seq);
  51 }
  52
  53 /* New-style handling of TIME_WAIT sockets. */
  54
  55 int tcp_tw_count;
  56
  57
  58 /* Must be called with locally disabled BHs. */
  59 static void tcp_timewait_kill(struct tcp_tw_bucket *tw)
  60 {
  61         struct tcp_ehash_bucket *ehead;
  62         struct tcp_bind_hashbucket *bhead;
  63         struct tcp_bind_bucket *tb;
  64
  65         /* Unlink from established hashes. */
  66         ehead = &tcp_ehash[tw->tw_hashent];
  67         write_lock(&ehead->lock);
  68         if (hlist_unhashed(&tw->tw_node)) {
  69                 write_unlock(&ehead->lock);
  70                 return;
  71         }
  72         __hlist_del(&tw->tw_node);
  73         sk_node_init(&tw->tw_node);
  74         write_unlock(&ehead->lock);
  75
  76         /* Disassociate with bind bucket. */
  77         bhead = &tcp_bhash[tcp_bhashfn(tw->tw_num)];
  78         spin_lock(&bhead->lock);
  79         tb = tw->tw_tb;
  80         __hlist_del(&tw->tw_bind_node);
  81         tw->tw_tb = NULL;
  82         tcp_bucket_destroy(tb);
  83         spin_unlock(&bhead->lock);
  84
  85 #ifdef INET_REFCNT_DEBUG
  86         if (atomic_read(&tw->tw_refcnt) != 1) {
  87                 printk(KERN_DEBUG "tw_bucket %p refcnt=%d\n", tw,
  88                        atomic_read(&tw->tw_refcnt));
  89         }
  90 #endif
  91         tcp_tw_put(tw);
  92 }
  93
  94 /*
  95  * * Main purpose of TIME-WAIT state is to close connection gracefully,
  96  *   when one of ends sits in LAST-ACK or CLOSING retransmitting FIN
  97  *   (and, probably, tail of data) and one or more our ACKs are lost.
  98  * * What is TIME-WAIT timeout? It is associated with maximal packet
  99  *   lifetime in the internet, which results in wrong conclusion, that
 100  *   it is set to catch "old duplicate segments" wandering out of their path.
 101  *   It is not quite correct. This timeout is calculated so that it exceeds
 102  *   maximal retransmission timeout enough to allow to lose one (or more)
 103  *   segments sent by peer and our ACKs. This time may be calculated from RTO.
 104  * * When TIME-WAIT socket receives RST, it means that another end
 105  *   finally closed and we are allowed to kill TIME-WAIT too.
 106  * * Second purpose of TIME-WAIT is catching old duplicate segments.
 107  *   Well, certainly it is pure paranoia, but if we load TIME-WAIT
 108  *   with this semantics, we MUST NOT kill TIME-WAIT state with RSTs.
 109  * * If we invented some more clever way to catch duplicates
 110  *   (f.e. based on PAWS), we could truncate TIME-WAIT to several RTOs.
 111  *
 112  * The algorithm below is based on FORMAL INTERPRETATION of RFCs.
 113  * When you compare it to RFCs, please, read section SEGMENT ARRIVES
 114  * from the very beginning.
 115  *
 116  * NOTE. With recycling (and later with fin-wait-2) TW bucket
 117  * is _not_ stateless. It means, that strictly speaking we must
 118  * spinlock it. I do not want! Well, probability of misbehaviour
 119  * is ridiculously low and, seems, we could use some mb() tricks
 120  * to avoid misread sequence numbers, states etc.  --ANK
 121  */
 122 enum tcp_tw_status
 123 tcp_timewait_state_process(struct tcp_tw_bucket *tw, struct sk_buff *skb,
 124                            struct tcphdr *th, unsigned len)
 125 {
 126         struct tcp_opt tp;
 127         int paws_reject = 0;
 128
 129         tp.saw_tstamp = 0;
 130         if (th->doff > (sizeof(struct tcphdr) >> 2) && tw->tw_ts_recent_stamp) {
 131                 tcp_parse_options(skb, &tp, 0);
 132
 133                 if (tp.saw_tstamp) {
 134                         tp.ts_recent       = tw->tw_ts_recent;
 135                         tp.ts_recent_stamp = tw->tw_ts_recent_stamp;
 136                         paws_reject = tcp_paws_check(&tp, th->rst);
 137                 }
 138         }
 139
 140         if (tw->tw_substate == TCP_FIN_WAIT2) {
 141                 /* Just repeat all the checks of tcp_rcv_state_process() */
 142
 143                 /* Out of window, send ACK */
 144                 if (paws_reject ||
 145                     !tcp_in_window(TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq,
 146                                    tw->tw_rcv_nxt,
 147                                    tw->tw_rcv_nxt + tw->tw_rcv_wnd))
 148                         return TCP_TW_ACK;
 149
 150                 if (th->rst)
 151                         goto kill;
 152
 153                 if (th->syn && !before(TCP_SKB_CB(skb)->seq, tw->tw_rcv_nxt))
 154                         goto kill_with_rst;
 155
 156                 /* Dup ACK? */
 157                 if (!after(TCP_SKB_CB(skb)->end_seq, tw->tw_rcv_nxt) ||
 158                     TCP_SKB_CB(skb)->end_seq == TCP_SKB_CB(skb)->seq) {
 159                         tcp_tw_put(tw);
 160                         return TCP_TW_SUCCESS;
 161                 }
 162
 163                 /* New data or FIN. If new data arrive after half-duplex close,
 164                  * reset.
 165                  */
 166                 if (!th->fin ||
 167                     TCP_SKB_CB(skb)->end_seq != tw->tw_rcv_nxt + 1) {
 168 kill_with_rst:
 169                         tcp_tw_deschedule(tw);
 170                         tcp_tw_put(tw);
 171                         return TCP_TW_RST;
 172                 }
 173
 174                 /* FIN arrived, enter true time-wait state. */
 175                 tw->tw_substate = TCP_TIME_WAIT;
 176                 tw->tw_rcv_nxt  = TCP_SKB_CB(skb)->end_seq;
 177                 if (tp.saw_tstamp) {
 178                         tw->tw_ts_recent_stamp  = xtime.tv_sec;
 179                         tw->tw_ts_recent        = tp.rcv_tsval;
 180                 }
 181
 182                 /* I am shamed, but failed to make it more elegant.
 183                  * Yes, it is direct reference to IP, which is impossible
 184                  * to generalize to IPv6. Taking into account that IPv6
 185                  * do not undertsnad recycling in any case, it not
 186                  * a big problem in practice. --ANK */
 187                 if (tw->tw_family == AF_INET &&
 188                     sysctl_tcp_tw_recycle && tw->tw_ts_recent_stamp &&
 189                     tcp_v4_tw_remember_stamp(tw))
 190                         tcp_tw_schedule(tw, tw->tw_timeout);
 191                 else
 192                         tcp_tw_schedule(tw, TCP_TIMEWAIT_LEN);
 193                 return TCP_TW_ACK;
 194         }
 195
 196         /*
 197          *      Now real TIME-WAIT state.
 198          *
 199          *      RFC 1122:
 200          *      "When a connection is [...] on TIME-WAIT state [...]
 201          *      [a TCP] MAY accept a new SYN from the remote TCP to
 202          *      reopen the connection directly, if it:
 203          *
 204          *      (1)  assigns its initial sequence number for the new
 205          *      connection to be larger than the largest sequence
 206          *      number it used on the previous connection incarnation,
 207          *      and
 208          *
 209          *      (2)  returns to TIME-WAIT state if the SYN turns out
 210          *      to be an old duplicate".
 211          */
 212
 213         if (!paws_reject &&
 214             (TCP_SKB_CB(skb)->seq == tw->tw_rcv_nxt &&
 215              (TCP_SKB_CB(skb)->seq == TCP_SKB_CB(skb)->end_seq || th->rst))) {
 216                 /* In window segment, it may be only reset or bare ack. */
 217
 218                 if (th->rst) {
 219                         /* This is TIME_WAIT assasination, in two flavors.
 220                          * Oh well... nobody has a sufficient solution to this
 221                          * protocol bug yet.
 222                          */
 223                         if (sysctl_tcp_rfc1337 == 0) {
 224 kill:
 225                                 tcp_tw_deschedule(tw);
 226                                 tcp_tw_put(tw);
 227                                 return TCP_TW_SUCCESS;
 228                         }
 229                 }
 230                 tcp_tw_schedule(tw, TCP_TIMEWAIT_LEN);
 231
 232                 if (tp.saw_tstamp) {
 233                         tw->tw_ts_recent        = tp.rcv_tsval;
 234                         tw->tw_ts_recent_stamp  = xtime.tv_sec;
 235                 }
 236
 237                 tcp_tw_put(tw);
 238                 return TCP_TW_SUCCESS;
 239         }
 240
 241         /* Out of window segment.
 242
 243            All the segments are ACKed immediately.
 244
 245            The only exception is new SYN. We accept it, if it is
 246            not old duplicate and we are not in danger to be killed
 247            by delayed old duplicates. RFC check is that it has
 248            newer sequence number works at rates <40Mbit/sec.
 249            However, if paws works, it is reliable AND even more,
 250            we even may relax silly seq space cutoff.
 251
 252            RED-PEN: we violate main RFC requirement, if this SYN will appear
 253            old duplicate (i.e. we receive RST in reply to SYN-ACK),
 254            we must return socket to time-wait state. It is not good,
 255            but not fatal yet.
 256          */
 257
 258         if (th->syn && !th->rst && !th->ack && !paws_reject &&
 259             (after(TCP_SKB_CB(skb)->seq, tw->tw_rcv_nxt) ||
 260              (tp.saw_tstamp && (s32)(tw->tw_ts_recent - tp.rcv_tsval) < 0))) {
 261                 u32 isn = tw->tw_snd_nxt + 65535 + 2;
 262                 if (isn == 0)
 263                         isn++;
 264                 TCP_SKB_CB(skb)->when = isn;
 265                 return TCP_TW_SYN;
 266         }
 267
 268         if (paws_reject)
 269                 NET_INC_STATS_BH(PAWSEstabRejected);
 270
 271         if(!th->rst) {
 272                 /* In this case we must reset the TIMEWAIT timer.
 273                  *
 274                  * If it is ACKless SYN it may be both old duplicate
 275                  * and new good SYN with random sequence number <rcv_nxt.
 276                  * Do not reschedule in the last case.
 277                  */
 278                 if (paws_reject || th->ack)
 279                         tcp_tw_schedule(tw, TCP_TIMEWAIT_LEN);
 280
 281                 /* Send ACK. Note, we do not put the bucket,
 282                  * it will be released by caller.
 283                  */
 284                 return TCP_TW_ACK;
 285         }
 286         tcp_tw_put(tw);
 287         return TCP_TW_SUCCESS;
 288 }
 289
 290 /* Enter the time wait state.  This is called with locally disabled BH.
 291  * Essentially we whip up a timewait bucket, copy the
 292  * relevant info into it from the SK, and mess with hash chains
 293  * and list linkage.
 294  */
 295 static void __tcp_tw_hashdance(struct sock *sk, struct tcp_tw_bucket *tw)
 296 {
 297         struct tcp_ehash_bucket *ehead = &tcp_ehash[sk->sk_hashent];
 298         struct tcp_bind_hashbucket *bhead;
 299
 300         /* Step 1: Put TW into bind hash. Original socket stays there too.
 301            Note, that any socket with inet_sk(sk)->num != 0 MUST be bound in
 302            binding cache, even if it is closed.
 303          */
 304         bhead = &tcp_bhash[tcp_bhashfn(inet_sk(sk)->num)];
 305         spin_lock(&bhead->lock);
 306         tw->tw_tb = tcp_sk(sk)->bind_hash;
 307         BUG_TRAP(tcp_sk(sk)->bind_hash);
 308         tw_add_bind_node(tw, &tw->tw_tb->owners);
 309         spin_unlock(&bhead->lock);
 310
 311         write_lock(&ehead->lock);
 312
 313         /* Step 2: Remove SK from established hash. */
 314         if (__sk_del_node_init(sk))
 315                 sock_prot_dec_use(sk->sk_prot);
 316
 317         /* Step 3: Hash TW into TIMEWAIT half of established hash table. */
 318         tw_add_node(tw, &(ehead + tcp_ehash_size)->chain);
 319         atomic_inc(&tw->tw_refcnt);
 320
 321         write_unlock(&ehead->lock);
 322 }
 323
 324 /*
 325  * Move a socket to time-wait or dead fin-wait-2 state.
 326  */
 327 void tcp_time_wait(struct sock *sk, int state, int timeo)
 328 {
 329         struct tcp_tw_bucket *tw = NULL;
 330         struct tcp_opt *tp = tcp_sk(sk);
 331         int recycle_ok = 0;
 332
 333         if (sysctl_tcp_tw_recycle && tp->ts_recent_stamp)
 334                 recycle_ok = tp->af_specific->remember_stamp(sk);
 335
 336         if (tcp_tw_count < sysctl_tcp_max_tw_buckets)
 337                 tw = kmem_cache_alloc(tcp_timewait_cachep, SLAB_ATOMIC);
 338
 339         if(tw != NULL) {
 340                 struct inet_opt *inet = inet_sk(sk);
 341                 int rto = (tp->rto<<2) - (tp->rto>>1);
 342
 343                 /* Give us an identity. */
 344                 tw->tw_daddr            = inet->daddr;
 345                 tw->tw_rcv_saddr        = inet->rcv_saddr;
 346                 tw->tw_bound_dev_if     = sk->sk_bound_dev_if;
 347                 tw->tw_num              = inet->num;
 348                 tw->tw_state            = TCP_TIME_WAIT;
 349                 tw->tw_substate         = state;
 350                 tw->tw_sport            = inet->sport;
 351                 tw->tw_dport            = inet->dport;
 352                 tw->tw_family           = sk->sk_family;
 353                 tw->tw_reuse            = sk->sk_reuse;
 354                 tw->tw_rcv_wscale       = tp->rcv_wscale;
 355                 atomic_set(&tw->tw_refcnt, 1);
 356
 357                 tw->tw_hashent          = sk->sk_hashent;
 358                 tw->tw_rcv_nxt          = tp->rcv_nxt;
 359                 tw->tw_snd_nxt          = tp->snd_nxt;
 360                 tw->tw_rcv_wnd          = tcp_receive_window(tp);
 361                 tw->tw_ts_recent        = tp->ts_recent;
 362                 tw->tw_ts_recent_stamp  = tp->ts_recent_stamp;
 363                 tw_dead_node_init(tw);
 364
 365 #if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
 366                 if (tw->tw_family == PF_INET6) {
 367                         struct ipv6_pinfo *np = inet6_sk(sk);
 368
 369                         ipv6_addr_copy(&tw->tw_v6_daddr, &np->daddr);
 370                         ipv6_addr_copy(&tw->tw_v6_rcv_saddr, &np->rcv_saddr);
 371                         tw->tw_v6_ipv6only = np->ipv6only;
 372                 } else {
 373                         memset(&tw->tw_v6_daddr, 0, sizeof(tw->tw_v6_daddr));
 374                         memset(&tw->tw_v6_rcv_saddr, 0, sizeof(tw->tw_v6_rcv_saddr));
 375                         tw->tw_v6_ipv6only = 0;
 376                 }
 377 #endif
 378                 /* Linkage updates. */
 379                 __tcp_tw_hashdance(sk, tw);
 380
 381                 /* Get the TIME_WAIT timeout firing. */
 382                 if (timeo < rto)
 383                         timeo = rto;
 384
 385                 if (recycle_ok) {
 386                         tw->tw_timeout = rto;
 387                 } else {
 388                         tw->tw_timeout = TCP_TIMEWAIT_LEN;
 389                         if (state == TCP_TIME_WAIT)
 390                                 timeo = TCP_TIMEWAIT_LEN;
 391                 }
 392
 393                 tcp_tw_schedule(tw, timeo);
 394                 tcp_tw_put(tw);
 395         } else {
 396                 /* Sorry, if we're out of memory, just CLOSE this
 397                  * socket up.  We've got bigger problems than
 398                  * non-graceful socket closings.
 399                  */
 400                 if (net_ratelimit())
 401                         printk(KERN_INFO "TCP: time wait bucket table overflow\n");
 402         }
 403
 404         tcp_update_metrics(sk);
 405         tcp_done(sk);
 406 }
 407
 408 /* Kill off TIME_WAIT sockets once their lifetime has expired. */
 409 static int tcp_tw_death_row_slot;
 410
 411 static void tcp_twkill(unsigned long);
 412
 413 /* TIME_WAIT reaping mechanism. */
 414 #define TCP_TWKILL_SLOTS        8       /* Please keep this a power of 2. */
 415 #define TCP_TWKILL_PERIOD       (TCP_TIMEWAIT_LEN/TCP_TWKILL_SLOTS)
 416
 417 #define TCP_TWKILL_QUOTA        100
 418
 419 static struct hlist_head tcp_tw_death_row[TCP_TWKILL_SLOTS];
 420 static spinlock_t tw_death_lock = SPIN_LOCK_UNLOCKED;
 421 static struct timer_list tcp_tw_timer = TIMER_INITIALIZER(tcp_twkill, 0, 0);
 422 static void twkill_work(void *);
 423 static DECLARE_WORK(tcp_twkill_work, twkill_work, NULL);
 424 static u32 twkill_thread_slots;
 425
 426 /* Returns non-zero if quota exceeded.  */
 427 static int tcp_do_twkill_work(int slot, unsigned int quota)
 428 {
 429         struct tcp_tw_bucket *tw;
 430         struct hlist_node *node;
 431         unsigned int killed;
 432         int ret;
 433
 434         /* NOTE: compare this to previous version where lock
 435          * was released after detaching chain. It was racy,
 436          * because tw buckets are scheduled in not serialized context
 437          * in 2.3 (with netfilter), and with softnet it is common, because
 438          * soft irqs are not sequenced.
 439          */
 440         killed = 0;
 441         ret = 0;
 442 rescan:
 443         tw_for_each_inmate(tw, node, &tcp_tw_death_row[slot]) {
 444                 __tw_del_dead_node(tw);
 445                 spin_unlock(&tw_death_lock);
 446                 tcp_timewait_kill(tw);
 447                 tcp_tw_put(tw);
 448                 killed++;
 449                 spin_lock(&tw_death_lock);
 450                 if (killed > quota) {
 451                         ret = 1;
 452                         break;
 453                 }
 454
 455                 /* While we dropped tw_death_lock, another cpu may have
 456                  * killed off the next TW bucket in the list, therefore
 457                  * do a fresh re-read of the hlist head node with the
 458                  * lock reacquired.  We still use the hlist traversal
 459                  * macro in order to get the prefetches.
 460                  */
 461                 goto rescan;
 462         }
 463
 464         tcp_tw_count -= killed;
 465         NET_ADD_STATS_BH(TimeWaited, killed);
 466
 467         return ret;
 468 }
 469
 470 static void tcp_twkill(unsigned long dummy)
 471 {
 472         int need_timer, ret;
 473
 474         spin_lock(&tw_death_lock);
 475
 476         if (tcp_tw_count == 0)
 477                 goto out;
 478
 479         need_timer = 0;
 480         ret = tcp_do_twkill_work(tcp_tw_death_row_slot, TCP_TWKILL_QUOTA);
 481         if (ret) {
 482                 twkill_thread_slots |= (1 << tcp_tw_death_row_slot);
 483                 mb();
 484                 schedule_work(&tcp_twkill_work);
 485                 need_timer = 1;
 486         } else {
 487                 /* We purged the entire slot, anything left?  */
 488                 if (tcp_tw_count)
 489                         need_timer = 1;
 490         }
 491         tcp_tw_death_row_slot =
 492                 ((tcp_tw_death_row_slot + 1) & (TCP_TWKILL_SLOTS - 1));
 493         if (need_timer)
 494                 mod_timer(&tcp_tw_timer, jiffies + TCP_TWKILL_PERIOD);
 495 out:
 496         spin_unlock(&tw_death_lock);
 497 }
 498
 499 extern void twkill_slots_invalid(void);
 500
 501 static void twkill_work(void *dummy)
 502 {
 503         int i;
 504
 505         if ((TCP_TWKILL_SLOTS - 1) > (sizeof(twkill_thread_slots) * 8))
 506                 twkill_slots_invalid();
 507
 508         while (twkill_thread_slots) {
 509                 spin_lock_bh(&tw_death_lock);
 510                 for (i = 0; i < TCP_TWKILL_SLOTS; i++) {
 511                         if (!(twkill_thread_slots & (1 << i)))
 512                                 continue;
 513
 514                         while (tcp_do_twkill_work(i, TCP_TWKILL_QUOTA) != 0) {
 515                                 if (need_resched()) {
 516                                         spin_unlock_bh(&tw_death_lock);
 517                                         schedule();
 518                                         spin_lock_bh(&tw_death_lock);
 519                                 }
 520                         }
 521
 522                         twkill_thread_slots &= ~(1 << i);
 523                 }
 524                 spin_unlock_bh(&tw_death_lock);
 525         }
 526 }
 527
 528 /* These are always called from BH context.  See callers in
 529  * tcp_input.c to verify this.
 530  */
 531
 532 /* This is for handling early-kills of TIME_WAIT sockets. */
 533 void tcp_tw_deschedule(struct tcp_tw_bucket *tw)
 534 {
 535         spin_lock(&tw_death_lock);
 536         if (tw_del_dead_node(tw)) {
 537                 tcp_tw_put(tw);
 538                 if (--tcp_tw_count == 0)
 539                         del_timer(&tcp_tw_timer);
 540         }
 541         spin_unlock(&tw_death_lock);
 542         tcp_timewait_kill(tw);
 543 }
 544
 545 /* Short-time timewait calendar */
 546
 547 static int tcp_twcal_hand = -1;
 548 static int tcp_twcal_jiffie;
 549 static void tcp_twcal_tick(unsigned long);
 550 static struct timer_list tcp_twcal_timer =
 551                 TIMER_INITIALIZER(tcp_twcal_tick, 0, 0);
 552 static struct hlist_head tcp_twcal_row[TCP_TW_RECYCLE_SLOTS];
 553
 554 void tcp_tw_schedule(struct tcp_tw_bucket *tw, int timeo)
 555 {
 556         struct hlist_head *list;
 557         int slot;
 558
 559         /* timeout := RTO * 3.5
 560          *
 561          * 3.5 = 1+2+0.5 to wait for two retransmits.
 562          *
 563          * RATIONALE: if FIN arrived and we entered TIME-WAIT state,
 564          * our ACK acking that FIN can be lost. If N subsequent retransmitted
 565          * FINs (or previous seqments) are lost (probability of such event
 566          * is p^(N+1), where p is probability to lose single packet and
 567          * time to detect the loss is about RTO*(2^N - 1) with exponential
 568          * backoff). Normal timewait length is calculated so, that we
 569          * waited at least for one retransmitted FIN (maximal RTO is 120sec).
 570          * [ BTW Linux. following BSD, violates this requirement waiting
 571          *   only for 60sec, we should wait at least for 240 secs.
 572          *   Well, 240 consumes too much of resources 8)
 573          * ]
 574          * This interval is not reduced to catch old duplicate and
 575          * responces to our wandering segments living for two MSLs.
 576          * However, if we use PAWS to detect
 577          * old duplicates, we can reduce the interval to bounds required
 578          * by RTO, rather than MSL. So, if peer understands PAWS, we
 579          * kill tw bucket after 3.5*RTO (it is important that this number
 580          * is greater than TS tick!) and detect old duplicates with help
 581          * of PAWS.
 582          */
 583         slot = (timeo + (1<<TCP_TW_RECYCLE_TICK) - 1) >> TCP_TW_RECYCLE_TICK;
 584
 585         spin_lock(&tw_death_lock);
 586
 587         /* Unlink it, if it was scheduled */
 588         if (tw_del_dead_node(tw))
 589                 tcp_tw_count--;
 590         else
 591                 atomic_inc(&tw->tw_refcnt);
 592
 593         if (slot >= TCP_TW_RECYCLE_SLOTS) {
 594                 /* Schedule to slow timer */
 595                 if (timeo >= TCP_TIMEWAIT_LEN) {
 596                         slot = TCP_TWKILL_SLOTS-1;
 597                 } else {
 598                         slot = (timeo + TCP_TWKILL_PERIOD-1) / TCP_TWKILL_PERIOD;
 599                         if (slot >= TCP_TWKILL_SLOTS)
 600                                 slot = TCP_TWKILL_SLOTS-1;
 601                 }
 602                 tw->tw_ttd = jiffies + timeo;
 603                 slot = (tcp_tw_death_row_slot + slot) & (TCP_TWKILL_SLOTS - 1);
 604                 list = &tcp_tw_death_row[slot];
 605         } else {
 606                 tw->tw_ttd = jiffies + (slot << TCP_TW_RECYCLE_TICK);
 607
 608                 if (tcp_twcal_hand < 0) {
 609                         tcp_twcal_hand = 0;
 610                         tcp_twcal_jiffie = jiffies;
 611                         tcp_twcal_timer.expires = tcp_twcal_jiffie + (slot<<TCP_TW_RECYCLE_TICK);
 612                         add_timer(&tcp_twcal_timer);
 613                 } else {
 614                         if (time_after(tcp_twcal_timer.expires, jiffies + (slot<<TCP_TW_RECYCLE_TICK)))
 615                                 mod_timer(&tcp_twcal_timer, jiffies + (slot<<TCP_TW_RECYCLE_TICK));
 616                         slot = (tcp_twcal_hand + slot)&(TCP_TW_RECYCLE_SLOTS-1);
 617                 }
 618                 list = &tcp_twcal_row[slot];
 619         }
 620
 621         hlist_add_head(&tw->tw_death_node, list);
 622
 623         if (tcp_tw_count++ == 0)
 624                 mod_timer(&tcp_tw_timer, jiffies+TCP_TWKILL_PERIOD);
 625         spin_unlock(&tw_death_lock);
 626 }
 627
 628 void tcp_twcal_tick(unsigned long dummy)
 629 {
 630         int n, slot;
 631         unsigned long j;
 632         unsigned long now = jiffies;
 633         int killed = 0;
 634         int adv = 0;
 635
 636         spin_lock(&tw_death_lock);
 637         if (tcp_twcal_hand < 0)
 638                 goto out;
 639
 640         slot = tcp_twcal_hand;
 641         j = tcp_twcal_jiffie;
 642
 643         for (n=0; n<TCP_TW_RECYCLE_SLOTS; n++) {
 644                 if (time_before_eq(j, now)) {
 645                         struct hlist_node *node, *safe;
 646                         struct tcp_tw_bucket *tw;
 647
 648                         tw_for_each_inmate_safe(tw, node, safe,
 649                                            &tcp_twcal_row[slot]) {
 650                                 __tw_del_dead_node(tw);
 651                                 tcp_timewait_kill(tw);
 652                                 tcp_tw_put(tw);
 653                                 killed++;
 654                         }
 655                 } else {
 656                         if (!adv) {
 657                                 adv = 1;
 658                                 tcp_twcal_jiffie = j;
 659                                 tcp_twcal_hand = slot;
 660                         }
 661
 662                         if (!hlist_empty(&tcp_twcal_row[slot])) {
 663                                 mod_timer(&tcp_twcal_timer, j);
 664                                 goto out;
 665                         }
 666                 }
 667                 j += (1<<TCP_TW_RECYCLE_TICK);
 668                 slot = (slot+1)&(TCP_TW_RECYCLE_SLOTS-1);
 669         }
 670         tcp_twcal_hand = -1;
 671
 672 out:
 673         if ((tcp_tw_count -= killed) == 0)
 674                 del_timer(&tcp_tw_timer);
 675         NET_ADD_STATS_BH(TimeWaitKilled, killed);
 676         spin_unlock(&tw_death_lock);
 677 }
 678
 679 /* This is not only more efficient than what we used to do, it eliminates
 680  * a lot of code duplication between IPv4/IPv6 SYN recv processing. -DaveM
 681  *
 682  * Actually, we could lots of memory writes here. tp of listening
 683  * socket contains all necessary default parameters.
 684  */
 685 struct sock *tcp_create_openreq_child(struct sock *sk, struct open_request *req, struct sk_buff *skb)
 686 {
 687         /* allocate the newsk from the same slab of the master sock,
 688          * if not, at sk_free time we'll try to free it from the wrong
 689          * slabcache (i.e. is it TCPv4 or v6?) -acme */
 690         struct sock *newsk = sk_alloc(PF_INET, GFP_ATOMIC, 0, sk->sk_slab);
 691
 692         if(newsk != NULL) {
 693                 struct tcp_opt *newtp;
 694                 struct sk_filter *filter;
 695
 696                 memcpy(newsk, sk, sizeof(struct tcp_sock));
 697                 newsk->sk_state = TCP_SYN_RECV;
 698
 699                 /* SANITY */
 700                 sk_node_init(&newsk->sk_node);
 701                 tcp_sk(newsk)->bind_hash = NULL;
 702
 703                 /* Clone the TCP header template */
 704                 inet_sk(newsk)->dport = req->rmt_port;
 705
 706                 sock_lock_init(newsk);
 707                 bh_lock_sock(newsk);
 708
 709                 newsk->sk_dst_lock = RW_LOCK_UNLOCKED;
 710                 atomic_set(&newsk->sk_rmem_alloc, 0);
 711                 skb_queue_head_init(&newsk->sk_receive_queue);
 712                 atomic_set(&newsk->sk_wmem_alloc, 0);
 713                 skb_queue_head_init(&newsk->sk_write_queue);
 714                 atomic_set(&newsk->sk_omem_alloc, 0);
 715                 newsk->sk_wmem_queued = 0;
 716                 newsk->sk_forward_alloc = 0;
 717
 718                 sock_reset_flag(newsk, SOCK_DONE);
 719                 newsk->sk_userlocks = sk->sk_userlocks & ~SOCK_BINDPORT_LOCK;
 720                 newsk->sk_backlog.head = newsk->sk_backlog.tail = NULL;
 721                 newsk->sk_callback_lock = RW_LOCK_UNLOCKED;
 722                 skb_queue_head_init(&newsk->sk_error_queue);
 723                 newsk->sk_write_space = tcp_write_space;
 724
 725                 if ((filter = newsk->sk_filter) != NULL)
 726                         sk_filter_charge(newsk, filter);
 727
 728                 if (sk->sk_create_child)
 729                         sk->sk_create_child(sk, newsk);
 730
 731                 if (unlikely(xfrm_sk_clone_policy(newsk))) {
 732                         /* It is still raw copy of parent, so invalidate
 733                          * destructor and make plain sk_free() */
 734                         newsk->sk_destruct = NULL;
 735                         sk_free(newsk);
 736                         return NULL;
 737                 }
 738
 739                 /* Now setup tcp_opt */
 740                 newtp = tcp_sk(newsk);
 741                 newtp->pred_flags = 0;
 742                 newtp->rcv_nxt = req->rcv_isn + 1;
 743                 newtp->snd_nxt = req->snt_isn + 1;
 744                 newtp->snd_una = req->snt_isn + 1;
 745                 newtp->snd_sml = req->snt_isn + 1;
 746
 747                 tcp_prequeue_init(newtp);
 748
 749                 tcp_init_wl(newtp, req->snt_isn, req->rcv_isn);
 750
 751                 newtp->retransmits = 0;
 752                 newtp->backoff = 0;
 753                 newtp->srtt = 0;
 754                 newtp->mdev = TCP_TIMEOUT_INIT;
 755                 newtp->rto = TCP_TIMEOUT_INIT;
 756
 757                 newtp->packets_out = 0;
 758                 newtp->left_out = 0;
 759                 newtp->retrans_out = 0;
 760                 newtp->sacked_out = 0;
 761                 newtp->fackets_out = 0;
 762                 newtp->snd_ssthresh = 0x7fffffff;
 763
 764                 /* So many TCP implementations out there (incorrectly) count the
 765                  * initial SYN frame in their delayed-ACK and congestion control
 766                  * algorithms that we must have the following bandaid to talk
 767                  * efficiently to them.  -DaveM
 768                  */
 769                 newtp->snd_cwnd = 2;
 770                 newtp->snd_cwnd_cnt = 0;
 771
 772                 newtp->bictcp.cnt = 0;
 773                 newtp->bictcp.last_max_cwnd = newtp->bictcp.last_cwnd = 0;
 774
 775                 newtp->frto_counter = 0;
 776                 newtp->frto_highmark = 0;
 777
 778                 tcp_set_ca_state(newtp, TCP_CA_Open);
 779                 tcp_init_xmit_timers(newsk);
 780                 skb_queue_head_init(&newtp->out_of_order_queue);
 781                 newtp->send_head = NULL;
 782                 newtp->rcv_wup = req->rcv_isn + 1;
 783                 newtp->write_seq = req->snt_isn + 1;
 784                 newtp->pushed_seq = newtp->write_seq;
 785                 newtp->copied_seq = req->rcv_isn + 1;
 786
 787                 newtp->saw_tstamp = 0;
 788
 789                 newtp->dsack = 0;
 790                 newtp->eff_sacks = 0;
 791
 792                 newtp->probes_out = 0;
 793                 newtp->num_sacks = 0;
 794                 newtp->urg_data = 0;
 795                 newtp->listen_opt = NULL;
 796                 newtp->accept_queue = newtp->accept_queue_tail = NULL;
 797                 /* Deinitialize syn_wait_lock to trap illegal accesses. */
 798                 memset(&newtp->syn_wait_lock, 0, sizeof(newtp->syn_wait_lock));
 799
 800                 /* Back to base struct sock members. */
 801                 newsk->sk_err = 0;
 802                 newsk->sk_priority = 0;
 803                 atomic_set(&newsk->sk_refcnt, 2);
 804 #ifdef INET_REFCNT_DEBUG
 805                 atomic_inc(&inet_sock_nr);
 806 #endif
 807                 atomic_inc(&tcp_sockets_allocated);
 808
 809                 if (sock_flag(newsk, SOCK_KEEPOPEN))
 810                         tcp_reset_keepalive_timer(newsk,
 811                                                   keepalive_time_when(newtp));
 812                 newsk->sk_socket = NULL;
 813                 newsk->sk_sleep = NULL;
 814                 newsk->sk_owner = NULL;
 815
 816                 newtp->tstamp_ok = req->tstamp_ok;
 817                 if((newtp->sack_ok = req->sack_ok) != 0) {
 818                         if (sysctl_tcp_fack)
 819                                 newtp->sack_ok |= 2;
 820                 }
 821                 newtp->window_clamp = req->window_clamp;
 822                 newtp->rcv_ssthresh = req->rcv_wnd;
 823                 newtp->rcv_wnd = req->rcv_wnd;
 824                 newtp->wscale_ok = req->wscale_ok;
 825                 if (newtp->wscale_ok) {
 826                         newtp->snd_wscale = req->snd_wscale;
 827                         newtp->rcv_wscale = req->rcv_wscale;
 828                 } else {
 829                         newtp->snd_wscale = newtp->rcv_wscale = 0;
 830                         newtp->window_clamp = min(newtp->window_clamp, 65535U);
 831                 }
 832                 newtp->snd_wnd = ntohs(skb->h.th->window) << newtp->snd_wscale;
 833                 newtp->max_window = newtp->snd_wnd;
 834
 835                 if (newtp->tstamp_ok) {
 836                         newtp->ts_recent = req->ts_recent;
 837                         newtp->ts_recent_stamp = xtime.tv_sec;
 838                         newtp->tcp_header_len = sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED;
 839                 } else {
 840                         newtp->ts_recent_stamp = 0;
 841                         newtp->tcp_header_len = sizeof(struct tcphdr);
 842                 }
 843                 if (skb->len >= TCP_MIN_RCVMSS+newtp->tcp_header_len)
 844                         newtp->ack.last_seg_size = skb->len-newtp->tcp_header_len;
 845                 newtp->mss_clamp = req->mss;
 846                 TCP_ECN_openreq_child(newtp, req);
 847                 if (newtp->ecn_flags&TCP_ECN_OK)
 848                         newsk->sk_no_largesend = 1;
 849
 850                 tcp_vegas_init(newtp);
 851                 TCP_INC_STATS_BH(TcpPassiveOpens);
 852         }
 853         return newsk;
 854 }
 855
 856 /*
 857  *      Process an incoming packet for SYN_RECV sockets represented
 858  *      as an open_request.
 859  */
 860
 861 struct sock *tcp_check_req(struct sock *sk,struct sk_buff *skb,
 862                            struct open_request *req,
 863                            struct open_request **prev)
 864 {
 865         struct tcphdr *th = skb->h.th;
 866         struct tcp_opt *tp = tcp_sk(sk);
 867         u32 flg = tcp_flag_word(th) & (TCP_FLAG_RST|TCP_FLAG_SYN|TCP_FLAG_ACK);
 868         int paws_reject = 0;
 869         struct tcp_opt ttp;
 870         struct sock *child;
 871
 872         ttp.saw_tstamp = 0;
 873         if (th->doff > (sizeof(struct tcphdr)>>2)) {
 874                 tcp_parse_options(skb, &ttp, 0);
 875
 876                 if (ttp.saw_tstamp) {
 877                         ttp.ts_recent = req->ts_recent;
 878                         /* We do not store true stamp, but it is not required,
 879                          * it can be estimated (approximately)
 880                          * from another data.
 881                          */
 882                         ttp.ts_recent_stamp = xtime.tv_sec - ((TCP_TIMEOUT_INIT/HZ)<<req->retrans);
 883                         paws_reject = tcp_paws_check(&ttp, th->rst);
 884                 }
 885         }
 886
 887         /* Check for pure retransmitted SYN. */
 888         if (TCP_SKB_CB(skb)->seq == req->rcv_isn &&
 889             flg == TCP_FLAG_SYN &&
 890             !paws_reject) {
 891                 /*
 892                  * RFC793 draws (Incorrectly! It was fixed in RFC1122)
 893                  * this case on figure 6 and figure 8, but formal
 894                  * protocol description says NOTHING.
 895                  * To be more exact, it says that we should send ACK,
 896                  * because this segment (at least, if it has no data)
 897                  * is out of window.
 898                  *
 899                  *  CONCLUSION: RFC793 (even with RFC1122) DOES NOT
 900                  *  describe SYN-RECV state. All the description
 901                  *  is wrong, we cannot believe to it and should
 902                  *  rely only on common sense and implementation
 903                  *  experience.
 904                  *
 905                  * Enforce "SYN-ACK" according to figure 8, figure 6
 906                  * of RFC793, fixed by RFC1122.
 907                  */
 908                 req->class->rtx_syn_ack(sk, req, NULL);
 909                 return NULL;
 910         }
 911
 912         /* Further reproduces section "SEGMENT ARRIVES"
 913            for state SYN-RECEIVED of RFC793.
 914            It is broken, however, it does not work only
 915            when SYNs are crossed.
 916
 917            You would think that SYN crossing is impossible here, since
 918            we should have a SYN_SENT socket (from connect()) on our end,
 919            but this is not true if the crossed SYNs were sent to both
 920            ends by a malicious third party.  We must defend against this,
 921            and to do that we first verify the ACK (as per RFC793, page
 922            36) and reset if it is invalid.  Is this a true full defense?
 923            To convince ourselves, let us consider a way in which the ACK
 924            test can still pass in this 'malicious crossed SYNs' case.
 925            Malicious sender sends identical SYNs (and thus identical sequence
 926            numbers) to both A and B:
 927
 928                 A: gets SYN, seq=7
 929                 B: gets SYN, seq=7
 930
 931            By our good fortune, both A and B select the same initial
 932            send sequence number of seven :-)
 933
 934                 A: sends SYN|ACK, seq=7, ack_seq=8
 935                 B: sends SYN|ACK, seq=7, ack_seq=8
 936
 937            So we are now A eating this SYN|ACK, ACK test passes.  So
 938            does sequence test, SYN is truncated, and thus we consider
 939            it a bare ACK.
 940
 941            If tp->defer_accept, we silently drop this bare ACK.  Otherwise,
 942            we create an established connection.  Both ends (listening sockets)
 943            accept the new incoming connection and try to talk to each other. 8-)
 944
 945            Note: This case is both harmless, and rare.  Possibility is about the
 946            same as us discovering intelligent life on another plant tomorrow.
 947
 948            But generally, we should (RFC lies!) to accept ACK
 949            from SYNACK both here and in tcp_rcv_state_process().
 950            tcp_rcv_state_process() does not, hence, we do not too.
 951
 952            Note that the case is absolutely generic:
 953            we cannot optimize anything here without
 954            violating protocol. All the checks must be made
 955            before attempt to create socket.
 956          */
 957
 958         /* RFC793 page 36: "If the connection is in any non-synchronized state ...
 959          *                  and the incoming segment acknowledges something not yet
 960          *                  sent (the segment carries an unaccaptable ACK) ...
 961          *                  a reset is sent."
 962          *
 963          * Invalid ACK: reset will be sent by listening socket
 964          */
 965         if ((flg & TCP_FLAG_ACK) &&
 966             (TCP_SKB_CB(skb)->ack_seq != req->snt_isn+1))
 967                 return sk;
 968
 969         /* Also, it would be not so bad idea to check rcv_tsecr, which
 970          * is essentially ACK extension and too early or too late values
 971          * should cause reset in unsynchronized states.
 972          */
 973
 974         /* RFC793: "first check sequence number". */
 975
 976         if (paws_reject || !tcp_in_window(TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq,
 977                                           req->rcv_isn+1, req->rcv_isn+1+req->rcv_wnd)) {
 978                 /* Out of window: send ACK and drop. */
 979                 if (!(flg & TCP_FLAG_RST))
 980                         req->class->send_ack(skb, req);
 981                 if (paws_reject)
 982                         NET_INC_STATS_BH(PAWSEstabRejected);
 983                 return NULL;
 984         }
 985
 986         /* In sequence, PAWS is OK. */
 987
 988         if (ttp.saw_tstamp && !after(TCP_SKB_CB(skb)->seq, req->rcv_isn+1))
 989                 req->ts_recent = ttp.rcv_tsval;
 990
 991         if (TCP_SKB_CB(skb)->seq == req->rcv_isn) {
 992                 /* Truncate SYN, it is out of window starting
 993                    at req->rcv_isn+1. */
 994                 flg &= ~TCP_FLAG_SYN;
 995         }
 996
 997         /* RFC793: "second check the RST bit" and
 998          *         "fourth, check the SYN bit"
 999          */
1000         if (flg & (TCP_FLAG_RST|TCP_FLAG_SYN))
1001                 goto embryonic_reset;
1002
1003         /* ACK sequence verified above, just make sure ACK is
1004          * set.  If ACK not set, just silently drop the packet.
1005          */
1006         if (!(flg & TCP_FLAG_ACK))
1007                 return NULL;
1008
1009         /* If TCP_DEFER_ACCEPT is set, drop bare ACK. */
1010         if (tp->defer_accept && TCP_SKB_CB(skb)->end_seq == req->rcv_isn+1) {
1011                 req->acked = 1;
1012                 return NULL;
1013         }
1014
1015         /* OK, ACK is valid, create big socket and
1016          * feed this segment to it. It will repeat all
1017          * the tests. THIS SEGMENT MUST MOVE SOCKET TO
1018          * ESTABLISHED STATE. If it will be dropped after
1019          * socket is created, wait for troubles.
1020          */
1021         child = tp->af_specific->syn_recv_sock(sk, skb, req, NULL);
1022         if (child == NULL)
1023                 goto listen_overflow;
1024
1025         sk_set_owner(child, sk->sk_owner);
1026         tcp_synq_unlink(tp, req, prev);
1027         tcp_synq_removed(sk, req);
1028
1029         tcp_acceptq_queue(sk, req, child);
1030         return child;
1031
1032 listen_overflow:
1033         if (!sysctl_tcp_abort_on_overflow) {
1034                 req->acked = 1;
1035                 return NULL;
1036         }
1037
1038 embryonic_reset:
1039         NET_INC_STATS_BH(EmbryonicRsts);
1040         if (!(flg & TCP_FLAG_RST))
1041                 req->class->send_reset(skb);
1042
1043         tcp_synq_drop(sk, req, prev);
1044         return NULL;
1045 }
1046
1047 /*
1048  * Queue segment on the new socket if the new socket is active,
1049  * otherwise we just shortcircuit this and continue with
1050  * the new socket.
1051  */
1052
1053 int tcp_child_process(struct sock *parent, struct sock *child,
1054                       struct sk_buff *skb)
1055 {
1056         int ret = 0;
1057         int state = child->sk_state;
1058
1059         if (!sock_owned_by_user(child)) {
1060                 ret = tcp_rcv_state_process(child, skb, skb->h.th, skb->len);
1061
1062                 /* Wakeup parent, send SIGIO */
1063                 if (state == TCP_SYN_RECV && child->sk_state != state)
1064                         parent->sk_data_ready(parent, 0);
1065         } else {
1066                 /* Alas, it is possible again, because we do lookup
1067                  * in main socket hash table and lock on listening
1068                  * socket does not protect us more.
1069                  */
1070                 sk_add_backlog(child, skb);
1071         }
1072
1073         bh_unlock_sock(child);
1074         sock_put(child);
1075         return ret;
1076 }
1077
1078 EXPORT_SYMBOL(tcp_check_req);
1079 EXPORT_SYMBOL(tcp_child_process);
1080 EXPORT_SYMBOL(tcp_create_openreq_child);
1081 EXPORT_SYMBOL(tcp_timewait_state_process);
1082 EXPORT_SYMBOL(tcp_tw_deschedule);
1083
1084 #ifdef CONFIG_SYSCTL
1085 EXPORT_SYMBOL(sysctl_tcp_tw_recycle);
1086 #endif