[PATCH, RFC] RCU : OOM avoidance and lower latency

[PATCH, RFC] RCU : OOM avoidance and lower latency

[Eric Dumazet]

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


In order to avoid some OOM triggered by a flood of call_rcu() calls, we 
increased in linux 2.6.14 maxbatch from 10 to 10000, and conditionally call 
set_need_resched() in call_rcu().

This solution doesnt solve all the problems and has drawbacks.

1) Using a big maxbatch has a bad impact on latency.
2) A flood of call_rcu_bh() still can OOM

I have some servers that once in a while crashes when the ip route cache is 
flushed. After raising /proc/sys/net/ipv4/route/secret_interval (so that *no* 
flush is done), I got better uptime for these servers. But in some cases I 
think the network stack can floods call_rcu_bh(), and a fatal OOM occurs.

I suggest in this patch :

1) To lower maxbatch to a more reasonable value (as far as the latency is 
concerned)

2) To be able to guard a RCU cpu queue against a maximal count (10.000 for 
example). If this limit is reached, free the oldest entry of this queue.

I assume that if a CPU queued 10.000 items in its RCU queue, then the oldest 
entry cannot still be in use by another CPU. This might sounds as a violation 
of RCU rules, (I'm not an RCU expert) but seems quite reasonable.


Signed-off-by: Eric Dumazet <dada1@cosmosbay.com>

[-- Attachment #2: RCU_OOM.patch --]
[-- Type: text/plain, Size: 2078 bytes --]

--- linux-2.6.15/kernel/rcupdate.c	2006-01-03 04:21:10.000000000 +0100
+++ linux-2.6.15-edum/kernel/rcupdate.c	2006-01-06 11:10:45.000000000 +0100
@@ -71,14 +71,14 @@
 
 /* Fake initialization required by compiler */
 static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL};
-static int maxbatch = 10000;
+static int maxbatch = 100;
 
 #ifndef __HAVE_ARCH_CMPXCHG
 /*
  * We use an array of spinlocks for the rcurefs -- similar to ones in sparc
  * 32 bit atomic_t implementations, and a hash function similar to that
  * for our refcounting needs.
- * Can't help multiprocessors which donot have cmpxchg :(
+ * Can't help multiprocessors which dont have cmpxchg :(
  */
 
 spinlock_t __rcuref_hash[RCUREF_HASH_SIZE] = {
@@ -110,9 +110,17 @@
 	*rdp->nxttail = head;
 	rdp->nxttail = &head->next;
 
-	if (unlikely(++rdp->count > 10000))
-		set_need_resched();
-
+/*
+ * OOM avoidance : If we queued too many items in this queue,
+ *  free the oldest entry
+ */
+	if (unlikely(++rdp->count > 10000)) {
+		rdp->count--;
+		head = rdp->donelist;
+		rdp->donelist = head->next;
+		local_irq_restore(flags);
+		return head->func(head);
+	}
 	local_irq_restore(flags);
 }
 
@@ -148,12 +156,17 @@
 	rdp = &__get_cpu_var(rcu_bh_data);
 	*rdp->nxttail = head;
 	rdp->nxttail = &head->next;
-	rdp->count++;
 /*
- *  Should we directly call rcu_do_batch() here ?
- *  if (unlikely(rdp->count > 10000))
- *      rcu_do_batch(rdp);
+ * OOM avoidance : If we queued too many items in this queue,
+ *  free the oldest entry
  */
+	if (unlikely(++rdp->count > 10000)) {
+		rdp->count--;
+		head = rdp->donelist;
+		rdp->donelist = head->next;
+		local_irq_restore(flags);
+		return head->func(head);
+	}
 	local_irq_restore(flags);
 }
 
@@ -209,7 +222,7 @@
 static void rcu_do_batch(struct rcu_data *rdp)
 {
 	struct rcu_head *next, *list;
-	int count = 0;
+	int count = maxbatch;
 
 	list = rdp->donelist;
 	while (list) {
@@ -217,7 +230,7 @@
 		list->func(list);
 		list = next;
 		rdp->count--;
-		if (++count >= maxbatch)
+		if (--count <= 0)
 			break;
 	}
 	if (!rdp->donelist)

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency (Version 2), HOTPLUG_CPU fix

[Eric Dumazet]

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

First patch was buggy, sorry :(

This 2nd version makes no more RCU assumptions, because only the 'donelist' 
queue is fetched for an item to be deleted. Items from the donelist are ready 
to be freed.

This V2 also corrects a problem in case of a CPU hotplug, we forgot to update 
the ->count variable when transfering a queue to another one.

-------------------------------------------------------------------------
In order to avoid some OOM triggered by a flood of call_rcu() calls, we 
increased in linux 2.6.14 maxbatch from 10 to 10000, and conditionally call 
set_need_resched() in call_rcu().

This solution doesnt solve all the problems and has drawbacks.

1) Using a big maxbatch has a bad impact on latency.
2) A flood of call_rcu_bh() still can OOM

I have some servers that once in a while crashes when the ip route cache is 
flushed. After raising /proc/sys/net/ipv4/route/secret_interval (so that *no* 
flush is done), I got better uptime for these servers. But in some cases I 
think the network stack can floods call_rcu_bh(), and a fatal OOM occurs.

I suggest in this patch :

1) To lower maxbatch to a more reasonable value (as far as the latency is 
concerned)

