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>
29 afs_uint32 dir_lookup_hits = 0;
30 afs_uint32 dir_lookup_misses = 0;
31 afs_uint32 dir_create_entry = 0;
32 afs_uint32 dir_remove_entry = 0;
34 afs_uint64 dir_lookup_time = 0;
35 afs_uint64 dir_create_time = 0;
36 afs_uint64 dir_remove_time = 0;
38 afs_uint64 dir_enums = 0;
40 afs_int32 cm_BPlusTrees = 1;
42 int cm_MemDumpDirStats(FILE *outputFile, char *cookie, int lock)
47 sprintf(output, "%s - Dir Lookup Hits: %-8d\r\n", cookie, dir_lookup_hits);
48 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
49 sprintf(output, "%s - Misses: %-8d\r\n", cookie, dir_lookup_misses);
50 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
51 sprintf(output, "%s - Enums: %-8d\r\n", cookie, dir_enums);
52 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
53 sprintf(output, "%s - Create: %-8d\r\n", cookie, dir_create_entry);
54 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
55 sprintf(output, "%s - Remove: %-8d\r\n", cookie, dir_remove_entry);
56 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
58 sprintf(output, "%s - Dir Times Lookup: %-16I64d\r\n", cookie, dir_lookup_time);
59 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
60 sprintf(output, "%s - Create: %-16I64d\r\n", cookie, dir_create_time);
61 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
62 sprintf(output, "%s - Remove: %-16I64d\r\n", cookie, dir_remove_time);
63 WriteFile(outputFile, output, (DWORD)strlen(output), &zilch, NULL);
68 void cm_DirDumpStats(void)
70 afsi_log("Dir Lookup Hits: %-8d", dir_lookup_hits);
71 afsi_log(" Misses: %-8d", dir_lookup_misses);
72 afsi_log(" Enums: %-8d", dir_enums);
73 afsi_log(" Create: %-8d", dir_create_entry);
74 afsi_log(" Remove: %-8d", dir_remove_entry);
76 afsi_log("Dir Times Lookup: %-16I64d", dir_lookup_time);
77 afsi_log(" Create: %-16I64d", dir_create_time);
78 afsi_log(" Remove: %-16I64d", dir_remove_time);
82 /* Local static prototypes */
84 cm_DirGetBlob(cm_dirOp_t * op,
85 unsigned int blobno, cm_buf_t ** bufferpp, cm_dirEntry_t ** blobpp);
88 cm_DirFindItem(cm_dirOp_t * op,
90 cm_buf_t ** itembufpp, cm_dirEntry_t ** itempp,
91 cm_buf_t ** prevbufpp, unsigned short **previtempp);
94 cm_DirOpAddBuffer(cm_dirOp_t * op, cm_buf_t * buffer);
96 /* flags for cm_DirOpDelBuffer */
97 #define DIROP_MODIFIED 1
98 #define DIROP_SCPLOCKED 2
101 cm_DirOpDelBuffer(cm_dirOp_t * op, cm_buf_t * buffer, int flags);
104 cm_DirCheckStatus(cm_dirOp_t * op, int locked);
107 cm_DirReleasePage(cm_dirOp_t * op, cm_buf_t ** bufferpp, int modified);
110 cm_DirGetPage(cm_dirOp_t * op,
111 long index, cm_buf_t ** bufferpp, void ** datapp);
114 cm_DirFindBlobs(cm_dirOp_t * op, int nblobs);
117 cm_DirAddPage(cm_dirOp_t * op, int pageno);
120 cm_DirFreeBlobs(cm_dirOp_t * op, int firstblob, int nblobs);
123 cm_DirPrefetchBuffers(cm_dirOp_t * op);
125 /* compute how many 32 byte entries an AFS 3 dir requires for storing
126 * the specified name.
129 cm_NameEntries(char *namep, size_t *lenp)
133 i = (long)strlen(namep);
135 return 1 + ((i+16) >> 5);
138 /* Create an entry in a file. Dir is a file representation, while
139 entry is a string name.
142 op->scp->rw is unlocked
145 op->scp->rw is unlocked
147 None of the directory buffers for op->scp should be locked by the
151 cm_DirCreateEntry(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
155 LARGE_INTEGER start, end;
157 cm_dirEntry_t *ep = NULL;
158 cm_buf_t *entrybuf = NULL;
160 unsigned short *pp = NULL;
161 cm_buf_t *prevptrbuf = NULL;
163 cm_dirHeader_t *dhp = NULL;
164 cm_buf_t *dhpbuf = NULL;
168 /* check name quality */
172 QueryPerformanceCounter(&start);
176 osi_Log4(afsd_logp, "cm_DirCreateEntry for op 0x%p, name [%s] and fid[%d,%d]",
177 op, osi_LogSaveString(afsd_logp, entry), cfid->vnode, cfid->unique);
179 /* First check if file already exists. */
180 code = cm_DirFindItem(op,
185 cm_DirReleasePage(op, &entrybuf, FALSE);
186 cm_DirReleasePage(op, &prevptrbuf, FALSE);
191 blobs = cm_NameEntries(entry, NULL); /* number of entries required */
192 firstelt = cm_DirFindBlobs(op, blobs);
194 osi_Log0(afsd_logp, "cm_DirCreateEntry returning EFBIG");
195 code = EFBIG; /* directory is full */
199 /* First, we fill in the directory entry. */
200 code = cm_DirGetBlob(op, firstelt, &entrybuf, &ep);
206 ep->flag = CM_DIR_FFIRST;
207 ep->fid.vnode = htonl(cfid->vnode);
208 ep->fid.unique = htonl(cfid->unique);
209 strcpy(ep->name, entry);
211 /* Now we just have to thread it on the hash table list. */
212 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
214 cm_DirReleasePage(op, &entrybuf, TRUE);
219 i = cm_DirHash(entry);
221 ep->next = dhp->hashTable[i];
222 dhp->hashTable[i] = htons(firstelt);
224 cm_DirReleasePage(op, &dhpbuf, TRUE);
225 cm_DirReleasePage(op, &entrybuf, TRUE);
227 osi_Log0(afsd_logp, "cm_DirCreateEntry returning success");
231 QueryPerformanceCounter(&end);
233 dir_create_time += (end.QuadPart - start.QuadPart);
237 /* Return the length of a directory in pages
240 op->scp->rw is locked
243 op->scp->rw is locked
245 The first directory page for op->scp should not be locked by the
249 cm_DirLength(cm_dirOp_t * op)
252 cm_dirHeader_t *dhp = NULL;
253 cm_buf_t *dhpbuf = NULL;
257 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
261 if (dhp->header.pgcount != 0)
262 ctr = ntohs(dhp->header.pgcount);
264 /* old style, count the pages */
266 for (i = 0; i < CM_DIR_MAXPAGES; i++)
267 if (dhp->alloMap[i] != CM_DIR_EPP)
270 cm_DirReleasePage(op, &dhpbuf, FALSE);
271 return ctr * CM_DIR_PAGESIZE;
274 /* Delete a directory entry.
277 op->scp->rw is unlocked
280 op->scp->rw is unlocked
282 None of the directory buffers for op->scp should be locked by the
286 cm_DirDeleteEntry(cm_dirOp_t * op, char *entry)
288 /* Delete an entry from a directory, including update of all free
289 entry descriptors. */
292 cm_dirEntry_t *firstitem = NULL;
293 cm_buf_t *itembuf = NULL;
294 unsigned short *previtem = NULL;
295 cm_buf_t *pibuf = NULL;
299 LARGE_INTEGER start, end;
301 QueryPerformanceCounter(&start);
303 osi_Log2(afsd_logp, "cm_DirDeleteEntry for op 0x%p, entry [%s]",
304 op, osi_LogSaveString(afsd_logp, entry));
306 code = cm_DirFindItem(op, entry,
307 &itembuf, &firstitem,
310 osi_Log0(afsd_logp, "cm_DirDeleteEntry returning ENOENT");
317 *previtem = firstitem->next;
318 cm_DirReleasePage(op, &pibuf, TRUE);
320 thyper = itembuf->offset;
321 thyper = LargeIntegerAdd(thyper,
322 ConvertLongToLargeInteger(((char *) firstitem) - itembuf->datap));
323 thyper = ExtendedLargeIntegerDivide(thyper, 32, &junk);
325 index = thyper.LowPart;
326 osi_assert(thyper.HighPart == 0);
328 nitems = cm_NameEntries(firstitem->name, NULL);
329 cm_DirReleasePage(op, &itembuf, FALSE);
331 cm_DirFreeBlobs(op, index, nitems);
333 osi_Log0(afsd_logp, "cm_DirDeleteEntry returning success");
337 QueryPerformanceCounter(&end);
339 dir_remove_time += (end.QuadPart - start.QuadPart);
344 /* Find a bunch of contiguous entries; at least nblobs in a row.
346 Called with op->scp->rw */
348 cm_DirFindBlobs(cm_dirOp_t * op, int nblobs)
353 cm_dirHeader_t *dhp = NULL;
354 cm_buf_t *dhpbuf = NULL;
355 int dhpModified = FALSE;
357 cm_pageHeader_t *pp = NULL;
358 cm_buf_t *pagebuf = NULL;
359 int pageModified = FALSE;
365 osi_Log2(afsd_logp, "cm_DirFindBlobs for op 0x%p, nblobs = %d",
368 code = cm_DirGetPage(op, 0, &dhpbuf, (void **) &dhp);
372 for (i = 0; i < CM_DIR_BIGMAXPAGES; i++) {
373 if (i >= CM_DIR_MAXPAGES || dhp->alloMap[i] >= nblobs) {
374 /* if page could contain enough entries */
375 /* If there are CM_DIR_EPP free entries, then the page is
376 not even allocated. */
377 if (i >= CM_DIR_MAXPAGES) {
379 /* this pages exists past the end of the old-style dir */
380 pgcount = ntohs(dhp->header.pgcount);
382 pgcount = CM_DIR_MAXPAGES;
383 dhp->header.pgcount = htons(pgcount);
387 if (i > pgcount - 1) {
388 /* this page is bigger than last allocated page */
389 cm_DirAddPage(op, i);
390 dhp->header.pgcount = htons(i + 1);
393 } else if (dhp->alloMap[i] == CM_DIR_EPP) {
394 /* Add the page to the directory. */
395 cm_DirAddPage(op, i);
396 dhp->alloMap[i] = CM_DIR_EPP - 1;
397 dhp->header.pgcount = htons(i + 1);
401 /* the create flag is not set for the GetPage call below
402 since the page should have been added if necessary
404 code = cm_DirGetPage(op, i, &pagebuf, &pp);
406 cm_DirReleasePage(op, &dhpbuf, dhpModified);
410 for (j = 0; j <= CM_DIR_EPP - nblobs; j++) {
412 for (k = 0; k < nblobs; k++)
413 if ((pp->freeBitmap[(j + k) >> 3] >> ((j + k) & 7)) & 1) {
423 /* Here we have the first index in j. We update the allocation maps
424 * and free up any resources we've got allocated. */
425 if (i < CM_DIR_MAXPAGES) {
426 dhp->alloMap[i] -= nblobs;
430 cm_DirReleasePage(op, &dhpbuf, dhpModified);
432 for (k = 0; k < nblobs; k++)
433 pp->freeBitmap[(j + k) >> 3] |= 1 << ((j + k) & 7);
435 cm_DirReleasePage(op, &pagebuf, TRUE);
437 osi_Log0(afsd_logp, "cm_DirFindBlobs returning success");
439 return j + i * CM_DIR_EPP;
441 cm_DirReleasePage(op, &pagebuf, pageModified);
445 /* If we make it here, the directory is full. */
446 osi_Log0(afsd_logp, "cm_DirFindBlobs directory is full");
447 cm_DirReleasePage(op, &dhpbuf, dhpModified);
451 /* Add a page to a directory.
453 Called with op->scp->rw
456 cm_DirAddPage(cm_dirOp_t * op, int pageno)
459 cm_pageHeader_t *pp = NULL;
460 cm_buf_t *pagebuf = NULL;
463 osi_Log2(afsd_logp, "cm_DirAddPage for op 0x%p, pageno=%d", op, pageno);
465 code = cm_DirGetPage(op, pageno, &pagebuf, (void **) &pp);
469 pp->tag = htons(1234);
472 pp->freeCount = CM_DIR_EPP - 1; /* The first dude is already allocated */
473 pp->freeBitmap[0] = 0x01;
474 for (i = 1; i < CM_DIR_EPP / 8; i++) /* It's a constant */
475 pp->freeBitmap[i] = 0;
477 cm_DirReleasePage(op, &pagebuf, TRUE);
479 osi_Log0(afsd_logp, "cm_DirAddPage returning success");
484 /* Free a whole bunch of directory entries.
486 Called with op->scp->rw
489 cm_DirFreeBlobs(cm_dirOp_t * op, int firstblob, int nblobs)
494 cm_dirHeader_t *dhp = NULL;
495 cm_buf_t *dhpbuf = NULL;
496 int dhpmodified = FALSE;
498 cm_pageHeader_t *pp = NULL;
499 cm_buf_t *pagebuf = NULL;
502 osi_Log3(afsd_logp, "cm_DirFreeBlobs for op 0x%p, firstblob=%d, nblobs=%d",
503 op, firstblob, nblobs);
505 page = firstblob / CM_DIR_EPP;
506 firstblob -= CM_DIR_EPP * page; /* convert to page-relative entry */
508 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
512 if (page < CM_DIR_MAXPAGES) {
513 dhp->alloMap[page] += nblobs;
517 cm_DirReleasePage(op, &dhpbuf, dhpmodified);
519 code = cm_DirGetPage(op, page, &pagebuf, &pp);
521 for (i = 0; i < nblobs; i++)
522 pp->freeBitmap[(firstblob + i) >> 3] &=
523 ~(1 << ((firstblob + i) & 7));
524 cm_DirReleasePage(op, &pagebuf, TRUE);
527 osi_Log1(afsd_logp, "cm_DirFreeBlobs returning code 0x%x", code);
533 * Format an empty directory properly. Note that the first 13 entries in a
534 * directory header page are allocated, 1 to the page header, 4 to the
535 * allocation map and 8 to the hash table.
537 * Called with op->scp->rw unlocked
540 cm_DirMakeDir(cm_dirOp_t * op, cm_fid_t * me, cm_fid_t * parent)
543 cm_dirHeader_t *dhp = NULL;
544 cm_buf_t *dhpbuf = NULL;
548 osi_Log3(afsd_logp, "cm_DirMakeDir for op 0x%p, directory fid[%d, %d]",
549 op, me->vnode, me->unique);
550 osi_Log2(afsd_logp, " parent[%d, %d]",
551 parent->vnode, parent->unique);
553 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
559 dhp->header.pgcount = htons(1);
560 dhp->header.tag = htons(1234);
561 dhp->header.freeCount = (CM_DIR_EPP - CM_DIR_DHE - 1);
562 dhp->header.freeBitmap[0] = 0xff;
563 dhp->header.freeBitmap[1] = 0x1f;
564 for (i = 2; i < CM_DIR_EPP / 8; i++)
565 dhp->header.freeBitmap[i] = 0;
566 dhp->alloMap[0] = (CM_DIR_EPP - CM_DIR_DHE - 1);
567 for (i = 1; i < CM_DIR_MAXPAGES; i++)
568 dhp->alloMap[i] = CM_DIR_EPP;
569 for (i = 0; i < CM_DIR_NHASHENT; i++)
570 dhp->hashTable[i] = 0;
572 cm_DirReleasePage(op, &dhpbuf, TRUE);
574 cm_DirCreateEntry(op, ".", me);
575 cm_DirCreateEntry(op, "..", parent); /* Virtue is its own .. */
577 osi_Log0(afsd_logp, "cm_DirMakeDir returning success");
584 /* Look up a file name in directory.
587 op->scp->rw is unlocked
590 op->scp->rw is unlocked
592 None of the directory buffers for op->scp should be locked by the
596 cm_DirLookup(cm_dirOp_t * op, char *entry, cm_fid_t * cfid)
598 cm_dirEntry_t *firstitem = NULL;
599 cm_buf_t *itembuf = NULL;
600 unsigned short *previtem = NULL;
601 cm_buf_t *pibuf = NULL;
606 lock_AssertNone(&op->scp->rw);
608 QueryPerformanceCounter(&start);
610 osi_Log2(afsd_logp, "cm_DirLookup for op 0x%p, entry[%s]",
611 op, osi_LogSaveString(afsd_logp, entry));
613 code = cm_DirFindItem(op, entry,
614 &itembuf, &firstitem,
617 if (code == CM_ERROR_NOTINCACHE) {
618 code = cm_DirPrefetchBuffers(op);
620 code = cm_DirFindItem(op, entry, &itembuf, &firstitem,
630 cm_DirReleasePage(op, &pibuf, FALSE);
632 cfid->cell = op->scp->fid.cell;
633 cfid->volume = op->scp->fid.volume;
634 cfid->vnode = ntohl(firstitem->fid.vnode);
635 cfid->unique = ntohl(firstitem->fid.unique);
637 cm_DirReleasePage(op, &itembuf, FALSE);
639 osi_Log2(afsd_logp, "cm_DirLookup returning fid[%d,%d]",
640 cfid->vnode, cfid->unique);
646 QueryPerformanceCounter(&end);
648 dir_lookup_time += (end.QuadPart - start.QuadPart);
653 /* Look up a file name in directory.
656 op->scp->rw is locked
659 op->scp->rw is locked
661 None of the directory buffers for op->scp should be locked by the
665 cm_DirLookupOffset(cm_dirOp_t * op, char *entry, cm_fid_t *cfid, osi_hyper_t *offsetp)
667 cm_dirEntry_t *firstitem = NULL;
668 cm_buf_t *itembuf = NULL;
669 unsigned short *previtem = NULL;
670 cm_buf_t *pibuf = NULL;
674 osi_Log2(afsd_logp, "cm_DirLookupOffset for op 0x%p, entry[%s]",
675 op, osi_LogSaveString(afsd_logp, entry));
677 code = cm_DirFindItem(op, entry,
678 &itembuf, &firstitem,
683 cm_DirReleasePage(op, &pibuf, FALSE);
685 cfid->cell = op->scp->fid.cell;
686 cfid->volume = op->scp->fid.volume;
687 cfid->vnode = ntohl(firstitem->fid.vnode);
688 cfid->unique = ntohl(firstitem->fid.unique);
692 thyper = itembuf->offset;
693 thyper = LargeIntegerAdd(thyper,
694 ConvertLongToLargeInteger(((char *) firstitem) - itembuf->datap));
699 cm_DirReleasePage(op, &itembuf, FALSE);
701 osi_Log2(afsd_logp, "cm_DirLookupOffset returning fid[%d,%d]",
702 cfid->vnode, cfid->unique);
704 osi_Log2(afsd_logp, " offset [%x:%x]",
705 offsetp->HighPart, offsetp->LowPart);
711 /* Apply a function to every directory entry in a directory.
714 op->scp->rw is locked
717 op->scp->rw is locked
719 None of the directory buffers for op->scp should be locked by the
722 The hook function cannot modify or lock any directory buffers.
725 cm_DirApply(cm_dirOp_t * op, int (*hookproc) (void *, char *, long, long), void *hook)
727 /* Enumerate the contents of a directory. */
731 cm_dirHeader_t *dhp = NULL;
732 cm_buf_t *dhpbuf = NULL;
734 cm_dirEntry_t *ep = NULL;
735 cm_buf_t *epbuf = NULL;
739 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
743 for (i = 0; i < CM_DIR_NHASHENT; i++) {
744 /* For each hash chain, enumerate everyone on the list. */
745 num = ntohs(dhp->hashTable[i]);
747 /* Walk down the hash table list. */
748 code = cm_DirGetBlob(op, num, &epbuf, &ep);
750 cm_DirReleasePage(op, &dhpbuf, FALSE);
754 num = ntohs(ep->next);
755 (*hookproc) (hook, ep->name, ntohl(ep->fid.vnode),
756 ntohl(ep->fid.unique));
758 cm_DirReleasePage(op, &epbuf, FALSE);
761 cm_DirReleasePage(op, &dhpbuf, FALSE);
766 /* Check if a directory is empty
769 op->scp->rw is locked
772 op->scp->rw is locked
774 None of the directory buffers for op->scp should be locked by the
778 cm_DirIsEmpty(cm_dirOp_t * op)
780 /* Enumerate the contents of a directory. */
784 cm_dirHeader_t *dhp = NULL;
785 cm_buf_t *dhpbuf = NULL;
787 cm_dirEntry_t *ep = NULL;
788 cm_buf_t *epbuf = NULL;
792 code = cm_DirGetPage(op, 0, &dhpbuf, &dhp);
796 for (i = 0; i < CM_DIR_NHASHENT; i++) {
797 /* For each hash chain, enumerate everyone on the list. */
798 num = ntohs(dhp->hashTable[i]);
801 /* Walk down the hash table list. */
802 code = cm_DirGetBlob(op, num, &epbuf, &ep);
806 if (strcmp(ep->name, "..") && strcmp(ep->name, ".")) {
807 cm_DirReleasePage(op, &epbuf, FALSE);
808 cm_DirReleasePage(op, &dhpbuf, FALSE);
811 num = ntohs(ep->next);
812 cm_DirReleasePage(op, &epbuf, FALSE);
815 cm_DirReleasePage(op, &dhpbuf, FALSE);
819 /* Return a pointer to an entry, given its number.
823 if *bufferpp != NULL, then *bufferpp->mx is locked
826 scp->rw may be unlocked
827 *bufferpp may be released
831 if *bufferpp != NULL, then *bufferpp->mx is locked
833 *bufferpp should be released via cm_DirReleasePage() or any other
834 *call that releases a directory buffer.
837 cm_DirGetBlob(cm_dirOp_t * op,
838 unsigned int blobno, cm_buf_t ** bufferpp, cm_dirEntry_t ** blobpp)
843 osi_Log2(afsd_logp, "cm_DirGetBlob for op 0x%p, blobno=%d",
846 code = cm_DirGetPage(op, blobno >> CM_DIR_LEPP,
847 bufferpp, (void **) &ep);
851 *blobpp = (cm_dirEntry_t *) (ep + 32 * (blobno & (CM_DIR_EPP - 1)));
857 cm_DirHash(char *string)
859 /* Hash a string to a number between 0 and NHASHENT. */
864 while ((tc = (*string++))) {
868 tval = hval & (CM_DIR_NHASHENT - 1);
872 tval = CM_DIR_NHASHENT - tval;
876 /* Find a directory entry, given its name. This entry returns a
877 * pointer to a locked buffer, and a pointer to a locked buffer (in
878 * previtem) referencing the found item (to aid the delete code). If
879 * no entry is found, however, no items are left locked, and a null
880 * pointer is returned instead.
889 cm_DirFindItem(cm_dirOp_t * op,
891 cm_buf_t ** itembufpp, cm_dirEntry_t ** itempp,
892 cm_buf_t ** prevbufpp, unsigned short **previtempp)
895 cm_dirHeader_t *dhp = NULL;
896 unsigned short *lp = NULL;
897 cm_dirEntry_t *tp = NULL;
898 cm_buf_t *hashbufp = NULL;
899 cm_buf_t *itembufp = NULL;
902 osi_Log2(afsd_logp, "cm_DirFindItem for op 0x%p, entry[%s]",
903 op, osi_LogSaveString(afsd_logp, ename));
905 i = cm_DirHash(ename);
907 if (op->scp->fileType != CM_SCACHETYPE_DIRECTORY) {
908 osi_Log0(afsd_logp, "cm_DirFindItem: The scp is not a directory");
909 return CM_ERROR_INVAL;
912 code = cm_DirGetPage(op, 0, &hashbufp, (void **) &dhp);
917 if (dhp->hashTable[i] == 0) {
919 osi_Log1(afsd_logp, "cm_DirFindItem: Hash bucket %d is empty", i);
920 cm_DirReleasePage(op, &hashbufp, FALSE);
924 code = cm_DirGetBlob(op,
925 (u_short) ntohs(dhp->hashTable[i]),
928 cm_DirReleasePage(op, &hashbufp, FALSE);
932 lp = &(dhp->hashTable[i]);
936 lp : pointer to blob number of entry we are looking at
937 hashbufp : buffer containing lp
938 tp : pointer to entry we are looking at
939 itembufp : buffer containing tp
942 /* Look at each hash conflict entry. */
943 if (!strcmp(ename, tp->name)) {
944 osi_Log0(afsd_logp, "cm_DirFindItem: returning success");
945 /* Found our entry. */
947 *prevbufpp = hashbufp;
949 *itembufpp = itembufp;
954 cm_DirReleasePage(op, &hashbufp, FALSE);
961 /* The end of the line */
962 osi_Log0(afsd_logp, "cm_DirFindItem: returning ENOENT");
963 cm_DirReleasePage(op, &hashbufp, FALSE);
967 code = cm_DirGetBlob(op,
968 (u_short) ntohs(*lp),
972 cm_DirReleasePage(op, &hashbufp, FALSE);
978 /* Begin a sequence of directory operations.
979 * Called with scp->rw unlocked.
982 cm_BeginDirOp(cm_scache_t * scp, cm_user_t * userp, cm_req_t * reqp,
983 afs_uint32 lockType, afs_uint32 flags, cm_dirOp_t * op)
986 int i, mxheld = 0, haveWrite = 0;
988 osi_Log4(afsd_logp, "Beginning dirOp[0x%p] for scp[0x%p], userp[0x%p] lockType[0x%x]",
989 op, scp, userp, lockType);
991 memset(op, 0, sizeof(*op));
997 op->req = *reqp; /* copy the values from the input */
999 op->dirtyBufCount = 0;
1002 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1003 op->buffers[i].flags = 0;
1006 if (lockType == CM_DIRLOCK_WRITE) {
1007 lock_ObtainWrite(&scp->dirlock);
1010 lock_ObtainRead(&scp->dirlock);
1013 lock_ObtainWrite(&scp->rw);
1015 code = cm_DirCheckStatus(op, 1);
1017 op->length = scp->length;
1018 op->newLength = op->length;
1019 op->dataVersion = scp->dataVersion;
1020 op->newDataVersion = op->dataVersion;
1023 if (!cm_BPlusTrees ||
1025 scp->dirDataVersion == scp->dataVersion))
1027 /* we know that haveWrite matches lockType at this point */
1029 case CM_DIRLOCK_NONE:
1031 lock_ReleaseWrite(&scp->dirlock);
1033 lock_ReleaseRead(&scp->dirlock);
1035 case CM_DIRLOCK_READ:
1036 osi_assert(!haveWrite);
1038 case CM_DIRLOCK_WRITE:
1040 osi_assert(haveWrite);
1042 op->lockType = lockType;
1044 if (!(scp->dirBplus &&
1045 scp->dirDataVersion == scp->dataVersion))
1050 lock_ReleaseWrite(&scp->rw);
1053 lock_ConvertRToW(&scp->dirlock);
1057 lock_ObtainWrite(&scp->rw);
1060 if (scp->dirBplus &&
1061 scp->dirDataVersion != scp->dataVersion)
1065 freeBtree(scp->dirBplus);
1066 scp->dirBplus = NULL;
1067 scp->dirDataVersion = CM_SCACHE_VERSION_BAD;
1070 if ((!scp->dirBplus) &&
1071 (!(flags & CM_DIROP_FLAG_NOBUILDTREE))) {
1073 lock_ReleaseWrite(&scp->rw);
1076 code = cm_BPlusDirBuildTree(scp, userp, reqp);
1077 osi_Log1(afsd_logp, "cm_BeginDirOp cm_BPlusDirBuildTree code 0x%x", code);
1079 lock_ObtainWrite(&scp->rw);
1084 freeBtree(scp->dirBplus);
1085 scp->dirBplus = NULL;
1086 scp->dirDataVersion = CM_SCACHE_VERSION_BAD;
1088 if (op->dataVersion != scp->dataVersion) {
1089 /* We lost the race, therefore we must update the
1090 * dirop state and retry to build the tree.
1092 op->length = scp->length;
1093 op->newLength = op->length;
1094 op->dataVersion = scp->dataVersion;
1095 op->newDataVersion = op->dataVersion;
1100 scp->dirDataVersion = scp->dataVersion;
1107 case CM_DIRLOCK_NONE:
1108 lock_ReleaseWrite(&scp->dirlock);
1110 case CM_DIRLOCK_READ:
1111 lock_ConvertWToR(&scp->dirlock);
1113 case CM_DIRLOCK_WRITE:
1115 /* got it already */;
1117 op->lockType = lockType;
1121 /* we know that haveWrite matches lockType at this point */
1123 case CM_DIRLOCK_NONE:
1125 lock_ReleaseWrite(&scp->dirlock);
1127 lock_ReleaseRead(&scp->dirlock);
1129 case CM_DIRLOCK_READ:
1130 osi_assert(!haveWrite);
1132 case CM_DIRLOCK_WRITE:
1134 osi_assert(haveWrite);
1136 op->lockType = lockType;
1141 lock_ReleaseWrite(&scp->rw);
1145 lock_ReleaseWrite(&scp->dirlock);
1147 lock_ReleaseRead(&scp->dirlock);
1150 osi_Log1(afsd_logp, "cm_BeginDirOp return code 0x%x", code);
1156 /* Check if it is safe for us to perform local directory updates.
1157 Called with op->scp->rw unlocked. */
1159 cm_CheckDirOpForSingleChange(cm_dirOp_t * op)
1164 if (op->scp == NULL)
1167 lock_ObtainWrite(&op->scp->rw);
1168 code = cm_DirCheckStatus(op, 1);
1171 op->dataVersion == op->scp->dataVersion - 1) {
1172 /* only one set of changes happened between cm_BeginDirOp()
1173 and this function. It is safe for us to perform local
1175 op->newDataVersion = op->scp->dataVersion;
1176 op->newLength = op->scp->serverLength;
1180 lock_ReleaseWrite(&op->scp->rw);
1183 osi_Log0(afsd_logp, "cm_CheckDirOpForSingleChange succeeded");
1186 "cm_CheckDirOpForSingleChange failed. code=0x%x, old dv=%d, new dv=%d",
1187 code, op->dataVersion, op->scp->dataVersion);
1191 /* End a sequence of directory operations.
1192 * Called with op->scp->rw unlocked.*/
1194 cm_EndDirOp(cm_dirOp_t * op)
1198 osi_Log4(afsd_logp, "Ending dirOp[0x%p] scp[0x%p] lockType[0x%x] with %d dirty buffer releases",
1199 op, op->scp, op->lockType, op->dirtyBufCount);
1201 if (op->scp == NULL)
1204 if (op->dirtyBufCount > 0) {
1206 /* update the data version on the B+ tree */
1207 if (op->scp->dirBplus &&
1208 op->scp->dirDataVersion == op->dataVersion) {
1210 switch (op->lockType) {
1211 case CM_DIRLOCK_READ:
1212 lock_ReleaseRead(&op->scp->dirlock);
1213 /* fall through ... */
1214 case CM_DIRLOCK_NONE:
1215 lock_ObtainWrite(&op->scp->dirlock);
1216 op->lockType = CM_DIRLOCK_WRITE;
1218 case CM_DIRLOCK_WRITE:
1220 /* already got it */;
1222 op->scp->dirDataVersion = op->newDataVersion;
1226 /* we made changes. We should go through the list of buffers
1227 * and update the dataVersion for each. */
1228 lock_ObtainWrite(&op->scp->rw);
1229 code = buf_ForceDataVersion(op->scp, op->dataVersion, op->newDataVersion);
1230 op->scp->flags |= CM_SCACHEFLAG_LOCAL;
1231 lock_ReleaseWrite(&op->scp->rw);
1234 switch (op->lockType) {
1235 case CM_DIRLOCK_NONE:
1237 case CM_DIRLOCK_READ:
1238 lock_ReleaseRead(&op->scp->dirlock);
1240 case CM_DIRLOCK_WRITE:
1242 lock_ReleaseWrite(&op->scp->dirlock);
1246 cm_ReleaseSCache(op->scp);
1250 cm_ReleaseUser(op->userp);
1253 osi_assertx(op->nBuffers == 0, "Buffer leak after dirOp termination");
1256 osi_Log1(afsd_logp, "cm_EndDirOp return code 0x%x", code);
1261 /* NOTE: Called without scp->rw and without bufferp->mx */
1263 cm_DirOpAddBuffer(cm_dirOp_t * op, cm_buf_t * bufferp)
1268 osi_Log2(afsd_logp, "cm_DirOpAddBuffer for op 0x%p, buffer %p", op, bufferp);
1270 if (bufferp == NULL)
1273 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1274 if ((op->buffers[i].flags & CM_DIROPBUFF_INUSE) &&
1275 op->buffers[i].bufferp == bufferp) {
1280 if (i < CM_DIROP_MAXBUFFERS) {
1281 /* we already have this buffer on our list */
1283 op->buffers[i].refcount++;
1285 "cm_DirOpAddBuffer: the buffer is already listed for the dirOp");
1288 /* we have to add a new buffer */
1289 osi_assertx(op->nBuffers < CM_DIROP_MAXBUFFERS - 1,
1290 "DirOp has exceeded CM_DIROP_MAXBUFFERS buffers");
1292 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1293 if (!(op->buffers[i].flags & CM_DIROPBUFF_INUSE))
1297 osi_assert(i < CM_DIROP_MAXBUFFERS);
1299 lock_ObtainMutex(&bufferp->mx);
1300 lock_ObtainWrite(&op->scp->rw);
1302 /* Make sure we are synchronized. */
1303 osi_assert(op->lockType != CM_DIRLOCK_NONE);
1305 code = cm_SyncOp(op->scp, bufferp, op->userp, &op->req, PRSFS_LOOKUP,
1306 CM_SCACHESYNC_NEEDCALLBACK |
1307 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ) |
1308 CM_SCACHESYNC_BUFLOCKED);
1310 if (code == 0 && bufferp->dataVersion != op->dataVersion) {
1312 "cm_DirOpAddBuffer: buffer data version mismatch. buf dv = %d. needs %d",
1313 bufferp->dataVersion, op->dataVersion);
1315 cm_SyncOpDone(op->scp, bufferp,
1316 CM_SCACHESYNC_NEEDCALLBACK |
1317 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ) |
1318 CM_SCACHESYNC_BUFLOCKED);
1319 code = CM_ERROR_NOTINCACHE;
1322 lock_ReleaseWrite(&op->scp->rw);
1323 lock_ReleaseMutex(&bufferp->mx);
1326 osi_Log1(afsd_logp, "cm_DirOpAddBuffer: failed to sync buffer. code=0x%x",
1332 op->buffers[i].bufferp = bufferp;
1333 op->buffers[i].refcount = 1; /* start with one ref */
1334 op->buffers[i].flags = CM_DIROPBUFF_INUSE;
1338 osi_Log0(afsd_logp, "cm_DirOpAddBuffer: returning success");
1344 /* Note: Called without op->scp->rw */
1346 cm_DirOpFindBuffer(cm_dirOp_t * op, osi_hyper_t offset, cm_buf_t ** bufferpp)
1350 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1351 if ((op->buffers[i].flags & CM_DIROPBUFF_INUSE) &&
1352 LargeIntegerEqualTo(op->buffers[i].bufferp->offset, offset))
1356 if (i < CM_DIROP_MAXBUFFERS) {
1358 op->buffers[i].refcount++;
1359 buf_Hold(op->buffers[i].bufferp);
1360 *bufferpp = op->buffers[i].bufferp;
1362 osi_Log2(afsd_logp, "cm_DirOpFindBuffer: found buffer for offset [%x:%x]",
1363 offset.HighPart, offset.LowPart);
1367 osi_Log2(afsd_logp, "cm_DirOpFindBuffer: buffer not found for offset [%x:%x]",
1368 offset.HighPart, offset.LowPart);
1373 /* NOTE: called with scp->rw held or not depending on the flags */
1375 cm_DirOpDelBuffer(cm_dirOp_t * op, cm_buf_t * bufferp, int flags)
1379 osi_Log3(afsd_logp, "cm_DirOpDelBuffer for op 0x%p, buffer 0x%p, flags=%d",
1380 op, bufferp, flags);
1382 for (i=0; i < CM_DIROP_MAXBUFFERS; i++) {
1383 if ((op->buffers[i].flags & CM_DIROPBUFF_INUSE) &&
1384 op->buffers[i].bufferp == bufferp)
1388 if (i < CM_DIROP_MAXBUFFERS) {
1390 if (flags & DIROP_MODIFIED)
1391 op->dirtyBufCount++;
1393 osi_assert(op->buffers[i].refcount > 0);
1394 op->buffers[i].refcount --;
1396 if (op->buffers[i].refcount == 0) {
1397 /* this was the last reference we had */
1399 osi_Log0(afsd_logp, "cm_DirOpDelBuffer: releasing buffer");
1401 /* if this buffer was modified, then we update the data
1402 version of the buffer with the data version of the
1404 if (!(flags & DIROP_SCPLOCKED)) {
1405 lock_ObtainWrite(&op->scp->rw);
1408 /* first make sure that the buffer is idle. It should
1409 have been idle all along. */
1410 osi_assertx((bufferp->cmFlags & (CM_BUF_CMFETCHING |
1411 CM_BUF_CMSTORING)) == 0,
1412 "Buffer is not idle while performing dirOp");
1414 cm_SyncOpDone(op->scp, bufferp,
1415 CM_SCACHESYNC_NEEDCALLBACK |
1416 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ));
1419 osi_assert(bufferp->dataVersion == op->dataVersion);
1422 lock_ReleaseWrite(&op->scp->rw);
1424 lock_ObtainMutex(&bufferp->mx);
1426 if (flags & DIROP_SCPLOCKED) {
1427 lock_ObtainWrite(&op->scp->rw);
1430 if (flags & DIROP_MODIFIED) {
1431 /* We don't update the dataversion here. Instead we
1432 wait until the dirOp is completed and then flip the
1433 dataversion on all the buffers in one go.
1434 Otherwise we won't know if the dataversion is
1435 current because it was fetched from the server or
1436 because we touched it during the dirOp. */
1438 if (bufferp->userp != op->userp) {
1439 if (bufferp->userp != NULL)
1440 cm_ReleaseUser(bufferp->userp);
1441 cm_HoldUser(op->userp);
1442 bufferp->userp = op->userp;
1446 lock_ReleaseMutex(&bufferp->mx);
1448 op->buffers[i].bufferp = NULL;
1449 buf_Release(bufferp);
1450 op->buffers[i].flags = 0;
1456 /* we have other references to this buffer. so we have to
1462 osi_Log0(afsd_logp, "cm_DirOpDelBuffer: buffer not found");
1463 osi_assertx(FALSE, "Attempt to delete a non-existent buffer from a dirOp");
1468 /* Check if we have current status and a callback for the given scp.
1469 This should be called before cm_DirGetPage() is called per scp.
1472 scp->rw locked state indicated by parameter
1475 scp->rw same state as upon entry
1478 scp->rw may be released
1481 cm_DirCheckStatus(cm_dirOp_t * op, int scp_locked)
1486 lock_ObtainWrite(&op->scp->rw);
1487 code = cm_SyncOp(op->scp, NULL, op->userp, &op->req, PRSFS_LOOKUP,
1488 CM_SCACHESYNC_NEEDCALLBACK | CM_SCACHESYNC_GETSTATUS);
1490 lock_ReleaseWrite(&op->scp->rw);
1492 osi_Log2(afsd_logp, "cm_DirCheckStatus for op 0x%p returning code 0x%x",
1498 /* Attempt to prefetch all the buffers for this operation.
1500 Called with scp->rw unlocked
1503 cm_DirPrefetchBuffers(cm_dirOp_t * op)
1507 cm_buf_t *bufferp = NULL;
1509 osi_Log1(afsd_logp, "cm_DirPrefetchBuffers for op 0x%p", op);
1511 /* prefetching is only done on read operations where we don't
1512 expect the data version to change. */
1513 if (op->dataVersion != op->newDataVersion) {
1514 osi_Log0(afsd_logp, "Skipping prefetch for write operation.");
1515 return CM_ERROR_INVAL;
1518 lock_ObtainWrite(&op->scp->rw);
1520 /* When we are prefetching a file, we first flush out any of its
1521 contents just to make sure that we don't end up with buffers
1522 that was locally modified. */
1524 if (op->scp->flags & CM_SCACHEFLAG_LOCAL)
1525 op->scp->bufDataVersionLow = op->scp->dataVersion;
1527 offset = ConvertLongToLargeInteger(0);
1528 while (LargeIntegerLessThan(offset, op->scp->length)) {
1529 osi_Log2(afsd_logp, "Trying prefetch for offset %08x:%08x",
1530 offset.HighPart, offset.LowPart);
1531 lock_ReleaseWrite(&op->scp->rw);
1533 code = buf_Get(op->scp, &offset, &op->req, &bufferp);
1535 lock_ObtainWrite(&op->scp->rw);
1542 code = cm_SyncOp(op->scp, bufferp, op->userp, &op->req, PRSFS_LOOKUP,
1543 CM_SCACHESYNC_NEEDCALLBACK |
1544 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ));
1549 cm_SyncOpDone(op->scp, bufferp, CM_SCACHESYNC_NEEDCALLBACK |
1550 (op->lockType == CM_DIRLOCK_WRITE ? CM_SCACHESYNC_WRITE : CM_SCACHESYNC_READ));
1552 if (cm_HaveBuffer(op->scp, bufferp, 0))
1555 code = cm_GetBuffer(op->scp, bufferp, NULL, op->userp, &op->req);
1564 buf_Release(bufferp);
1568 offset = LargeIntegerAdd(offset, ConvertLongToLargeInteger(cm_data.buf_blockSize));
1571 lock_ReleaseWrite(&op->scp->rw);
1573 osi_Log1(afsd_logp, "cm_DirPrefetchBuffers returning code 0x%x", code);
1578 /* Release a directory buffer that was obtained via a call to
1579 cm_DirGetPage() or any other function that returns a locked, held,
1580 directory page buffer.
1582 Called with scp->rw unlocked
1585 cm_DirReleasePage(cm_dirOp_t * op, cm_buf_t ** bufferpp, int modified)
1592 cm_DirOpDelBuffer(op, *bufferpp,
1593 ((modified ? DIROP_MODIFIED : 0)));
1594 buf_Release(*bufferpp);
1601 Returns the index'th directory page from scp. The userp and reqp
1602 will be used to fetch the buffer from the fileserver if necessary.
1603 If the call is successful, a locked and held cm_buf_t is returned
1604 via buferpp and a pointer to the directory page is returned via
1607 The returned buffer should be released via a call to
1608 cm_DirReleasePage() or by passing it into a subsequent call to
1609 cm_DirGetPage() for the *same* scp.
1611 If a *locked* buffer for the *same* scp is passed in via bufferpp
1612 to the function, it will check if the requested directory page is
1613 located in the specified buffer. If not, the buffer will be
1614 released and a new buffer returned that contains the requested
1617 If the specified page exists beyond the EOF for the scp, a new
1618 buffer will be allocated only if create is set to TRUE.
1620 Note: If a buffer is specified on entry via bufferpp, it is assumed
1621 that the buffer is unmodified. If the buffer is modified, it
1622 should be released via cm_DirReleasePage().
1626 If *bufferpp is non-NULL, then *bufferpp->mx is locked.
1630 If *bufferpp is non-NULL, then *bufferpp->mx is locked.
1633 scp->rw will be obtained and released
1637 cm_DirGetPage(cm_dirOp_t * op,
1638 long index, cm_buf_t ** bufferpp, void ** datapp)
1640 osi_hyper_t pageOffset; /* offset of the dir page from the
1641 start of the directory */
1642 osi_hyper_t bufferOffset; /* offset of the buffer from the start
1646 cm_buf_t * bufferp = NULL;
1648 void * datap = NULL;
1652 osi_Log2(afsd_logp, "cm_DirGetPage for op 0x%p, index %d", op, index);
1654 pageOffset = ConvertLongToLargeInteger(index * CM_DIR_PAGESIZE);
1655 bufferOffset.HighPart = pageOffset.HighPart;
1656 bufferOffset.LowPart = pageOffset.LowPart & ~(cm_data.buf_blockSize - 1);
1658 bufferp = *bufferpp;
1659 if (bufferp != NULL) {
1660 osi_assert(cm_FidCmp(&bufferp->fid, &op->scp->fid) == 0);
1662 thyper = bufferp->offset;
1665 if (!bufferp || !LargeIntegerEqualTo(thyper, bufferOffset)) {
1669 buf_Release(bufferp);
1670 cm_DirOpDelBuffer(op, bufferp, 0);
1674 /* first check if we are already working with the buffer */
1675 if (cm_DirOpFindBuffer(op, bufferOffset, &bufferp)) {
1680 code = buf_Get(op->scp, &bufferOffset, &op->req, &bufferp);
1682 osi_Log1(afsd_logp, " buf_Get returned code 0x%x", code);
1687 osi_assert(bufferp != NULL);
1689 /* DirOpAddBuffer will obtain bufferp->mx if necessary */
1690 code = cm_DirOpAddBuffer(op, bufferp);
1693 /* for some reason, the buffer was rejected. We can't use
1694 this buffer, and since this is the only buffer we can
1695 potentially use, there's no recourse.*/
1696 buf_Release(bufferp);
1704 /* now to figure out where the data is */
1705 thyper = LargeIntegerSubtract(pageOffset, bufferOffset);
1707 osi_assert(thyper.HighPart == 0);
1708 osi_assert(cm_data.buf_blockSize > thyper.LowPart &&
1709 cm_data.buf_blockSize - thyper.LowPart >= CM_DIR_PAGESIZE);
1711 datap = (void *) (((char *)bufferp->datap) + thyper.LowPart);
1716 /* also, if we are writing past EOF, we should make a note of the
1718 thyper = LargeIntegerAdd(pageOffset,
1719 ConvertLongToLargeInteger(CM_DIR_PAGESIZE));
1720 if (LargeIntegerLessThan(op->newLength, thyper)) {
1721 op->newLength = thyper;
1726 *bufferpp = bufferp;
1728 osi_Log1(afsd_logp, "cm_DirGetPage returning code 0x%x", code);
1735 cm_DirEntryListAdd(char * namep, cm_dirEntryList_t ** list)
1738 cm_dirEntryList_t * entry;
1740 len = strlen(namep);
1741 len += sizeof(cm_dirEntryList_t);
1743 entry = malloc(len);
1745 entry->nextp = *list;
1746 strcpy(entry->name, namep);
1752 cm_DirEntryListFree(cm_dirEntryList_t ** list)
1754 cm_dirEntryList_t * entry;
1755 cm_dirEntryList_t * next;
1757 for (entry = *list; entry; entry = next) {
1758 next = entry->nextp;