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