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