/*
   * INET		An implementation of the TCP/IP protocol suite for the LINUX
   *		operating system.  INET is implemented using the  BSD Socket
   *		interface as the means of communication with the user level.
   *
   *		Implementation of the Transmission Control Protocol(TCP).
   *

   * Authors:	Ross Biro

   *		Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG>
   *		Mark Evans, <evansmp@uhura.aston.ac.uk>
   *		Corey Minyard <wf-rch!minyard@relay.EU.net>
   *		Florian La Roche, <flla@stud.uni-sb.de>
   *		Charles Hedrick, <hedrick@klinzhai.rutgers.edu>
   *		Linus Torvalds, <torvalds@cs.helsinki.fi>
   *		Alan Cox, <gw4pts@gw4pts.ampr.org>
   *		Matthew Dillon, <dillon@apollo.west.oic.com>
   *		Arnt Gulbrandsen, <agulbra@nvg.unit.no>
   *		Jorge Cwik, <jorge@laser.satlink.net>
   */
  
  /*
   * Changes:
   *		Pedro Roque	:	Fast Retransmit/Recovery.
   *					Two receive queues.
   *					Retransmit queue handled by TCP.
   *					Better retransmit timer handling.
   *					New congestion avoidance.
   *					Header prediction.
   *					Variable renaming.
   *
   *		Eric		:	Fast Retransmit.
   *		Randy Scott	:	MSS option defines.
   *		Eric Schenk	:	Fixes to slow start algorithm.
   *		Eric Schenk	:	Yet another double ACK bug.
   *		Eric Schenk	:	Delayed ACK bug fixes.
   *		Eric Schenk	:	Floyd style fast retrans war avoidance.
   *		David S. Miller	:	Don't allow zero congestion window.
   *		Eric Schenk	:	Fix retransmitter so that it sends
   *					next packet on ack of previous packet.
   *		Andi Kleen	:	Moved open_request checking here
   *					and process RSTs for open_requests.
   *		Andi Kleen	:	Better prune_queue, and other fixes.

   *		Andrey Savochkin:	Fix RTT measurements in the presence of

   *					timestamps.
   *		Andrey Savochkin:	Check sequence numbers correctly when
   *					removing SACKs due to in sequence incoming
   *					data segments.
   *		Andi Kleen:		Make sure we never ack data there is not
   *					enough room for. Also make this condition
   *					a fatal error if it might still happen.

   *		Andi Kleen:		Add tcp_measure_rcv_mss to make

   *					connections with MSS<min(MTU,ann. MSS)

   *					work without delayed acks.

   *		Andi Kleen:		Process packets with PSH set in the
   *					fast path.
   *		J Hadi Salim:		ECN support
   *	 	Andrei Gurtov,
   *		Pasi Sarolahti,
   *		Panu Kuhlberg:		Experimental audit of TCP (re)transmission
   *					engine. Lots of bugs are found.
   *		Pasi Sarolahti:		F-RTO for dealing with spurious RTOs

   */

  #include <linux/mm.h>

  #include <linux/slab.h>

  #include <linux/module.h>
  #include <linux/sysctl.h>

  #include <linux/kernel.h>

  #include <net/dst.h>

  #include <net/tcp.h>
  #include <net/inet_common.h>
  #include <linux/ipsec.h>
  #include <asm/unaligned.h>

  #include <net/netdma.h>

  int sysctl_tcp_timestamps __read_mostly = 1;
  int sysctl_tcp_window_scaling __read_mostly = 1;
  int sysctl_tcp_sack __read_mostly = 1;
  int sysctl_tcp_fack __read_mostly = 1;
  int sysctl_tcp_reordering __read_mostly = TCP_FASTRETRANS_THRESH;

  EXPORT_SYMBOL(sysctl_tcp_reordering);

  int sysctl_tcp_ecn __read_mostly = 2;

  EXPORT_SYMBOL(sysctl_tcp_ecn);

  int sysctl_tcp_dsack __read_mostly = 1;
  int sysctl_tcp_app_win __read_mostly = 31;
  int sysctl_tcp_adv_win_scale __read_mostly = 2;

  EXPORT_SYMBOL(sysctl_tcp_adv_win_scale);

  int sysctl_tcp_stdurg __read_mostly;
  int sysctl_tcp_rfc1337 __read_mostly;
  int sysctl_tcp_max_orphans __read_mostly = NR_FILE;

  int sysctl_tcp_frto __read_mostly = 2;

  int sysctl_tcp_frto_response __read_mostly;

  int sysctl_tcp_nometrics_save __read_mostly;

  int sysctl_tcp_thin_dupack __read_mostly;

  int sysctl_tcp_moderate_rcvbuf __read_mostly = 1;
  int sysctl_tcp_abc __read_mostly;

  #define FLAG_DATA		0x01 /* Incoming frame contained data.		*/
  #define FLAG_WIN_UPDATE		0x02 /* Incoming ACK was a window update.	*/
  #define FLAG_DATA_ACKED		0x04 /* This ACK acknowledged new data.		*/
  #define FLAG_RETRANS_DATA_ACKED	0x08 /* "" "" some of which was retransmitted.	*/
  #define FLAG_SYN_ACKED		0x10 /* This ACK acknowledged SYN.		*/
  #define FLAG_DATA_SACKED	0x20 /* New SACK.				*/
  #define FLAG_ECE		0x40 /* ECE in this ACK				*/
  #define FLAG_DATA_LOST		0x80 /* SACK detected data lossage.		*/
  #define FLAG_SLOWPATH		0x100 /* Do not skip RFC checks for window update.*/

  #define FLAG_ONLY_ORIG_SACKED	0x200 /* SACKs only non-rexmit sent before RTO */

  #define FLAG_SND_UNA_ADVANCED	0x400 /* Snd_una was changed (!= FLAG_DATA_ACKED) */

  #define FLAG_DSACKING_ACK	0x800 /* SACK blocks contained D-SACK info */

  #define FLAG_NONHEAD_RETRANS_ACKED	0x1000 /* Non-head rexmitted data was ACKed */

  #define FLAG_SACK_RENEGING	0x2000 /* snd_una advanced to a sacked seq */

  
  #define FLAG_ACKED		(FLAG_DATA_ACKED|FLAG_SYN_ACKED)
  #define FLAG_NOT_DUP		(FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED)
  #define FLAG_CA_ALERT		(FLAG_DATA_SACKED|FLAG_ECE)
  #define FLAG_FORWARD_PROGRESS	(FLAG_ACKED|FLAG_DATA_SACKED)

  #define FLAG_ANY_PROGRESS	(FLAG_FORWARD_PROGRESS|FLAG_SND_UNA_ADVANCED)

  #define TCP_REMNANT (TCP_FLAG_FIN|TCP_FLAG_URG|TCP_FLAG_SYN|TCP_FLAG_PSH)

  #define TCP_HP_BITS (~(TCP_RESERVED_BITS|TCP_FLAG_PSH))

  /* Adapt the MSS value used to make delayed ack decision to the

   * real world.

   */

  static void tcp_measure_rcv_mss(struct sock *sk, const struct sk_buff *skb)

  {

  	struct inet_connection_sock *icsk = inet_csk(sk);

  	const unsigned int lss = icsk->icsk_ack.last_seg_size;

  	unsigned int len;

  	icsk->icsk_ack.last_seg_size = 0;

  
  	/* skb->len may jitter because of SACKs, even if peer
  	 * sends good full-sized frames.
  	 */

  	len = skb_shinfo(skb)->gso_size ? : skb->len;

  	if (len >= icsk->icsk_ack.rcv_mss) {
  		icsk->icsk_ack.rcv_mss = len;

  	} else {
  		/* Otherwise, we make more careful check taking into account,
  		 * that SACKs block is variable.
  		 *
  		 * "len" is invariant segment length, including TCP header.
  		 */

  		len += skb->data - skb_transport_header(skb);

  		if (len >= TCP_MSS_DEFAULT + sizeof(struct tcphdr) ||

  		    /* If PSH is not set, packet should be
  		     * full sized, provided peer TCP is not badly broken.
  		     * This observation (if it is correct 8)) allows
  		     * to handle super-low mtu links fairly.
  		     */
  		    (len >= TCP_MIN_MSS + sizeof(struct tcphdr) &&

  		     !(tcp_flag_word(tcp_hdr(skb)) & TCP_REMNANT))) {

  			/* Subtract also invariant (if peer is RFC compliant),
  			 * tcp header plus fixed timestamp option length.
  			 * Resulting "len" is MSS free of SACK jitter.
  			 */

  			len -= tcp_sk(sk)->tcp_header_len;
  			icsk->icsk_ack.last_seg_size = len;

  			if (len == lss) {

  				icsk->icsk_ack.rcv_mss = len;

  				return;
  			}
  		}

  		if (icsk->icsk_ack.pending & ICSK_ACK_PUSHED)
  			icsk->icsk_ack.pending |= ICSK_ACK_PUSHED2;

  		icsk->icsk_ack.pending |= ICSK_ACK_PUSHED;

  	}
  }

  static void tcp_incr_quickack(struct sock *sk)

  {

  	struct inet_connection_sock *icsk = inet_csk(sk);
  	unsigned quickacks = tcp_sk(sk)->rcv_wnd / (2 * icsk->icsk_ack.rcv_mss);

  	if (quickacks == 0)
  		quickacks = 2;

  	if (quickacks > icsk->icsk_ack.quick)
  		icsk->icsk_ack.quick = min(quickacks, TCP_MAX_QUICKACKS);

  }

  static void tcp_enter_quickack_mode(struct sock *sk)

  {

  	struct inet_connection_sock *icsk = inet_csk(sk);
  	tcp_incr_quickack(sk);
  	icsk->icsk_ack.pingpong = 0;
  	icsk->icsk_ack.ato = TCP_ATO_MIN;

  }
  
  /* Send ACKs quickly, if "quick" count is not exhausted
   * and the session is not interactive.
   */

  static inline int tcp_in_quickack_mode(const struct sock *sk)

  {

  	const struct inet_connection_sock *icsk = inet_csk(sk);
  	return icsk->icsk_ack.quick && !icsk->icsk_ack.pingpong;

  }

  static inline void TCP_ECN_queue_cwr(struct tcp_sock *tp)
  {

  	if (tp->ecn_flags & TCP_ECN_OK)

  		tp->ecn_flags |= TCP_ECN_QUEUE_CWR;
  }

  static inline void TCP_ECN_accept_cwr(struct tcp_sock *tp, const struct sk_buff *skb)

  {
  	if (tcp_hdr(skb)->cwr)
  		tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
  }
  
  static inline void TCP_ECN_withdraw_cwr(struct tcp_sock *tp)
  {
  	tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
  }

  static inline void TCP_ECN_check_ce(struct tcp_sock *tp, const struct sk_buff *skb)

  {

  	if (!(tp->ecn_flags & TCP_ECN_OK))
  		return;

  	switch (TCP_SKB_CB(skb)->ip_dsfield & INET_ECN_MASK) {

  	case INET_ECN_NOT_ECT:

  		/* Funny extension: if ECT is not set on a segment,

  		 * and we already seen ECT on a previous segment,
  		 * it is probably a retransmit.
  		 */
  		if (tp->ecn_flags & TCP_ECN_SEEN)

  			tcp_enter_quickack_mode((struct sock *)tp);

  		break;
  	case INET_ECN_CE:
  		tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
  		/* fallinto */
  	default:
  		tp->ecn_flags |= TCP_ECN_SEEN;

  	}
  }

  static inline void TCP_ECN_rcv_synack(struct tcp_sock *tp, const struct tcphdr *th)

  {

  	if ((tp->ecn_flags & TCP_ECN_OK) && (!th->ece || th->cwr))

  		tp->ecn_flags &= ~TCP_ECN_OK;
  }

  static inline void TCP_ECN_rcv_syn(struct tcp_sock *tp, const struct tcphdr *th)

  {

  	if ((tp->ecn_flags & TCP_ECN_OK) && (!th->ece || !th->cwr))

  		tp->ecn_flags &= ~TCP_ECN_OK;
  }

  static inline int TCP_ECN_rcv_ecn_echo(const struct tcp_sock *tp, const struct tcphdr *th)

  {

  	if (th->ece && !th->syn && (tp->ecn_flags & TCP_ECN_OK))

  		return 1;
  	return 0;
  }

  /* Buffer size and advertised window tuning.
   *
   * 1. Tuning sk->sk_sndbuf, when connection enters established state.
   */
  
  static void tcp_fixup_sndbuf(struct sock *sk)
  {

  	int sndmem = SKB_TRUESIZE(tcp_sk(sk)->rx_opt.mss_clamp + MAX_TCP_HEADER);

  	sndmem *= TCP_INIT_CWND;
  	if (sk->sk_sndbuf < sndmem)
  		sk->sk_sndbuf = min(sndmem, sysctl_tcp_wmem[2]);

  }
  
  /* 2. Tuning advertised window (window_clamp, rcv_ssthresh)
   *
   * All tcp_full_space() is split to two parts: "network" buffer, allocated
   * forward and advertised in receiver window (tp->rcv_wnd) and
   * "application buffer", required to isolate scheduling/application
   * latencies from network.
   * window_clamp is maximal advertised window. It can be less than
   * tcp_full_space(), in this case tcp_full_space() - window_clamp
   * is reserved for "application" buffer. The less window_clamp is
   * the smoother our behaviour from viewpoint of network, but the lower
   * throughput and the higher sensitivity of the connection to losses. 8)
   *
   * rcv_ssthresh is more strict window_clamp used at "slow start"
   * phase to predict further behaviour of this connection.
   * It is used for two goals:
   * - to enforce header prediction at sender, even when application
   *   requires some significant "application buffer". It is check #1.
   * - to prevent pruning of receive queue because of misprediction
   *   of receiver window. Check #2.
   *
   * The scheme does not work when sender sends good segments opening

   * window and then starts to feed us spaghetti. But it should work

   * in common situations. Otherwise, we have to rely on queue collapsing.
   */
  
  /* Slow part of check#2. */

  static int __tcp_grow_window(const struct sock *sk, const struct sk_buff *skb)

  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	/* Optimize this! */

  	int truesize = tcp_win_from_space(skb->truesize) >> 1;
  	int window = tcp_win_from_space(sysctl_tcp_rmem[2]) >> 1;

  
  	while (tp->rcv_ssthresh <= window) {
  		if (truesize <= skb->len)

  			return 2 * inet_csk(sk)->icsk_ack.rcv_mss;

  
  		truesize >>= 1;
  		window >>= 1;
  	}
  	return 0;
  }

  static void tcp_grow_window(struct sock *sk, const struct sk_buff *skb)

  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	/* Check #1 */
  	if (tp->rcv_ssthresh < tp->window_clamp &&
  	    (int)tp->rcv_ssthresh < tcp_space(sk) &&

  	    !sk_under_memory_pressure(sk)) {

  		int incr;
  
  		/* Check #2. Increase window, if skb with such overhead
  		 * will fit to rcvbuf in future.
  		 */
  		if (tcp_win_from_space(skb->truesize) <= skb->len)

  			incr = 2 * tp->advmss;

  		else

  			incr = __tcp_grow_window(sk, skb);

  
  		if (incr) {

  			tp->rcv_ssthresh = min(tp->rcv_ssthresh + incr,
  					       tp->window_clamp);

  			inet_csk(sk)->icsk_ack.quick |= 1;

  		}
  	}
  }
  
  /* 3. Tuning rcvbuf, when connection enters established state. */
  
  static void tcp_fixup_rcvbuf(struct sock *sk)
  {

  	u32 mss = tcp_sk(sk)->advmss;
  	u32 icwnd = TCP_DEFAULT_INIT_RCVWND;
  	int rcvmem;

  	/* Limit to 10 segments if mss <= 1460,
  	 * or 14600/mss segments, with a minimum of two segments.

  	 */

  	if (mss > 1460)
  		icwnd = max_t(u32, (1460 * TCP_DEFAULT_INIT_RCVWND) / mss, 2);
  
  	rcvmem = SKB_TRUESIZE(mss + MAX_TCP_HEADER);
  	while (tcp_win_from_space(rcvmem) < mss)

  		rcvmem += 128;

  
  	rcvmem *= icwnd;
  
  	if (sk->sk_rcvbuf < rcvmem)
  		sk->sk_rcvbuf = min(rcvmem, sysctl_tcp_rmem[2]);

  }

  /* 4. Try to fixup all. It is made immediately after connection enters

   *    established state.
   */
  static void tcp_init_buffer_space(struct sock *sk)
  {
  	struct tcp_sock *tp = tcp_sk(sk);
  	int maxwin;
  
  	if (!(sk->sk_userlocks & SOCK_RCVBUF_LOCK))
  		tcp_fixup_rcvbuf(sk);
  	if (!(sk->sk_userlocks & SOCK_SNDBUF_LOCK))
  		tcp_fixup_sndbuf(sk);
  
  	tp->rcvq_space.space = tp->rcv_wnd;
  
  	maxwin = tcp_full_space(sk);
  
  	if (tp->window_clamp >= maxwin) {
  		tp->window_clamp = maxwin;
  
  		if (sysctl_tcp_app_win && maxwin > 4 * tp->advmss)
  			tp->window_clamp = max(maxwin -
  					       (maxwin >> sysctl_tcp_app_win),
  					       4 * tp->advmss);
  	}
  
  	/* Force reservation of one segment. */
  	if (sysctl_tcp_app_win &&
  	    tp->window_clamp > 2 * tp->advmss &&
  	    tp->window_clamp + tp->advmss > maxwin)
  		tp->window_clamp = max(2 * tp->advmss, maxwin - tp->advmss);
  
  	tp->rcv_ssthresh = min(tp->rcv_ssthresh, tp->window_clamp);
  	tp->snd_cwnd_stamp = tcp_time_stamp;
  }

  /* 5. Recalculate window clamp after socket hit its memory bounds. */

  static void tcp_clamp_window(struct sock *sk)

  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	struct inet_connection_sock *icsk = inet_csk(sk);

  	icsk->icsk_ack.quick = 0;

  	if (sk->sk_rcvbuf < sysctl_tcp_rmem[2] &&
  	    !(sk->sk_userlocks & SOCK_RCVBUF_LOCK) &&

  	    !sk_under_memory_pressure(sk) &&
  	    sk_memory_allocated(sk) < sk_prot_mem_limits(sk, 0)) {

  		sk->sk_rcvbuf = min(atomic_read(&sk->sk_rmem_alloc),
  				    sysctl_tcp_rmem[2]);

  	}

  	if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf)

  		tp->rcv_ssthresh = min(tp->window_clamp, 2U * tp->advmss);

  }

  /* Initialize RCV_MSS value.
   * RCV_MSS is an our guess about MSS used by the peer.
   * We haven't any direct information about the MSS.
   * It's better to underestimate the RCV_MSS rather than overestimate.
   * Overestimations make us ACKing less frequently than needed.
   * Underestimations are more easy to detect and fix by tcp_measure_rcv_mss().
   */
  void tcp_initialize_rcv_mss(struct sock *sk)
  {

  	const struct tcp_sock *tp = tcp_sk(sk);

  	unsigned int hint = min_t(unsigned int, tp->advmss, tp->mss_cache);

  	hint = min(hint, tp->rcv_wnd / 2);

  	hint = min(hint, TCP_MSS_DEFAULT);

  	hint = max(hint, TCP_MIN_MSS);
  
  	inet_csk(sk)->icsk_ack.rcv_mss = hint;
  }

  EXPORT_SYMBOL(tcp_initialize_rcv_mss);

  /* Receiver "autotuning" code.
   *
   * The algorithm for RTT estimation w/o timestamps is based on
   * Dynamic Right-Sizing (DRS) by Wu Feng and Mike Fisk of LANL.

   * <http://public.lanl.gov/radiant/pubs.html#DRS>

   *
   * More detail on this code can be found at

   * <http://staff.psc.edu/jheffner/>,

   * though this reference is out of date.  A new paper
   * is pending.
   */
  static void tcp_rcv_rtt_update(struct tcp_sock *tp, u32 sample, int win_dep)
  {
  	u32 new_sample = tp->rcv_rtt_est.rtt;
  	long m = sample;
  
  	if (m == 0)
  		m = 1;
  
  	if (new_sample != 0) {
  		/* If we sample in larger samples in the non-timestamp
  		 * case, we could grossly overestimate the RTT especially
  		 * with chatty applications or bulk transfer apps which
  		 * are stalled on filesystem I/O.
  		 *
  		 * Also, since we are only going for a minimum in the

  		 * non-timestamp case, we do not smooth things out

  		 * else with timestamps disabled convergence takes too

  		 * long.
  		 */
  		if (!win_dep) {
  			m -= (new_sample >> 3);
  			new_sample += m;
  		} else if (m < new_sample)
  			new_sample = m << 3;
  	} else {

  		/* No previous measure. */

  		new_sample = m << 3;
  	}
  
  	if (tp->rcv_rtt_est.rtt != new_sample)
  		tp->rcv_rtt_est.rtt = new_sample;
  }
  
  static inline void tcp_rcv_rtt_measure(struct tcp_sock *tp)
  {
  	if (tp->rcv_rtt_est.time == 0)
  		goto new_measure;
  	if (before(tp->rcv_nxt, tp->rcv_rtt_est.seq))
  		return;

  	tcp_rcv_rtt_update(tp, jiffies - tp->rcv_rtt_est.time, 1);

  
  new_measure:
  	tp->rcv_rtt_est.seq = tp->rcv_nxt + tp->rcv_wnd;
  	tp->rcv_rtt_est.time = tcp_time_stamp;
  }

  static inline void tcp_rcv_rtt_measure_ts(struct sock *sk,
  					  const struct sk_buff *skb)

  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	if (tp->rx_opt.rcv_tsecr &&
  	    (TCP_SKB_CB(skb)->end_seq -

  	     TCP_SKB_CB(skb)->seq >= inet_csk(sk)->icsk_ack.rcv_mss))

  		tcp_rcv_rtt_update(tp, tcp_time_stamp - tp->rx_opt.rcv_tsecr, 0);
  }
  
  /*
   * This function should be called every time data is copied to user space.
   * It calculates the appropriate TCP receive buffer space.
   */
  void tcp_rcv_space_adjust(struct sock *sk)
  {
  	struct tcp_sock *tp = tcp_sk(sk);
  	int time;
  	int space;

  	if (tp->rcvq_space.time == 0)
  		goto new_measure;

  	time = tcp_time_stamp - tp->rcvq_space.time;

  	if (time < (tp->rcv_rtt_est.rtt >> 3) || tp->rcv_rtt_est.rtt == 0)

  		return;

  	space = 2 * (tp->copied_seq - tp->rcvq_space.seq);
  
  	space = max(tp->rcvq_space.space, space);
  
  	if (tp->rcvq_space.space != space) {
  		int rcvmem;
  
  		tp->rcvq_space.space = space;

  		if (sysctl_tcp_moderate_rcvbuf &&
  		    !(sk->sk_userlocks & SOCK_RCVBUF_LOCK)) {

  			int new_clamp = space;
  
  			/* Receive space grows, normalize in order to
  			 * take into account packet headers and sk_buff
  			 * structure overhead.
  			 */
  			space /= tp->advmss;
  			if (!space)
  				space = 1;

  			rcvmem = SKB_TRUESIZE(tp->advmss + MAX_TCP_HEADER);

  			while (tcp_win_from_space(rcvmem) < tp->advmss)
  				rcvmem += 128;
  			space *= rcvmem;
  			space = min(space, sysctl_tcp_rmem[2]);
  			if (space > sk->sk_rcvbuf) {
  				sk->sk_rcvbuf = space;
  
  				/* Make the window clamp follow along.  */
  				tp->window_clamp = new_clamp;
  			}
  		}
  	}

  new_measure:
  	tp->rcvq_space.seq = tp->copied_seq;
  	tp->rcvq_space.time = tcp_time_stamp;
  }
  
  /* There is something which you must keep in mind when you analyze the
   * behavior of the tp->ato delayed ack timeout interval.  When a
   * connection starts up, we want to ack as quickly as possible.  The
   * problem is that "good" TCP's do slow start at the beginning of data
   * transmission.  The means that until we send the first few ACK's the
   * sender will sit on his end and only queue most of his data, because
   * he can only send snd_cwnd unacked packets at any given time.  For
   * each ACK we send, he increments snd_cwnd and transmits more of his
   * queue.  -DaveM
   */

  static void tcp_event_data_recv(struct sock *sk, struct sk_buff *skb)

  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	struct inet_connection_sock *icsk = inet_csk(sk);

  	u32 now;

  	inet_csk_schedule_ack(sk);

  	tcp_measure_rcv_mss(sk, skb);

  
  	tcp_rcv_rtt_measure(tp);

  	now = tcp_time_stamp;

  	if (!icsk->icsk_ack.ato) {

  		/* The _first_ data packet received, initialize
  		 * delayed ACK engine.
  		 */

  		tcp_incr_quickack(sk);
  		icsk->icsk_ack.ato = TCP_ATO_MIN;

  	} else {

  		int m = now - icsk->icsk_ack.lrcvtime;

  		if (m <= TCP_ATO_MIN / 2) {

  			/* The fastest case is the first. */

  			icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + TCP_ATO_MIN / 2;
  		} else if (m < icsk->icsk_ack.ato) {
  			icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + m;
  			if (icsk->icsk_ack.ato > icsk->icsk_rto)
  				icsk->icsk_ack.ato = icsk->icsk_rto;
  		} else if (m > icsk->icsk_rto) {

  			/* Too long gap. Apparently sender failed to

  			 * restart window, so that we send ACKs quickly.
  			 */

  			tcp_incr_quickack(sk);

  			sk_mem_reclaim(sk);

  		}
  	}

  	icsk->icsk_ack.lrcvtime = now;

  
  	TCP_ECN_check_ce(tp, skb);
  
  	if (skb->len >= 128)

  		tcp_grow_window(sk, skb);

  }

  /* Called to compute a smoothed rtt estimate. The data fed to this
   * routine either comes from timestamps, or from segments that were
   * known _not_ to have been retransmitted [see Karn/Partridge
   * Proceedings SIGCOMM 87]. The algorithm is from the SIGCOMM 88
   * piece by Van Jacobson.
   * NOTE: the next three routines used to be one big routine.
   * To save cycles in the RFC 1323 implementation it was better to break
   * it up into three procedures. -- erics
   */

  static void tcp_rtt_estimator(struct sock *sk, const __u32 mrtt)

  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	long m = mrtt; /* RTT */

  	/*	The following amusing code comes from Jacobson's
  	 *	article in SIGCOMM '88.  Note that rtt and mdev
  	 *	are scaled versions of rtt and mean deviation.

  	 *	This is designed to be as fast as possible

  	 *	m stands for "measurement".
  	 *
  	 *	On a 1990 paper the rto value is changed to:
  	 *	RTO = rtt + 4 * mdev
  	 *
  	 * Funny. This algorithm seems to be very broken.
  	 * These formulae increase RTO, when it should be decreased, increase

  	 * too slowly, when it should be increased quickly, decrease too quickly

  	 * etc. I guess in BSD RTO takes ONE value, so that it is absolutely
  	 * does not matter how to _calculate_ it. Seems, it was trap
  	 * that VJ failed to avoid. 8)
  	 */

  	if (m == 0)

  		m = 1;
  	if (tp->srtt != 0) {
  		m -= (tp->srtt >> 3);	/* m is now error in rtt est */
  		tp->srtt += m;		/* rtt = 7/8 rtt + 1/8 new */
  		if (m < 0) {
  			m = -m;		/* m is now abs(error) */
  			m -= (tp->mdev >> 2);   /* similar update on mdev */
  			/* This is similar to one of Eifel findings.
  			 * Eifel blocks mdev updates when rtt decreases.
  			 * This solution is a bit different: we use finer gain
  			 * for mdev in this case (alpha*beta).
  			 * Like Eifel it also prevents growth of rto,
  			 * but also it limits too fast rto decreases,
  			 * happening in pure Eifel.
  			 */
  			if (m > 0)
  				m >>= 3;
  		} else {
  			m -= (tp->mdev >> 2);   /* similar update on mdev */
  		}
  		tp->mdev += m;	    	/* mdev = 3/4 mdev + 1/4 new */
  		if (tp->mdev > tp->mdev_max) {
  			tp->mdev_max = tp->mdev;
  			if (tp->mdev_max > tp->rttvar)
  				tp->rttvar = tp->mdev_max;
  		}
  		if (after(tp->snd_una, tp->rtt_seq)) {
  			if (tp->mdev_max < tp->rttvar)

  				tp->rttvar -= (tp->rttvar - tp->mdev_max) >> 2;

  			tp->rtt_seq = tp->snd_nxt;

  			tp->mdev_max = tcp_rto_min(sk);

  		}
  	} else {
  		/* no previous measure. */

  		tp->srtt = m << 3;	/* take the measured time to be rtt */
  		tp->mdev = m << 1;	/* make sure rto = 3*rtt */

  		tp->mdev_max = tp->rttvar = max(tp->mdev, tcp_rto_min(sk));

  		tp->rtt_seq = tp->snd_nxt;
  	}

  }
  
  /* Calculate rto without backoff.  This is the second half of Van Jacobson's
   * routine referred to above.
   */

  static inline void tcp_set_rto(struct sock *sk)

  {

  	const struct tcp_sock *tp = tcp_sk(sk);

  	/* Old crap is replaced with new one. 8)
  	 *
  	 * More seriously:
  	 * 1. If rtt variance happened to be less 50msec, it is hallucination.
  	 *    It cannot be less due to utterly erratic ACK generation made
  	 *    at least by solaris and freebsd. "Erratic ACKs" has _nothing_
  	 *    to do with delayed acks, because at cwnd>2 true delack timeout
  	 *    is invisible. Actually, Linux-2.4 also generates erratic

  	 *    ACKs in some circumstances.

  	 */

  	inet_csk(sk)->icsk_rto = __tcp_set_rto(tp);

  
  	/* 2. Fixups made earlier cannot be right.
  	 *    If we do not estimate RTO correctly without them,
  	 *    all the algo is pure shit and should be replaced

  	 *    with correct one. It is exactly, which we pretend to do.

  	 */

  	/* NOTE: clamping at TCP_RTO_MIN is not required, current algo
  	 * guarantees that rto is higher.
  	 */

  	tcp_bound_rto(sk);

  }
  
  /* Save metrics learned by this TCP session.
     This function is called only, when TCP finishes successfully
     i.e. when it enters TIME-WAIT or goes from LAST-ACK to CLOSE.
   */
  void tcp_update_metrics(struct sock *sk)
  {
  	struct tcp_sock *tp = tcp_sk(sk);
  	struct dst_entry *dst = __sk_dst_get(sk);
  
  	if (sysctl_tcp_nometrics_save)
  		return;
  
  	dst_confirm(dst);

  	if (dst && (dst->flags & DST_HOST)) {

  		const struct inet_connection_sock *icsk = inet_csk(sk);

  		int m;

  		unsigned long rtt;

  		if (icsk->icsk_backoff || !tp->srtt) {

  			/* This session failed to estimate rtt. Why?
  			 * Probably, no packets returned in time.
  			 * Reset our results.
  			 */
  			if (!(dst_metric_locked(dst, RTAX_RTT)))

  				dst_metric_set(dst, RTAX_RTT, 0);

  			return;
  		}

  		rtt = dst_metric_rtt(dst, RTAX_RTT);
  		m = rtt - tp->srtt;

  
  		/* If newly calculated rtt larger than stored one,
  		 * store new one. Otherwise, use EWMA. Remember,
  		 * rtt overestimation is always better than underestimation.
  		 */
  		if (!(dst_metric_locked(dst, RTAX_RTT))) {
  			if (m <= 0)

  				set_dst_metric_rtt(dst, RTAX_RTT, tp->srtt);

  			else

  				set_dst_metric_rtt(dst, RTAX_RTT, rtt - (m >> 3));

  		}
  
  		if (!(dst_metric_locked(dst, RTAX_RTTVAR))) {

  			unsigned long var;

  			if (m < 0)
  				m = -m;
  
  			/* Scale deviation to rttvar fixed point */
  			m >>= 1;
  			if (m < tp->mdev)
  				m = tp->mdev;

  			var = dst_metric_rtt(dst, RTAX_RTTVAR);
  			if (m >= var)
  				var = m;

  			else

  				var -= (var - m) >> 2;
  
  			set_dst_metric_rtt(dst, RTAX_RTTVAR, var);

  		}

  		if (tcp_in_initial_slowstart(tp)) {

  			/* Slow start still did not finish. */
  			if (dst_metric(dst, RTAX_SSTHRESH) &&
  			    !dst_metric_locked(dst, RTAX_SSTHRESH) &&
  			    (tp->snd_cwnd >> 1) > dst_metric(dst, RTAX_SSTHRESH))

  				dst_metric_set(dst, RTAX_SSTHRESH, tp->snd_cwnd >> 1);

  			if (!dst_metric_locked(dst, RTAX_CWND) &&
  			    tp->snd_cwnd > dst_metric(dst, RTAX_CWND))

  				dst_metric_set(dst, RTAX_CWND, tp->snd_cwnd);

  		} else if (tp->snd_cwnd > tp->snd_ssthresh &&

  			   icsk->icsk_ca_state == TCP_CA_Open) {

  			/* Cong. avoidance phase, cwnd is reliable. */
  			if (!dst_metric_locked(dst, RTAX_SSTHRESH))

  				dst_metric_set(dst, RTAX_SSTHRESH,
  					       max(tp->snd_cwnd >> 1, tp->snd_ssthresh));

  			if (!dst_metric_locked(dst, RTAX_CWND))

  				dst_metric_set(dst, RTAX_CWND,
  					       (dst_metric(dst, RTAX_CWND) +
  						tp->snd_cwnd) >> 1);

  		} else {
  			/* Else slow start did not finish, cwnd is non-sense,
  			   ssthresh may be also invalid.
  			 */
  			if (!dst_metric_locked(dst, RTAX_CWND))

  				dst_metric_set(dst, RTAX_CWND,
  					       (dst_metric(dst, RTAX_CWND) +
  						tp->snd_ssthresh) >> 1);

  			if (dst_metric(dst, RTAX_SSTHRESH) &&

  			    !dst_metric_locked(dst, RTAX_SSTHRESH) &&

  			    tp->snd_ssthresh > dst_metric(dst, RTAX_SSTHRESH))

  				dst_metric_set(dst, RTAX_SSTHRESH, tp->snd_ssthresh);

  		}
  
  		if (!dst_metric_locked(dst, RTAX_REORDERING)) {

  			if (dst_metric(dst, RTAX_REORDERING) < tp->reordering &&

  			    tp->reordering != sysctl_tcp_reordering)

  				dst_metric_set(dst, RTAX_REORDERING, tp->reordering);

  		}
  	}
  }

  __u32 tcp_init_cwnd(const struct tcp_sock *tp, const struct dst_entry *dst)

  {
  	__u32 cwnd = (dst ? dst_metric(dst, RTAX_INITCWND) : 0);

  	if (!cwnd)

  		cwnd = TCP_INIT_CWND;

  	return min_t(__u32, cwnd, tp->snd_cwnd_clamp);
  }

  /* Set slow start threshold and cwnd not falling to slow start */

  void tcp_enter_cwr(struct sock *sk, const int set_ssthresh)

  {
  	struct tcp_sock *tp = tcp_sk(sk);

  	const struct inet_connection_sock *icsk = inet_csk(sk);

  
  	tp->prior_ssthresh = 0;
  	tp->bytes_acked = 0;

  	if (icsk->icsk_ca_state < TCP_CA_CWR) {

  		tp->undo_marker = 0;

  		if (set_ssthresh)
  			tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);

  		tp->snd_cwnd = min(tp->snd_cwnd,
  				   tcp_packets_in_flight(tp) + 1U);
  		tp->snd_cwnd_cnt = 0;
  		tp->high_seq = tp->snd_nxt;
  		tp->snd_cwnd_stamp = tcp_time_stamp;
  		TCP_ECN_queue_cwr(tp);
  
  		tcp_set_ca_state(sk, TCP_CA_CWR);
  	}
  }

  /*
   * Packet counting of FACK is based on in-order assumptions, therefore TCP
   * disables it when reordering is detected
   */
  static void tcp_disable_fack(struct tcp_sock *tp)
  {

  	/* RFC3517 uses different metric in lost marker => reset on change */
  	if (tcp_is_fack(tp))
  		tp->lost_skb_hint = NULL;

  	tp->rx_opt.sack_ok &= ~TCP_FACK_ENABLED;

  }

  /* Take a notice that peer is sending D-SACKs */

  static void tcp_dsack_seen(struct tcp_sock *tp)
  {

  	tp->rx_opt.sack_ok |= TCP_DSACK_SEEN;

  }

  /* Initialize metrics on socket. */
  
  static void tcp_init_metrics(struct sock *sk)
  {
  	struct tcp_sock *tp = tcp_sk(sk);
  	struct dst_entry *dst = __sk_dst_get(sk);
  
  	if (dst == NULL)
  		goto reset;
  
  	dst_confirm(dst);
  
  	if (dst_metric_locked(dst, RTAX_CWND))
  		tp->snd_cwnd_clamp = dst_metric(dst, RTAX_CWND);
  	if (dst_metric(dst, RTAX_SSTHRESH)) {
  		tp->snd_ssthresh = dst_metric(dst, RTAX_SSTHRESH);
  		if (tp->snd_ssthresh > tp->snd_cwnd_clamp)
  			tp->snd_ssthresh = tp->snd_cwnd_clamp;

  	} else {
  		/* ssthresh may have been reduced unnecessarily during.
  		 * 3WHS. Restore it back to its initial default.
  		 */
  		tp->snd_ssthresh = TCP_INFINITE_SSTHRESH;

  	}
  	if (dst_metric(dst, RTAX_REORDERING) &&
  	    tp->reordering != dst_metric(dst, RTAX_REORDERING)) {

  		tcp_disable_fack(tp);

  		tp->reordering = dst_metric(dst, RTAX_REORDERING);
  	}

  	if (dst_metric(dst, RTAX_RTT) == 0 || tp->srtt == 0)

  		goto reset;
  
  	/* Initial rtt is determined from SYN,SYN-ACK.
  	 * The segment is small and rtt may appear much
  	 * less than real one. Use per-dst memory
  	 * to make it more realistic.
  	 *
  	 * A bit of theory. RTT is time passed after "normal" sized packet

  	 * is sent until it is ACKed. In normal circumstances sending small

  	 * packets force peer to delay ACKs and calculation is correct too.
  	 * The algorithm is adaptive and, provided we follow specs, it
  	 * NEVER underestimate RTT. BUT! If peer tries to make some clever
  	 * tricks sort of "quick acks" for time long enough to decrease RTT
  	 * to low value, and then abruptly stops to do it and starts to delay
  	 * ACKs, wait for troubles.
  	 */

  	if (dst_metric_rtt(dst, RTAX_RTT) > tp->srtt) {
  		tp->srtt = dst_metric_rtt(dst, RTAX_RTT);

  		tp->rtt_seq = tp->snd_nxt;
  	}

  	if (dst_metric_rtt(dst, RTAX_RTTVAR) > tp->mdev) {
  		tp->mdev = dst_metric_rtt(dst, RTAX_RTTVAR);

  		tp->mdev_max = tp->rttvar = max(tp->mdev, tcp_rto_min(sk));

  	}

  	tcp_set_rto(sk);

  reset:

  	if (tp->srtt == 0) {
  		/* RFC2988bis: We've failed to get a valid RTT sample from
  		 * 3WHS. This is most likely due to retransmission,
  		 * including spurious one. Reset the RTO back to 3secs
  		 * from the more aggressive 1sec to avoid more spurious
  		 * retransmission.

  		 */

  		tp->mdev = tp->mdev_max = tp->rttvar = TCP_TIMEOUT_FALLBACK;
  		inet_csk(sk)->icsk_rto = TCP_TIMEOUT_FALLBACK;

  	}

  	/* Cut cwnd down to 1 per RFC5681 if SYN or SYN-ACK has been
  	 * retransmitted. In light of RFC2988bis' more aggressive 1sec
  	 * initRTO, we only reset cwnd when more than 1 SYN/SYN-ACK
  	 * retransmission has occurred.
  	 */
  	if (tp->total_retrans > 1)
  		tp->snd_cwnd = 1;
  	else
  		tp->snd_cwnd = tcp_init_cwnd(tp, dst);

  	tp->snd_cwnd_stamp = tcp_time_stamp;

  }

  static void tcp_update_reordering(struct sock *sk, const int metric,
  				  const int ts)

  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	if (metric > tp->reordering) {

  		int mib_idx;

  		tp->reordering = min(TCP_MAX_REORDERING, metric);
  
  		/* This exciting event is worth to be remembered. 8) */
  		if (ts)

  			mib_idx = LINUX_MIB_TCPTSREORDER;

  		else if (tcp_is_reno(tp))

  			mib_idx = LINUX_MIB_TCPRENOREORDER;

  		else if (tcp_is_fack(tp))

  			mib_idx = LINUX_MIB_TCPFACKREORDER;

  		else

  			mib_idx = LINUX_MIB_TCPSACKREORDER;

  		NET_INC_STATS_BH(sock_net(sk), mib_idx);

  #if FASTRETRANS_DEBUG > 1
  		printk(KERN_DEBUG "Disorder%d %d %u f%u s%u rr%d
  ",

  		       tp->rx_opt.sack_ok, inet_csk(sk)->icsk_ca_state,

  		       tp->reordering,
  		       tp->fackets_out,
  		       tp->sacked_out,
  		       tp->undo_marker ? tp->undo_retrans : 0);
  #endif

  		tcp_disable_fack(tp);

  	}
  }

  /* This must be called before lost_out is incremented */

  static void tcp_verify_retransmit_hint(struct tcp_sock *tp, struct sk_buff *skb)
  {

  	if ((tp->retransmit_skb_hint == NULL) ||

  	    before(TCP_SKB_CB(skb)->seq,
  		   TCP_SKB_CB(tp->retransmit_skb_hint)->seq))

  		tp->retransmit_skb_hint = skb;
  
  	if (!tp->lost_out ||
  	    after(TCP_SKB_CB(skb)->end_seq, tp->retransmit_high))
  		tp->retransmit_high = TCP_SKB_CB(skb)->end_seq;

  }

  static void tcp_skb_mark_lost(struct tcp_sock *tp, struct sk_buff *skb)
  {
  	if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) {
  		tcp_verify_retransmit_hint(tp, skb);
  
  		tp->lost_out += tcp_skb_pcount(skb);
  		TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
  	}
  }

  static void tcp_skb_mark_lost_uncond_verify(struct tcp_sock *tp,
  					    struct sk_buff *skb)

  {
  	tcp_verify_retransmit_hint(tp, skb);
  
  	if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) {
  		tp->lost_out += tcp_skb_pcount(skb);
  		TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
  	}
  }

  /* This procedure tags the retransmission queue when SACKs arrive.
   *
   * We have three tag bits: SACKED(S), RETRANS(R) and LOST(L).
   * Packets in queue with these bits set are counted in variables
   * sacked_out, retrans_out and lost_out, correspondingly.
   *
   * Valid combinations are:
   * Tag  InFlight	Description
   * 0	1		- orig segment is in flight.
   * S	0		- nothing flies, orig reached receiver.
   * L	0		- nothing flies, orig lost by net.
   * R	2		- both orig and retransmit are in flight.
   * L|R	1		- orig is lost, retransmit is in flight.
   * S|R  1		- orig reached receiver, retrans is still in flight.
   * (L|S|R is logically valid, it could occur when L|R is sacked,
   *  but it is equivalent to plain S and code short-curcuits it to S.
   *  L|S is logically invalid, it would mean -1 packet in flight 8))
   *
   * These 6 states form finite state machine, controlled by the following events:
   * 1. New ACK (+SACK) arrives. (tcp_sacktag_write_queue())
   * 2. Retransmission. (tcp_retransmit_skb(), tcp_xmit_retransmit_queue())
   * 3. Loss detection event of one of three flavors:
   *	A. Scoreboard estimator decided the packet is lost.
   *	   A'. Reno "three dupacks" marks head of queue lost.
   *	   A''. Its FACK modfication, head until snd.fack is lost.
   *	B. SACK arrives sacking data transmitted after never retransmitted
   *	   hole was sent out.
   *	C. SACK arrives sacking SND.NXT at the moment, when the
   *	   segment was retransmitted.
   * 4. D-SACK added new rule: D-SACK changes any tag to S.
   *
   * It is pleasant to note, that state diagram turns out to be commutative,
   * so that we are allowed not to be bothered by order of our actions,
   * when multiple events arrive simultaneously. (see the function below).
   *
   * Reordering detection.
   * --------------------
   * Reordering metric is maximal distance, which a packet can be displaced
   * in packet stream. With SACKs we can estimate it:
   *
   * 1. SACK fills old hole and the corresponding segment was not
   *    ever retransmitted -> reordering. Alas, we cannot use it
   *    when segment was retransmitted.
   * 2. The last flaw is solved with D-SACK. D-SACK arrives
   *    for retransmitted and already SACKed segment -> reordering..
   * Both of these heuristics are not used in Loss state, when we cannot
   * account for retransmits accurately.

   *
   * SACK block validation.
   * ----------------------
   *
   * SACK block range validation checks that the received SACK block fits to
   * the expected sequence limits, i.e., it is between SND.UNA and SND.NXT.
   * Note that SND.UNA is not included to the range though being valid because

   * it means that the receiver is rather inconsistent with itself reporting
   * SACK reneging when it should advance SND.UNA. Such SACK block this is
   * perfectly valid, however, in light of RFC2018 which explicitly states
   * that "SACK block MUST reflect the newest segment.  Even if the newest
   * segment is going to be discarded ...", not that it looks very clever
   * in case of head skb. Due to potentional receiver driven attacks, we
   * choose to avoid immediate execution of a walk in write queue due to
   * reneging and defer head skb's loss recovery to standard loss recovery
   * procedure that will eventually trigger (nothing forbids us doing this).

   *
   * Implements also blockage to start_seq wrap-around. Problem lies in the
   * fact that though start_seq (s) is before end_seq (i.e., not reversed),
   * there's no guarantee that it will be before snd_nxt (n). The problem
   * happens when start_seq resides between end_seq wrap (e_w) and snd_nxt
   * wrap (s_w):
   *
   *         <- outs wnd ->                          <- wrapzone ->
   *         u     e      n                         u_w   e_w  s n_w
   *         |     |      |                          |     |   |  |
   * |<------------+------+----- TCP seqno space --------------+---------->|
   * ...-- <2^31 ->|                                           |<--------...
   * ...---- >2^31 ------>|                                    |<--------...
   *
   * Current code wouldn't be vulnerable but it's better still to discard such
   * crazy SACK blocks. Doing this check for start_seq alone closes somewhat
   * similar case (end_seq after snd_nxt wrap) as earlier reversed check in
   * snd_nxt wrap -> snd_una region will then become "well defined", i.e.,
   * equal to the ideal case (infinite seqno space without wrap caused issues).
   *
   * With D-SACK the lower bound is extended to cover sequence space below
   * SND.UNA down to undo_marker, which is the last point of interest. Yet

   * again, D-SACK block must not to go across snd_una (for the same reason as

   * for the normal SACK blocks, explained above). But there all simplicity
   * ends, TCP might receive valid D-SACKs below that. As long as they reside
   * fully below undo_marker they do not affect behavior in anyway and can
   * therefore be safely ignored. In rare cases (which are more or less
   * theoretical ones), the D-SACK will nicely cross that boundary due to skb
   * fragmentation and packet reordering past skb's retransmission. To consider
   * them correctly, the acceptable range must be extended even more though
   * the exact amount is rather hard to quantify. However, tp->max_window can
   * be used as an exaggerated estimate.

   */

  static int tcp_is_sackblock_valid(struct tcp_sock *tp, int is_dsack,
  				  u32 start_seq, u32 end_seq)
  {
  	/* Too far in future, or reversed (interpretation is ambiguous) */
  	if (after(end_seq, tp->snd_nxt) || !before(start_seq, end_seq))
  		return 0;
  
  	/* Nasty start_seq wrap-around check (see comments above) */
  	if (!before(start_seq, tp->snd_nxt))
  		return 0;

  	/* In outstanding window? ...This is valid exit for D-SACKs too.

  	 * start_seq == snd_una is non-sensical (see comments above)
  	 */
  	if (after(start_seq, tp->snd_una))
  		return 1;
  
  	if (!is_dsack || !tp->undo_marker)
  		return 0;
  
  	/* ...Then it's D-SACK, and must reside below snd_una completely */

  	if (after(end_seq, tp->snd_una))

  		return 0;
  
  	if (!before(start_seq, tp->undo_marker))
  		return 1;
  
  	/* Too old */
  	if (!after(end_seq, tp->undo_marker))
  		return 0;
  
  	/* Undo_marker boundary crossing (overestimates a lot). Known already:
  	 *   start_seq < undo_marker and end_seq >= undo_marker.
  	 */
  	return !before(start_seq, end_seq - tp->max_window);
  }

  /* Check for lost retransmit. This superb idea is borrowed from "ratehalving".
   * Event "C". Later note: FACK people cheated me again 8), we have to account
   * for reordering! Ugly, but should help.

   *
   * Search retransmitted skbs from write_queue that were sent when snd_nxt was
   * less than what is now known to be received by the other end (derived from

   * highest SACK block). Also calculate the lowest snd_nxt among the remaining
   * retransmitted skbs to avoid some costly processing per ACKs.

   */

  static void tcp_mark_lost_retrans(struct sock *sk)

  {

  	const struct inet_connection_sock *icsk = inet_csk(sk);

  	struct tcp_sock *tp = tcp_sk(sk);
  	struct sk_buff *skb;

  	int cnt = 0;

  	u32 new_low_seq = tp->snd_nxt;

  	u32 received_upto = tcp_highest_sack_seq(tp);

  
  	if (!tcp_is_fack(tp) || !tp->retrans_out ||
  	    !after(received_upto, tp->lost_retrans_low) ||
  	    icsk->icsk_ca_state != TCP_CA_Recovery)

  		return;

  
  	tcp_for_write_queue(skb, sk) {
  		u32 ack_seq = TCP_SKB_CB(skb)->ack_seq;
  
  		if (skb == tcp_send_head(sk))
  			break;

  		if (cnt == tp->retrans_out)

  			break;
  		if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
  			continue;

  		if (!(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS))
  			continue;

  		/* TODO: We would like to get rid of tcp_is_fack(tp) only
  		 * constraint here (see above) but figuring out that at
  		 * least tp->reordering SACK blocks reside between ack_seq
  		 * and received_upto is not easy task to do cheaply with
  		 * the available datastructures.
  		 *
  		 * Whether FACK should check here for tp->reordering segs
  		 * in-between one could argue for either way (it would be
  		 * rather simple to implement as we could count fack_count
  		 * during the walk and do tp->fackets_out - fack_count).
  		 */
  		if (after(received_upto, ack_seq)) {

  			TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
  			tp->retrans_out -= tcp_skb_pcount(skb);

  			tcp_skb_mark_lost_uncond_verify(tp, skb);

  			NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSTRETRANSMIT);

  		} else {

  			if (before(ack_seq, new_low_seq))

  				new_low_seq = ack_seq;

  			cnt += tcp_skb_pcount(skb);

  		}
  	}

  
  	if (tp->retrans_out)
  		tp->lost_retrans_low = new_low_seq;

  }

  static int tcp_check_dsack(struct sock *sk, const struct sk_buff *ack_skb,

  			   struct tcp_sack_block_wire *sp, int num_sacks,
  			   u32 prior_snd_una)
  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	u32 start_seq_0 = get_unaligned_be32(&sp[0].start_seq);
  	u32 end_seq_0 = get_unaligned_be32(&sp[0].end_seq);

  	int dup_sack = 0;
  
  	if (before(start_seq_0, TCP_SKB_CB(ack_skb)->ack_seq)) {
  		dup_sack = 1;

  		tcp_dsack_seen(tp);

  		NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPDSACKRECV);

  	} else if (num_sacks > 1) {

  		u32 end_seq_1 = get_unaligned_be32(&sp[1].end_seq);
  		u32 start_seq_1 = get_unaligned_be32(&sp[1].start_seq);

  
  		if (!after(end_seq_0, end_seq_1) &&
  		    !before(start_seq_0, start_seq_1)) {
  			dup_sack = 1;

  			tcp_dsack_seen(tp);

  			NET_INC_STATS_BH(sock_net(sk),
  					LINUX_MIB_TCPDSACKOFORECV);

  		}
  	}
  
  	/* D-SACK for already forgotten data... Do dumb counting. */

  	if (dup_sack && tp->undo_marker && tp->undo_retrans &&

  	    !after(end_seq_0, prior_snd_una) &&
  	    after(end_seq_0, tp->undo_marker))
  		tp->undo_retrans--;
  
  	return dup_sack;
  }

  struct tcp_sacktag_state {
  	int reord;
  	int fack_count;
  	int flag;
  };

  /* Check if skb is fully within the SACK block. In presence of GSO skbs,
   * the incoming SACK may not exactly match but we can find smaller MSS
   * aligned portion of it that matches. Therefore we might need to fragment
   * which may fail and creates some hassle (caller must handle error case
   * returns).

   *
   * FIXME: this could be merged to shift decision code

   */

  static int tcp_match_skb_to_sack(struct sock *sk, struct sk_buff *skb,
  				 u32 start_seq, u32 end_seq)

  {
  	int in_sack, err;
  	unsigned int pkt_len;

  	unsigned int mss;

  
  	in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) &&
  		  !before(end_seq, TCP_SKB_CB(skb)->end_seq);
  
  	if (tcp_skb_pcount(skb) > 1 && !in_sack &&
  	    after(TCP_SKB_CB(skb)->end_seq, start_seq)) {

  		mss = tcp_skb_mss(skb);

  		in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq);

  		if (!in_sack) {

  			pkt_len = start_seq - TCP_SKB_CB(skb)->seq;

  			if (pkt_len < mss)
  				pkt_len = mss;
  		} else {

  			pkt_len = end_seq - TCP_SKB_CB(skb)->seq;

  			if (pkt_len < mss)
  				return -EINVAL;
  		}
  
  		/* Round if necessary so that SACKs cover only full MSSes
  		 * and/or the remaining small portion (if present)
  		 */
  		if (pkt_len > mss) {
  			unsigned int new_len = (pkt_len / mss) * mss;
  			if (!in_sack && new_len < pkt_len) {
  				new_len += mss;
  				if (new_len > skb->len)
  					return 0;
  			}
  			pkt_len = new_len;
  		}
  		err = tcp_fragment(sk, skb, pkt_len, mss);

  		if (err < 0)
  			return err;
  	}
  
  	return in_sack;
  }

  static u8 tcp_sacktag_one(const struct sk_buff *skb, struct sock *sk,

  			  struct tcp_sacktag_state *state,
  			  int dup_sack, int pcount)

  {

  	struct tcp_sock *tp = tcp_sk(sk);

  	u8 sacked = TCP_SKB_CB(skb)->sacked;

  	int fack_count = state->fack_count;

  
  	/* Account D-SACK for retransmitted packet. */
  	if (dup_sack && (sacked & TCPCB_RETRANS)) {

  		if (tp->undo_marker && tp->undo_retrans &&
  		    after(TCP_SKB_CB(skb)->end_seq, tp->undo_marker))

  			tp->undo_retrans--;

  		if (sacked & TCPCB_SACKED_ACKED)

  			state->reord = min(fack_count, state->reord);

  	}
  
  	/* Nothing to do; acked frame is about to be dropped (was ACKed). */
  	if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))

  		return sacked;

  
  	if (!(sacked & TCPCB_SACKED_ACKED)) {
  		if (sacked & TCPCB_SACKED_RETRANS) {
  			/* If the segment is not tagged as lost,
  			 * we do not clear RETRANS, believing
  			 * that retransmission is still in flight.
  			 */
  			if (sacked & TCPCB_LOST) {

  				sacked &= ~(TCPCB_LOST|TCPCB_SACKED_RETRANS);

  				tp->lost_out -= pcount;
  				tp->retrans_out -= pcount;

  			}
  		} else {
  			if (!(sacked & TCPCB_RETRANS)) {
  				/* New sack for not retransmitted frame,
  				 * which was in hole. It is reordering.
  				 */
  				if (before(TCP_SKB_CB(skb)->seq,
  					   tcp_highest_sack_seq(tp)))

  					state->reord = min(fack_count,
  							   state->reord);

  
  				/* SACK enhanced F-RTO (RFC4138; Appendix B) */
  				if (!after(TCP_SKB_CB(skb)->end_seq, tp->frto_highmark))

  					state->flag |= FLAG_ONLY_ORIG_SACKED;

  			}
  
  			if (sacked & TCPCB_LOST) {

  				sacked &= ~TCPCB_LOST;

  				tp->lost_out -= pcount;

  			}
  		}

  		sacked |= TCPCB_SACKED_ACKED;
  		state->flag |= FLAG_DATA_SACKED;

  		tp->sacked_out += pcount;

  		fack_count += pcount;

  
  		/* Lost marker hint past SACKed? Tweak RFC3517 cnt */
  		if (!tcp_is_fack(tp) && (tp->lost_skb_hint != NULL) &&
  		    before(TCP_SKB_CB(skb)->seq,
  			   TCP_SKB_CB(tp->lost_skb_hint)->seq))

  			tp->lost_cnt_hint += pcount;

  
  		if (fack_count > tp->fackets_out)
  			tp->fackets_out = fack_count;

  	}
  
  	/* D-SACK. We can detect redundant retransmission in S|R and plain R
  	 * frames and clear it. undo_retrans is decreased above, L|R frames
  	 * are accounted above as well.
  	 */

  	if (dup_sack && (sacked & TCPCB_SACKED_RETRANS)) {
  		sacked &= ~TCPCB_SACKED_RETRANS;

  		tp->retrans_out -= pcount;

  	}

  	return sacked;

  }

  static int tcp_shifted_skb(struct sock *sk, struct sk_buff *skb,

  			   struct tcp_sacktag_state *state,

  			   unsigned int pcount, int shifted, int mss,
  			   int dup_sack)

  {
  	struct tcp_sock *tp = tcp_sk(sk);

  	struct sk_buff *prev = tcp_write_queue_prev(sk, skb);

  
  	BUG_ON(!pcount);

  	if (skb == tp->lost_skb_hint)

  		tp->lost_cnt_hint += pcount;

  	TCP_SKB_CB(prev)->end_seq += shifted;
  	TCP_SKB_CB(skb)->seq += shifted;
  
  	skb_shinfo(prev)->gso_segs += pcount;
  	BUG_ON(skb_shinfo(skb)->gso_segs < pcount);
  	skb_shinfo(skb)->gso_segs -= pcount;
  
  	/* When we're adding to gso_segs == 1, gso_size will be zero,
  	 * in theory this shouldn't be necessary but as long as DSACK
  	 * code can come after this skb later on it's better to keep
  	 * setting gso_size to something.
  	 */
  	if (!skb_shinfo(prev)->gso_size) {
  		skb_shinfo(prev)->gso_size = mss;
  		skb_shinfo(prev)->gso_type = sk->sk_gso_type;
  	}
  
  	/* CHECKME: To clear or not to clear? Mimics normal skb currently */
  	if (skb_shinfo(skb)->gso_segs <= 1) {
  		skb_shinfo(skb)->gso_size = 0;
  		skb_shinfo(skb)->gso_type = 0;
  	}

  	/* We discard results */

  	tcp_sacktag_one(skb, sk, state, dup_sack, pcount);

  
  	/* Difference in this won't matter, both ACKed by the same cumul. ACK */
  	TCP_SKB_CB(prev)->sacked |= (TCP_SKB_CB(skb)->sacked & TCPCB_EVER_RETRANS);

  	if (skb->len > 0) {
  		BUG_ON(!tcp_skb_pcount(skb));

  		NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKSHIFTED);

  		return 0;
  	}
  
  	/* Whole SKB was eaten :-) */

  	if (skb == tp->retransmit_skb_hint)
  		tp->retransmit_skb_hint = prev;
  	if (skb == tp->scoreboard_skb_hint)
  		tp->scoreboard_skb_hint = prev;
  	if (skb == tp->lost_skb_hint) {
  		tp->lost_skb_hint = prev;
  		tp->lost_cnt_hint -= tcp_skb_pcount(prev);
  	}

  	TCP_SKB_CB(skb)->tcp_flags |= TCP_SKB_CB(prev)->tcp_flags;

  	if (skb == tcp_highest_sack(sk))
  		tcp_advance_highest_sack(sk, skb);
  
  	tcp_unlink_write_queue(skb, sk);
  	sk_wmem_free_skb(sk, skb);

  	NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKMERGED);

  	return 1;
  }
  
  /* I wish gso_size would have a bit more sane initialization than
   * something-or-zero which complicates things
   */

  static int tcp_skb_seglen(const struct sk_buff *skb)

  {

  	return tcp_skb_pcount(skb) == 1 ? skb->len : tcp_skb_mss(skb);

  }
  
  /* Shifting pages past head area doesn't work */

  static int skb_can_shift(const struct sk_buff *skb)

  {
  	return !skb_headlen(skb) && skb_is_nonlinear(skb);
  }
  
  /* Try collapsing SACK blocks spanning across multiple skbs to a single
   * skb.
   */
  static struct sk_buff *tcp_shift_skb_data(struct sock *sk, struct sk_buff *skb,

  					  struct tcp_sacktag_state *state,

  					  u32 start_seq, u32 end_seq,

  					  int dup_sack)

  {
  	struct tcp_sock *tp = tcp_sk(sk);
  	struct sk_buff *prev;
  	int mss;
  	int pcount = 0;
  	int len;
  	int in_sack;
  
  	if (!sk_can_gso(sk))
  		goto fallback;
  
  	/* Normally R but no L won't result in plain S */
  	if (!dup_sack &&

  	    (TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_RETRANS)) == TCPCB_SACKED_RETRANS)

  		goto fallback;
  	if (!skb_can_shift(skb))
  		goto fallback;
  	/* This frame is about to be dropped (was ACKed). */
  	if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
  		goto fallback;
  
  	/* Can only happen with delayed DSACK + discard craziness */
  	if (unlikely(skb == tcp_write_queue_head(sk)))
  		goto fallback;
  	prev = tcp_write_queue_prev(sk, skb);
  
  	if ((TCP_SKB_CB(prev)->sacked & TCPCB_TAGBITS) != TCPCB_SACKED_ACKED)
  		goto fallback;
  
  	in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) &&
  		  !before(end_seq, TCP_SKB_CB(skb)->end_seq);
  
  	if (in_sack) {
  		len = skb->len;
  		pcount = tcp_skb_pcount(skb);

  		mss = tcp_skb_seglen(skb);

  
  		/* TODO: Fix DSACKs to not fragment already SACKed and we can
  		 * drop this restriction as unnecessary
  		 */

  		if (mss != tcp_skb_seglen(prev))

  			goto fallback;
  	} else {
  		if (!after(TCP_SKB_CB(skb)->end_seq, start_seq))
  			goto noop;
  		/* CHECKME: This is non-MSS split case only?, this will
  		 * cause skipped skbs due to advancing loop btw, original
  		 * has that feature too
  		 */
  		if (tcp_skb_pcount(skb) <= 1)
  			goto noop;
  
  		in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq);
  		if (!in_sack) {
  			/* TODO: head merge to next could be attempted here
  			 * if (!after(TCP_SKB_CB(skb)->end_seq, end_seq)),
  			 * though it might not be worth of the additional hassle
  			 *
  			 * ...we can probably just fallback to what was done
  			 * previously. We could try merging non-SACKed ones
  			 * as well but it probably isn't going to buy off
  			 * because later SACKs might again split them, and
  			 * it would make skb timestamp tracking considerably
  			 * harder problem.
  			 */
  			goto fallback;
  		}
  
  		len = end_seq - TCP_SKB_CB(skb)->seq;
  		BUG_ON(len < 0);
  		BUG_ON(len > skb->len);
  
  		/* MSS boundaries should be honoured or else pcount will
  		 * severely break even though it makes things bit trickier.
  		 * Optimize common case to avoid most of the divides
  		 */
  		mss = tcp_skb_mss(skb);
  
  		/* TODO: Fix DSACKs to not fragment already SACKed and we can
  		 * drop this restriction as unnecessary
  		 */

  		if (mss != tcp_skb_seglen(prev))

  			goto fallback;
  
  		if (len == mss) {
  			pcount = 1;
  		} else if (len < mss) {
  			goto noop;
  		} else {
  			pcount = len / mss;
  			len = pcount * mss;
  		}
  	}
  
  	if (!skb_shift(prev, skb, len))
  		goto fallback;

  	if (!tcp_shifted_skb(sk, skb, state, pcount, len, mss, dup_sack))

  		goto out;
  
  	/* Hole filled allows collapsing with the next as well, this is very
  	 * useful when hole on every nth skb pattern happens
  	 */
  	if (prev == tcp_write_queue_tail(sk))
  		goto out;
  	skb = tcp_write_queue_next(sk, prev);

  	if (!skb_can_shift(skb) ||
  	    (skb == tcp_send_head(sk)) ||
  	    ((TCP_SKB_CB(skb)->sacked & TCPCB_TAGBITS) != TCPCB_SACKED_ACKED) ||

  	    (mss != tcp_skb_seglen(skb)))

  		goto out;
  
  	len = skb->len;
  	if (skb_shift(prev, skb, len)) {
  		pcount += tcp_skb_pcount(skb);

  		tcp_shifted_skb(sk, skb, state, tcp_skb_pcount(skb), len, mss, 0);

  	}
  
  out:

  	state->fack_count += pcount;

  	return prev;
  
  noop:
  	return skb;
  
  fallback:

  	NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKSHIFTFALLBACK);

  	return NULL;
  }

  static struct sk_buff *tcp_sacktag_walk(struct sk_buff *skb, struct sock *sk,
  					struct tcp_sack_block *next_dup,

  					struct tcp_sacktag_state *state,

  					u32 start_seq, u32 end_seq,

  					int dup_sack_in)

  {

  	struct tcp_sock *tp = tcp_sk(sk);
  	struct sk_buff *tmp;

  	tcp_for_write_queue_from(skb, sk) {
  		int in_sack = 0;
  		int dup_sack = dup_sack_in;
  
  		if (skb == tcp_send_head(sk))
  			break;
  
  		/* queue is in-order => we can short-circuit the walk early */
  		if (!before(TCP_SKB_CB(skb)->seq, end_seq))
  			break;
  
  		if ((next_dup != NULL) &&
  		    before(TCP_SKB_CB(skb)->seq, next_dup->end_seq)) {
  			in_sack = tcp_match_skb_to_sack(sk, skb,
  							next_dup->start_seq,
  							next_dup->end_seq);
  			if (in_sack > 0)
  				dup_sack = 1;
  		}

  		/* skb reference here is a bit tricky to get right, since
  		 * shifting can eat and free both this skb and the next,
  		 * so not even _safe variant of the loop is enough.
  		 */
  		if (in_sack <= 0) {

  			tmp = tcp_shift_skb_data(sk, skb, state,
  						 start_seq, end_seq, dup_sack);

  			if (tmp != NULL) {
  				if (tmp != skb) {
  					skb = tmp;
  					continue;
  				}
  
  				in_sack = 0;
  			} else {
  				in_sack = tcp_match_skb_to_sack(sk, skb,
  								start_seq,
  								end_seq);
  			}
  		}

  		if (unlikely(in_sack < 0))
  			break;

  		if (in_sack) {

  			TCP_SKB_CB(skb)->sacked = tcp_sacktag_one(skb, sk,
  								  state,
  								  dup_sack,
  								  tcp_skb_pcount(skb));

  			if (!before(TCP_SKB_CB(skb)->seq,
  				    tcp_highest_sack_seq(tp)))
  				tcp_advance_highest_sack(sk, skb);
  		}

  		state->fack_count += tcp_skb_pcount(skb);

  	}
  	return skb;
  }
  
  /* Avoid all extra work that is being done by sacktag while walking in
   * a normal way
   */
  static struct sk_buff *tcp_sacktag_skip(struct sk_buff *skb, struct sock *sk,

  					struct tcp_sacktag_state *state,
  					u32 skip_to_seq)

  {
  	tcp_for_write_queue_from(skb, sk) {
  		if (skb == tcp_send_head(sk))
  			break;

  		if (after(TCP_SKB_CB(skb)->end_seq, skip_to_seq))

  			break;

  		state->fack_count += tcp_skb_pcount(skb);

  	}
  	return skb;
  }
  
  static struct sk_buff *tcp_maybe_skipping_dsack(struct sk_buff *skb,
  						struct sock *sk,
  						struct tcp_sack_block *next_dup,

  						struct tcp_sacktag_state *state,
  						u32 skip_to_seq)

  {
  	if (next_dup == NULL)
  		return skb;
  
  	if (before(next_dup->start_seq, skip_to_seq)) {

  		skb = tcp_sacktag_skip(skb, sk, state, next_dup->start_seq);
  		skb = tcp_sacktag_walk(skb, sk, NULL, state,
  				       next_dup->start_seq, next_dup->end_seq,
  				       1);

  	}
  
  	return skb;
  }

  static int tcp_sack_cache_ok(const struct tcp_sock *tp, const struct tcp_sack_block *cache)

  {
  	return cache < tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
  }

  static int

  tcp_sacktag_write_queue(struct sock *sk, const struct sk_buff *ack_skb,

  			u32 prior_snd_una)

  {

  	const struct inet_connection_sock *icsk = inet_csk(sk);

  	struct tcp_sock *tp = tcp_sk(sk);

  	const unsigned char *ptr = (skb_transport_header(ack_skb) +
  				    TCP_SKB_CB(ack_skb)->sacked);

  	struct tcp_sack_block_wire *sp_wire = (struct tcp_sack_block_wire *)(ptr+2);

  	struct tcp_sack_block sp[TCP_NUM_SACKS];

  	struct tcp_sack_block *cache;

  	struct tcp_sacktag_state state;

  	struct sk_buff *skb;

  	int num_sacks = min(TCP_NUM_SACKS, (ptr[1] - TCPOLEN_SACK_BASE) >> 3);

  	int used_sacks;

  	int found_dup_sack = 0;

  	int i, j;

  	int first_sack_index;

  	state.flag = 0;
  	state.reord = tp->packets_out;

  	if (!tp->sacked_out) {

  		if (WARN_ON(tp->fackets_out))
  			tp->fackets_out = 0;

  		tcp_highest_sack_reset(sk);

  	}

  	found_dup_sack = tcp_check_dsack(sk, ack_skb, sp_wire,

  					 num_sacks, prior_snd_una);
  	if (found_dup_sack)

  		state.flag |= FLAG_DSACKING_ACK;

  
  	/* Eliminate too old ACKs, but take into
  	 * account more or less fresh ones, they can
  	 * contain valid SACK info.
  	 */
  	if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
  		return 0;

  	if (!tp->packets_out)
  		goto out;

  	used_sacks = 0;
  	first_sack_index = 0;
  	for (i = 0; i < num_sacks; i++) {
  		int dup_sack = !i && found_dup_sack;

  		sp[used_sacks].start_seq = get_unaligned_be32(&sp_wire[i].start_seq);
  		sp[used_sacks].end_seq = get_unaligned_be32(&sp_wire[i].end_seq);

  
  		if (!tcp_is_sackblock_valid(tp, dup_sack,
  					    sp[used_sacks].start_seq,
  					    sp[used_sacks].end_seq)) {

  			int mib_idx;

  			if (dup_sack) {
  				if (!tp->undo_marker)

  					mib_idx = LINUX_MIB_TCPDSACKIGNOREDNOUNDO;

  				else

  					mib_idx = LINUX_MIB_TCPDSACKIGNOREDOLD;

  			} else {
  				/* Don't count olds caused by ACK reordering */
  				if ((TCP_SKB_CB(ack_skb)->ack_seq != tp->snd_una) &&
  				    !after(sp[used_sacks].end_seq, tp->snd_una))
  					continue;

  				mib_idx = LINUX_MIB_TCPSACKDISCARD;

  			}

  			NET_INC_STATS_BH(sock_net(sk), mib_idx);

  			if (i == 0)
  				first_sack_index = -1;
  			continue;
  		}
  
  		/* Ignore very old stuff early */
  		if (!after(sp[used_sacks].end_seq, prior_snd_una))
  			continue;
  
  		used_sacks++;
  	}

  	/* order SACK blocks to allow in order walk of the retrans queue */
  	for (i = used_sacks - 1; i > 0; i--) {

  		for (j = 0; j < i; j++) {
  			if (after(sp[j].start_seq, sp[j + 1].start_seq)) {

  				swap(sp[j], sp[j + 1]);

  				/* Track where the first SACK block goes to */
  				if (j == first_sack_index)

  					first_sack_index = j + 1;

  			}
  		}
  	}

  	skb = tcp_write_queue_head(sk);

  	state.fack_count = 0;

  	i = 0;
  
  	if (!tp->sacked_out) {
  		/* It's already past, so skip checking against it */
  		cache = tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
  	} else {
  		cache = tp->recv_sack_cache;
  		/* Skip empty blocks in at head of the cache */
  		while (tcp_sack_cache_ok(tp, cache) && !cache->start_seq &&
  		       !cache->end_seq)
  			cache++;

  	}

  	while (i < used_sacks) {

  		u32 start_seq = sp[i].start_seq;
  		u32 end_seq = sp[i].end_seq;

  		int dup_sack = (found_dup_sack && (i == first_sack_index));

  		struct tcp_sack_block *next_dup = NULL;

  		if (found_dup_sack && ((i + 1) == first_sack_index))
  			next_dup = &sp[i + 1];

  
  		/* Event "B" in the comment above. */
  		if (after(end_seq, tp->high_seq))

  			state.flag |= FLAG_DATA_LOST;

  		/* Skip too early cached blocks */
  		while (tcp_sack_cache_ok(tp, cache) &&
  		       !before(start_seq, cache->end_seq))
  			cache++;
  
  		/* Can skip some work by looking recv_sack_cache? */
  		if (tcp_sack_cache_ok(tp, cache) && !dup_sack &&
  		    after(end_seq, cache->start_seq)) {
  
  			/* Head todo? */
  			if (before(start_seq, cache->start_seq)) {

  				skb = tcp_sacktag_skip(skb, sk, &state,
  						       start_seq);

  				skb = tcp_sacktag_walk(skb, sk, next_dup,

  						       &state,

  						       start_seq,
  						       cache->start_seq,

  						       dup_sack);

  			}

  			/* Rest of the block already fully processed? */

  			if (!after(end_seq, cache->end_seq))

  				goto advance_sp;

  			skb = tcp_maybe_skipping_dsack(skb, sk, next_dup,

  						       &state,
  						       cache->end_seq);

  			/* ...tail remains todo... */

  			if (tcp_highest_sack_seq(tp) == cache->end_seq) {

  				/* ...but better entrypoint exists! */

  				skb = tcp_highest_sack(sk);
  				if (skb == NULL)
  					break;

  				state.fack_count = tp->fackets_out;

  				cache++;
  				goto walk;

  			}

  			skb = tcp_sacktag_skip(skb, sk, &state, cache->end_seq);

  			/* Check overlap against next cached too (past this one already) */
  			cache++;
  			continue;
  		}

  		if (!before(start_seq, tcp_highest_sack_seq(tp))) {
  			skb = tcp_highest_sack(sk);
  			if (skb == NULL)
  				break;

  			state.fack_count = tp->fackets_out;