Does the ordering of the fib_table_dump or /proc/net/fib_trie matter?

Does the ordering of the fib_table_dump or /proc/net/fib_trie matter?

[Alexander Duyck]

I am considering reversing the order of any non-lookup traversal of the
fib_trie so that it starts at the last node and works it's way up toward
the first node.  This would make it so that all walks using the parent
pointer all go in the same direction.

The problem right now is that leaf_walk_rcu and a couple of other
iterators traverse the trie in one direction grabbing the next child
(child++) of the parent, while fib_table_lookup is traversing the list
grabbing a previous child (child & (child - 1)) of the parent.  It makes
things a bit ugly for RCU as we have to have the node fully populated
before we can start updating the parent pointers on the children.

I want to have them both moving in the same direction so the
fib_table_lookup would remain the same, but the leaf_walk_rcu and others
would walk from the last child to the first (child--) and as a result
when I assemble a tnode in inflate or halve I would be able to populate
children from 0 to ((1 << tn->bits) - 1) without having to worry about
any iterators walking into uninitialized memory.

The question I have is if that would screw up any user-space apps.  I
know ip route can dump the list via "ip route show".  I'm just wondering
if there would be any problem with default being the last entry instead
of the first entry?

- Alex

Re: Does the ordering of the fib_table_dump or /proc/net/fib_trie matter?

[David Miller]

From: Alexander Duyck <alexander.duyck@gmail.com>
Date: Tue, 06 Jan 2015 12:30:06 -0800

> The question I have is if that would screw up any user-space apps.  I
> know ip route can dump the list via "ip route show".  I'm just wondering
> if there would be any problem with default being the last entry instead
> of the first entry?

The ordering already changed once when we went from fib_hash to
fib_trie, nobody should depend upon the ordering.

Re: Does the ordering of the fib_table_dump or /proc/net/fib_trie matter?

[Alexander Duyck]

On 01/06/2015 01:58 PM, David Miller wrote:
> From: Alexander Duyck <alexander.duyck@gmail.com>
> Date: Tue, 06 Jan 2015 12:30:06 -0800
>
>> The question I have is if that would screw up any user-space apps.  I
>> know ip route can dump the list via "ip route show".  I'm just wondering
>> if there would be any problem with default being the last entry instead
>> of the first entry?
> The ordering already changed once when we went from fib_hash to
> fib_trie, nobody should depend upon the ordering.

Okay good to hear.  I kind of thought that was the case, but I wanted to
make sure before I went too far down this rabbit hole.

Thanks.

- Alex