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_immediate(struct fib6_node *fn) in node_free_immediate() argument
155 kmem_cache_free(fib6_node_kmem, fn); in node_free_immediate()
160 struct fib6_node *fn = container_of(head, struct fib6_node, rcu); in node_free_rcu() local
162 kmem_cache_free(fib6_node_kmem, fn); in node_free_rcu()
165 static void node_free(struct fib6_node *fn) in node_free() argument
167 call_rcu(&fn->rcu, node_free_rcu); in node_free()
484 struct fib6_node *fn, *in, *ln; in fib6_add_1() local
494 fn = root; in fib6_add_1()
497 key = (struct rt6key *)((u8 *)fn->leaf + offset); in fib6_add_1()
502 if (plen < fn->fn_bit || in fib6_add_1()
503 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) { in fib6_add_1()
518 if (plen == fn->fn_bit) { in fib6_add_1()
520 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_1()
521 rt6_release(fn->leaf); in fib6_add_1()
522 fn->leaf = NULL; in fib6_add_1()
525 fn->fn_sernum = sernum; in fib6_add_1()
527 return fn; in fib6_add_1()
535 fn->fn_sernum = sernum; in fib6_add_1()
536 dir = addr_bit_set(addr, fn->fn_bit); in fib6_add_1()
537 pn = fn; in fib6_add_1()
538 fn = dir ? fn->right : fn->left; in fib6_add_1()
539 } while (fn); in fib6_add_1()
588 pn = fn->parent; in fib6_add_1()
626 in->leaf = fn->leaf; in fib6_add_1()
640 fn->parent = in; in fib6_add_1()
646 in->left = fn; in fib6_add_1()
649 in->right = fn; in fib6_add_1()
676 ln->right = fn; in fib6_add_1()
678 ln->left = fn; in fib6_add_1()
680 fn->parent = ln; in fib6_add_1()
723 static void fib6_purge_rt(struct rt6_info *rt, struct fib6_node *fn, in fib6_purge_rt() argument
733 while (fn) { in fib6_purge_rt()
734 if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) { in fib6_purge_rt()
735 fn->leaf = fib6_find_prefix(net, fn); in fib6_purge_rt()
736 atomic_inc(&fn->leaf->rt6i_ref); in fib6_purge_rt()
739 fn = fn->parent; in fib6_purge_rt()
750 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt, in fib6_add_rt2node() argument
764 ins = &fn->leaf; in fib6_add_rt2node()
766 for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) { in fib6_add_rt2node()
832 if (ins == &fn->leaf) in fib6_add_rt2node()
833 fn->rr_ptr = NULL; in fib6_add_rt2node()
841 sibling = fn->leaf; in fib6_add_rt2node()
879 rcu_assign_pointer(rt->rt6i_node, fn); in fib6_add_rt2node()
884 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_rt2node()
886 fn->fn_flags |= RTN_RTINFO; in fib6_add_rt2node()
904 rcu_assign_pointer(rt->rt6i_node, fn); in fib6_add_rt2node()
908 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_rt2node()
910 fn->fn_flags |= RTN_RTINFO; in fib6_add_rt2node()
914 fib6_purge_rt(iter, fn, info->nl_net); in fib6_add_rt2node()
915 if (fn->rr_ptr == iter) in fib6_add_rt2node()
916 fn->rr_ptr = NULL; in fib6_add_rt2node()
929 fib6_purge_rt(iter, fn, info->nl_net); in fib6_add_rt2node()
930 if (fn->rr_ptr == iter) in fib6_add_rt2node()
931 fn->rr_ptr = NULL; in fib6_add_rt2node()
970 struct fib6_node *fn, *pn = NULL; in fib6_add() local
989 fn = fib6_add_1(root, &rt->rt6i_dst.addr, rt->rt6i_dst.plen, in fib6_add()
992 if (IS_ERR(fn)) { in fib6_add()
993 err = PTR_ERR(fn); in fib6_add()
994 fn = NULL; in fib6_add()
998 pn = fn; in fib6_add()
1004 if (!fn->subtree) { in fib6_add()
1045 sfn->parent = fn; in fib6_add()
1046 fn->subtree = sfn; in fib6_add()
1048 sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr, in fib6_add()
1059 if (!fn->leaf) { in fib6_add()
1060 fn->leaf = rt; in fib6_add()
1063 fn = sn; in fib6_add()
1067 err = fib6_add_rt2node(fn, rt, info, mxc); in fib6_add()
1082 if (pn != fn && pn->leaf == rt) { in fib6_add()
1086 if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) { in fib6_add()
1108 if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT))) in fib6_add()
1109 fib6_repair_tree(info->nl_net, fn); in fib6_add()
1128 struct fib6_node *fn; in fib6_lookup_1() local
1138 fn = root; in fib6_lookup_1()
1143 dir = addr_bit_set(args->addr, fn->fn_bit); in fib6_lookup_1()
1145 next = dir ? fn->right : fn->left; in fib6_lookup_1()
1148 fn = next; in fib6_lookup_1()
1154 while (fn) { in fib6_lookup_1()
1155 if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) { in fib6_lookup_1()
1158 key = (struct rt6key *) ((u8 *) fn->leaf + in fib6_lookup_1()
1163 if (fn->subtree) { in fib6_lookup_1()
1165 sfn = fib6_lookup_1(fn->subtree, in fib6_lookup_1()
1169 fn = sfn; in fib6_lookup_1()
1172 if (fn->fn_flags & RTN_RTINFO) in fib6_lookup_1()
1173 return fn; in fib6_lookup_1()
1179 if (fn->fn_flags & RTN_ROOT) in fib6_lookup_1()
1182 fn = fn->parent; in fib6_lookup_1()
1191 struct fib6_node *fn; in fib6_lookup() local
1208 fn = fib6_lookup_1(root, daddr ? args : args + 1); in fib6_lookup()
1209 if (!fn || fn->fn_flags & RTN_TL_ROOT) in fib6_lookup()
1210 fn = root; in fib6_lookup()
1212 return fn; in fib6_lookup()
1225 struct fib6_node *fn; in fib6_locate_1() local
1227 for (fn = root; fn ; ) { in fib6_locate_1()
1228 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset); in fib6_locate_1()
1233 if (plen < fn->fn_bit || in fib6_locate_1()
1234 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) in fib6_locate_1()
1237 if (plen == fn->fn_bit) in fib6_locate_1()
1238 return fn; in fib6_locate_1()
1243 if (addr_bit_set(addr, fn->fn_bit)) in fib6_locate_1()
1244 fn = fn->right; in fib6_locate_1()
1246 fn = fn->left; in fib6_locate_1()
1255 struct fib6_node *fn; in fib6_locate() local
1257 fn = fib6_locate_1(root, daddr, dst_len, in fib6_locate()
1263 if (fn && fn->subtree) in fib6_locate()
1264 fn = fib6_locate_1(fn->subtree, saddr, src_len, in fib6_locate()
1269 if (fn && fn->fn_flags & RTN_RTINFO) in fib6_locate()
1270 return fn; in fib6_locate()
1281 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn) in fib6_find_prefix() argument
1283 if (fn->fn_flags & RTN_ROOT) in fib6_find_prefix()
1286 while (fn) { in fib6_find_prefix()
1287 if (fn->left) in fib6_find_prefix()
1288 return fn->left->leaf; in fib6_find_prefix()
1289 if (fn->right) in fib6_find_prefix()
1290 return fn->right->leaf; in fib6_find_prefix()
1292 fn = FIB6_SUBTREE(fn); in fib6_find_prefix()
1303 struct fib6_node *fn) in fib6_repair_tree() argument
1312 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter); in fib6_repair_tree()
1315 WARN_ON(fn->fn_flags & RTN_RTINFO); in fib6_repair_tree()
1316 WARN_ON(fn->fn_flags & RTN_TL_ROOT); in fib6_repair_tree()
1317 WARN_ON(fn->leaf); in fib6_repair_tree()
1321 if (fn->right) in fib6_repair_tree()
1322 child = fn->right, children |= 1; in fib6_repair_tree()
1323 if (fn->left) in fib6_repair_tree()
1324 child = fn->left, children |= 2; in fib6_repair_tree()
1326 if (children == 3 || FIB6_SUBTREE(fn) in fib6_repair_tree()
1329 || (children && fn->fn_flags & RTN_ROOT) in fib6_repair_tree()
1332 fn->leaf = fib6_find_prefix(net, fn); in fib6_repair_tree()
1334 if (!fn->leaf) { in fib6_repair_tree()
1335 WARN_ON(!fn->leaf); in fib6_repair_tree()
1336 fn->leaf = net->ipv6.ip6_null_entry; in fib6_repair_tree()
1339 atomic_inc(&fn->leaf->rt6i_ref); in fib6_repair_tree()
1340 return fn->parent; in fib6_repair_tree()
1343 pn = fn->parent; in fib6_repair_tree()
1345 if (FIB6_SUBTREE(pn) == fn) { in fib6_repair_tree()
1346 WARN_ON(!(fn->fn_flags & RTN_ROOT)); in fib6_repair_tree()
1350 WARN_ON(fn->fn_flags & RTN_ROOT); in fib6_repair_tree()
1352 if (pn->right == fn) in fib6_repair_tree()
1354 else if (pn->left == fn) in fib6_repair_tree()
1370 if (w->root == fn) { in fib6_repair_tree()
1373 } else if (w->node == fn) { in fib6_repair_tree()
1379 if (w->root == fn) { in fib6_repair_tree()
1383 if (w->node == fn) { in fib6_repair_tree()
1397 node_free(fn); in fib6_repair_tree()
1403 fn = pn; in fib6_repair_tree()
1407 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp, in fib6_del_route() argument
1423 if (fn->rr_ptr == rt) in fib6_del_route()
1424 fn->rr_ptr = NULL; in fib6_del_route()
1452 if (!fn->leaf) { in fib6_del_route()
1453 fn->fn_flags &= ~RTN_RTINFO; in fib6_del_route()
1455 fn = fib6_repair_tree(net, fn); in fib6_del_route()
1458 fib6_purge_rt(rt, fn, net); in fib6_del_route()
1466 struct fib6_node *fn = rcu_dereference_protected(rt->rt6i_node, in fib6_del() local
1473 WARN_ON(fn); in fib6_del()
1477 if (!fn || rt == net->ipv6.ip6_null_entry) in fib6_del()
1480 WARN_ON(!(fn->fn_flags & RTN_RTINFO)); in fib6_del()
1483 struct fib6_node *pn = fn; in fib6_del()
1499 for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) { in fib6_del()
1501 fib6_del_route(fn, rtp, info); in fib6_del()
1534 struct fib6_node *fn, *pn; in fib6_walk_continue() local
1537 fn = w->node; in fib6_walk_continue()
1538 if (!fn) in fib6_walk_continue()
1541 if (w->prune && fn != w->root && in fib6_walk_continue()
1542 fn->fn_flags & RTN_RTINFO && w->state < FWS_C) { in fib6_walk_continue()
1544 w->leaf = fn->leaf; in fib6_walk_continue()
1549 if (FIB6_SUBTREE(fn)) { in fib6_walk_continue()
1550 w->node = FIB6_SUBTREE(fn); in fib6_walk_continue()
1556 if (fn->left) { in fib6_walk_continue()
1557 w->node = fn->left; in fib6_walk_continue()
1563 if (fn->right) { in fib6_walk_continue()
1564 w->node = fn->right; in fib6_walk_continue()
1569 w->leaf = fn->leaf; in fib6_walk_continue()
1571 if (w->leaf && fn->fn_flags & RTN_RTINFO) { in fib6_walk_continue()
1589 if (fn == w->root) in fib6_walk_continue()
1591 pn = fn->parent; in fib6_walk_continue()
1594 if (FIB6_SUBTREE(pn) == fn) { in fib6_walk_continue()
1595 WARN_ON(!(fn->fn_flags & RTN_ROOT)); in fib6_walk_continue()
1600 if (pn->left == fn) { in fib6_walk_continue()
1604 if (pn->right == fn) { in fib6_walk_continue()
1738 static void fib6_prune_clones(struct net *net, struct fib6_node *fn) in fib6_prune_clones() argument
1740 fib6_clean_tree(net, fn, fib6_prune_clone, true, in fib6_prune_clones()