a720f95a2bfec78bb3777b0a1a6cb765c8b8fbb4
[openafs.git] / src / dir / salvage.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 /* This is the directory salvager.  It consists of two routines.  The first,
11  * DirOK, checks to see if the directory looks good.  If the directory does
12  * NOT look good, the approved procedure is to then call Salvage, which
13  * copies all the good entries from the damaged dir into a new directory.
14  */
15
16 #include <afsconfig.h>
17 #include <afs/param.h>
18
19 #include <roken.h>
20
21 #include "dir.h"
22 /* Defined in vol/vol-salvage.c */
23 extern void Log(const char *format, ...)
24     AFS_ATTRIBUTE_FORMAT(__printf__, 1, 2);
25
26 #define printf  Log             /* To make it work with volume salvager */
27
28 /* This routine is called with one parameter, the id (the same thing that is
29  * passed to physio or the buffer package) of a directory to check.  It
30  * returns 1 if the directory looks good, and 0 otherwise. */
31
32 #define MAXENAME 256
33
34 /* figure out how many pages in use in a directory, given ptr to its (locked)
35  * header */
36 static int
37 ComputeUsedPages(struct DirHeader *dhp)
38 {
39     afs_int32 usedPages, i;
40
41     if (dhp->header.pgcount != 0) {
42         /* new style */
43         usedPages = ntohs(dhp->header.pgcount);
44     } else {
45         /* old style */
46         usedPages = 0;
47         for (i = 0; i < MAXPAGES; i++) {
48             if (dhp->alloMap[i] == EPP) {
49                 usedPages = i;
50                 break;
51             }
52         }
53         if (usedPages == 0)
54             usedPages = MAXPAGES;
55     }
56     return usedPages;
57 }
58
59 /**
60  * check whether a directory object is ok.
61  *
62  * @param[in] file  opaque pointer to directory object fid
63  *
64  * @return operation status
65  *    @retval 1 dir is fine, or something went wrong checking
66  *    @retval 0 we *know* that the dir is bad
67  */
68 int
69 DirOK(void *file)
70 {
71     struct DirHeader *dhp;
72     struct PageHeader *pp;
73     struct DirEntry *ep;
74     struct DirBuffer headerbuf, pagebuf, entrybuf;
75     int i, j, k, up;
76     int havedot = 0, havedotdot = 0;
77     int usedPages, count, entry;
78     char eaMap[BIGMAXPAGES * EPP / 8];  /* Change eaSize initialization below, too. */
79     int eaSize;
80     afs_int32 entcount, maxents;
81     unsigned short ne;
82     int code;
83     int physerr;
84
85     eaSize = BIGMAXPAGES * EPP / 8;
86
87     /* Read the directory header */
88     code = DReadWithErrno(file, 0, &headerbuf, &physerr);
89     if (code) {
90         /* if physerr is 0, then we know that the read worked, but was short,
91          * and the damage is permanent.  Otherwise, we got an I/O or programming
92          * error.  Claim the dir is OK, but log something.
93          */
94         if (physerr != 0) {
95             printf("Could not read first page in directory (%d)\n", physerr);
96             Die("dirok1");
97             AFS_UNREACHED(return 1);
98         }
99         printf("First page in directory does not exist.\n");
100         return 0;
101     }
102     dhp = (struct DirHeader *)headerbuf.data;
103
104     /* Check magic number for first page */
105     if (dhp->header.tag != htons(1234)) {
106         printf("Bad first pageheader magic number.\n");
107         DRelease(&headerbuf, 0);
108         return 0;
109     }
110
111     /* Verify that the number of free entries in each directory page
112      * is within range (0-EPP). Also ensure directory is contiguous:
113      * Once the first alloMap entry with EPP free entries is found,
114      * the rest should match.
115      */
116     up = 0;                     /* count of used pages if total pages < MAXPAGES */
117     k = 0;                      /* found last page */
118     for (i = 0; i < MAXPAGES; i++) {
119         j = dhp->alloMap[i];
120
121         /* Check if in range */
122         if (i == 0) {
123             if ((j < 0) || (j > EPP - (13 + 2))) {
124                 /* First page's dirheader uses 13 entries and at least
125                  * two must exist for "." and ".."
126                  */
127                 printf("The dir header alloc map for page %d is bad.\n", i);
128                 DRelease(&headerbuf, 0);
129                 return 0;
130             }
131         } else {
132             if ((j < 0) || (j > EPP)) {
133                 printf("The dir header alloc map for page %d is bad.\n", i);
134                 DRelease(&headerbuf, 0);
135                 return 0;
136             }
137         }
138
139         /* Check if contiguous */
140         if (k) {                /* last page found */
141             if (j != EPP) {     /* remaining entries must be EPP */
142                 printf
143                     ("A partially-full page occurs in slot %d, after the dir end.\n",
144                      i);
145                 DRelease(&headerbuf, 0);
146                 return 0;
147             }
148         } else if (j == EPP) {  /* is this the last page */
149             k = 1;              /* yes */
150         } else {                /* a used page */
151             up++;               /* keep count */
152         }
153     }
154
155     /* Compute number of used directory pages and max entries in all
156      ** those pages, the value of 'up' must be less than pgcount. The above
157      ** loop only checks the first MAXPAGES in a directory. An alloMap does
158      ** not exists for pages between MAXPAGES and BIGMAXPAGES */
159     usedPages = ComputeUsedPages(dhp);
160     if (usedPages < up) {
161         printf
162             ("Count of used directory pages does not match count in directory header\n");
163         DRelease(&headerbuf, 0);
164         return 0;
165     }
166
167     /* For each directory page, check the magic number in each page
168      * header, and check that number of free entries (from freebitmap)
169      * matches the count in the alloMap from directory header.
170      */
171     for (i = 0; i < usedPages; i++) {
172         /* Read the page header */
173         code = DReadWithErrno(file, i, &pagebuf, &physerr);
174         if (code) {
175             DRelease(&headerbuf, 0);
176             if (physerr != 0) {
177                 /* couldn't read page, but not because it wasn't there permanently */
178                 printf("Failed to read dir page %d (errno %d)\n", i, physerr);
179                 Die("dirok2");
180                 AFS_UNREACHED(return 1);
181             }
182             printf("Directory shorter than alloMap indicates (page %d)\n", i);
183             return 0;
184         }
185         pp = (struct PageHeader *)pagebuf.data;
186
187         /* check the tag field */
188         if (pp->tag != htons(1234)) {
189             printf("Directory page %d has a bad magic number.\n", i);
190             DRelease(&pagebuf, 0);
191             DRelease(&headerbuf, 0);
192             return 0;
193         }
194
195         /* Count the number of entries allocated in this single
196          * directory page using the freebitmap in the page header.
197          */
198         count = 0;
199         for (j = 0; j < EPP / 8; j++) {
200             k = pp->freebitmap[j];
201             if (k & 0x80)
202                 count++;
203             if (k & 0x40)
204                 count++;
205             if (k & 0x20)
206                 count++;
207             if (k & 0x10)
208                 count++;
209             if (k & 0x08)
210                 count++;
211             if (k & 0x04)
212                 count++;
213             if (k & 0x02)
214                 count++;
215             if (k & 0x01)
216                 count++;
217         }
218         count = EPP - count;    /* Change to count of free entries */
219
220         /* Now check that the count of free entries matches the count in the alloMap */
221         if ((i < MAXPAGES) && ((count & 0xff) != (dhp->alloMap[i] & 0xff))) {
222             printf
223                 ("Header alloMap count doesn't match count in freebitmap for page %d.\n",
224                  i);
225             DRelease(&pagebuf, 0);
226             DRelease(&headerbuf, 0);
227             return 0;
228         }
229
230         DRelease(&pagebuf, 0);
231     }
232
233     /* Initialize the in-memory freebit map for all pages. */
234     for (i = 0; i < eaSize; i++) {
235         eaMap[i] = 0;
236         if (i < usedPages * (EPP / 8)) {
237             if (i == 0) {
238                 eaMap[i] = 0xff;        /* A dir header uses first 13 entries */
239             } else if (i == 1) {
240                 eaMap[i] = 0x1f;        /* A dir header uses first 13 entries */
241             } else if ((i % 8) == 0) {
242                 eaMap[i] = 0x01;        /* A page header uses only first entry */
243             }
244         }
245     }
246     maxents = usedPages * EPP;
247
248     /* Walk down all the hash lists, ensuring that each flag field has FFIRST
249      * in it.  Mark the appropriate bits in the in-memory freebit map.
250      * Check that the name is in the right hash bucket.
251      * Also check for loops in the hash chain by counting the entries.
252      */
253     for (entcount = 0, i = 0; i < NHASHENT; i++) {
254         for (entry = ntohs(dhp->hashTable[i]); entry; entry = ne) {
255             /* Verify that the entry is within range */
256             if (entry < 0 || entry >= maxents) {
257                 printf("Out-of-range hash id %d in chain %d.\n", entry, i);
258                 DRelease(&headerbuf, 0);
259                 return 0;
260             }
261
262             /* Read the directory entry */
263             code = afs_dir_GetBlobWithErrno(file, entry, &entrybuf, &physerr);
264             if (code) {
265                 if (physerr != 0) {
266                     /* something went wrong reading the page, but it wasn't
267                      * really something wrong with the dir that we can fix.
268                      */
269                     printf("Could not get dir blob %d (errno %d)\n", entry,
270                            physerr);
271                     DRelease(&headerbuf, 0);
272                     Die("dirok3");
273                 }
274                 printf("Invalid hash id %d in chain %d.\n", entry, i);
275                 DRelease(&headerbuf, 0);
276                 return 0;
277             }
278             ep = (struct DirEntry *)entrybuf.data;
279
280             ne = ntohs(ep->next);
281
282             /* There can't be more than maxents entries */
283             if (++entcount >= maxents) {
284                 printf("Directory's hash chain %d is circular.\n", i);
285                 DRelease(&entrybuf, 0);
286                 DRelease(&headerbuf, 0);
287                 return 0;
288             }
289
290             /* A null name is no good */
291             if (ep->name[0] == '\000') {
292                 printf("Dir entry %p in chain %d has bogus (null) name.\n",
293                         ep, i);
294                 DRelease(&entrybuf, 0);
295                 DRelease(&headerbuf, 0);
296                 return 0;
297             }
298
299             /* The entry flag better be FFIRST */
300             if (ep->flag != FFIRST) {
301                 printf("Dir entry %p in chain %d has bogus flag field.\n",
302                         ep, i);
303                 DRelease(&entrybuf, 0);
304                 DRelease(&headerbuf, 0);
305                 return 0;
306             }
307
308             /* Check the size of the name */
309             j = strlen(ep->name);
310             if (j >= MAXENAME) {        /* MAXENAME counts the null */
311                 printf("Dir entry %p in chain %d has too-long name.\n", ep, i);
312                 DRelease(&entrybuf, 0);
313                 DRelease(&headerbuf, 0);
314                 return 0;
315             }
316
317             /* The name used up k directory entries, set the bit in our in-memory
318              * freebitmap for each entry used by the name.
319              */
320             k = afs_dir_NameBlobs(ep->name);
321             for (j = 0; j < k; j++) {
322                 eaMap[(entry + j) >> 3] |= (1 << ((entry + j) & 7));
323             }
324
325             /* Hash the name and make sure it is in the correct name hash */
326             if ((j = afs_dir_DirHash(ep->name)) != i) {
327                 printf("Dir entry %p should be in hash bucket %d but IS in %d.\n",
328                        ep, j, i);
329                 DRelease(&entrybuf, 0);
330                 DRelease(&headerbuf, 0);
331                 return 0;
332             }
333
334             /* Check that if this is entry 13 (the 1st entry), then name must be "." */
335             if (entry == 13) {
336                 if (strcmp(ep->name, ".") == 0) {
337                     havedot = 1;
338                 } else {
339                     printf
340                         ("Dir entry %p, index 13 has name '%s' should be '.'\n",
341                          ep, ep->name);
342                     DRelease(&entrybuf, 0);
343                     DRelease(&headerbuf, 0);
344                     return 0;
345                 }
346             }
347
348             /* Check that if this is entry 14 (the 2nd entry), then name must be ".." */
349             if (entry == 14) {
350                 if (strcmp(ep->name, "..") == 0) {
351                     havedotdot = 1;
352                 } else {
353                     printf
354                         ("Dir entry %p, index 14 has name '%s' should be '..'\n",
355                          ep, ep->name);
356                     DRelease(&entrybuf, 0);
357                     DRelease(&headerbuf, 0);
358                     return 0;
359                 }
360             }
361
362             /* CHECK FOR DUPLICATE NAMES? */
363
364             DRelease(&entrybuf, 0);
365         }
366     }
367
368     /* Verify that we found '.' and '..' in the correct place */
369     if (!havedot || !havedotdot) {
370         printf
371             ("Directory entry '.' or '..' does not exist or is in the wrong index.\n");
372         DRelease(&headerbuf, 0);
373         return 0;
374     }
375
376     /* The in-memory freebit map has been computed.  Check that it
377      * matches the one in the page header.
378      * Note that if this matches, alloMap has already been checked against it.
379      */
380     for (i = 0; i < usedPages; i++) {
381         code = DReadWithErrno(file, i, &pagebuf, &physerr);
382         if (code) {
383             printf
384                 ("Failed on second attempt to read dir page %d (errno %d)\n",
385                  i, physerr);
386             DRelease(&headerbuf, 0);
387             /* if physerr is 0, then the dir is really bad, and we return dir
388              * *not* OK.  Otherwise, we Die instead of returning true (1),
389              * becauase the dir isn't known to be bad (we can't tell, since
390              * I/Os are failing).
391              */
392             if (physerr != 0)
393                 Die("dirok4");
394             else
395                 return 0;       /* dir is really shorter */
396         }
397         pp = (struct PageHeader *)pagebuf.data;
398
399         count = i * (EPP / 8);
400         for (j = 0; j < EPP / 8; j++) {
401             if (eaMap[count + j] != pp->freebitmap[j]) {
402                 printf
403                     ("Entry freebitmap error, page %d, map offset %d, %x should be %x.\n",
404                      i, j, pp->freebitmap[j], eaMap[count + j]);
405                 DRelease(&pagebuf, 0);
406                 DRelease(&headerbuf, 0);
407                 return 0;
408             }
409         }
410
411         DRelease(&pagebuf, 0);
412     }
413
414     /* Finally cleanup and return. */
415     DRelease(&headerbuf, 0);
416     return 1;
417 }
418
419 /**
420  * Salvage a directory object.
421  *
422  * @param[in] fromFile  fid of original, currently suspect directory object
423  * @param[in] toFile    fid where salvager will place new, fixed directory
424  * @param[in] vn        vnode of currently suspect directory
425  * @param[in] vu        uniquifier of currently suspect directory
426  * @param[in] pvn       vnode of parent directory
427  * @param[in] pvu       uniquifier of parent directory
428  *
429  * @return operation status
430  *    @retval 0 success
431  */
432 int
433 DirSalvage(void *fromFile, void *toFile, afs_int32 vn, afs_int32 vu,
434            afs_int32 pvn, afs_int32 pvu)
435 {
436     /* First do a MakeDir on the target. */
437     afs_int32 dot[3], dotdot[3], lfid[3], code, usedPages;
438     char tname[256];
439     int i;
440     char *tp;
441     struct DirBuffer headerbuf, entrybuf;
442     struct DirHeader *dhp;
443     struct DirEntry *ep;
444     int entry;
445     int physerr;
446
447     memset(dot, 0, sizeof(dot));
448     memset(dotdot, 0, sizeof(dotdot));
449     dot[1] = vn;
450     dot[2] = vu;
451     dotdot[1] = pvn;
452     dotdot[2] = pvu;
453
454     afs_dir_MakeDir(toFile, dot, dotdot);       /* Returns no error code. */
455
456     /* Find out how many pages are valid. */
457     code = DReadWithErrno(fromFile, 0, &headerbuf, &physerr);
458     if (code) {
459         printf("Failed to read first page of fromDir!\n");
460         /* if physerr != 0, then our call failed and we should let our
461          * caller know that there's something wrong with the new dir.  If not,
462          * then we return here anyway, with an empty, but at least good, directory.
463          */
464         return physerr;
465     }
466     dhp = (struct DirHeader *)headerbuf.data;
467
468     usedPages = ComputeUsedPages(dhp);
469
470     /* Finally, enumerate all the entries, doing a create on them. */
471     for (i = 0; i < NHASHENT; i++) {
472         entry = ntohs(dhp->hashTable[i]);
473         while (1) {
474             if (!entry)
475                 break;
476             if (entry < 0 || entry >= usedPages * EPP) {
477                 printf
478                     ("Warning: bogus hash table entry encountered, ignoring.\n");
479                 break;
480             }
481
482             code = afs_dir_GetBlobWithErrno(fromFile, entry, &entrybuf, &physerr);
483             if (code) {
484                 if (physerr != 0) {
485                     printf
486                         ("can't continue down hash chain (entry %d, errno %d)\n",
487                          entry, physerr);
488                     DRelease(&headerbuf, 0);
489                     return physerr;
490                 }
491                 printf
492                     ("Warning: bogus hash chain encountered, switching to next.\n");
493                 break;
494             }
495             ep = (struct DirEntry *)entrybuf.data;
496
497             strncpy(tname, ep->name, MAXENAME);
498             tname[MAXENAME - 1] = '\000';       /* just in case */
499             tp = tname;
500
501             entry = ntohs(ep->next);
502
503             if ((strcmp(tp, ".") != 0) && (strcmp(tp, "..") != 0)) {
504                 lfid[1] = ntohl(ep->fid.vnode);
505                 lfid[2] = ntohl(ep->fid.vunique);
506                 code = afs_dir_Create(toFile, tname, lfid);
507                 if (code) {
508                     printf
509                         ("Create of %s returned code %d, skipping to next hash chain.\n",
510                          tname, code);
511                     DRelease(&entrybuf, 0);
512                     break;
513                 }
514             }
515             DRelease(&entrybuf, 0);
516         }
517     }
518
519     /* Clean up things. */
520     DRelease(&headerbuf, 0);
521     return 0;
522 }