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