[IPv4]: More fib_alias insertion fixes

	Hello,

	some fib alias fixes:

- modify fib_find_alias to stop before the desired alias, even
if reaching different TOS. If no alias is found we have to append
at end of fn_alias.

- properly prepend/append new alias with same prefix/tos/prio

- use list_for_each_entry_continue

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

diff -ur v2.6.9-rc2-bk10/linux/net/ipv4/fib_hash.c linux/net/ipv4/fib_hash.c

--- v2.6.9-rc2-bk10/linux/net/ipv4/fib_hash.c	2004-09-25 22:44:31.000000000 +0300
+++ linux/net/ipv4/fib_hash.c	2004-09-25 22:45:06.580902744 +0300

@@ -431,24 +431,20 @@
 	return NULL;
 }
 
-/* Return the first fib alias matching TOS with
- * priority less than or equal to PRIO.
- */
+/* Return the first fib alias below TOS and after PRIO thresholds */
 static struct fib_alias *fib_find_alias(struct fib_node *fn, u8 tos, u32 prio)
 {
 	if (fn) {
 		struct list_head *head = &fn->fn_alias;
-		struct fib_alias *fa, *prev_fa;
+		struct fib_alias *fa;
 
-		prev_fa = NULL;
 		list_for_each_entry(fa, head, fa_list) {
-			if (fa->fa_tos != tos)
+			if (fa->fa_tos > tos)
 				continue;
-			prev_fa = fa;
-			if (prio <= fa->fa_info->fib_priority)
-				break;
+			if (fa->fa_info->fib_priority >= prio ||
+			    fa->fa_tos < tos)
+				return fa;
 		}
-		return prev_fa;
 	}
 	return NULL;
 }

@@ -461,6 +457,7 @@
 	struct fib_node *new_f, *f;
 	struct fib_alias *fa, *new_fa;
 	struct fn_zone *fz;
+	struct list_head *ins_before = NULL;
 	struct fib_info *fi;
 	int z = r->rtm_dst_len;
 	int type = r->rtm_type;

@@ -505,9 +502,12 @@
 	 * and we need to allocate a new one of those as well.
 	 */
 
-	if (fa &&
+	if (fa)
+		ins_before = &fa->fa_list;
+
+	if (fa && fa->fa_tos == tos &&
 	    fa->fa_info->fib_priority == fi->fib_priority) {
-		struct fib_alias *fa_orig;
+		struct list_head *fa_head;
 
 		err = -EEXIST;
 		if (n->nlmsg_flags & NLM_F_EXCL)

@@ -536,8 +536,9 @@
 		 * uses the same scope, type, and nexthop
 		 * information.
 		 */
-		fa_orig = fa;
-		list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
+		fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
+		fa_head = &f->fn_alias;
+		list_for_each_entry_continue(fa, fa_head, fa_list) {
 			if (fa->fa_tos != tos)
 				break;
 			if (fa->fa_info->fib_priority != fi->fib_priority)

@@ -546,9 +547,9 @@
 			    fa->fa_scope == r->rtm_scope &&
 			    fa->fa_info == fi)
 				goto out;
+			if (n->nlmsg_flags & NLM_F_APPEND)
+				ins_before = fa->fa_list.next;
 		}
-		if (!(n->nlmsg_flags & NLM_F_APPEND))
-			fa = fa_orig;
 	}
 
 	err = -ENOENT;

@@ -585,8 +586,7 @@
 	write_lock_bh(&fib_hash_lock);
 	if (new_f)
 		fib_insert_node(fz, new_f);
-	list_add(&new_fa->fa_list,
-		 (fa ? &fa->fa_list : &f->fn_alias));
+	list_add_tail(&new_fa->fa_list, ins_before? : &f->fn_alias);
 	write_unlock_bh(&fib_hash_lock);
 
 	if (new_f)

@@ -637,8 +637,9 @@
 		return -ESRCH;
 
 	fa_to_delete = NULL;
-	fa_head = fa->fa_list.prev;
-	list_for_each_entry(fa, fa_head, fa_list) {
+	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
+	fa_head = &f->fn_alias;
+	list_for_each_entry_continue(fa, fa_head, fa_list) {
 		struct fib_info *fi = fa->fa_info;
 
 		if (fa->fa_tos != tos)

On Sat, 25 Sep 2004 23:09:11 +0300 (EEST)
Julian Anastasov [off-list ref] wrote:

- modify fib_find_alias to stop before the desired alias, even
if reaching different TOS. If no alias is found we have to append
at end of fn_alias.

- properly prepend/append new alias with same prefix/tos/prio

- use list_for_each_entry_continue

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

Two things:

1) I applied a version of the list_for_each_entry_continue fix
   I got privately from Alexey, can you repatch relative to
   that?  It is included below.

2) The fib_alias list is not meant at all to be sorted by TOS
   value. Within a TOS it _is_ sorted by priority.  This was
   intentional, and I believe your changes assume I meant to
   keep the "aliases ordered by TOS" property.  I did not.

