kk Blog —— 通用基础

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

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,这个貌似更加合理。

IPIP实现IP隧道

https://blog.csdn.net/kkdelta/article/details/39611061

IPIP实现IP隧道的简单示例

两台主机,A和B,每台主机由两块网卡,其中eth0在同一个网段,能够互相连通。

A的eth1和B的eth1分别在两个不同的网段。

A: eth0:192.168.9.5 eth1:192.168.8.5

B: eth0:192.168.9.6 eth1:192.168.10.6

A:

1
2
3
4
ip tun add lxT mode ipip remote 192.168.9.6 local 192.168.9.5
ip link set lxT up
ip add add 192.168.200.1 brd 255.255.255.255 peer 192.168.200.2 dev lxT
ip ro add 192.168.200.0/24 via 192.168.200.1

B:

1
2
3
4
ip tun add lxT mode ipip remote 192.168.9.5 local 192.168.9.6
ip link set lxT up
ip add add 192.168.200.2 brd 255.255.255.255 peer 192.168.200.1 dev lxT
ip ro add 192.168.200.0/24 via 192.168.200.2

在A机器添加路由信息,指定到192.168.10.6通过lxT

1
ip ro add 192.168.10.6/32 dev lxT

在B机器添加路由信息,指定到192.168.8.5通过lxT

1
ip ro add 192.168.8.5/32 dev lxT

这样 192.168.8.5 和 192.168.10.6 就可以相互ping通了

部分参数

ttl N 设置进入通道数据包的TTL为N。N是一个1—255之间的数字。0是一个特殊的值,表示这个数据包的TTL值是继承(inherit)的。ttl参数的缺省值是:inherit。

tos T或者dsfield T 设置进入通道数据包的TOS域,缺省是inherit。

mode MODE 设置通道模式。有效的模式包括:ipip、sit和gre。

nopmtudisc 在这个通道上禁止路径最大传输单元发现( Path MTU Discovery)。默认情况下,这个功能是打开的。注意:这个选项和固定的ttl是不兼容的,如果使用了固定的ttl参数,系统会打开路径最大传输单元发现( Path MTU Discovery)功能。

ip tunnel gw

CLIENT:

1
2
ifconfig eth1 11.0.0.20/24
route add -net 14.0.0.0/24 gw 11.0.0.1 dev eth1

RS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ifconfig eth0 192.168.1.191/24
modprobe ipip # ip tun add tunl0 mode ipip remote any local any
ip link set tunl0 mtu 1480 up
ifconfig tunl0:0 14.0.0.1/24

ip tun add tunl1 mode ipip remote 12.0.0.1 local 12.0.0.102 dev eth1          # better
#ip tun add tunl1 mode ipip remote 192.168.1.102 local 192.168.1.191 dev eth0  # upload err
ip link set tunl1 mtu 1480 up

ip rule add from 14.0.0.1 table 1
ip route add table 1 default dev tunl1

find /proc/ -name rp_filter -exec cat {} \;
find /proc/ -name rp_filter -exec sh -c "echo 0 > {}" \;

GW:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
find /proc/ -name rp_filter -exec cat {} \;
find /proc/ -name rp_filter -exec sh -c "echo 0 > {}" \;

echo 1 > /proc/sys/net/ipv4/ip_forward

modprobe ipip # ip tun add tunl0 mode ipip remote any local any
ip link set tunl0 mtu 1480 up

ip tun add tunl1 mode ipip remote 192.168.1.191 local 192.168.1.102 dev enp3s0     # better
#ip tun add tunl1 mode ipip remote 12.0.0.102 local 12.0.0.1 dev enx00e04b367c0c    # upload err?
ip link set tunl1 mtu 1480 up

ip rule add from 11.0.0.20 table 1
ip route add table 1 default dev tunl1

linux策略路由

https://blog.csdn.net/guodong1010/article/category/6149064

