28647d0e7c15eeb77e4aa7c5c1cd2d177f1bb635
[openafs.git] / src / dir / dir.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 #include <afsconfig.h>
11 #include <afs/param.h>
12
13 #ifdef KERNEL
14 # if !defined(UKERNEL)
15 #  include "h/types.h"
16 #  include "h/param.h"
17 #  ifdef        AFS_AUX_ENV
18 #   include "h/mmu.h"
19 #   include "h/seg.h"
20 #   include "h/sysmacros.h"
21 #   include "h/signal.h"
22 #   include "h/errno.h"
23 #  endif
24 #  include "h/time.h"
25 #  if defined(AFS_AIX_ENV) || defined(AFS_SGI_ENV) || defined(AFS_SUN5_ENV) || defined(AFS_LINUX20_ENV)
26 #   include "h/errno.h"
27 #  else
28 #   if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX20_ENV)
29 #    include "h/kernel.h"
30 #   endif
31 #  endif
32 #  if   defined(AFS_SUN5_ENV) || defined(AFS_HPUX_ENV) || defined(AFS_FBSD_ENV) || defined(AFS_DARWIN80_ENV)
33 #   include "afs/sysincludes.h"
34 #  endif
35 #  if !defined(AFS_SGI64_ENV) && !defined(AFS_DARWIN_ENV) && !defined(AFS_OBSD48_ENV) && !defined(AFS_NBSD_ENV)
36 #   include "h/user.h"
37 #  endif /* AFS_SGI64_ENV */
38 #  include "h/uio.h"
39 #  ifdef        AFS_OSF_ENV
40 #   include <sys/mount.h>
41 #   include <sys/vnode.h>
42 #   include <ufs/inode.h>
43 #  endif
44 #  if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX20_ENV) && !defined(AFS_HPUX110_ENV)
45 #   include "h/mbuf.h"
46 #  endif
47 #  ifndef AFS_LINUX20_ENV
48 #   include "netinet/in.h"
49 #  endif
50 # else /* !defined(UKERNEL) */
51 #  include "afs/stds.h"
52 #  include "afs/sysincludes.h"
53 # endif /* !defined(UKERNEL) */
54
55 /* afs_buffer.c */
56 /* These are needed because afs_prototypes.h is not included here */
57 struct dcache;
58 struct DirBuffer;
59 extern int DRead(struct dcache *adc, int page, struct DirBuffer *);
60 extern int DNew(struct dcache *adc, int page, struct DirBuffer *);
61
62 # include "afs/afs_osi.h"
63
64 # include "afs/dir.h"
65
66 # ifdef AFS_LINUX20_ENV
67 #  include "h/string.h"
68 # endif
69
70 #else /* KERNEL */
71
72 # include <roken.h>
73 # include "dir.h"
74 #endif /* KERNEL */
75
76 afs_int32 DErrno;
77
78 /* Local static prototypes */
79 static int FindBlobs(dir_file_t, int);
80 static void AddPage(dir_file_t, int);
81 static void FreeBlobs(dir_file_t, int, int);
82 static int FindItem(dir_file_t, char *, struct DirBuffer *,
83                     struct DirBuffer *);
84
85 /* Find out how many entries are required to store a name. */
86 int
87 afs_dir_NameBlobs(char *name)
88 {
89     int i;
90     i = strlen(name) + 1;
91     return 1 + ((i + 15) >> 5);
92 }
93
94 /* Create an entry in a file.  Dir is a file representation, while entry is
95  * a string name. */
96 int
97 afs_dir_Create(dir_file_t dir, char *entry, void *voidfid)
98 {
99     afs_int32 *vfid = (afs_int32 *) voidfid;
100     int blobs, firstelt;
101     int i;
102     struct DirBuffer entrybuf, prevbuf, headerbuf;
103     struct DirEntry *ep;
104     struct DirHeader *dhp;
105
106     /* check name quality */
107     if (*entry == 0)
108         return EINVAL;
109
110     /* First check if file already exists. */
111     if (FindItem(dir, entry, &prevbuf, &entrybuf) == 0) {
112         DRelease(&entrybuf, 0);
113         DRelease(&prevbuf, 0);
114         return EEXIST;
115     }
116
117     blobs = afs_dir_NameBlobs(entry);   /* number of entries required */
118     firstelt = FindBlobs(dir, blobs);
119     if (firstelt < 0)
120         return EFBIG;           /* directory is full */
121
122     /* First, we fill in the directory entry. */
123     if (afs_dir_GetBlob(dir, firstelt, &entrybuf) != 0)
124         return EIO;
125     ep = (struct DirEntry *)entrybuf.data;
126
127     ep->flag = FFIRST;
128     ep->fid.vnode = htonl(vfid[1]);
129     ep->fid.vunique = htonl(vfid[2]);
130     strcpy(ep->name, entry);
131
132     /* Now we just have to thread it on the hash table list. */
133     if (DRead(dir, 0, &headerbuf) != 0) {
134         DRelease(&entrybuf, 1);
135         return EIO;
136     }
137     dhp = (struct DirHeader *)headerbuf.data;
138
139     i = afs_dir_DirHash(entry);
140     ep->next = dhp->hashTable[i];
141     dhp->hashTable[i] = htons(firstelt);
142     DRelease(&headerbuf, 1);
143     DRelease(&entrybuf, 1);
144     return 0;
145 }
146
147 int
148 afs_dir_Length(dir_file_t dir)
149 {
150     int i, ctr;
151     struct DirBuffer headerbuf;
152     struct DirHeader *dhp;
153
154     if (DRead(dir, 0, &headerbuf) != 0)
155         return 0;
156     dhp = (struct DirHeader *)headerbuf.data;
157
158     if (dhp->header.pgcount != 0)
159         ctr = ntohs(dhp->header.pgcount);
160     else {
161         /* old style, count the pages */
162         ctr = 0;
163         for (i = 0; i < MAXPAGES; i++)
164             if (dhp->alloMap[i] != EPP)
165                 ctr++;
166     }
167     DRelease(&headerbuf, 0);
168     return ctr * AFS_PAGESIZE;
169 }
170
171 /* Delete an entry from a directory, including update of all free entry
172  * descriptors. */
173 int
174 afs_dir_Delete(dir_file_t dir, char *entry)
175 {
176
177     int nitems, index;
178     struct DirBuffer entrybuf, prevbuf;
179     struct DirEntry *firstitem;
180     unsigned short *previtem;
181
182     if (FindItem(dir, entry, &prevbuf, &entrybuf) != 0)
183         return ENOENT;
184
185     firstitem = (struct DirEntry *)entrybuf.data;
186     previtem = (unsigned short *)prevbuf.data;
187
188     *previtem = firstitem->next;
189     DRelease(&prevbuf, 1);
190     index = DVOffset(&entrybuf) / 32;
191     nitems = afs_dir_NameBlobs(firstitem->name);
192     DRelease(&entrybuf, 0);
193     FreeBlobs(dir, index, nitems);
194     return 0;
195 }
196
197 /* Find a bunch of contiguous entries; at least nblobs in a row. */
198 static int
199 FindBlobs(dir_file_t dir, int nblobs)
200 {
201     int i, j, k;
202     int failed = 0;
203     struct DirBuffer headerbuf, pagebuf;
204     struct DirHeader *dhp;
205     struct PageHeader *pp;
206     int pgcount;
207
208     /* read the dir header in first. */
209     if (DRead(dir, 0, &headerbuf) != 0)
210         return -1;
211     dhp = (struct DirHeader *)headerbuf.data;
212
213     for (i = 0; i < BIGMAXPAGES; i++) {
214         if (i >= MAXPAGES || dhp->alloMap[i] >= nblobs) {
215             /* if page could contain enough entries */
216             /* If there are EPP free entries, then the page is not even allocated. */
217             if (i >= MAXPAGES) {
218                 /* this pages exists past the end of the old-style dir */
219                 pgcount = ntohs(dhp->header.pgcount);
220                 if (pgcount == 0) {
221                     pgcount = MAXPAGES;
222                     dhp->header.pgcount = htons(pgcount);
223                 }
224                 if (i > pgcount - 1) {
225                     /* this page is bigger than last allocated page */
226                     AddPage(dir, i);
227                     dhp->header.pgcount = htons(i + 1);
228                 }
229             } else if (dhp->alloMap[i] == EPP) {
230                 /* Add the page to the directory. */
231                 AddPage(dir, i);
232                 dhp->alloMap[i] = EPP - 1;
233                 dhp->header.pgcount = htons(i + 1);
234             }
235
236             /* read the page in. */
237             if (DRead(dir, i, &pagebuf) != 0) {
238                 DRelease(&headerbuf, 1);
239                 break;
240             }
241             pp = (struct PageHeader *)pagebuf.data;
242             for (j = 0; j <= EPP - nblobs; j++) {
243                 failed = 0;
244                 for (k = 0; k < nblobs; k++)
245                     if ((pp->freebitmap[(j + k) >> 3] >> ((j + k) & 7)) & 1) {
246                         failed = 1;
247                         break;
248                     }
249                 if (!failed)
250                     break;
251                 failed = 1;
252             }
253             if (!failed) {
254                 /* Here we have the first index in j.  We update the allocation maps
255                  * and free up any resources we've got allocated. */
256                 if (i < MAXPAGES)
257                     dhp->alloMap[i] -= nblobs;
258                 DRelease(&headerbuf, 1);
259                 for (k = 0; k < nblobs; k++)
260                     pp->freebitmap[(j + k) >> 3] |= 1 << ((j + k) & 7);
261                 DRelease(&pagebuf, 1);
262                 return j + i * EPP;
263             }
264             DRelease(&pagebuf, 0);      /* This dir page is unchanged. */
265         }
266     }
267     /* If we make it here, the directory is full. */
268     DRelease(&headerbuf, 1);
269     return -1;
270 }
271
272 static void
273 AddPage(dir_file_t dir, int pageno)
274 {                               /* Add a page to a directory. */
275     int i;
276     struct PageHeader *pp;
277     struct DirBuffer pagebuf;
278
279     /* Get a new buffer labelled dir,pageno */
280     DNew(dir, pageno, &pagebuf);
281     pp = (struct PageHeader *)pagebuf.data;
282
283     pp->tag = htons(1234);
284     if (pageno > 0)
285         pp->pgcount = 0;
286     pp->freecount = EPP - 1;    /* The first dude is already allocated */
287     pp->freebitmap[0] = 0x01;
288     for (i = 1; i < EPP / 8; i++)       /* It's a constant */
289         pp->freebitmap[i] = 0;
290     DRelease(&pagebuf, 1);
291 }
292
293 /* Free a whole bunch of directory entries. */
294
295 static void
296 FreeBlobs(dir_file_t dir, int firstblob, int nblobs)
297 {
298     int i;
299     int page;
300     struct DirBuffer headerbuf, pagehdbuf;
301     struct DirHeader *dhp;
302     struct PageHeader *pp;
303     page = firstblob / EPP;
304     firstblob -= EPP * page;    /* convert to page-relative entry */
305
306     if (DRead(dir, 0, &headerbuf) != 0)
307         return;
308     dhp = (struct DirHeader *)headerbuf.data;
309
310     if (page < MAXPAGES)
311         dhp->alloMap[page] += nblobs;
312
313     DRelease(&headerbuf, 1);
314
315     if (DRead(dir, page, &pagehdbuf) != 0)
316         return;
317     pp = (struct PageHeader *)pagehdbuf.data;
318
319     for (i = 0; i < nblobs; i++)
320         pp->freebitmap[(firstblob + i) >> 3] &= ~(1 << ((firstblob + i) & 7));
321
322     DRelease(&pagehdbuf, 1);
323 }
324
325 /*
326  * Format an empty directory properly.  Note that the first 13 entries in a
327  * directory header page are allocated, 1 to the page header, 4 to the
328  * allocation map and 8 to the hash table.
329  */
330 int
331 afs_dir_MakeDir(dir_file_t dir, afs_int32 * me, afs_int32 * parent)
332 {
333     int i;
334     struct DirBuffer buffer;
335     struct DirHeader *dhp;
336
337     DNew(dir, 0, &buffer);
338     dhp = (struct DirHeader *)buffer.data;
339
340     dhp->header.pgcount = htons(1);
341     dhp->header.tag = htons(1234);
342     dhp->header.freecount = (EPP - DHE - 1);
343     dhp->header.freebitmap[0] = 0xff;
344     dhp->header.freebitmap[1] = 0x1f;
345     for (i = 2; i < EPP / 8; i++)
346         dhp->header.freebitmap[i] = 0;
347     dhp->alloMap[0] = (EPP - DHE - 1);
348     for (i = 1; i < MAXPAGES; i++)
349         dhp->alloMap[i] = EPP;
350     for (i = 0; i < NHASHENT; i++)
351         dhp->hashTable[i] = 0;
352     DRelease(&buffer, 1);
353     afs_dir_Create(dir, ".", me);
354     afs_dir_Create(dir, "..", parent);  /* Virtue is its own .. */
355     return 0;
356 }
357
358 /* Look up a file name in directory. */
359
360 int
361 afs_dir_Lookup(dir_file_t dir, char *entry, void *voidfid)
362 {
363     afs_int32 *fid = (afs_int32 *) voidfid;
364     struct DirBuffer firstbuf, prevbuf;
365     struct DirEntry *firstitem;
366
367     if (FindItem(dir, entry, &prevbuf, &firstbuf) != 0)
368         return ENOENT;
369     DRelease(&prevbuf, 0);
370     firstitem = (struct DirEntry *)firstbuf.data;
371
372     fid[1] = ntohl(firstitem->fid.vnode);
373     fid[2] = ntohl(firstitem->fid.vunique);
374     DRelease(&firstbuf, 0);
375     return 0;
376 }
377
378 /* Look up a file name in directory. */
379
380 int
381 afs_dir_LookupOffset(dir_file_t dir, char *entry, void *voidfid,
382                      long *offsetp)
383 {
384     afs_int32 *fid = (afs_int32 *) voidfid;
385     struct DirBuffer firstbuf, prevbuf;
386     struct DirEntry *firstitem;
387
388     if (FindItem(dir, entry, &prevbuf, &firstbuf) != 0)
389         return ENOENT;
390     DRelease(&prevbuf, 0);
391     firstitem = (struct DirEntry *)firstbuf.data;
392
393     fid[1] = ntohl(firstitem->fid.vnode);
394     fid[2] = ntohl(firstitem->fid.vunique);
395     if (offsetp)
396         *offsetp = DVOffset(&firstbuf);
397     DRelease(&firstbuf, 0);
398     return 0;
399 }
400
401 /*
402  * Enumerate the contents of a directory. Break when hook function
403  * returns non 0.
404  */
405
406 int
407 afs_dir_EnumerateDir(dir_file_t dir, int (*proc) (void *, char *name,
408                                                   afs_int32 vnode,
409                                                   afs_int32 unique),
410                      void *hook)
411 {
412     int i;
413     int num;
414     struct DirBuffer headerbuf, entrybuf;
415     struct DirHeader *dhp;
416     struct DirEntry *ep;
417     int code = 0;
418
419     if (DRead(dir, 0, &headerbuf) != 0)
420         return EIO;
421     dhp = (struct DirHeader *)headerbuf.data;
422
423     for (i = 0; i < NHASHENT; i++) {
424         /* For each hash chain, enumerate everyone on the list. */
425         num = ntohs(dhp->hashTable[i]);
426         while (num != 0) {
427             /* Walk down the hash table list. */
428             DErrno = 0;
429             if (afs_dir_GetBlob(dir, num, &entrybuf) != 0) {
430                 if (DErrno) {
431                     /* we failed, return why */
432                     DRelease(&headerbuf, 0);
433                     return DErrno;
434                 }
435                 break;
436             }
437             ep = (struct DirEntry *)entrybuf.data;
438
439             num = ntohs(ep->next);
440             code = (*proc) (hook, ep->name, ntohl(ep->fid.vnode),
441                             ntohl(ep->fid.vunique));
442             DRelease(&entrybuf, 0);
443             if (code)
444                 break;
445         }
446     }
447     DRelease(&headerbuf, 0);
448     return 0;
449 }
450
451 int
452 afs_dir_IsEmpty(dir_file_t dir)
453 {
454     /* Enumerate the contents of a directory. */
455     int i;
456     int num;
457     struct DirBuffer headerbuf, entrybuf;
458     struct DirHeader *dhp;
459     struct DirEntry *ep;
460
461     if (DRead(dir, 0, &headerbuf) != 0)
462         return 0;
463     dhp = (struct DirHeader *)headerbuf.data;
464
465     for (i = 0; i < NHASHENT; i++) {
466         /* For each hash chain, enumerate everyone on the list. */
467         num = ntohs(dhp->hashTable[i]);
468         while (num != 0) {
469             /* Walk down the hash table list. */
470             if (afs_dir_GetBlob(dir, num, &entrybuf) != 0);
471                 break;
472             ep = (struct DirEntry *)entrybuf.data;
473             if (strcmp(ep->name, "..") && strcmp(ep->name, ".")) {
474                 DRelease(&entrybuf, 0);
475                 DRelease(&headerbuf, 0);
476                 return 1;
477             }
478             num = ntohs(ep->next);
479             DRelease(&entrybuf, 0);
480         }
481     }
482     DRelease(&headerbuf, 0);
483     return 0;
484 }
485
486 int
487 afs_dir_GetBlob(dir_file_t dir, afs_int32 blobno, struct DirBuffer *buffer)
488 {
489     int code;
490
491     memset(buffer, 0, sizeof(struct DirBuffer));
492
493     code = DRead(dir, blobno >> LEPP, buffer);
494     if (code)
495         return code;
496
497     buffer->data = (void *)(((long)buffer->data) + 32 * (blobno & (EPP - 1)));
498
499     return 0;
500 }
501
502 int
503 afs_dir_DirHash(char *string)
504 {
505     /* Hash a string to a number between 0 and NHASHENT. */
506     unsigned char tc;
507     unsigned int hval;
508     int tval;
509     hval = 0;
510     while ((tc = (*string++))) {
511         hval *= 173;
512         hval += tc;
513     }
514     tval = hval & (NHASHENT - 1);
515     if (tval == 0)
516         return tval;
517     else if (hval >= 1<<31)
518         tval = NHASHENT - tval;
519     return tval;
520 }
521
522
523 /* Find a directory entry, given its name.  This entry returns a pointer
524  * to a locked buffer, and a pointer to a locked buffer (in previtem)
525  * referencing the found item (to aid the delete code).  If no entry is
526  * found, however, no items are left locked, and a null pointer is
527  * returned instead. */
528
529 static int
530 FindItem(dir_file_t dir, char *ename, struct DirBuffer *prevbuf,
531          struct DirBuffer *itembuf )
532 {
533     int i, code;
534     struct DirBuffer curr, prev;
535     struct DirHeader *dhp;
536     struct DirEntry *tp;
537
538     memset(prevbuf, 0, sizeof(struct DirBuffer));
539     memset(itembuf, 0, sizeof(struct DirBuffer));
540
541     code = DRead(dir, 0, &prev);
542     if (code)
543         return code;
544     dhp = (struct DirHeader *)prev.data;
545
546     i = afs_dir_DirHash(ename);
547     if (dhp->hashTable[i] == 0) {
548         /* no such entry */
549         DRelease(&prev, 0);
550         return ENOENT;
551     }
552
553     code = afs_dir_GetBlob(dir, (u_short) ntohs(dhp->hashTable[i]),
554                            &curr);
555     if (code) {
556         DRelease(&prev, 0);
557         return code;
558     }
559
560     prev.data = &(dhp->hashTable[i]);
561
562     while (1) {
563         /* Look at each entry on the hash chain */
564         tp = (struct DirEntry *)curr.data;
565         if (!strcmp(ename, tp->name)) {
566             /* Found it! */
567             *prevbuf = prev;
568             *itembuf = curr;
569             return 0;
570         }
571         DRelease(&prev, 0);
572         if (tp->next == 0) {
573             /* The end of the line */
574             DRelease(&curr, 0);
575             return ENOENT;
576         }
577
578         prev = curr;
579         prev.data = &(tp->next);
580
581         code = afs_dir_GetBlob(dir, (u_short) ntohs(tp->next), &curr);
582         if (code) {
583             DRelease(&prev, 0);
584             return code;
585         }
586     }
587     /* Never reached */
588 }
589
590 static int
591 FindFid (void *dir, afs_uint32 vnode, afs_uint32 unique,
592          struct DirBuffer *itembuf)
593 {
594     /* Find a directory entry, given the vnode and uniquifier of a object.
595      * This entry returns a pointer to a locked buffer.  If no entry is found,
596      * however, no items are left locked, and a null pointer is returned
597      * instead.
598      */
599     int i, code;
600     unsigned short next;
601     struct DirBuffer curr, header;
602     struct DirHeader *dhp;
603     struct DirEntry *tp;
604
605     memset(itembuf, 0, sizeof(struct DirBuffer));
606
607     code = DRead(dir, 0, &header);
608     if (code)
609         return code;
610     dhp = (struct DirHeader *)header.data;
611
612     for (i=0; i<NHASHENT; i++) {
613         if (dhp->hashTable[i] != 0) {
614             code = afs_dir_GetBlob(dir, (u_short)ntohs(dhp->hashTable[i]),
615                                    &curr);
616             if (code) {
617                 DRelease(&header, 0);
618                 return code;
619             }
620
621             while (curr.data != NULL) {
622                 tp = (struct DirEntry *)curr.data;
623
624                 if (vnode == ntohl(tp->fid.vnode)
625                     && unique == ntohl(tp->fid.vunique)) {
626                     DRelease(&header, 0);
627                     *itembuf = curr;
628                     return 0;
629                 }
630
631                 next = tp->next;
632                 DRelease(&curr, 0);
633
634                 if (next == 0)
635                     break;
636
637                 code = afs_dir_GetBlob(dir, (u_short)ntohs(next), &curr);
638                 if (code) {
639                     DRelease(&header, 0);
640                     return code;
641                 }
642             }
643         }
644     }
645     DRelease(&header, 0);
646     return ENOENT;
647 }
648
649 int
650 afs_dir_InverseLookup(void *dir, afs_uint32 vnode, afs_uint32 unique,
651                       char *name, afs_uint32 length)
652 {
653     /* Look for the name pointing to given vnode and unique in a directory */
654     struct DirBuffer entrybuf;
655     struct DirEntry *entry;
656     int code = 0;
657
658     if (FindFid(dir, vnode, unique, &entrybuf) != 0)
659         return ENOENT;
660     entry = (struct DirEntry *)entrybuf.data;
661
662     if (strlen(entry->name) >= length)
663         code = E2BIG;
664     else
665         strcpy(name, entry->name);
666     DRelease(&entrybuf, 0);
667     return code;
668 }
669
670 /*!
671  * Change an entry fid.
672  *
673  * \param dir
674  * \param entry The entry name.
675  * \param old_fid The old find in MKFid format (host order).
676  * It can be omitted if you don't need a safety check...
677  * \param new_fid The new find in MKFid format (host order).
678  */
679 int
680 afs_dir_ChangeFid(dir_file_t dir, char *entry, afs_uint32 *old_fid,
681                   afs_uint32 *new_fid)
682 {
683     struct DirBuffer prevbuf, entrybuf;
684     struct DirEntry *firstitem;
685     struct MKFid *fid_old = (struct MKFid *) old_fid;
686     struct MKFid *fid_new = (struct MKFid *) new_fid;
687
688     /* Find entry. */
689     if (FindItem(dir, entry, &prevbuf, &entrybuf) != 0)
690         return ENOENT;
691     firstitem = (struct DirEntry *)entrybuf.data;
692     DRelease(&prevbuf, 1);
693
694     /* Replace fid. */
695     if (!old_fid ||
696         ((htonl(fid_old->vnode) == firstitem->fid.vnode) &&
697         (htonl(fid_old->vunique) == firstitem->fid.vunique))) {
698
699         firstitem->fid.vnode = htonl(fid_new->vnode);
700         firstitem->fid.vunique = htonl(fid_new->vunique);
701     }
702
703     DRelease(&entrybuf, 1);
704
705     return 0;
706 }