2 * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
3 * Copyright (c) 1995 Martin Husemann
4 * Some structure declaration borrowed from Paul Popelka
5 * (paulp@uts.amdahl.com), see /sys/msdosfs/ for reference.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 * must display the following acknowledgement:
17 * This product includes software developed by Martin Husemann
18 * and Wolfgang Solfrank.
19 * 4. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
24 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
25 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
26 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
28 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
32 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 #include <sys/cdefs.h>
38 __RCSID("$NetBSD: dir.c,v 1.14 1998/08/25 19:18:15 ross Exp $");
39 static const char rcsid[] =
40 "$FreeBSD: src/sbin/fsck_msdosfs/dir.c,v 1.1.2.1 2001/08/01 05:47:55 obrien Exp $";
51 #include <sys/param.h>
56 #define SLOT_EMPTY 0x00 /* slot has never been used */
57 #define SLOT_E5 0x05 /* the real value is 0xe5 */
58 #define SLOT_DELETED 0xe5 /* file in this slot deleted */
60 #define ATTR_NORMAL 0x00 /* normal file */
61 #define ATTR_READONLY 0x01 /* file is readonly */
62 #define ATTR_HIDDEN 0x02 /* file is hidden */
63 #define ATTR_SYSTEM 0x04 /* file is a system file */
64 #define ATTR_VOLUME 0x08 /* entry is a volume label */
65 #define ATTR_DIRECTORY 0x10 /* entry is a directory name */
66 #define ATTR_ARCHIVE 0x20 /* file is new or modified */
68 #define ATTR_WIN95 0x0f /* long name record */
71 * This is the format of the contents of the deTime field in the direntry
73 * We don't use bitfields because we don't know how compilers for
74 * arbitrary machines will lay them out.
76 #define DT_2SECONDS_MASK 0x1F /* seconds divided by 2 */
77 #define DT_2SECONDS_SHIFT 0
78 #define DT_MINUTES_MASK 0x7E0 /* minutes */
79 #define DT_MINUTES_SHIFT 5
80 #define DT_HOURS_MASK 0xF800 /* hours */
81 #define DT_HOURS_SHIFT 11
84 * This is the format of the contents of the deDate field in the direntry
87 #define DD_DAY_MASK 0x1F /* day of month */
88 #define DD_DAY_SHIFT 0
89 #define DD_MONTH_MASK 0x1E0 /* month */
90 #define DD_MONTH_SHIFT 5
91 #define DD_YEAR_MASK 0xFE00 /* year - 1980 */
92 #define DD_YEAR_SHIFT 9
96 static struct dosDirEntry *newDosDirEntry __P((void));
97 static void freeDosDirEntry __P((struct dosDirEntry *));
98 static struct dirTodoNode *newDirTodo __P((void));
99 static void freeDirTodo __P((struct dirTodoNode *));
100 static char *fullpath __P((struct dosDirEntry *));
101 static u_char calcShortSum __P((u_char *));
102 static int delete __P((int, struct bootblock *, struct fatEntry *, cl_t, int,
104 static int removede __P((int, struct bootblock *, struct fatEntry *, u_char *,
105 u_char *, cl_t, cl_t, cl_t, char *, int));
106 static int checksize __P((struct bootblock *, struct fatEntry *, u_char *,
107 struct dosDirEntry *));
108 static int readDosDirSection __P((int, struct bootblock *, struct fatEntry *,
109 struct dosDirEntry *));
112 * Manage free dosDirEntry structures.
114 static struct dosDirEntry *freede;
116 static struct dosDirEntry *
119 struct dosDirEntry *de;
121 if (!(de = freede)) {
122 if (!(de = (struct dosDirEntry *)malloc(sizeof *de)))
131 struct dosDirEntry *de;
138 * The same for dirTodoNode structures.
140 static struct dirTodoNode *freedt;
142 static struct dirTodoNode *
145 struct dirTodoNode *dt;
147 if (!(dt = freedt)) {
148 if (!(dt = (struct dirTodoNode *)malloc(sizeof *dt)))
157 struct dirTodoNode *dt;
164 * The stack of unread directories
166 struct dirTodoNode *pendingDirectories = NULL;
169 * Return the full pathname for a directory entry.
173 struct dosDirEntry *dir;
175 static char namebuf[MAXPATHLEN + 1];
179 cp = namebuf + sizeof namebuf - 1;
182 np = dir->lname[0] ? dir->lname : dir->name;
184 if ((cp -= nl) <= namebuf + 1)
188 } while ((dir = dir->parent) != NULL);
197 * Calculate a checksum over an 8.3 alias name
206 for (i = 0; i < 11; i++) {
207 sum = (sum << 7)|(sum >> 1); /* rotate right */
215 * Global variables temporarily used during a directory scan
217 static char longName[DOSLONGNAMELEN] = "";
218 static u_char *buffer = NULL;
219 static u_char *delbuf = NULL;
221 struct dosDirEntry *rootDir;
222 static struct dosDirEntry *lostDir;
225 * Init internal state for a new directory scan.
228 resetDosDirSection(boot, fat)
229 struct bootblock *boot;
230 struct fatEntry *fat;
236 b1 = boot->RootDirEnts * 32;
237 b2 = boot->SecPerClust * boot->BytesPerSec;
239 if (!(buffer = malloc(b1 > b2 ? b1 : b2))
240 || !(delbuf = malloc(b2))
241 || !(rootDir = newDosDirEntry())) {
242 perror("No space for directory");
245 memset(rootDir, 0, sizeof *rootDir);
246 if (boot->flags & FAT32) {
247 if (boot->RootCl < CLUST_FIRST || boot->RootCl >= boot->NumClusters) {
248 pfatal("Root directory starts with cluster out of range(%u)",
252 cl = fat[boot->RootCl].next;
254 || (cl >= CLUST_RSRVD && cl< CLUST_EOFS)
255 || fat[boot->RootCl].head != boot->RootCl) {
256 if (cl == CLUST_FREE)
257 pwarn("Root directory starts with free cluster\n");
258 else if (cl >= CLUST_RSRVD)
259 pwarn("Root directory starts with cluster marked %s\n",
262 pfatal("Root directory doesn't start a cluster chain");
266 fat[boot->RootCl].next = CLUST_FREE;
272 fat[boot->RootCl].flags |= FAT_USED;
273 rootDir->head = boot->RootCl;
280 * Cleanup after a directory scan
283 finishDosDirSection()
285 struct dirTodoNode *p, *np;
286 struct dosDirEntry *d, *nd;
288 for (p = pendingDirectories; p; p = np) {
292 pendingDirectories = 0;
293 for (d = rootDir; d; d = nd) {
294 if ((nd = d->child) != NULL) {
302 rootDir = lostDir = NULL;
310 * Delete directory entries between startcl, startoff and endcl, endoff.
313 delete(f, boot, fat, startcl, startoff, endcl, endoff, notlast)
315 struct bootblock *boot;
316 struct fatEntry *fat;
325 int clsz = boot->SecPerClust * boot->BytesPerSec;
327 s = delbuf + startoff;
329 while (startcl >= CLUST_FIRST && startcl < boot->NumClusters) {
330 if (startcl == endcl) {
335 off = startcl * boot->SecPerClust + boot->ClusterOffset;
336 off *= boot->BytesPerSec;
337 if (lseek(f, off, SEEK_SET) != off
338 || read(f, delbuf, clsz) != clsz) {
339 perror("Unable to read directory");
346 if (lseek(f, off, SEEK_SET) != off
347 || write(f, delbuf, clsz) != clsz) {
348 perror("Unable to write directory");
351 if (startcl == endcl)
353 startcl = fat[startcl].next;
360 removede(f, boot, fat, start, end, startcl, endcl, curcl, path, type)
362 struct bootblock *boot;
363 struct fatEntry *fat;
374 pwarn("Invalid long filename entry for %s\n", path);
377 pwarn("Invalid long filename entry at end of directory %s\n", path);
380 pwarn("Invalid long filename entry for volume label\n");
383 if (ask(0, "Remove")) {
384 if (startcl != curcl) {
385 if (delete(f, boot, fat,
386 startcl, start - buffer,
388 endcl == curcl) == FSFATAL)
393 for (; start < end; start += 32)
394 *start = SLOT_DELETED;
401 * Check an in-memory file entry
404 checksize(boot, fat, p, dir)
405 struct bootblock *boot;
406 struct fatEntry *fat;
408 struct dosDirEntry *dir;
411 * Check size on ordinary files
413 int32_t physicalSize;
415 if (dir->head == CLUST_FREE)
418 if (dir->head < CLUST_FIRST || dir->head >= boot->NumClusters)
420 physicalSize = fat[dir->head].length * boot->ClusterSize;
422 if (physicalSize < dir->size) {
423 pwarn("size of %s is %u, should at most be %u\n",
424 fullpath(dir), dir->size, physicalSize);
425 if (ask(1, "Truncate")) {
426 dir->size = physicalSize;
427 p[28] = (u_char)physicalSize;
428 p[29] = (u_char)(physicalSize >> 8);
429 p[30] = (u_char)(physicalSize >> 16);
430 p[31] = (u_char)(physicalSize >> 24);
434 } else if (physicalSize - dir->size >= boot->ClusterSize) {
435 pwarn("%s has too many clusters allocated\n",
437 if (ask(1, "Drop superfluous clusters")) {
441 for (cl = dir->head; (sz += boot->ClusterSize) < dir->size;)
443 clearchain(boot, fat, fat[cl].next);
444 fat[cl].next = CLUST_EOF;
453 * Read a directory and
454 * - resolve long name records
455 * - enter file and directory records into the parent's list
456 * - push directories onto the todo-stack
459 readDosDirSection(f, boot, fat, dir)
461 struct bootblock *boot;
462 struct fatEntry *fat;
463 struct dosDirEntry *dir;
465 struct dosDirEntry dirent, *d;
466 u_char *p, *vallfn, *invlfn, *empty;
469 cl_t cl, valcl = ~0, invcl = ~0, empcl = ~0;
474 #define THISMOD 0x8000 /* Only used within this routine */
477 if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
479 * Already handled somewhere else.
484 vallfn = invlfn = empty = NULL;
486 if (!(boot->flags & FAT32) && !dir->parent) {
487 last = boot->RootDirEnts * 32;
488 off = boot->ResSectors + boot->FATs * boot->FATsecs;
490 last = boot->SecPerClust * boot->BytesPerSec;
491 off = cl * boot->SecPerClust + boot->ClusterOffset;
494 off *= boot->BytesPerSec;
495 if (lseek(f, off, SEEK_SET) != off
496 || read(f, buffer, last) != last) {
497 perror("Unable to read directory");
502 * Check `.' and `..' entries here? XXX
504 for (p = buffer, i = 0; i < last; i++, p += 32) {
505 if (dir->fsckflags & DIREMPWARN) {
510 if (*p == SLOT_EMPTY || *p == SLOT_DELETED) {
511 if (*p == SLOT_EMPTY) {
512 dir->fsckflags |= DIREMPTY;
519 if (dir->fsckflags & DIREMPTY) {
520 if (!(dir->fsckflags & DIREMPWARN)) {
521 pwarn("%s has entries after end of directory\n",
523 if (ask(1, "Extend")) {
526 dir->fsckflags &= ~DIREMPTY;
527 if (delete(f, boot, fat,
528 empcl, empty - buffer,
529 cl, p - buffer, 1) == FSFATAL)
531 q = empcl == cl ? empty : buffer;
532 for (; q < p; q += 32)
534 mod |= THISMOD|FSDIRMOD;
535 } else if (ask(0, "Truncate"))
536 dir->fsckflags |= DIREMPWARN;
538 if (dir->fsckflags & DIREMPWARN) {
540 mod |= THISMOD|FSDIRMOD;
542 } else if (dir->fsckflags & DIREMPTY)
547 if (p[11] == ATTR_WIN95) {
549 if (shortSum != -1) {
555 memset(longName, 0, sizeof longName);
559 } else if (shortSum != p[13]
560 || lidx != (*p & LRNOMASK)) {
571 lidx = *p & LRNOMASK;
572 t = longName + --lidx * 13;
573 for (k = 1; k < 11 && t < longName + sizeof(longName); k += 2) {
574 if (!p[k] && !p[k + 1])
578 * Warn about those unusable chars in msdosfs here? XXX
584 for (k = 14; k < 26 && t < longName + sizeof(longName); k += 2) {
585 if (!p[k] && !p[k + 1])
592 for (k = 28; k < 32 && t < longName + sizeof(longName); k += 2) {
593 if (!p[k] && !p[k + 1])
599 if (t >= longName + sizeof(longName)) {
600 pwarn("long filename too long\n");
607 if (p[26] | (p[27] << 8)) {
608 pwarn("long filename record cluster start != 0\n");
615 continue; /* long records don't carry further
620 * This is a standard msdosfs directory entry.
622 memset(&dirent, 0, sizeof dirent);
625 * it's a short name record, but we need to know
626 * more, so get the flags first.
628 dirent.flags = p[11];
631 * Translate from 850 to ISO here XXX
633 for (j = 0; j < 8; j++)
634 dirent.name[j] = p[j];
635 dirent.name[8] = '\0';
636 for (k = 7; k >= 0 && dirent.name[k] == ' '; k--)
637 dirent.name[k] = '\0';
638 if (dirent.name[k] != '\0')
640 if (dirent.name[0] == SLOT_E5)
641 dirent.name[0] = 0xe5;
643 if (dirent.flags & ATTR_VOLUME) {
644 if (vallfn || invlfn) {
645 mod |= removede(f, boot, fat,
646 invlfn ? invlfn : vallfn, p,
647 invlfn ? invcl : valcl, -1, 0,
656 dirent.name[k++] = '.';
657 for (j = 0; j < 3; j++)
658 dirent.name[k++] = p[j+8];
659 dirent.name[k] = '\0';
660 for (k--; k >= 0 && dirent.name[k] == ' '; k--)
661 dirent.name[k] = '\0';
663 if (vallfn && shortSum != calcShortSum(p)) {
670 dirent.head = p[26] | (p[27] << 8);
671 if (boot->ClustMask == CLUST32_MASK)
672 dirent.head |= (p[20] << 16) | (p[21] << 24);
673 dirent.size = p[28] | (p[29] << 8) | (p[30] << 16) | (p[31] << 24);
675 strcpy(dirent.lname, longName);
681 dirent.next = dir->child;
684 mod |= k = removede(f, boot, fat,
685 invlfn, vallfn ? vallfn : p,
686 invcl, vallfn ? valcl : cl, cl,
687 fullpath(&dirent), 0);
691 ? (valcl == cl && vallfn != buffer)
697 vallfn = NULL; /* not used any longer */
700 if (dirent.size == 0 && !(dirent.flags & ATTR_DIRECTORY)) {
701 if (dirent.head != 0) {
702 pwarn("%s has clusters, but size 0\n",
704 if (ask(1, "Drop allocated clusters")) {
706 if (boot->ClustMask == CLUST32_MASK)
708 clearchain(boot, fat, dirent.head);
710 mod |= THISMOD|FSDIRMOD|FSFATMOD;
714 } else if (dirent.head == 0
715 && !strcmp(dirent.name, "..")
716 && dir->parent /* XXX */
717 && !dir->parent->parent) {
719 * Do nothing, the parent is the root
721 } else if (dirent.head < CLUST_FIRST
722 || dirent.head >= boot->NumClusters
723 || fat[dirent.head].next == CLUST_FREE
724 || (fat[dirent.head].next >= CLUST_RSRVD
725 && fat[dirent.head].next < CLUST_EOFS)
726 || fat[dirent.head].head != dirent.head) {
727 if (dirent.head == 0)
728 pwarn("%s has no clusters\n",
730 else if (dirent.head < CLUST_FIRST
731 || dirent.head >= boot->NumClusters)
732 pwarn("%s starts with cluster out of range(%u)\n",
735 else if (fat[dirent.head].next == CLUST_FREE)
736 pwarn("%s starts with free cluster\n",
738 else if (fat[dirent.head].next >= CLUST_RSRVD)
739 pwarn("%s starts with cluster marked %s\n",
741 rsrvdcltype(fat[dirent.head].next));
743 pwarn("%s doesn't start a cluster chain\n",
745 if (dirent.flags & ATTR_DIRECTORY) {
746 if (ask(0, "Remove")) {
748 mod |= THISMOD|FSDIRMOD;
753 if (ask(1, "Truncate")) {
754 p[28] = p[29] = p[30] = p[31] = 0;
756 if (boot->ClustMask == CLUST32_MASK)
759 mod |= THISMOD|FSDIRMOD;
765 if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters)
766 fat[dirent.head].flags |= FAT_USED;
768 if (dirent.flags & ATTR_DIRECTORY) {
770 * gather more info for directories
772 struct dirTodoNode *n;
775 pwarn("Directory %s has size != 0\n",
777 if (ask(1, "Correct")) {
778 p[28] = p[29] = p[30] = p[31] = 0;
780 mod |= THISMOD|FSDIRMOD;
785 * handle `.' and `..' specially
787 if (strcmp(dirent.name, ".") == 0) {
788 if (dirent.head != dir->head) {
789 pwarn("`.' entry in %s has incorrect start cluster\n",
791 if (ask(1, "Correct")) {
792 dirent.head = dir->head;
793 p[26] = (u_char)dirent.head;
794 p[27] = (u_char)(dirent.head >> 8);
795 if (boot->ClustMask == CLUST32_MASK) {
796 p[20] = (u_char)(dirent.head >> 16);
797 p[21] = (u_char)(dirent.head >> 24);
799 mod |= THISMOD|FSDIRMOD;
805 if (strcmp(dirent.name, "..") == 0) {
806 if (dir->parent) { /* XXX */
807 if (!dir->parent->parent) {
809 pwarn("`..' entry in %s has non-zero start cluster\n",
811 if (ask(1, "Correct")) {
814 if (boot->ClustMask == CLUST32_MASK)
816 mod |= THISMOD|FSDIRMOD;
820 } else if (dirent.head != dir->parent->head) {
821 pwarn("`..' entry in %s has incorrect start cluster\n",
823 if (ask(1, "Correct")) {
824 dirent.head = dir->parent->head;
825 p[26] = (u_char)dirent.head;
826 p[27] = (u_char)(dirent.head >> 8);
827 if (boot->ClustMask == CLUST32_MASK) {
828 p[20] = (u_char)(dirent.head >> 16);
829 p[21] = (u_char)(dirent.head >> 24);
831 mod |= THISMOD|FSDIRMOD;
839 /* create directory tree node */
840 if (!(d = newDosDirEntry())) {
841 perror("No space for directory");
844 memcpy(d, &dirent, sizeof(struct dosDirEntry));
845 /* link it into the tree */
848 /* Enter this directory into the todo list */
849 if (!(n = newDirTodo())) {
850 perror("No space for todo list");
853 n->next = pendingDirectories;
855 pendingDirectories = n;
857 mod |= k = checksize(boot, fat, p, &dirent);
865 if (lseek(f, off, SEEK_SET) != off
866 || write(f, buffer, last) != last) {
867 perror("Unable to write directory");
872 } while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
873 if (invlfn || vallfn)
874 mod |= removede(f, boot, fat,
875 invlfn ? invlfn : vallfn, p,
876 invlfn ? invcl : valcl, -1, 0,
878 return mod & ~THISMOD;
882 handleDirTree(dosfs, boot, fat)
884 struct bootblock *boot;
885 struct fatEntry *fat;
889 mod = readDosDirSection(dosfs, boot, fat, rootDir);
894 * process the directory todo list
896 while (pendingDirectories) {
897 struct dosDirEntry *dir = pendingDirectories->dir;
898 struct dirTodoNode *n = pendingDirectories->next;
901 * remove TODO entry now, the list might change during
904 freeDirTodo(pendingDirectories);
905 pendingDirectories = n;
908 * handle subdirectory
910 mod |= readDosDirSection(dosfs, boot, fat, dir);
919 * Try to reconnect a FAT chain into dir
921 static u_char *lfbuf;
926 reconnect(dosfs, boot, fat, head)
928 struct bootblock *boot;
929 struct fatEntry *fat;
932 struct dosDirEntry d;
935 if (!ask(1, "Reconnect"))
939 for (lostDir = rootDir->child; lostDir; lostDir = lostDir->next) {
940 if (!strcmp(lostDir->name, LOSTDIR))
943 if (!lostDir) { /* Create LOSTDIR? XXX */
944 pwarn("No %s directory\n", LOSTDIR);
949 lfbuf = malloc(boot->ClusterSize);
951 perror("No space for buffer");
959 for (; p < lfbuf + boot->ClusterSize; p += 32)
961 || *p == SLOT_DELETED)
963 if (p && p < lfbuf + boot->ClusterSize)
965 lfcl = p ? fat[lfcl].next : lostDir->head;
966 if (lfcl < CLUST_FIRST || lfcl >= boot->NumClusters) {
967 /* Extend LOSTDIR? XXX */
968 pwarn("No space in %s\n", LOSTDIR);
971 lfoff = lfcl * boot->ClusterSize
972 + boot->ClusterOffset * boot->BytesPerSec;
973 if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
974 || read(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
975 perror("could not read LOST.DIR");
982 /* Ensure uniqueness of entry here! XXX */
983 memset(&d, 0, sizeof d);
984 (void)snprintf(d.name, sizeof(d.name), "%u", head);
987 d.size = fat[head].length * boot->ClusterSize;
991 memcpy(p, d.name, strlen(d.name));
992 p[26] = (u_char)d.head;
993 p[27] = (u_char)(d.head >> 8);
994 if (boot->ClustMask == CLUST32_MASK) {
995 p[20] = (u_char)(d.head >> 16);
996 p[21] = (u_char)(d.head >> 24);
998 p[28] = (u_char)d.size;
999 p[29] = (u_char)(d.size >> 8);
1000 p[30] = (u_char)(d.size >> 16);
1001 p[31] = (u_char)(d.size >> 24);
1002 fat[head].flags |= FAT_USED;
1003 if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
1004 || write(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
1005 perror("could not write LOST.DIR");