kk Blog —— 通用基础


date [-d @int|str] [+%s|"+%F %T"]
netstat -ltunp
sar -n DEV 1

TCP接收窗口的调整算法

TCP接收窗口的调整算法（上）
TCP接收窗口的调整算法（中）
TCP接收窗口的调整算法（下）

TCP接收窗口的调整算法（上）

我们知道TCP首部中有一个16位的接收窗口字段，它可以告诉对端：我现在能接收多少数据。TCP的流控制主要就是通过调整接收窗口的大小来进行的。

本文内容：分析TCP接收窗口的调整算法，包括一些相关知识和初始接收窗口的取值。

内核版本：3.2.12

数据结构

以下是涉及到的数据结构。

1
2
3
4
5
6
7
8
9
10

struct tcp_sock {  
	...  
	/* 最早接收但未确认的段的序号，即当前接收窗口的左端*/  
	u32 rcv_wup; /* rcv_nxt on last window update sent */  
	u16 advmss; /* Advertised MSS. 本端能接收的MSS上限，建立连接时用来通告对端*/  
	u32 rcv_ssthresh; /* Current window clamp. 当前接收窗口大小的阈值*/  
	u32 rcv_wnd; /* Current receiver window，当前的接收窗口大小*/  
	u32 window_clamp; /* 接收窗口的最大值，这个值也会动态调整*/  
	...  
}
1
2
3
4
5
6
7

struct tcp_options_received {  
	...  
		snd_wscale : 4, /* Window scaling received from sender, 对端接收窗口扩大因子 */  
		rcv_wscale : 4; /* Window scaling to send to receiver, 本端接收窗口扩大因子 */  
	u16 user_mss; /* mss requested by user in ioctl */  
	u16 mss_clamp; /* Maximal mss, negotiated at connection setup，对端的最大mss */  
}
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

/** 
 * struct sock - network layer representation of sockets 
 * @sk_rcvbuf: size of receive buffer in bytes 
 * @sk_receive_queue: incoming packets 
 * @sk_write_queue: packet sending queue 
 * @sk_sndbuf: size of send buffer in bytes 
 */  
struct sock {  
	...  
	struct sk_buff_head sk_receive_queue;  
	/* 表示接收队列sk_receive_queue中所有段的数据总长度*/  
#define sk_rmem_alloc sk_backlog.rmem_alloc  
  
	int sk_rcvbuf; /* 接收缓冲区长度的上限*/  
	int sk_sndbuf; /* 发送缓冲区长度的上限*/  
  
	struct sk_buff_head sk_write_queue;  
	...  
}  
  
struct sk_buff_head {  
	/* These two members must be first. */  
	struct sk_buff *next;  
	struct sk_buff *prev;  
	__u32 qlen;  
	spinlock_t lock;  
};

TCP的核心系列 — SACK和DSACK的实现

TCP的核心系列 — SACK和DSACK的实现（一）
TCP的核心系列 — SACK和DSACK的实现（二）
TCP的核心系列 — SACK和DSACK的实现（三）
TCP的核心系列 — SACK和DSACK的实现（四）
TCP的核心系列 — SACK和DSACK的实现（五）
TCP的核心系列 — SACK和DSACK的实现（六）
TCP的核心系列 — SACK和DSACK的实现（七）

TCP的核心系列 — SACK和DSACK的实现（一）

TCP的实现中，SACK和DSACK是比较重要的一部分。

SACK和DSACK的处理部分由Ilpo Järvinen (ilpo.jarvinen@helsinki.fi) 维护。

tcp_ack()处理接收到的带有ACK标志的数据段时，如果此ACK处于慢速路径，且此ACK的记分牌不为空，则调用
tcp_sacktag_write_queue()来根据SACK选项标记发送队列中skb的记分牌状态。

笔者主要分析18和37这两个版本的实现。
相对而言，18版本的逻辑清晰，但效率较低；37版本的逻辑复杂，但效率较高。

本文主要内容：18版tcp_sacktag_write_queue()的实现，也即18版SACK和DSACK的实现。

18版数据结构

1
2
3
4
5

/* 这就是一个SACK块 */
struct tcp_sack_block {
	u32 start_seq;  /* 起始序号 */
	u32 end_seq;    /* 结束序号 */
};
1
2
3
4
5
6
7
8
9
10
11
12
13

struct tcp_sock {
	...
	/* Options received (usually on last packet, some only on SYN packets). */
	struct tcp_options_received rx_opt;
	...
	struct tcp_sack_block recv_sack_cache[4]; /* 保存收到的SACK块，用于提高效率*/
	...
	/* 快速路径中使用，上次第一个SACK块的结束处，现在直接从这里开始处理 */
	struct sk_buff *fastpath_skb_hint;
	int fastpath_cnt_hint;  /* 快速路径中使用，上次记录的fack_count，现在继续累加 */
	...

};
1
2
3
4
5
6
7
8
9
10

struct tcp_options_received {
	...
	u16 saw_tstamp : 1,    /* Saw TIMESTAMP on last packet */
		tstamp_ok : 1,     /* TIMESTAMP seen on SYN packet */
		dsack : 1,         /* D-SACK is scheduled, 下一个发送段是否存在D-SACK */
		sack_ok : 4,       /* SACK seen on SYN packet, 接收方是否支持SACK */
		...
	u8 num_sacks;          /* Number of SACK blocks, 下一个发送段中SACK块数 */
	...
};

linux进程调度之FIFO和RR调度策略

http://blog.chinaunix.net/uid-24774106-id-3379478.html

严格地说，对于优先级对于实时进程和普通进程的意义是不一样的。

1、在一定程度上，实时进程优先级高，实时进程存在，就没有普通进程占用CPU的机会，（但是前一篇博文也讲过了，实时组调度出现在内核以后，允许普通进程占用少量的CPU时间,取决于配置)。

