2 * Copyright 2000, International Business Machines Corporation and others.
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
10 /* ol_verify - online database verification */
12 #include <afsconfig.h>
13 #include <afs/param.h>
21 #include <netinet/in.h>
32 #include <sys/types.h>
36 #include "error_macros.h"
37 #include "budb_errs.h"
38 #include <afs/cellconfig.h>
39 #include "afs/audit.h"
45 * 1) volInfo structures refering to a volume of the same name are
46 * chained together, i.e. the volumes described differ in volid, partition
47 * etc. The structure at the head of this list (the sameNameChain) is
48 * treated specially. When a delete volInfo request is processed, heads
49 * are not deleted unless all other items on the sameNameChain are gone.
51 * The result is that volInfo (head) structures may be present
52 * even if no tape structures refer to them. These structures are
53 * unreachable in a top-down tree walk.
55 * 1) make the verify tolerant of errors. Want to get a summary statistic
56 * indicating how may dumps are lost and how many text blocks lost
57 * 2) Make the recreation instructions write out whatever is good. This
58 * is only for the off-line case.
61 /* flags associated with each structure. These are set and checked in
62 * the blockMap entries
65 #define MAP_DUMPHASH 1 /* dump name hash checked */
66 #define MAP_TAPEHASH 2 /* tape name hash checked */
67 #define MAP_VOLHASH 4 /* volume name hash checked */
68 #define MAP_IDHASH 8 /* dump id hash checked */
70 #define MAP_HASHES (MAP_DUMPHASH | MAP_TAPEHASH | MAP_VOLHASH | MAP_IDHASH)
72 #define MAP_FREE 0x10 /* item is free */
73 #define MAP_RECREATE 0x20
74 #define MAP_HTBLOCK 0x40 /* hash table block */
75 #define MAP_TAPEONDUMP 0x100
76 #define MAP_VOLFRAGONTAPE 0x200
77 #define MAP_VOLFRAGONVOL 0x400
78 #define MAP_VOLINFOONNAME 0x800
79 #define MAP_VOLINFONAMEHEAD 0x1000
80 #define MAP_TEXTBLOCK 0x2000 /* block of text */
81 #define MAP_APPENDEDDUMP 0x4000
83 /* one blockMap for every block in the database. Each element of the entries
84 * array describes the status of a data structure/entry in that block
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 */
95 /* status for verify call */
98 char hostname[64]; /* host on which checked */
99 afs_int32 status; /* ok, not ok */
102 int nBlocks; /* total number of blocks in db */
104 struct misc_hash_stats { /* stats for hashing */
105 int max; /* longest chain length */
106 double avg; /* avg length */
107 double std_dev; /* standard deviation of length */
111 int errors; /* errors encountered */
112 int maxErrors; /* abort after this many errors */
113 int nBlocks; /* number of database blocks */
114 int nDump, nTape, nVolInfo, nVolFrag; /* counts of each type */
115 int nVolName; /* volInfos w/ head==0 */
116 int maxVolsPerVolInfo; /* maximum list lengths */
119 int maxVolInfosPerName;
121 int maxAppendsPerDump;
122 int freeLength[NBLOCKTYPES]; /* length of free lists */
123 int fullyFree[NBLOCKTYPES]; /* free blocks full of free entries */
124 int veryLongChain; /* length of chain to report */
125 int checkFragCount; /* report fragment count errors */
126 struct misc_hash_stats dumpName, dumpIden, tapeName, volName;
127 FILE *recreate; /* stream for recreate instructions */
129 struct misc_data *misc;
131 struct blockMap **blockMap = 0; /* initial block map */
133 /* describes number of entries for each type of block */
135 int blockEntries[NBLOCKTYPES] =
142 1, /* hashTable_BLOCK */
146 int blockEntrySize[NBLOCKTYPES] =
149 sizeof(((struct vfBlock *)NULL)->a[0]),
150 sizeof(((struct viBlock *)NULL)->a[0]),
151 sizeof(((struct tBlock *)NULL)->a[0]),
152 sizeof(((struct dBlock *)NULL)->a[0]),
155 char *typeName[NBLOCKTYPES] =
165 int hashBlockType[HT_MAX_FUNCTION+1] =
174 /* Compatibility table for the bits in the blockMap. */
176 struct mapCompatability
178 short trigger; /* these bits trigger this element */
183 MAP_DUMPHASH | MAP_IDHASH,
184 MAP_TAPEHASH | MAP_TAPEONDUMP,
186 MAP_VOLINFONAMEHEAD | MAP_VOLHASH,
187 MAP_VOLFRAGONTAPE | MAP_VOLFRAGONVOL,
191 /* no. of entries in the mapC array */
192 int NMAPCs = (sizeof(mapC)/sizeof(mapC[0]));
194 /* for identifying stored textual information */
196 char *textName[TB_NUM] =
203 extern int sizeFunctions[];
204 extern int nHTBuckets;
206 #define DBBAD BUDB_DATABASEINCONSISTENT
208 /* ------------------------------------
209 * supporting routines
210 * ------------------------------------
214 * increment the error count
217 * 1 - maximum errors exceeded
223 if ( ++miscData.errors >= miscData.maxErrors )
229 /* convertDiskAddress
230 * given a disk address, break it down into a block and entry index. These
231 * permit access to the block map information. The conversion process
232 * compares the supplied address with the alignment/type information
233 * stored in the block map.
236 * BUDB_ADDR - address alignment checks failed
240 checkDiskAddress(address, type, blockIndexPtr, entryIndexPtr)
241 unsigned long address;
248 if (blockIndexPtr) *blockIndexPtr = -1;
249 if (entryIndexPtr) *entryIndexPtr = -1;
251 /* This is safest way to handle totally bogus addresses (eg 0x80001234). */
252 if ( (address < sizeof(db.h)) || (address >= ntohl(db.h.eofPtr)) )
255 address -= sizeof(db.h);
256 index = address / BLOCKSIZE;
257 offset = address - (index * BLOCKSIZE);
258 if (offset % sizeof(afs_int32)) /* alignment check */
260 if (offset && (type > 0) && (type <= MAX_STRUCTURE_BLOCK_TYPE))
262 offset -= sizeof(struct blockHeader);
263 if ((offset < 0) || (offset % blockEntrySize[type]))
265 offset /= blockEntrySize[type];
266 if (offset >= blockEntries[type])
269 if (blockIndexPtr) *blockIndexPtr = index;
270 if (entryIndexPtr) *entryIndexPtr = offset;
274 /* ConvertDiskAddress
275 * given a disk address, break it down into a block and entry index. These
276 * permit access to the block map information. The conversion process
277 * compares the supplied address with the alignment/type information
278 * stored in the block map.
281 * BUDB_ADDR - address alignment checks failed
285 ConvertDiskAddress(address, blockIndexPtr, entryIndexPtr)
293 index = (address - sizeof(db.h)) / BLOCKSIZE;
294 type = blockMap[index]->header.type;
296 code = checkDiskAddress(address, type, blockIndexPtr, entryIndexPtr);
304 static char error[16];
306 if ( (index < 0) || (index >= NBLOCKTYPES))
308 sprintf(error, "UNKNOWN_TYPE", index);
311 return(typeName[index]);
314 getDumpID(ut, tapePtr, dumpID)
315 struct tape *tapePtr;
322 code = dbread(ut, ntohl(tapePtr->dump), &d, sizeof(d));
324 *dumpID = ntohl(d.id);
327 /* ------------------------------------
328 * verification routines - structure specific
329 * ------------------------------------
333 * Follow the tapes entries hanging off of a dump and verify they belong
337 verifyDumpEntry( ut, dumpAddr, ai, ao, dumpPtr)
338 struct ubik_trans *ut;
341 struct dump *dumpPtr;
344 afs_int32 tapeAddr, tapeCount=0, volCount=0, appDumpCount=0;
345 afs_int32 appDumpAddr, appDumpIndex, appDumpOffset;
347 int tapeIndex, tapeOffset, ccheck=1;
348 afs_int32 code = 0, tcode;
349 int dumpIndex, dumpOffset;
351 tcode = ConvertDiskAddress(dumpAddr, &dumpIndex, &dumpOffset);
354 Log("verifyDumpEntry: Invalid dump entry addr 0x%x\n", dumpAddr);
355 if (BumpErrors()) ERROR(DBBAD);
359 /* Step though list of tapes hanging off of this dump */
360 for (tapeAddr=ntohl(dumpPtr->firstTape); tapeAddr; tapeAddr=ntohl(tape.nextTape))
362 tcode = ConvertDiskAddress(tapeAddr, &tapeIndex, &tapeOffset);
365 Log("verifyDumpEntry: Invalid tape entry addr 0x%x (on DumpID %u)\n",
366 tapeAddr, ntohl(dumpPtr->id));
367 Log(" Skipping remainder of tapes in dump\n");
368 if (BumpErrors()) ERROR(DBBAD);
373 tcode = dbread(ut, tapeAddr, &tape, sizeof(tape));
374 if (tcode) ERROR(BUDB_IO);
376 if ( ntohl(tape.dump) != dumpAddr )
380 getDumpID(ut, &tape, &did);
381 Log("verifyDumpEntry: Tape '%s' (addr 0x%x) doesn't point to\n",
382 tape.name, tapeAddr);
383 Log(" dumpID %u (addr 0x%x). Points to DumpID %u (addr 0x%x)\n",
384 ntohl(dumpPtr->id), dumpAddr, did, ntohl(tape.dump));
385 if (BumpErrors()) return(DBBAD);
388 /* Check if this tape entry has been examine already */
389 if ( blockMap[tapeIndex]->entries[tapeOffset] & MAP_TAPEONDUMP )
391 Log("verifyDumpEntry: Tape '%s' (addr 0x%x) on multiple dumps\n",
392 tape.name, tapeAddr);
393 if (BumpErrors()) return(DBBAD);
395 blockMap[tapeIndex]->entries[tapeOffset] |= MAP_TAPEONDUMP;
398 volCount += ntohl(tape.nVolumes);
401 if (ccheck && (ntohl(dumpPtr->nVolumes) != volCount))
403 Log("verifyDumpEntry: DumpID %u (addr 0x%x) volume count of %d is wrong (should be %d)\n",
404 ntohl(dumpPtr->id), dumpAddr, ntohl(dumpPtr->nVolumes), volCount);
405 if (BumpErrors()) return(DBBAD);
408 if (volCount > misc->maxVolsPerDump) misc->maxVolsPerDump = volCount;
409 if (tapeCount > misc->maxTapesPerDump) misc->maxTapesPerDump = tapeCount;
411 /* If this is an initial dump, then step though list of appended dumps
412 * hanging off of this dump.
414 if (ntohl(dumpPtr->initialDumpID) == 0) {
415 for (appDumpAddr=ntohl(dumpPtr->appendedDumpChain); appDumpAddr;
416 appDumpAddr=ntohl(appDump.appendedDumpChain)) {
418 tcode = ConvertDiskAddress(appDumpAddr, &appDumpIndex, &appDumpOffset);
420 Log("verifyDumpEntry: Invalid appended dump entry addr 0x%x\n", appDumpAddr);
421 Log("Skipping remainder of appended dumps\n");
422 if (BumpErrors()) ERROR(DBBAD);
426 /* Read the appended dump in */
427 tcode = dbread(ut, appDumpAddr, &appDump, sizeof(appDump));
428 if (tcode) ERROR(BUDB_IO);
430 /* Verify that it points to the parent dump */
431 if (ntohl(appDump.initialDumpID) != ntohl(dumpPtr->id)) {
432 Log("verifyDumpEntry: DumpID %u (addr 0x%x) initial DumpID incorrect (is %u, should be %u)\n",
433 ntohl(appDump.id), appDumpAddr,
434 ntohl(appDump.initialDumpID), ntohl(dumpPtr->id));
435 if (BumpErrors()) return(DBBAD);
438 /* Check if this appended dump entry has been examined already */
439 if ( blockMap[appDumpIndex]->entries[appDumpOffset] & MAP_APPENDEDDUMP ) {
440 Log("verifyDumpEntry: DumpID %u (addr %u) is on multiple appended dump chains\n",
441 ntohl(appDump.id), appDumpAddr);
442 Log("Skipping remainder of appended dumps\n");
443 if (BumpErrors()) return(DBBAD);
446 blockMap[appDumpIndex]->entries[appDumpOffset] |= MAP_APPENDEDDUMP;
452 if (appDumpCount > misc->maxAppendsPerDump) misc->maxAppendsPerDump = appDumpCount;
461 * Follw the volume fragments hanging off of a tape entry and verify
462 * they belong to the tape.
465 verifyTapeEntry (ut, tapeAddr, ai, ao, tapePtr)
466 struct ubik_trans *ut;
469 struct tape *tapePtr;
471 int volCount = 0, ccheck=1;
472 afs_int32 volFragAddr;
473 int blockIndex, entryIndex;
474 struct volFragment volFragment;
475 afs_int32 code = 0, tcode;
477 for (volFragAddr=ntohl(tapePtr->firstVol);
479 volFragAddr=ntohl(volFragment.sameTapeChain))
481 tcode = ConvertDiskAddress(volFragAddr, &blockIndex, &entryIndex);
486 getDumpID(ut, tapePtr, &did);
487 Log("verifyTapeEntry: Invalid volFrag addr 0x%x (on tape '%s' DumpID %u)\n",
488 volFragAddr, tapePtr->name, did);
489 Log(" Skipping remainder of volumes on tape\n");
490 if (BumpErrors()) ERROR(DBBAD);
495 tcode = dbread (ut, volFragAddr, &volFragment, sizeof(volFragment));
496 if (tcode) ERROR(tcode);
498 if ( ntohl(volFragment.tape) != tapeAddr )
502 getDumpID(ut, tapePtr, &did);
503 Log("verifyTapeEntry: VolFrag (addr 0x%x) doesn't point to \n",
505 Log (" tape '%s' DumpID %u (addr 0x%x). Points to addr 0x%x\n",
506 tapePtr->name, did, tapeAddr, ntohl(volFragment.tape));
507 if (BumpErrors()) ERROR(DBBAD);
510 /* Has this volume fragment already been examined */
511 if ( blockMap[blockIndex]->entries[entryIndex] & MAP_VOLFRAGONTAPE )
513 Log("verifyTapeEntry: VolFrag (addr %d) on multiple tapes\n",
515 if (BumpErrors()) ERROR(DBBAD);
517 blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLFRAGONTAPE;
522 /* now check computed vs. recorded volume counts */
523 if (ccheck && (ntohl(tapePtr->nVolumes) != volCount))
527 getDumpID(ut, tapePtr, &did);
528 Log("verifyTapeEntry: Tape '%s' DumpID %u (addr 0x%x) volFrag count of %d is wrong (should be %d)\n",
529 tapePtr->name, did, tapeAddr, ntohl(tapePtr->nVolumes), volCount);
530 if (BumpErrors()) ERROR(DBBAD);
533 if (volCount > misc->maxVolsPerTape) misc->maxVolsPerTape = volCount;
542 * volume fragments are the lowest leaf describing a dump (nothing hangs off of it).
543 * So no check is done agaist it.
546 verifyVolFragEntry (ut, va, ai, ao, v)
547 struct ubik_trans *ut;
550 struct volFragment *v;
556 /* verifyVolInfoEntry
557 * Follow the volume fragments hanging off of a volinfo structure and
558 * verify they belong to the volinfo structure.
559 * If the volinfo structure is at the head of the same name chain, then
560 * also verify all entries are also on the chain.
563 verifyVolInfoEntry (ut, volInfoAddr, ai, ao, volInfo)
564 struct ubik_trans *ut;
565 afs_int32 volInfoAddr;
567 struct volInfo *volInfo;
569 int volCount = 0, ccheck=1;
571 afs_int32 volFragAddr;
572 int blockIndex, entryIndex, bindex, eindex;
573 struct volFragment volFragment;
574 afs_int32 code = 0, tcode;
576 /* check each fragment attached to this volinfo structure */
577 for (volFragAddr=ntohl(volInfo->firstFragment); volFragAddr;
578 volFragAddr=ntohl(volFragment.sameNameChain))
580 tcode = ConvertDiskAddress (volFragAddr, &blockIndex, &entryIndex);
583 Log("verifyVolInfoEntry: Invalid volFrag entry addr 0x%x (on volume '%s')\n",
584 volFragAddr, volInfo->name);
585 Log(" Skipping remainder of volumes on tape\n");
586 if (BumpErrors()) ERROR(DBBAD);
591 tcode = dbread(ut, volFragAddr, &volFragment, sizeof(volFragment));
592 if (tcode) ERROR(tcode);
594 if ( ntohl(volFragment.vol) != volInfoAddr )
596 Log("verifyVolInfoEntry: volFrag (addr 0x%x) doesn't point to \n",
598 Log(" volInfo '%s' (addr 0x%x). Points to addr 0x%x\n",
599 volInfo->name, volInfoAddr, ntohl(volFragment.vol));
600 if (BumpErrors()) ERROR(DBBAD);
603 /* volume fragment already on a volinfo chain? */
604 if ( blockMap[blockIndex]->entries[entryIndex] & MAP_VOLFRAGONVOL )
606 Log("verifyVolInfoEntry: VolFrag (addr %d) on multiple volInfo chains\n",
608 if (BumpErrors()) ERROR(DBBAD);
610 blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLFRAGONVOL;
615 /* check computed vs. recorded number of fragments */
616 if (ccheck && misc->checkFragCount && (ntohl(volInfo->nFrags) != volCount))
618 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) volFrag count of %d is wrong (should be %d)\n",
619 volInfo->name, volInfoAddr, ntohl(volInfo->nFrags), volCount);
620 if (BumpErrors()) ERROR(DBBAD);
623 if (volCount > misc->maxVolsPerVolInfo) misc->maxVolsPerVolInfo = volCount;
625 /* Check that all volInfo structures with same name point to the same
626 * head. If sameNameHead == 0, this is the head structure so we check,
629 if (volInfo->sameNameHead == 0)
631 int viCount = 1; /* count this one */
635 for (tviAddr=ntohl(volInfo->sameNameChain); tviAddr; tviAddr = ntohl(tvi.sameNameChain))
638 tcode = ConvertDiskAddress (tviAddr, &blockIndex, &entryIndex);
641 Log("verifyVolInfoEntry: Invalid volInfo entry %s addr 0x%x\n",
642 volInfo->name, tviAddr);
643 Log(" Skipping remainder of volumes on same name chain\n");
644 if (BumpErrors()) ERROR(DBBAD);
649 tcode = dbread(ut, tviAddr, &tvi, sizeof(tvi));
650 if (tcode) ERROR(tcode);
652 if ( ntohl(tvi.sameNameHead) != volInfoAddr)
654 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) doesn't point to \n",
655 volInfo->name, tviAddr);
656 Log(" head of sameName volInfo (addr 0x%x). Points to addr 0x%x\n",
657 volInfoAddr, ntohl(tvi.sameNameHead));
658 if (BumpErrors()) ERROR(DBBAD);
661 if (blockMap[blockIndex]->entries[entryIndex] & MAP_VOLINFOONNAME)
663 Log("verifyVolInfoEntry: VolInfo (addr 0x%x) on multiple same name chains\n",
665 if (BumpErrors()) ERROR(DBBAD);
667 blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLINFOONNAME;
670 /* select the passed in structure flags */
671 if ( blockMap[ai]->entries[ao] & MAP_VOLINFONAMEHEAD)
673 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) is name head multiple times\n",
674 volInfo->name, volInfoAddr);
675 if (BumpErrors()) ERROR(DBBAD);
677 blockMap[ai]->entries[ao] |= MAP_VOLINFONAMEHEAD;
679 if (viCount > misc->maxVolInfosPerName) misc->maxVolInfosPerName = viCount;
690 /* ------------------------------------
691 * verification routines - general
692 * ------------------------------------
696 * Read each block header of every 2K block and remember it in our global
697 * blockMap array. Also check that the type of block is good.
701 struct ubik_trans *ut;
706 struct blockMap *ablockMap = 0;
709 afs_int32 code = 0, tcode;
711 /* Remember every header of every block in the database */
712 for (i=0; i<nBlocks; i++)
714 /* To avoid the call from timing out, do a poll every 256 blocks */
716 /* read the block header */
717 blockAddr = sizeof(db.h) + (i * BLOCKSIZE);
718 tcode = dbread(ut, blockAddr, (char *) &block.h, sizeof(block.h));
719 if (tcode) ERROR(tcode);
721 /* check the block type */
722 blocktype = block.h.type; /* char */
723 if ( (blocktype < 0) || (blocktype >= NBLOCKTYPES) )
725 Log("Block (index %d addr %d) has invalid type of %d\n", i, blockAddr, blocktype);
726 ERROR(BUDB_BLOCKTYPE);
729 /* allocate the block map memory */
730 bmsize = sizeof(*ablockMap) + (blockEntries[blocktype]-1) * sizeof(ablockMap->entries[0]);
731 ablockMap = (struct blockMap *) malloc(bmsize);
732 if (!ablockMap) ERROR(BUDB_NOMEM);
733 memset(ablockMap, 0, bmsize);
735 ablockMap->nEntries = blockEntries[blocktype];
737 /* save the block header in the block map */
738 memcpy(&ablockMap->header, &block.h, sizeof(ablockMap->header));
739 blockMap[i] = ablockMap;
746 int minvols, maxvols, ttlvols;
748 /* verifyHashTableBlock
749 * Take a 2K hash table block and traverse its entries. Make sure each entry
750 * is of the correct type for the hash table, is hashed into the correct
751 * entry and is not threaded on multiple lists.
754 verifyHashTableBlock(ut, mhtPtr, htBlockPtr, old, length, index, mapBit)
755 struct ubik_trans *ut;
756 struct memoryHashTable *mhtPtr;
757 struct htBlock *htBlockPtr;
759 afs_int32 length; /* size of whole hash table */
760 int index; /* base index of this block */
763 int type; /* hash table type */
764 int entrySize; /* hashed entry size */
765 int blockType; /* block type for this hash table */
766 int blockIndex, entryIndex;
767 char entry[sizeof(struct block)];
769 int hash; /* calculated hash value for entry */
771 afs_int32 code = 0, tcode;
773 type = ntohl(mhtPtr->ht->functionType);
774 entrySize = sizeFunctions[type];
775 blockType = hashBlockType[type];
777 /* step through this hash table block, being careful to stop
778 * before the end of the overall hash table
781 for ( i = 0; (i < nHTBuckets) && (index < length); i++, index++ )
783 entryAddr = ntohl(htBlockPtr->bucket[i]);
785 /* if this is the old hash table, all entries below the progress mark
786 * should have been moved to the new hash table
788 if (old && (index < mhtPtr->progress) && entryAddr)
790 Log("Old hash table not empty (entry %d) below progress (%d)\n",
791 i, mhtPtr->progress);
792 if (BumpErrors()) ERROR(DBBAD);
795 /* now walk down the chain of each bucket */
796 for (count=0; entryAddr; count++)
798 tcode = ConvertDiskAddress(entryAddr, &blockIndex, &entryIndex);
801 Log("verifyHashTableBlock: Invalid hash table chain addr 0x%x\n", entryAddr);
802 Log(" Skipping remainder of bucket %d\n", index);
803 if (BumpErrors()) ERROR(DBBAD);
808 if (blockMap[blockIndex]->header.type != blockType)
810 Log("Hash table chain (block index %d) incorrect\n", blockIndex);
811 Log(" Table type %d traverses block type %d\n",
812 blockType, blockMap[blockIndex]->header.type);
813 Log(" Skipping remainder of bucket %d\n", index);
814 if (BumpErrors()) ERROR(DBBAD);
818 if ( dbread(ut, entryAddr, &entry[0], entrySize) )
821 hash = ht_HashEntry(mhtPtr, &entry[0]) % length;
822 if (hash != index) /* if it hashed to some other place */
824 Log("Entry (addr 0x%x) bucket %d, should be hashed into bucket %d\n",
825 entryAddr, index, hash);
826 if (BumpErrors()) ERROR(DBBAD);
829 /* check if entry has been examined */
830 if (blockMap[blockIndex]->entries[entryIndex] & mapBit)
832 Log("Entry (addr 0x%x) multiply referenced\n", entryAddr);
833 if (BumpErrors()) ERROR(DBBAD);
835 blockMap[blockIndex]->entries[entryIndex] |= mapBit;
837 entryAddr = ntohl( *((dbadr *)(entry + mhtPtr->threadOffset)));
840 /* Log("Bucket %4d contains %d entries\n", index+1, count); */
842 if (count < minvols) minvols = count;
843 if (count > maxvols) maxvols = count;
851 * Read each 2K block a hashtable has (both its old hastable and
852 * new hashtable) and verify the block has not been read before.
853 * Will also make call to verify entries within each 2K block of
857 verifyHashTable(ut, mhtPtr, mapBit)
858 struct ubik_trans *ut;
859 struct memoryHashTable *mhtPtr;
862 struct hashTable *htPtr = mhtPtr->ht;
864 struct htBlock hashTableBlock;
865 int tableLength; /* # entries */
866 int hashblocks; /* # blocks */
867 dbadr tableAddr; /* disk addr of hash block */
868 int blockIndex, entryIndex;
871 afs_int32 code = 0, tcode;
873 extern int nHTBuckets; /* # buckets in a hash table */
875 LogDebug(4, "Htable: length %d oldlength %d progress %d\n",
876 mhtPtr->length, mhtPtr->oldLength, mhtPtr->progress);
878 /* check both old and current tables */
879 for ( old = 0; old <= 1; old++ )
881 tableLength = (old ? mhtPtr->oldLength : mhtPtr->length);
882 if (tableLength == 0) continue;
883 tableAddr = (old ? ntohl(htPtr->oldTable) : ntohl(htPtr->table));
885 maxvols = ttlvols = 0;
887 /* follow the chain of hashtable blocks - avoid infinite loops */
888 hashblocks = ((tableLength-1)/nHTBuckets)+1; /* numb of 2K hashtable blocks */
889 for (i=0; (tableAddr && (i<hashblocks+5)); i++)
891 tcode = ConvertDiskAddress(tableAddr, &blockIndex, &entryIndex);
894 Log("verifyHashTable: Invalid hash table chain addr 0x%x\n", tableAddr);
895 Log(" Skipping remainder of hash table chain\n");
896 if (BumpErrors()) return(DBBAD);
901 if ( blockMap[blockIndex]->header.type != hashTable_BLOCK )
903 Log("Hashtable block (index %d addr 0x%x) hashtype %d - type %d, expected type %d\n",
904 i+1, tableAddr, ntohl(htPtr->functionType),
905 blockMap[blockIndex]->header.type, hashTable_BLOCK);
906 Log(" Skipping remainder of hash table chain\n");
907 if (BumpErrors()) ERROR(BUDB_BLOCKTYPE);
911 /* check if we've examined this block before */
912 /* mark this (hash table) block as examined */
913 if (blockMap[blockIndex]->entries[entryIndex] & MAP_HTBLOCK)
915 Log("Hash table block (index %d addr 0x%x) multiple ref\n", i+1, tableAddr);
916 if (BumpErrors()) ERROR(BUDB_DATABASEINCONSISTENT);
918 blockMap[blockIndex]->entries[entryIndex] |= MAP_HTBLOCK;
920 /* Read the actual hash table block */
921 tcode = dbread(ut, tableAddr, &hashTableBlock, sizeof(hashTableBlock));
922 if (tcode) ERROR(tcode);
924 /* Verify its entries */
925 tcode = verifyHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
926 tableLength, (i*nHTBuckets), mapBit);
927 if (tcode) ERROR(tcode);
929 tableAddr = ntohl(hashTableBlock.h.next);
932 /* Verify numb hash blocks is as it says */
935 Log("Incorrect number of hash chain blocks: %d (expected %d), hashtype %d\n",
936 i, hashblocks, ntohl(htPtr->functionType));
937 if (BumpErrors()) ERROR(BUDB_DATABASEINCONSISTENT);
941 Log("%d entries; %u buckets; min = %d; max = %d\n",
942 ttlvols, tableLength, minvols, maxvols);
950 * do a linear walk of all the blocks. Check each block of structures
951 * to see if the actual free matches the recorded free. Also check
952 * the integrity of each allocated structure.
955 verifyEntryChains(ut)
956 struct ubik_trans *ut;
960 int blockIndex, entryIndex;
961 char entry[sizeof(struct block)];
966 static afs_int32 (*checkEntry[NBLOCKTYPES])()
967 = { 0, /* free block */
975 for (blockIndex=0; blockIndex<nBlocks; blockIndex++)
977 /* ignore non-structure or blocks with invalid type */
978 type = blockMap[blockIndex]->header.type;
979 if ((type <= 0) || (type > MAX_STRUCTURE_BLOCK_TYPE))
982 entrySize = blockEntrySize[type];
985 for (entryIndex=0; entryIndex<blockMap[blockIndex]->nEntries; entryIndex++)
987 offset = sizeof(db.h) + (blockIndex * BLOCKSIZE) +
988 sizeof(struct blockHeader) + (entryIndex * entrySize);
989 if ( dbread(ut, offset, &entry[0], entrySize) )
992 /* check if entry is free by looking at the first "afs_int32" of the structure */
993 if ( *((afs_int32 *)&entry[0]) == 0 ) /* zero is free */
995 /* Is it on any hash chain? */
996 if ( blockMap[blockIndex]->entries[entryIndex] & MAP_HASHES )
998 Log("Entry: blockindex %d, entryindex %d - marked free but hashed 0x%x\n",
999 blockIndex, entryIndex, blockMap[blockIndex]->entries[entryIndex]);
1000 if (BumpErrors()) return DBBAD;
1003 blockMap[blockIndex]->entries[entryIndex] |= MAP_FREE;
1008 /* check the entry itself for consistency */
1009 code = (*(checkEntry[type]))(ut, offset, blockIndex, entryIndex, &entry[0]);
1010 if (code) return code;
1014 /* check computed free with recorded free entries */
1015 if ( nFree != ntohs(blockMap[blockIndex]->header.nFree) )
1017 Log("Block (index %d) free count %d has %d free structs\n",
1018 blockIndex, ntohs(blockMap[blockIndex]->header.nFree), nFree);
1019 if (BumpErrors()) return DBBAD;
1032 int blockIndex, entryIndex;
1036 /* for each free list */
1037 for (i=0; i<NBLOCKTYPES; i++)
1039 misc->fullyFree[i] = misc->freeLength[i] = 0;
1041 for (addr=ntohl(db.h.freePtrs[i]); addr; addr=ntohl(blockMap[blockIndex]->header.next))
1043 misc->freeLength[i]++;
1045 code = ConvertDiskAddress (addr, &blockIndex, &entryIndex);
1046 if (code || (entryIndex != 0))
1048 Log("verifyFreeLists: Invalid free chain addr 0x%x in %s free chain\n",
1050 Log(" Skipping remainder of free chain\n");
1051 if (BumpErrors()) return(DBBAD);
1056 /* check block type */
1057 if (blockMap[blockIndex]->header.type != i)
1059 Log("verifyFreeLists: Found %s type in %s free chain\n",
1060 TypeName(blockMap[blockIndex]->header.type), TypeName(i), addr);
1061 if (BumpErrors()) return(DBBAD);
1064 /* If entire block isn't free, check if count of free entries is ok */
1065 nFree = ntohs(blockMap[blockIndex]->header.nFree);
1066 if (i != free_BLOCK)
1068 if ((nFree <= 0) || (nFree > blockEntries[i]))
1070 Log ("verifyFreeLists: Illegal free count %d on %s free chain\n",
1071 nFree, TypeName(i));
1072 if (BumpErrors()) return(DBBAD);
1074 else if (nFree == blockEntries[i])
1076 misc->fullyFree[i]++;
1080 /* Check if already examined the block */
1081 if (blockMap[blockIndex]->free)
1083 Log("verifyFreeLists: %s free chain block at addr 0x%x multiply threaded\n",
1085 if (BumpErrors()) return DBBAD;
1087 blockMap[blockIndex]->free++;
1095 * Examines each entry to make sure it was traversed appropriately by
1096 * checking the bits for compatibility.
1101 int blockIndex, entryIndex, i, entrySize, type, bits;
1104 for (blockIndex=0; blockIndex<nBlocks; blockIndex++)
1106 /* If no entries in this block, then the block should be marked free */
1107 if ((blockMap[blockIndex]->nEntries == 0) && !blockMap[blockIndex]->free)
1109 Log("verifyMapBits: Orphan free block (index %d)\n", blockIndex);
1110 if (BumpErrors()) return DBBAD;
1113 /* check each entry */
1114 for (entryIndex=0; entryIndex<blockMap[blockIndex]->nEntries; entryIndex++)
1116 if ((entryIndex%1024) == 0) IOMGR_Poll();
1118 bits = blockMap[blockIndex]->entries[entryIndex];
1120 for (i=0; i<NMAPCs; i++)
1121 if ((bits & mapC[i].trigger) == mapC[i].trigger) break;
1127 type = blockMap[blockIndex]->header.type;
1128 entrySize = blockEntrySize[type];
1129 offset = sizeof(db.h) + (blockIndex * BLOCKSIZE) +
1130 sizeof(struct blockHeader) + (entryIndex * entrySize);
1132 sprintf(logstr, "%s entry Block %d, Entry %d, (addr 0x%x)",
1133 TypeName(type), blockIndex, entryIndex, offset);
1135 if (!bits) strcat(logstr, ": An orphaned entry");
1136 if (bits & MAP_FREE) strcat(logstr, ": A valid free block");
1137 if (bits & MAP_HTBLOCK) strcat(logstr, ": A valid hash-table block");
1138 if (bits & MAP_TEXTBLOCK) strcat(logstr, ": A valid text block");
1139 if (bits & (MAP_DUMPHASH | MAP_IDHASH))
1141 if (!(bits & MAP_DUMPHASH))
1142 strcat(logstr, ": A dump not on dump-name hash-chain");
1143 else if (!(bits & MAP_IDHASH))
1144 strcat(logstr, ": A dump not on dump-id hash-chain");
1146 strcat(logstr, ": A valid dump entry");
1148 if (bits & (MAP_TAPEHASH | MAP_TAPEONDUMP))
1150 if (!(bits & MAP_TAPEHASH))
1151 strcat(logstr, ": A tape not on tape-name hash-chain");
1152 else if (!(bits & MAP_TAPEONDUMP))
1153 strcat(logstr, ": A tape not associated with a dump");
1155 strcat(logstr, ": A valid tape entry");
1157 if (bits & MAP_VOLINFOONNAME)
1158 strcat(logstr, ": A valid volInfo on a volume-name chain");
1159 if (bits & (MAP_VOLINFONAMEHEAD | MAP_VOLHASH))
1161 if (!(bits & MAP_VOLINFONAMEHEAD))
1162 strcat(logstr, ": A volInfo not the head of a volume-name hash-chain");
1163 else if (!(bits & MAP_VOLHASH))
1164 strcat(logstr, ": A volInfo not on volume-name hash-chain");
1166 strcat(logstr, ": A valid volInfo in volume-name hash-chain");
1168 if (bits & (MAP_VOLFRAGONTAPE | MAP_VOLFRAGONVOL))
1170 if (!(bits & MAP_VOLFRAGONTAPE))
1171 strcat(logstr, ": A volFrag not associated with a tape");
1172 else if (!(bits & MAP_VOLFRAGONVOL))
1173 strcat(logstr, ": A volFrag not associated with a volume");
1175 strcat(logstr, ": A valid volFrag entry");
1177 Log("%s\n", logstr);
1179 if (BumpErrors()) return DBBAD;
1189 struct ubik_trans *ut;
1193 extern afs_int32 verifyTextChain();
1195 /* check each of the text types in use */
1196 for (i=0; i<TB_NUM; i++)
1198 Log("Verify Text: %s", textName[i]);
1199 code = verifyTextChain(ut, &db.h.textBlock[i]);
1200 if (code) return(code);
1206 * check the integrity of a text chain. Also checks the new chain.
1209 verifyTextChain(ut, tbPtr)
1210 struct ubik_trans *ut;
1211 struct textBlock *tbPtr;
1214 int blockIndex, entryIndex;
1218 afs_int32 code = 0, tcode;
1220 for (new=0; new<2; new++)
1223 blockAddr = ntohl(tbPtr->textAddr);
1225 for (blockAddr = (new ? ntohl(tbPtr->newTextAddr) : ntohl(tbPtr->textAddr));
1226 blockAddr; blockAddr = ntohl(block.h.next))
1228 tcode = ConvertDiskAddress(blockAddr, &blockIndex, &entryIndex);
1231 Log("verifyTextChain: Invalid %s text block addr 0x%x\n",
1232 (new?"new":""), blockAddr);
1233 Log(" Skipping remainder of text chain\n");
1234 if (BumpErrors()) ERROR(tcode);
1238 tcode = dbread(ut, blockAddr, &block, sizeof(block));
1239 if (tcode) ERROR(tcode);
1241 if ( blockMap[blockIndex]->entries[entryIndex] & MAP_TEXTBLOCK )
1243 Log("verifyTextChain: Text block (addr 0x%x) multiply chained\n", blockAddr);
1244 if (BumpErrors()) ERROR(DBBAD);
1246 blockMap[blockIndex]->entries[entryIndex] |= MAP_TEXTBLOCK;
1248 size += BLOCK_DATA_SIZE;
1251 if ( ntohl(new?tbPtr->newsize:tbPtr->size) > size )
1253 Log("verifyTextChain: Text block %s size %d > computed capacity %d\n",
1254 (new?"new":""), ntohl(new?tbPtr->newsize:tbPtr->size), size);
1255 if (BumpErrors()) ERROR(DBBAD);
1263 /* -----------------------------------------
1264 * verification driver routines
1265 * -----------------------------------------
1269 * Check the integrity of the database
1273 verifyDatabase(ut, recreateFile)
1274 struct ubik_trans *ut;
1275 FILE *recreateFile; /* not used */
1279 afs_int32 code = 0, tcode;
1281 extern int nBlocks; /* no. blocks in database */
1282 extern struct ubik_dbase *BU_dbase;
1284 /* clear verification statistics */
1286 memset(&miscData, 0, sizeof(miscData));
1289 miscData.maxErrors = 1000000;
1291 miscData.maxErrors = 50; /* Catch the first 50 errors */
1293 miscData.veryLongChain = 0;
1294 miscData.checkFragCount = 1; /* check frags */
1297 eof = ntohl(db.h.eofPtr);
1298 eof -= sizeof(db.h); /* subtract header */
1299 nBlocks = eof / BLOCKSIZE;
1301 Log("Verify of backup database started\n");
1302 Log("Database is %u. %d blocks of %d Bytes\n", eof, nBlocks, BLOCKSIZE);
1304 if ((eof < 0) || (nBlocks*BLOCKSIZE != eof))
1306 Log("Database eofPtr (%d) bad, blocksize %d\n", eof, BLOCKSIZE);
1310 /* set size of database */
1311 miscData.nBlocks = nBlocks;
1313 if (nBlocks == 0) ERROR(0); /* Nothing to check? */
1315 /* construct block map - first level is the array of pointers */
1316 bmsize = nBlocks*sizeof(struct blockMap *);
1317 blockMap = (struct blockMap **) malloc(bmsize);
1318 if (!blockMap) ERROR(BUDB_NOMEM);
1319 memset(blockMap, 0, bmsize);
1321 /* verify blocks and construct the block map */
1322 Log("Read header of every block\n");
1323 tcode = verifyBlocks(ut);
1324 if (tcode) ERROR(tcode);
1326 /* check the various hash tables */
1327 Log("Verify volume name hash table\n");
1328 tcode = verifyHashTable(ut, &db.volName, MAP_VOLHASH);
1329 if (tcode) ERROR(tcode);
1331 Log("Verify tape name hash table\n");
1332 tcode = verifyHashTable(ut, &db.tapeName, MAP_TAPEHASH);
1333 if (tcode) ERROR(tcode);
1335 Log("Verify dump name hash table\n");
1336 tcode = verifyHashTable(ut, &db.dumpName, MAP_DUMPHASH);
1337 if (tcode) ERROR(tcode);
1339 Log("Verify dump id hash table\n");
1340 tcode = verifyHashTable(ut, &db.dumpIden, MAP_IDHASH);
1341 if (tcode) ERROR(tcode);
1343 /* check the entry chains */
1344 Log("Verify all blocks and entries\n");
1345 tcode = verifyEntryChains(ut);
1346 if (tcode) ERROR(tcode);
1348 /* check text blocks - Log message in verifyText */
1349 tcode = verifyText(ut);
1350 if (tcode) ERROR(tcode);
1352 /* check free list */
1353 Log("Verify Free Lists\n");
1354 tcode = verifyFreeLists();
1355 if (tcode) ERROR(tcode);
1357 /* check entry map bit compatibility */
1359 Log("Verify Map bits\n");
1360 tcode = verifyMapBits();
1361 if (tcode) ERROR(tcode);
1364 /* free the block map */
1365 if ( blockMap != 0 )
1369 /* free all the individual maps */
1370 for ( i = 0; i < nBlocks; i++ )
1376 /* free the pointer array */
1382 Log("# 2K database blocks = %d\n", miscData.nBlocks);
1383 Log("# Dump entries found = %d. 3 dumps per block\n", miscData.nDump);
1384 Log(" max tapes on a dump = %d\n", miscData.maxTapesPerDump);
1385 Log(" max volumes on a dump = %d\n", miscData.maxVolsPerDump);
1386 Log(" max appends on a dump = %d\n", miscData.maxAppendsPerDump);
1387 Log(" # Blocks with space = %d\n", miscData.freeLength[4]);
1388 Log(" # of those fully free = %d\n", miscData.fullyFree[4]);
1389 Log("# Tape entries found = %d. 20 tapes per block\n", miscData.nTape);
1390 Log(" max volumes on a tape = %d\n", miscData.maxVolsPerTape);
1391 Log(" # Blocks with space = %d\n", miscData.freeLength[3]);
1392 Log(" # of those fully free = %d\n", miscData.fullyFree[3]);
1393 Log("# VolInfo entries found = %d. 20 volInfos per block\n", miscData.nVolInfo);
1394 Log(" # head of sameNameCh = %d\n", miscData.nVolName);
1395 Log(" max on a sameNameCh = %d\n", miscData.maxVolInfosPerName);
1396 Log(" max VolFrags on chain = %d\n", miscData.maxVolsPerVolInfo);
1397 Log(" # Blocks with space = %d\n", miscData.freeLength[2]);
1398 Log(" # of those fully free = %d\n", miscData.fullyFree[2]);
1399 Log("# VolFrag entries found = %d. 45 VolFrags per block\n", miscData.nVolFrag);
1400 Log(" # Blocks with space = %d\n", miscData.freeLength[1]);
1401 Log(" # of those fully free = %d\n", miscData.fullyFree[1]);
1402 Log("# free blocks = %d\n", miscData.freeLength[0]);
1405 Log("Verify of database completed. %d errors found\n", miscData.errors);
1407 if (miscData.errors && !code) code = DBBAD;
1412 /* -----------------------------
1413 * interface routines
1414 * -----------------------------
1418 * check the integrity of the database
1420 * status - integrity: 0, ok; n, not ok (error value)
1421 * orphans - no. of orphan blocks
1422 * host - address of host that did verification
1424 afs_int32 DbVerify();
1425 afs_int32 SBUDB_DbVerify(call, status, orphans, host)
1426 struct rx_call *call;
1433 code = DbVerify(call, status, orphans, host);
1434 osi_auditU(call, BUDB_DBVfyEvent, code, AUD_END);
1438 afs_int32 DbVerify(call, status, orphans, host)
1439 struct rx_call *call;
1444 struct ubik_trans *ut = 0;
1445 afs_int32 code = 0, tcode;
1449 if ( callPermitted(call) == 0 )
1450 ERROR(BUDB_NOTPERMITTED);
1452 tcode = InitRPC (&ut, LOCKREAD, 1);
1453 if (tcode) ERROR(tcode);
1455 tcode = verifyDatabase(ut, 0); /* check the database */
1456 if (tcode) ERROR(tcode);
1460 if (code) ubik_AbortTrans(ut);
1461 else code = ubik_EndTrans(ut);
1467 gethostname(hostname, sizeof(hostname));
1468 th = gethostbyname(hostname);
1472 memcpy(host, th->h_addr, sizeof(afs_int32));
1473 *host = ntohl(*host);
1479 /* ----------------------
1481 * ----------------------
1485 * do a simple sanity check on the database header
1488 check_header(callerst)
1491 static int iteration_count = 0;
1494 eof = ntohl(db.h.eofPtr);
1495 if ( (eof == 0) || (eof < 0) )
1497 Log("Eof check failed, caller %s, eof 0x%x\n",
1501 eof -= sizeof(db.h);
1504 Log("Adjusted Eof check failed, caller %s, eof 0x%x\n",
1509 if ( iteration_count >= 10 )
1511 Log("Eof ptr is 0x%x\n", eof);
1512 iteration_count = 0;