https://www.cnblogs.com/iceocean/articles/1594488.html

1.策略路由介绍

策略性是指对于IP包的路由是以网络管理员根据需要定下的一些策略为主要依据进行路由的。例如我们可以有这样的策略:“所有来直自网A的包,选择X路径;其他选择Y路径”,或者是“所有TOS为A的包选择路径F;其他选者路径K”。

Cisco 的网络操作系统 (Cisco IOS) 从11.0开始就采用新的策略性路由机制。而Linux是在内核2.1开始采用策略性路由机制的。策略性路由机制与传统的路由算法相比主要是引入了多路由表以及规则的概念。

2.linux方式

2.1 多路由表(multiple Routing Tables)

传统的路由算法是仅使用一张路由表的。但是在有些情形底下,我们是需要使用多路由表的。例如一个子网通过一个路由器与外界相连,路由器与外界有两条线路相连,其中一条的速度比较快,一条的速度比较慢。对于子网内的大多数用户来说对速度并没有特殊的要求,所以可以让他们用比较慢的路由;但是子网内有一些特殊的用户却是对速度的要求比较苛刻,所以他们需要使用速度比较快的路由。如果使用一张路由表上述要求是无法实现的,而如果根据源地址或其它参数,对不同的用户使用不同的路由表,这样就可以大大提高路由器的性能。

2.2 规则(rule)

规则是策略性的关键性的新的概念。我们可以用自然语言这样描述规则,例如我门可以指定这样的规则:

规则一:“所有来自192.16.152.24的IP包,使用路由表10,本规则的优先级别是1500”

规则二:“所有的包,使用路由表253,本规则的优先级别是32767”

我们可以看到,规则包含3个要素:

什么样的包,将应用本规则(所谓的SELECTOR,可能是filter更能反映其作用);

符合本规则的包将对其采取什么动作(ACTION),例如用那个表;

本规则的优先级别。优先级别越高的规则越先匹配(数值越小优先级别越高)。

3. linux策略路由配置方式

传统的linux下配置路由的工具是route,而实现策略性路由配置的工具是iproute2工具包。

3.1 接口地址的配置 IP Addr

对于接口的配置可以用下面的命令进行:

1
Usage: ip addr [ add | del ] IFADDR dev STRING

例如:

1
router># ip addr add 192.168.0.1/24 broadcast 192.168.0.255 label eth0 dev eth0

上面表示,给接口eth0赋予地址192.168.0.1 掩码是255.255.255.0(24代表掩码中1的个数),广播地址是192.168.0.255

3.2 路由的配置 IP Route

Linux最多可以支持255张路由表,其中有3张表是内置的:

1
2
3
4
5
6
7
  表255 本地路由表(Local table)本地接口地址,广播地址,已及NAT地址都放在这个表。该路由表由系统自动维护,管理员不能直接修改。

  表254 主路由表(Main table)如果没有指明路由所属的表,所有的路由都默认都放在这个表里,一般来说,旧的路由工具(如route)所添加的路由都会加到这个表。一般是普通的路由。

  表253 默认路由表(Default table)一般来说默认的路由都放在这张表,但是如果特别指明放的也可以是所有的网关路由。

  表 0 保留

路由配置命令的格式如下:

Usage: ip route list SELECTOR
1
ip route { change | del | add | append | replace | monitor } ROUTE

如果想查看路由表的内容,可以通过命令:

1
ip route list table table_number

对于路由的操作包括change、del、add 、append 、replace 、 monitor这些。例如添加路由可以用:

1
2
router># ip route add 0/0 via 192.168.0.4 table main
router># ip route add 192.168.3.0/24 via 192.168.0.3 table 1

第一条命令是向主路由表(main table)即表254添加一条路由,路由的内容是设置192.168.0.4成为网关。

第二条命令代表向路由表1添加一条路由,子网192.168.3.0(子网掩码是255.255.255.0)的网关是192.168.0.3。

