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 = calloc(1, bmsize);
 703         if (!ablockMap)
 704             ERROR(BUDB_NOMEM);
 705
 706         ablockMap->nEntries = blockEntries[blocktype];
 707
 708         /* save the block header in the block map */
 709         memcpy(&ablockMap->header, &block.h, sizeof(ablockMap->header));
 710         blockMap[i] = ablockMap;
 711     }
 712
 713   error_exit:
 714     return (code);
 715 }
 716
 717 int minvols, maxvols, ttlvols;
 718
 719 /* verifyHashTableBlock
 720  *      Take a 2K hash table block and traverse its entries. Make sure each entry
 721  *      is of the correct type for the hash table, is hashed into the correct
 722  *      entry and is not threaded on multiple lists.
 723  */
 724 afs_int32
 725 verifyHashTableBlock(struct ubik_trans *ut,
 726                      struct memoryHashTable *mhtPtr,
 727                      struct htBlock *htBlockPtr,
 728                      int old,
 729                      afs_int32 length,  /* size of whole hash table */
 730                      int index,         /* base index of this block */
 731                      int mapBit)
 732 {
 733     int type;                   /* hash table type */
 734     int entrySize;              /* hashed entry size */
 735     int blockType;              /* block type for this hash table */
 736     int blockIndex, entryIndex;
 737     char entry[sizeof(struct block)];
 738     dbadr entryAddr;
 739     int hash;                   /* calculated hash value for entry */
 740     int i, count;
 741     afs_int32 code = 0, tcode;
 742
 743     type = ntohl(mhtPtr->ht->functionType);
 744     entrySize = sizeFunctions[type];
 745     blockType = hashBlockType[type];
 746
 747     /* step through this hash table block, being careful to stop
 748      * before the end of the overall hash table
 749      */
 750
 751     for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) {   /*f */
 752         entryAddr = ntohl(htBlockPtr->bucket[i]);
 753
 754         /* if this is the old hash table, all entries below the progress mark
 755          * should have been moved to the new hash table
 756          */
 757         if (old && (index < mhtPtr->progress) && entryAddr) {
 758             Log("Old hash table not empty (entry %d) below progress (%d)\n",
 759                 i, mhtPtr->progress);
 760             if (BumpErrors())
 761                 ERROR(DBBAD);
 762         }
 763
 764         /* now walk down the chain of each bucket */
 765         for (count = 0; entryAddr; count++) {   /*w */
 766             tcode = ConvertDiskAddress(entryAddr, &blockIndex, &entryIndex);
 767             if (tcode) {
 768                 Log("verifyHashTableBlock: Invalid hash table chain addr 0x%x\n", entryAddr);
 769                 Log("     Skipping remainder of bucket %d\n", index);
 770                 if (BumpErrors())
 771                     ERROR(DBBAD);
 772                 code = 0;
 773                 break;
 774             }
 775
 776             if (blockMap[blockIndex]->header.type != blockType) {
 777                 Log("Hash table chain (block index %d) incorrect\n",
 778                     blockIndex);
 779                 Log("     Table type %d traverses block type %d\n", blockType,
 780                     blockMap[blockIndex]->header.type);
 781                 Log("     Skipping remainder of bucket %d\n", index);
 782                 if (BumpErrors())
 783                     ERROR(DBBAD);
 784                 break;
 785             }
 786
 787             if (dbread(ut, entryAddr, &entry[0], entrySize))
 788                 ERROR(DBBAD);
 789
 790             hash = ht_HashEntry(mhtPtr, &entry[0]) % length;
 791             if (hash != index) {        /* if it hashed to some other place */
 792                 Log("Entry (addr 0x%x) bucket %d, should be hashed into bucket %d\n", entryAddr, index, hash);
 793                 if (BumpErrors())
 794                     ERROR(DBBAD);
 795             }
 796
 797             /* check if entry has been examined */
 798             if (blockMap[blockIndex]->entries[entryIndex] & mapBit) {
 799                 Log("Entry (addr 0x%x) multiply referenced\n", entryAddr);
 800                 if (BumpErrors())
 801                     ERROR(DBBAD);
 802             }
 803             blockMap[blockIndex]->entries[entryIndex] |= mapBit;
 804
 805             entryAddr = ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
 806         }                       /*w */
 807
 808         /* Log("Bucket %4d contains %d entries\n", index+1, count); */
 809         ttlvols += count;
 810         if (count < minvols)
 811             minvols = count;
 812         if (count > maxvols)
 813             maxvols = count;
 814     }                           /*f */
 815
 816   error_exit:
 817     return (code);
 818 }
 819
 820 /* verifyHashTable
 821  *      Read each 2K block a hashtable has (both its old hastable and
 822  *      new hashtable) and verify the block has not been read before.
 823  *      Will also make call to verify entries within each 2K block of
 824  *      the hash table.
 825  */
 826 afs_int32
 827 verifyHashTable(struct ubik_trans *ut, struct memoryHashTable *mhtPtr,
 828                 int mapBit)
 829 {
 830     struct hashTable *htPtr = mhtPtr->ht;
 831
 832     struct htBlock hashTableBlock;
 833     int tableLength;            /* # entries */
 834     int hashblocks;             /* # blocks */
 835     dbadr tableAddr;            /* disk addr of hash block */
 836     int blockIndex, entryIndex;
 837     int old;
 838     int i;
 839     afs_int32 code = 0, tcode;
 840
 841     extern int nHTBuckets;      /* # buckets in a hash table */
 842
 843     LogDebug(4, "Htable: length %d oldlength %d progress %d\n",
 844              mhtPtr->length, mhtPtr->oldLength, mhtPtr->progress);
 845
 846     /* check both old and current tables */
 847     for (old = 0; old <= 1; old++) {    /*fo */
 848         tableLength = (old ? mhtPtr->oldLength : mhtPtr->length);
 849         if (tableLength == 0)
 850             continue;
 851         tableAddr = (old ? ntohl(htPtr->oldTable) : ntohl(htPtr->table));
 852         minvols = 999999;
 853         maxvols = ttlvols = 0;
 854
 855         /* follow the chain of hashtable blocks - avoid infinite loops */
 856         hashblocks = ((tableLength - 1) / nHTBuckets) + 1;      /* numb of 2K hashtable blocks */
 857         for (i = 0; (tableAddr && (i < hashblocks + 5)); i++) {
 858             tcode = ConvertDiskAddress(tableAddr, &blockIndex, &entryIndex);
 859             if (tcode) {
 860                 Log("verifyHashTable: Invalid hash table chain addr 0x%x\n",
 861                     tableAddr);
 862                 Log("     Skipping remainder of hash table chain\n");
 863                 if (BumpErrors())
 864                     return (DBBAD);
 865                 code = 0;
 866                 break;
 867             }
 868
 869             if (blockMap[blockIndex]->header.type != hashTable_BLOCK) {
 870                 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);
 871                 Log("     Skipping remainder of hash table chain\n");
 872                 if (BumpErrors())
 873                     ERROR(BUDB_BLOCKTYPE);
 874                 break;
 875             }
 876
 877             /* check if we've examined this block before */
 878             /* mark this (hash table) block as examined  */
 879             if (blockMap[blockIndex]->entries[entryIndex] & MAP_HTBLOCK) {
 880                 Log("Hash table block (index %d addr 0x%x) multiple ref\n",
 881                     i + 1, tableAddr);
 882                 if (BumpErrors())
 883                     ERROR(BUDB_DATABASEINCONSISTENT);
 884             }
 885             blockMap[blockIndex]->entries[entryIndex] |= MAP_HTBLOCK;
 886
 887             /* Read the actual hash table block */
 888             tcode =
 889                 dbread(ut, tableAddr, &hashTableBlock,
 890                        sizeof(hashTableBlock));
 891             if (tcode)
 892                 ERROR(tcode);
 893
 894             /* Verify its entries */
 895             tcode =
 896                 verifyHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
 897                                      tableLength, (i * nHTBuckets), mapBit);
 898             if (tcode)
 899                 ERROR(tcode);
 900
 901             tableAddr = ntohl(hashTableBlock.h.next);
 902         }
 903
 904         /* Verify numb hash blocks is as it says */
 905         if (i != hashblocks) {
 906             Log("Incorrect number of hash chain blocks: %d (expected %d), hashtype %d\n", i, hashblocks, ntohl(htPtr->functionType));
 907             if (BumpErrors())
 908                 ERROR(BUDB_DATABASEINCONSISTENT);
 909         }
 910
 911         if (ttlvols)
 912             Log("%d entries; %u buckets; min = %d; max = %d\n", ttlvols,
 913                 tableLength, minvols, maxvols);
 914     }                           /*fo */
 915
 916   error_exit:
 917     return (code);
 918 }
 919
 920 /* verifyEntryChains
 921  *      do a linear walk of all the blocks. Check each block of structures
 922  *      to see if the actual free matches the recorded free. Also check
 923  *      the integrity of each allocated structure.
 924  */
 925 afs_int32
 926 verifyEntryChains(struct ubik_trans *ut)
 927 {
 928     afs_int32 code;
 929     afs_int32 offset;
 930     afs_int32 start;
 931     int blockIndex, entryIndex;
 932     char entry[sizeof(struct block)];
 933     int entrySize;
 934     int type;
 935     int nFree;
 936
 937     static afs_int32(*checkEntry[NBLOCKTYPES]) (struct ubik_trans *,
 938                                                 afs_int32, int, int, void *)
 939         = {
 940         /* FIXME: this list does not match typeName[] and may be incorrect */
 941         0,                      /* free block */
 942             verifyVolFragEntry, verifyVolInfoEntry, verifyTapeEntry, verifyDumpEntry, 0 /* text block */
 943     };
 944
 945     for (blockIndex = 0; blockIndex < nBlocks; blockIndex++) {  /*f */
 946         /* ignore non-structure or blocks with invalid type */
 947         type = blockMap[blockIndex]->header.type;
 948         if ((type <= 0) || (type > MAX_STRUCTURE_BLOCK_TYPE))
 949             continue;
 950
 951         entrySize = blockEntrySize[type];
 952         nFree = 0;
 953
 954         for (entryIndex = 0; entryIndex < blockMap[blockIndex]->nEntries; entryIndex++) {       /*f */
 955             offset =
 956                 sizeof(db.h) + (blockIndex * BLOCKSIZE) +
 957                 sizeof(struct blockHeader) + (entryIndex * entrySize);
 958             if (dbread(ut, offset, &entry[0], entrySize))
 959                 return BUDB_IO;
 960
 961             /* check if entry is free by looking at the first "afs_int32" of the structure */
 962             memcpy(&start, entry, sizeof(start));
 963             if (start == 0) {   /* zero is free */
 964                 /* Is it on any hash chain? */
 965                 if (blockMap[blockIndex]->entries[entryIndex] & MAP_HASHES) {
 966                     Log("Entry: blockindex %d, entryindex %d - marked free but hashed 0x%x\n", blockIndex, entryIndex, blockMap[blockIndex]->entries[entryIndex]);
 967                     if (BumpErrors())
 968                         return DBBAD;
 969                 }
 970
 971                 blockMap[blockIndex]->entries[entryIndex] |= MAP_FREE;
 972                 nFree++;
 973             } else {
 974                 /* check the entry itself for consistency */
 975                 code =
 976                     (*(checkEntry[type])) (ut, offset, blockIndex, entryIndex,
 977                                            &entry[0]);
 978                 if (code)
 979                     return code;
 980             }
 981         }                       /*f */
 982
 983         /* check computed free with recorded free entries */
 984         if (nFree != ntohs(blockMap[blockIndex]->header.nFree)) {
 985             Log("Block (index %d) free count %d has %d free structs\n",
 986                 blockIndex, ntohs(blockMap[blockIndex]->header.nFree), nFree);
 987             if (BumpErrors())
 988                 return DBBAD;
 989         }
 990     }                           /*f */
 991
 992     return 0;
 993 }
 994
 995
 996 afs_int32
 997 verifyFreeLists(void)
 998 {
 999     int i;
1000     afs_int32 addr;
1001     int blockIndex, entryIndex;
1002     int nFree;
1003     afs_int32 code;
1004
1005     /* for each free list */
1006     for (i = 0; i < NBLOCKTYPES; i++) {
1007         misc->fullyFree[i] = misc->freeLength[i] = 0;
1008
1009         for (addr = ntohl(db.h.freePtrs[i]); addr;
1010              addr = ntohl(blockMap[blockIndex]->header.next)) {
1011             misc->freeLength[i]++;
1012
1013             code = ConvertDiskAddress(addr, &blockIndex, &entryIndex);
1014             if (code || (entryIndex != 0)) {
1015                 Log("verifyFreeLists: Invalid free chain addr 0x%x in %s free chain\n", addr, TypeName(i));
1016                 Log("     Skipping remainder of free chain\n");
1017                 if (BumpErrors())
1018                     return (DBBAD);
1019                 break;
1020             }
1021
1022             /* check block type */
1023             if (blockMap[blockIndex]->header.type != i) {
1024                 Log("verifyFreeLists: Found %s type in %s free chain (addr 0x%x)\n",
1025                     TypeName(blockMap[blockIndex]->header.type), TypeName(i),
1026                     addr);
1027                 if (BumpErrors())
1028                     return (DBBAD);
1029             }
1030
1031             /* If entire block isn't free, check if count of free entries is ok */
1032             nFree = ntohs(blockMap[blockIndex]->header.nFree);
1033             if (i != free_BLOCK) {
1034                 if ((nFree <= 0) || (nFree > blockEntries[i])) {
1035                     Log("verifyFreeLists: Illegal free count %d on %s free chain\n", nFree, TypeName(i));
1036                     if (BumpErrors())
1037                         return (DBBAD);
1038                 } else if (nFree == blockEntries[i]) {
1039                     misc->fullyFree[i]++;
1040                 }
1041             }
1042
1043             /* Check if already examined the block */
1044             if (blockMap[blockIndex]->free) {
1045                 Log("verifyFreeLists: %s free chain block at addr 0x%x multiply threaded\n", TypeName(i), addr);
1046                 if (BumpErrors())
1047                     return DBBAD;
1048             }
1049             blockMap[blockIndex]->free++;
1050         }
1051     }
1052
1053     return 0;
1054 }
1055
1056 /* verifyMapBits
1057  *      Examines each entry to make sure it was traversed appropriately by
1058  *      checking the bits for compatibility.
1059  */
1060 afs_int32
1061 verifyMapBits(void)
1062 {
1063     int blockIndex, entryIndex, i, entrySize, type, bits;
1064     afs_int32 offset;
1065
1066     for (blockIndex = 0; blockIndex < nBlocks; blockIndex++) {
1067         /* If no entries in this block, then the block should be marked free */
1068         if ((blockMap[blockIndex]->nEntries == 0)
1069             && !blockMap[blockIndex]->free) {
1070             Log("verifyMapBits: Orphan free block (index %d)\n", blockIndex);
1071             if (BumpErrors())
1072                 return DBBAD;
1073         }
1074
1075         /* check each entry */
1076         for (entryIndex = 0; entryIndex < blockMap[blockIndex]->nEntries; entryIndex++) {       /*f */
1077 #ifndef AFS_PTHREAD_ENV
1078             if ((entryIndex % 1024) == 0)
1079                 IOMGR_Poll();
1080 #endif
1081             bits = blockMap[blockIndex]->entries[entryIndex];
1082
1083             for (i = 0; i < NMAPCs; i++)
1084                 if ((bits & mapC[i].trigger) == mapC[i].trigger)
1085                     break;
1086
1087             if (i >= NMAPCs) {
1088                 char logstr[256];
1089
1090                 type = blockMap[blockIndex]->header.type;
1091                 entrySize = blockEntrySize[type];
1092                 offset =
1093                     sizeof(db.h) + (blockIndex * BLOCKSIZE) +
1094                     sizeof(struct blockHeader) + (entryIndex * entrySize);
1095
1096                 sprintf(logstr, "%s entry Block %d, Entry %d, (addr 0x%x)",
1097                         TypeName(type), blockIndex, entryIndex, offset);
1098
1099                 if (!bits)
1100                     strcat(logstr, ": An orphaned entry");
1101                 if (bits & MAP_FREE)
1102                     strcat(logstr, ": A valid free block");
1103                 if (bits & MAP_HTBLOCK)
1104                     strcat(logstr, ": A valid hash-table block");
1105                 if (bits & MAP_TEXTBLOCK)
1106                     strcat(logstr, ": A valid text block");
1107                 if (bits & (MAP_DUMPHASH | MAP_IDHASH)) {
1108                     if (!(bits & MAP_DUMPHASH))
1109                         strcat(logstr,
1110                                ": A dump not on dump-name hash-chain");
1111                     else if (!(bits & MAP_IDHASH))
1112                         strcat(logstr, ": A dump not on dump-id hash-chain");
1113                     else
1114                         strcat(logstr, ": A valid dump entry");
1115                 }
1116                 if (bits & (MAP_TAPEHASH | MAP_TAPEONDUMP)) {
1117                     if (!(bits & MAP_TAPEHASH))
1118                         strcat(logstr,
1119                                ": A tape not on tape-name hash-chain");
1120                     else if (!(bits & MAP_TAPEONDUMP))
1121                         strcat(logstr, ": A tape not associated with a dump");
1122                     else
1123                         strcat(logstr, ": A valid tape entry");
1124                 }
1125                 if (bits & MAP_VOLINFOONNAME)
1126                     strcat(logstr,
1127                            ": A valid volInfo on a volume-name chain");
1128                 if (bits & (MAP_VOLINFONAMEHEAD | MAP_VOLHASH)) {
1129                     if (!(bits & MAP_VOLINFONAMEHEAD))
1130                         strcat(logstr,
1131                                ": A volInfo not the head of a volume-name hash-chain");
1132                     else if (!(bits & MAP_VOLHASH))
1133                         strcat(logstr,
1134                                ": A volInfo not on volume-name hash-chain");
1135                     else
1136                         strcat(logstr,
1137                                ": A valid volInfo in volume-name hash-chain");
1138                 }
1139                 if (bits & (MAP_VOLFRAGONTAPE | MAP_VOLFRAGONVOL)) {
1140                     if (!(bits & MAP_VOLFRAGONTAPE))
1141                         strcat(logstr,
1142                                ": A volFrag not associated with a tape");
1143                     else if (!(bits & MAP_VOLFRAGONVOL))
1144                         strcat(logstr,
1145                                ": A volFrag not associated with a volume");
1146                     else
1147                         strcat(logstr, ": A valid volFrag entry");
1148                 }
1149                 Log("%s\n", logstr);
1150
1151                 if (BumpErrors())
1152                     return DBBAD;
1153             }
1154         }                       /*f */
1155     }
1156
1157     return 0;
1158 }
1159
1160 afs_int32
1161 verifyText(struct ubik_trans *ut)
1162 {
1163     int i;
1164     afs_int32 code;
1165
1166     /* check each of the text types in use */
1167     for (i = 0; i < TB_NUM; i++) {
1168         Log("Verify Text: %s", textName[i]);
1169         code = verifyTextChain(ut, &db.h.textBlock[i]);
1170         if (code)
1171             return (code);
1172     }
1173     return (0);
1174 }
1175
1176 /* verifyTextChain
1177  *      check the integrity of a text chain. Also checks the new chain.
1178  */
1179 afs_int32
1180 verifyTextChain(struct ubik_trans *ut, struct textBlock *tbPtr)
1181 {
1182     dbadr blockAddr;
1183     int blockIndex, entryIndex;
1184     struct block block;
1185     afs_int32 size;
1186     int new;
1187     afs_int32 code = 0, tcode;
1188
1189     for (new = 0; new < 2; new++) {
1190         size = 0;
1191
1192         for (blockAddr =
1193              (new ? ntohl(tbPtr->newTextAddr) : ntohl(tbPtr->textAddr));
1194              blockAddr; blockAddr = ntohl(block.h.next)) {
1195             tcode = ConvertDiskAddress(blockAddr, &blockIndex, &entryIndex);
1196             if (tcode) {
1197                 Log("verifyTextChain: Invalid %s text block addr 0x%x\n",
1198                     (new ? "new" : ""), blockAddr);
1199                 Log("     Skipping remainder of text chain\n");
1200                 if (BumpErrors())
1201                     ERROR(tcode);
1202                 break;
1203             }
1204
1205             tcode = dbread(ut, blockAddr, &block, sizeof(block));
1206             if (tcode)
1207                 ERROR(tcode);
1208
1209             if (blockMap[blockIndex]->entries[entryIndex] & MAP_TEXTBLOCK) {
1210                 Log("verifyTextChain: Text block (addr 0x%x) multiply chained\n", blockAddr);
1211                 if (BumpErrors())
1212                     ERROR(DBBAD);
1213             }
1214             blockMap[blockIndex]->entries[entryIndex] |= MAP_TEXTBLOCK;
1215
1216             size += BLOCK_DATA_SIZE;
1217         }
1218
1219         if (ntohl(new ? tbPtr->newsize : tbPtr->size) > size) {
1220             Log("verifyTextChain: Text block %s size %d > computed capacity %d\n", (new ? "new" : ""), ntohl(new ? tbPtr->newsize : tbPtr->size), size);
1221             if (BumpErrors())
1222                 ERROR(DBBAD);
1223         }
1224     }
1225
1226   error_exit:
1227     return (code);
1228 }
1229
1230 /* -----------------------------------------
1231  * verification driver routines
1232  * -----------------------------------------
1233  */
1234
1235 /* verifyDatabase
1236  *      Check the integrity of the database
1237  */
1238
1239 afs_int32
1240 verifyDatabase(struct ubik_trans *ut,
1241                FILE *recreateFile)      /* not used */
1242 {
1243     afs_int32 eof;
1244     int bmsize;
1245     afs_int32 code = 0, tcode = 0;
1246
1247     extern int nBlocks;         /* no. blocks in database */
1248
1249     /* clear verification statistics */
1250     misc = &miscData;
1251     memset(&miscData, 0, sizeof(miscData));
1252
1253 #ifdef PDEBUG
1254     miscData.maxErrors = 1000000;
1255 #else
1256     miscData.maxErrors = 50;    /* Catch the first 50 errors */
1257 #endif
1258     miscData.veryLongChain = 0;
1259     miscData.checkFragCount = 1;        /* check frags */
1260
1261     /* check eofPtr */
1262     eof = ntohl(db.h.eofPtr);
1263     eof -= sizeof(db.h);        /* subtract header */
1264     nBlocks = eof / BLOCKSIZE;
1265
1266     Log("Verify of backup database started\n");
1267     Log("Database is %u. %d blocks of %d Bytes\n", eof, nBlocks, BLOCKSIZE);
1268
1269     if ((eof < 0) || (nBlocks * BLOCKSIZE != eof)) {
1270         Log("Database eofPtr (%d) bad, blocksize %d\n", eof, BLOCKSIZE);
1271         ERROR(DBBAD);
1272     }
1273
1274     /* set size of database */
1275     miscData.nBlocks = nBlocks;
1276
1277     if (nBlocks == 0)
1278         ERROR(0);               /* Nothing to check? */
1279
1280     /* construct block map - first level is the array of pointers */
1281     bmsize = nBlocks * sizeof(struct blockMap *);
1282     blockMap = calloc(1, bmsize);
1283     if (!blockMap)
1284         ERROR(BUDB_NOMEM);
1285
1286     /* verify blocks and construct the block map */
1287     Log("Read header of every block\n");
1288     tcode = verifyBlocks(ut);
1289     if (tcode)
1290         ERROR(tcode);
1291
1292     /* check the various hash tables */
1293     Log("Verify volume name hash table\n");
1294     tcode = verifyHashTable(ut, &db.volName, MAP_VOLHASH);
1295     if (tcode)
1296         ERROR(tcode);
1297
1298     Log("Verify tape name hash table\n");
1299     tcode = verifyHashTable(ut, &db.tapeName, MAP_TAPEHASH);
1300     if (tcode)
1301         ERROR(tcode);
1302
1303     Log("Verify dump name hash table\n");
1304     tcode = verifyHashTable(ut, &db.dumpName, MAP_DUMPHASH);
1305     if (tcode)
1306         ERROR(tcode);
1307
1308     Log("Verify dump id hash table\n");
1309     tcode = verifyHashTable(ut, &db.dumpIden, MAP_IDHASH);
1310     if (tcode)
1311         ERROR(tcode);
1312
1313     /* check the entry chains */
1314     Log("Verify all blocks and entries\n");
1315     tcode = verifyEntryChains(ut);
1316     if (tcode)
1317         ERROR(tcode);
1318
1319     /* check text blocks - Log message in verifyText */
1320     tcode = verifyText(ut);
1321     if (tcode)
1322         ERROR(tcode);
1323
1324     /* check free list */
1325     Log("Verify Free Lists\n");
1326     tcode = verifyFreeLists();
1327     if (tcode)
1328         ERROR(tcode);
1329
1330     /* check entry map bit compatibility */
1331
1332     Log("Verify Map bits\n");
1333     tcode = verifyMapBits();
1334     if (tcode)
1335         ERROR(tcode);
1336
1337   error_exit:
1338     /* free the block map */
1339     if (blockMap != 0) {
1340         int i;
1341
1342         /* free all the individual maps */
1343         for (i = 0; i < nBlocks; i++) {
1344             if (blockMap[i])
1345                 free(blockMap[i]);
1346         }
1347
1348         /* free the pointer array */
1349         free(blockMap);
1350         blockMap = 0;
1351     }
1352
1353     if (!tcode) {
1354         Log("# 2K database blocks    = %d\n", miscData.nBlocks);
1355         Log("# Dump entries found    = %d. 3 dumps per block\n",
1356             miscData.nDump);
1357         Log("  max tapes   on a dump = %d\n", miscData.maxTapesPerDump);
1358         Log("  max volumes on a dump = %d\n", miscData.maxVolsPerDump);
1359         Log("  max appends on a dump = %d\n", miscData.maxAppendsPerDump);
1360         Log("  # Blocks with space   = %d\n", miscData.freeLength[4]);
1361         Log("  # of those fully free = %d\n", miscData.fullyFree[4]);
1362         Log("# Tape entries found    = %d. 20 tapes per block\n",
1363             miscData.nTape);
1364         Log("  max volumes on a tape = %d\n", miscData.maxVolsPerTape);
1365         Log("  # Blocks with space   = %d\n", miscData.freeLength[3]);
1366         Log("  # of those fully free = %d\n", miscData.fullyFree[3]);
1367         Log("# VolInfo entries found = %d. 20 volInfos per block\n",
1368             miscData.nVolInfo);
1369         Log("  # head of sameNameCh  = %d\n", miscData.nVolName);
1370         Log("  max on a  sameNameCh  = %d\n", miscData.maxVolInfosPerName);
1371         Log("  max VolFrags on chain = %d\n", miscData.maxVolsPerVolInfo);
1372         Log("  # Blocks with space   = %d\n", miscData.freeLength[2]);
1373         Log("  # of those fully free = %d\n", miscData.fullyFree[2]);
1374         Log("# VolFrag entries found = %d. 45 VolFrags per block\n",
1375             miscData.nVolFrag);
1376         Log("  # Blocks with space   = %d\n", miscData.freeLength[1]);
1377         Log("  # of those fully free = %d\n", miscData.fullyFree[1]);
1378         Log("# free blocks           = %d\n", miscData.freeLength[0]);
1379     }
1380
1381     Log("Verify of database completed. %d errors found\n", miscData.errors);
1382
1383     if (miscData.errors && !code)
1384         code = DBBAD;
1385     return (code);
1386 }
1387
1388
1389 /* -----------------------------
1390  * interface routines
1391  * -----------------------------
1392  */
1393
1394 /* BUDB_DbVerify
1395  *      check the integrity of the database
1396  * exit:
1397  *      status - integrity: 0, ok; n, not ok (error value)
1398  *      orphans - no. of orphan blocks
1399  *      host - address of host that did verification
1400  */
1401 afs_int32
1402 SBUDB_DbVerify(struct rx_call *call, afs_int32 *status, afs_int32 *orphans,
1403                afs_int32 *host)
1404 {
1405     afs_int32 code;
1406
1407     code = DbVerify(call, status, orphans, host);
1408     osi_auditU(call, BUDB_DBVfyEvent, code, AUD_END);
1409     return code;
1410 }
1411
1412 afs_int32
1413 DbVerify(struct rx_call *call, afs_int32 *status, afs_int32 *orphans,
1414          afs_int32 *host)
1415 {
1416     struct ubik_trans *ut = 0;
1417     afs_int32 code = 0, tcode;
1418     char hostname[64];
1419     struct hostent *th;
1420
1421     if (callPermitted(call) == 0)
1422         ERROR(BUDB_NOTPERMITTED);
1423
1424     tcode = InitRPC(&ut, LOCKREAD, 1);
1425     if (tcode)
1426         ERROR(tcode);
1427
1428     tcode = verifyDatabase(ut, 0);      /* check the database */
1429     if (tcode)
1430         ERROR(tcode);
1431
1432   error_exit:
1433     if (ut) {
1434         if (code)
1435             ubik_AbortTrans(ut);
1436         else
1437             code = ubik_EndTrans(ut);
1438     }
1439
1440     *status = code;
1441     *orphans = 0;
1442
1443     gethostname(hostname, sizeof(hostname));
1444     th = gethostbyname(hostname);
1445     if (!th)
1446         *host = 0;
1447     else {
1448         memcpy(host, th->h_addr, sizeof(afs_int32));
1449         *host = ntohl(*host);
1450     }
1451
1452     return (0);
1453 }
1454
1455 /* ----------------------
1456  * debug support
1457  * ----------------------
1458  */
1459
1460 /* check_header
1461  *      do a simple sanity check on the database header
1462  */
1463 void
1464 check_header(char *callerst)
1465 {
1466     static int iteration_count = 0;
1467     afs_int32 eof;
1468
1469     eof = ntohl(db.h.eofPtr);
1470     if ((eof == 0) || (eof < 0)) {
1471         Log("Eof check failed, caller %s, eof 0x%x\n", callerst, eof);
1472     }
1473
1474     eof -= sizeof(db.h);
1475     if (eof < 0) {
1476         Log("Adjusted Eof check failed, caller %s, eof 0x%x\n", callerst,
1477             eof);
1478     }
1479
1480     iteration_count++;
1481     if (iteration_count >= 10) {
1482         Log("Eof ptr is 0x%x\n", eof);
1483         iteration_count = 0;
1484     }
1485 }