Re: Shrinking ext3 directories (repost)

Originally to:

To: Christopher Li <chrisl@xxxxxxxxxxxx>, <ext2-devel@xxxxxxxxxxxxxxxxxxxxx>
Cc: Andreas Dilger <adilger@xxxxxxxxxxxxx>, "Stephen C. Tweedie"

On Wednesday 19 June 2002 19:03, Christopher Li wrote:
> On Wed, 19 Jun 2002, Stephen C. Tweedie wrote:
> > On Tue, Jun 18, 2002 at 06:18:49PM -0400, Alexander Viro wrote:
> >
> > > IOW, making sure that empty blocks in the end of directory get freed
> > > is a matter of 10-20 lines. If you want such patch - just tell, it's
> > > half an hour of work...
> >
> > It's certainly easier at the tail, but with htree we may have
> > genuinely enormous directories and being able to hole-punch arbitrary
> > coalesced blocks could be a huge win. Also, doing the coalescing
> I would can contribute on that. I am thinking about it anyway.
> Daniel might already has some code there.

Here's some very skeletal pseudocode for the coalesce algorithm we've
been talking about. It should expand into about 200 lines without the
recursive index coalesce, which we can be lazy about and implement
later. I didn't handle the corner cases where the upper or lower leaves
don't exist. I also didn't say anything about what to do when they're
not in the same index block - we might as well treat that the same as
the 'doesn't exist' case for now.

First, the easy part:

static inline unsigned dx_get_fullness(struct dx_entry *entry)
return le32_to_cpu(entry->block.v) >> 24;

static void dx_set_block(struct dx_entry *entry, unsigned value)
entry->block.v = cpu_to_le32((dx_get_fullness(entry) << 24) | value);

static void dx_set_fullness(struct dx_entry *entry, unsigned value)
entry->block.v = cpu_to_le32(dx_get_block(entry) | (value << 24));

All the coalesce action is in delete:

<we just removed an entry>

fullness = <added up usage below entry before + add up usage above>
fullness_shift = blocksize_bits - 8;
threshold = <depends on blocksize>;

if (dx_get_fullness(at) != fullness >> fullness_shift) {
dx_set_fullness(at, round_it_down(fullness >> fullness_shift));
mark_dirty(<the index block>);

while (1) {
upper = (dx_get_fullness(upper_entry()) << fullness_shift);
lower = (dx_get_fullness(lower_entry()) << fullness_shirt);

if (max(upper, lower) + fullness > threshold)

merge_entry = upper < lower? lower_entry: upper_entry;
if (fullness + compute_fullness(merge_entry) < blocksize) {
<choose destination>
<from bottom to top, compact entries of destination>
<copy in entries of vacated block>
<remove vacated index entry>
<recursive coalesce of index blocks goes here>
<copy last block to vacated block>
<update index entry of last block>
<shorten directory>

actual = compute_fullness(merge_entry);
dx_set_fullness(merge_entry, min(255, (actual >> 24) +
!!(actual & 0xffffff)));
mark_dirty(<the index block>);


Sponsored by:
ThinkGeek at