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