2) To be able to guard a RCU cpu queue against a maximal count (10.000 for 
example). If this limit is reached, free the oldest entry (if available from 
the donelist queue).

3) Bug correction in __rcu_offline_cpu() where we forgot to adjust ->count 
field when transfering a queue to another one.

In my stress tests, I could not reproduce OOM anymore after applying this patch.

Signed-off-by: Eric Dumazet <dada1@cosmosbay.com>

[-- Attachment #2: RCU_OOM.patch --]
[-- Type: text/plain, Size: 3213 bytes --]

--- linux-2.6.15/kernel/rcupdate.c	2006-01-03 04:21:10.000000000 +0100
+++ linux-2.6.15-edum/kernel/rcupdate.c	2006-01-06 13:32:02.000000000 +0100
@@ -71,14 +71,14 @@
 
 /* Fake initialization required by compiler */
 static DEFINE_PER_CPU(struct tasklet_struct, rcu_tasklet) = {NULL};
-static int maxbatch = 10000;
+static int maxbatch = 100;
 
 #ifndef __HAVE_ARCH_CMPXCHG
 /*
  * We use an array of spinlocks for the rcurefs -- similar to ones in sparc
  * 32 bit atomic_t implementations, and a hash function similar to that
  * for our refcounting needs.
- * Can't help multiprocessors which donot have cmpxchg :(
+ * Can't help multiprocessors which dont have cmpxchg :(
  */
 
 spinlock_t __rcuref_hash[RCUREF_HASH_SIZE] = {
@@ -110,9 +110,19 @@
 	*rdp->nxttail = head;
 	rdp->nxttail = &head->next;
 
-	if (unlikely(++rdp->count > 10000))
-		set_need_resched();
-
+/*
+ * OOM avoidance : If we queued too many items in this queue,
+ *  free the oldest entry (from the donelist only to respect
+ *  RCU constraints)
+ */
+	if (unlikely(++rdp->count > 10000 && (head = rdp->donelist))) {
+		rdp->count--;
+		rdp->donelist = head->next;
+		if (!rdp->donelist)
+			rdp->donetail = &rdp->donelist;
+		local_irq_restore(flags);
+		return head->func(head);
+	}
 	local_irq_restore(flags);
 }
 
@@ -148,12 +158,19 @@
 	rdp = &__get_cpu_var(rcu_bh_data);
 	*rdp->nxttail = head;
 	rdp->nxttail = &head->next;
-	rdp->count++;
 /*
- *  Should we directly call rcu_do_batch() here ?
- *  if (unlikely(rdp->count > 10000))
- *      rcu_do_batch(rdp);
+ * OOM avoidance : If we queued too many items in this queue,
+ *  free the oldest entry (from the donelist only to respect
+ *  RCU constraints)
  */
+	if (unlikely(++rdp->count > 10000 && (head = rdp->donelist))) {
+		rdp->count--;
+		rdp->donelist = head->next;
+		if (!rdp->donelist)
+			rdp->donetail = &rdp->donelist;
+		local_irq_restore(flags);
+		return head->func(head);
+	}
 	local_irq_restore(flags);
 }
 
@@ -208,19 +225,20 @@
  */
 static void rcu_do_batch(struct rcu_data *rdp)
 {
-	struct rcu_head *next, *list;
-	int count = 0;
+	struct rcu_head *next = NULL, *list;
+	int count = maxbatch;
 
 	list = rdp->donelist;
 	while (list) {
-		next = rdp->donelist = list->next;
+		next = list->next;
 		list->func(list);
 		list = next;
 		rdp->count--;
-		if (++count >= maxbatch)
+		if (--count <= 0)
 			break;
 	}
-	if (!rdp->donelist)
+	rdp->donelist = next;
+	if (!next)
 		rdp->donetail = &rdp->donelist;
 	else
 		tasklet_schedule(&per_cpu(rcu_tasklet, rdp->cpu));
@@ -344,11 +362,9 @@
 static void rcu_move_batch(struct rcu_data *this_rdp, struct rcu_head *list,
 				struct rcu_head **tail)
 {
-	local_irq_disable();
 	*this_rdp->nxttail = list;
 	if (list)
 		this_rdp->nxttail = tail;
-	local_irq_enable();
 }
 
 static void __rcu_offline_cpu(struct rcu_data *this_rdp,
@@ -362,9 +378,12 @@
 	if (rcp->cur != rcp->completed)
 		cpu_quiet(rdp->cpu, rcp, rsp);
 	spin_unlock_bh(&rsp->lock);
+	local_irq_disable();
 	rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail);
 	rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail);
-
+	this_rdp->count += rdp->count;
+	rdp->count = 0;
+	local_irq_enable();
 }
 static void rcu_offline_cpu(int cpu)
 {

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Andi Kleen]

On Friday 06 January 2006 11:17, Eric Dumazet wrote:

>
> I assume that if a CPU queued 10.000 items in its RCU queue, then the
> oldest entry cannot still be in use by another CPU. This might sounds as a
> violation of RCU rules, (I'm not an RCU expert) but seems quite reasonable.

I don't think it's a good assumption. Another CPU might be stuck in a long 
running interrupt, and still have a reference in the code running below
the interrupt handler.

And in general letting correctness depend on magic numbers like this is 
very nasty.

-Andi

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Eric Dumazet]

