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>
26 #include <sys/types.h>
30 #include "error_macros.h"
31 #include "budb_errs.h"
32 #include "budb_internal.h"
33 #include <afs/cellconfig.h>
34 #include "afs/audit.h"
40 * 1) volInfo structures refering to a volume of the same name are
41 * chained together, i.e. the volumes described differ in volid, partition
42 * etc. The structure at the head of this list (the sameNameChain) is
43 * treated specially. When a delete volInfo request is processed, heads
44 * are not deleted unless all other items on the sameNameChain are gone.
46 * The result is that volInfo (head) structures may be present
47 * even if no tape structures refer to them. These structures are
48 * unreachable in a top-down tree walk.
50 * 1) make the verify tolerant of errors. Want to get a summary statistic
51 * indicating how may dumps are lost and how many text blocks lost
52 * 2) Make the recreation instructions write out whatever is good. This
53 * is only for the off-line case.
56 /* flags associated with each structure. These are set and checked in
57 * the blockMap entries
60 #define MAP_DUMPHASH 1 /* dump name hash checked */
61 #define MAP_TAPEHASH 2 /* tape name hash checked */
62 #define MAP_VOLHASH 4 /* volume name hash checked */
63 #define MAP_IDHASH 8 /* dump id hash checked */
65 #define MAP_HASHES (MAP_DUMPHASH | MAP_TAPEHASH | MAP_VOLHASH | MAP_IDHASH)
67 #define MAP_FREE 0x10 /* item is free */
68 #define MAP_RECREATE 0x20
69 #define MAP_HTBLOCK 0x40 /* hash table block */
70 #define MAP_TAPEONDUMP 0x100
71 #define MAP_VOLFRAGONTAPE 0x200
72 #define MAP_VOLFRAGONVOL 0x400
73 #define MAP_VOLINFOONNAME 0x800
74 #define MAP_VOLINFONAMEHEAD 0x1000
75 #define MAP_TEXTBLOCK 0x2000 /* block of text */
76 #define MAP_APPENDEDDUMP 0x4000
78 /* one blockMap for every block in the database. Each element of the entries
79 * array describes the status of a data structure/entry in that block
83 struct blockHeader header; /* copy of the block header */
84 char free; /* on free list */
85 int nEntries; /* size of the entries arrays */
86 afs_uint32 entries[1]; /* describes each entry */
89 /* status for verify call */
91 char hostname[64]; /* host on which checked */
92 afs_int32 status; /* ok, not ok */
95 int nBlocks; /* total number of blocks in db */
97 struct misc_hash_stats { /* stats for hashing */
98 int max; /* longest chain length */
99 double avg; /* avg length */
100 double std_dev; /* standard deviation of length */
104 int errors; /* errors encountered */
105 int maxErrors; /* abort after this many errors */
106 int nBlocks; /* number of database blocks */
107 int nDump, nTape, nVolInfo, nVolFrag; /* counts of each type */
108 int nVolName; /* volInfos w/ head==0 */
109 int maxVolsPerVolInfo; /* maximum list lengths */
112 int maxVolInfosPerName;
114 int maxAppendsPerDump;
115 int freeLength[NBLOCKTYPES]; /* length of free lists */
116 int fullyFree[NBLOCKTYPES]; /* free blocks full of free entries */
117 int veryLongChain; /* length of chain to report */
118 int checkFragCount; /* report fragment count errors */
119 struct misc_hash_stats dumpName, dumpIden, tapeName, volName;
120 FILE *recreate; /* stream for recreate instructions */
122 struct misc_data *misc;
124 struct blockMap **blockMap = 0; /* initial block map */
126 /* describes number of entries for each type of block */
128 int blockEntries[NBLOCKTYPES] = {
134 1, /* hashTable_BLOCK */
138 int blockEntrySize[NBLOCKTYPES] = {
140 sizeof(((struct vfBlock *) NULL)->a[0]),
141 sizeof(((struct viBlock *) NULL)->a[0]),
142 sizeof(((struct tBlock *) NULL)->a[0]),
143 sizeof(((struct dBlock *) NULL)->a[0]),
148 char *typeName[NBLOCKTYPES] = {
158 int hashBlockType[HT_MAX_FUNCTION + 1] = {
166 /* Compatibility table for the bits in the blockMap. */
168 struct mapCompatability {
169 short trigger; /* these bits trigger this element */
171 {MAP_FREE}, {MAP_HTBLOCK}, {MAP_DUMPHASH | MAP_IDHASH},
172 {MAP_TAPEHASH | MAP_TAPEONDUMP}, {MAP_VOLINFOONNAME},
173 {MAP_VOLINFONAMEHEAD | MAP_VOLHASH},
174 {MAP_VOLFRAGONTAPE | MAP_VOLFRAGONVOL}, {MAP_TEXTBLOCK}};
176 /* no. of entries in the mapC array */
177 int NMAPCs = (sizeof(mapC) / sizeof(mapC[0]));
179 /* for identifying stored textual information */
181 char *textName[TB_NUM] = {
187 extern int sizeFunctions[];
188 extern int nHTBuckets;
190 afs_int32 DbVerify(struct rx_call *call, afs_int32 *status,
191 afs_int32 *orphans, afs_int32 *host);
192 afs_int32 verifyTextChain(struct ubik_trans *ut, struct textBlock *tbPtr);
195 #define DBBAD BUDB_DATABASEINCONSISTENT
197 /* ------------------------------------
198 * supporting routines
199 * ------------------------------------
203 * increment the error count
206 * 1 - maximum errors exceeded
212 if (++miscData.errors >= miscData.maxErrors)
218 /* convertDiskAddress
219 * given a disk address, break it down into a block and entry index. These
220 * permit access to the block map information. The conversion process
221 * compares the supplied address with the alignment/type information
222 * stored in the block map.
225 * BUDB_ADDR - address alignment checks failed
229 checkDiskAddress(unsigned long address, int type, int *blockIndexPtr,
239 /* This is safest way to handle totally bogus addresses (eg 0x80001234). */
240 if ((address < sizeof(db.h)) || (address >= ntohl(db.h.eofPtr)))
243 address -= sizeof(db.h);
244 index = address / BLOCKSIZE;
245 offset = address - (index * BLOCKSIZE);
246 if (offset % sizeof(afs_int32)) /* alignment check */
248 if (offset && (type > 0) && (type <= MAX_STRUCTURE_BLOCK_TYPE)) {
249 offset -= sizeof(struct blockHeader);
250 if ((offset < 0) || (offset % blockEntrySize[type]))
252 offset /= blockEntrySize[type];
253 if (offset >= blockEntries[type])
257 *blockIndexPtr = index;
259 *entryIndexPtr = offset;
263 /* ConvertDiskAddress
264 * given a disk address, break it down into a block and entry index. These
265 * permit access to the block map information. The conversion process
266 * compares the supplied address with the alignment/type information
267 * stored in the block map.
270 * BUDB_ADDR - address alignment checks failed
274 ConvertDiskAddress(afs_uint32 address, int *blockIndexPtr, int *entryIndexPtr)
279 index = (address - sizeof(db.h)) / BLOCKSIZE;
280 type = blockMap[index]->header.type;
282 code = checkDiskAddress(address, type, blockIndexPtr, entryIndexPtr);
289 static char error[36];
291 if ((index < 0) || (index >= NBLOCKTYPES)) {
292 sprintf(error, "UNKNOWN_TYPE %d", index);
295 return (typeName[index]);
299 getDumpID(struct ubik_trans *ut,
300 struct tape *tapePtr,
307 code = dbread(ut, ntohl(tapePtr->dump), &d, sizeof(d));
309 *dumpID = ntohl(d.id);
313 /* ------------------------------------
314 * verification routines - structure specific
315 * ------------------------------------
319 * Follow the tapes entries hanging off of a dump and verify they belong
323 verifyDumpEntry(struct ubik_trans *ut, afs_int32 dumpAddr, int ai, int ao,
326 struct dump *dumpPtr = (struct dump *)param;
329 afs_int32 tapeAddr, tapeCount = 0, volCount = 0, appDumpCount = 0;
330 afs_int32 appDumpAddr, appDumpIndex, appDumpOffset;
332 int tapeIndex, tapeOffset, ccheck = 1;
333 afs_int32 code = 0, tcode;
334 int dumpIndex, dumpOffset;
336 tcode = ConvertDiskAddress(dumpAddr, &dumpIndex, &dumpOffset);
338 Log("verifyDumpEntry: Invalid dump entry addr 0x%x\n", dumpAddr);
344 /* Step though list of tapes hanging off of this dump */
345 for (tapeAddr = ntohl(dumpPtr->firstTape); tapeAddr;
346 tapeAddr = ntohl(tape.nextTape)) {
347 tcode = ConvertDiskAddress(tapeAddr, &tapeIndex, &tapeOffset);
349 Log("verifyDumpEntry: Invalid tape entry addr 0x%x (on DumpID %u)\n", tapeAddr, ntohl(dumpPtr->id));
350 Log(" Skipping remainder of tapes in dump\n");
357 tcode = dbread(ut, tapeAddr, &tape, sizeof(tape));
361 if (ntohl(tape.dump) != dumpAddr) {
364 getDumpID(ut, &tape, &did);
365 Log("verifyDumpEntry: Tape '%s' (addr 0x%x) doesn't point to\n",
366 tape.name, tapeAddr);
367 Log(" dumpID %u (addr 0x%x). Points to DumpID %u (addr 0x%x)\n", ntohl(dumpPtr->id), dumpAddr, did, ntohl(tape.dump));
372 /* Check if this tape entry has been examine already */
373 if (blockMap[tapeIndex]->entries[tapeOffset] & MAP_TAPEONDUMP) {
374 Log("verifyDumpEntry: Tape '%s' (addr 0x%x) on multiple dumps\n",
375 tape.name, tapeAddr);
379 blockMap[tapeIndex]->entries[tapeOffset] |= MAP_TAPEONDUMP;
382 volCount += ntohl(tape.nVolumes);
385 if (ccheck && (ntohl(dumpPtr->nVolumes) != volCount)) {
386 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);
391 if (volCount > misc->maxVolsPerDump)
392 misc->maxVolsPerDump = volCount;
393 if (tapeCount > misc->maxTapesPerDump)
394 misc->maxTapesPerDump = tapeCount;
396 /* If this is an initial dump, then step though list of appended dumps
397 * hanging off of this dump.
399 if (ntohl(dumpPtr->initialDumpID) == 0) {
400 for (appDumpAddr = ntohl(dumpPtr->appendedDumpChain); appDumpAddr;
401 appDumpAddr = ntohl(appDump.appendedDumpChain)) {
404 ConvertDiskAddress(appDumpAddr, &appDumpIndex,
407 Log("verifyDumpEntry: Invalid appended dump entry addr 0x%x\n", appDumpAddr);
408 Log("Skipping remainder of appended dumps\n");
414 /* Read the appended dump in */
415 tcode = dbread(ut, appDumpAddr, &appDump, sizeof(appDump));
419 /* Verify that it points to the parent dump */
420 if (ntohl(appDump.initialDumpID) != ntohl(dumpPtr->id)) {
421 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));
426 /* Check if this appended dump entry has been examined already */
427 if (blockMap[appDumpIndex]->
428 entries[appDumpOffset] & MAP_APPENDEDDUMP) {
429 Log("verifyDumpEntry: DumpID %u (addr %u) is on multiple appended dump chains\n", ntohl(appDump.id), appDumpAddr);
430 Log("Skipping remainder of appended dumps\n");
435 blockMap[appDumpIndex]->entries[appDumpOffset] |=
442 if (appDumpCount > misc->maxAppendsPerDump)
443 misc->maxAppendsPerDump = appDumpCount;
452 * Follw the volume fragments hanging off of a tape entry and verify
453 * they belong to the tape.
456 verifyTapeEntry(struct ubik_trans *ut, afs_int32 tapeAddr, int ai, int ao,
459 struct tape *tapePtr = (struct tape *) param;
460 int volCount = 0, ccheck = 1;
461 afs_int32 volFragAddr;
462 int blockIndex, entryIndex;
463 struct volFragment volFragment;
464 afs_int32 code = 0, tcode;
466 for (volFragAddr = ntohl(tapePtr->firstVol); volFragAddr;
467 volFragAddr = ntohl(volFragment.sameTapeChain)) {
468 tcode = ConvertDiskAddress(volFragAddr, &blockIndex, &entryIndex);
472 getDumpID(ut, tapePtr, &did);
473 Log("verifyTapeEntry: Invalid volFrag addr 0x%x (on tape '%s' DumpID %u)\n", volFragAddr, tapePtr->name, did);
474 Log(" Skipping remainder of volumes on tape\n");
481 tcode = dbread(ut, volFragAddr, &volFragment, sizeof(volFragment));
485 if (ntohl(volFragment.tape) != tapeAddr) {
488 getDumpID(ut, tapePtr, &did);
489 Log("verifyTapeEntry: VolFrag (addr 0x%x) doesn't point to \n",
491 Log(" tape '%s' DumpID %u (addr 0x%x). Points to addr 0x%x\n",
492 tapePtr->name, did, tapeAddr, ntohl(volFragment.tape));
497 /* Has this volume fragment already been examined */
498 if (blockMap[blockIndex]->entries[entryIndex] & MAP_VOLFRAGONTAPE) {
499 Log("verifyTapeEntry: VolFrag (addr %d) on multiple tapes\n",
504 blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLFRAGONTAPE;
509 /* now check computed vs. recorded volume counts */
510 if (ccheck && (ntohl(tapePtr->nVolumes) != volCount)) {
513 getDumpID(ut, tapePtr, &did);
514 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);
519 if (volCount > misc->maxVolsPerTape)
520 misc->maxVolsPerTape = volCount;
529 * volume fragments are the lowest leaf describing a dump (nothing hangs off of it).
530 * So no check is done agaist it.
533 verifyVolFragEntry(struct ubik_trans *ut, afs_int32 va, int ai, int ao,
536 /* struct volFragment *v = (struct volFragment *)param; */
541 /* verifyVolInfoEntry
542 * Follow the volume fragments hanging off of a volinfo structure and
543 * verify they belong to the volinfo structure.
544 * If the volinfo structure is at the head of the same name chain, then
545 * also verify all entries are also on the chain.
548 verifyVolInfoEntry(struct ubik_trans *ut, afs_int32 volInfoAddr, int ai,
551 struct volInfo *volInfo = (struct volInfo *) param;
553 int volCount = 0, ccheck = 1;
554 afs_int32 volFragAddr;
555 int blockIndex, entryIndex;
556 struct volFragment volFragment;
557 afs_int32 code = 0, tcode;
559 /* check each fragment attached to this volinfo structure */
560 for (volFragAddr = ntohl(volInfo->firstFragment); volFragAddr;
561 volFragAddr = ntohl(volFragment.sameNameChain)) {
562 tcode = ConvertDiskAddress(volFragAddr, &blockIndex, &entryIndex);
564 Log("verifyVolInfoEntry: Invalid volFrag entry addr 0x%x (on volume '%s')\n", volFragAddr, volInfo->name);
565 Log(" Skipping remainder of volumes on tape\n");
572 tcode = dbread(ut, volFragAddr, &volFragment, sizeof(volFragment));
576 if (ntohl(volFragment.vol) != volInfoAddr) {
577 Log("verifyVolInfoEntry: volFrag (addr 0x%x) doesn't point to \n",
579 Log(" volInfo '%s' (addr 0x%x). Points to addr 0x%x\n",
580 volInfo->name, volInfoAddr, ntohl(volFragment.vol));
585 /* volume fragment already on a volinfo chain? */
586 if (blockMap[blockIndex]->entries[entryIndex] & MAP_VOLFRAGONVOL) {
587 Log("verifyVolInfoEntry: VolFrag (addr %d) on multiple volInfo chains\n", volFragAddr);
591 blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLFRAGONVOL;
596 /* check computed vs. recorded number of fragments */
597 if (ccheck && misc->checkFragCount
598 && (ntohl(volInfo->nFrags) != volCount)) {
599 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) volFrag count of %d is wrong (should be %d)\n", volInfo->name, volInfoAddr, ntohl(volInfo->nFrags), volCount);
604 if (volCount > misc->maxVolsPerVolInfo)
605 misc->maxVolsPerVolInfo = volCount;
607 /* Check that all volInfo structures with same name point to the same
608 * head. If sameNameHead == 0, this is the head structure so we check,
611 if (volInfo->sameNameHead == 0) { /*i */
612 int viCount = 1; /* count this one */
616 for (tviAddr = ntohl(volInfo->sameNameChain); tviAddr;
617 tviAddr = ntohl(tvi.sameNameChain)) {
619 tcode = ConvertDiskAddress(tviAddr, &blockIndex, &entryIndex);
621 Log("verifyVolInfoEntry: Invalid volInfo entry %s addr 0x%x\n", volInfo->name, tviAddr);
622 Log(" Skipping remainder of volumes on same name chain\n");
629 tcode = dbread(ut, tviAddr, &tvi, sizeof(tvi));
633 if (ntohl(tvi.sameNameHead) != volInfoAddr) {
634 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) doesn't point to \n", volInfo->name, tviAddr);
635 Log(" head of sameName volInfo (addr 0x%x). Points to addr 0x%x\n", volInfoAddr, ntohl(tvi.sameNameHead));
640 if (blockMap[blockIndex]->entries[entryIndex] & MAP_VOLINFOONNAME) {
641 Log("verifyVolInfoEntry: VolInfo (addr 0x%x) on multiple same name chains\n", tviAddr);
645 blockMap[blockIndex]->entries[entryIndex] |= MAP_VOLINFOONNAME;
648 /* select the passed in structure flags */
649 if (blockMap[ai]->entries[ao] & MAP_VOLINFONAMEHEAD) {
650 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) is name head multiple times\n", volInfo->name, volInfoAddr);
654 blockMap[ai]->entries[ao] |= MAP_VOLINFONAMEHEAD;
656 if (viCount > misc->maxVolInfosPerName)
657 misc->maxVolInfosPerName = viCount;
668 /* ------------------------------------
669 * verification routines - general
670 * ------------------------------------
674 * Read each block header of every 2K block and remember it in our global
675 * blockMap array. Also check that the type of block is good.
678 verifyBlocks(struct ubik_trans *ut)
683 struct blockMap *ablockMap = 0;
686 afs_int32 code = 0, tcode;
688 /* Remember every header of every block in the database */
689 for (i = 0; i < nBlocks; i++) {
690 /* To avoid the call from timing out, do a poll every 256 blocks */
692 /* read the block header */
693 blockAddr = sizeof(db.h) + (i * BLOCKSIZE);
694 tcode = dbread(ut, blockAddr, (char *)&block.h, sizeof(block.h));
698 /* check the block type */
699 blocktype = block.h.type; /* char */
700 if ((blocktype < 0) || (blocktype >= NBLOCKTYPES)) {
701 Log("Block (index %d addr %d) has invalid type of %d\n", i,
702 blockAddr, blocktype);
703 ERROR(BUDB_BLOCKTYPE);
706 /* allocate the block map memory */
708 sizeof(*ablockMap) + (blockEntries[blocktype] -
709 1) * sizeof(ablockMap->entries[0]);
710 ablockMap = (struct blockMap *)malloc(bmsize);
713 memset(ablockMap, 0, bmsize);
715 ablockMap->nEntries = blockEntries[blocktype];
717 /* save the block header in the block map */
718 memcpy(&ablockMap->header, &block.h, sizeof(ablockMap->header));
719 blockMap[i] = ablockMap;
726 int minvols, maxvols, ttlvols;
728 /* verifyHashTableBlock
729 * Take a 2K hash table block and traverse its entries. Make sure each entry
730 * is of the correct type for the hash table, is hashed into the correct
731 * entry and is not threaded on multiple lists.
734 verifyHashTableBlock(struct ubik_trans *ut,
735 struct memoryHashTable *mhtPtr,
736 struct htBlock *htBlockPtr,
738 afs_int32 length, /* size of whole hash table */
739 int index, /* base index of this block */
742 int type; /* hash table type */
743 int entrySize; /* hashed entry size */
744 int blockType; /* block type for this hash table */
745 int blockIndex, entryIndex;
746 char entry[sizeof(struct block)];
748 int hash; /* calculated hash value for entry */
750 afs_int32 code = 0, tcode;
752 type = ntohl(mhtPtr->ht->functionType);
753 entrySize = sizeFunctions[type];
754 blockType = hashBlockType[type];
756 /* step through this hash table block, being careful to stop
757 * before the end of the overall hash table
760 for (i = 0; (i < nHTBuckets) && (index < length); i++, index++) { /*f */
761 entryAddr = ntohl(htBlockPtr->bucket[i]);
763 /* if this is the old hash table, all entries below the progress mark
764 * should have been moved to the new hash table
766 if (old && (index < mhtPtr->progress) && entryAddr) {
767 Log("Old hash table not empty (entry %d) below progress (%d)\n",
768 i, mhtPtr->progress);
773 /* now walk down the chain of each bucket */
774 for (count = 0; entryAddr; count++) { /*w */
775 tcode = ConvertDiskAddress(entryAddr, &blockIndex, &entryIndex);
777 Log("verifyHashTableBlock: Invalid hash table chain addr 0x%x\n", entryAddr);
778 Log(" Skipping remainder of bucket %d\n", index);
785 if (blockMap[blockIndex]->header.type != blockType) {
786 Log("Hash table chain (block index %d) incorrect\n",
788 Log(" Table type %d traverses block type %d\n", blockType,
789 blockMap[blockIndex]->header.type);
790 Log(" Skipping remainder of bucket %d\n", index);
796 if (dbread(ut, entryAddr, &entry[0], entrySize))
799 hash = ht_HashEntry(mhtPtr, &entry[0]) % length;
800 if (hash != index) { /* if it hashed to some other place */
801 Log("Entry (addr 0x%x) bucket %d, should be hashed into bucket %d\n", entryAddr, index, hash);
806 /* check if entry has been examined */
807 if (blockMap[blockIndex]->entries[entryIndex] & mapBit) {
808 Log("Entry (addr 0x%x) multiply referenced\n", entryAddr);
812 blockMap[blockIndex]->entries[entryIndex] |= mapBit;
814 entryAddr = ntohl(*((dbadr *) (entry + mhtPtr->threadOffset)));
817 /* Log("Bucket %4d contains %d entries\n", index+1, count); */
830 * Read each 2K block a hashtable has (both its old hastable and
831 * new hashtable) and verify the block has not been read before.
832 * Will also make call to verify entries within each 2K block of
836 verifyHashTable(struct ubik_trans *ut, struct memoryHashTable *mhtPtr,
839 struct hashTable *htPtr = mhtPtr->ht;
841 struct htBlock hashTableBlock;
842 int tableLength; /* # entries */
843 int hashblocks; /* # blocks */
844 dbadr tableAddr; /* disk addr of hash block */
845 int blockIndex, entryIndex;
848 afs_int32 code = 0, tcode;
850 extern int nHTBuckets; /* # buckets in a hash table */
852 LogDebug(4, "Htable: length %d oldlength %d progress %d\n",
853 mhtPtr->length, mhtPtr->oldLength, mhtPtr->progress);
855 /* check both old and current tables */
856 for (old = 0; old <= 1; old++) { /*fo */
857 tableLength = (old ? mhtPtr->oldLength : mhtPtr->length);
858 if (tableLength == 0)
860 tableAddr = (old ? ntohl(htPtr->oldTable) : ntohl(htPtr->table));
862 maxvols = ttlvols = 0;
864 /* follow the chain of hashtable blocks - avoid infinite loops */
865 hashblocks = ((tableLength - 1) / nHTBuckets) + 1; /* numb of 2K hashtable blocks */
866 for (i = 0; (tableAddr && (i < hashblocks + 5)); i++) {
867 tcode = ConvertDiskAddress(tableAddr, &blockIndex, &entryIndex);
869 Log("verifyHashTable: Invalid hash table chain addr 0x%x\n",
871 Log(" Skipping remainder of hash table chain\n");
878 if (blockMap[blockIndex]->header.type != hashTable_BLOCK) {
879 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);
880 Log(" Skipping remainder of hash table chain\n");
882 ERROR(BUDB_BLOCKTYPE);
886 /* check if we've examined this block before */
887 /* mark this (hash table) block as examined */
888 if (blockMap[blockIndex]->entries[entryIndex] & MAP_HTBLOCK) {
889 Log("Hash table block (index %d addr 0x%x) multiple ref\n",
892 ERROR(BUDB_DATABASEINCONSISTENT);
894 blockMap[blockIndex]->entries[entryIndex] |= MAP_HTBLOCK;
896 /* Read the actual hash table block */
898 dbread(ut, tableAddr, &hashTableBlock,
899 sizeof(hashTableBlock));
903 /* Verify its entries */
905 verifyHashTableBlock(ut, mhtPtr, &hashTableBlock, old,
906 tableLength, (i * nHTBuckets), mapBit);
910 tableAddr = ntohl(hashTableBlock.h.next);
913 /* Verify numb hash blocks is as it says */
914 if (i != hashblocks) {
915 Log("Incorrect number of hash chain blocks: %d (expected %d), hashtype %d\n", i, hashblocks, ntohl(htPtr->functionType));
917 ERROR(BUDB_DATABASEINCONSISTENT);
921 Log("%d entries; %u buckets; min = %d; max = %d\n", ttlvols,
922 tableLength, minvols, maxvols);
930 * do a linear walk of all the blocks. Check each block of structures
931 * to see if the actual free matches the recorded free. Also check
932 * the integrity of each allocated structure.
935 verifyEntryChains(struct ubik_trans *ut)
940 int blockIndex, entryIndex;
941 char entry[sizeof(struct block)];
946 static afs_int32(*checkEntry[NBLOCKTYPES]) (struct ubik_trans *,
947 afs_int32, int, int, void *)
949 /* FIXME: this list does not match typeName[] and may be incorrect */
951 verifyVolFragEntry, verifyVolInfoEntry, verifyTapeEntry, verifyDumpEntry, 0 /* text block */
954 for (blockIndex = 0; blockIndex < nBlocks; blockIndex++) { /*f */
955 /* ignore non-structure or blocks with invalid type */
956 type = blockMap[blockIndex]->header.type;
957 if ((type <= 0) || (type > MAX_STRUCTURE_BLOCK_TYPE))
960 entrySize = blockEntrySize[type];
963 for (entryIndex = 0; entryIndex < blockMap[blockIndex]->nEntries; entryIndex++) { /*f */
965 sizeof(db.h) + (blockIndex * BLOCKSIZE) +
966 sizeof(struct blockHeader) + (entryIndex * entrySize);
967 if (dbread(ut, offset, &entry[0], entrySize))
970 /* check if entry is free by looking at the first "afs_int32" of the structure */
971 memcpy(&start, entry, sizeof(start));
972 if (start == 0) { /* zero is free */
973 /* Is it on any hash chain? */
974 if (blockMap[blockIndex]->entries[entryIndex] & MAP_HASHES) {
975 Log("Entry: blockindex %d, entryindex %d - marked free but hashed 0x%x\n", blockIndex, entryIndex, blockMap[blockIndex]->entries[entryIndex]);
980 blockMap[blockIndex]->entries[entryIndex] |= MAP_FREE;
983 /* check the entry itself for consistency */
985 (*(checkEntry[type])) (ut, offset, blockIndex, entryIndex,
992 /* check computed free with recorded free entries */
993 if (nFree != ntohs(blockMap[blockIndex]->header.nFree)) {
994 Log("Block (index %d) free count %d has %d free structs\n",
995 blockIndex, ntohs(blockMap[blockIndex]->header.nFree), nFree);
1006 verifyFreeLists(void)
1010 int blockIndex, entryIndex;
1014 /* for each free list */
1015 for (i = 0; i < NBLOCKTYPES; i++) {
1016 misc->fullyFree[i] = misc->freeLength[i] = 0;
1018 for (addr = ntohl(db.h.freePtrs[i]); addr;
1019 addr = ntohl(blockMap[blockIndex]->header.next)) {
1020 misc->freeLength[i]++;
1022 code = ConvertDiskAddress(addr, &blockIndex, &entryIndex);
1023 if (code || (entryIndex != 0)) {
1024 Log("verifyFreeLists: Invalid free chain addr 0x%x in %s free chain\n", addr, TypeName(i));
1025 Log(" Skipping remainder of free chain\n");
1032 /* check block type */
1033 if (blockMap[blockIndex]->header.type != i) {
1034 Log("verifyFreeLists: Found %s type in %s free chain (addr 0x%x)\n",
1035 TypeName(blockMap[blockIndex]->header.type), TypeName(i),
1041 /* If entire block isn't free, check if count of free entries is ok */
1042 nFree = ntohs(blockMap[blockIndex]->header.nFree);
1043 if (i != free_BLOCK) {
1044 if ((nFree <= 0) || (nFree > blockEntries[i])) {
1045 Log("verifyFreeLists: Illegal free count %d on %s free chain\n", nFree, TypeName(i));
1048 } else if (nFree == blockEntries[i]) {
1049 misc->fullyFree[i]++;
1053 /* Check if already examined the block */
1054 if (blockMap[blockIndex]->free) {
1055 Log("verifyFreeLists: %s free chain block at addr 0x%x multiply threaded\n", TypeName(i), addr);
1059 blockMap[blockIndex]->free++;
1067 * Examines each entry to make sure it was traversed appropriately by
1068 * checking the bits for compatibility.
1073 int blockIndex, entryIndex, i, entrySize, type, bits;
1076 for (blockIndex = 0; blockIndex < nBlocks; blockIndex++) {
1077 /* If no entries in this block, then the block should be marked free */
1078 if ((blockMap[blockIndex]->nEntries == 0)
1079 && !blockMap[blockIndex]->free) {
1080 Log("verifyMapBits: Orphan free block (index %d)\n", blockIndex);
1085 /* check each entry */
1086 for (entryIndex = 0; entryIndex < blockMap[blockIndex]->nEntries; entryIndex++) { /*f */
1087 #ifndef AFS_PTHREAD_ENV
1088 if ((entryIndex % 1024) == 0)
1091 bits = blockMap[blockIndex]->entries[entryIndex];
1093 for (i = 0; i < NMAPCs; i++)
1094 if ((bits & mapC[i].trigger) == mapC[i].trigger)
1100 type = blockMap[blockIndex]->header.type;
1101 entrySize = blockEntrySize[type];
1103 sizeof(db.h) + (blockIndex * BLOCKSIZE) +
1104 sizeof(struct blockHeader) + (entryIndex * entrySize);
1106 sprintf(logstr, "%s entry Block %d, Entry %d, (addr 0x%x)",
1107 TypeName(type), blockIndex, entryIndex, offset);
1110 strcat(logstr, ": An orphaned entry");
1111 if (bits & MAP_FREE)
1112 strcat(logstr, ": A valid free block");
1113 if (bits & MAP_HTBLOCK)
1114 strcat(logstr, ": A valid hash-table block");
1115 if (bits & MAP_TEXTBLOCK)
1116 strcat(logstr, ": A valid text block");
1117 if (bits & (MAP_DUMPHASH | MAP_IDHASH)) {
1118 if (!(bits & MAP_DUMPHASH))
1120 ": A dump not on dump-name hash-chain");
1121 else if (!(bits & MAP_IDHASH))
1122 strcat(logstr, ": A dump not on dump-id hash-chain");
1124 strcat(logstr, ": A valid dump entry");
1126 if (bits & (MAP_TAPEHASH | MAP_TAPEONDUMP)) {
1127 if (!(bits & MAP_TAPEHASH))
1129 ": A tape not on tape-name hash-chain");
1130 else if (!(bits & MAP_TAPEONDUMP))
1131 strcat(logstr, ": A tape not associated with a dump");
1133 strcat(logstr, ": A valid tape entry");
1135 if (bits & MAP_VOLINFOONNAME)
1137 ": A valid volInfo on a volume-name chain");
1138 if (bits & (MAP_VOLINFONAMEHEAD | MAP_VOLHASH)) {
1139 if (!(bits & MAP_VOLINFONAMEHEAD))
1141 ": A volInfo not the head of a volume-name hash-chain");
1142 else if (!(bits & MAP_VOLHASH))
1144 ": A volInfo not on volume-name hash-chain");
1147 ": A valid volInfo in volume-name hash-chain");
1149 if (bits & (MAP_VOLFRAGONTAPE | MAP_VOLFRAGONVOL)) {
1150 if (!(bits & MAP_VOLFRAGONTAPE))
1152 ": A volFrag not associated with a tape");
1153 else if (!(bits & MAP_VOLFRAGONVOL))
1155 ": A volFrag not associated with a volume");
1157 strcat(logstr, ": A valid volFrag entry");
1159 Log("%s\n", logstr);
1171 verifyText(struct ubik_trans *ut)
1176 /* check each of the text types in use */
1177 for (i = 0; i < TB_NUM; i++) {
1178 Log("Verify Text: %s", textName[i]);
1179 code = verifyTextChain(ut, &db.h.textBlock[i]);
1187 * check the integrity of a text chain. Also checks the new chain.
1190 verifyTextChain(struct ubik_trans *ut, struct textBlock *tbPtr)
1193 int blockIndex, entryIndex;
1197 afs_int32 code = 0, tcode;
1199 for (new = 0; new < 2; new++) {
1201 blockAddr = ntohl(tbPtr->textAddr);
1204 (new ? ntohl(tbPtr->newTextAddr) : ntohl(tbPtr->textAddr));
1205 blockAddr; blockAddr = ntohl(block.h.next)) {
1206 tcode = ConvertDiskAddress(blockAddr, &blockIndex, &entryIndex);
1208 Log("verifyTextChain: Invalid %s text block addr 0x%x\n",
1209 (new ? "new" : ""), blockAddr);
1210 Log(" Skipping remainder of text chain\n");
1216 tcode = dbread(ut, blockAddr, &block, sizeof(block));
1220 if (blockMap[blockIndex]->entries[entryIndex] & MAP_TEXTBLOCK) {
1221 Log("verifyTextChain: Text block (addr 0x%x) multiply chained\n", blockAddr);
1225 blockMap[blockIndex]->entries[entryIndex] |= MAP_TEXTBLOCK;
1227 size += BLOCK_DATA_SIZE;
1230 if (ntohl(new ? tbPtr->newsize : tbPtr->size) > size) {
1231 Log("verifyTextChain: Text block %s size %d > computed capacity %d\n", (new ? "new" : ""), ntohl(new ? tbPtr->newsize : tbPtr->size), size);
1241 /* -----------------------------------------
1242 * verification driver routines
1243 * -----------------------------------------
1247 * Check the integrity of the database
1251 verifyDatabase(struct ubik_trans *ut,
1252 FILE *recreateFile) /* not used */
1256 afs_int32 code = 0, tcode = 0;
1258 extern int nBlocks; /* no. blocks in database */
1260 /* clear verification statistics */
1262 memset(&miscData, 0, sizeof(miscData));
1265 miscData.maxErrors = 1000000;
1267 miscData.maxErrors = 50; /* Catch the first 50 errors */
1269 miscData.veryLongChain = 0;
1270 miscData.checkFragCount = 1; /* check frags */
1273 eof = ntohl(db.h.eofPtr);
1274 eof -= sizeof(db.h); /* subtract header */
1275 nBlocks = eof / BLOCKSIZE;
1277 Log("Verify of backup database started\n");
1278 Log("Database is %u. %d blocks of %d Bytes\n", eof, nBlocks, BLOCKSIZE);
1280 if ((eof < 0) || (nBlocks * BLOCKSIZE != eof)) {
1281 Log("Database eofPtr (%d) bad, blocksize %d\n", eof, BLOCKSIZE);
1285 /* set size of database */
1286 miscData.nBlocks = nBlocks;
1289 ERROR(0); /* Nothing to check? */
1291 /* construct block map - first level is the array of pointers */
1292 bmsize = nBlocks * sizeof(struct blockMap *);
1293 blockMap = (struct blockMap **)malloc(bmsize);
1296 memset(blockMap, 0, bmsize);
1298 /* verify blocks and construct the block map */
1299 Log("Read header of every block\n");
1300 tcode = verifyBlocks(ut);
1304 /* check the various hash tables */
1305 Log("Verify volume name hash table\n");
1306 tcode = verifyHashTable(ut, &db.volName, MAP_VOLHASH);
1310 Log("Verify tape name hash table\n");
1311 tcode = verifyHashTable(ut, &db.tapeName, MAP_TAPEHASH);
1315 Log("Verify dump name hash table\n");
1316 tcode = verifyHashTable(ut, &db.dumpName, MAP_DUMPHASH);
1320 Log("Verify dump id hash table\n");
1321 tcode = verifyHashTable(ut, &db.dumpIden, MAP_IDHASH);
1325 /* check the entry chains */
1326 Log("Verify all blocks and entries\n");
1327 tcode = verifyEntryChains(ut);
1331 /* check text blocks - Log message in verifyText */
1332 tcode = verifyText(ut);
1336 /* check free list */
1337 Log("Verify Free Lists\n");
1338 tcode = verifyFreeLists();
1342 /* check entry map bit compatibility */
1344 Log("Verify Map bits\n");
1345 tcode = verifyMapBits();
1350 /* free the block map */
1351 if (blockMap != 0) {
1354 /* free all the individual maps */
1355 for (i = 0; i < nBlocks; i++) {
1360 /* free the pointer array */
1366 Log("# 2K database blocks = %d\n", miscData.nBlocks);
1367 Log("# Dump entries found = %d. 3 dumps per block\n",
1369 Log(" max tapes on a dump = %d\n", miscData.maxTapesPerDump);
1370 Log(" max volumes on a dump = %d\n", miscData.maxVolsPerDump);
1371 Log(" max appends on a dump = %d\n", miscData.maxAppendsPerDump);
1372 Log(" # Blocks with space = %d\n", miscData.freeLength[4]);
1373 Log(" # of those fully free = %d\n", miscData.fullyFree[4]);
1374 Log("# Tape entries found = %d. 20 tapes per block\n",
1376 Log(" max volumes on a tape = %d\n", miscData.maxVolsPerTape);
1377 Log(" # Blocks with space = %d\n", miscData.freeLength[3]);
1378 Log(" # of those fully free = %d\n", miscData.fullyFree[3]);
1379 Log("# VolInfo entries found = %d. 20 volInfos per block\n",
1381 Log(" # head of sameNameCh = %d\n", miscData.nVolName);
1382 Log(" max on a sameNameCh = %d\n", miscData.maxVolInfosPerName);
1383 Log(" max VolFrags on chain = %d\n", miscData.maxVolsPerVolInfo);
1384 Log(" # Blocks with space = %d\n", miscData.freeLength[2]);
1385 Log(" # of those fully free = %d\n", miscData.fullyFree[2]);
1386 Log("# VolFrag entries found = %d. 45 VolFrags per block\n",
1388 Log(" # Blocks with space = %d\n", miscData.freeLength[1]);
1389 Log(" # of those fully free = %d\n", miscData.fullyFree[1]);
1390 Log("# free blocks = %d\n", miscData.freeLength[0]);
1393 Log("Verify of database completed. %d errors found\n", miscData.errors);
1395 if (miscData.errors && !code)
1401 /* -----------------------------
1402 * interface routines
1403 * -----------------------------
1407 * check the integrity of the database
1409 * status - integrity: 0, ok; n, not ok (error value)
1410 * orphans - no. of orphan blocks
1411 * host - address of host that did verification
1414 SBUDB_DbVerify(struct rx_call *call, afs_int32 *status, afs_int32 *orphans,
1419 code = DbVerify(call, status, orphans, host);
1420 osi_auditU(call, BUDB_DBVfyEvent, code, AUD_END);
1425 DbVerify(struct rx_call *call, afs_int32 *status, afs_int32 *orphans,
1428 struct ubik_trans *ut = 0;
1429 afs_int32 code = 0, tcode;
1433 if (callPermitted(call) == 0)
1434 ERROR(BUDB_NOTPERMITTED);
1436 tcode = InitRPC(&ut, LOCKREAD, 1);
1440 tcode = verifyDatabase(ut, 0); /* check the database */
1447 ubik_AbortTrans(ut);
1449 code = ubik_EndTrans(ut);
1455 gethostname(hostname, sizeof(hostname));
1456 th = gethostbyname(hostname);
1460 memcpy(host, th->h_addr, sizeof(afs_int32));
1461 *host = ntohl(*host);
1467 /* ----------------------
1469 * ----------------------
1473 * do a simple sanity check on the database header
1476 check_header(char *callerst)
1478 static int iteration_count = 0;
1481 eof = ntohl(db.h.eofPtr);
1482 if ((eof == 0) || (eof < 0)) {
1483 Log("Eof check failed, caller %s, eof 0x%x\n", callerst, eof);
1486 eof -= sizeof(db.h);
1488 Log("Adjusted Eof check failed, caller %s, eof 0x%x\n", callerst,
1493 if (iteration_count >= 10) {
1494 Log("Eof ptr is 0x%x\n", eof);
1495 iteration_count = 0;