kk Blog —— 通用基础

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

负数的取模运算

https://www.cnblogs.com/ppboy_dxh/archive/2011/02/18/1958175.html

在不同的语言中,对负数执行取模运算,结果有可能会是不同的。例如,(-11)%5在python中计算的结果是4,而在C(C99)中计算的结果则是-1。

truncate除法 && floor除法

 在大多数编程语言中,如果整数a不是整数b的整数倍数的话,那么a、b做除法产生的实际结果的小数部分将会被截除,这个过程称为截尾(truncation)。如果除法的结果是正数的话,那么一般的编程语言都会把结果趋零截尾,也就是说,直接把商的小数部分去除。但是如果除法的结果是负数的话,不同的语言通常采用了两种不同的截尾方法:一种是趋零截尾(truncate toward zero),另一种是趋负无穷截尾(truncate toward negative infinity);相应的,两种除法分别被称为truncate除法和floor除法。

 事实上,可以认为不管除法的结果是正是负,truncate除法都是趋零结尾;而floor除法都是趋负无穷结尾。

取模运算

 取模运算实际上是计算两数相除以后的余数。假设q是a、b相除产生的商(quotient),r是相应的余数(remainder),那么在几乎所有的计算系统中,都满足a=b*q+r,其中|r|<|a|。因此r有两个选择,一个为正,一个为负;相应的,q也有两个选择。如果a、b都是正数的话,那么一般的编程语言中,r为正数;或者如果a、b都是负数的话,一般r为负数。但是如果a、b一正一负的话,不同的语言则会根据除法的不同结果而使得r的结果也不同,并且一般r的计算方法都会满足r=a-(a/b)*b

常见语言

 (1)C/Java语言

  C/Java语言除法采用的是趋零截尾(事实上,C89对于除数或被除数之一为负数情况的结果是未定义的;C99才正式确定了趋零截尾),即truncate除法。它们的取模运算符是%,并且此运算符只接受整型操作数。一个规律是,取模运算的结果的符号与第一个操作数的符号相同(或为0)。因此(-11)%5=-11-[(-11)/5]*5=-11-(-2)*5=-1

 (2)C++语言

  C++语言的截尾方式取决于特定的机器。如果两个操作数均为正,那么取模运算的结果也为正数(或为0);如果两个操作数均为负数,那么取模运算的结果为负数(或为0);如果只有一个操作数为负数,那么取模运算的结果是取决于特定实现的。

 (3)Python语言

  Python语言除法采用的是趋负无穷截尾,即floor除法。它的取模运算符也是%,并且此运算符可以接受浮点操作数。一个类似的规律是,取模运算的结果的符号与第二个操作数的符号相同。因此(-11)%5=-11-[(-11)/5]*5=-11-(-3)*5=4

  这里需要注意的是,Python 3.x中"/“运算符的意义发生了变化,”/“产生的结果将不会再进行截尾;相应的”//“运算符的结果才会进行截尾。

seq_file

https://www.cnblogs.com/Wandererzj/archive/2012/04/16/2452209.html

1
2
3
4
5
6
7
struct seq_operations {
	void * (*start) (struct seq_file *m, loff_t *pos);
	void (*stop) (struct seq_file *m, void *v);
	void * (*next) (struct seq_file *m, void *v, loff_t *pos);
	int (*show) (struct seq_file *m, void *v);
};

seq_open

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int seq_open(struct file *file, const struct seq_operations *op)
{
    struct seq_file *p = file->private_data;

    if (!p) {
        p = kmalloc(sizeof(*p), GFP_KERNEL);
        if (!p)
            return -ENOMEM;
        file->private_data = p;
    }
    memset(p, 0, sizeof(*p));
    mutex_init(&p->lock);
    p->op = op;

    file->f_version = 0;

    file->f_mode &= ~FMODE_PWRITE;
    return 0;
}

seq_read 读取过程

正常情况下分两次完成:

第一次执行执行seq_read时:start->show->next->show…->next->show->next->stop,此时返回内核自定义缓冲区所有内容,即copied !=0,所以会有第二次读取操作

