[lkml]   [2000]   [Jan]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: Suggestion: a garbage-collected file system
Also sprach Sean Hunter:
} On Mon, Jan 10, 2000 at 04:26:40PM +0100, David Madore wrote:
} > 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.
} Has it occurred to you that using reference counting to decide when to
} free disk resources _is_ garbage collection?
A primitive form of gc, but yes, in a way.

[baroque snippage]
} > 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).
} Err, ok
} User "sam" is a trusting soul, and gives me permission to read files
} in her "shared" directory. After a while we do more work together,
} and the "shared" directory gets moved into my directory.
} so my "work" directory contains sam's "shared" directory. Now I can
} remove my "work" directory (because I own it), and because the gcfs
} doesn't mind me deleteing a dir that still contains files, Sam won't
} be able to reference her files via the root filesystem. To cap it
} all, when she quits that long-running emacs session that has them all
} open, the kernel will helpfully garbage-collect them for her.
} Great! (Extrapolate to root if you're not too bored already)
"sam" would still have a reference to her stuff, so the gc would not
collect that garbage, one would think.

} > 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.
} Make sure it can handle infinitely nested circular references like the
} above example. That was a trivial case off the top of mind head. I'm
} sure a genuinely devious mind like Al Viro would be able to come up
} with some much nastier ones.
Traditional gc's used with programs have to deal with really convoluted
things too...

|| Bill Wendling

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:55    [W:0.091 / U:1.448 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site