kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

内核tcp协议栈SACK的处理tcp_sacktag_write_queue

http://simohayha.iteye.com/blog/578744

上一篇处理ack的blog中我们知道当我们接收到ack的时候，我们会判断sack段，如果包含sack段的话，我们就要进行处理。这篇blog就主要来介绍内核如何处理sack段。

SACK是包含在tcp的option中的，由于tcp的头的长度的限制，因此SACK也就是最多包含4个段，也就是32个字节。我们先来看tcp中的SACK段的表示：

1
2
3
4

struct tcp_sack_block {
	u32   start_seq; //起始序列号
	u32   end_seq;   //结束序列号
};

可以看到很简单，就是一个段的起始序列号和一个结束序列号。

前一篇blog我们知道tcp_skb_cb的sacked域也就是sack option的偏移值，而在tcp的option它的组成是由3部分组成的，第一部分为option类型，第二部分为当前option的长度，第三部分才是数据段，因此我们如果要取得SACK的段，就必须这样计算。

这里ack_skb也就是我们要处理的skbuffer。

1
2
3
4
5

//首先得到sack option的起始指针。
unsigned char *ptr = (skb_transport_header(ack_skb) +
			  TCP_SKB_CB(ack_skb)->sacked);
//加2的意思也就是加上类型和长度，这里刚好是2个字节。最终结果也就是sack option的数据段。
struct tcp_sack_block_wire *sp_wire = (struct tcp_sack_block_wire *)(ptr+2);

这里很奇怪，内核还有一个tcp_sack_block_wire类型的结构，它和tcp_sack_block是完全一样的。

而我们如果要得到当前的SACK段的个数我们要这样做:

1
2

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

这里ptr1也就是sack option的长度(字节数),而TCPOLEN_SACK_BASE为类型和长度字段的长度，因此这两个值的差也就是sack段的总长度，而这里每个段都是8个字节，因此我们右移3位就得到了它的个数，最后sack的段的长度不能大于4,因此我们要取一个最小值。

上面的结构下面这张图非常清晰的展示了，这几个域的关系：

然后我们来看SACK的处理，在内核中SACK的处理是通过tcp_sacktag_write_queue来实现的，这个函数比较长，因此这里我们分段来看。

先来看函数的原型

1
2
3

static int
tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb,
			u32 prior_snd_una)

第一个参数是当前的sock，第二个参数是要处理的skb，第三个参数是接受ack的时候的snd_una.

在看之前这里有几个重要的域要再要说明下。
1 tcp socket的sacked_out域，这个域保存了所有被sack的段的个数。
2 还有一个就是tcp_sacktag_state结构，这个结构保存了当前skb的一些信息。

1
2
3
4
5

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

3 tcp socket的highest_sack域，这个域也就是被sack确认的最大序列号的skb。

先来看第一部分，这部分的代码主要功能是初始化一些用到的值，比如sack的指针，当前有多少sack段等等，以及一些合法性校验。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

//sack段的最大个数
#define TCP_NUM_SACKS 4
......
......
	const struct inet_connection_sock *icsk = inet_csk(sk);
	struct tcp_sock *tp = tcp_sk(sk);
	//下面两句代码，前面已经分析过了，也就是取得sack的指针以及sack 数据段的指针。
	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);
	//这个数组最终会用来保存所有的SACK段。
	struct tcp_sack_block sp[TCP_NUM_SACKS];
	struct tcp_sack_block *cache;
	struct tcp_sacktag_state state;
	struct sk_buff *skb;
	//这里得到当前的sack段的个数，这段代码前面也介绍过了。
	int num_sacks = min(TCP_NUM_SACKS, (ptr[1] - TCPOLEN_SACK_BASE) >> 3);
	int used_sacks;
	//重复的sack的个数。
	int found_dup_sack = 0;
	int i, j;
	int first_sack_index;

	state.flag = 0;
	state.reord = tp->packets_out;
	//如果sack的个数为0,则我们要更新相关的域。
	if (!tp->sacked_out) {
		if (WARN_ON(tp->fackets_out))
			tp->fackets_out = 0;
	//这个函数主要更新highest_sack域。
		tcp_highest_sack_reset(sk);
	}

	//开始检测是否有重复的sack。这个函数紧接着会详细分析。
	found_dup_sack = tcp_check_dsack(sk, ack_skb, sp_wire,
					 num_sacks, prior_snd_una);
	//如果有发现，则设置flag。
	if (found_dup_sack)
		state.flag |= FLAG_DSACKING_ACK;

	//再次判断ack的序列号是否太老。
	if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
		return 0;
	//如果packets_out为0,则说明我们没有发送还没有确认的段，此时进入out，也就是错误处理。
	if (!tp->packets_out)
		goto out;

在看接下来的部分之前我们先来看tcp_highest_sack_reset和tcp_check_dsack函数，先是tcp_highest_sack_reset函数。

1
2
3
4
5

static inline void tcp_highest_sack_reset(struct sock *sk)
{
	//设置highest_sack为写队列的头。
	tcp_sk(sk)->highest_sack = tcp_write_queue_head(sk);
}

这里原因很简单，因为当sacked_out为0,则说明没有通过sack确认的段，此时highest_sack自然就指向写队列的头。
第二个是tcp_check_dsack函数，这个函数比较复杂，他主要是为了检测D-SACK,也就是重复的sack。
有关dsack的概念可以去看RFC 2883和3708.
我这里简要的提一下dsack的功能，D-SACK的功能主要是使接受者能够通过sack的块来报道接收到的重复的段，从而使发送者更好的进行拥塞控制。
这里D-SACK的判断是通过RFC2883中所描述的进行的。如果是下面两种情况，则说明收到了一个D-SACK。
1 如果SACK的第一个段所ack的区域被当前skb的ack所确认的段覆盖了一部分，则说明我们收到了一个d-sack,而代码中也就是sack第一个段的起始序列号小于snd_una。下面的图描述了这种情况：

2 如果sack的第二个段完全包含了第二个段，则说明我们收到了重复的sack，下面这张图描述了这种关系。

最后要注意的是，这里收到D-SACK后，我们需要打开当前sock d-sack的option。并设置dsack的flag。

然后我们还需要判断dsack的数据是否已经被ack完全确认过了，如果确认过了，我们就需要更新undo_retrans域，这个域表示重传的数据段的个数。

来看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

static int tcp_check_dsack(struct sock *sk, 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);
	//首先取得sack的第一个段的起始和结束序列号
	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;

	//判断D-sack,首先判断第一个条件，也就是起始序列号小于ack的序列号
	if (before(start_seq_0, TCP_SKB_CB(ack_skb)->ack_seq)) {
		//设置dsack标记。
		dup_sack = 1;
		//这里更新tcp的option的sack_ok域。
		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);
		}
	}

	//判断是否dsack的数据段完全被ack所确认。
	if (dup_sack &&
		!after(end_seq_0, prior_snd_una) &&
		after(end_seq_0, tp->undo_marker))
		//更新重传段的个数。
		tp->undo_retrans--;

	return dup_sack;
}

然后回到tcp_sacktag_write_queue，接下来这部分很简单，主要是提取sack的段到sp中，并校验每个段的合法性，然后统计一些信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//开始遍历，这里num_sacks也就是我们前面计算的sack段的个数
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;
	}

	//忽略已经确认过的段。
	if (!after(sp[used_sacks].end_seq, prior_snd_una))
		continue;
	//这个值表示我们要使用的sack的段的个数。
	used_sacks++;
}

然后接下来的代码就是排序sack的段，也就是按照序列号的大小来排序：

1
2
3
4
5
6
7
8
9
10
11
12
13

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;
		}
	}
}

