sbin/fsck_msdosfs/dir.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
   5  * Copyright (c) 1995 Martin Husemann
   6  * Some structure declaration borrowed from Paul Popelka
   7  * (paulp@uts.amdahl.com), see /sys/msdosfs/ for reference.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30
  31 #include <sys/cdefs.h>
  32 #ifndef lint
  33 __RCSID("$NetBSD: dir.c,v 1.20 2006/06/05 16:51:18 christos Exp $");
  34 static const char rcsid[] =
  35   "$FreeBSD$";
  36 #endif /* not lint */
  37
  38 #include <assert.h>
  39 #include <inttypes.h>
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <ctype.h>
  44 #include <unistd.h>
  45 #include <time.h>
  46
  47 #include <sys/param.h>
  48
  49 #include "ext.h"
  50 #include "fsutil.h"
  51
  52 #define SLOT_EMPTY      0x00            /* slot has never been used */
  53 #define SLOT_E5         0x05            /* the real value is 0xe5 */
  54 #define SLOT_DELETED    0xe5            /* file in this slot deleted */
  55
  56 #define ATTR_NORMAL     0x00            /* normal file */
  57 #define ATTR_READONLY   0x01            /* file is readonly */
  58 #define ATTR_HIDDEN     0x02            /* file is hidden */
  59 #define ATTR_SYSTEM     0x04            /* file is a system file */
  60 #define ATTR_VOLUME     0x08            /* entry is a volume label */
  61 #define ATTR_DIRECTORY  0x10            /* entry is a directory name */
  62 #define ATTR_ARCHIVE    0x20            /* file is new or modified */
  63
  64 #define ATTR_WIN95      0x0f            /* long name record */
  65
  66 /*
  67  * This is the format of the contents of the deTime field in the direntry
  68  * structure.
  69  * We don't use bitfields because we don't know how compilers for
  70  * arbitrary machines will lay them out.
  71  */
  72 #define DT_2SECONDS_MASK        0x1F    /* seconds divided by 2 */
  73 #define DT_2SECONDS_SHIFT       0
  74 #define DT_MINUTES_MASK         0x7E0   /* minutes */
  75 #define DT_MINUTES_SHIFT        5
  76 #define DT_HOURS_MASK           0xF800  /* hours */
  77 #define DT_HOURS_SHIFT          11
  78
  79 /*
  80  * This is the format of the contents of the deDate field in the direntry
  81  * structure.
  82  */
  83 #define DD_DAY_MASK             0x1F    /* day of month */
  84 #define DD_DAY_SHIFT            0
  85 #define DD_MONTH_MASK           0x1E0   /* month */
  86 #define DD_MONTH_SHIFT          5
  87 #define DD_YEAR_MASK            0xFE00  /* year - 1980 */
  88 #define DD_YEAR_SHIFT           9
  89
  90
  91 /* dir.c */
  92 static struct dosDirEntry *newDosDirEntry(void);
  93 static void freeDosDirEntry(struct dosDirEntry *);
  94 static struct dirTodoNode *newDirTodo(void);
  95 static void freeDirTodo(struct dirTodoNode *);
  96 static char *fullpath(struct dosDirEntry *);
  97 static u_char calcShortSum(u_char *);
  98 static int delete(int, struct bootblock *, struct fatEntry *, cl_t, int,
  99     cl_t, int, int);
 100 static int removede(int, struct bootblock *, struct fatEntry *, u_char *,
 101     u_char *, cl_t, cl_t, cl_t, char *, int);
 102 static int checksize(struct bootblock *, struct fatEntry *, u_char *,
 103     struct dosDirEntry *);
 104 static int readDosDirSection(int, struct bootblock *, struct fatEntry *,
 105     struct dosDirEntry *);
 106
 107 /*
 108  * Manage free dosDirEntry structures.
 109  */
 110 static struct dosDirEntry *freede;
 111
 112 static struct dosDirEntry *
 113 newDosDirEntry(void)
 114 {
 115         struct dosDirEntry *de;
 116
 117         if (!(de = freede)) {
 118                 if (!(de = malloc(sizeof *de)))
 119                         return 0;
 120         } else
 121                 freede = de->next;
 122         return de;
 123 }
 124
 125 static void
 126 freeDosDirEntry(struct dosDirEntry *de)
 127 {
 128         de->next = freede;
 129         freede = de;
 130 }
 131
 132 /*
 133  * The same for dirTodoNode structures.
 134  */
 135 static struct dirTodoNode *freedt;
 136
 137 static struct dirTodoNode *
 138 newDirTodo(void)
 139 {
 140         struct dirTodoNode *dt;
 141
 142         if (!(dt = freedt)) {
 143                 if (!(dt = malloc(sizeof *dt)))
 144                         return 0;
 145         } else
 146                 freedt = dt->next;
 147         return dt;
 148 }
 149
 150 static void
 151 freeDirTodo(struct dirTodoNode *dt)
 152 {
 153         dt->next = freedt;
 154         freedt = dt;
 155 }
 156
 157 /*
 158  * The stack of unread directories
 159  */
 160 static struct dirTodoNode *pendingDirectories = NULL;
 161
 162 /*
 163  * Return the full pathname for a directory entry.
 164  */
 165 static char *
 166 fullpath(struct dosDirEntry *dir)
 167 {
 168         static char namebuf[MAXPATHLEN + 1];
 169         char *cp, *np;
 170         int nl;
 171
 172         cp = namebuf + sizeof namebuf;
 173         *--cp = '\0';
 174
 175         for(;;) {
 176                 np = dir->lname[0] ? dir->lname : dir->name;
 177                 nl = strlen(np);
 178                 if (cp <= namebuf + 1 + nl) {
 179                         *--cp = '?';
 180                         break;
 181                 }
 182                 cp -= nl;
 183                 memcpy(cp, np, nl);
 184                 dir = dir->parent;
 185                 if (!dir)
 186                         break;
 187                 *--cp = '/';
 188         }
 189
 190         return cp;
 191 }
 192
 193 /*
 194  * Calculate a checksum over an 8.3 alias name
 195  */
 196 static u_char
 197 calcShortSum(u_char *p)
 198 {
 199         u_char sum = 0;
 200         int i;
 201
 202         for (i = 0; i < 11; i++) {
 203                 sum = (sum << 7)|(sum >> 1);    /* rotate right */
 204                 sum += p[i];
 205         }
 206
 207         return sum;
 208 }
 209
 210 /*
 211  * Global variables temporarily used during a directory scan
 212  */
 213 static char longName[DOSLONGNAMELEN] = "";
 214 static u_char *buffer = NULL;
 215 static u_char *delbuf = NULL;
 216
 217 static struct dosDirEntry *rootDir;
 218 static struct dosDirEntry *lostDir;
 219
 220 /*
 221  * Init internal state for a new directory scan.
 222  */
 223 int
 224 resetDosDirSection(struct bootblock *boot, struct fatEntry *fat)
 225 {
 226         int b1, b2;
 227         int ret = FSOK;
 228         size_t len;
 229
 230         b1 = boot->bpbRootDirEnts * 32;
 231         b2 = boot->bpbSecPerClust * boot->bpbBytesPerSec;
 232
 233         if ((buffer = malloc(len = MAX(b1, b2))) == NULL) {
 234                 perr("No space for directory buffer (%zu)", len);
 235                 return FSFATAL;
 236         }
 237
 238         if ((delbuf = malloc(len = b2)) == NULL) {
 239                 free(buffer);
 240                 perr("No space for directory delbuf (%zu)", len);
 241                 return FSFATAL;
 242         }
 243
 244         if ((rootDir = newDosDirEntry()) == NULL) {
 245                 free(buffer);
 246                 free(delbuf);
 247                 perr("No space for directory entry");
 248                 return FSFATAL;
 249         }
 250
 251         memset(rootDir, 0, sizeof *rootDir);
 252         if (boot->flags & FAT32) {
 253                 if (boot->bpbRootClust < CLUST_FIRST ||
 254                     boot->bpbRootClust >= boot->NumClusters) {
 255                         pfatal("Root directory starts with cluster out of range(%u)",
 256                                boot->bpbRootClust);
 257                         return FSFATAL;
 258                 }
 259                 if (fat[boot->bpbRootClust].head != boot->bpbRootClust) {
 260                         pfatal("Root directory doesn't start a cluster chain");
 261                         return FSFATAL;
 262                 }
 263
 264                 fat[boot->bpbRootClust].flags |= FAT_USED;
 265                 rootDir->head = boot->bpbRootClust;
 266         }
 267
 268         return ret;
 269 }
 270
 271 /*
 272  * Cleanup after a directory scan
 273  */
 274 void
 275 finishDosDirSection(void)
 276 {
 277         struct dirTodoNode *p, *np;
 278         struct dosDirEntry *d, *nd;
 279
 280         for (p = pendingDirectories; p; p = np) {
 281                 np = p->next;
 282                 freeDirTodo(p);
 283         }
 284         pendingDirectories = NULL;
 285         for (d = rootDir; d; d = nd) {
 286                 if ((nd = d->child) != NULL) {
 287                         d->child = 0;
 288                         continue;
 289                 }
 290                 if (!(nd = d->next))
 291                         nd = d->parent;
 292                 freeDosDirEntry(d);
 293         }
 294         rootDir = lostDir = NULL;
 295         free(buffer);
 296         free(delbuf);
 297         buffer = NULL;
 298         delbuf = NULL;
 299 }
 300
 301 /*
 302  * Delete directory entries between startcl, startoff and endcl, endoff.
 303  */
 304 static int
 305 delete(int f, struct bootblock *boot, struct fatEntry *fat, cl_t startcl,
 306     int startoff, cl_t endcl, int endoff, int notlast)
 307 {
 308         u_char *s, *e;
 309         off_t off;
 310         int clsz = boot->bpbSecPerClust * boot->bpbBytesPerSec;
 311
 312         s = delbuf + startoff;
 313         e = delbuf + clsz;
 314         while (startcl >= CLUST_FIRST && startcl < boot->NumClusters) {
 315                 if (startcl == endcl) {
 316                         if (notlast)
 317                                 break;
 318                         e = delbuf + endoff;
 319                 }
 320                 off = (startcl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
 321
 322                 off *= boot->bpbBytesPerSec;
 323                 if (lseek(f, off, SEEK_SET) != off) {
 324                         perr("Unable to lseek to %" PRId64, off);
 325                         return FSFATAL;
 326                 }
 327                 if (read(f, delbuf, clsz) != clsz) {
 328                         perr("Unable to read directory");
 329                         return FSFATAL;
 330                 }
 331                 while (s < e) {
 332                         *s = SLOT_DELETED;
 333                         s += 32;
 334                 }
 335                 if (lseek(f, off, SEEK_SET) != off) {
 336                         perr("Unable to lseek to %" PRId64, off);
 337                         return FSFATAL;
 338                 }
 339                 if (write(f, delbuf, clsz) != clsz) {
 340                         perr("Unable to write directory");
 341                         return FSFATAL;
 342                 }
 343                 if (startcl == endcl)
 344                         break;
 345                 startcl = fat[startcl].next;
 346                 s = delbuf;
 347         }
 348         return FSOK;
 349 }
 350
 351 static int
 352 removede(int f, struct bootblock *boot, struct fatEntry *fat, u_char *start,
 353     u_char *end, cl_t startcl, cl_t endcl, cl_t curcl, char *path, int type)
 354 {
 355         switch (type) {
 356         case 0:
 357                 pwarn("Invalid long filename entry for %s\n", path);
 358                 break;
 359         case 1:
 360                 pwarn("Invalid long filename entry at end of directory %s\n",
 361                     path);
 362                 break;
 363         case 2:
 364                 pwarn("Invalid long filename entry for volume label\n");
 365                 break;
 366         }
 367         if (ask(0, "Remove")) {
 368                 if (startcl != curcl) {
 369                         if (delete(f, boot, fat,
 370                                    startcl, start - buffer,
 371                                    endcl, end - buffer,
 372                                    endcl == curcl) == FSFATAL)
 373                                 return FSFATAL;
 374                         start = buffer;
 375                 }
 376                 /* startcl is < CLUST_FIRST for !fat32 root */
 377                 if ((endcl == curcl) || (startcl < CLUST_FIRST))
 378                         for (; start < end; start += 32)
 379                                 *start = SLOT_DELETED;
 380                 return FSDIRMOD;
 381         }
 382         return FSERROR;
 383 }
 384
 385 /*
 386  * Check an in-memory file entry
 387  */
 388 static int
 389 checksize(struct bootblock *boot, struct fatEntry *fat, u_char *p,
 390     struct dosDirEntry *dir)
 391 {
 392         /*
 393          * Check size on ordinary files
 394          */
 395         u_int32_t physicalSize;
 396
 397         if (dir->head == CLUST_FREE)
 398                 physicalSize = 0;
 399         else {
 400                 if (dir->head < CLUST_FIRST || dir->head >= boot->NumClusters)
 401                         return FSERROR;
 402                 physicalSize = fat[dir->head].length * boot->ClusterSize;
 403         }
 404         if (physicalSize < dir->size) {
 405                 pwarn("size of %s is %u, should at most be %u\n",
 406                       fullpath(dir), dir->size, physicalSize);
 407                 if (ask(1, "Truncate")) {
 408                         dir->size = physicalSize;
 409                         p[28] = (u_char)physicalSize;
 410                         p[29] = (u_char)(physicalSize >> 8);
 411                         p[30] = (u_char)(physicalSize >> 16);
 412                         p[31] = (u_char)(physicalSize >> 24);
 413                         return FSDIRMOD;
 414                 } else
 415                         return FSERROR;
 416         } else if (physicalSize - dir->size >= boot->ClusterSize) {
 417                 pwarn("%s has too many clusters allocated\n",
 418                       fullpath(dir));
 419                 if (ask(1, "Drop superfluous clusters")) {
 420                         cl_t cl;
 421                         u_int32_t sz, len;
 422
 423                         for (cl = dir->head, len = sz = 0;
 424                             (sz += boot->ClusterSize) < dir->size; len++)
 425                                 cl = fat[cl].next;
 426                         clearchain(boot, fat, fat[cl].next);
 427                         fat[cl].next = CLUST_EOF;
 428                         fat[dir->head].length = len;
 429                         return FSFATMOD;
 430                 } else
 431                         return FSERROR;
 432         }
 433         return FSOK;
 434 }
 435
 436 static const u_char dot_name[11]    = ".          ";
 437 static const u_char dotdot_name[11] = "..         ";
 438
 439 /*
 440  * Basic sanity check if the subdirectory have good '.' and '..' entries,
 441  * and they are directory entries.  Further sanity checks are performed
 442  * when we traverse into it.
 443  */
 444 static int
 445 check_subdirectory(int f, struct bootblock *boot, struct dosDirEntry *dir)
 446 {
 447         u_char *buf, *cp;
 448         off_t off;
 449         cl_t cl;
 450         int retval = FSOK;
 451
 452         cl = dir->head;
 453         if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
 454                 return FSERROR;
 455         }
 456
 457         if (!(boot->flags & FAT32) && !dir->parent) {
 458                 off = boot->bpbResSectors + boot->bpbFATs *
 459                         boot->FATsecs;
 460         } else {
 461                 off = (cl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
 462         }
 463
 464         /*
 465          * We only need to check the first two entries of the directory,
 466          * which is found in the first sector of the directory entry,
 467          * so read in only the first sector.
 468          */
 469         buf = malloc(boot->bpbBytesPerSec);
 470         if (buf == NULL) {
 471                 perr("No space for directory buffer (%u)",
 472                     boot->bpbBytesPerSec);
 473                 return FSFATAL;
 474         }
 475
 476         off *= boot->bpbBytesPerSec;
 477         if (lseek(f, off, SEEK_SET) != off ||
 478             read(f, buf, boot->bpbBytesPerSec) != (ssize_t)boot->bpbBytesPerSec) {
 479                 perr("Unable to read directory");
 480                 free(buf);
 481                 return FSFATAL;
 482         }
 483
 484         /*
 485          * Both `.' and `..' must be present and be the first two entries
 486          * and be ATTR_DIRECTORY of a valid subdirectory.
 487          */
 488         cp = buf;
 489         if (memcmp(cp, dot_name, sizeof(dot_name)) != 0 ||
 490             (cp[11] & ATTR_DIRECTORY) != ATTR_DIRECTORY) {
 491                 pwarn("%s: Incorrect `.' for %s.\n", __func__, dir->name);
 492                 retval |= FSERROR;
 493         }
 494         cp += 32;
 495         if (memcmp(cp, dotdot_name, sizeof(dotdot_name)) != 0 ||
 496             (cp[11] & ATTR_DIRECTORY) != ATTR_DIRECTORY) {
 497                 pwarn("%s: Incorrect `..' for %s. \n", __func__, dir->name);
 498                 retval |= FSERROR;
 499         }
 500
 501         free(buf);
 502         return retval;
 503 }
 504
 505 /*
 506  * Read a directory and
 507  *   - resolve long name records
 508  *   - enter file and directory records into the parent's list
 509  *   - push directories onto the todo-stack
 510  */
 511 static int
 512 readDosDirSection(int f, struct bootblock *boot, struct fatEntry *fat,
 513     struct dosDirEntry *dir)
 514 {
 515         struct dosDirEntry dirent, *d;
 516         u_char *p, *vallfn, *invlfn, *empty;
 517         off_t off;
 518         int i, j, k, last;
 519         cl_t cl, valcl = ~0, invcl = ~0, empcl = ~0;
 520         char *t;
 521         u_int lidx = 0;
 522         int shortSum;
 523         int mod = FSOK;
 524 #define THISMOD 0x8000                  /* Only used within this routine */
 525
 526         cl = dir->head;
 527         if (dir->parent && (cl < CLUST_FIRST || cl >= boot->NumClusters)) {
 528                 /*
 529                  * Already handled somewhere else.
 530                  */
 531                 return FSOK;
 532         }
 533         shortSum = -1;
 534         vallfn = invlfn = empty = NULL;
 535         do {
 536                 if (!(boot->flags & FAT32) && !dir->parent) {
 537                         last = boot->bpbRootDirEnts * 32;
 538                         off = boot->bpbResSectors + boot->bpbFATs *
 539                             boot->FATsecs;
 540                 } else {
 541                         last = boot->bpbSecPerClust * boot->bpbBytesPerSec;
 542                         off = (cl - CLUST_FIRST) * boot->bpbSecPerClust + boot->FirstCluster;
 543                 }
 544
 545                 off *= boot->bpbBytesPerSec;
 546                 if (lseek(f, off, SEEK_SET) != off
 547                     || read(f, buffer, last) != last) {
 548                         perr("Unable to read directory");
 549                         return FSFATAL;
 550                 }
 551                 last /= 32;
 552                 for (p = buffer, i = 0; i < last; i++, p += 32) {
 553                         if (dir->fsckflags & DIREMPWARN) {
 554                                 *p = SLOT_EMPTY;
 555                                 continue;
 556                         }
 557
 558                         if (*p == SLOT_EMPTY || *p == SLOT_DELETED) {
 559                                 if (*p == SLOT_EMPTY) {
 560                                         dir->fsckflags |= DIREMPTY;
 561                                         empty = p;
 562                                         empcl = cl;
 563                                 }
 564                                 continue;
 565                         }
 566
 567                         if (dir->fsckflags & DIREMPTY) {
 568                                 if (!(dir->fsckflags & DIREMPWARN)) {
 569                                         pwarn("%s has entries after end of directory\n",
 570                                               fullpath(dir));
 571                                         if (ask(1, "Extend")) {
 572                                                 u_char *q;
 573
 574                                                 dir->fsckflags &= ~DIREMPTY;
 575                                                 if (delete(f, boot, fat,
 576                                                            empcl, empty - buffer,
 577                                                            cl, p - buffer, 1) == FSFATAL)
 578                                                         return FSFATAL;
 579                                                 q = ((empcl == cl) ? empty : buffer);
 580                                                 assert(q != NULL);
 581                                                 for (; q < p; q += 32)
 582                                                         *q = SLOT_DELETED;
 583                                                 mod |= THISMOD|FSDIRMOD;
 584                                         } else if (ask(0, "Truncate"))
 585                                                 dir->fsckflags |= DIREMPWARN;
 586                                 }
 587                                 if (dir->fsckflags & DIREMPWARN) {
 588                                         *p = SLOT_DELETED;
 589                                         mod |= THISMOD|FSDIRMOD;
 590                                         continue;
 591                                 } else if (dir->fsckflags & DIREMPTY)
 592                                         mod |= FSERROR;
 593                                 empty = NULL;
 594                         }
 595
 596                         if (p[11] == ATTR_WIN95) {
 597                                 if (*p & LRFIRST) {
 598                                         if (shortSum != -1) {
 599                                                 if (!invlfn) {
 600                                                         invlfn = vallfn;
 601                                                         invcl = valcl;
 602                                                 }
 603                                         }
 604                                         memset(longName, 0, sizeof longName);
 605                                         shortSum = p[13];
 606                                         vallfn = p;
 607                                         valcl = cl;
 608                                 } else if (shortSum != p[13]
 609                                            || lidx != (*p & LRNOMASK)) {
 610                                         if (!invlfn) {
 611                                                 invlfn = vallfn;
 612                                                 invcl = valcl;
 613                                         }
 614                                         if (!invlfn) {
 615                                                 invlfn = p;
 616                                                 invcl = cl;
 617                                         }
 618                                         vallfn = NULL;
 619                                 }
 620                                 lidx = *p & LRNOMASK;
 621                                 if (lidx == 0) {
 622                                         pwarn("invalid long name\n");
 623                                         if (!invlfn) {
 624                                                 invlfn = vallfn;
 625                                                 invcl = valcl;
 626                                         }
 627                                         vallfn = NULL;
 628                                         continue;
 629                                 }
 630                                 t = longName + --lidx * 13;
 631                                 for (k = 1; k < 11 && t < longName +
 632                                     sizeof(longName); k += 2) {
 633                                         if (!p[k] && !p[k + 1])
 634                                                 break;
 635                                         *t++ = p[k];
 636                                         /*
 637                                          * Warn about those unusable chars in msdosfs here?     XXX
 638                                          */
 639                                         if (p[k + 1])
 640                                                 t[-1] = '?';
 641                                 }
 642                                 if (k >= 11)
 643                                         for (k = 14; k < 26 && t < longName + sizeof(longName); k += 2) {
 644                                                 if (!p[k] && !p[k + 1])
 645                                                         break;
 646                                                 *t++ = p[k];
 647                                                 if (p[k + 1])
 648                                                         t[-1] = '?';
 649                                         }
 650                                 if (k >= 26)
 651                                         for (k = 28; k < 32 && t < longName + sizeof(longName); k += 2) {
 652                                                 if (!p[k] && !p[k + 1])
 653                                                         break;
 654                                                 *t++ = p[k];
 655                                                 if (p[k + 1])
 656                                                         t[-1] = '?';
 657                                         }
 658                                 if (t >= longName + sizeof(longName)) {
 659                                         pwarn("long filename too long\n");
 660                                         if (!invlfn) {
 661                                                 invlfn = vallfn;
 662                                                 invcl = valcl;
 663                                         }
 664                                         vallfn = NULL;
 665                                 }
 666                                 if (p[26] | (p[27] << 8)) {
 667                                         pwarn("long filename record cluster start != 0\n");
 668                                         if (!invlfn) {
 669                                                 invlfn = vallfn;
 670                                                 invcl = cl;
 671                                         }
 672                                         vallfn = NULL;
 673                                 }
 674                                 continue;       /* long records don't carry further
 675                                                  * information */
 676                         }
 677
 678                         /*
 679                          * This is a standard msdosfs directory entry.
 680                          */
 681                         memset(&dirent, 0, sizeof dirent);
 682
 683                         /*
 684                          * it's a short name record, but we need to know
 685                          * more, so get the flags first.
 686                          */
 687                         dirent.flags = p[11];
 688
 689                         /*
 690                          * Translate from 850 to ISO here               XXX
 691                          */
 692                         for (j = 0; j < 8; j++)
 693                                 dirent.name[j] = p[j];
 694                         dirent.name[8] = '\0';
 695                         for (k = 7; k >= 0 && dirent.name[k] == ' '; k--)
 696                                 dirent.name[k] = '\0';
 697                         if (k < 0 || dirent.name[k] != '\0')
 698                                 k++;
 699                         if (dirent.name[0] == SLOT_E5)
 700                                 dirent.name[0] = 0xe5;
 701
 702                         if (dirent.flags & ATTR_VOLUME) {
 703                                 if (vallfn || invlfn) {
 704                                         mod |= removede(f, boot, fat,
 705                                                         invlfn ? invlfn : vallfn, p,
 706                                                         invlfn ? invcl : valcl, -1, 0,
 707                                                         fullpath(dir), 2);
 708                                         vallfn = NULL;
 709                                         invlfn = NULL;
 710                                 }
 711                                 continue;
 712                         }
 713
 714                         if (p[8] != ' ')
 715                                 dirent.name[k++] = '.';
 716                         for (j = 0; j < 3; j++)
 717                                 dirent.name[k++] = p[j+8];
 718                         dirent.name[k] = '\0';
 719                         for (k--; k >= 0 && dirent.name[k] == ' '; k--)
 720                                 dirent.name[k] = '\0';
 721
 722                         if (vallfn && shortSum != calcShortSum(p)) {
 723                                 if (!invlfn) {
 724                                         invlfn = vallfn;
 725                                         invcl = valcl;
 726                                 }
 727                                 vallfn = NULL;
 728                         }
 729                         dirent.head = p[26] | (p[27] << 8);
 730                         if (boot->ClustMask == CLUST32_MASK)
 731                                 dirent.head |= (p[20] << 16) | (p[21] << 24);
 732                         dirent.size = p[28] | (p[29] << 8) | (p[30] << 16) | (p[31] << 24);
 733                         if (vallfn) {
 734                                 strlcpy(dirent.lname, longName,
 735                                     sizeof(dirent.lname));
 736                                 longName[0] = '\0';
 737                                 shortSum = -1;
 738                         }
 739
 740                         dirent.parent = dir;
 741                         dirent.next = dir->child;
 742
 743                         if (invlfn) {
 744                                 mod |= k = removede(f, boot, fat,
 745                                                     invlfn, vallfn ? vallfn : p,
 746                                                     invcl, vallfn ? valcl : cl, cl,
 747                                                     fullpath(&dirent), 0);
 748                                 if (mod & FSFATAL)
 749                                         return FSFATAL;
 750                                 if (vallfn
 751                                     ? (valcl == cl && vallfn != buffer)
 752                                     : p != buffer)
 753                                         if (k & FSDIRMOD)
 754                                                 mod |= THISMOD;
 755                         }
 756
 757                         vallfn = NULL; /* not used any longer */
 758                         invlfn = NULL;
 759
 760                         if (dirent.size == 0 && !(dirent.flags & ATTR_DIRECTORY)) {
 761                                 if (dirent.head != 0) {
 762                                         pwarn("%s has clusters, but size 0\n",
 763                                               fullpath(&dirent));
 764                                         if (ask(1, "Drop allocated clusters")) {
 765                                                 p[26] = p[27] = 0;
 766                                                 if (boot->ClustMask == CLUST32_MASK)
 767                                                         p[20] = p[21] = 0;
 768                                                 clearchain(boot, fat, dirent.head);
 769                                                 dirent.head = 0;
 770                                                 mod |= THISMOD|FSDIRMOD|FSFATMOD;
 771                                         } else
 772                                                 mod |= FSERROR;
 773                                 }
 774                         } else if (dirent.head == 0
 775                                    && !strcmp(dirent.name, "..")
 776                                    && dir->parent                       /* XXX */
 777                                    && !dir->parent->parent) {
 778                                 /*
 779                                  *  Do nothing, the parent is the root
 780                                  */
 781                         } else if (dirent.head < CLUST_FIRST
 782                                    || dirent.head >= boot->NumClusters
 783                                    || fat[dirent.head].next == CLUST_FREE
 784                                    || (fat[dirent.head].next >= CLUST_RSRVD
 785                                        && fat[dirent.head].next < CLUST_EOFS)
 786                                    || fat[dirent.head].head != dirent.head) {
 787                                 if (dirent.head == 0)
 788                                         pwarn("%s has no clusters\n",
 789                                               fullpath(&dirent));
 790                                 else if (dirent.head < CLUST_FIRST
 791                                          || dirent.head >= boot->NumClusters)
 792                                         pwarn("%s starts with cluster out of range(%u)\n",
 793                                               fullpath(&dirent),
 794                                               dirent.head);
 795                                 else if (fat[dirent.head].next == CLUST_FREE)
 796                                         pwarn("%s starts with free cluster\n",
 797                                               fullpath(&dirent));
 798                                 else if (fat[dirent.head].next >= CLUST_RSRVD)
 799                                         pwarn("%s starts with cluster marked %s\n",
 800                                               fullpath(&dirent),
 801                                               rsrvdcltype(fat[dirent.head].next));
 802                                 else
 803                                         pwarn("%s doesn't start a cluster chain\n",
 804                                               fullpath(&dirent));
 805                                 if (dirent.flags & ATTR_DIRECTORY) {
 806                                         if (ask(0, "Remove")) {
 807                                                 *p = SLOT_DELETED;
 808                                                 mod |= THISMOD|FSDIRMOD;
 809                                         } else
 810                                                 mod |= FSERROR;
 811                                         continue;
 812                                 } else {
 813                                         if (ask(1, "Truncate")) {
 814                                                 p[28] = p[29] = p[30] = p[31] = 0;
 815                                                 p[26] = p[27] = 0;
 816                                                 if (boot->ClustMask == CLUST32_MASK)
 817                                                         p[20] = p[21] = 0;
 818                                                 dirent.size = 0;
 819                                                 mod |= THISMOD|FSDIRMOD;
 820                                         } else
 821                                                 mod |= FSERROR;
 822                                 }
 823                         }
 824
 825                         if (dirent.head >= CLUST_FIRST && dirent.head < boot->NumClusters)
 826                                 fat[dirent.head].flags |= FAT_USED;
 827
 828                         if (dirent.flags & ATTR_DIRECTORY) {
 829                                 /*
 830                                  * gather more info for directories
 831                                  */
 832                                 struct dirTodoNode *n;
 833
 834                                 if (dirent.size) {
 835                                         pwarn("Directory %s has size != 0\n",
 836                                               fullpath(&dirent));
 837                                         if (ask(1, "Correct")) {
 838                                                 p[28] = p[29] = p[30] = p[31] = 0;
 839                                                 dirent.size = 0;
 840                                                 mod |= THISMOD|FSDIRMOD;
 841                                         } else
 842                                                 mod |= FSERROR;
 843                                 }
 844                                 /*
 845                                  * handle `.' and `..' specially
 846                                  */
 847                                 if (strcmp(dirent.name, ".") == 0) {
 848                                         if (dirent.head != dir->head) {
 849                                                 pwarn("`.' entry in %s has incorrect start cluster\n",
 850                                                       fullpath(dir));
 851                                                 if (ask(1, "Correct")) {
 852                                                         dirent.head = dir->head;
 853                                                         p[26] = (u_char)dirent.head;
 854                                                         p[27] = (u_char)(dirent.head >> 8);
 855                                                         if (boot->ClustMask == CLUST32_MASK) {
 856                                                                 p[20] = (u_char)(dirent.head >> 16);
 857                                                                 p[21] = (u_char)(dirent.head >> 24);
 858                                                         }
 859                                                         mod |= THISMOD|FSDIRMOD;
 860                                                 } else
 861                                                         mod |= FSERROR;
 862                                         }
 863                                         continue;
 864                                 }
 865                                 if (strcmp(dirent.name, "..") == 0) {
 866                                         if (dir->parent) {              /* XXX */
 867                                                 if (!dir->parent->parent) {
 868                                                         if (dirent.head) {
 869                                                                 pwarn("`..' entry in %s has non-zero start cluster\n",
 870                                                                       fullpath(dir));
 871                                                                 if (ask(1, "Correct")) {
 872                                                                         dirent.head = 0;
 873                                                                         p[26] = p[27] = 0;
 874                                                                         if (boot->ClustMask == CLUST32_MASK)
 875                                                                                 p[20] = p[21] = 0;
 876                                                                         mod |= THISMOD|FSDIRMOD;
 877                                                                 } else
 878                                                                         mod |= FSERROR;
 879                                                         }
 880                                                 } else if (dirent.head != dir->parent->head) {
 881                                                         pwarn("`..' entry in %s has incorrect start cluster\n",
 882                                                               fullpath(dir));
 883                                                         if (ask(1, "Correct")) {
 884                                                                 dirent.head = dir->parent->head;
 885                                                                 p[26] = (u_char)dirent.head;
 886                                                                 p[27] = (u_char)(dirent.head >> 8);
 887                                                                 if (boot->ClustMask == CLUST32_MASK) {
 888                                                                         p[20] = (u_char)(dirent.head >> 16);
 889                                                                         p[21] = (u_char)(dirent.head >> 24);
 890                                                                 }
 891                                                                 mod |= THISMOD|FSDIRMOD;
 892                                                         } else
 893                                                                 mod |= FSERROR;
 894                                                 }
 895                                         }
 896                                         continue;
 897                                 } else {
 898                                         /*
 899                                          * Only one directory entry can point
 900                                          * to dir->head, it's '.'.
 901                                          */
 902                                         if (dirent.head == dir->head) {
 903                                                 pwarn("%s entry in %s has incorrect start cluster\n",
 904                                                                 dirent.name, fullpath(dir));
 905                                                 if (ask(1, "Remove")) {
 906                                                         *p = SLOT_DELETED;
 907                                                         mod |= THISMOD|FSDIRMOD;
 908                                                 } else
 909                                                         mod |= FSERROR;
 910                                                 continue;
 911                                         } else if ((check_subdirectory(f, boot,
 912                                             &dirent) & FSERROR) == FSERROR) {
 913                                                 /*
 914                                                  * A subdirectory should have
 915                                                  * a dot (.) entry and a dot-dot
 916                                                  * (..) entry of ATTR_DIRECTORY,
 917                                                  * we will inspect further when
 918                                                  * traversing into it.
 919                                                  */
 920                                                 if (ask(1, "Remove")) {
 921                                                         *p = SLOT_DELETED;
 922                                                         mod |= THISMOD|FSDIRMOD;
 923                                                 } else
 924                                                         mod |= FSERROR;
 925                                                 continue;
 926                                         }
 927                                 }
 928
 929                                 /* create directory tree node */
 930                                 if (!(d = newDosDirEntry())) {
 931                                         perr("No space for directory");
 932                                         return FSFATAL;
 933                                 }
 934                                 memcpy(d, &dirent, sizeof(struct dosDirEntry));
 935                                 /* link it into the tree */
 936                                 dir->child = d;
 937
 938                                 /* Enter this directory into the todo list */
 939                                 if (!(n = newDirTodo())) {
 940                                         perr("No space for todo list");
 941                                         return FSFATAL;
 942                                 }
 943                                 n->next = pendingDirectories;
 944                                 n->dir = d;
 945                                 pendingDirectories = n;
 946                         } else {
 947                                 mod |= k = checksize(boot, fat, p, &dirent);
 948                                 if (k & FSDIRMOD)
 949                                         mod |= THISMOD;
 950                         }
 951                         boot->NumFiles++;
 952                 }
 953
 954                 if (!(boot->flags & FAT32) && !dir->parent)
 955                         break;
 956
 957                 if (mod & THISMOD) {
 958                         last *= 32;
 959                         if (lseek(f, off, SEEK_SET) != off
 960                             || write(f, buffer, last) != last) {
 961                                 perr("Unable to write directory");
 962                                 return FSFATAL;
 963                         }
 964                         mod &= ~THISMOD;
 965                 }
 966         } while ((cl = fat[cl].next) >= CLUST_FIRST && cl < boot->NumClusters);
 967         if (invlfn || vallfn)
 968                 mod |= removede(f, boot, fat,
 969                                 invlfn ? invlfn : vallfn, p,
 970                                 invlfn ? invcl : valcl, -1, 0,
 971                                 fullpath(dir), 1);
 972
 973         /* The root directory of non fat32 filesystems is in a special
 974          * area and may have been modified above without being written out.
 975          */
 976         if ((mod & FSDIRMOD) && !(boot->flags & FAT32) && !dir->parent) {
 977                 last *= 32;
 978                 if (lseek(f, off, SEEK_SET) != off
 979                     || write(f, buffer, last) != last) {
 980                         perr("Unable to write directory");
 981                         return FSFATAL;
 982                 }
 983                 mod &= ~THISMOD;
 984         }
 985         return mod & ~THISMOD;
 986 }
 987
 988 int
 989 handleDirTree(int dosfs, struct bootblock *boot, struct fatEntry *fat)
 990 {
 991         int mod;
 992
 993         mod = readDosDirSection(dosfs, boot, fat, rootDir);
 994         if (mod & FSFATAL)
 995                 return FSFATAL;
 996
 997         /*
 998          * process the directory todo list
 999          */
1000         while (pendingDirectories) {
1001                 struct dosDirEntry *dir = pendingDirectories->dir;
1002                 struct dirTodoNode *n = pendingDirectories->next;
1003
1004                 /*
1005                  * remove TODO entry now, the list might change during
1006                  * directory reads
1007                  */
1008                 freeDirTodo(pendingDirectories);
1009                 pendingDirectories = n;
1010
1011                 /*
1012                  * handle subdirectory
1013                  */
1014                 mod |= readDosDirSection(dosfs, boot, fat, dir);
1015                 if (mod & FSFATAL)
1016                         return FSFATAL;
1017         }
1018
1019         return mod;
1020 }
1021
1022 /*
1023  * Try to reconnect a FAT chain into dir
1024  */
1025 static u_char *lfbuf;
1026 static cl_t lfcl;
1027 static off_t lfoff;
1028
1029 int
1030 reconnect(int dosfs, struct bootblock *boot, struct fatEntry *fat, cl_t head)
1031 {
1032         struct dosDirEntry d;
1033         int len;
1034         u_char *p;
1035
1036         if (!ask(1, "Reconnect"))
1037                 return FSERROR;
1038
1039         if (!lostDir) {
1040                 for (lostDir = rootDir->child; lostDir; lostDir = lostDir->next) {
1041                         if (!strcmp(lostDir->name, LOSTDIR))
1042                                 break;
1043                 }
1044                 if (!lostDir) {         /* Create LOSTDIR?              XXX */
1045                         pwarn("No %s directory\n", LOSTDIR);
1046                         return FSERROR;
1047                 }
1048         }
1049         if (!lfbuf) {
1050                 lfbuf = malloc(boot->ClusterSize);
1051                 if (!lfbuf) {
1052                         perr("No space for buffer");
1053                         return FSFATAL;
1054                 }
1055                 p = NULL;
1056         } else
1057                 p = lfbuf;
1058         while (1) {
1059                 if (p)
1060                         for (; p < lfbuf + boot->ClusterSize; p += 32)
1061                                 if (*p == SLOT_EMPTY
1062                                     || *p == SLOT_DELETED)
1063                                         break;
1064                 if (p && p < lfbuf + boot->ClusterSize)
1065                         break;
1066                 lfcl = p ? fat[lfcl].next : lostDir->head;
1067                 if (lfcl < CLUST_FIRST || lfcl >= boot->NumClusters) {
1068                         /* Extend LOSTDIR?                              XXX */
1069                         pwarn("No space in %s\n", LOSTDIR);
1070                         lfcl = (lostDir->head < boot->NumClusters) ? lostDir->head : 0;
1071                         return FSERROR;
1072                 }
1073                 lfoff = (lfcl - CLUST_FIRST) * boot->ClusterSize
1074                     + boot->FirstCluster * boot->bpbBytesPerSec;
1075
1076                 if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
1077                     || (size_t)read(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
1078                         perr("could not read LOST.DIR");
1079                         return FSFATAL;
1080                 }
1081                 p = lfbuf;
1082         }
1083
1084         boot->NumFiles++;
1085         /* Ensure uniqueness of entry here!                             XXX */
1086         memset(&d, 0, sizeof d);
1087         /* worst case -1 = 4294967295, 10 digits */
1088         len = snprintf(d.name, sizeof(d.name), "%u", head);
1089         d.flags = 0;
1090         d.head = head;
1091         d.size = fat[head].length * boot->ClusterSize;
1092
1093         memcpy(p, d.name, len);
1094         memset(p + len, ' ', 11 - len);
1095         memset(p + 11, 0, 32 - 11);
1096         p[26] = (u_char)d.head;
1097         p[27] = (u_char)(d.head >> 8);
1098         if (boot->ClustMask == CLUST32_MASK) {
1099                 p[20] = (u_char)(d.head >> 16);
1100                 p[21] = (u_char)(d.head >> 24);
1101         }
1102         p[28] = (u_char)d.size;
1103         p[29] = (u_char)(d.size >> 8);
1104         p[30] = (u_char)(d.size >> 16);
1105         p[31] = (u_char)(d.size >> 24);
1106         fat[head].flags |= FAT_USED;
1107         if (lseek(dosfs, lfoff, SEEK_SET) != lfoff
1108             || (size_t)write(dosfs, lfbuf, boot->ClusterSize) != boot->ClusterSize) {
1109                 perr("could not write LOST.DIR");
1110                 return FSFATAL;
1111         }
1112         return FSDIRMOD;
1113 }
1114
1115 void
1116 finishlf(void)
1117 {
1118         if (lfbuf)
1119                 free(lfbuf);
1120         lfbuf = NULL;
1121 }