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