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>
12 #include <afs/afsint.h>
15 # if !defined(UKERNEL)
17 # if !defined(AFS_LINUX_ENV)
23 # include "h/sysmacros.h"
24 # include "h/signal.h"
28 # if defined(AFS_AIX_ENV) || defined(AFS_SGI_ENV) || defined(AFS_SUN5_ENV) || defined(AFS_LINUX_ENV)
31 # if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX_ENV)
32 # include "h/kernel.h"
35 # include "afs/sysincludes.h"
36 # if !defined(AFS_SGI_ENV) && !defined(AFS_DARWIN_ENV) && !defined(AFS_OBSD48_ENV) && !defined(AFS_NBSD_ENV)
38 # endif /* AFS_SGI_ENV */
40 # if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX_ENV) && !defined(AFS_HPUX110_ENV)
43 # ifndef AFS_LINUX_ENV
44 # include "netinet/in.h"
46 # include "afsincludes.h"
47 # else /* !defined(UKERNEL) */
48 # include "afs/stds.h"
49 # include "afs/sysincludes.h"
50 # include "afsincludes.h"
51 # endif /* !defined(UKERNEL) */
54 /* These are needed because afs_prototypes.h is not included here */
57 extern int DRead(struct dcache *adc, int page, struct DirBuffer *);
58 extern int DNew(struct dcache *adc, int page, struct DirBuffer *);
60 # include "afs/afs_osi.h"
65 # include "h/string.h"
74 /* Local static prototypes */
75 static int FindBlobs(dir_file_t, int);
76 static int AddPage(dir_file_t, int);
77 static void FreeBlobs(dir_file_t, int, int);
78 static int FindItem(dir_file_t, char *, struct DirBuffer *,
81 /* Find out how many entries are required to store a name. */
83 afs_dir_NameBlobs(char *name)
87 return 1 + ((i + 15) >> 5);
90 /* Create an entry in a file. Dir is a file representation, while entry is
93 afs_dir_Create(dir_file_t dir, char *entry, void *voidfid)
95 afs_int32 *vfid = (afs_int32 *) voidfid;
98 struct DirBuffer entrybuf, prevbuf, headerbuf;
99 struct DirEntryFlex *ep;
100 struct DirHeader *dhp;
104 /* check name quality */
108 /* First check if file already exists. */
109 code = FindItem(dir, entry, &prevbuf, &entrybuf);
110 if (code && code != ENOENT) {
114 DRelease(&entrybuf, 0);
115 DRelease(&prevbuf, 0);
119 blobs = afs_dir_NameBlobs(entry); /* number of entries required */
120 firstelt = FindBlobs(dir, blobs);
122 return EFBIG; /* directory is full */
124 /* First, we fill in the directory entry. */
125 if (afs_dir_GetBlob(dir, firstelt, &entrybuf) != 0)
130 ep->fid.vnode = htonl(vfid[1]);
131 ep->fid.vunique = htonl(vfid[2]);
134 * Note, the size of ep->name does not represent the maximum size of the
135 * name. FindBlobs has already ensured that the name can fit.
137 rlen = strlcpy(ep->name, entry, AFSNAMEMAX + 1);
138 if (rlen >= AFSNAMEMAX + 1) {
139 DRelease(&entrybuf, 1);
143 /* Now we just have to thread it on the hash table list. */
144 if (DRead(dir, 0, &headerbuf) != 0) {
145 DRelease(&entrybuf, 1);
148 dhp = (struct DirHeader *)headerbuf.data;
150 i = afs_dir_DirHash(entry);
151 ep->next = dhp->hashTable[i];
152 dhp->hashTable[i] = htons(firstelt);
153 DRelease(&headerbuf, 1);
154 DRelease(&entrybuf, 1);
159 afs_dir_Length(dir_file_t dir)
162 struct DirBuffer headerbuf;
163 struct DirHeader *dhp;
165 if (DRead(dir, 0, &headerbuf) != 0)
167 dhp = (struct DirHeader *)headerbuf.data;
169 if (dhp->header.pgcount != 0)
170 ctr = ntohs(dhp->header.pgcount);
172 /* old style, count the pages */
174 for (i = 0; i < MAXPAGES; i++)
175 if (dhp->alloMap[i] != EPP)
178 DRelease(&headerbuf, 0);
179 return ctr * AFS_PAGESIZE;
182 /* Delete an entry from a directory, including update of all free entry
185 afs_dir_Delete(dir_file_t dir, char *entry)
189 struct DirBuffer entrybuf, prevbuf;
190 struct DirEntry *firstitem;
191 unsigned short *previtem;
194 code = FindItem(dir, entry, &prevbuf, &entrybuf);
199 firstitem = (struct DirEntry *)entrybuf.data;
200 previtem = (unsigned short *)prevbuf.data;
202 *previtem = firstitem->next;
203 DRelease(&prevbuf, 1);
204 index = DVOffset(&entrybuf) / 32;
205 nitems = afs_dir_NameBlobs(firstitem->name);
206 /* Clear entire DirEntry and any DirXEntry extensions */
207 memset(firstitem, 0, nitems * sizeof(*firstitem));
208 DRelease(&entrybuf, 1);
209 FreeBlobs(dir, index, nitems);
214 * Find a bunch of contiguous entries; at least nblobs in a row.
216 * \param dir pointer to the directory object
217 * \param nblobs number of contiguous entries we need
219 * \return element number (directory entry) of the requested space
220 * \retval -1 failed to find 'nblobs' contiguous entries
223 FindBlobs(dir_file_t dir, int nblobs)
227 struct DirBuffer headerbuf, pagebuf;
228 struct DirHeader *dhp;
229 struct PageHeader *pp;
233 /* read the dir header in first. */
234 if (DRead(dir, 0, &headerbuf) != 0)
236 dhp = (struct DirHeader *)headerbuf.data;
238 for (i = 0; i < BIGMAXPAGES; i++) {
239 if (i >= MAXPAGES || dhp->alloMap[i] >= nblobs) {
240 /* if page could contain enough entries */
241 /* If there are EPP free entries, then the page is not even allocated. */
243 /* this pages exists past the end of the old-style dir */
244 pgcount = ntohs(dhp->header.pgcount);
247 dhp->header.pgcount = htons(pgcount);
249 if (i > pgcount - 1) {
250 /* this page is bigger than last allocated page */
251 code = AddPage(dir, i);
254 dhp->header.pgcount = htons(i + 1);
256 } else if (dhp->alloMap[i] == EPP) {
257 /* Add the page to the directory. */
258 code = AddPage(dir, i);
261 dhp->alloMap[i] = EPP - 1;
262 dhp->header.pgcount = htons(i + 1);
265 /* read the page in. */
266 if (DRead(dir, i, &pagebuf) != 0) {
269 pp = (struct PageHeader *)pagebuf.data;
270 for (j = 0; j <= EPP - nblobs; j++) {
272 for (k = 0; k < nblobs; k++)
273 if ((pp->freebitmap[(j + k) >> 3] >> ((j + k) & 7)) & 1) {
282 /* Here we have the first index in j. We update the allocation maps
283 * and free up any resources we've got allocated. */
285 dhp->alloMap[i] -= nblobs;
286 DRelease(&headerbuf, 1);
287 for (k = 0; k < nblobs; k++)
288 pp->freebitmap[(j + k) >> 3] |= 1 << ((j + k) & 7);
289 DRelease(&pagebuf, 1);
292 DRelease(&pagebuf, 0); /* This dir page is unchanged. */
295 /* If we make it here, the directory is full, or we encountered an I/O error. */
296 DRelease(&headerbuf, 1);
301 * Add a page to a directory object.
303 * \param dir pointer to the directory object
304 * \param pageno page number to add
307 * \retval non-zero return error from DNew
310 AddPage(dir_file_t dir, int pageno)
311 { /* Add a page to a directory. */
313 struct PageHeader *pp;
314 struct DirBuffer pagebuf;
317 /* Get a new buffer labelled dir,pageno */
318 code = DNew(dir, pageno, &pagebuf);
321 pp = (struct PageHeader *)pagebuf.data;
323 pp->tag = htons(1234);
326 pp->freecount = EPP - 1; /* The first dude is already allocated */
327 pp->freebitmap[0] = 0x01;
328 for (i = 1; i < EPP / 8; i++) /* It's a constant */
329 pp->freebitmap[i] = 0;
330 DRelease(&pagebuf, 1);
334 /* Free a whole bunch of directory entries. */
337 FreeBlobs(dir_file_t dir, int firstblob, int nblobs)
341 struct DirBuffer headerbuf, pagehdbuf;
342 struct DirHeader *dhp;
343 struct PageHeader *pp;
344 page = firstblob / EPP;
345 firstblob -= EPP * page; /* convert to page-relative entry */
347 if (DRead(dir, 0, &headerbuf) != 0)
349 dhp = (struct DirHeader *)headerbuf.data;
352 dhp->alloMap[page] += nblobs;
354 DRelease(&headerbuf, 1);
356 if (DRead(dir, page, &pagehdbuf) != 0)
358 pp = (struct PageHeader *)pagehdbuf.data;
360 for (i = 0; i < nblobs; i++)
361 pp->freebitmap[(firstblob + i) >> 3] &= ~(1 << ((firstblob + i) & 7));
363 DRelease(&pagehdbuf, 1);
367 * Format an empty directory properly. Note that the first 13 entries in a
368 * directory header page are allocated, 1 to the page header, 4 to the
369 * allocation map and 8 to the hash table.
371 * \param dir pointer to the directory object
372 * \param me fid (vnode+uniq) for new dir
373 * \param parent fid (vnode+uniq) for parent dir
376 * \retval nonzero error code
379 afs_dir_MakeDir(dir_file_t dir, afs_int32 * me, afs_int32 * parent)
382 struct DirBuffer buffer;
383 struct DirHeader *dhp;
386 code = DNew(dir, 0, &buffer);
389 dhp = (struct DirHeader *)buffer.data;
391 dhp->header.pgcount = htons(1);
392 dhp->header.tag = htons(1234);
393 dhp->header.freecount = (EPP - DHE - 1);
394 dhp->header.freebitmap[0] = 0xff;
395 dhp->header.freebitmap[1] = 0x1f;
396 for (i = 2; i < EPP / 8; i++)
397 dhp->header.freebitmap[i] = 0;
398 dhp->alloMap[0] = (EPP - DHE - 1);
399 for (i = 1; i < MAXPAGES; i++)
400 dhp->alloMap[i] = EPP;
401 for (i = 0; i < NHASHENT; i++)
402 dhp->hashTable[i] = 0;
403 DRelease(&buffer, 1);
404 code = afs_dir_Create(dir, ".", me);
407 code = afs_dir_Create(dir, "..", parent);
413 /* Look up a file name in directory. */
416 afs_dir_Lookup(dir_file_t dir, char *entry, void *voidfid)
418 afs_int32 *fid = (afs_int32 *) voidfid;
419 struct DirBuffer firstbuf, prevbuf;
420 struct DirEntry *firstitem;
423 code = FindItem(dir, entry, &prevbuf, &firstbuf);
427 DRelease(&prevbuf, 0);
428 firstitem = (struct DirEntry *)firstbuf.data;
430 fid[1] = ntohl(firstitem->fid.vnode);
431 fid[2] = ntohl(firstitem->fid.vunique);
432 DRelease(&firstbuf, 0);
436 /* Look up a file name in directory. */
439 afs_dir_LookupOffset(dir_file_t dir, char *entry, void *voidfid,
442 afs_int32 *fid = (afs_int32 *) voidfid;
443 struct DirBuffer firstbuf, prevbuf;
444 struct DirEntry *firstitem;
447 code = FindItem(dir, entry, &prevbuf, &firstbuf);
451 DRelease(&prevbuf, 0);
452 firstitem = (struct DirEntry *)firstbuf.data;
454 fid[1] = ntohl(firstitem->fid.vnode);
455 fid[2] = ntohl(firstitem->fid.vunique);
457 *offsetp = DVOffset(&firstbuf);
458 DRelease(&firstbuf, 0);
463 * Enumerate the contents of a directory. Break when hook function
468 afs_dir_EnumerateDir(dir_file_t dir, int (*proc) (void *, char *name,
475 struct DirBuffer headerbuf, entrybuf;
476 struct DirHeader *dhp;
481 if (DRead(dir, 0, &headerbuf) != 0)
483 dhp = (struct DirHeader *)headerbuf.data;
485 for (i = 0; i < NHASHENT; i++) {
486 /* For each hash chain, enumerate everyone on the list. */
487 num = ntohs(dhp->hashTable[i]);
489 while (num != 0 && elements < BIGMAXPAGES * EPP) {
492 /* Walk down the hash table list. */
493 code = afs_dir_GetVerifiedBlob(dir, num, &entrybuf);
497 ep = (struct DirEntry *)entrybuf.data;
499 DRelease(&entrybuf, 0);
503 num = ntohs(ep->next);
504 code = (*proc) (hook, ep->name, ntohl(ep->fid.vnode),
505 ntohl(ep->fid.vunique));
506 DRelease(&entrybuf, 0);
513 DRelease(&headerbuf, 0);
518 afs_dir_IsEmpty(dir_file_t dir)
520 /* Enumerate the contents of a directory. */
523 struct DirBuffer headerbuf, entrybuf;
524 struct DirHeader *dhp;
528 if (DRead(dir, 0, &headerbuf) != 0)
530 dhp = (struct DirHeader *)headerbuf.data;
532 for (i = 0; i < NHASHENT; i++) {
533 /* For each hash chain, enumerate everyone on the list. */
534 num = ntohs(dhp->hashTable[i]);
536 while (num != 0 && elements < BIGMAXPAGES * EPP) {
538 /* Walk down the hash table list. */
539 if (afs_dir_GetVerifiedBlob(dir, num, &entrybuf) != 0)
541 ep = (struct DirEntry *)entrybuf.data;
542 if (strcmp(ep->name, "..") && strcmp(ep->name, ".")) {
543 DRelease(&entrybuf, 0);
544 DRelease(&headerbuf, 0);
547 num = ntohs(ep->next);
548 DRelease(&entrybuf, 0);
551 DRelease(&headerbuf, 0);
555 /* Return a pointer to an entry, given its number. Also return the maximum
556 * size of the entry, which is determined by its position within the directory
559 * If physerr is supplied by caller, it will be set to:
560 * 0 for logical errors
561 * errno for physical errors
564 GetBlobWithLimit(dir_file_t dir, afs_int32 blobno,
565 struct DirBuffer *buffer, afs_size_t *maxlen, int *physerr)
571 memset(buffer, 0, sizeof(struct DirBuffer));
573 code = DReadWithErrno(dir, blobno >> LEPP, buffer, physerr);
577 pos = 32 * (blobno & (EPP - 1));
579 *maxlen = AFS_PAGESIZE - pos - 1;
581 buffer->data = (void *)(((char *)buffer->data) + pos);
587 * Given an entry's number, return a pointer to that entry.
588 * If physerr is supplied by caller, it will be set to:
589 * 0 for logical errors
590 * errno for physical errors
593 afs_dir_GetBlobWithErrno(dir_file_t dir, afs_int32 blobno, struct DirBuffer *buffer,
596 afs_size_t maxlen = 0;
597 return GetBlobWithLimit(dir, blobno, buffer, &maxlen, physerr);
600 /* Given an entries number, return a pointer to that entry */
602 afs_dir_GetBlob(dir_file_t dir, afs_int32 blobno, struct DirBuffer *buffer)
604 afs_size_t maxlen = 0;
605 return GetBlobWithLimit(dir, blobno, buffer, &maxlen, NULL);
608 /* Return an entry, having verified that the name held within the entry
609 * doesn't overflow off the end of the directory page it is contained
614 afs_dir_GetVerifiedBlob(dir_file_t file, afs_int32 blobno,
615 struct DirBuffer *outbuf)
617 struct DirEntry *dir;
618 struct DirBuffer buffer;
623 code = GetBlobWithLimit(file, blobno, &buffer, &maxlen, NULL);
627 dir = (struct DirEntry *)buffer.data;
629 /* A blob is only valid if the name within it is NULL terminated before
630 * the end of the blob's containing page */
631 for (cp = dir->name; *cp != '\0' && cp < ((char *)dir) + maxlen; cp++);
634 DRelease(&buffer, 0);
643 afs_dir_DirHash(char *string)
645 /* Hash a string to a number between 0 and NHASHENT. */
650 while ((tc = (*string++))) {
654 tval = hval & (NHASHENT - 1);
657 else if (hval >= 1u<<31)
658 tval = NHASHENT - tval;
663 /* Find a directory entry, given its name. This entry returns a pointer
664 * to a locked buffer, and a pointer to a locked buffer (in previtem)
665 * referencing the found item (to aid the delete code). If no entry is
666 * found, however, no items are left locked, and a null pointer is
667 * returned instead. */
670 FindItem(dir_file_t dir, char *ename, struct DirBuffer *prevbuf,
671 struct DirBuffer *itembuf )
674 struct DirBuffer curr, prev;
675 struct DirHeader *dhp;
679 memset(prevbuf, 0, sizeof(struct DirBuffer));
680 memset(itembuf, 0, sizeof(struct DirBuffer));
682 code = DRead(dir, 0, &prev);
685 dhp = (struct DirHeader *)prev.data;
687 i = afs_dir_DirHash(ename);
688 if (dhp->hashTable[i] == 0) {
694 code = afs_dir_GetVerifiedBlob(dir,
695 (u_short) ntohs(dhp->hashTable[i]),
701 prev.data = &(dhp->hashTable[i]);
703 /* Detect circular hash chains. Absolute max size of a directory */
704 while (elements < BIGMAXPAGES * EPP) {
707 /* Look at each entry on the hash chain */
708 tp = (struct DirEntry *)curr.data;
709 if (!strcmp(ename, tp->name)) {
719 prev.data = &(tp->next);
722 /* The end of the line */
727 code = afs_dir_GetVerifiedBlob(dir, (u_short) ntohs(tp->next),
733 /* If we've reached here, we've hit our loop limit. Something is weird with
734 * the directory; maybe a circular hash chain? */
743 FindFid (void *dir, afs_uint32 vnode, afs_uint32 unique,
744 struct DirBuffer *itembuf)
746 /* Find a directory entry, given the vnode and uniquifier of a object.
747 * This entry returns a pointer to a locked buffer. If no entry is found,
748 * however, no items are left locked, and a null pointer is returned
753 struct DirBuffer curr, header;
754 struct DirHeader *dhp;
758 memset(itembuf, 0, sizeof(struct DirBuffer));
760 code = DRead(dir, 0, &header);
763 dhp = (struct DirHeader *)header.data;
765 for (i=0; i<NHASHENT; i++) {
766 if (dhp->hashTable[i] != 0) {
767 code = afs_dir_GetVerifiedBlob(dir,
768 (u_short)ntohs(dhp->hashTable[i]),
771 DRelease(&header, 0);
775 while(curr.data != NULL && elements < BIGMAXPAGES * EPP) {
777 tp = (struct DirEntry *)curr.data;
779 if (vnode == ntohl(tp->fid.vnode)
780 && unique == ntohl(tp->fid.vunique)) {
781 DRelease(&header, 0);
792 code = afs_dir_GetVerifiedBlob(dir, (u_short)ntohs(next),
795 DRelease(&header, 0);
801 DRelease(&header, 0);
806 afs_dir_InverseLookup(void *dir, afs_uint32 vnode, afs_uint32 unique,
807 char *name, afs_uint32 length)
809 /* Look for the name pointing to given vnode and unique in a directory */
810 struct DirBuffer entrybuf;
811 struct DirEntry *entry;
815 code = FindFid(dir, vnode, unique, &entrybuf);
819 entry = (struct DirEntry *)entrybuf.data;
821 rlen = strlcpy(name, entry->name, length);
822 if (rlen >= length) {
825 DRelease(&entrybuf, 0);
830 * Change an entry fid.
833 * \param entry The entry name.
834 * \param old_fid The old find in MKFid format (host order).
835 * It can be omitted if you don't need a safety check...
836 * \param new_fid The new find in MKFid format (host order).
839 afs_dir_ChangeFid(dir_file_t dir, char *entry, afs_uint32 *old_fid,
842 struct DirBuffer prevbuf, entrybuf;
843 struct DirEntry *firstitem;
844 struct MKFid *fid_old = (struct MKFid *) old_fid;
845 struct MKFid *fid_new = (struct MKFid *) new_fid;
849 code = FindItem(dir, entry, &prevbuf, &entrybuf);
853 firstitem = (struct DirEntry *)entrybuf.data;
854 DRelease(&prevbuf, 1);
858 ((htonl(fid_old->vnode) == firstitem->fid.vnode) &&
859 (htonl(fid_old->vunique) == firstitem->fid.vunique))) {
861 firstitem->fid.vnode = htonl(fid_new->vnode);
862 firstitem->fid.vunique = htonl(fid_new->vunique);
865 DRelease(&entrybuf, 1);