kk Blog —— 通用基础


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

nulls_hlist原理 和 tcp连接查找

1
2
3
4
5

struct proto tcp_prot = {
	...
	.slab_flags             = SLAB_DESTROY_BY_RCU,
	...
}

sk 的slab初始化的时候带上 SLAB_DESTROY_BY_RCU ，所以free(sk)只会把sk加入到slab的freelist，并不会释放内存。

这也就是为什么__inet_lookup_established里需要两次INET_MATCH。因为第一次INET_MATCH到atomic_inc_not_zero之间有可能在另一个cpu上将sk放到freelist，然后sk又被其他连接alloc拿去用了

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

__inet_lookup_established() {
	...
begin:
	sk_nulls_for_each_rcu(sk, node, &head->chain) {
		if (likely(INET_MATCH(sk, net, acookie, saddr, daddr, ports, dif))) {
			if (unlikely(!atomic_inc_not_zero(&sk->sk_refcnt)))
				goto out;
			if (unlikely(!INET_MATCH(sk, net, acookie, saddr, daddr, ports, dif))) {
				sock_gen_put(sk);
				goto begin;
			}
			goto found;
		}
	}
	...
}

https://blog.csdn.net/dog250/article/details/73013732

Linux 4.7之前TCP连接处理问题

我们已经知道，在TCP的接收主函数tcp_v4_rcv中，基于skb的元数据查找socket的过程是无锁的，查找完毕之后，会针对找到的socket结果上锁或者无锁处理，逻辑非常清晰：

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

tcp_v4_rcv(skb)
{
	sk = lockless_lookup(skb);
	if (sk.is_listener) {
// Lockless begin
		process_handshake(sk, skb);
		new_sk = build_synack_sk(skb);
		new_sk.listener = sk;
	} else if (sk.is_synrecv) {
		listener = sk.lister;
		child_sk = build_child_sk(skb, sk);
		add_sk_into_acceptq(listener, child_sk);
// Lockless end
		goto data;
	} else {
data:
		lock(sk);
		process(sk, skb);
		unlock(sk);
	}
}

这个逻辑已经臻于完美了，至少在表面上看来确实如此！

当我知道了4.7内核针对syncookie的优化之后，我便内窥了lockless_lookup内部，突破性的改进在于，4.7内核用真正的RCU callback替换了一个仅有的Atomic操作，做到了真正的无锁化查找！

看来我们都被骗了，其实所谓的lockless_lookup并不是真正的lockless，为了应景和应题，本文只讨论Listener socket，我们来看下它的逻辑：

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

lockless_lookup(skb)
{
	hash = hashfn(skb);
	hlist = listener_list[hash];
// 第一部分：#1-查找socket
begin:
	sk_nulls_for_each_rcu(sk, node, hlist) {
		if (match(skb, sk)) {
			ret = sk;
		}
	}
// 第二部分：#2-与socket重新hash并插入hlist进行互斥    
	if (get_nulls_value(node) != hash) {
		goto begin;
	}

// 第三部分：#3-与socket被释放进行互斥   
	if (ret) {
		if (!atomic_inc_not_zero(ret))
			ret = NULL;
	}

	return ret;
}

这个逻辑可以分为3个部分，我在注释中已经标明，可以看到，虽然在调用者tcp_v4_rcv看来，查找socket的操作是无锁的，然而内窥其实现逻辑之后便会发现，它其实还是在内部进行了两个轻量级的互斥操作。下面我来一个一个说。

nulls hlist互斥

由于在lockless_lookup被调用时是无锁的，所以在sk_nulls_for_each_rcu遍历过程中会出现以下情况造成遍历混乱：

这种情况下，常规的hlist是无法发现的，因为这种hlist以next为NULL视为链表的结束。不管一个node被重新hash到哪个链表，在结束的时候都会碰到NULL，此时你根本区别不出来这个NULL是不是一开始遍历开始时那个hlist冲突链表的NULL。怎么解决这个问题呢？上锁肯定是不妥的，幸亏Linux内核有一个精妙的数据结构，即nulls hlist！下面我先来简单地介绍一下这个精妙的hlist数据结构和标准的hlist有何不同。

差异：

1.nulls hlist不再以NULL结尾，而以一个大到231空间的任意值结尾

2.nulls hlist以node最低位是不是1标识是不是链表的结束

于是nulls hlist的结尾节点的next字段可以编码为高31位和低1位，如果低1位为1，那么高31位便可以取出当初存进去的任意值，是不是很精妙呢？！之所以可以这么做，原因很简单，在计算机中，Linux内核数据结构的所有的地址都是对齐存放的，因此最低1位的数据位是空闲的，当然可以借为它用了。

