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