No subject

[Unknown]

i.tum.de>
From: Matthew Dillon <dillon at 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 at crater.dragonflybsd.org>
List-Subscribe: <mailto:bugs-request at crater.dragonflybsd.org?body=subscribe>
List-Unsubscribe: <mailto:bugs-request at crater.dragonflybsd.org?body=unsubscribe>
List-Help: <mailto:bugs-request at crater.dragonflybsd.org?body=help>
List-Owner: <mailto:owner-bugs at crater.dragonflybsd.org>
References: <20080702212005.29c8710a.bastyaelvtars at gmail.com>	<20080702213943.d57fbad6.bastyaelvtars at gmail.com>	<200807022320.m62NKCJK082805 at apollo.backplane.com>	<20080703185505.efbbe9f5.bastyaelvtars at gmail.com>	<200807031726.m63HQx9K090099 at apollo.backplane.com> <20080703212717.a70f80d7.bastyaelvtars at gmail.com> <200807152209.m6FM98cj010364 at apollo.backplane.com> <487D27E1.9070305 at online.de> <487D3398.2080004 at fs.ei.tum.de> <200807160128.m6G1SI84011776 at apollo.backplane.com> <487DB323.9060208 at fs.e
i.tum.de>
Sender: bugs-errors at crater.dragonflybsd.org
Errors-To: bugs-errors at 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 at backplane.com>