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