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