Re: 2.6.11 on AMD64 traps

Re: 2.6.11 on AMD64 traps

[Andre Tomt]

[just adding netdev to CC, from LKML]

Michal Vanco wrote:
> Hello,
> 
> I see this problem running 2.6.11 on dual AMD64:
> 
> Running quagga routing daemon (ospf+bgp) and issuing "netstat -rn |wc -l" command
> while quagga tries to load more than 154000 routes from its bgp neighbours causes this trap:
> 
> Unable to handle kernel paging request at 00000000007f5c60 RIP:
> <ffffffff8041be35>{fib_get_next+181}
> PGD 3a112067 PUD 3a115067 PMD 0
> Oops: 0000 [1] SMP
> CPU 1
> Modules linked in:
> Pid: 2537, comm: netstat Not tainted 2.6.11-mv
> RIP: 0010:[<ffffffff8041be35>] <ffffffff8041be35>{fib_get_next+181}
> RSP: 0018:ffff81003a13fe90  EFLAGS: 00010206
> RAX: ffff81003a74c000 RBX: 0000000000000000 RCX: ffff81003a13ff50
> RDX: 00000000007f5c60 RSI: 0000000000000000 RDI: ffff81003a004d00
> RBP: ffff81003a13fed8 R08: ffff81003f3ff7c0 R09: 0000000000000800
> R10: 00007fffffffefe0 R11: 0000000000000246 R12: ffff810002231480
> R13: 00002aaaaab08000 R14: 0000000000000400 R15: ffff8100022314a8
> FS:  00002aaaaae00620(0000) GS:ffffffff806195c0(0000) knlGS:0000000000000000
> CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
> CR2: 00000000007f5c60 CR3: 000000003a12e000 CR4: 00000000000006e0
> Process netstat (pid: 2537, threadinfo ffff81003a13e000, task ffff81003a66a760)
> Stack: ffffffff8041bf0f ffff810002231480 ffff81003a67ac80 0000000000000000
> ffffffff8019576b 0000000000000000 ffff81003a13ff50 00002aaaaab08000
> 00000000000006f7 00000000000006f8
> Call Trace:<ffffffff8041bf0f>{fib_seq_start+63} <ffffffff8019576b>{seq_read+219}
> <ffffffff8017497f>{vfs_read+191} <ffffffff80174c53>{sys_read+83}
> <ffffffff8010d1ba>{system_call+126}
> 
> Code: 48 8b 0a 0f 18 09 48 8b 72 10 48 8b 06 0f 18 08 48 8d 42 10
> RIP <ffffffff8041be35>{fib_get_next+181} RSP <ffff81003a13fe90>
> CR2: 00000000007f5c60
> 
> I saw the same issue on 2.6.10 before. I'm not a kernel hacker but it sounds like
> locking problem. But may be I'm totally wrong in this.
> 
> michal

Re: 2.6.11 on AMD64 traps

[Patrick McHardy]

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

> Michal Vanco wrote:
>>
>> I see this problem running 2.6.11 on dual AMD64:
>>
>> Running quagga routing daemon (ospf+bgp) and issuing "netstat -rn |wc 
>> -l" command
>> while quagga tries to load more than 154000 routes from its bgp 
>> neighbours causes this trap:

This patch should fix it. The crash is caused by stale pointers,
the pointers in fib_iter_state are not reloaded after seq->stop()
followed by seq->start(pos > 0).


[-- Attachment #2: x --]
[-- Type: text/plain, Size: 1158 bytes --]

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2005/03/09 20:41:46+01:00 kaber@coreworks.de 
#   [IPV4]: Fix crash while reading /proc/net/route caused by stale pointers
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
# net/ipv4/fib_hash.c
#   2005/03/09 20:41:37+01:00 kaber@coreworks.de +11 -1
#   [IPV4]: Fix crash while reading /proc/net/route caused by stale pointers
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
diff -Nru a/net/ipv4/fib_hash.c b/net/ipv4/fib_hash.c
--- a/net/ipv4/fib_hash.c	2005-03-09 20:43:55 +01:00
+++ b/net/ipv4/fib_hash.c	2005-03-09 20:43:55 +01:00
@@ -919,13 +919,23 @@
 	return fa;
 }
 
