[PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Julian Anastasov]

	fib_info can be shared by many route prefixes but we don't
want duplicate alternative routes for a prefix+tos+priority. Last
change was not correct to check fib_treeref because it accounts usage
from other prefixes. Additionally, avoid replacement without error
if new route is same, as Joonwoo Park suggests.

Signed-off-by: Julian Anastasov <ja@ssi.bg>
---

--- linux-2.6.24/net/ipv4/fib_hash.c_orig	2008-01-25 10:45:06.000000000 +0200
+++ linux-2.6.24/net/ipv4/fib_hash.c	2008-01-26 14:11:34.000000000 +0200
@@ -434,19 +434,43 @@ static int fn_hash_insert(struct fib_tab
 
 	if (fa && fa->fa_tos == tos &&
 	    fa->fa_info->fib_priority == fi->fib_priority) {
-		struct fib_alias *fa_orig;
+		struct fib_alias *fa_first, *fa_match;
 
 		err = -EEXIST;
 		if (cfg->fc_nlflags & NLM_F_EXCL)
 			goto out;
 
+		/* We have 2 goals:
+		 * 1. Find exact match for type, scope, fib_info to avoid
+		 * duplicate routes
+		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
+		 */
+		fa_match = NULL;
+		fa_first = fa;
+		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
+		list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
+			if (fa->fa_tos != tos)
+				break;
+			if (fa->fa_info->fib_priority != fi->fib_priority)
+				break;
+			if (fa->fa_type == cfg->fc_type &&
+			    fa->fa_scope == cfg->fc_scope &&
+			    fa->fa_info == fi) {
+				fa_match = fa;
+				break;
+			}
+		}
+
 		if (cfg->fc_nlflags & NLM_F_REPLACE) {
 			struct fib_info *fi_drop;
 			u8 state;
 
-			if (fi->fib_treeref > 1)
+			fa = fa_first;
+			if (fa_match) {
+				if (fa == fa_match)
+					err = 0;
 				goto out;
-
+			}
 			write_lock_bh(&fib_hash_lock);
 			fi_drop = fa->fa_info;
 			fa->fa_info = fi;
@@ -469,20 +493,11 @@ static int fn_hash_insert(struct fib_tab
 		 * uses the same scope, type, and nexthop
 		 * information.
 		 */
-		fa_orig = fa;
-		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
-		list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
-			if (fa->fa_tos != tos)
-				break;
-			if (fa->fa_info->fib_priority != fi->fib_priority)
-				break;
-			if (fa->fa_type == cfg->fc_type &&
-			    fa->fa_scope == cfg->fc_scope &&
-			    fa->fa_info == fi)
-				goto out;
-		}
+		if (fa_match)
+			goto out;
+
 		if (!(cfg->fc_nlflags & NLM_F_APPEND))
-			fa = fa_orig;
+			fa = fa_first;
 	}
 
 	err = -ENOENT;

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Jarek Poplawski]

Hi, I have a few questions below:

Julian Anastasov wrote, On 01/26/2008 01:41 PM:

