[lkml]   [2000]   [Jan]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: Suggestion: a garbage-collected file system
"Towers, Tim (London)" <ttowers@MLE.CO.UK>:
>My problem with this is how to mark something as deletable? in
>such a way as you can undelete it when necessary
>You also shouldn't be using a deleted file - though should you
>see it in its old place? Changing its owner & permissions
>(uid=-4,perms=0x1000) could do that, but whilst we can trap
>the unlink in user space changing ownerships and enabling
>a special "overwrite" case would require kernel changes (since
>anyone should be able to overwrite a deleted file). Contrariwise,
>a user-space application could be used to retrieve the old file
>permissions, effectively restoring the file.

There are several utilities that open a scratch file, unlink it, then
write/read it. This permits simple cleanup on exit. The last link to
the file is removed when the process exits, THEN the file is deleted.

The major difficulty with a general GC cleanup is the time it takes to
do the cleanup. A mark-and-sweep algorithm requires two complete passes
through the data space. The reference counting technique is used only
because it is fast, and incremental. The general GC cleanup also has
a crash recovery problem. Each time a restart occurs a full GC cleanup
has to be done. Recovery of "lost" files is not possible, since they
are "deleted". A mark-and-sweep scan used to take .5 second or so for
a 100MB memory sweep. Consider how long that will take for a small 8GB
of disk (even dividing by 4096, thats still over 2 million units; Including
the I/O time you should get something on the order of 1/2 hour per
recovery pass (worst case 2 - 5 hours - two read/write cycles). Attempting
to do this in memory using bitmaps to support the mark cycle requires
consideration of how large the bitmap can get.

Other background information - try to find some details on the old
Symbolics Lisp machine. I think they were doing a GC file system. I used
one once, just to see what it was like. The hardware should have had
the capability to keep up with a VAX 780 single cpu, but the throughput
was about like a pentium 75 MHZ PC. I'm not blaiming it on the fs though,
just their general GC was slooow for the system.
Jesse I Pollard, II
Any opinions expressed are solely my own.

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.166 / U:0.776 seconds]
©2003-2011 Jasper Spaans