Lines Matching refs:n
92 #define IS_TRIE(n) ((n)->pos >= KEYLENGTH) argument
93 #define IS_TNODE(n) ((n)->bits) argument
94 #define IS_LEAF(n) (!(n)->bits) argument
118 #define TNODE_SIZE(n) offsetof(struct tnode, kv[0].tnode[n]) argument
176 static inline void node_set_parent(struct key_vector *n, struct key_vector *tp) in node_set_parent() argument
178 if (n) in node_set_parent()
179 rcu_assign_pointer(tn_info(n)->parent, tp); in node_set_parent()
182 #define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER(tn_info(n)->parent, p) argument
286 struct tnode *n = container_of(head, struct tnode, rcu); in __node_free_rcu() local
288 if (!n->tn_bits) in __node_free_rcu()
289 kmem_cache_free(trie_leaf_kmem, n); in __node_free_rcu()
290 else if (n->tn_bits <= TNODE_KMALLOC_MAX) in __node_free_rcu()
291 kfree(n); in __node_free_rcu()
293 vfree(n); in __node_free_rcu()
296 #define node_free(n) call_rcu(&tn_info(n)->rcu, __node_free_rcu) argument
315 static inline void empty_child_inc(struct key_vector *n) in empty_child_inc() argument
317 ++tn_info(n)->empty_children ? : ++tn_info(n)->full_children; in empty_child_inc()
320 static inline void empty_child_dec(struct key_vector *n) in empty_child_dec() argument
322 tn_info(n)->empty_children-- ? : tn_info(n)->full_children--; in empty_child_dec()
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()
386 struct key_vector *n) in put_child() argument
394 if (!n && chi) in put_child()
396 if (n && !chi) in put_child()
401 isfull = tnode_full(tn, n); 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()
437 struct key_vector *n) in put_child_root() argument
440 rcu_assign_pointer(tp->tnode[0], n); in put_child_root()
442 put_child(tp, get_index(key, tp), n); in put_child_root()
451 struct key_vector *n) 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()
658 struct key_vector *n, *tp; in collapse() local
662 for (n = NULL, i = child_length(oldtnode); !n && i;) in collapse()
663 n = get_child(oldtnode, --i); in collapse()
667 put_child_root(tp, oldtnode->key, n); in collapse()
668 node_set_parent(n, tp); in collapse()
687 struct key_vector *n = get_child(tn, i); in update_suffix() local
689 if (!n || (n->slen <= slen)) in update_suffix()
693 stride <<= (n->slen - slen); in update_suffix()
694 slen = n->slen; in update_suffix()
915 struct key_vector *pn, *n = t->kv; in fib_find_node() local
919 pn = n; in fib_find_node()
920 n = get_child_rcu(n, index); in fib_find_node()
922 if (!n) in fib_find_node()
925 index = get_cindex(key, n); in fib_find_node()
941 if (index >= (1ul << n->bits)) { in fib_find_node()
942 n = NULL; in fib_find_node()
947 } while (IS_TNODE(n)); in fib_find_node()
951 return n; in fib_find_node()
992 struct key_vector *n, *l; in fib_insert_node() local
999 n = get_child(tp, get_index(key, tp)); in fib_insert_node()
1007 if (n) { in fib_insert_node()
1010 tn = tnode_new(key, __fls(key ^ n->key), 1); in fib_insert_node()
1016 put_child(tn, get_index(key, tn) ^ 1, n); in fib_insert_node()
1020 node_set_parent(n, tn); in fib_insert_node()
1252 static inline t_key prefix_mismatch(t_key key, struct key_vector *n) in prefix_mismatch() argument
1254 t_key prefix = n->key; in prefix_mismatch()
1268 struct key_vector *n, *pn; in fib_table_lookup() local
1276 n = get_child_rcu(pn, cindex); in fib_table_lookup()
1277 if (!n) in fib_table_lookup()
1286 index = get_cindex(key, n); in fib_table_lookup()
1302 if (index >= (1ul << n->bits)) in fib_table_lookup()
1306 if (IS_LEAF(n)) in fib_table_lookup()
1312 if (n->slen > n->pos) { in fib_table_lookup()
1313 pn = n; in fib_table_lookup()
1317 n = get_child_rcu(n, index); in fib_table_lookup()
1318 if (unlikely(!n)) in fib_table_lookup()
1325 struct key_vector __rcu **cptr = n->tnode; in fib_table_lookup()
1331 if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos)) in fib_table_lookup()
1335 if (unlikely(IS_LEAF(n))) in fib_table_lookup()
1343 while ((n = rcu_dereference(*cptr)) == NULL) { in fib_table_lookup()
1346 if (!n) in fib_table_lookup()
1381 index = key ^ n->key; in fib_table_lookup()
1384 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) { in fib_table_lookup()
1424 res->fa_head = &n->leaf; in fib_table_lookup()
1543 struct key_vector *pn, *n = *tn; in leaf_walk_rcu() local
1549 pn = n; in leaf_walk_rcu()
1556 n = get_child_rcu(pn, cindex++); in leaf_walk_rcu()
1557 if (!n) in leaf_walk_rcu()
1561 if (IS_LEAF(n) && (n->key >= key)) in leaf_walk_rcu()
1563 } while (IS_TNODE(n)); in leaf_walk_rcu()
1577 n = get_child_rcu(pn, cindex++); in leaf_walk_rcu()
1578 if (!n) in leaf_walk_rcu()
1582 if (IS_LEAF(n)) in leaf_walk_rcu()
1586 pn = n; in leaf_walk_rcu()
1595 return n; in leaf_walk_rcu()
1608 struct key_vector *n; in fib_trie_free() local
1616 n = pn; in fib_trie_free()
1620 put_child_root(pn, n->key, NULL); in fib_trie_free()
1621 node_free(n); in fib_trie_free()
1629 n = get_child(pn, cindex); in fib_trie_free()
1630 if (!n) in fib_trie_free()
1633 if (IS_TNODE(n)) { in fib_trie_free()
1635 pn = n; in fib_trie_free()
1636 cindex = 1ul << n->bits; in fib_trie_free()
1641 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) { in fib_trie_free()
1646 put_child_root(pn, n->key, NULL); in fib_trie_free()
1647 node_free(n); in fib_trie_free()
1724 struct key_vector *n; in fib_table_flush_external() local
1741 n = get_child(pn, cindex); in fib_table_flush_external()
1742 if (!n) in fib_table_flush_external()
1745 if (IS_TNODE(n)) { in fib_table_flush_external()
1747 pn = n; in fib_table_flush_external()
1748 cindex = 1ul << n->bits; in fib_table_flush_external()
1753 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) { in fib_table_flush_external()
1771 netdev_switch_fib_ipv4_del(n->key, in fib_table_flush_external()
1778 n->slen = slen; in fib_table_flush_external()
1780 if (hlist_empty(&n->leaf)) { in fib_table_flush_external()
1781 put_child_root(pn, n->key, NULL); in fib_table_flush_external()
1782 node_free(n); in fib_table_flush_external()
1800 struct key_vector *n; in fib_table_flush() local
1817 n = get_child(pn, cindex); in fib_table_flush()
1818 if (!n) in fib_table_flush()
1821 if (IS_TNODE(n)) { in fib_table_flush()
1823 pn = n; in fib_table_flush()
1824 cindex = 1ul << n->bits; in fib_table_flush()
1829 hlist_for_each_entry_safe(fa, tmp, &n->leaf, fa_list) { in fib_table_flush()
1837 netdev_switch_fib_ipv4_del(n->key, in fib_table_flush()
1848 n->slen = slen; in fib_table_flush()
1850 if (hlist_empty(&n->leaf)) { in fib_table_flush()
1851 put_child_root(pn, n->key, NULL); in fib_table_flush()
1852 node_free(n); in fib_table_flush()
2021 struct key_vector *n = get_child_rcu(pn, cindex++); in fib_trie_get_next() local
2023 if (!n) in fib_trie_get_next()
2026 if (IS_LEAF(n)) { in fib_trie_get_next()
2031 iter->tnode = n; in fib_trie_get_next()
2036 return n; in fib_trie_get_next()
2056 struct key_vector *n, *pn = t->kv; in fib_trie_get_first() local
2061 n = rcu_dereference(pn->tnode[0]); in fib_trie_get_first()
2062 if (!n) in fib_trie_get_first()
2065 if (IS_TNODE(n)) { in fib_trie_get_first()
2066 iter->tnode = n; in fib_trie_get_first()
2075 return n; in fib_trie_get_first()
2080 struct key_vector *n; in trie_collect_stats() local
2086 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) { in trie_collect_stats()
2087 if (IS_LEAF(n)) { in trie_collect_stats()
2095 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) in trie_collect_stats()
2099 if (n->bits < MAX_STAT_DEPTH) in trie_collect_stats()
2100 s->nodesizes[n->bits]++; in trie_collect_stats()
2101 s->nullpointers += tn_info(n)->empty_children; in trie_collect_stats()
2250 struct key_vector *n; in fib_trie_get_idx() local
2252 for (n = fib_trie_get_first(iter, in fib_trie_get_idx()
2254 n; n = fib_trie_get_next(iter)) in fib_trie_get_idx()
2257 return n; in fib_trie_get_idx()
2279 struct key_vector *n; in fib_trie_seq_next() local
2283 n = fib_trie_get_next(iter); in fib_trie_seq_next()
2284 if (n) in fib_trie_seq_next()
2285 return n; in fib_trie_seq_next()
2291 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data); in fib_trie_seq_next()
2292 if (n) in fib_trie_seq_next()
2300 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data); in fib_trie_seq_next()
2301 if (n) in fib_trie_seq_next()
2309 return n; in fib_trie_seq_next()
2318 static void seq_indent(struct seq_file *seq, int n) in seq_indent() argument
2320 while (n-- > 0) in seq_indent()
2365 struct key_vector *n = v; in fib_trie_seq_show() local
2367 if (IS_TRIE(node_parent_rcu(n))) in fib_trie_seq_show()
2370 if (IS_TNODE(n)) { in fib_trie_seq_show()
2371 __be32 prf = htonl(n->key); in fib_trie_seq_show()
2375 &prf, KEYLENGTH - n->pos - n->bits, n->bits, in fib_trie_seq_show()
2376 tn_info(n)->full_children, in fib_trie_seq_show()
2377 tn_info(n)->empty_children); in fib_trie_seq_show()
2379 __be32 val = htonl(n->key); in fib_trie_seq_show()
2385 hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) { in fib_trie_seq_show()