Andi Kleen a écrit :
> On Friday 06 January 2006 11:17, Eric Dumazet wrote:
> 
>> I assume that if a CPU queued 10.000 items in its RCU queue, then the
>> oldest entry cannot still be in use by another CPU. This might sounds as a
>> violation of RCU rules, (I'm not an RCU expert) but seems quite reasonable.
> 
> I don't think it's a good assumption. Another CPU might be stuck in a long 
> running interrupt, and still have a reference in the code running below
> the interrupt handler.
> 
> And in general letting correctness depend on magic numbers like this is 
> very nasty.
> 

I agree Andi, I posted a 2nd version of the patch with no more assumptions.

Eric

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Lee Revell]

On Fri, 2006-01-06 at 13:58 +0100, Andi Kleen wrote:
> Another CPU might be stuck in a long 
> running interrupt

Shouldn't a long running interrupt be considered a bug?

Lee

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Andi Kleen]

On Friday 06 January 2006 20:26, Lee Revell wrote:
> On Fri, 2006-01-06 at 13:58 +0100, Andi Kleen wrote:
> > Another CPU might be stuck in a long 
> > running interrupt
> 
> Shouldn't a long running interrupt be considered a bug?

In normal operation yes, but there can be always exceptional
circumstances where it's unavoidable (e.g. during error handling) 
and in the name of defensive programming the rest of the system ought 
to tolerate it.

-Andi

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Alan Cox]

On Gwe, 2006-01-06 at 11:17 +0100, Eric Dumazet wrote:
> I assume that if a CPU queued 10.000 items in its RCU queue, then the oldest 
> entry cannot still be in use by another CPU. This might sounds as a violation 
> of RCU rules, (I'm not an RCU expert) but seems quite reasonable.

Fixing the real problem in the routing code would be the real fix. 

The underlying problem of RCU and memory usage could be solved more
safely by making sure that the sleeping memory allocator path always
waits until at least one RCU cleanup has occurred after it fails an
allocation before it starts trying harder. That ought to also naturally
throttle memory consumers more in the situation which is the right
behaviour.

Alan

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Eric Dumazet]

Alan Cox a écrit :
> On Gwe, 2006-01-06 at 11:17 +0100, Eric Dumazet wrote:
>> I assume that if a CPU queued 10.000 items in its RCU queue, then the oldest 
>> entry cannot still be in use by another CPU. This might sounds as a violation 
>> of RCU rules, (I'm not an RCU expert) but seems quite reasonable.
> 
> Fixing the real problem in the routing code would be the real fix. 
> 

So far nobody succeeded in 'fixing the routing code', few people can even read 
the code from the first line to the last one...

I think this code is not buggy, it only makes general RCU assumptions about 
delayed freeing of dst entries. In some cases, the general assumptions are 
just wrong. We can fix it at RCU level, and future users of call_rcu_bh() wont 
have to think *hard* about 'general assumptions'.

Of course, we can ignore the RCU problem and mark somewhere on a sticker: 
***DONT USE OR RISK CRASHES***
***USE IT ONLY FOR FUN***

> The underlying problem of RCU and memory usage could be solved more
> safely by making sure that the sleeping memory allocator path always
> waits until at least one RCU cleanup has occurred after it fails an
> allocation before it starts trying harder. That ought to also naturally
> throttle memory consumers more in the situation which is the right
> behaviour.
> 

In the case of call_rcu_bh(), you can be sure that the caller cannot afford 
'sleeping memory allocations'. Better drop a frame than block the stack, no ?

Eric

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Alan Cox]

On Gwe, 2006-01-06 at 15:00 +0100, Eric Dumazet wrote:
> In the case of call_rcu_bh(), you can be sure that the caller cannot afford 
> 'sleeping memory allocations'. Better drop a frame than block the stack, no ?

atomic allocations can't sleep and will fail which is fine. If memory
allocation pressure exists for sleeping allocations because of a large
rcu backlog we want to be sure that the rcu backlog from the networking
stack or other sources does not cause us to OOM kill or take incorrect
action.

So if for example we want to grow a process stack and the memory is
there just stuck in the RCU lists pending recovery we want to let the
RCU recovery happen before making drastic decisions.

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Paul E. McKenney]

On Fri, Jan 06, 2006 at 01:37:12PM +0000, Alan Cox wrote:
> On Gwe, 2006-01-06 at 11:17 +0100, Eric Dumazet wrote:
> > I assume that if a CPU queued 10.000 items in its RCU queue, then the oldest 
> > entry cannot still be in use by another CPU. This might sounds as a violation 
> > of RCU rules, (I'm not an RCU expert) but seems quite reasonable.
> 
> Fixing the real problem in the routing code would be the real fix. 
> 
> The underlying problem of RCU and memory usage could be solved more
> safely by making sure that the sleeping memory allocator path always
> waits until at least one RCU cleanup has occurred after it fails an
> allocation before it starts trying harder. That ought to also naturally
> throttle memory consumers more in the situation which is the right
> behaviour.

A quick look at rt_garbage_collect() leads me to believe that although
the IP route cache does try to limit its use of memory, it does not
fully account for memory that it has released to RCU, but that RCU has
not yet freed due to a grace period not having elapsed.

The following appears to be possible:

1.	rt_garbage_collect() sees that there are too many entries,
	and sets "goal" to the number to free up, based on a
	computed "equilibrium" value.

2.	The number of entries is (correctly) decremented only when
	the corresponding RCU callback is invoked, which actually
	frees the entry.

3.	Between the time that rt_garbage_collect() is invoked the
	first time and when the RCU grace period ends, rt_garbage_collect()
	is invoked again.  It still sees too many entries (since
	RCU has not yet freed the ones released by the earlier
	invocation in step (1) above), so frees a bunch more.

4.	Packets routed now miss the route cache, because the corresponding
	entries are waiting for a grace period, slowing the system down.
	Therefore, even more entries are freed to make room for new
	entries corresponding to the new packets.

If my (likely quite naive) reading of the IP route cache code is correct,
it would be possible to end up in a steady state with most of the entries
always being in RCU rather than in the route cache.

Eric, could this be what is happening to your system?

If it is, one straightforward fix would be to keep a count of the number
of route-cache entries waiting on RCU, and for rt_garbage_collect()
to subtract this number of entries from its goal.  Does this make sense?

							Thanx, Paul

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Eric Dumazet]

