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