* [RFC PATCH 08/17] fib_trie: Update meaning of pos to represent unchecked bits
From: Alexander Duyck @ 2014-12-22 17:41 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change moves the pos value to the other side of the "bits" field. By
doing this it actually simplifies a significant amount of code in the trie.
For example when halving a tree we know that the bit lost exists at
oldnode->pos, and if we inflate the tree the new bit being add is at
tn->pos. Previously to find those bits you would have to subtract pos and
bits from the keylength or start with a value of (1 << 31) and then shift
that.
There are a number of spots throughout the code that benefit from this. In
the case of the hot-path searches the main advantage is that we can drop 2
or more operations from the search path as we no longer need to compute the
value for the index to be shifted by and can instead just use the raw pos
value.
In addition the tkey_extract_bits is now defunct and can be replaced by
get_index since the two operations were doing the same thing, but now
get_index does it much more quickly as it is only an xor and shift versus a
pair of shifts and a subtraction.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 194 +++++++++++++++++++++------------------------------
1 file changed, 81 insertions(+), 113 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 969ecf3..d27aa27 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -90,8 +90,7 @@ typedef unsigned int t_key;
#define IS_TNODE(n) ((n)->bits)
#define IS_LEAF(n) (!(n)->bits)
-#define get_shift(_kv) (KEYLENGTH - (_kv)->pos - (_kv)->bits)
-#define get_index(_key, _kv) (((_key) ^ (_kv)->key) >> get_shift(_kv))
+#define get_index(_key, _kv) (((_key) ^ (_kv)->key) >> (_kv)->pos)
struct tnode {
t_key key;
@@ -209,81 +208,64 @@ static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn, unsigned
return rcu_dereference_rtnl(tn->child[i]);
}
-static inline t_key mask_pfx(t_key k, unsigned int l)
-{
- return (l == 0) ? 0 : k >> (KEYLENGTH-l) << (KEYLENGTH-l);
-}
-
-static inline t_key tkey_extract_bits(t_key a, unsigned int offset, unsigned int bits)
-{
- if (offset < KEYLENGTH)
- return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
- else
- return 0;
-}
-
-/*
- To understand this stuff, an understanding of keys and all their bits is
- necessary. Every node in the trie has a key associated with it, but not
- all of the bits in that key are significant.
-
- Consider a node 'n' and its parent 'tp'.
-
- If n is a leaf, every bit in its key is significant. Its presence is
- necessitated by path compression, since during a tree traversal (when
- searching for a leaf - unless we are doing an insertion) we will completely
- ignore all skipped bits we encounter. Thus we need to verify, at the end of
- a potentially successful search, that we have indeed been walking the
- correct key path.
-
- Note that we can never "miss" the correct key in the tree if present by
- following the wrong path. Path compression ensures that segments of the key
- that are the same for all keys with a given prefix are skipped, but the
- skipped part *is* identical for each node in the subtrie below the skipped
- bit! trie_insert() in this implementation takes care of that - note the
- call to tkey_sub_equals() in trie_insert().
-
- if n is an internal node - a 'tnode' here, the various parts of its key
- have many different meanings.
-
- Example:
- _________________________________________________________________
- | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
- -----------------------------------------------------------------
- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
-
- _________________________________________________________________
- | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
- -----------------------------------------------------------------
- 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
-
- tp->pos = 7
- tp->bits = 3
- n->pos = 15
- n->bits = 4
-
- First, let's just ignore the bits that come before the parent tp, that is
- the bits from 0 to (tp->pos-1). They are *known* but at this point we do
- not use them for anything.
-
- The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
- index into the parent's child array. That is, they will be used to find
- 'n' among tp's children.
-
- The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
- for the node n.
-
- All the bits we have seen so far are significant to the node n. The rest
- of the bits are really not needed or indeed known in n->key.
-
- The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
- n's child array, and will of course be different for each child.
-
-
- The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
- at this point.
-
-*/
+/* To understand this stuff, an understanding of keys and all their bits is
+ * necessary. Every node in the trie has a key associated with it, but not
+ * all of the bits in that key are significant.
+ *
+ * Consider a node 'n' and its parent 'tp'.
+ *
+ * If n is a leaf, every bit in its key is significant. Its presence is
+ * necessitated by path compression, since during a tree traversal (when
+ * searching for a leaf - unless we are doing an insertion) we will completely
+ * ignore all skipped bits we encounter. Thus we need to verify, at the end of
+ * a potentially successful search, that we have indeed been walking the
+ * correct key path.
+ *
+ * Note that we can never "miss" the correct key in the tree if present by
+ * following the wrong path. Path compression ensures that segments of the key
+ * that are the same for all keys with a given prefix are skipped, but the
+ * skipped part *is* identical for each node in the subtrie below the skipped
+ * bit! trie_insert() in this implementation takes care of that.
+ *
+ * if n is an internal node - a 'tnode' here, the various parts of its key
+ * have many different meanings.
+ *
+ * Example:
+ * _________________________________________________________________
+ * | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
+ * -----------------------------------------------------------------
+ * 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16
+ *
+ * _________________________________________________________________
+ * | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
+ * -----------------------------------------------------------------
+ * 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
+ *
+ * tp->pos = 22
+ * tp->bits = 3
+ * n->pos = 13
+ * n->bits = 4
+ *
+ * First, let's just ignore the bits that come before the parent tp, that is
+ * the bits from (tp->pos + tp->bits) to 31. They are *known* but at this
+ * point we do not use them for anything.
+ *
+ * The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
+ * index into the parent's child array. That is, they will be used to find
+ * 'n' among tp's children.
+ *
+ * The bits from (n->pos + n->bits) to (tn->pos - 1) - "S" - are skipped bits
+ * for the node n.
+ *
+ * All the bits we have seen so far are significant to the node n. The rest
+ * of the bits are really not needed or indeed known in n->key.
+ *
+ * The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
+ * n's child array, and will of course be different for each child.
+ *
+ * The rest of the bits, from 0 to (n->pos + n->bits), are completely unknown
+ * at this point.
+ */
static const int halve_threshold = 25;
static const int inflate_threshold = 50;
@@ -367,7 +349,7 @@ static struct tnode *leaf_new(t_key key)
* as the nodes are searched
*/
l->key = key;
- l->pos = KEYLENGTH;
+ l->pos = 0;
/* set bits to 0 indicating we are not a tnode */
l->bits = 0;
@@ -400,7 +382,7 @@ static struct tnode *tnode_new(t_key key, int pos, int bits)
tn->parent = NULL;
tn->pos = pos;
tn->bits = bits;
- tn->key = mask_pfx(key, pos);
+ tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
tn->full_children = 0;
tn->empty_children = 1<<bits;
}
@@ -410,14 +392,12 @@ static struct tnode *tnode_new(t_key key, int pos, int bits)
return tn;
}
-/*
- * Check whether a tnode 'n' is "full", i.e. it is an internal node
+/* Check whether a tnode 'n' is "full", i.e. it is an internal node
* and no bits are skipped. See discussion in dyntree paper p. 6
*/
-
static inline int tnode_full(const struct tnode *tn, const struct tnode *n)
{
- return n && IS_TNODE(n) && (n->pos == (tn->pos + tn->bits));
+ return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
}
static inline void put_child(struct tnode *tn, int i,
@@ -641,11 +621,12 @@ static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
{
int olen = tnode_child_length(oldtnode);
struct tnode *tn;
+ t_key m;
int i;
pr_debug("In inflate\n");
- tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
+ tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
if (!tn)
return ERR_PTR(-ENOMEM);
@@ -656,21 +637,18 @@ static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
* fails. In case of failure we return the oldnode and inflate
* of tnode is ignored.
*/
+ for (i = 0, m = 1u << tn->pos; i < olen; i++) {
+ struct tnode *inode = tnode_get_child(oldtnode, i);
- for (i = 0; i < olen; i++) {
- struct tnode *inode;
-
- inode = tnode_get_child(oldtnode, i);
- if (tnode_full(oldtnode, inode) && inode->bits > 1) {
+ if (tnode_full(oldtnode, inode) && (inode->bits > 1)) {
struct tnode *left, *right;
- t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
- left = tnode_new(inode->key&(~m), inode->pos + 1,
+ left = tnode_new(inode->key & ~m, inode->pos,
inode->bits - 1);
if (!left)
goto nomem;
- right = tnode_new(inode->key|m, inode->pos + 1,
+ right = tnode_new(inode->key | m, inode->pos,
inode->bits - 1);
if (!right) {
@@ -694,9 +672,7 @@ static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
/* A leaf or an internal node with skipped bits */
if (!tnode_full(oldtnode, inode)) {
- put_child(tn,
- tkey_extract_bits(inode->key, tn->pos, tn->bits),
- inode);
+ put_child(tn, get_index(inode->key, tn), inode);
continue;
}
@@ -767,7 +743,7 @@ static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
pr_debug("In halve\n");
- tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
+ tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
if (!tn)
return ERR_PTR(-ENOMEM);
@@ -787,7 +763,7 @@ static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
if (left && right) {
struct tnode *newn;
- newn = tnode_new(left->key, tn->pos + tn->bits, 1);
+ newn = tnode_new(left->key, oldtnode->pos, 1);
if (!newn)
goto nomem;
@@ -915,7 +891,7 @@ static void trie_rebalance(struct trie *t, struct tnode *tn)
key = tn->key;
while (tn != NULL && (tp = node_parent(tn)) != NULL) {
- cindex = tkey_extract_bits(key, tp->pos, tp->bits);
+ cindex = get_index(key, tp);
wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
tn = resize(t, tn);
@@ -1005,11 +981,8 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
*/
if (n) {
struct tnode *tn;
- int newpos;
-
- newpos = KEYLENGTH - __fls(n->key ^ key) - 1;
- tn = tnode_new(key, newpos, 1);
+ tn = tnode_new(key, __fls(key ^ n->key), 1);
if (!tn) {
free_leaf_info(li);
node_free(l);
@@ -1555,12 +1528,7 @@ static int trie_flush_leaf(struct tnode *l)
static struct tnode *leaf_walk_rcu(struct tnode *p, struct tnode *c)
{
do {
- t_key idx;
-
- if (c)
- idx = tkey_extract_bits(c->key, p->pos, p->bits) + 1;
- else
- idx = 0;
+ t_key idx = c ? idx = get_index(c->key, p) + 1 : 0;
while (idx < 1u << p->bits) {
c = tnode_get_child_rcu(p, idx++);
@@ -1847,7 +1815,7 @@ rescan:
/* Current node exhausted, pop back up */
p = node_parent_rcu(tn);
if (p) {
- cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
+ cindex = get_index(tn->key, p) + 1;
tn = p;
--iter->depth;
goto rescan;
@@ -2182,10 +2150,10 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
if (IS_TNODE(n)) {
__be32 prf = htonl(n->key);
- seq_indent(seq, iter->depth - 1);
- seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
- &prf, n->pos, n->bits, n->full_children,
- n->empty_children);
+ seq_indent(seq, iter->depth-1);
+ seq_printf(seq, " +-- %pI4/%zu %u %u %u\n",
+ &prf, KEYLENGTH - n->pos - n->bits, n->bits,
+ n->full_children, n->empty_children);
} else {
struct leaf_info *li;
__be32 val = htonl(n->key);
^ permalink raw reply related
* [RFC PATCH 09/17] fib_trie: Use unsigned long for anything dealing with a shift by bits
From: Alexander Duyck @ 2014-12-22 17:41 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change makes it so that anything that can be shifted by, or compared
to a value shifted by bits is updated to be an unsigned long. This is
mostly a precaution against an insanely huge address space that somehow
starts coming close to the 2^32 root node size which would require
something like 1.5 billion addresses.
I chose unsigned long instead of unsigned long long since I do not believe
it is possible to allocate a 32 bit tnode on a 32 bit system as the memory
consumed would be 16GB + 28B which exceeds the addressible space for any
one process.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 53 +++++++++++++++++++++++++--------------------------
1 file changed, 26 insertions(+), 27 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index d27aa27..74ad943 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -146,8 +146,8 @@ struct trie {
#endif
};
-static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
- int wasfull);
+static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
+ struct tnode *n, int wasfull);
static struct tnode *resize(struct trie *t, struct tnode *tn);
static struct tnode *inflate(struct trie *t, struct tnode *tn);
static struct tnode *halve(struct trie *t, struct tnode *tn);
@@ -183,25 +183,23 @@ static inline void node_set_parent(struct tnode *n, struct tnode *tp)
/* This provides us with the number of children in this node, in the case of a
* leaf this will return 0 meaning none of the children are accessible.
*/
-static inline int tnode_child_length(const struct tnode *tn)
+static inline unsigned long tnode_child_length(const struct tnode *tn)
{
return (1ul << tn->bits) & ~(1ul);
}
-/*
- * caller must hold RTNL
- */
-static inline struct tnode *tnode_get_child(const struct tnode *tn, unsigned int i)
+/* caller must hold RTNL */
+static inline struct tnode *tnode_get_child(const struct tnode *tn,
+ unsigned long i)
{
BUG_ON(i >= tnode_child_length(tn));
return rtnl_dereference(tn->child[i]);
}
-/*
- * caller must hold RCU read lock or RTNL
- */
-static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
+/* caller must hold RCU read lock or RTNL */
+static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn,
+ unsigned long i)
{
BUG_ON(i >= tnode_child_length(tn));
@@ -400,7 +398,7 @@ static inline int tnode_full(const struct tnode *tn, const struct tnode *n)
return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
}
-static inline void put_child(struct tnode *tn, int i,
+static inline void put_child(struct tnode *tn, unsigned long i,
struct tnode *n)
{
tnode_put_child_reorg(tn, i, n, -1);
@@ -411,13 +409,13 @@ static inline void put_child(struct tnode *tn, int i,
* Update the value of full_children and empty_children.
*/
-static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
- int wasfull)
+static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
+ struct tnode *n, int wasfull)
{
struct tnode *chi = rtnl_dereference(tn->child[i]);
int isfull;
- BUG_ON(i >= 1<<tn->bits);
+ BUG_ON(i >= tnode_child_length(tn));
/* update emptyChildren */
if (n == NULL && chi != NULL)
@@ -607,10 +605,10 @@ no_children:
static void tnode_clean_free(struct tnode *tn)
{
struct tnode *tofree;
- int i;
+ unsigned long i;
for (i = 0; i < tnode_child_length(tn); i++) {
- tofree = rtnl_dereference(tn->child[i]);
+ tofree = tnode_get_child(tn, i);
if (tofree)
node_free(tofree);
}
@@ -619,10 +617,10 @@ static void tnode_clean_free(struct tnode *tn)
static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
{
- int olen = tnode_child_length(oldtnode);
+ unsigned long olen = tnode_child_length(oldtnode);
struct tnode *tn;
+ unsigned long i;
t_key m;
- int i;
pr_debug("In inflate\n");
@@ -664,7 +662,7 @@ static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
for (i = 0; i < olen; i++) {
struct tnode *inode = tnode_get_child(oldtnode, i);
struct tnode *left, *right;
- int size, j;
+ unsigned long size, j;
/* An empty child */
if (inode == NULL)
@@ -737,7 +735,7 @@ nomem:
static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
{
- int olen = tnode_child_length(oldtnode);
+ unsigned long olen = tnode_child_length(oldtnode);
struct tnode *tn, *left, *right;
int i;
@@ -1528,9 +1526,9 @@ static int trie_flush_leaf(struct tnode *l)
static struct tnode *leaf_walk_rcu(struct tnode *p, struct tnode *c)
{
do {
- t_key idx = c ? idx = get_index(c->key, p) + 1 : 0;
+ unsigned long idx = c ? idx = get_index(c->key, p) + 1 : 0;
- while (idx < 1u << p->bits) {
+ while (idx < tnode_child_length(p)) {
c = tnode_get_child_rcu(p, idx++);
if (!c)
continue;
@@ -1782,8 +1780,8 @@ struct fib_trie_iter {
static struct tnode *fib_trie_get_next(struct fib_trie_iter *iter)
{
+ unsigned long cindex = iter->index;
struct tnode *tn = iter->tnode;
- unsigned int cindex = iter->index;
struct tnode *p;
/* A single entry routing table */
@@ -1793,7 +1791,7 @@ static struct tnode *fib_trie_get_next(struct fib_trie_iter *iter)
pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
iter->tnode, iter->index, iter->depth);
rescan:
- while (cindex < (1<<tn->bits)) {
+ while (cindex < tnode_child_length(tn)) {
struct tnode *n = tnode_get_child_rcu(tn, cindex);
if (n) {
@@ -1870,15 +1868,16 @@ static void trie_collect_stats(struct trie *t, struct trie_stat *s)
hlist_for_each_entry_rcu(li, &n->list, hlist)
++s->prefixes;
} else {
- int i;
+ unsigned long i;
s->tnodes++;
if (n->bits < MAX_STAT_DEPTH)
s->nodesizes[n->bits]++;
- for (i = 0; i < tnode_child_length(n); i++)
+ for (i = 0; i < tnode_child_length(n); i++) {
if (!rcu_access_pointer(n->child[i]))
s->nullpointers++;
+ }
}
}
rcu_read_unlock();
^ permalink raw reply related
* [RFC PATCH 10/17] fib_trie: Push rcu_read_lock/unlock to callers
From: Alexander Duyck @ 2014-12-22 17:41 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change is to start cleaning up some of the rcu_read_lock/unlock
handling. I realized while reviewing the code there are several spots that
I don't believe are being handled correctly or are masking warnings by
locally calling rcu_read_lock/unlock instead of calling them at the correct
level.
A common example is a call to fib_get_table followed by fib_table_lookup.
The rcu_read_lock/unlock ought to wrap both but there are several spots where
they were not wrapped.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
include/net/ip_fib.h | 50 ++++++++++-------
net/ipv4/fib_frontend.c | 27 +++++----
net/ipv4/fib_rules.c | 22 +++-----
net/ipv4/fib_trie.c | 137 ++++++++++++++++++++---------------------------
4 files changed, 113 insertions(+), 123 deletions(-)
diff --git a/include/net/ip_fib.h b/include/net/ip_fib.h
index 09a819e..5bd120e 100644
--- a/include/net/ip_fib.h
+++ b/include/net/ip_fib.h
@@ -222,16 +222,19 @@ static inline struct fib_table *fib_new_table(struct net *net, u32 id)
static inline int fib_lookup(struct net *net, const struct flowi4 *flp,
struct fib_result *res)
{
- struct fib_table *table;
+ int err = -ENETUNREACH;
+
+ rcu_read_lock();
+
+ if (!fib_table_lookup(fib_get_table(net, RT_TABLE_LOCAL), flp, res,
+ FIB_LOOKUP_NOREF) ||
+ !fib_table_lookup(fib_get_table(net, RT_TABLE_MAIN), flp, res,
+ FIB_LOOKUP_NOREF))
+ err = 0;
- table = fib_get_table(net, RT_TABLE_LOCAL);
- if (!fib_table_lookup(table, flp, res, FIB_LOOKUP_NOREF))
- return 0;
+ rcu_read_unlock();
- table = fib_get_table(net, RT_TABLE_MAIN);
- if (!fib_table_lookup(table, flp, res, FIB_LOOKUP_NOREF))
- return 0;
- return -ENETUNREACH;
+ return err;
}
#else /* CONFIG_IP_MULTIPLE_TABLES */
@@ -247,20 +250,25 @@ static inline int fib_lookup(struct net *net, struct flowi4 *flp,
struct fib_result *res)
{
if (!net->ipv4.fib_has_custom_rules) {
+ int err = -ENETUNREACH;
+
+ rcu_read_lock();
+
res->tclassid = 0;
- if (net->ipv4.fib_local &&
- !fib_table_lookup(net->ipv4.fib_local, flp, res,
- FIB_LOOKUP_NOREF))
- return 0;
- if (net->ipv4.fib_main &&
- !fib_table_lookup(net->ipv4.fib_main, flp, res,
- FIB_LOOKUP_NOREF))
- return 0;
- if (net->ipv4.fib_default &&
- !fib_table_lookup(net->ipv4.fib_default, flp, res,
- FIB_LOOKUP_NOREF))
- return 0;
- return -ENETUNREACH;
+ if ((net->ipv4.fib_local &&
+ !fib_table_lookup(net->ipv4.fib_local, flp, res,
+ FIB_LOOKUP_NOREF)) ||
+ (net->ipv4.fib_main &&
+ !fib_table_lookup(net->ipv4.fib_main, flp, res,
+ FIB_LOOKUP_NOREF)) ||
+ (net->ipv4.fib_default &&
+ !fib_table_lookup(net->ipv4.fib_default, flp, res,
+ FIB_LOOKUP_NOREF)))
+ err = 0;
+
+ rcu_read_unlock();
+
+ return err;
}
return __fib_lookup(net, flp, res);
}
diff --git a/net/ipv4/fib_frontend.c b/net/ipv4/fib_frontend.c
index 6689020..57be71d 100644
--- a/net/ipv4/fib_frontend.c
+++ b/net/ipv4/fib_frontend.c
@@ -109,6 +109,7 @@ struct fib_table *fib_new_table(struct net *net, u32 id)
return tb;
}
+/* caller must hold either rtnl or rcu read lock */
struct fib_table *fib_get_table(struct net *net, u32 id)
{
struct fib_table *tb;
@@ -119,15 +120,11 @@ struct fib_table *fib_get_table(struct net *net, u32 id)
id = RT_TABLE_MAIN;
h = id & (FIB_TABLE_HASHSZ - 1);
- rcu_read_lock();
head = &net->ipv4.fib_table_hash[h];
hlist_for_each_entry_rcu(tb, head, tb_hlist) {
- if (tb->tb_id == id) {
- rcu_read_unlock();
+ if (tb->tb_id == id)
return tb;
- }
}
- rcu_read_unlock();
return NULL;
}
#endif /* CONFIG_IP_MULTIPLE_TABLES */
@@ -167,16 +164,18 @@ static inline unsigned int __inet_dev_addr_type(struct net *net,
if (ipv4_is_multicast(addr))
return RTN_MULTICAST;
+ rcu_read_lock();
+
local_table = fib_get_table(net, RT_TABLE_LOCAL);
if (local_table) {
ret = RTN_UNICAST;
- rcu_read_lock();
if (!fib_table_lookup(local_table, &fl4, &res, FIB_LOOKUP_NOREF)) {
if (!dev || dev == res.fi->fib_dev)
ret = res.type;
}
- rcu_read_unlock();
}
+
+ rcu_read_unlock();
return ret;
}
@@ -919,7 +918,7 @@ void fib_del_ifaddr(struct in_ifaddr *ifa, struct in_ifaddr *iprim)
#undef BRD1_OK
}
-static void nl_fib_lookup(struct fib_result_nl *frn, struct fib_table *tb)
+static void nl_fib_lookup(struct net *net, struct fib_result_nl *frn)
{
struct fib_result res;
@@ -929,6 +928,11 @@ static void nl_fib_lookup(struct fib_result_nl *frn, struct fib_table *tb)
.flowi4_tos = frn->fl_tos,
.flowi4_scope = frn->fl_scope,
};
+ struct fib_table *tb;
+
+ rcu_read_lock();
+
+ tb = fib_get_table(net, frn->tb_id_in);
frn->err = -ENOENT;
if (tb) {
@@ -945,6 +949,8 @@ static void nl_fib_lookup(struct fib_result_nl *frn, struct fib_table *tb)
}
local_bh_enable();
}
+
+ rcu_read_unlock();
}
static void nl_fib_input(struct sk_buff *skb)
@@ -952,7 +958,6 @@ static void nl_fib_input(struct sk_buff *skb)
struct net *net;
struct fib_result_nl *frn;
struct nlmsghdr *nlh;
- struct fib_table *tb;
u32 portid;
net = sock_net(skb->sk);
@@ -967,9 +972,7 @@ static void nl_fib_input(struct sk_buff *skb)
nlh = nlmsg_hdr(skb);
frn = (struct fib_result_nl *) nlmsg_data(nlh);
- tb = fib_get_table(net, frn->tb_id_in);
-
- nl_fib_lookup(frn, tb);
+ nl_fib_lookup(net, frn);
portid = NETLINK_CB(skb).portid; /* netlink portid */
NETLINK_CB(skb).portid = 0; /* from kernel */
diff --git a/net/ipv4/fib_rules.c b/net/ipv4/fib_rules.c
index 8f7bd56..d3db718 100644
--- a/net/ipv4/fib_rules.c
+++ b/net/ipv4/fib_rules.c
@@ -81,27 +81,25 @@ static int fib4_rule_action(struct fib_rule *rule, struct flowi *flp,
break;
case FR_ACT_UNREACHABLE:
- err = -ENETUNREACH;
- goto errout;
+ return -ENETUNREACH;
case FR_ACT_PROHIBIT:
- err = -EACCES;
- goto errout;
+ return -EACCES;
case FR_ACT_BLACKHOLE:
default:
- err = -EINVAL;
- goto errout;
+ return -EINVAL;
}
+ rcu_read_lock();
+
tbl = fib_get_table(rule->fr_net, rule->table);
- if (!tbl)
- goto errout;
+ if (tbl)
+ err = fib_table_lookup(tbl, &flp->u.ip4,
+ (struct fib_result *)arg->result,
+ arg->flags);
- err = fib_table_lookup(tbl, &flp->u.ip4, (struct fib_result *) arg->result, arg->flags);
- if (err > 0)
- err = -EAGAIN;
-errout:
+ rcu_read_unlock();
return err;
}
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 74ad943..45fab6e 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -1181,72 +1181,6 @@ err:
return err;
}
-/* should be called with rcu_read_lock */
-static int check_leaf(struct fib_table *tb, struct trie *t, struct tnode *l,
- t_key key, const struct flowi4 *flp,
- struct fib_result *res, int fib_flags)
-{
- struct leaf_info *li;
- struct hlist_head *hhead = &l->list;
-
- hlist_for_each_entry_rcu(li, hhead, hlist) {
- struct fib_alias *fa;
-
- if (l->key != (key & li->mask_plen))
- continue;
-
- list_for_each_entry_rcu(fa, &li->falh, fa_list) {
- struct fib_info *fi = fa->fa_info;
- int nhsel, err;
-
- if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
- continue;
- if (fi->fib_dead)
- continue;
- if (fa->fa_info->fib_scope < flp->flowi4_scope)
- continue;
- fib_alias_accessed(fa);
- err = fib_props[fa->fa_type].error;
- if (unlikely(err < 0)) {
-#ifdef CONFIG_IP_FIB_TRIE_STATS
- this_cpu_inc(t->stats->semantic_match_passed);
-#endif
- return err;
- }
- if (fi->fib_flags & RTNH_F_DEAD)
- continue;
- for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
- const struct fib_nh *nh = &fi->fib_nh[nhsel];
-
- if (nh->nh_flags & RTNH_F_DEAD)
- continue;
- if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
- continue;
-
-#ifdef CONFIG_IP_FIB_TRIE_STATS
- this_cpu_inc(t->stats->semantic_match_passed);
-#endif
- res->prefixlen = li->plen;
- res->nh_sel = nhsel;
- res->type = fa->fa_type;
- res->scope = fi->fib_scope;
- res->fi = fi;
- res->table = tb;
- res->fa_head = &li->falh;
- if (!(fib_flags & FIB_LOOKUP_NOREF))
- atomic_inc(&fi->fib_clntref);
- return 0;
- }
- }
-
-#ifdef CONFIG_IP_FIB_TRIE_STATS
- this_cpu_ptr(t->stats->semantic_match_miss);
-#endif
- }
-
- return 1;
-}
-
static inline t_key prefix_mismatch(t_key key, struct tnode *n)
{
t_key prefix = n->key;
@@ -1254,6 +1188,7 @@ static inline t_key prefix_mismatch(t_key key, struct tnode *n)
return (key ^ prefix) & (prefix | -prefix);
}
+/* should be called with rcu_read_lock */
int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
struct fib_result *res, int fib_flags)
{
@@ -1263,15 +1198,12 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
#endif
const t_key key = ntohl(flp->daddr);
struct tnode *n, *pn;
+ struct leaf_info *li;
t_key cindex;
- int ret = 1;
-
- rcu_read_lock();
n = rcu_dereference(t->trie);
-
if (!n)
- goto failed;
+ return -EAGAIN;
#ifdef CONFIG_IP_FIB_TRIE_STATS
this_cpu_inc(stats->gets);
@@ -1346,7 +1278,7 @@ backtrace:
pn = node_parent_rcu(pn);
if (unlikely(!pn))
- goto failed;
+ return -EAGAIN;
#ifdef CONFIG_IP_FIB_TRIE_STATS
this_cpu_inc(stats->backtrack);
#endif
@@ -1364,12 +1296,61 @@ backtrace:
found:
/* Step 3: Process the leaf, if that fails fall back to backtracing */
- ret = check_leaf(tb, t, n, key, flp, res, fib_flags);
- if (unlikely(ret > 0))
- goto backtrace;
-failed:
- rcu_read_unlock();
- return ret;
+ hlist_for_each_entry_rcu(li, &n->list, hlist) {
+ struct fib_alias *fa;
+
+ if (n->key != (key & li->mask_plen))
+ continue;
+
+ list_for_each_entry_rcu(fa, &li->falh, fa_list) {
+ struct fib_info *fi = fa->fa_info;
+ int nhsel, err;
+
+ if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos)
+ continue;
+ if (fi->fib_dead)
+ continue;
+ if (fa->fa_info->fib_scope < flp->flowi4_scope)
+ continue;
+ fib_alias_accessed(fa);
+ err = fib_props[fa->fa_type].error;
+ if (unlikely(err < 0)) {
+#ifdef CONFIG_IP_FIB_TRIE_STATS
+ this_cpu_inc(stats->semantic_match_passed);
+#endif
+ return err;
+ }
+ if (fi->fib_flags & RTNH_F_DEAD)
+ continue;
+ for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) {
+ const struct fib_nh *nh = &fi->fib_nh[nhsel];
+
+ if (nh->nh_flags & RTNH_F_DEAD)
+ continue;
+ if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif)
+ continue;
+
+#ifdef CONFIG_IP_FIB_TRIE_STATS
+ this_cpu_inc(stats->semantic_match_passed);
+#endif
+ res->prefixlen = li->plen;
+ res->nh_sel = nhsel;
+ res->type = fa->fa_type;
+ res->scope = fi->fib_scope;
+ res->fi = fi;
+ res->table = tb;
+ res->fa_head = &li->falh;
+ if (!(fib_flags & FIB_LOOKUP_NOREF))
+ atomic_inc(&fi->fib_clntref);
+ return err;
+ }
+ }
+
+#ifdef CONFIG_IP_FIB_TRIE_STATS
+ this_cpu_inc(stats->semantic_match_miss);
+#endif
+ }
+ goto backtrace;
}
EXPORT_SYMBOL_GPL(fib_table_lookup);
^ permalink raw reply related
* [RFC PATCH 11/17] fib_trie: Move resize to after inflate/halve
From: Alexander Duyck @ 2014-12-22 17:42 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change consists of a cut/paste of resize to behind inflate and halve
so that I could remove the two function prototypes.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 311 +++++++++++++++++++++++++--------------------------
1 file changed, 154 insertions(+), 157 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 45fab6e..2394cd8 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -149,8 +149,6 @@ struct trie {
static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
struct tnode *n, int wasfull);
static struct tnode *resize(struct trie *t, struct tnode *tn);
-static struct tnode *inflate(struct trie *t, struct tnode *tn);
-static struct tnode *halve(struct trie *t, struct tnode *tn);
/* tnodes to free after resize(); protected by RTNL */
static struct callback_head *tnode_free_head;
static size_t tnode_free_size;
@@ -447,161 +445,6 @@ static void put_child_root(struct tnode *tp, struct trie *t,
rcu_assign_pointer(t->trie, n);
}
-#define MAX_WORK 10
-static struct tnode *resize(struct trie *t, struct tnode *tn)
-{
- struct tnode *old_tn, *n = NULL;
- int inflate_threshold_use;
- int halve_threshold_use;
- int max_work;
-
- if (!tn)
- return NULL;
-
- pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
- tn, inflate_threshold, halve_threshold);
-
- /* No children */
- if (tn->empty_children > (tnode_child_length(tn) - 1))
- goto no_children;
-
- /* One child */
- if (tn->empty_children == (tnode_child_length(tn) - 1))
- goto one_child;
- /*
- * Double as long as the resulting node has a number of
- * nonempty nodes that are above the threshold.
- */
-
- /*
- * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
- * the Helsinki University of Technology and Matti Tikkanen of Nokia
- * Telecommunications, page 6:
- * "A node is doubled if the ratio of non-empty children to all
- * children in the *doubled* node is at least 'high'."
- *
- * 'high' in this instance is the variable 'inflate_threshold'. It
- * is expressed as a percentage, so we multiply it with
- * tnode_child_length() and instead of multiplying by 2 (since the
- * child array will be doubled by inflate()) and multiplying
- * the left-hand side by 100 (to handle the percentage thing) we
- * multiply the left-hand side by 50.
- *
- * The left-hand side may look a bit weird: tnode_child_length(tn)
- * - tn->empty_children is of course the number of non-null children
- * in the current node. tn->full_children is the number of "full"
- * children, that is non-null tnodes with a skip value of 0.
- * All of those will be doubled in the resulting inflated tnode, so
- * we just count them one extra time here.
- *
- * A clearer way to write this would be:
- *
- * to_be_doubled = tn->full_children;
- * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
- * tn->full_children;
- *
- * new_child_length = tnode_child_length(tn) * 2;
- *
- * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
- * new_child_length;
- * if (new_fill_factor >= inflate_threshold)
- *
- * ...and so on, tho it would mess up the while () loop.
- *
- * anyway,
- * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
- * inflate_threshold
- *
- * avoid a division:
- * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
- * inflate_threshold * new_child_length
- *
- * expand not_to_be_doubled and to_be_doubled, and shorten:
- * 100 * (tnode_child_length(tn) - tn->empty_children +
- * tn->full_children) >= inflate_threshold * new_child_length
- *
- * expand new_child_length:
- * 100 * (tnode_child_length(tn) - tn->empty_children +
- * tn->full_children) >=
- * inflate_threshold * tnode_child_length(tn) * 2
- *
- * shorten again:
- * 50 * (tn->full_children + tnode_child_length(tn) -
- * tn->empty_children) >= inflate_threshold *
- * tnode_child_length(tn)
- *
- */
-
- /* Keep root node larger */
-
- if (!node_parent(tn)) {
- inflate_threshold_use = inflate_threshold_root;
- halve_threshold_use = halve_threshold_root;
- } else {
- inflate_threshold_use = inflate_threshold;
- halve_threshold_use = halve_threshold;
- }
-
- max_work = MAX_WORK;
- while ((tn->full_children > 0 && max_work-- &&
- 50 * (tn->full_children + tnode_child_length(tn)
- - tn->empty_children)
- >= inflate_threshold_use * tnode_child_length(tn))) {
-
- old_tn = tn;
- tn = inflate(t, tn);
-
- if (IS_ERR(tn)) {
- tn = old_tn;
-#ifdef CONFIG_IP_FIB_TRIE_STATS
- this_cpu_inc(t->stats->resize_node_skipped);
-#endif
- break;
- }
- }
-
- /* Return if at least one inflate is run */
- if (max_work != MAX_WORK)
- return tn;
-
- /*
- * Halve as long as the number of empty children in this
- * node is above threshold.
- */
-
- max_work = MAX_WORK;
- while (tn->bits > 1 && max_work-- &&
- 100 * (tnode_child_length(tn) - tn->empty_children) <
- halve_threshold_use * tnode_child_length(tn)) {
-
- old_tn = tn;
- tn = halve(t, tn);
- if (IS_ERR(tn)) {
- tn = old_tn;
-#ifdef CONFIG_IP_FIB_TRIE_STATS
- this_cpu_inc(t->stats->resize_node_skipped);
-#endif
- break;
- }
- }
-
-
- /* Only one child remains */
- if (tn->empty_children == (tnode_child_length(tn) - 1)) {
- unsigned long i;
-one_child:
- for (i = tnode_child_length(tn); !n && i;)
- n = tnode_get_child(tn, --i);
-no_children:
- /* compress one level */
- node_set_parent(n, NULL);
- tnode_free_safe(tn);
- return n;
- }
- return tn;
-}
-
-
static void tnode_clean_free(struct tnode *tn)
{
struct tnode *tofree;
@@ -804,6 +647,160 @@ nomem:
return ERR_PTR(-ENOMEM);
}
+#define MAX_WORK 10
+static struct tnode *resize(struct trie *t, struct tnode *tn)
+{
+ struct tnode *old_tn, *n = NULL;
+ int inflate_threshold_use;
+ int halve_threshold_use;
+ int max_work;
+
+ if (!tn)
+ return NULL;
+
+ pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
+ tn, inflate_threshold, halve_threshold);
+
+ /* No children */
+ if (tn->empty_children > (tnode_child_length(tn) - 1))
+ goto no_children;
+
+ /* One child */
+ if (tn->empty_children == (tnode_child_length(tn) - 1))
+ goto one_child;
+ /*
+ * Double as long as the resulting node has a number of
+ * nonempty nodes that are above the threshold.
+ */
+
+ /*
+ * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
+ * the Helsinki University of Technology and Matti Tikkanen of Nokia
+ * Telecommunications, page 6:
+ * "A node is doubled if the ratio of non-empty children to all
+ * children in the *doubled* node is at least 'high'."
+ *
+ * 'high' in this instance is the variable 'inflate_threshold'. It
+ * is expressed as a percentage, so we multiply it with
+ * tnode_child_length() and instead of multiplying by 2 (since the
+ * child array will be doubled by inflate()) and multiplying
+ * the left-hand side by 100 (to handle the percentage thing) we
+ * multiply the left-hand side by 50.
+ *
+ * The left-hand side may look a bit weird: tnode_child_length(tn)
+ * - tn->empty_children is of course the number of non-null children
+ * in the current node. tn->full_children is the number of "full"
+ * children, that is non-null tnodes with a skip value of 0.
+ * All of those will be doubled in the resulting inflated tnode, so
+ * we just count them one extra time here.
+ *
+ * A clearer way to write this would be:
+ *
+ * to_be_doubled = tn->full_children;
+ * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
+ * tn->full_children;
+ *
+ * new_child_length = tnode_child_length(tn) * 2;
+ *
+ * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
+ * new_child_length;
+ * if (new_fill_factor >= inflate_threshold)
+ *
+ * ...and so on, tho it would mess up the while () loop.
+ *
+ * anyway,
+ * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
+ * inflate_threshold
+ *
+ * avoid a division:
+ * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
+ * inflate_threshold * new_child_length
+ *
+ * expand not_to_be_doubled and to_be_doubled, and shorten:
+ * 100 * (tnode_child_length(tn) - tn->empty_children +
+ * tn->full_children) >= inflate_threshold * new_child_length
+ *
+ * expand new_child_length:
+ * 100 * (tnode_child_length(tn) - tn->empty_children +
+ * tn->full_children) >=
+ * inflate_threshold * tnode_child_length(tn) * 2
+ *
+ * shorten again:
+ * 50 * (tn->full_children + tnode_child_length(tn) -
+ * tn->empty_children) >= inflate_threshold *
+ * tnode_child_length(tn)
+ *
+ */
+
+ /* Keep root node larger */
+
+ if (!node_parent(tn)) {
+ inflate_threshold_use = inflate_threshold_root;
+ halve_threshold_use = halve_threshold_root;
+ } else {
+ inflate_threshold_use = inflate_threshold;
+ halve_threshold_use = halve_threshold;
+ }
+
+ max_work = MAX_WORK;
+ while ((tn->full_children > 0 && max_work-- &&
+ 50 * (tn->full_children + tnode_child_length(tn)
+ - tn->empty_children)
+ >= inflate_threshold_use * tnode_child_length(tn))) {
+
+ old_tn = tn;
+ tn = inflate(t, tn);
+
+ if (IS_ERR(tn)) {
+ tn = old_tn;
+#ifdef CONFIG_IP_FIB_TRIE_STATS
+ this_cpu_inc(t->stats->resize_node_skipped);
+#endif
+ break;
+ }
+ }
+
+ /* Return if at least one inflate is run */
+ if (max_work != MAX_WORK)
+ return tn;
+
+ /*
+ * Halve as long as the number of empty children in this
+ * node is above threshold.
+ */
+
+ max_work = MAX_WORK;
+ while (tn->bits > 1 && max_work-- &&
+ 100 * (tnode_child_length(tn) - tn->empty_children) <
+ halve_threshold_use * tnode_child_length(tn)) {
+
+ old_tn = tn;
+ tn = halve(t, tn);
+ if (IS_ERR(tn)) {
+ tn = old_tn;
+#ifdef CONFIG_IP_FIB_TRIE_STATS
+ this_cpu_inc(t->stats->resize_node_skipped);
+#endif
+ break;
+ }
+ }
+
+
+ /* Only one child remains */
+ if (tn->empty_children == (tnode_child_length(tn) - 1)) {
+ unsigned long i;
+one_child:
+ for (i = tnode_child_length(tn); !n && i;)
+ n = tnode_get_child(tn, --i);
+no_children:
+ /* compress one level */
+ node_set_parent(n, NULL);
+ tnode_free_safe(tn);
+ return n;
+ }
+ return tn;
+}
+
/* readside must use rcu_read_lock currently dump routines
via get_fa_head and dump */
^ permalink raw reply related
* [RFC PATCH 12/17] fib_trie: Add functions should_inflate and should_halve
From: Alexander Duyck @ 2014-12-22 17:42 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change pulls the logic for if we should inflate/halve the nodes out
into separate functions. It also addresses what I believe is a bug where 1
full node is all that is needed to keep a node from ever being halved.
Simple script to reproduce the issue:
modprobe dummy; ifconfig dummy0 up
for i in `seq 0 255`; do ifconfig dummy0:$i 10.0.${i}.1/24 up; done
ifconfig dummy0:256 10.0.255.33/16 up
for i in `seq 0 254`; do ifconfig dummy0:$i down; done
Results from /proc/net/fib_triestat
Before:
Local:
Aver depth: 3.00
Max depth: 4
Leaves: 17
Prefixes: 18
Internal nodes: 11
1: 8 2: 2 10: 1
Pointers: 1048
Null ptrs: 1021
Total size: 11 kB
After:
Local:
Aver depth: 3.41
Max depth: 5
Leaves: 17
Prefixes: 18
Internal nodes: 12
1: 8 2: 3 3: 1
Pointers: 36
Null ptrs: 8
Total size: 3 kB
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 175 ++++++++++++++++++++++++++-------------------------
1 file changed, 89 insertions(+), 86 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 2394cd8..7ef101c 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -647,12 +647,94 @@ nomem:
return ERR_PTR(-ENOMEM);
}
+/* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
+ * the Helsinki University of Technology and Matti Tikkanen of Nokia
+ * Telecommunications, page 6:
+ * "A node is doubled if the ratio of non-empty children to all
+ * children in the *doubled* node is at least 'high'."
+ *
+ * 'high' in this instance is the variable 'inflate_threshold'. It
+ * is expressed as a percentage, so we multiply it with
+ * tnode_child_length() and instead of multiplying by 2 (since the
+ * child array will be doubled by inflate()) and multiplying
+ * the left-hand side by 100 (to handle the percentage thing) we
+ * multiply the left-hand side by 50.
+ *
+ * The left-hand side may look a bit weird: tnode_child_length(tn)
+ * - tn->empty_children is of course the number of non-null children
+ * in the current node. tn->full_children is the number of "full"
+ * children, that is non-null tnodes with a skip value of 0.
+ * All of those will be doubled in the resulting inflated tnode, so
+ * we just count them one extra time here.
+ *
+ * A clearer way to write this would be:
+ *
+ * to_be_doubled = tn->full_children;
+ * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
+ * tn->full_children;
+ *
+ * new_child_length = tnode_child_length(tn) * 2;
+ *
+ * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
+ * new_child_length;
+ * if (new_fill_factor >= inflate_threshold)
+ *
+ * ...and so on, tho it would mess up the while () loop.
+ *
+ * anyway,
+ * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
+ * inflate_threshold
+ *
+ * avoid a division:
+ * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
+ * inflate_threshold * new_child_length
+ *
+ * expand not_to_be_doubled and to_be_doubled, and shorten:
+ * 100 * (tnode_child_length(tn) - tn->empty_children +
+ * tn->full_children) >= inflate_threshold * new_child_length
+ *
+ * expand new_child_length:
+ * 100 * (tnode_child_length(tn) - tn->empty_children +
+ * tn->full_children) >=
+ * inflate_threshold * tnode_child_length(tn) * 2
+ *
+ * shorten again:
+ * 50 * (tn->full_children + tnode_child_length(tn) -
+ * tn->empty_children) >= inflate_threshold *
+ * tnode_child_length(tn)
+ *
+ */
+static bool should_inflate(const struct tnode *tn)
+{
+ unsigned long used = tnode_child_length(tn);
+ unsigned long threshold = used;
+
+ /* Keep root node larger */
+ threshold *= node_parent(tn) ? inflate_threshold :
+ inflate_threshold_root;
+ used += tn->full_children;
+ used -= tn->empty_children;
+
+ return tn->pos && ((50 * used) >= threshold);
+}
+
+static bool should_halve(const struct tnode *tn)
+{
+ unsigned long used = tnode_child_length(tn);
+ unsigned long threshold = used;
+
+ /* Keep root node larger */
+ threshold *= node_parent(tn) ? halve_threshold :
+ halve_threshold_root;
+ used -= tn->empty_children;
+
+ return (tn->bits > 1) && ((100 * used) < threshold);
+}
+
#define MAX_WORK 10
static struct tnode *resize(struct trie *t, struct tnode *tn)
{
struct tnode *old_tn, *n = NULL;
- int inflate_threshold_use;
- int halve_threshold_use;
int max_work;
if (!tn)
@@ -668,86 +750,12 @@ static struct tnode *resize(struct trie *t, struct tnode *tn)
/* One child */
if (tn->empty_children == (tnode_child_length(tn) - 1))
goto one_child;
- /*
- * Double as long as the resulting node has a number of
- * nonempty nodes that are above the threshold.
- */
- /*
- * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
- * the Helsinki University of Technology and Matti Tikkanen of Nokia
- * Telecommunications, page 6:
- * "A node is doubled if the ratio of non-empty children to all
- * children in the *doubled* node is at least 'high'."
- *
- * 'high' in this instance is the variable 'inflate_threshold'. It
- * is expressed as a percentage, so we multiply it with
- * tnode_child_length() and instead of multiplying by 2 (since the
- * child array will be doubled by inflate()) and multiplying
- * the left-hand side by 100 (to handle the percentage thing) we
- * multiply the left-hand side by 50.
- *
- * The left-hand side may look a bit weird: tnode_child_length(tn)
- * - tn->empty_children is of course the number of non-null children
- * in the current node. tn->full_children is the number of "full"
- * children, that is non-null tnodes with a skip value of 0.
- * All of those will be doubled in the resulting inflated tnode, so
- * we just count them one extra time here.
- *
- * A clearer way to write this would be:
- *
- * to_be_doubled = tn->full_children;
- * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
- * tn->full_children;
- *
- * new_child_length = tnode_child_length(tn) * 2;
- *
- * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
- * new_child_length;
- * if (new_fill_factor >= inflate_threshold)
- *
- * ...and so on, tho it would mess up the while () loop.
- *
- * anyway,
- * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
- * inflate_threshold
- *
- * avoid a division:
- * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
- * inflate_threshold * new_child_length
- *
- * expand not_to_be_doubled and to_be_doubled, and shorten:
- * 100 * (tnode_child_length(tn) - tn->empty_children +
- * tn->full_children) >= inflate_threshold * new_child_length
- *
- * expand new_child_length:
- * 100 * (tnode_child_length(tn) - tn->empty_children +
- * tn->full_children) >=
- * inflate_threshold * tnode_child_length(tn) * 2
- *
- * shorten again:
- * 50 * (tn->full_children + tnode_child_length(tn) -
- * tn->empty_children) >= inflate_threshold *
- * tnode_child_length(tn)
- *
+ /* Double as long as the resulting node has a number of
+ * nonempty nodes that are above the threshold.
*/
-
- /* Keep root node larger */
-
- if (!node_parent(tn)) {
- inflate_threshold_use = inflate_threshold_root;
- halve_threshold_use = halve_threshold_root;
- } else {
- inflate_threshold_use = inflate_threshold;
- halve_threshold_use = halve_threshold;
- }
-
max_work = MAX_WORK;
- while ((tn->full_children > 0 && max_work-- &&
- 50 * (tn->full_children + tnode_child_length(tn)
- - tn->empty_children)
- >= inflate_threshold_use * tnode_child_length(tn))) {
-
+ while (should_inflate(tn) && max_work--) {
old_tn = tn;
tn = inflate(t, tn);
@@ -764,16 +772,11 @@ static struct tnode *resize(struct trie *t, struct tnode *tn)
if (max_work != MAX_WORK)
return tn;
- /*
- * Halve as long as the number of empty children in this
+ /* Halve as long as the number of empty children in this
* node is above threshold.
*/
-
max_work = MAX_WORK;
- while (tn->bits > 1 && max_work-- &&
- 100 * (tnode_child_length(tn) - tn->empty_children) <
- halve_threshold_use * tnode_child_length(tn)) {
-
+ while (should_halve(tn) && max_work--) {
old_tn = tn;
tn = halve(t, tn);
if (IS_ERR(tn)) {
^ permalink raw reply related
* [RFC PATCH 13/17] fib_trie: Push assignment of child to parent down into inflate/halve
From: Alexander Duyck @ 2014-12-22 17:42 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change makes it so that the assignment of the tnode to the parent is
handled directly within whatever function is currently handling the node be
it inflate, halve, or resize. By doing this we can avoid some of the need
to set NULL pointers in the tree while we are resizing the subnodes.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 149 +++++++++++++++++++++++----------------------------
1 file changed, 66 insertions(+), 83 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 7ef101c..352ecf4 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -146,9 +146,7 @@ struct trie {
#endif
};
-static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
- struct tnode *n, int wasfull);
-static struct tnode *resize(struct trie *t, struct tnode *tn);
+static void resize(struct trie *t, struct tnode *tn);
/* tnodes to free after resize(); protected by RTNL */
static struct callback_head *tnode_free_head;
static size_t tnode_free_size;
@@ -396,22 +394,13 @@ static inline int tnode_full(const struct tnode *tn, const struct tnode *n)
return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
}
-static inline void put_child(struct tnode *tn, unsigned long i,
- struct tnode *n)
-{
- tnode_put_child_reorg(tn, i, n, -1);
-}
-
- /*
- * Add a child at position i overwriting the old value.
- * Update the value of full_children and empty_children.
- */
-
-static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
- struct tnode *n, int wasfull)
+/* Add a child at position i overwriting the old value.
+ * Update the value of full_children and empty_children.
+ */
+static void put_child(struct tnode *tn, unsigned long i, struct tnode *n)
{
struct tnode *chi = rtnl_dereference(tn->child[i]);
- int isfull;
+ int isfull, wasfull;
BUG_ON(i >= tnode_child_length(tn));
@@ -422,10 +411,9 @@ static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
tn->empty_children--;
/* update fullChildren */
- if (wasfull == -1)
- wasfull = tnode_full(tn, chi);
-
+ wasfull = tnode_full(tn, chi);
isfull = tnode_full(tn, n);
+
if (wasfull && !isfull)
tn->full_children--;
else if (!wasfull && isfull)
@@ -458,9 +446,10 @@ static void tnode_clean_free(struct tnode *tn)
node_free(tn);
}
-static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
+static int inflate(struct trie *t, struct tnode *oldtnode)
{
unsigned long olen = tnode_child_length(oldtnode);
+ struct tnode *tp = node_parent(oldtnode);
struct tnode *tn;
unsigned long i;
t_key m;
@@ -468,9 +457,8 @@ static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
pr_debug("In inflate\n");
tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
-
if (!tn)
- return ERR_PTR(-ENOMEM);
+ return -ENOMEM;
/*
* Preallocate and store tnodes before the actual work so we
@@ -564,30 +552,36 @@ static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
put_child(left, j, rtnl_dereference(inode->child[j]));
put_child(right, j, rtnl_dereference(inode->child[j + size]));
}
- put_child(tn, 2*i, resize(t, left));
- put_child(tn, 2*i+1, resize(t, right));
+
+ put_child(tn, 2 * i, left);
+ put_child(tn, 2 * i + 1, right);
tnode_free_safe(inode);
+
+ resize(t, left);
+ resize(t, right);
}
+
+ put_child_root(tp, t, tn->key, tn);
tnode_free_safe(oldtnode);
- return tn;
+ return 0;
nomem:
tnode_clean_free(tn);
- return ERR_PTR(-ENOMEM);
+ return -ENOMEM;
}
-static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
+static int halve(struct trie *t, struct tnode *oldtnode)
{
unsigned long olen = tnode_child_length(oldtnode);
+ struct tnode *tp = node_parent(oldtnode);
struct tnode *tn, *left, *right;
int i;
pr_debug("In halve\n");
tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
-
if (!tn)
- return ERR_PTR(-ENOMEM);
+ return -ENOMEM;
/*
* Preallocate and store tnodes before the actual work so we
@@ -606,8 +600,10 @@ static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
newn = tnode_new(left->key, oldtnode->pos, 1);
- if (!newn)
- goto nomem;
+ if (!newn) {
+ tnode_clean_free(tn);
+ return -ENOMEM;
+ }
put_child(tn, i/2, newn);
}
@@ -635,16 +631,18 @@ static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
/* Two nonempty children */
newBinNode = tnode_get_child(tn, i/2);
- put_child(tn, i/2, NULL);
put_child(newBinNode, 0, left);
put_child(newBinNode, 1, right);
- put_child(tn, i/2, resize(t, newBinNode));
+
+ put_child(tn, i / 2, newBinNode);
+
+ resize(t, newBinNode);
}
+
+ put_child_root(tp, t, tn->key, tn);
tnode_free_safe(oldtnode);
- return tn;
-nomem:
- tnode_clean_free(tn);
- return ERR_PTR(-ENOMEM);
+
+ return 0;
}
/* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
@@ -704,45 +702,48 @@ nomem:
* tnode_child_length(tn)
*
*/
-static bool should_inflate(const struct tnode *tn)
+static bool should_inflate(const struct tnode *tp, const struct tnode *tn)
{
unsigned long used = tnode_child_length(tn);
unsigned long threshold = used;
/* Keep root node larger */
- threshold *= node_parent(tn) ? inflate_threshold :
- inflate_threshold_root;
+ threshold *= tp ? inflate_threshold : inflate_threshold_root;
used += tn->full_children;
used -= tn->empty_children;
return tn->pos && ((50 * used) >= threshold);
}
-static bool should_halve(const struct tnode *tn)
+static bool should_halve(const struct tnode *tp, const struct tnode *tn)
{
unsigned long used = tnode_child_length(tn);
unsigned long threshold = used;
/* Keep root node larger */
- threshold *= node_parent(tn) ? halve_threshold :
- halve_threshold_root;
+ threshold *= tp ? halve_threshold : halve_threshold_root;
used -= tn->empty_children;
return (tn->bits > 1) && ((100 * used) < threshold);
}
#define MAX_WORK 10
-static struct tnode *resize(struct trie *t, struct tnode *tn)
+static void resize(struct trie *t, struct tnode *tn)
{
- struct tnode *old_tn, *n = NULL;
+ struct tnode *tp = node_parent(tn), *n = NULL;
+ struct tnode __rcu **cptr;
int max_work;
- if (!tn)
- return NULL;
-
pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
tn, inflate_threshold, halve_threshold);
+ /* track the tnode via the pointer from the parent instead of
+ * doing it ourselves. This way we can let RCU fully do its
+ * thing without us interfering
+ */
+ cptr = tp ? &tp->child[get_index(tn->key, tp)] : &t->trie;
+ BUG_ON(tn != rtnl_dereference(*cptr));
+
/* No children */
if (tn->empty_children > (tnode_child_length(tn) - 1))
goto no_children;
@@ -755,39 +756,35 @@ static struct tnode *resize(struct trie *t, struct tnode *tn)
* nonempty nodes that are above the threshold.
*/
max_work = MAX_WORK;
- while (should_inflate(tn) && max_work--) {
- old_tn = tn;
- tn = inflate(t, tn);
-
- if (IS_ERR(tn)) {
- tn = old_tn;
+ while (should_inflate(tp, tn) && max_work--) {
+ if (inflate(t, tn)) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
this_cpu_inc(t->stats->resize_node_skipped);
#endif
break;
}
+
+ tn = rtnl_dereference(*cptr);
}
/* Return if at least one inflate is run */
if (max_work != MAX_WORK)
- return tn;
+ return;
/* Halve as long as the number of empty children in this
* node is above threshold.
*/
max_work = MAX_WORK;
- while (should_halve(tn) && max_work--) {
- old_tn = tn;
- tn = halve(t, tn);
- if (IS_ERR(tn)) {
- tn = old_tn;
+ while (should_halve(tp, tn) && max_work--) {
+ if (halve(t, tn)) {
#ifdef CONFIG_IP_FIB_TRIE_STATS
this_cpu_inc(t->stats->resize_node_skipped);
#endif
break;
}
- }
+ tn = rtnl_dereference(*cptr);
+ }
/* Only one child remains */
if (tn->empty_children == (tnode_child_length(tn) - 1)) {
@@ -797,11 +794,12 @@ one_child:
n = tnode_get_child(tn, --i);
no_children:
/* compress one level */
- node_set_parent(n, NULL);
+ put_child_root(tp, t, tn->key, n);
+ node_set_parent(n, tp);
+
+ /* drop dead node */
tnode_free_safe(tn);
- return n;
}
- return tn;
}
/* readside must use rcu_read_lock currently dump routines
@@ -882,34 +880,19 @@ static struct tnode *fib_find_node(struct trie *t, u32 key)
static void trie_rebalance(struct trie *t, struct tnode *tn)
{
- int wasfull;
- t_key cindex, key;
struct tnode *tp;
- key = tn->key;
-
- while (tn != NULL && (tp = node_parent(tn)) != NULL) {
- cindex = get_index(key, tp);
- wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
- tn = resize(t, tn);
-
- tnode_put_child_reorg(tp, cindex, tn, wasfull);
-
- tp = node_parent(tn);
- if (!tp)
- rcu_assign_pointer(t->trie, tn);
+ while ((tp = node_parent(tn)) != NULL) {
+ resize(t, tn);
tnode_free_flush();
- if (!tp)
- break;
tn = tp;
}
/* Handle last (top) tnode */
if (IS_TNODE(tn))
- tn = resize(t, tn);
+ resize(t, tn);
- rcu_assign_pointer(t->trie, tn);
tnode_free_flush();
}
^ permalink raw reply related
* [RFC PATCH 14/17] fib_trie: Push tnode flushing down to inflate/halve
From: Alexander Duyck @ 2014-12-22 17:42 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change pushes the tnode freeing down into the inflate and halve
functions. It makes more sense here as we have a better grasp of what is
going on and when a given cluster of nodes is ready to be freed.
I believe this may address a bug in the freeing logic as well. For some
reason if the freelist got to a certain size we would call
synchronize_rcu(). I'm assuming that what they meant to do is call
synchronize_rcu() after they had handed off that much memory via
call_rcu(). As such that is what I have updated the behavior to be.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 103 +++++++++++++++++++++++++--------------------------
1 file changed, 50 insertions(+), 53 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 352ecf4..a41abf8 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -147,8 +147,6 @@ struct trie {
};
static void resize(struct trie *t, struct tnode *tn);
-/* tnodes to free after resize(); protected by RTNL */
-static struct callback_head *tnode_free_head;
static size_t tnode_free_size;
/*
@@ -307,32 +305,6 @@ static struct tnode *tnode_alloc(size_t size)
return vzalloc(size);
}
-static void tnode_free_safe(struct tnode *tn)
-{
- BUG_ON(IS_LEAF(tn));
- tn->rcu.next = tnode_free_head;
- tnode_free_head = &tn->rcu;
-}
-
-static void tnode_free_flush(void)
-{
- struct callback_head *head;
-
- while ((head = tnode_free_head)) {
- struct tnode *tn = container_of(head, struct tnode, rcu);
-
- tnode_free_head = head->next;
- tnode_free_size += offsetof(struct tnode, child[1 << tn->bits]);
-
- node_free(tn);
- }
-
- if (tnode_free_size >= PAGE_SIZE * sync_pages) {
- tnode_free_size = 0;
- synchronize_rcu();
- }
-}
-
static struct tnode *leaf_new(t_key key)
{
struct tnode *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
@@ -433,17 +405,33 @@ static void put_child_root(struct tnode *tp, struct trie *t,
rcu_assign_pointer(t->trie, n);
}
-static void tnode_clean_free(struct tnode *tn)
+static inline void tnode_free_init(struct tnode *tn)
{
- struct tnode *tofree;
- unsigned long i;
+ tn->rcu.next = NULL;
+}
+
+static inline void tnode_free_append(struct tnode *tn, struct tnode *n)
+{
+ n->rcu.next = tn->rcu.next;
+ tn->rcu.next = &n->rcu;
+}
- for (i = 0; i < tnode_child_length(tn); i++) {
- tofree = tnode_get_child(tn, i);
- if (tofree)
- node_free(tofree);
+static void tnode_free(struct tnode *tn)
+{
+ struct callback_head *head = &tn->rcu;
+
+ while (head) {
+ head = head->next;
+ tnode_free_size += offsetof(struct tnode, child[1 << tn->bits]);
+ node_free(tn);
+
+ tn = container_of(head, struct tnode, rcu);
+ }
+
+ if (tnode_free_size >= PAGE_SIZE * sync_pages) {
+ tnode_free_size = 0;
+ synchronize_rcu();
}
- node_free(tn);
}
static int inflate(struct trie *t, struct tnode *oldtnode)
@@ -476,20 +464,23 @@ static int inflate(struct trie *t, struct tnode *oldtnode)
inode->bits - 1);
if (!left)
goto nomem;
+ tnode_free_append(tn, left);
right = tnode_new(inode->key | m, inode->pos,
inode->bits - 1);
- if (!right) {
- node_free(left);
+ if (!right)
goto nomem;
- }
+ tnode_free_append(tn, right);
put_child(tn, 2*i, left);
put_child(tn, 2*i+1, right);
}
}
+ /* prepare oldtnode to be freed */
+ tnode_free_init(oldtnode);
+
for (i = 0; i < olen; i++) {
struct tnode *inode = tnode_get_child(oldtnode, i);
struct tnode *left, *right;
@@ -505,12 +496,13 @@ static int inflate(struct trie *t, struct tnode *oldtnode)
continue;
}
+ /* drop the node in the old tnode free list */
+ tnode_free_append(oldtnode, inode);
+
/* An internal node with two children */
if (inode->bits == 1) {
put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
-
- tnode_free_safe(inode);
continue;
}
@@ -556,17 +548,19 @@ static int inflate(struct trie *t, struct tnode *oldtnode)
put_child(tn, 2 * i, left);
put_child(tn, 2 * i + 1, right);
- tnode_free_safe(inode);
-
+ /* resize child nodes */
resize(t, left);
resize(t, right);
}
put_child_root(tp, t, tn->key, tn);
- tnode_free_safe(oldtnode);
+
+ /* we completed without error, prepare to free old node */
+ tnode_free(oldtnode);
return 0;
nomem:
- tnode_clean_free(tn);
+ /* all pointers should be clean so we are done */
+ tnode_free(tn);
return -ENOMEM;
}
@@ -599,17 +593,20 @@ static int halve(struct trie *t, struct tnode *oldtnode)
struct tnode *newn;
newn = tnode_new(left->key, oldtnode->pos, 1);
-
if (!newn) {
- tnode_clean_free(tn);
+ tnode_free(tn);
return -ENOMEM;
}
+ tnode_free_append(tn, newn);
put_child(tn, i/2, newn);
}
}
+ /* prepare oldtnode to be freed */
+ tnode_free_init(oldtnode);
+
for (i = 0; i < olen; i += 2) {
struct tnode *newBinNode;
@@ -636,11 +633,14 @@ static int halve(struct trie *t, struct tnode *oldtnode)
put_child(tn, i / 2, newBinNode);
+ /* resize child node */
resize(t, newBinNode);
}
put_child_root(tp, t, tn->key, tn);
- tnode_free_safe(oldtnode);
+
+ /* all pointers should be clean so we are done */
+ tnode_free(oldtnode);
return 0;
}
@@ -798,7 +798,8 @@ no_children:
node_set_parent(n, tp);
/* drop dead node */
- tnode_free_safe(tn);
+ tnode_free_init(tn);
+ tnode_free(tn);
}
}
@@ -884,16 +885,12 @@ static void trie_rebalance(struct trie *t, struct tnode *tn)
while ((tp = node_parent(tn)) != NULL) {
resize(t, tn);
-
- tnode_free_flush();
tn = tp;
}
/* Handle last (top) tnode */
if (IS_TNODE(tn))
resize(t, tn);
-
- tnode_free_flush();
}
/* only used from updater-side */
^ permalink raw reply related
* [RFC PATCH 15/17] fib_trie: inflate/halve nodes in a more RCU friendly way
From: Alexander Duyck @ 2014-12-22 17:42 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change pulls the node_set_parent functionality out of put_child_reorg
and instead leaves that to the function to take care of as well. By doing
this we can fully construct the new cluster of tnodes and all of the
pointers out of it before we start routing pointers into it.
I am suspecting this will likely fix some concurency issues though I don't
have a good test to show as such.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 236 +++++++++++++++++++++++++--------------------------
1 file changed, 115 insertions(+), 121 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index a41abf8..1a0f9c5 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -391,8 +391,6 @@ static void put_child(struct tnode *tn, unsigned long i, struct tnode *n)
else if (!wasfull && isfull)
tn->full_children++;
- node_set_parent(n, tn);
-
rcu_assign_pointer(tn->child[i], n);
}
@@ -436,10 +434,8 @@ static void tnode_free(struct tnode *tn)
static int inflate(struct trie *t, struct tnode *oldtnode)
{
- unsigned long olen = tnode_child_length(oldtnode);
- struct tnode *tp = node_parent(oldtnode);
- struct tnode *tn;
- unsigned long i;
+ struct tnode *inode, *node0, *node1, *tn, *tp;
+ unsigned long i, j, k;
t_key m;
pr_debug("In inflate\n");
@@ -448,43 +444,13 @@ static int inflate(struct trie *t, struct tnode *oldtnode)
if (!tn)
return -ENOMEM;
- /*
- * Preallocate and store tnodes before the actual work so we
- * don't get into an inconsistent state if memory allocation
- * fails. In case of failure we return the oldnode and inflate
- * of tnode is ignored.
+ /* Assemble all of the pointers in our cluster, in this case that
+ * represents all of the pointers out of our allocated nodes that
+ * point to existing tnodes and the links between our allocated
+ * nodes.
*/
- for (i = 0, m = 1u << tn->pos; i < olen; i++) {
- struct tnode *inode = tnode_get_child(oldtnode, i);
-
- if (tnode_full(oldtnode, inode) && (inode->bits > 1)) {
- struct tnode *left, *right;
-
- left = tnode_new(inode->key & ~m, inode->pos,
- inode->bits - 1);
- if (!left)
- goto nomem;
- tnode_free_append(tn, left);
-
- right = tnode_new(inode->key | m, inode->pos,
- inode->bits - 1);
-
- if (!right)
- goto nomem;
- tnode_free_append(tn, right);
-
- put_child(tn, 2*i, left);
- put_child(tn, 2*i+1, right);
- }
- }
-
- /* prepare oldtnode to be freed */
- tnode_free_init(oldtnode);
-
- for (i = 0; i < olen; i++) {
- struct tnode *inode = tnode_get_child(oldtnode, i);
- struct tnode *left, *right;
- unsigned long size, j;
+ for (i = tnode_child_length(oldtnode), m = 1u << tn->pos; i;) {
+ inode = tnode_get_child(oldtnode, --i);
/* An empty child */
if (inode == NULL)
@@ -496,65 +462,99 @@ static int inflate(struct trie *t, struct tnode *oldtnode)
continue;
}
- /* drop the node in the old tnode free list */
- tnode_free_append(oldtnode, inode);
-
/* An internal node with two children */
if (inode->bits == 1) {
- put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
- put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
+ put_child(tn, 2 * i + 1, tnode_get_child(inode, 1));
+ put_child(tn, 2 * i, tnode_get_child(inode, 0));
continue;
}
- /* An internal node with more than two children */
-
/* We will replace this node 'inode' with two new
- * ones, 'left' and 'right', each with half of the
+ * ones, 'node0' and 'node1', each with half of the
* original children. The two new nodes will have
* a position one bit further down the key and this
* means that the "significant" part of their keys
* (see the discussion near the top of this file)
* will differ by one bit, which will be "0" in
- * left's key and "1" in right's key. Since we are
+ * node0's key and "1" in node1's key. Since we are
* moving the key position by one step, the bit that
* we are moving away from - the bit at position
- * (inode->pos) - is the one that will differ between
- * left and right. So... we synthesize that bit in the
- * two new keys.
- * The mask 'm' below will be a single "one" bit at
- * the position (inode->pos)
+ * (tn->pos) - is the one that will differ between
+ * node0 and node1. So... we synthesize that bit in the
+ * two new keys.
*/
+ node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);
+ if (!node1)
+ goto nomem;
+ tnode_free_append(tn, node1);
+
+ node0 = tnode_new(inode->key & ~m, inode->pos, inode->bits - 1);
+ if (!node0)
+ goto nomem;
+ tnode_free_append(tn, node0);
+
+ /* populate child pointers in new nodes */
+ for (k = tnode_child_length(inode), j = k / 2; j;) {
+ put_child(node1, --j, tnode_get_child(inode, --k));
+ put_child(node0, j, tnode_get_child(inode, j));
+ put_child(node1, --j, tnode_get_child(inode, --k));
+ put_child(node0, j, tnode_get_child(inode, j));
+ }
- /* Use the old key, but set the new significant
- * bit to zero.
- */
+ /* link new nodes to parent */
+ NODE_INIT_PARENT(node1, tn);
+ NODE_INIT_PARENT(node0, tn);
+
+ /* link parent to nodes */
+ put_child(tn, 2 * i + 1, node1);
+ put_child(tn, 2 * i, node0);
+ }
- left = tnode_get_child(tn, 2*i);
- put_child(tn, 2*i, NULL);
+ /* setup the parent pointer into and out of this node */
+ tp = node_parent(oldtnode);
+ NODE_INIT_PARENT(tn, tp);
+ put_child_root(tp, t, tn->key, tn);
+
+ /* prepare oldtnode to be freed */
+ tnode_free_init(oldtnode);
- BUG_ON(!left);
+ /* update all child nodes parent pointers to route to us */
+ for (i = tnode_child_length(oldtnode); i;) {
+ inode = tnode_get_child(oldtnode, --i);
+
+ /* A leaf or an internal node with skipped bits */
+ if (!tnode_full(oldtnode, inode)) {
+ node_set_parent(inode, tn);
+ continue;
+ }
- right = tnode_get_child(tn, 2*i+1);
- put_child(tn, 2*i+1, NULL);
+ /* drop the node in the old tnode free list */
+ tnode_free_append(oldtnode, inode);
- BUG_ON(!right);
+ /* fetch new nodes */
+ node1 = tnode_get_child(tn, 2 * i + 1);
+ node0 = tnode_get_child(tn, 2 * i);
- size = tnode_child_length(left);
- for (j = 0; j < size; j++) {
- put_child(left, j, rtnl_dereference(inode->child[j]));
- put_child(right, j, rtnl_dereference(inode->child[j + size]));
+ /* bits == 1 then node0 and node1 represent inode's children */
+ if (inode->bits == 1) {
+ node_set_parent(node1, tn);
+ node_set_parent(node0, tn);
+ continue;
}
- put_child(tn, 2 * i, left);
- put_child(tn, 2 * i + 1, right);
+ /* update parent pointers in child node's children */
+ for (k = tnode_child_length(inode), j = k / 2; j;) {
+ node_set_parent(tnode_get_child(inode, --k), node1);
+ node_set_parent(tnode_get_child(inode, --j), node0);
+ node_set_parent(tnode_get_child(inode, --k), node1);
+ node_set_parent(tnode_get_child(inode, --j), node0);
+ }
/* resize child nodes */
- resize(t, left);
- resize(t, right);
+ resize(t, node1);
+ resize(t, node0);
}
- put_child_root(tp, t, tn->key, tn);
-
/* we completed without error, prepare to free old node */
tnode_free(oldtnode);
return 0;
@@ -566,10 +566,8 @@ nomem:
static int halve(struct trie *t, struct tnode *oldtnode)
{
- unsigned long olen = tnode_child_length(oldtnode);
- struct tnode *tp = node_parent(oldtnode);
- struct tnode *tn, *left, *right;
- int i;
+ struct tnode *tn, *tp, *inode, *node0, *node1;
+ unsigned long i;
pr_debug("In halve\n");
@@ -577,68 +575,64 @@ static int halve(struct trie *t, struct tnode *oldtnode)
if (!tn)
return -ENOMEM;
- /*
- * Preallocate and store tnodes before the actual work so we
- * don't get into an inconsistent state if memory allocation
- * fails. In case of failure we return the oldnode and halve
- * of tnode is ignored.
+ /* Assemble all of the pointers in our cluster, in this case that
+ * represents all of the pointers out of our allocated nodes that
+ * point to existing tnodes and the links between our allocated
+ * nodes.
*/
+ for (i = tnode_child_length(oldtnode); i;) {
+ node1 = tnode_get_child(oldtnode, --i);
+ node0 = tnode_get_child(oldtnode, --i);
- for (i = 0; i < olen; i += 2) {
- left = tnode_get_child(oldtnode, i);
- right = tnode_get_child(oldtnode, i+1);
+ /* At least one of the children is empty */
+ if (!node1 || !node0) {
+ put_child(tn, i / 2, node1 ? : node0);
+ continue;
+ }
/* Two nonempty children */
- if (left && right) {
- struct tnode *newn;
-
- newn = tnode_new(left->key, oldtnode->pos, 1);
- if (!newn) {
- tnode_free(tn);
- return -ENOMEM;
- }
- tnode_free_append(tn, newn);
-
- put_child(tn, i/2, newn);
+ inode = tnode_new(node0->key, oldtnode->pos, 1);
+ if (!inode) {
+ tnode_free(tn);
+ return -ENOMEM;
}
+ tnode_free_append(tn, inode);
+ /* initialize pointers out of node */
+ put_child(inode, 1, node1);
+ put_child(inode, 0, node0);
+ NODE_INIT_PARENT(inode, tn);
+
+ /* link parent to node */
+ put_child(tn, i / 2, inode);
}
+ /* setup the parent pointer out of and back into this node */
+ tp = node_parent(oldtnode);
+ NODE_INIT_PARENT(tn, tp);
+ put_child_root(tp, t, tn->key, tn);
+
/* prepare oldtnode to be freed */
tnode_free_init(oldtnode);
- for (i = 0; i < olen; i += 2) {
- struct tnode *newBinNode;
-
- left = tnode_get_child(oldtnode, i);
- right = tnode_get_child(oldtnode, i+1);
-
- /* At least one of the children is empty */
- if (left == NULL) {
- if (right == NULL) /* Both are empty */
- continue;
- put_child(tn, i/2, right);
- continue;
- }
+ /* update all of the child parent pointers */
+ for (i = tnode_child_length(tn); i;) {
+ inode = tnode_get_child(tn, --i);
- if (right == NULL) {
- put_child(tn, i/2, left);
+ /* only new tnodes will be considered "full" nodes */
+ if (!tnode_full(tn, inode)) {
+ node_set_parent(inode, tn);
continue;
}
/* Two nonempty children */
- newBinNode = tnode_get_child(tn, i/2);
- put_child(newBinNode, 0, left);
- put_child(newBinNode, 1, right);
-
- put_child(tn, i / 2, newBinNode);
+ node_set_parent(tnode_get_child(inode, 1), inode);
+ node_set_parent(tnode_get_child(inode, 0), inode);
/* resize child node */
- resize(t, newBinNode);
+ resize(t, inode);
}
- put_child_root(tp, t, tn->key, tn);
-
/* all pointers should be clean so we are done */
tnode_free(oldtnode);
^ permalink raw reply related
* [RFC PATCH 16/17] fib_trie: Remove checks for index >= tnode_child_length from tnode_get_child
From: Alexander Duyck @ 2014-12-22 17:42 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
For some reason the compiler doesn't seem to understand that when we are in
a loop that runs from tnode_child_length - 1 to 0 we don't expect the value
of tn->bits to change. As such every call to tnode_get_child was rerunning
tnode_chile_length which ended up consuming quite a bit of space in the
resultant assembly code.
I have gone though and verified that in all cases where tnode_get_child
is used we are either winding though a fixed loop from tnode_child_length -
1 to 0, or are in a fastpath case where we are verifying the value by
either checking for any remaining bits after shifting index by bits and
testing for leaf, or by using tnode_child_length.
size net/ipv4/fib_trie.o
Before:
text data bss dec hex filename
15506 376 8 15890 3e12 net/ipv4/fib_trie.o
After:
text data bss dec hex filename
14827 376 8 15211 3b6b net/ipv4/fib_trie.o
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 14 +++++---------
1 file changed, 5 insertions(+), 9 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 1a0f9c5..b6298ed 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -186,8 +186,6 @@ static inline unsigned long tnode_child_length(const struct tnode *tn)
static inline struct tnode *tnode_get_child(const struct tnode *tn,
unsigned long i)
{
- BUG_ON(i >= tnode_child_length(tn));
-
return rtnl_dereference(tn->child[i]);
}
@@ -195,8 +193,6 @@ static inline struct tnode *tnode_get_child(const struct tnode *tn,
static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn,
unsigned long i)
{
- BUG_ON(i >= tnode_child_length(tn));
-
return rcu_dereference_rtnl(tn->child[i]);
}
@@ -371,7 +367,7 @@ static inline int tnode_full(const struct tnode *tn, const struct tnode *n)
*/
static void put_child(struct tnode *tn, unsigned long i, struct tnode *n)
{
- struct tnode *chi = rtnl_dereference(tn->child[i]);
+ struct tnode *chi = tnode_get_child(tn, i);
int isfull, wasfull;
BUG_ON(i >= tnode_child_length(tn));
@@ -867,7 +863,7 @@ static struct tnode *fib_find_node(struct trie *t, u32 key)
if (IS_LEAF(n))
break;
- n = rcu_dereference_rtnl(n->child[index]);
+ n = tnode_get_child_rcu(n, index);
}
return n;
@@ -934,7 +930,7 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
}
tp = n;
- n = rcu_dereference_rtnl(n->child[index]);
+ n = tnode_get_child_rcu(n, index);
}
l = leaf_new(key);
@@ -1210,7 +1206,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
pn = n;
cindex = index;
- n = rcu_dereference_rtnl(n->child[index]);
+ n = tnode_get_child_rcu(n, index);
if (unlikely(!n))
goto backtrace;
}
@@ -1829,7 +1825,7 @@ static void trie_collect_stats(struct trie *t, struct trie_stat *s)
if (n->bits < MAX_STAT_DEPTH)
s->nodesizes[n->bits]++;
- for (i = 0; i < tnode_child_length(n); i++) {
+ for (i = tnode_child_length(n); i--;) {
if (!rcu_access_pointer(n->child[i]))
s->nullpointers++;
}
^ permalink raw reply related
* [RFC PATCH 17/17] fib_trie: Add tracking value for suffix length
From: Alexander Duyck @ 2014-12-22 17:42 UTC (permalink / raw)
To: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
This change adds a tracking value for the maximum suffix length of all
prefixes stored in any given tnode. With this value we can determine if we
need to backtrace or not based on if the suffix is greater than the pos
value.
By doing this we can reduce the CPU overhead for lookups in the local table
as many of the prefixes there are 32b long and have a suffix length of 0
meaning we can immediately backtrace to the root node without needing to
test any of the nodes between it and where we ended up.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
---
net/ipv4/fib_trie.c | 129 ++++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 122 insertions(+), 7 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index b6298ed..d366dcc 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -96,6 +96,7 @@ struct tnode {
t_key key;
unsigned char bits; /* 2log(KEYLENGTH) bits needed */
unsigned char pos; /* 2log(KEYLENGTH) bits needed */
+ unsigned char slen;
struct tnode __rcu *parent;
struct rcu_head rcu;
union {
@@ -311,6 +312,7 @@ static struct tnode *leaf_new(t_key key)
* as the nodes are searched
*/
l->key = key;
+ l->slen = 0;
l->pos = 0;
/* set bits to 0 indicating we are not a tnode */
l->bits = 0;
@@ -342,6 +344,7 @@ static struct tnode *tnode_new(t_key key, int pos, int bits)
if (tn) {
tn->parent = NULL;
+ tn->slen = pos;
tn->pos = pos;
tn->bits = bits;
tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
@@ -387,6 +390,9 @@ static void put_child(struct tnode *tn, unsigned long i, struct tnode *n)
else if (!wasfull && isfull)
tn->full_children++;
+ if (n && (tn->slen < n->slen))
+ tn->slen = n->slen;
+
rcu_assign_pointer(tn->child[i], n);
}
@@ -635,6 +641,41 @@ static int halve(struct trie *t, struct tnode *oldtnode)
return 0;
}
+static unsigned char update_suffix(struct tnode *tn)
+{
+ unsigned char slen = tn->pos;
+ unsigned long stride, i;
+
+ /* search though the list of children looking for nodes that might
+ * have a suffix greater than the one we currently have. This is
+ * why we start with a stride of 2 since a stride of 1 would
+ * represent the nodes with suffix length equal to tn->pos
+ */
+ for (i = 0, stride = 0x2ul ; i < tnode_child_length(tn); i += stride) {
+ struct tnode *n = tnode_get_child(tn, i);
+
+ if (!n || (n->slen <= slen))
+ continue;
+
+ /* update stride and slen based on new value */
+ stride <<= (n->slen - slen);
+ slen = n->slen;
+ i &= ~(stride - 1);
+
+ /* if slen covers all but the last bit we can stop here
+ * there will be nothing longer than that since only node
+ * 0 and 1 << (bits - 1) could have that as their suffix
+ * length.
+ */
+ if ((slen + 1) >= (tn->pos + tn->bits))
+ break;
+ }
+
+ tn->slen = slen;
+
+ return slen;
+}
+
/* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
* the Helsinki University of Technology and Matti Tikkanen of Nokia
* Telecommunications, page 6:
@@ -790,6 +831,19 @@ no_children:
/* drop dead node */
tnode_free_init(tn);
tnode_free(tn);
+ return;
+ }
+
+ /* Return if at least one deflate was run */
+ if (max_work != MAX_WORK)
+ return;
+
+ /* push the suffix length to the parent node */
+ if (tn->slen > tn->pos) {
+ unsigned char slen = update_suffix(tn);
+
+ if (tp && (slen > tp->slen))
+ tp->slen = slen;
}
}
@@ -818,8 +872,58 @@ static inline struct list_head *get_fa_head(struct tnode *l, int plen)
return &li->falh;
}
-static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
+static void leaf_pull_suffix(struct tnode *l)
+{
+ struct tnode *tp = node_parent(l);
+
+ while (tp && (tp->slen > tp->pos) && (tp->slen > l->slen)) {
+ if (update_suffix(tp) > l->slen)
+ break;
+ tp = node_parent(tp);
+ }
+}
+
+static void leaf_push_suffix(struct tnode *l)
+{
+ struct tnode *tn = node_parent(l);
+
+ /* if this is a new leaf then tn will be NULL and we can sort
+ * out parent suffix lengths as a part of trie_rebalance
+ */
+ while (tn && (tn->slen < l->slen)) {
+ tn->slen = l->slen;
+ tn = node_parent(tn);
+ }
+}
+
+static void remove_leaf_info(struct tnode *l, struct leaf_info *old)
+{
+ struct hlist_node *prev;
+
+ /* record the location of the pointer to this object */
+ prev = rtnl_dereference(hlist_pprev_rcu(&old->hlist));
+
+ /* remove the leaf info from the list */
+ hlist_del_rcu(&old->hlist);
+
+ /* if we emptied the list this leaf will be freed and we can sort
+ * out parent suffix lengths as a part of trie_rebalance
+ */
+ if (hlist_empty(&l->list))
+ return;
+
+ /* if we removed the tail then we need to update slen */
+ if (!rcu_access_pointer(hlist_next_rcu(prev))) {
+ struct leaf_info *li = hlist_entry(prev, typeof(*li), hlist);
+
+ l->slen = KEYLENGTH - li->plen;
+ leaf_pull_suffix(l);
+ }
+}
+
+static void insert_leaf_info(struct tnode *l, struct leaf_info *new)
{
+ struct hlist_head *head = &l->list;
struct leaf_info *li = NULL, *last = NULL;
if (hlist_empty(head)) {
@@ -836,6 +940,12 @@ static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
else
hlist_add_before_rcu(&new->hlist, &li->hlist);
}
+
+ /* if we added to the tail node then we need to update slen */
+ if (!rcu_access_pointer(hlist_next_rcu(&new->hlist))) {
+ l->slen = KEYLENGTH - new->plen;
+ leaf_push_suffix(l);
+ }
}
/* rcu_read_lock needs to be hold by caller from readside */
@@ -925,7 +1035,7 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
/* we have found a leaf. Prefixes have already been compared */
if (IS_LEAF(n)) {
/* Case 1: n is a leaf, and prefixes match*/
- insert_leaf_info(&n->list, li);
+ insert_leaf_info(n, li);
return fa_head;
}
@@ -939,7 +1049,7 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
return NULL;
}
- insert_leaf_info(&l->list, li);
+ insert_leaf_info(l, li);
/* Case 2: n is a LEAF or a TNODE and the key doesn't match.
*
@@ -1203,8 +1313,13 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
if (IS_LEAF(n))
goto found;
- pn = n;
- cindex = index;
+ /* only record pn and cindex if we are going to be chopping
+ * bits later. Otherwise we are just wasting cycles.
+ */
+ if (n->slen > n->pos) {
+ pn = n;
+ cindex = index;
+ }
n = tnode_get_child_rcu(n, index);
if (unlikely(!n))
@@ -1220,7 +1335,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp,
* between the key and the prefix exist in the region of
* the lsb and higher in the prefix.
*/
- if (unlikely(prefix_mismatch(key, n)))
+ if (unlikely(prefix_mismatch(key, n)) || (n->slen == n->pos))
goto backtrace;
/* exit out and process leaf */
@@ -1419,7 +1534,7 @@ int fib_table_delete(struct fib_table *tb, struct fib_config *cfg)
tb->tb_num_default--;
if (list_empty(fa_head)) {
- hlist_del_rcu(&li->hlist);
+ remove_leaf_info(l, li);
free_leaf_info(li);
}
^ permalink raw reply related
* Re: [BUG] rtl8192se: panic accessing unmapped memory in skb
From: Larry Finger @ 2014-12-22 17:43 UTC (permalink / raw)
To: Eric Biggers; +Cc: linux-wireless, netdev, linux-kernel
In-Reply-To: <20141221234714.GA30675@zzz>
On 12/21/2014 05:47 PM, Eric Biggers wrote:
> Hi,
>
> To get your patched version to work at all I had to update
> _rtl_pci_init_rx_ring() to account for new return value of
> _rtl_pci_init_one_rxdesc(). I will let you know if anything shows up in the
> kernel log, but I expect this is a highly sporadic problem. The system has 4 GB
> of memory, and I used the 3.18 kernel for 10 days prior to the panic with no
> issues. The panic occurred while upgrading system packages, so it's possible
> jhat the system was experiencing memory pressure.
>
> I upgraded from 3.17 to 3.18 on Dec 8, so I've actually only had since then to
> notice any bugs that may have been introduced since 3.17.
>
> It does appear there were changes made to pci.c between 3.17 and 3.18. It
> appears the 3.17 code will drop the incoming packet if a new skb can't be
> allocated, whereas the 3.18 code assumes a new skb can always be allocated. The
> 3.17 behavior seems more logical to me. I don't know how either of these
> behaviors compare to other networking drivers, however.
Sorry about missing the necessary changes in the rest of the driver. That is
what I get for only compile testing.
I reviewed the 3.17 => 3.18 changes and found the difference in the logic that
you noticed, and I missed earlier. As a result, I need to push this change for
3.19 with the notation for updating of 3.18. You have probably received this
patch already. As it needs to be backported, I decided to forgo changing the
return value of _rtl_pci_init_one_rxdesc(). That change should be made, but
there is no emergency there.
Thanks,
Larry
^ permalink raw reply
* [PATCH 0/5] netlink/genetlink cleanups & multicast improvements
From: Johannes Berg @ 2014-12-22 17:56 UTC (permalink / raw)
To: netdev
I'm looking at using the multicast group functionality in a way that would
benefit from knowing when there are subscribers to avoid collecting the
required data when there aren't any. During this I noticed that the unbind
for multicast groups doesn't actually work - it's never called when sockets
are closed. Luckily, nobody actually uses the functionality.
While looking at the code trying to find why it's not called and where the
multicast listeners are actually removed, I found the potential cleanup in
patch 3. Patch 2 also has a cleanup for a generic netlink API in this area.
johannes
^ permalink raw reply
* [PATCH 1/5] netlink: rename netlink_unbind() to netlink_undo_bind()
From: Johannes Berg @ 2014-12-22 17:56 UTC (permalink / raw)
To: netdev; +Cc: Johannes Berg
In-Reply-To: <1419270999-22165-1-git-send-email-johannes@sipsolutions.net>
From: Johannes Berg <johannes.berg@intel.com>
The new name is more expressive - this isn't a generic unbind
function but rather only a little undo helper for use only in
netlink_bind().
Signed-off-by: Johannes Berg <johannes.berg@intel.com>
---
net/netlink/af_netlink.c | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/net/netlink/af_netlink.c b/net/netlink/af_netlink.c
index ef5f77b44ec7..1117a2cc7c28 100644
--- a/net/netlink/af_netlink.c
+++ b/net/netlink/af_netlink.c
@@ -1430,8 +1430,8 @@ static int netlink_realloc_groups(struct sock *sk)
return err;
}
-static void netlink_unbind(int group, long unsigned int groups,
- struct netlink_sock *nlk)
+static void netlink_undo_bind(int group, long unsigned int groups,
+ struct netlink_sock *nlk)
{
int undo;
@@ -1481,7 +1481,7 @@ static int netlink_bind(struct socket *sock, struct sockaddr *addr,
err = nlk->netlink_bind(group);
if (!err)
continue;
- netlink_unbind(group, groups, nlk);
+ netlink_undo_bind(group, groups, nlk);
return err;
}
}
@@ -1491,7 +1491,7 @@ static int netlink_bind(struct socket *sock, struct sockaddr *addr,
netlink_insert(sk, net, nladdr->nl_pid) :
netlink_autobind(sock);
if (err) {
- netlink_unbind(nlk->ngroups, groups, nlk);
+ netlink_undo_bind(nlk->ngroups, groups, nlk);
return err;
}
}
--
2.1.1
^ permalink raw reply related
* [PATCH 4/5] netlink: call unbind when releasing socket
From: Johannes Berg @ 2014-12-22 17:56 UTC (permalink / raw)
To: netdev; +Cc: Johannes Berg
In-Reply-To: <1419270999-22165-1-git-send-email-johannes@sipsolutions.net>
From: Johannes Berg <johannes.berg@intel.com>
Currently, netlink_unbind() is only called when the socket
explicitly unbinds, which limits its usefulness (luckily
there are no users of it yet anyway.)
Call netlink_unbind() also when a socket is released, so it
becomes possible to track listeners with this callback and
without also implementing a netlink notifier (and checking
netlink_has_listeners() in there.)
Signed-off-by: Johannes Berg <johannes.berg@intel.com>
---
net/netlink/af_netlink.c | 7 +++++++
1 file changed, 7 insertions(+)
diff --git a/net/netlink/af_netlink.c b/net/netlink/af_netlink.c
index df6086f69592..07a903de4439 100644
--- a/net/netlink/af_netlink.c
+++ b/net/netlink/af_netlink.c
@@ -1266,6 +1266,13 @@ static int netlink_release(struct socket *sock)
netlink_table_ungrab();
}
+ if (nlk->netlink_unbind) {
+ int i;
+
+ for (i = 0; i < nlk->ngroups; i++)
+ if (test_bit(i, nlk->groups))
+ nlk->netlink_unbind(i + 1);
+ }
kfree(nlk->groups);
nlk->groups = NULL;
--
2.1.1
^ permalink raw reply related
* [PATCH 2/5] genetlink: pass only network namespace to genl_has_listeners()
From: Johannes Berg @ 2014-12-22 17:56 UTC (permalink / raw)
To: netdev; +Cc: Johannes Berg
In-Reply-To: <1419270999-22165-1-git-send-email-johannes@sipsolutions.net>
From: Johannes Berg <johannes.berg@intel.com>
There's no point to force the caller to know about the internal
genl_sock to use inside struct net, just have them pass the network
namespace. This doesn't really change code generation since it's
an inline, but makes the caller less magic - there's never any
reason to pass another socket.
Signed-off-by: Johannes Berg <johannes.berg@intel.com>
---
include/net/genetlink.h | 4 ++--
net/openvswitch/datapath.c | 3 +--
2 files changed, 3 insertions(+), 4 deletions(-)
diff --git a/include/net/genetlink.h b/include/net/genetlink.h
index af10c2cf8a1d..38620da4aa7a 100644
--- a/include/net/genetlink.h
+++ b/include/net/genetlink.h
@@ -395,11 +395,11 @@ static inline int genl_set_err(struct genl_family *family, struct net *net,
}
static inline int genl_has_listeners(struct genl_family *family,
- struct sock *sk, unsigned int group)
+ struct net *net, unsigned int group)
{
if (WARN_ON_ONCE(group >= family->n_mcgrps))
return -EINVAL;
group = family->mcgrp_offset + group;
- return netlink_has_listeners(sk, group);
+ return netlink_has_listeners(net->genl_sock, group);
}
#endif /* __NET_GENERIC_NETLINK_H */
diff --git a/net/openvswitch/datapath.c b/net/openvswitch/datapath.c
index 332b5a031739..4e9a5f035cbc 100644
--- a/net/openvswitch/datapath.c
+++ b/net/openvswitch/datapath.c
@@ -83,8 +83,7 @@ static bool ovs_must_notify(struct genl_family *family, struct genl_info *info,
unsigned int group)
{
return info->nlhdr->nlmsg_flags & NLM_F_ECHO ||
- genl_has_listeners(family, genl_info_net(info)->genl_sock,
- group);
+ genl_has_listeners(family, genl_info_net(info), group);
}
static void ovs_notify(struct genl_family *family,
--
2.1.1
^ permalink raw reply related
* [PATCH 3/5] netlink: update listeners directly when removing socket
From: Johannes Berg @ 2014-12-22 17:56 UTC (permalink / raw)
To: netdev; +Cc: Johannes Berg
In-Reply-To: <1419270999-22165-1-git-send-email-johannes@sipsolutions.net>
From: Johannes Berg <johannes.berg@intel.com>
The code is now confusing to read - first in one function down
(netlink_remove) any group subscriptions are implicitly removed
by calling __sk_del_bind_node(), but the subscriber database is
only updated far later by calling netlink_update_listeners().
Move the latter call to just after removal from the list so it
is easier to follow the code.
This also enables moving the locking inside the kernel-socket
conditional, which improves the normal socket destruction path.
Signed-off-by: Johannes Berg <johannes.berg@intel.com>
---
net/netlink/af_netlink.c | 10 +++++-----
1 file changed, 5 insertions(+), 5 deletions(-)
diff --git a/net/netlink/af_netlink.c b/net/netlink/af_netlink.c
index 1117a2cc7c28..df6086f69592 100644
--- a/net/netlink/af_netlink.c
+++ b/net/netlink/af_netlink.c
@@ -1111,8 +1111,10 @@ static void netlink_remove(struct sock *sk)
mutex_unlock(&nl_sk_hash_lock);
netlink_table_grab();
- if (nlk_sk(sk)->subscriptions)
+ if (nlk_sk(sk)->subscriptions) {
__sk_del_bind_node(sk);
+ netlink_update_listeners(sk);
+ }
netlink_table_ungrab();
}
@@ -1246,8 +1248,8 @@ static int netlink_release(struct socket *sock)
module_put(nlk->module);
- netlink_table_grab();
if (netlink_is_kernel(sk)) {
+ netlink_table_grab();
BUG_ON(nl_table[sk->sk_protocol].registered == 0);
if (--nl_table[sk->sk_protocol].registered == 0) {
struct listeners *old;
@@ -1261,10 +1263,8 @@ static int netlink_release(struct socket *sock)
nl_table[sk->sk_protocol].flags = 0;
nl_table[sk->sk_protocol].registered = 0;
}
- } else if (nlk->subscriptions) {
- netlink_update_listeners(sk);
+ netlink_table_ungrab();
}
- netlink_table_ungrab();
kfree(nlk->groups);
nlk->groups = NULL;
--
2.1.1
^ permalink raw reply related
* [PATCH 5/5] genetlink: pass multicast bind/unbind to families
From: Johannes Berg @ 2014-12-22 17:56 UTC (permalink / raw)
To: netdev; +Cc: Johannes Berg
In-Reply-To: <1419270999-22165-1-git-send-email-johannes@sipsolutions.net>
From: Johannes Berg <johannes.berg@intel.com>
In order to make the newly fixed multicast bind/unbind
functionality in generic netlink, pass them down to the
appropriate family.
Signed-off-by: Johannes Berg <johannes.berg@intel.com>
---
include/net/genetlink.h | 5 +++++
net/netlink/genetlink.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 56 insertions(+)
diff --git a/include/net/genetlink.h b/include/net/genetlink.h
index 38620da4aa7a..3ed31e5a445b 100644
--- a/include/net/genetlink.h
+++ b/include/net/genetlink.h
@@ -31,6 +31,9 @@ struct genl_info;
* do additional, common, filtering and return an error
* @post_doit: called after an operation's doit callback, it may
* undo operations done by pre_doit, for example release locks
+ * @mcast_bind: a socket bound to the given multicast group (which
+ * is given as the offset into the groups array)
+ * @mcast_unbind: a socket was unbound from the given multicast group
* @attrbuf: buffer to store parsed attributes
* @family_list: family list
* @mcgrps: multicast groups used by this family (private)
@@ -53,6 +56,8 @@ struct genl_family {
void (*post_doit)(const struct genl_ops *ops,
struct sk_buff *skb,
struct genl_info *info);
+ int (*mcast_bind)(int group);
+ void (*mcast_unbind)(int group);
struct nlattr ** attrbuf; /* private */
const struct genl_ops * ops; /* private */
const struct genl_multicast_group *mcgrps; /* private */
diff --git a/net/netlink/genetlink.c b/net/netlink/genetlink.c
index 76393f2f4b22..960d3a41682a 100644
--- a/net/netlink/genetlink.c
+++ b/net/netlink/genetlink.c
@@ -983,11 +983,62 @@ static struct genl_multicast_group genl_ctrl_groups[] = {
{ .name = "notify", },
};
+static int genl_bind(int group)
+{
+ int i, err;
+ bool found = false;
+
+ down_read(&cb_lock);
+ for (i = 0; i < GENL_FAM_TAB_SIZE; i++) {
+ struct genl_family *f;
+
+ list_for_each_entry(f, genl_family_chain(i), family_list) {
+ if (group >= f->mcgrp_offset &&
+ group < f->mcgrp_offset + f->n_mcgrps) {
+ err = f->mcast_bind(group - f->mcgrp_offset);
+ found = true;
+ break;
+ }
+ }
+ }
+ up_read(&cb_lock);
+
+ if (WARN_ON(!found))
+ err = 0;
+
+ return err;
+}
+
+static void genl_unbind(int group)
+{
+ int i;
+ bool found = false;
+
+ down_read(&cb_lock);
+ for (i = 0; i < GENL_FAM_TAB_SIZE; i++) {
+ struct genl_family *f;
+
+ list_for_each_entry(f, genl_family_chain(i), family_list) {
+ if (group >= f->mcgrp_offset &&
+ group < f->mcgrp_offset + f->n_mcgrps) {
+ f->mcast_unbind(group - f->mcgrp_offset);
+ found = true;
+ break;
+ }
+ }
+ }
+ up_read(&cb_lock);
+
+ WARN_ON(!found);
+}
+
static int __net_init genl_pernet_init(struct net *net)
{
struct netlink_kernel_cfg cfg = {
.input = genl_rcv,
.flags = NL_CFG_F_NONROOT_RECV,
+ .bind = genl_bind,
+ .unbind = genl_unbind,
};
/* we'll bump the group number right afterwards */
--
2.1.1
^ permalink raw reply related
* Re: [RFC PATCH 00/17] fib_trie: Reduce time spent in fib_table_lookup by 35 to 75%
From: Dave Taht @ 2014-12-22 18:08 UTC (permalink / raw)
To: Alexander Duyck; +Cc: netdev@vger.kernel.org
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
impressive. I think. But I don't quite understand what you mean by a depth of 7?
What did your routing table actually look like?
For example, my ipv4 routing table looks like this at the moment.
What is depth? searching from /32, /31, /30, /29?
root@davedesk:~# ip route
default via 172.21.2.21 dev se00 proto babel onlink
10.1.10.0/24 via 172.21.2.21 dev se00 proto babel onlink
10.1.10.12 via 172.21.2.21 dev se00 proto babel onlink
50.197.142.144/29 via 172.21.0.1 dev ge00 proto babel onlink
73.15.8.0/23 via 172.21.0.1 dev ge00 proto babel onlink
172.20.1.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.2.0/27 via 172.21.0.1 dev ge00 proto babel onlink
172.20.2.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.2.7 via 172.21.0.1 dev ge00 proto babel onlink
172.20.4.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.5.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.6.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.6.1 via 172.21.0.1 dev ge00 proto babel onlink
172.20.7.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.8.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.20.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.47.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.47.1 via 172.21.0.1 dev ge00 proto babel onlink
172.20.92.64/27 via 172.21.0.1 dev ge00 proto babel onlink
172.20.92.96/27 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.2 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.3 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.4 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.5 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.6 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.7 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.9 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.10 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.11 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.16 via 172.21.0.1 dev ge00 proto babel onlink
172.20.142.45 via 172.21.0.1 dev ge00 proto babel onlink
172.20.143.4 via 172.21.0.1 dev ge00 proto babel onlink
172.20.143.6 via 172.21.0.1 dev ge00 proto babel onlink
172.20.143.7 via 172.21.0.1 dev ge00 proto babel onlink
172.20.143.20 via 172.21.0.1 dev ge00 proto babel onlink
172.20.222.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.20.223.0/24 via 172.21.0.1 dev ge00 proto babel onlink
172.21.0.0/24 dev ge00 proto kernel scope link src 172.21.0.2
172.21.0.1 via 172.21.0.1 dev ge00 proto babel onlink
172.21.2.0/27 dev se00 proto kernel scope link src 172.21.2.1
172.21.2.20 via 172.21.2.20 dev se00 proto babel onlink
172.21.2.21 via 172.21.2.21 dev se00 proto babel onlink
172.21.2.64/27 dev sw00 proto kernel scope link src 172.21.2.65
172.21.2.96/27 dev sw10 proto kernel scope link src 172.21.2.97
172.21.2.128/27 dev gw00 proto kernel scope link src 172.21.2.129
172.21.2.160/27 dev gw10 proto kernel scope link src 172.21.2.161
172.21.128.0/24 via 172.21.2.21 dev se00 proto babel onlink
172.21.128.0/20 via 172.21.2.21 dev se00 proto babel onlink
172.21.129.0/24 via 172.21.2.21 dev se00 proto babel onlink
172.23.2.0/23 via 172.21.0.1 dev ge00 proto babel onlink
172.23.6.0/23 via 172.21.0.1 dev ge00 proto babel onlink
172.23.143.3 via 172.21.0.1 dev ge00 proto babel onlink
172.23.143.7 via 172.21.0.1 dev ge00 proto babel onlink
192.168.7.2 via 172.21.0.1 dev ge00 proto babel onlink
Dave Täht
http://www.bufferbloat.net/projects/bloat/wiki/Upcoming_Talks
^ permalink raw reply
* Re: [PATCH] net: unisys: adding unisys virtnic driver
From: David Miller @ 2014-12-22 18:08 UTC (permalink / raw)
To: zyjzyj2000
Cc: earfvids, benjamin.romer, netdev, dzickus, Bruce.Vessey,
sparmaintainer, prarit
In-Reply-To: <5497D708.7070109@gmail.com>
From: zhuyj <zyjzyj2000@gmail.com>
Date: Mon, 22 Dec 2014 16:32:08 +0800
> Compared with veth, tun/tap, is there any difference about this
> virtnic?
First, please do not top-post.
Second, do not quote an entire huge patch just to make a 2-line
comment. Everyone now has to receive that huge patch again in
their inbox, so you are creating a huge burdon for everyone on
the list.
^ permalink raw reply
* [PATCH RFC] ipw2200: select CFG80211_WEXT
From: Paul Bolle @ 2014-12-22 18:10 UTC (permalink / raw)
To: Johannes Berg
Cc: Stanislav Yakovlev, Kalle Valo, linux-wireless, netdev,
linux-kernel
Commit 24a0aa212ee2 ("cfg80211: make WEXT compatibility unselectable")
made it impossible to depend on CFG80211_WEXT. It does still allow to
select that symbol. (Yes, the commit summary is confusing.)
So make IPW2200 select CFG80211_WEXT, so that the ipw2200 driver can be
built again.
Signed-off-by: Paul Bolle <pebolle@tiscali.nl>
---
Johannes,
Building v3.19-rc1 for an outdated ThinkPad X41 left me without the
ipw2200 driver. It turns out this trivial patch is all that's needed to
make ipw2200 buildable again.
(A similar patch would be needed for the drivers behind Kconfig symbol
HERMES. Ie, orinico and friends.)
I must admit that I do not fully understand your commit. (How was
CFG80211_WEXT "marked for deprecation and removal for a little more than
two years"?) There's some terminology confusion: what you call "select"
I tend to call "set". Anyhow, your commit basically disables building
ipw2200 (and apparently orinoco and friends)?
Was that your intention?
drivers/net/wireless/ipw2x00/Kconfig | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/drivers/net/wireless/ipw2x00/Kconfig b/drivers/net/wireless/ipw2x00/Kconfig
index 91c0cb3c368e..21de4fe6cf2d 100644
--- a/drivers/net/wireless/ipw2x00/Kconfig
+++ b/drivers/net/wireless/ipw2x00/Kconfig
@@ -65,7 +65,8 @@ config IPW2100_DEBUG
config IPW2200
tristate "Intel PRO/Wireless 2200BG and 2915ABG Network Connection"
- depends on PCI && CFG80211 && CFG80211_WEXT
+ depends on PCI && CFG80211
+ select CFG80211_WEXT
select WIRELESS_EXT
select WEXT_SPY
select WEXT_PRIV
--
2.1.0
^ permalink raw reply related
* Re: [PATCH iproute2] ip lib: Added shorter timestamp option
From: Stephen Hemminger @ 2014-12-22 18:12 UTC (permalink / raw)
To: Vadim Kochan; +Cc: netdev
In-Reply-To: <1418285526-28859-1-git-send-email-vadim4j@gmail.com>
On Thu, 11 Dec 2014 10:12:06 +0200
Vadim Kochan <vadim4j@gmail.com> wrote:
> From: Vadim Kochan <vadim4j@gmail.com>
>
> Added another timestamp format to look like more logging info:
>
> [Dec 01 01:46:20.675589] 2: enp0s25: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state UP group default
> link/ether 3c:97:0e:a3:86:2e brd ff:ff:ff:ff:ff:ff
>
> Signed-off-by: Vadim Kochan <vadim4j@gmail.com>
I would suggest supporting RFC3339 which is a standard for timestamps instead.
[2014-22-12T01:46:20.1012] ...
^ permalink raw reply
* Re: [RFC PATCH 05/17] fib_trie: Optimize fib_table_lookup to avoid wasting time on loops/variables
From: David Miller @ 2014-12-22 18:30 UTC (permalink / raw)
To: alexander.h.duyck; +Cc: netdev
In-Reply-To: <20141222174123.1119.28780.stgit@ahduyck-vm-fedora20>
From: Alexander Duyck <alexander.h.duyck@redhat.com>
Date: Mon, 22 Dec 2014 09:41:24 -0800
> This patch is meant to reduce the complexity of fib_table_lookup by reducing
> the number of variables to the bare minimum while still keeping the same if
> not improved functionality versus the original.
>
> Most of this change was started off by the desire to rid the function of
> chopped_off and current_prefix_length as they actually added very little to
> the function since they only applied when computing the cindex. I was able
> to replace them mostly with just a check for the prefix match. As long as
> the prefix between the key and the node being tested was the same we know
> we can search the tnode fully versus just testing cindex 0.
>
> The second portion of the change ended up being a massive reordering.
> Originally the calls to check_leaf were up near the start of the loop, and
> the backtracing and descending into lower levels of tnodes was later. This
> didn't make much sense as the structure of the tree means the leaves are
> always the last thing to be tested. As such I reordered things so that we
> instead have a loop that will delve into the tree and only exit when we
> have either found a leaf or we have exhausted the tree. The advantage of
> rearranging things like this is that we can fully inline check_leaf since
> there is now only one reference to it in the function.
>
> Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
I really like this change, in particular that you got rid of the
__fls().
That's unfortunately expensive on older sparcs, so when I was
micro-benchmarking the routing cache changes it would show up in
perf.
^ permalink raw reply
* Re: [RFC PATCH 17/17] fib_trie: Add tracking value for suffix length
From: David Miller @ 2014-12-22 18:32 UTC (permalink / raw)
To: alexander.h.duyck; +Cc: netdev
In-Reply-To: <20141222174238.1119.68562.stgit@ahduyck-vm-fedora20>
From: Alexander Duyck <alexander.h.duyck@redhat.com>
Date: Mon, 22 Dec 2014 09:42:38 -0800
> This change adds a tracking value for the maximum suffix length of all
> prefixes stored in any given tnode. With this value we can determine if we
> need to backtrace or not based on if the suffix is greater than the pos
> value.
>
> By doing this we can reduce the CPU overhead for lookups in the local table
> as many of the prefixes there are 32b long and have a suffix length of 0
> meaning we can immediately backtrace to the root node without needing to
> test any of the nodes between it and where we ended up.
>
> Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
This is a really nice optimization.
^ permalink raw reply
* Re: [RFC PATCH 02/17] fib_trie: Make leaf and tnode more uniform
From: David Miller @ 2014-12-22 18:33 UTC (permalink / raw)
To: alexander.h.duyck; +Cc: netdev
In-Reply-To: <20141222174105.1119.71598.stgit@ahduyck-vm-fedora20>
From: Alexander Duyck <alexander.h.duyck@redhat.com>
Date: Mon, 22 Dec 2014 09:41:05 -0800
> -#define IS_TNODE(n) (!(n->parent & T_LEAF))
> -#define IS_LEAF(n) (n->parent & T_LEAF)
> +struct tnode {
> + t_key key;
> + unsigned char bits; /* 2log(KEYLENGTH) bits needed */
> + unsigned char pos; /* 2log(KEYLENGTH) bits needed */
> + struct tnode __rcu *parent;
> + union {
> + struct rcu_head rcu;
> + struct tnode *tnode_free;
> + };
> + unsigned int full_children; /* KEYLENGTH bits needed */
> + unsigned int empty_children; /* KEYLENGTH bits needed */
> + struct rt_trie_node __rcu *child[0];
> +};
I wonder if we can compress this even further.
The full_children and empty_children can probably both be a u16, right?
If so, you can stick at least one of them after 'bits' and 'pos' and
thus save 4 bytes on 32b.
^ permalink raw reply
* Re: [RFC PATCH 00/17] fib_trie: Reduce time spent in fib_table_lookup by 35 to 75%
From: David Miller @ 2014-12-22 18:35 UTC (permalink / raw)
To: alexander.h.duyck; +Cc: netdev
In-Reply-To: <20141222172632.1119.51469.stgit@ahduyck-vm-fedora20>
From: Alexander Duyck <alexander.h.duyck@redhat.com>
Date: Mon, 22 Dec 2014 09:40:52 -0800
> These patches are meant to address several performance issues I have seen
> in the fib_trie implementation, and fib_table_lookup specifically. With
> these changes in place I have seen a reduction of up to 35 to 75% for the
> total time spent in fib_table_lookup depending on the type of search being
> performed.
Fantastic work Alexander.
I had a patch series, just for micro-benchmarking, that got rid of the
local table and just put everything in the global one.
Everything works and we always only do one probe into the FIB.
That speeds things up a lot.
The only problem is that we have to take into consideration cases
where userspace tries to directly modify and do things to the local
table. Also we might have to pretend we have a local table in
dumps too.
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox