59 					 struct fib6_node *fn);
62 					  struct fib6_node *fn);
110 	struct fib6_node *fn;  in fib6_update_sernum()  local
112 	fn = rcu_dereference_protected(f6i->fib6_node,  in fib6_update_sernum()
114 	if (fn)  in fib6_update_sernum()
115 		WRITE_ONCE(fn->fn_sernum, fib6_new_sernum(net));  in fib6_update_sernum()
185 	struct fib6_node *fn;  in node_alloc()  local
187 	fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);  in node_alloc()
188 	if (fn)  in node_alloc()
191 	return fn;  in node_alloc()
194 static void node_free_immediate(struct net *net, struct fib6_node *fn)  in node_free_immediate()  argument
196 	kmem_cache_free(fib6_node_kmem, fn);  in node_free_immediate()
202 	struct fib6_node *fn = container_of(head, struct fib6_node, rcu);  in node_free_rcu()  local
204 	kmem_cache_free(fib6_node_kmem, fn);  in node_free_rcu()
207 static void node_free(struct net *net, struct fib6_node *fn)  in node_free()  argument
209 	call_rcu(&fn->rcu, node_free_rcu);  in node_free()
749 	struct fib6_node *fn, *in, *ln;  in fib6_add_1()  local
759 	fn = root;  in fib6_add_1()
762 		struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_add_1()
769 		if (plen < fn->fn_bit ||  in fib6_add_1()
770 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {  in fib6_add_1()
787 		if (plen == fn->fn_bit) {  in fib6_add_1()
789 			if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_1()
790 				RCU_INIT_POINTER(fn->leaf, NULL);  in fib6_add_1()
793 			} else if (fn->fn_flags & RTN_TL_ROOT &&  in fib6_add_1()
794 				   rcu_access_pointer(fn->leaf) ==  in fib6_add_1()
796 				RCU_INIT_POINTER(fn->leaf, NULL);  in fib6_add_1()
799 			return fn;  in fib6_add_1()
807 		dir = addr_bit_set(addr, fn->fn_bit);  in fib6_add_1()
808 		pn = fn;  in fib6_add_1()
809 		fn = dir ?  in fib6_add_1()
810 		     rcu_dereference_protected(fn->right,  in fib6_add_1()
812 		     rcu_dereference_protected(fn->left,  in fib6_add_1()
814 	} while (fn);  in fib6_add_1()
863 	pn = rcu_dereference_protected(fn->parent,  in fib6_add_1()
902 		in->leaf = fn->leaf;  in fib6_add_1()
915 		rcu_assign_pointer(fn->parent, in);  in fib6_add_1()
919 			rcu_assign_pointer(in->left, fn);  in fib6_add_1()
922 			rcu_assign_pointer(in->right, fn);  in fib6_add_1()
942 			RCU_INIT_POINTER(ln->right, fn);  in fib6_add_1()
944 			RCU_INIT_POINTER(ln->left, fn);  in fib6_add_1()
946 		rcu_assign_pointer(fn->parent, ln);  in fib6_add_1()
1027 static void fib6_purge_rt(struct fib6_info *rt, struct fib6_node *fn,  in fib6_purge_rt()  argument
1046 		while (fn) {  in fib6_purge_rt()
1047 			struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_purge_rt()
1050 			if (!(fn->fn_flags & RTN_RTINFO) && leaf == rt) {  in fib6_purge_rt()
1051 				new_leaf = fib6_find_prefix(net, table, fn);  in fib6_purge_rt()
1054 				rcu_assign_pointer(fn->leaf, new_leaf);  in fib6_purge_rt()
1057 			fn = rcu_dereference_protected(fn->parent,  in fib6_purge_rt()
1067 static int fib6_add_rt2node(struct fib6_node *fn, struct fib6_info *rt,  in fib6_add_rt2node()  argument
1071 	struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_add_rt2node()
1089 	ins = &fn->leaf;  in fib6_add_rt2node()
1165 	if (ins == &fn->leaf)  in fib6_add_rt2node()
1166 		fn->rr_ptr = NULL;  in fib6_add_rt2node()
1217 		    (notify_sibling_rt || ins == &fn->leaf)) {  in fib6_add_rt2node()
1249 		rcu_assign_pointer(rt->fib6_node, fn);  in fib6_add_rt2node()
1255 		if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_rt2node()
1257 			fn->fn_flags |= RTN_RTINFO;  in fib6_add_rt2node()
1270 		if (!info->skip_notify_kernel && ins == &fn->leaf) {  in fib6_add_rt2node()
1279 		rcu_assign_pointer(rt->fib6_node, fn);  in fib6_add_rt2node()
1284 		if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_rt2node()
1286 			fn->fn_flags |= RTN_RTINFO;  in fib6_add_rt2node()
1290 		fib6_purge_rt(iter, fn, info->nl_net);  in fib6_add_rt2node()
1291 		if (rcu_access_pointer(fn->rr_ptr) == iter)  in fib6_add_rt2node()
1292 			fn->rr_ptr = NULL;  in fib6_add_rt2node()
1306 					fib6_purge_rt(iter, fn, info->nl_net);  in fib6_add_rt2node()
1307 					if (rcu_access_pointer(fn->rr_ptr) == iter)  in fib6_add_rt2node()
1308 						fn->rr_ptr = NULL;  in fib6_add_rt2node()
1343 	struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,  in __fib6_update_sernum_upto_root()  local
1348 	while (fn) {  in __fib6_update_sernum_upto_root()
1349 		WRITE_ONCE(fn->fn_sernum, sernum);  in __fib6_update_sernum_upto_root()
1350 		fn = rcu_dereference_protected(fn->parent,  in __fib6_update_sernum_upto_root()
1379 	struct fib6_node *fn, *pn = NULL;  in fib6_add()  local
1393 	fn = fib6_add_1(info->nl_net, table, root,  in fib6_add()
1397 	if (IS_ERR(fn)) {  in fib6_add()
1398 		err = PTR_ERR(fn);  in fib6_add()
1399 		fn = NULL;  in fib6_add()
1403 	pn = fn;  in fib6_add()
1409 		if (!rcu_access_pointer(fn->subtree)) {  in fib6_add()
1450 			rcu_assign_pointer(sfn->parent, fn);  in fib6_add()
1451 			rcu_assign_pointer(fn->subtree, sfn);  in fib6_add()
1453 			sn = fib6_add_1(info->nl_net, table, FIB6_SUBTREE(fn),  in fib6_add()
1464 		if (!rcu_access_pointer(fn->leaf)) {  in fib6_add()
1465 			if (fn->fn_flags & RTN_TL_ROOT) {  in fib6_add()
1467 				rcu_assign_pointer(fn->leaf,  in fib6_add()
1471 				rcu_assign_pointer(fn->leaf, rt);  in fib6_add()
1474 		fn = sn;  in fib6_add()
1478 	err = fib6_add_rt2node(fn, rt, info, extack);  in fib6_add()
1493 		if (pn != fn) {  in fib6_add()
1531 	if (fn &&  in fib6_add()
1532 	    (!(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)) ||  in fib6_add()
1533 	     (fn->fn_flags & RTN_TL_ROOT &&  in fib6_add()
1534 	      !rcu_access_pointer(fn->leaf))))  in fib6_add()
1535 		fib6_repair_tree(info->nl_net, table, fn);  in fib6_add()
1552 	struct fib6_node *fn;  in fib6_node_lookup_1()  local
1562 	fn = root;  in fib6_node_lookup_1()
1567 		dir = addr_bit_set(args->addr, fn->fn_bit);  in fib6_node_lookup_1()
1569 		next = dir ? rcu_dereference(fn->right) :  in fib6_node_lookup_1()
1570 			     rcu_dereference(fn->left);  in fib6_node_lookup_1()
1573 			fn = next;  in fib6_node_lookup_1()
1579 	while (fn) {  in fib6_node_lookup_1()
1580 		struct fib6_node *subtree = FIB6_SUBTREE(fn);  in fib6_node_lookup_1()
1582 		if (subtree || fn->fn_flags & RTN_RTINFO) {  in fib6_node_lookup_1()
1583 			struct fib6_info *leaf = rcu_dereference(fn->leaf);  in fib6_node_lookup_1()
1599 					fn = sfn;  in fib6_node_lookup_1()
1602 				if (fn->fn_flags & RTN_RTINFO)  in fib6_node_lookup_1()
1603 					return fn;  in fib6_node_lookup_1()
1607 		if (fn->fn_flags & RTN_ROOT)  in fib6_node_lookup_1()
1610 		fn = rcu_dereference(fn->parent);  in fib6_node_lookup_1()
1622 	struct fib6_node *fn;  in fib6_node_lookup()  local
1639 	fn = fib6_node_lookup_1(root, daddr ? args : args + 1);  in fib6_node_lookup()
1640 	if (!fn || fn->fn_flags & RTN_TL_ROOT)  in fib6_node_lookup()
1641 		fn = root;  in fib6_node_lookup()
1643 	return fn;  in fib6_node_lookup()
1663 	struct fib6_node *fn, *prev = NULL;  in fib6_locate_1()  local
1665 	for (fn = root; fn ; ) {  in fib6_locate_1()
1666 		struct fib6_info *leaf = rcu_dereference(fn->leaf);  in fib6_locate_1()
1671 			if (plen <= fn->fn_bit)  in fib6_locate_1()
1682 		if (plen < fn->fn_bit ||  in fib6_locate_1()
1683 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))  in fib6_locate_1()
1686 		if (plen == fn->fn_bit)  in fib6_locate_1()
1687 			return fn;  in fib6_locate_1()
1689 		if (fn->fn_flags & RTN_RTINFO)  in fib6_locate_1()
1690 			prev = fn;  in fib6_locate_1()
1696 		if (addr_bit_set(addr, fn->fn_bit))  in fib6_locate_1()
1697 			fn = rcu_dereference(fn->right);  in fib6_locate_1()
1699 			fn = rcu_dereference(fn->left);  in fib6_locate_1()
1713 	struct fib6_node *fn;  in fib6_locate()  local
1715 	fn = fib6_locate_1(root, daddr, dst_len,  in fib6_locate()
1722 		if (fn) {  in fib6_locate()
1723 			struct fib6_node *subtree = FIB6_SUBTREE(fn);  in fib6_locate()
1726 				fn = fib6_locate_1(subtree, saddr, src_len,  in fib6_locate()
1734 	if (fn && fn->fn_flags & RTN_RTINFO)  in fib6_locate()
1735 		return fn;  in fib6_locate()
1748 					 struct fib6_node *fn)  in fib6_find_prefix()  argument
1752 	if (fn->fn_flags & RTN_ROOT)  in fib6_find_prefix()
1755 	while (fn) {  in fib6_find_prefix()
1756 		child_left = rcu_dereference_protected(fn->left,  in fib6_find_prefix()
1758 		child_right = rcu_dereference_protected(fn->right,  in fib6_find_prefix()
1767 		fn = FIB6_SUBTREE(fn);  in fib6_find_prefix()
1780 					  struct fib6_node *fn)  in fib6_repair_tree()  argument
1789 	if (fn->fn_flags & RTN_TL_ROOT) {  in fib6_repair_tree()
1790 		rcu_assign_pointer(fn->leaf, net->ipv6.fib6_null_entry);  in fib6_repair_tree()
1791 		return fn;  in fib6_repair_tree()
1795 		struct fib6_node *fn_r = rcu_dereference_protected(fn->right,  in fib6_repair_tree()
1797 		struct fib6_node *fn_l = rcu_dereference_protected(fn->left,  in fib6_repair_tree()
1799 		struct fib6_node *pn = rcu_dereference_protected(fn->parent,  in fib6_repair_tree()
1805 		struct fib6_info *fn_leaf = rcu_dereference_protected(fn->leaf,  in fib6_repair_tree()
1811 		RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);  in fib6_repair_tree()
1814 		WARN_ON(fn->fn_flags & RTN_RTINFO);  in fib6_repair_tree()
1815 		WARN_ON(fn->fn_flags & RTN_TL_ROOT);  in fib6_repair_tree()
1829 		if (children == 3 || FIB6_SUBTREE(fn)  in fib6_repair_tree()
1832 		    || (children && fn->fn_flags & RTN_ROOT)  in fib6_repair_tree()
1835 			new_fn_leaf = fib6_find_prefix(net, table, fn);  in fib6_repair_tree()
1843 			rcu_assign_pointer(fn->leaf, new_fn_leaf);  in fib6_repair_tree()
1848 		if (FIB6_SUBTREE(pn) == fn) {  in fib6_repair_tree()
1849 			WARN_ON(!(fn->fn_flags & RTN_ROOT));  in fib6_repair_tree()
1853 			WARN_ON(fn->fn_flags & RTN_ROOT);  in fib6_repair_tree()
1855 			if (pn_r == fn)  in fib6_repair_tree()
1857 			else if (pn_l == fn)  in fib6_repair_tree()
1873 				if (w->node == fn) {  in fib6_repair_tree()
1879 				if (w->node == fn) {  in fib6_repair_tree()
1893 		node_free(net, fn);  in fib6_repair_tree()
1899 		fn = pn;  in fib6_repair_tree()
1903 static void fib6_del_route(struct fib6_table *table, struct fib6_node *fn,  in fib6_del_route()  argument
1919 	leaf = rcu_dereference_protected(fn->leaf,  in fib6_del_route()
1936 	if (rcu_access_pointer(fn->rr_ptr) == rt)  in fib6_del_route()
1937 		fn->rr_ptr = NULL;  in fib6_del_route()
1976 	if (!rcu_access_pointer(fn->leaf)) {  in fib6_del_route()
1977 		if (!(fn->fn_flags & RTN_TL_ROOT)) {  in fib6_del_route()
1978 			fn->fn_flags &= ~RTN_RTINFO;  in fib6_del_route()
1981 		fn = fib6_repair_tree(net, table, fn);  in fib6_del_route()
1984 	fib6_purge_rt(rt, fn, net);  in fib6_del_route()
2006 	struct fib6_node *fn;  in fib6_del()  local
2012 	fn = rcu_dereference_protected(rt->fib6_node,  in fib6_del()
2014 	if (!fn)  in fib6_del()
2017 	WARN_ON(!(fn->fn_flags & RTN_RTINFO));  in fib6_del()
2023 	for (rtp = &fn->leaf; *rtp; rtp = rtp_next) {  in fib6_del()
2029 			fib6_del_route(table, fn, rtp, info);  in fib6_del()
2065 	struct fib6_node *fn, *pn, *left, *right;  in fib6_walk_continue()  local
2071 		fn = w->node;  in fib6_walk_continue()
2072 		if (!fn)  in fib6_walk_continue()
2078 			if (FIB6_SUBTREE(fn)) {  in fib6_walk_continue()
2079 				w->node = FIB6_SUBTREE(fn);  in fib6_walk_continue()
2086 			left = rcu_dereference_protected(fn->left, 1);  in fib6_walk_continue()
2095 			right = rcu_dereference_protected(fn->right, 1);  in fib6_walk_continue()
2102 			w->leaf = rcu_dereference_protected(fn->leaf, 1);  in fib6_walk_continue()
2105 			if (w->leaf && fn->fn_flags & RTN_RTINFO) {  in fib6_walk_continue()
2124 			if (fn == w->root)  in fib6_walk_continue()
2126 			pn = rcu_dereference_protected(fn->parent, 1);  in fib6_walk_continue()
2131 			if (FIB6_SUBTREE(pn) == fn) {  in fib6_walk_continue()
2132 				WARN_ON(!(fn->fn_flags & RTN_ROOT));  in fib6_walk_continue()
2137 			if (left == fn) {  in fib6_walk_continue()
2141 			if (right == fn) {  in fib6_walk_continue()