tcp_input.c

GNU Hurd 源代码

		if (*ptr == __constant_ntohl((TCPOPT_NOP << 24) | (TCPOPT_NOP << 16)
					     | (TCPOPT_TIMESTAMP << 8) | TCPOLEN_TIMESTAMP)) {
			tp->saw_tstamp = 1;
			tp->rcv_tsval = ntohl(*++ptr);
			tp->rcv_tsecr = ntohl(*++ptr);
			return 1;
		}
	}
	tcp_parse_options(sk, th, tp, 0);
	return 1;
}

#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.	*/

static __inline__ void clear_fast_retransmit(struct tcp_opt *tp)
{
	if (tp->dup_acks > 3)
		tp->snd_cwnd = (tp->snd_ssthresh);

	tp->dup_acks = 0;
}

/* NOTE: This code assumes that tp->dup_acks gets cleared when a
 * retransmit timer fires.
 */
static void tcp_fast_retrans(struct sock *sk, u32 ack, int not_dup)
{
	struct tcp_opt *tp = &(sk->tp_pinfo.af_tcp);

	/* Note: If not_dup is set this implies we got a
	 * data carrying packet or a window update.
	 * This carries no new information about possible
	 * lost packets, so we have to ignore it for the purposes
	 * of counting duplicate acks. Ideally this does not imply we
	 * should stop our fast retransmit phase, more acks may come
	 * later without data to help us. Unfortunately this would make
	 * the code below much more complex. For now if I see such
	 * a packet I clear the fast retransmit phase.
	 */
	if (ack == tp->snd_una && tp->packets_out && (not_dup == 0)) {
		/* This is the standard reno style fast retransmit branch. */

                /* 1. When the third duplicate ack is received, set ssthresh 
                 * to one half the current congestion window, but no less 
                 * than two segments. Retransmit the missing segment.
                 */
		if (tp->high_seq == 0 || after(ack, tp->high_seq)) {
			tp->dup_acks++;
			if ((tp->fackets_out > 3) || (tp->dup_acks == 3)) {
                                tp->snd_ssthresh = tcp_recalc_ssthresh(tp);
                                tp->snd_cwnd = (tp->snd_ssthresh + 3);
				tp->high_seq = tp->snd_nxt;
				if(!tp->fackets_out)
					tcp_retransmit_skb(sk,
							   skb_peek(&sk->write_queue));
				else
					tcp_fack_retransmit(sk);
                                tcp_reset_xmit_timer(sk, TIME_RETRANS, tp->rto);
			}
		} else if (++tp->dup_acks > 3) {
			/* 2. Each time another duplicate ACK arrives, increment 
			 * cwnd by the segment size. [...] Transmit a packet...
			 *
			 * Packet transmission will be done on normal flow processing
			 * since we're not in "retransmit mode".  We do not use
			 * duplicate ACKs to artificially inflate the congestion
			 * window when doing FACK.
			 */
			if(!tp->fackets_out) {
				tp->snd_cwnd++;
			} else {
				/* Fill any further holes which may have
				 * appeared.
				 *
				 * We may want to change this to run every
				 * further multiple-of-3 dup ack increments,
				 * to be more robust against out-of-order
				 * packet delivery.  -DaveM
				 */
				tcp_fack_retransmit(sk);
			}
		}
	} else if (tp->high_seq != 0) {
		/* In this branch we deal with clearing the Floyd style
		 * block on duplicate fast retransmits, and if requested
		 * we do Hoe style secondary fast retransmits.
		 */
		if (!before(ack, tp->high_seq) || (not_dup & FLAG_DATA) != 0) {
			/* Once we have acked all the packets up to high_seq
			 * we are done this fast retransmit phase.
			 * Alternatively data arrived. In this case we
			 * Have to abort the fast retransmit attempt.
			 * Note that we do want to accept a window
			 * update since this is expected with Hoe's algorithm.
			 */
			clear_fast_retransmit(tp);

			/* After we have cleared up to high_seq we can
			 * clear the Floyd style block.
			 */
			if (!before(ack, tp->high_seq)) {
				tp->high_seq = 0;
				tp->fackets_out = 0;
			}
		} else if (tp->dup_acks >= 3) {
			if (!tp->fackets_out) {
				/* Hoe Style. We didn't ack the whole
				 * window. Take this as a cue that
				 * another packet was lost and retransmit it.
				 * Don't muck with the congestion window here.
				 * Note that we have to be careful not to
				 * act if this was a window update and it
				 * didn't ack new data, since this does
				 * not indicate a packet left the system.
				 * We can test this by just checking
				 * if ack changed from snd_una, since
				 * the only way to get here without advancing
				 * from snd_una is if this was a window update.
				 */
				if (ack != tp->snd_una && before(ack, tp->high_seq)) {
                                	tcp_retransmit_skb(sk,
							   skb_peek(&sk->write_queue));
                                	tcp_reset_xmit_timer(sk, TIME_RETRANS, tp->rto);
				}
			} else {
				/* FACK style, fill any remaining holes in
				 * receiver's queue.
				 */
				tcp_fack_retransmit(sk);
			}
		}
	}
}