+static struct fib_alias *fib_get_idx(struct seq_file *seq, loff_t pos)
+{
+	struct fib_alias *fa = fib_get_first(seq);
+
+	if (fa)
+		while (pos && (fa = fib_get_next(seq)))
+			--pos;
+	return pos ? NULL : fa;
+}
+
 static void *fib_seq_start(struct seq_file *seq, loff_t *pos)
 {
 	void *v = NULL;
 
 	read_lock(&fib_hash_lock);
 	if (ip_fib_main_table)
-		v = *pos ? fib_get_next(seq) : SEQ_START_TOKEN;
+		v = *pos ? fib_get_idx(seq, *pos - 1) : SEQ_START_TOKEN;
 	return v;
 }
 

Re: 2.6.11 on AMD64 traps

[Michal Vanco]

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

On Wednesday 09 March 2005 20:45, Patrick McHardy wrote:
> > Michal Vanco wrote:
> >> I see this problem running 2.6.11 on dual AMD64:
> >>
> >> Running quagga routing daemon (ospf+bgp) and issuing "netstat -rn |wc
> >> -l" command
> >> while quagga tries to load more than 154000 routes from its bgp
> >> neighbours causes this trap:
>
> This patch should fix it. The crash is caused by stale pointers,
> the pointers in fib_iter_state are not reloaded after seq->stop()
> followed by seq->start(pos > 0).

Well. Trap vanished after applying this patch, but another weird thing occurs:

# ip route show | wc -l
156033
# date; time ip route show > /dev/null; date; time netstat -rn > /dev/null
Wed Mar  9 22:15:21 CET 2005

real    0m0.656s
user    0m0.415s
sys     0m0.242s
Wed Mar  9 22:15:22 CET 2005

real    6m41.472s
user    0m1.261s
sys     6m40.143s

regards,
-- 
Ing. Michal Vančo
Network Engineer
SATRO s.r.o.
e-mail: vanco@satro.sk

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: 2.6.11 on AMD64 traps

[Patrick McHardy]

Michal Vanco wrote:
> On Wednesday 09 March 2005 20:45, Patrick McHardy wrote:
>>
>>This patch should fix it. The crash is caused by stale pointers,
>>the pointers in fib_iter_state are not reloaded after seq->stop()
>>followed by seq->start(pos > 0).
> 
> Well. Trap vanished after applying this patch, but another weird thing occurs:
> 
> # ip route show | wc -l
> 156033
> # date; time ip route show > /dev/null; date; time netstat -rn > /dev/null
> Wed Mar  9 22:15:21 CET 2005
> 
> real    0m0.656s
> user    0m0.415s
> sys     0m0.242s
> Wed Mar  9 22:15:22 CET 2005
> 
> real    6m41.472s
> user    0m1.261s
> sys     6m40.143s

Yes, I know it is totally inefficient. Just use ip route, which doesn't
suffer from this problem.

Regards
Patrick

Re: 2.6.11 on AMD64 traps

[Michal Vanco]

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

On Wednesday 09 March 2005 21:34, Patrick McHardy wrote:
> Michal Vanco wrote:
> > On Wednesday 09 March 2005 20:45, Patrick McHardy wrote:
> >>This patch should fix it. The crash is caused by stale pointers,
> >>the pointers in fib_iter_state are not reloaded after seq->stop()
> >>followed by seq->start(pos > 0).
> >
> > Well. Trap vanished after applying this patch, but another weird thing
> > occurs:
> >
> > # ip route show | wc -l
> > 156033
> > # date; time ip route show > /dev/null; date; time netstat -rn >
> > /dev/null Wed Mar  9 22:15:21 CET 2005
> >
> > real    0m0.656s
> > user    0m0.415s
> > sys     0m0.242s
> > Wed Mar  9 22:15:22 CET 2005
> >
> > real    6m41.472s
> > user    0m1.261s
> > sys     6m40.143s
>
> Yes, I know it is totally inefficient. Just use ip route, which doesn't
> suffer from this problem.
>

