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