src/fat.c

   1 /* fat.c - Read/write access to the FAT
   2
   3    Copyright (C) 1993 Werner Almesberger <werner.almesberger@lrc.di.epfl.ch>
   4    Copyright (C) 1998 Roman Hodek <Roman.Hodek@informatik.uni-erlangen.de>
   5
   6    This program is free software: you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation, either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program. If not, see <http://www.gnu.org/licenses/>.
  18
  19    On Debian systems, the complete text of the GNU General Public License
  20    can be found in /usr/share/common-licenses/GPL-3 file.
  21 */
  22
  23 /* FAT32, VFAT, Atari format support, and various fixes additions May 1998
  24  * by Roman Hodek <Roman.Hodek@informatik.uni-erlangen.de> */
  25
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <unistd.h>
  31
  32 #include "common.h"
  33 #include "dosfsck.h"
  34 #include "io.h"
  35 #include "check.h"
  36 #include "fat.h"
  37
  38
  39 /**
  40  * Fetch the FAT entry for a specified cluster.
  41  *
  42  * @param[out]  entry       Cluster to which cluster of interest is linked
  43  * @param[in]   fat         FAT table for the partition
  44  * @param[in]   cluster     Cluster of interest
  45  * @param[in]   fs          Information from the FAT boot sectors (bits per FAT entry)
  46  */
  47 void get_fat(FAT_ENTRY *entry,void *fat,unsigned long cluster,DOS_FS *fs)
  48 {
  49     unsigned char *ptr;
  50
  51     switch(fs->fat_bits) {
  52       case 12:
  53         ptr = &((unsigned char *) fat)[cluster*3/2];
  54         entry->value = 0xfff & (cluster & 1 ? (ptr[0] >> 4) | (ptr[1] << 4) :
  55           (ptr[0] | ptr[1] << 8));
  56         break;
  57       case 16:
  58         entry->value = CF_LE_W(((unsigned short *) fat)[cluster]);
  59         break;
  60       case 32:
  61         /* According to M$, the high 4 bits of a FAT32 entry are reserved and
  62          * are not part of the cluster number. So we cut them off. */
  63         {
  64             unsigned long e = CF_LE_L(((unsigned int *) fat)[cluster]);
  65             entry->value = e & 0xfffffff;
  66             entry->reserved = e >> 28;
  67         }
  68         break;
  69       default:
  70         die("Bad FAT entry size: %d bits.",fs->fat_bits);
  71     }
  72 }
  73
  74
  75 /**
  76  * Build a bookkeeping structure from the partition's FAT table.
  77  * If the partition has multiple FATs and they don't agree, try to pick a winner,
  78  * and queue a command to overwrite the loser.
  79  * One error that is fixed here is a cluster that links to something out of range.
  80  *
  81  * @param[inout]    fs      Information about the filesystem
  82  */
  83 void read_fat(DOS_FS *fs)
  84 {
  85     int eff_size;
  86     unsigned long i;
  87     void *first,*second = NULL;
  88     int first_ok,second_ok;
  89     unsigned long total_num_clusters;
  90
  91     /* Clean up from previous pass */
  92     free(fs->fat);
  93     free(fs->cluster_owner);
  94     fs->fat = NULL;
  95     fs->cluster_owner = NULL;
  96
  97     total_num_clusters = fs->clusters + 2UL;
  98     eff_size = (total_num_clusters*fs->fat_bits+7)/8ULL;
  99     first = alloc(eff_size);
 100     fs_read(fs->fat_start,eff_size,first);
 101     if (fs->nfats > 1) {
 102         second = alloc(eff_size);
 103         fs_read(fs->fat_start+fs->fat_size,eff_size,second);
 104     }
 105     if (second && memcmp(first,second,eff_size) != 0) {
 106         FAT_ENTRY first_media, second_media;
 107         get_fat(&first_media,first,0,fs);
 108         get_fat(&second_media,second,0,fs);
 109         first_ok = (first_media.value & FAT_EXTD(fs)) == FAT_EXTD(fs);
 110         second_ok = (second_media.value & FAT_EXTD(fs)) == FAT_EXTD(fs);
 111         if (first_ok && !second_ok) {
 112             printf("FATs differ - using first FAT.\n");
 113             fs_write(fs->fat_start+fs->fat_size,eff_size,first);
 114         }
 115         if (!first_ok && second_ok) {
 116             printf("FATs differ - using second FAT.\n");
 117             fs_write(fs->fat_start,eff_size,second);
 118             memcpy(first,second,eff_size);
 119         }
 120         if (first_ok && second_ok) {
 121             if (interactive) {
 122                 printf("FATs differ but appear to be intact. Use which FAT ?\n"
 123                   "1) Use first FAT\n2) Use second FAT\n");
 124                 if (get_key("12","?") == '1') {
 125                     fs_write(fs->fat_start+fs->fat_size,eff_size,first);
 126                 } else {
 127                     fs_write(fs->fat_start,eff_size,second);
 128                     memcpy(first,second,eff_size);
 129                 }
 130             }
 131             else {
 132                 printf("FATs differ but appear to be intact. Using first "
 133                   "FAT.\n");
 134                 fs_write(fs->fat_start+fs->fat_size,eff_size,first);
 135             }
 136         }
 137         if (!first_ok && !second_ok) {
 138             printf("Both FATs appear to be corrupt. Giving up.\n");
 139             exit(1);
 140         }
 141     }
 142     if (second) {
 143           free(second);
 144     }
 145     fs->fat = (unsigned char*) first;
 146
 147     fs->cluster_owner = alloc(total_num_clusters * sizeof(DOS_FILE *));
 148     memset(fs->cluster_owner, 0, (total_num_clusters * sizeof(DOS_FILE *)));
 149
 150     /* Truncate any cluster chains that link to something out of range */
 151     for (i = 2; i < fs->clusters+2; i++) {
 152         FAT_ENTRY curEntry;
 153         get_fat(&curEntry, fs->fat, i, fs);
 154         if (curEntry.value == 1) {
 155             printf("Cluster %ld out of range (1). Setting to EOF.\n",
 156                    i-2);
 157             set_fat(fs, i, -1);
 158         }
 159         if (curEntry.value >= fs->clusters+2 &&
 160             (curEntry.value < FAT_MIN_BAD(fs))) {
 161             printf("Cluster %ld out of range (%ld > %ld). Setting to EOF.\n",
 162                    i-2, curEntry.value, fs->clusters+2-1);
 163             set_fat(fs,i,-1);
 164         }
 165     }
 166 }
 167
 168
 169 /**
 170  * Update the FAT entry for a specified cluster
 171  * (i.e., change the cluster it links to).
 172  * Queue a command to write out this change.
 173  *
 174  * @param[in,out]   fs          Information about the filesystem
 175  * @param[in]       cluster     Cluster to change
 176  * @param[in]       new         Cluster to link to
 177  *                              Special values:
 178  *                                 0 == free cluster
 179  *                                -1 == end-of-chain
 180  *                                -2 == bad cluster
 181  */
 182 void set_fat(DOS_FS *fs,unsigned long cluster,unsigned long new)
 183 {
 184     unsigned char *data = NULL;
 185     int size;
 186     loff_t offs;
 187
 188     if ((long)new == -1)
 189         new = FAT_EOF(fs);
 190     else if ((long)new == -2)
 191         new = FAT_BAD(fs);
 192     switch( fs->fat_bits ) {
 193       case 12:
 194         data = fs->fat + cluster*3/2;
 195         offs = fs->fat_start+cluster*3/2;
 196         if (cluster & 1) {
 197             FAT_ENTRY prevEntry;
 198             get_fat(&prevEntry, fs->fat, cluster-1, fs);
 199             data[0] = ((new & 0xf) << 4) | (prevEntry.value >> 8);
 200             data[1] = new >> 4;
 201         }
 202         else {
 203             FAT_ENTRY subseqEntry;
 204             get_fat(&subseqEntry, fs->fat, cluster+1, fs);
 205             data[0] = new & 0xff;
 206             data[1] = (new >> 8) | (cluster == fs->clusters-1 ? 0 :
 207               (0xff & subseqEntry.value) << 4);
 208         }
 209         size = 2;
 210         break;
 211       case 16:
 212         data = fs->fat + cluster*2;
 213         offs = fs->fat_start+cluster*2;
 214         *(unsigned short *) data = CT_LE_W(new);
 215         size = 2;
 216         break;
 217       case 32:
 218         {
 219             FAT_ENTRY curEntry;
 220             get_fat(&curEntry, fs->fat, cluster, fs);
 221
 222             data = fs->fat + cluster*4;
 223             offs = fs->fat_start+cluster*4;
 224             /* According to M$, the high 4 bits of a FAT32 entry are reserved and
 225              * are not part of the cluster number. So we never touch them. */
 226             *(unsigned long *) data = CT_LE_L( (new & 0xfffffff) |
 227                                                (curEntry.reserved << 28) );
 228             size = 4;
 229         }
 230         break;
 231       default:
 232         die("Bad FAT entry size: %d bits.",fs->fat_bits);
 233     }
 234     fs_write(offs,size,data);
 235     if (fs->nfats > 1) {
 236         fs_write(offs+fs->fat_size,size,data);
 237     }
 238 }
 239
 240
 241 int bad_cluster(DOS_FS *fs,unsigned long cluster)
 242 {
 243     FAT_ENTRY curEntry;
 244     get_fat(&curEntry, fs->fat, cluster, fs);
 245
 246     return FAT_IS_BAD(fs, curEntry.value);
 247 }
 248
 249
 250 /**
 251  * Get the cluster to which the specified cluster is linked.
 252  * If the linked cluster is marked bad, abort.
 253  *
 254  * @param[in]   fs          Information about the filesystem
 255  * @param[in]   cluster     Cluster to follow
 256  *
 257  * @return  -1              'cluster' is at the end of the chain
 258  * @return  Other values    Next cluster in this chain
 259  */
 260 unsigned long next_cluster(DOS_FS *fs,unsigned long cluster)
 261 {
 262     unsigned long value;
 263     FAT_ENTRY curEntry;
 264
 265     get_fat(&curEntry, fs->fat, cluster, fs);
 266
 267     value = curEntry.value;
 268     if (FAT_IS_BAD(fs,value))
 269         die("Internal error: next_cluster on bad cluster");
 270     return FAT_IS_EOF(fs,value) ? -1 : value;
 271 }
 272
 273
 274 loff_t cluster_start(DOS_FS *fs,unsigned long cluster)
 275 {
 276     return fs->data_start+((loff_t)cluster-2)*(unsigned long long)fs->cluster_size;
 277 }
 278
 279
 280 /**
 281  * Update internal bookkeeping to show that the specified cluster belongs
 282  * to the specified dentry.
 283  *
 284  * @param[in,out]   fs          Information about the filesystem
 285  * @param[in]       cluster     Cluster being assigned
 286  * @param[in]       owner       Information on dentry that owns this cluster
 287  *                              (may be NULL)
 288  */
 289 void set_owner(DOS_FS *fs,unsigned long cluster,DOS_FILE *owner)
 290 {
 291     if (fs->cluster_owner == NULL)
 292         die("Internal error: attempt to set owner in non-existent table");
 293
 294     if (owner && fs->cluster_owner[cluster] && (fs->cluster_owner[cluster] != owner))
 295         die("Internal error: attempt to change file owner");
 296     fs->cluster_owner[cluster] = owner;
 297 }
 298
 299
 300 DOS_FILE *get_owner(DOS_FS *fs,unsigned long cluster)
 301 {
 302     if (fs->cluster_owner == NULL)
 303         return NULL;
 304     else
 305         return fs->cluster_owner[cluster];
 306 }
 307
 308
 309 void fix_bad(DOS_FS *fs)
 310 {
 311     unsigned long i;
 312
 313     if (verbose)
 314         printf("Checking for bad clusters.\n");
 315     for (i = 2; i < fs->clusters+2; i++) {
 316         FAT_ENTRY curEntry;
 317         get_fat(&curEntry, fs->fat, i, fs);
 318
 319         if (!get_owner(fs,i) && !FAT_IS_BAD(fs, curEntry.value))
 320             if (!fs_test(cluster_start(fs,i),fs->cluster_size)) {
 321                 printf("Cluster %lu is unreadable.\n",i);
 322                 set_fat(fs,i,-2);
 323             }
 324     }
 325 }
 326
 327
 328 void reclaim_free(DOS_FS *fs)
 329 {
 330     int reclaimed;
 331     unsigned long i;
 332
 333     if (verbose)
 334         printf("Checking for unused clusters.\n");
 335     reclaimed = 0;
 336     for (i = 2; i < fs->clusters+2; i++) {
 337         FAT_ENTRY curEntry;
 338         get_fat(&curEntry, fs->fat, i, fs);
 339
 340         if (!get_owner(fs,i) && curEntry.value &&
 341             !FAT_IS_BAD(fs, curEntry.value)) {
 342             set_fat(fs,i,0);
 343             reclaimed++;
 344         }
 345     }
 346     if (reclaimed)
 347         printf("Reclaimed %d unused cluster%s (%llu bytes).\n",reclaimed,
 348           reclaimed == 1 ?  "" : "s",(unsigned long long)reclaimed*fs->cluster_size);
 349 }
 350
 351
 352 /**
 353  * Assign the specified owner to all orphan chains (except cycles).
 354  * Break cross-links between orphan chains.
 355  *
 356  * @param[in,out]   fs             Information about the filesystem
 357  * @param[in]       owner          dentry to be assigned ownership of orphans
 358  * @param[in,out]   num_refs       For each orphan cluster [index], how many
 359  *                                 clusters link to it.
 360  * @param[in]       start_cluster  Where to start scanning for orphans
 361  */
 362 static void tag_free(DOS_FS *fs, DOS_FILE *owner, unsigned long *num_refs,
 363                      unsigned long start_cluster)
 364 {
 365     int prev;
 366     unsigned long i,walk;
 367
 368     if (start_cluster == 0)
 369         start_cluster = 2;
 370
 371     for (i = start_cluster; i < fs->clusters+2; i++) {
 372         FAT_ENTRY curEntry;
 373         get_fat(&curEntry, fs->fat, i, fs);
 374
 375         /* If the current entry is the head of an un-owned chain... */
 376         if (curEntry.value && !FAT_IS_BAD(fs, curEntry.value) &&
 377             !get_owner(fs, i) && !num_refs[i]) {
 378             prev = 0;
 379             /* Walk the chain, claiming ownership as we go */
 380             for (walk = i; walk != -1;
 381                  walk = next_cluster(fs,walk)) {
 382                 if (!get_owner(fs, walk)) {
 383                     set_owner(fs, walk, owner);
 384                 } else {
 385                     /* We've run into cross-links between orphaned chains,
 386                      * or a cycle with a tail.
 387                      * Terminate this orphan chain (break the link)
 388                      */
 389                         set_fat(fs,prev,-1);
 390
 391                     /* This is not necessary because 'walk' is owned and thus
 392                      * will never become the head of a chain (the only case
 393                      * that would matter during reclaim to files).
 394                      * It's easier to decrement than to prove that it's
 395                      * unnecessary.
 396                      */
 397                     num_refs[walk]--;
 398                         break;
 399                     }
 400                 prev = walk;
 401             }
 402         }
 403     }
 404 }
 405
 406 /**
 407  * Recover orphan chains to files, handling any cycles or cross-links.
 408  *
 409  * @param[in,out]   fs             Information about the filesystem
 410  */
 411 void reclaim_file(DOS_FS *fs)
 412 {
 413     DOS_FILE orphan;
 414     int reclaimed,files;
 415     int changed = 0;
 416     unsigned long i,next,walk;
 417     unsigned long *num_refs = NULL;     /* Only for orphaned clusters */
 418     unsigned long total_num_clusters;
 419
 420     if (verbose)
 421         printf("Reclaiming unconnected clusters.\n");
 422
 423     total_num_clusters = fs->clusters + 2UL;
 424     num_refs = alloc(total_num_clusters * sizeof(unsigned long));
 425     memset(num_refs, 0, (total_num_clusters * sizeof(unsigned long)));
 426
 427     /* Guarantee that all orphan chains (except cycles) end cleanly
 428      * with an end-of-chain mark.
 429      */
 430
 431     for (i = 2; i < total_num_clusters; i++) {
 432         FAT_ENTRY curEntry;
 433         get_fat(&curEntry, fs->fat, i, fs);
 434
 435         next = curEntry.value;
 436         if (!get_owner(fs,i) && next && next < fs->clusters+2) {
 437             /* Cluster is linked, but not owned (orphan) */
 438             FAT_ENTRY nextEntry;
 439             get_fat(&nextEntry, fs->fat, next, fs);
 440
 441             /* Mark it end-of-chain if it links into an owned cluster,
 442              * a free cluster, or a bad cluster.
 443              */
 444             if (get_owner(fs,next) || !nextEntry.value ||
 445                 FAT_IS_BAD(fs, nextEntry.value)) set_fat(fs,i,-1);
 446             else
 447                 num_refs[next]++;
 448         }
 449     }
 450
 451     /* Scan until all the orphans are accounted for,
 452      * and all cycles and cross-links are broken
 453      */
 454     do {
 455         tag_free(fs, &orphan, num_refs, changed);
 456         changed = 0;
 457
 458         /* Any unaccounted-for orphans must be part of a cycle */
 459         for (i = 2; i < total_num_clusters; i++) {
 460             FAT_ENTRY curEntry;
 461             get_fat(&curEntry, fs->fat, i, fs);
 462
 463             if (curEntry.value && !FAT_IS_BAD(fs, curEntry.value) &&
 464                 !get_owner(fs, i)) {
 465                 if (!num_refs[curEntry.value]--)
 466                     die("Internal error: num_refs going below zero");
 467                 set_fat(fs,i,-1);
 468                 changed = curEntry.value;
 469                 printf("Broke cycle at cluster %lu in free chain.\n",i);
 470
 471                 /* If we've created a new chain head,
 472                  * tag_free() can claim it
 473                  */
 474                 if (num_refs[curEntry.value] == 0)
 475                 break;
 476             }
 477         }
 478     }
 479     while (changed);
 480
 481     /* Now we can start recovery */
 482     files = reclaimed = 0;
 483     for (i = 2; i < total_num_clusters; i++)
 484         /* If this cluster is the head of an orphan chain... */
 485         if (get_owner(fs, i) == &orphan && !num_refs[i]) {
 486             DIR_ENT de;
 487             loff_t offset;
 488             files++;
 489             offset = alloc_rootdir_entry(fs,&de,"FSCK%04dREC");
 490             de.start = CT_LE_W(i&0xffff);
 491             if (fs->fat_bits == 32)
 492                 de.starthi = CT_LE_W(i>>16);
 493             for (walk = i; walk > 0 && walk != -1;
 494                  walk = next_cluster(fs,walk)) {
 495                 de.size = CT_LE_L(CF_LE_L(de.size)+fs->cluster_size);
 496                 reclaimed++;
 497             }
 498             fs_write(offset,sizeof(DIR_ENT),&de);
 499         }
 500     if (reclaimed)
 501         printf("Reclaimed %d unused cluster%s (%llu bytes) in %d chain%s.\n",
 502           reclaimed,reclaimed == 1 ? "" : "s",(unsigned long long)reclaimed*fs->cluster_size,files,
 503           files == 1 ? "" : "s");
 504
 505     free(num_refs);
 506 }
 507
 508
 509 unsigned long update_free(DOS_FS *fs)
 510 {
 511     unsigned long i;
 512     unsigned long free = 0;
 513     int do_set = 0;
 514
 515     for (i = 2; i < fs->clusters+2; i++) {
 516         FAT_ENTRY curEntry;
 517         get_fat(&curEntry, fs->fat, i, fs);
 518
 519         if (!get_owner(fs,i) && !FAT_IS_BAD(fs, curEntry.value))
 520             ++free;
 521     }
 522
 523     if (!fs->fsinfo_start)
 524         return free;
 525
 526     if (verbose)
 527         printf("Checking free cluster summary.\n");
 528     if (fs->free_clusters != 0xFFFFFFFF) {
 529         if (free != fs->free_clusters) {
 530             printf( "Free cluster summary wrong (%ld vs. really %ld)\n",
 531                     fs->free_clusters,free);
 532             if (interactive)
 533                 printf( "1) Correct\n2) Don't correct\n" );
 534             else printf( "  Auto-correcting.\n" );
 535             if (!interactive || get_key("12","?") == '1')
 536                 do_set = 1;
 537         }
 538     }
 539     else {
 540         printf( "Free cluster summary uninitialized (should be %ld)\n", free );
 541         if (rw) {
 542             if (interactive)
 543                 printf( "1) Set it\n2) Leave it uninitialized\n" );
 544             else printf( "  Auto-setting.\n" );
 545             if (!interactive || get_key("12","?") == '1')
 546                 do_set = 1;
 547         }
 548     }
 549
 550     if (do_set) {
 551         unsigned long le_free = CT_LE_L(free);
 552         fs->free_clusters = free;
 553         fs_write(fs->fsinfo_start+offsetof(struct info_sector,free_clusters),
 554                  sizeof(le_free), &le_free);
 555     }
 556
 557     return free;
 558 }