Lines Matching refs:fn
79 static void fib6_prune_clones(struct net *net, struct fib6_node *fn,
81 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn);
82 static struct fib6_node *fib6_repair_tree(struct net *net, struct fib6_node *fn);
153 struct fib6_node *fn;
155 fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
157 return fn;
160 static __inline__ void node_free(struct fib6_node * fn)
162 kmem_cache_free(fib6_node_kmem, fn);
432 struct fib6_node *fn, *in, *ln;
443 fn = root;
446 key = (struct rt6key *)((u8 *)fn->leaf + offset);
451 if (plen < fn->fn_bit ||
452 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
459 if (plen == fn->fn_bit) {
461 if ((fn->fn_flags & RTN_RTINFO) == 0) {
462 rt6_release(fn->leaf);
463 fn->leaf = NULL;
466 fn->fn_sernum = sernum;
468 return fn;
476 fn->fn_sernum = sernum;
477 dir = addr_bit_set(addr, fn->fn_bit);
478 pn = fn;
479 fn = dir ? fn->right: fn->left;
480 } while (fn);
513 pn = fn->parent;
526 * (new leaf node)[ln] (old node)[fn]
551 in->leaf = fn->leaf;
565 fn->parent = in;
571 in->left = fn;
574 in->right = fn;
581 * (old node)[fn] NULL
601 ln->right = fn;
603 ln->left = fn;
605 fn->parent = ln;
614 static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
620 ins = &fn->leaf;
622 for (iter = fn->leaf; iter; iter=iter->dst.rt6_next) {
654 if (ins == &fn->leaf)
655 fn->rr_ptr = NULL;
663 rt->rt6i_node = fn;
668 if ((fn->fn_flags & RTN_RTINFO) == 0) {
670 fn->fn_flags |= RTN_RTINFO;
699 struct fib6_node *fn, *pn = NULL;
702 fn = fib6_add_1(root, &rt->rt6i_dst.addr, sizeof(struct in6_addr),
705 if (fn == NULL)
708 pn = fn;
714 if (fn->subtree == NULL) {
720 * fn[main tree]
753 sfn->parent = fn;
754 fn->subtree = sfn;
756 sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
764 if (fn->leaf == NULL) {
765 fn->leaf = rt;
768 fn = sn;
772 err = fib6_add_rt2node(fn, rt, info);
787 if (pn != fn && pn->leaf == rt) {
791 if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) {
811 if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
812 fib6_repair_tree(info->nl_net, fn);
831 struct fib6_node *fn;
841 fn = root;
846 dir = addr_bit_set(args->addr, fn->fn_bit);
848 next = dir ? fn->right : fn->left;
851 fn = next;
858 while(fn) {
859 if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) {
862 key = (struct rt6key *) ((u8 *) fn->leaf +
867 if (fn->subtree)
868 fn = fib6_lookup_1(fn->subtree, args + 1);
870 if (!fn || fn->fn_flags & RTN_RTINFO)
871 return fn;
875 if (fn->fn_flags & RTN_ROOT)
878 fn = fn->parent;
887 struct fib6_node *fn;
904 fn = fib6_lookup_1(root, daddr ? args : args + 1);
906 if (fn == NULL || fn->fn_flags & RTN_TL_ROOT)
907 fn = root;
909 return fn;
922 struct fib6_node *fn;
924 for (fn = root; fn ; ) {
925 struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
930 if (plen < fn->fn_bit ||
931 !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
934 if (plen == fn->fn_bit)
935 return fn;
940 if (addr_bit_set(addr, fn->fn_bit))
941 fn = fn->right;
943 fn = fn->left;
952 struct fib6_node *fn;
954 fn = fib6_locate_1(root, daddr, dst_len,
960 if (fn && fn->subtree)
961 fn = fib6_locate_1(fn->subtree, saddr, src_len,
966 if (fn && fn->fn_flags&RTN_RTINFO)
967 return fn;
978 static struct rt6_info *fib6_find_prefix(struct net *net, struct fib6_node *fn)
980 if (fn->fn_flags&RTN_ROOT)
983 while(fn) {
984 if(fn->left)
985 return fn->left->leaf;
987 if(fn->right)
988 return fn->right->leaf;
990 fn = FIB6_SUBTREE(fn);
996 * Called to trim the tree of intermediate nodes when possible. "fn"
1001 struct fib6_node *fn)
1010 RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
1013 WARN_ON(fn->fn_flags & RTN_RTINFO);
1014 WARN_ON(fn->fn_flags & RTN_TL_ROOT);
1015 WARN_ON(fn->leaf != NULL);
1019 if (fn->right) child = fn->right, children |= 1;
1020 if (fn->left) child = fn->left, children |= 2;
1022 if (children == 3 || FIB6_SUBTREE(fn)
1024 /* Subtree root (i.e. fn) may have one child */
1025 || (children && fn->fn_flags&RTN_ROOT)
1028 fn->leaf = fib6_find_prefix(net, fn);
1030 if (fn->leaf==NULL) {
1031 WARN_ON(!fn->leaf);
1032 fn->leaf = net->ipv6.ip6_null_entry;
1035 atomic_inc(&fn->leaf->rt6i_ref);
1036 return fn->parent;
1039 pn = fn->parent;
1041 if (FIB6_SUBTREE(pn) == fn) {
1042 WARN_ON(!(fn->fn_flags & RTN_ROOT));
1046 WARN_ON(fn->fn_flags & RTN_ROOT);
1048 if (pn->right == fn) pn->right = child;
1049 else if (pn->left == fn) pn->left = child;
1064 if (w->root == fn) {
1067 } else if (w->node == fn) {
1073 if (w->root == fn) {
1077 if (w->node == fn) {
1091 node_free(fn);
1097 fn = pn;
1101 static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
1117 if (fn->rr_ptr == rt)
1118 fn->rr_ptr = NULL;
1135 if (fn->leaf == NULL) {
1136 fn->fn_flags &= ~RTN_RTINFO;
1138 fn = fib6_repair_tree(net, fn);
1148 while (fn) {
1149 if (!(fn->fn_flags&RTN_RTINFO) && fn->leaf == rt) {
1150 fn->leaf = fib6_find_prefix(net, fn);
1151 atomic_inc(&fn->leaf->rt6i_ref);
1154 fn = fn->parent;
1167 struct fib6_node *fn = rt->rt6i_node;
1172 WARN_ON(fn != NULL);
1176 if (fn == NULL || rt == net->ipv6.ip6_null_entry)
1179 WARN_ON(!(fn->fn_flags & RTN_RTINFO));
1182 struct fib6_node *pn = fn;
1198 for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->dst.rt6_next) {
1200 fib6_del_route(fn, rtp, info);
1233 struct fib6_node *fn, *pn;
1236 fn = w->node;
1237 if (fn == NULL)
1240 if (w->prune && fn != w->root &&
1241 fn->fn_flags&RTN_RTINFO && w->state < FWS_C) {
1243 w->leaf = fn->leaf;
1248 if (FIB6_SUBTREE(fn)) {
1249 w->node = FIB6_SUBTREE(fn);
1255 if (fn->left) {
1256 w->node = fn->left;
1262 if (fn->right) {
1263 w->node = fn->right;
1268 w->leaf = fn->leaf;
1270 if (w->leaf && fn->fn_flags&RTN_RTINFO) {
1287 if (fn == w->root)
1289 pn = fn->parent;
1292 if (FIB6_SUBTREE(pn) == fn) {
1293 WARN_ON(!(fn->fn_flags & RTN_ROOT));
1298 if (pn->left == fn) {
1302 if (pn->right == fn) {
1416 static void fib6_prune_clones(struct net *net, struct fib6_node *fn,
1419 fib6_clean_tree(net, fn, fib6_prune_clone, 1, rt);