2、对于实时进程而言，高优先级的进程存在，低优先级的进程是轮不上的，没机会跑在CPU上，所谓实时进程的调度策略,指的是相同优先级之间的调度策略。如果是FIFO实时进程在占用CPU，除非出现以下事情，否则FIFO一条道跑到黑。
a）FIFO进程良心发现，调用了系统调用sched_yield 自愿让出CPU
b) 更高优先级的进程横空出世，抢占FIFO进程的CPU。有些人觉得很奇怪，怎么FIFO占着CPU，为啥还能有更高优先级的进程出现呢。别忘记，我们是多核多CPU ,如果其他CPU上出现了一个比FIFO优先级高的进程，可能会push到FIFO进程所在的CPU上。
c) FIFO进程停止（TASK_STOPPED or TASK_TRACED状态）或者被杀死（EXIT_ZOMBIE or EXIT_DEAD状态）
d) FIFO进程执行了阻塞调用并进入睡眠（TASK_INTERRUPTIBLE OR TASK_UNINTERRUPTIBLE）。

如果是进程的调度策略是时间片轮转RR，那么，除了前面提到的abcd，RR实时进程耗尽自己的时间片后，自动退到对应优先级实时队列的队尾，重新调度。

1
2
3
4
5
6
7
8

struct sched_param {
	/* ... */
	int sched_priority;
	/* ... */
};
int sched_setscheduler (pid_t pid,
				int policy,
				const struct sched_param *sp);

sched_setscheduler函数的第二个参数调度方法 ：

1
2
3
4
5
6

#define SCHED_OTHER 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#ifdef __USE_GNU
# define SCHED_BATCH 3
#endif

SCHED_OTHER表示普通进程，对于普通进程，第三个参数sp->sched_priority只能是0
SCHED_FIFO 和SCHED_RR表示实时进程的调度策略，第三个参数的取值范围为[1,99]。
如果sched_setscheduler 优先级设置的值和调度策略不符合的话，会返回失败的。

应用层和内核层的优先级含义是不同的：
首先说实时进程：实时进程的优先级设置可以通过sched_setsheduler设置，也可以通过sched_setparam设置优先级的大小。 int sched_setparam (pid_t pid, const struct sched_param *sp);

在用户层或者应用层，1表示优先级最低，99表示优先级最高。但是在内核中，[0,99]表示的实时进程的优先级，0最高，99最低。[100,139]是普通进程折腾的范围。应用层比较天真率直，就看大小，数字大，则优先级高。ps查看进程的优先级也是如此。有意思的是，应用层实时进程最高优先级的99，在ps看进程优先级的时候，输出的是139.

对于普通进程，是通过nice系统调用来调整优先级的。从内核角度讲[100,139]是普通进程的优先级的范围，100最高，139最低，默认是120。普通进程的优先级的作用和实时进程不同，普通进程优先级表示的是占的CPU时间。深入linux内核架构中提到，普通优先级越高（100最高，139最低），享受的CPU time越多，相邻的两个优先级，高一级的进程比低一级的进程多占用10%的CPU，比如内核优先级数值为120的进程要比数值是121的进程多占用10%的CPU。

内核中有一个数组：prio_to_weight[20]表示的是默认优先级120的权重，数值为1024，prio_to_weight[21]表示nice值为1，优先级为121的进程的权重，数值为820。这就到了CFS的原理了

1
2
3
4
5
6
7
8
9
10

static const int prio_to_weight[40] = {
 /* -20 */ 88761, 71755, 56483, 46273, 36291,
 /* -15 */ 29154, 23254, 18705, 14949, 11916,
 /* -10 */ 9548, 7620, 6100, 4904, 3906,
 /* -5 */ 3121, 2501, 1991, 1586, 1277,
 /* 0 */ 1024, 820, 655, 526, 423,
 /* 5 */ 335, 272, 215, 172, 137,
 /* 10 */ 110, 87, 70, 56, 45,
 /* 15 */ 36, 29, 23, 18, 15,
};

假如有1台电脑，10个人玩，怎么才公平。
1 约定好时间片，每人玩1小时，玩完后记账，张XX 1小时，谁玩的时间短，谁去玩
2 引入优先级的概念，李四有紧急情况，需要提高他玩电脑的时间，怎么办，玩1个小时，记账半小时，那么同等情况下，李四会比其他人被选中玩电脑的频率要高，就体现了这个优先级的概念。
3 王五也有紧急情况，但是以考察，不如李四的紧急，好吧，玩1个小时，记账45分钟。
4 情况有变化，听说这里有电脑，突然又来了10个人，如果按照每人玩1小时的时间片，排在最后的那哥们早就开始骂人了，怎么办？时间片动态变化，根据人数来确定时间片。人越多，每个人玩的时间越少，防止哥们老捞不着玩，耐心耗尽，开始骂人。

这个记账就是我们prio_to_weight的作用。我就不多说了，prio_to_weight[20]就是基准，玩一小时，记账一小时，数组20以前的值是特权一级，玩1小时记账20分钟之类的享有特权的，数组20之后是倒霉蛋，玩1小时，记账1.5小时之类的倒霉蛋。 CFS这种调度好在大家都能捞着玩。

对于FIFO而言，一旦sleep过后，高优先级运行，低优先级是没戏运行的，同等优先级的进程，先运行的不运行完，后运行的也没戏。
对于RR而言，高优先级的先运行，同等优先级的进程过家家，你玩完，我玩，我玩完你再玩，每个进程耗费一个时间片的时间。对于Linux，RR时间片是100ms：

1

#define DEF_TIMESLICE        (100 * HZ / 1000)