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