net/ipv4/fib_trie.c

203 static inline void node_set_parent(struct key_vector *n, struct key_vector *tp)
206 		rcu_assign_pointer(tn_info(n)->parent, tp);
235  * Consider a node 'n' and its parent 'tp'.
264  * tp->pos = 22
265  * tp->bits = 3
269  * First, let's just ignore the bits that come before the parent tp, that is
270  * the bits from (tp->pos + tp->bits) to 31. They are *known* but at this
273  * The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
275  * 'n' among tp's children.
277  * The bits from (n->pos + n->bits) to (tp->pos - 1) - "S" - are skipped bits
469 static inline void put_child_root(struct key_vector *tp, t_key key,
472 	if (IS_TRIE(tp))
473 		rcu_assign_pointer(tp->tnode[0], n);
475 		put_child(tp, get_index(key, tp), n);
512 	struct key_vector *tp = node_parent(oldtnode);
516 	NODE_INIT_PARENT(tn, tp);
517 	put_child_root(tp, tn->key, tn);
534 	return tp;
691 	struct key_vector *n, *tp;
699 	tp = node_parent(oldtnode);
700 	put_child_root(tp, oldtnode->key, n);
701 	node_set_parent(n, tp);
706 	return tp;
804 static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn)
810 	threshold *= IS_TRIE(tp) ? inflate_threshold_root : inflate_threshold;
819 static inline bool should_halve(struct key_vector *tp, struct key_vector *tn)
825 	threshold *= IS_TRIE(tp) ? halve_threshold_root : halve_threshold;
853 	struct key_vector *tp = node_parent(tn);
854 	unsigned long cindex = get_index(tn->key, tp);
864 	BUG_ON(tn != get_child(tp, cindex));
869 	while (should_inflate(tp, tn) && max_work) {
870 		tp = inflate(t, tn);
871 		if (!tp) {
879 		tn = get_child(tp, cindex);
883 	tp = node_parent(tn);
887 		return tp;
892 	while (should_halve(tp, tn) && max_work) {
893 		tp = halve(t, tn);
894 		if (!tp) {
902 		tn = get_child(tp, cindex);
937 					struct key_vector **tp, u32 key)
973 	*tp = pn;
1020 	struct key_vector *l, *tp;
1030 	l = fib_find_node(t, &tp, be32_to_cpu(fri->dst));
1110 static int fib_insert_node(struct trie *t, struct key_vector *tp,
1120 	n = get_child(tp, get_index(key, tp));
1136 		NODE_INIT_PARENT(tn, tp);
1140 		put_child_root(tp, key, tn);
1144 		tp = tn;
1148 	node_push_suffix(tp, new->fa_slen);
1149 	NODE_INIT_PARENT(l, tp);
1150 	put_child_root(tp, key, l);
1151 	trie_rebalance(t, tp);
1160 static int fib_insert_alias(struct trie *t, struct key_vector *tp,
1165 		return fib_insert_node(t, tp, new, key);
1190 		node_push_suffix(tp, new->fa_slen);
1212 static void fib_remove_alias(struct trie *t, struct key_vector *tp,
1221 	struct key_vector *l, *tp;
1244 	l = fib_find_node(t, &tp, key);
1379 	err = fib_insert_alias(t, tp, l, new_fa, fa, key);
1384 	l = l ? l : fib_find_node(t, &tp, key);
1411 	fib_remove_alias(t, tp, l, new_fa);
1651 static void fib_remove_alias(struct trie *t, struct key_vector *tp,
1665 		if (tp->slen == l->slen)
1666 			node_pull_suffix(tp, tp->pos);
1667 		put_child_root(tp, l->key, NULL);
1669 		trie_rebalance(t, tp);
1679 	node_pull_suffix(tp, fa->fa_slen);
1718 	struct key_vector *l, *tp;
1729 	l = fib_find_node(t, &tp, key);
1774 	fib_remove_alias(t, tp, l, fa_to_delete);
1903 	struct key_vector *l, *tp = ot->kv;
1918 	while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
2216 	struct key_vector *l, *tp = t->kv;
2220 	while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
2360 	struct key_vector *l, *tp = t->kv;
2373 	while ((l = leaf_walk_rcu(&tp, key)) != NULL) {
2859 	struct key_vector *l, **tp = &iter->tnode;
2872 	while ((l = leaf_walk_rcu(tp, key)) && (pos-- > 0)) {