> 	fib_info can be shared by many route prefixes but we don't
> want duplicate alternative routes for a prefix+tos+priority. Last
> change was not correct to check fib_treeref because it accounts usage
> from other prefixes. Additionally, avoid replacement without error
> if new route is same, as Joonwoo Park suggests.
> 
> Signed-off-by: Julian Anastasov <ja@ssi.bg>
> ---
> 
> --- linux-2.6.24/net/ipv4/fib_hash.c_orig	2008-01-25 10:45:06.000000000 +0200
> +++ linux-2.6.24/net/ipv4/fib_hash.c	2008-01-26 14:11:34.000000000 +0200
> @@ -434,19 +434,43 @@ static int fn_hash_insert(struct fib_tab
>  
>  	if (fa && fa->fa_tos == tos &&
>  	    fa->fa_info->fib_priority == fi->fib_priority) {
> -		struct fib_alias *fa_orig;
> +		struct fib_alias *fa_first, *fa_match;
>  
>  		err = -EEXIST;
>  		if (cfg->fc_nlflags & NLM_F_EXCL)
>  			goto out;

BTW, the way "add" works wasn't questioned now, but it seems could be,
or man ip should call it e.g. "ip route add - add new destination",
and append "ip route append" (unless I have old man).

>  
> +		/* We have 2 goals:
> +		 * 1. Find exact match for type, scope, fib_info to avoid
> +		 * duplicate routes
> +		 * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
> +		 */
> +		fa_match = NULL;
> +		fa_first = fa;
> +		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
> +		list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
> +			if (fa->fa_tos != tos)
> +				break;
> +			if (fa->fa_info->fib_priority != fi->fib_priority)
> +				break;
> +			if (fa->fa_type == cfg->fc_type &&
> +			    fa->fa_scope == cfg->fc_scope &&
> +			    fa->fa_info == fi) {
> +				fa_match = fa;
> +				break;

Why can't we try goto out from here? (less reading...)

> +			}
> +		}
> +


>  		if (cfg->fc_nlflags & NLM_F_REPLACE) {
>  			struct fib_info *fi_drop;
>  			u8 state;
>  
> -			if (fi->fib_treeref > 1)
> +			fa = fa_first;
> +			if (fa_match) {
> +				if (fa == fa_match)
> +					err = 0;

Could you comment more why returning an error seems to depend on the
order of aliases here? But, IMHO there is no reason to change the old
behavior WRT this error, so probably this err = 0 should be always if
NLM_F_REPLACE is set.

>  				goto out;
> -
> +			}
>  			write_lock_bh(&fib_hash_lock);
>  			fi_drop = fa->fa_info;
>  			fa->fa_info = fi;
> @@ -469,20 +493,11 @@ static int fn_hash_insert(struct fib_tab
>  		 * uses the same scope, type, and nexthop
>  		 * information.
>  		 */
> -		fa_orig = fa;
> -		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
> -		list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
> -			if (fa->fa_tos != tos)
> -				break;
> -			if (fa->fa_info->fib_priority != fi->fib_priority)
> -				break;
> -			if (fa->fa_type == cfg->fc_type &&
> -			    fa->fa_scope == cfg->fc_scope &&
> -			    fa->fa_info == fi)
> -				goto out;
> -		}
> +		if (fa_match)
> +			goto out;
> +
>  		if (!(cfg->fc_nlflags & NLM_F_APPEND))
> -			fa = fa_orig;
> +			fa = fa_first;
>  	}
>  
>  	err = -ENOENT;

Generally this patch looks OK to me.

Thanks,
Jarek P. 

PS: I think, this FIB info you sent earlier is just fine for
Documentation/networking without any changes! (Maybe one more patch?)

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Jarek Poplawski]

On 28-01-2008 00:20, Jarek Poplawski wrote:
> Hi, I have a few questions below:
> 
> Julian Anastasov wrote, On 01/26/2008 01:41 PM:
...
>> --- linux-2.6.24/net/ipv4/fib_hash.c_orig	2008-01-25 10:45:06.000000000 +0200
>> +++ linux-2.6.24/net/ipv4/fib_hash.c	2008-01-26 14:11:34.000000000 +0200
>> @@ -434,19 +434,43 @@ static int fn_hash_insert(struct fib_tab
>>  
>>  	if (fa && fa->fa_tos == tos &&
>>  	    fa->fa_info->fib_priority == fi->fib_priority) {

...One more doubt here. Your FIB description doesn't say about this,
and a code at the end of this function, where a new alias is inserted,
doesn't seem to show this too. Are these aliases in the node sorted by
fib_priority too? I mean, isn't it possible here, that we got fa
from fib_node_alias() with right tos but greater fib_priority, but
there is a better match (with right priority) later on the list yet?
(The comment above this reads something else, but I'd be glad if you
could confirm this.)

Regards,
Jarek P. 

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Jarek Poplawski]

On Mon, Jan 28, 2008 at 09:33:02AM +0100, Jarek Poplawski wrote:
...
> from fib_node_alias() with right tos but greater fib_priority, but

"from fib_find_alias()" of course...

arek P. 

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Jarek Poplawski]

On Mon, Jan 28, 2008 at 09:33:02AM +0100, Jarek Poplawski wrote:
...
> [...] Are these aliases in the node sorted by
> fib_priority too? [...] 

OK, I see they are!

