src/dir/salvage.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 #ifndef lint
  11 #endif
  12 /* This is the directory salvager.  It consists of two routines.  The first, DirOK, checks to see if the directory looks good.  If the directory does NOT look good, the approved procedure is to then call Salvage, which copies all the good entries from the damaged dir into a new directory. */
  13
  14 #include <afs/param.h>
  15 #include <sys/types.h>
  16 #include <errno.h>
  17 #ifdef AFS_NT40_ENV
  18 #include <winsock2.h>
  19 #else
  20 #include <netinet/in.h>
  21 #endif
  22
  23 #include "dir.h"
  24 #define printf  Log     /* To make it work with volume salvager */
  25
  26 /* This routine is called with one parameter, the id (the same thing that is passed to physio or the buffer package) of a directory to check.  It returns 1 if the directory looks good, and 0 otherwise. */
  27
  28 #define MAXENAME 256
  29
  30 struct DirEntry *GetBlob();
  31 struct PageHeader *DRead();
  32 extern afs_int32 DErrno;
  33 int NameBlobs(), Lookup(), Create(), MakeDir();
  34
  35 /* figure out how many pages in use in a directory, given ptr to its (locked) header */
  36 static ComputeUsedPages(dhp)
  37 register struct DirHeader *dhp; {
  38     register afs_int32 usedPages, i;
  39
  40     if (dhp->header.pgcount != 0) {
  41         /* new style */
  42         usedPages = ntohs(dhp->header.pgcount);
  43     }
  44     else {
  45         /* old style */
  46         usedPages = 0;
  47         for(i=0; i<MAXPAGES; i++) {
  48             if (dhp->alloMap[i] == EPP) {
  49                 usedPages = i;
  50                 break;
  51             }
  52         }
  53         if (usedPages == 0) usedPages = MAXPAGES;
  54     }
  55     return usedPages;
  56 }
  57
  58 /* returns true if something went wrong checking, or if dir is fine.  Returns
  59  * false if we *know* that the dir is bad.
  60  */
  61 int DirOK (file)
  62     char *file; {
  63     struct DirHeader *dhp;
  64     struct PageHeader *pp;
  65     struct DirEntry *ep;
  66     int i, j, k, up;
  67     int havedot = 0, havedotdot = 0;
  68     int usedPages, count, entry;
  69     char eaMap[BIGMAXPAGES*EPP/8];      /* Change eaSize initialization below, too. */
  70     int eaSize;
  71     afs_int32 entcount, maxents;
  72     unsigned short ne;
  73
  74     eaSize = BIGMAXPAGES*EPP/8;
  75
  76     /* Read the directory header */
  77     dhp = (struct DirHeader *) DRead (file, 0);
  78     if (!dhp) {
  79         /* if DErrno is 0, then we know that the read worked, but was short,
  80          * and the damage is permanent.  Otherwise, we got an I/O or programming
  81          * error.  Claim the dir is OK, but log something.
  82          */
  83         if (DErrno != 0) {
  84             printf("Could not read first page in directory (%d)\n", DErrno);
  85             Die("dirok1");
  86             return 1;
  87         }
  88         printf("First page in directory does not exist.\n");
  89         return 0;
  90     }
  91
  92     /* Check magic number for first page */
  93     if (dhp->header.tag != htons(1234)) {
  94         printf("Bad first pageheader magic number.\n");
  95         DRelease(dhp, 0);
  96         return 0;
  97     }
  98
  99     /* Verify that the number of free entries in each directory page
 100      * is within range (0-EPP). Also ensure directory is contiguous:
 101      * Once the first alloMap entry with EPP free entries is found,
 102      * the rest should match.
 103      */
 104     up = 0;  /* count of used pages if total pages < MAXPAGES */
 105     k  = 0;  /* found last page */
 106     for(i=0; i<MAXPAGES; i++) {
 107         j = dhp->alloMap[i];
 108
 109         /* Check if in range */
 110         if (i == 0) {
 111            if ((j < 0) || (j > EPP-(13+2))) {
 112               /* First page's dirheader uses 13 entries and at least
 113                * two must exist for "." and ".."
 114                */
 115               printf("The dir header alloc map for page %d is bad.\n", i);
 116               DRelease(dhp, 0);
 117               return 0;
 118            }
 119         } else {
 120            if ((j < 0) || (j > EPP)) {
 121               printf("The dir header alloc map for page %d is bad.\n", i);
 122               DRelease(dhp, 0);
 123               return 0;
 124            }
 125         }
 126
 127         /* Check if contiguous */
 128         if (k) {                      /* last page found */
 129            if (j != EPP) {               /* remaining entries must be EPP */
 130               printf("A partially-full page occurs in slot %d, after the dir end.\n", i);
 131               DRelease(dhp, 0);
 132               return 0;
 133            }
 134         } else if (j == EPP) {        /* is this the last page */
 135            k = 1;                        /* yes */
 136         } else {                      /* a used page */
 137            up++;                         /* keep count */
 138         }
 139     }
 140
 141     /* Compute number of used directory pages and max entries in all
 142     ** those pages, the value of 'up' must be less than pgcount. The above
 143     ** loop only checks the first MAXPAGES in a directory. An alloMap does
 144     ** not exists for pages between MAXPAGES and BIGMAXPAGES */
 145     usedPages = ComputeUsedPages(dhp);
 146     if (usedPages < up) {
 147        printf("Count of used directory pages does not match count in directory header\n");
 148        DRelease(dhp, 0);
 149        return 0;
 150     }
 151
 152     /* For each directory page, check the magic number in each page
 153      * header, and check that number of free entries (from freebitmap)
 154      * matches the count in the alloMap from directory header.
 155      */
 156     for (i=0; i<usedPages; i++) {
 157         /* Read the page header */
 158         pp = (struct PageHeader *) DRead(file, i);
 159         if (!pp) {
 160             DRelease(dhp, 0);
 161             if (DErrno != 0) {
 162                 /* couldn't read page, but not because it wasn't there permanently */
 163                 printf("Failed to read dir page %d (errno %d)\n", i, DErrno);
 164                 Die("dirok2");
 165                 return 1;
 166             }
 167             printf("Directory shorter than alloMap indicates (page %d)\n", i);
 168             return 0;
 169         }
 170
 171         /* check the tag field */
 172         if (pp->tag != htons(1234)) {
 173             printf("Directory page %d has a bad magic number.\n", i);
 174             DRelease(pp, 0);
 175             DRelease(dhp, 0);
 176             return 0;
 177         }
 178
 179         /* Count the number of entries allocated in this single
 180          * directory page using the freebitmap in the page header.
 181          */
 182         count = 0;
 183         for(j=0; j<EPP/8; j++) {
 184             k = pp->freebitmap[j];
 185             if (k & 0x80) count++;
 186             if (k & 0x40) count++;
 187             if (k & 0x20) count++;
 188             if (k & 0x10) count++;
 189             if (k & 0x08) count++;
 190             if (k & 0x04) count++;
 191             if (k & 0x02) count++;
 192             if (k & 0x01) count++;
 193         }
 194         count = EPP - count;          /* Change to count of free entries */
 195
 196         /* Now check that the count of free entries matches the count in the alloMap */
 197         if ( (i < MAXPAGES) && ((count & 0xff) != (dhp->alloMap[i] & 0xff)) ) {
 198            printf("Header alloMap count doesn't match count in freebitmap for page %d.\n", i);
 199            DRelease(pp, 0);
 200            DRelease(dhp, 0);
 201            return 0;
 202         }
 203
 204         DRelease(pp, 0);
 205     }
 206
 207     /* Initialize the in-memory freebit map for all pages. */
 208     for (i=0; i<eaSize; i++) {
 209        eaMap[i] = 0;
 210        if (i < usedPages*(EPP/8)) {
 211           if (i == 0) {
 212              eaMap[i] = 0xff;        /* A dir header uses first 13 entries */
 213           } else if (i == 1) {
 214              eaMap[i] = 0x1f;        /* A dir header uses first 13 entries */
 215           } else if ((i%8) == 0) {
 216              eaMap[i] = 0x01;        /* A page header uses only first entry */
 217           }
 218        }
 219     }
 220     maxents = usedPages * EPP;
 221
 222     /* Walk down all the hash lists, ensuring that each flag field has FFIRST
 223      * in it.  Mark the appropriate bits in the in-memory freebit map.
 224      * Check that the name is in the right hash bucket.
 225      * Also check for loops in the hash chain by counting the entries.
 226      */
 227     for (entcount=0,i=0; i<NHASHENT; i++) {
 228         for (entry = ntohs(dhp->hashTable[i]); entry; entry = ne) {
 229             /* Verify that the entry is within range */
 230             if (entry < 0 || entry >= maxents) {
 231                 printf("Out-of-range hash id %d in chain %d.\n", entry, i);
 232                 DRelease(dhp, 0);
 233                 return 0;
 234             }
 235
 236             /* Read the directory entry */
 237             DErrno = 0;
 238             ep = GetBlob(file, entry);
 239             if (!ep) {
 240                 if (DErrno != 0) {
 241                     /* something went wrong reading the page, but it wasn't
 242                      * really something wrong with the dir that we can fix.
 243                      */
 244                     printf("Could not get dir blob %d (errno %d)\n", entry, DErrno);
 245                     DRelease(dhp, 0);
 246                     Die("dirok3");
 247                 }
 248                 printf("Invalid hash id %d in chain %d.\n", entry, i);
 249                 DRelease(dhp, 0);
 250                 return 0;
 251             }
 252             ne = ntohs(ep->next);
 253
 254             /* There can't be more than maxents entries */
 255             if (++entcount >= maxents) {
 256                 printf("Directory's hash chain %d is circular.\n", i);
 257                 DRelease(ep, 0);
 258                 DRelease(dhp, 0);
 259                 return 0;
 260             }
 261
 262             /* A null name is no good */
 263             if (ep->name[0] == '\000') {
 264                 printf("Dir entry %x in chain %d has bogus (null) name.\n", ep, i);
 265                 DRelease(ep, 0);
 266                 DRelease(dhp, 0);
 267                 return 0;
 268             }
 269
 270             /* The entry flag better be FFIRST */
 271             if (ep->flag != FFIRST) {
 272                 printf("Dir entry %x in chain %d has bogus flag field.\n", ep, i);
 273                 DRelease(ep, 0);
 274                 DRelease(dhp, 0);
 275                 return 0;
 276             }
 277
 278             /* Check the size of the name */
 279             j = strlen(ep->name);
 280             if (j >= MAXENAME) {        /* MAXENAME counts the null */
 281                 printf("Dir entry %x in chain %d has too-long name.\n", ep, i);
 282                 DRelease(ep, 0);
 283                 DRelease(dhp, 0);
 284                 return 0;
 285             }
 286
 287             /* The name used up k directory entries, set the bit in our in-memory
 288              * freebitmap for each entry used by the name.
 289              */
 290             k = NameBlobs(ep->name);
 291             for (j=0; j<k; j++) {
 292                eaMap[(entry+j)>>3] |= (1<<((entry+j)&7));
 293             }
 294
 295             /* Hash the name and make sure it is in the correct name hash */
 296             if ((j=DirHash(ep->name)) != i) {
 297                 printf("Dir entry %x should be in hash bucket %d but IS in %d.\n", ep, j, i);
 298                 DRelease(ep, 0);
 299                 DRelease(dhp, 0);
 300                 return 0;
 301             }
 302
 303             /* Check that if this is entry 13 (the 1st entry), then name must be "." */
 304             if (entry == 13) {
 305                if (strcmp(ep->name,".") == 0) {
 306                   havedot = 1;
 307                } else {
 308                   printf("Dir entry %x, index 13 has name '%s' should be '.'\n",
 309                          ep, ep->name);
 310                   DRelease(ep, 0);
 311                   DRelease(dhp, 0);
 312                   return 0;
 313                }
 314             }
 315
 316             /* Check that if this is entry 14 (the 2nd entry), then name must be ".." */
 317             if (entry == 14) {
 318                if (strcmp(ep->name,"..") == 0) {
 319                   havedotdot = 1;
 320                } else {
 321                   printf("Dir entry %x, index 14 has name '%s' should be '..'\n",
 322                          ep, ep->name);
 323                   DRelease(ep, 0);
 324                   DRelease(dhp, 0);
 325                   return 0;
 326                }
 327             }
 328
 329             /* CHECK FOR DUPLICATE NAMES? */
 330
 331             DRelease(ep, 0);
 332         }
 333     }
 334
 335     /* Verify that we found '.' and '..' in the correct place */
 336     if (!havedot || !havedotdot) {
 337        printf("Directory entry '.' or '..' does not exist or is in the wrong index.\n");
 338        DRelease(dhp, 0);
 339        return 0;
 340     }
 341
 342     /* The in-memory freebit map has been computed.  Check that it
 343      * matches the one in the page header.
 344      * Note that if this matches, alloMap has already been checked against it.
 345      */
 346     for(i=0; i<usedPages; i++) {
 347         pp = DRead(file, i);
 348         if (!pp) {
 349             printf("Failed on second attempt to read dir page %d (errno %d)\n", i, DErrno);
 350             DRelease(dhp, 0);
 351             /* if DErrno is 0, then the dir is really bad, and we return dir *not* OK.
 352              * otherwise, we want to return true (1), meaning the dir isn't known
 353              * to be bad (we can't tell, since I/Os are failing.
 354              */
 355             if (DErrno != 0) Die("dirok4");
 356             else return 0;      /* dir is really shorter */
 357         }
 358
 359         count = i*(EPP/8);
 360         for (j=0; j<EPP/8; j++) {
 361            if (eaMap[count+j] != pp->freebitmap[j]) {
 362               printf("Entry freebitmap error, page %d, map offset %d, %x should be %x.\n",
 363                      i, j, pp->freebitmap[j], eaMap[count+j]);
 364               DRelease(pp, 0);
 365               DRelease(dhp, 0);
 366               return 0;
 367            }
 368         }
 369
 370         DRelease(pp, 0);
 371     }
 372
 373     /* Finally cleanup and return. */
 374     DRelease(dhp, 0);
 375     return 1;
 376 }
 377
 378 /* This routine is called with six parameters.  The first is the id of
 379  * the original, currently suspect, directory.  The second is the file
 380  * id of the place the salvager should place the new, fixed, directory.
 381  * The third and the fourth parameters are the vnode number and the
 382  * uniquifier of the currently suspect directory. The fifth and the
 383  * sixth parameters are the vnode number and the uniquifier of the
 384  * parent directory.
 385  */
 386 int DirSalvage (fromFile, toFile, vn, vu, pvn, pvu)
 387     char *fromFile, *toFile;
 388     afs_int32 vn, vu, pvn, pvu;
 389 {
 390     /* First do a MakeDir on the target. */
 391     afs_int32 dot[3], dotdot[3], lfid[3], code, usedPages;
 392     char tname[256];
 393     register int i;
 394     register char *tp, tc;
 395     struct DirHeader *dhp;
 396     struct DirEntry *ep;
 397     int entry;
 398
 399     bzero(dot, sizeof(dot));
 400     bzero(dotdot, sizeof(dotdot));
 401     dot[1]    = vn;
 402     dot[2]    = vu;
 403     dotdot[1] = pvn;
 404     dotdot[2] = pvu;
 405
 406     MakeDir(toFile, dot, dotdot);       /* Returns no error code. */
 407
 408     /* Find out how many pages are valid, using stupid heuristic since DRead
 409      * never returns null.
 410      */
 411     dhp = (struct DirHeader *) DRead(fromFile, 0);
 412     if (!dhp) {
 413         printf("Failed to read first page of fromDir!\n");
 414         /* if DErrno != 0, then our call failed and we should let our
 415          * caller know that there's something wrong with the new dir.  If not,
 416          * then we return here anyway, with an empty, but at least good, directory.
 417          */
 418         return DErrno;
 419     }
 420
 421     usedPages = ComputeUsedPages(dhp);
 422
 423     /* Finally, enumerate all the entries, doing a create on them. */
 424     for(i=0; i<NHASHENT; i++) {
 425         entry = ntohs(dhp->hashTable[i]);
 426         while(1) {
 427             if (!entry) break;
 428             if (entry < 0 || entry >= usedPages*EPP) {
 429                 printf("Warning: bogus hash table entry encountered, ignoring.\n");
 430                 break;
 431             }
 432             DErrno = 0;
 433             ep = GetBlob(fromFile, entry);
 434             if (!ep) {
 435                 if (DErrno) {
 436                     printf("can't continue down hash chain (entry %d, errno %d)\n",
 437                            entry, DErrno);
 438                     DRelease(dhp, 0);
 439                     return DErrno;
 440                 }
 441                 printf("Warning: bogus hash chain encountered, switching to next.\n");
 442                 break;
 443             }
 444             strncpy(tname, ep->name, MAXENAME);
 445             tname[MAXENAME-1] = '\000'; /* just in case */
 446             tp = tname;
 447
 448             entry = ntohs(ep->next);
 449
 450             if ((strcmp(tp,".") != 0) && (strcmp(tp,"..") != 0)) {
 451                lfid[1] = ntohl(ep->fid.vnode);
 452                lfid[2] = ntohl(ep->fid.vunique);
 453                code = Create(toFile, tname, lfid);
 454                if (code) {
 455                   printf("Create of %s returned code %d, skipping to next hash chain.\n", tname, code);
 456                   DRelease(ep, 0);
 457                   break;
 458                }
 459             }
 460             DRelease(ep, 0);
 461         }
 462     }
 463
 464     /* Clean up things. */
 465     DRelease(dhp, 0);
 466     return 0;
 467 }