src/dir/dir.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 #include <afsconfig.h>
  11 #include <afs/param.h>
  12
  13 #ifdef KERNEL
  14 # if !defined(UKERNEL)
  15 #  include "h/types.h"
  16 #  if !defined(AFS_LINUX26_ENV)
  17 #   include "h/param.h"
  18 #  endif
  19 #  ifdef        AFS_AUX_ENV
  20 #   include "h/mmu.h"
  21 #   include "h/seg.h"
  22 #   include "h/sysmacros.h"
  23 #   include "h/signal.h"
  24 #   include "h/errno.h"
  25 #  endif
  26 #  include "h/time.h"
  27 #  if defined(AFS_AIX_ENV) || defined(AFS_SGI_ENV) || defined(AFS_SUN5_ENV) || defined(AFS_LINUX20_ENV)
  28 #   include "h/errno.h"
  29 #  else
  30 #   if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX20_ENV)
  31 #    include "h/kernel.h"
  32 #   endif
  33 #  endif
  34 #  if   defined(AFS_SUN5_ENV) || defined(AFS_HPUX_ENV) || defined(AFS_FBSD_ENV) || defined(AFS_DARWIN80_ENV)
  35 #   include "afs/sysincludes.h"
  36 #  endif
  37 #  if !defined(AFS_SGI64_ENV) && !defined(AFS_DARWIN_ENV) && !defined(AFS_OBSD48_ENV) && !defined(AFS_NBSD_ENV)
  38 #   include "h/user.h"
  39 #  endif /* AFS_SGI64_ENV */
  40 #  include "h/uio.h"
  41 #  if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX20_ENV) && !defined(AFS_HPUX110_ENV)
  42 #   include "h/mbuf.h"
  43 #  endif
  44 #  ifndef AFS_LINUX20_ENV
  45 #   include "netinet/in.h"
  46 #  endif
  47 # else /* !defined(UKERNEL) */
  48 #  include "afs/stds.h"
  49 #  include "afs/sysincludes.h"
  50 # endif /* !defined(UKERNEL) */
  51
  52 /* afs_buffer.c */
  53 /* These are needed because afs_prototypes.h is not included here */
  54 struct dcache;
  55 struct DirBuffer;
  56 extern int DRead(struct dcache *adc, int page, struct DirBuffer *);
  57 extern int DNew(struct dcache *adc, int page, struct DirBuffer *);
  58
  59 # include "afs/afs_osi.h"
  60
  61 # include "afs/dir.h"
  62
  63 # ifdef AFS_LINUX20_ENV
  64 #  include "h/string.h"
  65 # endif
  66
  67 #else /* KERNEL */
  68
  69 # include <roken.h>
  70 # include "dir.h"
  71 #endif /* KERNEL */
  72
  73 /* Local static prototypes */
  74 static int FindBlobs(dir_file_t, int);
  75 static int AddPage(dir_file_t, int);
  76 static void FreeBlobs(dir_file_t, int, int);
  77 static int FindItem(dir_file_t, char *, struct DirBuffer *,
  78                     struct DirBuffer *);
  79
  80 /* Find out how many entries are required to store a name. */
  81 int
  82 afs_dir_NameBlobs(char *name)
  83 {
  84     int i;
  85     i = strlen(name) + 1;
  86     return 1 + ((i + 15) >> 5);
  87 }
  88
  89 /* Create an entry in a file.  Dir is a file representation, while entry is
  90  * a string name. */
  91 int
  92 afs_dir_Create(dir_file_t dir, char *entry, void *voidfid)
  93 {
  94     afs_int32 *vfid = (afs_int32 *) voidfid;
  95     int blobs, firstelt;
  96     int i;
  97     struct DirBuffer entrybuf, prevbuf, headerbuf;
  98     struct DirEntry *ep;
  99     struct DirHeader *dhp;
 100     int code;
 101
 102     /* check name quality */
 103     if (*entry == 0)
 104         return EINVAL;
 105
 106     /* First check if file already exists. */
 107     code = FindItem(dir, entry, &prevbuf, &entrybuf);
 108     if (code && code != ENOENT) {
 109         return code;
 110     }
 111     if (code == 0) {
 112         DRelease(&entrybuf, 0);
 113         DRelease(&prevbuf, 0);
 114         return EEXIST;
 115     }
 116
 117     blobs = afs_dir_NameBlobs(entry);   /* number of entries required */
 118     firstelt = FindBlobs(dir, blobs);
 119     if (firstelt < 0)
 120         return EFBIG;           /* directory is full */
 121
 122     /* First, we fill in the directory entry. */
 123     if (afs_dir_GetBlob(dir, firstelt, &entrybuf) != 0)
 124         return EIO;
 125     ep = (struct DirEntry *)entrybuf.data;
 126
 127     ep->flag = FFIRST;
 128     ep->fid.vnode = htonl(vfid[1]);
 129     ep->fid.vunique = htonl(vfid[2]);
 130     strcpy(ep->name, entry);
 131
 132     /* Now we just have to thread it on the hash table list. */
 133     if (DRead(dir, 0, &headerbuf) != 0) {
 134         DRelease(&entrybuf, 1);
 135         return EIO;
 136     }
 137     dhp = (struct DirHeader *)headerbuf.data;
 138
 139     i = afs_dir_DirHash(entry);
 140     ep->next = dhp->hashTable[i];
 141     dhp->hashTable[i] = htons(firstelt);
 142     DRelease(&headerbuf, 1);
 143     DRelease(&entrybuf, 1);
 144     return 0;
 145 }
 146
 147 int
 148 afs_dir_Length(dir_file_t dir)
 149 {
 150     int i, ctr;
 151     struct DirBuffer headerbuf;
 152     struct DirHeader *dhp;
 153
 154     if (DRead(dir, 0, &headerbuf) != 0)
 155         return 0;
 156     dhp = (struct DirHeader *)headerbuf.data;
 157
 158     if (dhp->header.pgcount != 0)
 159         ctr = ntohs(dhp->header.pgcount);
 160     else {
 161         /* old style, count the pages */
 162         ctr = 0;
 163         for (i = 0; i < MAXPAGES; i++)
 164             if (dhp->alloMap[i] != EPP)
 165                 ctr++;
 166     }
 167     DRelease(&headerbuf, 0);
 168     return ctr * AFS_PAGESIZE;
 169 }
 170
 171 /* Delete an entry from a directory, including update of all free entry
 172  * descriptors. */
 173 int
 174 afs_dir_Delete(dir_file_t dir, char *entry)
 175 {
 176
 177     int nitems, index;
 178     struct DirBuffer entrybuf, prevbuf;
 179     struct DirEntry *firstitem;
 180     unsigned short *previtem;
 181     int code;
 182
 183     code = FindItem(dir, entry, &prevbuf, &entrybuf);
 184     if (code) {
 185         return code;
 186     }
 187
 188     firstitem = (struct DirEntry *)entrybuf.data;
 189     previtem = (unsigned short *)prevbuf.data;
 190
 191     *previtem = firstitem->next;
 192     DRelease(&prevbuf, 1);
 193     index = DVOffset(&entrybuf) / 32;
 194     nitems = afs_dir_NameBlobs(firstitem->name);
 195     /* Clear entire DirEntry and any DirXEntry extensions */
 196     memset(firstitem, 0, nitems * sizeof(*firstitem));
 197     DRelease(&entrybuf, 1);
 198     FreeBlobs(dir, index, nitems);
 199     return 0;
 200 }
 201
 202 /*!
 203  * Find a bunch of contiguous entries; at least nblobs in a row.
 204  *
 205  * \param dir       pointer to the directory object
 206  * \param nblobs    number of contiguous entries we need
 207  *
 208  * \return element number (directory entry) of the requested space
 209  * \retval -1           failed to find 'nblobs' contiguous entries
 210  */
 211 static int
 212 FindBlobs(dir_file_t dir, int nblobs)
 213 {
 214     int i, j, k;
 215     int failed = 0;
 216     struct DirBuffer headerbuf, pagebuf;
 217     struct DirHeader *dhp;
 218     struct PageHeader *pp;
 219     int pgcount;
 220     int code;
 221
 222     /* read the dir header in first. */
 223     if (DRead(dir, 0, &headerbuf) != 0)
 224         return -1;
 225     dhp = (struct DirHeader *)headerbuf.data;
 226
 227     for (i = 0; i < BIGMAXPAGES; i++) {
 228         if (i >= MAXPAGES || dhp->alloMap[i] >= nblobs) {
 229             /* if page could contain enough entries */
 230             /* If there are EPP free entries, then the page is not even allocated. */
 231             if (i >= MAXPAGES) {
 232                 /* this pages exists past the end of the old-style dir */
 233                 pgcount = ntohs(dhp->header.pgcount);
 234                 if (pgcount == 0) {
 235                     pgcount = MAXPAGES;
 236                     dhp->header.pgcount = htons(pgcount);
 237                 }
 238                 if (i > pgcount - 1) {
 239                     /* this page is bigger than last allocated page */
 240                     code = AddPage(dir, i);
 241                     if (code)
 242                         break;
 243                     dhp->header.pgcount = htons(i + 1);
 244                 }
 245             } else if (dhp->alloMap[i] == EPP) {
 246                 /* Add the page to the directory. */
 247                 code = AddPage(dir, i);
 248                 if (code)
 249                     break;
 250                 dhp->alloMap[i] = EPP - 1;
 251                 dhp->header.pgcount = htons(i + 1);
 252             }
 253
 254             /* read the page in. */
 255             if (DRead(dir, i, &pagebuf) != 0) {
 256                 break;
 257             }
 258             pp = (struct PageHeader *)pagebuf.data;
 259             for (j = 0; j <= EPP - nblobs; j++) {
 260                 failed = 0;
 261                 for (k = 0; k < nblobs; k++)
 262                     if ((pp->freebitmap[(j + k) >> 3] >> ((j + k) & 7)) & 1) {
 263                         failed = 1;
 264                         break;
 265                     }
 266                 if (!failed)
 267                     break;
 268                 failed = 1;
 269             }
 270             if (!failed) {
 271                 /* Here we have the first index in j.  We update the allocation maps
 272                  * and free up any resources we've got allocated. */
 273                 if (i < MAXPAGES)
 274                     dhp->alloMap[i] -= nblobs;
 275                 DRelease(&headerbuf, 1);
 276                 for (k = 0; k < nblobs; k++)
 277                     pp->freebitmap[(j + k) >> 3] |= 1 << ((j + k) & 7);
 278                 DRelease(&pagebuf, 1);
 279                 return j + i * EPP;
 280             }
 281             DRelease(&pagebuf, 0);      /* This dir page is unchanged. */
 282         }
 283     }
 284     /* If we make it here, the directory is full, or we encountered an I/O error. */
 285     DRelease(&headerbuf, 1);
 286     return -1;
 287 }
 288
 289 /*!
 290  * Add a page to a directory object.
 291  *
 292  * \param dir       pointer to the directory object
 293  * \param pageno    page number to add
 294  *
 295  * \retval 0        succcess
 296  * \retval non-zero return error from DNew
 297  */
 298 static int
 299 AddPage(dir_file_t dir, int pageno)
 300 {                               /* Add a page to a directory. */
 301     int i;
 302     struct PageHeader *pp;
 303     struct DirBuffer pagebuf;
 304     int code;
 305
 306     /* Get a new buffer labelled dir,pageno */
 307     code = DNew(dir, pageno, &pagebuf);
 308     if (code)
 309         return code;
 310     pp = (struct PageHeader *)pagebuf.data;
 311
 312     pp->tag = htons(1234);
 313     if (pageno > 0)
 314         pp->pgcount = 0;
 315     pp->freecount = EPP - 1;    /* The first dude is already allocated */
 316     pp->freebitmap[0] = 0x01;
 317     for (i = 1; i < EPP / 8; i++)       /* It's a constant */
 318         pp->freebitmap[i] = 0;
 319     DRelease(&pagebuf, 1);
 320     return 0;
 321 }
 322
 323 /* Free a whole bunch of directory entries. */
 324
 325 static void
 326 FreeBlobs(dir_file_t dir, int firstblob, int nblobs)
 327 {
 328     int i;
 329     int page;
 330     struct DirBuffer headerbuf, pagehdbuf;
 331     struct DirHeader *dhp;
 332     struct PageHeader *pp;
 333     page = firstblob / EPP;
 334     firstblob -= EPP * page;    /* convert to page-relative entry */
 335
 336     if (DRead(dir, 0, &headerbuf) != 0)
 337         return;
 338     dhp = (struct DirHeader *)headerbuf.data;
 339
 340     if (page < MAXPAGES)
 341         dhp->alloMap[page] += nblobs;
 342
 343     DRelease(&headerbuf, 1);
 344
 345     if (DRead(dir, page, &pagehdbuf) != 0)
 346         return;
 347     pp = (struct PageHeader *)pagehdbuf.data;
 348
 349     for (i = 0; i < nblobs; i++)
 350         pp->freebitmap[(firstblob + i) >> 3] &= ~(1 << ((firstblob + i) & 7));
 351
 352     DRelease(&pagehdbuf, 1);
 353 }
 354
 355 /*!
 356  * Format an empty directory properly.  Note that the first 13 entries in a
 357  * directory header page are allocated, 1 to the page header, 4 to the
 358  * allocation map and 8 to the hash table.
 359  *
 360  * \param dir       pointer to the directory object
 361  * \param me        fid (vnode+uniq) for new dir
 362  * \param parent    fid (vnode+uniq) for parent dir
 363  *
 364  * \retval 0        success
 365  * \retval nonzero  error code
 366  */
 367 int
 368 afs_dir_MakeDir(dir_file_t dir, afs_int32 * me, afs_int32 * parent)
 369 {
 370     int i;
 371     struct DirBuffer buffer;
 372     struct DirHeader *dhp;
 373     int code;
 374
 375     code = DNew(dir, 0, &buffer);
 376     if (code)
 377         return code;
 378     dhp = (struct DirHeader *)buffer.data;
 379
 380     dhp->header.pgcount = htons(1);
 381     dhp->header.tag = htons(1234);
 382     dhp->header.freecount = (EPP - DHE - 1);
 383     dhp->header.freebitmap[0] = 0xff;
 384     dhp->header.freebitmap[1] = 0x1f;
 385     for (i = 2; i < EPP / 8; i++)
 386         dhp->header.freebitmap[i] = 0;
 387     dhp->alloMap[0] = (EPP - DHE - 1);
 388     for (i = 1; i < MAXPAGES; i++)
 389         dhp->alloMap[i] = EPP;
 390     for (i = 0; i < NHASHENT; i++)
 391         dhp->hashTable[i] = 0;
 392     DRelease(&buffer, 1);
 393     code = afs_dir_Create(dir, ".", me);
 394     if (code)
 395         return code;
 396     code = afs_dir_Create(dir, "..", parent);
 397     if (code)
 398         return code;
 399     return 0;
 400 }
 401
 402 /* Look up a file name in directory. */
 403
 404 int
 405 afs_dir_Lookup(dir_file_t dir, char *entry, void *voidfid)
 406 {
 407     afs_int32 *fid = (afs_int32 *) voidfid;
 408     struct DirBuffer firstbuf, prevbuf;
 409     struct DirEntry *firstitem;
 410     int code;
 411
 412     code = FindItem(dir, entry, &prevbuf, &firstbuf);
 413     if (code) {
 414         return code;
 415     }
 416     DRelease(&prevbuf, 0);
 417     firstitem = (struct DirEntry *)firstbuf.data;
 418
 419     fid[1] = ntohl(firstitem->fid.vnode);
 420     fid[2] = ntohl(firstitem->fid.vunique);
 421     DRelease(&firstbuf, 0);
 422     return 0;
 423 }
 424
 425 /* Look up a file name in directory. */
 426
 427 int
 428 afs_dir_LookupOffset(dir_file_t dir, char *entry, void *voidfid,
 429                      long *offsetp)
 430 {
 431     afs_int32 *fid = (afs_int32 *) voidfid;
 432     struct DirBuffer firstbuf, prevbuf;
 433     struct DirEntry *firstitem;
 434     int code;
 435
 436     code = FindItem(dir, entry, &prevbuf, &firstbuf);
 437     if (code) {
 438         return code;
 439     }
 440     DRelease(&prevbuf, 0);
 441     firstitem = (struct DirEntry *)firstbuf.data;
 442
 443     fid[1] = ntohl(firstitem->fid.vnode);
 444     fid[2] = ntohl(firstitem->fid.vunique);
 445     if (offsetp)
 446         *offsetp = DVOffset(&firstbuf);
 447     DRelease(&firstbuf, 0);
 448     return 0;
 449 }
 450
 451 /*
 452  * Enumerate the contents of a directory. Break when hook function
 453  * returns non 0.
 454  */
 455
 456 int
 457 afs_dir_EnumerateDir(dir_file_t dir, int (*proc) (void *, char *name,
 458                                                   afs_int32 vnode,
 459                                                   afs_int32 unique),
 460                      void *hook)
 461 {
 462     int i;
 463     int num;
 464     struct DirBuffer headerbuf, entrybuf;
 465     struct DirHeader *dhp;
 466     struct DirEntry *ep;
 467     int code = 0;
 468     int elements;
 469
 470     if (DRead(dir, 0, &headerbuf) != 0)
 471         return EIO;
 472     dhp = (struct DirHeader *)headerbuf.data;
 473
 474     for (i = 0; i < NHASHENT; i++) {
 475         /* For each hash chain, enumerate everyone on the list. */
 476         num = ntohs(dhp->hashTable[i]);
 477         elements = 0;
 478         while (num != 0 && elements < BIGMAXPAGES * EPP) {
 479             elements++;
 480
 481             /* Walk down the hash table list. */
 482             code = afs_dir_GetVerifiedBlob(dir, num, &entrybuf);
 483             if (code)
 484                 goto out;
 485
 486             ep = (struct DirEntry *)entrybuf.data;
 487             if (!ep) {
 488                 DRelease(&entrybuf, 0);
 489                 break;
 490             }
 491
 492             num = ntohs(ep->next);
 493             code = (*proc) (hook, ep->name, ntohl(ep->fid.vnode),
 494                             ntohl(ep->fid.vunique));
 495             DRelease(&entrybuf, 0);
 496             if (code)
 497                 goto out;
 498         }
 499     }
 500
 501 out:
 502     DRelease(&headerbuf, 0);
 503     return 0;
 504 }
 505
 506 int
 507 afs_dir_IsEmpty(dir_file_t dir)
 508 {
 509     /* Enumerate the contents of a directory. */
 510     int i;
 511     int num;
 512     struct DirBuffer headerbuf, entrybuf;
 513     struct DirHeader *dhp;
 514     struct DirEntry *ep;
 515     int elements;
 516
 517     if (DRead(dir, 0, &headerbuf) != 0)
 518         return 0;
 519     dhp = (struct DirHeader *)headerbuf.data;
 520
 521     for (i = 0; i < NHASHENT; i++) {
 522         /* For each hash chain, enumerate everyone on the list. */
 523         num = ntohs(dhp->hashTable[i]);
 524         elements = 0;
 525         while (num != 0 && elements < BIGMAXPAGES * EPP) {
 526             elements++;
 527             /* Walk down the hash table list. */
 528             if (afs_dir_GetVerifiedBlob(dir, num, &entrybuf) != 0)
 529                 break;
 530             ep = (struct DirEntry *)entrybuf.data;
 531             if (strcmp(ep->name, "..") && strcmp(ep->name, ".")) {
 532                 DRelease(&entrybuf, 0);
 533                 DRelease(&headerbuf, 0);
 534                 return 1;
 535             }
 536             num = ntohs(ep->next);
 537             DRelease(&entrybuf, 0);
 538         }
 539     }
 540     DRelease(&headerbuf, 0);
 541     return 0;
 542 }
 543
 544 /* Return a pointer to an entry, given its number. Also return the maximum
 545  * size of the entry, which is determined by its position within the directory
 546  * page.
 547  *
 548  * If physerr is supplied by caller, it will be set to:
 549  *      0       for logical errors
 550  *      errno   for physical errors
 551  */
 552 static int
 553 GetBlobWithLimit(dir_file_t dir, afs_int32 blobno,
 554                 struct DirBuffer *buffer, afs_size_t *maxlen, int *physerr)
 555 {
 556     afs_size_t pos;
 557     int code;
 558
 559     *maxlen = 0;
 560     memset(buffer, 0, sizeof(struct DirBuffer));
 561
 562     code = DReadWithErrno(dir, blobno >> LEPP, buffer, physerr);
 563     if (code)
 564         return code;
 565
 566     pos = 32 * (blobno & (EPP - 1));
 567
 568     *maxlen = AFS_PAGESIZE - pos - 1;
 569
 570     buffer->data = (void *)(((char *)buffer->data) + pos);
 571
 572     return 0;
 573 }
 574
 575 /*
 576  * Given an entry's number, return a pointer to that entry.
 577  * If physerr is supplied by caller, it will be set to:
 578  *      0       for logical errors
 579  *      errno   for physical errors
 580  */
 581 int
 582 afs_dir_GetBlobWithErrno(dir_file_t dir, afs_int32 blobno, struct DirBuffer *buffer,
 583                         int *physerr)
 584 {
 585     afs_size_t maxlen = 0;
 586     return GetBlobWithLimit(dir, blobno, buffer, &maxlen, physerr);
 587 }
 588
 589 /* Given an entries number, return a pointer to that entry */
 590 int
 591 afs_dir_GetBlob(dir_file_t dir, afs_int32 blobno, struct DirBuffer *buffer)
 592 {
 593     afs_size_t maxlen = 0;
 594     return GetBlobWithLimit(dir, blobno, buffer, &maxlen, NULL);
 595 }
 596
 597 /* Return an entry, having verified that the name held within the entry
 598  * doesn't overflow off the end of the directory page it is contained
 599  * within
 600  */
 601
 602 int
 603 afs_dir_GetVerifiedBlob(dir_file_t file, afs_int32 blobno,
 604                         struct DirBuffer *outbuf)
 605 {
 606     struct DirEntry *dir;
 607     struct DirBuffer buffer;
 608     afs_size_t maxlen;
 609     int code;
 610     char *cp;
 611
 612     code = GetBlobWithLimit(file, blobno, &buffer, &maxlen, NULL);
 613     if (code)
 614         return code;
 615
 616     dir = (struct DirEntry *)buffer.data;
 617
 618     /* A blob is only valid if the name within it is NULL terminated before
 619      * the end of the blob's containing page */
 620     for (cp = dir->name; *cp != '\0' && cp < ((char *)dir) + maxlen; cp++);
 621
 622     if (*cp != '\0') {
 623         DRelease(&buffer, 0);
 624         return EIO;
 625     }
 626
 627     *outbuf = buffer;
 628     return 0;
 629 }
 630
 631 int
 632 afs_dir_DirHash(char *string)
 633 {
 634     /* Hash a string to a number between 0 and NHASHENT. */
 635     unsigned char tc;
 636     unsigned int hval;
 637     int tval;
 638     hval = 0;
 639     while ((tc = (*string++))) {
 640         hval *= 173;
 641         hval += tc;
 642     }
 643     tval = hval & (NHASHENT - 1);
 644     if (tval == 0)
 645         return tval;
 646     else if (hval >= 1u<<31)
 647         tval = NHASHENT - tval;
 648     return tval;
 649 }
 650
 651
 652 /* Find a directory entry, given its name.  This entry returns a pointer
 653  * to a locked buffer, and a pointer to a locked buffer (in previtem)
 654  * referencing the found item (to aid the delete code).  If no entry is
 655  * found, however, no items are left locked, and a null pointer is
 656  * returned instead. */
 657
 658 static int
 659 FindItem(dir_file_t dir, char *ename, struct DirBuffer *prevbuf,
 660          struct DirBuffer *itembuf )
 661 {
 662     int i, code;
 663     struct DirBuffer curr, prev;
 664     struct DirHeader *dhp;
 665     struct DirEntry *tp;
 666     int elements;
 667
 668     memset(prevbuf, 0, sizeof(struct DirBuffer));
 669     memset(itembuf, 0, sizeof(struct DirBuffer));
 670
 671     code = DRead(dir, 0, &prev);
 672     if (code)
 673         return code;
 674     dhp = (struct DirHeader *)prev.data;
 675
 676     i = afs_dir_DirHash(ename);
 677     if (dhp->hashTable[i] == 0) {
 678         /* no such entry */
 679         code = ENOENT;
 680         goto out;
 681     }
 682
 683     code = afs_dir_GetVerifiedBlob(dir,
 684                                    (u_short) ntohs(dhp->hashTable[i]),
 685                                    &curr);
 686     if (code) {
 687         goto out;
 688     }
 689
 690     prev.data = &(dhp->hashTable[i]);
 691     elements = 0;
 692     /* Detect circular hash chains. Absolute max size of a directory */
 693     while (elements < BIGMAXPAGES * EPP) {
 694         elements++;
 695
 696         /* Look at each entry on the hash chain */
 697         tp = (struct DirEntry *)curr.data;
 698         if (!strcmp(ename, tp->name)) {
 699             /* Found it! */
 700             *prevbuf = prev;
 701             *itembuf = curr;
 702             return 0;
 703         }
 704
 705         DRelease(&prev, 0);
 706
 707         prev = curr;
 708         prev.data = &(tp->next);
 709
 710         if (tp->next == 0) {
 711             /* The end of the line */
 712             code = ENOENT;
 713             goto out;
 714         }
 715
 716         code = afs_dir_GetVerifiedBlob(dir, (u_short) ntohs(tp->next),
 717                                        &curr);
 718         if (code)
 719             goto out;
 720     }
 721
 722     /* If we've reached here, we've hit our loop limit. Something is weird with
 723      * the directory; maybe a circular hash chain? */
 724     code = EIO;
 725
 726 out:
 727     DRelease(&prev, 0);
 728     return code;
 729 }
 730
 731 static int
 732 FindFid (void *dir, afs_uint32 vnode, afs_uint32 unique,
 733          struct DirBuffer *itembuf)
 734 {
 735     /* Find a directory entry, given the vnode and uniquifier of a object.
 736      * This entry returns a pointer to a locked buffer.  If no entry is found,
 737      * however, no items are left locked, and a null pointer is returned
 738      * instead.
 739      */
 740     int i, code;
 741     unsigned short next;
 742     struct DirBuffer curr, header;
 743     struct DirHeader *dhp;
 744     struct DirEntry *tp;
 745     int elements;
 746
 747     memset(itembuf, 0, sizeof(struct DirBuffer));
 748
 749     code = DRead(dir, 0, &header);
 750     if (code)
 751         return code;
 752     dhp = (struct DirHeader *)header.data;
 753
 754     for (i=0; i<NHASHENT; i++) {
 755         if (dhp->hashTable[i] != 0) {
 756             code = afs_dir_GetVerifiedBlob(dir,
 757                                            (u_short)ntohs(dhp->hashTable[i]),
 758                                            &curr);
 759             if (code) {
 760                 DRelease(&header, 0);
 761                 return code;
 762             }
 763             elements = 0;
 764             while(curr.data != NULL && elements < BIGMAXPAGES * EPP) {
 765                 elements++;
 766                 tp = (struct DirEntry *)curr.data;
 767
 768                 if (vnode == ntohl(tp->fid.vnode)
 769                     && unique == ntohl(tp->fid.vunique)) {
 770                     DRelease(&header, 0);
 771                     *itembuf = curr;
 772                     return 0;
 773                 }
 774
 775                 next = tp->next;
 776                 DRelease(&curr, 0);
 777
 778                 if (next == 0)
 779                     break;
 780
 781                 code = afs_dir_GetVerifiedBlob(dir, (u_short)ntohs(next),
 782                                                &curr);
 783                 if (code) {
 784                     DRelease(&header, 0);
 785                     return code;
 786                 }
 787             }
 788         }
 789     }
 790     DRelease(&header, 0);
 791     return ENOENT;
 792 }
 793
 794 int
 795 afs_dir_InverseLookup(void *dir, afs_uint32 vnode, afs_uint32 unique,
 796                       char *name, afs_uint32 length)
 797 {
 798     /* Look for the name pointing to given vnode and unique in a directory */
 799     struct DirBuffer entrybuf;
 800     struct DirEntry *entry;
 801     int code = 0;
 802
 803     code = FindFid(dir, vnode, unique, &entrybuf);
 804     if (code) {
 805         return code;
 806     }
 807     entry = (struct DirEntry *)entrybuf.data;
 808
 809     if (strlen(entry->name) >= length)
 810         code = E2BIG;
 811     else
 812         strcpy(name, entry->name);
 813     DRelease(&entrybuf, 0);
 814     return code;
 815 }
 816
 817 /*!
 818  * Change an entry fid.
 819  *
 820  * \param dir
 821  * \param entry The entry name.
 822  * \param old_fid The old find in MKFid format (host order).
 823  * It can be omitted if you don't need a safety check...
 824  * \param new_fid The new find in MKFid format (host order).
 825  */
 826 int
 827 afs_dir_ChangeFid(dir_file_t dir, char *entry, afs_uint32 *old_fid,
 828                   afs_uint32 *new_fid)
 829 {
 830     struct DirBuffer prevbuf, entrybuf;
 831     struct DirEntry *firstitem;
 832     struct MKFid *fid_old = (struct MKFid *) old_fid;
 833     struct MKFid *fid_new = (struct MKFid *) new_fid;
 834     int code;
 835
 836     /* Find entry. */
 837     code = FindItem(dir, entry, &prevbuf, &entrybuf);
 838     if (code) {
 839         return code;
 840     }
 841     firstitem = (struct DirEntry *)entrybuf.data;
 842     DRelease(&prevbuf, 1);
 843
 844     /* Replace fid. */
 845     if (!old_fid ||
 846         ((htonl(fid_old->vnode) == firstitem->fid.vnode) &&
 847         (htonl(fid_old->vunique) == firstitem->fid.vunique))) {
 848
 849         firstitem->fid.vnode = htonl(fid_new->vnode);
 850         firstitem->fid.vunique = htonl(fid_new->vunique);
 851     }
 852
 853     DRelease(&entrybuf, 1);
 854
 855     return 0;
 856 }