Sorry for bothering,
Jarek P. 

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Julian Anastasov]

	Hello,

On Mon, 28 Jan 2008, Jarek Poplawski wrote:

> BTW, the way "add" works wasn't questioned now, but it seems could be,
> or man ip should call it e.g. "ip route add - add new destination",
> and append "ip route append" (unless I have old man).

	"add" is similar to "prepend", only that checks NLM_F_EXCL
to avoid many alternative routes, only one route for tos+priority is
allowed for "add". As for the sorting by tos/priority and the
insertion position I remember for thread on this issue:

http://marc.info/?t=109614290600002&r=1&w=2

> > +		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
> > +		list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
> > +			if (fa->fa_tos != tos)
> > +				break;
> > +			if (fa->fa_info->fib_priority != fi->fib_priority)
> > +				break;
> > +			if (fa->fa_type == cfg->fc_type &&
> > +			    fa->fa_scope == cfg->fc_scope &&
> > +			    fa->fa_info == fi) {
> > +				fa_match = fa;
> > +				break;
> 
> Why can't we try goto out from here? (less reading...)

	The case with NLM_F_REPLACE needs to check more things, one
day one can combine NLM_F_APPEND+NLM_F_REPLACE to replace last
alternative route, not only the first one as currently implemented.

> > +			fa = fa_first;
> > +			if (fa_match) {
> > +				if (fa == fa_match)
> > +					err = 0;
> 
> Could you comment more why returning an error seems to depend on the
> order of aliases here? But, IMHO there is no reason to change the old
> behavior WRT this error, so probably this err = 0 should be always if
> NLM_F_REPLACE is set.

	fa_match is some existing alias that matches all new parameters.
As NLM_F_REPLACE changes the first alternative route for 
tos+priority if fa_match == fa_first (we are replacing alias that
matches all parameters) we return 0, only that routing cache is not 
flushed - nothing is replaced/changed. So, "fa == fa_match" means
"replace will not change existing parameters", return 0 as this is
not an error.

> PS: I think, this FIB info you sent earlier is just fine for
> Documentation/networking without any changes! (Maybe one more patch?)

	This is so small part of the picture, such 15-minute listing
is not enough to explain everything. May be such and other information
can be added as part of some known documentation.

Regards

--
Julian Anastasov <ja@ssi.bg>

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Jarek Poplawski]

On Tue, Jan 29, 2008 at 02:30:47AM +0200, Julian Anastasov wrote:
> 
> 	Hello,
> 
> On Mon, 28 Jan 2008, Jarek Poplawski wrote:
> 
> > BTW, the way "add" works wasn't questioned now, but it seems could be,
> > or man ip should call it e.g. "ip route add - add new destination",
> > and append "ip route append" (unless I have old man).
> 
> 	"add" is similar to "prepend", only that checks NLM_F_EXCL
> to avoid many alternative routes, only one route for tos+priority is
> allowed for "add". As for the sorting by tos/priority and the
> insertion position I remember for thread on this issue:

Yes but I've meant this man (8) ip description could be confusing:

"  ip route add - add new route
   ip route change - change route
   ip route replace - change or add new one"

One can wonder why there is an error while adding two new routes with
"add", but OK to do the same with "replace". But, it's "man" problem
of course.

> 
> http://marc.info/?t=109614290600002&r=1&w=2
> 
> > > +		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
> > > +		list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
> > > +			if (fa->fa_tos != tos)
> > > +				break;
> > > +			if (fa->fa_info->fib_priority != fi->fib_priority)
> > > +				break;
> > > +			if (fa->fa_type == cfg->fc_type &&
> > > +			    fa->fa_scope == cfg->fc_scope &&
> > > +			    fa->fa_info == fi) {
> > > +				fa_match = fa;
> > > +				break;
> > 
> > Why can't we try goto out from here? (less reading...)
> 
> 	The case with NLM_F_REPLACE needs to check more things, one
> day one can combine NLM_F_APPEND+NLM_F_REPLACE to replace last
> alternative route, not only the first one as currently implemented.

I'm not sure I can understand your point: do you mean there could be
something to do for these options is fa_match exists? But, maybe it
relates to my question below...

> 
> > > +			fa = fa_first;
> > > +			if (fa_match) {
> > > +				if (fa == fa_match)
> > > +					err = 0;
> > 
> > Could you comment more why returning an error seems to depend on the
> > order of aliases here? But, IMHO there is no reason to change the old
> > behavior WRT this error, so probably this err = 0 should be always if
> > NLM_F_REPLACE is set.
> 
> 	fa_match is some existing alias that matches all new parameters.
> As NLM_F_REPLACE changes the first alternative route for 
> tos+priority if fa_match == fa_first (we are replacing alias that
> matches all parameters) we return 0, only that routing cache is not 
> flushed - nothing is replaced/changed. So, "fa == fa_match" means
> "replace will not change existing parameters", return 0 as this is
> not an error.

Probably I miss something, but what parameters do we change if
(fa_match) && (fa != fa_match)? Isn't this "goto out" in any case?

> 
> > PS: I think, this FIB info you sent earlier is just fine for
> > Documentation/networking without any changes! (Maybe one more patch?)
> 
> 	This is so small part of the picture, such 15-minute listing
> is not enough to explain everything. May be such and other information
> can be added as part of some known documentation.

This is small but condensed, and IMHO it fits very well what is now
in this directory.

Thanks,
Jarek P.

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Jarek Poplawski]

On Tue, Jan 29, 2008 at 09:49:15AM +0100, Jarek Poplawski wrote:
> On Tue, Jan 29, 2008 at 02:30:47AM +0200, Julian Anastasov wrote:
...
> > 	fa_match is some existing alias that matches all new parameters.
> > As NLM_F_REPLACE changes the first alternative route for 
> > tos+priority if fa_match == fa_first (we are replacing alias that
> > matches all parameters) we return 0, only that routing cache is not 
> > flushed - nothing is replaced/changed. So, "fa == fa_match" means
> > "replace will not change existing parameters", return 0 as this is
> > not an error.
> 
> Probably I miss something, but what parameters do we change if
> (fa_match) && (fa != fa_match)? Isn't this "goto out" in any case?

OOPS! You mean change is needed, but we can't do this! (I'm so slow...)

All correct!

Thanks again,
Jarek P.

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Jarek Poplawski]

