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 = (u_int) last_cookie;
 180       *(u_int *) chain[num_entries].ne_cookie = (u_int) last_cookie;
 181       chain[num_entries].ne_name = key;
 182       if (num_entries < max_entries - 1) {      /* link to next one */
 183         chain[num_entries].ne_nextentry = &chain[num_entries + 1];
 184       }
 185       ++num_entries;
 186     } /* end of "while (k)" */
 187   } /* end of "for (i ... NKVHASH ..." */
 188
 189   /* terminate chain */
 190   if (num_entries > 0) {
 191     chain[num_entries - 1].ne_nextentry = NULL;
 192     retval = &chain[0];
 193   }
 194
 195   return retval;
 196 }
 197
 198
 199
 200 /* This one is called only if map is browsable */
 201 static int
 202 amfs_readdir_browsable(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count, int fully_browsable)
 203 {
 204   u_int gen = *(u_int *) (uintptr_t) cookie;
 205   int chain_length, i;
 206   static nfsentry *te, *te_next;
 207   static int j;
 208
 209   dp->dl_eof = FALSE;           /* assume readdir not done */
 210
 211   if (amuDebug(D_READDIR))
 212     plog(XLOG_DEBUG, "amfs_readdir_browsable gen=%u, count=%d",
 213          gen, count);
 214
 215   if (gen == 0) {
 216     /*
 217      * In the default instance (which is used to start a search) we return
 218      * "." and "..".
 219      *
 220      * This assumes that the count is big enough to allow both "." and ".."
 221      * to be returned in a single packet.  If it isn't (which would be
 222      * fairly unbelievable) then tough.
 223      */
 224     dlog("%s: default search", __func__);
 225     /*
 226      * Check for enough room.  This is extremely approximate but is more
 227      * than enough space.  Really need 2 times:
 228      *      4byte fileid
 229      *      4byte cookie
 230      *      4byte name length
 231      *      4byte name
 232      * plus the dirlist structure */
 233     if (count < (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp))))
 234       return EINVAL;
 235
 236     /*
 237      * compute # of entries to send in this chain.
 238      * heuristics: 128 bytes per entry.
 239      * This is too much probably, but it seems to work better because
 240      * of the re-entrant nature of nfs_readdir, and esp. on systems
 241      * like OpenBSD 2.2.
 242      */
 243     chain_length = count / 128;
 244
 245     /* reset static state counters */
 246     te = te_next = NULL;
 247
 248     dp->dl_entries = ep;
 249
 250     /* construct "." */
 251     ep[0].ne_fileid = mp->am_gen;
 252     ep[0].ne_name = ".";
 253     ep[0].ne_nextentry = &ep[1];
 254     *(u_int *) ep[0].ne_cookie = 0;
 255
 256     /* construct ".." */
 257     if (mp->am_parent)
 258       ep[1].ne_fileid = mp->am_parent->am_gen;
 259     else
 260       ep[1].ne_fileid = mp->am_gen;
 261
 262     ep[1].ne_name = "..";
 263     ep[1].ne_nextentry = NULL;
 264     (void)memcpy(ep[1].ne_cookie, &dotdotcookie, sizeof(dotdotcookie));
 265
 266     /*
 267      * If map is browsable, call a function make_entry_chain() to construct
 268      * a linked list of unmounted keys, and return it.  Then link the chain
 269      * to the regular list.  Get the chain only once, but return
 270      * chunks of it each time.
 271      */
 272     te = make_entry_chain(mp, dp->dl_entries, fully_browsable);
 273     if (!te)
 274       return 0;
 275     if (amuDebug(D_READDIR)) {
 276       nfsentry *ne;
 277       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 278         plog(XLOG_DEBUG, "gen1 key %4d \"%s\"", j++, ne->ne_name);
 279     }
 280
 281     /* return only "chain_length" entries */
 282     te_next = te;
 283     for (i=1; i<chain_length; ++i) {
 284       te_next = te_next->ne_nextentry;
 285       if (!te_next)
 286         break;
 287     }
 288     if (te_next) {
 289       nfsentry *te_saved = te_next->ne_nextentry;
 290       te_next->ne_nextentry = NULL; /* terminate "te" chain */
 291       te_next = te_saved;       /* save rest of "te" for next iteration */
 292       dp->dl_eof = FALSE;       /* tell readdir there's more */
 293     } else {
 294       dp->dl_eof = TRUE;        /* tell readdir that's it */
 295     }
 296     ep[1].ne_nextentry = te;    /* append this chunk of "te" chain */
 297     if (amuDebug(D_READDIR)) {
 298       nfsentry *ne;
 299       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 300         plog(XLOG_DEBUG, "gen2 key %4d \"%s\"", j++, ne->ne_name);
 301       for (j = 0, ne = ep; ne; ne = ne->ne_nextentry)
 302         plog(XLOG_DEBUG, "gen2+ key %4d \"%s\" fi=%d ck=%d",
 303              j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie);
 304       plog(XLOG_DEBUG, "EOF is %d", dp->dl_eof);
 305     }
 306     return 0;
 307   } /* end of "if (gen == 0)" statement */
 308
 309   dlog("%s: real child", __func__);
 310
 311   if (gen == DOT_DOT_COOKIE) {
 312     dlog("%s: End of readdir in %s", __func__, mp->am_path);
 313     dp->dl_eof = TRUE;
 314     dp->dl_entries = NULL;
 315     return 0;
 316   }
 317
 318   /*
 319    * If browsable directories, then continue serving readdir() with another
 320    * chunk of entries, starting from where we left off (when gen was equal
 321    * to 0).  Once again, assume last chunk served to readdir.
 322    */
 323   dp->dl_eof = TRUE;
 324   dp->dl_entries = ep;
 325
 326   te = te_next;                 /* reset 'te' from last saved te_next */
 327   if (!te) {                    /* another indicator of end of readdir */
 328     dp->dl_entries = NULL;
 329     return 0;
 330   }
 331   /*
 332    * compute # of entries to send in this chain.
 333    * heuristics: 128 bytes per entry.
 334    */
 335   chain_length = count / 128;
 336
 337   /* return only "chain_length" entries */
 338   for (i = 1; i < chain_length; ++i) {
 339     te_next = te_next->ne_nextentry;
 340     if (!te_next)
 341       break;
 342   }
 343   if (te_next) {
 344     nfsentry *te_saved = te_next->ne_nextentry;
 345     te_next->ne_nextentry = NULL; /* terminate "te" chain */
 346     te_next = te_saved;         /* save rest of "te" for next iteration */
 347     dp->dl_eof = FALSE;         /* tell readdir there's more */
 348   }
 349   ep = te;                      /* send next chunk of "te" chain */
 350   dp->dl_entries = ep;
 351   if (amuDebug(D_READDIR)) {
 352     nfsentry *ne;
 353     plog(XLOG_DEBUG, "dl_entries=%p, te_next=%p, dl_eof=%d",
 354          dp->dl_entries, te_next, dp->dl_eof);
 355     for (ne = te; ne; ne = ne->ne_nextentry)
 356       plog(XLOG_DEBUG, "gen3 key %4d \"%s\"", j++, ne->ne_name);
 357   }
 358   return 0;
 359 }
 360
 361 static int
 362 amfs_readdir(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count)
 363 {
 364   u_int gen = *(u_int *) (uintptr_t) cookie;
 365   am_node *xp;
 366
 367   dp->dl_eof = FALSE;           /* assume readdir not done */
 368
 369   /* when gen is 0, we start reading from the beginning of the directory */
 370   if (gen == 0) {
 371     /*
 372      * In the default instance (which is used to start a search) we return
 373      * "." and "..".
 374      *
 375      * This assumes that the count is big enough to allow both "." and ".."
 376      * to be returned in a single packet.  If it isn't (which would be
 377      * fairly unbelievable) then tough.
 378      */
 379     dlog("%s: default search", __func__);
 380     /*
 381      * Check for enough room.  This is extremely approximate but is more
 382      * than enough space.  Really need 2 times:
 383      *      4byte fileid
 384      *      4byte cookie
 385      *      4byte name length
 386      *      4byte name
 387      * plus the dirlist structure */
 388 #define NEEDROOM (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp)))
 389     if (count < NEEDROOM) {
 390       dlog("%s: not enough room %u < %zu", __func__, count, NEEDROOM);
 391       return EINVAL;
 392     }
 393
 394     xp = next_nonerror_node(mp->am_child);
 395     dp->dl_entries = ep;
 396
 397     /* construct "." */
 398     ep[0].ne_fileid = mp->am_gen;
 399     ep[0].ne_name = ".";
 400     ep[0].ne_nextentry = &ep[1];
 401     *(u_int *) ep[0].ne_cookie = 0;
 402
 403     /* construct ".." */
 404     if (mp->am_parent)
 405       ep[1].ne_fileid = mp->am_parent->am_gen;
 406     else
 407       ep[1].ne_fileid = mp->am_gen;
 408     ep[1].ne_name = "..";
 409     ep[1].ne_nextentry = NULL;
 410     (void)memcpy(ep[1].ne_cookie, (xp ? &xp->am_gen : &dotdotcookie),
 411       sizeof(dotdotcookie));
 412
 413     if (!xp)
 414       dp->dl_eof = TRUE;        /* by default assume readdir done */
 415
 416     if (amuDebug(D_READDIR)) {
 417       nfsentry *ne;
 418       int j;
 419       for (j = 0, ne = ep; ne; ne = ne->ne_nextentry)
 420         plog(XLOG_DEBUG, "gen1 key %4d \"%s\" fi=%d ck=%d",
 421              j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie);
 422     }
 423     return 0;
 424   }
 425   dlog("%s: real child", __func__);
 426
 427   if (gen == DOT_DOT_COOKIE) {
 428     dlog("%s: End of readdir in %s", __func__, mp->am_path);
 429     dp->dl_eof = TRUE;
 430     dp->dl_entries = NULL;
 431     if (amuDebug(D_READDIR))
 432       plog(XLOG_DEBUG, "end of readdir eof=TRUE, dl_entries=0\n");
 433     return 0;
 434   }
 435
 436   /* non-browsable directories code */
 437   xp = mp->am_child;
 438   while (xp && xp->am_gen != gen)
 439     xp = xp->am_osib;
 440
 441   if (xp) {
 442     int nbytes = count / 2;     /* conservative */
 443     int todo = MAX_READDIR_ENTRIES;
 444
 445     dp->dl_entries = ep;
 446     do {
 447       am_node *xp_next = next_nonerror_node(xp->am_osib);
 448
 449       if (xp_next) {
 450         *(u_int *) ep->ne_cookie = xp_next->am_gen;
 451       } else {
 452         *(u_int *) ep->ne_cookie = DOT_DOT_COOKIE;
 453         dp->dl_eof = TRUE;
 454       }
 455
 456       ep->ne_fileid = xp->am_gen;
 457       ep->ne_name = xp->am_name;
 458       nbytes -= sizeof(*ep) + 1;
 459       if (xp->am_name)
 460         nbytes -= strlen(xp->am_name);
 461
 462       xp = xp_next;
 463
 464       if (nbytes > 0 && !dp->dl_eof && todo > 1) {
 465         ep->ne_nextentry = ep + 1;
 466         ep++;
 467         --todo;
 468       } else {
 469         todo = 0;
 470       }
 471     } while (todo > 0);
 472
 473     ep->ne_nextentry = NULL;
 474
 475     if (amuDebug(D_READDIR)) {
 476       nfsentry *ne;
 477       int j;
 478       for (j=0,ne=ep; ne; ne=ne->ne_nextentry)
 479         plog(XLOG_DEBUG, "gen2 key %4d \"%s\" fi=%d ck=%d",
 480              j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie);
 481     }
 482     return 0;
 483   }
 484   return ESTALE;
 485 }
 486
 487 /*
 488  * Search a chain for an entry with some name.
 489  */
 490 static int
 491 key_already_in_chain3(char *keyname, const am_entry3 *chain)
 492 {
 493   const am_entry3 *tmpchain = chain;
 494
 495   while (tmpchain) {
 496     if (keyname && tmpchain->name && STREQ(keyname, tmpchain->name))
 497         return 1;
 498     tmpchain = tmpchain->nextentry;
 499   }
 500
 501   return 0;
 502 }
 503
 504 /*
 505  * Create a chain of entries which are not linked.
 506  */
 507 static am_entry3 *
 508 make_entry_chain3(am_node *mp, const am_entry3 *current_chain, int fully_browsable)
 509 {
 510   static uint64 last_cookie = (uint64) 2;       /* monotonically increasing */
 511   static am_entry3 chain[MAX_CHAIN];
 512   static int max_entries = MAX_CHAIN;
 513   char *key;
 514   int num_entries = 0, i;
 515   u_int preflen = 0;
 516   am_entry3 *retval = (am_entry3 *) NULL;
 517   mntfs *mf;
 518   mnt_map *mmp;
 519
 520   if (!mp) {
 521     plog(XLOG_DEBUG, "make_entry_chain3: mp is (NULL)");
 522     return retval;
 523   }
 524   mf = mp->am_al->al_mnt;
 525   if (!mf) {
 526     plog(XLOG_DEBUG, "make_entry_chain3: mp->am_al->al_mnt is (NULL)");
 527     return retval;
 528   }
 529   mmp = (mnt_map *) mf->mf_private;
 530   if (!mmp) {
 531     plog(XLOG_DEBUG, "make_entry_chain3: mp->am_al->al_mnt->mf_private is (NULL)");
 532     return retval;
 533   }
 534
 535   if (mp->am_pref)
 536     preflen = strlen(mp->am_pref);
 537
 538   /* iterate over keys */
 539   for (i = 0; i < NKVHASH; i++) {
 540     kv *k;
 541     for (k = mmp->kvhash[i]; k ; k = k->next) {
 542
 543       /*
 544        * Skip unwanted entries which are either not real entries or
 545        * very difficult to interpret (wildcards...)  This test needs
 546        * lots of improvement.  Any takers?
 547        */
 548       key = k->key;
 549       if (!key)
 550         continue;
 551
 552       /* Skip '/defaults' */
 553       if (STREQ(key, "/defaults"))
 554         continue;
 555
 556       /* Skip '*' */
 557       if (!fully_browsable && strchr(key, '*'))
 558         continue;
 559
 560       /*
 561        * If the map has a prefix-string then check if the key starts with
 562        * this string, and if it does, skip over this prefix.  If it has a
 563        * prefix and it doesn't match the start of the key, skip it.
 564        */
 565       if (preflen) {
 566         if (preflen > strlen(key))
 567           continue;
 568         if (!NSTREQ(key, mp->am_pref, preflen))
 569           continue;
 570         key += preflen;
 571       }
 572
 573       /* no more '/' are allowed, unless browsable_dirs=full was used */
 574       if (!fully_browsable && strchr(key, '/'))
 575         continue;
 576
 577       /* no duplicates allowed */
 578       if (key_already_in_chain3(key, current_chain))
 579         continue;
 580
 581       /* fill in a cell and link the entry */
 582       if (num_entries >= max_entries) {
 583         /* out of space */
 584         plog(XLOG_DEBUG, "make_entry_chain3: no more space in chain");
 585         if (num_entries > 0) {
 586           chain[num_entries - 1].nextentry = NULL;
 587           retval = &chain[0];
 588         }
 589         return retval;
 590       }
 591
 592       /* we have space.  put entry in next cell */
 593       ++last_cookie;
 594       chain[num_entries].fileid = last_cookie;
 595       chain[num_entries].cookie = last_cookie;
 596       chain[num_entries].name = key;
 597       if (num_entries < max_entries - 1) {      /* link to next one */
 598         chain[num_entries].nextentry = &chain[num_entries + 1];
 599       }
 600       ++num_entries;
 601     } /* end of "while (k)" */
 602   } /* end of "for (i ... NKVHASH ..." */
 603
 604   /* terminate chain */
 605   if (num_entries > 0) {
 606     chain[num_entries - 1].nextentry = NULL;
 607     retval = &chain[0];
 608   }
 609
 610   return retval;
 611 }
 612
 613 static size_t needroom3(void)
 614 {
 615   /*
 616    * Check for enough room.  This is extremely approximate but should
 617    * be enough space.  Really need 2 times:
 618    *      (8byte fileid
 619    *      8byte cookie
 620    *      8byte name pointer
 621    *      8byte next entry addres) = sizeof(am_entry3)
 622    *      2byte name + 1byte terminator
 623    * plus the size of the am_dirlist3 structure */
 624   return ((2 * ((sizeof(am_entry3) + sizeof("..") + 1))) + sizeof(am_dirlist3));
 625 }
 626
 627 /* This one is called only if map is browsable */
 628 static int
 629 amfs_readdir3_browsable(am_node *mp, am_cookie3 cookie,
 630                         am_dirlist3 *dp, am_entry3 *ep, u_int count,
 631                         int fully_browsable)
 632 {
 633   uint64 gen = *(uint64 *) (uintptr_t) cookie;
 634   int chain_length, i;
 635   static am_entry3 *te, *te_next;
 636   static int j;
 637
 638   dp->eof = FALSE;              /* assume readdir not done */
 639
 640   if (amuDebug(D_READDIR))
 641     plog(XLOG_DEBUG, "amfs_readdir3_browsable gen=%lu, count=%d", (long unsigned) gen, count);
 642
 643   if (gen == 0) {
 644     size_t needed = needroom3();
 645     /*
 646      * In the default instance (which is used to start a search) we return
 647      * "." and "..".
 648      *
 649      * This assumes that the count is big enough to allow both "." and ".."
 650      * to be returned in a single packet.  If it isn't (which would be
 651      * fairly unbelievable) then tough.
 652      */
 653     dlog("%s: default search", __func__);
 654
 655     if (count < needed) {
 656       dlog("%s: not enough room %u < %zu", __func__, count, needed);
 657       return EINVAL;
 658     }
 659
 660     /*
 661      * compute # of entries to send in this chain.
 662      * heuristics: 128 bytes per entry.
 663      * This is too much probably, but it seems to work better because
 664      * of the re-entrant nature of nfs_readdir, and esp. on systems
 665      * like OpenBSD 2.2.
 666      */
 667     chain_length = count / 128;
 668
 669     /* reset static state counters */
 670     te = te_next = NULL;
 671
 672     dp->entries = ep;
 673
 674     /* construct "." */
 675     ep[0].fileid = mp->am_gen;
 676     ep[0].name = ".";
 677     ep[0].nextentry = &ep[1];
 678     ep[0].cookie = 0;
 679
 680     /* construct ".." */
 681     if (mp->am_parent)
 682       ep[1].fileid = mp->am_parent->am_gen;
 683     else
 684       ep[1].fileid = mp->am_gen;
 685
 686     ep[1].name = "..";
 687     ep[1].nextentry = NULL;
 688     ep[1].cookie = dotdotcookie;
 689
 690     /*
 691      * If map is browsable, call a function make_entry_chain() to construct
 692      * a linked list of unmounted keys, and return it.  Then link the chain
 693      * to the regular list.  Get the chain only once, but return
 694      * chunks of it each time.
 695      */
 696     te = make_entry_chain3(mp, dp->entries, fully_browsable);
 697     if (!te)
 698       return 0;
 699     if (amuDebug(D_READDIR)) {
 700       am_entry3 *ne;
 701       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 702         plog(XLOG_DEBUG, "gen1 key %4d \"%s\"", j++, ne->ne_name);
 703     }
 704
 705     /* return only "chain_length" entries */
 706     te_next = te;
 707     for (i=1; i<chain_length; ++i) {
 708       te_next = te_next->nextentry;
 709       if (!te_next)
 710         break;
 711     }
 712     if (te_next) {
 713       am_entry3 *te_saved = te_next->nextentry;
 714       te_next->nextentry = NULL; /* terminate "te" chain */
 715       te_next = te_saved;        /* save rest of "te" for next iteration */
 716       dp->eof = FALSE;           /* tell readdir there's more */
 717     } else {
 718       dp->eof = TRUE;            /* tell readdir that's it */
 719     }
 720     ep[1].nextentry = te;        /* append this chunk of "te" chain */
 721     if (amuDebug(D_READDIR)) {
 722       am_entry3 *ne;
 723       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 724         plog(XLOG_DEBUG, "gen2 key %4d \"%s\"", j++, ne->name);
 725       for (j = 0, ne = ep; ne; ne = ne->ne_nextentry) {
 726         plog(XLOG_DEBUG, "gen2+ key %4d \"%s\" fi=%lu ck=%lu",
 727              j++, ne->name, (long unsigned) ne->fileid, (long unsigned) ne->cookie);
 728       }
 729       plog(XLOG_DEBUG, "EOF is %d", dp->eof);
 730     }
 731     return 0;
 732   } /* end of "if (gen == 0)" statement */
 733
 734   dlog("%s: real child", __func__);
 735
 736   if (gen == DOT_DOT_COOKIE) {
 737     dlog("%s: End of readdir in %s", __func__, mp->am_path);
 738     dp->eof = TRUE;
 739     dp->entries = NULL;
 740     return 0;
 741   }
 742
 743   /*
 744    * If browsable directories, then continue serving readdir() with another
 745    * chunk of entries, starting from where we left off (when gen was equal
 746    * to 0).  Once again, assume last chunk served to readdir.
 747    */
 748   dp->eof = TRUE;
 749   dp->entries = ep;
 750
 751   te = te_next;                 /* reset 'te' from last saved te_next */
 752   if (!te) {                    /* another indicator of end of readdir */
 753     dp->entries = NULL;
 754     return 0;
 755   }
 756   /*
 757    * compute # of entries to send in this chain.
 758    * heuristics: 128 bytes per entry.
 759    */
 760   chain_length = count / 128;
 761
 762   /* return only "chain_length" entries */
 763   for (i = 1; i < chain_length; ++i) {
 764     te_next = te_next->nextentry;
 765     if (!te_next)
 766       break;
 767   }
 768   if (te_next) {
 769     am_entry3 *te_saved = te_next->nextentry;
 770     te_next->nextentry = NULL; /* terminate "te" chain */
 771     te_next = te_saved;         /* save rest of "te" for next iteration */
 772     dp->eof = FALSE;            /* tell readdir there's more */
 773   }
 774   ep = te;                      /* send next chunk of "te" chain */
 775   dp->entries = ep;
 776   if (amuDebug(D_READDIR)) {
 777     am_entry3 *ne;
 778     plog(XLOG_DEBUG,
 779          "entries=%p, te_next=%p, eof=%d", dp->entries, te_next, dp->eof);
 780     for (ne = te; ne; ne = ne->nextentry)
 781       plog(XLOG_DEBUG, "gen3 key %4d \"%s\"", j++, ne->name);
 782   }
 783   return 0;
 784 }
 785
 786 static int
 787 amfs_readdir3(am_node *mp, am_cookie3 cookie,
 788               am_dirlist3 *dp, am_entry3 *ep, u_int count)
 789 {
 790   uint64 gen = *(uint64 *) (uintptr_t) cookie;
 791   am_node *xp;
 792
 793   if (amuDebug(D_READDIR))
 794     plog(XLOG_DEBUG, "amfs_readdir3 gen=%lu, count=%d", (long unsigned) gen, count);
 795
 796   dp->eof = FALSE;              /* assume readdir not done */
 797
 798   /* when gen is 0, we start reading from the beginning of the directory */
 799   if (gen == 0) {
 800     size_t needed = needroom3();
 801     /*
 802      * In the default instance (which is used to start a search) we return
 803      * "." and "..".
 804      *
 805      * This assumes that the count is big enough to allow both "." and ".."
 806      * to be returned in a single packet.  If it isn't (which would be
 807      * fairly unbelievable) then tough.
 808      */
 809     dlog("%s: default search", __func__);
 810
 811     if (count < needed) {
 812       dlog("%s: not enough room %u < %zu", __func__, count, needed);
 813       return EINVAL;
 814     }
 815
 816     xp = next_nonerror_node(mp->am_child);
 817     dp->entries = ep;
 818
 819     /* construct "." */
 820     ep[0].fileid = mp->am_gen;
 821     ep[0].name = ".";
 822     ep[0].cookie = 0;
 823     ep[0].nextentry = &ep[1];
 824
 825     /* construct ".." */
 826     if (mp->am_parent)
 827       ep[1].fileid = mp->am_parent->am_gen;
 828     else
 829       ep[1].fileid = mp->am_gen;
 830     ep[1].name = "..";
 831     ep[1].nextentry = NULL;
 832     ep[1].cookie = (xp ? xp->am_gen : dotdotcookie);
 833
 834     if (!xp)
 835       dp->eof = TRUE;   /* by default assume readdir done */
 836
 837     if (amuDebug(D_READDIR)) {
 838       am_entry3 *ne;
 839       int j;
 840       for (j = 0, ne = ep; ne; ne = ne->nextentry) {
 841         plog(XLOG_DEBUG, "gen1 key %4d \"%s\" fi=%lu ck=%lu",
 842              j++, ne->name, (long unsigned) ne->fileid, (long unsigned) ne->cookie);
 843       }
 844     }
 845     return 0;
 846   }
 847   dlog("%s: real child", __func__);
 848
 849   if (gen == (uint64) DOT_DOT_COOKIE) {
 850     dlog("%s: End of readdir in %s", __func__, mp->am_path);
 851     dp->eof = TRUE;
 852     dp->entries = NULL;
 853     if (amuDebug(D_READDIR))
 854       plog(XLOG_DEBUG, "end of readdir eof=TRUE, dl_entries=0\n");
 855     return 0;
 856   }
 857
 858   /* non-browsable directories code */
 859   xp = mp->am_child;
 860   while (xp && xp->am_gen != gen)
 861     xp = xp->am_osib;
 862
 863   if (xp) {
 864     int nbytes = count / 2;     /* conservative */
 865     int todo = MAX_READDIR_ENTRIES;
 866
 867     dp->entries = ep;
 868     do {
 869       am_node *xp_next = next_nonerror_node(xp->am_osib);
 870
 871       if (xp_next) {
 872         ep->cookie = xp_next->am_gen;
 873       } else {
 874         ep->cookie = (uint64) dotdotcookie;
 875         dp->eof = TRUE;
 876       }
 877
 878       ep->fileid = xp->am_gen;
 879       ep->name = xp->am_name;
 880       nbytes -= sizeof(*ep) + 1;
 881       if (xp->am_name)
 882         nbytes -= strlen(xp->am_name);
 883
 884       xp = xp_next;
 885
 886       if (nbytes > 0 && !dp->dl_eof && todo > 1) {
 887         ep->nextentry = ep + 1;
 888         ep++;
 889         --todo;
 890       } else {
 891         todo = 0;
 892       }
 893     } while (todo > 0);
 894
 895     ep->nextentry = NULL;
 896
 897     if (amuDebug(D_READDIR)) {
 898       am_entry3 *ne;
 899       int j;
 900       for (j = 0, ne = ep; ne; ne = ne->nextentry) {
 901         plog(XLOG_DEBUG, "gen2 key %4d \"%s\" fi=%lu ck=%lu",
 902              j++, ne->name, (long unsigned) ne->fileid, (long unsigned) ne->cookie);
 903       }
 904     }
 905     return 0;
 906   }
 907   return ESTALE;
 908 }
 909
 910 /*
 911  * This readdir function which call a special version of it that allows
 912  * browsing if browsable_dirs=yes was set on the map.
 913  */
 914 int
 915 amfs_generic_readdir(am_node *mp, voidp cookie, voidp dp, voidp ep, u_int count)
 916 {
 917   int browsable, full;
 918
 919   /* check if map is browsable */
 920   browsable = 0;
 921   if (mp->am_al->al_mnt && mp->am_al->al_mnt->mf_mopts) {
 922     mntent_t mnt;
 923     mnt.mnt_opts = mp->am_al->al_mnt->mf_mopts;
 924     if (amu_hasmntopt(&mnt, "fullybrowsable"))
 925       browsable = 2;
 926     else if (amu_hasmntopt(&mnt, "browsable"))
 927       browsable = 1;
 928   }
 929   full = (browsable == 2);
 930
 931   if (nfs_dispatcher == nfs_program_2) {
 932     if (browsable)
 933       return amfs_readdir_browsable(mp, cookie, dp, ep, count, full);
 934     else
 935       return amfs_readdir(mp, cookie, dp, ep, count);
 936   } else {
 937     if (browsable)
 938       return amfs_readdir3_browsable(mp, (am_cookie3) (uintptr_t) cookie, dp, ep, count, full);
 939     else
 940       return amfs_readdir3(mp, (am_cookie3) (uintptr_t) cookie, dp, ep, count);
 941   }
 942 }