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