Paul E. McKenney a écrit :
> On Fri, Jan 06, 2006 at 01:37:12PM +0000, Alan Cox wrote:
>> On Gwe, 2006-01-06 at 11:17 +0100, Eric Dumazet wrote:
>>> I assume that if a CPU queued 10.000 items in its RCU queue, then the oldest 
>>> entry cannot still be in use by another CPU. This might sounds as a violation 
>>> of RCU rules, (I'm not an RCU expert) but seems quite reasonable.
>> Fixing the real problem in the routing code would be the real fix. 
>>
>> The underlying problem of RCU and memory usage could be solved more
>> safely by making sure that the sleeping memory allocator path always
>> waits until at least one RCU cleanup has occurred after it fails an
>> allocation before it starts trying harder. That ought to also naturally
>> throttle memory consumers more in the situation which is the right
>> behaviour.
> 
> A quick look at rt_garbage_collect() leads me to believe that although
> the IP route cache does try to limit its use of memory, it does not
> fully account for memory that it has released to RCU, but that RCU has
> not yet freed due to a grace period not having elapsed.
> 
> The following appears to be possible:
> 
> 1.	rt_garbage_collect() sees that there are too many entries,
> 	and sets "goal" to the number to free up, based on a
> 	computed "equilibrium" value.
> 
> 2.	The number of entries is (correctly) decremented only when
> 	the corresponding RCU callback is invoked, which actually
> 	frees the entry.
> 
> 3.	Between the time that rt_garbage_collect() is invoked the
> 	first time and when the RCU grace period ends, rt_garbage_collect()
> 	is invoked again.  It still sees too many entries (since
> 	RCU has not yet freed the ones released by the earlier
> 	invocation in step (1) above), so frees a bunch more.
> 
> 4.	Packets routed now miss the route cache, because the corresponding
> 	entries are waiting for a grace period, slowing the system down.
> 	Therefore, even more entries are freed to make room for new
> 	entries corresponding to the new packets.
> 
> If my (likely quite naive) reading of the IP route cache code is correct,
> it would be possible to end up in a steady state with most of the entries
> always being in RCU rather than in the route cache.
> 
> Eric, could this be what is happening to your system?
> 
> If it is, one straightforward fix would be to keep a count of the number
> of route-cache entries waiting on RCU, and for rt_garbage_collect()
> to subtract this number of entries from its goal.  Does this make sense?
> 

Hi Paul

Thanks for reviewing route code :)

As I said, the problem comes from 'route flush cache', that is periodically 
done by rt_run_flush(), triggered by rt_flush_timer.

The 10% of LOWMEM ram that was used by route-cache entries are pushed into rcu 
queues (with call_rcu_bh()) and network continue to receive
packets from *many* sources that want their route-cache entry.


Eric

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Paul E. McKenney]

On Fri, Jan 06, 2006 at 06:19:15PM +0100, Eric Dumazet wrote:
> Paul E. McKenney a écrit :
> >On Fri, Jan 06, 2006 at 01:37:12PM +0000, Alan Cox wrote:
> >>On Gwe, 2006-01-06 at 11:17 +0100, Eric Dumazet wrote:
> >>>I assume that if a CPU queued 10.000 items in its RCU queue, then the 
> >>>oldest entry cannot still be in use by another CPU. This might sounds as 
> >>>a violation of RCU rules, (I'm not an RCU expert) but seems quite 
> >>>reasonable.
> >>Fixing the real problem in the routing code would be the real fix. 
> >>
> >>The underlying problem of RCU and memory usage could be solved more
> >>safely by making sure that the sleeping memory allocator path always
> >>waits until at least one RCU cleanup has occurred after it fails an
> >>allocation before it starts trying harder. That ought to also naturally
> >>throttle memory consumers more in the situation which is the right
> >>behaviour.
> >
> >A quick look at rt_garbage_collect() leads me to believe that although
> >the IP route cache does try to limit its use of memory, it does not
> >fully account for memory that it has released to RCU, but that RCU has
> >not yet freed due to a grace period not having elapsed.
> >
> >The following appears to be possible:
> >
> >1.	rt_garbage_collect() sees that there are too many entries,
> >	and sets "goal" to the number to free up, based on a
> >	computed "equilibrium" value.
> >
> >2.	The number of entries is (correctly) decremented only when
> >	the corresponding RCU callback is invoked, which actually
> >	frees the entry.
> >
> >3.	Between the time that rt_garbage_collect() is invoked the
> >	first time and when the RCU grace period ends, rt_garbage_collect()
> >	is invoked again.  It still sees too many entries (since
> >	RCU has not yet freed the ones released by the earlier
> >	invocation in step (1) above), so frees a bunch more.
> >
> >4.	Packets routed now miss the route cache, because the corresponding
> >	entries are waiting for a grace period, slowing the system down.
> >	Therefore, even more entries are freed to make room for new
> >	entries corresponding to the new packets.
> >
> >If my (likely quite naive) reading of the IP route cache code is correct,
> >it would be possible to end up in a steady state with most of the entries
> >always being in RCU rather than in the route cache.
> >
> >Eric, could this be what is happening to your system?
> >
> >If it is, one straightforward fix would be to keep a count of the number
> >of route-cache entries waiting on RCU, and for rt_garbage_collect()
> >to subtract this number of entries from its goal.  Does this make sense?
> >
> 
> Hi Paul
> 
> Thanks for reviewing route code :)
> 
> As I said, the problem comes from 'route flush cache', that is periodically 
> done by rt_run_flush(), triggered by rt_flush_timer.
> 
> The 10% of LOWMEM ram that was used by route-cache entries are pushed into 
> rcu queues (with call_rcu_bh()) and network continue to receive
> packets from *many* sources that want their route-cache entry.

