contrib/amd/amd/readdir.c

   1 /*
   2  * Copyright (c) 1997-2014 Erez Zadok
   3  * Copyright (c) 1990 Jan-Simon Pendry
   4  * Copyright (c) 1990 Imperial College of Science, Technology & Medicine
   5  * Copyright (c) 1990 The Regents of the University of California.
   6  * All rights reserved.
   7  *
   8  * This code is derived from software contributed to Berkeley by
   9  * Jan-Simon Pendry at Imperial College, London.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. Neither the name of the University nor the names of its contributors
  20  *    may be used to endorse or promote products derived from this software
  21  *    without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  *
  35  *
  36  * File: am-utils/amd/readdir.c
  37  *
  38  */
  39
  40
  41 #include <stdint.h>
  42 #ifdef HAVE_CONFIG_H
  43 # include <config.h>
  44 #endif /* HAVE_CONFIG_H */
  45 #include <am_defs.h>
  46 #include <amd.h>
  47
  48
  49 /****************************************************************************
  50  *** MACROS                                                               ***
  51  ****************************************************************************/
  52 #define DOT_DOT_COOKIE  (u_int) 1
  53 #define MAX_CHAIN       2048
  54
  55
  56 /****************************************************************************
  57  *** FORWARD DEFINITIONS                                                  ***
  58  ****************************************************************************/
  59 static int key_already_in_chain(char *keyname, const nfsentry *chain);
  60 static nfsentry *make_entry_chain(am_node *mp, const nfsentry *current_chain, int fully_browsable);
  61 static int amfs_readdir_browsable(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count, int fully_browsable);
  62
  63 static const u_int dotdotcookie = DOT_DOT_COOKIE;
  64
  65 /****************************************************************************
  66  *** FUNCTIONS                                                             ***
  67  ****************************************************************************/
  68 /*
  69  * Was: NEW_TOPLVL_READDIR
  70  * Search a chain for an entry with some name.
  71  * -Erez Zadok <ezk@cs.columbia.edu>
  72  */
  73 static int
  74 key_already_in_chain(char *keyname, const nfsentry *chain)
  75 {
  76   const nfsentry *tmpchain = chain;
  77
  78   while (tmpchain) {
  79     if (keyname && tmpchain->ne_name && STREQ(keyname, tmpchain->ne_name))
  80         return 1;
  81     tmpchain = tmpchain->ne_nextentry;
  82   }
  83
  84   return 0;
  85 }
  86
  87
  88 /*
  89  * Create a chain of entries which are not linked.
  90  * -Erez Zadok <ezk@cs.columbia.edu>
  91  */
  92 static nfsentry *
  93 make_entry_chain(am_node *mp, const nfsentry *current_chain, int fully_browsable)
  94 {
  95   static u_int last_cookie = (u_int) 2; /* monotonically increasing */
  96   static nfsentry chain[MAX_CHAIN];
  97   static int max_entries = MAX_CHAIN;
  98   char *key;
  99   int num_entries = 0, i;
 100   u_int preflen = 0;
 101   nfsentry *retval = (nfsentry *) NULL;
 102   mntfs *mf;
 103   mnt_map *mmp;
 104
 105   if (!mp) {
 106     plog(XLOG_DEBUG, "make_entry_chain: mp is (NULL)");
 107     return retval;
 108   }
 109   mf = mp->am_al->al_mnt;
 110   if (!mf) {
 111     plog(XLOG_DEBUG, "make_entry_chain: mp->am_al->al_mnt is (NULL)");
 112     return retval;
 113   }
 114   mmp = (mnt_map *) mf->mf_private;
 115   if (!mmp) {
 116     plog(XLOG_DEBUG, "make_entry_chain: mp->am_al->al_mnt->mf_private is (NULL)");
 117     return retval;
 118   }
 119
 120   if (mp->am_pref)
 121     preflen = strlen(mp->am_pref);
 122
 123   /* iterate over keys */
 124   for (i = 0; i < NKVHASH; i++) {
 125     kv *k;
 126     for (k = mmp->kvhash[i]; k ; k = k->next) {
 127
 128       /*
 129        * Skip unwanted entries which are either not real entries or
 130        * very difficult to interpret (wildcards...)  This test needs
 131        * lots of improvement.  Any takers?
 132        */
 133       key = k->key;
 134       if (!key)
 135         continue;
 136
 137       /* Skip '/defaults' */
 138       if (STREQ(key, "/defaults"))
 139         continue;
 140
 141       /* Skip '*' */
 142       if (!fully_browsable && strchr(key, '*'))
 143         continue;
 144
 145       /*
 146        * If the map has a prefix-string then check if the key starts with
 147        * this string, and if it does, skip over this prefix.  If it has a
 148        * prefix and it doesn't match the start of the key, skip it.
 149        */
 150       if (preflen) {
 151         if (preflen > strlen(key))
 152           continue;
 153         if (!NSTREQ(key, mp->am_pref, preflen))
 154           continue;
 155         key += preflen;
 156       }
 157
 158       /* no more '/' are allowed, unless browsable_dirs=full was used */
 159       if (!fully_browsable && strchr(key, '/'))
 160         continue;
 161
 162       /* no duplicates allowed */
 163       if (key_already_in_chain(key, current_chain))
 164         continue;
 165
 166       /* fill in a cell and link the entry */
 167       if (num_entries >= max_entries) {
 168         /* out of space */
 169         plog(XLOG_DEBUG, "make_entry_chain: no more space in chain");
 170         if (num_entries > 0) {
 171           chain[num_entries - 1].ne_nextentry = NULL;
 172           retval = &chain[0];
 173         }
 174         return retval;
 175       }
 176
 177       /* we have space.  put entry in next cell */
 178       ++last_cookie;
 179       chain[num_entries].ne_fileid = last_cookie;
 180       (void)memcpy(chain[num_entries].ne_cookie, &last_cookie,
 181         sizeof(last_cookie));
 182       chain[num_entries].ne_name = key;
 183       if (num_entries < max_entries - 1) {      /* link to next one */
 184         chain[num_entries].ne_nextentry = &chain[num_entries + 1];
 185       }
 186       ++num_entries;
 187     } /* end of "while (k)" */
 188   } /* end of "for (i ... NKVHASH ..." */
 189
 190   /* terminate chain */
 191   if (num_entries > 0) {
 192     chain[num_entries - 1].ne_nextentry = NULL;
 193     retval = &chain[0];
 194   }
 195
 196   return retval;
 197 }
 198
 199
 200
 201 /* This one is called only if map is browsable */
 202 static int
 203 amfs_readdir_browsable(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count, int fully_browsable)
 204 {
 205   u_int gen = *(u_int *) (uintptr_t) cookie;
 206   int chain_length, i;
 207   static nfsentry *te, *te_next;
 208   static int j;
 209
 210   dp->dl_eof = FALSE;           /* assume readdir not done */
 211
 212   if (amuDebug(D_READDIR))
 213     plog(XLOG_DEBUG, "amfs_readdir_browsable gen=%u, count=%d",
 214          gen, count);
 215
 216   if (gen == 0) {
 217     /*
 218      * In the default instance (which is used to start a search) we return
 219      * "." and "..".
 220      *
 221      * This assumes that the count is big enough to allow both "." and ".."
 222      * to be returned in a single packet.  If it isn't (which would be
 223      * fairly unbelievable) then tough.
 224      */
 225     dlog("%s: default search", __func__);
 226     /*
 227      * Check for enough room.  This is extremely approximate but is more
 228      * than enough space.  Really need 2 times:
 229      *      4byte fileid
 230      *      4byte cookie
 231      *      4byte name length
 232      *      4byte name
 233      * plus the dirlist structure */
 234     if (count < (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp))))
 235       return EINVAL;
 236
 237     /*
 238      * compute # of entries to send in this chain.
 239      * heuristics: 128 bytes per entry.
 240      * This is too much probably, but it seems to work better because
 241      * of the re-entrant nature of nfs_readdir, and esp. on systems
 242      * like OpenBSD 2.2.
 243      */
 244     chain_length = count / 128;
 245
 246     /* reset static state counters */
 247     te = te_next = NULL;
 248
 249     dp->dl_entries = ep;
 250
 251     /* construct "." */
 252     ep[0].ne_fileid = mp->am_gen;
 253     ep[0].ne_name = ".";
 254     ep[0].ne_nextentry = &ep[1];
 255     (void)memset(ep[0].ne_cookie, 0, sizeof(u_int));
 256
 257     /* construct ".." */
 258     if (mp->am_parent)
 259       ep[1].ne_fileid = mp->am_parent->am_gen;
 260     else
 261       ep[1].ne_fileid = mp->am_gen;
 262
 263     ep[1].ne_name = "..";
 264     ep[1].ne_nextentry = NULL;
 265     (void)memcpy(ep[1].ne_cookie, &dotdotcookie, sizeof(dotdotcookie));
 266
 267     /*
 268      * If map is browsable, call a function make_entry_chain() to construct
 269      * a linked list of unmounted keys, and return it.  Then link the chain
 270      * to the regular list.  Get the chain only once, but return
 271      * chunks of it each time.
 272      */
 273     te = make_entry_chain(mp, dp->dl_entries, fully_browsable);
 274     if (!te)
 275       return 0;
 276     if (amuDebug(D_READDIR)) {
 277       nfsentry *ne;
 278       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 279         plog(XLOG_DEBUG, "gen1 key %4d \"%s\"", j++, ne->ne_name);
 280     }
 281
 282     /* return only "chain_length" entries */
 283     te_next = te;
 284     for (i=1; i<chain_length; ++i) {
 285       te_next = te_next->ne_nextentry;
 286       if (!te_next)
 287         break;
 288     }
 289     if (te_next) {
 290       nfsentry *te_saved = te_next->ne_nextentry;
 291       te_next->ne_nextentry = NULL; /* terminate "te" chain */
 292       te_next = te_saved;       /* save rest of "te" for next iteration */
 293       dp->dl_eof = FALSE;       /* tell readdir there's more */
 294     } else {
 295       dp->dl_eof = TRUE;        /* tell readdir that's it */
 296     }
 297     ep[1].ne_nextentry = te;    /* append this chunk of "te" chain */
 298     if (amuDebug(D_READDIR)) {
 299       nfsentry *ne;
 300       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 301         plog(XLOG_DEBUG, "gen2 key %4d \"%s\"", j++, ne->ne_name);
 302       for (j = 0, ne = ep; ne; ne = ne->ne_nextentry) {
 303         u_int cookie;
 304         (void)memcpy(&cookie, ne->ne_cookie, sizeof(cookie));
 305         plog(XLOG_DEBUG, "gen2+ key %4d \"%s\" fi=%d ck=%d",
 306              j++, ne->ne_name, ne->ne_fileid, cookie);
 307       }
 308       plog(XLOG_DEBUG, "EOF is %d", dp->dl_eof);
 309     }
 310     return 0;
 311   } /* end of "if (gen == 0)" statement */
 312
 313   dlog("%s: real child", __func__);
 314
 315   if (gen == DOT_DOT_COOKIE) {
 316     dlog("%s: End of readdir in %s", __func__, mp->am_path);
 317     dp->dl_eof = TRUE;
 318     dp->dl_entries = NULL;
 319     return 0;
 320   }
 321
 322   /*
 323    * If browsable directories, then continue serving readdir() with another
 324    * chunk of entries, starting from where we left off (when gen was equal
 325    * to 0).  Once again, assume last chunk served to readdir.
 326    */
 327   dp->dl_eof = TRUE;
 328   dp->dl_entries = ep;
 329
 330   te = te_next;                 /* reset 'te' from last saved te_next */
 331   if (!te) {                    /* another indicator of end of readdir */
 332     dp->dl_entries = NULL;
 333     return 0;
 334   }
 335   /*
 336    * compute # of entries to send in this chain.
 337    * heuristics: 128 bytes per entry.
 338    */
 339   chain_length = count / 128;
 340
 341   /* return only "chain_length" entries */
 342   for (i = 1; i < chain_length; ++i) {
 343     te_next = te_next->ne_nextentry;
 344     if (!te_next)
 345       break;
 346   }
 347   if (te_next) {
 348     nfsentry *te_saved = te_next->ne_nextentry;
 349     te_next->ne_nextentry = NULL; /* terminate "te" chain */
 350     te_next = te_saved;         /* save rest of "te" for next iteration */
 351     dp->dl_eof = FALSE;         /* tell readdir there's more */
 352   }
 353   ep = te;                      /* send next chunk of "te" chain */
 354   dp->dl_entries = ep;
 355   if (amuDebug(D_READDIR)) {
 356     nfsentry *ne;
 357     plog(XLOG_DEBUG, "dl_entries=%p, te_next=%p, dl_eof=%d",
 358          dp->dl_entries, te_next, dp->dl_eof);
 359     for (ne = te; ne; ne = ne->ne_nextentry)
 360       plog(XLOG_DEBUG, "gen3 key %4d \"%s\"", j++, ne->ne_name);
 361   }
 362   return 0;
 363 }
 364
 365 static int
 366 amfs_readdir(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count)
 367 {
 368   u_int gen = *(u_int *) (uintptr_t) cookie;
 369   am_node *xp;
 370
 371   dp->dl_eof = FALSE;           /* assume readdir not done */
 372
 373   /* when gen is 0, we start reading from the beginning of the directory */
 374   if (gen == 0) {
 375     /*
 376      * In the default instance (which is used to start a search) we return
 377      * "." and "..".
 378      *
 379      * This assumes that the count is big enough to allow both "." and ".."
 380      * to be returned in a single packet.  If it isn't (which would be
 381      * fairly unbelievable) then tough.
 382      */
 383     dlog("%s: default search", __func__);
 384     /*
 385      * Check for enough room.  This is extremely approximate but is more
 386      * than enough space.  Really need 2 times:
 387      *      4byte fileid
 388      *      4byte cookie
 389      *      4byte name length
 390      *      4byte name
 391      * plus the dirlist structure */
 392 #define NEEDROOM (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp)))
 393     if (count < NEEDROOM) {
 394       dlog("%s: not enough room %u < %zu", __func__, count, NEEDROOM);
 395       return EINVAL;
 396     }
 397
 398     xp = next_nonerror_node(mp->am_child);
 399     dp->dl_entries = ep;
 400
 401     /* construct "." */
 402     ep[0].ne_fileid = mp->am_gen;
 403     ep[0].ne_name = ".";
 404     ep[0].ne_nextentry = &ep[1];
 405     (void)memset(ep[0].ne_cookie, 0, sizeof(u_int));
 406
 407     /* construct ".." */
 408     if (mp->am_parent)
 409       ep[1].ne_fileid = mp->am_parent->am_gen;
 410     else
 411       ep[1].ne_fileid = mp->am_gen;
 412     ep[1].ne_name = "..";
 413     ep[1].ne_nextentry = NULL;
 414     (void)memcpy(ep[1].ne_cookie, (xp ? &xp->am_gen : &dotdotcookie),
 415       sizeof(dotdotcookie));
 416
 417     if (!xp)
 418       dp->dl_eof = TRUE;        /* by default assume readdir done */
 419
 420     if (amuDebug(D_READDIR)) {
 421       nfsentry *ne;
 422       int j;
 423       for (j = 0, ne = ep; ne; ne = ne->ne_nextentry) {
 424         u_int cookie;
 425         (void)memcpy(&cookie, ne->ne_cookie, sizeof(cookie));
 426         plog(XLOG_DEBUG, "gen1 key %4d \"%s\" fi=%d ck=%d",
 427              j++, ne->ne_name, ne->ne_fileid, cookie);
 428       }
 429     }
 430     return 0;
 431   }
 432   dlog("%s: real child", __func__);
 433
 434   if (gen == DOT_DOT_COOKIE) {
 435     dlog("%s: End of readdir in %s", __func__, mp->am_path);
 436     dp->dl_eof = TRUE;
 437     dp->dl_entries = NULL;
 438     if (amuDebug(D_READDIR))
 439       plog(XLOG_DEBUG, "end of readdir eof=TRUE, dl_entries=0\n");
 440     return 0;
 441   }
 442
 443   /* non-browsable directories code */
 444   xp = mp->am_child;
 445   while (xp && xp->am_gen != gen)
 446     xp = xp->am_osib;
 447
 448   if (xp) {
 449     int nbytes = count / 2;     /* conservative */
 450     int todo = MAX_READDIR_ENTRIES;
 451
 452     dp->dl_entries = ep;
 453     do {
 454       am_node *xp_next = next_nonerror_node(xp->am_osib);
 455
 456       if (xp_next) {
 457         (void)memcpy(ep->ne_cookie, &xp_next->am_gen, sizeof(xp_next->am_gen));
 458       } else {
 459         (void)memcpy(ep->ne_cookie, &dotdotcookie, sizeof(dotdotcookie));
 460         dp->dl_eof = TRUE;
 461       }
 462
 463       ep->ne_fileid = xp->am_gen;
 464       ep->ne_name = xp->am_name;
 465       nbytes -= sizeof(*ep) + 1;
 466       if (xp->am_name)
 467         nbytes -= strlen(xp->am_name);
 468
 469       xp = xp_next;
 470
 471       if (nbytes > 0 && !dp->dl_eof && todo > 1) {
 472         ep->ne_nextentry = ep + 1;
 473         ep++;
 474         --todo;
 475       } else {
 476         todo = 0;
 477       }
 478     } while (todo > 0);
 479
 480     ep->ne_nextentry = NULL;
 481
 482     if (amuDebug(D_READDIR)) {
 483       nfsentry *ne;
 484       int j;
 485       for (j=0,ne=ep; ne; ne=ne->ne_nextentry) {
 486         u_int cookie;
 487         (void)memcpy(&cookie, ne->ne_cookie, sizeof(cookie));
 488         plog(XLOG_DEBUG, "gen2 key %4d \"%s\" fi=%d ck=%d",
 489              j++, ne->ne_name, ne->ne_fileid, cookie);
 490       }
 491     }
 492     return 0;
 493   }
 494   return ESTALE;
 495 }
 496
 497 /*
 498  * Search a chain for an entry with some name.
 499  */
 500 static int
 501 key_already_in_chain3(char *keyname, const am_entry3 *chain)
 502 {
 503   const am_entry3 *tmpchain = chain;
 504
 505   while (tmpchain) {
 506     if (keyname && tmpchain->name && STREQ(keyname, tmpchain->name))
 507         return 1;
 508     tmpchain = tmpchain->nextentry;
 509   }
 510
 511   return 0;
 512 }
 513
 514 /*
 515  * Create a chain of entries which are not linked.
 516  */
 517 static am_entry3 *
 518 make_entry_chain3(am_node *mp, const am_entry3 *current_chain, int fully_browsable)
 519 {
 520   static uint64 last_cookie = (uint64) 2;       /* monotonically increasing */
 521   static am_entry3 chain[MAX_CHAIN];
 522   static int max_entries = MAX_CHAIN;
 523   char *key;
 524   int num_entries = 0, i;
 525   u_int preflen = 0;
 526   am_entry3 *retval = (am_entry3 *) NULL;
 527   mntfs *mf;
 528   mnt_map *mmp;
 529
 530   if (!mp) {
 531     plog(XLOG_DEBUG, "make_entry_chain3: mp is (NULL)");
 532     return retval;
 533   }
 534   mf = mp->am_al->al_mnt;
 535   if (!mf) {
 536     plog(XLOG_DEBUG, "make_entry_chain3: mp->am_al->al_mnt is (NULL)");
 537     return retval;
 538   }
 539   mmp = (mnt_map *) mf->mf_private;
 540   if (!mmp) {
 541     plog(XLOG_DEBUG, "make_entry_chain3: mp->am_al->al_mnt->mf_private is (NULL)");
 542     return retval;
 543   }
 544
 545   if (mp->am_pref)
 546     preflen = strlen(mp->am_pref);
 547
 548   /* iterate over keys */
 549   for (i = 0; i < NKVHASH; i++) {
 550     kv *k;
 551     for (k = mmp->kvhash[i]; k ; k = k->next) {
 552
 553       /*
 554        * Skip unwanted entries which are either not real entries or
 555        * very difficult to interpret (wildcards...)  This test needs
 556        * lots of improvement.  Any takers?
 557        */
 558       key = k->key;
 559       if (!key)
 560         continue;
 561
 562       /* Skip '/defaults' */
 563       if (STREQ(key, "/defaults"))
 564         continue;
 565
 566       /* Skip '*' */
 567       if (!fully_browsable && strchr(key, '*'))
 568         continue;
 569
 570       /*
 571        * If the map has a prefix-string then check if the key starts with
 572        * this string, and if it does, skip over this prefix.  If it has a
 573        * prefix and it doesn't match the start of the key, skip it.
 574        */
 575       if (preflen) {
 576         if (preflen > strlen(key))
 577           continue;
 578         if (!NSTREQ(key, mp->am_pref, preflen))
 579           continue;
 580         key += preflen;
 581       }
 582
 583       /* no more '/' are allowed, unless browsable_dirs=full was used */
 584       if (!fully_browsable && strchr(key, '/'))
 585         continue;
 586
 587       /* no duplicates allowed */
 588       if (key_already_in_chain3(key, current_chain))
 589         continue;
 590
 591       /* fill in a cell and link the entry */
 592       if (num_entries >= max_entries) {
 593         /* out of space */
 594         plog(XLOG_DEBUG, "make_entry_chain3: no more space in chain");
 595         if (num_entries > 0) {
 596           chain[num_entries - 1].nextentry = NULL;
 597           retval = &chain[0];
 598         }
 599         return retval;
 600       }
 601
 602       /* we have space.  put entry in next cell */
 603       ++last_cookie;
 604       chain[num_entries].fileid = last_cookie;
 605       chain[num_entries].cookie = last_cookie;
 606       chain[num_entries].name = key;
 607       if (num_entries < max_entries - 1) {      /* link to next one */
 608         chain[num_entries].nextentry = &chain[num_entries + 1];
 609       }
 610       ++num_entries;
 611     } /* end of "while (k)" */
 612   } /* end of "for (i ... NKVHASH ..." */
 613
 614   /* terminate chain */
 615   if (num_entries > 0) {
 616     chain[num_entries - 1].nextentry = NULL;
 617     retval = &chain[0];
 618   }
 619
 620   return retval;
 621 }
 622
 623 static size_t needroom3(void)
 624 {
 625   /*
 626    * Check for enough room.  This is extremely approximate but should
 627    * be enough space.  Really need 2 times:
 628    *      (8byte fileid
 629    *      8byte cookie
 630    *      8byte name pointer
 631    *      8byte next entry addres) = sizeof(am_entry3)
 632    *      2byte name + 1byte terminator
 633    * plus the size of the am_dirlist3 structure */
 634   return ((2 * ((sizeof(am_entry3) + sizeof("..") + 1))) + sizeof(am_dirlist3));
 635 }
 636
 637 /* This one is called only if map is browsable */
 638 static int
 639 amfs_readdir3_browsable(am_node *mp, am_cookie3 cookie,
 640                         am_dirlist3 *dp, am_entry3 *ep, u_int count,
 641                         int fully_browsable)
 642 {
 643   uint64 gen = *(uint64 *) (uintptr_t) cookie;
 644   int chain_length, i;
 645   static am_entry3 *te, *te_next;
 646   static int j;
 647
 648   dp->eof = FALSE;              /* assume readdir not done */
 649
 650   if (amuDebug(D_READDIR))
 651     plog(XLOG_DEBUG, "amfs_readdir3_browsable gen=%lu, count=%d", (long unsigned) gen, count);
 652
 653   if (gen == 0) {
 654     size_t needed = needroom3();
 655     /*
 656      * In the default instance (which is used to start a search) we return
 657      * "." and "..".
 658      *
 659      * This assumes that the count is big enough to allow both "." and ".."
 660      * to be returned in a single packet.  If it isn't (which would be
 661      * fairly unbelievable) then tough.
 662      */
 663     dlog("%s: default search", __func__);
 664
 665     if (count < needed) {
 666       dlog("%s: not enough room %u < %zu", __func__, count, needed);
 667       return EINVAL;
 668     }
 669
 670     /*
 671      * compute # of entries to send in this chain.
 672      * heuristics: 128 bytes per entry.
 673      * This is too much probably, but it seems to work better because
 674      * of the re-entrant nature of nfs_readdir, and esp. on systems
 675      * like OpenBSD 2.2.
 676      */
 677     chain_length = count / 128;
 678
 679     /* reset static state counters */
 680     te = te_next = NULL;
 681
 682     dp->entries = ep;
 683
 684     /* construct "." */
 685     ep[0].fileid = mp->am_gen;
 686     ep[0].name = ".";
 687     ep[0].nextentry = &ep[1];
 688     ep[0].cookie = 0;
 689
 690     /* construct ".." */
 691     if (mp->am_parent)
 692       ep[1].fileid = mp->am_parent->am_gen;
 693     else
 694       ep[1].fileid = mp->am_gen;
 695
 696     ep[1].name = "..";
 697     ep[1].nextentry = NULL;
 698     ep[1].cookie = dotdotcookie;
 699
 700     /*
 701      * If map is browsable, call a function make_entry_chain() to construct
 702      * a linked list of unmounted keys, and return it.  Then link the chain
 703      * to the regular list.  Get the chain only once, but return
 704      * chunks of it each time.
 705      */
 706     te = make_entry_chain3(mp, dp->entries, fully_browsable);
 707     if (!te)
 708       return 0;
 709     if (amuDebug(D_READDIR)) {
 710       am_entry3 *ne;
 711       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 712         plog(XLOG_DEBUG, "gen1 key %4d \"%s\"", j++, ne->ne_name);
 713     }
 714
 715     /* return only "chain_length" entries */
 716     te_next = te;
 717     for (i=1; i<chain_length; ++i) {
 718       te_next = te_next->nextentry;
 719       if (!te_next)
 720         break;
 721     }
 722     if (te_next) {
 723       am_entry3 *te_saved = te_next->nextentry;
 724       te_next->nextentry = NULL; /* terminate "te" chain */
 725       te_next = te_saved;        /* save rest of "te" for next iteration */
 726       dp->eof = FALSE;           /* tell readdir there's more */
 727     } else {
 728       dp->eof = TRUE;            /* tell readdir that's it */
 729     }
 730     ep[1].nextentry = te;        /* append this chunk of "te" chain */
 731     if (amuDebug(D_READDIR)) {
 732       am_entry3 *ne;
 733       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 734         plog(XLOG_DEBUG, "gen2 key %4d \"%s\"", j++, ne->name);
 735       for (j = 0, ne = ep; ne; ne = ne->ne_nextentry) {
 736         plog(XLOG_DEBUG, "gen2+ key %4d \"%s\" fi=%lu ck=%lu",
 737              j++, ne->name, (long unsigned) ne->fileid, (long unsigned) ne->cookie);
 738       }
 739       plog(XLOG_DEBUG, "EOF is %d", dp->eof);
 740     }
 741     return 0;
 742   } /* end of "if (gen == 0)" statement */
 743
 744   dlog("%s: real child", __func__);
 745
 746   if (gen == DOT_DOT_COOKIE) {
 747     dlog("%s: End of readdir in %s", __func__, mp->am_path);
 748     dp->eof = TRUE;
 749     dp->entries = NULL;
 750     return 0;
 751   }
 752
 753   /*
 754    * If browsable directories, then continue serving readdir() with another
 755    * chunk of entries, starting from where we left off (when gen was equal
 756    * to 0).  Once again, assume last chunk served to readdir.
 757    */
 758   dp->eof = TRUE;
 759   dp->entries = ep;
 760
 761   te = te_next;                 /* reset 'te' from last saved te_next */
 762   if (!te) {                    /* another indicator of end of readdir */
 763     dp->entries = NULL;
 764     return 0;
 765   }
 766   /*
 767    * compute # of entries to send in this chain.
 768    * heuristics: 128 bytes per entry.
 769    */
 770   chain_length = count / 128;
 771
 772   /* return only "chain_length" entries */
 773   for (i = 1; i < chain_length; ++i) {
 774     te_next = te_next->nextentry;
 775     if (!te_next)
 776       break;
 777   }
 778   if (te_next) {
 779     am_entry3 *te_saved = te_next->nextentry;
 780     te_next->nextentry = NULL; /* terminate "te" chain */
 781     te_next = te_saved;         /* save rest of "te" for next iteration */
 782     dp->eof = FALSE;            /* tell readdir there's more */
 783   }
 784   ep = te;                      /* send next chunk of "te" chain */
 785   dp->entries = ep;
 786   if (amuDebug(D_READDIR)) {
 787     am_entry3 *ne;
 788     plog(XLOG_DEBUG,
 789          "entries=%p, te_next=%p, eof=%d", dp->entries, te_next, dp->eof);
 790     for (ne = te; ne; ne = ne->nextentry)
 791       plog(XLOG_DEBUG, "gen3 key %4d \"%s\"", j++, ne->name);
 792   }
 793   return 0;
 794 }
 795
 796 static int
 797 amfs_readdir3(am_node *mp, am_cookie3 cookie,
 798               am_dirlist3 *dp, am_entry3 *ep, u_int count)
 799 {
 800   uint64 gen = *(uint64 *) (uintptr_t) cookie;
 801   am_node *xp;
 802
 803   if (amuDebug(D_READDIR))
 804     plog(XLOG_DEBUG, "amfs_readdir3 gen=%lu, count=%d", (long unsigned) gen, count);
 805
 806   dp->eof = FALSE;              /* assume readdir not done */
 807
 808   /* when gen is 0, we start reading from the beginning of the directory */
 809   if (gen == 0) {
 810     size_t needed = needroom3();
 811     /*
 812      * In the default instance (which is used to start a search) we return
 813      * "." and "..".
 814      *
 815      * This assumes that the count is big enough to allow both "." and ".."
 816      * to be returned in a single packet.  If it isn't (which would be
 817      * fairly unbelievable) then tough.
 818      */
 819     dlog("%s: default search", __func__);
 820
 821     if (count < needed) {
 822       dlog("%s: not enough room %u < %zu", __func__, count, needed);
 823       return EINVAL;
 824     }
 825
 826     xp = next_nonerror_node(mp->am_child);
 827     dp->entries = ep;
 828
 829     /* construct "." */
 830     ep[0].fileid = mp->am_gen;
 831     ep[0].name = ".";
 832     ep[0].cookie = 0;
 833     ep[0].nextentry = &ep[1];
 834
 835     /* construct ".." */
 836     if (mp->am_parent)
 837       ep[1].fileid = mp->am_parent->am_gen;
 838     else
 839       ep[1].fileid = mp->am_gen;
 840     ep[1].name = "..";
 841     ep[1].nextentry = NULL;
 842     ep[1].cookie = (xp ? xp->am_gen : dotdotcookie);
 843
 844     if (!xp)
 845       dp->eof = TRUE;   /* by default assume readdir done */
 846
 847     if (amuDebug(D_READDIR)) {
 848       am_entry3 *ne;
 849       int j;
 850       for (j = 0, ne = ep; ne; ne = ne->nextentry) {
 851         plog(XLOG_DEBUG, "gen1 key %4d \"%s\" fi=%lu ck=%lu",
 852              j++, ne->name, (long unsigned) ne->fileid, (long unsigned) ne->cookie);
 853       }
 854     }
 855     return 0;
 856   }
 857   dlog("%s: real child", __func__);
 858
 859   if (gen == (uint64) DOT_DOT_COOKIE) {
 860     dlog("%s: End of readdir in %s", __func__, mp->am_path);
 861     dp->eof = TRUE;
 862     dp->entries = NULL;
 863     if (amuDebug(D_READDIR))
 864       plog(XLOG_DEBUG, "end of readdir eof=TRUE, dl_entries=0\n");
 865     return 0;
 866   }
 867
 868   /* non-browsable directories code */
 869   xp = mp->am_child;
 870   while (xp && xp->am_gen != gen)
 871     xp = xp->am_osib;
 872
 873   if (xp) {
 874     int nbytes = count / 2;     /* conservative */
 875     int todo = MAX_READDIR_ENTRIES;
 876
 877     dp->entries = ep;
 878     do {
 879       am_node *xp_next = next_nonerror_node(xp->am_osib);
 880
 881       if (xp_next) {
 882         ep->cookie = xp_next->am_gen;
 883       } else {
 884         ep->cookie = (uint64) dotdotcookie;
 885         dp->eof = TRUE;
 886       }
 887
 888       ep->fileid = xp->am_gen;
 889       ep->name = xp->am_name;
 890       nbytes -= sizeof(*ep) + 1;
 891       if (xp->am_name)
 892         nbytes -= strlen(xp->am_name);
 893
 894       xp = xp_next;
 895
 896       if (nbytes > 0 && !dp->dl_eof && todo > 1) {
 897         ep->nextentry = ep + 1;
 898         ep++;
 899         --todo;
 900       } else {
 901         todo = 0;
 902       }
 903     } while (todo > 0);
 904
 905     ep->nextentry = NULL;
 906
 907     if (amuDebug(D_READDIR)) {
 908       am_entry3 *ne;
 909       int j;
 910       for (j = 0, ne = ep; ne; ne = ne->nextentry) {
 911         plog(XLOG_DEBUG, "gen2 key %4d \"%s\" fi=%lu ck=%lu",
 912              j++, ne->name, (long unsigned) ne->fileid, (long unsigned) ne->cookie);
 913       }
 914     }
 915     return 0;
 916   }
 917   return ESTALE;
 918 }
 919
 920 /*
 921  * This readdir function which call a special version of it that allows
 922  * browsing if browsable_dirs=yes was set on the map.
 923  */
 924 int
 925 amfs_generic_readdir(am_node *mp, voidp cookie, voidp dp, voidp ep, u_int count)
 926 {
 927   int browsable, full;
 928
 929   /* check if map is browsable */
 930   browsable = 0;
 931   if (mp->am_al->al_mnt && mp->am_al->al_mnt->mf_mopts) {
 932     mntent_t mnt;
 933     mnt.mnt_opts = mp->am_al->al_mnt->mf_mopts;
 934     if (amu_hasmntopt(&mnt, "fullybrowsable"))
 935       browsable = 2;
 936     else if (amu_hasmntopt(&mnt, "browsable"))
 937       browsable = 1;
 938   }
 939   full = (browsable == 2);
 940
 941   if (nfs_dispatcher == nfs_program_2) {
 942     if (browsable)
 943       return amfs_readdir_browsable(mp, cookie, dp, ep, count, full);
 944     else
 945       return amfs_readdir(mp, cookie, dp, ep, count);
 946   } else {
 947     if (browsable)
 948       return amfs_readdir3_browsable(mp, (am_cookie3) (uintptr_t) cookie, dp, ep, count, full);
 949     else
 950       return amfs_readdir3(mp, (am_cookie3) (uintptr_t) cookie, dp, ep, count);
 951   }
 952 }