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