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