149 static struct key_vector *resize(struct trie *t, struct key_vector *tn);
168 #define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)  argument
169 #define get_child(tn, i) rtnl_dereference((tn)->tnode[i])  argument
172 #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)  argument
173 #define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])  argument
187 static inline unsigned long child_length(const struct key_vector *tn)  in child_length()  argument
189 	return (1ul << tn->bits) & ~(1ul);  in child_length()
350 	struct key_vector *tn = tnode->kv;  in tnode_new()  local
366 	tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;  in tnode_new()
367 	tn->pos = pos;  in tnode_new()
368 	tn->bits = bits;  in tnode_new()
369 	tn->slen = pos;  in tnode_new()
371 	return tn;  in tnode_new()
377 static inline int tnode_full(struct key_vector *tn, struct key_vector *n)  in tnode_full()  argument
379 	return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);  in tnode_full()
385 static void put_child(struct key_vector *tn, unsigned long i,  in put_child()  argument
388 	struct key_vector *chi = get_child(tn, i);  in put_child()
391 	BUG_ON(i >= child_length(tn));  in put_child()
395 		empty_child_inc(tn);  in put_child()
397 		empty_child_dec(tn);  in put_child()
400 	wasfull = tnode_full(tn, chi);  in put_child()
401 	isfull = tnode_full(tn, n);  in put_child()
404 		tn_info(tn)->full_children--;  in put_child()
406 		tn_info(tn)->full_children++;  in put_child()
408 	if (n && (tn->slen < n->slen))  in put_child()
409 		tn->slen = n->slen;  in put_child()
411 	rcu_assign_pointer(tn->tnode[i], n);  in put_child()
414 static void update_children(struct key_vector *tn)  in update_children()  argument
419 	for (i = child_length(tn); i;) {  in update_children()
420 		struct key_vector *inode = get_child(tn, --i);  in update_children()
429 		if (node_parent(inode) == tn)  in update_children()
432 			node_set_parent(inode, tn);  in update_children()
445 static inline void tnode_free_init(struct key_vector *tn)  in tnode_free_init()  argument
447 	tn_info(tn)->rcu.next = NULL;  in tnode_free_init()
450 static inline void tnode_free_append(struct key_vector *tn,  in tnode_free_append()  argument
453 	tn_info(n)->rcu.next = tn_info(tn)->rcu.next;  in tnode_free_append()
454 	tn_info(tn)->rcu.next = &tn_info(n)->rcu;  in tnode_free_append()
457 static void tnode_free(struct key_vector *tn)  in tnode_free()  argument
459 	struct callback_head *head = &tn_info(tn)->rcu;  in tnode_free()
463 		tnode_free_size += TNODE_SIZE(1ul << tn->bits);  in tnode_free()
464 		node_free(tn);  in tnode_free()
466 		tn = container_of(head, struct tnode, rcu)->kv;  in tnode_free()
477 				  struct key_vector *tn)  in replace()  argument
483 	NODE_INIT_PARENT(tn, tp);  in replace()
484 	put_child_root(tp, tn->key, tn);  in replace()
487 	update_children(tn);  in replace()
493 	for (i = child_length(tn); i;) {  in replace()
494 		struct key_vector *inode = get_child(tn, --i);  in replace()
497 		if (tnode_full(tn, inode))  in replace()
498 			tn = resize(t, inode);  in replace()
507 	struct key_vector *tn;  in inflate()  local
513 	tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);  in inflate()
514 	if (!tn)  in inflate()
525 	for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {  in inflate()
536 			put_child(tn, get_index(inode->key, tn), inode);  in inflate()
545 			put_child(tn, 2 * i + 1, get_child(inode, 1));  in inflate()
546 			put_child(tn, 2 * i, get_child(inode, 0));  in inflate()
569 		tnode_free_append(tn, node1);  in inflate()
572 		tnode_free_append(tn, node0);  in inflate()
583 		NODE_INIT_PARENT(node1, tn);  in inflate()
584 		NODE_INIT_PARENT(node0, tn);  in inflate()
587 		put_child(tn, 2 * i + 1, node1);  in inflate()
588 		put_child(tn, 2 * i, node0);  in inflate()
592 	return replace(t, oldtnode, tn);  in inflate()
595 	tnode_free(tn);  in inflate()
603 	struct key_vector *tn;  in halve()  local
608 	tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);  in halve()
609 	if (!tn)  in halve()
627 			put_child(tn, i / 2, node1 ? : node0);  in halve()
635 		tnode_free_append(tn, inode);  in halve()
640 		NODE_INIT_PARENT(inode, tn);  in halve()
643 		put_child(tn, i / 2, inode);  in halve()
647 	return replace(t, oldtnode, tn);  in halve()
650 	tnode_free(tn);  in halve()
676 static unsigned char update_suffix(struct key_vector *tn)  in update_suffix()  argument
678 	unsigned char slen = tn->pos;  in update_suffix()
686 	for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {  in update_suffix()
687 		struct key_vector *n = get_child(tn, i);  in update_suffix()
702 		if ((slen + 1) >= (tn->pos + tn->bits))  in update_suffix()
706 	tn->slen = slen;  in update_suffix()
768 static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)  in should_inflate()  argument
770 	unsigned long used = child_length(tn);  in should_inflate()
775 	used -= tn_info(tn)->empty_children;  in should_inflate()
776 	used += tn_info(tn)->full_children;  in should_inflate()
780 	return (used > 1) && tn->pos && ((50 * used) >= threshold);  in should_inflate()
783 static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)  in should_halve()  argument
785 	unsigned long used = child_length(tn);  in should_halve()
790 	used -= tn_info(tn)->empty_children;  in should_halve()
794 	return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);  in should_halve()
797 static inline bool should_collapse(struct key_vector *tn)  in should_collapse()  argument
799 	unsigned long used = child_length(tn);  in should_collapse()
801 	used -= tn_info(tn)->empty_children;  in should_collapse()
804 	if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children)  in should_collapse()
812 static struct key_vector *resize(struct trie *t, struct key_vector *tn)  in resize()  argument
817 	struct key_vector *tp = node_parent(tn);  in resize()
818 	unsigned long cindex = get_index(tn->key, tp);  in resize()
822 		 tn, inflate_threshold, halve_threshold);  in resize()
828 	BUG_ON(tn != get_child(tp, cindex));  in resize()
833 	while (should_inflate(tp, tn) && max_work) {  in resize()
834 		tp = inflate(t, tn);  in resize()
843 		tn = get_child(tp, cindex);  in resize()
847 	tp = node_parent(tn);  in resize()
856 	while (should_halve(tp, tn) && max_work) {  in resize()
857 		tp = halve(t, tn);  in resize()
866 		tn = get_child(tp, cindex);  in resize()
870 	if (should_collapse(tn))  in resize()
871 		return collapse(t, tn);  in resize()
874 	tp = node_parent(tn);  in resize()
881 	if (tn->slen > tn->pos) {  in resize()
882 		unsigned char slen = update_suffix(tn);  in resize()
900 static void leaf_push_suffix(struct key_vector *tn, struct key_vector *l)  in leaf_push_suffix()  argument
905 	while (tn->slen < l->slen) {  in leaf_push_suffix()
906 		tn->slen = l->slen;  in leaf_push_suffix()
907 		tn = node_parent(tn);  in leaf_push_suffix()
983 static void trie_rebalance(struct trie *t, struct key_vector *tn)  in trie_rebalance()  argument
985 	while (!IS_TRIE(tn))  in trie_rebalance()
986 		tn = resize(t, tn);  in trie_rebalance()
1008 		struct key_vector *tn;  in fib_insert_node()  local
1010 		tn = tnode_new(key, __fls(key ^ n->key), 1);  in fib_insert_node()
1011 		if (!tn)  in fib_insert_node()
1015 		NODE_INIT_PARENT(tn, tp);  in fib_insert_node()
1016 		put_child(tn, get_index(key, tn) ^ 1, n);  in fib_insert_node()
1019 		put_child_root(tp, key, tn);  in fib_insert_node()
1020 		node_set_parent(n, tn);  in fib_insert_node()
1023 		tp = tn;  in fib_insert_node()
1541 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)  in leaf_walk_rcu()  argument
1543 	struct key_vector *pn, *n = *tn;  in leaf_walk_rcu()
1590 	*tn = pn;  in leaf_walk_rcu()
1594 	*tn = pn;  in leaf_walk_rcu()