WHCSRL 技术网

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

推荐阅读