lib/bufdir/fdir.c

   1 /*
   2  * Copyright (c) 1995 - 2006 Kungliga Tekniska Högskolan
   3  * (Royal Institute of Technology, Stockholm, Sweden).
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * 3. Neither the name of the Institute nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  */
  33
  34 /*
  35  * Routines for reading an AFS directory
  36  */
  37
  38 #ifndef _KERNEL
  39 #include <config.h>
  40
  41 RCSID("$Id$") ;
  42
  43 #include <sys/types.h>
  44 #include <sys/errno.h>
  45 #include <stdio.h>
  46 #include <unistd.h>
  47 #include <assert.h>
  48 #include <rx/rx.h>
  49 #else /* _KERNEL */
  50 #include <nnpfs_locl.h>
  51 #endif /* _KERNEL */
  52
  53 #include <afs_dir.h>
  54 #include <fdir.h>
  55
  56 /*
  57  * Hash the filename of one entry.
  58  */
  59
  60 static unsigned
  61 hashentry (const char *sentry)
  62 {
  63      int s = 0, h;
  64      const unsigned char *entry = (const unsigned char *)sentry;
  65
  66      while (*entry)
  67           s = s * 173 + *entry++;
  68      h = s & (ADIRHASHSIZE - 1);
  69      if (h == 0)
  70           return h;
  71      else if( s < 0 )
  72           h = ADIRHASHSIZE - h;
  73      return h;
  74 }
  75
  76 /*
  77  * Return the number of additional DirEntries used by an entry with
  78  * the filename `name`.
  79  */
  80
  81 static unsigned
  82 additional_entries (const char *filename,
  83                     const char *raw_utf,
  84                     const char *norm_utf)
  85 {
  86     static DirEntry dummy;
  87
  88     size_t len = (strlen(filename) - sizeof(dummy.name) + 1
  89                   + sizeof(DirEntry) - 1);
  90     if (raw_utf) {
  91         /* align to 4 byte boundery */
  92         if (len % 4)
  93             len += 4 - (len % 4);
  94         len += sizeof(DirEntry2);
  95         len += strlen(raw_utf);
  96         if (norm_utf)
  97             len += strlen(norm_utf);
  98     }
  99     return len / sizeof(DirEntry);
 100 }
 101
 102 /*
 103  * Return a pointer to page number `pageno'.
 104  */
 105
 106 static DirPage1 *
 107 getpage (DirPage0 *page0, unsigned pageno)
 108 {
 109     return (DirPage1 *)((char *)page0 + AFSDIR_PAGESIZE * pageno);
 110 }
 111
 112 /*
 113  * Return the entry `num' in the directory `page0'.
 114  * The directory must be continuous in memory after page0.
 115  */
 116
 117 static DirEntry *
 118 getentry (DirPage0 *page0,
 119           unsigned short num,
 120           size_t npages)
 121 {
 122      DirPage1 *page;
 123      unsigned idx = num / ENTRIESPERPAGE;
 124
 125      if (idx >= npages)
 126          return NULL;
 127
 128      page = getpage (page0, idx);
 129
 130      if (page->header.pg_tag != htons(AFSDIRMAGIC) &&
 131          page->header.pg_tag != htons(AFSDIRMAGIC_UTF8))
 132          return NULL;
 133
 134      return &page->entry[num % ENTRIESPERPAGE];
 135 }
 136
 137 /*
 138  * Return a pointer to the entry with name `name' in the directory `page0'.
 139  */
 140
 141 static DirEntry *
 142 find_entry(DirPage0 *page0, const char *name, size_t npages)
 143 {
 144     DirEntry *entry;
 145     unsigned short i;
 146
 147     for (i = ntohs(page0->dheader.hash[hashentry (name)]);
 148          i != 0;
 149          i = ntohs(entry->next))
 150     {
 151         entry = getentry (page0, (unsigned short)(i - 1), npages);
 152         if (entry == NULL)
 153             return NULL;
 154
 155         if (strcmp (entry->name, name) == 0)
 156             return entry;
 157     }
 158     return NULL;
 159 }
 160
 161 /*
 162  * Return the fid for the entry with `name' in `page0'.  `fid' is set
 163  * to the fid of that file.  `dir' should be the fid of the directory.
 164  * Return zero if succesful, and -1 otherwise.
 165  */
 166
 167 static int
 168 find_by_name (DirPage0 *page0,
 169               const char *name,
 170               VenusFid *fid,
 171               const VenusFid *dir,
 172               unsigned npages)
 173 {
 174     const DirEntry *entry = find_entry (page0, name, npages);
 175
 176     if (entry == NULL)
 177         return -1;
 178     fid->Cell       = dir->Cell;
 179     fid->fid.Volume = dir->fid.Volume;
 180     fid->fid.Vnode  = ntohl (entry->fid.Vnode);
 181     fid->fid.Unique = ntohl (entry->fid.Unique);
 182     return 0;
 183 }
 184
 185 /*
 186  * Return true if slot `off' on `page' is being used.
 187  */
 188
 189 static int
 190 used_slot (DirPage1 *page, int off)
 191 {
 192     return page->header.pg_bitmap[off / 8] & (1 << (off % 8));
 193 }
 194
 195 /*
 196  * Return true if slot w/ index `off' on `page' is a valid entry.
 197  */
 198
 199 static int
 200 first_slotp (DirPage1 *page, int off)
 201 {
 202     DirEntry *entry = &page->entry[off];
 203     if (used_slot(page, off + 1)
 204         && (entry->flag & AFSDIR_FIRST))
 205         return TRUE;
 206
 207     return FALSE;
 208 }
 209
 210 /*
 211  * Is this page `pageno' empty?
 212  */
 213
 214 static int
 215 is_page_empty (DirPage0 *page0, unsigned pageno)
 216 {
 217     DirPage1 *page;
 218     int i;
 219
 220     if (pageno < MAXPAGES)
 221         return page0->dheader.map[pageno] == ENTRIESPERPAGE - 1;
 222     page = getpage (page0, pageno);
 223     if (page->header.pg_bitmap[0] != 1)
 224         return 0;
 225     for (i = 1; i < sizeof(page->header.pg_bitmap); ++i)
 226         if (page->header.pg_bitmap[i] != 0)
 227             return 0;
 228     return 1;
 229 }
 230
 231 /*
 232  * Lookup `name' in the AFS directory identified by `dir' and return
 233  * the Fid in `file'. Return value is 0 or error code.
 234  */
 235
 236 int
 237 fdir_lookup (fbuf *the_fbuf, const VenusFid *dir,
 238              const char *name, VenusFid *file)
 239 {
 240      DirPage0 *page0;
 241      unsigned ind;
 242      unsigned npages;
 243      size_t len = fbuf_len(the_fbuf);
 244
 245      page0 = (DirPage0 *)fbuf_buf(the_fbuf);
 246      assert (page0);
 247
 248      npages = ntohs(page0->header.pg_pgcount);
 249      if (npages < len / AFSDIR_PAGESIZE)
 250          npages = len / AFSDIR_PAGESIZE;
 251
 252      ind = find_by_name (page0, name, file, dir, npages);
 253
 254      if (ind == 0)
 255          return 0;
 256      else
 257          return ENOENT;
 258 }
 259
 260 /*
 261  * Return TRUE if dir is empty.
 262  */
 263
 264 int
 265 fdir_emptyp (fbuf *dir)
 266 {
 267      DirPage0 *page0;
 268      unsigned npages;
 269      size_t len = fbuf_len(dir);
 270
 271      page0 = (DirPage0 *)fbuf_buf(dir);
 272      assert (page0);
 273
 274      npages = ntohs(page0->header.pg_pgcount);
 275      if (npages < len / AFSDIR_PAGESIZE)
 276          npages = len / AFSDIR_PAGESIZE;
 277
 278      return (npages == 1) && (page0->dheader.map[0] == 49);
 279 }
 280
 281 /*
 282  * Read all entries in the AFS directory identified by `dir' and call
 283  * `func' on each entry with the fid, the name, and `arg'.
 284  */
 285
 286 int
 287 fdir_readdir (fbuf *the_fbuf,
 288               fdir_readdir_func func,
 289               void *arg,
 290               VenusFid dir,
 291               uint32_t *offset)
 292 {
 293      DirPage0 *page0;
 294      unsigned i, j;
 295      VenusFid fid;
 296      size_t len = fbuf_len(the_fbuf);
 297      unsigned npages;
 298      int ret;
 299
 300      page0 = (DirPage0 *)fbuf_buf(the_fbuf);
 301
 302      assert (page0);
 303
 304      npages = ntohs(page0->header.pg_pgcount);
 305      if (npages < len / AFSDIR_PAGESIZE)
 306          npages = len / AFSDIR_PAGESIZE;
 307
 308      if (offset && *offset) {
 309          i = *offset / ENTRIESPERPAGE;
 310          j = *offset % ENTRIESPERPAGE;
 311
 312          if (i == 0 && j < 12)
 313              return EINVAL;
 314      } else {
 315          i = 0;
 316          j = 12; /* first slot */
 317      }
 318
 319      for (; i < npages; ++i) {
 320          DirPage1 *page = getpage (page0, i);
 321
 322          for (; j < ENTRIESPERPAGE - 1; ++j) {
 323              if (first_slotp (page, j)) {
 324                  DirEntry *entry = &page->entry[j];
 325                  int nentries;
 326                  char *name;
 327                  char *raw_utf = NULL;
 328                  char *norm_utf = NULL;
 329
 330                  if ((entry->flag & AFSDIR_FIRST) == 0)
 331                      continue;
 332
 333                  fid.Cell       = dir.Cell;
 334                  fid.fid.Volume = dir.fid.Volume;
 335                  fid.fid.Vnode  = ntohl (entry->fid.Vnode);
 336                  fid.fid.Unique = ntohl (entry->fid.Unique);
 337
 338                  if (entry->flag & AFSDIR_UTFENT) {
 339                      DirEntry2 *direntry2 = (DirEntry2 *)((char *)entry) + (entry->length << 2);
 340
 341                      /*
 342                       * Check that the end of the entry isn't past end
 343                       * of page
 344                       */
 345                      if ((unsigned char *)direntry2 >
 346                          ((unsigned char *)page) + AFSDIR_PAGESIZE - sizeof(*direntry2))
 347                          continue;
 348
 349                      raw_utf = ((char *)entry) + direntry2->raw_offset;
 350                      if (direntry2->raw_offset != direntry2->norm_offset)
 351                          norm_utf = ((char *)entry) + direntry2->norm_offset;
 352
 353                      /*
 354                       * Check that the start of the name isn't over
 355                       * the page, we should really check if its inside
 356                       * page, but lets skip that for now.
 357                       */
 358                      if (raw_utf > ((char *)page) + AFSDIR_PAGESIZE)
 359                          continue;
 360
 361                      name = raw_utf;
 362                  } else
 363                      name = entry->name;
 364
 365                  nentries = additional_entries(entry->name, raw_utf, norm_utf);
 366
 367                  /* Break on non-zero return, increase counter if >= 0 */
 368                  ret = (*func)(&fid, name, arg);
 369                  if (ret < 0)
 370                      goto done;
 371
 372                  j += nentries;
 373
 374                  if (ret)
 375                      goto done;
 376              }
 377          }
 378          j = 0;
 379      }
 380
 381  done:
 382      if (offset)
 383          *offset = i * ENTRIESPERPAGE + j;
 384
 385      return 0;
 386 }
 387
 388 #ifndef _KERNEL
 389
 390 /*
 391  * Return non-zero is `the_fbuf' passes casual inspection as a
 392  * directory.
 393  */
 394
 395 int
 396 fdir_dirp (fbuf *the_fbuf)
 397 {
 398      DirPage0 *page0;
 399      DirPage1 *page;
 400      unsigned num, npages;
 401      size_t len = fbuf_len(the_fbuf);
 402
 403      if (len < AFSDIR_PAGESIZE)
 404          return 0;
 405
 406      page0 = (DirPage0 *)fbuf_buf(the_fbuf);
 407      assert (page0);
 408
 409      npages = ntohs(page0->header.pg_pgcount);
 410      if (npages < len / AFSDIR_PAGESIZE)
 411          npages = len / AFSDIR_PAGESIZE;
 412
 413      for (num = 0; num < npages; num++) {
 414          page = getpage (page0, num);
 415
 416          if (page->header.pg_tag != htons(AFSDIRMAGIC) &&
 417              page->header.pg_tag != htons(AFSDIRMAGIC_UTF8))
 418              return 0;
 419      }
 420      return 1;
 421 }
 422
 423
 424 /*
 425  * Change the fid for `name' to `fid'.  Return 0 or -1.
 426  */
 427
 428 static int
 429 update_fid_by_name (DirPage0 *page0,
 430                     const char *name,
 431                     const VenusFid *fid,
 432                     unsigned npages)
 433 {
 434     DirEntry *entry = find_entry (page0, name, npages);
 435
 436     if (entry == NULL)
 437         return -1;
 438
 439     entry->fid.Vnode = htonl (fid->fid.Vnode);
 440     entry->fid.Unique = htonl (fid->fid.Unique);
 441     return 0;
 442 }
 443
 444 /*
 445  * Mark slot `off' on `page' as being used.
 446  */
 447
 448 static void
 449 set_used (DirPage1 *page, int off)
 450 {
 451     page->header.pg_bitmap[off / 8] |= 1 << (off % 8);
 452 }
 453
 454 /*
 455  * Mark slot `off' on `page' as not being used.
 456  */
 457
 458 static void
 459 set_unused (DirPage1 *page, int off)
 460 {
 461     page->header.pg_bitmap[off / 8] &= ~(1 << (off % 8));
 462 }
 463
 464 /*
 465  * Add a new page to the directory in `the_fbuf', returning a pointer
 466  * to the new page in `ret_page'.
 467  * Return 0 iff succesful.
 468  */
 469
 470 static int
 471 create_new_page (DirPage1 **ret_page,
 472                  fbuf *the_fbuf, int utf8_page)
 473 {
 474     int ret;
 475     DirPage1 *page1;
 476     size_t len = fbuf_len(the_fbuf);
 477
 478     ret = fbuf_truncate (the_fbuf, len + AFSDIR_PAGESIZE);
 479     if (ret)
 480         return ret;
 481
 482     page1 = (DirPage1 *)((char *)fbuf_buf(the_fbuf) + len);
 483     page1->header.pg_pgcount   = htons(0);
 484     if (utf8_page)
 485         page1->header.pg_tag       = htons(AFSDIRMAGIC_UTF8);
 486     else
 487         page1->header.pg_tag       = htons(AFSDIRMAGIC);
 488     page1->header.pg_freecount = ENTRIESPERPAGE - 1;
 489     memset (page1->header.pg_bitmap, 0, sizeof(page1->header.pg_bitmap));
 490     set_used (page1, 0);
 491     *ret_page = page1;
 492
 493     return 0;
 494 }
 495
 496 /*
 497  * Create a new entry with name `filename', fid `fid', and next
 498  * pointer `next' in the page `page' with page number `pageno'.
 499  * Return the index in the page or -1 if unsuccesful.
 500  */
 501
 502 static int
 503 add_to_page (DirPage0 *page0,
 504              DirPage1 *page,
 505              unsigned pageno,
 506              const char *filename,
 507              const char *raw_name,
 508              AFSFid fid,
 509              unsigned next)
 510 {
 511     int i, j;
 512     unsigned n;
 513
 514     n = 1 + additional_entries (filename, raw_name, NULL);
 515
 516     if (pageno < MAXPAGES && page0->dheader.map[pageno] < n)
 517         return -1;
 518
 519     for (i = 0; i < ENTRIESPERPAGE - n;) {
 520         for (j = 0; j < n && !used_slot (page, i + j + 1); ++j)
 521             ;
 522         if (j == n) {
 523             int k;
 524
 525             for (k = i + 1; k < i + j + 1; ++k)
 526                 page->header.pg_bitmap[k / 8] |= (1 << (k % 8));
 527
 528             page->entry[i].flag = AFSDIR_FIRST;
 529             page->entry[i].length = 0;
 530             page->entry[i].next = next;
 531             page->entry[i].fid.Vnode  = htonl(fid.Vnode);
 532             page->entry[i].fid.Unique = htonl(fid.Unique);
 533             strcpy (page->entry[i].name, filename);
 534             if (raw_name) {
 535                 DirEntry2 *entry2;
 536                 size_t fnl2, fnl = strlen(filename) + 1;
 537
 538                 page->entry[i].flag |= AFSDIR_UTFENT;
 539
 540                 if (fnl % 4)
 541                     fnl2 = fnl + (4 - (fnl % 4));
 542                 else
 543                     fnl2 = fnl;
 544                 memset(page->entry[i].name + fnl, 0, fnl2 - fnl);
 545
 546                 page->entry[i].length =
 547                     (((unsigned char *)&page->entry[i].name) -
 548                      ((unsigned char *)&page->entry[i]) +
 549                      fnl2) >> 2;
 550
 551                 entry2 = (DirEntry2 *)(page->entry[i].name + fnl2);
 552                 entry2->utf_next = 0;
 553                 entry2->raw_offset =
 554                     ((unsigned char *)&page->entry[i].name) -
 555                     ((unsigned char *)&page->entry[i]) +
 556                     fnl2 + sizeof(*entry2);
 557                 entry2->norm_offset = entry2->raw_offset;
 558                 strcpy((char *)(((unsigned char *)&page->entry[i]) + entry2->raw_offset),
 559                        raw_name);
 560             }
 561             memset(page->entry[i + j - 1].fill, 0, 4);
 562             if (pageno < MAXPAGES)
 563                 page0->dheader.map[pageno] -= n;
 564             return i;
 565         }
 566         i += j + 1;
 567     }
 568     return -1;
 569 }
 570
 571 /*
 572  * Remove the entry `off' from the page `page' (page number `pageno').
 573  */
 574
 575 static int
 576 remove_from_page (DirPage0 *page0,
 577                   DirPage1 *page,
 578                   unsigned pageno,
 579                   unsigned off)
 580 {
 581     DirEntry *entry = &page->entry[off];
 582     unsigned n, i;
 583
 584     n = 1 + additional_entries (entry->name, NULL, NULL);
 585
 586     if (pageno < MAXPAGES)
 587         page0->dheader.map[pageno] += n;
 588
 589     entry->next = 0;
 590     entry->fid.Vnode  = 0;
 591     entry->fid.Unique = 0;
 592
 593     for (i = off + 1; i < off + n + 1; ++i)
 594         set_unused (page, i);
 595     return 0;
 596 }
 597
 598 /*
 599  * Lookup `name' in the AFS directory identified by `dir' and change the
 600  * fid to `fid'.
 601  */
 602
 603 int
 604 fdir_changefid (fbuf *the_fbuf,
 605                 const char *name,
 606                 const VenusFid *file)
 607 {
 608     DirPage0 *page0;
 609     unsigned npages;
 610     size_t len = fbuf_len(the_fbuf);
 611     int ret;
 612
 613     page0 = (DirPage0 *)fbuf_buf(the_fbuf);
 614     assert (page0);
 615
 616     npages = ntohs(page0->header.pg_pgcount);
 617     if (npages < len / AFSDIR_PAGESIZE)
 618         npages = len / AFSDIR_PAGESIZE;
 619
 620     ret = update_fid_by_name (page0, name, file, npages);
 621
 622     if (ret == 0)
 623         return 0;
 624     else
 625         return ENOENT;
 626 }
 627
 628 /*
 629  * Create a new directory with only . and ..
 630  */
 631
 632 int
 633 fdir_mkdir (fbuf *the_fbuf,
 634             AFSFid dot,
 635             AFSFid dot_dot,
 636             int utf8_dir)
 637 {
 638     DirPage0 *page0;
 639     DirPage1 *page;
 640     int ind;
 641     int i;
 642     int tmp;
 643     int ret;
 644
 645     ret = create_new_page (&page, the_fbuf, utf8_dir);
 646     if (ret)
 647         return ret;
 648
 649     page0 = (DirPage0 *)fbuf_buf(the_fbuf);
 650     memset (&page0->dheader, 0, sizeof(page0->dheader));
 651     tmp = ENTRIESPERPAGE
 652         - (sizeof(PageHeader) + sizeof(DirHeader)) / sizeof(DirEntry);
 653     if (utf8_dir)
 654         tmp -= 32;
 655     page0->header.pg_freecount = tmp;
 656     page0->dheader.map[0]      = tmp;
 657     page0->header.pg_pgcount   = htons(1);
 658
 659     /* set hashtable used */
 660     for (i = 0; i < 13; ++i)
 661         set_used (page, i);
 662
 663     if (utf8_dir) {
 664         /* set hashtable_utf used */
 665         for (; i < 13 + 32; ++i)
 666             set_used (page, i);
 667     }
 668
 669     assert (page0->dheader.hash[hashentry(".")] == 0);
 670
 671     ind = add_to_page (page0, page, 0, ".", NULL, dot, 0);
 672
 673     assert (ind >= 0);
 674
 675     page0->dheader.hash[hashentry(".")] = htons(ind + 1);
 676
 677     assert (page0->dheader.hash[hashentry("..")] == 0);
 678
 679     ind = add_to_page (page0, page, 0, "..", NULL, dot_dot, 0);
 680
 681     assert (ind >= 0);
 682
 683     page0->dheader.hash[hashentry("..")] = htons(ind + 1);
 684
 685     return 0;
 686 }
 687
 688 /*
 689  * Create a new entry with name `filename' and contents `fid' in `dir'.
 690  */
 691
 692 int
 693 fdir_creat (fbuf *dir,
 694             const char *name,
 695             const char *utf8name,
 696             AFSFid fid)
 697 {
 698     int ret;
 699     int i;
 700     size_t npages;
 701     DirPage0 *page0;
 702     DirPage1 *page;
 703     int ind = 0;
 704     unsigned hash_value, next;
 705     int utf8_dir, convert_dir = 0;
 706
 707     if (fbuf_len(dir) == 0)
 708         return EINVAL;
 709
 710     page0 = (DirPage0 *)fbuf_buf(dir);
 711     assert (page0);
 712
 713     npages = ntohs(page0->header.pg_pgcount);
 714     if (npages < fbuf_len(dir) / AFSDIR_PAGESIZE)
 715         npages = fbuf_len(dir) / AFSDIR_PAGESIZE;
 716
 717     if (find_entry (page0, name, npages))
 718         return EEXIST;
 719
 720     if (page0->header.pg_tag == htons(AFSDIRMAGIC_UTF8))
 721         utf8_dir = 1;
 722     else if (utf8name) {
 723         convert_dir = 1;
 724         utf8_dir = 1;
 725         utf8name = NULL;
 726     } else
 727         utf8_dir = 0;
 728
 729     hash_value = hashentry (name);
 730     next = page0->dheader.hash[hash_value];
 731
 732     for (i = 0; i < npages; ++i) {
 733         page = getpage (page0, i);
 734         ind = add_to_page (page0, page, i, name, utf8name, fid, next);
 735         if (ind >= 0)
 736             break;
 737     }
 738     if (i == npages) {
 739         ret = create_new_page (&page, dir, utf8_dir);
 740         if (ret)
 741             return ret;
 742         page0 = (DirPage0 *)fbuf_buf(dir);
 743         page0->header.pg_pgcount = htons(npages + 1);
 744         if (i < MAXPAGES)
 745             page0->dheader.map[i] = ENTRIESPERPAGE - 1;
 746         ind = add_to_page (page0, page, i, name, utf8name, fid, next);
 747         assert (ind >= 0);
 748     }
 749     ind += i * ENTRIESPERPAGE;
 750
 751     page0->dheader.hash[hash_value] = htons(ind + 1);
 752
 753     return 0;
 754 }
 755
 756 /*
 757  * Remove the entry named `name' in dir.
 758  */
 759
 760 int
 761 fdir_remove (fbuf *dir,
 762              const char *name,
 763              AFSFid *fid)
 764 {
 765     int i;
 766     unsigned len = fbuf_len(dir);
 767     DirPage0 *page0;
 768     DirPage1 *page;
 769     unsigned hash_value;
 770     DirEntry *entry = NULL;
 771     DirEntry *prev_entry;
 772     unsigned pageno;
 773     int found;
 774     size_t npages;
 775
 776
 777     page0 = (DirPage0 *)fbuf_buf(dir);
 778
 779     npages = ntohs(page0->header.pg_pgcount);
 780     if (npages < len / AFSDIR_PAGESIZE)
 781         npages = len / AFSDIR_PAGESIZE;
 782
 783     hash_value = hashentry (name);
 784     i = ntohs(page0->dheader.hash[hash_value]);
 785     found = i == 0;
 786     prev_entry = NULL;
 787     while (!found) {
 788         entry = getentry (page0, i - 1, npages);
 789         if (entry == NULL)
 790             return ENOENT;
 791
 792         if (strcmp (entry->name, name) == 0) {
 793             found = TRUE;
 794         } else {
 795             i = ntohs(entry->next);
 796             if (i == 0)
 797                 found = TRUE;
 798             prev_entry = entry;
 799         }
 800     }
 801     if (i == 0)
 802         return ENOENT;
 803     else {
 804         if (fid) {
 805             fid->Vnode = ntohl(entry->fid.Vnode);
 806             fid->Unique = ntohl(entry->fid.Unique);
 807         }
 808
 809         if (prev_entry == NULL)
 810             page0->dheader.hash[hash_value] = entry->next;
 811         else
 812             prev_entry->next = entry->next;
 813
 814         pageno = (i - 1) / ENTRIESPERPAGE;
 815         page = getpage (page0, pageno);
 816         remove_from_page (page0, page, pageno, (i - 1) % ENTRIESPERPAGE);
 817         if (pageno == npages - 1
 818             && is_page_empty (page0, pageno)) {
 819             do {
 820                 len -= AFSDIR_PAGESIZE;
 821                 --pageno;
 822                 --npages;
 823             } while(is_page_empty(page0, pageno));
 824             page0->header.pg_pgcount = htons(npages);
 825             fbuf_truncate (dir, len);
 826         }
 827         return 0;
 828     }
 829 }
 830
 831 #endif /* _KERNEL */