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