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()
203 	struct fib6_node *fn = container_of(head, struct fib6_node, rcu);  in node_free_rcu()  local
205 	kmem_cache_free(fib6_node_kmem, fn);  in node_free_rcu()
208 static void node_free(struct net *net, struct fib6_node *fn)  in node_free()  argument
210 	call_rcu(&fn->rcu, node_free_rcu);  in node_free()
755 	struct fib6_node *fn, *in, *ln;  in fib6_add_1()  local
763 	fn = root;  in fib6_add_1()
766 		struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_add_1()
773 		if (plen < fn->fn_bit ||  in fib6_add_1()
774 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {  in fib6_add_1()
791 		if (plen == fn->fn_bit) {  in fib6_add_1()
793 			if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_1()
794 				RCU_INIT_POINTER(fn->leaf, NULL);  in fib6_add_1()
797 			} else if (fn->fn_flags & RTN_TL_ROOT &&  in fib6_add_1()
798 				   rcu_access_pointer(fn->leaf) ==  in fib6_add_1()
800 				RCU_INIT_POINTER(fn->leaf, NULL);  in fib6_add_1()
803 			return fn;  in fib6_add_1()
811 		dir = addr_bit_set(addr, fn->fn_bit);  in fib6_add_1()
812 		pn = fn;  in fib6_add_1()
813 		fn = dir ?  in fib6_add_1()
814 		     rcu_dereference_protected(fn->right,  in fib6_add_1()
816 		     rcu_dereference_protected(fn->left,  in fib6_add_1()
818 	} while (fn);  in fib6_add_1()
867 	pn = rcu_dereference_protected(fn->parent,  in fib6_add_1()
881 	 *	(new leaf node)[ln] (old node)[fn]  in fib6_add_1()
906 		in->leaf = fn->leaf;  in fib6_add_1()
919 		rcu_assign_pointer(fn->parent, in);  in fib6_add_1()
923 			rcu_assign_pointer(in->left, fn);  in fib6_add_1()
926 			rcu_assign_pointer(in->right, fn);  in fib6_add_1()
933 		 *	     (old node)[fn] NULL  in fib6_add_1()
946 			RCU_INIT_POINTER(ln->right, fn);  in fib6_add_1()
948 			RCU_INIT_POINTER(ln->left, fn);  in fib6_add_1()
950 		rcu_assign_pointer(fn->parent, ln);  in fib6_add_1()
1035 static void fib6_purge_rt(struct fib6_info *rt, struct fib6_node *fn,  in fib6_purge_rt()  argument
1054 		while (fn) {  in fib6_purge_rt()
1055 			struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_purge_rt()
1058 			if (!(fn->fn_flags & RTN_RTINFO) && leaf == rt) {  in fib6_purge_rt()
1059 				new_leaf = fib6_find_prefix(net, table, fn);  in fib6_purge_rt()
1062 				rcu_assign_pointer(fn->leaf, new_leaf);  in fib6_purge_rt()
1065 			fn = rcu_dereference_protected(fn->parent,  in fib6_purge_rt()
1078 static int fib6_add_rt2node(struct fib6_node *fn, struct fib6_info *rt,  in fib6_add_rt2node()  argument
1082 	struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,  in fib6_add_rt2node()
1100 	ins = &fn->leaf;  in fib6_add_rt2node()
1179 	if (ins == &fn->leaf)  in fib6_add_rt2node()
1180 		fn->rr_ptr = NULL;  in fib6_add_rt2node()
1231 		    (notify_sibling_rt || ins == &fn->leaf)) {  in fib6_add_rt2node()
1263 		rcu_assign_pointer(rt->fib6_node, fn);  in fib6_add_rt2node()
1269 		if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_rt2node()
1271 			fn->fn_flags |= RTN_RTINFO;  in fib6_add_rt2node()
1284 		if (!info->skip_notify_kernel && ins == &fn->leaf) {  in fib6_add_rt2node()
1293 		rcu_assign_pointer(rt->fib6_node, fn);  in fib6_add_rt2node()
1298 		if (!(fn->fn_flags & RTN_RTINFO)) {  in fib6_add_rt2node()
1300 			fn->fn_flags |= RTN_RTINFO;  in fib6_add_rt2node()
1304 		fib6_purge_rt(iter, fn, info->nl_net);  in fib6_add_rt2node()
1305 		if (rcu_access_pointer(fn->rr_ptr) == iter)  in fib6_add_rt2node()
1306 			fn->rr_ptr = NULL;  in fib6_add_rt2node()
1320 					fib6_purge_rt(iter, fn, info->nl_net);  in fib6_add_rt2node()
1321 					if (rcu_access_pointer(fn->rr_ptr) == iter)  in fib6_add_rt2node()
1322 						fn->rr_ptr = NULL;  in fib6_add_rt2node()
1357 	struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,  in __fib6_update_sernum_upto_root()  local
1362 	while (fn) {  in __fib6_update_sernum_upto_root()
1363 		WRITE_ONCE(fn->fn_sernum, sernum);  in __fib6_update_sernum_upto_root()
1364 		fn = rcu_dereference_protected(fn->parent,  in __fib6_update_sernum_upto_root()
1393 	struct fib6_node *fn;  in fib6_add()  local
1410 	fn = fib6_add_1(info->nl_net, table, root,  in fib6_add()
1414 	if (IS_ERR(fn)) {  in fib6_add()
1415 		err = PTR_ERR(fn);  in fib6_add()
1416 		fn = NULL;  in fib6_add()
1421 	pn = fn;  in fib6_add()
1426 		if (!rcu_access_pointer(fn->subtree)) {  in fib6_add()
1432 			 *		fn[main tree]  in fib6_add()
1467 			rcu_assign_pointer(sfn->parent, fn);  in fib6_add()
1468 			rcu_assign_pointer(fn->subtree, sfn);  in fib6_add()
1470 			sn = fib6_add_1(info->nl_net, table, FIB6_SUBTREE(fn),  in fib6_add()
1481 		if (!rcu_access_pointer(fn->leaf)) {  in fib6_add()
1482 			if (fn->fn_flags & RTN_TL_ROOT) {  in fib6_add()
1484 				rcu_assign_pointer(fn->leaf,  in fib6_add()
1488 				rcu_assign_pointer(fn->leaf, rt);  in fib6_add()
1491 		fn = sn;  in fib6_add()
1495 	err = fib6_add_rt2node(fn, rt, info, extack);  in fib6_add()
1514 		if (pn != fn) {  in fib6_add()
1541 	/* fn->leaf could be NULL and fib6_repair_tree() needs to be called if:  in fib6_add()
1542 	 * 1. fn is an intermediate node and we failed to add the new  in fib6_add()
1545 	 * 2. fn is the root node in the table and we fail to add the first  in fib6_add()
1548 	if (fn &&  in fib6_add()
1549 	    (!(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)) ||  in fib6_add()
1550 	     (fn->fn_flags & RTN_TL_ROOT &&  in fib6_add()
1551 	      !rcu_access_pointer(fn->leaf))))  in fib6_add()
1552 		fib6_repair_tree(info->nl_net, table, fn);  in fib6_add()
1569 	struct fib6_node *fn;  in fib6_node_lookup_1()  local
1579 	fn = root;  in fib6_node_lookup_1()
1584 		dir = addr_bit_set(args->addr, fn->fn_bit);  in fib6_node_lookup_1()
1586 		next = dir ? rcu_dereference(fn->right) :  in fib6_node_lookup_1()
1587 			     rcu_dereference(fn->left);  in fib6_node_lookup_1()
1590 			fn = next;  in fib6_node_lookup_1()
1596 	while (fn) {  in fib6_node_lookup_1()
1597 		struct fib6_node *subtree = FIB6_SUBTREE(fn);  in fib6_node_lookup_1()
1599 		if (subtree || fn->fn_flags & RTN_RTINFO) {  in fib6_node_lookup_1()
1600 			struct fib6_info *leaf = rcu_dereference(fn->leaf);  in fib6_node_lookup_1()
1616 					fn = sfn;  in fib6_node_lookup_1()
1619 				if (fn->fn_flags & RTN_RTINFO)  in fib6_node_lookup_1()
1620 					return fn;  in fib6_node_lookup_1()
1624 		if (fn->fn_flags & RTN_ROOT)  in fib6_node_lookup_1()
1627 		fn = rcu_dereference(fn->parent);  in fib6_node_lookup_1()
1639 	struct fib6_node *fn;  in fib6_node_lookup()  local
1656 	fn = fib6_node_lookup_1(root, daddr ? args : args + 1);  in fib6_node_lookup()
1657 	if (!fn || fn->fn_flags & RTN_TL_ROOT)  in fib6_node_lookup()
1658 		fn = root;  in fib6_node_lookup()
1660 	return fn;  in fib6_node_lookup()
1666  *	exact_match == true means we try to find fn with exact match of
1668  *	exact_match == false means we try to find fn with longest prefix
1669  *	match of the passed in prefix addr. This is useful for finding fn
1680 	struct fib6_node *fn, *prev = NULL;  in fib6_locate_1()  local
1682 	for (fn = root; fn ; ) {  in fib6_locate_1()
1683 		struct fib6_info *leaf = rcu_dereference(fn->leaf);  in fib6_locate_1()
1688 			if (plen <= fn->fn_bit)  in fib6_locate_1()
1699 		if (plen < fn->fn_bit ||  in fib6_locate_1()
1700 		    !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))  in fib6_locate_1()
1703 		if (plen == fn->fn_bit)  in fib6_locate_1()
1704 			return fn;  in fib6_locate_1()
1706 		if (fn->fn_flags & RTN_RTINFO)  in fib6_locate_1()
1707 			prev = fn;  in fib6_locate_1()
1713 		if (addr_bit_set(addr, fn->fn_bit))  in fib6_locate_1()
1714 			fn = rcu_dereference(fn->right);  in fib6_locate_1()
1716 			fn = rcu_dereference(fn->left);  in fib6_locate_1()
1730 	struct fib6_node *fn;  in fib6_locate()  local
1732 	fn = fib6_locate_1(root, daddr, dst_len,  in fib6_locate()
1739 		if (fn) {  in fib6_locate()
1740 			struct fib6_node *subtree = FIB6_SUBTREE(fn);  in fib6_locate()
1743 				fn = fib6_locate_1(subtree, saddr, src_len,  in fib6_locate()
1751 	if (fn && fn->fn_flags & RTN_RTINFO)  in fib6_locate()
1752 		return fn;  in fib6_locate()
1765 					 struct fib6_node *fn)  in fib6_find_prefix()  argument
1769 	if (fn->fn_flags & RTN_ROOT)  in fib6_find_prefix()
1772 	while (fn) {  in fib6_find_prefix()
1773 		child_left = rcu_dereference_protected(fn->left,  in fib6_find_prefix()
1775 		child_right = rcu_dereference_protected(fn->right,  in fib6_find_prefix()
1784 		fn = FIB6_SUBTREE(fn);  in fib6_find_prefix()
1790  *	Called to trim the tree of intermediate nodes when possible. "fn"
1797 					  struct fib6_node *fn)  in fib6_repair_tree()  argument
1805 	/* Set fn->leaf to null_entry for root node. */  in fib6_repair_tree()
1806 	if (fn->fn_flags & RTN_TL_ROOT) {  in fib6_repair_tree()
1807 		rcu_assign_pointer(fn->leaf, net->ipv6.fib6_null_entry);  in fib6_repair_tree()
1808 		return fn;  in fib6_repair_tree()
1812 		struct fib6_node *fn_r = rcu_dereference_protected(fn->right,  in fib6_repair_tree()
1814 		struct fib6_node *fn_l = rcu_dereference_protected(fn->left,  in fib6_repair_tree()
1816 		struct fib6_node *pn = rcu_dereference_protected(fn->parent,  in fib6_repair_tree()
1822 		struct fib6_info *fn_leaf = rcu_dereference_protected(fn->leaf,  in fib6_repair_tree()
1828 		pr_debug("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);  in fib6_repair_tree()
1831 		WARN_ON(fn->fn_flags & RTN_RTINFO);  in fib6_repair_tree()
1832 		WARN_ON(fn->fn_flags & RTN_TL_ROOT);  in fib6_repair_tree()
1846 		if (children == 3 || FIB6_SUBTREE(fn)  in fib6_repair_tree()
1848 		    /* Subtree root (i.e. fn) may have one child */  in fib6_repair_tree()
1849 		    || (children && fn->fn_flags & RTN_ROOT)  in fib6_repair_tree()
1852 			new_fn_leaf = fib6_find_prefix(net, table, fn);  in fib6_repair_tree()
1860 			rcu_assign_pointer(fn->leaf, new_fn_leaf);  in fib6_repair_tree()
1865 		if (FIB6_SUBTREE(pn) == fn) {  in fib6_repair_tree()
1866 			WARN_ON(!(fn->fn_flags & RTN_ROOT));  in fib6_repair_tree()
1870 			WARN_ON(fn->fn_flags & RTN_ROOT);  in fib6_repair_tree()
1872 			if (pn_r == fn)  in fib6_repair_tree()
1874 			else if (pn_l == fn)  in fib6_repair_tree()
1890 				if (w->node == fn) {  in fib6_repair_tree()
1897 				if (w->node == fn) {  in fib6_repair_tree()
1913 		node_free(net, fn);  in fib6_repair_tree()
1919 		fn = pn;  in fib6_repair_tree()
1923 static void fib6_del_route(struct fib6_table *table, struct fib6_node *fn,  in fib6_del_route()  argument
1937 	leaf = rcu_dereference_protected(fn->leaf,  in fib6_del_route()
1954 	if (rcu_access_pointer(fn->rr_ptr) == rt)  in fib6_del_route()
1955 		fn->rr_ptr = NULL;  in fib6_del_route()
1994 	if (!rcu_access_pointer(fn->leaf)) {  in fib6_del_route()
1995 		if (!(fn->fn_flags & RTN_TL_ROOT)) {  in fib6_del_route()
1996 			fn->fn_flags &= ~RTN_RTINFO;  in fib6_del_route()
1999 		fn = fib6_repair_tree(net, table, fn);  in fib6_del_route()
2002 	fib6_purge_rt(rt, fn, net);  in fib6_del_route()
2024 	struct fib6_node *fn;  in fib6_del()  local
2030 	fn = rcu_dereference_protected(rt->fib6_node,  in fib6_del()
2032 	if (!fn)  in fib6_del()
2035 	WARN_ON(!(fn->fn_flags & RTN_RTINFO));  in fib6_del()
2041 	for (rtp = &fn->leaf; *rtp; rtp = rtp_next) {  in fib6_del()
2047 			fib6_del_route(table, fn, rtp, info);  in fib6_del()
2083 	struct fib6_node *fn, *pn, *left, *right;  in fib6_walk_continue()  local
2089 		fn = w->node;  in fib6_walk_continue()
2090 		if (!fn)  in fib6_walk_continue()
2096 			if (FIB6_SUBTREE(fn)) {  in fib6_walk_continue()
2097 				w->node = FIB6_SUBTREE(fn);  in fib6_walk_continue()
2104 			left = rcu_dereference_protected(fn->left, 1);  in fib6_walk_continue()
2113 			right = rcu_dereference_protected(fn->right, 1);  in fib6_walk_continue()
2120 			w->leaf = rcu_dereference_protected(fn->leaf, 1);  in fib6_walk_continue()
2123 			if (w->leaf && fn->fn_flags & RTN_RTINFO) {  in fib6_walk_continue()
2142 			if (fn == w->root)  in fib6_walk_continue()
2144 			pn = rcu_dereference_protected(fn->parent, 1);  in fib6_walk_continue()
2149 			if (FIB6_SUBTREE(pn) == fn) {  in fib6_walk_continue()
2150 				WARN_ON(!(fn->fn_flags & RTN_ROOT));  in fib6_walk_continue()
2155 			if (left == fn) {  in fib6_walk_continue()
2159 			if (right == fn) {  in fib6_walk_continue()