Hello, Eric,

The rt_run_flush() function could indeed be suffering from the same
problem.  Dipankar's recent patch should help RCU grace periods proceed
more quickly, does that help?

If not, it may be worthwhile to limit the number of times that
rt_run_flush() runs per RCU grace period.

						Thanx, Paul

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[David S. Miller]

From: "Paul E. McKenney" <paulmck@us.ibm.com>
Date: Fri, 6 Jan 2006 12:26:26 -0800

> If not, it may be worthwhile to limit the number of times that
> rt_run_flush() runs per RCU grace period.

This is mixing two sets of requirements.

rt_run_flush() runs periodically in order to regenerate the hash
function secret key.  Now, for that specific case it might actually be
possible to rehash instead of flush, but the locking is a little bit
tricky :-)  And also, I think we're regenerating the secret key
just a little bit too often, I think we'd get enough security
with a less frequent regeneration.

I'll look into this and your other ideas later today hopefully.

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Andi Kleen]

On Friday 06 January 2006 21:26, Paul E. McKenney wrote:

> If not, it may be worthwhile to limit the number of times that
> rt_run_flush() runs per RCU grace period.

Problem is that without rt_run_flush new routes and route attribute
changes don't get used by the stack. If RCU takes long and routes
keep changing this might be a big issue.

As a admin I would be certainly annoyed if the network stack
ignored my new route for some unbounded time.

Perhaps a better way would be to just exclude dst entries in RCU state
from the normal accounting and assume that if the system
really runs short of memory because of this the results would
trigger quiescent states more quickly, freeing the memory again.

-Andi

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[David S. Miller]

From: Andi Kleen <ak@suse.de>
Date: Fri, 6 Jan 2006 21:57:41 +0100

> Perhaps a better way would be to just exclude dst entries in RCU state
> from the normal accounting and assume that if the system
> really runs short of memory because of this the results would
> trigger quiescent states more quickly, freeing the memory again.

That's one idea...

Eric, how important do you honestly think the per-hashchain spinlocks
are?  That's the big barrier from making rt_secret_rebuild() a simple
rehash instead of flushing the whole table as it does now.

The lock is only grabbed for updates, and the access to these locks is
random and as such probably non-local when taken anyways.  Back before
we used RCU for reads, this array-of-spinlock thing made a lot more
sense.

I mean something like this patch:

diff --git a/net/ipv4/route.c b/net/ipv4/route.c
index f701a13..f9436c7 100644
--- a/net/ipv4/route.c
+++ b/net/ipv4/route.c
@@ -204,36 +204,8 @@ __u8 ip_tos2prio[16] = {
 struct rt_hash_bucket {
 	struct rtable	*chain;
 };
-#if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK)
-/*
- * Instead of using one spinlock for each rt_hash_bucket, we use a table of spinlocks
- * The size of this table is a power of two and depends on the number of CPUS.
- */
-#if NR_CPUS >= 32
-#define RT_HASH_LOCK_SZ	4096
-#elif NR_CPUS >= 16
-#define RT_HASH_LOCK_SZ	2048
-#elif NR_CPUS >= 8
-#define RT_HASH_LOCK_SZ	1024
-#elif NR_CPUS >= 4
-#define RT_HASH_LOCK_SZ	512
-#else
-#define RT_HASH_LOCK_SZ	256
-#endif
 
-static spinlock_t	*rt_hash_locks;
-# define rt_hash_lock_addr(slot) &rt_hash_locks[(slot) & (RT_HASH_LOCK_SZ - 1)]
-# define rt_hash_lock_init()	{ \
-		int i; \
-		rt_hash_locks = kmalloc(sizeof(spinlock_t) * RT_HASH_LOCK_SZ, GFP_KERNEL); \
-		if (!rt_hash_locks) panic("IP: failed to allocate rt_hash_locks\n"); \
-		for (i = 0; i < RT_HASH_LOCK_SZ; i++) \
-			spin_lock_init(&rt_hash_locks[i]); \
-		}
-#else
-# define rt_hash_lock_addr(slot) NULL
-# define rt_hash_lock_init()
-#endif
+static DEFINE_SPINLOCK(rt_hash_lock);
 
 static struct rt_hash_bucket 	*rt_hash_table;
 static unsigned			rt_hash_mask;
