151 static struct key_vector *resize(struct trie *t, struct key_vector *tn);
170 #define node_parent(tn) rtnl_dereference(tn_info(tn)->parent)  argument
171 #define get_child(tn, i) rtnl_dereference((tn)->tnode[i])  argument
174 #define node_parent_rcu(tn) rcu_dereference_rtnl(tn_info(tn)->parent)  argument
175 #define get_child_rcu(tn, i) rcu_dereference_rtnl((tn)->tnode[i])  argument
189 static inline unsigned long child_length(const struct key_vector *tn)  in child_length()  argument
191 	return (1ul << tn->bits) & ~(1ul);  in child_length()
353 	struct key_vector *tn;  in tnode_new()  local
371 	tn = tnode->kv;  in tnode_new()
372 	tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;  in tnode_new()
373 	tn->pos = pos;  in tnode_new()
374 	tn->bits = bits;  in tnode_new()
375 	tn->slen = pos;  in tnode_new()
377 	return tn;  in tnode_new()
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()
391 static void put_child(struct key_vector *tn, unsigned long i,  in put_child()  argument
394 	struct key_vector *chi = get_child(tn, i);  in put_child()
397 	BUG_ON(i >= child_length(tn));  in put_child()
401 		empty_child_inc(tn);  in put_child()
403 		empty_child_dec(tn);  in put_child()
406 	wasfull = tnode_full(tn, chi);  in put_child()
407 	isfull = tnode_full(tn, n);  in put_child()
410 		tn_info(tn)->full_children--;  in put_child()
412 		tn_info(tn)->full_children++;  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()
420 static void update_children(struct key_vector *tn)  in update_children()  argument
425 	for (i = child_length(tn); i;) {  in update_children()
426 		struct key_vector *inode = get_child(tn, --i);  in update_children()
435 		if (node_parent(inode) == tn)  in update_children()
438 			node_set_parent(inode, tn);  in update_children()
451 static inline void tnode_free_init(struct key_vector *tn)  in tnode_free_init()  argument
453 	tn_info(tn)->rcu.next = NULL;  in tnode_free_init()
456 static inline void tnode_free_append(struct key_vector *tn,  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()
463 static void tnode_free(struct key_vector *tn)  in tnode_free()  argument
465 	struct callback_head *head = &tn_info(tn)->rcu;  in tnode_free()
469 		tnode_free_size += TNODE_SIZE(1ul << tn->bits);  in tnode_free()
470 		node_free(tn);  in tnode_free()
472 		tn = container_of(head, struct tnode, rcu)->kv;  in tnode_free()
483 				  struct key_vector *tn)  in replace()  argument
489 	NODE_INIT_PARENT(tn, tp);  in replace()
490 	put_child_root(tp, tn->key, tn);  in replace()
493 	update_children(tn);  in replace()
499 	for (i = child_length(tn); i;) {  in replace()
500 		struct key_vector *inode = get_child(tn, --i);  in replace()
503 		if (tnode_full(tn, inode))  in replace()
504 			tn = resize(t, inode);  in replace()
513 	struct key_vector *tn;  in inflate()  local
519 	tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);  in inflate()
520 	if (!tn)  in inflate()
531 	for (i = child_length(oldtnode), m = 1u << tn->pos; i;) {  in inflate()
542 			put_child(tn, get_index(inode->key, tn), inode);  in inflate()
551 			put_child(tn, 2 * i + 1, get_child(inode, 1));  in inflate()
552 			put_child(tn, 2 * i, get_child(inode, 0));  in inflate()
575 		tnode_free_append(tn, node1);  in inflate()
578 		tnode_free_append(tn, node0);  in inflate()
589 		NODE_INIT_PARENT(node1, tn);  in inflate()
590 		NODE_INIT_PARENT(node0, tn);  in inflate()
593 		put_child(tn, 2 * i + 1, node1);  in inflate()
594 		put_child(tn, 2 * i, node0);  in inflate()
598 	return replace(t, oldtnode, tn);  in inflate()
601 	tnode_free(tn);  in inflate()
609 	struct key_vector *tn;  in halve()  local
614 	tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);  in halve()
615 	if (!tn)  in halve()
633 			put_child(tn, i / 2, node1 ? : node0);  in halve()
641 		tnode_free_append(tn, inode);  in halve()
646 		NODE_INIT_PARENT(inode, tn);  in halve()
649 		put_child(tn, i / 2, inode);  in halve()
653 	return replace(t, oldtnode, tn);  in halve()
656 	tnode_free(tn);  in halve()
682 static unsigned char update_suffix(struct key_vector *tn)  in update_suffix()  argument
684 	unsigned char slen = tn->pos;  in update_suffix()
692 	for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) {  in update_suffix()
693 		struct key_vector *n = get_child(tn, i);  in update_suffix()
708 		if ((slen + 1) >= (tn->pos + tn->bits))  in update_suffix()
712 	tn->slen = slen;  in update_suffix()
774 static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)  in should_inflate()  argument
776 	unsigned long used = child_length(tn);  in should_inflate()
781 	used -= tn_info(tn)->empty_children;  in should_inflate()
782 	used += tn_info(tn)->full_children;  in should_inflate()
786 	return (used > 1) && tn->pos && ((50 * used) >= threshold);  in should_inflate()
789 static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)  in should_halve()  argument
791 	unsigned long used = child_length(tn);  in should_halve()
796 	used -= tn_info(tn)->empty_children;  in should_halve()
800 	return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);  in should_halve()
803 static inline bool should_collapse(struct key_vector *tn)  in should_collapse()  argument
805 	unsigned long used = child_length(tn);  in should_collapse()
807 	used -= tn_info(tn)->empty_children;  in should_collapse()
810 	if ((tn->bits == KEYLENGTH) && tn_info(tn)->full_children)  in should_collapse()
818 static struct key_vector *resize(struct trie *t, struct key_vector *tn)  in resize()  argument
823 	struct key_vector *tp = node_parent(tn);  in resize()
824 	unsigned long cindex = get_index(tn->key, tp);  in resize()
828 		 tn, inflate_threshold, halve_threshold);  in resize()
834 	BUG_ON(tn != get_child(tp, cindex));  in resize()
839 	while (should_inflate(tp, tn) && max_work) {  in resize()
840 		tp = inflate(t, tn);  in resize()
849 		tn = get_child(tp, cindex);  in resize()
853 	tp = node_parent(tn);  in resize()
862 	while (should_halve(tp, tn) && max_work) {  in resize()
863 		tp = halve(t, tn);  in resize()
872 		tn = get_child(tp, cindex);  in resize()
876 	if (should_collapse(tn))  in resize()
877 		return collapse(t, tn);  in resize()
880 	tp = node_parent(tn);  in resize()
887 	if (tn->slen > tn->pos) {  in resize()
888 		unsigned char slen = update_suffix(tn);  in resize()
906 static void leaf_push_suffix(struct key_vector *tn, struct key_vector *l)  in leaf_push_suffix()  argument
911 	while (tn->slen < l->slen) {  in leaf_push_suffix()
912 		tn->slen = l->slen;  in leaf_push_suffix()
913 		tn = node_parent(tn);  in leaf_push_suffix()
989 static void trie_rebalance(struct trie *t, struct key_vector *tn)  in trie_rebalance()  argument
991 	while (!IS_TRIE(tn))  in trie_rebalance()
992 		tn = resize(t, tn);  in trie_rebalance()
1014 		struct key_vector *tn;  in fib_insert_node()  local
1016 		tn = tnode_new(key, __fls(key ^ n->key), 1);  in fib_insert_node()
1017 		if (!tn)  in fib_insert_node()
1021 		NODE_INIT_PARENT(tn, tp);  in fib_insert_node()
1022 		put_child(tn, get_index(key, tn) ^ 1, n);  in fib_insert_node()
1025 		put_child_root(tp, key, tn);  in fib_insert_node()
1026 		node_set_parent(n, tn);  in fib_insert_node()
1029 		tp = tn;  in fib_insert_node()
1563 static struct key_vector *leaf_walk_rcu(struct key_vector **tn, t_key key)  in leaf_walk_rcu()  argument
1565 	struct key_vector *pn, *n = *tn;  in leaf_walk_rcu()
1612 	*tn = pn;  in leaf_walk_rcu()
1616 	*tn = pn;  in leaf_walk_rcu()