Hi everybody.
There's something I would like to try implementing, and that is a
garbage-collected file system for Linux.
Such a filesystem (``gcfs'') would not use reference-counting (as is
done on inodes) to decide when to free disk resources, but rather, it
would garbage-collect the directory structure.
The advantage of this is that in such a filesystem we can remove some
of the irritating limitations that Unix filesystems traditionally are
subject to because of the requirements imposed by the
reference-counting strategy.
In plain English: in the gcfs, hard links are permitted on
directories; is is permitted to move or link a directory to a
subdirectory of itself (thus creating hard cycles in the filesystem);
and it is permitted to remove a non-empty directory (this creates a
``detached'' subtree that is no longer reachable from the root inode,
and that will be garbage-collected when all the open files and working
directories accessing the subtree are closed or removed).
There are many uses (some interesting and some simply very strange)
that a gcfs could be put to; but really I'm interested in this because
it sounds so cool.
There are essentially two classes of problems with this gcfs. Number
one, determine precisely what the garbage-collecting algorithm should
be. Number two, find how to adapt the Unix filesystem semantics to
garbage-collected data, and vice versa.
For number one, the garbage-collection algorithm I was thinking of
using is Baker's treadmill algorithm (with a write barrier), which is
documented in the book ``Garbage Collection: Algorithms for Automatic
Dynamic Memory Management'' by Jones and Lins (published by Wiley) in
section 8.8; I will describe it in more detail if I find some people
are interested in my proposal. It is a non-moving concurrent
garbage-collector. ``Concurrent'' means that a kernel thread would
take place of garbage-collecting in parallel with the normal
filesystem use. ``Non-moving'' means that data does not get shuffled
around while the collection takes place, something which is clearly
desirable for a filesystem (that is, moving is undesirable).
A lot of implementation details have to be settled. For example, the
treadmill algorithm works by organizing the data blocks (disk blocks
in this case) in a doubly linked circular list: where should the
points for this doubly linked list be stored? A barrier must be
placed to protect the collector from the actions of the mutator (``the
mutator'' refers to the processes using, and modifying, the
filesystem): I prefer a write barrier to a read barrier, but even this
leaves a lot of possibilities.
Number two, how do we implement this as a traditional filesystem? The
first question to be answered is whether the Linux VFS layer makes few
enough assumptions on the semantics of filesystems so that a gcfs is
possible. For example, it must not make the assumption anywhere that
to rmdir() a directory the directory must be empty. It must not make
the assumption that reference-counting is effectively used in the
filesystem. It must not make the assumption that the .. entry in a
directory points to the ``parent'' directory (something which is
rather meaningless in a gcfs). And so on. Or, if it makes these
assumptions, it must make them in a benign way, that is, it need can
be fooled into thinking that the filesystem has Unix semantics.
This is where I have insufficient knowledge of the kernel internals to
answer all these questions: can someone fill me up on this? It would
be a shame to start worrying about all the gc details only to discover
that the gcfs cannot be implemented under Linux because the VFS makes
some faulty assumptions about filesystem semantics.
This is certainly a fun think to work on. I'm not sure how difficult
it might be, though.
--
David A. Madore
(david.madore@ens.fr,
http://www.eleves.ens.fr:8080/home/madore/ )
-
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.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sat Jan 15 2000 - 21:00:15 EST