现在我们考虑这个nulls node的高31位存什么数据好呢？答案很明确，当然是存该hlist的hash值了，这样以下的操作一目了然：

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

init:
for (i = 0; i < INET_LHTABLE_SIZE; i++) {
	// 低1位和高31位的拼接：
	// 低1位保存1，代表结束，新节点会插入到其前面
	// 高31位保存该list的hash值
	listener_list[i].next = (1UL | (((long)i) << 1)) 
}

lookup:
hash1 = hashfn(skb);
hlist = listener_list[hash1];
sk_nulls_for_each_rcu...{
	...
}
hash2 = get_nulls_value(node);
if (hash1 != hash2) {
	// 发现结束的时候已经不在开始遍历的链表上了
	goto begin;
}
//.....

是不是很精妙呢？其实在Linux中，很多地方都用到了这个nulls hlist数据结构，我第一次看到它是在当年搞nf conntrack的时候。   以上的叙述大致解释了这个nulls hlist的精妙之处，说完了优点再看看它的问题，这个nulls hlist带啦的不断retry是一种消极尝试，非常类似顺序锁读操作，只要读冲突便一直重复，直到某次没有冲突，关于顺序锁，可以看一下read_seqbegin/read_seqretry以及write_seqlock这对夫妻和小三。   为什么需要这样？答案是，在无锁化的lookup中，必须这样！因为你取出一个node和从该node取出下一个node之间是有时间差的，你没有对这个时间差强制没有任何保护措施，这就是根本原因，所以，消极的尝试也未尝不是一个好办法。   总结下根本原因，取出node和取出下一个node之间存在race！

原子变量互斥

刚刚说完了lockless_lookup的第二部分，下面看看第三部分，atomic_inc_not_zero带来的互斥。

我们知道，在sk_nulls_for_each_rcu找到一个匹配的socket并且nulls node检查通过之后，在实际使用它之前，由于无锁化调用，会存在race，此期间可能会有别的线程将该socket释放到虚空，如何避免使用一个已经被释放的socket呢？这个很简单，操作原子计数器即可：

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

free：
if (atomic_dec_and_test(sk)) {
	// 此往后，由于已经将ref减为0，别处的inc_not_zero将失败，因此可以放心释放socket了。
	free(sk);
}

lookup：
if (ret && !atomic_inc_not_zero(ret)) {
	ret = NULL;
	goto done;
}
// 此处后，由于已经增加了ref，引用的数据将是有效数据
//...

虽然这个Atomic变量不是什么锁，但是在微观上，操作它是要锁总线的，即便在代码层面没有看到任何lock字眼，但这是指令集的逻辑。当面对ddos攻击的时候，试想同时会有多少的线程争抢这个Atomic底下的总线资源！！这是一笔昂贵的开销！

为什么非要有这么一个操作呢？答案很明确，怕取到一个被释放的socket从而导致内核数据混乱，简单点说就是怕panic。所以必然要有个原子变量来保护一下，事实证明，这么做还真不错呢。然而把问题更上一层来谈，为什么内核数据会混乱导致panic？因为取出node和使用node之间存在race，在这两个操作之间，node可能会被释放掉。这一点和上面的“取出node和取出下一个node之间存在race”是不同的。

现在发现了2个race：

1.取出node和取出下一个node之间；

2.取出node和使用node之间。

但归根结底，这两个race是同一个问题导致，那就是socket被释放(重新hash也有个先被释放的过程)！如果一个socket在被lookup期间，不允许被释放是否可以呢(你可以调用释放操作，但在此期间，你要保证数据有效)？当然可以，如何做到就是一个简单的事情了。如果能做到这一点并且真的做了，上述针对两个race的两个互斥就可以去掉了，TCP的新建连接数性能指标必然会有大幅度提升。

Linux 4.7的优化

Linux 4.7内核通过SOCK_RCU_FREE标识重构了sk_destruct的实现：

1
2
3
4
5
6
7

void sk_destruct(struct sock *sk)
{
	if (sock_flag(sk, SOCK_RCU_FREE))
		call_rcu(&sk->sk_rcu, __sk_destruct);
	else
		__sk_destruct(&sk->sk_rcu);
}

如果携带有SOCK_RCU_FREE标识，便通过RCU callback进行释放，我们知道，RCU callback的调用时机是必须经过一个grace period，而这个period通过rcu lock/unlock可以严格控制。

一切显得简单明了。Linux 4.7内核仅为Listener socket设置了SOCK_RCU_FREE标识：

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

// 创建socket
__inet_hash(...)
{
	...
	sock_set_flag(sk, SOCK_RCU_FREE);
	...
}

