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