DragonFly bugs List (threaded) for 2008-07
From: Matthew Dillon <firstname.lastname@example.org>
Subject: Re: hammer_alloc_data panic
Date: Wed, 16 Jul 2008 09:25:53 -0700 (PDT)
References: <email@example.com> <firstname.lastname@example.org> <200807022320.m62NKCJK082805@apollo.backplane.com> <email@example.com> <200807031726.m63HQx9K090099@apollo.backplane.com> <firstname.lastname@example.org> <200807152209.m6FM98cj010364@apollo.backplane.com> <487D27E1.email@example.com> <487D3398.firstname.lastname@example.org> <200807160128.m6G1SI84011776@apollo.backplane.com> <487DB323.email@example.com
X-Trace: 1216226442 crater_reader.dragonflybsd.org 851 220.127.116.11
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?
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.