LKML Archive on
help / color / mirror / Atom feed
From: Mathieu Desnoyers <>
To: Peter Zijlstra <>
Cc: Christoph Lameter <>,
Subject: Re: [RFC PATCH] Implement slub fastpath with sequence number
Date: Wed, 12 Mar 2008 18:17:03 -0400	[thread overview]
Message-ID: <20080312221703.GA25625@Krystal> (raw)
In-Reply-To: <1205246043.8514.188.camel@twins>

* Peter Zijlstra ( wrote:
> On Tue, 2008-03-11 at 05:31 -0400, Mathieu Desnoyers wrote:
> > Here is a new version that works. tested on x86. tweaked the bitmasks
> > into unions to remove operations from the critical path, but I tried to
> > keep that clean. It applies on vm.git HEAD.
> > 
> > It allows the cmpxchg_local to detect object re-use by keeping a counter in the
> > freeoffset MSBs.
> > 
> > Whenever an object is freed in the cpu slab cache, the counter is incremented.
> > Whenever the alloc/free slow paths are modifying the offset or freebase, the
> > sequence counter is also incremented. It is used to make sure we know if
> > freebase has been modified in an interrupt nested over the fast path.
> Is it (remotely) possible that the version will wrap giving the false
> impression that nothing has changed and thus falsely proceed with a
> wrong object?

If we have exactly, on a 32 bits arch, 65536 memory alloc or free in the
slab we are dealing with done in interrupt and softirqs nested over the
cmpxchg_local loop, without ever giving the control back to check the
value, and that after we get the control back the offset within the slab
is exactly the same, then, yes, it's possible. In that case, we would
think it's ok to proceed with the object and we would have memory
corruption (object used twice or free object list corruption).

Given that the alloc fast path takes about 115 cycles on a 3GHz Pentium
4 for an alloc/free pair (65536 * 38.33ns = 2.5ms total), having this
scenario would mean that every other interrupt would not have been
serviced for 2.5ms. In that case, we would probably have other problems
to deal with. On 64 bits architectures, with 2^32 bits, we would have to
wait for about 160 seconds (approx.).

This is why I added a check to verify if the sequence number delta is
bigger than half of the number of bits we have to count it :

+       /*
+        * Just to be paranoid : warn if we detect that enough free or
+        * slow paths nested on top of us to get the counter to go
+        * half-way to overflow. That would be insane to do that much
+        * allocations/free in interrupt handers, but check it anyway.
+        */
+       WARN_ON(result - old > -1UL >> 1);

If we ever have a kernel which starts to behave weirdly and *could* be
unlucky and get nearer to overflow, this check would likely detect it.
Worse case I have seen so far on my stressed machine was a delta of 3.

> I would really prefer if we defer all this fast path fiddling until we
> have the cpu_ops in place, this all just makes the code utterly
> unreadable.

Even with cpu_ops in place, I think it would be safer to still disable
preemption in the fastpath. It would make sure a thread is not stopped
in the middle of the cmpxchg loop, a lot of activity happens, and later
on the thread is woken up. In this scenario, the 16 bits might not be
enough to keep track of allocations/frees in the slab.


Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

  parent reply	other threads:[~2008-03-12 22:17 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2008-03-11  9:31 Mathieu Desnoyers
2008-03-11  9:41 ` Nick Piggin
2008-03-11 14:45   ` Pekka Enberg
2008-03-11 23:13     ` Nick Piggin
2008-03-12  4:14       ` Christoph Lameter
2008-03-11 14:34 ` Peter Zijlstra
2008-03-12  4:15   ` Christoph Lameter
2008-03-12 22:17   ` Mathieu Desnoyers [this message]
2008-03-13  1:20     ` Mathieu Desnoyers
2008-03-13  1:35       ` Mathieu Desnoyers

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20080312221703.GA25625@Krystal \ \ \ \ \
    --subject='Re: [RFC PATCH] Implement slub fastpath with sequence number' \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).