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