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