然后就是cache的初始化，这里的tcp socket的recv_sack_cache域要注意，这个域保存了上一次处理的sack的段的序列号。可以看到这个域类型也是tcp_sack_block，而且大小也是4,

1
2
3
4
5
6
7
8
9
10
11
12
13

//如果sack的数据段的个数为0,则说明我们要忽略调cache，此时可以看到cache指向recv_sack_cache的末尾。
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，然后跳过空的块。
	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++;
}

然后就是开始真正处理重传队列中的skb了。

我们要知道重传队列中的skb有三种类型，分别是SACKED(S), RETRANS® 和LOST(L)，而每种类型所处理的数据包的个数分别保存在sacked_out, retrans_out 和lost_out中。

而处于重传队列的skb也就是会处于下面6中状态：

1
2
3
4
5
6
7

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

这里Tag也就是上面所说的三种类型，而InFlight也就是表示还在网络中的段的个数。

然后重传队列中的skb的状态变迁是通过下面这几种事件来触发的：

1
2
3
4
5
6
7
8
9
10
11

 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.

在进入这段代码分析之前，我们先来看几个重要的域。

tcp socket的high_seq域，这个域是我们进入拥塞控制的时候最大的发送序列号，也就是snd_nxt.

然后这里还有FACK的概念，FACK算法也就是收到的不同的SACK块之间的hole，他就认为是这些段丢失掉了。因此这里tcp socket有一个fackets_out域，这个域表示了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

	//首先取得写队列的头，以便与下面的遍历。
	skb = tcp_write_queue_head(sk);
	state.fack_count = 0;
	i = 0;

	//这里used_sacks表示我们需要处理的sack段的个数。
	while (i < used_sacks) {
		u32 start_seq = sp[i].start_seq;
		u32 end_seq = sp[i].end_seq;
		//得到是否是重复的sack
		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];

		//如果sack段的结束序列号大于将要发送的最大序列号，这个情况说明我们可能有数据丢失。因此设置丢失标记。这里可以看到也就是上面所说的事件B到达。
		if (after(end_seq, tp->high_seq))
			state.flag |= FLAG_DATA_LOST;

		//跳过一些太老的cache
		while (tcp_sack_cache_ok(tp, cache) &&
			   !before(start_seq, cache->end_seq))
			cache++;

		//如果有cache，就先处理cache的sack块。
		if (tcp_sack_cache_ok(tp, cache) && !dup_sack &&
			after(end_seq, cache->start_seq)) {

			//如果当前的段的起始序列号小于cache的起始序列号(这个说明他们之间有交叉)，则我们处理他们之间的段。
			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);
			}

			//处理剩下的块，也就是cache->end_seq和ned_seq之间的段。
			if (!after(end_seq, cache->end_seq))
				goto advance_sp;
			//是否有需要跳过处理的skb
			skb = tcp_maybe_skipping_dsack(skb, sk, next_dup,
							   &state,
							   cache->end_seq);

			/* ...tail remains todo... */
			//如果刚好等于sack处理的最大序列号，则我们需要处理这个段。
			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;
			}

			//再次检测是否有需要skip的段。
			skb = tcp_sacktag_skip(skb, sk, &state, cache->end_seq);

			//紧接着处理下一个cache。
			cache++;
			continue;
		}

		//然后处理这次新的sack段。
		if (!before(start_seq, tcp_highest_sack_seq(tp))) {
			skb = tcp_highest_sack(sk);
			if (skb == NULL)
				break;
			state.fack_count = tp->fackets_out;
		}
		skb = tcp_sacktag_skip(skb, sk, &state, start_seq);

walk:
		//处理sack的段，主要是tag赋值。
		skb = tcp_sacktag_walk(skb, sk, next_dup, &state,
					   start_seq, end_seq, dup_sack);

advance_sp:
		/* SACK enhanced FRTO (RFC4138, Appendix B): Clearing correct
		 * due to in-order walk
		 */
		if (after(end_seq, tp->frto_highmark))
			state.flag &= ~FLAG_ONLY_ORIG_SACKED;

		i++;
	}

上面的代码并不复杂，这里主要有两个函数，我们需要详细的来分析，一个是tcp_sacktag_skip，一个是tcp_sacktag_walk。

先来看tcp_sacktag_skip，我们给重传队列的skb的tag赋值时，我们需要遍历整个队列，可是由于我们有序列号，因此我们可以先确认起始的skb，然后从这个skb开始遍历，这里这个函数就是用来确认起始skb的，这里确认的步骤主要是通过start_seq来确认的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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) {
		//如果当前的skb刚好等于发送队列的头，则说明我们这个是第一个数据包，则我们直接跳出循环。
		if (skb == tcp_send_head(sk))
			break;

		//如果skb的结束序列号大于我们传递进来的序列号，则说明这个skb包含了我们sack确认的段，因此我们退出循环。
		if (after(TCP_SKB_CB(skb)->end_seq, skip_to_seq))
			break;
		//更新fack的计数。
		state->fack_count += tcp_skb_pcount(skb);
	}
	//返回skb
	return skb;
}

然后是最关键的一个函数tcp_sacktag_walk，这个函数主要是遍历重传队列，找到对应需要设置的段，然后设置tcp_cb的sacked域为TCPCB_SACKED_ACKED，这里要注意，还有一种情况就是sack确认了多个skb，这个时候我们就需要合并这些skb，然后再处理。