Sure. Can (or will) this ever be fixed to any usable state also with netstat?
Is this problem related only to AMD64?

regards,
-- 
Ing. Michal Vančo
Network Engineer
SATRO s.r.o.
e-mail: vanco@satro.sk

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: 2.6.11 on AMD64 traps

[Patrick McHardy]

Michal Vanco wrote:
> On Wednesday 09 March 2005 21:34, Patrick McHardy wrote:
>>
>>Yes, I know it is totally inefficient. Just use ip route, which doesn't
>>suffer from this problem.
> 
> Sure. Can (or will) this ever be fixed to any usable state also with netstat?
> Is this problem related only to AMD64?

Maybe. To start dumping entries of an open hashed hash-table at a
specific position we need to skip all entries before that position by
walking over them. This results in quadratic time complexity. It might
be possible to improve this by cacheing the last position in
fib_iter_state even between ->stop() and ->start() calls and using
generation IDs for invalidation.

Regards
Patrick

Re: 2.6.11 on AMD64 traps

[Michal Vanco]

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

On Wednesday 09 March 2005 22:05, Patrick McHardy wrote:
> Michal Vanco wrote:
> > On Wednesday 09 March 2005 21:34, Patrick McHardy wrote:
> >>Yes, I know it is totally inefficient. Just use ip route, which doesn't
> >>suffer from this problem.
> >
> > Sure. Can (or will) this ever be fixed to any usable state also with
> > netstat? Is this problem related only to AMD64?
>
> Maybe. To start dumping entries of an open hashed hash-table at a
> specific position we need to skip all entries before that position by
> walking over them. This results in quadratic time complexity. It might
> be possible to improve this by cacheing the last position in
> fib_iter_state even between ->stop() and ->start() calls and using
> generation IDs for invalidation.
>

Ok. Thank's for help.

regards,
Michal

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: 2.6.11 on AMD64 traps

[Patrick McHardy]

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

Michal Vanco wrote:
> On Wednesday 09 March 2005 22:05, Patrick McHardy wrote:
> 
>>>Sure. Can (or will) this ever be fixed to any usable state also with
>>>netstat? Is this problem related only to AMD64?
>>
>>Maybe. To start dumping entries of an open hashed hash-table at a
>>specific position we need to skip all entries before that position by
>>walking over them. This results in quadratic time complexity. It might
>>be possible to improve this by cacheing the last position in
>>fib_iter_state even between ->stop() and ->start() calls and using
>>generation IDs for invalidation.

And here it is. Could you redo your timing-test with this patch please?

Thanks
Patrick


[-- Attachment #2: x --]
[-- Type: text/plain, Size: 3012 bytes --]

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2005/03/10 00:07:21+01:00 kaber@coreworks.de 
#   [IPV4]: Speed up sequential reading of /proc/net/route
#   
#   Cacheing the current position reduces complexity from O(n^2)
#   to O(n).
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
# net/ipv4/fib_hash.c
#   2005/03/10 00:07:11+01:00 kaber@coreworks.de +22 -1
#   [IPV4]: Speed up sequential reading of /proc/net/route
#   
#   Cacheing the current position reduces complexity from O(n^2)
#   to O(n).
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
diff -Nru a/net/ipv4/fib_hash.c b/net/ipv4/fib_hash.c
--- a/net/ipv4/fib_hash.c	2005-03-10 00:07:43 +01:00
+++ b/net/ipv4/fib_hash.c	2005-03-10 00:07:43 +01:00
@@ -93,6 +93,7 @@
 }
 
 static DEFINE_RWLOCK(fib_hash_lock);