On Tue, Jan 29, 2008 at 10:10:30AM +0100, Jarek Poplawski wrote:
> On Tue, Jan 29, 2008 at 09:49:15AM +0100, Jarek Poplawski wrote:
> > On Tue, Jan 29, 2008 at 02:30:47AM +0200, Julian Anastasov wrote:
> ...
> > > 	fa_match is some existing alias that matches all new parameters.
> > > As NLM_F_REPLACE changes the first alternative route for 
> > > tos+priority if fa_match == fa_first (we are replacing alias that
> > > matches all parameters) we return 0, only that routing cache is not 
> > > flushed - nothing is replaced/changed. So, "fa == fa_match" means
> > > "replace will not change existing parameters", return 0 as this is
> > > not an error.
> > 
> > Probably I miss something, but what parameters do we change if
> > (fa_match) && (fa != fa_match)? Isn't this "goto out" in any case?
> 
> OOPS! You mean change is needed, but we can't do this! (I'm so slow...)

...On the other hand, I wonder how bad would be switching these two
to avoid this error? After all "replace" with this "add or change"
meaning looks quite permissive, and after all it was used before with
no such errors, so, even if correct, it could still break some
scripts...

Jarek P.

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Julian Anastasov]

	Hello,

On Tue, 29 Jan 2008, Jarek Poplawski wrote:

> ...On the other hand, I wonder how bad would be switching these two
> to avoid this error? After all "replace" with this "add or change"
> meaning looks quite permissive, and after all it was used before with
> no such errors, so, even if correct, it could still break some
> scripts...

	Agreed, what could break are scripts that add 2 equal 
alternative routes and checking for errors. BTW, I tried to add
more information and that is what I have finally:

http://www.ssi.bg/~ja/fib.txt

Regards

--
Julian Anastasov <ja@ssi.bg>

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[Jarek Poplawski]

On Sat, Feb 02, 2008 at 12:56:08PM +0200, Julian Anastasov wrote:
> 
> 	Hello,

Hi!

