Lines Matching refs:fn
65 static void fib6_prune_clones(struct net *net, struct fib6_node *fn);
66 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn);
67 static struct fib6_node *fib6_repair_tree(struct net *net, struct fib6_node *fn);
145 struct fib6_node *fn; in node_alloc() local
147 fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC); in node_alloc()
149 return fn; in node_alloc()
152 static void node_free(struct fib6_node *fn) in node_free() argument
154 kmem_cache_free(fib6_node_kmem, fn); in node_free()
425 struct fib6_node *fn, *in, *ln; in fib6_add_1() local
435 fn = root; in fib6_add_1()
438 key = (struct rt6key *)((u8 *)fn->leaf + offset); in fib6_add_1()
443 if (plen < fn->fn_bit || in fib6_add_1()
444 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) { in fib6_add_1()
459 if (plen == fn->fn_bit) { in fib6_add_1()
461 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_1()
462 rt6_release(fn->leaf); in fib6_add_1()
463 fn->leaf = NULL; in fib6_add_1()
466 fn->fn_sernum = sernum; in fib6_add_1()
468 return fn; in fib6_add_1()
476 fn->fn_sernum = sernum; in fib6_add_1()
477 dir = addr_bit_set(addr, fn->fn_bit); in fib6_add_1()
478 pn = fn; in fib6_add_1()
479 fn = dir ? fn->right : fn->left; in fib6_add_1()
480 } while (fn); in fib6_add_1()
529 pn = fn->parent; in fib6_add_1()
567 in->leaf = fn->leaf; in fib6_add_1()
581 fn->parent = in; in fib6_add_1()
587 in->left = fn; in fib6_add_1()
590 in->right = fn; in fib6_add_1()
617 ln->right = fn; in fib6_add_1()
619 ln->left = fn; in fib6_add_1()
621 fn->parent = ln; in fib6_add_1()
664 static void fib6_purge_rt(struct rt6_info *rt, struct fib6_node *fn, in fib6_purge_rt() argument
674 while (fn) { in fib6_purge_rt()
675 if (!(fn->fn_flags & RTN_RTINFO) && fn->leaf == rt) { in fib6_purge_rt()
676 fn->leaf = fib6_find_prefix(net, fn); in fib6_purge_rt()
677 atomic_inc(&fn->leaf->rt6i_ref); in fib6_purge_rt()
680 fn = fn->parent; in fib6_purge_rt()
691 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt, in fib6_add_rt2node() argument
705 ins = &fn->leaf; in fib6_add_rt2node()
707 for (iter = fn->leaf; iter; iter = iter->dst.rt6_next) { in fib6_add_rt2node()
774 if (ins == &fn->leaf) in fib6_add_rt2node()
775 fn->rr_ptr = NULL; in fib6_add_rt2node()
783 sibling = fn->leaf; in fib6_add_rt2node()
821 rt->rt6i_node = fn; in fib6_add_rt2node()
826 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_rt2node()
828 fn->fn_flags |= RTN_RTINFO; in fib6_add_rt2node()
846 rt->rt6i_node = fn; in fib6_add_rt2node()
850 if (!(fn->fn_flags & RTN_RTINFO)) { in fib6_add_rt2node()
852 fn->fn_flags |= RTN_RTINFO; in fib6_add_rt2node()
855 fib6_purge_rt(iter, fn, info->nl_net); in fib6_add_rt2node()
865 fib6_purge_rt(iter, fn, info->nl_net); in fib6_add_rt2node()
904 struct fib6_node *fn, *pn = NULL; in fib6_add() local
919 fn = fib6_add_1(root, &rt->rt6i_dst.addr, rt->rt6i_dst.plen, in fib6_add()
922 if (IS_ERR(fn)) { in fib6_add()
923 err = PTR_ERR(fn); in fib6_add()
924 fn = NULL; in fib6_add()
928 pn = fn; in fib6_add()
934 if (!fn->subtree) { in fib6_add()
975 sfn->parent = fn; in fib6_add()
976 fn->subtree = sfn; in fib6_add()
978 sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr, in fib6_add()
989 if (!fn->leaf) { in fib6_add()
990 fn->leaf = rt; in fib6_add()
993 fn = sn; in fib6_add()
997 err = fib6_add_rt2node(fn, rt, info, mxc); in fib6_add()
1011 if (pn != fn && pn->leaf == rt) { in fib6_add()
1015 if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) { in fib6_add()
1035 if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT))) in fib6_add()
1036 fib6_repair_tree(info->nl_net, fn); in fib6_add()
1055 struct fib6_node *fn; in fib6_lookup_1() local
1065 fn = root; in fib6_lookup_1()
1070 dir = addr_bit_set(args->addr, fn->fn_bit); in fib6_lookup_1()
1072 next = dir ? fn->right : fn->left; in fib6_lookup_1()
1075 fn = next; in fib6_lookup_1()
1081 while (fn) { in fib6_lookup_1()
1082 if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) { in fib6_lookup_1()
1085 key = (struct rt6key *) ((u8 *) fn->leaf + in fib6_lookup_1()
1090 if (fn->subtree) { in fib6_lookup_1()
1092 sfn = fib6_lookup_1(fn->subtree, in fib6_lookup_1()
1096 fn = sfn; in fib6_lookup_1()
1099 if (fn->fn_flags & RTN_RTINFO) in fib6_lookup_1()
1100 return fn; in fib6_lookup_1()
1106 if (fn->fn_flags & RTN_ROOT) in fib6_lookup_1()
1109 fn = fn->parent; in fib6_lookup_1()
1118 struct fib6_node *fn; in fib6_lookup() local
1135 fn = fib6_lookup_1(root, daddr ? args : args + 1); in fib6_lookup()
1136 if (!fn || fn->fn_flags & RTN_TL_ROOT) in fib6_lookup()
1137 fn = root; in fib6_lookup()
1139 return fn; in fib6_lookup()
1152 struct fib6_node *fn; in fib6_locate_1() local
1154 for (fn = root; fn ; ) { in fib6_locate_1()
1155 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset); in fib6_locate_1()
1160 if (plen < fn->fn_bit || in fib6_locate_1()
1161 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) in fib6_locate_1()
1164 if (plen == fn->fn_bit) in fib6_locate_1()
1165 return fn; in fib6_locate_1()
1170 if (addr_bit_set(addr, fn->fn_bit)) in fib6_locate_1()
1171 fn = fn->right; in fib6_locate_1()
1173 fn = fn->left; in fib6_locate_1()
1182 struct fib6_node *fn; in fib6_locate() local
1184 fn = fib6_locate_1(root, daddr, dst_len, in fib6_locate()
1190 if (fn && fn->subtree) in fib6_locate()
1191 fn = fib6_locate_1(fn->subtree, saddr, src_len, in fib6_locate()
1196 if (fn && fn->fn_flags & RTN_RTINFO) in fib6_locate()
1197 return fn; in fib6_locate()
1208 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn) in fib6_find_prefix() argument
1210 if (fn->fn_flags & RTN_ROOT) in fib6_find_prefix()
1213 while (fn) { in fib6_find_prefix()
1214 if (fn->left) in fib6_find_prefix()
1215 return fn->left->leaf; in fib6_find_prefix()
1216 if (fn->right) in fib6_find_prefix()
1217 return fn->right->leaf; in fib6_find_prefix()
1219 fn = FIB6_SUBTREE(fn); in fib6_find_prefix()
1230 struct fib6_node *fn) in fib6_repair_tree() argument
1239 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter); in fib6_repair_tree()
1242 WARN_ON(fn->fn_flags & RTN_RTINFO); in fib6_repair_tree()
1243 WARN_ON(fn->fn_flags & RTN_TL_ROOT); in fib6_repair_tree()
1244 WARN_ON(fn->leaf); in fib6_repair_tree()
1248 if (fn->right) in fib6_repair_tree()
1249 child = fn->right, children |= 1; in fib6_repair_tree()
1250 if (fn->left) in fib6_repair_tree()
1251 child = fn->left, children |= 2; in fib6_repair_tree()
1253 if (children == 3 || FIB6_SUBTREE(fn) in fib6_repair_tree()
1256 || (children && fn->fn_flags & RTN_ROOT) in fib6_repair_tree()
1259 fn->leaf = fib6_find_prefix(net, fn); in fib6_repair_tree()
1261 if (!fn->leaf) { in fib6_repair_tree()
1262 WARN_ON(!fn->leaf); in fib6_repair_tree()
1263 fn->leaf = net->ipv6.ip6_null_entry; in fib6_repair_tree()
1266 atomic_inc(&fn->leaf->rt6i_ref); in fib6_repair_tree()
1267 return fn->parent; in fib6_repair_tree()
1270 pn = fn->parent; in fib6_repair_tree()
1272 if (FIB6_SUBTREE(pn) == fn) { in fib6_repair_tree()
1273 WARN_ON(!(fn->fn_flags & RTN_ROOT)); in fib6_repair_tree()
1277 WARN_ON(fn->fn_flags & RTN_ROOT); in fib6_repair_tree()
1279 if (pn->right == fn) in fib6_repair_tree()
1281 else if (pn->left == fn) in fib6_repair_tree()
1297 if (w->root == fn) { in fib6_repair_tree()
1300 } else if (w->node == fn) { in fib6_repair_tree()
1306 if (w->root == fn) { in fib6_repair_tree()
1310 if (w->node == fn) { in fib6_repair_tree()
1324 node_free(fn); in fib6_repair_tree()
1330 fn = pn; in fib6_repair_tree()
1334 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp, in fib6_del_route() argument
1350 if (fn->rr_ptr == rt) in fib6_del_route()
1351 fn->rr_ptr = NULL; in fib6_del_route()
1379 if (!fn->leaf) { in fib6_del_route()
1380 fn->fn_flags &= ~RTN_RTINFO; in fib6_del_route()
1382 fn = fib6_repair_tree(net, fn); in fib6_del_route()
1385 fib6_purge_rt(rt, fn, net); in fib6_del_route()
1394 struct fib6_node *fn = rt->rt6i_node; in fib6_del() local
1399 WARN_ON(fn); in fib6_del()
1403 if (!fn || rt == net->ipv6.ip6_null_entry) in fib6_del()
1406 WARN_ON(!(fn->fn_flags & RTN_RTINFO)); in fib6_del()
1409 struct fib6_node *pn = fn; in fib6_del()
1425 for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) { in fib6_del()
1427 fib6_del_route(fn, rtp, info); in fib6_del()
1460 struct fib6_node *fn, *pn; in fib6_walk_continue() local
1463 fn = w->node; in fib6_walk_continue()
1464 if (!fn) in fib6_walk_continue()
1467 if (w->prune && fn != w->root && in fib6_walk_continue()
1468 fn->fn_flags & RTN_RTINFO && w->state < FWS_C) { in fib6_walk_continue()
1470 w->leaf = fn->leaf; in fib6_walk_continue()
1475 if (FIB6_SUBTREE(fn)) { in fib6_walk_continue()
1476 w->node = FIB6_SUBTREE(fn); in fib6_walk_continue()
1482 if (fn->left) { in fib6_walk_continue()
1483 w->node = fn->left; in fib6_walk_continue()
1489 if (fn->right) { in fib6_walk_continue()
1490 w->node = fn->right; in fib6_walk_continue()
1495 w->leaf = fn->leaf; in fib6_walk_continue()
1497 if (w->leaf && fn->fn_flags & RTN_RTINFO) { in fib6_walk_continue()
1515 if (fn == w->root) in fib6_walk_continue()
1517 pn = fn->parent; in fib6_walk_continue()
1520 if (FIB6_SUBTREE(pn) == fn) { in fib6_walk_continue()
1521 WARN_ON(!(fn->fn_flags & RTN_ROOT)); in fib6_walk_continue()
1526 if (pn->left == fn) { in fib6_walk_continue()
1530 if (pn->right == fn) { in fib6_walk_continue()
1662 static void fib6_prune_clones(struct net *net, struct fib6_node *fn) in fib6_prune_clones() argument
1664 fib6_clean_tree(net, fn, fib6_prune_clone, true, in fib6_prune_clones()