1/* fat.c - Read/write access to the FAT */ 2 3/* Written 1993 by Werner Almesberger */ 4 5/* FAT32, VFAT, Atari format support, and various fixes additions May 1998 6 * by Roman Hodek <Roman.Hodek@informatik.uni-erlangen.de> */ 7 8 9#include <stdio.h> 10#include <stdlib.h> 11#include <string.h> 12#include <unistd.h> 13 14#define _LINUX_STRING_H_ 15#include <linux/msdos_fs.h> 16 17#include "common.h" 18#include "dosfsck.h" 19#include "io.h" 20#include "check.h" 21#include "fat.h" 22 23 24static void get_fat(FAT_ENTRY *entry,void *fat,unsigned long cluster,DOS_FS *fs) 25{ 26 unsigned char *ptr; 27 28 switch(fs->fat_bits) { 29 case 12: 30 ptr = &((unsigned char *) fat)[cluster*3/2]; 31 entry->value = 0xfff & (cluster & 1 ? (ptr[0] >> 4) | (ptr[1] << 4) : 32 (ptr[0] | ptr[1] << 8)); 33 break; 34 case 16: 35 entry->value = CF_LE_W(((unsigned short *) fat)[cluster]); 36 break; 37 case 32: 38 /* According to M$, the high 4 bits of a FAT32 entry are reserved and 39 * are not part of the cluster number. So we cut them off. */ 40 { 41 unsigned long e = CF_LE_L(((unsigned long *) fat)[cluster]); 42 entry->value = e & 0xfffffff; 43 entry->reserved = e >> 28; 44 } 45 break; 46 default: 47 die("Bad FAT entry size: %d bits.",fs->fat_bits); 48 } 49 entry->owner = NULL; 50} 51 52 53void read_fat(DOS_FS *fs) 54{ 55 int eff_size; 56 unsigned long i; 57 void *first,*second,*use; 58 int first_ok,second_ok; 59 60 eff_size = ((fs->clusters+2)*fs->fat_bits+7)/8; 61 first = alloc(eff_size); 62 second = alloc(eff_size); 63 fs_read(fs->fat_start,eff_size,first); 64 fs_read(fs->fat_start+fs->fat_size,eff_size,second); 65 use = first; 66 if (memcmp(first,second,eff_size) != 0) { 67 FAT_ENTRY first_media, second_media; 68 get_fat(&first_media,first,0,fs); 69 get_fat(&second_media,second,0,fs); 70 first_ok = (first_media.value & FAT_EXTD(fs)) == FAT_EXTD(fs); 71 second_ok = (second_media.value & FAT_EXTD(fs)) == FAT_EXTD(fs); 72 if (first_ok && !second_ok) { 73 printf("FATs differ - using first FAT.\n"); 74 fs_write(fs->fat_start+fs->fat_size,eff_size,use = first); 75 } 76 if (!first_ok && second_ok) { 77 printf("FATs differ - using second FAT.\n"); 78 fs_write(fs->fat_start,eff_size,use = second); 79 } 80 if (first_ok && second_ok) { 81 if (interactive) { 82 printf("FATs differ but appear to be intact. Use which FAT ?\n" 83 "1) Use first FAT\n2) Use second FAT\n"); 84 if (get_key("12","?") == '1') 85 fs_write(fs->fat_start+fs->fat_size,eff_size,use = first); 86 else fs_write(fs->fat_start,eff_size,use = second); 87 } 88 else { 89 printf("FATs differ but appear to be intact. Using first " 90 "FAT.\n"); 91 fs_write(fs->fat_start+fs->fat_size,eff_size,use = first); 92 } 93 } 94 if (!first_ok && !second_ok) { 95 printf("Both FATs appear to be corrupt. Giving up.\n"); 96 exit(1); 97 } 98 } 99 fs->fat = qalloc(&mem_queue,sizeof(FAT_ENTRY)*(fs->clusters+2)); 100 for (i = 2; i < fs->clusters+2; i++) get_fat(&fs->fat[i],use,i,fs); 101 for (i = 2; i < fs->clusters+2; i++) 102 if (fs->fat[i].value >= fs->clusters+2 && 103 (fs->fat[i].value < FAT_MIN_BAD(fs))) { 104 printf("Cluster %ld out of range (%ld > %ld). Setting to EOF.\n", 105 i-2,fs->fat[i].value,fs->clusters+2-1); 106 set_fat(fs,i,-1); 107 } 108 free(first); 109 free(second); 110} 111 112 113void set_fat(DOS_FS *fs,unsigned long cluster,unsigned long new) 114{ 115 unsigned char data[4]; 116 int size; 117 loff_t offs; 118 119 if ((long)new == -1) 120 new = FAT_EOF(fs); 121 else if ((long)new == -2) 122 new = FAT_BAD(fs); 123 switch( fs->fat_bits ) { 124 case 12: 125 offs = fs->fat_start+cluster*3/2; 126 if (cluster & 1) { 127 data[0] = ((new & 0xf) << 4) | (fs->fat[cluster-1].value >> 8); 128 data[1] = new >> 4; 129 } 130 else { 131 data[0] = new & 0xff; 132 data[1] = (new >> 8) | (cluster == fs->clusters-1 ? 0 : 133 (0xff & fs->fat[cluster+1].value) << 4); 134 } 135 size = 2; 136 break; 137 case 16: 138 offs = fs->fat_start+cluster*2; 139 *(unsigned short *) data = CT_LE_W(new); 140 size = 2; 141 break; 142 case 32: 143 offs = fs->fat_start+cluster*4; 144 /* According to M$, the high 4 bits of a FAT32 entry are reserved and 145 * are not part of the cluster number. So we never touch them. */ 146 *(unsigned long *) data = CT_LE_L( (new & 0xfffffff) | 147 (fs->fat[cluster].reserved << 28) ); 148 size = 4; 149 break; 150 default: 151 die("Bad FAT entry size: %d bits.",fs->fat_bits); 152 } 153 fs->fat[cluster].value = new; 154 fs_write(offs,size,&data); 155 fs_write(offs+fs->fat_size,size,&data); 156} 157 158 159int bad_cluster(DOS_FS *fs,unsigned long cluster) 160{ 161 return FAT_IS_BAD(fs,fs->fat[cluster].value); 162} 163 164 165unsigned long next_cluster(DOS_FS *fs,unsigned long cluster) 166{ 167 unsigned long value; 168 169 value = fs->fat[cluster].value; 170 if (FAT_IS_BAD(fs,value)) 171 die("Internal error: next_cluster on bad cluster"); 172 return FAT_IS_EOF(fs,value) ? -1 : value; 173} 174 175 176loff_t cluster_start(DOS_FS *fs,unsigned long cluster) 177{ 178 return fs->data_start+((loff_t)cluster-2)*fs->cluster_size; 179} 180 181 182void set_owner(DOS_FS *fs,unsigned long cluster,DOS_FILE *owner) 183{ 184 if (owner && fs->fat[cluster].owner) 185 die("Internal error: attempt to change file owner"); 186 fs->fat[cluster].owner = owner; 187} 188 189 190DOS_FILE *get_owner(DOS_FS *fs,unsigned long cluster) 191{ 192 return fs->fat[cluster].owner; 193} 194 195 196void fix_bad(DOS_FS *fs) 197{ 198 unsigned long i; 199 200 if (verbose) 201 printf("Checking for bad clusters.\n"); 202 for (i = 2; i < fs->clusters+2; i++) 203 if (!get_owner(fs,i) && !FAT_IS_BAD(fs,fs->fat[i].value)) 204 if (!fs_test(cluster_start(fs,i),fs->cluster_size)) { 205 printf("Cluster %lu is unreadable.\n",i); 206 set_fat(fs,i,-2); 207 } 208} 209 210 211void reclaim_free(DOS_FS *fs) 212{ 213 int reclaimed; 214 unsigned long i; 215 216 if (verbose) 217 printf("Checking for unused clusters.\n"); 218 reclaimed = 0; 219 for (i = 2; i < fs->clusters+2; i++) 220 if (!get_owner(fs,i) && fs->fat[i].value && 221 !FAT_IS_BAD(fs,fs->fat[i].value)) { 222 set_fat(fs,i,0); 223 reclaimed++; 224 } 225 if (reclaimed) 226 printf("Reclaimed %d unused cluster%s (%d bytes).\n",reclaimed, 227 reclaimed == 1 ? "" : "s",reclaimed*fs->cluster_size); 228} 229 230 231static void tag_free(DOS_FS *fs,DOS_FILE *ptr) 232{ 233 DOS_FILE *owner; 234 int prev; 235 unsigned long i,walk; 236 237 for (i = 2; i < fs->clusters+2; i++) 238 if (fs->fat[i].value && !FAT_IS_BAD(fs,fs->fat[i].value) && 239 !get_owner(fs,i) && !fs->fat[i].prev) { 240 prev = 0; 241 for (walk = i; walk > 0 && walk != -1; 242 walk = next_cluster(fs,walk)) { 243 if (!(owner = get_owner(fs,walk))) set_owner(fs,walk,ptr); 244 else if (owner != ptr) 245 die("Internal error: free chain collides with file"); 246 else { 247 set_fat(fs,prev,-1); 248 break; 249 } 250 prev = walk; 251 } 252 } 253} 254 255 256void reclaim_file(DOS_FS *fs) 257{ 258 DOS_FILE dummy; 259 int reclaimed,files,changed; 260 unsigned long i,next,walk; 261 262 if (verbose) 263 printf("Reclaiming unconnected clusters.\n"); 264 for (i = 2; i < fs->clusters+2; i++) fs->fat[i].prev = 0; 265 for (i = 2; i < fs->clusters+2; i++) { 266 next = fs->fat[i].value; 267 if (!get_owner(fs,i) && next && next < fs->clusters+2) { 268 if (get_owner(fs,next) || !fs->fat[next].value || 269 FAT_IS_BAD(fs,fs->fat[next].value)) set_fat(fs,i,-1); 270 else fs->fat[next].prev++; 271 } 272 } 273 do { 274 tag_free(fs,&dummy); 275 changed = 0; 276 for (i = 2; i < fs->clusters+2; i++) 277 if (fs->fat[i].value && !FAT_IS_BAD(fs,fs->fat[i].value) && 278 !get_owner(fs, i)) { 279 if (!fs->fat[fs->fat[i].value].prev--) 280 die("Internal error: prev going below zero"); 281 set_fat(fs,i,-1); 282 changed = 1; 283 printf("Broke cycle at cluster %lu in free chain.\n",i); 284 break; 285 } 286 } 287 while (changed); 288 files = reclaimed = 0; 289 for (i = 2; i < fs->clusters+2; i++) 290 if (get_owner(fs,i) == &dummy && !fs->fat[i].prev) { 291 DIR_ENT de; 292 loff_t offset; 293 files++; 294 offset = alloc_rootdir_entry(fs,&de,"FSCK%04dREC"); 295 de.start = CT_LE_W(i&0xffff); 296 if (fs->fat_bits == 32) 297 de.starthi = CT_LE_W(i>>16); 298 for (walk = i; walk > 0 && walk != -1; 299 walk = next_cluster(fs,walk)) { 300 de.size = CT_LE_L(CF_LE_L(de.size)+fs->cluster_size); 301 reclaimed++; 302 } 303 fs_write(offset,sizeof(DIR_ENT),&de); 304 } 305 if (reclaimed) 306 printf("Reclaimed %d unused cluster%s (%d bytes) in %d chain%s.\n", 307 reclaimed,reclaimed == 1 ? "" : "s",reclaimed*fs->cluster_size,files, 308 files == 1 ? "" : "s"); 309} 310 311 312unsigned long update_free(DOS_FS *fs) 313{ 314 unsigned long i; 315 unsigned long free = 0; 316 int do_set = 0; 317 318 for (i = 2; i < fs->clusters+2; i++) 319 if (!get_owner(fs,i) && !FAT_IS_BAD(fs,fs->fat[i].value)) 320 ++free; 321 322 if (!fs->fsinfo_start) 323 return free; 324 325 if (verbose) 326 printf("Checking free cluster summary.\n"); 327 if (fs->free_clusters >= 0) { 328 if (free != fs->free_clusters) { 329 printf( "Free cluster summary wrong (%ld vs. really %ld)\n", 330 fs->free_clusters,free); 331 if (interactive) 332 printf( "1) Correct\n2) Don't correct\n" ); 333 else printf( " Auto-correcting.\n" ); 334 if (!interactive || get_key("12","?") == '1') 335 do_set = 1; 336 } 337 } 338 else { 339 printf( "Free cluster summary uninitialized (should be %ld)\n", free ); 340 if (interactive) 341 printf( "1) Set it\n2) Leave it uninitialized\n" ); 342 else printf( " Auto-setting.\n" ); 343 if (!interactive || get_key("12","?") == '1') 344 do_set = 1; 345 } 346 347 if (do_set) { 348 fs->free_clusters = free; 349 free = CT_LE_L(free); 350 fs_write(fs->fsinfo_start+offsetof(struct info_sector,free_clusters), 351 sizeof(free),&free); 352 } 353 354 return free; 355} 356 357/* Local Variables: */ 358/* tab-width: 8 */ 359/* End: */ 360