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