+static unsigned int fib_hash_genid;
 
 #define FZ_MAX_DIVISOR ((PAGE_SIZE<<MAX_ORDER) / sizeof(struct hlist_head))
 
@@ -181,6 +182,7 @@
 		fz->fz_hashmask = new_hashmask;
 		fz->fz_divisor = new_divisor;
 		fn_rebuild_zone(fz, old_ht, old_divisor);
+		fib_hash_genid++;
 		write_unlock_bh(&fib_hash_lock);
 
 		fz_hash_free(old_ht, old_divisor);
@@ -236,6 +238,7 @@
 		table->fn_zones[i]->fz_next = fz;
 	}
 	table->fn_zones[z] = fz;
+	fib_hash_genid++;
 	write_unlock_bh(&fib_hash_lock);
 	return fz;
 }
@@ -451,6 +454,7 @@
 			fa->fa_scope = r->rtm_scope;
 			state = fa->fa_state;
 			fa->fa_state &= ~FA_S_ACCESSED;
+			fib_hash_genid++;
 			write_unlock_bh(&fib_hash_lock);
 
 			fib_release_info(fi_drop);
@@ -515,6 +519,7 @@
 		fib_insert_node(fz, new_f);
 	list_add_tail(&new_fa->fa_list,
 		 (fa ? &fa->fa_list : &f->fn_alias));
+	fib_hash_genid++;
 	write_unlock_bh(&fib_hash_lock);
 
 	if (new_f)
@@ -600,6 +605,7 @@
 			hlist_del(&f->fn_hash);
 			kill_fn = 1;
 		}
+		fib_hash_genid++;
 		write_unlock_bh(&fib_hash_lock);
 
 		if (fa->fa_state & FA_S_ACCESSED)
@@ -637,6 +643,7 @@
 					hlist_del(&f->fn_hash);
 					kill_f = 1;
 				}
+				fib_hash_genid++;
 				write_unlock_bh(&fib_hash_lock);
 
 				fn_free_alias(fa);
@@ -801,6 +808,9 @@
 	struct hlist_head *hash_head;
 	struct fib_node *fn;
 	struct fib_alias *fa;
+	loff_t pos;
+	unsigned int genid;
+	int valid;
 };
 
 static struct fib_alias *fib_get_first(struct seq_file *seq)
@@ -812,6 +822,9 @@
 	iter->hash_head = NULL;
 	iter->fn        = NULL;
 	iter->fa        = NULL;
+	iter->pos	= 0;
+	iter->genid	= fib_hash_genid;
+	iter->valid	= 1;
 
 	for (iter->zone = table->fn_zone_list; iter->zone;
 	     iter->zone = iter->zone->fz_next) {
@@ -916,12 +929,20 @@
 		}
 	}
 out:
+	iter->pos++;
 	return fa;
 }
 
 static struct fib_alias *fib_get_idx(struct seq_file *seq, loff_t pos)
 {
-	struct fib_alias *fa = fib_get_first(seq);
+	struct fib_iter_state *iter = seq->private;
+	struct fib_alias *fa;
+	
+	if (iter->valid && pos >= iter->pos && iter->genid == fib_hash_genid) {
+		fa   = iter->fa;
+		pos -= iter->pos;
+	} else
+		fa = fib_get_first(seq);
 
 	if (fa)
 		while (pos && (fa = fib_get_next(seq)))

Re: 2.6.11 on AMD64 traps

[Michal Vanco]

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

On Thursday 10 March 2005 00:27, Patrick McHardy wrote:
> Michal Vanco wrote:
> > On Wednesday 09 March 2005 22:05, Patrick McHardy wrote:
> >>>Sure. Can (or will) this ever be fixed to any usable state also with
> >>>netstat? Is this problem related only to AMD64?
> >>
> >>Maybe. To start dumping entries of an open hashed hash-table at a
> >>specific position we need to skip all entries before that position by
> >>walking over them. This results in quadratic time complexity. It might
> >>be possible to improve this by cacheing the last position in
> >>fib_iter_state even between ->stop() and ->start() calls and using
> >>generation IDs for invalidation.
>
> And here it is. Could you redo your timing-test with this patch please?

Wonderfull:

# time ip route show | wc -l; time netstat -rn | wc -l
155991

real    0m1.110s
user    0m0.441s
sys     0m1.100s
155991

real    0m1.435s
user    0m1.026s
sys     0m0.436s

It seems that netlink is still little bit faster than /proc, but it doesn't 
make any sense in case like this.
Will this patch be included in future kernels?

Great job. Thank you for help.

Best regards,
-- 
Ing. Michal Vančo
Network Engineer
SATRO s.r.o.
e-mail: vanco@satro.sk

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: 2.6.11 on AMD64 traps

[Patrick McHardy]

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

Michal Vanco wrote:
> On Thursday 10 March 2005 00:27, Patrick McHardy wrote:
> 
>>And here it is. Could you redo your timing-test with this patch please?
> 
> Wonderfull:
> 
> # time ip route show | wc -l; time netstat -rn | wc -l
> 155991
> 
> real    0m1.110s
> user    0m0.441s
> sys     0m1.100s
> 155991
> 
> real    0m1.435s
> user    0m1.026s
> sys     0m0.436s
> 
> It seems that netlink is still little bit faster than /proc, but it doesn't 
> make any sense in case like this.

The system time is higher with netlink. It also repeatedly needs to
skip over the entries, its just not as bad as with seq_file because
more entries are dumped at once. dumping over netlink could be improved
in a simlar way, but there is no room in netlink_callback->args for the
pointers and the genid.

> Will this patch be included in future kernels?

I hope so. Dave, are you fine with making /proc more efficient than
netlink ? :)

Regards
Patrick

[-- Attachment #2: x --]
[-- Type: text/plain, Size: 3012 bytes --]

# This is a BitKeeper generated diff -Nru style patch.
#
# ChangeSet
#   2005/03/10 00:07:21+01:00 kaber@coreworks.de 
#   [IPV4]: Speed up sequential reading of /proc/net/route
#   
#   Cacheing the current position reduces complexity from O(n^2)
#   to O(n).
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
# net/ipv4/fib_hash.c
#   2005/03/10 00:07:11+01:00 kaber@coreworks.de +22 -1
#   [IPV4]: Speed up sequential reading of /proc/net/route
#   
#   Cacheing the current position reduces complexity from O(n^2)
#   to O(n).
#   
#   Signed-off-by: Patrick McHardy <kaber@trash.net>
# 
diff -Nru a/net/ipv4/fib_hash.c b/net/ipv4/fib_hash.c
--- a/net/ipv4/fib_hash.c	2005-03-10 00:07:43 +01:00
+++ b/net/ipv4/fib_hash.c	2005-03-10 00:07:43 +01:00
@@ -93,6 +93,7 @@
 }
 
 static DEFINE_RWLOCK(fib_hash_lock);
+static unsigned int fib_hash_genid;
 
 #define FZ_MAX_DIVISOR ((PAGE_SIZE<<MAX_ORDER) / sizeof(struct hlist_head))
 
@@ -181,6 +182,7 @@
 		fz->fz_hashmask = new_hashmask;
 		fz->fz_divisor = new_divisor;
 		fn_rebuild_zone(fz, old_ht, old_divisor);
+		fib_hash_genid++;
 		write_unlock_bh(&fib_hash_lock);
 
 		fz_hash_free(old_ht, old_divisor);
@@ -236,6 +238,7 @@
 		table->fn_zones[i]->fz_next = fz;
 	}
 	table->fn_zones[z] = fz;