// 从一个Listener socket派生子socket
inet_csk_clone_lock(...)
{
	struct sock *newsk = sk_clone_lock(sk, priority);
	if (newsk) {
		...
		/* listeners have SOCK_RCU_FREE, not the children */
		sock_reset_flag(newsk, SOCK_RCU_FREE);
		...
	}
	...
}

这保证了在lockless_lookup调用中不必再担心取到错误的数据和无效的数据，前提是lockless_lookup的调用必须有rcu锁的保护。这很容易：

1
2
3
4
5

	rcu_read_lock();
	sk = lockless_lookup(skb);
	...
done:
	rcu_read_unlock();12345

当然，这个lock/unlock没有体现在tcp_v4_rcv函数里，而是体现在了ip_local_deliver_finish里。

社区patch

以下是一个社区的patch：

[PATCH v2 net-next 06/11] tcp/dccp: do not touch listener sk_refcnt under synflood

http://www.spinics.net/lists/netdev/msg371229.html

本地下载 do-not-touch-listener-sk_refcnt-under-synflood.patch

作者详细说明了取消原子变量操作后带来的收益并且携带测试结果，我想这算是令人信服的，最重要的是，它已经被合入内核了。

crash执行shell脚本

crash执行shell脚本

1
2
3
4
5

crash> kmem -S TCP > /tmp/slabinfo

[root@vm1 ~]# cat /tmp/slabinfo | grep '\[fff' | awk -F[ '{print $2}' | awk -F] '{print "sock "$1" | grep skc_portpair >> /tmp/sock"}' > /tmp/sock.sh

crash> < /tmp/sock.sh

ip tcp_metric, 链路状态历史

开关

/proc/sys/net/ipv4/tcp_no_metrics_save

命令

https://www.linux.org/docs/man8/ip-tcp_metrics.html

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

NAME
       ip-tcp_metrics - management for TCP Metrics

SYNOPSIS
       ip [ OPTIONS ] tcp_metrics { COMMAND | help }


       ip tcp_metrics { show | flush } SELECTOR

       ip tcp_metrics delete [ address ] ADDRESS

       SELECTOR := [ [ address ] PREFIX ]

EXAMPLES

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

   ip tcp_metrics show address 192.168.0.0/24
       Shows the entries for destinations from subnet

   ip tcp_metrics show 192.168.0.0/24
       The same but address keyword is optional

   ip tcp_metrics
       Show all is the default action

   ip tcp_metrics delete 192.168.0.1
       Removes the entry for 192.168.0.1 from cache.

   ip tcp_metrics flush 192.168.0.0/24
       Removes entries for destinations from subnet

   ip tcp_metrics flush all
       Removes all entries from cache

   ip -6 tcp_metrics flush all
       Removes all IPv6 entries from cache keeping the IPv4 entries.

https://blog.csdn.net/dog250/article/details/52071132

在inet_peer/tcp_metrics_hash中记录通往一个IP地址的链路状况历史的metrics信息

2.6.32版本内核

路由cache项记录了一个标准的二元组，它记如下：

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

struct rtable
{
	union
	{
		struct dst_entry    dst;
	} u;
	...
	// 以下为记录二元组的信息
	__be32            rt_dst;    /* Path destination    */
	__be32            rt_src;    /* Path source        */
	int            rt_iif;
 
	/* Info on neighbour */
	__be32            rt_gateway;
 
	/* Miscellaneous cached information */
	__be32            rt_spec_dst; /* RFC1122 specific destination */
	// peer很重要！
	struct inet_peer    *peer; /* long-living peer info */
};

注意这个peer字段，很重要！peer结构体记如下：

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

struct inet_peer
{
	/* group together avl_left,avl_right,v4daddr to speedup lookups */
	struct inet_peer    *avl_left, *avl_right;
	__be32            v4daddr;    /* peer's address */
	__u16            avl_height;
	__u16            ip_id_count;    /* IP ID for the next packet */
	struct list_head    unused;
	__u32            dtime;        /* the time of last use of not
				         * referenced entries */
	atomic_t        refcnt;
	atomic_t        rid;        /* Frag reception counter */
	__u32            tcp_ts;
	unsigned long        tcp_ts_stamp;
};

已经初见雏形了，peer里面记录了一些关于tcp的描述信息，这个可以指导TCP进行拥塞控制。我需要在peer结构体里面添加诸如init_cwnd，RTT，ssthresh之类的就好了，这些信息从哪来？从上次的连接中来，或者从所有之前的连接数据的移动指数平均而来！

在建立或者接受连接的时候，甚至在每次发送数据包的时候，都需要查找路由，然后在命中路由cache的时候，自然而然就取到了peer字段，然后就可以用peer字段里面的数据指导TCP连接了，可以说，这个数据仅仅对TCP初始拥塞控制参数有效，其后的数据还是在本连接内学习为好。

