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