@@ -627,7 +599,7 @@ static void rt_check_expire(unsigned lon
 
 		if (*rthp == 0)
 			continue;
-		spin_lock(rt_hash_lock_addr(i));
+		spin_lock(&rt_hash_lock);
 		while ((rth = *rthp) != NULL) {
 			if (rth->u.dst.expires) {
 				/* Entry is expired even if it is in use */
@@ -660,7 +632,7 @@ static void rt_check_expire(unsigned lon
  			rt_free(rth);
 #endif /* CONFIG_IP_ROUTE_MULTIPATH_CACHED */
 		}
-		spin_unlock(rt_hash_lock_addr(i));
+		spin_unlock(&rt_hash_lock);
 
 		/* Fallback loop breaker. */
 		if (time_after(jiffies, now))
@@ -683,11 +655,11 @@ static void rt_run_flush(unsigned long d
 	get_random_bytes(&rt_hash_rnd, 4);
 
 	for (i = rt_hash_mask; i >= 0; i--) {
-		spin_lock_bh(rt_hash_lock_addr(i));
+		spin_lock_bh(&rt_hash_lock);
 		rth = rt_hash_table[i].chain;
 		if (rth)
 			rt_hash_table[i].chain = NULL;
-		spin_unlock_bh(rt_hash_lock_addr(i));
+		spin_unlock_bh(&rt_hash_lock);
 
 		for (; rth; rth = next) {
 			next = rth->u.rt_next;
@@ -820,7 +792,7 @@ static int rt_garbage_collect(void)
 
 			k = (k + 1) & rt_hash_mask;
 			rthp = &rt_hash_table[k].chain;
-			spin_lock_bh(rt_hash_lock_addr(k));
+			spin_lock_bh(&rt_hash_lock);
 			while ((rth = *rthp) != NULL) {
 				if (!rt_may_expire(rth, tmo, expire)) {
 					tmo >>= 1;
@@ -852,7 +824,7 @@ static int rt_garbage_collect(void)
 				goal--;
 #endif /* CONFIG_IP_ROUTE_MULTIPATH_CACHED */
 			}
-			spin_unlock_bh(rt_hash_lock_addr(k));
+			spin_unlock_bh(&rt_hash_lock);
 			if (goal <= 0)
 				break;
 		}
@@ -922,7 +894,7 @@ restart:
 
 	rthp = &rt_hash_table[hash].chain;
 
-	spin_lock_bh(rt_hash_lock_addr(hash));
+	spin_lock_bh(&rt_hash_lock);
 	while ((rth = *rthp) != NULL) {
 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
 		if (!(rth->u.dst.flags & DST_BALANCED) &&
@@ -948,7 +920,7 @@ restart:
 			rth->u.dst.__use++;
 			dst_hold(&rth->u.dst);
 			rth->u.dst.lastuse = now;
-			spin_unlock_bh(rt_hash_lock_addr(hash));
+			spin_unlock_bh(&rt_hash_lock);
 
 			rt_drop(rt);
 			*rp = rth;
@@ -989,7 +961,7 @@ restart:
 	if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
 		int err = arp_bind_neighbour(&rt->u.dst);
 		if (err) {
-			spin_unlock_bh(rt_hash_lock_addr(hash));
+			spin_unlock_bh(&rt_hash_lock);
 
 			if (err != -ENOBUFS) {
 				rt_drop(rt);
@@ -1030,7 +1002,7 @@ restart:
 	}
 #endif
 	rt_hash_table[hash].chain = rt;
-	spin_unlock_bh(rt_hash_lock_addr(hash));
+	spin_unlock_bh(&rt_hash_lock);
 	*rp = rt;
 	return 0;
 }
@@ -1098,7 +1070,7 @@ static void rt_del(unsigned hash, struct
 {
 	struct rtable **rthp;
 
-	spin_lock_bh(rt_hash_lock_addr(hash));
+	spin_lock_bh(&rt_hash_lock);
 	ip_rt_put(rt);
 	for (rthp = &rt_hash_table[hash].chain; *rthp;
 	     rthp = &(*rthp)->u.rt_next)
@@ -1107,7 +1079,7 @@ static void rt_del(unsigned hash, struct
 			rt_free(rt);
 			break;
 		}
-	spin_unlock_bh(rt_hash_lock_addr(hash));
+	spin_unlock_bh(&rt_hash_lock);
 }
 
 void ip_rt_redirect(u32 old_gw, u32 daddr, u32 new_gw,
@@ -3155,7 +3127,6 @@ int __init ip_rt_init(void)
 					&rt_hash_mask,
 					0);
 	memset(rt_hash_table, 0, (rt_hash_mask + 1) * sizeof(struct rt_hash_bucket));
-	rt_hash_lock_init();
 
 	ipv4_dst_ops.gc_thresh = (rt_hash_mask + 1);
 	ip_rt_max_size = (rt_hash_mask + 1) * 16;

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Andi Kleen]

On Saturday 07 January 2006 01:17, David S. Miller wrote:

> 
> I mean something like this patch:

Looks like a good idea to me.

I always disliked the per chain spinlocks even for other hash tables like
TCP/UDP multiplex - it would be much nicer to use a much smaller separately 
hashed lock table and save cache. In this case the special case of using
a one entry only lock hash table makes sense.

-Andi

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[David S. Miller]

From: Andi Kleen <ak@suse.de>
Date: Sat, 7 Jan 2006 02:09:01 +0100

> I always disliked the per chain spinlocks even for other hash tables like
> TCP/UDP multiplex - it would be much nicer to use a much smaller separately 
> hashed lock table and save cache. In this case the special case of using
> a one entry only lock hash table makes sense.

I used to think they were a great technique.  But in each case I
thought they could be applied, better schemes have come along.
In the case of the page cache we went to a per-address-space tree,
and here in the routing cache we went to RCU.

There are RCU patches around for the TCP hashes and I'd like to
put those in at some point as well.  In fact, they'd be even
more far reaching since Arnaldo abstracted away the socket
hashing stuff into an inet_hashtables subsystem.

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Eric Dumazet]

Andi Kleen a écrit :
> 
> I always disliked the per chain spinlocks even for other hash tables like
> TCP/UDP multiplex - it would be much nicer to use a much smaller separately 
> hashed lock table and save cache. In this case the special case of using
> a one entry only lock hash table makes sense.
> 

I agree, I do use a hashed spinlock array on my local tree for TCP, mainly to 
reduce the hash table size by a 2 factor.

Eric

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[David S. Miller]

From: Eric Dumazet <dada1@cosmosbay.com>
Date: Sat, 07 Jan 2006 08:34:35 +0100

> I agree, I do use a hashed spinlock array on my local tree for TCP,
> mainly to reduce the hash table size by a 2 factor.

So what do you think about going to a single spinlock for the
routing cache?

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Eric Dumazet]

David S. Miller a écrit :
> From: Eric Dumazet <dada1@cosmosbay.com>
> Date: Sat, 07 Jan 2006 08:34:35 +0100
> 
>> I agree, I do use a hashed spinlock array on my local tree for TCP,
>> mainly to reduce the hash table size by a 2 factor.
> 
> So what do you think about going to a single spinlock for the
> routing cache?

I have no problem with this, since the biggest server I have is 4 way, but are 
you sure big machines wont suffer from this single spinlock ?

Also I dont understand what you want to do after this single spinlock patch.
How is it supposed to help the 'ip route flush cache' problem ?

In my case, I have about 600.000 dst-entries :

# grep ip_dst /proc/slabinfo
ip_dst_cache      616250 622440    320   12    1 : tunables   54   27    8 : 
slabdata  51870  51870      0


Eric

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[David S. Miller]

From: Eric Dumazet <dada1@cosmosbay.com>
Date: Sat, 07 Jan 2006 08:53:52 +0100

> I have no problem with this, since the biggest server I have is 4
> way, but are you sure big machines wont suffer from this single
> spinlock ?

It is the main question.

> Also I dont understand what you want to do after this single
> spinlock patch.  How is it supposed to help the 'ip route flush
> cache' problem ?  In my case, I have about 600.000 dst-entries :

I don't claim to have a solution to this problem currently.

Doing RCU and going through the whole DST GC machinery is overkill for
an active system.  So, perhaps a very simple solution will do:

1) On rt_run_flush(), do not rt_free(), instead collect all active
   routing cache entries onto a global list, begin a timer to
   fire in 10 seconds (or some sysctl configurable amount).

2) When a new routing cache entry is needed, check the global
   list appended to in #1 above first, failing that do dst_alloc()
   as is done currently.

3) If timer expires, rt_free() any entries in the global list.

The missing trick is how to ensure RCU semantics when reallocating
from the global list.

The idea is that an active system will immediately repopulate itself
with all of these entries just flushed from the table.

RCU really doesn't handle this kind of problem very well.  It truly
excels when work is generated by process context work, not interrupt
work.

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Paul E. McKenney]

On Sat, Jan 07, 2006 at 12:36:25AM -0800, David S. Miller wrote:
> From: Eric Dumazet <dada1@cosmosbay.com>
> Date: Sat, 07 Jan 2006 08:53:52 +0100
> 
> > I have no problem with this, since the biggest server I have is 4
> > way, but are you sure big machines wont suffer from this single
> > spinlock ?
> 
> It is the main question.
> 
> > Also I dont understand what you want to do after this single
> > spinlock patch.  How is it supposed to help the 'ip route flush
> > cache' problem ?  In my case, I have about 600.000 dst-entries :
> 
> I don't claim to have a solution to this problem currently.
> 
> Doing RCU and going through the whole DST GC machinery is overkill for
> an active system.  So, perhaps a very simple solution will do:
> 
> 1) On rt_run_flush(), do not rt_free(), instead collect all active
>    routing cache entries onto a global list, begin a timer to
>    fire in 10 seconds (or some sysctl configurable amount).
> 
> 2) When a new routing cache entry is needed, check the global
>    list appended to in #1 above first, failing that do dst_alloc()
>    as is done currently.
> 
> 3) If timer expires, rt_free() any entries in the global list.
> 
> The missing trick is how to ensure RCU semantics when reallocating
> from the global list.