> On Tue, 29 Jan 2008, Jarek Poplawski wrote:
> 
> > ...On the other hand, I wonder how bad would be switching these two
> > to avoid this error? After all "replace" with this "add or change"
> > meaning looks quite permissive, and after all it was used before with
> > no such errors, so, even if correct, it could still break some
> > scripts...
> 
> 	Agreed, what could break are scripts that add 2 equal 
> alternative routes and checking for errors.

BTW, I would be glad if you could use this in some patch (unless you
have no time - then let me know)...

> BTW, I tried to add
> more information and that is what I have finally:
> 
> http://www.ssi.bg/~ja/fib.txt

Great! But, I hope more people will know about this if you send it as
a patch with a new thread. BTW#2: I've thought it maybe needs a bit of
cosmetcs like more uniform TOS or tos and "." or no "." after
paragraphs, or more consistent wrapping, but then I've exagerated with
this for sure. Anyway, below are some suggestions, but feel free to
skip them all!

Thanks,
Jarek P.


--- fib.txt.orig	2008-02-02 15:44:09.000000000 +0100
+++ fib.txt	2008-02-02 18:57:56.000000000 +0100
@@ -1,42 +1,55 @@
 
 		FIB - Forwarding Information Base
 
-- Routes are organized in routing tables
+- Routes are organized in routing tables.
+
 - For "fib_hash" algorithm routing tables have 33 zones (for prefix
-lengths 0..32), routing lookup walks them from 32 to 0 to find a
-node containing all routing information
-- Zones are implemented as hash tables where nodes are hashed by
-key (prefix=network) because there can be lots of prefixes in a zone.
+lengths 0..32), routing lookup walks them from 32 to 0 to find a node
+containing all routing information.
+
+- Zones are implemented as hash tables where nodes are hashed by key
+(prefix = network) because there can be lots of prefixes in a zone.
+
 - Nodes can be stored with other methods, eg. trie, where nodes are
-searched (we hope faster) by prefix and length, no zones are used
-in this case
-- Nodes have a list of aliases (tos+type+scope+fib_info ptr) sorted by
-decreasing TOS because TOS=0 must be a last hit when looking for route,
-TOS 0 matches packet with any TOS. type is unicast, local, prohibit, etc.
-scope is host, link, etc. Additionally, aliases with same TOS are
-sorted by fib_info priority (ascending).
-- fib_info is a structure containing protocol (kernel, boot, zebra, etc),
-prefsrc, priority (metric), metrics, nexthop(s). Fallback routes have
-higher value for priority, they are used if more priority routes
-disappear or their nexthops are dead.
-- fib_info structures are organized in 2 global hash tables, one
-keyed by prefsrc and another by nexthop_count+protocol+prefsrc+priority
-- fib_info is a shared structure, different aliases can point to same
-fib_info, even aliases from different prefixes, from different routing
-tables. By this way if fib_info contains multipath route then many
-aliases share same route path scheduling context.
-- Nexthop contains gateway, output device, scope and weight. Weight
+searched (we hope faster) by prefix and length; no zones are used in
+this case.
+
+- Nodes have a list of aliases (tos + type + scope + fib_info ptr)
+sorted by decreasing tos because tos = 0 must be the last hit when
+looking for a route (tos = 0 matches packet with any tos); type is:
+unicast, local, prohibit, etc.; scope is: host, link, etc.
+Additionally, aliases with the same tos are sorted by fib_info
+priority (ascending).
+
+- fib_info is a structure containing: protocol (kernel, boot, zebra,
+etc.), prefsrc, priority (metric), metrics, nexthop(s). Fallback
+routes have higher value for priority; they are used if routes with
+more priority disappear or their nexthops are dead.
+
+- fib_info structures are organized in 2 global hash tables, one keyed
+by prefsrc, and another by: nexthop_count + protocol + prefsrc +
+priority.
+
+- fib_info structure is shared: different aliases can point at the
+same fib_info, even aliases with different prefixes or from different
+routing tables. This way if fib_info contains multipath route, then
+many aliases share the same route path scheduling context.
+
+- Nexthop contains: gateway, output device, scope and weight; weight
 is used for path scheduling where nexthops have relative priority
