src/budb/ol_verify.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 /* ol_verify - online database verification */
  11
  12 #include <afs/param.h>
  13 #include <stdio.h>
  14 #ifdef AFS_NT40_ENV
  15 #include <winsock2.h>
  16 #else
  17 #include <netinet/in.h>
  18 #include <netdb.h>
  19 #endif
  20 #include <afs/stds.h>
  21 #include <sys/types.h>
  22 #include <lock.h>
  23 #include <ubik.h>
  24 #include "database.h"
  25 #include "error_macros.h"
  26 #include "budb_errs.h"
  27 #include <afs/cellconfig.h>
  28 #include "afs/audit.h"
  29
  30 #undef min
  31 #undef max
  32
  33 /* notes
  34  * 1) volInfo structures refering to a volume of the same name are
  35  *      chained together, i.e. the volumes described differ in volid, partition
  36  *      etc. The structure at the head of this list (the sameNameChain) is
  37  *      treated specially. When a delete volInfo request is processed, heads
  38  *      are not deleted unless all other items on the sameNameChain are gone.
  39  *
  40  *      The result is that volInfo (head) structures may be present
  41  *      even if no tape structures refer to them. These structures are
  42  *      unreachable in a top-down tree walk.
  43  * TO DO
  44  * 1)   make the verify tolerant of errors. Want to get a summary statistic
  45  *      indicating how may dumps are lost and how many text blocks lost
  46  * 2)   Make the recreation instructions write out whatever is good. This
  47  *      is only for the off-line case.
  48  */
  49
  50 /* flags associated with each structure. These are set and checked in
  51  * the blockMap entries
  52  */
  53
  54 #define MAP_DUMPHASH            1       /* dump name hash checked */
  55 #define MAP_TAPEHASH            2       /* tape name hash checked */
  56 #define MAP_VOLHASH             4       /* volume name hash checked */
  57 #define MAP_IDHASH              8       /* dump id hash checked */
  58
  59 #define MAP_HASHES (MAP_DUMPHASH | MAP_TAPEHASH | MAP_VOLHASH | MAP_IDHASH)
  60
  61 #define MAP_FREE                0x10    /* item is free */
  62 #define MAP_RECREATE            0x20
  63 #define MAP_HTBLOCK             0x40    /* hash table block */
  64 #define MAP_TAPEONDUMP          0x100
  65 #define MAP_VOLFRAGONTAPE       0x200
  66 #define MAP_VOLFRAGONVOL        0x400
  67 #define MAP_VOLINFOONNAME       0x800
  68 #define MAP_VOLINFONAMEHEAD     0x1000
  69 #define MAP_TEXTBLOCK           0x2000  /* block of text */
  70 #define MAP_APPENDEDDUMP        0x4000
  71
  72 /* one blockMap for every block in the database. Each element of the entries
  73  *      array describes the status of a data structure/entry in that block
  74  */
  75
  76 struct blockMap
  77 {
  78     struct blockHeader header;          /* copy of the block header */
  79     char  free;                         /* on free list */
  80     int   nEntries;                     /* size of the entries arrays */
  81     afs_uint32 entries[1];                      /* describes each entry */
  82 };
  83
  84 /* status for verify call */
  85 struct dbStatus
  86 {
  87     char hostname[64];          /* host on which checked */
  88     afs_int32 status;           /* ok, not ok */
  89 };
  90
  91 int nBlocks;                    /* total number of blocks in db */
  92
  93 struct misc_hash_stats {                /* stats for hashing */
  94     int max;                            /* longest chain length */
  95     double avg;                         /* avg length */
  96     double std_dev;                     /* standard deviation of length */
  97 };
  98
  99 struct misc_data {
 100     int errors;                         /* errors encountered */
 101     int maxErrors;                      /* abort after this many errors */
 102     int nBlocks;                        /* number of database blocks */
 103     int  nDump, nTape, nVolInfo, nVolFrag; /* counts of each type */
 104     int  nVolName;                      /* volInfos w/ head==0 */
 105     int  maxVolsPerVolInfo;             /* maximum list lengths */
 106     int  maxVolsPerTape;
 107     int  maxVolsPerDump;
 108     int  maxVolInfosPerName;
 109     int  maxTapesPerDump;
 110     int  maxAppendsPerDump;
 111     int  freeLength[NBLOCKTYPES];       /* length of free lists */
 112     int  fullyFree[NBLOCKTYPES];        /* free blocks full of free entries */
 113     int  veryLongChain;                 /* length of chain to report */
 114     int  checkFragCount;                /* report fragment count errors */
 115     struct misc_hash_stats dumpName, dumpIden, tapeName, volName;
 116     FILE *recreate;                     /* stream for recreate instructions */
 117 } miscData;
 118 struct misc_data *misc;
 119
 120 struct blockMap **blockMap = 0;                 /* initial block map */
 121
 122 /* describes number of entries for each type of block */
 123
 124 int blockEntries[NBLOCKTYPES] =
 125 {
 126     0                    /* free_BLOCK */,
 127     NvolFragmentS,
 128     NvolInfoS,
 129     NtapeS,
 130     NdumpS,
 131     1,                  /* hashTable_BLOCK */
 132     1                   /* text block */
 133 };
 134
 135 int blockEntrySize[NBLOCKTYPES] =
 136 {
 137     0                                    /* free */,
 138     sizeof(((struct vfBlock *)0)->a[0]),
 139     sizeof(((struct viBlock *)0)->a[0]),
 140     sizeof(((struct tBlock *)0)->a[0]),
 141     sizeof(((struct dBlock *)0)->a[0]),
 142     0};
 143
 144 char *typeName[NBLOCKTYPES] =
 145 {
 146     "free",
 147     "volFragment",
 148     "volInfo",
 149     "tape",
 150     "dump",
 151     "hashTable"
 152 };
 153
 154 int hashBlockType[HT_MAX_FUNCTION+1] =
 155  {
 156     0,
 157     dump_BLOCK,
 158     dump_BLOCK,
 159     tape_BLOCK,
 160     volInfo_BLOCK
 161 };
 162
 163 /* Compatibility table for the bits in the blockMap. */
 164
 165 struct mapCompatability
 166 {
 167     short trigger;                      /* these bits trigger this element */
 168 } mapC[] =
 169 {
 170     MAP_FREE,
 171     MAP_HTBLOCK,
 172     MAP_DUMPHASH | MAP_IDHASH,
 173     MAP_TAPEHASH | MAP_TAPEONDUMP,
 174     MAP_VOLINFOONNAME,
 175     MAP_VOLINFONAMEHEAD | MAP_VOLHASH,
 176     MAP_VOLFRAGONTAPE | MAP_VOLFRAGONVOL,
 177     MAP_TEXTBLOCK
 178 };
 179
 180 /* no. of entries in the mapC array */
 181 int NMAPCs = (sizeof(mapC)/sizeof(mapC[0]));
 182
 183 /* for identifying stored textual information */
 184
 185 char *textName[TB_NUM] =
 186 {
 187     "Dump Schedule\n",
 188     "Volume Sets\n",
 189     "Tape Hosts\n"
 190 };
 191
 192 extern int sizeFunctions[];
 193 extern int nHTBuckets;
 194
 195 #define DBBAD BUDB_DATABASEINCONSISTENT
 196
 197 /* ------------------------------------
 198  * supporting routines
 199  * ------------------------------------
 200  */
 201
 202 /* BumpErrors
 203  *      increment the error count
 204  * exit:
 205  *      0 - continue
 206  *      1 - maximum errors exceeded
 207  */
 208
 209 afs_int32
 210 BumpErrors()
 211 {
 212     if ( ++miscData.errors >= miscData.maxErrors )
 213         return(1);
 214     else
 215         return(0);
 216 }
 217
 218 /* convertDiskAddress
 219  *      given a disk address, break it down into a block and entry index. These
 220  *      permit access to the block map information. The conversion process
 221  *      compares the supplied address with the alignment/type information
 222  *      stored in the block map.
 223  * exit:
 224  *      0 - ok
 225  *      BUDB_ADDR - address alignment checks failed
 226  */
 227
 228 afs_int32
 229 checkDiskAddress(address, type, blockIndexPtr, entryIndexPtr)
 230      unsigned long address;
 231      int type;
 232      int *blockIndexPtr;
 233      int *entryIndexPtr;
 234 {
 235     int index, offset;
 236
 237     if (blockIndexPtr) *blockIndexPtr = -1;
 238     if (entryIndexPtr) *entryIndexPtr = -1;
 239
 240     /* This is safest way to handle totally bogus addresses (eg 0x80001234). */
 241     if ( (address < sizeof(db.h)) || (address >= ntohl(db.h.eofPtr)) )
 242         return BUDB_ADDR;
 243
 244     address -= sizeof(db.h);
 245     index = address / BLOCKSIZE;
 246     offset = address - (index * BLOCKSIZE);
 247     if (offset % sizeof(afs_int32))                     /* alignment check */
 248         return BUDB_ADDR;
 249     if (offset && (type > 0) && (type <= MAX_STRUCTURE_BLOCK_TYPE))
 250     {
 251         offset -= sizeof(struct blockHeader);
 252         if ((offset < 0) || (offset % blockEntrySize[type]))
 253             return BUDB_ADDR;
 254         offset /= blockEntrySize[type];
 255         if (offset >= blockEntries[type])
 256             return BUDB_ADDR;
 257     }
 258     if (blockIndexPtr) *blockIndexPtr = index;
 259     if (entryIndexPtr) *entryIndexPtr = offset;
 260     return 0;
 261 }
 262
 263 /* ConvertDiskAddress
 264  *      given a disk address, break it down into a block and entry index. These
 265  *      permit access to the block map information. The conversion process
 266  *      compares the supplied address with the alignment/type information
 267  *      stored in the block map.
 268  * exit:
 269  *      0 - ok
 270  *      BUDB_ADDR - address alignment checks failed
 271  */
 272
 273 afs_int32
 274 ConvertDiskAddress(address, blockIndexPtr, entryIndexPtr)
 275      afs_uint32 address;
 276      int *blockIndexPtr;
 277      int *entryIndexPtr;
 278 {
 279     int index, type;
 280     afs_int32 code;
 281
 282     index = (address - sizeof(db.h)) / BLOCKSIZE;
 283     type = blockMap[index]->header.type;
 284
 285     code = checkDiskAddress(address, type, blockIndexPtr, entryIndexPtr);
 286     return (code);
 287 }
 288
 289 char *
 290 TypeName(index)
 291      int index;
 292 {
 293     static char error[16];
 294
 295     if ( (index < 0) || (index >= NBLOCKTYPES))
 296     {
 297         sprintf(error, "UNKNOWN_TYPE", index);
 298         return(error);
 299     }
 300     return(typeName[index]);
 301 }
 302
 303 getDumpID(ut, tapePtr, dumpID)
 304   struct tape *tapePtr;
 305   afs_int32 *dumpID;
 306 {
 307   struct dump d;
 308   afs_int32 code;
 309
 310   *dumpID = 0;
 311   code = dbread(ut, ntohl(tapePtr->dump), &d, sizeof(d));
 312   if (!code)
 313      *dumpID = ntohl(d.id);
 314 }
 315
 316 /* ------------------------------------
 317  * verification routines - structure specific
 318  * ------------------------------------
 319  */
 320
 321 /* verifyDumpEntry
 322  *      Follow the tapes entries hanging off of a dump and verify they belong
 323  *      to the dump.
 324  */
 325 afs_int32
 326 verifyDumpEntry( ut, dumpAddr, ai, ao, dumpPtr)
 327      struct ubik_trans *ut;
 328      afs_int32 dumpAddr;
 329      int ai, ao;
 330      struct dump *dumpPtr;
 331 {
 332     struct tape tape;
 333     afs_int32 tapeAddr, tapeCount=0, volCount=0, appDumpCount=0;
 334     afs_int32 appDumpAddr, appDumpIndex, appDumpOffset;
 335     struct dump appDump;
 336     int tapeIndex, tapeOffset, ccheck=1;
 337     afs_int32 code = 0, tcode;
 338     int dumpIndex, dumpOffset;
 339
 340     tcode = ConvertDiskAddress(dumpAddr, &dumpIndex, &dumpOffset);
 341     if (tcode)
 342     {
 343         Log("verifyDumpEntry: Invalid dump entry addr 0x%x\n", dumpAddr);
 344         if (BumpErrors()) ERROR(DBBAD);
 345         ERROR(0);
 346     }
 347
 348     /* Step though list of tapes hanging off of this dump */
 349     for (tapeAddr=ntohl(dumpPtr->firstTape); tapeAddr; tapeAddr=ntohl(tape.nextTape))
 350     {
 351         tcode = ConvertDiskAddress(tapeAddr, &tapeIndex, &tapeOffset);
 352         if (tcode)
 353         {
 354             Log("verifyDumpEntry: Invalid tape entry addr 0x%x (on DumpID %u)\n",
 355                 tapeAddr, ntohl(dumpPtr->id));
 356             Log("     Skipping remainder of tapes in dump\n");
 357             if (BumpErrors()) ERROR(DBBAD);
 358             ccheck = 0;
 359             break;
 360         }
 361
 362         tcode = dbread(ut, tapeAddr, &tape, sizeof(tape));
 363         if (tcode) ERROR(BUDB_IO);
 364
 365         if ( ntohl(tape.dump) != dumpAddr )
 366         {
 367             afs_int32 did;
 368
 369             getDumpID(ut, &tape, &did);
 370             Log("verifyDumpEntry: Tape '%s' (addr 0x%x) doesn't point to\n",
 371                 tape.name, tapeAddr);
 372             Log("     dumpID %u (addr 0x%x). Points to DumpID %u (addr 0x%x)\n",
 373                 ntohl(dumpPtr->id), dumpAddr, did, ntohl(tape.dump));
 374             if (BumpErrors()) return(DBBAD);
 375         }
 376
 377         /* Check if this tape entry has been examine already */
 378         if ( blockMap[tapeIndex]->entries[tapeOffset] & MAP_TAPEONDUMP )
 379         {
 380             Log("verifyDumpEntry: Tape '%s' (addr 0x%x) on multiple dumps\n",
 381                 tape.name, tapeAddr);
 382             if (BumpErrors()) return(DBBAD);
 383         }
 384         blockMap[tapeIndex]->entries[tapeOffset] |= MAP_TAPEONDUMP;
 385
 386         tapeCount++;
 387         volCount += ntohl(tape.nVolumes);
 388     }
 389
 390     if (ccheck && (ntohl(dumpPtr->nVolumes) != volCount))
 391     {
 392         Log("verifyDumpEntry: DumpID %u (addr 0x%x) volume count of %d is wrong (should be %d)\n",
 393             ntohl(dumpPtr->id), dumpAddr, ntohl(dumpPtr->nVolumes), volCount);
 394         if (BumpErrors()) return(DBBAD);
 395     }
 396
 397     if (volCount  > misc->maxVolsPerDump)  misc->maxVolsPerDump  = volCount;
 398     if (tapeCount > misc->maxTapesPerDump) misc->maxTapesPerDump = tapeCount;
 399
 400     /* If this is an initial dump, then step though list of appended dumps
 401      * hanging off of this dump.
 402      */
 403     if (ntohl(dumpPtr->initialDumpID) == 0) {
 404        for (appDumpAddr=ntohl(dumpPtr->appendedDumpChain); appDumpAddr;
 405             appDumpAddr=ntohl(appDump.appendedDumpChain)) {
 406
 407           tcode = ConvertDiskAddress(appDumpAddr, &appDumpIndex, &appDumpOffset);
 408           if (tcode) {
 409              Log("verifyDumpEntry: Invalid appended dump entry addr 0x%x\n", appDumpAddr);
 410              Log("Skipping remainder of appended dumps\n");
 411              if (BumpErrors()) ERROR(DBBAD);
 412              break;
 413           }
 414
 415           /* Read the appended dump in */
 416           tcode = dbread(ut, appDumpAddr, &appDump, sizeof(appDump));
 417           if (tcode) ERROR(BUDB_IO);
 418
 419           /* Verify that it points to the parent dump */
 420           if (ntohl(appDump.initialDumpID) != ntohl(dumpPtr->id)) {
 421              Log("verifyDumpEntry: DumpID %u (addr 0x%x) initial DumpID incorrect (is %u, should be %u)\n",
 422                  ntohl(appDump.id), appDumpAddr,
 423                  ntohl(appDump.initialDumpID), ntohl(dumpPtr->id));
 424              if (BumpErrors()) return(DBBAD);
 425           }
 426
 427           /* Check if this appended dump entry has been examined already */
 428           if ( blockMap[appDumpIndex]->entries[appDumpOffset] & MAP_APPENDEDDUMP ) {
 429              Log("verifyDumpEntry: DumpID %u (addr %u) is on multiple appended dump chains\n",
 430                  ntohl(appDump.id), appDumpAddr);
 431              Log("Skipping remainder of appended dumps\n");
 432              if (BumpErrors()) return(DBBAD);
 433              break;
 434           }
 435           blockMap[appDumpIndex]->entries[appDumpOffset] |= MAP_APPENDEDDUMP;
 436
 437           appDumpCount++;
 438        }
 439     }
 440
 441     if (appDumpCount > misc->maxAppendsPerDump) misc->maxAppendsPerDump = appDumpCount;
 442     misc->nDump++;
 443
 444 error_exit:
 445     return(code);
 446 }
 447
 448 /*
 449  * verifyTapeEntry
 450  *      Follw the volume fragments hanging off of a tape entry and verify
 451  *      they belong to the tape.
 452  */
 453 afs_int32
 454 verifyTapeEntry (ut, tapeAddr, ai, ao, tapePtr)
 455   struct ubik_trans *ut;
 456   afs_int32 tapeAddr;
 457   int ai, ao;
 458   struct tape *tapePtr;
 459 {
 460     int volCount = 0, ccheck=1;
 461     afs_int32 volFragAddr;
 462     int blockIndex, entryIndex;
 463     struct volFragment volFragment;
 464     afs_int32 code = 0, tcode;
 465
 466     for (volFragAddr=ntohl(tapePtr->firstVol);
 467          volFragAddr;
 468          volFragAddr=ntohl(volFragment.sameTapeChain))
 469     {
 470         tcode = ConvertDiskAddress(volFragAddr, &blockIndex, &entryIndex);
 471         if (tcode)
 472         {
 473             afs_int32 did;
 474
 475             getDumpID(ut, tapePtr, &did);
 476             Log("verifyTapeEntry: Invalid volFrag addr 0x%x (on tape '%s' DumpID %u)\n",
 477                 volFragAddr, tapePtr->name, did);
 478             Log("     Skipping remainder of volumes on tape\n");
 479             if (BumpErrors()) ERROR(DBBAD);
 480             ccheck = 0;
 481             break;
 482         }
 483
 484         tcode = dbread (ut, volFragAddr, &volFragment, sizeof(volFragment));
 485         if (tcode) ERROR(tcode);
 486
 487         if ( ntohl(volFragment.tape) != tapeAddr )
 488         {
 489             afs_int32 did;
 490
 491             getDumpID(ut, tapePtr, &did);
 492             Log("verifyTapeEntry: VolFrag (addr 0x%x) doesn't point to \n",
 493                 volFragAddr);
 494             Log ("     tape '%s' DumpID %u (addr 0x%x). Points to addr 0x%x\n",
 495                  tapePtr->name, did, tapeAddr, ntohl(volFragment.tape));
 496             if (BumpErrors()) ERROR(DBBAD);
 497         }
 498
 499         /* Has this volume fragment already been examined */
 500         if ( blockMap[blockIndex]->entries[entryIndex] & MAP_VOLFRAGONTAPE )
 501         {
 502             Log("verifyTapeEntry: VolFrag (addr %d) on multiple tapes\n",
 503                 volFragAddr);
 504             if (BumpErrors()) ERROR(DBBAD);
 505         }
 506         blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLFRAGONTAPE;
 507
 508         volCount++;
 509     }
 510
 511     /* now check computed vs. recorded volume counts */
 512     if (ccheck && (ntohl(tapePtr->nVolumes) != volCount))
 513     {
 514         afs_int32 did;
 515
 516         getDumpID(ut, tapePtr, &did);
 517         Log("verifyTapeEntry: Tape '%s' DumpID %u (addr 0x%x) volFrag count of %d is wrong (should be %d)\n",
 518             tapePtr->name, did, tapeAddr, ntohl(tapePtr->nVolumes), volCount);
 519         if (BumpErrors()) ERROR(DBBAD);
 520     }
 521
 522     if (volCount > misc->maxVolsPerTape) misc->maxVolsPerTape = volCount;
 523     misc->nTape++;
 524
 525 error_exit:
 526     return(code);
 527 }
 528
 529 /*
 530  * verifyVolFragEntry
 531  *      volume fragments are the lowest leaf describing a dump (nothing hangs off of it).
 532  *      So no check is done agaist it.
 533  */
 534 afs_int32
 535 verifyVolFragEntry (ut, va, ai, ao, v)
 536      struct ubik_trans *ut;
 537      afs_int32 va;
 538      int ai, ao;
 539      struct volFragment *v;
 540 {
 541     misc->nVolFrag++;
 542     return 0;
 543 }
 544
 545 /* verifyVolInfoEntry
 546  *      Follow the volume fragments hanging off of a volinfo structure and
 547  *      verify they belong to the volinfo structure.
 548  *      If the volinfo structure is at the head of the same name chain, then
 549  *      also verify all entries are also on the chain.
 550  */
 551 afs_int32
 552 verifyVolInfoEntry (ut, volInfoAddr, ai, ao, volInfo)
 553      struct ubik_trans *ut;
 554      afs_int32 volInfoAddr;
 555      int ai, ao;
 556      struct volInfo *volInfo;
 557 {
 558     int volCount = 0, ccheck=1;
 559     int nFrags;
 560     afs_int32 volFragAddr;
 561     int blockIndex, entryIndex, bindex, eindex;
 562     struct volFragment volFragment;
 563     afs_int32 code = 0, tcode;
 564
 565     /* check each fragment attached to this volinfo structure */
 566     for (volFragAddr=ntohl(volInfo->firstFragment);     volFragAddr;
 567          volFragAddr=ntohl(volFragment.sameNameChain))
 568     {
 569         tcode = ConvertDiskAddress (volFragAddr, &blockIndex, &entryIndex);
 570         if (tcode)
 571         {
 572             Log("verifyVolInfoEntry: Invalid volFrag entry addr 0x%x (on volume '%s')\n",
 573                 volFragAddr, volInfo->name);
 574             Log("     Skipping remainder of volumes on tape\n");
 575             if (BumpErrors()) ERROR(DBBAD);
 576             ccheck = 0;
 577             break;
 578         }
 579
 580         tcode = dbread(ut, volFragAddr, &volFragment, sizeof(volFragment));
 581         if (tcode) ERROR(tcode);
 582
 583         if ( ntohl(volFragment.vol) != volInfoAddr )
 584         {
 585             Log("verifyVolInfoEntry: volFrag (addr 0x%x) doesn't point to \n",
 586                 volFragAddr);
 587             Log("     volInfo '%s' (addr 0x%x). Points to addr 0x%x\n",
 588                 volInfo->name, volInfoAddr, ntohl(volFragment.vol));
 589             if (BumpErrors()) ERROR(DBBAD);
 590         }
 591
 592         /* volume fragment already on a volinfo chain? */
 593         if ( blockMap[blockIndex]->entries[entryIndex] & MAP_VOLFRAGONVOL )
 594         {
 595             Log("verifyVolInfoEntry: VolFrag (addr %d) on multiple volInfo chains\n",
 596                 volFragAddr);
 597             if (BumpErrors()) ERROR(DBBAD);
 598         }
 599         blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLFRAGONVOL;
 600
 601         volCount++;
 602     }
 603
 604     /* check computed vs. recorded number of fragments */
 605     if (ccheck && misc->checkFragCount && (ntohl(volInfo->nFrags) != volCount))
 606     {
 607         Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) volFrag count of %d is wrong (should be %d)\n",
 608             volInfo->name, volInfoAddr, ntohl(volInfo->nFrags), volCount);
 609         if (BumpErrors()) ERROR(DBBAD);
 610     }
 611
 612     if (volCount > misc->maxVolsPerVolInfo) misc->maxVolsPerVolInfo = volCount;
 613
 614     /* Check that all volInfo structures with same name point to the same
 615      * head. If sameNameHead == 0, this is the head structure so we check,
 616      * otherwise ignore
 617      */
 618     if (volInfo->sameNameHead == 0)
 619     { /*i*/
 620         int viCount = 1;                /* count this one */
 621         struct volInfo tvi;
 622         afs_int32 tviAddr;
 623
 624         for (tviAddr=ntohl(volInfo->sameNameChain); tviAddr; tviAddr = ntohl(tvi.sameNameChain))
 625         {
 626             viCount++;
 627             tcode = ConvertDiskAddress (tviAddr, &blockIndex, &entryIndex);
 628             if (tcode)
 629             {
 630                 Log("verifyVolInfoEntry: Invalid volInfo entry %s addr 0x%x\n",
 631                     volInfo->name, tviAddr);
 632                 Log("     Skipping remainder of volumes on same name chain\n");
 633                 if (BumpErrors()) ERROR(DBBAD);
 634                 code = 0;
 635                 break;
 636             }
 637
 638             tcode = dbread(ut, tviAddr, &tvi, sizeof(tvi));
 639             if (tcode) ERROR(tcode);
 640
 641             if ( ntohl(tvi.sameNameHead) != volInfoAddr)
 642             {
 643                 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) doesn't point to \n",
 644                     volInfo->name, tviAddr);
 645                 Log("     head of sameName volInfo (addr 0x%x). Points to addr 0x%x\n",
 646                     volInfoAddr, ntohl(tvi.sameNameHead));
 647                 if (BumpErrors()) ERROR(DBBAD);
 648             }
 649
 650             if (blockMap[blockIndex]->entries[entryIndex] & MAP_VOLINFOONNAME)
 651             {
 652                 Log("verifyVolInfoEntry: VolInfo (addr 0x%x) on multiple same name chains\n",
 653                     tviAddr);
 654                 if (BumpErrors()) ERROR(DBBAD);
 655             }
 656             blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLINFOONNAME;
 657         }
 658
 659         /* select the passed in structure flags */
 660         if ( blockMap[ai]->entries[ao] & MAP_VOLINFONAMEHEAD)
 661         {
 662             Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) is name head multiple times\n",
 663                 volInfo->name, volInfoAddr);
 664             if (BumpErrors()) ERROR(DBBAD);
 665         }
 666         blockMap[ai]->entries[ao] |= MAP_VOLINFONAMEHEAD;
 667
 668         if (viCount > misc->maxVolInfosPerName) misc->maxVolInfosPerName = viCount;
 669         misc->nVolName++;
 670     } /*i*/
 671
 672     misc->nVolInfo++;
 673
 674 error_exit:
 675     return(code);
 676 }
 677
 678
 679 /* ------------------------------------
 680  * verification routines - general
 681  * ------------------------------------
 682  */
 683
 684 /* verifyBlocks
 685  *     Read each block header of every 2K block and remember it in our global
 686  *     blockMap array. Also check that the type of block is good.
 687  */
 688 afs_int32
 689 verifyBlocks(ut)
 690      struct ubik_trans *ut;
 691 {
 692     struct block block;
 693     int blocktype;
 694     afs_int32 blockAddr;
 695     struct blockMap *ablockMap = 0;
 696     int bmsize;
 697     int i;
 698     afs_int32 code = 0, tcode;
 699
 700     /* Remember every header of every block in the database */
 701     for (i=0; i<nBlocks; i++)
 702     {
 703         /* To avoid the call from timing out, do a poll every 256 blocks */
 704
 705         /* read the block header */
 706         blockAddr = sizeof(db.h) + (i * BLOCKSIZE);
 707         tcode = dbread(ut, blockAddr, (char *) &block.h, sizeof(block.h));
 708         if (tcode) ERROR(tcode);
 709
 710         /* check the block type */
 711         blocktype = block.h.type;                       /* char */
 712         if ( (blocktype < 0) || (blocktype >= NBLOCKTYPES) )
 713         {
 714             Log("Block (index %d addr %d) has invalid type of %d\n", i, blockAddr, blocktype);
 715             ERROR(BUDB_BLOCKTYPE);
 716         }
 717
 718         /* allocate the block map memory */
 719         bmsize = sizeof(*ablockMap) + (blockEntries[blocktype]-1) * sizeof(ablockMap->entries[0]);
 720         ablockMap = (struct blockMap *) malloc(bmsize);
 721         if (!ablockMap) ERROR(BUDB_NOMEM);
 722         bzero(ablockMap, bmsize);
 723
 724         ablockMap->nEntries = blockEntries[blocktype];
 725
 726         /* save the block header in the block map */
 727         bcopy(&block.h, &ablockMap->header, sizeof(ablockMap->header));
 728         blockMap[i] = ablockMap;
 729     }
 730
 731 error_exit:
 732     return(code);
 733 }
 734
 735 int minvols, maxvols, ttlvols;
 736
 737 /* verifyHashTableBlock
 738  *      Take a 2K hash table block and traverse its entries. Make sure each entry
 739  *      is of the correct type for the hash table, is hashed into the correct
 740  *      entry and is not threaded on multiple lists.
 741  */
 742 afs_int32
 743 verifyHashTableBlock(ut, mhtPtr, htBlockPtr, old, length, index, mapBit)
 744      struct ubik_trans *ut;
 745      struct memoryHashTable *mhtPtr;
 746      struct htBlock *htBlockPtr;
 747      int old;
 748      afs_int32 length;                       /* size of whole hash table */
 749      int index;                         /* base index of this block */
 750      int mapBit;
 751 {
 752     int type;                           /* hash table type */
 753     int entrySize;                      /* hashed entry size */
 754     int blockType;                      /* block type for this hash table */
 755     int blockIndex, entryIndex;
 756     char entry[sizeof(struct block)];
 757     dbadr entryAddr;
 758     int hash;                           /* calculated hash value for entry */
 759     int i, count;
 760     afs_int32 code = 0, tcode;
 761
 762     type = ntohl(mhtPtr->ht->functionType);
 763     entrySize = sizeFunctions[type];
 764     blockType = hashBlockType[type];
 765
 766     /* step through this hash table block, being careful to stop
 767      * before the end of the overall hash table
 768      */
 769
 770     for ( i = 0; (i < nHTBuckets) && (index < length); i++, index++ )
 771     { /*f*/
 772         entryAddr = ntohl(htBlockPtr->bucket[i]);
 773
 774         /* if this is the old hash table, all entries below the progress mark
 775          * should have been moved to the new hash table
 776          */
 777         if (old && (index < mhtPtr->progress) && entryAddr)
 778         {
 779             Log("Old hash table not empty (entry %d) below progress (%d)\n",
 780                 i,  mhtPtr->progress);
 781             if (BumpErrors()) ERROR(DBBAD);
 782         }
 783
 784         /* now walk down the chain of each bucket */
 785         for (count=0; entryAddr; count++)
 786         { /*w*/
 787             tcode = ConvertDiskAddress(entryAddr, &blockIndex, &entryIndex);
 788             if (tcode)
 789             {
 790                 Log("verifyHashTableBlock: Invalid hash table chain addr 0x%x\n", entryAddr);
 791                 Log("     Skipping remainder of bucket %d\n", index);
 792                 if (BumpErrors()) ERROR(DBBAD);
 793                 code = 0;
 794                 break;
 795             }
 796
 797             if (blockMap[blockIndex]->header.type != blockType)
 798             {
 799                 Log("Hash table chain (block index %d) incorrect\n", blockIndex);
 800                 Log("     Table type %d traverses block type %d\n",
 801                     blockType, blockMap[blockIndex]->header.type);
 802                 Log("     Skipping remainder of bucket %d\n", index);
 803                 if (BumpErrors()) ERROR(DBBAD);
 804                 break;
 805             }
 806
 807             if ( dbread(ut, entryAddr, &entry[0], entrySize) )
 808                 ERROR(DBBAD);
 809
 810             hash = ht_HashEntry(mhtPtr, &entry[0]) % length;
 811             if (hash != index)          /* if it hashed to some other place */
 812             {
 813                 Log("Entry (addr 0x%x) bucket %d, should be hashed into bucket %d\n",
 814                     entryAddr, index, hash);
 815                 if (BumpErrors()) ERROR(DBBAD);
 816             }
 817
 818             /* check if entry has been examined */
 819             if (blockMap[blockIndex]->entries[entryIndex] & mapBit)
 820             {
 821                 Log("Entry (addr 0x%x) multiply referenced\n", entryAddr);
 822                 if (BumpErrors()) ERROR(DBBAD);
 823             }
 824             blockMap[blockIndex]->entries[entryIndex] |= mapBit;
 825
 826             entryAddr = ntohl( *((dbadr *)(entry + mhtPtr->threadOffset)));
 827         } /*w*/
 828
 829         /* Log("Bucket %4d contains %d entries\n", index+1, count); */
 830         ttlvols += count;
 831         if (count < minvols) minvols = count;
 832         if (count > maxvols) maxvols = count;
 833     } /*f*/
 834
 835 error_exit:
 836     return(code);
 837 }
 838
 839 /* verifyHashTable
 840  *      Read each 2K block a hashtable has (both its old hastable and
 841  *      new hashtable) and verify the block has not been read before.
 842  *      Will also make call to verify entries within each 2K block of
 843  *      the hash table.
 844  */
 845 afs_int32
 846 verifyHashTable(ut, mhtPtr, mapBit)
 847      struct ubik_trans *ut;
 848      struct memoryHashTable *mhtPtr;
 849      int mapBit;
 850 {
 851     struct hashTable *htPtr = mhtPtr->ht;
 852
 853     struct htBlock hashTableBlock;
 854     int tableLength;                            /* # entries */
 855     int hashblocks;                             /* # blocks */
 856     dbadr tableAddr;                            /* disk addr of hash block */
 857     int blockIndex, entryIndex;
 858     int old;
 859     int i;
 860     afs_int32 code = 0, tcode;
 861
 862     extern int nHTBuckets;                      /* # buckets in a hash table */
 863
 864     LogDebug(4, "Htable: length %d oldlength %d progress %d\n",
 865         mhtPtr->length, mhtPtr->oldLength, mhtPtr->progress);
 866
 867     /* check both old and current tables */
 868     for ( old = 0; old <= 1; old++ )
 869     { /*fo*/
 870         tableLength = (old ? mhtPtr->oldLength      : mhtPtr->length);
 871         if (tableLength == 0) continue;
 872         tableAddr   = (old ? ntohl(htPtr->oldTable) : ntohl(htPtr->table));
 873         minvols = 999999;
 874         maxvols = ttlvols = 0;
 875
 876         /* follow the chain of hashtable blocks - avoid infinite loops */
 877         hashblocks = ((tableLength-1)/nHTBuckets)+1;   /* numb of 2K hashtable blocks */
 878         for (i=0; (tableAddr && (i<hashblocks+5)); i++)
 879         {
 880             tcode = ConvertDiskAddress(tableAddr, &blockIndex, &entryIndex);
 881             if (tcode)
 882             {
 883                 Log("verifyHashTable: Invalid hash table chain addr 0x%x\n", tableAddr);
 884                 Log("     Skipping remainder of hash table chain\n");
 885                 if (BumpErrors()) return(DBBAD);
 886                 code = 0;
 887                 break;
 888             }
 889
 890             if ( blockMap[blockIndex]->header.type != hashTable_BLOCK )
 891             {
 892                 Log("Hashtable block (index %d addr 0x%x) hashtype %d - type %d, expected type %d\n",
 893                     i+1, tableAddr, ntohl(htPtr->functionType),
 894                     blockMap[blockIndex]->header.type, hashTable_BLOCK);
 895                 Log("     Skipping remainder of hash table chain\n");
 896                 if (BumpErrors()) ERROR(BUDB_BLOCKTYPE);
 897                 break;
 898             }
 899
 900             /* check if we've examined this block before */
 901             /* mark this (hash table) block as examined  */
 902             if (blockMap[blockIndex]->entries[entryIndex] & MAP_HTBLOCK)
 903             {
 904                 Log("Hash table block (index %d addr 0x%x) multiple ref\n", i+1, tableAddr);
 905                 if (BumpErrors()) ERROR(BUDB_DATABASEINCONSISTENT);
 906             }
 907             blockMap[blockIndex]->entries[entryIndex] |= MAP_HTBLOCK;
 908
 909             /* Read the actual hash table block */
 910             tcode = dbread(ut, tableAddr, &hashTableBlock, sizeof(hashTableBlock));
 911             if (tcode) ERROR(tcode);
 912
 913             /* Verify its entries */
 914             tcode = verifyHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
 915                                         tableLength, (i*nHTBuckets), mapBit);
 916             if (tcode) ERROR(tcode);
 917
 918             tableAddr = ntohl(hashTableBlock.h.next);
 919         }
 920
 921         /* Verify numb hash blocks is as it says */
 922         if (i != hashblocks)
 923         {
 924             Log("Incorrect number of hash chain blocks: %d (expected %d), hashtype %d\n",
 925                 i, hashblocks, ntohl(htPtr->functionType));
 926             if (BumpErrors()) ERROR(BUDB_DATABASEINCONSISTENT);
 927         }
 928
 929         if (ttlvols)
 930             Log("%d entries; %u buckets; min = %d; max = %d\n",
 931                 ttlvols, tableLength, minvols, maxvols);
 932     } /*fo*/
 933
 934 error_exit:
 935     return(code);
 936 }
 937
 938 /* verifyEntryChains
 939  *      do a linear walk of all the blocks. Check each block of structures
 940  *      to see if the actual free matches the recorded free. Also check
 941  *      the integrity of each allocated structure.
 942  */
 943 afs_int32
 944 verifyEntryChains(ut)
 945      struct ubik_trans *ut;
 946 {
 947     afs_int32 code;
 948     afs_int32 offset;
 949     int blockIndex, entryIndex;
 950     char entry[sizeof(struct block)];
 951     int entrySize;
 952     int type;
 953     int nFree;
 954
 955     static afs_int32 (*checkEntry[NBLOCKTYPES])()
 956         = {     0,                              /* free block */
 957                 verifyVolFragEntry,
 958                 verifyVolInfoEntry,
 959                 verifyTapeEntry,
 960                 verifyDumpEntry,
 961                 0                               /* text block */
 962           };
 963
 964     for (blockIndex=0; blockIndex<nBlocks; blockIndex++)
 965     { /*f*/
 966         /* ignore non-structure or blocks with invalid type */
 967         type = blockMap[blockIndex]->header.type;
 968         if ((type <= 0) || (type > MAX_STRUCTURE_BLOCK_TYPE))
 969             continue;
 970
 971         entrySize = blockEntrySize[type];
 972         nFree = 0;
 973
 974         for (entryIndex=0; entryIndex<blockMap[blockIndex]->nEntries; entryIndex++)
 975         { /*f*/
 976             offset = sizeof(db.h) + (blockIndex * BLOCKSIZE) +
 977                      sizeof(struct blockHeader) + (entryIndex * entrySize);
 978             if ( dbread(ut, offset, &entry[0], entrySize) )
 979                 return BUDB_IO;
 980
 981             /* check if entry is free by looking at the first "afs_int32" of the structure */
 982             if ( *((afs_int32 *)&entry[0]) == 0 )                          /* zero is free */
 983             {
 984                 /* Is it on any hash chain? */
 985                 if ( blockMap[blockIndex]->entries[entryIndex] & MAP_HASHES )
 986                 {
 987                     Log("Entry: blockindex %d, entryindex %d - marked free but hashed 0x%x\n",
 988                         blockIndex, entryIndex, blockMap[blockIndex]->entries[entryIndex]);
 989                     if (BumpErrors()) return DBBAD;
 990                 }
 991
 992                 blockMap[blockIndex]->entries[entryIndex] |= MAP_FREE;
 993                 nFree++;
 994             }
 995             else
 996             {
 997                 /* check the entry itself for consistency */
 998                 code = (*(checkEntry[type]))(ut, offset, blockIndex, entryIndex, &entry[0]);
 999                 if (code) return code;
1000             }
1001         } /*f*/
1002
1003         /* check computed free with recorded free entries */
1004         if ( nFree != ntohs(blockMap[blockIndex]->header.nFree) )
1005         {
1006             Log("Block (index %d) free count %d has %d free structs\n",
1007                 blockIndex, ntohs(blockMap[blockIndex]->header.nFree), nFree);
1008             if (BumpErrors()) return DBBAD;
1009         }
1010     } /*f*/
1011
1012     return 0;
1013 }
1014
1015
1016 afs_int32
1017 verifyFreeLists()
1018 {
1019     int i;
1020     afs_int32 addr;
1021     int blockIndex, entryIndex;
1022     int nFree;
1023     afs_int32 code;
1024
1025     /* for each free list */
1026     for (i=0; i<NBLOCKTYPES; i++)
1027     {
1028         misc->fullyFree[i] = misc->freeLength[i] = 0;
1029
1030         for (addr=ntohl(db.h.freePtrs[i]); addr; addr=ntohl(blockMap[blockIndex]->header.next))
1031         {
1032             misc->freeLength[i]++;
1033
1034             code = ConvertDiskAddress (addr, &blockIndex, &entryIndex);
1035             if (code || (entryIndex != 0))
1036             {
1037                 Log("verifyFreeLists: Invalid free chain addr 0x%x in %s free chain\n",
1038                     addr, TypeName(i));
1039                 Log("     Skipping remainder of free chain\n");
1040                 if (BumpErrors()) return(DBBAD);
1041                 code = 0;
1042                 break;
1043             }
1044
1045             /* check block type */
1046             if (blockMap[blockIndex]->header.type != i)
1047             {
1048                 Log("verifyFreeLists: Found %s type in %s free chain\n",
1049                     TypeName(blockMap[blockIndex]->header.type), TypeName(i), addr);
1050                 if (BumpErrors()) return(DBBAD);
1051             }
1052
1053             /* If entire block isn't free, check if count of free entries is ok */
1054             nFree = ntohs(blockMap[blockIndex]->header.nFree);
1055             if (i != free_BLOCK)
1056             {
1057                 if ((nFree <= 0) || (nFree > blockEntries[i]))
1058                 {
1059                     Log ("verifyFreeLists: Illegal free count %d on %s free chain\n",
1060                          nFree, TypeName(i));
1061                     if (BumpErrors()) return(DBBAD);
1062                 }
1063                 else if (nFree == blockEntries[i])
1064                 {
1065                     misc->fullyFree[i]++;
1066                 }
1067             }
1068
1069             /* Check if already examined the block */
1070             if (blockMap[blockIndex]->free)
1071             {
1072                 Log("verifyFreeLists: %s free chain block at addr 0x%x multiply threaded\n",
1073                     TypeName(i), addr);
1074                 if (BumpErrors()) return DBBAD;
1075             }
1076             blockMap[blockIndex]->free++;
1077         }
1078     }
1079
1080     return 0;
1081 }
1082
1083 /* verifyMapBits
1084  *      Examines each entry to make sure it was traversed appropriately by
1085  *      checking the bits for compatibility.
1086  */
1087 afs_int32
1088 verifyMapBits()
1089 {
1090     int blockIndex, entryIndex, i, entrySize, type, bits;
1091     afs_int32 offset;
1092
1093     for (blockIndex=0; blockIndex<nBlocks; blockIndex++)
1094     {
1095         /* If no entries in this block, then the block should be marked free */
1096         if ((blockMap[blockIndex]->nEntries == 0) && !blockMap[blockIndex]->free)
1097         {
1098             Log("verifyMapBits: Orphan free block (index %d)\n", blockIndex);
1099             if (BumpErrors()) return DBBAD;
1100         }
1101
1102         /* check each entry */
1103         for (entryIndex=0; entryIndex<blockMap[blockIndex]->nEntries; entryIndex++)
1104         { /*f*/
1105             if ((entryIndex%1024) == 0) IOMGR_Poll();
1106
1107             bits = blockMap[blockIndex]->entries[entryIndex];
1108
1109             for (i=0; i<NMAPCs; i++)
1110                 if ((bits & mapC[i].trigger) == mapC[i].trigger) break;
1111
1112             if (i >= NMAPCs)
1113             {
1114                 char logstr[256];
1115
1116                 type = blockMap[blockIndex]->header.type;
1117                 entrySize = blockEntrySize[type];
1118                 offset = sizeof(db.h) + (blockIndex * BLOCKSIZE) +
1119                          sizeof(struct blockHeader) + (entryIndex * entrySize);
1120
1121                 sprintf(logstr, "%s entry Block %d, Entry %d, (addr 0x%x)",
1122                         TypeName(type), blockIndex, entryIndex, offset);
1123
1124                 if (!bits)                    strcat(logstr, ": An orphaned entry");
1125                 if (bits & MAP_FREE)          strcat(logstr, ": A valid free block");
1126                 if (bits & MAP_HTBLOCK)       strcat(logstr, ": A valid hash-table block");
1127                 if (bits & MAP_TEXTBLOCK)     strcat(logstr, ": A valid text block");
1128                 if (bits & (MAP_DUMPHASH | MAP_IDHASH))
1129                 {
1130                     if      (!(bits & MAP_DUMPHASH))
1131                         strcat(logstr, ": A dump not on dump-name hash-chain");
1132                     else if (!(bits & MAP_IDHASH))
1133                         strcat(logstr, ": A dump not on dump-id hash-chain");
1134                     else
1135                         strcat(logstr, ": A valid dump entry");
1136                 }
1137                 if (bits & (MAP_TAPEHASH | MAP_TAPEONDUMP))
1138                 {
1139                     if (!(bits & MAP_TAPEHASH))
1140                         strcat(logstr, ": A tape not on tape-name hash-chain");
1141                     else if (!(bits & MAP_TAPEONDUMP))
1142                         strcat(logstr, ": A tape not associated with a dump");
1143                     else
1144                         strcat(logstr, ": A valid tape entry");
1145                 }
1146                 if (bits & MAP_VOLINFOONNAME)
1147                     strcat(logstr, ": A valid volInfo on a volume-name chain");
1148                 if (bits & (MAP_VOLINFONAMEHEAD | MAP_VOLHASH))
1149                 {
1150                     if (!(bits & MAP_VOLINFONAMEHEAD))
1151                         strcat(logstr, ": A volInfo not the head of a volume-name hash-chain");
1152                     else if (!(bits & MAP_VOLHASH))
1153                         strcat(logstr, ": A volInfo not on volume-name hash-chain");
1154                     else
1155                         strcat(logstr, ": A valid volInfo in volume-name hash-chain");
1156                 }
1157                 if (bits & (MAP_VOLFRAGONTAPE | MAP_VOLFRAGONVOL))
1158                 {
1159                     if (!(bits & MAP_VOLFRAGONTAPE))
1160                         strcat(logstr, ": A volFrag not associated with a tape");
1161                     else if (!(bits & MAP_VOLFRAGONVOL))
1162                         strcat(logstr, ": A volFrag not associated with a volume");
1163                     else
1164                         strcat(logstr, ": A valid volFrag entry");
1165                 }
1166                 Log("%s\n", logstr);
1167
1168                 if (BumpErrors()) return DBBAD;
1169             }
1170         } /*f*/
1171     }
1172
1173     return 0;
1174 }
1175
1176 afs_int32
1177 verifyText(ut)
1178      struct ubik_trans *ut;
1179 {
1180     int i;
1181     afs_int32 code;
1182     extern afs_int32 verifyTextChain();
1183
1184     /* check each of the text types in use */
1185     for (i=0; i<TB_NUM; i++)
1186     {
1187         Log("Verify Text: %s", textName[i]);
1188         code = verifyTextChain(ut, &db.h.textBlock[i]);
1189         if (code) return(code);
1190     }
1191     return(0);
1192 }
1193
1194 /* verifyTextChain
1195  *      check the integrity of a text chain. Also checks the new chain.
1196  */
1197 afs_int32
1198 verifyTextChain(ut, tbPtr)
1199      struct ubik_trans *ut;
1200      struct textBlock *tbPtr;
1201 {
1202     dbadr blockAddr;
1203     int blockIndex, entryIndex;
1204     struct block block;
1205     afs_int32 size;
1206     int   new;
1207     afs_int32 code = 0, tcode;
1208
1209     for (new=0; new<2; new++)
1210     {
1211         size = 0;
1212         blockAddr = ntohl(tbPtr->textAddr);
1213
1214         for (blockAddr = (new ? ntohl(tbPtr->newTextAddr) : ntohl(tbPtr->textAddr));
1215              blockAddr; blockAddr = ntohl(block.h.next))
1216         {
1217             tcode = ConvertDiskAddress(blockAddr, &blockIndex, &entryIndex);
1218             if (tcode)
1219             {
1220                 Log("verifyTextChain: Invalid %s text block addr 0x%x\n",
1221                     (new?"new":""), blockAddr);
1222                 Log("     Skipping remainder of text chain\n");
1223                 if (BumpErrors()) ERROR(tcode);
1224                 break;
1225             }
1226
1227             tcode = dbread(ut, blockAddr, &block, sizeof(block));
1228             if (tcode) ERROR(tcode);
1229
1230             if ( blockMap[blockIndex]->entries[entryIndex] & MAP_TEXTBLOCK )
1231             {
1232                 Log("verifyTextChain: Text block (addr 0x%x) multiply chained\n", blockAddr);
1233                 if (BumpErrors()) ERROR(DBBAD);
1234             }
1235             blockMap[blockIndex]->entries[entryIndex] |= MAP_TEXTBLOCK;
1236
1237             size += BLOCK_DATA_SIZE;
1238         }
1239
1240         if ( ntohl(new?tbPtr->newsize:tbPtr->size) > size )
1241         {
1242             Log("verifyTextChain: Text block %s size %d > computed capacity %d\n",
1243                 (new?"new":""), ntohl(new?tbPtr->newsize:tbPtr->size), size);
1244             if (BumpErrors()) ERROR(DBBAD);
1245         }
1246     }
1247
1248 error_exit:
1249     return(code);
1250 }
1251
1252 /* -----------------------------------------
1253  * verification driver routines
1254  * -----------------------------------------
1255  */
1256
1257 /* verifyDatabase
1258  *      Check the integrity of the database
1259  */
1260
1261 afs_int32
1262 verifyDatabase(ut, recreateFile)
1263      struct ubik_trans *ut;
1264      FILE *recreateFile;                 /* not used */
1265 {
1266     afs_int32 eof;
1267     int   j, bmsize;
1268     afs_int32 code = 0, tcode;
1269
1270     extern int nBlocks;                 /* no. blocks in database */
1271     extern struct ubik_dbase *BU_dbase;
1272
1273     /* clear verification statistics */
1274     misc = &miscData;
1275     bzero (&miscData, sizeof(miscData));
1276
1277 #ifdef PDEBUG
1278     miscData.maxErrors = 1000000;
1279 #else
1280     miscData.maxErrors = 50;                   /* Catch the first 50 errors */
1281 #endif
1282     miscData.veryLongChain = 0;
1283     miscData.checkFragCount = 1;                /* check frags */
1284
1285     /* check eofPtr */
1286     eof = ntohl(db.h.eofPtr);
1287     eof -= sizeof(db.h);                        /* subtract header */
1288     nBlocks = eof / BLOCKSIZE;
1289
1290     Log("Verify of backup database started\n");
1291     Log("Database is %u. %d blocks of %d Bytes\n", eof, nBlocks, BLOCKSIZE);
1292
1293     if ((eof < 0) || (nBlocks*BLOCKSIZE != eof))
1294     {
1295         Log("Database eofPtr (%d) bad, blocksize %d\n", eof, BLOCKSIZE);
1296         ERROR(DBBAD);
1297     }
1298
1299     /* set size of database */
1300     miscData.nBlocks = nBlocks;
1301
1302     if (nBlocks == 0) ERROR(0);    /* Nothing to check? */
1303
1304     /* construct block map - first level is the array of pointers */
1305     bmsize = nBlocks*sizeof(struct blockMap *);
1306     blockMap = (struct blockMap **) malloc(bmsize);
1307     if (!blockMap) ERROR(BUDB_NOMEM);
1308     bzero(blockMap, bmsize);
1309
1310      /* verify blocks and construct the block map */
1311     Log("Read header of every block\n");
1312     tcode = verifyBlocks(ut);
1313     if (tcode) ERROR(tcode);
1314
1315     /* check the various hash tables */
1316     Log("Verify volume name hash table\n");
1317     tcode = verifyHashTable(ut, &db.volName, MAP_VOLHASH);
1318     if (tcode) ERROR(tcode);
1319
1320     Log("Verify tape name hash table\n");
1321     tcode = verifyHashTable(ut, &db.tapeName, MAP_TAPEHASH);
1322     if (tcode) ERROR(tcode);
1323
1324     Log("Verify dump name hash table\n");
1325     tcode = verifyHashTable(ut, &db.dumpName, MAP_DUMPHASH);
1326     if (tcode) ERROR(tcode);
1327
1328     Log("Verify dump id hash table\n");
1329     tcode = verifyHashTable(ut, &db.dumpIden, MAP_IDHASH);
1330     if (tcode) ERROR(tcode);
1331
1332     /* check the entry chains */
1333     Log("Verify all blocks and entries\n");
1334     tcode = verifyEntryChains(ut);
1335     if (tcode) ERROR(tcode);
1336
1337     /* check text blocks - Log message in verifyText */
1338     tcode = verifyText(ut);
1339     if (tcode) ERROR(tcode);
1340
1341     /* check free list */
1342     Log("Verify Free Lists\n");
1343     tcode = verifyFreeLists();
1344     if (tcode) ERROR(tcode);
1345
1346     /* check entry map bit compatibility */
1347
1348     Log("Verify Map bits\n");
1349     tcode = verifyMapBits();
1350     if (tcode) ERROR(tcode);
1351
1352 error_exit:
1353     /* free the block map */
1354     if ( blockMap != 0 )
1355     {
1356         int i;
1357
1358         /* free all the individual maps */
1359         for ( i = 0; i < nBlocks; i++ )
1360         {
1361             if ( blockMap[i] )
1362                 free(blockMap[i]);
1363         }
1364
1365         /* free the pointer array */
1366         free(blockMap);
1367         blockMap = 0;
1368     }
1369
1370     if (!tcode) {
1371        Log("# 2K database blocks    = %d\n", miscData.nBlocks);
1372        Log("# Dump entries found    = %d. 3 dumps per block\n", miscData.nDump);
1373        Log("  max tapes   on a dump = %d\n", miscData.maxTapesPerDump);
1374        Log("  max volumes on a dump = %d\n", miscData.maxVolsPerDump);
1375        Log("  max appends on a dump = %d\n", miscData.maxAppendsPerDump);
1376        Log("  # Blocks with space   = %d\n", miscData.freeLength[4]);
1377        Log("  # of those fully free = %d\n", miscData.fullyFree[4]);
1378        Log("# Tape entries found    = %d. 20 tapes per block\n", miscData.nTape);
1379        Log("  max volumes on a tape = %d\n", miscData.maxVolsPerTape);
1380        Log("  # Blocks with space   = %d\n", miscData.freeLength[3]);
1381        Log("  # of those fully free = %d\n", miscData.fullyFree[3]);
1382        Log("# VolInfo entries found = %d. 20 volInfos per block\n", miscData.nVolInfo);
1383        Log("  # head of sameNameCh  = %d\n", miscData.nVolName);
1384        Log("  max on a  sameNameCh  = %d\n", miscData.maxVolInfosPerName);
1385        Log("  max VolFrags on chain = %d\n", miscData.maxVolsPerVolInfo);
1386        Log("  # Blocks with space   = %d\n", miscData.freeLength[2]);
1387        Log("  # of those fully free = %d\n", miscData.fullyFree[2]);
1388        Log("# VolFrag entries found = %d. 45 VolFrags per block\n", miscData.nVolFrag);
1389        Log("  # Blocks with space   = %d\n", miscData.freeLength[1]);
1390        Log("  # of those fully free = %d\n", miscData.fullyFree[1]);
1391        Log("# free blocks           = %d\n", miscData.freeLength[0]);
1392     }
1393
1394     Log("Verify of database completed. %d errors found\n", miscData.errors);
1395
1396     if (miscData.errors && !code) code = DBBAD;
1397     return(code);
1398 }
1399
1400
1401 /* -----------------------------
1402  * interface routines
1403  * -----------------------------
1404  */
1405
1406 /* BUDB_DbVerify
1407  *      check the integrity of the database
1408  * exit:
1409  *      status - integrity: 0, ok; n, not ok (error value)
1410  *      orphans - no. of orphan blocks
1411  *      host - address of host that did verification
1412  */
1413 afs_int32 DbVerify();
1414 afs_int32 BUDB_DbVerify(call, status, orphans, host)
1415      struct rx_call *call;
1416      afs_int32 *status;
1417      afs_int32 *orphans;
1418      afs_int32 *host;
1419 {
1420      afs_int32 code;
1421
1422      code = DbVerify(call, status, orphans, host);
1423      osi_auditU(call, BUDB_DBVfyEvent, code, AUD_END);
1424      return code;
1425 }
1426
1427 afs_int32 DbVerify(call, status, orphans, host)
1428      struct rx_call *call;
1429      afs_int32 *status;
1430      afs_int32 *orphans;
1431      afs_int32 *host;
1432 {
1433     struct ubik_trans *ut = 0;
1434     afs_int32 code = 0, tcode;
1435     char hostname[64];
1436     struct hostent *th;
1437
1438     if ( callPermitted(call) == 0 )
1439         ERROR(BUDB_NOTPERMITTED);
1440
1441     tcode = InitRPC (&ut, LOCKREAD, 1);
1442     if (tcode) ERROR(tcode);
1443
1444     tcode = verifyDatabase(ut, 0);    /* check the database */
1445     if (tcode) ERROR(tcode);
1446
1447 error_exit:
1448     if (ut) {
1449         if (code) ubik_AbortTrans(ut);
1450         else code = ubik_EndTrans(ut);
1451     }
1452
1453     *status  = code;
1454     *orphans = 0;
1455
1456     gethostname(hostname, sizeof(hostname));
1457     th = gethostbyname(hostname);
1458     if (!th) *host = 0;
1459     else
1460     {
1461         bcopy(th->h_addr, host, sizeof(afs_int32));
1462         *host = ntohl(*host);
1463     }
1464
1465     return(0);
1466 }
1467
1468 /* ----------------------
1469  * debug support
1470  * ----------------------
1471  */
1472
1473 /* check_header
1474  *      do a simple sanity check on the database header
1475  */
1476
1477 check_header(callerst)
1478      char *callerst;
1479 {
1480     static int iteration_count = 0;
1481     afs_int32 eof;
1482
1483     eof = ntohl(db.h.eofPtr);
1484     if ( (eof == 0) || (eof < 0) )
1485     {
1486         Log("Eof check failed, caller %s, eof 0x%x\n",
1487             callerst, eof);
1488     }
1489
1490     eof -= sizeof(db.h);
1491     if ( eof < 0 )
1492     {
1493         Log("Adjusted Eof check failed, caller %s, eof 0x%x\n",
1494             callerst, eof);
1495     }
1496
1497     iteration_count++;
1498     if ( iteration_count >= 10 )
1499     {
1500         Log("Eof ptr is 0x%x\n", eof);
1501         iteration_count = 0;
1502     }
1503 }