Please give test cases when posting fixes of this nature.
I wouldn't have to guess about #2 if you gave a bunch of
"ip route foo" commands that gave behavior you think is
incorrect.

Thanks.

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2004/09/25 19:47:58-07:00 kuznet@ms2.inr.ac.ru 
#   [IPV4]: Fix fa_list walking in fib_hash.c
#   
#   Prevent accidently referencing f->fn_alias list
#   head as a real fib_alias object.
#   
#   Signed-off-by: David S. Miller [off-list ref]
# 
# net/ipv4/fib_hash.c
#   2004/09/25 19:47:27-07:00 kuznet@ms2.inr.ac.ru +4 -4
#   [IPV4]: Fix fa_list walking in fib_hash.c
#   
#   Prevent accidently referencing f->fn_alias list
#   head as a real fib_alias object.
#   
#   Signed-off-by: David S. Miller [off-list ref]
# 
diff -Nru a/net/ipv4/fib_hash.c b/net/ipv4/fib_hash.c

--- a/net/ipv4/fib_hash.c	2004-09-25 19:54:08 -07:00
+++ b/net/ipv4/fib_hash.c	2004-09-25 19:54:08 -07:00

@@ -537,7 +537,8 @@
 		 * information.
 		 */
 		fa_orig = fa;
-		list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
+		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)

@@ -611,7 +612,6 @@
 	struct fn_hash *table = (struct fn_hash*)tb->tb_data;
 	struct fib_node *f;
 	struct fib_alias *fa, *fa_to_delete;
-	struct list_head *fa_head;
 	int z = r->rtm_dst_len;
 	struct fn_zone *fz;
 	u32 key;

@@ -637,8 +637,8 @@
 		return -ESRCH;
 
 	fa_to_delete = NULL;
-	fa_head = fa->fa_list.prev;
-	list_for_each_entry(fa, fa_head, fa_list) {
+	fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
+	list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
 		struct fib_info *fi = fa->fa_info;
 
 		if (fa->fa_tos != tos)

	Hello,

On Sat, 25 Sep 2004, David S. Miller wrote:

2) The fib_alias list is not meant at all to be sorted by TOS
   value. Within a TOS it _is_ sorted by priority.  This was
   intentional, and I believe your changes assume I meant to
   keep the "aliases ordered by TOS" property.  I did not.

	But it still needs one exception: the entries with TOS 0
must be at tail to allow fn_hash_lookup to match by TOS. With
random TOS insertion this is not guaranteed, the entries with
TOS=0 (wildcard) will match before the others.

	So, I fixed it to allow the TOS subchains to be
in any order but always before the subchain with TOS 0.

Please give test cases when posting fixes of this nature.
I wouldn't have to guess about #2 if you gave a bunch of
"ip route foo" commands that gave behavior you think is
incorrect.

	ok, I'm attaching 3 files: new diff, test script to add/del
entries in custom table and its output in another file (after
applying the patch). I'm using:

./rt.sh start
./rt.sh stop

Regards

--
Julian Anastasov [off-list ref]

Julian Anastasov [off-list ref] wrote:

       But it still needs one exception: the entries with TOS 0
must be at tail to allow fn_hash_lookup to match by TOS. With
random TOS insertion this is not guaranteed, the entries with
TOS=0 (wildcard) will match before the others.

