• linux网络协议栈源码分析 - 路由查找树

    1、路由查找树(fib trie)

    1.1、路由查找树数据结构(key_vector)

            路由查找树的节点为key_vector，对于非叶子节点，tnode存储该节点的子节点，数据结构如下:

    1. struct key_vector {
    2. 	t_key key;
    3. 	unsigned char pos;		/* 2log(KEYLENGTH) bits needed */
    4. 	unsigned char bits;		/* 2log(KEYLENGTH) bits needed */
    5. 	unsigned char slen;
    6. 	union {
    7. 		/* This list pointer if valid if (pos | bits) == 0 (LEAF) */
    8. 		struct hlist_head leaf;
    9. 		/* This array is valid if (pos | bits) > 0 (TNODE) */
    10. 		struct key_vector __rcu *tnode[0];
    11. 	};
    12. };

            key_vector各字段的意义参考https://www.kernel.org/doc/html/latest/networking/fib_trie.html。

    • key为节点的关键字，前缀相同的节点存储在该节点下；
    • pos、bits用于子节点的索引，key里面的[pos, pos+bits)为子节点的索引，共有bits位二进制用于索引子节点，也就是该节点下能存储2^{bits}个子节点；
    • leaf/tnode用于指向叶子节点的路由信息或者子节点的信息，通过IS_LEAF宏来判断该节点是否是叶子节点，也就是bits为0的时候，该节点是叶子节点，否则是中间节点，该节点下存储其他子节点。
    • slen英文为suffix length，后缀长度。

    1.2、路由查找树(lpc trie struct)

            下图拷贝自https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux​，从上到下、从左到右，以第一个key = 192.0.2.0的节点为例:

    • bits = 2，那么该节点可以存储2^{^{bits}}也就是4个子节点；
    • pos = 4，那么子节点索引就是从第4位开始，又因为bits = 2，所以，子节点索引就是key[5:4]，下图中可以看到，该节点可以存储4个子节点，除去一个没有指向任何子节点的空指针外，共有3个子节点，分别为192.0.2.0、192.0.2.47、192.0.2.48，这几个子节点的[5:4]二进制位分别为0、2、3，也就是在父节点对应的索引，key_vector使用数组存储子节点指针，对应子节点的索引实际也是数组的索引，子节点指针存储在tnode指针数组里面。

    2、节点查找(fib_find_node)

    2.1、子节点索引计算(get_cindex)

             key的子节点的索引的计算是通过get_cindex宏来实现的，cindex是child index的缩写，get_cindex除了计算key的子节点索引外，还计算了key是否与节点的前缀匹配，get_cindex定义如下:

    #define get_cindex(key, kv) (((key) ^ (kv)->key) >> (kv)->pos)
    • (key)\wedge (kv)->key，节点kv的[pos, pos + bits)位为0，亦或操作key[pos+bits-1, pos]\wedge 0 = key[pos+bits-1, pos]，也就是相当于取key[pos+bits-1, pos]的值；
    • (key)\wedge (kv)->key，节点kv的[31,pos+bits] 为该节点匹配的前缀，如果key与kv的前缀相同，那么key[31:pos+bits]\wedge kv->key[31:pos+bits]就为0，否则就不为0，不为0就有(key[31:pos+bits]\wedge kv->key[31:pos+bits])\ll pos \geq 2^{bits}，也就是通过比较get_cindex的值是否大于等于2^{^{bits}}(1\ll bits)就可以判断出前缀是否相同。

    2.2、节点查找(fib_find_node)

           

    1. static struct key_vector *fib_find_node(struct trie *t,
    2. 					struct key_vector **tp, u32 key)
    3. {
    4. 	struct key_vector *pn, *n = t->kv; // n: 查找树的根节点, pn: 查找树节点的父节点
    5. 	unsigned long index = 0; // 子节点索引(0.0.0.0的第一个子节点也是0.0.0.0)
    6.  
    7. 	do {
    8. 		pn = n; // 记录父节点
    9. 		n = get_child_rcu(n, index); // 获取index子节点(第1次循环时，n指向0.0.0.0的根节点，index为0，根节点下只有一个子节点，索引就是0)
    10.  
    11. 		if (!n) // 子节点为空，那么父节点就是最长匹配的节点
    12. 			break; // 退出循环
    13.  
    14. 		index = get_cindex(key, n); // 子节点n不为空，需要在子节点n里面查找更长的匹配节点
    15.  
    16. 		/* This bit of code is a bit tricky but it combines multiple
    17. 		 * checks into a single check.  The prefix consists of the
    18. 		 * prefix plus zeros for the bits in the cindex. The index
    19. 		 * is the difference between the key and this value.  From
    20. 		 * this we can actually derive several pieces of data.
    21. 		 *   if (index >= (1ul << bits))
    22. 		 *     we have a mismatch in skip bits and failed
    23. 		 *   else
    24. 		 *     we know the value is cindex
    25. 		 *
    26. 		 * This check is safe even if bits == KEYLENGTH due to the
    27. 		 * fact that we can only allocate a node with 32 bits if a
    28. 		 * long is greater than 32 bits.
    29. 		 */
    30. 		if (index >= (1ul << n->bits)) { // index大于等于1ul << n->bits，那么key与kv的前缀不匹配，父节点就是最长匹配的节点
    31. 			n = NULL; // n为NULL，表示是查找中间节点时退出循环，非查找到叶子节点之后导致没有更长匹配而退出循环的
    32. 			break;
    33. 		}
    34.  
    35. 		/* keep searching until we find a perfect match leaf or NULL */
    36. 	} while (IS_TNODE(n)); // n是非叶子节点，那么继续在n的子节点里面进行匹配查找
    37.  
    38. 	*tp = pn; // tp记录key所在的最小非叶子节点
    39.  
    40. 	return n;
    41. }

         

    3、路由查找(fib_table_lookup)

    3.1、前缀不匹配比较(prefix_mismatch)

            prefix_mismatch用于 检查key的前缀是否不匹配:

    • key\wedge prefix为0，那么key= prefix，0 & 任何数都为0，prefix_mismatch返回0，也就是key匹配；
    • key\wedge prefix不为0，那么key的后缀不为0或者前缀不匹配，- prefix为prefix的各位取反加1， 首先prefix后缀为0的部分先变成了1，加1之后又变成了0，并且向prefix最低为1的位进1(取反之后该位变成0了)最终该位有变成1了，最终结果就是prefix后缀为0的部分还是为0，其次prefix不为0的前缀部分取反，其中夹杂的0的二进制位变成了1，prefix\mid -prefix就是使前缀部分变为1，把不为0的部分当作子网的话，这里一定程度上就是计算子网掩码，(key\wedge prefix) \& (prefix \mid -prefix)最终就是检查key的不为0的前缀是否不同。
    1. static inline t_key prefix_mismatch(t_key key, struct key_vector *n)
    2. {
    3. 	t_key prefix = n->key;
    4.  
    5. 	return (key ^ prefix) & (prefix | -prefix);
    6. }

    3.2、路由查找(fib_table_lookup)

            fib_table_lookup主要原理就是深度优先查找最长匹配的路由，没有查找的路由的情况下使用回溯加分支限界减少查找路径查找父节点、兄弟节点，更详细的说明查看如下代码中的注释说明，fib_table_lookup代码实现如下:

    1. int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
    2. 		     struct fib_result *res, int fib_flags)
    3. {
    4. 	struct trie *t = (struct trie *) tb->tb_data;
    5. #ifdef CONFIG_IP_FIB_TRIE_STATS
    6. 	struct trie_use_stats __percpu *stats = t->stats;
    7. #endif
    8. 	const t_key key = ntohl(flp->daddr);
    9. 	struct key_vector *n, *pn;
    10. 	struct fib_alias *fa;
    11. 	unsigned long index;
    12. 	t_key cindex;
    13.  
    14. 	trace_fib_table_lookup(tb->tb_id, flp);
    15.  
    16. 	pn = t->kv; // 获取路由表的根节点
    17. 	cindex = 0; // 根节点的子节点索引(根节点只有一个子节点，索引为0)
    18.  
    19. 	n = get_child_rcu(pn, cindex); // 获取根节点的第0个索引的子节点
    20. 	if (!n) // 如果子节点为空，此时应该还没建立好路由表，返回-EAGAIN，需要再次查找路由表
    21. 		return -EAGAIN;
    22.  
    23. #ifdef CONFIG_IP_FIB_TRIE_STATS
    24. 	this_cpu_inc(stats->gets);
    25. #endif
    26.  
    27. 	/* Step 1: Travel to the longest prefix match in the trie */ // 在查找树里面遍历最长的前缀匹配
    28. 	for (;;) {
    29. 		index = get_cindex(key, n); // key的子节点索引
    30.  
    31. 		/* This bit of code is a bit tricky but it combines multiple
    32. 		 * checks into a single check.  The prefix consists of the
    33. 		 * prefix plus zeros for the "bits" in the prefix. The index
    34. 		 * is the difference between the key and this value.  From
    35. 		 * this we can actually derive several pieces of data.
    36. 		 *   if (index >= (1ul << bits))
    37. 		 *     we have a mismatch in skip bits and failed
    38. 		 *   else
    39. 		 *     we know the value is cindex
    40. 		 *
    41. 		 * This check is safe even if bits == KEYLENGTH due to the
    42. 		 * fact that we can only allocate a node with 32 bits if a
    43. 		 * long is greater than 32 bits.
    44. 		 */
    45. 		if (index >= (1ul << n->bits)) // key与n前缀不同(与n的子节点也不可能相同，没必要查找子节点)，退出当前循环
    46. 			break;
    47.  
    48. 		/* we have found a leaf. Prefixes have already been compared */
    49. 		if (IS_LEAF(n)) // 如果n是叶子节点，n指向fib_alias路由表项
    50. 			goto found; // 找到了key的路由表项，跳转到found
    51.  
    52. 		/* only record pn and cindex if we are going to be chopping
    53. 		 * bits later.  Otherwise we are just wasting cycles.
    54. 		 */
    55. 		if (n->slen > n->pos) { // 节点n的后缀长度slen大于pos，那么记录回溯的节点为当前节点(put_child如果子节点的slen大于父节点的slen，那么使用子节点的slen作为父节点的slen，也就是父节点比子节点匹配更长的前缀)
    56. 			pn = n; // 记录父节点为n节点，backtrace回溯的时候，从pn开始回溯(剪掉不需要回溯的分支)
    57. 			cindex = index; // 记录key在pn中的子节点索引(回溯的时候，需要往更小索引的子节点查找)
    58. 		}
    59.  
    60. 		n = get_child_rcu(n, index); // 获取key在n的子节点
    61. 		if (unlikely(!n)) // 子节点为空，找不到匹配的路由
    62. 			goto backtrace; // 跳转到backtrace，回溯查找路由
    63. 	}
    64.  
    65. 	/* Step 2: Sort out leaves and begin backtracing for longest prefix */
    66. 	for (;;) {
    67. 		/* record the pointer where our next node pointer is stored */
    68. 		struct key_vector __rcu **cptr = n->tnode;
    69.  
    70. 		/* This test verifies that none of the bits that differ
    71. 		 * between the key and the prefix exist in the region of
    72. 		 * the lsb and higher in the prefix.
    73. 		 */
    74. 		if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos)) // 前缀不匹配需要回溯其他节点；不为0的前缀匹配但是slen等于pos，n的子节点的slen小于等于n节点的slen，n的子节点的前缀长度大于等于n的前缀长度，那么也需要回溯，这里比较绕，以192.168.2.0/24子网为例，192.168.3.1的前23位与192.168.2.0的前23位是匹配的，但是子网是24位，192.168.3.1并不在192.168.2.0/24这个子网里面，192.168.3.1也不会在192.168.2.0下面划分的更小的子网里面，所以需要回溯其他子网
    75. 			goto backtrace;
    76.  
    77. 		/* exit out and process leaf */
    78. 		if (unlikely(IS_LEAF(n))) // 是叶子节点
    79. 			break; // 跳出当前循环，也就是跳转到了found
    80.  
    81. 		/* Don't bother recording parent info.  Since we are in
    82. 		 * prefix match mode we will have to come back to wherever
    83. 		 * we started this traversal anyway
    84. 		 */
    85.  
    86. 		while ((n = rcu_dereference(*cptr)) == NULL) {
    87. backtrace:
    88. #ifdef CONFIG_IP_FIB_TRIE_STATS
    89. 			if (!n)
    90. 				this_cpu_inc(stats->null_node_hit);
    91. #endif
    92. 			/* If we are at cindex 0 there are no more bits for
    93. 			 * us to strip at this level so we must ascend back
    94. 			 * up one level to see if there are any more bits to
    95. 			 * be stripped there.
    96. 			 */
    97. 			while (!cindex) { // cindex为0，也就是cindex是pn的最小子节点索引，回溯的时候是从当前子节点往更小的子节点回溯，因为当前已经是最小的索引的子节点了，那么只能往上一层节点回溯；回溯的过程就是缩短前缀的匹配
    98. 				t_key pkey = pn->key; // 获取父节点的key
    99.  
    100. 				/* If we don't have a parent then there is
    101. 				 * nothing for us to do as we do not have any
    102. 				 * further nodes to parse.
    103. 				 */
    104. 				if (IS_TRIE(pn)) // (n)->pos >= KEYLENGTH，pn没有父节点
    105. 					return -EAGAIN; // 找不到匹配的节点，返回-EAGAIN
    106. #ifdef CONFIG_IP_FIB_TRIE_STATS
    107. 				this_cpu_inc(stats->backtrack);
    108. #endif
    109. 				/* Get Child's index */
    110. 				pn = node_parent_rcu(pn); // 获取pn的父节点
    111. 				cindex = get_index(pkey, pn); // 获取key在父节点的索引(回溯从更新索引的子节点查找)
    112. 			}
    113.  
    114. 			/* strip the least significant bit from the cindex */
    115. 			cindex &= cindex - 1; // 清除cindex最低的1的比特位，减少前缀匹配的位数(减1操作，后面的为0的二进制位都需要向前借1，导致后面的0都变成1了，最后向最低的为1的二进制位借1之后，最低的为1的二进制位就变成0了，旧的1&新的0最终还是使原来最低的为1的二进制位变成了0，低位的0借位变成1之后呢，因为原来是0，与操作之后又回到了0，整个操作就是将最低位的1变成0)
    116.  
    117. 			/* grab pointer for next child node */
    118. 			cptr = &pn->tnode[cindex]; // 下一个查找的子节点
    119. 		}
    120. 	}
    121.  
    122. found:
    123. 	/* this line carries forward the xor from earlier in the function */
    124. 	index = key ^ n->key; // 获取key的后缀(前缀部分相同，亦或之后就变成0了，n->key后缀部分为0，任何数与0亦或还是该数)
    125.  
    126. 	/* Step 3: Process the leaf, if that fails fall back to backtracing */
    127. 	hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) { // 遍历fib_alias下面的路由，查找符合flp条件的路由，fib_alias数据结构参考机械工业出版社《Linux内核源码剖析：TCP/IP实现(上册)》"19.3.4 fib_alias结构"
    128. 		struct fib_info *fi = fa->fa_info;
    129. 		int nhsel, err;
    130.  
    131. 		if ((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen < KEYLENGTH)) {
    132. 			if (index >= (1ul << fa->fa_slen))
    133. 				continue;
    134. 		}
    135. 		if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
    136. 			continue;
    137. 		if (fi->fib_dead)
    138. 			continue;
    139. 		if (fa->fa_info->fib_scope < flp->flowi4_scope)
    140. 			continue;
    141. 		fib_alias_accessed(fa);
    142. 		err = fib_props[fa->fa_type].error;
    143. 		if (unlikely(err < 0)) {
    144. #ifdef CONFIG_IP_FIB_TRIE_STATS
    145. 			this_cpu_inc(stats->semantic_match_passed);
    146. #endif
    147. 			return err;
    148. 		}
    149. 		if (fi->fib_flags & RTNH_F_DEAD)
    150. 			continue;
    151. 		for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
    152. 			const struct fib_nh *nh = &fi->fib_nh[nhsel];
    153. 			struct in_device *in_dev = __in_dev_get_rcu(nh->nh_dev);
    154.  
    155. 			if (nh->nh_flags & RTNH_F_DEAD)
    156. 				continue;
    157. 			if (in_dev &&
    158. 			    IN_DEV_IGNORE_ROUTES_WITH_LINKDOWN(in_dev) &&
    159. 			    nh->nh_flags & RTNH_F_LINKDOWN &&
    160. 			    !(fib_flags & FIB_LOOKUP_IGNORE_LINKSTATE))
    161. 				continue;
    162. 			if (!(flp->flowi4_flags & FLOWI_FLAG_SKIP_NH_OIF)) {
    163. 				if (flp->flowi4_oif &&
    164. 				    flp->flowi4_oif != nh->nh_oif)
    165. 					continue;
    166. 			}
    167.  
    168. 			if (!(fib_flags & FIB_LOOKUP_NOREF))
    169. 				atomic_inc(&fi->fib_clntref);
    170.  
    171. 			res->prefixlen = KEYLENGTH - fa->fa_slen; // 填充返回结果
    172. 			res->nh_sel = nhsel;
    173. 			res->type = fa->fa_type;
    174. 			res->scope = fi->fib_scope;
    175. 			res->fi = fi; // fib_info包含fib_nh，fib_nh包含具体的网关、输出网卡等路由信息
    176. 			res->table = tb;
    177. 			res->fa_head = &n->leaf;
    178. #ifdef CONFIG_IP_FIB_TRIE_STATS
    179. 			this_cpu_inc(stats->semantic_match_passed);
    180. #endif
    181. 			trace_fib_table_lookup_nh(nh);
    182.  
    183. 			return err;
    184. 		}
    185. 	}
    186. #ifdef CONFIG_IP_FIB_TRIE_STATS
    187. 	this_cpu_inc(stats->semantic_match_miss);
    188. #endif
    189. 	goto backtrace;
    190. }

            如下图所示，下图是一个简要的查找路径，红色线条从跟节点开始深度优先查找，找到最底层的时候找到空节点，然后绿箭头回溯父节点，第2层子节点索引为2，存在更小的子节点索引，缩小前缀匹配位数之后，可能匹配更小子节点的索引，所以往更小的子节点索引的兄弟节点查找路由。

     

    4、参考文档

    https://www.kernel.org/doc/html/latest/networking/fib_trie.html

    https://vincent.bernat.ch/en/blog/2017-ipv4-route-lookup-linux

  • 相关阅读:
    数字秒表verilog电子秒表跑表，代码/视频
    C语言第四章第2节用if语句实现选择结构学习导案
    ThinkPHP和uniapp开发的CRM售后管理系统（客户、合同、工单、任务、报价、产品、库存、出纳、收费）
    c语言-通讯录（3种版本）
    广州大学2023-2024学年第一学期《计算机网络》A卷
    JavaScript大作业(餐厅美食网站设计与实现)
    代码随想录——长按键入
    【GDAL-java的四个常用代码示例】
    Linux V4L2编程和驱动底层分析
    并发-Executor框架笔记
  • 原文地址：https://blog.csdn.net/arm7star/article/details/125950936