+	fib_hash_genid++;
 	write_unlock_bh(&fib_hash_lock);
 	return fz;
 }
@@ -451,6 +454,7 @@
 			fa->fa_scope = r->rtm_scope;
 			state = fa->fa_state;
 			fa->fa_state &= ~FA_S_ACCESSED;
+			fib_hash_genid++;
 			write_unlock_bh(&fib_hash_lock);
 
 			fib_release_info(fi_drop);
@@ -515,6 +519,7 @@
 		fib_insert_node(fz, new_f);
 	list_add_tail(&new_fa->fa_list,
 		 (fa ? &fa->fa_list : &f->fn_alias));
+	fib_hash_genid++;
 	write_unlock_bh(&fib_hash_lock);
 
 	if (new_f)
@@ -600,6 +605,7 @@
 			hlist_del(&f->fn_hash);
 			kill_fn = 1;
 		}
+		fib_hash_genid++;
 		write_unlock_bh(&fib_hash_lock);
 
 		if (fa->fa_state & FA_S_ACCESSED)
@@ -637,6 +643,7 @@
 					hlist_del(&f->fn_hash);
 					kill_f = 1;
 				}
+				fib_hash_genid++;
 				write_unlock_bh(&fib_hash_lock);
 
 				fn_free_alias(fa);
@@ -801,6 +808,9 @@
 	struct hlist_head *hash_head;
 	struct fib_node *fn;
 	struct fib_alias *fa;
+	loff_t pos;
+	unsigned int genid;
+	int valid;
 };
 
 static struct fib_alias *fib_get_first(struct seq_file *seq)
@@ -812,6 +822,9 @@
 	iter->hash_head = NULL;
 	iter->fn        = NULL;
 	iter->fa        = NULL;
+	iter->pos	= 0;
+	iter->genid	= fib_hash_genid;
+	iter->valid	= 1;
 
 	for (iter->zone = table->fn_zone_list; iter->zone;
 	     iter->zone = iter->zone->fz_next) {
@@ -916,12 +929,20 @@
 		}
 	}
 out:
+	iter->pos++;
 	return fa;
 }
 
 static struct fib_alias *fib_get_idx(struct seq_file *seq, loff_t pos)
 {
-	struct fib_alias *fa = fib_get_first(seq);
+	struct fib_iter_state *iter = seq->private;
+	struct fib_alias *fa;
+	
+	if (iter->valid && pos >= iter->pos && iter->genid == fib_hash_genid) {
+		fa   = iter->fa;
+		pos -= iter->pos;
+	} else
+		fa = fib_get_first(seq);
 
 	if (fa)
 		while (pos && (fa = fib_get_next(seq)))

Re: 2.6.11 on AMD64 traps

[David S. Miller]

On Thu, 10 Mar 2005 00:57:56 +0100
Patrick McHardy <kaber@trash.net> wrote:

> > Will this patch be included in future kernels?
> 
> I hope so. Dave, are you fine with making /proc more efficient than
> netlink ? :)

No objection :-)  I'll hit this on my next pass over my 2.6.x
backlog which should start tonight.

Re: 2.6.11 on AMD64 traps

[David S. Miller]

On Wed, 09 Mar 2005 20:45:35 +0100
Patrick McHardy <kaber@trash.net> wrote:

> > Michal Vanco wrote:
> >>
> >> I see this problem running 2.6.11 on dual AMD64:
> >>
> >> Running quagga routing daemon (ospf+bgp) and issuing "netstat -rn |wc 
> >> -l" command
> >> while quagga tries to load more than 154000 routes from its bgp 
> >> neighbours causes this trap:
> 
> This patch should fix it. The crash is caused by stale pointers,
> the pointers in fib_iter_state are not reloaded after seq->stop()
> followed by seq->start(pos > 0).

Applied, thanks Patrick.