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.
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 #include <sys/cdefs.h>
31 __RCSID("$NetBSD: dir.c,v 1.20 2006/06/05 16:51:18 christos Exp $");
32 static const char rcsid[] =
43 #include <sys/param.h>
48 #define SLOT_EMPTY 0x00 /* slot has never been used */
49 #define SLOT_E5 0x05 /* the real value is 0xe5 */
50 #define SLOT_DELETED 0xe5 /* file in this slot deleted */
52 #define ATTR_NORMAL 0x00 /* normal file */
53 #define ATTR_READONLY 0x01 /* file is readonly */
54 #define ATTR_HIDDEN 0x02 /* file is hidden */
55 #define ATTR_SYSTEM 0x04 /* file is a system file */
56 #define ATTR_VOLUME 0x08 /* entry is a volume label */
57 #define ATTR_DIRECTORY 0x10 /* entry is a directory name */
58 #define ATTR_ARCHIVE 0x20 /* file is new or modified */
60 #define ATTR_WIN95 0x0f /* long name record */
63 * This is the format of the contents of the deTime field in the direntry
65 * We don't use bitfields because we don't know how compilers for
66 * arbitrary machines will lay them out.
68 #define DT_2SECONDS_MASK 0x1F /* seconds divided by 2 */
69 #define DT_2SECONDS_SHIFT 0
70 #define DT_MINUTES_MASK 0x7E0 /* minutes */
71 #define DT_MINUTES_SHIFT 5
72 #define DT_HOURS_MASK 0xF800 /* hours */
73 #define DT_HOURS_SHIFT 11
76 * This is the format of the contents of the deDate field in the direntry
79 #define DD_DAY_MASK 0x1F /* day of month */
80 #define DD_DAY_SHIFT 0
81 #define DD_MONTH_MASK 0x1E0 /* month */
82 #define DD_MONTH_SHIFT 5
83 #define DD_YEAR_MASK 0xFE00 /* year - 1980 */
84 #define DD_YEAR_SHIFT 9
88 static struct dosDirEntry *newDosDirEntry(void);
89 static void freeDosDirEntry(struct dosDirEntry *);
90 static struct dirTodoNode *newDirTodo(void);
91 static void freeDirTodo(struct dirTodoNode *);
92 static char *fullpath(struct dosDirEntry *);
93 static u_char calcShortSum(u_char *);
94 static int delete(int, struct bootblock *, struct fatEntry *, cl_t, int,
96 static int removede(int, struct bootblock *, struct fatEntry *, u_char *,
97 u_char *, cl_t, cl_t, cl_t, char *, int);
98 static int checksize(struct bootblock *, struct fatEntry *, u_char *,
99 struct dosDirEntry *);
100 static int readDosDirSection(int, struct bootblock *, struct fatEntry *,
101 struct dosDirEntry *);
104 * Manage free dosDirEntry structures.
106 static struct dosDirEntry *freede;
108 static struct dosDirEntry *
111 struct dosDirEntry *de;
113 if (!(de = freede)) {
114 if (!(de = (struct dosDirEntry *)malloc(sizeof *de)))
122 freeDosDirEntry(struct dosDirEntry *de)
129 * The same for dirTodoNode structures.
131 static struct dirTodoNode *freedt;
133 static struct dirTodoNode *
136 struct dirTodoNode *dt;
138 if (!(dt = freedt)) {
139 if (!(dt = (struct dirTodoNode *)malloc(sizeof *dt)))
147 freeDirTodo(struct dirTodoNode *dt)
154 * The stack of unread directories
156 static struct dirTodoNode *pendingDirectories = NULL;
159 * Return the full pathname for a directory entry.
162 fullpath(struct dosDirEntry *dir)
164 static char namebuf[MAXPATHLEN + 1];
168 cp = namebuf + sizeof namebuf - 1;
171 np = dir->lname[0] ? dir->lname : dir->name;
173 if ((cp -= nl) <= namebuf + 1)
177 } while ((dir = dir->parent) != NULL);
186 * Calculate a checksum over an 8.3 alias name
189 calcShortSum(u_char *p)
194 for (i = 0; i < 11; i++) {
195 sum = (sum << 7)|(sum >> 1); /* rotate right */
203 * Global variables temporarily used during a directory scan
205 static char longName[DOSLONGNAMELEN] = "";
206 static u_char *buffer = NULL;
207 static u_char *delbuf = NULL;
209 struct dosDirEntry *rootDir;
210 static struct dosDirEntry *lostDir;
213 * Init internal state for a new directory scan.
216 resetDosDirSection(struct bootblock *boot, struct fatEntry *fat)
223 b1 = boot->bpbRootDirEnts * 32;
224 b2 = boot->bpbSecPerClust * boot->bpbBytesPerSec;
226 if ((buffer = malloc(len = b1 > b2 ? b1 : b2)) == NULL) {
227 perr("No space for directory buffer (%zu)", len);
231 if ((delbuf = malloc(len = b2)) == NULL) {
233 perr("No space for directory delbuf (%zu)", len);
237 if ((rootDir = newDosDirEntry()) == NULL) {
240 perr("No space for directory entry");
244 memset(rootDir, 0, sizeof *rootDir);
245 if (boot->flags & FAT32) {
246 if (boot->bpbRootClust < CLUST_FIRST ||
247 boot->bpbRootClust >= boot->NumClusters) {
248 pfatal("Root directory starts with cluster out of range(%u)",
252 cl = fat[boot->bpbRootClust].next;
254 || (cl >= CLUST_RSRVD && cl< CLUST_EOFS)
255 || fat[boot->bpbRootClust].head != boot->bpbRootClust) {
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->bpbRootClust].next = CLUST_FREE;
272 fat[boot->bpbRootClust].flags |= FAT_USED;
273 rootDir->head = boot->bpbRootClust;
280 * Cleanup after a directory scan
283 finishDosDirSection(void)
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(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
314 int startoff, cl_t endcl, int endoff, int notlast)
318 int clsz = boot->bpbSecPerClust * boot->bpbBytesPerSec;
320 s = delbuf + startoff;
322 while (startcl >= CLUST_FIRST && startcl < boot->NumClusters) {
323 if (startcl == endcl) {
328 off = startcl * boot->bpbSecPerClust + boot->ClusterOffset;
329 off *= boot->bpbBytesPerSec;
330 if (lseek(f, off, SEEK_SET) != off
331 || read(f, delbuf, clsz) != clsz) {
332 perr("Unable to read directory");
339 if (lseek(f, off, SEEK_SET) != off
340 || write(f, delbuf, clsz) != clsz) {
341 perr("Unable to write directory");
344 if (startcl == endcl)
346 startcl = fat[startcl].next;
353 removede(int f, struct bootblock *boot, struct fatEntry *fat, u_char *start,
354 u_char *end, cl_t startcl, cl_t endcl, cl_t curcl, char *path, int type)
358 pwarn("Invalid long filename entry for %s\n", path);
361 pwarn("Invalid long filename entry at end of directory %s\n",
365 pwarn("Invalid long filename entry for volume label\n");
368 if (ask(0, "Remove")) {
369 if (startcl != curcl) {
370 if (delete(f, boot, fat,
371 startcl, start - buffer,
373 endcl == curcl) == FSFATAL)
377 /* startcl is < CLUST_FIRST for !fat32 root */
378 if ((endcl == curcl) || (startcl < CLUST_FIRST))
379 for (; start < end; start += 32)
380 *start = SLOT_DELETED;
387 * Check an in-memory file entry
390 checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
391 struct dosDirEntry *dir)
394 * Check size on ordinary files
396 u_int32_t physicalSize;
398 if (dir->head == CLUST_FREE)
401 if (dir->head < CLUST_FIRST || dir->head >= boot->NumClusters)
403 physicalSize = fat[dir->head].length * boot->ClusterSize;
405 if (physicalSize < dir->size) {
406 pwarn("size of %s is %u, should at most be %u\n",
407 fullpath(dir), dir->size, physicalSize);
408 if (ask(1, "Truncate")) {
409 dir->size = physicalSize;
410 p[28] = (u_char)physicalSize;
411 p[29] = (u_char)(physicalSize >> 8);
412 p[30] = (u_char)(physicalSize >> 16);
413 p[31] = (u_char)(physicalSize >> 24);
417 } else if (physicalSize - dir->size >= boot->ClusterSize) {
418 pwarn("%s has too many clusters allocated\n",
420 if (ask(1, "Drop superfluous clusters")) {
424 for (cl = dir->head; (sz += boot->ClusterSize) <
427 clearchain(boot, fat, fat[cl].next);
428 fat[cl].next = CLUST_EOF;
437 * Read a directory and
438 * - resolve long name records
439 * - enter file and directory records into the parent's list
440 * - push directories onto the todo-stack
443 readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
444 struct dosDirEntry *dir)
446 struct dosDirEntry dirent, *d;
447 u_char *p, *vallfn, *invlfn, *empty;
450 cl_t cl, valcl = ~0, invcl = ~0, empcl = ~0;
455 #define THISMOD 0x8000 /* Only used within this routine */
458 if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
460 * Already handled somewhere else.
465 vallfn = invlfn = empty = NULL;
467 if (!(boot->flags & FAT32) && !dir->parent) {
468 last = boot->bpbRootDirEnts * 32;
469 off = boot->bpbResSectors + boot->bpbFATs *
472 last = boot->bpbSecPerClust * boot->bpbBytesPerSec;
473 off = cl * boot->bpbSecPerClust + boot->ClusterOffset;
476 off *= boot->bpbBytesPerSec;
477 if (lseek(f, off, SEEK_SET) != off
478 || read(f, buffer, last) != last) {
479 perr("Unable to read directory");
484 * Check `.' and `..' entries here? XXX
486 for (p = buffer, i = 0; i < last; i++, p += 32) {
487 if (dir->fsckflags & DIREMPWARN) {
492 if (*p == SLOT_EMPTY || *p == SLOT_DELETED) {
493 if (*p == SLOT_EMPTY) {
494 dir->fsckflags |= DIREMPTY;
501 if (dir->fsckflags & DIREMPTY) {
502 if (!(dir->fsckflags & DIREMPWARN)) {
503 pwarn("%s has entries after end of directory\n",
505 if (ask(1, "Extend")) {
508 dir->fsckflags &= ~DIREMPTY;
509 if (delete(f, boot, fat,
510 empcl, empty - buffer,
511 cl, p - buffer, 1) == FSFATAL)
513 q = empcl == cl ? empty : buffer;
514 for (; q < p; q += 32)
516 mod |= THISMOD|FSDIRMOD;
517 } else if (ask(0, "Truncate"))
518 dir->fsckflags |= DIREMPWARN;
520 if (dir->fsckflags & DIREMPWARN) {
522 mod |= THISMOD|FSDIRMOD;
524 } else if (dir->fsckflags & DIREMPTY)
529 if (p[11] == ATTR_WIN95) {
531 if (shortSum != -1) {
537 memset(longName, 0, sizeof longName);
541 } else if (shortSum != p[13]
542 || lidx != (*p & LRNOMASK)) {
553 lidx = *p & LRNOMASK;
554 t = longName + --lidx * 13;
555 for (k = 1; k < 11 && t < longName +
556 sizeof(longName); k += 2) {
557 if (!p[k] && !p[k + 1])
561 * Warn about those unusable chars in msdosfs here? XXX
567 for (k = 14; k < 26 && t < longName + sizeof(longName); k += 2) {
568 if (!p[k] && !p[k + 1])
575 for (k = 28; k < 32 && t < longName + sizeof(longName); k += 2) {
576 if (!p[k] && !p[k + 1])
582 if (t >= longName + sizeof(longName)) {
583 pwarn("long filename too long\n");
590 if (p[26] | (p[27] << 8)) {
591 pwarn("long filename record cluster start != 0\n");
598 continue; /* long records don't carry further
603 * This is a standard msdosfs directory entry.
605 memset(&dirent, 0, sizeof dirent);
608 * it's a short name record, but we need to know
609 * more, so get the flags first.
611 dirent.flags = p[11];
614 * Translate from 850 to ISO here XXX
616 for (j = 0; j < 8; j++)
617 dirent.name[j] = p[j];
618 dirent.name[8] = '\0';
619 for (k = 7; k >= 0 && dirent.name[k] == ' '; k--)
620 dirent.name[k] = '\0';
621 if (dirent.name[k] != '\0')
623 if (dirent.name[0] == SLOT_E5)
624 dirent.name[0] = 0xe5;
626 if (dirent.flags & ATTR_VOLUME) {
627 if (vallfn || invlfn) {
628 mod |= removede(f, boot, fat,
629 invlfn ? invlfn : vallfn, p,
630 invlfn ? invcl : valcl, -1, 0,
639 dirent.name[k++] = '.';
640 for (j = 0; j < 3; j++)
641 dirent.name[k++] = p[j+8];
642 dirent.name[k] = '\0';
643 for (k--; k >= 0 && dirent.name[k] == ' '; k--)
644 dirent.name[k] = '\0';
646 if (vallfn && shortSum != calcShortSum(p)) {
653 dirent.head = p[26] | (p[27] << 8);
654 if (boot->ClustMask == CLUST32_MASK)
655 dirent.head |= (p[20] << 16) | (p[21] << 24);
656 dirent.size = p[28] | (p[29] << 8) | (p[30] << 16) | (p[31] << 24);
658 strlcpy(dirent.lname, longName,
659 sizeof(dirent.lname));
665 dirent.next = dir->child;
668 mod |= k = removede(f, boot, fat,
669 invlfn, vallfn ? vallfn : p,
670 invcl, vallfn ? valcl : cl, cl,
671 fullpath(&dirent), 0);
675 ? (valcl == cl && vallfn != buffer)
681 vallfn = NULL; /* not used any longer */
684 if (dirent.size == 0 && !(dirent.flags & ATTR_DIRECTORY)) {
685 if (dirent.head != 0) {
686 pwarn("%s has clusters, but size 0\n",
688 if (ask(1, "Drop allocated clusters")) {
690 if (boot->ClustMask == CLUST32_MASK)
692 clearchain(boot, fat, dirent.head);
694 mod |= THISMOD|FSDIRMOD|FSFATMOD;
698 } else if (dirent.head == 0
699 && !strcmp(dirent.name, "..")
700 && dir->parent /* XXX */
701 && !dir->parent->parent) {
703 * Do nothing, the parent is the root
705 } else if (dirent.head < CLUST_FIRST
706 || dirent.head >= boot->NumClusters
707 || fat[dirent.head].next == CLUST_FREE
708 || (fat[dirent.head].next >= CLUST_RSRVD
709 && fat[dirent.head].next < CLUST_EOFS)
710 || fat[dirent.head].head != dirent.head) {
711 if (dirent.head == 0)
712 pwarn("%s has no clusters\n",
714 else if (dirent.head < CLUST_FIRST
715 || dirent.head >= boot->NumClusters)
716 pwarn("%s starts with cluster out of range(%u)\n",
719 else if (fat[dirent.head].next == CLUST_FREE)
720 pwarn("%s starts with free cluster\n",
722 else if (fat[dirent.head].next >= CLUST_RSRVD)
723 pwarn("%s starts with cluster marked %s\n",
725 rsrvdcltype(fat[dirent.head].next));
727 pwarn("%s doesn't start a cluster chain\n",
729 if (dirent.flags & ATTR_DIRECTORY) {
730 if (ask(0, "Remove")) {
732 mod |= THISMOD|FSDIRMOD;
737 if (ask(1, "Truncate")) {
738 p[28] = p[29] = p[30] = p[31] = 0;
740 if (boot->ClustMask == CLUST32_MASK)
743 mod |= THISMOD|FSDIRMOD;
749 if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters)
750 fat[dirent.head].flags |= FAT_USED;
752 if (dirent.flags & ATTR_DIRECTORY) {
754 * gather more info for directories
756 struct dirTodoNode *n;
759 pwarn("Directory %s has size != 0\n",
761 if (ask(1, "Correct")) {
762 p[28] = p[29] = p[30] = p[31] = 0;
764 mod |= THISMOD|FSDIRMOD;
769 * handle `.' and `..' specially
771 if (strcmp(dirent.name, ".") == 0) {
772 if (dirent.head != dir->head) {
773 pwarn("`.' entry in %s has incorrect start cluster\n",
775 if (ask(1, "Correct")) {
776 dirent.head = dir->head;
777 p[26] = (u_char)dirent.head;
778 p[27] = (u_char)(dirent.head >> 8);
779 if (boot->ClustMask == CLUST32_MASK) {
780 p[20] = (u_char)(dirent.head >> 16);
781 p[21] = (u_char)(dirent.head >> 24);
783 mod |= THISMOD|FSDIRMOD;
789 if (strcmp(dirent.name, "..") == 0) {
790 if (dir->parent) { /* XXX */
791 if (!dir->parent->parent) {
793 pwarn("`..' entry in %s has non-zero start cluster\n",
795 if (ask(1, "Correct")) {
798 if (boot->ClustMask == CLUST32_MASK)
800 mod |= THISMOD|FSDIRMOD;
804 } else if (dirent.head != dir->parent->head) {
805 pwarn("`..' entry in %s has incorrect start cluster\n",
807 if (ask(1, "Correct")) {
808 dirent.head = dir->parent->head;
809 p[26] = (u_char)dirent.head;
810 p[27] = (u_char)(dirent.head >> 8);
811 if (boot->ClustMask == CLUST32_MASK) {
812 p[20] = (u_char)(dirent.head >> 16);
813 p[21] = (u_char)(dirent.head >> 24);
815 mod |= THISMOD|FSDIRMOD;
823 /* create directory tree node */
824 if (!(d = newDosDirEntry())) {
825 perr("No space for directory");
828 memcpy(d, &dirent, sizeof(struct dosDirEntry));
829 /* link it into the tree */
832 /* Enter this directory into the todo list */
833 if (!(n = newDirTodo())) {
834 perr("No space for todo list");
837 n->next = pendingDirectories;
839 pendingDirectories = n;
841 mod |= k = checksize(boot, fat, p, &dirent);
848 if (!(boot->flags & FAT32) && !dir->parent)
853 if (lseek(f, off, SEEK_SET) != off
854 || write(f, buffer, last) != last) {
855 perr("Unable to write directory");
860 } while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
861 if (invlfn || vallfn)
862 mod |= removede(f, boot, fat,
863 invlfn ? invlfn : vallfn, p,
864 invlfn ? invcl : valcl, -1, 0,
867 /* The root directory of non fat32 filesystems is in a special
868 * area and may have been modified above without being written out.
870 if ((mod & FSDIRMOD) && !(boot->flags & FAT32) && !dir->parent) {
872 if (lseek(f, off, SEEK_SET) != off
873 || write(f, buffer, last) != last) {
874 perr("Unable to write directory");
879 return mod & ~THISMOD;
883 handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
887 mod = readDosDirSection(dosfs, boot, fat, rootDir);
892 * process the directory todo list
894 while (pendingDirectories) {
895 struct dosDirEntry *dir = pendingDirectories->dir;
896 struct dirTodoNode *n = pendingDirectories->next;
899 * remove TODO entry now, the list might change during
902 freeDirTodo(pendingDirectories);
903 pendingDirectories = n;
906 * handle subdirectory
908 mod |= readDosDirSection(dosfs, boot, fat, dir);
917 * Try to reconnect a FAT chain into dir
919 static u_char *lfbuf;
924 reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
926 struct dosDirEntry d;
929 if (!ask(1, "Reconnect"))
933 for (lostDir = rootDir->child; lostDir; lostDir = lostDir->next) {
934 if (!strcmp(lostDir->name, LOSTDIR))
937 if (!lostDir) { /* Create LOSTDIR? XXX */
938 pwarn("No %s directory\n", LOSTDIR);
943 lfbuf = malloc(boot->ClusterSize);
945 perr("No space for buffer");
953 for (; p < lfbuf + boot->ClusterSize; p += 32)
955 || *p == SLOT_DELETED)
957 if (p && p < lfbuf + boot->ClusterSize)
959 lfcl = p ? fat[lfcl].next : lostDir->head;
960 if (lfcl < CLUST_FIRST || lfcl >= boot->NumClusters) {
961 /* Extend LOSTDIR? XXX */
962 pwarn("No space in %s\n", LOSTDIR);
965 lfoff = lfcl * boot->ClusterSize
966 + boot->ClusterOffset * boot->bpbBytesPerSec;
967 if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
968 || (size_t)read(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
969 perr("could not read LOST.DIR");
976 /* Ensure uniqueness of entry here! XXX */
977 memset(&d, 0, sizeof d);
978 (void)snprintf(d.name, sizeof(d.name), "%u", head);
981 d.size = fat[head].length * boot->ClusterSize;
985 memcpy(p, d.name, strlen(d.name));
986 p[26] = (u_char)d.head;
987 p[27] = (u_char)(d.head >> 8);
988 if (boot->ClustMask == CLUST32_MASK) {
989 p[20] = (u_char)(d.head >> 16);
990 p[21] = (u_char)(d.head >> 24);
992 p[28] = (u_char)d.size;
993 p[29] = (u_char)(d.size >> 8);
994 p[30] = (u_char)(d.size >> 16);
995 p[31] = (u_char)(d.size >> 24);
996 fat[head].flags |= FAT_USED;
997 if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
998 || (size_t)write(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
999 perr("could not write LOST.DIR");