Re: [PATCH] Clean up fib_hash datastructures

[jamal <hadi@cyberus.ca>]

On Mon, 2004-09-20 at 15:11, David S. Miller wrote:
> On 20 Sep 2004 09:24:32 -0400
> jamal <hadi@cyberus.ca> wrote:
> 
> > On Sun, 2004-09-19 at 22:53, David S. Miller wrote:

Sorry missed this (that what happens with reading email backwards).

> Furthermore, once you have 1000 devices the algorithms in
> net/ipv4/fib_semantics.c fall apart.

Yikes - I just looked.
fib_sync_down and up are horrible. I think its at least 0(n^2). Yes, I
can see what would happen when you suddenly bring down 1000 devices.

> The code in fib_semantics.c was written assuming that next
> hop information composed of a small set of unique entries.
> So even if your routing tables were huge, those routing
> entries pointed to a small group of unique next-hop objects
> (which is what fib_info represents).
> 

yep - i see it.

> So all of that code was using a singly linked list of all
> fib_info's to do lookups.  Therefore once you have a couple
> thousand entries, even the simplest event processing becomes
> expensive.

Good cleanup in -bk7 with the hashes.

> > I like the idea except for when enforcing that scheme to be used
> > by other algorithms[1]. 
> 
> It is the core issue.
> 
> I read from this statement that it is envisioned that some
> fib_node lookup algorithm could, in a different way, find
> all fib_nodes corresponding to a given fib_info.  I ask you
> to provide what that mechanism might be before I am willing
> to be concerned about this possibility :-)

The way i see it is any new alg will have a fib_info at the end of its
lookup but not fib_node. fib_semantics only cares about fib_info.
Hence my comment above (my worry being you are breaking this
relationship - in particular now that you are thrwoing out TOS)

BTW, dont see the code in -bk7.

> Jamal and others, while I have your brains active in this area
> I have a question.
> 
> I tried very hard to preserve existing behavior wrt. TOS
> handling wrt. the setting of CONFIG_IP_ROUTE_TOS.  Basically,
> the r->rtm_tos is ignored when adding routes, and treated as
> zero.
> 
> I believe I was successful in preserving existing behavior, but
> I wonder if it makes sense any longer.  CONFIG_IP_ROUTE_TOS
> changes not one data structure.  It does exactly:
> 
> 1) Controls the presence of a TOS comparison in
>    fib_rules.c:fib_lookup()
> 
> 2) Controls, in fib_hash.c:
> 	a) TOS comparison in fn_hash_lookup()
> 	b) whether TOS is paid attention to in fn_hash_insert
> 	c) similarly in fn_hash_delete()
> 
> In the TOS comparison changes, the TOS test treats zero
> TOS values as "any TOS".  Therefore unless the user explicitly
> tried to add a non-zero TOS route, TOS makes no difference
> in behavior both with and without CONFIG_IP_ROUTE_TOS set.
> 
> Therefore, I think it behooves us just kill off this config
> value.  It saves a mere 6 or 7 lines of code and no data
> space.

Still need comment on this after killing TOS?

cheers,
jamal