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