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/
This archive was generated by hypermail 2b29 : Sat Jan 15 2000 - 21:00:18 EST