59 					 struct fib6_node *fn);
62 					  struct fib6_node *fn);
109 	struct fib6_node *fn;  in fib6_update_sernum()  local
111 	fn = rcu_dereference_protected(f6i->fib6_node,  in fib6_update_sernum()
113 	if (fn)  in fib6_update_sernum()
114 		WRITE_ONCE(fn->fn_sernum, fib6_new_sernum(net));  in fib6_update_sernum()
186 	struct fib6_node *fn;  in node_alloc()  local
188 	fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);  in node_alloc()
189 	if (fn)  in node_alloc()
192 	return fn;  in node_alloc()
195 static void node_free_immediate(struct net *net, struct fib6_node *fn)  in node_free_immediate()  argument
197 	kmem_cache_free(fib6_node_kmem, fn);  in node_free_immediate()
201 static void node_free(struct net *net, struct fib6_node *fn)  in node_free()  argument
203 	kfree_rcu(fn, rcu);  in node_free()
748 	struct fib6_node *fn, *in, *ln;  in fib6_add_1()  local
756 	fn = root;  in fib6_add_1()
759 		struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_add_1()
766 		if (plen < fn->fn_bit ||  in fib6_add_1()
767 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {  in fib6_add_1()
784 		if (plen == fn->fn_bit) {  in fib6_add_1()
786 			if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_1()
787 				RCU_INIT_POINTER(fn->leaf, NULL);  in fib6_add_1()
790 			} else if (fn->fn_flags & RTN_TL_ROOT &&  in fib6_add_1()
791 				   rcu_access_pointer(fn->leaf) ==  in fib6_add_1()
793 				RCU_INIT_POINTER(fn->leaf, NULL);  in fib6_add_1()
796 			return fn;  in fib6_add_1()
804 		dir = addr_bit_set(addr, fn->fn_bit);  in fib6_add_1()
805 		pn = fn;  in fib6_add_1()
806 		fn = dir ?  in fib6_add_1()
807 		     rcu_dereference_protected(fn->right,  in fib6_add_1()
809 		     rcu_dereference_protected(fn->left,  in fib6_add_1()
811 	} while (fn);  in fib6_add_1()
860 	pn = rcu_dereference_protected(fn->parent,  in fib6_add_1()
899 		in->leaf = fn->leaf;  in fib6_add_1()
912 		rcu_assign_pointer(fn->parent, in);  in fib6_add_1()
916 			rcu_assign_pointer(in->left, fn);  in fib6_add_1()
919 			rcu_assign_pointer(in->right, fn);  in fib6_add_1()
939 			RCU_INIT_POINTER(ln->right, fn);  in fib6_add_1()
941 			RCU_INIT_POINTER(ln->left, fn);  in fib6_add_1()
943 		rcu_assign_pointer(fn->parent, ln);  in fib6_add_1()
1028 static void fib6_purge_rt(struct fib6_info *rt, struct fib6_node *fn,  in fib6_purge_rt()  argument
1047 		while (fn) {  in fib6_purge_rt()
1048 			struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_purge_rt()
1051 			if (!(fn->fn_flags & RTN_RTINFO) && leaf == rt) {  in fib6_purge_rt()
1052 				new_leaf = fib6_find_prefix(net, table, fn);  in fib6_purge_rt()
1055 				rcu_assign_pointer(fn->leaf, new_leaf);  in fib6_purge_rt()
1058 			fn = rcu_dereference_protected(fn->parent,  in fib6_purge_rt()
1071 static int fib6_add_rt2node(struct fib6_node *fn, struct fib6_info *rt,  in fib6_add_rt2node()  argument
1075 	struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_add_rt2node()
1093 	ins = &fn->leaf;  in fib6_add_rt2node()
1172 	if (ins == &fn->leaf)  in fib6_add_rt2node()
1173 		fn->rr_ptr = NULL;  in fib6_add_rt2node()
1224 		    (notify_sibling_rt || ins == &fn->leaf)) {  in fib6_add_rt2node()
1256 		rcu_assign_pointer(rt->fib6_node, fn);  in fib6_add_rt2node()
1262 		if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_rt2node()
1264 			fn->fn_flags |= RTN_RTINFO;  in fib6_add_rt2node()
1277 		if (!info->skip_notify_kernel && ins == &fn->leaf) {  in fib6_add_rt2node()
1286 		rcu_assign_pointer(rt->fib6_node, fn);  in fib6_add_rt2node()
1291 		if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_rt2node()
1293 			fn->fn_flags |= RTN_RTINFO;  in fib6_add_rt2node()
1297 		fib6_purge_rt(iter, fn, info->nl_net);  in fib6_add_rt2node()
1298 		if (rcu_access_pointer(fn->rr_ptr) == iter)  in fib6_add_rt2node()
1299 			fn->rr_ptr = NULL;  in fib6_add_rt2node()
1313 					fib6_purge_rt(iter, fn, info->nl_net);  in fib6_add_rt2node()
1314 					if (rcu_access_pointer(fn->rr_ptr) == iter)  in fib6_add_rt2node()
1315 						fn->rr_ptr = NULL;  in fib6_add_rt2node()
1350 	struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,  in __fib6_update_sernum_upto_root()  local
1355 	while (fn) {  in __fib6_update_sernum_upto_root()
1356 		WRITE_ONCE(fn->fn_sernum, sernum);  in __fib6_update_sernum_upto_root()
1357 		fn = rcu_dereference_protected(fn->parent,  in __fib6_update_sernum_upto_root()
1386 	struct fib6_node *fn;  in fib6_add()  local
1403 	fn = fib6_add_1(info->nl_net, table, root,  in fib6_add()
1407 	if (IS_ERR(fn)) {  in fib6_add()
1408 		err = PTR_ERR(fn);  in fib6_add()
1409 		fn = NULL;  in fib6_add()
1414 	pn = fn;  in fib6_add()
1419 		if (!rcu_access_pointer(fn->subtree)) {  in fib6_add()
1460 			rcu_assign_pointer(sfn->parent, fn);  in fib6_add()
1461 			rcu_assign_pointer(fn->subtree, sfn);  in fib6_add()
1463 			sn = fib6_add_1(info->nl_net, table, FIB6_SUBTREE(fn),  in fib6_add()
1474 		if (!rcu_access_pointer(fn->leaf)) {  in fib6_add()
1475 			if (fn->fn_flags & RTN_TL_ROOT) {  in fib6_add()
1477 				rcu_assign_pointer(fn->leaf,  in fib6_add()
1481 				rcu_assign_pointer(fn->leaf, rt);  in fib6_add()
1484 		fn = sn;  in fib6_add()
1488 	err = fib6_add_rt2node(fn, rt, info, extack);  in fib6_add()
1507 		if (pn != fn) {  in fib6_add()
1541 	if (fn &&  in fib6_add()
1542 	    (!(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)) ||  in fib6_add()
1543 	     (fn->fn_flags & RTN_TL_ROOT &&  in fib6_add()
1544 	      !rcu_access_pointer(fn->leaf))))  in fib6_add()
1545 		fib6_repair_tree(info->nl_net, table, fn);  in fib6_add()
1562 	struct fib6_node *fn;  in fib6_node_lookup_1()  local
1572 	fn = root;  in fib6_node_lookup_1()
1577 		dir = addr_bit_set(args->addr, fn->fn_bit);  in fib6_node_lookup_1()
1579 		next = dir ? rcu_dereference(fn->right) :  in fib6_node_lookup_1()
1580 			     rcu_dereference(fn->left);  in fib6_node_lookup_1()
1583 			fn = next;  in fib6_node_lookup_1()
1589 	while (fn) {  in fib6_node_lookup_1()
1590 		struct fib6_node *subtree = FIB6_SUBTREE(fn);  in fib6_node_lookup_1()
1592 		if (subtree || fn->fn_flags & RTN_RTINFO) {  in fib6_node_lookup_1()
1593 			struct fib6_info *leaf = rcu_dereference(fn->leaf);  in fib6_node_lookup_1()
1609 					fn = sfn;  in fib6_node_lookup_1()
1612 				if (fn->fn_flags & RTN_RTINFO)  in fib6_node_lookup_1()
1613 					return fn;  in fib6_node_lookup_1()
1617 		if (fn->fn_flags & RTN_ROOT)  in fib6_node_lookup_1()
1620 		fn = rcu_dereference(fn->parent);  in fib6_node_lookup_1()
1632 	struct fib6_node *fn;  in fib6_node_lookup()  local
1649 	fn = fib6_node_lookup_1(root, daddr ? args : args + 1);  in fib6_node_lookup()
1650 	if (!fn || fn->fn_flags & RTN_TL_ROOT)  in fib6_node_lookup()
1651 		fn = root;  in fib6_node_lookup()
1653 	return fn;  in fib6_node_lookup()
1673 	struct fib6_node *fn, *prev = NULL;  in fib6_locate_1()  local
1675 	for (fn = root; fn ; ) {  in fib6_locate_1()
1676 		struct fib6_info *leaf = rcu_dereference(fn->leaf);  in fib6_locate_1()
1681 			if (plen <= fn->fn_bit)  in fib6_locate_1()
1692 		if (plen < fn->fn_bit ||  in fib6_locate_1()
1693 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))  in fib6_locate_1()
1696 		if (plen == fn->fn_bit)  in fib6_locate_1()
1697 			return fn;  in fib6_locate_1()
1699 		if (fn->fn_flags & RTN_RTINFO)  in fib6_locate_1()
1700 			prev = fn;  in fib6_locate_1()
1706 		if (addr_bit_set(addr, fn->fn_bit))  in fib6_locate_1()
1707 			fn = rcu_dereference(fn->right);  in fib6_locate_1()
1709 			fn = rcu_dereference(fn->left);  in fib6_locate_1()
1723 	struct fib6_node *fn;  in fib6_locate()  local
1725 	fn = fib6_locate_1(root, daddr, dst_len,  in fib6_locate()
1732 		if (fn) {  in fib6_locate()
1733 			struct fib6_node *subtree = FIB6_SUBTREE(fn);  in fib6_locate()
1736 				fn = fib6_locate_1(subtree, saddr, src_len,  in fib6_locate()
1744 	if (fn && fn->fn_flags & RTN_RTINFO)  in fib6_locate()
1745 		return fn;  in fib6_locate()
1758 					 struct fib6_node *fn)  in fib6_find_prefix()  argument
1762 	if (fn->fn_flags & RTN_ROOT)  in fib6_find_prefix()
1765 	while (fn) {  in fib6_find_prefix()
1766 		child_left = rcu_dereference_protected(fn->left,  in fib6_find_prefix()
1768 		child_right = rcu_dereference_protected(fn->right,  in fib6_find_prefix()
1777 		fn = FIB6_SUBTREE(fn);  in fib6_find_prefix()
1790 					  struct fib6_node *fn)  in fib6_repair_tree()  argument
1799 	if (fn->fn_flags & RTN_TL_ROOT) {  in fib6_repair_tree()
1800 		rcu_assign_pointer(fn->leaf, net->ipv6.fib6_null_entry);  in fib6_repair_tree()
1801 		return fn;  in fib6_repair_tree()
1805 		struct fib6_node *fn_r = rcu_dereference_protected(fn->right,  in fib6_repair_tree()
1807 		struct fib6_node *fn_l = rcu_dereference_protected(fn->left,  in fib6_repair_tree()
1809 		struct fib6_node *pn = rcu_dereference_protected(fn->parent,  in fib6_repair_tree()
1815 		struct fib6_info *fn_leaf = rcu_dereference_protected(fn->leaf,  in fib6_repair_tree()
1821 		pr_debug("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);  in fib6_repair_tree()
1824 		WARN_ON(fn->fn_flags & RTN_RTINFO);  in fib6_repair_tree()
1825 		WARN_ON(fn->fn_flags & RTN_TL_ROOT);  in fib6_repair_tree()
1839 		if (children == 3 || FIB6_SUBTREE(fn)  in fib6_repair_tree()
1842 		    || (children && fn->fn_flags & RTN_ROOT)  in fib6_repair_tree()
1845 			new_fn_leaf = fib6_find_prefix(net, table, fn);  in fib6_repair_tree()
1853 			rcu_assign_pointer(fn->leaf, new_fn_leaf);  in fib6_repair_tree()
1858 		if (FIB6_SUBTREE(pn) == fn) {  in fib6_repair_tree()
1859 			WARN_ON(!(fn->fn_flags & RTN_ROOT));  in fib6_repair_tree()
1863 			WARN_ON(fn->fn_flags & RTN_ROOT);  in fib6_repair_tree()
1865 			if (pn_r == fn)  in fib6_repair_tree()
1867 			else if (pn_l == fn)  in fib6_repair_tree()
1883 				if (w->node == fn) {  in fib6_repair_tree()
1890 				if (w->node == fn) {  in fib6_repair_tree()
1906 		node_free(net, fn);  in fib6_repair_tree()
1912 		fn = pn;  in fib6_repair_tree()
1916 static void fib6_del_route(struct fib6_table *table, struct fib6_node *fn,  in fib6_del_route()  argument
1930 	leaf = rcu_dereference_protected(fn->leaf,  in fib6_del_route()
1947 	if (rcu_access_pointer(fn->rr_ptr) == rt)  in fib6_del_route()
1948 		fn->rr_ptr = NULL;  in fib6_del_route()
1987 	if (!rcu_access_pointer(fn->leaf)) {  in fib6_del_route()
1988 		if (!(fn->fn_flags & RTN_TL_ROOT)) {  in fib6_del_route()
1989 			fn->fn_flags &= ~RTN_RTINFO;  in fib6_del_route()
1992 		fn = fib6_repair_tree(net, table, fn);  in fib6_del_route()
1995 	fib6_purge_rt(rt, fn, net);  in fib6_del_route()
2017 	struct fib6_node *fn;  in fib6_del()  local
2023 	fn = rcu_dereference_protected(rt->fib6_node,  in fib6_del()
2025 	if (!fn)  in fib6_del()
2028 	WARN_ON(!(fn->fn_flags & RTN_RTINFO));  in fib6_del()
2034 	for (rtp = &fn->leaf; *rtp; rtp = rtp_next) {  in fib6_del()
2040 			fib6_del_route(table, fn, rtp, info);  in fib6_del()
2076 	struct fib6_node *fn, *pn, *left, *right;  in fib6_walk_continue()  local
2082 		fn = w->node;  in fib6_walk_continue()
2083 		if (!fn)  in fib6_walk_continue()
2089 			if (FIB6_SUBTREE(fn)) {  in fib6_walk_continue()
2090 				w->node = FIB6_SUBTREE(fn);  in fib6_walk_continue()
2097 			left = rcu_dereference_protected(fn->left, 1);  in fib6_walk_continue()
2106 			right = rcu_dereference_protected(fn->right, 1);  in fib6_walk_continue()
2113 			w->leaf = rcu_dereference_protected(fn->leaf, 1);  in fib6_walk_continue()
2116 			if (w->leaf && fn->fn_flags & RTN_RTINFO) {  in fib6_walk_continue()
2135 			if (fn == w->root)  in fib6_walk_continue()
2137 			pn = rcu_dereference_protected(fn->parent, 1);  in fib6_walk_continue()
2142 			if (FIB6_SUBTREE(pn) == fn) {  in fib6_walk_continue()
2143 				WARN_ON(!(fn->fn_flags & RTN_ROOT));  in fib6_walk_continue()
2148 			if (left == fn) {  in fib6_walk_continue()
2152 			if (right == fn) {  in fib6_walk_continue()