[no subject]

i.tum.de>
From: Matthew Dillon <dillon@apollo.backplane.com>
Subject: Re: hammer_alloc_data panic
Date: Wed, 16 Jul 2008 09:25:53 -0700 (PDT)
BestServHost: crater.dragonflybsd.org
List-Post: <mailto:bugs@crater.dragonflybsd.org>
List-Subscribe: <mailto:bugs-request@crater.dragonflybsd.org?body=subscribe>
List-Unsubscribe: <mailto:bugs-request@crater.dragonflybsd.org?body=unsubscribe>
List-Help: <mailto:bugs-request@crater.dragonflybsd.org?body=help>
List-Owner: <mailto:owner-bugs@crater.dragonflybsd.org>
References: <20080702212005.29c8710a.bastyaelvtars@gmail.com>	<20080702213943.d57fbad6.bastyaelvtars@gmail.com>	<200807022320.m62NKCJK082805@apollo.backplane.com>	<20080703185505.efbbe9f5.bastyaelvtars@gmail.com>	<200807031726.m63HQx9K090099@apollo.backplane.com> <20080703212717.a70f80d7.bastyaelvtars@gmail.com> <200807152209.m6FM98cj010364@apollo.backplane.com> <487D27E1.9070305@online.de> <487D3398.2080004@fs.ei.tum.de> <200807160128.m6G1SI84011776@apollo.backplane.com> <487DB323.9060208@fs.e
i.tum.de>
Sender: bugs-errors@crater.dragonflybsd.org
Errors-To: bugs-errors@crater.dragonflybsd.org
Lines: 46
NNTP-Posting-Host: 216.240.41.25
X-Trace: 1216226442 crater_reader.dragonflybsd.org 851 216.240.41.25
Xref: crater_reader.dragonflybsd.org dragonfly.bugs:8694


:Why do you need to reserve 1GB?  Wouldn't (in theory), one block be 
:enough to be able to make progress?
:
:cheers
:   simon

    Not without a more sophisticated algorithm, no.  The reason is simple.
    Lets say you have a filesystem with 32 blocks and 16 of them are half
    full.  Now you reblock.

    But the reblocking doesn't scan by block, it scans the B-Tree.  So,
    due to fragmentation, reblocking by scanning the B-Tree might free up
    *some* of the space in each of those 16 blocks while filling up a new
    block, but the new block may become completely full before any one 
    of those 16 blocks becomes completely empty.  So another new block needs
    to be allocated.

    Eventually all of the original 16 blocks will be compacted and (since
    they were originally half full), 8 of them will be freed up.  But it
    could have required numerous new blocks to be filled before any of the
    original 16 became completely free and reusable.

    If you reblock with a low fill level, like 20%, then there is a much
    MUCH higher chance that the reblocker will be able to clear out 
    partially empty blocks  before having to allocate additional new
    blocks.  Once you accomplish that you can use a larger fill level,
    and repeat, until you get to 100%.

    --

    Is it possible to reblock with one free block?  Yes, but it requires
    a different algorithm.  The algorithm would have to scan the B-Tree
    for all elements using that block we are trying to free.  Then scan
    the tree again for the next block we are tryingto free, and so forth.
    It would be very very expensive.  Some optimizations could be made
    (e.g. to free a limited number of blocks simultaniously with one
    B-Tree scan), but no matter what it will be far more time and
    disk-intensive then the current algorithm.  We might want to implement
    it anyway as an emergency measure, but frankly at that point I think
    the person's best bet is to free up some space by removing files
    and pruning before doing a standard reblocking.

					-Matt
					Matthew Dillon 
					<dillon@backplane.com>