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.
34 * $NetBSD: dir.c,v 1.14 1998/08/25 19:18:15 ross Exp $
35 * $FreeBSD: src/sbin/fsck_msdosfs/dir.c,v 1.1.2.1 2001/08/01 05:47:55 obrien Exp $
45 #include <sys/param.h>
50 #define SLOT_EMPTY 0x00 /* slot has never been used */
51 #define SLOT_E5 0x05 /* the real value is 0xe5 */
52 #define SLOT_DELETED 0xe5 /* file in this slot deleted */
54 #define ATTR_NORMAL 0x00 /* normal file */
55 #define ATTR_READONLY 0x01 /* file is readonly */
56 #define ATTR_HIDDEN 0x02 /* file is hidden */
57 #define ATTR_SYSTEM 0x04 /* file is a system file */
58 #define ATTR_VOLUME 0x08 /* entry is a volume label */
59 #define ATTR_DIRECTORY 0x10 /* entry is a directory name */
60 #define ATTR_ARCHIVE 0x20 /* file is new or modified */
62 #define ATTR_WIN95 0x0f /* long name record */
65 * This is the format of the contents of the deTime field in the direntry
67 * We don't use bitfields because we don't know how compilers for
68 * arbitrary machines will lay them out.
70 #define DT_2SECONDS_MASK 0x1F /* seconds divided by 2 */
71 #define DT_2SECONDS_SHIFT 0
72 #define DT_MINUTES_MASK 0x7E0 /* minutes */
73 #define DT_MINUTES_SHIFT 5
74 #define DT_HOURS_MASK 0xF800 /* hours */
75 #define DT_HOURS_SHIFT 11
78 * This is the format of the contents of the deDate field in the direntry
81 #define DD_DAY_MASK 0x1F /* day of month */
82 #define DD_DAY_SHIFT 0
83 #define DD_MONTH_MASK 0x1E0 /* month */
84 #define DD_MONTH_SHIFT 5
85 #define DD_YEAR_MASK 0xFE00 /* year - 1980 */
86 #define DD_YEAR_SHIFT 9
90 static struct dosDirEntry *newDosDirEntry(void);
91 static void freeDosDirEntry(struct dosDirEntry *);
92 static struct dirTodoNode *newDirTodo(void);
93 static void freeDirTodo(struct dirTodoNode *);
94 static char *fullpath(struct dosDirEntry *);
95 static u_char calcShortSum(u_char *);
96 static int delete(int, struct bootblock *, struct fatEntry *, cl_t, int,
98 static int removede(int, struct bootblock *, struct fatEntry *, u_char *,
99 u_char *, cl_t, cl_t, cl_t, char *, int);
100 static int checksize(struct bootblock *, struct fatEntry *, u_char *,
101 struct dosDirEntry *);
102 static int readDosDirSection(int, struct bootblock *, struct fatEntry *,
103 struct dosDirEntry *);
106 * Manage free dosDirEntry structures.
108 static struct dosDirEntry *freede;
110 static struct dosDirEntry *
113 struct dosDirEntry *de;
115 if (!(de = freede)) {
116 if (!(de = (struct dosDirEntry *)malloc(sizeof *de)))
124 freeDosDirEntry(struct dosDirEntry *de)
131 * The same for dirTodoNode structures.
133 static struct dirTodoNode *freedt;
135 static struct dirTodoNode *
138 struct dirTodoNode *dt;
140 if (!(dt = freedt)) {
141 if (!(dt = (struct dirTodoNode *)malloc(sizeof *dt)))
149 freeDirTodo(struct dirTodoNode *dt)
156 * The stack of unread directories
158 struct dirTodoNode *pendingDirectories = NULL;
161 * Return the full pathname for a directory entry.
164 fullpath(struct dosDirEntry *dir)
166 static char namebuf[MAXPATHLEN + 1];
170 cp = namebuf + sizeof namebuf - 1;
173 np = dir->lname[0] ? dir->lname : dir->name;
175 if ((cp -= nl) <= namebuf + 1)
179 } while ((dir = dir->parent) != NULL);
188 * Calculate a checksum over an 8.3 alias name
191 calcShortSum(u_char *p)
196 for (i = 0; i < 11; i++) {
197 sum = (sum << 7)|(sum >> 1); /* rotate right */
205 * Global variables temporarily used during a directory scan
207 static char longName[DOSLONGNAMELEN] = "";
208 static u_char *buffer = NULL;
209 static u_char *delbuf = NULL;
211 struct dosDirEntry *rootDir;
212 static struct dosDirEntry *lostDir;
215 * Init internal state for a new directory scan.
218 resetDosDirSection(struct bootblock *boot, struct fatEntry *fat)
224 b1 = boot->RootDirEnts * 32;
225 b2 = boot->SecPerClust * boot->BytesPerSec;
227 if (!(buffer = malloc(b1 > b2 ? b1 : b2))
228 || !(delbuf = malloc(b2))
229 || !(rootDir = newDosDirEntry())) {
230 perror("No space for directory");
233 memset(rootDir, 0, sizeof *rootDir);
234 if (boot->flags & FAT32) {
235 if (boot->RootCl < CLUST_FIRST || boot->RootCl >= boot->NumClusters) {
236 pfatal("Root directory starts with cluster out of range(%u)",
240 cl = fat[boot->RootCl].next;
242 || (cl >= CLUST_RSRVD && cl< CLUST_EOFS)
243 || fat[boot->RootCl].head != boot->RootCl) {
244 if (cl == CLUST_FREE)
245 pwarn("Root directory starts with free cluster\n");
246 else if (cl >= CLUST_RSRVD)
247 pwarn("Root directory starts with cluster marked %s\n",
250 pfatal("Root directory doesn't start a cluster chain");
254 fat[boot->RootCl].next = CLUST_FREE;
260 fat[boot->RootCl].flags |= FAT_USED;
261 rootDir->head = boot->RootCl;
268 * Cleanup after a directory scan
271 finishDosDirSection(void)
273 struct dirTodoNode *p, *np;
274 struct dosDirEntry *d, *nd;
276 for (p = pendingDirectories; p; p = np) {
280 pendingDirectories = NULL;
281 for (d = rootDir; d; d = nd) {
282 if ((nd = d->child) != NULL) {
290 rootDir = lostDir = NULL;
298 * Delete directory entries between startcl, startoff and endcl, endoff.
301 delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
302 int startoff, cl_t endcl, int endoff, int notlast)
306 int clsz = boot->SecPerClust * boot->BytesPerSec;
308 s = delbuf + startoff;
310 while (startcl >= CLUST_FIRST && startcl < boot->NumClusters) {
311 if (startcl == endcl) {
316 off = startcl * boot->SecPerClust + boot->ClusterOffset;
317 off *= boot->BytesPerSec;
318 if (lseek(f, off, SEEK_SET) != off
319 || read(f, delbuf, clsz) != clsz) {
320 perror("Unable to read directory");
327 if (lseek(f, off, SEEK_SET) != off
328 || write(f, delbuf, clsz) != clsz) {
329 perror("Unable to write directory");
332 if (startcl == endcl)
334 startcl = fat[startcl].next;
341 removede(int f, struct bootblock *boot, struct fatEntry *fat, u_char *start,
342 u_char *end, cl_t startcl, cl_t endcl, cl_t curcl, char *path,
347 pwarn("Invalid long filename entry for %s\n", path);
350 pwarn("Invalid long filename entry at end of directory %s\n", path);
353 pwarn("Invalid long filename entry for volume label\n");
356 if (ask(0, "Remove")) {
357 if (startcl != curcl) {
358 if (delete(f, boot, fat,
359 startcl, start - buffer,
361 endcl == curcl) == FSFATAL)
366 for (; start < end; start += 32)
367 *start = SLOT_DELETED;
374 * Check an in-memory file entry
377 checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
378 struct dosDirEntry *dir)
381 * Check size on ordinary files
383 int32_t physicalSize;
385 if (dir->head == CLUST_FREE)
388 if (dir->head < CLUST_FIRST || dir->head >= boot->NumClusters)
390 physicalSize = fat[dir->head].length * boot->ClusterSize;
392 if (physicalSize < dir->size) {
393 pwarn("size of %s is %u, should at most be %u\n",
394 fullpath(dir), dir->size, physicalSize);
395 if (ask(1, "Truncate")) {
396 dir->size = physicalSize;
397 p[28] = (u_char)physicalSize;
398 p[29] = (u_char)(physicalSize >> 8);
399 p[30] = (u_char)(physicalSize >> 16);
400 p[31] = (u_char)(physicalSize >> 24);
404 } else if (physicalSize - dir->size >= boot->ClusterSize) {
405 pwarn("%s has too many clusters allocated\n",
407 if (ask(1, "Drop superfluous clusters")) {
411 for (cl = dir->head; (sz += boot->ClusterSize) < dir->size;)
413 clearchain(boot, fat, fat[cl].next);
414 fat[cl].next = CLUST_EOF;
423 * Read a directory and
424 * - resolve long name records
425 * - enter file and directory records into the parent's list
426 * - push directories onto the todo-stack
429 readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
430 struct dosDirEntry *dir)
432 struct dosDirEntry dirent, *d;
433 u_char *p, *vallfn, *invlfn, *empty;
436 cl_t cl, valcl = ~0, invcl = ~0, empcl = ~0;
441 #define THISMOD 0x8000 /* Only used within this routine */
444 if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
446 * Already handled somewhere else.
451 vallfn = invlfn = empty = NULL;
453 if (!(boot->flags & FAT32) && !dir->parent) {
454 last = boot->RootDirEnts * 32;
455 off = boot->ResSectors + boot->FATs * boot->FATsecs;
457 last = boot->SecPerClust * boot->BytesPerSec;
458 off = cl * boot->SecPerClust + boot->ClusterOffset;
461 off *= boot->BytesPerSec;
462 if (lseek(f, off, SEEK_SET) != off
463 || read(f, buffer, last) != last) {
464 perror("Unable to read directory");
469 * Check `.' and `..' entries here? XXX
471 for (p = buffer, i = 0; i < last; i++, p += 32) {
472 if (dir->fsckflags & DIREMPWARN) {
477 if (*p == SLOT_EMPTY || *p == SLOT_DELETED) {
478 if (*p == SLOT_EMPTY) {
479 dir->fsckflags |= DIREMPTY;
486 if (dir->fsckflags & DIREMPTY) {
487 if (!(dir->fsckflags & DIREMPWARN)) {
488 pwarn("%s has entries after end of directory\n",
490 if (ask(1, "Extend")) {
493 dir->fsckflags &= ~DIREMPTY;
494 if (delete(f, boot, fat,
495 empcl, empty - buffer,
496 cl, p - buffer, 1) == FSFATAL)
498 q = empcl == cl ? empty : buffer;
499 for (; q < p; q += 32)
501 mod |= THISMOD|FSDIRMOD;
502 } else if (ask(0, "Truncate"))
503 dir->fsckflags |= DIREMPWARN;
505 if (dir->fsckflags & DIREMPWARN) {
507 mod |= THISMOD|FSDIRMOD;
509 } else if (dir->fsckflags & DIREMPTY)
514 if (p[11] == ATTR_WIN95) {
516 if (shortSum != -1) {
522 memset(longName, 0, sizeof longName);
526 } else if (shortSum != p[13]
527 || lidx != (*p & LRNOMASK)) {
538 lidx = *p & LRNOMASK;
539 t = longName + --lidx * 13;
540 for (k = 1; k < 11 && t < longName + sizeof(longName); k += 2) {
541 if (!p[k] && !p[k + 1])
545 * Warn about those unusable chars in msdosfs here? XXX
551 for (k = 14; k < 26 && t < longName + sizeof(longName); k += 2) {
552 if (!p[k] && !p[k + 1])
559 for (k = 28; k < 32 && t < longName + sizeof(longName); k += 2) {
560 if (!p[k] && !p[k + 1])
566 if (t >= longName + sizeof(longName)) {
567 pwarn("long filename too long\n");
574 if (p[26] | (p[27] << 8)) {
575 pwarn("long filename record cluster start != 0\n");
582 continue; /* long records don't carry further
587 * This is a standard msdosfs directory entry.
589 memset(&dirent, 0, sizeof dirent);
592 * it's a short name record, but we need to know
593 * more, so get the flags first.
595 dirent.flags = p[11];
598 * Translate from 850 to ISO here XXX
600 for (j = 0; j < 8; j++)
601 dirent.name[j] = p[j];
602 dirent.name[8] = '\0';
603 for (k = 7; k >= 0 && dirent.name[k] == ' '; k--)
604 dirent.name[k] = '\0';
605 if (dirent.name[k] != '\0')
607 if (dirent.name[0] == SLOT_E5)
608 dirent.name[0] = 0xe5;
610 if (dirent.flags & ATTR_VOLUME) {
611 if (vallfn || invlfn) {
612 mod |= removede(f, boot, fat,
613 invlfn ? invlfn : vallfn, p,
614 invlfn ? invcl : valcl, -1, 0,
623 dirent.name[k++] = '.';
624 for (j = 0; j < 3; j++)
625 dirent.name[k++] = p[j+8];
626 dirent.name[k] = '\0';
627 for (k--; k >= 0 && dirent.name[k] == ' '; k--)
628 dirent.name[k] = '\0';
630 if (vallfn && shortSum != calcShortSum(p)) {
637 dirent.head = p[26] | (p[27] << 8);
638 if (boot->ClustMask == CLUST32_MASK)
639 dirent.head |= (p[20] << 16) | (p[21] << 24);
640 dirent.size = p[28] | (p[29] << 8) | (p[30] << 16) | (p[31] << 24);
642 strcpy(dirent.lname, longName);
648 dirent.next = dir->child;
651 mod |= k = removede(f, boot, fat,
652 invlfn, vallfn ? vallfn : p,
653 invcl, vallfn ? valcl : cl, cl,
654 fullpath(&dirent), 0);
658 ? (valcl == cl && vallfn != buffer)
664 vallfn = NULL; /* not used any longer */
667 if (dirent.size == 0 && !(dirent.flags & ATTR_DIRECTORY)) {
668 if (dirent.head != 0) {
669 pwarn("%s has clusters, but size 0\n",
671 if (ask(1, "Drop allocated clusters")) {
673 if (boot->ClustMask == CLUST32_MASK)
675 clearchain(boot, fat, dirent.head);
677 mod |= THISMOD|FSDIRMOD|FSFATMOD;
681 } else if (dirent.head == 0
682 && !strcmp(dirent.name, "..")
683 && dir->parent /* XXX */
684 && !dir->parent->parent) {
686 * Do nothing, the parent is the root
688 } else if (dirent.head < CLUST_FIRST
689 || dirent.head >= boot->NumClusters
690 || fat[dirent.head].next == CLUST_FREE
691 || (fat[dirent.head].next >= CLUST_RSRVD
692 && fat[dirent.head].next < CLUST_EOFS)
693 || fat[dirent.head].head != dirent.head) {
694 if (dirent.head == 0)
695 pwarn("%s has no clusters\n",
697 else if (dirent.head < CLUST_FIRST
698 || dirent.head >= boot->NumClusters)
699 pwarn("%s starts with cluster out of range(%u)\n",
702 else if (fat[dirent.head].next == CLUST_FREE)
703 pwarn("%s starts with free cluster\n",
705 else if (fat[dirent.head].next >= CLUST_RSRVD)
706 pwarn("%s starts with cluster marked %s\n",
708 rsrvdcltype(fat[dirent.head].next));
710 pwarn("%s doesn't start a cluster chain\n",
712 if (dirent.flags & ATTR_DIRECTORY) {
713 if (ask(0, "Remove")) {
715 mod |= THISMOD|FSDIRMOD;
720 if (ask(1, "Truncate")) {
721 p[28] = p[29] = p[30] = p[31] = 0;
723 if (boot->ClustMask == CLUST32_MASK)
726 mod |= THISMOD|FSDIRMOD;
732 if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters)
733 fat[dirent.head].flags |= FAT_USED;
735 if (dirent.flags & ATTR_DIRECTORY) {
737 * gather more info for directories
739 struct dirTodoNode *n;
742 pwarn("Directory %s has size != 0\n",
744 if (ask(1, "Correct")) {
745 p[28] = p[29] = p[30] = p[31] = 0;
747 mod |= THISMOD|FSDIRMOD;
752 * handle `.' and `..' specially
754 if (strcmp(dirent.name, ".") == 0) {
755 if (dirent.head != dir->head) {
756 pwarn("`.' entry in %s has incorrect start cluster\n",
758 if (ask(1, "Correct")) {
759 dirent.head = dir->head;
760 p[26] = (u_char)dirent.head;
761 p[27] = (u_char)(dirent.head >> 8);
762 if (boot->ClustMask == CLUST32_MASK) {
763 p[20] = (u_char)(dirent.head >> 16);
764 p[21] = (u_char)(dirent.head >> 24);
766 mod |= THISMOD|FSDIRMOD;
772 if (strcmp(dirent.name, "..") == 0) {
773 if (dir->parent) { /* XXX */
774 if (!dir->parent->parent) {
776 pwarn("`..' entry in %s has non-zero start cluster\n",
778 if (ask(1, "Correct")) {
781 if (boot->ClustMask == CLUST32_MASK)
783 mod |= THISMOD|FSDIRMOD;
787 } else if (dirent.head != dir->parent->head) {
788 pwarn("`..' entry in %s has incorrect start cluster\n",
790 if (ask(1, "Correct")) {
791 dirent.head = dir->parent->head;
792 p[26] = (u_char)dirent.head;
793 p[27] = (u_char)(dirent.head >> 8);
794 if (boot->ClustMask == CLUST32_MASK) {
795 p[20] = (u_char)(dirent.head >> 16);
796 p[21] = (u_char)(dirent.head >> 24);
798 mod |= THISMOD|FSDIRMOD;
806 /* create directory tree node */
807 if (!(d = newDosDirEntry())) {
808 perror("No space for directory");
811 memcpy(d, &dirent, sizeof(struct dosDirEntry));
812 /* link it into the tree */
815 /* Enter this directory into the todo list */
816 if (!(n = newDirTodo())) {
817 perror("No space for todo list");
820 n->next = pendingDirectories;
822 pendingDirectories = n;
824 mod |= k = checksize(boot, fat, p, &dirent);
832 if (lseek(f, off, SEEK_SET) != off
833 || write(f, buffer, last) != last) {
834 perror("Unable to write directory");
839 } while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
840 if (invlfn || vallfn)
841 mod |= removede(f, boot, fat,
842 invlfn ? invlfn : vallfn, p,
843 invlfn ? invcl : valcl, -1, 0,
845 return mod & ~THISMOD;
849 handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
853 mod = readDosDirSection(dosfs, boot, fat, rootDir);
858 * process the directory todo list
860 while (pendingDirectories) {
861 struct dosDirEntry *dir = pendingDirectories->dir;
862 struct dirTodoNode *n = pendingDirectories->next;
865 * remove TODO entry now, the list might change during
868 freeDirTodo(pendingDirectories);
869 pendingDirectories = n;
872 * handle subdirectory
874 mod |= readDosDirSection(dosfs, boot, fat, dir);
883 * Try to reconnect a FAT chain into dir
885 static u_char *lfbuf;
890 reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
892 struct dosDirEntry d;
895 if (!ask(1, "Reconnect"))
899 for (lostDir = rootDir->child; lostDir; lostDir = lostDir->next) {
900 if (!strcmp(lostDir->name, LOSTDIR))
903 if (!lostDir) { /* Create LOSTDIR? XXX */
904 pwarn("No %s directory\n", LOSTDIR);
909 lfbuf = malloc(boot->ClusterSize);
911 perror("No space for buffer");
919 for (; p < lfbuf + boot->ClusterSize; p += 32)
921 || *p == SLOT_DELETED)
923 if (p && p < lfbuf + boot->ClusterSize)
925 lfcl = p ? fat[lfcl].next : lostDir->head;
926 if (lfcl < CLUST_FIRST || lfcl >= boot->NumClusters) {
927 /* Extend LOSTDIR? XXX */
928 pwarn("No space in %s\n", LOSTDIR);
931 lfoff = lfcl * boot->ClusterSize
932 + boot->ClusterOffset * boot->BytesPerSec;
933 if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
934 || read(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
935 perror("could not read LOST.DIR");
942 /* Ensure uniqueness of entry here! XXX */
943 memset(&d, 0, sizeof d);
944 snprintf(d.name, sizeof(d.name), "%u", head);
947 d.size = fat[head].length * boot->ClusterSize;
951 memcpy(p, d.name, strlen(d.name));
952 p[26] = (u_char)d.head;
953 p[27] = (u_char)(d.head >> 8);
954 if (boot->ClustMask == CLUST32_MASK) {
955 p[20] = (u_char)(d.head >> 16);
956 p[21] = (u_char)(d.head >> 24);
958 p[28] = (u_char)d.size;
959 p[29] = (u_char)(d.size >> 8);
960 p[30] = (u_char)(d.size >> 16);
961 p[31] = (u_char)(d.size >> 24);
962 fat[head].flags |= FAT_USED;
963 if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
964 || write(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
965 perror("could not write LOST.DIR");