/* This is Jacobson's slow start and congestion avoidance. 
 * SIGCOMM '88, p. 328.
 */
static __inline__ void tcp_cong_avoid(struct tcp_opt *tp)
{
        if (tp->snd_cwnd <= tp->snd_ssthresh) {
                /* In "safe" area, increase. */
                tp->snd_cwnd++;
	} else {
                /* In dangerous area, increase slowly.
		 * In theory this is tp->snd_cwnd += 1 / tp->snd_cwnd
		 */
		if (tp->snd_cwnd_cnt >= tp->snd_cwnd) {
			tp->snd_cwnd++;
			tp->snd_cwnd_cnt=0;
		} else
			tp->snd_cwnd_cnt++;
        }       
}

/* Remove acknowledged frames from the retransmission queue. */
static int tcp_clean_rtx_queue(struct sock *sk, __u32 ack,
			       __u32 *seq, __u32 *seq_rtt)
{
	struct tcp_opt *tp = &(sk->tp_pinfo.af_tcp);
	struct sk_buff *skb;
	__u32 now = tcp_time_stamp;
	int acked = 0;

	/* If we are retransmitting, and this ACK clears up to
	 * the retransmit head, or further, then clear our state.
	 */
	if (tp->retrans_head != NULL &&
	    !before(ack, TCP_SKB_CB(tp->retrans_head)->end_seq))
		tp->retrans_head = NULL;

	while((skb=skb_peek(&sk->write_queue)) && (skb != tp->send_head)) {
		struct tcp_skb_cb *scb = TCP_SKB_CB(skb); 
		__u8 sacked = scb->sacked;
		
		/* If our packet is before the ack sequence we can
		 * discard it as it's confirmed to have arrived at
		 * the other end.
		 */
		if (after(scb->end_seq, ack))
			break;

		/* Initial outgoing SYN's get put onto the write_queue
		 * just like anything else we transmit.  It is not
		 * true data, and if we misinform our callers that
		 * this ACK acks real data, we will erroneously exit
		 * connection startup slow start one packet too
		 * quickly.  This is severely frowned upon behavior.
		 */
		if((sacked & TCPCB_SACKED_RETRANS) && tp->retrans_out)
			tp->retrans_out--;
		if(!(scb->flags & TCPCB_FLAG_SYN)) {
			acked |= FLAG_DATA_ACKED;
			if(sacked & TCPCB_SACKED_RETRANS)
				acked |= FLAG_RETRANS_DATA_ACKED;
			if(tp->fackets_out)
				tp->fackets_out--;
		} else {
			/* This is pure paranoia. */
			tp->retrans_head = NULL;
		}		
		tp->packets_out--;
		*seq = scb->seq;
		*seq_rtt = now - scb->when;
		__skb_unlink(skb, skb->list);
		kfree_skb(skb);
	}
	return acked;
}

