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();
  57 extern void *DNew();
  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();
  66 extern void *DNew();
  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
  89 #if defined(AFS_DISCON_ENV)
  90 #define ChangeFid       afs_dir_ChangeFid
  91 #endif
  92
  93 #else /* KERNEL */
  94
  95 # ifdef HAVE_UNISTD_H
  96 #  include <unistd.h>
  97 # endif
  98 # include <sys/types.h>
  99 # include <errno.h>
 100 # include "dir.h"
 101 #ifdef AFS_NT40_ENV
 102 #include <winsock2.h>
 103 #else
 104 #include <netinet/in.h>
 105 #endif
 106
 107 #include <string.h>
 108 #endif /* KERNEL */
 109
 110 afs_int32 DErrno;
 111
 112 /* Local static prototypes */
 113 static struct DirEntry *FindItem(void *dir, char *ename,
 114                                  unsigned short **previtem);
 115
 116
 117 int
 118 NameBlobs(char *name)
 119 {                               /* Find out how many entries are required to store a name. */
 120     register int i;
 121     i = strlen(name) + 1;
 122     return 1 + ((i + 15) >> 5);
 123 }
 124
 125 /* Create an entry in a file.  Dir is a file representation, while entry is a string name. */
 126
 127 int
 128 Create(void *dir, char *entry, void *voidfid)
 129 {
 130     afs_int32 *vfid = (afs_int32 *) voidfid;
 131     int blobs, firstelt;
 132     register int i;
 133     register struct DirEntry *ep;
 134     unsigned short *pp = NULL;
 135     register struct DirHeader *dhp;
 136
 137     /* check name quality */
 138     if (*entry == 0)
 139         return EINVAL;
 140     /* First check if file already exists. */
 141     ep = FindItem(dir, entry, &pp);
 142     if (ep) {
 143         DRelease(ep, 0);
 144         DRelease(pp, 0);
 145         return EEXIST;
 146     }
 147     blobs = NameBlobs(entry);   /* number of entries required */
 148     firstelt = FindBlobs(dir, blobs);
 149     if (firstelt < 0)
 150         return EFBIG;           /* directory is full */
 151     /* First, we fill in the directory entry. */
 152     ep = GetBlob(dir, firstelt);
 153     if (ep == 0)
 154         return EIO;
 155     ep->flag = FFIRST;
 156     ep->fid.vnode = htonl(vfid[1]);
 157     ep->fid.vunique = htonl(vfid[2]);
 158     strcpy(ep->name, entry);
 159     /* Now we just have to thread it on the hash table list. */
 160     dhp = (struct DirHeader *)DRead(dir, 0);
 161     if (!dhp) {
 162         DRelease(ep, 1);
 163         return EIO;
 164     }
 165     i = DirHash(entry);
 166     ep->next = dhp->hashTable[i];
 167     dhp->hashTable[i] = htons(firstelt);
 168     DRelease(dhp, 1);
 169     DRelease(ep, 1);
 170     return 0;
 171 }
 172
 173 int
 174 Length(void *dir)
 175 {
 176     int i, ctr;
 177     struct DirHeader *dhp;
 178     dhp = (struct DirHeader *)DRead(dir, 0);
 179     if (!dhp)
 180         return 0;
 181     if (dhp->header.pgcount != 0)
 182         ctr = ntohs(dhp->header.pgcount);
 183     else {
 184         /* old style, count the pages */
 185         ctr = 0;
 186         for (i = 0; i < MAXPAGES; i++)
 187             if (dhp->alloMap[i] != EPP)
 188                 ctr++;
 189     }
 190     DRelease(dhp, 0);
 191     return ctr * AFS_PAGESIZE;
 192 }
 193
 194 int
 195 Delete(void *dir, char *entry)
 196 {
 197     /* Delete an entry from a directory, including update of all free entry descriptors. */
 198     int nitems, index;
 199     register struct DirEntry *firstitem;
 200     unsigned short *previtem;
 201     firstitem = FindItem(dir, entry, &previtem);
 202     if (firstitem == 0)
 203         return ENOENT;
 204     *previtem = firstitem->next;
 205     DRelease(previtem, 1);
 206     index = DVOffset(firstitem) / 32;
 207     nitems = NameBlobs(firstitem->name);
 208     DRelease(firstitem, 0);
 209     FreeBlobs(dir, index, nitems);
 210     return 0;
 211 }
 212
 213 int
 214 FindBlobs(void *dir, int nblobs)
 215 {
 216     /* Find a bunch of contiguous entries; at least nblobs in a row. */
 217     register int i, j, k;
 218     int failed = 0;
 219     register struct DirHeader *dhp;
 220     struct PageHeader *pp;
 221     int pgcount;
 222
 223     dhp = (struct DirHeader *)DRead(dir, 0);    /* read the dir header in first. */
 224     if (!dhp)
 225         return -1;
 226     for (i = 0; i < BIGMAXPAGES; i++) {
 227         if (i >= MAXPAGES || dhp->alloMap[i] >= nblobs) {
 228             /* if page could contain enough entries */
 229             /* If there are EPP free entries, then the page is not even allocated. */
 230             if (i >= MAXPAGES) {
 231                 /* this pages exists past the end of the old-style dir */
 232                 pgcount = ntohs(dhp->header.pgcount);
 233                 if (pgcount == 0) {
 234                     pgcount = MAXPAGES;
 235                     dhp->header.pgcount = htons(pgcount);
 236                 }
 237                 if (i > pgcount - 1) {
 238                     /* this page is bigger than last allocated page */
 239                     AddPage(dir, i);
 240                     dhp->header.pgcount = htons(i + 1);
 241                 }
 242             } else if (dhp->alloMap[i] == EPP) {
 243                 /* Add the page to the directory. */
 244                 AddPage(dir, i);
 245                 dhp->alloMap[i] = EPP - 1;
 246                 dhp->header.pgcount = htons(i + 1);
 247             }
 248             pp = (struct PageHeader *)DRead(dir, i);    /* read the page in. */
 249             if (!pp) {
 250                 DRelease(dhp, 1);
 251                 break;
 252             }
 253             for (j = 0; j <= EPP - nblobs; j++) {
 254                 failed = 0;
 255                 for (k = 0; k < nblobs; k++)
 256                     if ((pp->freebitmap[(j + k) >> 3] >> ((j + k) & 7)) & 1) {
 257                         failed = 1;
 258                         break;
 259                     }
 260                 if (!failed)
 261                     break;
 262                 failed = 1;
 263             }
 264             if (!failed) {
 265                 /* Here we have the first index in j.  We update the allocation maps
 266                  * and free up any resources we've got allocated. */
 267                 if (i < MAXPAGES)
 268                     dhp->alloMap[i] -= nblobs;
 269                 DRelease(dhp, 1);
 270                 for (k = 0; k < nblobs; k++)
 271                     pp->freebitmap[(j + k) >> 3] |= 1 << ((j + k) & 7);
 272                 DRelease(pp, 1);
 273                 return j + i * EPP;
 274             }
 275             DRelease(pp, 0);    /* This dir page is unchanged. */
 276         }
 277     }
 278     /* If we make it here, the directory is full. */
 279     DRelease(dhp, 1);
 280     return -1;
 281 }
 282
 283 void
 284 AddPage(void *dir, int pageno)
 285 {                               /* Add a page to a directory. */
 286     register int i;
 287     register struct PageHeader *pp;
 288
 289     pp = (struct PageHeader *)DNew(dir, pageno);        /* Get a new buffer labelled dir,pageno */
 290     pp->tag = htons(1234);
 291     if (pageno > 0)
 292         pp->pgcount = 0;
 293     pp->freecount = EPP - 1;    /* The first dude is already allocated */
 294     pp->freebitmap[0] = 0x01;
 295     for (i = 1; i < EPP / 8; i++)       /* It's a constant */
 296         pp->freebitmap[i] = 0;
 297     DRelease(pp, 1);
 298 }
 299
 300 /* Free a whole bunch of directory entries. */
 301
 302 void
 303 FreeBlobs(void *dir, register int firstblob, int nblobs)
 304 {
 305     register int i;
 306     int page;
 307     struct DirHeader *dhp;
 308     struct PageHeader *pp;
 309     page = firstblob / EPP;
 310     firstblob -= EPP * page;    /* convert to page-relative entry */
 311     dhp = (struct DirHeader *)DRead(dir, 0);
 312     if (!dhp)
 313         return;
 314     if (page < MAXPAGES)
 315         dhp->alloMap[page] += nblobs;
 316     DRelease(dhp, 1);
 317     pp = (struct PageHeader *)DRead(dir, page);
 318     if (pp)
 319         for (i = 0; i < nblobs; i++)
 320             pp->freebitmap[(firstblob + i) >> 3] &=
 321                 ~(1 << ((firstblob + i) & 7));
 322     DRelease(pp, 1);
 323 }
 324
 325 /*
 326  * Format an empty directory properly.  Note that the first 13 entries in a
 327  * directory header page are allocated, 1 to the page header, 4 to the
 328  * allocation map and 8 to the hash table.
 329  */
 330 int
 331 MakeDir(void *dir, afs_int32 * me, afs_int32 * parent)
 332 {
 333     register int i;
 334     register struct DirHeader *dhp;
 335     dhp = (struct DirHeader *)DNew(dir, 0);
 336     dhp->header.pgcount = htons(1);
 337     dhp->header.tag = htons(1234);
 338     dhp->header.freecount = (EPP - DHE - 1);
 339     dhp->header.freebitmap[0] = 0xff;
 340     dhp->header.freebitmap[1] = 0x1f;
 341     for (i = 2; i < EPP / 8; i++)
 342         dhp->header.freebitmap[i] = 0;
 343     dhp->alloMap[0] = (EPP - DHE - 1);
 344     for (i = 1; i < MAXPAGES; i++)
 345         dhp->alloMap[i] = EPP;
 346     for (i = 0; i < NHASHENT; i++)
 347         dhp->hashTable[i] = 0;
 348     DRelease(dhp, 1);
 349     Create(dir, ".", me);
 350     Create(dir, "..", parent);  /* Virtue is its own .. */
 351     return 0;
 352 }
 353
 354 /* Look up a file name in directory. */
 355
 356 int
 357 Lookup(void *dir, char *entry, void *voidfid)
 358 {
 359     afs_int32 *fid = (afs_int32 *) voidfid;
 360     register struct DirEntry *firstitem;
 361     unsigned short *previtem;
 362
 363     firstitem = FindItem(dir, entry, &previtem);
 364     if (firstitem == 0)
 365         return ENOENT;
 366     DRelease(previtem, 0);
 367     fid[1] = ntohl(firstitem->fid.vnode);
 368     fid[2] = ntohl(firstitem->fid.vunique);
 369     DRelease(firstitem, 0);
 370     return 0;
 371 }
 372
 373 /* Look up a file name in directory. */
 374
 375 int
 376 LookupOffset(void *dir, char *entry, void *voidfid, long *offsetp)
 377 {
 378     afs_int32 *fid = (afs_int32 *) voidfid;
 379     register struct DirEntry *firstitem;
 380     unsigned short *previtem;
 381
 382     firstitem = FindItem(dir, entry, &previtem);
 383     if (firstitem == 0)
 384         return ENOENT;
 385     DRelease(previtem, 0);
 386     fid[1] = ntohl(firstitem->fid.vnode);
 387     fid[2] = ntohl(firstitem->fid.vunique);
 388     if (offsetp)
 389         *offsetp = DVOffset(firstitem);
 390     DRelease(firstitem, 0);
 391     return 0;
 392 }
 393
 394 int
 395 EnumerateDir(void *dir, int (*hookproc) (), void *hook)
 396 {
 397     /* Enumerate the contents of a directory.
 398      * Break when hook function returns non 0.
 399      */
 400     register int i;
 401     int num;
 402     register struct DirHeader *dhp;
 403     register 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     register int i;
 443     int num;
 444     register struct DirHeader *dhp;
 445     register 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(register char *string)
 483 {
 484     /* Hash a string to a number between 0 and NHASHENT. */
 485     register unsigned char tc;
 486     unsigned int hval;
 487     register 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 static struct DirEntry *
 502 FindItem(void *dir, char *ename, unsigned short **previtem)
 503 {
 504     /* 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. */
 505     register int i;
 506     register struct DirHeader *dhp;
 507     register unsigned short *lp;
 508     register struct DirEntry *tp;
 509     i = DirHash(ename);
 510     dhp = (struct DirHeader *)DRead(dir, 0);
 511     if (!dhp)
 512         return 0;
 513     if (dhp->hashTable[i] == 0) {
 514         /* no such entry */
 515         DRelease(dhp, 0);
 516         return 0;
 517     }
 518     tp = GetBlob(dir, (u_short) ntohs(dhp->hashTable[i]));
 519     if (!tp) {
 520         DRelease(dhp, 0);
 521         return 0;
 522     }
 523     lp = &(dhp->hashTable[i]);
 524     while (1) {
 525         /* Look at each hash conflict entry. */
 526         if (!strcmp(ename, tp->name)) {
 527             /* Found our entry. */
 528             *previtem = lp;
 529             return tp;
 530         }
 531         DRelease(lp, 0);
 532         lp = &(tp->next);
 533         if (tp->next == 0) {
 534             /* The end of the line */
 535             DRelease(lp, 0);    /* Release all locks. */
 536             return 0;
 537         }
 538         tp = GetBlob(dir, (u_short) ntohs(tp->next));
 539         if (!tp) {
 540             DRelease(lp, 0);
 541             return 0;
 542         }
 543     }
 544 }
 545
 546 #if defined(AFS_DISCON_ENV)
 547 /*!
 548  * Change an entry fid.
 549  *
 550  * \param dir
 551  * \param entry The entry name.
 552  * \param old_fid The old find in MKFid format (host order).
 553  * It can be omitted if you don't need a safety check...
 554  * \param new_fid The new find in MKFid format (host order).
 555  */
 556 int ChangeFid(void *dir,
 557                 char *entry,
 558                 afs_uint32 *old_fid,
 559                 afs_uint32 *new_fid)
 560 {
 561     struct DirEntry *firstitem;
 562     unsigned short *previtem;
 563     struct MKFid *fid_old = (struct MKFid *) old_fid;
 564     struct MKFid *fid_new = (struct MKFid *) new_fid;
 565
 566     /* Find entry. */
 567     firstitem = FindItem(dir, entry, &previtem);
 568     if (firstitem == 0) {
 569         return ENOENT;
 570     }
 571     DRelease(previtem, 1);
 572     /* Replace fid. */
 573     if (!old_fid ||
 574         ((htonl(fid_old->vnode) == firstitem->fid.vnode) &&
 575         (htonl(fid_old->vunique) == firstitem->fid.vunique))) {
 576
 577         firstitem->fid.vnode = htonl(fid_new->vnode);
 578         firstitem->fid.vunique = htonl(fid_new->vunique);
 579     }
 580
 581     DRelease(firstitem, 1);
 582
 583     return 0;
 584 }
 585 #endif