在多路由表的路由体系里,所有的路由的操作,例如网路由表添加路由,或者在路由表里寻找特定的路由,需要指明要操作的路由表,所有没有指明路由表,默认是对主路由表(表254)进行操作。而在单表体系里,路由的操作是不用指明路由表的。

3.3 规则的配置 IP Rule

在Linux里,总共可以定义232个优先级的规则,一个优先级别只能有一条规则,即理论上总共可以有条规则。其中有3个规则是默认的。命令用法如下:

1
2
3
4
5
6
7
8
9
10
Usage: ip rule [ list | add | del ] SELECTOR ACTION

SELECTOR := [ from PREFIX ] [ to PREFIX ] [ tos TOS ]
	[ dev STRING ] [ pref NUMBER ]

ACTION := [ table TABLE_ID ] [ nat ADDRESS ]
	[ prohibit | reject | unreachable ]
	[ flowid CLASSID ]

TABLE_ID := [ local | main | default | new | NUMBER

首先我们可以看看路由表默认的所有规则:

1
2
3
4
root@netmonster# ip rule list
0: from all lookup local
32766: from all lookup main
32767: from all lookup default

规则0,它是优先级别最高的规则,规则规定,所有的包,都必须首先使用local表(254)进行路由。本规则不能被更改和删除。

规则32766,规定所有的包,使用表main进行路由。本规则可以被更改和删除。

规则32767,规定所有的包,使用表default进行路由。本规则可以被更改和删除。

在默认情况下进行路由时,首先会根据规则0在本地路由表里寻找路由,如果目的地址是本网络,或是广播地址的话,在这里就可以找到合适的路由;如果路由失败,就会匹配下一个不空的规则,在这里只有32766规则,在这里将会在主路由表里寻找路由;如果失败,就会匹配32767规则,即寻找默认路由表。如果失败,路由将失败。重这里可以看出,策略性路由是往前兼容的。

还可以添加规则:

1
2
router># ip rule add [from 0/0] table 1 pref 32800
router >#ip rule add from 192.168.3.112/32 [tos 0x10] table 2 pref 1500prohibit

第一条命令将向规则链增加一条规则,规则匹配的对象是所有的数据包,动作是选用路由表1的路由,这条规则的优先级是32800。

第二条命令将向规则链增加一条规则,规则匹配的对象是IP为192.168.3.112,tos等于0x10的包,使用路由表2,这条规则的优先级是1500,动作是。添加以后,我们可以看看系统规则的变化。

1
2
3
4
5
6
router># ip rule
0: from all lookup local
1500 from 192.168.3.112/32 [tos 0x10] lookup 2
32766: from all lookup main
32767: from all lookup default
32800: from all lookup 1

上面的规则是以源地址为关键字,作为是否匹配的依据的。除了源地址外,还可以用以下的信息:

From – 源地址

To – 目的地址(这里是选择规则时使用,查找路由表时也使用)

Tos – IP包头的TOS(type of sevice)域

Dev – 物理接口

Fwmark – 防火墙参数

采取的动作除了指定表,还可以指定下面的动作:

Table 指明所使用的表

Nat 透明网关

Action prohibit 丢弃该包,并发送 COMM.ADM.PROHIITED的ICMP信息

Reject 单纯丢弃该包

Unreachable丢弃该包,并发送 NET UNREACHABLE的ICMP信息

4.策略路由的应用

4.1 基于源地址选路( Source-Sensitive Routing)

如果一个网络通过两条线路接入互联网,一条是比较快的ADSL,另外一条是比较慢的普通的调制解调器。这样的话,网络管理员既可以提供无差别的路由服务,也可以根据源地址的不同,使一些特定的地址使用较快的线路,而普通用户则使用较慢的线路,即基于源址的选路。

4.2 根据服务级别选路( Quality of Service)

网络管理员可以根据IP报头的服务级别域,对于不同的服务要求可以分别对待对于传送速率、吞吐量以及可靠性的有不同要求的数据报根据网络的状况进行不同的路由。

4.3 节省费用的应用

网络管理员可以根据通信的状况,让一些比较大的阵发性通信使用一些带宽比较高但是比较贵的路径一段短的时间,然后让基本的通信继续使用原来比较便宜的基本线路。例如,管理员知道,某一台主机与一个特定的地址通信通常是伴随着大量的阵发性通信的,那么网络管理员可以安排一些策略,使得这些主机使用特别的路由,这些路由是按需拨号,带宽比较高的线路,通信完成以后就停止使用,而普通的通信则不受影响。这样既提高网络的性能,又能节省费用。

4.4 负载平衡(Load Sharing)

根据网络交通的特征,网络管理员可以在不同的路径之间分配负荷实现负载平衡。

5 linux下策略路由的实现

在Linux下,策略性路由是由RPDB实现的。对于RPDB的内部机制的理解,可以加深对于策略性路由使用的理解。文件主要包含:

1
2
3
4
5
fib_hash.c
fib_rules.c
fib_sematic
fib_frontend.c
route.c

RDPB主要由多路由表和规则组成。路由表以及对其的操作和其对外的接口是整个RPDB的核心部分。路由表主要由table,zone,node这些主要的数据结构构成。对路由表的操作主要包含物理的操作以及语义的操作。路由表除了向IP层提供路由寻找的接口以外还必须与几个元素提供接口:与用户的接口(即更改路由)、proc的接口、IP层控制接口、以及和硬件的接口(网络接口的改变会导致路由表内容的改变)。处在RDPB的中心的规则,由规则选取表。IP层并不直接使用路由表,而是通过一个路由适配层,路由适配层提供为IP层提供高性能的路由服务。

5.1 路由表(Fib Table)

数据结构:

在整个策略性路由的框架里,路由表是最重要的的数据结构,我们在上面以及对路由表的概念和结构进行了清楚的说明。Linux里通过下面这些主要的数据结构进行实现的。

1
2
3
4
5
6
7
主要数据结构       作用          位置
struct fib_table  路由表           ip_fib.h 116
struct fn_hash        路由表的哈希数据    fib_hash.c 104
struct fn_zone        zone域         fib_hash.c 85
struct fib_node       路由节点        fib_hash.c 68
struct fib_info       路由信息        ip_fib.h 57
struct fib_result 路由结果        ip_fib.h 86

数据结构之间的主要关系如下。路由表由路由表号以及路由表的操作函数指针还有表数据组成。这里需要注意的是,路由表结构里并不直接定义zone域,而是通过一个数据指针指向fn_hash。只有当zone里有数据才会连接到fn_zone_list里。

系统的所有的路由表由数组变量*fib_tables[RT_TABLE_MAX+1]维护,其中系统定义RT_TABLE_MAX为254,也就是说系统最大的路由表为255张,所有的路由表的操作都是对这个数组进行的。。同时系统还定义了三长路由表*local_table; *main_table

路由表的操作:

Linux策略路由代码的主要部分是对路由表的操作。对于路由表的操作,物理操作是直观的和易于理解的。对于表的操作不外乎就是添加、删除、更新等的操作。还有一种操作,是所谓的语义操作,语义操作主要是指诸如计算下一条的地址,把节点转换为路由项,寻找指定信息的路由等。

1、物理操作(operation):

路由表的物理操作主要包括如下这些函数:

路由标操作实现函数 位置

新建路由表

删除路由表

搜索路由 fn_hash_lookup fib_hash.c 269

插入路由到路由表 fn_hash_insert fib_hash.c 341

删除路由表的路由 fn_hash_delete

fn_hash_dump

fib_hash.c 433

fib_hash.c 614

更新路由表的路由 fn_hash_flush fib_hash.c 729

显示路由表的路由信息 fn_hash_get_info fib_hash.c 750

选择默认路由 fn_hash_select_default fib_hash.c 842

2、语义操作(semantics operation):

语义操作并不涉及路由表整体框架的理解,而且,函数名也是不言自明的,所以请大家参考fib_semantics.c。

3、接口(front end)

对于路由表接口的理解,关键在于理解那里有

IP

首先是路由表于IP层的接口。路由在目前linux的意义上来说,最主要的还是IP层的路由,所以和IP层的的接口是最主要的接口。和ip层的衔接主要是向IP层提供寻找路由、路由控制、寻找指定ip的接口。

Fil_lookup

ip_rt_ioctl fib_frontend.c 286;“ f

ip_dev_find 145

Inet

路由表还必须提供配置接口,即用户直接操作路由的接口,例如增加和删除一条路由。当然在策略性路由里,还有规则的添加和删除。

inet_rtm_delroute 351

inet_rtm_newroute 366

inet_check_attr 335

proc

在 /proc/net/route 里显示路由信息。

fib_get_procinfo

4、网络设备(net dev event)

路由是和硬件关联的,当网络设备启动或关闭的时候,必须通知路由表的管理程序,更新路由表的信息。

fib_disable_ip 567

fib_inetaddr_event 575

fib_netdev_event

5、内部维护( magic)

上面我们提到,本地路由表(local table)的维护是由系统自动进行的。也就是说当用户为硬件设置IP地址等的时候,系统自动在本地路由表里添加本地接口地址以及广播地址。

fib_magic 417

fib_add_ifaddr 459

fib_del_ifaddr 498

Rule

1、数据结构

规则在fib_rules.c的52行里定义为 struct fib_rule。而RPDB里所有的路由是保存在101行的变量fib_rules里的,注意这个变量很关键,它掌管着所有的规则,规则的添加和删除都是对这个变量进行的。

2、系统定义规则:

fib_rules被定义以后被赋予了三条默认的规则:默认规则,本地规则以及主规则。

u 本地规则local_rule

1
2
3
4
5
6
static struct fib_rule local_rule = {
	r_next: &main_rule, /*下一条规则是主规则*/
	r_clntref: ATOMIC_INIT(2),
	r_table: RT_TABLE_LOCAL, /*指向本地路由表*/
	r_action: RTN_UNICAST, /*动作是返回路由*/
};

u 主规则main_rule

1
2
3
4
5
6
7
static struct fib_rule main_rule = {
	r_next: &default_rule,/*下一条规则是默认规则*/
	r_clntref: ATOMIC_INIT(2),
	r_preference: 0x7FFE, /*默认规则的优先级32766*/
	r_table: RT_TABLE_MAIN, /*指向主路由表*/
	r_action: RTN_UNICAST, /*动作是返回路由*/
};

u 默认规则default rule

1
2
3
4
5
6
static struct fib_rule default_rule = {
	r_clntref: ATOMIC_INIT(2),
	r_preference: 0x7FFF,/*默认规则的优先级32767*/
	r_table: RT_TABLE_DEFAULT,/*指默认路由表*/
	r_action: RTN_UNICAST,/*动作是返回路由*/
};

规则链的链头指向本地规则。

RPDB的中心函数fib_lookup

现在到了讨论RPDB的实现的的中心函数fib_lookup了。RPDB通过提供接口函数fib_lookup,作为寻找路由的入口点,在这里有必要详细讨论这个函数,下面是源代码:,

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
310 int fib_lookup(const struct rt_key *key, struct fib_result *res)
311 {
312   int err;
313   struct fib_rule *r, *policy;
314   struct fib_table *tb;
315
316   u32 daddr = key->dst;
317   u32 saddr = key->src;
318
321   read_lock(&fib_rules_lock);
322   for (r = fib_rules; r; r=r->r_next) {/*扫描规则链fib_rules里的每一条规则直到匹配为止*/
323       if (((saddr^r->r_src) & r->r_srcmask) ||
324           ((daddr^r->r_dst) & r->r_dstmask) ||
325 #ifdef CONFIG_IP_ROUTE_TOS
326           (r->r_tos && r->r_tos != key->tos) ||
327 #endif
328 #ifdef CONFIG_IP_ROUTE_FWMARK
329           (r->r_fwmark && r->r_fwmark != key->fwmark) ||
330 #endif
331           (r->r_ifindex && r->r_ifindex != key->iif))
332       continue;/*以上为判断规则是否匹配,如果不匹配则扫描下一条规则,否则继续*/
335       switch (r->r_action) {/*好了,开始处理动作了*/
336       case RTN_UNICAST:/*没有设置动作*/
337       case RTN_NAT: /*动作nat ADDRESS*/
338           policy = r;
339           break;
340       case RTN_UNREACHABLE: /*动作unreachable*/
341           read_unlock(&fib_rules_lock);
342           return -ENETUNREACH;
343       default:
344           case RTN_BLACKHOLE:/* 动作reject */
345           read_unlock(&fib_rules_lock);
346           return -EINVAL;
347       case RTN_PROHIBIT:/* 动作prohibit */
348           read_unlock(&fib_rules_lock);
349           return -EACCES;
350       }
351       /*选择路由表*/
352       if ((tb = fib_get_table(r->r_table)) == NULL)
353           continue;
		/*在路由表里寻找指定的路由*/
354       err = tb->tb_lookup(tb, key, res);
355       if (err == 0) {/*命中目标*/
356           res->r = policy;
357           if (policy)
358               atomic_inc(&policy->r_clntref);
359           read_unlock(&fib_rules_lock);
360           return 0;
361       }
362       if (err < 0 && err != -EAGAIN) {/*路由失败*/
363           read_unlock(&fib_rules_lock);
364           return err;
365       }
366   }
368   read_unlock(&fib_rules_lock);
369   return -ENETUNREACH;
370 }

上面的这段代码的思路是非常的清晰的。首先程序从优先级高到低扫描所有的规则,如果规则匹配,处理该规则的动作。如果是普通的路由寻址或者是nat地址转换的换,首先从规则得到路由表,然后对该路由表进行操作。这样RPDB终于清晰的显现出来了。

5.2 IP层路由适配(IP route)

路由表以及规则组成的系统,可以完成路由的管理以及查找的工作,但是为了使得IP层的路由工作更加的高效,linux的路由体系里,route.c里完成大多数IP层与RPDB的适配工作,以及路由缓冲(route cache)的功能。

调用接口

IP层的路由接口分为发送路由接口以及接收路由接口:

发送路由接口

IP层在发送数据时如果需要进行路由工作的时候,就会调用ip_route_out函数。这个函数在完成一些键值的简单转换以后,就会调用ip_route_output_key函数,这个函数首先在缓存里寻找路由,如果失败就会调用ip_route_output_slow,ip_route_output_slow里调用fib_lookup在路由表里寻找路由,如果命中,首先在缓存里添加这个路由,然后返回结果。

ip_route_out route.h

ip_route_output_key route.c 1984;

ip_route_output_slow route.c 1690;"

接收路由接口

IP层接到一个数据包以后,如果需要进行路由,就调用函数ip_route_input,ip_route_input现在缓存里寻找,如果失败则ip_route_inpu调用ip_route_input_slow, ip_route_input_slow里调用fib_lookup在路由表里寻找路由,如果命中,首先在缓存里添加这个路由,然后返回结果。

ip_route_input_slow route.c 1312;“ f

ip_route_input route.c 1622;“ f

cache

路由缓存保存的是最近使用的路由。当IP在路由表进行路由以后,如果命中就会在路由缓存里增加该路由。同时系统还会定时检查路由缓存里的项目是否失效,如果失效则清除。