static void tcp_ack_probe(struct sock *sk, __u32 ack)
{
	struct tcp_opt *tp = &(sk->tp_pinfo.af_tcp);
	
	/* Our probe was answered. */
	tp->probes_out = 0;
	
	/* Was it a usable window open? */

	/* should always be non-null */
	if (tp->send_head != NULL &&
	    !before (ack + tp->snd_wnd, TCP_SKB_CB(tp->send_head)->end_seq)) {
		tp->backoff = 0;
		tp->pending = 0;
		tcp_clear_xmit_timer(sk, TIME_PROBE0);
	} else {
		tcp_reset_xmit_timer(sk, TIME_PROBE0,
				     min(tp->rto << tp->backoff, 120*HZ));
	}
}
 
/* Should we open up the congestion window? */
static __inline__ int should_advance_cwnd(struct tcp_opt *tp, int flag)
{
	/* Data must have been acked. */
	if ((flag & FLAG_DATA_ACKED) == 0)
		return 0;

	/* Some of the data acked was retransmitted somehow? */
	if ((flag & FLAG_RETRANS_DATA_ACKED) != 0) {
		/* We advance in all cases except during
		 * non-FACK fast retransmit/recovery.
		 */
		if (tp->fackets_out != 0 ||
		    tp->retransmits != 0)
			return 1;

		/* Non-FACK fast retransmit does it's own
		 * congestion window management, don't get
		 * in the way.
		 */
		return 0;
	}

	/* New non-retransmitted data acked, always advance.  */
	return 1;
}

/* Read draft-ietf-tcplw-high-performance before mucking
 * with this code. (Superceeds RFC1323)
 */
static void tcp_ack_saw_tstamp(struct sock *sk, struct tcp_opt *tp,
			       u32 seq, u32 ack, int flag)
{
	__u32 seq_rtt;

	/* RTTM Rule: A TSecr value received in a segment is used to
	 * update the averaged RTT measurement only if the segment
	 * acknowledges some new data, i.e., only if it advances the
	 * left edge of the send window.
	 *
	 * See draft-ietf-tcplw-high-performance-00, section 3.3.
	 * 1998/04/10 Andrey V. Savochkin <[e-mail]>
	 */
	if (!(flag & FLAG_DATA_ACKED))
		return;

	seq_rtt = tcp_time_stamp - tp->rcv_tsecr;
	tcp_rtt_estimator(tp, seq_rtt);
	if (tp->retransmits) {
		if (tp->packets_out == 0) {
			tp->retransmits = 0;
			tp->fackets_out = 0;
			tp->retrans_out = 0;
			tp->backoff = 0;
			tcp_set_rto(tp);
		} else {
			/* Still retransmitting, use backoff */
			tcp_set_rto(tp);
			tp->rto = tp->rto << tp->backoff;
		}
	} else {
		tcp_set_rto(tp);
	}

	tcp_bound_rto(tp);
}

static __inline__ void tcp_ack_packets_out(struct sock *sk, struct tcp_opt *tp)
{
	struct sk_buff *skb = skb_peek(&sk->write_queue);

	/* Some data was ACK'd, if still retransmitting (due to a
	 * timeout), resend more of the retransmit queue.  The
	 * congestion window is handled properly by that code.
	 */
	if (tp->retransmits) {
		tcp_xmit_retransmit_queue(sk);
		tcp_reset_xmit_timer(sk, TIME_RETRANS, tp->rto);
	} else {
		__u32 when = tp->rto - (tcp_time_stamp - TCP_SKB_CB(skb)->when);
		if ((__s32)when < 0)
			when = 1;
		tcp_reset_xmit_timer(sk, TIME_RETRANS, when);
	}
}

