2 * Copyright 2000, International Business Machines Corporation and others.
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
10 #include <afsconfig.h>
11 #include <afs/param.h>
14 # if !defined(UKERNEL)
16 # if !defined(AFS_LINUX26_ENV)
22 # include "h/sysmacros.h"
23 # include "h/signal.h"
27 # if defined(AFS_AIX_ENV) || defined(AFS_SGI_ENV) || defined(AFS_SUN5_ENV) || defined(AFS_LINUX20_ENV)
30 # if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX20_ENV)
31 # include "h/kernel.h"
34 # if defined(AFS_SUN5_ENV) || defined(AFS_HPUX_ENV) || defined(AFS_FBSD_ENV) || defined(AFS_DARWIN80_ENV)
35 # include "afs/sysincludes.h"
37 # if !defined(AFS_SGI64_ENV) && !defined(AFS_DARWIN_ENV) && !defined(AFS_OBSD48_ENV) && !defined(AFS_NBSD_ENV)
39 # endif /* AFS_SGI64_ENV */
42 # include <sys/mount.h>
43 # include <sys/vnode.h>
44 # include <ufs/inode.h>
46 # if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX20_ENV) && !defined(AFS_HPUX110_ENV)
49 # ifndef AFS_LINUX20_ENV
50 # include "netinet/in.h"
52 # else /* !defined(UKERNEL) */
53 # include "afs/stds.h"
54 # include "afs/sysincludes.h"
55 # endif /* !defined(UKERNEL) */
58 /* These are needed because afs_prototypes.h is not included here */
61 extern int DRead(struct dcache
*adc
, int page
, struct DirBuffer
*);
62 extern int DNew(struct dcache
*adc
, int page
, struct DirBuffer
*);
64 # include "afs/afs_osi.h"
68 # ifdef AFS_LINUX20_ENV
69 # include "h/string.h"
80 /* Local static prototypes */
81 static int FindBlobs(dir_file_t
, int);
82 static void AddPage(dir_file_t
, int);
83 static void FreeBlobs(dir_file_t
, int, int);
84 static int FindItem(dir_file_t
, char *, struct DirBuffer
*,
87 /* Find out how many entries are required to store a name. */
89 afs_dir_NameBlobs(char *name
)
93 return 1 + ((i
+ 15) >> 5);
96 /* Create an entry in a file. Dir is a file representation, while entry is
99 afs_dir_Create(dir_file_t dir
, char *entry
, void *voidfid
)
101 afs_int32
*vfid
= (afs_int32
*) voidfid
;
104 struct DirBuffer entrybuf
, prevbuf
, headerbuf
;
106 struct DirHeader
*dhp
;
109 /* check name quality */
113 /* First check if file already exists. */
114 code
= FindItem(dir
, entry
, &prevbuf
, &entrybuf
);
115 if (code
&& code
!= ENOENT
) {
119 DRelease(&entrybuf
, 0);
120 DRelease(&prevbuf
, 0);
124 blobs
= afs_dir_NameBlobs(entry
); /* number of entries required */
125 firstelt
= FindBlobs(dir
, blobs
);
127 return EFBIG
; /* directory is full */
129 /* First, we fill in the directory entry. */
130 if (afs_dir_GetBlob(dir
, firstelt
, &entrybuf
) != 0)
132 ep
= (struct DirEntry
*)entrybuf
.data
;
135 ep
->fid
.vnode
= htonl(vfid
[1]);
136 ep
->fid
.vunique
= htonl(vfid
[2]);
137 strcpy(ep
->name
, entry
);
139 /* Now we just have to thread it on the hash table list. */
140 if (DRead(dir
, 0, &headerbuf
) != 0) {
141 DRelease(&entrybuf
, 1);
144 dhp
= (struct DirHeader
*)headerbuf
.data
;
146 i
= afs_dir_DirHash(entry
);
147 ep
->next
= dhp
->hashTable
[i
];
148 dhp
->hashTable
[i
] = htons(firstelt
);
149 DRelease(&headerbuf
, 1);
150 DRelease(&entrybuf
, 1);
155 afs_dir_Length(dir_file_t dir
)
158 struct DirBuffer headerbuf
;
159 struct DirHeader
*dhp
;
161 if (DRead(dir
, 0, &headerbuf
) != 0)
163 dhp
= (struct DirHeader
*)headerbuf
.data
;
165 if (dhp
->header
.pgcount
!= 0)
166 ctr
= ntohs(dhp
->header
.pgcount
);
168 /* old style, count the pages */
170 for (i
= 0; i
< MAXPAGES
; i
++)
171 if (dhp
->alloMap
[i
] != EPP
)
174 DRelease(&headerbuf
, 0);
175 return ctr
* AFS_PAGESIZE
;
178 /* Delete an entry from a directory, including update of all free entry
181 afs_dir_Delete(dir_file_t dir
, char *entry
)
185 struct DirBuffer entrybuf
, prevbuf
;
186 struct DirEntry
*firstitem
;
187 unsigned short *previtem
;
190 code
= FindItem(dir
, entry
, &prevbuf
, &entrybuf
);
195 firstitem
= (struct DirEntry
*)entrybuf
.data
;
196 previtem
= (unsigned short *)prevbuf
.data
;
198 *previtem
= firstitem
->next
;
199 DRelease(&prevbuf
, 1);
200 index
= DVOffset(&entrybuf
) / 32;
201 nitems
= afs_dir_NameBlobs(firstitem
->name
);
202 /* Clear entire DirEntry and any DirXEntry extensions */
203 memset(firstitem
, 0, nitems
* sizeof(*firstitem
));
204 DRelease(&entrybuf
, 1);
205 FreeBlobs(dir
, index
, nitems
);
209 /* Find a bunch of contiguous entries; at least nblobs in a row. */
211 FindBlobs(dir_file_t dir
, int nblobs
)
215 struct DirBuffer headerbuf
, pagebuf
;
216 struct DirHeader
*dhp
;
217 struct PageHeader
*pp
;
220 /* read the dir header in first. */
221 if (DRead(dir
, 0, &headerbuf
) != 0)
223 dhp
= (struct DirHeader
*)headerbuf
.data
;
225 for (i
= 0; i
< BIGMAXPAGES
; i
++) {
226 if (i
>= MAXPAGES
|| dhp
->alloMap
[i
] >= nblobs
) {
227 /* if page could contain enough entries */
228 /* If there are EPP free entries, then the page is not even allocated. */
230 /* this pages exists past the end of the old-style dir */
231 pgcount
= ntohs(dhp
->header
.pgcount
);
234 dhp
->header
.pgcount
= htons(pgcount
);
236 if (i
> pgcount
- 1) {
237 /* this page is bigger than last allocated page */
239 dhp
->header
.pgcount
= htons(i
+ 1);
241 } else if (dhp
->alloMap
[i
] == EPP
) {
242 /* Add the page to the directory. */
244 dhp
->alloMap
[i
] = EPP
- 1;
245 dhp
->header
.pgcount
= htons(i
+ 1);
248 /* read the page in. */
249 if (DRead(dir
, i
, &pagebuf
) != 0) {
252 pp
= (struct PageHeader
*)pagebuf
.data
;
253 for (j
= 0; j
<= EPP
- nblobs
; j
++) {
255 for (k
= 0; k
< nblobs
; k
++)
256 if ((pp
->freebitmap
[(j
+ k
) >> 3] >> ((j
+ k
) & 7)) & 1) {
265 /* Here we have the first index in j. We update the allocation maps
266 * and free up any resources we've got allocated. */
268 dhp
->alloMap
[i
] -= nblobs
;
269 DRelease(&headerbuf
, 1);
270 for (k
= 0; k
< nblobs
; k
++)
271 pp
->freebitmap
[(j
+ k
) >> 3] |= 1 << ((j
+ k
) & 7);
272 DRelease(&pagebuf
, 1);
275 DRelease(&pagebuf
, 0); /* This dir page is unchanged. */
278 /* If we make it here, the directory is full. */
279 DRelease(&headerbuf
, 1);
284 AddPage(dir_file_t dir
, int pageno
)
285 { /* Add a page to a directory. */
287 struct PageHeader
*pp
;
288 struct DirBuffer pagebuf
;
290 /* Get a new buffer labelled dir,pageno */
291 DNew(dir
, pageno
, &pagebuf
);
292 pp
= (struct PageHeader
*)pagebuf
.data
;
294 pp
->tag
= htons(1234);
297 pp
->freecount
= EPP
- 1; /* The first dude is already allocated */
298 pp
->freebitmap
[0] = 0x01;
299 for (i
= 1; i
< EPP
/ 8; i
++) /* It's a constant */
300 pp
->freebitmap
[i
] = 0;
301 DRelease(&pagebuf
, 1);
304 /* Free a whole bunch of directory entries. */
307 FreeBlobs(dir_file_t dir
, int firstblob
, int nblobs
)
311 struct DirBuffer headerbuf
, pagehdbuf
;
312 struct DirHeader
*dhp
;
313 struct PageHeader
*pp
;
314 page
= firstblob
/ EPP
;
315 firstblob
-= EPP
* page
; /* convert to page-relative entry */
317 if (DRead(dir
, 0, &headerbuf
) != 0)
319 dhp
= (struct DirHeader
*)headerbuf
.data
;
322 dhp
->alloMap
[page
] += nblobs
;
324 DRelease(&headerbuf
, 1);
326 if (DRead(dir
, page
, &pagehdbuf
) != 0)
328 pp
= (struct PageHeader
*)pagehdbuf
.data
;
330 for (i
= 0; i
< nblobs
; i
++)
331 pp
->freebitmap
[(firstblob
+ i
) >> 3] &= ~(1 << ((firstblob
+ i
) & 7));
333 DRelease(&pagehdbuf
, 1);
337 * Format an empty directory properly. Note that the first 13 entries in a
338 * directory header page are allocated, 1 to the page header, 4 to the
339 * allocation map and 8 to the hash table.
342 afs_dir_MakeDir(dir_file_t dir
, afs_int32
* me
, afs_int32
* parent
)
345 struct DirBuffer buffer
;
346 struct DirHeader
*dhp
;
348 DNew(dir
, 0, &buffer
);
349 dhp
= (struct DirHeader
*)buffer
.data
;
351 dhp
->header
.pgcount
= htons(1);
352 dhp
->header
.tag
= htons(1234);
353 dhp
->header
.freecount
= (EPP
- DHE
- 1);
354 dhp
->header
.freebitmap
[0] = 0xff;
355 dhp
->header
.freebitmap
[1] = 0x1f;
356 for (i
= 2; i
< EPP
/ 8; i
++)
357 dhp
->header
.freebitmap
[i
] = 0;
358 dhp
->alloMap
[0] = (EPP
- DHE
- 1);
359 for (i
= 1; i
< MAXPAGES
; i
++)
360 dhp
->alloMap
[i
] = EPP
;
361 for (i
= 0; i
< NHASHENT
; i
++)
362 dhp
->hashTable
[i
] = 0;
363 DRelease(&buffer
, 1);
364 afs_dir_Create(dir
, ".", me
);
365 afs_dir_Create(dir
, "..", parent
); /* Virtue is its own .. */
369 /* Look up a file name in directory. */
372 afs_dir_Lookup(dir_file_t dir
, char *entry
, void *voidfid
)
374 afs_int32
*fid
= (afs_int32
*) voidfid
;
375 struct DirBuffer firstbuf
, prevbuf
;
376 struct DirEntry
*firstitem
;
379 code
= FindItem(dir
, entry
, &prevbuf
, &firstbuf
);
383 DRelease(&prevbuf
, 0);
384 firstitem
= (struct DirEntry
*)firstbuf
.data
;
386 fid
[1] = ntohl(firstitem
->fid
.vnode
);
387 fid
[2] = ntohl(firstitem
->fid
.vunique
);
388 DRelease(&firstbuf
, 0);
392 /* Look up a file name in directory. */
395 afs_dir_LookupOffset(dir_file_t dir
, char *entry
, void *voidfid
,
398 afs_int32
*fid
= (afs_int32
*) voidfid
;
399 struct DirBuffer firstbuf
, prevbuf
;
400 struct DirEntry
*firstitem
;
403 code
= FindItem(dir
, entry
, &prevbuf
, &firstbuf
);
407 DRelease(&prevbuf
, 0);
408 firstitem
= (struct DirEntry
*)firstbuf
.data
;
410 fid
[1] = ntohl(firstitem
->fid
.vnode
);
411 fid
[2] = ntohl(firstitem
->fid
.vunique
);
413 *offsetp
= DVOffset(&firstbuf
);
414 DRelease(&firstbuf
, 0);
419 * Enumerate the contents of a directory. Break when hook function
424 afs_dir_EnumerateDir(dir_file_t dir
, int (*proc
) (void *, char *name
,
431 struct DirBuffer headerbuf
, entrybuf
;
432 struct DirHeader
*dhp
;
437 if (DRead(dir
, 0, &headerbuf
) != 0)
439 dhp
= (struct DirHeader
*)headerbuf
.data
;
441 for (i
= 0; i
< NHASHENT
; i
++) {
442 /* For each hash chain, enumerate everyone on the list. */
443 num
= ntohs(dhp
->hashTable
[i
]);
445 while (num
!= 0 && elements
< BIGMAXPAGES
* EPP
) {
448 /* Walk down the hash table list. */
449 code
= afs_dir_GetVerifiedBlob(dir
, num
, &entrybuf
);
453 ep
= (struct DirEntry
*)entrybuf
.data
;
455 DRelease(&entrybuf
, 0);
459 num
= ntohs(ep
->next
);
460 code
= (*proc
) (hook
, ep
->name
, ntohl(ep
->fid
.vnode
),
461 ntohl(ep
->fid
.vunique
));
462 DRelease(&entrybuf
, 0);
469 DRelease(&headerbuf
, 0);
474 afs_dir_IsEmpty(dir_file_t dir
)
476 /* Enumerate the contents of a directory. */
479 struct DirBuffer headerbuf
, entrybuf
;
480 struct DirHeader
*dhp
;
484 if (DRead(dir
, 0, &headerbuf
) != 0)
486 dhp
= (struct DirHeader
*)headerbuf
.data
;
488 for (i
= 0; i
< NHASHENT
; i
++) {
489 /* For each hash chain, enumerate everyone on the list. */
490 num
= ntohs(dhp
->hashTable
[i
]);
492 while (num
!= 0 && elements
< BIGMAXPAGES
* EPP
) {
494 /* Walk down the hash table list. */
495 if (afs_dir_GetVerifiedBlob(dir
, num
, &entrybuf
) != 0)
497 ep
= (struct DirEntry
*)entrybuf
.data
;
498 if (strcmp(ep
->name
, "..") && strcmp(ep
->name
, ".")) {
499 DRelease(&entrybuf
, 0);
500 DRelease(&headerbuf
, 0);
503 num
= ntohs(ep
->next
);
504 DRelease(&entrybuf
, 0);
507 DRelease(&headerbuf
, 0);
511 /* Return a pointer to an entry, given its number. Also return the maximum
512 * size of the entry, which is determined by its position within the directory
517 GetBlobWithLimit(dir_file_t dir
, afs_int32 blobno
,
518 struct DirBuffer
*buffer
, afs_size_t
*maxlen
)
524 memset(buffer
, 0, sizeof(struct DirBuffer
));
526 code
= DRead(dir
, blobno
>> LEPP
, buffer
);
530 pos
= 32 * (blobno
& (EPP
- 1));
532 *maxlen
= AFS_PAGESIZE
- pos
- 1;
534 buffer
->data
= (void *)(((char *)buffer
->data
) + pos
);
539 /* Given an entries number, return a pointer to that entry */
541 afs_dir_GetBlob(dir_file_t dir
, afs_int32 blobno
, struct DirBuffer
*buffer
)
543 afs_size_t maxlen
= 0;
544 return GetBlobWithLimit(dir
, blobno
, buffer
, &maxlen
);
547 /* Return an entry, having verified that the name held within the entry
548 * doesn't overflow off the end of the directory page it is contained
553 afs_dir_GetVerifiedBlob(dir_file_t file
, afs_int32 blobno
,
554 struct DirBuffer
*outbuf
)
556 struct DirEntry
*dir
;
557 struct DirBuffer buffer
;
562 code
= GetBlobWithLimit(file
, blobno
, &buffer
, &maxlen
);
566 dir
= (struct DirEntry
*)buffer
.data
;
568 /* A blob is only valid if the name within it is NULL terminated before
569 * the end of the blob's containing page */
570 for (cp
= dir
->name
; *cp
!= '\0' && cp
< ((char *)dir
) + maxlen
; cp
++);
573 DRelease(&buffer
, 0);
582 afs_dir_DirHash(char *string
)
584 /* Hash a string to a number between 0 and NHASHENT. */
589 while ((tc
= (*string
++))) {
593 tval
= hval
& (NHASHENT
- 1);
596 else if (hval
>= 1u<<31)
597 tval
= NHASHENT
- tval
;
602 /* Find a directory entry, given its name. This entry returns a pointer
603 * to a locked buffer, and a pointer to a locked buffer (in previtem)
604 * referencing the found item (to aid the delete code). If no entry is
605 * found, however, no items are left locked, and a null pointer is
606 * returned instead. */
609 FindItem(dir_file_t dir
, char *ename
, struct DirBuffer
*prevbuf
,
610 struct DirBuffer
*itembuf
)
613 struct DirBuffer curr
, prev
;
614 struct DirHeader
*dhp
;
618 memset(prevbuf
, 0, sizeof(struct DirBuffer
));
619 memset(itembuf
, 0, sizeof(struct DirBuffer
));
621 code
= DRead(dir
, 0, &prev
);
624 dhp
= (struct DirHeader
*)prev
.data
;
626 i
= afs_dir_DirHash(ename
);
627 if (dhp
->hashTable
[i
] == 0) {
633 code
= afs_dir_GetVerifiedBlob(dir
,
634 (u_short
) ntohs(dhp
->hashTable
[i
]),
640 prev
.data
= &(dhp
->hashTable
[i
]);
642 /* Detect circular hash chains. Absolute max size of a directory */
643 while (elements
< BIGMAXPAGES
* EPP
) {
646 /* Look at each entry on the hash chain */
647 tp
= (struct DirEntry
*)curr
.data
;
648 if (!strcmp(ename
, tp
->name
)) {
658 prev
.data
= &(tp
->next
);
661 /* The end of the line */
666 code
= afs_dir_GetVerifiedBlob(dir
, (u_short
) ntohs(tp
->next
),
672 /* If we've reached here, we've hit our loop limit. Something is weird with
673 * the directory; maybe a circular hash chain? */
682 FindFid (void *dir
, afs_uint32 vnode
, afs_uint32 unique
,
683 struct DirBuffer
*itembuf
)
685 /* Find a directory entry, given the vnode and uniquifier of a object.
686 * This entry returns a pointer to a locked buffer. If no entry is found,
687 * however, no items are left locked, and a null pointer is returned
692 struct DirBuffer curr
, header
;
693 struct DirHeader
*dhp
;
697 memset(itembuf
, 0, sizeof(struct DirBuffer
));
699 code
= DRead(dir
, 0, &header
);
702 dhp
= (struct DirHeader
*)header
.data
;
704 for (i
=0; i
<NHASHENT
; i
++) {
705 if (dhp
->hashTable
[i
] != 0) {
706 code
= afs_dir_GetVerifiedBlob(dir
,
707 (u_short
)ntohs(dhp
->hashTable
[i
]),
710 DRelease(&header
, 0);
714 while(curr
.data
!= NULL
&& elements
< BIGMAXPAGES
* EPP
) {
716 tp
= (struct DirEntry
*)curr
.data
;
718 if (vnode
== ntohl(tp
->fid
.vnode
)
719 && unique
== ntohl(tp
->fid
.vunique
)) {
720 DRelease(&header
, 0);
731 code
= afs_dir_GetVerifiedBlob(dir
, (u_short
)ntohs(next
),
734 DRelease(&header
, 0);
740 DRelease(&header
, 0);
745 afs_dir_InverseLookup(void *dir
, afs_uint32 vnode
, afs_uint32 unique
,
746 char *name
, afs_uint32 length
)
748 /* Look for the name pointing to given vnode and unique in a directory */
749 struct DirBuffer entrybuf
;
750 struct DirEntry
*entry
;
753 code
= FindFid(dir
, vnode
, unique
, &entrybuf
);
757 entry
= (struct DirEntry
*)entrybuf
.data
;
759 if (strlen(entry
->name
) >= length
)
762 strcpy(name
, entry
->name
);
763 DRelease(&entrybuf
, 0);
768 * Change an entry fid.
771 * \param entry The entry name.
772 * \param old_fid The old find in MKFid format (host order).
773 * It can be omitted if you don't need a safety check...
774 * \param new_fid The new find in MKFid format (host order).
777 afs_dir_ChangeFid(dir_file_t dir
, char *entry
, afs_uint32
*old_fid
,
780 struct DirBuffer prevbuf
, entrybuf
;
781 struct DirEntry
*firstitem
;
782 struct MKFid
*fid_old
= (struct MKFid
*) old_fid
;
783 struct MKFid
*fid_new
= (struct MKFid
*) new_fid
;
787 code
= FindItem(dir
, entry
, &prevbuf
, &entrybuf
);
791 firstitem
= (struct DirEntry
*)entrybuf
.data
;
792 DRelease(&prevbuf
, 1);
796 ((htonl(fid_old
->vnode
) == firstitem
->fid
.vnode
) &&
797 (htonl(fid_old
->vunique
) == firstitem
->fid
.vunique
))) {
799 firstitem
->fid
.vnode
= htonl(fid_new
->vnode
);
800 firstitem
->fid
.vunique
= htonl(fid_new
->vunique
);
803 DRelease(&entrybuf
, 1);