FAT integrity

Arkady posted this interesting bit of information to the FreeDOS mailing list about checking the FAT integrity. What I thought was great is that Arkady posted it in pseudo-code format, which I am attempting to reproduce in html:


How to check the FAT integrity: (checking partition table, BPB and file names integrity is an another story)

1. Let assume we have enough memory to read entire FAT (note: FAT12 requires up to 5.9K, FAT16 - 126K) and then keep [sorted] array with two values per each file on the disk (starting cluster and clusters counter).

1.1. read FAT;

1.2. read second (and later, if present) FAT copies and compare it with first FAT copy (if second FAT not fit in memory then you may read it in parts down to sector size) - they should be equal;

1.3. check all entries: valid entry value should be >2 and less than clusters in partition (don't forget to check if FAT size valid);

1.4. find all chains and remember they first cluster and size:
{

1.4.1. if no more allocated entry (value >2 and not "reserved" nor "bad") in FAT then step 1.5;

1.4.2. remember found entry as "starting cluster" in next free array item and init "clusters counter" in array by 1;

1.4.3. remember found entry value in variable E and init entry by 1;
{

1.4.4. if E == EOF (i.e. we found chain end) then step 1.4.1;

1.4.5. if entry at position E == 1 then step 1.4.9;

1.4.6. if entry at position E == 2 then ERROR (cross-link);

1.4.7. if entry at position E == "free"/"bad"/"reserved" then ERROR (unterminated chain);

1.4.8. increment last "clusters counter", remember entry value at position E in E, init this entry by 2 and goto 1.4.4;

}

1.4.9. find E value as "starting cluster" in array then replace found "starting cluster" by value from new/last item, add new/last "clusters counter" to found, free new/last array item and goto step 1.4.1;

}

1.5. read all directories and check they entries against array/FAT:
{

1.5.1. if entry."starting cluster" point to 2 in FAT then ERROR (cross-link);

1.5.2. if entry not point to 1 in FAT then ERROR (unterminated chain);

1.5.3. replace FAT entry by 2;

1.5.3. find starting cluster in array and check "cluster count" against (file_size + cluster_size - 1)/cluster_size;

}