第二次执行seq_read时:由于此时内核自定义内容都返回,根据seq_file->index指示,所以执行start->stop,返回0,即copied=0,并退出seq_read操作

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
ssize_t seq_read(struct file *file, char __user *buf, size_t size, loff_t *ppos)
{
	struct seq_file *m = (struct seq_file *)file->private_data;
	size_t copied = 0;
	loff_t pos;
	size_t n;
	void *p;
	int err = 0;

	mutex_lock(&m->lock);

	...

	/* we need at least one record in buffer */
	pos = m->index;
	p = m->op->start(m, &pos);
	while (1)
	{
		err = PTR_ERR(p);
		if (!p || IS_ERR(p))
			break;
		err = m->op->show(m, p);

		if (err < 0)
			break;
		if (unlikely(err))
			m->count = 0;
		if (unlikely(!m->count)) {
			p = m->op->next(m, p, &pos);
			m->index = pos;
			continue;
		}

		if (m->count < m->size)
			goto Fill;
		m->op->stop(m, p);
		kfree(m->buf);
		m->buf = kmalloc(m->size <<= 1, GFP_KERNEL);
		if (!m->buf)
			goto Enomem;
		m->count = 0;
		m->version = 0;
		pos = m->index;
		p = m->op->start(m, &pos);
	}
	m->op->stop(m, p);
	m->count = 0;
	goto Done;
Fill:
	/* they want more? let's try to get some more */
	while (m->count < size) {
		size_t offs = m->count;
		loff_t next = pos;
		p = m->op->next(m, p, &next);
		if (!p || IS_ERR(p)) {
			err = PTR_ERR(p);
			break;
		}
		err = m->op->show(m, p);
		if (m->count == m->size || err) {
			m->count = offs;
			if (likely(err <= 0))
				break;
		}
		pos = next;
	}
	m->op->stop(m, p);
	n = min(m->count, size);
	err = copy_to_user(buf, m->buf, n);
	if (err)
		goto Efault;
	copied += n;
	m->count -= n;
	if (m->count)
		m->from = n;
	else
		pos++;
	m->index = pos;
Done:
	if (!copied)
		copied = err;   //copied = 0
	else {
		*ppos += copied;
		m->read_pos += copied;
	}
	file->f_version = m->version;
	mutex_unlock(&m->lock);
	return copied;
Enomem:
	err = -ENOMEM;
	goto Done;
Efault:
	err = -EFAULT;
	goto Done;
}

lsof

lsof查看端口被哪些程序在使用

1
2
3
4
lsof -i TCP:port -n
lsof -i UDP:port -n
lsof -i :port -n
lsof -i tcp:1521 -n

查看连接创建时间

1
2
3
4
5
6
7
8
netstat -npt | grep port
tcp        0      0 ::ffff:192.168.251.43:51520 ::ffff:192.168.110.231:8998 ESTABLISHED 32439/java  

lsof -p pid | grep port
java    32439 root  118u  IPv6          165707367      0t0       TCP SC-HOST-43:51518->192.168.110.231:8998 (ESTABLISHED) 
java    32439 root  126u  IPv6          165707404      0t0       TCP SC-HOST-43:51520->192.168.110.231:8998 (ESTABLISHED)

注意到118u和126u是这两个连接的文件名,然后去ll /proc/pid/fd/118,就可以看到这个连接的建立时间了。

查看进程启动路径

1
ls -l /proc/pid/xx

indent 代码格式化

https://www.cnblogs.com/sky-heaven/p/9012508.html

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
常用的设置:
	indent -npro -kr -i8 -ts8 -sob -l80 -ss -bl  -bli 0

