94 #define IS_TRIE(n)	((n)->pos >= KEYLENGTH)  argument
95 #define IS_TNODE(n)	((n)->bits)  argument
96 #define IS_LEAF(n)	(!(n)->bits)  argument
120 #define TNODE_SIZE(n)	offsetof(struct tnode, kv[0].tnode[n])  argument
178 static inline void node_set_parent(struct key_vector *n, struct key_vector *tp)  in node_set_parent()  argument
180 	if (n)  in node_set_parent()
181 		rcu_assign_pointer(tn_info(n)->parent, tp);  in node_set_parent()
184 #define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER(tn_info(n)->parent, p)  argument
288 	struct tnode *n = container_of(head, struct tnode, rcu);  in __node_free_rcu()  local
290 	if (!n->tn_bits)  in __node_free_rcu()
291 		kmem_cache_free(trie_leaf_kmem, n);  in __node_free_rcu()
292 	else if (n->tn_bits <= TNODE_KMALLOC_MAX)  in __node_free_rcu()
293 		kfree(n);  in __node_free_rcu()
295 		vfree(n);  in __node_free_rcu()
298 #define node_free(n) call_rcu(&tn_info(n)->rcu, __node_free_rcu)  argument
317 static inline void empty_child_inc(struct key_vector *n)  in empty_child_inc()  argument
319 	++tn_info(n)->empty_children ? : ++tn_info(n)->full_children;  in empty_child_inc()
322 static inline void empty_child_dec(struct key_vector *n)  in empty_child_dec()  argument
324 	tn_info(n)->empty_children-- ? : tn_info(n)->full_children--;  in empty_child_dec()
383 static inline int tnode_full(struct key_vector *tn, struct key_vector *n)  in tnode_full()  argument
385 	return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);  in tnode_full()
392 		      struct key_vector *n)  in put_child()  argument
400 	if (!n && chi)  in put_child()
402 	if (n && !chi)  in put_child()
407 	isfull = tnode_full(tn, n);  in put_child()
414 	if (n && (tn->slen < n->slen))  in put_child()
415 		tn->slen = n->slen;  in put_child()
417 	rcu_assign_pointer(tn->tnode[i], n);  in put_child()
443 				  struct key_vector *n)  in put_child_root()  argument
446 		rcu_assign_pointer(tp->tnode[0], n);  in put_child_root()
448 		put_child(tp, get_index(key, tp), n);  in put_child_root()
457 				     struct key_vector *n)  in tnode_free_append()  argument
459 	tn_info(n)->rcu.next = tn_info(tn)->rcu.next;  in tnode_free_append()
460 	tn_info(tn)->rcu.next = &tn_info(n)->rcu;  in tnode_free_append()
664 	struct key_vector *n, *tp;  in collapse()  local
668 	for (n = NULL, i = child_length(oldtnode); !n && i;)  in collapse()
669 		n = get_child(oldtnode, --i);  in collapse()
673 	put_child_root(tp, oldtnode->key, n);  in collapse()
674 	node_set_parent(n, tp);  in collapse()
693 		struct key_vector *n = get_child(tn, i);  in update_suffix()  local
695 		if (!n || (n->slen <= slen))  in update_suffix()
699 		stride <<= (n->slen - slen);  in update_suffix()
700 		slen = n->slen;  in update_suffix()
921 	struct key_vector *pn, *n = t->kv;  in fib_find_node()  local
925 		pn = n;  in fib_find_node()
926 		n = get_child_rcu(n, index);  in fib_find_node()
928 		if (!n)  in fib_find_node()
931 		index = get_cindex(key, n);  in fib_find_node()
947 		if (index >= (1ul << n->bits)) {  in fib_find_node()
948 			n = NULL;  in fib_find_node()
953 	} while (IS_TNODE(n));  in fib_find_node()
957 	return n;  in fib_find_node()
998 	struct key_vector *n, *l;  in fib_insert_node()  local
1005 	n = get_child(tp, get_index(key, tp));  in fib_insert_node()
1013 	if (n) {  in fib_insert_node()
1016 		tn = tnode_new(key, __fls(key ^ n->key), 1);  in fib_insert_node()
1022 		put_child(tn, get_index(key, tn) ^ 1, n);  in fib_insert_node()
1026 		node_set_parent(n, tn);  in fib_insert_node()
1261 static inline t_key prefix_mismatch(t_key key, struct key_vector *n)  in prefix_mismatch()  argument
1263 	t_key prefix = n->key;  in prefix_mismatch()
1277 	struct key_vector *n, *pn;  in fib_table_lookup()  local
1287 	n = get_child_rcu(pn, cindex);  in fib_table_lookup()
1288 	if (!n)  in fib_table_lookup()
1297 		index = get_cindex(key, n);  in fib_table_lookup()
1313 		if (index >= (1ul << n->bits))  in fib_table_lookup()
1317 		if (IS_LEAF(n))  in fib_table_lookup()
1323 		if (n->slen > n->pos) {  in fib_table_lookup()
1324 			pn = n;  in fib_table_lookup()
1328 		n = get_child_rcu(n, index);  in fib_table_lookup()
1329 		if (unlikely(!n))  in fib_table_lookup()
1336 		struct key_vector __rcu **cptr = n->tnode;  in fib_table_lookup()
1342 		if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))  in fib_table_lookup()
1346 		if (unlikely(IS_LEAF(n)))  in fib_table_lookup()
1354 		while ((n = rcu_dereference(*cptr)) == NULL) {  in fib_table_lookup()
1357 			if (!n)  in fib_table_lookup()
1392 	index = key ^ n->key;  in fib_table_lookup()
1395 	hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {  in fib_table_lookup()
1444 			res->fa_head = &n->leaf;  in fib_table_lookup()
1565 	struct key_vector *pn, *n = *tn;  in leaf_walk_rcu()  local
1571 		pn = n;  in leaf_walk_rcu()
1578 		n = get_child_rcu(pn, cindex++);  in leaf_walk_rcu()
1579 		if (!n)  in leaf_walk_rcu()
1583 		if (IS_LEAF(n) && (n->key >= key))  in leaf_walk_rcu()
1585 	} while (IS_TNODE(n));  in leaf_walk_rcu()
1599 		n = get_child_rcu(pn, cindex++);  in leaf_walk_rcu()
1600 		if (!n)  in leaf_walk_rcu()
1604 		if (IS_LEAF(n))  in leaf_walk_rcu()
1608 		pn = n;  in leaf_walk_rcu()
1617 	return n;  in leaf_walk_rcu()
1630 		struct key_vector *n;  in fib_trie_free()  local
1638 			n = pn;  in fib_trie_free()
1642 			put_child_root(pn, n->key, NULL);  in fib_trie_free()
1643 			node_free(n);  in fib_trie_free()
1651 		n = get_child(pn, cindex);  in fib_trie_free()
1652 		if (!n)  in fib_trie_free()
1655 		if (IS_TNODE(n)) {  in fib_trie_free()
1657 			pn = n;  in fib_trie_free()
1658 			cindex = 1ul << n->bits;  in fib_trie_free()
1663 		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {  in fib_trie_free()
1668 		put_child_root(pn, n->key, NULL);  in fib_trie_free()
1669 		node_free(n);  in fib_trie_free()
1746 		struct key_vector *n;  in fib_table_flush_external()  local
1763 		n = get_child(pn, cindex);  in fib_table_flush_external()
1764 		if (!n)  in fib_table_flush_external()
1767 		if (IS_TNODE(n)) {  in fib_table_flush_external()
1769 			pn = n;  in fib_table_flush_external()
1770 			cindex = 1ul << n->bits;  in fib_table_flush_external()
1775 		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {  in fib_table_flush_external()
1793 			switchdev_fib_ipv4_del(n->key, KEYLENGTH - fa->fa_slen,  in fib_table_flush_external()
1799 		n->slen = slen;  in fib_table_flush_external()
1801 		if (hlist_empty(&n->leaf)) {  in fib_table_flush_external()
1802 			put_child_root(pn, n->key, NULL);  in fib_table_flush_external()
1803 			node_free(n);  in fib_table_flush_external()
1821 		struct key_vector *n;  in fib_table_flush()  local
1838 		n = get_child(pn, cindex);  in fib_table_flush()
1839 		if (!n)  in fib_table_flush()
1842 		if (IS_TNODE(n)) {  in fib_table_flush()
1844 			pn = n;  in fib_table_flush()
1845 			cindex = 1ul << n->bits;  in fib_table_flush()
1850 		hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) {  in fib_table_flush()
1858 			switchdev_fib_ipv4_del(n->key, KEYLENGTH - fa->fa_slen,  in fib_table_flush()
1868 		n->slen = slen;  in fib_table_flush()
1870 		if (hlist_empty(&n->leaf)) {  in fib_table_flush()
1871 			put_child_root(pn, n->key, NULL);  in fib_table_flush()
1872 			node_free(n);  in fib_table_flush()
2040 			struct key_vector *n = get_child_rcu(pn, cindex++);  in fib_trie_get_next()  local
2042 			if (!n)  in fib_trie_get_next()
2045 			if (IS_LEAF(n)) {  in fib_trie_get_next()
2050 				iter->tnode = n;  in fib_trie_get_next()
2055 			return n;  in fib_trie_get_next()
2075 	struct key_vector *n, *pn;  in fib_trie_get_first()  local
2081 	n = rcu_dereference(pn->tnode[0]);  in fib_trie_get_first()
2082 	if (!n)  in fib_trie_get_first()
2085 	if (IS_TNODE(n)) {  in fib_trie_get_first()
2086 		iter->tnode = n;  in fib_trie_get_first()
2095 	return n;  in fib_trie_get_first()
2100 	struct key_vector *n;  in trie_collect_stats()  local
2106 	for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {  in trie_collect_stats()
2107 		if (IS_LEAF(n)) {  in trie_collect_stats()
2115 			hlist_for_each_entry_rcu(fa, &n->leaf, fa_list)  in trie_collect_stats()
2119 			if (n->bits < MAX_STAT_DEPTH)  in trie_collect_stats()
2120 				s->nodesizes[n->bits]++;  in trie_collect_stats()
2121 			s->nullpointers += tn_info(n)->empty_children;  in trie_collect_stats()
2270 			struct key_vector *n;  in fib_trie_get_idx()  local
2272 			for (n = fib_trie_get_first(iter,  in fib_trie_get_idx()
2274 			     n; n = fib_trie_get_next(iter))  in fib_trie_get_idx()
2277 					return n;  in fib_trie_get_idx()
2299 	struct key_vector *n;  in fib_trie_seq_next()  local
2303 	n = fib_trie_get_next(iter);  in fib_trie_seq_next()
2304 	if (n)  in fib_trie_seq_next()
2305 		return n;  in fib_trie_seq_next()
2311 		n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);  in fib_trie_seq_next()
2312 		if (n)  in fib_trie_seq_next()
2320 			n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);  in fib_trie_seq_next()
2321 			if (n)  in fib_trie_seq_next()
2329 	return n;  in fib_trie_seq_next()
2338 static void seq_indent(struct seq_file *seq, int n)  in seq_indent()  argument
2340 	while (n-- > 0)  in seq_indent()
2385 	struct key_vector *n = v;  in fib_trie_seq_show()  local
2387 	if (IS_TRIE(node_parent_rcu(n)))  in fib_trie_seq_show()
2390 	if (IS_TNODE(n)) {  in fib_trie_seq_show()
2391 		__be32 prf = htonl(n->key);  in fib_trie_seq_show()
2395 			   &prf, KEYLENGTH - n->pos - n->bits, n->bits,  in fib_trie_seq_show()
2396 			   tn_info(n)->full_children,  in fib_trie_seq_show()
2397 			   tn_info(n)->empty_children);  in fib_trie_seq_show()
2399 		__be32 val = htonl(n->key);  in fib_trie_seq_show()
2405 		hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) {  in fib_trie_seq_show()