函数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