参数说明:
-npro或--ignore-profile  不要读取indent的配置文件.indent.pro。
-kr  指定使用Kernighan&Ritchie的格式。
-i8  --indent-level 设置缩排的格数为8。
-ts8 设置tab的长度
-sob或--swallow-optional-blank-lines  删除多余的空白行。
-l80 代码超过80换行
-ss或--space-special-semicolon  若for区段只有一行时,在分号前加上空格。
-ncs或--no-space-after-casts  不要在cast之后空一格。
-bl {分行显示
-bli 0 括号缩进为0
功能说明:调整C原始代码文件的格式。
语  法:indent [参数][源文件] 或 indent [参数][源文件][-o 目标文件]
补充说明:indent可辨识C的原始代码文件,并加以格式化,以方便程序设计师阅读。
参  数:
 -bad或--blank-lines-after-declarations  在声明区段或加上空白行。
 -bap或--blank-lines-after-procedures  在程序或加上空白行。
 -bbb或--blank-lines-after-block-comments  在注释区段后加上空白行。
 -bc或--blank-lines-after-commas  在声明区段中,若出现逗号即换行。
 -bl或--braces-after-if-line  if(或是else,for等等)与后面执行区段的"{"不同行,且"}"自成一行。
 -bli<缩排格数>或--brace-indent<缩排格数>  设置{ }缩排的格数。
 -br或--braces-on-if-line  if(或是else,for等等)与后面执行跛段的"{"不同行,且"}"自成一行。
 -bs或--blank-before-sizeof  在sizeof之后空一格。
 -c<栏数>或--comment-indentation<栏数>  将注释置于程序码右侧指定的栏位。
 -cd<栏数>或--declaration-comment-column<栏数>  将注释置于声明右侧指定的栏位。
 -cdb或--comment-delimiters-on-blank-lines  注释符号自成一行。
 -ce或--cuddle-else  将else置于"}"(if执行区段的结尾)之后。
 -ci<缩排格数>或--continuation-indentation<缩排格数>  叙述过长而换行时,指定换行后缩排的格数。
 -cli<缩排格数>或--case-indentation-<缩排格数>  使用case时,switch缩排的格数。
 -cp<栏数>或-else-endif-column<栏数>  将注释置于else与elseif叙述右侧定的栏位。
 -cs或--space-after-cast  在cast之后空一格。
 -d<缩排格数>或-line-comments-indentation<缩排格数>  针对不是放在程序码右侧的注释,设置其缩排格数。
 -di<栏数>或--declaration-indentation<栏数>  将声明区段的变量置于指定的栏位。
 -fc1或--format-first-column-comments  针对放在每行最前端的注释,设置其格式。
 -fca或--format-all-comments  设置所有注释的格式。
 -gnu或--gnu-style.  指定使用GNU的格式,此为预设值。
 -i<格数>或--indent-level<格数>  设置缩排的格数。
 -ip<格数>或--parameter-indentation<格数>  设置参数的缩排格数。
 -kr或--k-and-r-style.  指定使用Kernighan&Ritchie的格式。
 -lp或--continue-at-parentheses  叙述过长而换行,且叙述中包含了括弧时,将括弧中的每行起始栏位内容垂直对其排列。
 -nbad或--no-blank-lines-after-declarations  在声明区段后不要加上空白行。
 -nbap或--no-blank-lines-after-procedures  在程序后不要加上空白行。
 -nbbb或--no-blank-lines-after-block-comments  在注释区段后不要加上空白行。
 -nbc或--no-blank-lines-after-commas  在声明区段中,即使出现逗号,仍旧不要换行。
 -ncdb或--no-comment-delimiters-on-blank-lines  注释符号不要自成一行。
 -nce或--dont-cuddle-else  不要将else置于"}"之后。
 -ncs或--no-space-after-casts  不要在cast之后空一格。
 -nfc1或--dont-format-first-column-comments  不要格式化放在每行最前端的注释。
 -nfca或--dont-format-comments  不要格式化任何的注释。
 -nip或--no-parameter-indentation  参数不要缩排。
 -nlp或--dont-line-up-parentheses  叙述过长而换行,且叙述中包含了括弧时,不用将括弧中的每行起始栏位垂直对其排列。
 -npcs或--no-space-after-function-call-names  在调用的函数名称之后,不要加上空格。
 -npro或--ignore-profile  不要读取indent的配置文件.indent.pro。
 -npsl或--dont-break-procedure-type  程序类型与程序名称放在同一行。
 -nsc或--dont-star-comments  注解左侧不要加上星号(*)。
 -nsob或--leave-optional-semicolon  不用处理多余的空白行。
 -nss或--dont-space-special-semicolon  若for或while区段仅有一行时,在分号前不加上空格。
 -nv或--no-verbosity  不显示详细的信息。
 -orig或--original  使用Berkeley的格式。
 -pcs或--space-after-procedure-calls  在调用的函数名称与"{"之间加上空格。
 -psl或--procnames-start-lines  程序类型置于程序名称的前一行。
 -sc或--start-left-side-of-comments  在每行注释左侧加上星号(*)。
 -sob或--swallow-optional-blank-lines  删除多余的空白行。
 -ss或--space-special-semicolon  若for或swile区段今有一行时,在分号前加上空格。
 -st或--standard-output  将结果显示在标准输出设备。
 -T  数据类型名称缩排。
 -ts<格数>或--tab-size<格数>  设置tab的长度。
 -v或--verbose  执行时显示详细的信息。
 -version  显示版本信息。

如果你不想在参数上花太多时间来研究,你也可以在你的linux下的源代码里面,也就是/usr/src/linux/scripts/Lindent,找到Lindent脚本,这个是linux内核源代码格式,你可以直接拿过来用。比如

cp /usr/src/linux/scripts/Lindent /usr/bin $Lindent test.c

Lindent脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/bin/sh
PARAM="-npro -kr -i8 -ts8 -sob -l80 -ss -ncs -cp1"
RES=`indent --version`
V1=`echo $RES | cut -d' ' -f3 | cut -d'.' -f1`
V2=`echo $RES | cut -d' ' -f3 | cut -d'.' -f2`
V3=`echo $RES | cut -d' ' -f3 | cut -d'.' -f3`
if [ $V1 -gt 2 ]; then
  PARAM="$PARAM -il0"
elif [ $V1 -eq 2 ]; then
  if [ $V2 -gt 2 ]; then
    PARAM="$PARAM -il0";
  elif [ $V2 -eq 2 ]; then
    if [ $V3 -ge 10 ]; then
      PARAM="$PARAM -il0"
    fi
  fi
fi
indent $PARAM "$@"

hybrid slow start 混合慢启动算法

https://www.jianshu.com/p/f2edbaca4f2c

传统的单纯采用指数增长的慢启动算法有一个无法避免的问题,在临界进入拥塞避免阶段时,特别是在高带宽长距离网络中,容易出现大规模丢包,进而导致大量数据包重传,也有可能出现timeout,致使网络带宽利用率下降。

Hybrid Slow Start,它在传统的慢启动算法中加入了判断机制,强制从慢启动转入拥塞避免。这里主要说说其在CUBIC中是怎么实现的。

变量介绍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define HYSTART_ACK_TRAIN      0x1 //进入拥塞避免的条件
#define HYSTART_DELAY          0x2 //进入拥塞避免的条件
#define HYSTART_MIN_SAMPLES    8   //表示至少取一个RTT的前8个ACK作为样本
#define HYSTART_DELAY_MIN      (4u<<3) 
#define HYSTART_DELAY_MAX      (16u<<3)
/* if x > HYSTART_DELAY_MAX,return HYSTART_DELAY_MAX 
 * else if x < HYSTART_DELAY_MIN,return HYATART_DELAY_MIN
 * else return x
 */
#define HYSTART_DELAY_THRESH clamp(x, HYSTART_DELAY_MIN, HYSTART_DELAY_MAX)
static int hystart __read_mostly = 1;
static int hystart_detect __read_mostly = HYSTART_ACK_TRAIN | HYSART_DELAY;
static int hystart_low_window __read_mostly = 16;
static int hystart_ack_delta __read_mostly = 2;

struct bictcp {
	...
	u32    delay_min;   //全局最小rtt
	u32    round_start; //记录慢启动的起始时间
	u32    curr_rtt;    //记录样本中的最小rtt
	u8      found;
	u8      sample_cnt; //样本计数变量
	...
};

两类退出slow start机制

在Hybrid Slow Start算法中给出了种类判断机制用来退出慢启动进入拥塞避免,分别是ACKs train length和Increase in packet delays。

ACKS train length

这里给出一段原文描述,在这段描述中说了怎么测ACKs train length以及为什么要用ACKs train length。

The ACK train length is measured by calculating the sum of inter-arrival times of all the closely spaced ACKs within an RTT round. The train length is strongly affected by the bottleneck bandwidth, routing delays and buffer sizes along the path, and is easily stretched out by congestion caused by cross traffic in the path, so by estimating the train length we can reliably find a safe exit point of Slow Start.

Increase in packet delays

同样还是一段原文描述,如果你问我为什么不直接翻译成中文,我不会回答你这个问题的。

Increase in packet delays during Slow Start may indicate the possibility of the bottleneck router being congested.

但是Increase in packet delays的测量会受到bursty transmission的影响,所以只测一个RTT中刚开始的几个数据包的往返时间来避免bursty transission的影响,在后面给出的code中会看到

函数实现

hystart重置函数

1
2
3
4
5
6
7
8
9
10
static inline void bictcp_hystart_reset(struct sock *sk)
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct bictcp *ca = inet_csk_ca(sk);

	ca->round_start = ca->last_ack = bictcp_clock(); //记录慢启动的开始时间
	ca->end_seq = tp->snd_nxt;
	ca->curr_rtt = 0;   //重置样本最小rtt为0
	ca->sample_cnt = 0; //重置样本计数为0
}

