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