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