Good point.

               prev_fa = NULL;
               list_for_each_entry(fa, head, fa_list) {
                       if (fa->fa_tos != tos)
-                               continue;
+                       {
+                               if (!prev_fa && fa->fa_tos)
+                                       continue;
+                               /* Stop at TOS 0 or after entries from our TOS */
+                               return fa;
+                       }

Well if we're doing this then we might as well keep it sorted by TOS.
It makes the code simpler, right?

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--
===== net/ipv4/fib_hash.c 1.26 vs edited =====

--- 1.26/net/ipv4/fib_hash.c	2004-09-24 06:19:43 +10:00
+++ edited/net/ipv4/fib_hash.c	2004-09-26 18:12:57 +10:00

@@ -442,9 +442,11 @@
 
 		prev_fa = NULL;
 		list_for_each_entry(fa, head, fa_list) {
-			if (fa->fa_tos != tos)
-				continue;
+			if (fa->fa_tos < tos)
+				break;
 			prev_fa = fa;
+			if (fa->fa_tos > tos)
+				continue;
 			if (prio <= fa->fa_info->fib_priority)
 				break;
 		}

@@ -506,6 +508,7 @@
 	 */
 
 	if (fa &&
+	    fa->fa_tos == tos &&
 	    fa->fa_info->fib_priority == fi->fib_priority) {
 		struct fib_alias *fa_orig;
 

	Hello,

On Sun, 26 Sep 2004, Herbert Xu wrote:

Well if we're doing this then we might as well keep it sorted by TOS.
It makes the code simpler, right?

	I do not know for good reason to avoid order by TOS, may be
Dave can explain.

	As for your last change, it is wrong:

                prev_fa = NULL;
                list_for_each_entry(fa, head, fa_list) {
-                       if (fa->fa_tos != tos)
-                               continue;
+                       if (fa->fa_tos < tos)

	here prev_fa can be NULL but we require to stop at fa.
It happens when we are creating first entry in our subchain.

+                               break;
                        prev_fa = fa;
+                       if (fa->fa_tos > tos)
+                               continue;
                        if (prio <= fa->fa_info->fib_priority)
                                break;

	here if fa is the last one it is wrong to return prev_fa!=NULL,
we need to return NULL (append) because we have to append
new entry in our subchain (which is last in this case).

                }

	Here is my understanding how should work fib_find_alias (already
implemented, refer to my first posting, the case where we sort by TOS).
Note that the logic is same as before fib_alias appeared:

- fib_find_alias can return exact match: the desired TOS & PRIO.
This is the first entry in a subchain where append and prepend
matter (NLM_F_APPEND).

- the return value should be used in this way: if NULL then we have
to append the new entry at end of list. Else, it is a fa with
fa_tos<desired_TOS || (fa_tos==desired_TOS && fib_priority >= desired PRIO)
We are going to insert the new entry before this fa (even if it is
not exact match, even if it is from next subchain). Saying it in
another way: use append only if there is no place to insert.

	Sometimes we can add entry with metric less
than existing one but sometimes we have to insert new entry
between two subchains (fa points to first entry in next subchain).
The result: fa points to next subchain or somehere in our
subchain - the place to insert.

- list_add serves the purpose to insert between head and first
(fa and next fa/fn_alias), we need list_add_tail (insert before fa
or fn_alias, i.e. append at tail).

	So, may be we need my 1st version of fib_find_alias plus
'fa->fa_tos == tos' plus list_add_tail?

Regards

--
Julian Anastasov [off-list ref]

Julian Anastasov [off-list ref] wrote:

       As for your last change, it is wrong:

quoted

                prev_fa = NULL;
                list_for_each_entry(fa, head, fa_list) {
-                       if (fa->fa_tos != tos)
-                               continue;
+                       if (fa->fa_tos < tos)

       here prev_fa can be NULL but we require to stop at fa.
It happens when we are creating first entry in our subchain.

If fa->fa_tos < tos, then we should add the new entry before fa.
If prev_fa is not NULL, then adding after prev_fa is obviously
correct.  If prev_fa is NULL, the caller will add it after the
head of the list which is also correct since fa must've been the
first element in the list.

quoted

+                               break;
                        prev_fa = fa;
+                       if (fa->fa_tos > tos)
+                               continue;
                        if (prio <= fa->fa_info->fib_priority)
                                break;

       here if fa is the last one it is wrong to return prev_fa!=NULL,
we need to return NULL (append) because we have to append
new entry in our subchain (which is last in this case).

I still haven't figured out what you mean here, but I've found a bug :)
When prio < fa->fa_info->fib_priority, this returns the wrong entry.

- fib_find_alias can return exact match: the desired TOS & PRIO.
This is the first entry in a subchain where append and prepend
matter (NLM_F_APPEND).

Ack.

- the return value should be used in this way: if NULL then we have
to append the new entry at end of list. Else, it is a fa with

Not quite.  If it's NULL we add it at the *head* of the list.  We
call list_add and not list_add_tail.  Actually your patch changes the
list_add call to list_add_tail so your comment would be correct if your
patch had been applied :)

fa_tos<desired_TOS || (fa_tos==desired_TOS && fib_priority >= desired PRIO)
We are going to insert the new entry before this fa (even if it is
not exact match, even if it is from next subchain). Saying it in
another way: use append only if there is no place to insert.

Again this is only true if we apply your patch.  As it is find_alias
returns (and is expected to return) the entry *before* where the new
entry should be added.

Whether it *should* be before or after is obviously a deep philosophical
question :)

