Re: ext2fs enhacement/fix [re: shrinking directories]

Jan Kara (jack@atrey.karlin.mff.cuni.cz)
Sun, 19 Jul 1998 23:23:23 +0200

>
> an opportunity for a simple heuristic or a /proc ctl. even a mount
> option.
>
> even a partial sort. as in when a file is accessed, that struct is bumped
> up one index if it isn't in the dcache or it's access time is greater than
> the tuned limit. reason why i say that is because it limits the amount of
> structure updating. over time, all the frequently used entries will sit
> at the top and the aged and ghost entries at the bottom.
OK. It would probably need something which will prevent "swapping" of often
used entries in the beggining of the directory.... But it's true this won't
take much time (OK, I'm not quite sure because you'll need a write of a block
in addition but buffer-cache might lower the impact of it).
>
> this will make for a very fast shrink procedure if the shrink procedure is
> called an order of times greater than the struct update period.
>

> this serves to mimise the impact of sorting from the most used entries to
> the ghost entries and minimise the expense of a shrink procedure.
There is a question how long will the "way" of entry through dir last in the
case of big directories, but it depends on some constants and probably only
testing can offer reliable results.
> do bear in mind i'm hardly lucid after a few days and only a few hours of
> sleep. :)
I also haven't slept lot in last days (gone to bed about 3 o'clock in the morning
and woken about 8 :).

Looking on ext2_rmdir code I was hit by an idea (it happens only rarely:).
When ext2 is freeing the dir-entry it tries to "recombine" the free space.
If there is a free entry before the freed one (only in the same block), it
will concatenate the free space. Maybe it could also concatenate with the
following entry, if it's free... We can also make concatenating across the
block boundaries but the effect of this might be uncertain...

Good night and sweet dreams wishes
Honza :)

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.altern.org/andrebalsa/doc/lkml-faq.html