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>
20 #include <afs/cellconfig.h>
21 #include <afs/audit.h>
24 #include "error_macros.h"
25 #include "budb_errs.h"
26 #include "budb_internal.h"
32 * 1) volInfo structures refering to a volume of the same name are
33 * chained together, i.e. the volumes described differ in volid, partition
34 * etc. The structure at the head of this list (the sameNameChain) is
35 * treated specially. When a delete volInfo request is processed, heads
36 * are not deleted unless all other items on the sameNameChain are gone.
38 * The result is that volInfo (head) structures may be present
39 * even if no tape structures refer to them. These structures are
40 * unreachable in a top-down tree walk.
42 * 1) make the verify tolerant of errors. Want to get a summary statistic
43 * indicating how may dumps are lost and how many text blocks lost
44 * 2) Make the recreation instructions write out whatever is good. This
45 * is only for the off-line case.
48 /* flags associated with each structure. These are set and checked in
49 * the blockMap entries
52 #define MAP_DUMPHASH 1 /* dump name hash checked */
53 #define MAP_TAPEHASH 2 /* tape name hash checked */
54 #define MAP_VOLHASH 4 /* volume name hash checked */
55 #define MAP_IDHASH 8 /* dump id hash checked */
57 #define MAP_HASHES (MAP_DUMPHASH | MAP_TAPEHASH | MAP_VOLHASH | MAP_IDHASH)
59 #define MAP_FREE 0x10 /* item is free */
60 #define MAP_RECREATE 0x20
61 #define MAP_HTBLOCK 0x40 /* hash table block */
62 #define MAP_TAPEONDUMP 0x100
63 #define MAP_VOLFRAGONTAPE 0x200
64 #define MAP_VOLFRAGONVOL 0x400
65 #define MAP_VOLINFOONNAME 0x800
66 #define MAP_VOLINFONAMEHEAD 0x1000
67 #define MAP_TEXTBLOCK 0x2000 /* block of text */
68 #define MAP_APPENDEDDUMP 0x4000
70 /* one blockMap for every block in the database. Each element of the entries
71 * array describes the status of a data structure/entry in that block
75 struct blockHeader header
; /* copy of the block header */
76 char free
; /* on free list */
77 int nEntries
; /* size of the entries arrays */
78 afs_uint32 entries
[1]; /* describes each entry */
81 /* status for verify call */
83 char hostname
[64]; /* host on which checked */
84 afs_int32 status
; /* ok, not ok */
87 int nBlocks
; /* total number of blocks in db */
89 struct misc_hash_stats
{ /* stats for hashing */
90 int max
; /* longest chain length */
91 double avg
; /* avg length */
92 double std_dev
; /* standard deviation of length */
96 int errors
; /* errors encountered */
97 int maxErrors
; /* abort after this many errors */
98 int nBlocks
; /* number of database blocks */
99 int nDump
, nTape
, nVolInfo
, nVolFrag
; /* counts of each type */
100 int nVolName
; /* volInfos w/ head==0 */
101 int maxVolsPerVolInfo
; /* maximum list lengths */
104 int maxVolInfosPerName
;
106 int maxAppendsPerDump
;
107 int freeLength
[NBLOCKTYPES
]; /* length of free lists */
108 int fullyFree
[NBLOCKTYPES
]; /* free blocks full of free entries */
109 int veryLongChain
; /* length of chain to report */
110 int checkFragCount
; /* report fragment count errors */
111 struct misc_hash_stats dumpName
, dumpIden
, tapeName
, volName
;
112 FILE *recreate
; /* stream for recreate instructions */
114 struct misc_data
*misc
;
116 struct blockMap
**blockMap
= 0; /* initial block map */
118 /* describes number of entries for each type of block */
120 int blockEntries
[NBLOCKTYPES
] = {
126 1, /* hashTable_BLOCK */
130 int blockEntrySize
[NBLOCKTYPES
] = {
132 sizeof(struct vfBlock_frag
),
133 sizeof(struct viBlock_info
),
134 sizeof(struct tBlock_tape
),
135 sizeof(struct dBlock_dump
),
140 char *typeName
[NBLOCKTYPES
] = {
150 int hashBlockType
[HT_MAX_FUNCTION
+ 1] = {
158 /* Compatibility table for the bits in the blockMap. */
160 struct mapCompatability
{
161 short trigger
; /* these bits trigger this element */
163 {MAP_FREE
}, {MAP_HTBLOCK
}, {MAP_DUMPHASH
| MAP_IDHASH
},
164 {MAP_TAPEHASH
| MAP_TAPEONDUMP
}, {MAP_VOLINFOONNAME
},
165 {MAP_VOLINFONAMEHEAD
| MAP_VOLHASH
},
166 {MAP_VOLFRAGONTAPE
| MAP_VOLFRAGONVOL
}, {MAP_TEXTBLOCK
}};
168 /* no. of entries in the mapC array */
169 int NMAPCs
= (sizeof(mapC
) / sizeof(mapC
[0]));
171 /* for identifying stored textual information */
173 char *textName
[TB_NUM
] = {
179 extern int sizeFunctions
[];
180 extern int nHTBuckets
;
182 afs_int32
DbVerify(struct rx_call
*call
, afs_int32
*status
,
183 afs_int32
*orphans
, afs_int32
*host
);
184 afs_int32
verifyTextChain(struct ubik_trans
*ut
, struct textBlock
*tbPtr
);
187 #define DBBAD BUDB_DATABASEINCONSISTENT
189 /* ------------------------------------
190 * supporting routines
191 * ------------------------------------
195 * increment the error count
198 * 1 - maximum errors exceeded
204 if (++miscData
.errors
>= miscData
.maxErrors
)
210 /* convertDiskAddress
211 * given a disk address, break it down into a block and entry index. These
212 * permit access to the block map information. The conversion process
213 * compares the supplied address with the alignment/type information
214 * stored in the block map.
217 * BUDB_ADDR - address alignment checks failed
221 checkDiskAddress(unsigned long address
, int type
, int *blockIndexPtr
,
231 /* This is safest way to handle totally bogus addresses (eg 0x80001234). */
232 if ((address
< sizeof(db
.h
)) || (address
>= ntohl(db
.h
.eofPtr
)))
235 address
-= sizeof(db
.h
);
236 index
= address
/ BLOCKSIZE
;
237 offset
= address
- (index
* BLOCKSIZE
);
238 if (offset
% sizeof(afs_int32
)) /* alignment check */
240 if (offset
&& (type
> 0) && (type
<= MAX_STRUCTURE_BLOCK_TYPE
)) {
241 offset
-= sizeof(struct blockHeader
);
242 if ((offset
< 0) || (offset
% blockEntrySize
[type
]))
244 offset
/= blockEntrySize
[type
];
245 if (offset
>= blockEntries
[type
])
249 *blockIndexPtr
= index
;
251 *entryIndexPtr
= offset
;
255 /* ConvertDiskAddress
256 * given a disk address, break it down into a block and entry index. These
257 * permit access to the block map information. The conversion process
258 * compares the supplied address with the alignment/type information
259 * stored in the block map.
262 * BUDB_ADDR - address alignment checks failed
266 ConvertDiskAddress(afs_uint32 address
, int *blockIndexPtr
, int *entryIndexPtr
)
271 index
= (address
- sizeof(db
.h
)) / BLOCKSIZE
;
272 type
= blockMap
[index
]->header
.type
;
274 code
= checkDiskAddress(address
, type
, blockIndexPtr
, entryIndexPtr
);
281 static char error
[36];
283 if ((index
< 0) || (index
>= NBLOCKTYPES
)) {
284 sprintf(error
, "UNKNOWN_TYPE %d", index
);
287 return (typeName
[index
]);
291 getDumpID(struct ubik_trans
*ut
,
292 struct tape
*tapePtr
,
299 code
= dbread(ut
, ntohl(tapePtr
->dump
), &d
, sizeof(d
));
301 *dumpID
= ntohl(d
.id
);
305 /* ------------------------------------
306 * verification routines - structure specific
307 * ------------------------------------
311 * Follow the tapes entries hanging off of a dump and verify they belong
315 verifyDumpEntry(struct ubik_trans
*ut
, afs_int32 dumpAddr
, int ai
, int ao
,
318 struct dump
*dumpPtr
= (struct dump
*)param
;
321 afs_int32 tapeAddr
, tapeCount
= 0, volCount
= 0, appDumpCount
= 0;
322 afs_int32 appDumpAddr
, appDumpIndex
, appDumpOffset
;
324 int tapeIndex
, tapeOffset
, ccheck
= 1;
325 afs_int32 code
= 0, tcode
;
326 int dumpIndex
, dumpOffset
;
328 tcode
= ConvertDiskAddress(dumpAddr
, &dumpIndex
, &dumpOffset
);
330 Log("verifyDumpEntry: Invalid dump entry addr 0x%x\n", dumpAddr
);
336 /* Step though list of tapes hanging off of this dump */
337 for (tapeAddr
= ntohl(dumpPtr
->firstTape
); tapeAddr
;
338 tapeAddr
= ntohl(tape
.nextTape
)) {
339 tcode
= ConvertDiskAddress(tapeAddr
, &tapeIndex
, &tapeOffset
);
341 Log("verifyDumpEntry: Invalid tape entry addr 0x%x (on DumpID %u)\n", tapeAddr
, ntohl(dumpPtr
->id
));
342 Log(" Skipping remainder of tapes in dump\n");
349 tcode
= dbread(ut
, tapeAddr
, &tape
, sizeof(tape
));
353 if (ntohl(tape
.dump
) != dumpAddr
) {
356 getDumpID(ut
, &tape
, &did
);
357 Log("verifyDumpEntry: Tape '%s' (addr 0x%x) doesn't point to\n",
358 tape
.name
, tapeAddr
);
359 Log(" dumpID %u (addr 0x%x). Points to DumpID %u (addr 0x%x)\n", ntohl(dumpPtr
->id
), dumpAddr
, did
, ntohl(tape
.dump
));
364 /* Check if this tape entry has been examine already */
365 if (blockMap
[tapeIndex
]->entries
[tapeOffset
] & MAP_TAPEONDUMP
) {
366 Log("verifyDumpEntry: Tape '%s' (addr 0x%x) on multiple dumps\n",
367 tape
.name
, tapeAddr
);
371 blockMap
[tapeIndex
]->entries
[tapeOffset
] |= MAP_TAPEONDUMP
;
374 volCount
+= ntohl(tape
.nVolumes
);
377 if (ccheck
&& (ntohl(dumpPtr
->nVolumes
) != volCount
)) {
378 Log("verifyDumpEntry: DumpID %u (addr 0x%x) volume count of %d is wrong (should be %d)\n", ntohl(dumpPtr
->id
), dumpAddr
, ntohl(dumpPtr
->nVolumes
), volCount
);
383 if (volCount
> misc
->maxVolsPerDump
)
384 misc
->maxVolsPerDump
= volCount
;
385 if (tapeCount
> misc
->maxTapesPerDump
)
386 misc
->maxTapesPerDump
= tapeCount
;
388 /* If this is an initial dump, then step though list of appended dumps
389 * hanging off of this dump.
391 if (ntohl(dumpPtr
->initialDumpID
) == 0) {
392 for (appDumpAddr
= ntohl(dumpPtr
->appendedDumpChain
); appDumpAddr
;
393 appDumpAddr
= ntohl(appDump
.appendedDumpChain
)) {
396 ConvertDiskAddress(appDumpAddr
, &appDumpIndex
,
399 Log("verifyDumpEntry: Invalid appended dump entry addr 0x%x\n", appDumpAddr
);
400 Log("Skipping remainder of appended dumps\n");
406 /* Read the appended dump in */
407 tcode
= dbread(ut
, appDumpAddr
, &appDump
, sizeof(appDump
));
411 /* Verify that it points to the parent dump */
412 if (ntohl(appDump
.initialDumpID
) != ntohl(dumpPtr
->id
)) {
413 Log("verifyDumpEntry: DumpID %u (addr 0x%x) initial DumpID incorrect (is %u, should be %u)\n", ntohl(appDump
.id
), appDumpAddr
, ntohl(appDump
.initialDumpID
), ntohl(dumpPtr
->id
));
418 /* Check if this appended dump entry has been examined already */
419 if (blockMap
[appDumpIndex
]->
420 entries
[appDumpOffset
] & MAP_APPENDEDDUMP
) {
421 Log("verifyDumpEntry: DumpID %u (addr %u) is on multiple appended dump chains\n", ntohl(appDump
.id
), appDumpAddr
);
422 Log("Skipping remainder of appended dumps\n");
427 blockMap
[appDumpIndex
]->entries
[appDumpOffset
] |=
434 if (appDumpCount
> misc
->maxAppendsPerDump
)
435 misc
->maxAppendsPerDump
= appDumpCount
;
444 * Follw the volume fragments hanging off of a tape entry and verify
445 * they belong to the tape.
448 verifyTapeEntry(struct ubik_trans
*ut
, afs_int32 tapeAddr
, int ai
, int ao
,
451 struct tape
*tapePtr
= (struct tape
*) param
;
452 int volCount
= 0, ccheck
= 1;
453 afs_int32 volFragAddr
;
454 int blockIndex
, entryIndex
;
455 struct volFragment volFragment
;
456 afs_int32 code
= 0, tcode
;
458 for (volFragAddr
= ntohl(tapePtr
->firstVol
); volFragAddr
;
459 volFragAddr
= ntohl(volFragment
.sameTapeChain
)) {
460 tcode
= ConvertDiskAddress(volFragAddr
, &blockIndex
, &entryIndex
);
464 getDumpID(ut
, tapePtr
, &did
);
465 Log("verifyTapeEntry: Invalid volFrag addr 0x%x (on tape '%s' DumpID %u)\n", volFragAddr
, tapePtr
->name
, did
);
466 Log(" Skipping remainder of volumes on tape\n");
473 tcode
= dbread(ut
, volFragAddr
, &volFragment
, sizeof(volFragment
));
477 if (ntohl(volFragment
.tape
) != tapeAddr
) {
480 getDumpID(ut
, tapePtr
, &did
);
481 Log("verifyTapeEntry: VolFrag (addr 0x%x) doesn't point to \n",
483 Log(" tape '%s' DumpID %u (addr 0x%x). Points to addr 0x%x\n",
484 tapePtr
->name
, did
, tapeAddr
, ntohl(volFragment
.tape
));
489 /* Has this volume fragment already been examined */
490 if (blockMap
[blockIndex
]->entries
[entryIndex
] & MAP_VOLFRAGONTAPE
) {
491 Log("verifyTapeEntry: VolFrag (addr %d) on multiple tapes\n",
496 blockMap
[blockIndex
]->entries
[entryIndex
] |= MAP_VOLFRAGONTAPE
;
501 /* now check computed vs. recorded volume counts */
502 if (ccheck
&& (ntohl(tapePtr
->nVolumes
) != volCount
)) {
505 getDumpID(ut
, tapePtr
, &did
);
506 Log("verifyTapeEntry: Tape '%s' DumpID %u (addr 0x%x) volFrag count of %d is wrong (should be %d)\n", tapePtr
->name
, did
, tapeAddr
, ntohl(tapePtr
->nVolumes
), volCount
);
511 if (volCount
> misc
->maxVolsPerTape
)
512 misc
->maxVolsPerTape
= volCount
;
521 * volume fragments are the lowest leaf describing a dump (nothing hangs off of it).
522 * So no check is done agaist it.
525 verifyVolFragEntry(struct ubik_trans
*ut
, afs_int32 va
, int ai
, int ao
,
528 /* struct volFragment *v = (struct volFragment *)param; */
533 /* verifyVolInfoEntry
534 * Follow the volume fragments hanging off of a volinfo structure and
535 * verify they belong to the volinfo structure.
536 * If the volinfo structure is at the head of the same name chain, then
537 * also verify all entries are also on the chain.
540 verifyVolInfoEntry(struct ubik_trans
*ut
, afs_int32 volInfoAddr
, int ai
,
543 struct volInfo
*volInfo
= (struct volInfo
*) param
;
545 int volCount
= 0, ccheck
= 1;
546 afs_int32 volFragAddr
;
547 int blockIndex
, entryIndex
;
548 struct volFragment volFragment
;
549 afs_int32 code
= 0, tcode
;
551 /* check each fragment attached to this volinfo structure */
552 for (volFragAddr
= ntohl(volInfo
->firstFragment
); volFragAddr
;
553 volFragAddr
= ntohl(volFragment
.sameNameChain
)) {
554 tcode
= ConvertDiskAddress(volFragAddr
, &blockIndex
, &entryIndex
);
556 Log("verifyVolInfoEntry: Invalid volFrag entry addr 0x%x (on volume '%s')\n", volFragAddr
, volInfo
->name
);
557 Log(" Skipping remainder of volumes on tape\n");
564 tcode
= dbread(ut
, volFragAddr
, &volFragment
, sizeof(volFragment
));
568 if (ntohl(volFragment
.vol
) != volInfoAddr
) {
569 Log("verifyVolInfoEntry: volFrag (addr 0x%x) doesn't point to \n",
571 Log(" volInfo '%s' (addr 0x%x). Points to addr 0x%x\n",
572 volInfo
->name
, volInfoAddr
, ntohl(volFragment
.vol
));
577 /* volume fragment already on a volinfo chain? */
578 if (blockMap
[blockIndex
]->entries
[entryIndex
] & MAP_VOLFRAGONVOL
) {
579 Log("verifyVolInfoEntry: VolFrag (addr %d) on multiple volInfo chains\n", volFragAddr
);
583 blockMap
[blockIndex
]->entries
[entryIndex
] |= MAP_VOLFRAGONVOL
;
588 /* check computed vs. recorded number of fragments */
589 if (ccheck
&& misc
->checkFragCount
590 && (ntohl(volInfo
->nFrags
) != volCount
)) {
591 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) volFrag count of %d is wrong (should be %d)\n", volInfo
->name
, volInfoAddr
, ntohl(volInfo
->nFrags
), volCount
);
596 if (volCount
> misc
->maxVolsPerVolInfo
)
597 misc
->maxVolsPerVolInfo
= volCount
;
599 /* Check that all volInfo structures with same name point to the same
600 * head. If sameNameHead == 0, this is the head structure so we check,
603 if (volInfo
->sameNameHead
== 0) { /*i */
604 int viCount
= 1; /* count this one */
608 for (tviAddr
= ntohl(volInfo
->sameNameChain
); tviAddr
;
609 tviAddr
= ntohl(tvi
.sameNameChain
)) {
611 tcode
= ConvertDiskAddress(tviAddr
, &blockIndex
, &entryIndex
);
613 Log("verifyVolInfoEntry: Invalid volInfo entry %s addr 0x%x\n", volInfo
->name
, tviAddr
);
614 Log(" Skipping remainder of volumes on same name chain\n");
621 tcode
= dbread(ut
, tviAddr
, &tvi
, sizeof(tvi
));
625 if (ntohl(tvi
.sameNameHead
) != volInfoAddr
) {
626 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) doesn't point to \n", volInfo
->name
, tviAddr
);
627 Log(" head of sameName volInfo (addr 0x%x). Points to addr 0x%x\n", volInfoAddr
, ntohl(tvi
.sameNameHead
));
632 if (blockMap
[blockIndex
]->entries
[entryIndex
] & MAP_VOLINFOONNAME
) {
633 Log("verifyVolInfoEntry: VolInfo (addr 0x%x) on multiple same name chains\n", tviAddr
);
637 blockMap
[blockIndex
]->entries
[entryIndex
] |= MAP_VOLINFOONNAME
;
640 /* select the passed in structure flags */
641 if (blockMap
[ai
]->entries
[ao
] & MAP_VOLINFONAMEHEAD
) {
642 Log("verifyVolInfoEntry: VolInfo '%s' (addr 0x%x) is name head multiple times\n", volInfo
->name
, volInfoAddr
);
646 blockMap
[ai
]->entries
[ao
] |= MAP_VOLINFONAMEHEAD
;
648 if (viCount
> misc
->maxVolInfosPerName
)
649 misc
->maxVolInfosPerName
= viCount
;
660 /* ------------------------------------
661 * verification routines - general
662 * ------------------------------------
666 * Read each block header of every 2K block and remember it in our global
667 * blockMap array. Also check that the type of block is good.
670 verifyBlocks(struct ubik_trans
*ut
)
675 struct blockMap
*ablockMap
= 0;
678 afs_int32 code
= 0, tcode
;
680 /* Remember every header of every block in the database */
681 for (i
= 0; i
< nBlocks
; i
++) {
682 /* To avoid the call from timing out, do a poll every 256 blocks */
684 /* read the block header */
685 blockAddr
= sizeof(db
.h
) + (i
* BLOCKSIZE
);
686 tcode
= dbread(ut
, blockAddr
, (char *)&block
.h
, sizeof(block
.h
));
690 /* check the block type */
691 blocktype
= block
.h
.type
; /* char */
692 if ((blocktype
< 0) || (blocktype
>= NBLOCKTYPES
)) {
693 Log("Block (index %d addr %d) has invalid type of %d\n", i
,
694 blockAddr
, blocktype
);
695 ERROR(BUDB_BLOCKTYPE
);
698 /* allocate the block map memory */
700 sizeof(*ablockMap
) + (blockEntries
[blocktype
] -
701 1) * sizeof(ablockMap
->entries
[0]);
702 ablockMap
= calloc(1, bmsize
);
706 ablockMap
->nEntries
= blockEntries
[blocktype
];
708 /* save the block header in the block map */
709 memcpy(&ablockMap
->header
, &block
.h
, sizeof(ablockMap
->header
));
710 blockMap
[i
] = ablockMap
;
717 int minvols
, maxvols
, ttlvols
;
719 /* verifyHashTableBlock
720 * Take a 2K hash table block and traverse its entries. Make sure each entry
721 * is of the correct type for the hash table, is hashed into the correct
722 * entry and is not threaded on multiple lists.
725 verifyHashTableBlock(struct ubik_trans
*ut
,
726 struct memoryHashTable
*mhtPtr
,
727 struct htBlock
*htBlockPtr
,
729 afs_int32 length
, /* size of whole hash table */
730 int index
, /* base index of this block */
733 int type
; /* hash table type */
734 int entrySize
; /* hashed entry size */
735 int blockType
; /* block type for this hash table */
736 int blockIndex
, entryIndex
;
737 char entry
[sizeof(struct block
)];
739 int hash
; /* calculated hash value for entry */
741 afs_int32 code
= 0, tcode
;
743 type
= ntohl(mhtPtr
->ht
->functionType
);
744 entrySize
= sizeFunctions
[type
];
745 blockType
= hashBlockType
[type
];
747 /* step through this hash table block, being careful to stop
748 * before the end of the overall hash table
751 for (i
= 0; (i
< nHTBuckets
) && (index
< length
); i
++, index
++) { /*f */
752 entryAddr
= ntohl(htBlockPtr
->bucket
[i
]);
754 /* if this is the old hash table, all entries below the progress mark
755 * should have been moved to the new hash table
757 if (old
&& (index
< mhtPtr
->progress
) && entryAddr
) {
758 Log("Old hash table not empty (entry %d) below progress (%d)\n",
759 i
, mhtPtr
->progress
);
764 /* now walk down the chain of each bucket */
765 for (count
= 0; entryAddr
; count
++) { /*w */
766 tcode
= ConvertDiskAddress(entryAddr
, &blockIndex
, &entryIndex
);
768 Log("verifyHashTableBlock: Invalid hash table chain addr 0x%x\n", entryAddr
);
769 Log(" Skipping remainder of bucket %d\n", index
);
776 if (blockMap
[blockIndex
]->header
.type
!= blockType
) {
777 Log("Hash table chain (block index %d) incorrect\n",
779 Log(" Table type %d traverses block type %d\n", blockType
,
780 blockMap
[blockIndex
]->header
.type
);
781 Log(" Skipping remainder of bucket %d\n", index
);
787 if (dbread(ut
, entryAddr
, &entry
[0], entrySize
))
790 hash
= ht_HashEntry(mhtPtr
, &entry
[0]) % length
;
791 if (hash
!= index
) { /* if it hashed to some other place */
792 Log("Entry (addr 0x%x) bucket %d, should be hashed into bucket %d\n", entryAddr
, index
, hash
);
797 /* check if entry has been examined */
798 if (blockMap
[blockIndex
]->entries
[entryIndex
] & mapBit
) {
799 Log("Entry (addr 0x%x) multiply referenced\n", entryAddr
);
803 blockMap
[blockIndex
]->entries
[entryIndex
] |= mapBit
;
805 entryAddr
= ntohl(*((dbadr
*) (entry
+ mhtPtr
->threadOffset
)));
808 /* Log("Bucket %4d contains %d entries\n", index+1, count); */
821 * Read each 2K block a hashtable has (both its old hastable and
822 * new hashtable) and verify the block has not been read before.
823 * Will also make call to verify entries within each 2K block of
827 verifyHashTable(struct ubik_trans
*ut
, struct memoryHashTable
*mhtPtr
,
830 struct hashTable
*htPtr
= mhtPtr
->ht
;
832 struct htBlock hashTableBlock
;
833 int tableLength
; /* # entries */
834 int hashblocks
; /* # blocks */
835 dbadr tableAddr
; /* disk addr of hash block */
836 int blockIndex
, entryIndex
;
839 afs_int32 code
= 0, tcode
;
841 extern int nHTBuckets
; /* # buckets in a hash table */
843 LogDebug(4, "Htable: length %d oldlength %d progress %d\n",
844 mhtPtr
->length
, mhtPtr
->oldLength
, mhtPtr
->progress
);
846 /* check both old and current tables */
847 for (old
= 0; old
<= 1; old
++) { /*fo */
848 tableLength
= (old
? mhtPtr
->oldLength
: mhtPtr
->length
);
849 if (tableLength
== 0)
851 tableAddr
= (old
? ntohl(htPtr
->oldTable
) : ntohl(htPtr
->table
));
853 maxvols
= ttlvols
= 0;
855 /* follow the chain of hashtable blocks - avoid infinite loops */
856 hashblocks
= ((tableLength
- 1) / nHTBuckets
) + 1; /* numb of 2K hashtable blocks */
857 for (i
= 0; (tableAddr
&& (i
< hashblocks
+ 5)); i
++) {
858 tcode
= ConvertDiskAddress(tableAddr
, &blockIndex
, &entryIndex
);
860 Log("verifyHashTable: Invalid hash table chain addr 0x%x\n",
862 Log(" Skipping remainder of hash table chain\n");
869 if (blockMap
[blockIndex
]->header
.type
!= hashTable_BLOCK
) {
870 Log("Hashtable block (index %d addr 0x%x) hashtype %d - type %d, expected type %d\n", i
+ 1, tableAddr
, ntohl(htPtr
->functionType
), blockMap
[blockIndex
]->header
.type
, hashTable_BLOCK
);
871 Log(" Skipping remainder of hash table chain\n");
873 ERROR(BUDB_BLOCKTYPE
);
877 /* check if we've examined this block before */
878 /* mark this (hash table) block as examined */
879 if (blockMap
[blockIndex
]->entries
[entryIndex
] & MAP_HTBLOCK
) {
880 Log("Hash table block (index %d addr 0x%x) multiple ref\n",
883 ERROR(BUDB_DATABASEINCONSISTENT
);
885 blockMap
[blockIndex
]->entries
[entryIndex
] |= MAP_HTBLOCK
;
887 /* Read the actual hash table block */
889 dbread(ut
, tableAddr
, &hashTableBlock
,
890 sizeof(hashTableBlock
));
894 /* Verify its entries */
896 verifyHashTableBlock(ut
, mhtPtr
, &hashTableBlock
, old
,
897 tableLength
, (i
* nHTBuckets
), mapBit
);
901 tableAddr
= ntohl(hashTableBlock
.h
.next
);
904 /* Verify numb hash blocks is as it says */
905 if (i
!= hashblocks
) {
906 Log("Incorrect number of hash chain blocks: %d (expected %d), hashtype %d\n", i
, hashblocks
, ntohl(htPtr
->functionType
));
908 ERROR(BUDB_DATABASEINCONSISTENT
);
912 Log("%d entries; %u buckets; min = %d; max = %d\n", ttlvols
,
913 tableLength
, minvols
, maxvols
);
921 * do a linear walk of all the blocks. Check each block of structures
922 * to see if the actual free matches the recorded free. Also check
923 * the integrity of each allocated structure.
926 verifyEntryChains(struct ubik_trans
*ut
)
931 int blockIndex
, entryIndex
;
932 char entry
[sizeof(struct block
)];
937 static afs_int32(*checkEntry
[NBLOCKTYPES
]) (struct ubik_trans
*,
938 afs_int32
, int, int, void *)
940 /* FIXME: this list does not match typeName[] and may be incorrect */
942 verifyVolFragEntry
, verifyVolInfoEntry
, verifyTapeEntry
, verifyDumpEntry
, 0 /* text block */
945 for (blockIndex
= 0; blockIndex
< nBlocks
; blockIndex
++) { /*f */
946 /* ignore non-structure or blocks with invalid type */
947 type
= blockMap
[blockIndex
]->header
.type
;
948 if ((type
<= 0) || (type
> MAX_STRUCTURE_BLOCK_TYPE
))
951 entrySize
= blockEntrySize
[type
];
954 for (entryIndex
= 0; entryIndex
< blockMap
[blockIndex
]->nEntries
; entryIndex
++) { /*f */
956 sizeof(db
.h
) + (blockIndex
* BLOCKSIZE
) +
957 sizeof(struct blockHeader
) + (entryIndex
* entrySize
);
958 if (dbread(ut
, offset
, &entry
[0], entrySize
))
961 /* check if entry is free by looking at the first "afs_int32" of the structure */
962 memcpy(&start
, entry
, sizeof(start
));
963 if (start
== 0) { /* zero is free */
964 /* Is it on any hash chain? */
965 if (blockMap
[blockIndex
]->entries
[entryIndex
] & MAP_HASHES
) {
966 Log("Entry: blockindex %d, entryindex %d - marked free but hashed 0x%x\n", blockIndex
, entryIndex
, blockMap
[blockIndex
]->entries
[entryIndex
]);
971 blockMap
[blockIndex
]->entries
[entryIndex
] |= MAP_FREE
;
974 /* check the entry itself for consistency */
976 (*(checkEntry
[type
])) (ut
, offset
, blockIndex
, entryIndex
,
983 /* check computed free with recorded free entries */
984 if (nFree
!= ntohs(blockMap
[blockIndex
]->header
.nFree
)) {
985 Log("Block (index %d) free count %d has %d free structs\n",
986 blockIndex
, ntohs(blockMap
[blockIndex
]->header
.nFree
), nFree
);
997 verifyFreeLists(void)
1001 int blockIndex
, entryIndex
;
1005 /* for each free list */
1006 for (i
= 0; i
< NBLOCKTYPES
; i
++) {
1007 misc
->fullyFree
[i
] = misc
->freeLength
[i
] = 0;
1009 for (addr
= ntohl(db
.h
.freePtrs
[i
]); addr
;
1010 addr
= ntohl(blockMap
[blockIndex
]->header
.next
)) {
1011 misc
->freeLength
[i
]++;
1013 code
= ConvertDiskAddress(addr
, &blockIndex
, &entryIndex
);
1014 if (code
|| (entryIndex
!= 0)) {
1015 Log("verifyFreeLists: Invalid free chain addr 0x%x in %s free chain\n", addr
, TypeName(i
));
1016 Log(" Skipping remainder of free chain\n");
1022 /* check block type */
1023 if (blockMap
[blockIndex
]->header
.type
!= i
) {
1024 Log("verifyFreeLists: Found %s type in %s free chain (addr 0x%x)\n",
1025 TypeName(blockMap
[blockIndex
]->header
.type
), TypeName(i
),
1031 /* If entire block isn't free, check if count of free entries is ok */
1032 nFree
= ntohs(blockMap
[blockIndex
]->header
.nFree
);
1033 if (i
!= free_BLOCK
) {
1034 if ((nFree
<= 0) || (nFree
> blockEntries
[i
])) {
1035 Log("verifyFreeLists: Illegal free count %d on %s free chain\n", nFree
, TypeName(i
));
1038 } else if (nFree
== blockEntries
[i
]) {
1039 misc
->fullyFree
[i
]++;
1043 /* Check if already examined the block */
1044 if (blockMap
[blockIndex
]->free
) {
1045 Log("verifyFreeLists: %s free chain block at addr 0x%x multiply threaded\n", TypeName(i
), addr
);
1049 blockMap
[blockIndex
]->free
++;
1057 * Examines each entry to make sure it was traversed appropriately by
1058 * checking the bits for compatibility.
1063 int blockIndex
, entryIndex
, i
, entrySize
, type
, bits
;
1066 for (blockIndex
= 0; blockIndex
< nBlocks
; blockIndex
++) {
1067 /* If no entries in this block, then the block should be marked free */
1068 if ((blockMap
[blockIndex
]->nEntries
== 0)
1069 && !blockMap
[blockIndex
]->free
) {
1070 Log("verifyMapBits: Orphan free block (index %d)\n", blockIndex
);
1075 /* check each entry */
1076 for (entryIndex
= 0; entryIndex
< blockMap
[blockIndex
]->nEntries
; entryIndex
++) { /*f */
1077 #ifndef AFS_PTHREAD_ENV
1078 if ((entryIndex
% 1024) == 0)
1081 bits
= blockMap
[blockIndex
]->entries
[entryIndex
];
1083 for (i
= 0; i
< NMAPCs
; i
++)
1084 if ((bits
& mapC
[i
].trigger
) == mapC
[i
].trigger
)
1090 type
= blockMap
[blockIndex
]->header
.type
;
1091 entrySize
= blockEntrySize
[type
];
1093 sizeof(db
.h
) + (blockIndex
* BLOCKSIZE
) +
1094 sizeof(struct blockHeader
) + (entryIndex
* entrySize
);
1096 sprintf(logstr
, "%s entry Block %d, Entry %d, (addr 0x%x)",
1097 TypeName(type
), blockIndex
, entryIndex
, offset
);
1100 strcat(logstr
, ": An orphaned entry");
1101 if (bits
& MAP_FREE
)
1102 strcat(logstr
, ": A valid free block");
1103 if (bits
& MAP_HTBLOCK
)
1104 strcat(logstr
, ": A valid hash-table block");
1105 if (bits
& MAP_TEXTBLOCK
)
1106 strcat(logstr
, ": A valid text block");
1107 if (bits
& (MAP_DUMPHASH
| MAP_IDHASH
)) {
1108 if (!(bits
& MAP_DUMPHASH
))
1110 ": A dump not on dump-name hash-chain");
1111 else if (!(bits
& MAP_IDHASH
))
1112 strcat(logstr
, ": A dump not on dump-id hash-chain");
1114 strcat(logstr
, ": A valid dump entry");
1116 if (bits
& (MAP_TAPEHASH
| MAP_TAPEONDUMP
)) {
1117 if (!(bits
& MAP_TAPEHASH
))
1119 ": A tape not on tape-name hash-chain");
1120 else if (!(bits
& MAP_TAPEONDUMP
))
1121 strcat(logstr
, ": A tape not associated with a dump");
1123 strcat(logstr
, ": A valid tape entry");
1125 if (bits
& MAP_VOLINFOONNAME
)
1127 ": A valid volInfo on a volume-name chain");
1128 if (bits
& (MAP_VOLINFONAMEHEAD
| MAP_VOLHASH
)) {
1129 if (!(bits
& MAP_VOLINFONAMEHEAD
))
1131 ": A volInfo not the head of a volume-name hash-chain");
1132 else if (!(bits
& MAP_VOLHASH
))
1134 ": A volInfo not on volume-name hash-chain");
1137 ": A valid volInfo in volume-name hash-chain");
1139 if (bits
& (MAP_VOLFRAGONTAPE
| MAP_VOLFRAGONVOL
)) {
1140 if (!(bits
& MAP_VOLFRAGONTAPE
))
1142 ": A volFrag not associated with a tape");
1143 else if (!(bits
& MAP_VOLFRAGONVOL
))
1145 ": A volFrag not associated with a volume");
1147 strcat(logstr
, ": A valid volFrag entry");
1149 Log("%s\n", logstr
);
1161 verifyText(struct ubik_trans
*ut
)
1166 /* check each of the text types in use */
1167 for (i
= 0; i
< TB_NUM
; i
++) {
1168 Log("Verify Text: %s", textName
[i
]);
1169 code
= verifyTextChain(ut
, &db
.h
.textBlock
[i
]);
1177 * check the integrity of a text chain. Also checks the new chain.
1180 verifyTextChain(struct ubik_trans
*ut
, struct textBlock
*tbPtr
)
1183 int blockIndex
, entryIndex
;
1187 afs_int32 code
= 0, tcode
;
1189 for (new = 0; new < 2; new++) {
1193 (new ? ntohl(tbPtr
->newTextAddr
) : ntohl(tbPtr
->textAddr
));
1194 blockAddr
; blockAddr
= ntohl(block
.h
.next
)) {
1195 tcode
= ConvertDiskAddress(blockAddr
, &blockIndex
, &entryIndex
);
1197 Log("verifyTextChain: Invalid %s text block addr 0x%x\n",
1198 (new ? "new" : ""), blockAddr
);
1199 Log(" Skipping remainder of text chain\n");
1205 tcode
= dbread(ut
, blockAddr
, &block
, sizeof(block
));
1209 if (blockMap
[blockIndex
]->entries
[entryIndex
] & MAP_TEXTBLOCK
) {
1210 Log("verifyTextChain: Text block (addr 0x%x) multiply chained\n", blockAddr
);
1214 blockMap
[blockIndex
]->entries
[entryIndex
] |= MAP_TEXTBLOCK
;
1216 size
+= BLOCK_DATA_SIZE
;
1219 if (ntohl(new ? tbPtr
->newsize
: tbPtr
->size
) > size
) {
1220 Log("verifyTextChain: Text block %s size %d > computed capacity %d\n", (new ? "new" : ""), ntohl(new ? tbPtr
->newsize
: tbPtr
->size
), size
);
1230 /* -----------------------------------------
1231 * verification driver routines
1232 * -----------------------------------------
1236 * Check the integrity of the database
1240 verifyDatabase(struct ubik_trans
*ut
,
1241 FILE *recreateFile
) /* not used */
1245 afs_int32 code
= 0, tcode
= 0;
1247 extern int nBlocks
; /* no. blocks in database */
1249 /* clear verification statistics */
1251 memset(&miscData
, 0, sizeof(miscData
));
1254 miscData
.maxErrors
= 1000000;
1256 miscData
.maxErrors
= 50; /* Catch the first 50 errors */
1258 miscData
.veryLongChain
= 0;
1259 miscData
.checkFragCount
= 1; /* check frags */
1262 eof
= ntohl(db
.h
.eofPtr
);
1263 eof
-= sizeof(db
.h
); /* subtract header */
1264 nBlocks
= eof
/ BLOCKSIZE
;
1266 Log("Verify of backup database started\n");
1267 Log("Database is %u. %d blocks of %d Bytes\n", eof
, nBlocks
, BLOCKSIZE
);
1269 if ((eof
< 0) || (nBlocks
* BLOCKSIZE
!= eof
)) {
1270 Log("Database eofPtr (%d) bad, blocksize %d\n", eof
, BLOCKSIZE
);
1274 /* set size of database */
1275 miscData
.nBlocks
= nBlocks
;
1278 ERROR(0); /* Nothing to check? */
1280 /* construct block map - first level is the array of pointers */
1281 bmsize
= nBlocks
* sizeof(struct blockMap
*);
1282 blockMap
= calloc(1, bmsize
);
1286 /* verify blocks and construct the block map */
1287 Log("Read header of every block\n");
1288 tcode
= verifyBlocks(ut
);
1292 /* check the various hash tables */
1293 Log("Verify volume name hash table\n");
1294 tcode
= verifyHashTable(ut
, &db
.volName
, MAP_VOLHASH
);
1298 Log("Verify tape name hash table\n");
1299 tcode
= verifyHashTable(ut
, &db
.tapeName
, MAP_TAPEHASH
);
1303 Log("Verify dump name hash table\n");
1304 tcode
= verifyHashTable(ut
, &db
.dumpName
, MAP_DUMPHASH
);
1308 Log("Verify dump id hash table\n");
1309 tcode
= verifyHashTable(ut
, &db
.dumpIden
, MAP_IDHASH
);
1313 /* check the entry chains */
1314 Log("Verify all blocks and entries\n");
1315 tcode
= verifyEntryChains(ut
);
1319 /* check text blocks - Log message in verifyText */
1320 tcode
= verifyText(ut
);
1324 /* check free list */
1325 Log("Verify Free Lists\n");
1326 tcode
= verifyFreeLists();
1330 /* check entry map bit compatibility */
1332 Log("Verify Map bits\n");
1333 tcode
= verifyMapBits();
1338 /* free the block map */
1339 if (blockMap
!= 0) {
1342 /* free all the individual maps */
1343 for (i
= 0; i
< nBlocks
; i
++) {
1348 /* free the pointer array */
1354 Log("# 2K database blocks = %d\n", miscData
.nBlocks
);
1355 Log("# Dump entries found = %d. 3 dumps per block\n",
1357 Log(" max tapes on a dump = %d\n", miscData
.maxTapesPerDump
);
1358 Log(" max volumes on a dump = %d\n", miscData
.maxVolsPerDump
);
1359 Log(" max appends on a dump = %d\n", miscData
.maxAppendsPerDump
);
1360 Log(" # Blocks with space = %d\n", miscData
.freeLength
[4]);
1361 Log(" # of those fully free = %d\n", miscData
.fullyFree
[4]);
1362 Log("# Tape entries found = %d. 20 tapes per block\n",
1364 Log(" max volumes on a tape = %d\n", miscData
.maxVolsPerTape
);
1365 Log(" # Blocks with space = %d\n", miscData
.freeLength
[3]);
1366 Log(" # of those fully free = %d\n", miscData
.fullyFree
[3]);
1367 Log("# VolInfo entries found = %d. 20 volInfos per block\n",
1369 Log(" # head of sameNameCh = %d\n", miscData
.nVolName
);
1370 Log(" max on a sameNameCh = %d\n", miscData
.maxVolInfosPerName
);
1371 Log(" max VolFrags on chain = %d\n", miscData
.maxVolsPerVolInfo
);
1372 Log(" # Blocks with space = %d\n", miscData
.freeLength
[2]);
1373 Log(" # of those fully free = %d\n", miscData
.fullyFree
[2]);
1374 Log("# VolFrag entries found = %d. 45 VolFrags per block\n",
1376 Log(" # Blocks with space = %d\n", miscData
.freeLength
[1]);
1377 Log(" # of those fully free = %d\n", miscData
.fullyFree
[1]);
1378 Log("# free blocks = %d\n", miscData
.freeLength
[0]);
1381 Log("Verify of database completed. %d errors found\n", miscData
.errors
);
1383 if (miscData
.errors
&& !code
)
1389 /* -----------------------------
1390 * interface routines
1391 * -----------------------------
1395 * check the integrity of the database
1397 * status - integrity: 0, ok; n, not ok (error value)
1398 * orphans - no. of orphan blocks
1399 * host - address of host that did verification
1402 SBUDB_DbVerify(struct rx_call
*call
, afs_int32
*status
, afs_int32
*orphans
,
1407 code
= DbVerify(call
, status
, orphans
, host
);
1408 osi_auditU(call
, BUDB_DBVfyEvent
, code
, AUD_END
);
1413 DbVerify(struct rx_call
*call
, afs_int32
*status
, afs_int32
*orphans
,
1416 struct ubik_trans
*ut
= 0;
1417 afs_int32 code
= 0, tcode
;
1421 if (callPermitted(call
) == 0)
1422 ERROR(BUDB_NOTPERMITTED
);
1424 tcode
= InitRPC(&ut
, LOCKREAD
, 1);
1428 tcode
= verifyDatabase(ut
, 0); /* check the database */
1435 ubik_AbortTrans(ut
);
1437 code
= ubik_EndTrans(ut
);
1443 gethostname(hostname
, sizeof(hostname
));
1444 th
= gethostbyname(hostname
);
1448 memcpy(host
, th
->h_addr
, sizeof(afs_int32
));
1449 *host
= ntohl(*host
);
1455 /* ----------------------
1457 * ----------------------
1461 * do a simple sanity check on the database header
1464 check_header(char *callerst
)
1466 static int iteration_count
= 0;
1469 eof
= ntohl(db
.h
.eofPtr
);
1470 if ((eof
== 0) || (eof
< 0)) {
1471 Log("Eof check failed, caller %s, eof 0x%x\n", callerst
, eof
);
1474 eof
-= sizeof(db
.h
);
1476 Log("Adjusted Eof check failed, caller %s, eof 0x%x\n", callerst
,
1481 if (iteration_count
>= 10) {
1482 Log("Eof ptr is 0x%x\n", eof
);
1483 iteration_count
= 0;