So here are two patches to fix the fib_priority problem.  The first one
returns the entry before as we do now while the second one returns the
entry afterwards.

Actually, I just noticed that this philosophical question does have
practical implications :) The list_for_each_entry_continue() loop in
fn_hash_delete will fail if fa is the entry before the correct position.

Therefore I withdraw my endorsement for the "entry before" interpretation :)
So patch 1 is only present for review purposes, please don't apply it.

Patch 2 is good as far as I can see.  So,

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
-- patch 1
===== net/ipv4/fib_hash.c 1.26 vs edited =====

--- 1.26/net/ipv4/fib_hash.c	2004-09-24 06:19:43 +10:00
+++ edited/net/ipv4/fib_hash.c	2004-09-26 22:02:51 +10:00

@@ -442,11 +442,15 @@
 
 		prev_fa = NULL;
 		list_for_each_entry(fa, head, fa_list) {
-			if (fa->fa_tos != tos)
-				continue;
-			prev_fa = fa;
-			if (prio <= fa->fa_info->fib_priority)
+			if (fa->fa_tos < tos)
 				break;
+			if (fa->fa_tos == tos) {
+				if (prio == fa->fa_info->fib_priority)
+					prev_fa = fa;
+				if (prio <= fa->fa_info->fib_priority)
+					break;
+			}
+			prev_fa = fa;
 		}
 		return prev_fa;
 	}

@@ -506,6 +510,7 @@
 	 */
 
 	if (fa &&
+	    fa->fa_tos == tos &&
 	    fa->fa_info->fib_priority == fi->fib_priority) {
 		struct fib_alias *fa_orig;

-- patch 2

===== net/ipv4/fib_hash.c 1.27 vs edited =====

--- 1.27/net/ipv4/fib_hash.c	2004-09-26 22:11:38 +10:00
+++ edited/net/ipv4/fib_hash.c	2004-09-26 22:25:10 +10:00

@@ -432,23 +432,23 @@
 }
 
 /* Return the first fib alias matching TOS with
- * priority less than or equal to PRIO.
+ * the same priority or the point where the node should be inserted.
  */
 static struct fib_alias *fib_find_alias(struct fib_node *fn, u8 tos, u32 prio)
 {
 	if (fn) {
 		struct list_head *head = &fn->fn_alias;
-		struct fib_alias *fa, *prev_fa;
+		struct fib_alias *fa;
 
-		prev_fa = NULL;
 		list_for_each_entry(fa, head, fa_list) {
-			if (fa->fa_tos != tos)
+			if (fa->fa_tos < tos)
+				break;
+			if (fa->fa_tos > tos)
 				continue;
-			prev_fa = fa;
 			if (prio <= fa->fa_info->fib_priority)
 				break;
 		}
-		return prev_fa;
+		return fa;
 	}
 	return NULL;
 }

@@ -506,6 +506,7 @@
 	 */
 
 	if (fa &&
+	    fa->fa_tos == tos &&
 	    fa->fa_info->fib_priority == fi->fib_priority) {
 		struct fib_alias *fa_orig;
 

@@ -586,7 +587,7 @@
 	write_lock_bh(&fib_hash_lock);
 	if (new_f)
 		fib_insert_node(fz, new_f);
-	list_add(&new_fa->fa_list,
+	list_add_tail(&new_fa->fa_list,
 		 (fa ? &fa->fa_list : &f->fn_alias));
 	write_unlock_bh(&fib_hash_lock);
 

On Sun, Sep 26, 2004 at 10:32:34PM +1000, Herbert Xu wrote:

Therefore I withdraw my endorsement for the "entry before" interpretation :)
So patch 1 is only present for review purposes, please don't apply it.

Patch 2 is good as far as I can see.  So,

And now that I look at your patch again, it is pretty much the same
as patch 2.  So please accept my apologies for going on this
goose-chase.

Cheers,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

	Hello,

	attaching version with fib_alias ordered by TOS ...

On Sun, 26 Sep 2004, Herbert Xu wrote:

quoted

       here prev_fa can be NULL but we require to stop at fa.
It happens when we are creating first entry in our subchain.

If fa->fa_tos < tos, then we should add the new entry before fa.

	True, but in your patch2 you return fa after
list_for_each_entry which is not valid when the loop terminates.
Just change it to return the fa into the loop.

If prev_fa is not NULL, then adding after prev_fa is obviously
correct.  If prev_fa is NULL, the caller will add it after the

	May be there are two varaints when we do not return list_head
but fa:

- "insert before": find a place to "insert before" else add in tail

- "insert after": find a place to "insert after" else add in top

	but as fib_find_alias is used also for deletion I do
not think we have many choices, we return the node to insert
before, as in the comment.

head of the list which is also correct since fa must've been the
first element in the list.

quoted

quoted

+                               break;
                        prev_fa = fa;
+                       if (fa->fa_tos > tos)
+                               continue;
                        if (prio <= fa->fa_info->fib_priority)
                                break;

       here if fa is the last one it is wrong to return prev_fa!=NULL,
we need to return NULL (append) because we have to append
new entry in our subchain (which is last in this case).

I still haven't figured out what you mean here, but I've found a bug :)
When prio < fa->fa_info->fib_priority, this returns the wrong entry.

	Yes, this is one of the original problems :) If you have the
