src/budb/ol_verify.c

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