然后来看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

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;

	//开始遍历skb队列。
	tcp_for_write_queue_from(skb, sk) {
		//in_sack不为0的话表示当前的skb就是我们要设置标记的skb。
		int in_sack = 0;
		int dup_sack = dup_sack_in;

		if (skb == tcp_send_head(sk))
			break;

		//由于skb是有序的，因此如果某个skb的序列号大于sack段的结束序列号，我们就退出循环。
		if (!before(TCP_SKB_CB(skb)->seq, end_seq))
			break;
		//如果存在next_dup,则判断是否需要进入处理。这里就是skb的序列号小于dup的结束序列号
		if ((next_dup != NULL) &&
			before(TCP_SKB_CB(skb)->seq, next_dup->end_seq)) {
			//返回值付给in_sack,也就是这个函数会返回当前skb是否能够被sack的段确认。
			in_sack = tcp_match_skb_to_sack(sk, skb,
							next_dup->start_seq,
							next_dup->end_seq);
			if (in_sack > 0)
				dup_sack = 1;
		}

		//如果小于等于0,则尝试着合并多个skb段(主要是由于可能一个sack段确认了多个skb，这样我们尝试着合并他们)
		if (in_sack <= 0) {
			tmp = tcp_shift_skb_data(sk, skb, state,
						 start_seq, end_seq, dup_sack);
			//这里tmp就为我们合并成功的skb。
			if (tmp != NULL) {
				//如果不等，则我们从合并成功的skb重新开始处理。
				if (tmp != skb) {
					skb = tmp;
					continue;
				}

				in_sack = 0;
			} else {
				//否则我们单独处理这个skb
				in_sack = tcp_match_skb_to_sack(sk, skb,
								start_seq,
								end_seq);
			}
		}

		if (unlikely(in_sack < 0))
			break;
		//如果in_sack大于0,则说明我们需要处理这个skb了。
		if (in_sack) {
			//开始处理skb，紧接着我们会分析这个函数。
			TCP_SKB_CB(skb)->sacked = tcp_sacktag_one(skb, sk,
								  state,
								  dup_sack,
								  tcp_skb_pcount(skb));
			//是否需要更新sack处理的那个最大的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;
}

然后我们来看tcp_sacktag_one函数，这个函数用来设置对应的tag，这里所要设置的也就是tcp_cb的sacked域。我们再来回顾一下它的值：

1
2
3
4
5
6

#define TCPCB_SACKED_ACKED      0x01 /* SKB ACK'd by a SACK block    */
#define TCPCB_SACKED_RETRANS    0x02  /* SKB retransmitted        */
#define TCPCB_LOST              0x04  /* SKB is lost          */
#define TCPCB_TAGBITS           0x07  /* All tag bits         */
#define TCPCB_EVER_RETRANS      0x80  /* Ever retransmitted frame */
#define TCPCB_RETRANS     (TCPCB_SACKED_RETRANS|TCPCB_EVER_RETRANS)

如果一切都正常的话，我们最终就会设置skb的这个域为TCPCB_SACKED_ACKED，也就是已经被sack过了。

这个函数处理比较简单，主要就是通过序列号以及sacked本身的值最终来确认sacked要被设置的值。

这里我们还记得，一开始sacked是被初始化为sack option的偏移(如果是正确的sack)的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

static u8 tcp_sacktag_one(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;

	......

	//如果skb的结束序列号小于发送未确认的，则说明这个帧应当被丢弃。
	if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
		return sacked;
	//如果当前的skb还未被sack确认过，则我们才会进入处理。
	if (!(sacked & TCPCB_SACKED_ACKED)) {
		//如果是重传被sack确认的。
		if (sacked & TCPCB_SACKED_RETRANS) {
			//如果设置了lost，则我们需要修改它的tag。
			if (sacked & TCPCB_LOST) {
				sacked &= ~(TCPCB_LOST|TCPCB_SACKED_RETRANS);
				//更新lost的数据包
				tp->lost_out -= pcount;
				tp->retrans_out -= pcount;
			}
		} else {
			.......
		}
		//开始修改sacked，设置flag。
		sacked |= TCPCB_SACKED_ACKED;
		state->flag |= FLAG_DATA_SACKED;
		//增加sack确认的包的个数/
		tp->sacked_out += pcount;

		fack_count += pcount;

		//处理fack
		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;
}

最后我们来看tcp_sacktag_write_queue的最后一部分，也就是更新cache的部分。

它也就是将处理过的sack清0,没处理过的保存到cache中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//开始遍历，可以看到这里将将我们未处理的sack段的序列号清0.
for (i = 0; i < ARRAY_SIZE(tp->recv_sack_cache) - used_sacks; i++) {
		tp->recv_sack_cache[i].start_seq = 0;
		tp->recv_sack_cache[i].end_seq = 0;
	}
	//然后保存这次处理了的段。
	for (j = 0; j < used_sacks; j++)
		tp->recv_sack_cache[i++] = sp[j];

	//标记丢失的段。
	tcp_mark_lost_retrans(sk);

	tcp_verify_left_out(tp);

	if ((state.reord < tp->fackets_out) &&
		((icsk->icsk_ca_state != TCP_CA_Loss) || tp->undo_marker) &&
		(!tp->frto_highmark || after(tp->snd_una, tp->frto_highmark)))
		tcp_update_reordering(sk, tp->fackets_out - state.reord, 0);

内核tcp的ack的处理tcp_ack

http://simohayha.iteye.com/blog/572505

我们来看tcp输入对于ack，段的处理。

  • 先是ack的处理，在内核中，处理ack段是通过tcp_ack来进行的。
    这个函数主要功能是：
  • update重传队列，并基于sack来设置skb的相关buf。
  • update发送窗口。
  • 基于sack的信息或者重复ack来决定是否进入拥塞模式。
    在看之前我们要知道tcp是累积确认的。为了解决带来的缺点，我们才需要sack的。

然后我们来看几个很重要的数据结构，先是tcp_skb_cb，它其实就是表示skb中所保存的tcp的控制信息。而他是保存在skb的cb中的(这个域可以看我前面的blog）。所以这里我们经常会用TCP_SKB_CB来存取这个结构。

1

#define TCP_SKB_CB(__skb)   ((struct tcp_skb_cb *)&((__skb)->cb[0]))

这里还有一个inet_skb_parm，这个结构保存了ipoption的一些信息。

1
2
3
4
5
6
7
8
9
10
11

struct inet_skb_parm
{
	struct ip_options   opt;        /* Compiled IP options      */
	unsigned char       flags;

	#define IPSKB_FORWARDED           1
	#define IPSKB_XFRM_TUNNEL_SIZE    2
	#define IPSKB_XFRM_TRANSFORMED    4
	#define IPSKB_FRAG_COMPLETE       8
	#define IPSKB_REROUTED            16
};

然后来看tcp_skb_cb：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

struct tcp_skb_cb {
	union {
		struct inet_skb_parm    h4;
#if defined(CONFIG_IPV6) || defined (CONFIG_IPV6_MODULE)
		struct inet6_skb_parm   h6;
#endif
	} header;   /* For incoming frames      */
//这个表示当前tcp包的序列号
	__u32       seq;
//这个表示结束序列号，也就是SEQ + FIN + SYN + datalen。
	__u32       end_seq;
//主要用来计算rtt
	__u32       when;
//tcp头的flag（比如syn，fin等)，它能取的值，我们下面会介绍。
	__u8        flags;

//SACK/FACK的状态flag或者是sack option的偏移(相对于tcp头的)。我们下面会介绍
	__u8        sacked;
//ack的序列号。
	__u32       ack_seq;
};

下面就是flags所能取的值，可以看到也就是tcp头的控制位。

1
2
3
4
5
6
7
8

#define TCPCB_FLAG_FIN      0x01
#define TCPCB_FLAG_SYN      0x02
#define TCPCB_FLAG_RST      0x04
#define TCPCB_FLAG_PSH      0x08
#define TCPCB_FLAG_ACK      0x10
#define TCPCB_FLAG_URG      0x20
#define TCPCB_FLAG_ECE      0x40
#define TCPCB_FLAG_CWR      0x80

然后是sack/fack的状态标记：

1
2
3
4
5
6
7
8
9
10

//有这个域说明当前的tcpcb是被sack块确认的。
#define TCPCB_SACKED_ACKED  0x01
//表示重传的帧
#define TCPCB_SACKED_RETRANS    0x02
//丢失
#define TCPCB_LOST      0x04
#define TCPCB_TAGBITS       0x07
//重传的帧。
#define TCPCB_EVER_RETRANS  0x80
#define TCPCB_RETRANS       (TCPCB_SACKED_RETRANS|TCPCB_EVER_RETRANS)

这里要注意，当我们接收到正确的SACK后，这个域就会被初始化为sack所在的相对偏移(也就是相对于tcp头的偏移值，这样我们就能很容易得到sack option的位置). 然后是tcp_sock，这个结构保存了我们整个tcp层所需要得所有必要的信息（也就是从sock中提取出来).我们分两个部分来看这个结构，这里只看我们关注的两部分，第一部分是窗口相关的一些域。第二部分是拥塞控制的一些相关域。 先来看窗口相关的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//我们期待从另一台设备接收的下一个数据字节的序列号。
u32 rcv_nxt;
//还没有被读取的数据的序列号。
u32 copied_seq;
//当最后一次窗口update被发送之前我们的rcv_nxt.
u32 rcv_wup;
//将要发送给另一台设备的下一个数据字节的序列号。
u32 snd_nxt;
//已经发送但尚未被确认的第一个数据字节的序列号。
u32 snd_una;
//
u32 snd_sml;
//最后一次接收到ack的时间戳，主要用于keepalive
u32 rcv_tstamp;
//最后一次发送数据包的时间戳。
u32 lsndtime;
//发送窗口长度
u32 snd_wnd;
//接收窗口长度。
u32 rcv_wnd
//发送未确认的数据包的个数（或者字节数？）
u32 packets_out;
//重传的数据包的个数
u32 retrans_out;

然后是拥塞部分，看这里之前还是需要取熟悉一下tcp拥塞控制的相关概念。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//慢开始的阀值，也就是超过这个我们就要进入拥塞避免的阶段
u32  snd_ssthresh;
//发送的拥塞窗口
u32 snd_cwnd;
//这个应该是拥塞状态下所发松的数据字节数
u32 snd_cwnd_cnt;
//这里也就是cwnd的最大值
u32 snd_cwnd_clamp;
//这两个值不太理解什么意思。
u32 snd_cwnd_used;
u32 snd_cwnd_stamp;

//接收窗口打消
u32 rcv_wnd;
//tcp的发送buf数据的尾部序列号。
u32 write_seq;
//最后一次push的数据的序列号
u32 pushed_seq;
//丢失的数据包字节数
u32 lost_out;
//sack的数据包的字节数
u32 sacked_out;
//fack处理的数据包的字节数
u32 fackets_out;
u32 tso_deferred;
//计数
u32 bytes_acked;

分析完相关的数据结构我们来看函数的实现。
来看tcp_ack的代码,函数比较大，因此我们分段来看，先来看一开始的一些校验部分。
这里有一个tcp_abc也就是proc下面的可以设置的东西，这个主要是看要不要每个ack都要进行拥塞控制。

Controls Appropriate Byte Count defined in RFC3465. If set to 0 then does congestion avoid once per ACK. 1 is conservative value, and 2 is more aggressive. The default value is 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

struct inet_connection_sock *icsk = inet_csk(sk);
struct tcp_sock *tp = tcp_sk(sk);
//等待ack，也就是发送未确认的序列号。
u32 prior_snd_una = tp->snd_una;
u32 ack_seq = TCP_SKB_CB(skb)->seq;
//得到ack的序列号。
u32 ack = TCP_SKB_CB(skb)->ack_seq;
u32 prior_in_flight;
u32 prior_fackets;
int prior_packets;
int frto_cwnd = 0;

//如果ack的序列号小于发送未确认的，也就是说可能这个ack只是重传老的ack，因此我们忽略它。
if (before(ack, prior_snd_una))
	goto old_ack;

//如果ack大于snd_nxt,也就是它确认了我们还没发送的数据段，因此我们discard这个段。
if (after(ack, tp->snd_nxt))
	goto invalid_ack;
//如果ack大于发送未确认，则设置flag
if (after(ack, prior_snd_una))
	flag |= FLAG_SND_UNA_ADVANCED;

//是否设置tcp_abc，有设置的话，说明我们不需要每个ack都要拥塞避免，因此我们需要计算已经ack的字节数。
if (sysctl_tcp_abc) {
	if (icsk->icsk_ca_state < TCP_CA_CWR)
		tp->bytes_acked += ack - prior_snd_una;
	else if (icsk->icsk_ca_state == TCP_CA_Loss)
		 tp->bytes_acked += min(ack - prior_snd_una,qtp->mss_cache);
}

//得到fack的数据包的字节数
prior_fackets = tp->fackets_out;
//计算还在传输的数据段的字节数,下面会详细分析这个函数。
prior_in_flight = tcp_packets_in_flight(tp);

packets_out这个表示已经发送还没有ack的数据段的字节数(这个值不会重复加的，比如重传的话不会增加这个值）。
sakced_out :sack了的字节数。
lost_out:丢失了的字节数。
retrans_out:重传的字节数。
现在我们就对这个函数的返回值很清楚了，它也就是包含了还没有到达对方的数据段的字节数。

1
2
3
4
5
6
7
8
9

static inline unsigned int tcp_left_out(const struct tcp_sock *tp)
{
	return tp->sacked_out + tp->lost_out;
}

static inline unsigned int tcp_packets_in_flight(const struct tcp_sock *tp)
{
	return tp->packets_out - tcp_left_out(tp) + tp->retrans_out;
}

接下来这一段主要是通过判断flag(slow还是fast)来进行一些窗口的操作。有关slow_path和fast_path的区别，可以看我前面的blog。
fast_path的话很简单，我们就更新相关的域以及snd_wl1(这个域主要是用于update窗口的时候).它这里会被赋值为我们这次的数据包的序列号。然后进行拥塞控制的操作。
snd_wl1是只要我们需要更新发送窗口的话，这个值是都会被更新的。
slow_path的话，我们就需要判断要不要update窗口的大小了。以及是否要处理sack等。
在看下面的代码之前，我们先来看传递进tcp_ack这个函数中的第三个参数flag，这里我们在函数中也还会修改这个值，这个flag也就是当前的skb的类型信息。看了注释后就清楚了。可疑看到好几个都是ack的类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

//这个说明当前的输入帧包含有数据。
#define FLAG_DATA       0x01
//这个说明当前的ack是一个窗口更新的ack
#define FLAG_WIN_UPDATE     0x02
//这个ack确认了一些数据
#define FLAG_DATA_ACKED     0x04
//这个表示ack确认了一些我们重传的段。
#define FLAG_RETRANS_DATA_ACKED 0x08
//这个表示这个ack是对syn的回复。
#define FLAG_SYN_ACKED      0x10
//新的sack
#define FLAG_DATA_SACKED    0x20
//ack中包含ECE
#define FLAG_ECE        0x40
//sack检测到了数据丢失。
#define FLAG_DATA_LOST      0x80
//当更新窗口的时候不跳过RFC的检测。
#define FLAG_SLOWPATH       0x100

#define FLAG_ONLY_ORIG_SACKED   0x200
//snd_una被改变了。也就是更新了。
#define FLAG_SND_UNA_ADVANCED   0x400
//包含D-sack
#define FLAG_DSACKING_ACK   0x800
//这个不太理解什么意思。
#define FLAG_NONHEAD_RETRANS_ACKED  0x1000
//
#define FLAG_SACK_RENEGING  0x2000

//下面也就是一些组合。
#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)

然后我们来看代码，下面的代码会设置flag，也就是用上面的宏。
这里有一个很大的不同就是slow_path中，我们需要update窗口的大小，而在fast模式中，我们不需要，这个详细去看我前面的blog介绍的fast和slow的区别。fast就是最理想的情况，因此我们不需要update窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//如果不是slowpath并且ack确实是正确的序列号(必须大于snd_una).
	if (!(flag & FLAG_SLOWPATH) && after(ack, prior_snd_una)) {
//更新snd_wl1域为ack_seq;
		tcp_update_wl(tp, ack_seq);
//snd_una更新为ack也就是确认的序列号
		tp->snd_una = ack;
//更新flag域。
		flag |= FLAG_WIN_UPDATE;
//进入拥塞的操作。
		tcp_ca_event(sk, CA_EVENT_FAST_ACK);
................................
	} else {
//这个判断主要是为了判断是否输入帧包含数据。也就是ack还包含了数据，如果有的话，我们设置标记然后后面会处理。
		if (ack_seq != TCP_SKB_CB(skb)->end_seq)
			flag |= FLAG_DATA;
		else
.....................................

//然后进入更新窗口的操作。
		flag |= tcp_ack_update_window(sk, skb, ack, ack_seq);
//然后判断是否有sack段，有的话，我们进入sack段的处理。
		if (TCP_SKB_CB(skb)->sacked)
			flag |= tcp_sacktag_write_queue(sk, skb, prior_snd_una);
//判断是否有ecn标记，如果有的话，设置ecn标记。
		if (TCP_ECN_rcv_ecn_echo(tp, tcp_hdr(skb)))
			flag |= FLAG_ECE;
//进入拥塞的处理。
		tcp_ca_event(sk, CA_EVENT_SLOW_ACK);
	}

接下来这段主要工作是：
1 清理重传队列中的已经ack的段。
2 处理F-RTO。
3 判断是否是零窗口探测的回复ack。
4 检测是否要进入拥塞处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

sk->sk_err_soft = 0;
icsk->icsk_probes_out = 0;
tp->rcv_tstamp = tcp_time_stamp;
//如果发送并且没有ack的数据段的值为0,则说明这个有可能是0窗口探测的回复，因此我们进入no_queue的处理，这个我们紧接着会详细介绍。
prior_packets = tp->packets_out;
if (!prior_packets)
	goto no_queue;
//清理重传队列中的已经ack的数据段。
flag |= tcp_clean_rtx_queue(sk, prior_fackets, prior_snd_una);

//处理F-RTO
if (tp->frto_counter)
	frto_cwnd = tcp_process_frto(sk, flag);

if (before(tp->frto_highmark, tp->snd_una))
	tp->frto_highmark = 0;
//判断ack是否是可疑的。它主要是检测我们是否进入拥塞状态，或者已经处于拥塞状态。
if (tcp_ack_is_dubious(sk, flag)) {
//检测flag以及是否需要update拥塞窗口的大小。
if ((flag & FLAG_DATA_ACKED) && !frto_cwnd &&
	tcp_may_raise_cwnd(sk, flag))
//如果都为真，则更新拥塞窗口。
	tcp_cong_avoid(sk, ack, prior_in_flight);
//这里进入拥塞状态的处理(这个函数是一个非常关键的函数,等到后面详细分析拥塞的时候，会分析到)。
	tcp_fastretrans_alert(sk, prior_packets - tp->packets_out,flag);
} else {
//这里可以看到和上面相比，没有tcp_may_raise_cwnd这个，我们紧接着就会分析到。
	if ((flag & FLAG_DATA_ACKED) && !frto_cwnd)
		tcp_cong_avoid(sk, ack, prior_in_flight);
}
//是否更新neigh子系统。
if ((flag & FLAG_FORWARD_PROGRESS) || !(flag & FLAG_NOT_DUP))
	dst_confirm(sk->sk_dst_cache);

return 1;

no_queue:
//这里判断发送缓冲区是否为空，如果不为空，则我们进入判断需要重启keepalive定时器还是关闭定时器
	if (tcp_send_head(sk))
		tcp_ack_probe(sk);
	return 1;

ok，，接着来看上面略过的几个函数，先来看tcp_ack_is_dubious，这里的条件我们一个个来看
1 说明flag不能是 FLAG_NOT_DUP的， FLAG_NOT_DUP表示我们的ack不是重复的。
2 是flag是CA_ALERT,它的意思是我们是否在我们进入拥塞状态时被alert。
3 拥塞状态不能为TCP_CA_OPEN不为这个，就说明我们已经进入了拥塞状态。
可以看下面这几个宏的定义，就比较清楚了。

1
2
3
4
5

#define FLAG_ACKED  (FLAG_DATA_ACKED|FLAG_SYN_ACKED)
#define FLAG_NOT_DUP (FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED)

//收到sack则说明可能有的段丢失了。而ECE则是路由器提示我们有拥塞了。我们必须处理。
#define FLAG_CA_ALERT       (FLAG_DATA_SACKED|FLAG_ECE)

上面的任意一个为真。就说明ack是可疑的。这里起始也可以说我们就必须进入拥塞的处理了(tcp_fastretrans_alert)

1
2
3
4

static inline int tcp_ack_is_dubious(const struct sock *sk, const int flag)
{
	return (!(flag & FLAG_NOT_DUP) || (flag & FLAG_CA_ALERT) ||inet_csk(sk)->icsk_ca_state != TCP_CA_Open);
}

然后是 tcp_may_raise_cwnd，这个函数用来判断是否需要增大拥塞窗口。
1 不能有ECE flag或者发送的拥塞窗口不能大于slow start的阀值。
3 拥塞状态为RECO或者CWR.

1
2
3
4
5

static inline int tcp_may_raise_cwnd(const struct sock *sk, const int flag)
{
	const struct tcp_sock *tp = tcp_sk(sk);
	return (!(flag & FLAG_ECE) || tp->snd_cwnd < tp->snd_ssthresh) &&!((1 << inet_csk(sk)->icsk_ca_state) & (TCPF_CA_Recovery | TCPF_CA_CWR));
}

在看tcp_ack_update_window函数之前，我们先来看tcp_may_update_window，这个函数用来判断是否需要更新发送窗口。
1 新的数据已经被ack了。
2 当前的数据包的序列号大于当窗口更新的时候那个数据包的序列号。
3 当前的数据包的序列号等于窗口更新时的序列号并且新的窗口大小大于当前的发送窗口大小。这个说明对端可能已经增加了窗口的大小

1
2
3
4
5
6

static inline int tcp_may_update_window(const struct tcp_sock *tp,const u32 ack, const u32 ack_seq,const u32 nwin)
{
	return (after(ack, tp->snd_una) ||
		after(ack_seq, tp->snd_wl1) ||
		(ack_seq == tp->snd_wl1 && nwin > tp->snd_wnd));
}

然后是tcp_ack_update_window函数，这个主要用来更新发送窗口的大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

static int tcp_ack_update_window(struct sock *sk, struct sk_buff *skb, u32 ack, u32 ack_seq)
{
	struct tcp_sock *tp = tcp_sk(sk);
	int flag = 0;
	//得到窗口的大小。
	u32 nwin = ntohs(tcp_hdr(skb)->window);

	if (likely(!tcp_hdr(skb)->syn))
		nwin <<= tp->rx_opt.snd_wscale;

	//判断是否需要update窗口。
	if (tcp_may_update_window(tp, ack, ack_seq, nwin)) {
		flag |= FLAG_WIN_UPDATE;
	//更新snd_wl1
		tcp_update_wl(tp, ack_seq);
	//如果不等于，则说明我们需要更新窗口。
		if (tp->snd_wnd != nwin) {
			tp->snd_wnd = nwin;
	...................................
		}
	}

	tp->snd_una = ack;
	return flag;
}

然后是tcp_cong_avoid函数，这个函数用来实现慢开始和快重传的拥塞算法。

1
2
3
4
5
6

static void tcp_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
{
	const struct inet_connection_sock *icsk = inet_csk(sk);
	icsk->icsk_ca_ops->cong_avoid(sk, ack, in_flight);
	tcp_sk(sk)->snd_cwnd_stamp = tcp_time_stamp;
}

可以看到它主要是调用cong_avoid回调函数，而这个函数被初始化为tcp_reno_cong_avoid，我们来看这个函数，在看这个函数之前我们要知道一些慢开始和快回复的概念。这些东西随便介绍tcp的书上都有介绍的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void tcp_reno_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
{
	struct tcp_sock *tp = tcp_sk(sk);
	//是否已经到达拥塞窗口的限制。
	if (!tcp_is_cwnd_limited(sk, in_flight))
		return;
	//如果拥塞窗口还没有到达慢开始的阈值，我们就进入慢开始处理。
	if (tp->snd_cwnd <= tp->snd_ssthresh)
		tcp_slow_start(tp);

	//否则我们就要进入拥塞避免阶段。
	else if (sysctl_tcp_abc) {
	//RFC3465,只有当当前的拥塞窗口的所有段都被ack了，窗口才被允许增加。
	if (tp->bytes_acked >= tp->snd_cwnd*tp->mss_cache) {
		tp->bytes_acked -= tp->snd_cwnd*tp->mss_cache;
			if (tp->snd_cwnd < tp->snd_cwnd_clamp)
				tp->snd_cwnd++;
		}
	} else {
	//和上面处理方式类似。
		tcp_cong_avoid_ai(tp, tp->snd_cwnd);
	}
}

最后我们来看tcp_clean_rtx_queue函数，这个函数主要用于清理发送队列中已经被ack的数据段。函数比较大，我们来分段看。
这里有使用karn算法，也就是如果重传的段，则计算rto的话，不采样这次的值。
还有就是要判断是syn的ack回复，还是数据的ack回复。以及sack的判断。
首先是遍历部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

while ((skb = tcp_write_queue_head(sk)) && skb != tcp_send_head(sk)) {
	struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
	u32 acked_pcount;
	u8 sacked = scb->sacked;
	//这个说明当前的数据已经在发送未确认的段里面了。
	if (after(scb->end_seq, tp->snd_una)) {
		//这边不是很懂。
		if (tcp_skb_pcount(skb) == 1 ||
			!after(tp->snd_una, scb->seq))
			break;
		acked_pcount = tcp_tso_acked(sk, skb);
		if (!acked_pcount)
			break;
		fully_acked = 0;
	} else {
		acked_pcount = tcp_skb_pcount(skb);
	}
	//如果sack的状态有被设置重传，则我们会使用karn算法。
	if (sacked & TCPCB_RETRANS) {
		//如果标记为sack了重传段，则更新重传的计数。
		if (sacked & TCPCB_SACKED_RETRANS)
			tp->retrans_out -= acked_pcount;
		flag |= FLAG_RETRANS_DATA_ACKED;

		//都为-1，也就是后面计算rtt，不会采样这次值。
		ca_seq_rtt = -1;
		seq_rtt = -1;
			if ((flag & FLAG_DATA_ACKED) || (acked_pcount > 1))
		flag |= FLAG_NONHEAD_RETRANS_ACKED;
	} else {
		//否则根据时间戳得到对应的rtt
		ca_seq_rtt = now - scb->when;
		last_ackt = skb->tstamp;
		if (seq_rtt < 0) {
			seq_rtt = ca_seq_rtt;
		}
		if (!(sacked & TCPCB_SACKED_ACKED))
			reord = min(pkts_acked, reord);
	}
	//如果有sack的数据包被ack确认了，则我们需要减小sack的计数
	if (sacked & TCPCB_SACKED_ACKED)
		tp->sacked_out -= acked_pcount;
	if (sacked & TCPCB_LOST)
		tp->lost_out -= acked_pcount;
	//总得发送为ack的数据字节计数更新。
	tp->packets_out -= acked_pcount;
	pkts_acked += acked_pcount;
	//判断是否为syn的ack。
	if (!(scb->flags & TCPCB_FLAG_SYN)) {
		flag |= FLAG_DATA_ACKED;
	} else {
		//如果是设置标记
		flag |= FLAG_SYN_ACKED;
		tp->retrans_stamp = 0;
	}

	if (!fully_acked)
		break;
	//从写buf，unlink掉。
	tcp_unlink_write_queue(skb, sk);
	//释放内存。
	sk_wmem_free_skb(sk, skb);
	tp->scoreboard_skb_hint = NULL;
	if (skb == tp->retransmit_skb_hint)
		tp->retransmit_skb_hint = NULL;
	if (skb == tp->lost_skb_hint)
		tp->lost_skb_hint = NULL;
}

剩下的部分就是计算rtt的部分，这里就不介绍了。

git-svn

常用

1
2
3
4

1、git-svn clone your_svn_repository
2、git add/commit
3、git-svn rebase    获取中心svn repository的更新；
4、git-svn dcommit   将本地git库的修改同步到中心svn库。

git-svn默认包含在Git的安装包中，不过在Ubuntu中，git-svn是作为一个独立的Package需要额外安装的(sudo apt-get install git-svn)。安装后你就可以使用git svn xxx命令来操作中心SVN代码库了。当然如果你要使用与git svn等价的git-svn命令的话，你还需要将/usr/lib/git-core配置到你的PATH环境变量中，否则Shell会提示你无法找到 git-svn这个命令。

  • 检出一个已存在svn repository(类似于svn checkout)
    我们可以通过git-svn clone命令完成这个操作： git-svn clone your_svn_repository_url

  • 从中心服务器的svn repository获取最新更新
    这个操作可以通过"git-svn rebase"完成。注意这里用的是rebase，而不是update。update命令对于通过git-svn检出的svn repostory的git版本库是不可用的。

  • 查看提交历史日志
    这个简单，使用"git-svn log"，加上-v选项，还可以提供每次commit操作涉及的相关文件的详细信息。

  • 将本地代码同步到Svn服务器
    完成这一操作需要通过"git-svn dcommit"命令。这个命令会将你在本地使用git commit提交到本地代码库的所有更改逐一提交到svn库中。加上-n选项，则该命令不会真正执行commit到svn的操作，而是会显示会有哪些本地 变动将被commit到svn服务器。git-svn dcommit似乎不能单独提交某个本地版本的修改，而是一次批量提交所有与svn中心版本库的差异。

下面是一个git-svn的一般使用流程：

1、git-svn clone your_svn_repository；
2、修改本地代码，使用git add/commit将修改提交到本地git库；
3、定期使用git-svn rebase获取中心svn repository的更新；
4、使用git-svn dcommit命令将本地git库的修改同步到中心svn库。

冲突

使用git-svn处理代码冲突的步骤有些繁琐，不过瑕不掩瑜吧。这里用一个小例子来说明一下。

假设某svn中心库上的某个项目foo中只有一个源码文件foo.c：
* 我在使用git-svn clone检出版本时，foo.c当时只有一个commit版本信息："svn v1"；
* clone出来后，我在本地git库中修改foo.c，并通过git commit提交到本地git库中，版本为"git v1"；
* 不过与此同时另外一个同事也在修改foo.c这个文件，并已经将他的修改提交到了svn库中，版本为"svn v2"；
* 此时我使用git-svn dcommit尝试提交我的改动，git-svn提示我：
Committing to svn://10.10.1.1:80/foo …
M foo.c
事务过时: 过期: ”foo/foo.c“在事务“260-1” at /usr/lib/git-core/git-svn line 570
* 使用git-svn rebase获取svn服务器上的最新foo.c，导致与foo.c冲突，不过此时svn版本信息已经添加到本地git库中(通过git log可以查看)，git-svn rebase提示你在解决foo.c的冲突后，运行git rebase –continue完成rebase操作；
* 打开foo.c，修改代码，解决冲突；
* 执行git rebase –continue，git提示我：
You must edit all merge conflicts and then
mark them as resolved using git add
* 执行git add foo.c，告知git已完成冲突解决；
* 再次执行git rebase –continue，提示"Applying: git v1"，此时"git v1"版本又一次成功加入本地版本库，你可通过git log查看；
* 执行git-svn dcommit将foo.c的改动同步到svn中心库，到此算是完成一次冲突解决。

  • 设置忽略文件
    要忽略某些文件, 需要首先执行如下命令:
    git config –global core.excludesfile ~/.gitignore
    然后编辑 vi ~/.gitignore.
    例如: 需要忽略vim的临时文件，就写:
    .*.swp

解析pcap数据包格式(code)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268

#include <stdio.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <string.h>
#include <linux/types.h>

typedef unsigned int  bpf_u_int32;
typedef unsigned short  u_short;
typedef int bpf_int32;
typedef struct pcap_file_header {
	bpf_u_int32 magic;
	u_short version_major;
	u_short version_minor;
	bpf_int32 thiszone;
	bpf_u_int32 sigfigs;   
	bpf_u_int32 snaplen;   
	bpf_u_int32 linktype;  
}pcap_file_header;
 
typedef struct  timestamp{
	bpf_u_int32 timestamp_s;
	bpf_u_int32 timestamp_ms;
}timestamp;
 
typedef struct pcap_header{
	timestamp ts;
	bpf_u_int32 capture_len;
	bpf_u_int32 len;
 
}pcap_header;


#define ETH_ALEN 6
#define __LITTLE_ENDIAN_BITFIELD 1
#define NIPQUAD(addr) \
		((unsigned char *)&addr)[0], \
		((unsigned char *)&addr)[1], \
		((unsigned char *)&addr)[2], \
		((unsigned char *)&addr)[3]


struct ethhdr {
	unsigned char h_dest[ETH_ALEN];       /* destination eth addr */
	unsigned char h_source[ETH_ALEN];     /* source ether addr    */
	unsigned short    h_proto;                /* packet type ID field */
};

struct iphdr {
#if defined(__LITTLE_ENDIAN_BITFIELD)
	__u8  ihl:4,
			version:4;
#elif defined (__BIG_ENDIAN_BITFIELD)
	__u8  version:4,
			ihl:4;
#endif
	__u8    tos;
	__be16  tot_len;
	__be16  id;
	__be16  frag_off;
	__u8    ttl;
	__u8    protocol;
	__u16   check;
	__be32  saddr;
	__be32  daddr;
	/*The options start here. */
};

struct tcphdr {
	__u16   source;
	__u16   dest;
	__u32   seq;
	__u32   ack_seq;
#if defined(__LITTLE_ENDIAN_BITFIELD)
	__u16   res1:4,
			doff:4,
			fin:1,
			syn:1,
			rst:1,
			psh:1,
			ack:1,
			urg:1,
			ece:1,
			cwr:1;
#elif defined(__BIG_ENDIAN_BITFIELD)
	__u16   doff:4,
			res1:4,
			cwr:1,
			ece:1,
			urg:1,
			ack:1,
			psh:1,
			rst:1,
			syn:1,
			fin:1;
#endif  
	__u16   window;
	__u16   check;
	__u16   urg_ptr;
};

struct udphdr {
	__u16   source;
	__u16   dest;
	__u16   len;
	__u16   check;
};

struct icmphdr {
	__u8  type;
	__u8  code;
	__u16 checksum;
	union {
		struct {
			__u16   id;
			__u16   sequence;
		} echo;
		__u32   gateway;
		struct {
			__u16   __unused;
			__u16   mtu;
		} frag;
	} un;
};

FILE *fp1, *fp2;
__u32 flag1, flag2, seq1, seq2, ip1, ip2;
long long stime;

void printPcap(int count, void * data, struct pcap_header *ph)
{
	size_t size = ph->capture_len;
	unsigned  short iPos = 0;
	struct ethhdr *eth;
	struct iphdr *iph;
	struct tcphdr *tcph;
	struct udphdr *udph;
	struct icmphdr *icmph;
	__u8 op1, op2, type, len;
	void * data1;
	int i;
	long long dt;

	if (data==NULL) {
		return;
	}
	eth = (struct ethhdr*)(data);
	eth->h_proto = ntohs(eth->h_proto);
	//printf("Ether:\tproto = 0x%x\n", eth->h_proto);
	if (eth->h_proto == 0x0800) { // IP
		iph = (struct iphdr*)(data+sizeof(struct ethhdr));
		if (iph->protocol == IPPROTO_TCP) { // tcp
			tcph = (struct tcphdr*)(data+sizeof(struct ethhdr)+sizeof(struct iphdr));
			if (tcph->ack == 0 && tcph->syn == 1) {
				seq1 = ntohl(tcph->seq);
				ip1 = iph->saddr;
				flag1 = 1;
				stime = 1000000LL*ph->ts.timestamp_s + ph->ts.timestamp_ms;
			} else if (tcph->ack == 1 && tcph->syn == 1) {
				seq2 = ntohl(tcph->seq);
				ip2 = iph->saddr;
				flag2 = 1;
			}

			if (flag1 == 0) {
				flag1 = 1;
				seq1 = ntohl(tcph->seq)-1;
				ip1 = iph->saddr;
				stime = 1000000LL*ph->ts.timestamp_s + ph->ts.timestamp_ms;
			}
			if (flag2 == 0 && iph->saddr != ip1) {
				flag2 = 1;
				seq2 = ntohl(tcph->seq)-1;
				ip2 = iph->saddr;
			}

			dt = (1000000LL*ph->ts.timestamp_s+ph->ts.timestamp_ms) - stime;
			fprintf(fp1, "%d\t%llu\t", count, dt/1000);
			fprintf(fp1, "%d.%d.%d.%d\t%d.%d.%d.%d\t%u\t%u\t%d\t",
						NIPQUAD(iph->saddr), NIPQUAD(iph->daddr),
						(iph->saddr==ip1?ntohl(tcph->seq)-seq1:ntohl(tcph->seq)-seq2),
						(iph->saddr==ip1?ntohl(tcph->ack_seq)-seq2:ntohl(tcph->ack_seq)-seq1),
						ntohs(iph->tot_len)-iph->ihl*4-tcph->doff*4 + tcph->syn + tcph->fin);
			fprintf(fp1, "%d\t%d\t%d\t%d\t", ntohs(iph->tot_len), iph->ihl*4, tcph->doff*4, iph->ttl);
			fprintf(fp1, "%u\t%u\t%d\t%d\t%d\t",
						ntohl(tcph->seq), ntohl(tcph->ack_seq),
						tcph->ack, tcph->syn, ntohs(tcph->window));

			if (tcph->doff > 5) {
				data1 = data + sizeof(struct ethhdr)+sizeof(struct iphdr)+sizeof(struct tcphdr);
				op1 = *(__u8*)(data1);
				op2 = *(__u8*)(data1+1);
				type = *(__u8*)(data1+2);
				len = *(__u8*)(data1+3);
				//fprintf(fp1, "%u\t%u\t%u\t%u\n", op1, op2, type, len);
				if (op1 == 1 && op2 == 1 && type == 5) { // sack
					i = 4;
					while (i < len+2) {
						if (i > 4) fprintf(fp1, " ");
						fprintf(fp1, "%u-%u", ntohl(*(__u32*)(data1+i))-seq2, ntohl(*(__u32*)(data1+i+4))-seq2);
						i += 8;
					}
				}
			}
			fprintf(fp1, "\n");

		} else if (iph->protocol == IPPROTO_UDP) { // udp
			udph = (struct udphdr*)(data+sizeof(struct ethhdr)+sizeof(struct iphdr));
			//printf("UDP:\tsource=%u\tdest=%u\tlen=%d\n", ntohs(udph->source), ntohs(udph->dest), ntohs(udph->len));
		} else if (iph->protocol == IPPROTO_ICMP) { // ICMP
			icmph = (struct icmphdr*)(data+sizeof(struct ethhdr)+sizeof(struct iphdr));
			//printf("ICMP:\ttype=%u\tcode=%u\n", icmph->type, icmph->code);
		}
	}
}

#define MAX_ETH_FRAME 1514000
int main (int argc, const char * argv[])
{
	pcap_file_header  pfh;
	pcap_header  ph;
	int count=0;
	void * buff = NULL;
	int readSize=0;
	int ret = 0;
 
	 if (argc != 2) {
		 printf("uage: ./a.out pcap_filename\n");
		 return -1;
	 }
	FILE *fp = fopen(argv[1], "r");
	if (fp==NULL) {
		fprintf(stderr, "Open file %s error.", argv[1]);
		return -1;
	}
	fread(&pfh, sizeof(pcap_file_header), 1, fp);
 
	fp1 = fopen("out", "w");
	fprintf(fp1, "#ID\tTIME\tsaddr\tdaddr\tseq\tack_seq\tpayload\ttot_len\tihl\tdoff\tttl\tseq\tack_seq\tack\tsyn\twin\tSACK\n");
	buff = (void *)malloc(MAX_ETH_FRAME);
	flag1 = flag2 = 0;

	for (count=1; ; count++) {
		memset(buff,0,MAX_ETH_FRAME);
		readSize=fread(&ph, sizeof(pcap_header), 1, fp);
		if (readSize<=0) {
			break;
		}
		if (buff==NULL) {
			fprintf(stderr, "malloc memory failed.\n");
			return -1;
		}
 
		readSize=fread(buff,1,ph.capture_len, fp);
		if (readSize != ph.capture_len) {
			free(buff);
			fprintf(stderr, "pcap file parse error.\n");
			return -1;
		}
		printPcap(count, buff, &ph);

		if (feof(fp) || readSize <=0 ) {
			break;
		}
	}
	fclose(fp);
	fclose(fp1);
	return ret;
}

解析pcap数据包格式

协议是一个比较复杂的协议集，有很多专业书籍介绍。在此，我仅介绍其与编程密切相关的部分：以太网上TCP/IP协议的分层结构及其报文格式。
我们知道TCP/IP协议采用分层结构，其分层模型及协议如下表：
应　用　层 (Application) HTTP、Telnet、FTP、SMTP、SNMP
传　输　层 (Transport) TCP、UDP
网 间 网层 (Internet) IP【ARP、RARP、ICMP】
网络接口层 (Network) Ethernet、X.25、SLIP、PPP

协议采用分层结构，因此，数据报文也采用分层封装的方法。下面以应用最广泛的以太网为例说明其数据报文分层封装，如下图所示：

任何通讯协议都有独特的报文格式，TCP/IP协议也不例外。对于通讯协议编程，我们首先要清楚其报文格式。由于TCP/IP协议采用分层模型，各层都有专用的报头，以下就简单介绍以太网下TCP/IP各层报文格式。

8字节的前导用于帧同步，CRC域用于帧校验。这些用户不必关心其由网卡芯片自动添加。目的地址和源地址是指网卡的物理地址，即MAC地址，具有唯一性。帧类型或协议类型是指数据包的高级协议，如 0x0806表示ARP协议，0x0800表示IP协议等。

　　ARP/RARP（地址解析/反向地址解析）报文格式如下图：

“硬件类型”域指发送者本机网络接口类型（值“1”代表以太网）。“协议类型”域指发送者所提供/请求的高级协议地址类型（“0x0800”代表 IP协议）。“操作”域指出本报文的类型（“1”为ARP请求，“2”为ARP响应，“3”为RARP请求，“4”为RARP响应）。

　　IP数据报头格式如下图：

　　我们用单片机实现TCP/IP协议要作一些简化，不考虑数据分片和优先权。因此，在此我们不讨论服务类型和标志偏移域，只需填“0” 即可。协议“版本”为4，“头长度”单位为32Bit，“总长度”以字节为单位，表示整个IP数据报长度。“标识”是数据包的ID号，用于识别不同的IP 数据包。“生存时间” TTL是个数量及的概念，防止无用数据包一直存在网络中。一般每经过路由器时减一，因此通过TTL 可以算出数据包到达目的地所经过的路由器个数。“协议”域表示创建该数据包的高级协议类型。如 1表示ICMP协议，6表示TCP协议，17表示 UDP协议等。IP数据包为简化数据转发时间，仅采用头校验的方法，数据正确性由高层协议保证。

　　ICMP（网间网控制报文协议）协议 应用广泛。在此仅给出最常见的回应请求与应答报文格式，用户命令ping便是利用此报文来测试信宿机的可到达性。报文格式如下图所示：

　　类型0 为回应应答报文，8 为回应请求报文。整个数据包均参与检验。注意ICMP封装在IP数据包里传送。

　　UDP报文格式如下图：

　　TCP报文格式如下图：

WireShark捕获的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

		以下为物理层的数据帧概况

Frame 1 (62 bytes on wire, 62 bytes captured)           1号帧，线路62字节，实际捕获62字节
Arrival Time: Jan 21, 2008 15:17:33.910261000           捕获日期和时间
[Time delta from previous packet:0.00000 seconds]       此包与前一包的时间间隔
[Time since reference or first frame: 0.00 seconds]     此包与第1帧的间隔时间
Frame Number: 1                                         帧序号
Packet Length: 62 bytes                                 帧长度
Capture Length: 62 bytes                                捕获长度
[Frame is marked: False]                                此帧是否做了标记：否
[Protocols in frame: eth:ip:tcp]                        帧内封装的协议层次结构
[Coloring Rule Name: HTTP]                              用不同颜色染色标记的协议名称：HTTP
[Coloring Rule String: http || tcp.port == 80]          染色显示规则的字符串：


		以下为数据链路层以太网帧头部信息
Ethernet II, Src: AcerTech_5b:d4:61 (00:00:e2:5b:d4:61), Dst: Jetcell_e5:1d:0a (00:d0:2b:e5:1d:0a)
以太网协议版本II，源地址：厂名_序号（网卡地址），目的：厂名_序号（网卡地址）
 Destination: Jetcell_e5:1d:0a (00:d0:2b:e5:1d:0a)       目的：厂名_序号（网卡地址）
 Source: AcerTech_5b:d4:61 (00:00:e2:5b:d4:61)           源：厂名_序号（网卡地址）
 Type: IP (0x0800)                                       帧内封装的上层协议类型为IP（十六进制码0800）看教材70页图3.2

		以下为互联网层IP包头部信息
Internet Protocol, Src: 202.203.44.225 (202.203.44.225), Dst: 202.203.208.32 (202.203.208.32)
互联网协议，源IP地址，目的IP地址
Version: 4                                                       互联网协议IPv4
Header length: 20 bytes                                          IP包头部长度
Differentiated Services Field:0x00(DSCP 0x00:Default;ECN:0x00)   差分服务字段
Total Length: 48                                                 IP包的总长度
Identification:0x8360 (33632)                                    标志字段
Flags:                                                           标记字段（在路由传输时，是否允许将此IP包分段）
Fragment offset: 0                                               分段偏移量（将一个IP包分段后传输时，本段的标识）
Time to live: 128                                                生存期TTL
Protocol: TCP (0x06)                                             此包内封装的上层协议为TCP
Header checksum: 0xe4ce [correct]                                头部数据的校验和
Source: 202.203.44.225 (202.203.44.225)                          源IP地址
Destination: 202.203.208.32 (202.203.208.32)                     目的IP地址

		以下为传输层TCP数据段头部信息
Transmission Control Protocol, Src Port: 2764 (2764), Dst Port: http (80), Seq: 0, Len: 0   传输控制协议TCP的内容
Source port: 2764 (2764）                              源端口名称（端口号）
Destination port: http (80)                            目的端口名http（端口号80）
Sequence number: 0    (relative sequence number)       序列号（相对序列号）
Header length: 28 bytes                                头部长度
Flags: 0x02 (SYN)                                      TCP标记字段（本字段是SYN，是请求建立TCP连接）
Window size: 65535                                     流量控制的窗口大小
Checksum: 0xf73b [correct]                             TCP数据段的校验和
Options: (8 bytes)                                     可选项