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         /* FIXME: this list does not match typeName[] and may be incorrect */
 965         0,                      /* free block */
 966             verifyVolFragEntry, verifyVolInfoEntry, verifyTapeEntry, verifyDumpEntry, 0 /* text block */
 967     };
 968
 969     for (blockIndex = 0; blockIndex < nBlocks; blockIndex++) {  /*f */
 970         /* ignore non-structure or blocks with invalid type */
 971         type = blockMap[blockIndex]->header.type;
 972         if ((type <= 0) || (type > MAX_STRUCTURE_BLOCK_TYPE))
 973             continue;
 974
 975         entrySize = blockEntrySize[type];
 976         nFree = 0;
 977
 978         for (entryIndex = 0; entryIndex < blockMap[blockIndex]->nEntries; entryIndex++) {       /*f */
 979             offset =
 980                 sizeof(db.h) + (blockIndex * BLOCKSIZE) +
 981                 sizeof(struct blockHeader) + (entryIndex * entrySize);
 982             if (dbread(ut, offset, &entry[0], entrySize))
 983                 return BUDB_IO;
 984
 985             /* check if entry is free by looking at the first "afs_int32" of the structure */
 986             if (*((afs_int32 *) & entry[0]) == 0) {     /* zero is free */
 987                 /* Is it on any hash chain? */
 988                 if (blockMap[blockIndex]->entries[entryIndex] & MAP_HASHES) {
 989                     Log("Entry: blockindex %d, entryindex %d - marked free but hashed 0x%x\n", blockIndex, entryIndex, blockMap[blockIndex]->entries[entryIndex]);
 990                     if (BumpErrors())
 991                         return DBBAD;
 992                 }
 993
 994                 blockMap[blockIndex]->entries[entryIndex] |= MAP_FREE;
 995                 nFree++;
 996             } else {
 997                 /* check the entry itself for consistency */
 998                 code =
 999                     (*(checkEntry[type])) (ut, offset, blockIndex, entryIndex,
1000                                            &entry[0]);
1001                 if (code)
1002                     return code;
1003             }
1004         }                       /*f */
1005
1006         /* check computed free with recorded free entries */
1007         if (nFree != ntohs(blockMap[blockIndex]->header.nFree)) {
1008             Log("Block (index %d) free count %d has %d free structs\n",
1009                 blockIndex, ntohs(blockMap[blockIndex]->header.nFree), nFree);
1010             if (BumpErrors())
1011                 return DBBAD;
1012         }
1013     }                           /*f */
1014
1015     return 0;
1016 }
1017
1018
1019 afs_int32
1020 verifyFreeLists()
1021 {
1022     int i;
1023     afs_int32 addr;
1024     int blockIndex, entryIndex;
1025     int nFree;
1026     afs_int32 code;
1027
1028     /* for each free list */
1029     for (i = 0; i < NBLOCKTYPES; i++) {
1030         misc->fullyFree[i] = misc->freeLength[i] = 0;
1031
1032         for (addr = ntohl(db.h.freePtrs[i]); addr;
1033              addr = ntohl(blockMap[blockIndex]->header.next)) {
1034             misc->freeLength[i]++;
1035
1036             code = ConvertDiskAddress(addr, &blockIndex, &entryIndex);
1037             if (code || (entryIndex != 0)) {
1038                 Log("verifyFreeLists: Invalid free chain addr 0x%x in %s free chain\n", addr, TypeName(i));
1039                 Log("     Skipping remainder of free chain\n");
1040                 if (BumpErrors())
1041                     return (DBBAD);
1042                 code = 0;
1043                 break;
1044             }
1045
1046             /* check block type */
1047             if (blockMap[blockIndex]->header.type != i) {
1048                 Log("verifyFreeLists: Found %s type in %s free chain (addr 0x%x)\n",
1049                     TypeName(blockMap[blockIndex]->header.type), TypeName(i),
1050                     addr);
1051                 if (BumpErrors())
1052                     return (DBBAD);
1053             }
1054
1055             /* If entire block isn't free, check if count of free entries is ok */
1056             nFree = ntohs(blockMap[blockIndex]->header.nFree);
1057             if (i != free_BLOCK) {
1058                 if ((nFree <= 0) || (nFree > blockEntries[i])) {
1059                     Log("verifyFreeLists: Illegal free count %d on %s free chain\n", nFree, TypeName(i));
1060                     if (BumpErrors())
1061                         return (DBBAD);
1062                 } else if (nFree == blockEntries[i]) {
1063                     misc->fullyFree[i]++;
1064                 }
1065             }
1066
1067             /* Check if already examined the block */
1068             if (blockMap[blockIndex]->free) {
1069                 Log("verifyFreeLists: %s free chain block at addr 0x%x multiply threaded\n", TypeName(i), addr);
1070                 if (BumpErrors())
1071                     return DBBAD;
1072             }
1073             blockMap[blockIndex]->free++;
1074         }
1075     }
1076
1077     return 0;
1078 }
1079
1080 /* verifyMapBits
1081  *      Examines each entry to make sure it was traversed appropriately by
1082  *      checking the bits for compatibility.
1083  */
1084 afs_int32
1085 verifyMapBits()
1086 {
1087     int blockIndex, entryIndex, i, entrySize, type, bits;
1088     afs_int32 offset;
1089
1090     for (blockIndex = 0; blockIndex < nBlocks; blockIndex++) {
1091         /* If no entries in this block, then the block should be marked free */
1092         if ((blockMap[blockIndex]->nEntries == 0)
1093             && !blockMap[blockIndex]->free) {
1094             Log("verifyMapBits: Orphan free block (index %d)\n", blockIndex);
1095             if (BumpErrors())
1096                 return DBBAD;
1097         }
1098
1099         /* check each entry */
1100         for (entryIndex = 0; entryIndex < blockMap[blockIndex]->nEntries; entryIndex++) {       /*f */
1101             if ((entryIndex % 1024) == 0)
1102                 IOMGR_Poll();
1103
1104             bits = blockMap[blockIndex]->entries[entryIndex];
1105
1106             for (i = 0; i < NMAPCs; i++)
1107                 if ((bits & mapC[i].trigger) == mapC[i].trigger)
1108                     break;
1109
1110             if (i >= NMAPCs) {
1111                 char logstr[256];
1112
1113                 type = blockMap[blockIndex]->header.type;
1114                 entrySize = blockEntrySize[type];
1115                 offset =
1116                     sizeof(db.h) + (blockIndex * BLOCKSIZE) +
1117                     sizeof(struct blockHeader) + (entryIndex * entrySize);
1118
1119                 sprintf(logstr, "%s entry Block %d, Entry %d, (addr 0x%x)",
1120                         TypeName(type), blockIndex, entryIndex, offset);
1121
1122                 if (!bits)
1123                     strcat(logstr, ": An orphaned entry");
1124                 if (bits & MAP_FREE)
1125                     strcat(logstr, ": A valid free block");
1126                 if (bits & MAP_HTBLOCK)
1127                     strcat(logstr, ": A valid hash-table block");
1128                 if (bits & MAP_TEXTBLOCK)
1129                     strcat(logstr, ": A valid text block");
1130                 if (bits & (MAP_DUMPHASH | MAP_IDHASH)) {
1131                     if (!(bits & MAP_DUMPHASH))
1132                         strcat(logstr,
1133                                ": A dump not on dump-name hash-chain");
1134                     else if (!(bits & MAP_IDHASH))
1135                         strcat(logstr, ": A dump not on dump-id hash-chain");
1136                     else
1137                         strcat(logstr, ": A valid dump entry");
1138                 }
1139                 if (bits & (MAP_TAPEHASH | MAP_TAPEONDUMP)) {
1140                     if (!(bits & MAP_TAPEHASH))
1141                         strcat(logstr,
1142                                ": A tape not on tape-name hash-chain");
1143                     else if (!(bits & MAP_TAPEONDUMP))
1144                         strcat(logstr, ": A tape not associated with a dump");
1145                     else
1146                         strcat(logstr, ": A valid tape entry");
1147                 }
1148                 if (bits & MAP_VOLINFOONNAME)
1149                     strcat(logstr,
1150                            ": A valid volInfo on a volume-name chain");
1151                 if (bits & (MAP_VOLINFONAMEHEAD | MAP_VOLHASH)) {
1152                     if (!(bits & MAP_VOLINFONAMEHEAD))
1153                         strcat(logstr,
1154                                ": A volInfo not the head of a volume-name hash-chain");
1155                     else if (!(bits & MAP_VOLHASH))
1156                         strcat(logstr,
1157                                ": A volInfo not on volume-name hash-chain");
1158                     else
1159                         strcat(logstr,
1160                                ": A valid volInfo in volume-name hash-chain");
1161                 }
1162                 if (bits & (MAP_VOLFRAGONTAPE | MAP_VOLFRAGONVOL)) {
1163                     if (!(bits & MAP_VOLFRAGONTAPE))
1164                         strcat(logstr,
1165                                ": A volFrag not associated with a tape");
1166                     else if (!(bits & MAP_VOLFRAGONVOL))
1167                         strcat(logstr,
1168                                ": A volFrag not associated with a volume");
1169                     else
1170                         strcat(logstr, ": A valid volFrag entry");
1171                 }
1172                 Log("%s\n", logstr);
1173
1174                 if (BumpErrors())
1175                     return DBBAD;
1176             }
1177         }                       /*f */
1178     }
1179
1180     return 0;
1181 }
1182
1183 afs_int32
1184 verifyText(ut)
1185      struct ubik_trans *ut;
1186 {
1187     int i;
1188     afs_int32 code;
1189     extern afs_int32 verifyTextChain();
1190
1191     /* check each of the text types in use */
1192     for (i = 0; i < TB_NUM; i++) {
1193         Log("Verify Text: %s", textName[i]);
1194         code = verifyTextChain(ut, &db.h.textBlock[i]);
1195         if (code)
1196             return (code);
1197     }
1198     return (0);
1199 }
1200
1201 /* verifyTextChain
1202  *      check the integrity of a text chain. Also checks the new chain.
1203  */
1204 afs_int32
1205 verifyTextChain(ut, tbPtr)
1206      struct ubik_trans *ut;
1207      struct textBlock *tbPtr;
1208 {
1209     dbadr blockAddr;
1210     int blockIndex, entryIndex;
1211     struct block block;
1212     afs_int32 size;
1213     int new;
1214     afs_int32 code = 0, tcode;
1215
1216     for (new = 0; new < 2; new++) {
1217         size = 0;
1218         blockAddr = ntohl(tbPtr->textAddr);
1219
1220         for (blockAddr =
1221              (new ? ntohl(tbPtr->newTextAddr) : ntohl(tbPtr->textAddr));
1222              blockAddr; blockAddr = ntohl(block.h.next)) {
1223             tcode = ConvertDiskAddress(blockAddr, &blockIndex, &entryIndex);
1224             if (tcode) {
1225                 Log("verifyTextChain: Invalid %s text block addr 0x%x\n",
1226                     (new ? "new" : ""), blockAddr);
1227                 Log("     Skipping remainder of text chain\n");
1228                 if (BumpErrors())
1229                     ERROR(tcode);
1230                 break;
1231             }
1232
1233             tcode = dbread(ut, blockAddr, &block, sizeof(block));
1234             if (tcode)
1235                 ERROR(tcode);
1236
1237             if (blockMap[blockIndex]->entries[entryIndex] & MAP_TEXTBLOCK) {
1238                 Log("verifyTextChain: Text block (addr 0x%x) multiply chained\n", blockAddr);
1239                 if (BumpErrors())
1240                     ERROR(DBBAD);
1241             }
1242             blockMap[blockIndex]->entries[entryIndex] |= MAP_TEXTBLOCK;
1243
1244             size += BLOCK_DATA_SIZE;
1245         }
1246
1247         if (ntohl(new ? tbPtr->newsize : tbPtr->size) > size) {
1248             Log("verifyTextChain: Text block %s size %d > computed capacity %d\n", (new ? "new" : ""), ntohl(new ? tbPtr->newsize : tbPtr->size), size);
1249             if (BumpErrors())
1250                 ERROR(DBBAD);
1251         }
1252     }
1253
1254   error_exit:
1255     return (code);
1256 }
1257
1258 /* -----------------------------------------
1259  * verification driver routines
1260  * -----------------------------------------
1261  */
1262
1263 /* verifyDatabase
1264  *      Check the integrity of the database
1265  */
1266
1267 afs_int32
1268 verifyDatabase(ut, recreateFile)
1269      struct ubik_trans *ut;
1270      FILE *recreateFile;        /* not used */
1271 {
1272     afs_int32 eof;
1273     int bmsize;
1274     afs_int32 code = 0, tcode;
1275
1276     extern int nBlocks;         /* no. blocks in database */
1277     extern struct ubik_dbase *BU_dbase;
1278
1279     /* clear verification statistics */
1280     misc = &miscData;
1281     memset(&miscData, 0, sizeof(miscData));
1282
1283 #ifdef PDEBUG
1284     miscData.maxErrors = 1000000;
1285 #else
1286     miscData.maxErrors = 50;    /* Catch the first 50 errors */
1287 #endif
1288     miscData.veryLongChain = 0;
1289     miscData.checkFragCount = 1;        /* check frags */
1290
1291     /* check eofPtr */
1292     eof = ntohl(db.h.eofPtr);
1293     eof -= sizeof(db.h);        /* subtract header */
1294     nBlocks = eof / BLOCKSIZE;
1295
1296     Log("Verify of backup database started\n");
1297     Log("Database is %u. %d blocks of %d Bytes\n", eof, nBlocks, BLOCKSIZE);
1298
1299     if ((eof < 0) || (nBlocks * BLOCKSIZE != eof)) {
1300         Log("Database eofPtr (%d) bad, blocksize %d\n", eof, BLOCKSIZE);
1301         ERROR(DBBAD);
1302     }
1303
1304     /* set size of database */
1305     miscData.nBlocks = nBlocks;
1306
1307     if (nBlocks == 0)
1308         ERROR(0);               /* Nothing to check? */
1309
1310     /* construct block map - first level is the array of pointers */
1311     bmsize = nBlocks * sizeof(struct blockMap *);
1312     blockMap = (struct blockMap **)malloc(bmsize);
1313     if (!blockMap)
1314         ERROR(BUDB_NOMEM);
1315     memset(blockMap, 0, bmsize);
1316
1317     /* verify blocks and construct the block map */
1318     Log("Read header of every block\n");
1319     tcode = verifyBlocks(ut);
1320     if (tcode)
1321         ERROR(tcode);
1322
1323     /* check the various hash tables */
1324     Log("Verify volume name hash table\n");
1325     tcode = verifyHashTable(ut, &db.volName, MAP_VOLHASH);
1326     if (tcode)
1327         ERROR(tcode);
1328
1329     Log("Verify tape name hash table\n");
1330     tcode = verifyHashTable(ut, &db.tapeName, MAP_TAPEHASH);
1331     if (tcode)
1332         ERROR(tcode);
1333
1334     Log("Verify dump name hash table\n");
1335     tcode = verifyHashTable(ut, &db.dumpName, MAP_DUMPHASH);
1336     if (tcode)
1337         ERROR(tcode);
1338
1339     Log("Verify dump id hash table\n");
1340     tcode = verifyHashTable(ut, &db.dumpIden, MAP_IDHASH);
1341     if (tcode)
1342         ERROR(tcode);
1343
1344     /* check the entry chains */
1345     Log("Verify all blocks and entries\n");
1346     tcode = verifyEntryChains(ut);
1347     if (tcode)
1348         ERROR(tcode);
1349
1350     /* check text blocks - Log message in verifyText */
1351     tcode = verifyText(ut);
1352     if (tcode)
1353         ERROR(tcode);
1354
1355     /* check free list */
1356     Log("Verify Free Lists\n");
1357     tcode = verifyFreeLists();
1358     if (tcode)
1359         ERROR(tcode);
1360
1361     /* check entry map bit compatibility */
1362
1363     Log("Verify Map bits\n");
1364     tcode = verifyMapBits();
1365     if (tcode)
1366         ERROR(tcode);
1367
1368   error_exit:
1369     /* free the block map */
1370     if (blockMap != 0) {
1371         int i;
1372
1373         /* free all the individual maps */
1374         for (i = 0; i < nBlocks; i++) {
1375             if (blockMap[i])
1376                 free(blockMap[i]);
1377         }
1378
1379         /* free the pointer array */
1380         free(blockMap);
1381         blockMap = 0;
1382     }
1383
1384     if (!tcode) {
1385         Log("# 2K database blocks    = %d\n", miscData.nBlocks);
1386         Log("# Dump entries found    = %d. 3 dumps per block\n",
1387             miscData.nDump);
1388         Log("  max tapes   on a dump = %d\n", miscData.maxTapesPerDump);
1389         Log("  max volumes on a dump = %d\n", miscData.maxVolsPerDump);
1390         Log("  max appends on a dump = %d\n", miscData.maxAppendsPerDump);
1391         Log("  # Blocks with space   = %d\n", miscData.freeLength[4]);
1392         Log("  # of those fully free = %d\n", miscData.fullyFree[4]);
1393         Log("# Tape entries found    = %d. 20 tapes per block\n",
1394             miscData.nTape);
1395         Log("  max volumes on a tape = %d\n", miscData.maxVolsPerTape);
1396         Log("  # Blocks with space   = %d\n", miscData.freeLength[3]);
1397         Log("  # of those fully free = %d\n", miscData.fullyFree[3]);
1398         Log("# VolInfo entries found = %d. 20 volInfos per block\n",
1399             miscData.nVolInfo);
1400         Log("  # head of sameNameCh  = %d\n", miscData.nVolName);
1401         Log("  max on a  sameNameCh  = %d\n", miscData.maxVolInfosPerName);
1402         Log("  max VolFrags on chain = %d\n", miscData.maxVolsPerVolInfo);
1403         Log("  # Blocks with space   = %d\n", miscData.freeLength[2]);
1404         Log("  # of those fully free = %d\n", miscData.fullyFree[2]);
1405         Log("# VolFrag entries found = %d. 45 VolFrags per block\n",
1406             miscData.nVolFrag);
1407         Log("  # Blocks with space   = %d\n", miscData.freeLength[1]);
1408         Log("  # of those fully free = %d\n", miscData.fullyFree[1]);
1409         Log("# free blocks           = %d\n", miscData.freeLength[0]);
1410     }
1411
1412     Log("Verify of database completed. %d errors found\n", miscData.errors);
1413
1414     if (miscData.errors && !code)
1415         code = DBBAD;
1416     return (code);
1417 }
1418
1419
1420 /* -----------------------------
1421  * interface routines
1422  * -----------------------------
1423  */
1424
1425 /* BUDB_DbVerify
1426  *      check the integrity of the database
1427  * exit:
1428  *      status - integrity: 0, ok; n, not ok (error value)
1429  *      orphans - no. of orphan blocks
1430  *      host - address of host that did verification
1431  */
1432 afs_int32 DbVerify();
1433 afs_int32
1434 SBUDB_DbVerify(call, status, orphans, host)
1435      struct rx_call *call;
1436      afs_int32 *status;
1437      afs_int32 *orphans;
1438      afs_int32 *host;
1439 {
1440     afs_int32 code;
1441
1442     code = DbVerify(call, status, orphans, host);
1443     osi_auditU(call, BUDB_DBVfyEvent, code, AUD_END);
1444     return code;
1445 }
1446
1447 afs_int32
1448 DbVerify(call, status, orphans, host)
1449      struct rx_call *call;
1450      afs_int32 *status;
1451      afs_int32 *orphans;
1452      afs_int32 *host;
1453 {
1454     struct ubik_trans *ut = 0;
1455     afs_int32 code = 0, tcode;
1456     char hostname[64];
1457     struct hostent *th;
1458
1459     if (callPermitted(call) == 0)
1460         ERROR(BUDB_NOTPERMITTED);
1461
1462     tcode = InitRPC(&ut, LOCKREAD, 1);
1463     if (tcode)
1464         ERROR(tcode);
1465
1466     tcode = verifyDatabase(ut, 0);      /* check the database */
1467     if (tcode)
1468         ERROR(tcode);
1469
1470   error_exit:
1471     if (ut) {
1472         if (code)
1473             ubik_AbortTrans(ut);
1474         else
1475             code = ubik_EndTrans(ut);
1476     }
1477
1478     *status = code;
1479     *orphans = 0;
1480
1481     gethostname(hostname, sizeof(hostname));
1482     th = gethostbyname(hostname);
1483     if (!th)
1484         *host = 0;
1485     else {
1486         memcpy(host, th->h_addr, sizeof(afs_int32));
1487         *host = ntohl(*host);
1488     }
1489
1490     return (0);
1491 }
1492
1493 /* ----------------------
1494  * debug support
1495  * ----------------------
1496  */
1497
1498 /* check_header
1499  *      do a simple sanity check on the database header
1500  */
1501
1502 check_header(callerst)
1503      char *callerst;
1504 {
1505     static int iteration_count = 0;
1506     afs_int32 eof;
1507
1508     eof = ntohl(db.h.eofPtr);
1509     if ((eof == 0) || (eof < 0)) {
1510         Log("Eof check failed, caller %s, eof 0x%x\n", callerst, eof);
1511     }
1512
1513     eof -= sizeof(db.h);
1514     if (eof < 0) {
1515         Log("Adjusted Eof check failed, caller %s, eof 0x%x\n", callerst,
1516             eof);
1517     }
1518
1519     iteration_count++;
1520     if (iteration_count >= 10) {
1521         Log("Eof ptr is 0x%x\n", eof);
1522         iteration_count = 0;
1523     }
1524 }