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