Re: A couple of questions

[Kuba Ober <kuba@mareimbrium.org>]

On pi±tek 17 maj 2002 09:11 am, berthiaume_wayne@emc.com wrote:
> Kuba, I guess the question that should be posed this way: What is
> the downside of not asking the user and just fixing what can be fixed? Is
> there a potential for unrepairable damage if you were to fix blindly
> without "user" intervention?

The downside is that with fsck's that are quick hacks, you really require user 
to know a lot, and you ask complicated questions.

Fsck should *first* get all the information it can from the fs and digest it. 
Only then can it try to fix things, and ask questions about things that are 
doubtful. There are certain things that are 99.999995 true, almost 
assertions, because certain damage patterns have extremely slim chances of 
occuring.

This is essentially a way to formulate fsck algorithm in terms similar to some 
expert systems.

Example: I'll use FAT16 for the example fs, since I assume most people know it 
well enough. With FAT16 filesystem, it was quite easy to discern clusters 
occupied by directories from clusters occupied by file data. And then, there 
was more data that increased the probablity that you indeed had a proper 
directory cluster. It might have went in steps:
(assuming all fat copies were zeroed)
1. Read all disk clusters, detect those that are probable directories basing 
solely on cluster contents. Define an "is-directory" property for each 
cluster. Assign 0 to this property in those clusters which failed detection 
in this step, and 0.8 to clusters which were detected.
2. Check for mutual links between directories detected thus far (the forward 
and backward links). Bump the "is-directory" probabilities for clusters that 
have passed to 1.0.
3. Assign "is-first-cluster" probabilities for all clusters. Set them to value 
of "is-directory" from the directory cluster that contained an entry pointing 
to this cluster, or 0 if nothing points to them.
4. Check for consecutive directory clusters, starting at all clusters having 
is-first-cluster > 0 && is-directory > 0. Bump "is-directory" basing on 
best-known neighbors, etc, ...

There were many shortcuts taken here, since I ignore multiply-linked entries, 
loops, etc. It was meant as example of the idea, not implementation.  There 
is a lot of what-if kind of approach in fs recovery, and by providing an 
expert-system fuzzy-logic (ie non-binary) approach, there can be a lot of 
knowledge gained about a filesystem without asking a single question. We're 
really looking for answers if we depend on a piece of information in doing a 
recovery decision, and we consider the information we have to be too 
doubtful.

That also means that the fsck/recovery program needs to do a lot of stuff, a 
lot more than one thinks. The typical "multi-pass" approach where errors are 
fixed from lower-level to higher-level is wrong, since it inherently either 
looses information, or doesn't have it yet in earlier steps.

There can be only three passes: gather data from the media, ask additional 
questions to the user if they are needed, do the fixes. I don't see it any 
other way, and I was always thinking of an ideal fsck tool in these terms 
since I was about 12 (late 80's, already had a third HD in my 286/8 machine, 
and had done a few recovery operations with diskeditor). An example of wrong 
approach is say norton disk doctor, on FAT16: it would first check FAT, fix 
that, and only afterwards check & fix directory structure -- it looses a lot 
of information that each of the passes keeps to itself, eg. fixing cluster 
chains in FAT doesn't really look at what those clusters contain, etc.

Cheers, Kuba