/* This routine deals with incoming acks, but not outgoing ones. */
static int tcp_ack(struct sock *sk, struct tcphdr *th, 
		   u32 ack_seq, u32 ack, int len)
{
	struct tcp_opt *tp = &(sk->tp_pinfo.af_tcp);
	int flag = 0;
	u32 seq = 0;
	u32 seq_rtt = 0;

	if(sk->zapped)
		return(1);	/* Dead, can't ack any more so why bother */

	if (tp->pending == TIME_KEEPOPEN)
	  	tp->probes_out = 0;

	tp->rcv_tstamp = tcp_time_stamp;

	/* If the ack is newer than sent or older than previous acks
	 * then we can probably ignore it.
	 */
	if (after(ack, tp->snd_nxt) || before(ack, tp->snd_una))
		goto uninteresting_ack;

	/* If there is data set flag 1 */
	if (len != th->doff*4) {
		flag |= FLAG_DATA;
		tcp_delack_estimator(tp);
	}

	/* Update our send window. */

	/* This is the window update code as per RFC 793
	 * snd_wl{1,2} are used to prevent unordered
	 * segments from shrinking the window 
	 */
	if (before(tp->snd_wl1, ack_seq) ||
	    (tp->snd_wl1 == ack_seq && !after(tp->snd_wl2, ack))) {
		u32 nwin = ntohs(th->window) << tp->snd_wscale;

		if ((tp->snd_wl2 != ack) || (nwin > tp->snd_wnd)) {
			flag |= FLAG_WIN_UPDATE;
			tp->snd_wnd = nwin;

			tp->snd_wl1 = ack_seq;
			tp->snd_wl2 = ack;

			if (nwin > tp->max_window)
				tp->max_window = nwin;
		}
	}

	/* We passed data and got it acked, remove any soft error
	 * log. Something worked...
	 */
	sk->err_soft = 0;

	/* If this ack opens up a zero window, clear backoff.  It was
	 * being used to time the probes, and is probably far higher than
	 * it needs to be for normal retransmission.
	 */
	if (tp->pending == TIME_PROBE0)
		tcp_ack_probe(sk, ack);

	/* See if we can take anything off of the retransmit queue. */
	flag |= tcp_clean_rtx_queue(sk, ack, &seq, &seq_rtt);

	/* We must do this here, before code below clears out important
	 * state contained in tp->fackets_out and tp->retransmits.  -DaveM
	 */
	if (should_advance_cwnd(tp, flag))
		tcp_cong_avoid(tp);

	/* If we have a timestamp, we always do rtt estimates. */
	if (tp->saw_tstamp) {
		tcp_ack_saw_tstamp(sk, tp, seq, ack, flag);
	} else {
		/* If we were retransmiting don't count rtt estimate. */
		if (tp->retransmits) {
			if (tp->packets_out == 0) {
				tp->retransmits = 0;
				tp->fackets_out = 0;
				tp->retrans_out = 0;
			}
		} else {
			/* We don't have a timestamp. Can only use
			 * packets that are not retransmitted to determine
			 * rtt estimates. Also, we must not reset the
			 * backoff for rto until we get a non-retransmitted
			 * packet. This allows us to deal with a situation
			 * where the network delay has increased suddenly.
			 * I.e. Karn's algorithm. (SIGCOMM '87, p5.)
			 */
			if (flag & FLAG_DATA_ACKED) {
				if(!(flag & FLAG_RETRANS_DATA_ACKED)) {
					tp->backoff = 0;
					tcp_rtt_estimator(tp, seq_rtt);
					tcp_set_rto(tp);
					tcp_bound_rto(tp);
				}
			}
		}
	}

	if (tp->packets_out) {
		if (flag & FLAG_DATA_ACKED)
			tcp_ack_packets_out(sk, tp);
	} else {
		tcp_clear_xmit_timer(sk, TIME_RETRANS);
	}

	flag &= (FLAG_DATA | FLAG_WIN_UPDATE);
	if ((ack == tp->snd_una	&& tp->packets_out && flag == 0) ||
	    (tp->high_seq != 0)) {
		tcp_fast_retrans(sk, ack, flag);
	} else {
		/* Clear any aborted fast retransmit starts. */
		tp->dup_acks = 0;
	}
	/* It is not a brain fart, I thought a bit now. 8)
	 *
	 * Forward progress is indicated, if:
	 *   1. the ack acknowledges new data.
	 *   2. or the ack is duplicate, but it is caused by new segment
	 *      arrival. This case is filtered by:
	 *      - it contains no data, syn or fin.