Hybrid Slow Start实现的核心部分

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
static void hystart_update(struct sock *sk, u32 delay)
{
	struct tcp_sock *tp = tcp_sk(sk);
	struct bictcp *ca = inet_csk_ca(sk);

	//如果ca->found & hystart_detect为真,表示应该进入拥塞避免
	if (!(ca->found & hystart_detect)) {
		u32 now = bictcp_clock(); //获取当前时间

		/* first detection parameter - ack-train detection */
		/* 前后到来的两个ACK的间隔时间小于hystart_ack_delta才有效 */
		if ((s32)(now - ca->last_ack) <= hystart_ack_delta) {
			ca->last_ack = now;  //更新上一个ACK到来的时间
			/* 每次慢启动时会重置round_start为0,结合前面的if条件,下面的
			 * if成立的条件是:从慢启动开始到现在经过的时间如果大于
			 * delay_min>>4,那么可以进入拥塞避免了。至于为什么选
			 * delay_min>>4这个值,鬼知道。
			 */
			if ((s32)(now - ca->round_start) > ca->delay_min >> 4)
				ca->found |= HYSTART_ACK_TRAIN;
		}   

		/* obtain the minimum delay of more than sampling packets */
		/* 如果样本计数小于HYSTART_MIN_SAMPLES(默认为8) */
		if (ca->sample_cnt < HYSTART_MIN_SAMPLES) {
			if (ca->curr_rtt == 0 || ca->curr_rtt > delay)
				ca->curr_rtt = delay;/* 更新样本中的最小rtt */

			ca->sample_cnt++;
		} else {//如果样本大于8了,那么就可以判断是否要进入拥塞避免了
			/* 如果前面8个样本中的最小rtt大于全局最小rtt与阈值的和,那么表示网络出
			 * 现了拥塞,应立马进入拥塞避免阶段,HYSTART_DELAY_THRESH()的返
			 * 回值在前面的变量介绍中有说明。
			if (ca->curr_rtt > ca->delay_min +
				HYSTART_DELAY_THRESH(ca->delay_min>>4))
				ca->found |= HYSTART_DELAY;
		}   
		/*  
		 * Either one of two conditions are met,
		 * we exit from slow start immediately.
		 */
		/* 如果为真就进入拥塞避免 */
		if (ca->found & hystart_detect)
			tp->snd_ssthresh = tp->snd_cwnd;
	}   
}