Lines Matching refs:fn
66 static void fib6_prune_clones(struct net *net, struct fib6_node *fn);
67 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn);
68 static struct fib6_node *fib6_repair_tree(struct net *net, struct fib6_node *fn);
146 struct fib6_node *fn; in node_alloc() local
148 fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC); in node_alloc()
150 return fn; in node_alloc()
153 static void node_free(struct fib6_node *fn) in node_free() argument
155 kmem_cache_free(fib6_node_kmem, fn); in node_free()
466 struct fib6_node *fn, *in, *ln; in fib6_add_1() local
476 fn = root; in fib6_add_1()
479 key = (struct rt6key *)((u8 *)fn->leaf + offset); in fib6_add_1()
484 if (plen < fn->fn_bit || in fib6_add_1()
485 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) { in fib6_add_1()
500 if (plen == fn->fn_bit) { in fib6_add_1()
502 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_1()
503 rt6_release(fn->leaf); in fib6_add_1()
504 fn->leaf = NULL; in fib6_add_1()
507 fn->fn_sernum = sernum; in fib6_add_1()
509 return fn; in fib6_add_1()
517 fn->fn_sernum = sernum; in fib6_add_1()
518 dir = addr_bit_set(addr, fn->fn_bit); in fib6_add_1()
519 pn = fn; in fib6_add_1()
520 fn = dir ? fn->right : fn->left; in fib6_add_1()
521 } while (fn); in fib6_add_1()
570 pn = fn->parent; in fib6_add_1()
608 in->leaf = fn->leaf; in fib6_add_1()
622 fn->parent = in; in fib6_add_1()
628 in->left = fn; in fib6_add_1()
631 in->right = fn; in fib6_add_1()
658 ln->right = fn; in fib6_add_1()
660 ln->left = fn; in fib6_add_1()
662 fn->parent = ln; in fib6_add_1()
705 static void fib6_purge_rt(struct rt6_info *rt, struct fib6_node *fn, in fib6_purge_rt() argument
715 while (fn) { in fib6_purge_rt()
716 if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) { in fib6_purge_rt()
717 fn->leaf = fib6_find_prefix(net, fn); in fib6_purge_rt()
718 atomic_inc(&fn->leaf->rt6i_ref); in fib6_purge_rt()
721 fn = fn->parent; in fib6_purge_rt()
732 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt, in fib6_add_rt2node() argument
746 ins = &fn->leaf; in fib6_add_rt2node()
748 for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) { in fib6_add_rt2node()
816 if (ins == &fn->leaf) in fib6_add_rt2node()
817 fn->rr_ptr = NULL; in fib6_add_rt2node()
825 sibling = fn->leaf; in fib6_add_rt2node()
863 rt->rt6i_node = fn; in fib6_add_rt2node()
868 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_rt2node()
870 fn->fn_flags |= RTN_RTINFO; in fib6_add_rt2node()
888 rt->rt6i_node = fn; in fib6_add_rt2node()
892 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_rt2node()
894 fn->fn_flags |= RTN_RTINFO; in fib6_add_rt2node()
897 fib6_purge_rt(iter, fn, info->nl_net); in fib6_add_rt2node()
907 fib6_purge_rt(iter, fn, info->nl_net); in fib6_add_rt2node()
946 struct fib6_node *fn, *pn = NULL; in fib6_add() local
965 fn = fib6_add_1(root, &rt->rt6i_dst.addr, rt->rt6i_dst.plen, in fib6_add()
968 if (IS_ERR(fn)) { in fib6_add()
969 err = PTR_ERR(fn); in fib6_add()
970 fn = NULL; in fib6_add()
974 pn = fn; in fib6_add()
980 if (!fn->subtree) { in fib6_add()
1021 sfn->parent = fn; in fib6_add()
1022 fn->subtree = sfn; in fib6_add()
1024 sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr, in fib6_add()
1035 if (!fn->leaf) { in fib6_add()
1036 fn->leaf = rt; in fib6_add()
1039 fn = sn; in fib6_add()
1043 err = fib6_add_rt2node(fn, rt, info, mxc); in fib6_add()
1058 if (pn != fn && pn->leaf == rt) { in fib6_add()
1062 if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) { in fib6_add()
1083 if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT))) in fib6_add()
1084 fib6_repair_tree(info->nl_net, fn); in fib6_add()
1104 struct fib6_node *fn; in fib6_lookup_1() local
1114 fn = root; in fib6_lookup_1()
1119 dir = addr_bit_set(args->addr, fn->fn_bit); in fib6_lookup_1()
1121 next = dir ? fn->right : fn->left; in fib6_lookup_1()
1124 fn = next; in fib6_lookup_1()
1130 while (fn) { in fib6_lookup_1()
1131 if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) { in fib6_lookup_1()
1134 key = (struct rt6key *) ((u8 *) fn->leaf + in fib6_lookup_1()
1139 if (fn->subtree) { in fib6_lookup_1()
1141 sfn = fib6_lookup_1(fn->subtree, in fib6_lookup_1()
1145 fn = sfn; in fib6_lookup_1()
1148 if (fn->fn_flags & RTN_RTINFO) in fib6_lookup_1()
1149 return fn; in fib6_lookup_1()
1155 if (fn->fn_flags & RTN_ROOT) in fib6_lookup_1()
1158 fn = fn->parent; in fib6_lookup_1()
1167 struct fib6_node *fn; in fib6_lookup() local
1184 fn = fib6_lookup_1(root, daddr ? args : args + 1); in fib6_lookup()
1185 if (!fn || fn->fn_flags & RTN_TL_ROOT) in fib6_lookup()
1186 fn = root; in fib6_lookup()
1188 return fn; in fib6_lookup()
1201 struct fib6_node *fn; in fib6_locate_1() local
1203 for (fn = root; fn ; ) { in fib6_locate_1()
1204 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset); in fib6_locate_1()
1209 if (plen < fn->fn_bit || in fib6_locate_1()
1210 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) in fib6_locate_1()
1213 if (plen == fn->fn_bit) in fib6_locate_1()
1214 return fn; in fib6_locate_1()
1219 if (addr_bit_set(addr, fn->fn_bit)) in fib6_locate_1()
1220 fn = fn->right; in fib6_locate_1()
1222 fn = fn->left; in fib6_locate_1()
1231 struct fib6_node *fn; in fib6_locate() local
1233 fn = fib6_locate_1(root, daddr, dst_len, in fib6_locate()
1239 if (fn && fn->subtree) in fib6_locate()
1240 fn = fib6_locate_1(fn->subtree, saddr, src_len, in fib6_locate()
1245 if (fn && fn->fn_flags & RTN_RTINFO) in fib6_locate()
1246 return fn; in fib6_locate()
1257 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn) in fib6_find_prefix() argument
1259 if (fn->fn_flags & RTN_ROOT) in fib6_find_prefix()
1262 while (fn) { in fib6_find_prefix()
1263 if (fn->left) in fib6_find_prefix()
1264 return fn->left->leaf; in fib6_find_prefix()
1265 if (fn->right) in fib6_find_prefix()
1266 return fn->right->leaf; in fib6_find_prefix()
1268 fn = FIB6_SUBTREE(fn); in fib6_find_prefix()
1279 struct fib6_node *fn) in fib6_repair_tree() argument
1288 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter); in fib6_repair_tree()
1291 WARN_ON(fn->fn_flags & RTN_RTINFO); in fib6_repair_tree()
1292 WARN_ON(fn->fn_flags & RTN_TL_ROOT); in fib6_repair_tree()
1293 WARN_ON(fn->leaf); in fib6_repair_tree()
1297 if (fn->right) in fib6_repair_tree()
1298 child = fn->right, children |= 1; in fib6_repair_tree()
1299 if (fn->left) in fib6_repair_tree()
1300 child = fn->left, children |= 2; in fib6_repair_tree()
1302 if (children == 3 || FIB6_SUBTREE(fn) in fib6_repair_tree()
1305 || (children && fn->fn_flags & RTN_ROOT) in fib6_repair_tree()
1308 fn->leaf = fib6_find_prefix(net, fn); in fib6_repair_tree()
1310 if (!fn->leaf) { in fib6_repair_tree()
1311 WARN_ON(!fn->leaf); in fib6_repair_tree()
1312 fn->leaf = net->ipv6.ip6_null_entry; in fib6_repair_tree()
1315 atomic_inc(&fn->leaf->rt6i_ref); in fib6_repair_tree()
1316 return fn->parent; in fib6_repair_tree()
1319 pn = fn->parent; in fib6_repair_tree()
1321 if (FIB6_SUBTREE(pn) == fn) { in fib6_repair_tree()
1322 WARN_ON(!(fn->fn_flags & RTN_ROOT)); in fib6_repair_tree()
1326 WARN_ON(fn->fn_flags & RTN_ROOT); in fib6_repair_tree()
1328 if (pn->right == fn) in fib6_repair_tree()
1330 else if (pn->left == fn) in fib6_repair_tree()
1346 if (w->root == fn) { in fib6_repair_tree()
1349 } else if (w->node == fn) { in fib6_repair_tree()
1355 if (w->root == fn) { in fib6_repair_tree()
1359 if (w->node == fn) { in fib6_repair_tree()
1373 node_free(fn); in fib6_repair_tree()
1379 fn = pn; in fib6_repair_tree()
1383 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp, in fib6_del_route() argument
1399 if (fn->rr_ptr == rt) in fib6_del_route()
1400 fn->rr_ptr = NULL; in fib6_del_route()
1428 if (!fn->leaf) { in fib6_del_route()
1429 fn->fn_flags &= ~RTN_RTINFO; in fib6_del_route()
1431 fn = fib6_repair_tree(net, fn); in fib6_del_route()
1434 fib6_purge_rt(rt, fn, net); in fib6_del_route()
1443 struct fib6_node *fn = rt->rt6i_node; in fib6_del() local
1448 WARN_ON(fn); in fib6_del()
1452 if (!fn || rt == net->ipv6.ip6_null_entry) in fib6_del()
1455 WARN_ON(!(fn->fn_flags & RTN_RTINFO)); in fib6_del()
1458 struct fib6_node *pn = fn; in fib6_del()
1474 for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) { in fib6_del()
1476 fib6_del_route(fn, rtp, info); in fib6_del()
1509 struct fib6_node *fn, *pn; in fib6_walk_continue() local
1512 fn = w->node; in fib6_walk_continue()
1513 if (!fn) in fib6_walk_continue()
1516 if (w->prune && fn != w->root && in fib6_walk_continue()
1517 fn->fn_flags & RTN_RTINFO && w->state < FWS_C) { in fib6_walk_continue()
1519 w->leaf = fn->leaf; in fib6_walk_continue()
1524 if (FIB6_SUBTREE(fn)) { in fib6_walk_continue()
1525 w->node = FIB6_SUBTREE(fn); in fib6_walk_continue()
1531 if (fn->left) { in fib6_walk_continue()
1532 w->node = fn->left; in fib6_walk_continue()
1538 if (fn->right) { in fib6_walk_continue()
1539 w->node = fn->right; in fib6_walk_continue()
1544 w->leaf = fn->leaf; in fib6_walk_continue()
1546 if (w->leaf && fn->fn_flags & RTN_RTINFO) { in fib6_walk_continue()
1564 if (fn == w->root) in fib6_walk_continue()
1566 pn = fn->parent; in fib6_walk_continue()
1569 if (FIB6_SUBTREE(pn) == fn) { in fib6_walk_continue()
1570 WARN_ON(!(fn->fn_flags & RTN_ROOT)); in fib6_walk_continue()
1575 if (pn->left == fn) { in fib6_walk_continue()
1579 if (pn->right == fn) { in fib6_walk_continue()
1711 static void fib6_prune_clones(struct net *net, struct fib6_node *fn) in fib6_prune_clones() argument
1713 fib6_clean_tree(net, fn, fib6_prune_clone, true, in fib6_prune_clones()