Re: ext3 allocate-with-reservation latencies

From: Mingming Cao (cmm_at_us.ibm.com)
Date: 04/12/05

  • Next message: Ingo Molnar: "Re: [patch] sched: unlocked context-switches" 
    To: "Stephen C. Tweedie" <sct@redhat.com>
Date:	Mon, 11 Apr 2005 23:41:27 -0700

    On Mon, 2005-04-11 at 20:57 +0100, Stephen C. Tweedie wrote:
    > Hi,

    Hi Stephen,

    >
    > On Mon, 2005-04-11 at 19:38, Mingming Cao wrote:
    > > Ah.. I see the win with the read lock now: once the a reservation window
    > > is added, updating it (either winding it forward and or searching for a
    > > avaliable window) probably is the majorirty of the operations on the
    > > tree, and using read lock for that should help reduce the latency.
    >
    > Right. The down side is that for things like a kernel "tar xf", we'll
    > be doing lots of small file unpacks, and hopefully most files will be
    > just one or two reservations --- so there's little winding forward going
    > on. The searching will still be improved in that case.

    Just a side note that "tar xf" should know the file size before
    unpacking it. So it could set the reservation window size large enough
    to fit the entire file before doing the file write through ioctl
    command.

    > Note that this may improve average case latencies, but it's not likely
    > to improve worst-case ones. We still need a write lock to install a new
    > window, and that's going to have to wait for us to finish finding a free
    > bit even if that operation starts using a read lock.
    >
    Yes indeed. However nothing is free and there are always trade-offs.:)

    By worse case you mean multiple writes trying to allocate blocks around
    same area?

    But I wonder if the latency saw by Lee belongs to this worst-case: the
    latency comes mostly from loop calling find_next_zero_bit() in
    bitmap_search_next_usable_block(). Even if we take out the whole
    reservation, we still possibility run into this kind of latency: the
    bitmap on disk and on journal are extremely inconsistent so we need to
    keep searching them both until we find a free bit on both map.

    > I'm not really sure what to do about worst-case here. For that, we
    > really do want to drop the lock entirely while we do the bitmap scan.
    >

    Hmm...if we drop the lock entirely while scan the bitmap, assuming you
    mean drop the read lock, then I am afraid we have to re-check the tree
    (require a read or write lock ) to see if the new window space is still
    there after the scan succeed. This is probably not very interesting for
    the window rotating case.

    > That leaves two options. Hold a reservation while we do that; or don't.
    > Holding one poses the problems we discussed before: either you hold a
    > large reservation (bad for disk layout in the presence of concurrent
    > allocators), or you hold smaller ones (high cost as you continually
    > advance the window, which requires some read lock on the tree to avoid
    > bumping into the next window.)
    >

    Well, we cannot hold a reservation (which need to update the tree)
    without a write lock. I guess if we want to improve the average case
    latency by replacing the current spin_lock with the read lock for the
    new window space searching, we don't have much choice here.

    > Just how bad would it be if we didn't hold a lock _or_ a window at all
    > while doing the search for new window space?

    I wonder if this is feasible: Walk through the rb tree without a lock?
    What if some node is being removed by another thread while we are
    walking through the tree and trying to get the next node from it?

    Thanks,

    Mingming

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

  • Next message: Ingo Molnar: "Re: [patch] sched: unlocked context-switches"

    Relevant Pages

    • Re: ext3 allocate-with-reservation latencies
      ... > enough as you fill up a block group with small files, ... probably try to skip the block groups without enough usable free blocks ... > No, I'm suggesting that if we need the write lock for tree updates, we ... > individual window. ...
      (Linux-Kernel)
    • Re: ext3 allocate-with-reservation latencies
      ... > what I was suggesting is, if allocation from the home group failed and ... > probably try to skip the block groups without enough usable free blocks ... and using read lock for that should help reduce the latency. ... window, and that's going to have to wait for us to finish finding a free ...
      (Linux-Kernel)
    • Re: Isolation level question
      ... But you are getting an EXCLUSIVE lock when update the row where nunber = 1. ... > first window I run: ... > set transaction isolation level read uncommitted ... > In the second window, ...
      (microsoft.public.sqlserver.programming)
    • RE: synchronizing domain user Local cached credentials with domain (VP
      ... locally cached credentials are out of sync with domain credentials. ... For the technical savvy will lock their screen and logon on ... change (script the detection of the Window bubble, ...
      (microsoft.public.windowsxp.security_admin)
    • Re: Legend C and Vista C sensitivity
      ... > I have had a basic yellow etrex for the last two years and have been happy ... My first GPSr was an eTrex Summit, bought in 2000, on which reception ... (again, near a window). ... lock inside a building, no matter how close you were to a window. ...
      (sci.geo.satellite-nav)