Messages in this thread | | | Date | Tue, 11 Jan 2000 12:05:49 -0600 | From | Bill Wendling <> | Subject | Re: 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 wendling@ganymede.isdn.uiuc.edu
- 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/
| |