IPv4路由别名fib_alias
fib_alias用于连接tries树节点和基础的fib_info结构。
在新增路由表项时,如果没有合适的fib_alias可用,可用表示新增表项和已有fib_alias的tos,priority,以及type,scope相同,并且使用相同的fib_info,则需要创建新的fib_alias结构。
添加fib_alias
如果在tries树中没有找到可插入fib_alias的叶子节点,即节点l为空,使用函数fib_insert_node添加节点以及相关联的新的fib_alias结构(参见 IPv4路由tries树节点添加与查找 https://redwingz.blog.csdn.net/article/details/121002339 )。否则,如果在tries树中找到匹配的叶子节点,并且在此叶子节点的fib_alias链表中遍历找到了合适的插入位置,即参数fa(参见以下函数fib_find_alias,),将新的fib_alias插入到匹配项fa之前。
如果没有合适的插入点(fa为空),放宽查找条件,再次遍历叶子节点l的fib_alias链表,查找合适的节点,但是新的fib_alias要插入到找到节点之后。匹配条件变为:1)新fib_alias的后缀长度要大于等于遍历项的后缀长度fa_slen,反过来讲,就是在此链表中前缀长度按照由大到小排列;2)并且如果两者后缀长度相等,新的fib_alias的表ID要小于等于遍历项的表ID的项,也就是tb_id在链表中是按照由大到小排列。
如果以上遍历,找到合适的fib_alias,将新的fib_alias添加到此项之后。否者,没有匹配项时,将新的fib_alias添加到叶子节点l的首部。
static int fib_insert_alias(struct trie *t, struct key_vector *tp,
struct key_vector *l, struct fib_alias *new,
struct fib_alias *fa, t_key key)
{
if (!l)
return fib_insert_node(t, tp, new, key);
if (fa) {
hlist_add_before_rcu(&new->fa_list, &fa->fa_list);
} else {
struct fib_alias *last;
hlist_for_each_entry(last, &l->leaf, fa_list) {
if (new->fa_slen < last->fa_slen)
break;
if ((new->fa_slen == last->fa_slen) &&
(new->tb_id > last->tb_id))
break;
fa = last;
}
if (fa)
hlist_add_behind_rcu(&new->fa_list, &fa->fa_list);
else
hlist_add_head_rcu(&new->fa_list, &l->leaf);
}
- 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
函数最后更新相关节点的后缀长度。由于后缀长度由小到大排列,如果新的fib_alias添加到了链表末尾,表明节点l的后缀长度小于新fib_alias的后缀长度,进行更新。
/* if we added to the tail node then we need to update slen */
if (l->slen < new->fa_slen) {
l->slen = new->fa_slen;
node_push_suffix(tp, new->fa_slen);
}
return 0;
- 1
- 2
- 3
- 4
- 5
- 6
fib_alias查找
在给定tries树节点的fib_alias链表(fah)中查找匹配的项,匹配项的后缀长度需要与slen相等,表ID也要相等。后缀长度fa_slen在链表中是由小到大排列的。反过来讲,fib_alias的前缀长度由大到小排列,即最长匹配的项在最前。相反的,tb_id在链表中是按照由大到小排列的。另外,tos值也是按照由大到小排列。
如果设置了查找第一个fib_alias,返回此时正在遍历的项。否则,找到TOS值小于给定tos值的项;或者两者tos值相等,但是优先级priority大于等于给定prio的项。
新的fib_alias要插入到找到的fib_alias之前,参见以上函数fib_insert_alias。
/* Return the first fib alias matching TOS with
* priority less than or equal to PRIO.
* If 'find_first' is set, return the first matching
* fib alias, regardless of TOS and priority.
*/
static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 slen,
u8 tos, u32 prio, u32 tb_id, bool find_first)
{
struct fib_alias *fa;
if (!fah) return NULL;
hlist_for_each_entry(fa, fah, fa_list) {
if (fa->fa_slen < slen)
continue;
if (fa->fa_slen != slen)
break;
if (fa->tb_id > tb_id)
continue;
if (fa->tb_id != tb_id)
break;
if (find_first)
return fa;
if (fa->fa_tos > tos)
continue;
if (fa->fa_info->fib_priority >= prio || fa->fa_tos < tos)
return fa;
}
return NULL;
- 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
内核版本 5.10