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 <afs/param.h>
26 afs_uint32 dir_lookup_hits = 0;
27 afs_uint32 dir_lookup_misses = 0;
28 afs_uint32 dir_create_entry = 0;
29 afs_uint32 dir_remove_entry = 0;
31 afs_uint64 dir_lookup_time = 0;
32 afs_uint64 dir_create_time = 0;
33 afs_uint64 dir_remove_time = 0;
35 afs_uint64 dir_enums = 0;
37 afs_int32 cm_BPlusTrees = 1;
39 int cm_MemDumpDirStats(FILE *outputFile, char *cookie, int lock)
44 sprintf(output, "%s - Dir Lookup Hits: %-8d\r\n", cookie, dir_lookup_hits);
45 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
46 sprintf(output, "%s - Misses: %-8d\r\n", cookie, dir_lookup_misses);
47 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
48 sprintf(output, "%s - Enums: %-8d\r\n", cookie, dir_enums);
49 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
50 sprintf(output, "%s - Create: %-8d\r\n", cookie, dir_create_entry);
51 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
52 sprintf(output, "%s - Remove: %-8d\r\n", cookie, dir_remove_entry);
53 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
55 sprintf(output, "%s - Dir Times Lookup: %-16I64d\r\n", cookie, dir_lookup_time);
56 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
57 sprintf(output, "%s - Create: %-16I64d\r\n", cookie, dir_create_time);
58 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
59 sprintf(output, "%s - Remove: %-16I64d\r\n", cookie, dir_remove_time);
60 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
65 void cm_DirDumpStats(void)
67 afsi_log("Dir Lookup Hits: %-8d", dir_lookup_hits);
68 afsi_log(" Misses: %-8d", dir_lookup_misses);
69 afsi_log(" Enums: %-8d", dir_enums);
70 afsi_log(" Create: %-8d", dir_create_entry);
71 afsi_log(" Remove: %-8d", dir_remove_entry);
73 afsi_log("Dir Times Lookup: %-16I64d", dir_lookup_time);
74 afsi_log(" Create: %-16I64d", dir_create_time);
75 afsi_log(" Remove: %-16I64d", dir_remove_time);
79 /* Local static prototypes */
81 cm_DirGetBlob(cm_dirOp_t * op,
82 unsigned int blobno, cm_buf_t ** bufferpp, cm_dirEntry_t ** blobpp);
85 cm_DirFindItem(cm_dirOp_t * op,
87 cm_buf_t ** itembufpp, cm_dirEntry_t ** itempp,
88 cm_buf_t ** prevbufpp, unsigned short **previtempp);
91 cm_DirOpAddBuffer(cm_dirOp_t * op, cm_buf_t * buffer);
93 /* flags for cm_DirOpDelBuffer */
94 #define DIROP_MODIFIED 1
95 #define DIROP_SCPLOCKED 2
98 cm_DirOpDelBuffer(cm_dirOp_t * op, cm_buf_t * buffer, int flags);
101 cm_DirCheckStatus(cm_dirOp_t * op, int locked);
104 cm_DirReleasePage(cm_dirOp_t * op, cm_buf_t ** bufferpp, int modified);
107 cm_DirGetPage(cm_dirOp_t * op,
108 long index, cm_buf_t ** bufferpp, void ** datapp);
111 cm_DirFindBlobs(cm_dirOp_t * op, int nblobs);
114 cm_DirAddPage(cm_dirOp_t * op, int pageno);
117 cm_DirFreeBlobs(cm_dirOp_t * op, int firstblob, int nblobs);
120 cm_DirPrefetchBuffers(cm_dirOp_t * op);
122 /* compute how many 32 byte entries an AFS 3 dir requires for storing
123 * the specified name.
126 cm_NameEntries(char *namep, size_t *lenp)
130 i = (long)strlen(namep);
132 return 1 + ((i+16) >> 5);
135 /* Create an entry in a file. Dir is a file representation, while
136 entry is a string name.
139 op->scp->rw is unlocked
142 op->scp->rw is unlocked
144 None of the directory buffers for op->scp should be locked by the
148 cm_DirCreateEntry(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
152 LARGE_INTEGER start, end;
154 cm_dirEntry_t *ep = NULL;
155 cm_buf_t *entrybuf = NULL;
157 unsigned short *pp = NULL;
158 cm_buf_t *prevptrbuf = NULL;
160 cm_dirHeader_t *dhp = NULL;
161 cm_buf_t *dhpbuf = NULL;
165 /* check name quality */
169 QueryPerformanceCounter(&start);
173 osi_Log4(afsd_logp, "cm_DirCreateEntry for op 0x%p, name [%s] and fid[%d,%d]",
174 op, osi_LogSaveString(afsd_logp, entry), cfid->vnode, cfid->unique);
176 /* First check if file already exists. */
177 code = cm_DirFindItem(op,
182 cm_DirReleasePage(op, &entrybuf, FALSE);
183 cm_DirReleasePage(op, &prevptrbuf, FALSE);
188 blobs = cm_NameEntries(entry, NULL); /* number of entries required */
189 firstelt = cm_DirFindBlobs(op, blobs);
191 osi_Log0(afsd_logp, "cm_DirCreateEntry returning EFBIG");
192 code = EFBIG; /* directory is full */
196 /* First, we fill in the directory entry. */
197 code = cm_DirGetBlob(op, firstelt, &entrybuf, &ep);
203 ep->flag = CM_DIR_FFIRST;
204 ep->fid.vnode = htonl(cfid->vnode);
205 ep->fid.unique = htonl(cfid->unique);
206 strcpy(ep->name, entry);
208 /* Now we just have to thread it on the hash table list. */
209 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
211 cm_DirReleasePage(op, &entrybuf, TRUE);
216 i = cm_DirHash(entry);
218 ep->next = dhp->hashTable[i];
219 dhp->hashTable[i] = htons(firstelt);
221 cm_DirReleasePage(op, &dhpbuf, TRUE);
222 cm_DirReleasePage(op, &entrybuf, TRUE);
224 osi_Log0(afsd_logp, "cm_DirCreateEntry returning success");
228 QueryPerformanceCounter(&end);
230 dir_create_time += (end.QuadPart - start.QuadPart);
234 /* Return the length of a directory in pages
237 op->scp->rw is locked
240 op->scp->rw is locked
242 The first directory page for op->scp should not be locked by the
246 cm_DirLength(cm_dirOp_t * op)
249 cm_dirHeader_t *dhp = NULL;
250 cm_buf_t *dhpbuf = NULL;
254 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
258 if (dhp->header.pgcount != 0)
259 ctr = ntohs(dhp->header.pgcount);
261 /* old style, count the pages */
263 for (i = 0; i < CM_DIR_MAXPAGES; i++)
264 if (dhp->alloMap[i] != CM_DIR_EPP)
267 cm_DirReleasePage(op, &dhpbuf, FALSE);
268 return ctr * CM_DIR_PAGESIZE;
271 /* Delete a directory entry.
274 op->scp->rw is unlocked
277 op->scp->rw is unlocked
279 None of the directory buffers for op->scp should be locked by the
283 cm_DirDeleteEntry(cm_dirOp_t * op, char *entry)
285 /* Delete an entry from a directory, including update of all free
286 entry descriptors. */
289 cm_dirEntry_t *firstitem = NULL;
290 cm_buf_t *itembuf = NULL;
291 unsigned short *previtem = NULL;
292 cm_buf_t *pibuf = NULL;
296 LARGE_INTEGER start, end;
298 QueryPerformanceCounter(&start);
300 osi_Log2(afsd_logp, "cm_DirDeleteEntry for op 0x%p, entry [%s]",
301 op, osi_LogSaveString(afsd_logp, entry));
303 code = cm_DirFindItem(op, entry,
304 &itembuf, &firstitem,
307 osi_Log0(afsd_logp, "cm_DirDeleteEntry returning ENOENT");
314 *previtem = firstitem->next;
315 cm_DirReleasePage(op, &pibuf, TRUE);
317 thyper = itembuf->offset;
318 thyper = LargeIntegerAdd(thyper,
319 ConvertLongToLargeInteger(((char *) firstitem) - itembuf->datap));
320 thyper = ExtendedLargeIntegerDivide(thyper, 32, &junk);
322 index = thyper.LowPart;
323 osi_assert(thyper.HighPart == 0);
325 nitems = cm_NameEntries(firstitem->name, NULL);
326 cm_DirReleasePage(op, &itembuf, FALSE);
328 cm_DirFreeBlobs(op, index, nitems);
330 osi_Log0(afsd_logp, "cm_DirDeleteEntry returning success");
334 QueryPerformanceCounter(&end);
336 dir_remove_time += (end.QuadPart - start.QuadPart);
341 /* Find a bunch of contiguous entries; at least nblobs in a row.
343 Called with op->scp->rw */
345 cm_DirFindBlobs(cm_dirOp_t * op, int nblobs)
350 cm_dirHeader_t *dhp = NULL;
351 cm_buf_t *dhpbuf = NULL;
352 int dhpModified = FALSE;
354 cm_pageHeader_t *pp = NULL;
355 cm_buf_t *pagebuf = NULL;
356 int pageModified = FALSE;
362 osi_Log2(afsd_logp, "cm_DirFindBlobs for op 0x%p, nblobs = %d",
365 code = cm_DirGetPage(op, 0, &dhpbuf, (void **) &dhp);
369 for (i = 0; i < CM_DIR_BIGMAXPAGES; i++) {
370 if (i >= CM_DIR_MAXPAGES || dhp->alloMap[i] >= nblobs) {
371 /* if page could contain enough entries */
372 /* If there are CM_DIR_EPP free entries, then the page is
373 not even allocated. */
374 if (i >= CM_DIR_MAXPAGES) {
376 /* this pages exists past the end of the old-style dir */
377 pgcount = ntohs(dhp->header.pgcount);
379 pgcount = CM_DIR_MAXPAGES;
380 dhp->header.pgcount = htons(pgcount);
384 if (i > pgcount - 1) {
385 /* this page is bigger than last allocated page */
386 cm_DirAddPage(op, i);
387 dhp->header.pgcount = htons(i + 1);
390 } else if (dhp->alloMap[i] == CM_DIR_EPP) {
391 /* Add the page to the directory. */
392 cm_DirAddPage(op, i);
393 dhp->alloMap[i] = CM_DIR_EPP - 1;
394 dhp->header.pgcount = htons(i + 1);
398 /* the create flag is not set for the GetPage call below
399 since the page should have been added if necessary
401 code = cm_DirGetPage(op, i, &pagebuf, &pp);
403 cm_DirReleasePage(op, &dhpbuf, dhpModified);
407 for (j = 0; j <= CM_DIR_EPP - nblobs; j++) {
409 for (k = 0; k < nblobs; k++)
410 if ((pp->freeBitmap[(j + k) >> 3] >> ((j + k) & 7)) & 1) {
420 /* Here we have the first index in j. We update the allocation maps
421 * and free up any resources we've got allocated. */
422 if (i < CM_DIR_MAXPAGES) {
423 dhp->alloMap[i] -= nblobs;
427 cm_DirReleasePage(op, &dhpbuf, dhpModified);
429 for (k = 0; k < nblobs; k++)
430 pp->freeBitmap[(j + k) >> 3] |= 1 << ((j + k) & 7);
432 cm_DirReleasePage(op, &pagebuf, TRUE);
434 osi_Log0(afsd_logp, "cm_DirFindBlobs returning success");
436 return j + i * CM_DIR_EPP;
438 cm_DirReleasePage(op, &pagebuf, pageModified);
442 /* If we make it here, the directory is full. */
443 osi_Log0(afsd_logp, "cm_DirFindBlobs directory is full");
444 cm_DirReleasePage(op, &dhpbuf, dhpModified);
448 /* Add a page to a directory.
450 Called with op->scp->rw
453 cm_DirAddPage(cm_dirOp_t * op, int pageno)
456 cm_pageHeader_t *pp = NULL;
457 cm_buf_t *pagebuf = NULL;
460 osi_Log2(afsd_logp, "cm_DirAddPage for op 0x%p, pageno=%d", op, pageno);
462 code = cm_DirGetPage(op, pageno, &pagebuf, (void **) &pp);
466 pp->tag = htons(1234);
469 pp->freeCount = CM_DIR_EPP - 1; /* The first dude is already allocated */
470 pp->freeBitmap[0] = 0x01;
471 for (i = 1; i < CM_DIR_EPP / 8; i++) /* It's a constant */
472 pp->freeBitmap[i] = 0;
474 cm_DirReleasePage(op, &pagebuf, TRUE);
476 osi_Log0(afsd_logp, "cm_DirAddPage returning success");
481 /* Free a whole bunch of directory entries.
483 Called with op->scp->rw
486 cm_DirFreeBlobs(cm_dirOp_t * op, int firstblob, int nblobs)
491 cm_dirHeader_t *dhp = NULL;
492 cm_buf_t *dhpbuf = NULL;
493 int dhpmodified = FALSE;
495 cm_pageHeader_t *pp = NULL;
496 cm_buf_t *pagebuf = NULL;
499 osi_Log3(afsd_logp, "cm_DirFreeBlobs for op 0x%p, firstblob=%d, nblobs=%d",
500 op, firstblob, nblobs);
502 page = firstblob / CM_DIR_EPP;
503 firstblob -= CM_DIR_EPP * page; /* convert to page-relative entry */
505 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
509 if (page < CM_DIR_MAXPAGES) {
510 dhp->alloMap[page] += nblobs;
514 cm_DirReleasePage(op, &dhpbuf, dhpmodified);
516 code = cm_DirGetPage(op, page, &pagebuf, &pp);
518 for (i = 0; i < nblobs; i++)
519 pp->freeBitmap[(firstblob + i) >> 3] &=
520 ~(1 << ((firstblob + i) & 7));
521 cm_DirReleasePage(op, &pagebuf, TRUE);
524 osi_Log1(afsd_logp, "cm_DirFreeBlobs returning code 0x%x", code);
530 * Format an empty directory properly. Note that the first 13 entries in a
531 * directory header page are allocated, 1 to the page header, 4 to the
532 * allocation map and 8 to the hash table.
534 * Called with op->scp->rw unlocked
537 cm_DirMakeDir(cm_dirOp_t * op, cm_fid_t * me, cm_fid_t * parent)
540 cm_dirHeader_t *dhp = NULL;
541 cm_buf_t *dhpbuf = NULL;
545 osi_Log3(afsd_logp, "cm_DirMakeDir for op 0x%p, directory fid[%d, %d]",
546 op, me->vnode, me->unique);
547 osi_Log2(afsd_logp, " parent[%d, %d]",
548 parent->vnode, parent->unique);
550 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
556 dhp->header.pgcount = htons(1);
557 dhp->header.tag = htons(1234);
558 dhp->header.freeCount = (CM_DIR_EPP - CM_DIR_DHE - 1);
559 dhp->header.freeBitmap[0] = 0xff;
560 dhp->header.freeBitmap[1] = 0x1f;
561 for (i = 2; i < CM_DIR_EPP / 8; i++)
562 dhp->header.freeBitmap[i] = 0;
563 dhp->alloMap[0] = (CM_DIR_EPP - CM_DIR_DHE - 1);
564 for (i = 1; i < CM_DIR_MAXPAGES; i++)
565 dhp->alloMap[i] = CM_DIR_EPP;
566 for (i = 0; i < CM_DIR_NHASHENT; i++)
567 dhp->hashTable[i] = 0;
569 cm_DirReleasePage(op, &dhpbuf, TRUE);
571 cm_DirCreateEntry(op, ".", me);
572 cm_DirCreateEntry(op, "..", parent); /* Virtue is its own .. */
574 osi_Log0(afsd_logp, "cm_DirMakeDir returning success");
581 /* Look up a file name in directory.
584 op->scp->rw is unlocked
587 op->scp->rw is unlocked
589 None of the directory buffers for op->scp should be locked by the
593 cm_DirLookup(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
595 cm_dirEntry_t *firstitem = NULL;
596 cm_buf_t *itembuf = NULL;
597 unsigned short *previtem = NULL;
598 cm_buf_t *pibuf = NULL;
603 QueryPerformanceCounter(&start);
605 osi_Log2(afsd_logp, "cm_DirLookup for op 0x%p, entry[%s]",
606 op, osi_LogSaveString(afsd_logp, entry));
608 code = cm_DirFindItem(op, entry,
609 &itembuf, &firstitem,
612 if (code == CM_ERROR_NOTINCACHE) {
613 code = cm_DirPrefetchBuffers(op);
615 code = cm_DirFindItem(op, entry, &itembuf, &firstitem,
625 cm_DirReleasePage(op, &pibuf, FALSE);
627 cfid->cell = op->scp->fid.cell;
628 cfid->volume = op->scp->fid.volume;
629 cfid->vnode = ntohl(firstitem->fid.vnode);
630 cfid->unique = ntohl(firstitem->fid.unique);
632 cm_DirReleasePage(op, &itembuf, FALSE);
634 osi_Log2(afsd_logp, "cm_DirLookup returning fid[%d,%d]",
635 cfid->vnode, cfid->unique);
641 QueryPerformanceCounter(&end);
643 dir_lookup_time += (end.QuadPart - start.QuadPart);
648 /* Look up a file name in directory.
651 op->scp->rw is locked
654 op->scp->rw is locked
656 None of the directory buffers for op->scp should be locked by the
660 cm_DirLookupOffset(cm_dirOp_t * op, char *entry, cm_fid_t *cfid, osi_hyper_t *offsetp)
662 cm_dirEntry_t *firstitem = NULL;
663 cm_buf_t *itembuf = NULL;
664 unsigned short *previtem = NULL;
665 cm_buf_t *pibuf = NULL;
669 osi_Log2(afsd_logp, "cm_DirLookupOffset for op 0x%p, entry[%s]",
670 op, osi_LogSaveString(afsd_logp, entry));
672 code = cm_DirFindItem(op, entry,
673 &itembuf, &firstitem,
678 cm_DirReleasePage(op, &pibuf, FALSE);
680 cfid->cell = op->scp->fid.cell;
681 cfid->volume = op->scp->fid.volume;
682 cfid->vnode = ntohl(firstitem->fid.vnode);
683 cfid->unique = ntohl(firstitem->fid.unique);
687 thyper = itembuf->offset;
688 thyper = LargeIntegerAdd(thyper,
689 ConvertLongToLargeInteger(((char *) firstitem) - itembuf->datap));
694 cm_DirReleasePage(op, &itembuf, FALSE);
696 osi_Log2(afsd_logp, "cm_DirLookupOffset returning fid[%d,%d]",
697 cfid->vnode, cfid->unique);
699 osi_Log2(afsd_logp, " offset [%x:%x]",
700 offsetp->HighPart, offsetp->LowPart);
706 /* Apply a function to every directory entry in a directory.
709 op->scp->rw is locked
712 op->scp->rw is locked
714 None of the directory buffers for op->scp should be locked by the
717 The hook function cannot modify or lock any directory buffers.
720 cm_DirApply(cm_dirOp_t * op, int (*hookproc) (void *, char *, long, long), void *hook)
722 /* Enumerate the contents of a directory. */
726 cm_dirHeader_t *dhp = NULL;
727 cm_buf_t *dhpbuf = NULL;
729 cm_dirEntry_t *ep = NULL;
730 cm_buf_t *epbuf = NULL;
734 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
738 for (i = 0; i < CM_DIR_NHASHENT; i++) {
739 /* For each hash chain, enumerate everyone on the list. */
740 num = ntohs(dhp->hashTable[i]);
742 /* Walk down the hash table list. */
743 code = cm_DirGetBlob(op, num, &epbuf, &ep);
745 cm_DirReleasePage(op, &dhpbuf, FALSE);
749 num = ntohs(ep->next);
750 (*hookproc) (hook, ep->name, ntohl(ep->fid.vnode),
751 ntohl(ep->fid.unique));
753 cm_DirReleasePage(op, &epbuf, FALSE);
756 cm_DirReleasePage(op, &dhpbuf, FALSE);
761 /* Check if a directory is empty
764 op->scp->rw is locked
767 op->scp->rw is locked
769 None of the directory buffers for op->scp should be locked by the
773 cm_DirIsEmpty(cm_dirOp_t * op)
775 /* Enumerate the contents of a directory. */
779 cm_dirHeader_t *dhp = NULL;
780 cm_buf_t *dhpbuf = NULL;
782 cm_dirEntry_t *ep = NULL;
783 cm_buf_t *epbuf = NULL;
787 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
791 for (i = 0; i < CM_DIR_NHASHENT; i++) {
792 /* For each hash chain, enumerate everyone on the list. */
793 num = ntohs(dhp->hashTable[i]);
796 /* Walk down the hash table list. */
797 code = cm_DirGetBlob(op, num, &epbuf, &ep);
801 if (strcmp(ep->name, "..") && strcmp(ep->name, ".")) {
802 cm_DirReleasePage(op, &epbuf, FALSE);
803 cm_DirReleasePage(op, &dhpbuf, FALSE);
806 num = ntohs(ep->next);
807 cm_DirReleasePage(op, &epbuf, FALSE);
810 cm_DirReleasePage(op, &dhpbuf, FALSE);
814 /* Return a pointer to an entry, given its number.
818 if *bufferpp != NULL, then *bufferpp->mx is locked
821 scp->rw may be unlocked
822 *bufferpp may be released
826 if *bufferpp != NULL, then *bufferpp->mx is locked
828 *bufferpp should be released via cm_DirReleasePage() or any other
829 *call that releases a directory buffer.
832 cm_DirGetBlob(cm_dirOp_t * op,
833 unsigned int blobno, cm_buf_t ** bufferpp, cm_dirEntry_t ** blobpp)
838 osi_Log2(afsd_logp, "cm_DirGetBlob for op 0x%p, blobno=%d",
841 code = cm_DirGetPage(op, blobno >> CM_DIR_LEPP,
842 bufferpp, (void **) &ep);
846 *blobpp = (cm_dirEntry_t *) (ep + 32 * (blobno & (CM_DIR_EPP - 1)));
852 cm_DirHash(char *string)
854 /* Hash a string to a number between 0 and NHASHENT. */
855 register unsigned char tc;
859 while ((tc = (*string++))) {
863 tval = hval & (CM_DIR_NHASHENT - 1);
867 tval = CM_DIR_NHASHENT - tval;
871 /* Find a directory entry, given its name. This entry returns a
872 * pointer to a locked buffer, and a pointer to a locked buffer (in
873 * previtem) referencing the found item (to aid the delete code). If
874 * no entry is found, however, no items are left locked, and a null
875 * pointer is returned instead.
884 cm_DirFindItem(cm_dirOp_t * op,
886 cm_buf_t ** itembufpp, cm_dirEntry_t ** itempp,
887 cm_buf_t ** prevbufpp, unsigned short **previtempp)
890 cm_dirHeader_t *dhp = NULL;
891 unsigned short *lp = NULL;
892 cm_dirEntry_t *tp = NULL;
893 cm_buf_t *hashbufp = NULL;
894 cm_buf_t *itembufp = NULL;
897 osi_Log2(afsd_logp, "cm_DirFindItem for op 0x%p, entry[%s]",
898 op, osi_LogSaveString(afsd_logp, ename));
900 i = cm_DirHash(ename);
902 if (op->scp->fileType != CM_SCACHETYPE_DIRECTORY) {
903 osi_Log0(afsd_logp, "cm_DirFindItem: The scp is not a directory");
904 return CM_ERROR_INVAL;
907 code = cm_DirGetPage(op, 0, &hashbufp, (void **) &dhp);
912 if (dhp->hashTable[i] == 0) {
914 osi_Log1(afsd_logp, "cm_DirFindItem: Hash bucket %d is empty", i);
915 cm_DirReleasePage(op, &hashbufp, FALSE);
919 code = cm_DirGetBlob(op,
920 (u_short) ntohs(dhp->hashTable[i]),
923 cm_DirReleasePage(op, &hashbufp, FALSE);
927 lp = &(dhp->hashTable[i]);
931 lp : pointer to blob number of entry we are looking at
932 hashbufp : buffer containing lp
933 tp : pointer to entry we are looking at
934 itembufp : buffer containing tp
937 /* Look at each hash conflict entry. */
938 if (!strcmp(ename, tp->name)) {
939 osi_Log0(afsd_logp, "cm_DirFindItem: returning success");
940 /* Found our entry. */
942 *prevbufpp = hashbufp;
944 *itembufpp = itembufp;
949 cm_DirReleasePage(op, &hashbufp, FALSE);
956 /* The end of the line */
957 osi_Log0(afsd_logp, "cm_DirFindItem: returning ENOENT");
958 cm_DirReleasePage(op, &hashbufp, FALSE);
962 code = cm_DirGetBlob(op,
963 (u_short) ntohs(*lp),
967 cm_DirReleasePage(op, &hashbufp, FALSE);
973 /* Begin a sequence of directory operations.
974 * Called with scp->rw unlocked.
977 cm_BeginDirOp(cm_scache_t * scp, cm_user_t * userp, cm_req_t * reqp,
978 afs_uint32 lockType, cm_dirOp_t * op)
981 int i, mxheld = 0, haveWrite = 0;
983 osi_Log3(afsd_logp, "Beginning dirOp[0x%p] for scp[0x%p], userp[0x%p]",
986 memset(op, 0, sizeof(*op));
992 op->req = *reqp; /* copy the values from the input */
994 op->dirtyBufCount = 0;
997 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
998 op->buffers[i].flags = 0;
1001 if (lockType == CM_DIRLOCK_WRITE) {
1002 lock_ObtainWrite(&scp->dirlock);
1005 lock_ObtainRead(&scp->dirlock);
1008 lock_ObtainWrite(&scp->rw);
1010 code = cm_DirCheckStatus(op, 1);
1012 op->length = scp->length;
1013 op->newLength = op->length;
1014 op->dataVersion = scp->dataVersion;
1015 op->newDataVersion = op->dataVersion;
1018 if (!cm_BPlusTrees ||
1020 scp->dirDataVersion == scp->dataVersion))
1022 /* we know that haveWrite matches lockType at this point */
1024 case CM_DIRLOCK_NONE:
1026 lock_ReleaseWrite(&scp->dirlock);
1028 lock_ReleaseRead(&scp->dirlock);
1030 case CM_DIRLOCK_READ:
1031 osi_assert(!haveWrite);
1033 case CM_DIRLOCK_WRITE:
1035 osi_assert(haveWrite);
1038 if (!(scp->dirBplus &&
1039 scp->dirDataVersion == scp->dataVersion))
1044 lock_ReleaseWrite(&scp->rw);
1047 lock_ConvertRToW(&scp->dirlock);
1051 lock_ObtainWrite(&scp->rw);
1054 if (scp->dirBplus &&
1055 scp->dirDataVersion != scp->dataVersion)
1059 freeBtree(scp->dirBplus);
1060 scp->dirBplus = NULL;
1061 scp->dirDataVersion = -1;
1064 if (!scp->dirBplus) {
1066 lock_ReleaseWrite(&scp->rw);
1069 cm_BPlusDirBuildTree(scp, userp, reqp);
1071 lock_ObtainWrite(&scp->rw);
1074 if (op->dataVersion != scp->dataVersion) {
1075 /* We lost the race, therefore we must update the
1076 * dirop state and retry to build the tree.
1078 op->length = scp->length;
1079 op->newLength = op->length;
1080 op->dataVersion = scp->dataVersion;
1081 op->newDataVersion = op->dataVersion;
1086 scp->dirDataVersion = scp->dataVersion;
1091 case CM_DIRLOCK_NONE:
1092 lock_ReleaseWrite(&scp->dirlock);
1094 case CM_DIRLOCK_READ:
1095 lock_ConvertWToR(&scp->dirlock);
1097 case CM_DIRLOCK_WRITE:
1099 /* got it already */;
1104 /* we know that haveWrite matches lockType at this point */
1106 case CM_DIRLOCK_NONE:
1108 lock_ReleaseWrite(&scp->dirlock);
1110 lock_ReleaseRead(&scp->dirlock);
1112 case CM_DIRLOCK_READ:
1113 osi_assert(!haveWrite);
1115 case CM_DIRLOCK_WRITE:
1117 osi_assert(haveWrite);
1120 op->lockType = lockType;
1122 lock_ReleaseWrite(&scp->rw);
1125 lock_ReleaseWrite(&scp->dirlock);
1127 lock_ReleaseRead(&scp->dirlock);
1129 lock_ReleaseWrite(&scp->rw);
1136 /* Check if it is safe for us to perform local directory updates.
1137 Called with op->scp->rw unlocked. */
1139 cm_CheckDirOpForSingleChange(cm_dirOp_t * op)
1144 if (op->scp == NULL)
1147 lock_ObtainWrite(&op->scp->rw);
1148 code = cm_DirCheckStatus(op, 1);
1151 op->dataVersion == op->scp->dataVersion - 1) {
1152 /* only one set of changes happened between cm_BeginDirOp()
1153 and this function. It is safe for us to perform local
1155 op->newDataVersion = op->scp->dataVersion;
1156 op->newLength = op->scp->serverLength;
1160 lock_ReleaseWrite(&op->scp->rw);
1163 osi_Log0(afsd_logp, "cm_CheckDirOpForSingleChange succeeded");
1166 "cm_CheckDirOpForSingleChange failed. code=0x%x, old dv=%d, new dv=%d",
1167 code, op->dataVersion, op->scp->dataVersion);
1171 /* End a sequence of directory operations.
1172 * Called with op->scp->rw unlocked.*/
1174 cm_EndDirOp(cm_dirOp_t * op)
1178 if (op->scp == NULL)
1181 osi_Log2(afsd_logp, "Ending dirOp 0x%p with %d dirty buffer releases",
1182 op, op->dirtyBufCount);
1184 if (op->dirtyBufCount > 0) {
1186 /* update the data version on the B+ tree */
1187 if (op->scp->dirBplus &&
1188 op->scp->dirDataVersion == op->dataVersion) {
1190 switch (op->lockType) {
1191 case CM_DIRLOCK_READ:
1192 lock_ReleaseRead(&op->scp->dirlock);
1193 /* fall through ... */
1194 case CM_DIRLOCK_NONE:
1195 lock_ObtainWrite(&op->scp->dirlock);
1196 op->lockType = CM_DIRLOCK_WRITE;
1198 case CM_DIRLOCK_WRITE:
1200 /* already got it */;
1202 op->scp->dirDataVersion = op->newDataVersion;
1206 /* we made changes. We should go through the list of buffers
1207 * and update the dataVersion for each. */
1208 lock_ObtainWrite(&op->scp->rw);
1209 code = buf_ForceDataVersion(op->scp, op->dataVersion, op->newDataVersion);
1210 op->scp->flags |= CM_SCACHEFLAG_LOCAL;
1211 lock_ReleaseWrite(&op->scp->rw);
1214 switch (op->lockType) {
1215 case CM_DIRLOCK_NONE:
1217 case CM_DIRLOCK_READ:
1218 lock_ReleaseRead(&op->scp->dirlock);
1220 case CM_DIRLOCK_WRITE:
1222 lock_ReleaseWrite(&op->scp->dirlock);
1226 cm_ReleaseSCache(op->scp);
1230 cm_ReleaseUser(op->userp);
1233 osi_assertx(op->nBuffers == 0, "Buffer leak after dirOp termination");
1238 /* NOTE: Called without scp->rw and without bufferp->mx */
1240 cm_DirOpAddBuffer(cm_dirOp_t * op, cm_buf_t * bufferp)
1245 osi_Log2(afsd_logp, "cm_DirOpAddBuffer for op 0x%p, buffer %p", op, bufferp);
1247 if (bufferp == NULL)
1250 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1251 if ((op->buffers[i].flags & CM_DIROPBUFF_INUSE) &&
1252 op->buffers[i].bufferp == bufferp) {
1257 if (i < CM_DIROP_MAXBUFFERS) {
1258 /* we already have this buffer on our list */
1260 op->buffers[i].refcount++;
1262 "cm_DirOpAddBuffer: the buffer is already listed for the dirOp");
1265 /* we have to add a new buffer */
1266 osi_assertx(op->nBuffers < CM_DIROP_MAXBUFFERS - 1,
1267 "DirOp has exceeded CM_DIROP_MAXBUFFERS buffers");
1269 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1270 if (!(op->buffers[i].flags & CM_DIROPBUFF_INUSE))
1274 osi_assert(i < CM_DIROP_MAXBUFFERS);
1276 lock_ObtainMutex(&bufferp->mx);
1277 lock_ObtainWrite(&op->scp->rw);
1279 /* Make sure we are synchronized. */
1280 osi_assert(op->lockType != CM_DIRLOCK_NONE);
1282 code = cm_SyncOp(op->scp, bufferp, op->userp, &op->req, PRSFS_LOOKUP,
1283 CM_SCACHESYNC_NEEDCALLBACK |
1284 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ) |
1285 CM_SCACHESYNC_BUFLOCKED);
1287 if (code == 0 && bufferp->dataVersion != op->dataVersion) {
1289 "cm_DirOpAddBuffer: buffer data version mismatch. buf dv = %d. needs %d",
1290 bufferp->dataVersion, op->dataVersion);
1292 cm_SyncOpDone(op->scp, bufferp,
1293 CM_SCACHESYNC_NEEDCALLBACK |
1294 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ) |
1295 CM_SCACHESYNC_BUFLOCKED);
1296 code = CM_ERROR_NOTINCACHE;
1299 lock_ReleaseWrite(&op->scp->rw);
1300 lock_ReleaseMutex(&bufferp->mx);
1303 osi_Log1(afsd_logp, "cm_DirOpAddBuffer: failed to sync buffer. code=0x%x",
1309 op->buffers[i].bufferp = bufferp;
1310 op->buffers[i].refcount = 1; /* start with one ref */
1311 op->buffers[i].flags = CM_DIROPBUFF_INUSE;
1315 osi_Log0(afsd_logp, "cm_DirOpAddBuffer: returning success");
1321 /* Note: Called without op->scp->rw */
1323 cm_DirOpFindBuffer(cm_dirOp_t * op, osi_hyper_t offset, cm_buf_t ** bufferpp)
1327 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1328 if ((op->buffers[i].flags & CM_DIROPBUFF_INUSE) &&
1329 LargeIntegerEqualTo(op->buffers[i].bufferp->offset, offset))
1333 if (i < CM_DIROP_MAXBUFFERS) {
1335 op->buffers[i].refcount++;
1336 buf_Hold(op->buffers[i].bufferp);
1337 *bufferpp = op->buffers[i].bufferp;
1339 osi_Log2(afsd_logp, "cm_DirOpFindBuffer: found buffer for offset [%x:%x]",
1340 offset.HighPart, offset.LowPart);
1344 osi_Log2(afsd_logp, "cm_DirOpFindBuffer: buffer not found for offset [%x:%x]",
1345 offset.HighPart, offset.LowPart);
1350 /* NOTE: called with scp->rw held or not depending on the flags */
1352 cm_DirOpDelBuffer(cm_dirOp_t * op, cm_buf_t * bufferp, int flags)
1356 osi_Log3(afsd_logp, "cm_DirOpDelBuffer for op 0x%p, buffer 0x%p, flags=%d",
1357 op, bufferp, flags);
1359 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1360 if ((op->buffers[i].flags & CM_DIROPBUFF_INUSE) &&
1361 op->buffers[i].bufferp == bufferp)
1365 if (i < CM_DIROP_MAXBUFFERS) {
1367 if (flags & DIROP_MODIFIED)
1368 op->dirtyBufCount++;
1370 osi_assert(op->buffers[i].refcount > 0);
1371 op->buffers[i].refcount --;
1373 if (op->buffers[i].refcount == 0) {
1374 /* this was the last reference we had */
1376 osi_Log0(afsd_logp, "cm_DirOpDelBuffer: releasing buffer");
1378 /* if this buffer was modified, then we update the data
1379 version of the buffer with the data version of the
1381 if (!(flags & DIROP_SCPLOCKED)) {
1382 lock_ObtainWrite(&op->scp->rw);
1385 /* first make sure that the buffer is idle. It should
1386 have been idle all along. */
1387 osi_assertx((bufferp->cmFlags & (CM_BUF_CMFETCHING |
1388 CM_BUF_CMSTORING)) == 0,
1389 "Buffer is not idle while performing dirOp");
1391 cm_SyncOpDone(op->scp, bufferp,
1392 CM_SCACHESYNC_NEEDCALLBACK |
1393 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ));
1396 osi_assert(bufferp->dataVersion == op->dataVersion);
1399 lock_ReleaseWrite(&op->scp->rw);
1401 lock_ObtainMutex(&bufferp->mx);
1403 if (flags & DIROP_SCPLOCKED) {
1404 lock_ObtainWrite(&op->scp->rw);
1407 if (flags & DIROP_MODIFIED) {
1408 /* We don't update the dataversion here. Instead we
1409 wait until the dirOp is completed and then flip the
1410 dataversion on all the buffers in one go.
1411 Otherwise we won't know if the dataversion is
1412 current because it was fetched from the server or
1413 because we touched it during the dirOp. */
1415 if (bufferp->userp != op->userp) {
1416 if (bufferp->userp != NULL)
1417 cm_ReleaseUser(bufferp->userp);
1418 cm_HoldUser(op->userp);
1419 bufferp->userp = op->userp;
1423 lock_ReleaseMutex(&bufferp->mx);
1425 op->buffers[i].bufferp = NULL;
1426 buf_Release(bufferp);
1427 op->buffers[i].flags = 0;
1433 /* we have other references to this buffer. so we have to
1439 osi_Log0(afsd_logp, "cm_DirOpDelBuffer: buffer not found");
1440 osi_assertx(FALSE, "Attempt to delete a non-existent buffer from a dirOp");
1445 /* Check if we have current status and a callback for the given scp.
1446 This should be called before cm_DirGetPage() is called per scp.
1449 scp->rw locked state indicated by parameter
1452 scp->rw same state as upon entry
1455 scp->rw may be released
1458 cm_DirCheckStatus(cm_dirOp_t * op, int scp_locked)
1463 lock_ObtainWrite(&op->scp->rw);
1464 code = cm_SyncOp(op->scp, NULL, op->userp, &op->req, PRSFS_LOOKUP,
1465 CM_SCACHESYNC_NEEDCALLBACK | CM_SCACHESYNC_GETSTATUS);
1467 lock_ReleaseWrite(&op->scp->rw);
1469 osi_Log2(afsd_logp, "cm_DirCheckStatus for op 0x%p returning code 0x%x",
1475 /* Attempt to prefetch all the buffers for this operation.
1477 Called with scp->rw unlocked
1480 cm_DirPrefetchBuffers(cm_dirOp_t * op)
1484 cm_buf_t *bufferp = NULL;
1486 osi_Log1(afsd_logp, "cm_DirPrefetchBuffers for op 0x%p", op);
1488 /* prefetching is only done on read operations where we don't
1489 expect the data version to change. */
1490 if (op->dataVersion != op->newDataVersion) {
1491 osi_Log0(afsd_logp, "Skipping prefetch for write operation.");
1492 return CM_ERROR_INVAL;
1495 lock_ObtainWrite(&op->scp->rw);
1497 /* When we are prefetching a file, we first flush out any of its
1498 contents just to make sure that we don't end up with buffers
1499 that was locally modified. */
1501 if (op->scp->flags & CM_SCACHEFLAG_LOCAL) {
1502 lock_ReleaseWrite(&op->scp->rw);
1503 code = cm_FlushFile(op->scp, op->userp, &op->req);
1506 lock_ObtainWrite(&op->scp->rw);
1509 offset = ConvertLongToLargeInteger(0);
1510 while (LargeIntegerLessThan(offset, op->scp->length)) {
1511 osi_Log2(afsd_logp, "Trying prefetch for offset %08x:%08x",
1512 offset.HighPart, offset.LowPart);
1513 lock_ReleaseWrite(&op->scp->rw);
1515 code = buf_Get(op->scp, &offset, &bufferp);
1517 lock_ObtainWrite(&op->scp->rw);
1524 code = cm_SyncOp(op->scp, bufferp, op->userp, &op->req, PRSFS_LOOKUP,
1525 CM_SCACHESYNC_NEEDCALLBACK |
1526 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ));
1531 cm_SyncOpDone(op->scp, bufferp, CM_SCACHESYNC_NEEDCALLBACK |
1532 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ));
1534 if (cm_HaveBuffer(op->scp, bufferp, 0))
1537 code = cm_GetBuffer(op->scp, bufferp, NULL, op->userp, &op->req);
1546 buf_Release(bufferp);
1550 offset = LargeIntegerAdd(offset, ConvertLongToLargeInteger(cm_data.buf_blockSize));
1554 lock_ReleaseWrite(&op->scp->rw);
1556 osi_Log1(afsd_logp, "cm_DirPrefetchBuffers returning code 0x%x", code);
1561 /* Release a directory buffer that was obtained via a call to
1562 cm_DirGetPage() or any other function that returns a locked, held,
1563 directory page buffer.
1565 Called with scp->rw unlocked
1568 cm_DirReleasePage(cm_dirOp_t * op, cm_buf_t ** bufferpp, int modified)
1575 cm_DirOpDelBuffer(op, *bufferpp,
1576 ((modified ? DIROP_MODIFIED : 0)));
1577 buf_Release(*bufferpp);
1584 Returns the index'th directory page from scp. The userp and reqp
1585 will be used to fetch the buffer from the fileserver if necessary.
1586 If the call is successful, a locked and held cm_buf_t is returned
1587 via buferpp and a pointer to the directory page is returned via
1590 The returned buffer should be released via a call to
1591 cm_DirReleasePage() or by passing it into a subsequent call to
1592 cm_DirGetPage() for the *same* scp.
1594 If a *locked* buffer for the *same* scp is passed in via bufferpp
1595 to the function, it will check if the requested directory page is
1596 located in the specified buffer. If not, the buffer will be
1597 released and a new buffer returned that contains the requested
1600 If the specified page exists beyond the EOF for the scp, a new
1601 buffer will be allocated only if create is set to TRUE.
1603 Note: If a buffer is specified on entry via bufferpp, it is assumed
1604 that the buffer is unmodified. If the buffer is modified, it
1605 should be released via cm_DirReleasePage().
1609 If *bufferpp is non-NULL, then *bufferpp->mx is locked.
1613 If *bufferpp is non-NULL, then *bufferpp->mx is locked.
1616 scp->rw will be obtained and released
1620 cm_DirGetPage(cm_dirOp_t * op,
1621 long index, cm_buf_t ** bufferpp, void ** datapp)
1623 osi_hyper_t pageOffset; /* offset of the dir page from the
1624 start of the directory */
1625 osi_hyper_t bufferOffset; /* offset of the buffer from the start
1629 cm_buf_t * bufferp = NULL;
1631 void * datap = NULL;
1635 osi_Log2(afsd_logp, "cm_DirGetPage for op 0x%p, index %d", op, index);
1637 pageOffset = ConvertLongToLargeInteger(index * CM_DIR_PAGESIZE);
1638 bufferOffset.HighPart = pageOffset.HighPart;
1639 bufferOffset.LowPart = pageOffset.LowPart & ~(cm_data.buf_blockSize - 1);
1641 bufferp = *bufferpp;
1642 if (bufferp != NULL) {
1643 osi_assert(cm_FidCmp(&bufferp->fid, &op->scp->fid) == 0);
1645 thyper = bufferp->offset;
1648 if (!bufferp || !LargeIntegerEqualTo(thyper, bufferOffset)) {
1652 buf_Release(bufferp);
1653 cm_DirOpDelBuffer(op, bufferp, 0);
1657 /* first check if we are already working with the buffer */
1658 if (cm_DirOpFindBuffer(op, bufferOffset, &bufferp)) {
1663 code = buf_Get(op->scp, &bufferOffset, &bufferp);
1665 osi_Log1(afsd_logp, " buf_Get returned code 0x%x", code);
1670 osi_assert(bufferp != NULL);
1672 /* DirOpAddBuffer will obtain bufferp->mx if necessary */
1673 code = cm_DirOpAddBuffer(op, bufferp);
1676 /* for some reason, the buffer was rejected. We can't use
1677 this buffer, and since this is the only buffer we can
1678 potentially use, there's no recourse.*/
1679 buf_Release(bufferp);
1687 /* now to figure out where the data is */
1688 thyper = LargeIntegerSubtract(pageOffset, bufferOffset);
1690 osi_assert(thyper.HighPart == 0);
1691 osi_assert(cm_data.buf_blockSize > thyper.LowPart &&
1692 cm_data.buf_blockSize - thyper.LowPart >= CM_DIR_PAGESIZE);
1694 datap = (void *) (((char *)bufferp->datap) + thyper.LowPart);
1699 /* also, if we are writing past EOF, we should make a note of the
1701 thyper = LargeIntegerAdd(pageOffset,
1702 ConvertLongToLargeInteger(CM_DIR_PAGESIZE));
1703 if (LargeIntegerLessThan(op->newLength, thyper)) {
1704 op->newLength = thyper;
1709 *bufferpp = bufferp;
1711 osi_Log1(afsd_logp, "cm_DirGetPage returning code 0x%x", code);
1718 cm_DirEntryListAdd(char * namep, cm_dirEntryList_t ** list)
1721 cm_dirEntryList_t * entry;
1723 len = strlen(namep);
1724 len += sizeof(cm_dirEntryList_t);
1726 entry = malloc(len);
1728 entry->nextp = *list;
1729 strcpy(entry->name, namep);
1735 cm_DirEntryListFree(cm_dirEntryList_t ** list)
1737 cm_dirEntryList_t * entry;
1738 cm_dirEntryList_t * next;
1740 for (entry = *list; entry; entry = next) {
1741 next = entry->nextp;