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