3.10内核, inet_peer结构体依然存在，只是不再用它了

路由cache在3.5之后被去除了，因此rtable也就和peer脱了钩。

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

struct rtable {
	struct dst_entry    dst;
 
	int            rt_genid;
	unsigned int        rt_flags;
	__u16            rt_type;
	__u8            rt_is_input;
	__u8            rt_uses_gateway;
 
	int            rt_iif;
 
	/* Info on neighbour */
	__be32            rt_gateway;
 
	/* Miscellaneous cached information */
	u32            rt_pmtu;
 
	struct list_head    rt_uncached;
};

inet_peer从此变成了一个独立的东西，随用随取，取到则用，取不到则罢。inet_getpeer接口非常好用，它完成以下措施：

1.如果二元组不存在，可以创建；

2.如果二元组存在，则立即取到。

这就是说，你可以调用唯一的这个接口完成查询，创建操作，至于销毁，完全靠系统的一个定时器来负责，完全不用用户操心。在认同了inet_peer框架带来的福音之后，我们再来看inet_peer结构体与2.6.32内核的不同：

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

struct inet_peer {
	/* group together avl_left,avl_right,v4daddr to speedup lookups */
	struct inet_peer __rcu    *avl_left, *avl_right;
	struct inetpeer_addr    daddr;
	__u32            avl_height;
 
	// 此为关键！
	u32            metrics[RTAX_MAX];
	u32            rate_tokens;    /* rate limiting for ICMP */
	unsigned long        rate_last;
	union {
		struct list_head    gc_list;
		struct rcu_head     gc_rcu;
	};
	/*
	 * Once inet_peer is queued for deletion (refcnt == -1), following fields
	 * are not available: rid, ip_id_count
	 * We can share memory with rcu_head to help keep inet_peer small.
	 */
	union {
		struct {
			atomic_t            rid;        /* Frag reception counter */
			atomic_t            ip_id_count;    /* IP ID for the next packet */
		};
		struct rcu_head         rcu;
		struct inet_peer    *gc_next;
	};
 
	/* following fields might be frequently dirtied */
	__u32            dtime;    /* the time of last use of not referenced entries */
	atomic_t        refcnt;
};

注意metrics字段！看看RTAX_MAX即可：

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

enum {
	RTAX_UNSPEC,
#define RTAX_UNSPEC RTAX_UNSPEC
	RTAX_LOCK,
#define RTAX_LOCK RTAX_LOCK
	RTAX_MTU,
#define RTAX_MTU RTAX_MTU
	RTAX_WINDOW,
#define RTAX_WINDOW RTAX_WINDOW
	RTAX_RTT,
#define RTAX_RTT RTAX_RTT
	RTAX_RTTVAR,
#define RTAX_RTTVAR RTAX_RTTVAR
	RTAX_SSTHRESH,
#define RTAX_SSTHRESH RTAX_SSTHRESH
	RTAX_CWND,
#define RTAX_CWND RTAX_CWND
	RTAX_ADVMSS,
#define RTAX_ADVMSS RTAX_ADVMSS
	RTAX_REORDERING,
#define RTAX_REORDERING RTAX_REORDERING
	RTAX_HOPLIMIT,
#define RTAX_HOPLIMIT RTAX_HOPLIMIT
	RTAX_INITCWND,
#define RTAX_INITCWND RTAX_INITCWND
	RTAX_FEATURES,
#define RTAX_FEATURES RTAX_FEATURES
	RTAX_RTO_MIN,
#define RTAX_RTO_MIN RTAX_RTO_MIN
	RTAX_INITRWND,
#define RTAX_INITRWND RTAX_INITRWND
	__RTAX_MAX
};
 
#define RTAX_MAX (__RTAX_MAX - 1)

几乎涵盖了大多数的TCP拥塞控制参数，这简直是荒漠甘泉！然而，然而我发现这个inet_peer框架几乎没有被调用的地方。这又是为何？这又一次在逼我重新造轮子吗？…从中，我看到了社区里面的点滴，inet_peer结构体依然存在，只是不再用它了，作为替代，作为替代一定有新的东西完成inet_peer的功能并且甚之！

3.10内核中，tcp_metrics_hash占据了主角

不同于inet_peer，在既有的3.10内核中，tcp_metrics_hash占据了主角，仔细看看这个架构，感觉还是比inet_peer好，比之更加正式。这个接口是靠以下两个维护的：

tcp_get_metrics

tcp_update_metrics

这个metrics框架也是一个类似inet_peer一样全局的信息记录，但是功能跟inet_peer有些重复。在TCP连接初始之时，调用tcp_get_metrics获取TCP拥塞参数，然后在TCP连接结束的时候，会调用tcp_update_metrics来更新metrics，这个貌似更加合理。