函数fib6_locate处理用户层面涉及到的路由项查找，如在路由删除时，用了查找对应的路由节点。其与数据处理路径中的路由查找函数fib6_node_lookup不同，比如后者在查询路由时没有目的地址的前缀长度信息。

static int ip6_route_del(struct fib6_config *cfg, struct netlink_ext_ack *extack)
{
    struct fib6_table *table;
    struct fib6_info *rt;
    struct fib6_node *fn;
    int err = -ESRCH;
            
    table = fib6_get_table(cfg->fc_nlinfo.nl_net, cfg->fc_table);
    if (!table) {
        NL_SET_ERR_MSG(extack, "FIB table does not exist");
        return err;
    }
    rcu_read_lock();

    fn = fib6_locate(&table->tb6_root,
             &cfg->fc_dst, cfg->fc_dst_len,
             &cfg->fc_src, cfg->fc_src_len,
             !(cfg->fc_flags & RTF_CACHE));

路由项查找

根据目的地址/前缀长度找到对应的路由节点，如果指定了源地址和其前缀长度，并且定义了对IPv6子树的支持，再次根据源地址和其前缀在子树中进行查找。最后，找到的节点需要包含路由信息（RTN_RTINFO）。

struct fib6_node *fib6_locate(struct fib6_node *root,
                  const struct in6_addr *daddr, int dst_len,
                  const struct in6_addr *saddr, int src_len,
                  bool exact_match)
{    
    struct fib6_node *fn; 
   
    fn = fib6_locate_1(root, daddr, dst_len,
               offsetof(struct fib6_info, fib6_dst),
               exact_match);

#ifdef CONFIG_IPV6_SUBTREES
    if (src_len) {
        WARN_ON(saddr == NULL);
        if (fn) {
            struct fib6_node *subtree = FIB6_SUBTREE(fn);

            if (subtree) {
                fn = fib6_locate_1(subtree, saddr, src_len,
                       offsetof(struct fib6_info, fib6_src),
                       exact_match);
            }
        }
    }
#endif

    if (fn && fn->fn_flags & RTN_RTINFO)
        return fn;

    return NULL;

以下遍历从路由表根节点开始，如果当前遍历的节点没有叶子节点（leaf），并且要查找的地址前缀长度大于当前节点的前缀长度，继续遍历下一个节点；否则，如果查找地址的前缀长度小于等于当前节点的前缀长度，不在需要继续向下查找，结束遍历。

/*  Get node with specified destination prefix (and source prefix, if subtrees are used)
 *  exact_match == true means we try to find fn with exact match of
 *  the passed in prefix addr
 *  exact_match == false means we try to find fn with longest prefix
 *  match of the passed in prefix addr. This is useful for finding fn
 *  for cached route as it will be stored in the exception table under
 *  the node with longest prefix length.
 */ 
static struct fib6_node *fib6_locate_1(struct fib6_node *root,
                       const struct in6_addr *addr,
                       int plen, int offset, bool exact_match)
{
    struct fib6_node *fn, *prev = NULL;

    for (fn = root; fn ; ) {
        struct fib6_info *leaf = rcu_dereference(fn->leaf);
        struct rt6key *key;

        /* This node is being deleted */
        if (!leaf) {
            if (plen <= fn->fn_bit)  goto out;
            else goto next;
        }

对于叶子节点存在的情况，如果查询地址的前缀长度小于当前遍历节点的前缀长度，并且以节点的前缀长度做掩码，两者的网络地址不相等，表明没有找到地址和前缀都匹配的节点，结束遍历。

否则，如果查询地址的前缀长度和当前遍历节点的前缀长度相等，返回此节点值，表明完全匹配。最后，在查询地址前缀长度大于当前节点前缀长度时，根据查询地址中下一个位的值（0或者1），决定接下来遍历树中的左子树或者右子树。

        key = (struct rt6key *)((u8 *)leaf + offset);
        /* Prefix match */
        if (plen < fn->fn_bit ||
            !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
            goto out;

        if (plen == fn->fn_bit)
            return fn;

        if (fn->fn_flags & RTN_RTINFO)
            prev = fn;
next:
        /*  We have more bits to go
         */
        if (addr_bit_set(addr, fn->fn_bit))
            fn = rcu_dereference(fn->right);
        else
            fn = rcu_dereference(fn->left);
    }

这里表明以上遍历没有完全匹配的路由项，所以，对于设置了exact_match参数的情况，返回空；否则，返回上一个包含路由信息的节点（非最长前缀匹配的节点）。

out:
    if (exact_match)
        return NULL;
    else
        return prev;

邻居发现中的路由

在接收到路由器的RA报文之后，由函数ndisc_router_discovery进行处理。在支持RFC4191路由信息选项的情况下，解析其中的数据，由函数rt6_route_rcv处理。

static void ndisc_router_discovery(struct sk_buff *skb)
{

#ifdef CONFIG_IPV6_ROUTE_INFO
    if (in6_dev->cnf.accept_ra_rtr_pref && ndopts.nd_opts_ri) {
        struct nd_opt_hdr *p;
        for (p = ndopts.nd_opts_ri; p;
             p = ndisc_next_option(p, ndopts.nd_opts_ri_end)) {
            struct route_info *ri = (struct route_info *)p;
#ifdef CONFIG_IPV6_NDISC_NODETYPE
            if (skb->ndisc_nodetype == NDISC_NODETYPE_NODEFAULT &&
                ri->prefix_len == 0)
                continue;
#endif
            if (ri->prefix_len == 0 && !in6_dev->cnf.accept_ra_defrtr)
                continue;
            if (ri->prefix_len < in6_dev->cnf.accept_ra_rt_info_min_plen)
                continue;
            if (ri->prefix_len > in6_dev->cnf.accept_ra_rt_info_max_plen)
                continue;
            rt6_route_rcv(skb->dev, (u8 *)p, (p->nd_opt_len) << 3,
                      &ipv6_hdr(skb)->saddr);
        }
    }
skip_routeinfo:
#endif

另外，如果RA报文中包含前缀信息选项，由函数addrconf_prefix_rcv进行处理。

    if (in6_dev->cnf.accept_ra_pinfo && ndopts.nd_opts_pi) {
        struct nd_opt_hdr *p;
        for (p = ndopts.nd_opts_pi; p;
             p = ndisc_next_option(p, ndopts.nd_opts_pi_end)) {
            addrconf_prefix_rcv(skb->dev, (u8 *)p,
                        (p->nd_opt_len) << 3,
                        ndopts.nd_opts_src_lladdr != NULL);
        }
    }

对于RA报文中的路由信息选项，处理函数rt6_route_rcv如下，在添加路由之前，先由函数rt6_get_route_info查询当前路由表中是否存在相同路由。

int rt6_route_rcv(struct net_device *dev, u8 *opt, int len, const struct in6_addr *gwaddr)
{

    if (rinfo->prefix_len == 0)
        rt = rt6_get_dflt_router(net, gwaddr, dev);
    else
        rt = rt6_get_route_info(net, prefix, rinfo->prefix_len, gwaddr, dev);

    if (rt && !lifetime) {
        ip6_del_rt(net, rt, false);
        rt = NULL;
    }

    if (!rt && lifetime)
        rt = rt6_add_route_info(net, prefix, rinfo->prefix_len, gwaddr,
                    dev, pref);
    else if (rt)
        rt->fib6_flags = RTF_ROUTEINFO | (rt->fib6_flags & ~RTF_PREF_MASK) | RTF_PREF(pref);

对于RA报文中的前缀信息选项，处理函数addrconf_prefix_rcv如下，需由函数addrconf_get_prefix_route确定当前路由表中是否有相同的路由。

void addrconf_prefix_rcv(struct net_device *dev, u8 *opt, int len, bool sllao)
{

    /*  Two things going on here:
     *  1) Add routes for on-link prefixes
     *  2) Configure prefixes with the auto flag set
     */

    if (pinfo->onlink) {
        struct fib6_info *rt;
        unsigned long rt_expires;

        ...
        if (addrconf_finite_timeout(rt_expires))
            rt_expires *= HZ;

        rt = addrconf_get_prefix_route(&pinfo->prefix,
                           pinfo->prefix_len, dev,
                           RTF_ADDRCONF | RTF_PREFIX_RT,
                           RTF_DEFAULT, true);

路由信息处理过程中，函数rt6_get_route_info进行路由查找，上节函数fib6_locate获得表中的路由节点。之后，遍历此节点的叶子节点，由于RA报文中的路由信息不携带nexthop属性，排除配置了nexthop属性的叶子。

另外，叶子节点中路由下一跳接口需要与指定的设备相同；必须包含RTF_ROUTEINFO标志，表面是RA路由信息所添加，并且带有下一跳网关，网关地址必须相等。符合以上所有条件，即找到合适的路由项。

static struct fib6_info *rt6_get_route_info(struct net *net,
                       const struct in6_addr *prefix, int prefixlen,
                       const struct in6_addr *gwaddr, struct net_device *dev)
{
    u32 tb_id = l3mdev_fib_table(dev) ? : RT6_TABLE_INFO;
    int ifindex = dev->ifindex;
    struct fib6_info *rt = NULL;
    struct fib6_table *table;

    table = fib6_get_table(net, tb_id);
    if (!table)
        return NULL;

    rcu_read_lock();
    fn = fib6_locate(&table->tb6_root, prefix, prefixlen, NULL, 0, true);
    if (!fn)
        goto out;

    for_each_fib6_node_rt_rcu(fn) {
        /* these routes do not use nexthops */
        if (rt->nh)
            continue;
        if (rt->fib6_nh->fib_nh_dev->ifindex != ifindex)
            continue;
        if (!(rt->fib6_flags & RTF_ROUTEINFO) ||
            !rt->fib6_nh->fib_nh_gw_family)
            continue;
        if (!ipv6_addr_equal(&rt->fib6_nh->fib_nh_gw6, gwaddr))
            continue;
        if (!fib6_info_hold_safe(rt))
            continue;
        break;
    }   
out:
    rcu_read_unlock();
    return rt;

前缀信息处理过程中使用addrconf_get_prefix_route获取路由信息，函数fib6_locate获得表中的路由节点。与以上相同，RA报文中的前缀信息也不会包含nexthop属性，排除配置了nexthop属性的叶子节点。

另外，两者下一跳设备必须相同，网关配置情况也要一致，标志位flags配置一致，即为找到合适的路由项。

static struct fib6_info *addrconf_get_prefix_route(const struct in6_addr *pfx,
                          int plen, const struct net_device *dev,
                          u32 flags, u32 noflags, bool no_gw)
{
    struct fib6_node *fn;
    struct fib6_info *rt = NULL;
    struct fib6_table *table;
    u32 tb_id = l3mdev_fib_table(dev) ? : RT6_TABLE_PREFIX;

    table = fib6_get_table(dev_net(dev), tb_id);
    if (!table)
        return NULL;

    rcu_read_lock();
    fn = fib6_locate(&table->tb6_root, pfx, plen, NULL, 0, true);
    if (!fn)
        goto out;

    for_each_fib6_node_rt_rcu(fn) {
        /* prefix routes only use builtin fib6_nh */
        if (rt->nh)
            continue;

        if (rt->fib6_nh->fib_nh_dev->ifindex != dev->ifindex)
            continue;
        if (no_gw && rt->fib6_nh->fib_nh_gw_family)
            continue;
        if ((rt->fib6_flags & flags) != flags)
            continue;
        if ((rt->fib6_flags & noflags) != 0)
            continue;
        if (!fib6_info_hold_safe(rt))
            continue;
        break;
    }
out:
    rcu_read_unlock();
    return rt;

内核版本 5.10