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