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