Move fib_alias out of fib_hash.c

Move fib_alias out of fib_hash.c

[David S. Miller]

[-- Attachment #1: Type: text/plain, Size: 333 bytes --]


Ok, this begins the movement of fib_alias object handling
out of fib_hash.c  The idea is to make fib_hash.c purely
a longest-matching-prefix lookup implementation.

Look at fn_hash_lookup() after these changes, and you'll
get an idea of how I want the whole fib_hash.c file to look
in the end.

I'll work on insert/delete tomorrow.

[-- Attachment #2: diff1 --]
[-- Type: application/octet-stream, Size: 2922 bytes --]

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2004/09/28 20:49:52-07:00 davem@nuts.davemloft.net 
#   [IPV4]: Define fib_alias in new header fib_lookup.h
#   
#   Also s/FN_S_ACCESSED/FA_S_ACCESSED/
#   
#   Signed-off-by: David S. Miller <davem@davemloft.net>
# 
# net/ipv4/fib_hash.c
#   2004/09/28 20:49:13-07:00 davem@nuts.davemloft.net +7 -16
#   [IPV4]: Define fib_alias in new header fib_lookup.h
# 
# net/ipv4/fib_lookup.h
#   2004/09/28 20:49:07-07:00 davem@nuts.davemloft.net +19 -0
#   [IPV4]: Define fib_alias in new header fib_lookup.h
# 
# net/ipv4/fib_lookup.h
#   2004/09/28 20:49:07-07:00 davem@nuts.davemloft.net +0 -0
#   BitKeeper file /disk1/BK/net-2.6/net/ipv4/fib_lookup.h
# 
diff -Nru a/net/ipv4/fib_hash.c b/net/ipv4/fib_hash.c
--- a/net/ipv4/fib_hash.c	2004-09-28 21:24:46 -07:00
+++ b/net/ipv4/fib_hash.c	2004-09-28 21:24:46 -07:00
@@ -43,6 +43,8 @@
 #include <net/sock.h>
 #include <net/ip_fib.h>
 
+#include "fib_lookup.h"
+
 static kmem_cache_t *fn_hash_kmem;
 static kmem_cache_t *fn_alias_kmem;
 
@@ -52,17 +54,6 @@
 	u32			fn_key;
 };
 
-struct fib_alias {
-	struct list_head	fa_list;
-	struct fib_info		*fa_info;
-	u8			fa_tos;
-	u8			fa_type;
-	u8			fa_scope;
-	u8			fa_state;
-};
-
-#define FN_S_ACCESSED	1
-
 struct fn_zone {
 	struct fn_zone		*fz_next;	/* Next not empty zone	*/
 	struct hlist_head	*fz_hash;	/* Hash table pointer	*/
@@ -277,7 +268,7 @@
 				if (fa->fa_scope < flp->fl4_scope)
 					continue;
 
-				fa->fa_state |= FN_S_ACCESSED;
+				fa->fa_state |= FA_S_ACCESSED;
 
 				err = fib_semantic_match(fa->fa_type,
 							 fa->fa_info,
@@ -358,7 +349,7 @@
 			if (!next_fi->fib_nh[0].nh_gw ||
 			    next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
 				continue;
-			fa->fa_state |= FN_S_ACCESSED;
+			fa->fa_state |= FA_S_ACCESSED;
 
 			if (fi == NULL) {
 				if (next_fi != res->fi)
@@ -521,11 +512,11 @@
 			fa->fa_type = type;
 			fa->fa_scope = r->rtm_scope;
 			state = fa->fa_state;
-			fa->fa_state &= ~FN_S_ACCESSED;
+			fa->fa_state &= ~FA_S_ACCESSED;
 			write_unlock_bh(&fib_hash_lock);
 
 			fib_release_info(fi_drop);
-			if (state & FN_S_ACCESSED)
+			if (state & FA_S_ACCESSED)
 				rt_cache_flush(-1);
 			return 0;
 		}
@@ -669,7 +660,7 @@
 		}
 		write_unlock_bh(&fib_hash_lock);
 
-		if (fa->fa_state & FN_S_ACCESSED)
+		if (fa->fa_state & FA_S_ACCESSED)
 			rt_cache_flush(-1);
 		fn_free_alias(fa);
 		if (kill_fn) {
diff -Nru a/net/ipv4/fib_lookup.h b/net/ipv4/fib_lookup.h
--- /dev/null	Wed Dec 31 16:00:00 196900
+++ b/net/ipv4/fib_lookup.h	2004-09-28 21:24:46 -07:00
@@ -0,0 +1,19 @@
+#ifndef _FIB_LOOKUP_H
+#define _FIB_LOOKUP_H
+
+#include <linux/types.h>
+#include <linux/list.h>
+#include <net/ip_fib.h>
+
+struct fib_alias {
+	struct list_head	fa_list;
+	struct fib_info		*fa_info;
+	u8			fa_tos;
+	u8			fa_type;
+	u8			fa_scope;
+	u8			fa_state;
+};
+
+#define FA_S_ACCESSED	0x01
+
+#endif /* _FIB_LOOKUP_H */

[-- Attachment #3: diff2 --]
[-- Type: application/octet-stream, Size: 3403 bytes --]

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2004/09/28 20:59:05-07:00 davem@nuts.davemloft.net 
#   [IPV4]: Move some fib_semantics exports into fib_lookup.h
#   
#   Signed-off-by: David S. Miller <davem@davemloft.net>
# 
# net/ipv4/fib_semantics.c
#   2004/09/28 20:58:33-07:00 davem@nuts.davemloft.net +2 -0
#   [IPV4]: Move some fib_semantics exports into fib_lookup.h
# 
# net/ipv4/fib_lookup.h
#   2004/09/28 20:58:33-07:00 davem@nuts.davemloft.net +14 -0
#   [IPV4]: Move some fib_semantics exports into fib_lookup.h
# 
# include/net/ip_fib.h
#   2004/09/28 20:58:33-07:00 davem@nuts.davemloft.net +1 -12
#   [IPV4]: Move some fib_semantics exports into fib_lookup.h
# 
diff -Nru a/include/net/ip_fib.h b/include/net/ip_fib.h
--- a/include/net/ip_fib.h	2004-09-28 21:25:03 -07:00
+++ b/include/net/ip_fib.h	2004-09-28 21:25:03 -07:00
@@ -210,22 +210,11 @@
 extern void fib_select_multipath(const struct flowi *flp, struct fib_result *res);
 
 /* Exported by fib_semantics.c */
-extern int 		ip_fib_check_default(u32 gw, struct net_device *dev);
-extern void		fib_release_info(struct fib_info *);
-extern int		fib_semantic_match(int type, struct fib_info *,
-					   const struct flowi *, struct fib_result*);
-extern struct fib_info	*fib_create_info(const struct rtmsg *r, struct kern_rta *rta,
-					 const struct nlmsghdr *, int *err);
-extern int fib_nh_match(struct rtmsg *r, struct nlmsghdr *, struct kern_rta *rta, struct fib_info *fi);
-extern int fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
-			 u8 tb_id, u8 type, u8 scope, void *dst, int dst_len, u8 tos,
-			 struct fib_info *fi);
+extern int ip_fib_check_default(u32 gw, struct net_device *dev);
 extern int fib_sync_down(u32 local, struct net_device *dev, int force);
 extern int fib_sync_up(struct net_device *dev);
 extern int fib_convert_rtentry(int cmd, struct nlmsghdr *nl, struct rtmsg *rtm,
 			       struct kern_rta *rta, struct rtentry *r);
-extern void fib_node_seq_show(struct seq_file *seq, int type, int dead,
-			      struct fib_info *fi, u32 prefix, u32 mask);
 extern u32  __fib_res_prefsrc(struct fib_result *res);
 
 /* Exported by fib_hash.c */
diff -Nru a/net/ipv4/fib_lookup.h b/net/ipv4/fib_lookup.h
--- a/net/ipv4/fib_lookup.h	2004-09-28 21:25:03 -07:00
+++ b/net/ipv4/fib_lookup.h	2004-09-28 21:25:03 -07:00
@@ -16,4 +16,18 @@
 
 #define FA_S_ACCESSED	0x01
 
+/* Exported by fib_semantics.c */
+extern int fib_semantic_match(int type, struct fib_info *,
+			      const struct flowi *, struct fib_result *);
+extern void fib_release_info(struct fib_info *);
+extern struct fib_info *fib_create_info(const struct rtmsg *r,
+					struct kern_rta *rta,
+					const struct nlmsghdr *,
+					int *err);
+extern int fib_nh_match(struct rtmsg *r, struct nlmsghdr *,
+			struct kern_rta *rta, struct fib_info *fi);
+extern int fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
+			 u8 tb_id, u8 type, u8 scope, void *dst,
+			 int dst_len, u8 tos, struct fib_info *fi);
+
 #endif /* _FIB_LOOKUP_H */
diff -Nru a/net/ipv4/fib_semantics.c b/net/ipv4/fib_semantics.c
--- a/net/ipv4/fib_semantics.c	2004-09-28 21:25:03 -07:00
+++ b/net/ipv4/fib_semantics.c	2004-09-28 21:25:03 -07:00
@@ -43,6 +43,8 @@
 #include <net/sock.h>
 #include <net/ip_fib.h>
 
+#include "fib_lookup.h"
+
 #define FSprintk(a...)
 
 static rwlock_t fib_info_lock = RW_LOCK_UNLOCKED;

[-- Attachment #4: diff3 --]
[-- Type: application/octet-stream, Size: 4880 bytes --]

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2004/09/28 21:23:40-07:00 davem@nuts.davemloft.net 
#   [IPV4]: Do fib_alias lookup walk directly in fib_semantic_match().
#   
#   Signed-off-by: David S. Miller <davem@davemloft.net>
# 
# net/ipv4/fib_semantics.c
#   2004/09/28 21:23:07-07:00 davem@nuts.davemloft.net +60 -38
#   [IPV4]: Do fib_alias lookup walk directly in fib_semantic_match().
# 
# net/ipv4/fib_lookup.h
#   2004/09/28 21:23:07-07:00 davem@nuts.davemloft.net +3 -2
#   [IPV4]: Do fib_alias lookup walk directly in fib_semantic_match().
# 
# net/ipv4/fib_hash.c
#   2004/09/28 21:23:07-07:00 davem@nuts.davemloft.net +5 -23
#   [IPV4]: Do fib_alias lookup walk directly in fib_semantic_match().
# 
diff -Nru a/net/ipv4/fib_hash.c b/net/ipv4/fib_hash.c
--- a/net/ipv4/fib_hash.c	2004-09-28 21:25:20 -07:00
+++ b/net/ipv4/fib_hash.c	2004-09-28 21:25:20 -07:00
@@ -256,32 +256,14 @@
 
 		head = &fz->fz_hash[fn_hash(k, fz)];
 		hlist_for_each_entry(f, node, head, fn_hash) {
-			struct fib_alias *fa;
-
 			if (f->fn_key != k)
 				continue;
 
-			list_for_each_entry(fa, &f->fn_alias, fa_list) {
-				if (fa->fa_tos &&
-				    fa->fa_tos != flp->fl4_tos)
-					continue;
-				if (fa->fa_scope < flp->fl4_scope)
-					continue;
-
-				fa->fa_state |= FA_S_ACCESSED;
-
-				err = fib_semantic_match(fa->fa_type,
-							 fa->fa_info,
-							 flp, res);
-				if (err == 0) {
-					res->type = fa->fa_type;
-					res->scope = fa->fa_scope;
-					res->prefixlen = fz->fz_order;
-					goto out;
-				}
-				if (err < 0)
-					goto out;
-			}
+			err = fib_semantic_match(&f->fn_alias,
+						 flp, res,
+						 fz->fz_order);
+			if (err <= 0)
+				goto out;
 		}
 	}
 	err = 1;
diff -Nru a/net/ipv4/fib_lookup.h b/net/ipv4/fib_lookup.h
--- a/net/ipv4/fib_lookup.h	2004-09-28 21:25:20 -07:00
+++ b/net/ipv4/fib_lookup.h	2004-09-28 21:25:20 -07:00
@@ -17,8 +17,9 @@
 #define FA_S_ACCESSED	0x01
 
 /* Exported by fib_semantics.c */
-extern int fib_semantic_match(int type, struct fib_info *,
-			      const struct flowi *, struct fib_result *);
+extern int fib_semantic_match(struct list_head *head,
+			      const struct flowi *flp,
+			      struct fib_result *res, int prefixlen);
 extern void fib_release_info(struct fib_info *);
 extern struct fib_info *fib_create_info(const struct rtmsg *r,
 					struct kern_rta *rta,
diff -Nru a/net/ipv4/fib_semantics.c b/net/ipv4/fib_semantics.c
--- a/net/ipv4/fib_semantics.c	2004-09-28 21:25:20 -07:00
+++ b/net/ipv4/fib_semantics.c	2004-09-28 21:25:20 -07:00
@@ -760,51 +760,73 @@
 	return NULL;
 }
 
-int 
-fib_semantic_match(int type, struct fib_info *fi, const struct flowi *flp, struct fib_result *res)
+int fib_semantic_match(struct list_head *head, const struct flowi *flp,
+		       struct fib_result *res, int prefixlen)
 {
-	int err = fib_props[type].error;
+	struct fib_alias *fa;
+	int nh_sel = 0;
 
-	if (err == 0) {
-		if (fi->fib_flags&RTNH_F_DEAD)
-			return 1;
-
-		res->fi = fi;
-
-		switch (type) {
-		case RTN_UNICAST:
-		case RTN_LOCAL:
-		case RTN_BROADCAST:
-		case RTN_ANYCAST:
-		case RTN_MULTICAST:
-			for_nexthops(fi) {
-				if (nh->nh_flags&RTNH_F_DEAD)
-					continue;
-				if (!flp->oif || flp->oif == nh->nh_oif)
-					break;
-			}
+	list_for_each_entry(fa, head, fa_list) {
+		int err;
+
+		if (fa->fa_tos &&
+		    fa->fa_tos != flp->fl4_tos)
+			continue;
+
+		if (fa->fa_scope < flp->fl4_scope)
+			continue;
+
+		fa->fa_state |= FA_S_ACCESSED;
+
+		err = fib_props[fa->fa_type].error;
+		if (err == 0) {
+			struct fib_info *fi = fa->fa_info;
+
+			if (fi->fib_flags & RTNH_F_DEAD)
+				continue;
+
+			switch (fa->fa_type) {
+			case RTN_UNICAST:
+			case RTN_LOCAL:
+			case RTN_BROADCAST:
+			case RTN_ANYCAST:
+			case RTN_MULTICAST:
+				for_nexthops(fi) {
+					if (nh->nh_flags&RTNH_F_DEAD)
+						continue;
+					if (!flp->oif || flp->oif == nh->nh_oif)
+						break;
+				}
 #ifdef CONFIG_IP_ROUTE_MULTIPATH
-			if (nhsel < fi->fib_nhs) {
-				res->nh_sel = nhsel;
-				atomic_inc(&fi->fib_clntref);
-				return 0;
-			}
+				if (nhsel < fi->fib_nhs) {
+					nh_sel = nhsel;
+					goto out_fill_res;
+				}
 #else
-			if (nhsel < 1) {
-				atomic_inc(&fi->fib_clntref);
-				return 0;
-			}
+				if (nhsel < 1) {
+					goto out_fill_res;
+				}
 #endif
-			endfor_nexthops(fi);
-			res->fi = NULL;
-			return 1;
-		default:
-			res->fi = NULL;
-			printk(KERN_DEBUG "impossible 102\n");
-			return -EINVAL;
+				endfor_nexthops(fi);
+				continue;
+
+			default:
+				printk(KERN_DEBUG "impossible 102\n");
+				return -EINVAL;
+			};
 		}
+		return err;
 	}
-	return err;
+	return 1;
+
+out_fill_res:
+	res->prefixlen = prefixlen;
+	res->nh_sel = nh_sel;
+	res->type = fa->fa_type;
+	res->scope = fa->fa_scope;
+	res->fi = fa->fa_info;
+	atomic_inc(&res->fi->fib_clntref);
+	return 0;
 }
 
 /* Find appropriate source address to this destination */

Move fib_alias out of fib_hash.c

[Robert Olsson]

David S. Miller writes:
 > 
 > Ok, this begins the movement of fib_alias object handling
 > out of fib_hash.c  The idea is to make fib_hash.c purely
 > a longest-matching-prefix lookup implementation.
 > 
 > Look at fn_hash_lookup() after these changes, and you'll
 > get an idea of how I want the whole fib_hash.c file to look
 > in the end.


Exactly,
  we can interface new lookups cleanly. For a trie something like:

static int
fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
{
	struct trie *t = (struct trie *) tb->tb_data;
	struct list_head *fah=NULL;
	int err=1, plen, r;

	r = trie_pfx_get(t, flp->fl4_dst, &fah, &plen);

	if (r && fah) 
		err = fib_semantic_match(fah,
					 flp, res,
					 plen);
	return err;
}



Cheers.
						--ro

Re: Move fib_alias out of fib_hash.c

[David S. Miller]

On Wed, 29 Sep 2004 17:20:45 +0200
Robert Olsson <Robert.Olsson@data.slu.se> wrote:

>   we can interface new lookups cleanly. For a trie something like:

You are already making a critical logic error.

You cannot find the longest matching prefix and just use that.

Rather, you must iterate through all matching prefixes in the
table from longest to shortest, trying fib_semantic_match() on
each one until it says OK.

If you don't do that, then you're not providing the same behavior
of the current code.  If next hops go down, you have to try the
next longest matching prefix and so on and so forth.  It can also
be the case that the longest matching prefix entry has no matching
TOS key, whereas a shorter prefix does.

This makes using a new algorithm very non-trivial.

Probably what you should do is keep an array on the function
stack, recording shorter prefix entries you see on your walk
down to the longest matching prefix.  Then you process the array
one entry at a time back to the root, trying fib_semantic_match()
on each one.

Re: Move fib_alias out of fib_hash.c

[Steven Blake]

On Wed, 2004-09-29 at 15:53, David S. Miller wrote:

> On Wed, 29 Sep 2004 17:20:45 +0200
> Robert Olsson <Robert.Olsson@data.slu.se> wrote:
> 
> >   we can interface new lookups cleanly. For a trie something like:
> 
> You are already making a critical logic error.
> 
> You cannot find the longest matching prefix and just use that.
> 
> Rather, you must iterate through all matching prefixes in the
> table from longest to shortest, trying fib_semantic_match() on
> each one until it says OK.
> 
> If you don't do that, then you're not providing the same behavior
> of the current code.  If next hops go down, you have to try the
> next longest matching prefix and so on and so forth.

I'm not criticizing the current design, but it is very typical of
routers to put the burden of fixing up the FIB in the event of a
next-hop state change on the routing daemon, and not the dataplane.
Which is one reason why having a FIB datastructure that can be updated
very efficiently is important.

> It can also
> be the case that the longest matching prefix entry has no matching
> TOS key, whereas a shorter prefix does.

No routing protocols are distributing TOS-specific routes, and there is
no prospect of that feature ever coming back.  Why pay the cost of
matching TOS on every packet forwarded?


Regards,

// Steve

Re: Move fib_alias out of fib_hash.c

[David S. Miller]

On Wed, 29 Sep 2004 17:20:43 -0400
Steven Blake <slblake@petri-meat.com> wrote:

> > It can also
> > be the case that the longest matching prefix entry has no matching
> > TOS key, whereas a shorter prefix does.
> 
> No routing protocols are distributing TOS-specific routes, and there is
> no prospect of that feature ever coming back.  Why pay the cost of
> matching TOS on every packet forwarded?

Because once we add functionality to the kernel we can't simply
rip it out.  People do use TOS routing, via static routes or
similar.

Re: Move fib_alias out of fib_hash.c

[Andi Kleen]

On Wed, Sep 29, 2004 at 02:27:50PM -0700, David S. Miller wrote:
> On Wed, 29 Sep 2004 17:20:43 -0400
> Steven Blake <slblake@petri-meat.com> wrote:
> 
> > > It can also
> > > be the case that the longest matching prefix entry has no matching
> > > TOS key, whereas a shorter prefix does.
> > 
> > No routing protocols are distributing TOS-specific routes, and there is
> > no prospect of that feature ever coming back.  Why pay the cost of
> > matching TOS on every packet forwarded?
> 
> Because once we add functionality to the kernel we can't simply
> rip it out.  People do use TOS routing, via static routes or
> similar.

I'm not so sure anybody uses it really. How about adding a printk for it 
and seeing if anybody complains? 

-Andi

Re: Move fib_alias out of fib_hash.c

[Ben Greear]

Andi Kleen wrote:
> On Wed, Sep 29, 2004 at 02:27:50PM -0700, David S. Miller wrote:

>>Because once we add functionality to the kernel we can't simply
>>rip it out.  People do use TOS routing, via static routes or
>>similar.
> 
> 
> I'm not so sure anybody uses it really. How about adding a printk for it 
> and seeing if anybody complains? 

I don't think you should remove existing features in the middle of a stable
release cycle.  If you want to have a compile option, that defaults to off,
allows some new algorithm, then that sounds more reasonable...

And I don't think the majority of people would see the printk untill way
too late.

Ben

-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: Move fib_alias out of fib_hash.c

[Andi Kleen]

On Wed, Sep 29, 2004 at 03:24:55PM -0700, Ben Greear wrote:
> Andi Kleen wrote:
> >On Wed, Sep 29, 2004 at 02:27:50PM -0700, David S. Miller wrote:
> 
> >>Because once we add functionality to the kernel we can't simply
> >>rip it out.  People do use TOS routing, via static routes or
> >>similar.
> >
> >
> >I'm not so sure anybody uses it really. How about adding a printk for it 
> >and seeing if anybody complains? 
> 
> I don't think you should remove existing features in the middle of a stable
> release cycle.  If you want to have a compile option, that defaults to off,


There is no stable release cycle anymore. Linus has abolished that.

Maybe we will get it back at some point if the current way doesn't
work out, but currently it's unlimited hacking time.

> And I don't think the majority of people would see the printk untill way
> too late.

That was always the case, nothing new.

-Andi

Re: Move fib_alias out of fib_hash.c

[Ben Greear]

Andi Kleen wrote:

> There is no stable release cycle anymore. Linus has abolished that.
> 
> Maybe we will get it back at some point if the current way doesn't
> work out, but currently it's unlimited hacking time.

Sounds fun for the programmers and a pain in the ass for everyone
else.  But, maybe I can shove some of my patches into the tree with
less friction!

Ben

-- 
Ben Greear <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: Move fib_alias out of fib_hash.c

[Robert Olsson]

Steven Blake writes:

 > No routing protocols are distributing TOS-specific routes, and there is
 > no prospect of that feature ever coming back.  Why pay the cost of
 > matching TOS on every packet forwarded?

 Well you may be right but with a pluggable lookup algo we could choose
 between TOS-capable/complex and more lightweight and speedy things.

 Cheers.
						--ro

Re: Move fib_alias out of fib_hash.c

[Robert Olsson]

David S. Miller writes:

 > You cannot find the longest matching prefix and just use that.
 > 
 > Rather, you must iterate through all matching prefixes in the
 > table from longest to shortest, trying fib_semantic_match() on
 > each one until it says OK.

 You're right we have to match semantics then first after that return 
 longest prefix to comply w. current matching.


 > This makes using a new algorithm very non-trivial.

 Yes and will take resources compared to simple longest prefix.

 > Probably what you should do is keep an array on the function
 > stack, recording shorter prefix entries you see on your walk
 > down to the longest matching prefix.  Then you process the array
 > one entry at a time back to the root, trying fib_semantic_match()
 > on each one.

 We have backtracking as we search to leaves and as leaves does not 
 always has a matching prefix.  So we have to look into how semantics 
 match can be done here instead and backtrack until we got a semantics 
 match. Was about to test w. ipv6 to start with due to ipv4 complexity.
 Anyway ipv4 fib-code is cleaner now.

 Cheers.
						--ro