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