The straightforward ways of doing this require a per-entry lock in
addition to the dst_entry reference count -- lots of read-side overhead.

More complex approaches use a generation number that is incremented
when adding to or removing from the global list.  When the generation
number overflows, unconditionally rt_free() it rather than adding
to the global list again.  Then there needs to be some clever code
on the read side to detect the case when the generation number
changes while acquiring a reference.  And memory barriers.  Also
lots of read-side overhead.  Also, it is now -always- necessary to
acquire a reference on the read-side.

> The idea is that an active system will immediately repopulate itself
> with all of these entries just flushed from the table.
> 
> RCU really doesn't handle this kind of problem very well.  It truly
> excels when work is generated by process context work, not interrupt
> work.

Sounds like a challenge to me.  ;-)

Well, one possible way to attack Eric's workload might be the following:

o	Size the hash table to strike the appropriate balance between
	read-side search overhead and memory consumption.  Call the
	number of hash-chain headers N.

o	Create a hashed array of locks sized to allow the update to
	proceed sufficiently quickly.  Call the number of locks M,
	probably a power of two.  This means that M CPUs can be doing
	the update in parallel.

o	Create an array of M^2 list headers (call it xfer[][]), but
	since this is only needed during an update, it can be allocated
	and deallocated if need be.  (Me, with my big-server experience,
	would probably just create the array, since M is not likely to
	be too large.  But your mileage may vary.  And you really only
	need M*(M-1) list headers, but that makes the index calculation
	a bit more annoying.)