-compared to other nexthops in multipath route.
-- There can be many aliases with same tos, there can be alternative
-routes (aliases) with same tos and priority (metric) but only one alias
-with particular tos, type, scope and fib_info can exist to avoid duplicate
-alternative routes.
-- The operation to replace route includes replacing of alias. The alias
-in node (table -> prefix/len) is matched by tos and fib_info priority and
-they can not be changed. The parameters that are changed are type, scope
-and fib_info (except priority).
-- The 'ip' tool maps route operations to NLM_F_* flags as follows: 
+compared to other nexthops in a multipath route.
+
+- There can be many alternative routes (aliases) with the same tos and
+priority (metric), but only one alias can exist with particular: tos,
+type, scope and fib_info - to avoid duplicate alternative routes.
+
+- The operation to replace a route includes replacing an alias. The
+alias in a node (table -> prefix/len) is matched by tos and fib_info
+priority, and they cannot be changed. The parameters that are
+changed are: type, scope and fib_info (except priority).
+
+- The 'ip' tool maps route operations to NLM_F_* flags as follows:
+
 	- ip route add		-> NLM_F_CREATE | NLM_F_EXCL
 		- add unique route
 	- ip route change	-> NLM_F_REPLACE
@@ -49,30 +62,33 @@ and fib_info (except priority).
 		- create new alternative route as last
 	- ip route test		-> NLM_F_EXCL
 		- check if route exists
-- By default, 'ip route add' adds no more than one route for particular
-prefix/len, tos and fib_info priority. This is guaranteed by the
-NLM_F_EXCL flag. Extension to this rule is the support for alternative
-routes where 'ip route prepend' and 'ip route append' which avoid the
-NLM_F_EXCL flag and allow many routes for prefix/len, tos and
-fib_info priority to be added. Still, there should be no more than one
-alternative route with same prefix/len, tos and all remaining fib_info
-parameters.
+
+- By default, 'ip route add' adds no more than one route for
+particular prefix/len, tos and fib_info priority. This is guaranteed
+by the NLM_F_EXCL flag. An extension to this rule is support for
+alternative routes with 'ip route prepend' and 'ip route append' which
+avoid the NLM_F_EXCL flag and allow many routes for prefix/len, tos
+and fib_info priority to be added. Still, there should be no more than
+one alternative route with the same prefix/len, tos and all remaining
+fib_info parameters.
+
 - As for the 'route' tool, it works just like 'ip route prepend' which
 allows alternative routes to be created.
+
 - Additionally, the IP stack can automatically add local or broadcast
-'proto kernel' routes when IP address is added and unicast subnet route
-when primary IP address for subnet is added. The routes are created in
-the 'ip route append' way in local or main table.
+'proto kernel' routes when IP address is added, and unicast subnet
+route when primary IP address for a subnet is added. The routes are
+created in the 'ip route append' way in local or main table.
 
-FIB tree:
+- FIB tree:
 
 * routing table
-	* node (prefix/len)
-		* alias (tos, type, scope)
-			-> fib_info (priority, protocol, prefsrc, metrics)
-				* nexthop (gateway, outdev, scope, weight)
-
-- one or many routing tables with fast access to multiple nodes, each
-node has list with aliases with unique parameters sorted by decreasing tos
-and increasing priority.
+  * node (prefix/len)
+    * alias (tos, type, scope)
+      -> fib_info (priority, protocol, prefsrc, metrics)
+         * nexthop (gateway, outdev, scope, weight)
+
+- One or more routing tables can exist with fast access to multiple
+nodes; each node has a list of aliases with unique parameters sorted
+by decreasing tos and increasing priority.
 

Re: [PATCHv2 2.6.24] fib: fix route replacement, fib_info is shared

[David Miller]

From: Julian Anastasov <ja@ssi.bg>
Date: Sat, 26 Jan 2008 14:41:32 +0200 (EET)

> 
> 	fib_info can be shared by many route prefixes but we don't
> want duplicate alternative routes for a prefix+tos+priority. Last
> change was not correct to check fib_treeref because it accounts usage
> from other prefixes. Additionally, avoid replacement without error
> if new route is same, as Joonwoo Park suggests.
> 
> Signed-off-by: Julian Anastasov <ja@ssi.bg>

Applied, thank you.