[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.031 / U:0.976 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site