o	Use a two-phase update.  In the first phase, each updating
	CPU acquires the corresponding lock and removes entries from
	the corresponding partition of the hash table.  If the new
	location of a given entry falls into the same partition, it
	is added back to the appropriate hash chain of that partition.
	Otherwise, add the entry to xfer[dst][src], where "src" and 
	"dst" are indexes of the corresponding partitions.

o	When all CPUs finish removing entries from their partition,
	they check into a barrier.  Once all have checked in, they
	can start the second phase of the update.

o	In the second phase, each CPU removes the entries from the
	xfer array that are destined for its partition and adds them
	to the hash chain that they are destined for.

Some commentary and variations, in the hope that this inspires someone
to come up with an even better idea:

o	Unless M is at least three, there is no performance gain
	over a single global lock with a single CPU doing the update,
	since each element must now undergo four list operations rather
	than just two.

o	The xfer[][] array must have each entry cache-aligned, or
	you lose big on cacheline effects.  Note that it is -not-
	sufficient to simply align the rows or the columns, since
	each CPU has its own column when inserting and its own
	row when removing from xfer[][].

o	And the data-skew effects are less severe if this procedure
	runs from process context.  A spinning barrier must be used
	otherwise.  But note that the per-partition locks could remain
	spinlocks, only the barrier need involve sleeping (in case
	that helps, am getting a bit ahead of my understanding of
	this part of the kernel).

	So I half-agree with Dave -- this works better if the bulk
	update is done in process context, however, updates involving
	single entries being individually added and removed from the
	hash table can be done from interrupt context.

o	One (more complex!) way to reduce the effect of data skew to
	partition the array based on the number of elements in each
	partition rather than by the number of chains, but this would
	require a second barrier that is completed before dropping locks
	in order to avoid messing up concurrent single-element updates.

	And this only handles the phase-1 data-skew effects. It is
	possible to handle phase-2 data skew as well, but it takes an
	up-front full-table scan and so it is not clear how it could
	possibly be a performance win.

o	Note that routing slows down significantly while an update is
	in progress, because on average only half of the entries are
	in the hash table during the update.  I have no idea whether
	or not this is acceptable.  I am assuming that the same
	mechanism that prevents two concurrent route-cache misses
	from inserting two entries from the same route would also
	prevent adding a new entry when one was already in the
	xfer array.

Thoughts?

							Thanx, Paul

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Eric Dumazet]

David S. Miller a écrit :
> 
> Eric, how important do you honestly think the per-hashchain spinlocks
> are?  That's the big barrier from making rt_secret_rebuild() a simple
> rehash instead of flushing the whole table as it does now.
> 

No problem for me in going to a single spinlock.
I did the hashed spinlock patch in order to reduce the size of the route hash 
table and not hurting big NUMA machines. If you think a single spinlock is OK, 
that's even better !

> The lock is only grabbed for updates, and the access to these locks is
> random and as such probably non-local when taken anyways.  Back before
> we used RCU for reads, this array-of-spinlock thing made a lot more
> sense.
> 
> I mean something like this patch:
> 

> +static DEFINE_SPINLOCK(rt_hash_lock);


Just one point : This should be cache_line aligned, and use one full cache 
line to avoid false sharing at least. (If a cpu takes the lock, no need to 
invalidate *rt_hash_table for all other cpus)

Eric

Re: [PATCH, RFC] RCU : OOM avoidance and lower latency

[Lee Revell]

On Fri, 2006-01-06 at 11:17 +0100, Eric Dumazet wrote:
> I have some servers that once in a while crashes when the ip route
> cache is flushed. After
> raising /proc/sys/net/ipv4/route/secret_interval (so that *no* 
> flush is done), I got better uptime for these servers. 

Argh, where is that documented?  I have been banging my head against
this for weeks - how do I keep the kernel from flushing 4096 routes at
once in softirq context causing huge (~8-20ms) latency problems?

I tried all the route related sysctls I could find and nothing worked...

Lee