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 #  include "h/param.h"
  17 #  ifdef        AFS_AUX_ENV
  18 #   include "h/mmu.h"
  19 #   include "h/seg.h"
  20 #   include "h/sysmacros.h"
  21 #   include "h/signal.h"
  22 #   include "h/errno.h"
  23 #  endif
  24 #  include "h/time.h"
  25 #  if defined(AFS_AIX_ENV) || defined(AFS_SGI_ENV) || defined(AFS_SUN5_ENV) || defined(AFS_LINUX20_ENV)
  26 #   include "h/errno.h"
  27 #  else
  28 #   if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX20_ENV)
  29 #    include "h/kernel.h"
  30 #   endif
  31 #  endif
  32 #  if   defined(AFS_SUN56_ENV) || defined(AFS_HPUX_ENV) || defined(AFS_FBSD_ENV) || defined(AFS_DARWIN80_ENV)
  33 #   include "afs/sysincludes.h"
  34 #  endif
  35 #  if !defined(AFS_SGI64_ENV) && !defined(AFS_DARWIN_ENV) && !defined(AFS_OBSD48_ENV)
  36 #   include "h/user.h"
  37 #  endif /* AFS_SGI64_ENV */
  38 #  include "h/uio.h"
  39 #  ifdef        AFS_OSF_ENV
  40 #   include <sys/mount.h>
  41 #   include <sys/vnode.h>
  42 #   include <ufs/inode.h>
  43 #  endif
  44 #  if !defined(AFS_SUN5_ENV) && !defined(AFS_LINUX20_ENV) && !defined(AFS_HPUX110_ENV)
  45 #   include "h/mbuf.h"
  46 #  endif
  47 #  ifndef AFS_LINUX20_ENV
  48 #   include "netinet/in.h"
  49 #  endif
  50
  51 /* afs_buffer.c */
  52 /* These are needed because afs_prototypes.h is not included here */
  53 struct dcache;
  54 extern void *DRead(struct dcache *adc, int page);
  55 extern void *DNew(struct dcache *adc, int page);
  56
  57 # else /* !defined(UKERNEL) */
  58 #  include "afs/stds.h"
  59 #  include "afs/sysincludes.h"
  60
  61 /* afs_buffer.c */
  62 /* These are needed because afs_prototypes.h is not included here */
  63 extern void *DRead(afs_int32 *fid, int page);
  64 extern void *DNew(afs_int32 *fid, int page);
  65
  66 # endif /* !defined(UKERNEL) */
  67 # include "afs/afs_osi.h"
  68
  69 # include "afs/dir.h"
  70
  71 # ifdef AFS_LINUX20_ENV
  72 #  include "h/string.h"
  73 # endif
  74
  75 /* generic renaming */
  76 # define        NameBlobs       afs_dir_NameBlobs
  77 # define        GetBlob         afs_dir_GetBlob
  78 # define        Create          afs_dir_Create
  79 # define        Length          afs_dir_Length
  80 # define        Delete          afs_dir_Delete
  81 # define        MakeDir         afs_dir_MakeDir
  82 # define        Lookup          afs_dir_Lookup
  83 # define        LookupOffset    afs_dir_LookupOffset
  84 # define        EnumerateDir    afs_dir_EnumerateDir
  85 # define        IsEmpty         afs_dir_IsEmpty
  86 # define InverseLookup   afs_dir_InverseLookup
  87 # define ChangeFid      afs_dir_ChangeFid
  88
  89 #else /* KERNEL */
  90
  91 # include <roken.h>
  92 # include "dir.h"
  93 #endif /* KERNEL */
  94
  95 afs_int32 DErrno;
  96
  97 /* Local static prototypes */
  98 static struct DirEntry *FindItem(void *dir, char *ename,
  99                                  unsigned short **previtem);
 100
 101
 102 /* Find out how many entries are required to store a name. */
 103 int
 104 NameBlobs(char *name)
 105 {
 106     int i;
 107     i = strlen(name) + 1;
 108     return 1 + ((i + 15) >> 5);
 109 }
 110
 111 /* Create an entry in a file.  Dir is a file representation, while entry is
 112  * a string name. */
 113 int
 114 Create(void *dir, char *entry, void *voidfid)
 115 {
 116     afs_int32 *vfid = (afs_int32 *) voidfid;
 117     int blobs, firstelt;
 118     int i;
 119     struct DirEntry *ep;
 120     unsigned short *pp = NULL;
 121     struct DirHeader *dhp;
 122
 123     /* check name quality */
 124     if (*entry == 0)
 125         return EINVAL;
 126     /* First check if file already exists. */
 127     ep = FindItem(dir, entry, &pp);
 128     if (ep) {
 129         DRelease(ep, 0);
 130         DRelease(pp, 0);
 131         return EEXIST;
 132     }
 133     blobs = NameBlobs(entry);   /* number of entries required */
 134     firstelt = FindBlobs(dir, blobs);
 135     if (firstelt < 0)
 136         return EFBIG;           /* directory is full */
 137     /* First, we fill in the directory entry. */
 138     ep = GetBlob(dir, firstelt);
 139     if (ep == 0)
 140         return EIO;
 141     ep->flag = FFIRST;
 142     ep->fid.vnode = htonl(vfid[1]);
 143     ep->fid.vunique = htonl(vfid[2]);
 144     strcpy(ep->name, entry);
 145     /* Now we just have to thread it on the hash table list. */
 146     dhp = (struct DirHeader *)DRead(dir, 0);
 147     if (!dhp) {
 148         DRelease(ep, 1);
 149         return EIO;
 150     }
 151     i = DirHash(entry);
 152     ep->next = dhp->hashTable[i];
 153     dhp->hashTable[i] = htons(firstelt);
 154     DRelease(dhp, 1);
 155     DRelease(ep, 1);
 156     return 0;
 157 }
 158
 159 int
 160 Length(void *dir)
 161 {
 162     int i, ctr;
 163     struct DirHeader *dhp;
 164     dhp = (struct DirHeader *)DRead(dir, 0);
 165     if (!dhp)
 166         return 0;
 167     if (dhp->header.pgcount != 0)
 168         ctr = ntohs(dhp->header.pgcount);
 169     else {
 170         /* old style, count the pages */
 171         ctr = 0;
 172         for (i = 0; i < MAXPAGES; i++)
 173             if (dhp->alloMap[i] != EPP)
 174                 ctr++;
 175     }
 176     DRelease(dhp, 0);
 177     return ctr * AFS_PAGESIZE;
 178 }
 179
 180 int
 181 Delete(void *dir, char *entry)
 182 {
 183     /* Delete an entry from a directory, including update of all free entry descriptors. */
 184     int nitems, index;
 185     struct DirEntry *firstitem;
 186     unsigned short *previtem;
 187     firstitem = FindItem(dir, entry, &previtem);
 188     if (firstitem == 0)
 189         return ENOENT;
 190     *previtem = firstitem->next;
 191     DRelease(previtem, 1);
 192     index = DVOffset(firstitem) / 32;
 193     nitems = NameBlobs(firstitem->name);
 194     DRelease(firstitem, 0);
 195     FreeBlobs(dir, index, nitems);
 196     return 0;
 197 }
 198
 199 int
 200 FindBlobs(void *dir, int nblobs)
 201 {
 202     /* Find a bunch of contiguous entries; at least nblobs in a row. */
 203     int i, j, k;
 204     int failed = 0;
 205     struct DirHeader *dhp;
 206     struct PageHeader *pp;
 207     int pgcount;
 208
 209     dhp = (struct DirHeader *)DRead(dir, 0);    /* read the dir header in first. */
 210     if (!dhp)
 211         return -1;
 212     for (i = 0; i < BIGMAXPAGES; i++) {
 213         if (i >= MAXPAGES || dhp->alloMap[i] >= nblobs) {
 214             /* if page could contain enough entries */
 215             /* If there are EPP free entries, then the page is not even allocated. */
 216             if (i >= MAXPAGES) {
 217                 /* this pages exists past the end of the old-style dir */
 218                 pgcount = ntohs(dhp->header.pgcount);
 219                 if (pgcount == 0) {
 220                     pgcount = MAXPAGES;
 221                     dhp->header.pgcount = htons(pgcount);
 222                 }
 223                 if (i > pgcount - 1) {
 224                     /* this page is bigger than last allocated page */
 225                     AddPage(dir, i);
 226                     dhp->header.pgcount = htons(i + 1);
 227                 }
 228             } else if (dhp->alloMap[i] == EPP) {
 229                 /* Add the page to the directory. */
 230                 AddPage(dir, i);
 231                 dhp->alloMap[i] = EPP - 1;
 232                 dhp->header.pgcount = htons(i + 1);
 233             }
 234             pp = (struct PageHeader *)DRead(dir, i);    /* read the page in. */
 235             if (!pp) {
 236                 DRelease(dhp, 1);
 237                 break;
 238             }
 239             for (j = 0; j <= EPP - nblobs; j++) {
 240                 failed = 0;
 241                 for (k = 0; k < nblobs; k++)
 242                     if ((pp->freebitmap[(j + k) >> 3] >> ((j + k) & 7)) & 1) {
 243                         failed = 1;
 244                         break;
 245                     }
 246                 if (!failed)
 247                     break;
 248                 failed = 1;
 249             }
 250             if (!failed) {
 251                 /* Here we have the first index in j.  We update the allocation maps
 252                  * and free up any resources we've got allocated. */
 253                 if (i < MAXPAGES)
 254                     dhp->alloMap[i] -= nblobs;
 255                 DRelease(dhp, 1);
 256                 for (k = 0; k < nblobs; k++)
 257                     pp->freebitmap[(j + k) >> 3] |= 1 << ((j + k) & 7);
 258                 DRelease(pp, 1);
 259                 return j + i * EPP;
 260             }
 261             DRelease(pp, 0);    /* This dir page is unchanged. */
 262         }
 263     }
 264     /* If we make it here, the directory is full. */
 265     DRelease(dhp, 1);
 266     return -1;
 267 }
 268
 269 void
 270 AddPage(void *dir, int pageno)
 271 {                               /* Add a page to a directory. */
 272     int i;
 273     struct PageHeader *pp;
 274
 275     pp = (struct PageHeader *)DNew(dir, pageno);        /* Get a new buffer labelled dir,pageno */
 276     pp->tag = htons(1234);
 277     if (pageno > 0)
 278         pp->pgcount = 0;
 279     pp->freecount = EPP - 1;    /* The first dude is already allocated */
 280     pp->freebitmap[0] = 0x01;
 281     for (i = 1; i < EPP / 8; i++)       /* It's a constant */
 282         pp->freebitmap[i] = 0;
 283     DRelease(pp, 1);
 284 }
 285
 286 /* Free a whole bunch of directory entries. */
 287
 288 void
 289 FreeBlobs(void *dir, int firstblob, int nblobs)
 290 {
 291     int i;
 292     int page;
 293     struct DirHeader *dhp;
 294     struct PageHeader *pp;
 295     page = firstblob / EPP;
 296     firstblob -= EPP * page;    /* convert to page-relative entry */
 297     dhp = (struct DirHeader *)DRead(dir, 0);
 298     if (!dhp)
 299         return;
 300     if (page < MAXPAGES)
 301         dhp->alloMap[page] += nblobs;
 302     DRelease(dhp, 1);
 303     pp = (struct PageHeader *)DRead(dir, page);
 304     if (pp)
 305         for (i = 0; i < nblobs; i++)
 306             pp->freebitmap[(firstblob + i) >> 3] &=
 307                 ~(1 << ((firstblob + i) & 7));
 308     DRelease(pp, 1);
 309 }
 310
 311 /*
 312  * Format an empty directory properly.  Note that the first 13 entries in a
 313  * directory header page are allocated, 1 to the page header, 4 to the
 314  * allocation map and 8 to the hash table.
 315  */
 316 int
 317 MakeDir(void *dir, afs_int32 * me, afs_int32 * parent)
 318 {
 319     int i;
 320     struct DirHeader *dhp;
 321     dhp = (struct DirHeader *)DNew(dir, 0);
 322     dhp->header.pgcount = htons(1);
 323     dhp->header.tag = htons(1234);
 324     dhp->header.freecount = (EPP - DHE - 1);
 325     dhp->header.freebitmap[0] = 0xff;
 326     dhp->header.freebitmap[1] = 0x1f;
 327     for (i = 2; i < EPP / 8; i++)
 328         dhp->header.freebitmap[i] = 0;
 329     dhp->alloMap[0] = (EPP - DHE - 1);
 330     for (i = 1; i < MAXPAGES; i++)
 331         dhp->alloMap[i] = EPP;
 332     for (i = 0; i < NHASHENT; i++)
 333         dhp->hashTable[i] = 0;
 334     DRelease(dhp, 1);
 335     Create(dir, ".", me);
 336     Create(dir, "..", parent);  /* Virtue is its own .. */
 337     return 0;
 338 }
 339
 340 /* Look up a file name in directory. */
 341
 342 int
 343 Lookup(void *dir, char *entry, void *voidfid)
 344 {
 345     afs_int32 *fid = (afs_int32 *) voidfid;
 346     struct DirEntry *firstitem;
 347     unsigned short *previtem;
 348
 349     firstitem = FindItem(dir, entry, &previtem);
 350     if (firstitem == 0)
 351         return ENOENT;
 352     DRelease(previtem, 0);
 353     fid[1] = ntohl(firstitem->fid.vnode);
 354     fid[2] = ntohl(firstitem->fid.vunique);
 355     DRelease(firstitem, 0);
 356     return 0;
 357 }
 358
 359 /* Look up a file name in directory. */
 360
 361 int
 362 LookupOffset(void *dir, char *entry, void *voidfid, long *offsetp)
 363 {
 364     afs_int32 *fid = (afs_int32 *) voidfid;
 365     struct DirEntry *firstitem;
 366     unsigned short *previtem;
 367
 368     firstitem = FindItem(dir, entry, &previtem);
 369     if (firstitem == 0)
 370         return ENOENT;
 371     DRelease(previtem, 0);
 372     fid[1] = ntohl(firstitem->fid.vnode);
 373     fid[2] = ntohl(firstitem->fid.vunique);
 374     if (offsetp)
 375         *offsetp = DVOffset(firstitem);
 376     DRelease(firstitem, 0);
 377     return 0;
 378 }
 379
 380 int
 381 EnumerateDir(void *dir, int (*hookproc) (void *dir, char *name,
 382                                          afs_int32 vnode, afs_int32 unique),
 383              void *hook)
 384 {
 385     /* Enumerate the contents of a directory.
 386      * Break when hook function returns non 0.
 387      */
 388     int i;
 389     int num;
 390     struct DirHeader *dhp;
 391     struct DirEntry *ep;
 392     int code = 0;
 393
 394     dhp = (struct DirHeader *)DRead(dir, 0);
 395     if (!dhp)
 396         return EIO;             /* first page should be there */
 397
 398     for (i = 0; i < NHASHENT; i++) {
 399         /* For each hash chain, enumerate everyone on the list. */
 400         num = ntohs(dhp->hashTable[i]);
 401         while (num != 0) {
 402             /* Walk down the hash table list. */
 403             DErrno = 0;
 404             ep = GetBlob(dir, num);
 405             if (!ep) {
 406                 if (DErrno) {
 407                     /* we failed, return why */
 408                     DRelease(dhp, 0);
 409                     return DErrno;
 410                 }
 411                 break;
 412             }
 413
 414             num = ntohs(ep->next);
 415             code = (*hookproc) (hook, ep->name, ntohl(ep->fid.vnode),
 416                          ntohl(ep->fid.vunique));
 417             DRelease(ep, 0);
 418             if (code)
 419                 break;
 420         }
 421     }
 422     DRelease(dhp, 0);
 423     return 0;
 424 }
 425
 426 int
 427 IsEmpty(void *dir)
 428 {
 429     /* Enumerate the contents of a directory. */
 430     int i;
 431     int num;
 432     struct DirHeader *dhp;
 433     struct DirEntry *ep;
 434     dhp = (struct DirHeader *)DRead(dir, 0);
 435     if (!dhp)
 436         return 0;
 437     for (i = 0; i < NHASHENT; i++) {
 438         /* For each hash chain, enumerate everyone on the list. */
 439         num = ntohs(dhp->hashTable[i]);
 440         while (num != 0) {
 441             /* Walk down the hash table list. */
 442             ep = GetBlob(dir, num);
 443             if (!ep)
 444                 break;
 445             if (strcmp(ep->name, "..") && strcmp(ep->name, ".")) {
 446                 DRelease(ep, 0);
 447                 DRelease(dhp, 0);
 448                 return 1;
 449             }
 450             num = ntohs(ep->next);
 451             DRelease(ep, 0);
 452         }
 453     }
 454     DRelease(dhp, 0);
 455     return 0;
 456 }
 457
 458 struct DirEntry *
 459 GetBlob(void *dir, afs_int32 blobno)
 460 {
 461     /* Return a pointer to an entry, given its number. */
 462     struct DirEntry *ep;
 463     ep = DRead(dir, blobno >> LEPP);
 464     if (!ep)
 465         return 0;
 466     return (struct DirEntry *)(((long)ep) + 32 * (blobno & (EPP - 1)));
 467 }
 468
 469 int
 470 DirHash(char *string)
 471 {
 472     /* Hash a string to a number between 0 and NHASHENT. */
 473     unsigned char tc;
 474     unsigned int hval;
 475     int tval;
 476     hval = 0;
 477     while ((tc = (*string++))) {
 478         hval *= 173;
 479         hval += tc;
 480     }
 481     tval = hval & (NHASHENT - 1);
 482     if (tval == 0)
 483         return tval;
 484     else if (hval >= 1<<31)
 485         tval = NHASHENT - tval;
 486     return tval;
 487 }
 488
 489
 490 /* Find a directory entry, given its name.  This entry returns a pointer
 491  * to a locked buffer, and a pointer to a locked buffer (in previtem)
 492  * referencing the found item (to aid the delete code).  If no entry is
 493  * found, however, no items are left locked, and a null pointer is
 494  * returned instead. */
 495
 496 static struct DirEntry *
 497 FindItem(void *dir, char *ename, unsigned short **previtem)
 498 {
 499     int i;
 500     struct DirHeader *dhp;
 501     unsigned short *lp;
 502     struct DirEntry *tp;
 503     i = DirHash(ename);
 504     dhp = (struct DirHeader *)DRead(dir, 0);
 505     if (!dhp)
 506         return 0;
 507     if (dhp->hashTable[i] == 0) {
 508         /* no such entry */
 509         DRelease(dhp, 0);
 510         return 0;
 511     }
 512     tp = GetBlob(dir, (u_short) ntohs(dhp->hashTable[i]));
 513     if (!tp) {
 514         DRelease(dhp, 0);
 515         return 0;
 516     }
 517     lp = &(dhp->hashTable[i]);
 518     while (1) {
 519         /* Look at each hash conflict entry. */
 520         if (!strcmp(ename, tp->name)) {
 521             /* Found our entry. */
 522             *previtem = lp;
 523             return tp;
 524         }
 525         DRelease(lp, 0);
 526         lp = &(tp->next);
 527         if (tp->next == 0) {
 528             /* The end of the line */
 529             DRelease(lp, 0);    /* Release all locks. */
 530             return 0;
 531         }
 532         tp = GetBlob(dir, (u_short) ntohs(tp->next));
 533         if (!tp) {
 534             DRelease(lp, 0);
 535             return 0;
 536         }
 537     }
 538 }
 539
 540 static struct DirEntry *
 541 FindFid (void *dir, afs_uint32 vnode, afs_uint32 unique)
 542 {
 543     /* Find a directory entry, given the vnode and uniquifier of a object.
 544      * This entry returns a pointer to a locked buffer.  If no entry is found,
 545      * however, no items are left locked, and a null pointer is returned
 546      * instead.
 547      */
 548     int i;
 549     struct DirHeader *dhp;
 550     unsigned short *lp;
 551     struct DirEntry *tp;
 552     dhp = (struct DirHeader *) DRead(dir,0);
 553     if (!dhp) return 0;
 554     for (i=0; i<NHASHENT; i++) {
 555         if (dhp->hashTable[i] != 0) {
 556             tp = GetBlob(dir,(u_short)ntohs(dhp->hashTable[i]));
 557             if (!tp) { /* should not happen */
 558                 DRelease(dhp, 0);
 559                 return 0;
 560             }
 561             while(tp) {
 562                 if (vnode == ntohl(tp->fid.vnode)
 563                     && unique == ntohl(tp->fid.vunique)) {
 564                     DRelease(dhp, 0);
 565                     return tp;
 566                 }
 567                 lp = &(tp->next);
 568                 if (tp->next == 0)
 569                     break;
 570                 tp = GetBlob(dir,(u_short)ntohs(tp->next));
 571                 DRelease(lp, 0);
 572             }
 573             DRelease(lp, 0);
 574         }
 575     }
 576     DRelease(dhp, 0);
 577     return NULL;
 578 }
 579
 580 int
 581 InverseLookup (void *dir, afs_uint32 vnode, afs_uint32 unique, char *name,
 582                afs_uint32 length)
 583 {
 584     /* Look for the name pointing to given vnode and unique in a directory */
 585     struct DirEntry *entry;
 586     int code = 0;
 587
 588     entry = FindFid(dir, vnode, unique);
 589     if (!entry)
 590         return ENOENT;
 591     if (strlen(entry->name) >= length)
 592         code = E2BIG;
 593     else
 594         strcpy(name, entry->name);
 595     DRelease(entry, 0);
 596     return code;
 597 }
 598
 599 /*!
 600  * Change an entry fid.
 601  *
 602  * \param dir
 603  * \param entry The entry name.
 604  * \param old_fid The old find in MKFid format (host order).
 605  * It can be omitted if you don't need a safety check...
 606  * \param new_fid The new find in MKFid format (host order).
 607  */
 608 int ChangeFid(void *dir,
 609                 char *entry,
 610                 afs_uint32 *old_fid,
 611                 afs_uint32 *new_fid)
 612 {
 613     struct DirEntry *firstitem;
 614     unsigned short *previtem;
 615     struct MKFid *fid_old = (struct MKFid *) old_fid;
 616     struct MKFid *fid_new = (struct MKFid *) new_fid;
 617
 618     /* Find entry. */
 619     firstitem = FindItem(dir, entry, &previtem);
 620     if (firstitem == 0) {
 621         return ENOENT;
 622     }
 623     DRelease(previtem, 1);
 624     /* Replace fid. */
 625     if (!old_fid ||
 626         ((htonl(fid_old->vnode) == firstitem->fid.vnode) &&
 627         (htonl(fid_old->vunique) == firstitem->fid.vunique))) {
 628
 629         firstitem->fid.vnode = htonl(fid_new->vnode);
 630         firstitem->fid.vunique = htonl(fid_new->vunique);
 631     }
 632
 633     DRelease(firstitem, 1);
 634
 635     return 0;
 636 }