kernel running you can try the posted test script.

quoted

- the return value should be used in this way: if NULL then we have
to append the new entry at end of list. Else, it is a fa with

Not quite.  If it's NULL we add it at the *head* of the list.  We
call list_add and not list_add_tail.  Actually your patch changes the
list_add call to list_add_tail so your comment would be correct if your
patch had been applied :)

        It seems there are too many wishes currently in fib_find_alias.
list_add can be used for "insert after" but fa is declared to be for
"insert before fa". I think, fib_find_alias was originally designed
to be used for "insert before fa".

quoted

fa_tos<desired_TOS || (fa_tos==desired_TOS && fib_priority >= desired PRIO)
We are going to insert the new entry before this fa (even if it is
not exact match, even if it is from next subchain). Saying it in
another way: use append only if there is no place to insert.

Again this is only true if we apply your patch.  As it is find_alias
returns (and is expected to return) the entry *before* where the new
entry should be added.

	Yes, "insert before fa", then why list_add is used?

Whether it *should* be before or after is obviously a deep philosophical
question :)

So here are two patches to fix the fib_priority problem.  The first one
returns the entry before as we do now while the second one returns the
entry afterwards.

Actually, I just noticed that this philosophical question does have
practical implications :) The list_for_each_entry_continue() loop in
fn_hash_delete will fail if fa is the entry before the correct position.

	There are simply no alternatives :) I'm attaching version
with TOS ordering for review.

Therefore I withdraw my endorsement for the "entry before" interpretation :)
So patch 1 is only present for review purposes, please don't apply it.

Patch 2 is good as far as I can see.  So,

	return fa in loop

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Cheers,

Regards

--
Julian Anastasov [off-list ref]

Julian Anastasov [off-list ref] wrote:

       True, but in your patch2 you return fa after
list_for_each_entry which is not valid when the loop terminates.
Just change it to return the fa into the loop.

You're right, we dereference it in fn_hash_insert.

Looks good.

Thanks,
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

I'll guess struct fib_alias should not be defined in fib_hash.c to 
support pluggable lookup algorithms.

Cheers.
						--ro

Robert Olsson [off-list ref] wrote:

I'll guess struct fib_alias should not be defined in fib_hash.c to 
support pluggable lookup algorithms.

Should one turn up then we can move it out :)
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Herbert Xu writes:
 > Robert Olsson [off-list ref] wrote:
 > > 
 > > I'll guess struct fib_alias should not be defined in fib_hash.c to 
 > > support pluggable lookup algorithms.
 > 
 > Should one turn up then we can move it out :)

 Do. :-) Seems fib_find_alias should be moved out as well.

 Cheers.

						--ro

On Mon, 27 Sep 2004 07:23:16 +1000
Herbert Xu [off-list ref] wrote:

quoted

[-- text/plain, encoding base64, charset: US-ASCII, 28 lines, name: fib_ins3.diff --]
[-- Description: fib_alias ordered by TOS --]

diff -ur v2.6.9-rc2-bk10/linux/net/ipv4/fib_hash.c linux/net/ipv4/fib_hash.c

--- v2.6.9-rc2-bk10/linux/net/ipv4/fib_hash.c   2004-09-26 16:52:11.000000000 +0300

Looks good.

To me too, thanks for describing all of this and for the
test scripts Julian.

Patch applied, thanks.

On Mon, 27 Sep 2004 13:53:33 +0200
Robert Olsson [off-list ref] wrote:

I'll guess struct fib_alias should not be defined in fib_hash.c to 
support pluggable lookup algorithms.

Yes, all the fib_alias handling can move into fib_semantics()
in fact.  I'll work on that.