contrib/amd/amd/readdir.c

   1 /*
   2  * Copyright (c) 1997-2006 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. All advertising materials mentioning features or use of this software
  20  *    must display the following acknowledgment:
  21  *      This product includes software developed by the University of
  22  *      California, Berkeley and its contributors.
  23  * 4. Neither the name of the University nor the names of its contributors
  24  *    may be used to endorse or promote products derived from this software
  25  *    without specific prior written permission.
  26  *
  27  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37  * SUCH DAMAGE.
  38  *
  39  *
  40  * File: am-utils/amd/readdir.c
  41  *
  42  */
  43
  44
  45 #ifdef HAVE_CONFIG_H
  46 # include <config.h>
  47 #endif /* HAVE_CONFIG_H */
  48 #include <am_defs.h>
  49 #include <amd.h>
  50
  51
  52 /****************************************************************************
  53  *** MACROS                                                               ***
  54  ****************************************************************************/
  55 #define DOT_DOT_COOKIE  (u_int) 1
  56 #define MAX_CHAIN       2048
  57
  58
  59 /****************************************************************************
  60  *** FORWARD DEFINITIONS                                                  ***
  61  ****************************************************************************/
  62 static int key_already_in_chain(char *keyname, const nfsentry *chain);
  63 static nfsentry *make_entry_chain(am_node *mp, const nfsentry *current_chain, int fully_browsable);
  64 static int amfs_readdir_browsable(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count, int fully_browsable);
  65
  66
  67 /****************************************************************************
  68  *** FUNCTIONS                                                             ***
  69  ****************************************************************************/
  70 /*
  71  * Was: NEW_TOPLVL_READDIR
  72  * Search a chain for an entry with some name.
  73  * -Erez Zadok <ezk@cs.columbia.edu>
  74  */
  75 static int
  76 key_already_in_chain(char *keyname, const nfsentry *chain)
  77 {
  78   const nfsentry *tmpchain = chain;
  79
  80   while (tmpchain) {
  81     if (keyname && tmpchain->ne_name && STREQ(keyname, tmpchain->ne_name))
  82         return 1;
  83     tmpchain = tmpchain->ne_nextentry;
  84   }
  85
  86   return 0;
  87 }
  88
  89
  90 /*
  91  * Create a chain of entries which are not linked.
  92  * -Erez Zadok <ezk@cs.columbia.edu>
  93  */
  94 static nfsentry *
  95 make_entry_chain(am_node *mp, const nfsentry *current_chain, int fully_browsable)
  96 {
  97   static u_int last_cookie = (u_int) 2; /* monotonically increasing */
  98   static nfsentry chain[MAX_CHAIN];
  99   static int max_entries = MAX_CHAIN;
 100   char *key;
 101   int num_entries = 0, i;
 102   u_int preflen = 0;
 103   nfsentry *retval = (nfsentry *) NULL;
 104   mntfs *mf;
 105   mnt_map *mmp;
 106
 107   if (!mp) {
 108     plog(XLOG_DEBUG, "make_entry_chain: mp is (NULL)");
 109     return retval;
 110   }
 111   mf = mp->am_mnt;
 112   if (!mf) {
 113     plog(XLOG_DEBUG, "make_entry_chain: mp->am_mnt is (NULL)");
 114     return retval;
 115   }
 116   mmp = (mnt_map *) mf->mf_private;
 117   if (!mmp) {
 118     plog(XLOG_DEBUG, "make_entry_chain: mp->am_mnt->mf_private is (NULL)");
 119     return retval;
 120   }
 121
 122   if (mp->am_pref)
 123     preflen = strlen(mp->am_pref);
 124
 125   /* iterate over keys */
 126   for (i = 0; i < NKVHASH; i++) {
 127     kv *k;
 128     for (k = mmp->kvhash[i]; k ; k = k->next) {
 129
 130       /*
 131        * Skip unwanted entries which are either not real entries or
 132        * very difficult to interpret (wildcards...)  This test needs
 133        * lots of improvement.  Any takers?
 134        */
 135       key = k->key;
 136       if (!key)
 137         continue;
 138
 139       /* Skip '/defaults' */
 140       if (STREQ(key, "/defaults"))
 141         continue;
 142
 143       /* Skip '*' */
 144       if (!fully_browsable && strchr(key, '*'))
 145         continue;
 146
 147       /*
 148        * If the map has a prefix-string then check if the key starts with
 149        * this string, and if it does, skip over this prefix.  If it has a
 150        * prefix and it doesn't match the start of the key, skip it.
 151        */
 152       if (preflen) {
 153         if (preflen > strlen(key))
 154           continue;
 155         if (!NSTREQ(key, mp->am_pref, preflen))
 156           continue;
 157         key += preflen;
 158       }
 159
 160       /* no more '/' are allowed, unless browsable_dirs=full was used */
 161       if (!fully_browsable && strchr(key, '/'))
 162         continue;
 163
 164       /* no duplicates allowed */
 165       if (key_already_in_chain(key, current_chain))
 166         continue;
 167
 168       /* fill in a cell and link the entry */
 169       if (num_entries >= max_entries) {
 170         /* out of space */
 171         plog(XLOG_DEBUG, "make_entry_chain: no more space in chain");
 172         if (num_entries > 0) {
 173           chain[num_entries - 1].ne_nextentry = 0;
 174           retval = &chain[0];
 175         }
 176         return retval;
 177       }
 178
 179       /* we have space.  put entry in next cell */
 180       ++last_cookie;
 181       chain[num_entries].ne_fileid = (u_int) last_cookie;
 182       *(u_int *) chain[num_entries].ne_cookie = (u_int) last_cookie;
 183       chain[num_entries].ne_name = key;
 184       if (num_entries < max_entries - 1) {      /* link to next one */
 185         chain[num_entries].ne_nextentry = &chain[num_entries + 1];
 186       }
 187       ++num_entries;
 188     } /* end of "while (k)" */
 189   } /* end of "for (i ... NKVHASH ..." */
 190
 191   /* terminate chain */
 192   if (num_entries > 0) {
 193     chain[num_entries - 1].ne_nextentry = 0;
 194     retval = &chain[0];
 195   }
 196
 197   return retval;
 198 }
 199
 200
 201
 202 /* This one is called only if map is browsable */
 203 static int
 204 amfs_readdir_browsable(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count, int fully_browsable)
 205 {
 206   u_int gen = *(u_int *) cookie;
 207   int chain_length, i;
 208   static nfsentry *te, *te_next;
 209   static int j;
 210
 211   dp->dl_eof = FALSE;           /* assume readdir not done */
 212
 213   if (amuDebug(D_READDIR))
 214     plog(XLOG_DEBUG, "amfs_readdir_browsable gen=%u, count=%d",
 215          gen, count);
 216
 217   if (gen == 0) {
 218     /*
 219      * In the default instance (which is used to start a search) we return
 220      * "." and "..".
 221      *
 222      * This assumes that the count is big enough to allow both "." and ".."
 223      * to be returned in a single packet.  If it isn't (which would be
 224      * fairly unbelievable) then tough.
 225      */
 226     dlog("amfs_readdir_browsable: default search");
 227     /*
 228      * Check for enough room.  This is extremely approximate but is more
 229      * than enough space.  Really need 2 times:
 230      *      4byte fileid
 231      *      4byte cookie
 232      *      4byte name length
 233      *      4byte name
 234      * plus the dirlist structure */
 235     if (count < (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp))))
 236       return EINVAL;
 237
 238     /*
 239      * compute # of entries to send in this chain.
 240      * heuristics: 128 bytes per entry.
 241      * This is too much probably, but it seems to work better because
 242      * of the re-entrant nature of nfs_readdir, and esp. on systems
 243      * like OpenBSD 2.2.
 244      */
 245     chain_length = count / 128;
 246
 247     /* reset static state counters */
 248     te = te_next = NULL;
 249
 250     dp->dl_entries = ep;
 251
 252     /* construct "." */
 253     ep[0].ne_fileid = mp->am_gen;
 254     ep[0].ne_name = ".";
 255     ep[0].ne_nextentry = &ep[1];
 256     *(u_int *) ep[0].ne_cookie = 0;
 257
 258     /* construct ".." */
 259     if (mp->am_parent)
 260       ep[1].ne_fileid = mp->am_parent->am_gen;
 261     else
 262       ep[1].ne_fileid = mp->am_gen;
 263
 264     ep[1].ne_name = "..";
 265     ep[1].ne_nextentry = 0;
 266     *(u_int *) ep[1].ne_cookie = DOT_DOT_COOKIE;
 267
 268     /*
 269      * If map is browsable, call a function make_entry_chain() to construct
 270      * a linked list of unmounted keys, and return it.  Then link the chain
 271      * to the regular list.  Get the chain only once, but return
 272      * chunks of it each time.
 273      */
 274     te = make_entry_chain(mp, dp->dl_entries, fully_browsable);
 275     if (!te)
 276       return 0;
 277     if (amuDebug(D_READDIR)) {
 278       nfsentry *ne;
 279       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 280         plog(XLOG_DEBUG, "gen1 key %4d \"%s\"", j++, ne->ne_name);
 281     }
 282
 283     /* return only "chain_length" entries */
 284     te_next = te;
 285     for (i=1; i<chain_length; ++i) {
 286       te_next = te_next->ne_nextentry;
 287       if (!te_next)
 288         break;
 289     }
 290     if (te_next) {
 291       nfsentry *te_saved = te_next->ne_nextentry;
 292       te_next->ne_nextentry = NULL; /* terminate "te" chain */
 293       te_next = te_saved;       /* save rest of "te" for next iteration */
 294       dp->dl_eof = FALSE;       /* tell readdir there's more */
 295     } else {
 296       dp->dl_eof = TRUE;        /* tell readdir that's it */
 297     }
 298     ep[1].ne_nextentry = te;    /* append this chunk of "te" chain */
 299     if (amuDebug(D_READDIR)) {
 300       nfsentry *ne;
 301       for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
 302         plog(XLOG_DEBUG, "gen2 key %4d \"%s\"", j++, ne->ne_name);
 303       for (j = 0, ne = ep; ne; ne = ne->ne_nextentry)
 304         plog(XLOG_DEBUG, "gen2+ key %4d \"%s\" fi=%d ck=%d",
 305              j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie);
 306       plog(XLOG_DEBUG, "EOF is %d", dp->dl_eof);
 307     }
 308     return 0;
 309   } /* end of "if (gen == 0)" statement */
 310
 311   dlog("amfs_readdir_browsable: real child");
 312
 313   if (gen == DOT_DOT_COOKIE) {
 314     dlog("amfs_readdir_browsable: End of readdir in %s", mp->am_path);
 315     dp->dl_eof = TRUE;
 316     dp->dl_entries = 0;
 317     return 0;
 318   }
 319
 320   /*
 321    * If browsable directories, then continue serving readdir() with another
 322    * chunk of entries, starting from where we left off (when gen was equal
 323    * to 0).  Once again, assume last chunk served to readdir.
 324    */
 325   dp->dl_eof = TRUE;
 326   dp->dl_entries = ep;
 327
 328   te = te_next;                 /* reset 'te' from last saved te_next */
 329   if (!te) {                    /* another indicator of end of readdir */
 330     dp->dl_entries = 0;
 331     return 0;
 332   }
 333   /*
 334    * compute # of entries to send in this chain.
 335    * heuristics: 128 bytes per entry.
 336    */
 337   chain_length = count / 128;
 338
 339   /* return only "chain_length" entries */
 340   for (i = 1; i < chain_length; ++i) {
 341     te_next = te_next->ne_nextentry;
 342     if (!te_next)
 343       break;
 344   }
 345   if (te_next) {
 346     nfsentry *te_saved = te_next->ne_nextentry;
 347     te_next->ne_nextentry = NULL; /* terminate "te" chain */
 348     te_next = te_saved;         /* save rest of "te" for next iteration */
 349     dp->dl_eof = FALSE;         /* tell readdir there's more */
 350   }
 351   ep = te;                      /* send next chunk of "te" chain */
 352   dp->dl_entries = ep;
 353   if (amuDebug(D_READDIR)) {
 354     nfsentry *ne;
 355     plog(XLOG_DEBUG, "dl_entries=%p, te_next=%p, dl_eof=%d",
 356          dp->dl_entries, te_next, dp->dl_eof);
 357     for (ne = te; ne; ne = ne->ne_nextentry)
 358       plog(XLOG_DEBUG, "gen3 key %4d \"%s\"", j++, ne->ne_name);
 359   }
 360   return 0;
 361 }
 362
 363
 364 /*
 365  * This readdir function which call a special version of it that allows
 366  * browsing if browsable_dirs=yes was set on the map.
 367  */
 368 int
 369 amfs_generic_readdir(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count)
 370 {
 371   u_int gen = *(u_int *) cookie;
 372   am_node *xp;
 373   mntent_t mnt;
 374
 375   dp->dl_eof = FALSE;           /* assume readdir not done */
 376
 377   /* check if map is browsable */
 378   if (mp->am_mnt && mp->am_mnt->mf_mopts) {
 379     mnt.mnt_opts = mp->am_mnt->mf_mopts;
 380     if (amu_hasmntopt(&mnt, "fullybrowsable"))
 381       return amfs_readdir_browsable(mp, cookie, dp, ep, count, TRUE);
 382     if (amu_hasmntopt(&mnt, "browsable"))
 383       return amfs_readdir_browsable(mp, cookie, dp, ep, count, FALSE);
 384   }
 385
 386   /* when gen is 0, we start reading from the beginning of the directory */
 387   if (gen == 0) {
 388     /*
 389      * In the default instance (which is used to start a search) we return
 390      * "." and "..".
 391      *
 392      * This assumes that the count is big enough to allow both "." and ".."
 393      * to be returned in a single packet.  If it isn't (which would be
 394      * fairly unbelievable) then tough.
 395      */
 396     dlog("amfs_generic_readdir: default search");
 397     /*
 398      * Check for enough room.  This is extremely approximate but is more
 399      * than enough space.  Really need 2 times:
 400      *      4byte fileid
 401      *      4byte cookie
 402      *      4byte name length
 403      *      4byte name
 404      * plus the dirlist structure */
 405     if (count < (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp))))
 406       return EINVAL;
 407
 408     xp = next_nonerror_node(mp->am_child);
 409     dp->dl_entries = ep;
 410
 411     /* construct "." */
 412     ep[0].ne_fileid = mp->am_gen;
 413     ep[0].ne_name = ".";
 414     ep[0].ne_nextentry = &ep[1];
 415     *(u_int *) ep[0].ne_cookie = 0;
 416
 417     /* construct ".." */
 418     if (mp->am_parent)
 419       ep[1].ne_fileid = mp->am_parent->am_gen;
 420     else
 421       ep[1].ne_fileid = mp->am_gen;
 422     ep[1].ne_name = "..";
 423     ep[1].ne_nextentry = 0;
 424     *(u_int *) ep[1].ne_cookie = (xp ? xp->am_gen : DOT_DOT_COOKIE);
 425
 426     if (!xp)
 427       dp->dl_eof = TRUE;        /* by default assume readdir done */
 428
 429     if (amuDebug(D_READDIR)) {
 430       nfsentry *ne;
 431       int j;
 432       for (j = 0, ne = ep; ne; ne = ne->ne_nextentry)
 433         plog(XLOG_DEBUG, "gen1 key %4d \"%s\" fi=%d ck=%d",
 434              j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie);
 435     }
 436     return 0;
 437   }
 438   dlog("amfs_generic_readdir: real child");
 439
 440   if (gen == DOT_DOT_COOKIE) {
 441     dlog("amfs_generic_readdir: End of readdir in %s", mp->am_path);
 442     dp->dl_eof = TRUE;
 443     dp->dl_entries = 0;
 444     if (amuDebug(D_READDIR))
 445       plog(XLOG_DEBUG, "end of readdir eof=TRUE, dl_entries=0\n");
 446     return 0;
 447   }
 448
 449   /* non-browsable directories code */
 450   xp = mp->am_child;
 451   while (xp && xp->am_gen != gen)
 452     xp = xp->am_osib;
 453
 454   if (xp) {
 455     int nbytes = count / 2;     /* conservative */
 456     int todo = MAX_READDIR_ENTRIES;
 457
 458     dp->dl_entries = ep;
 459     do {
 460       am_node *xp_next = next_nonerror_node(xp->am_osib);
 461
 462       if (xp_next) {
 463         *(u_int *) ep->ne_cookie = xp_next->am_gen;
 464       } else {
 465         *(u_int *) ep->ne_cookie = DOT_DOT_COOKIE;
 466         dp->dl_eof = TRUE;
 467       }
 468
 469       ep->ne_fileid = xp->am_gen;
 470       ep->ne_name = xp->am_name;
 471       nbytes -= sizeof(*ep) + 1;
 472       if (xp->am_name)
 473         nbytes -= strlen(xp->am_name);
 474
 475       xp = xp_next;
 476
 477       if (nbytes > 0 && !dp->dl_eof && todo > 1) {
 478         ep->ne_nextentry = ep + 1;
 479         ep++;
 480         --todo;
 481       } else {
 482         todo = 0;
 483       }
 484     } while (todo > 0);
 485
 486     ep->ne_nextentry = 0;
 487
 488     if (amuDebug(D_READDIR)) {
 489       nfsentry *ne;
 490       int j;
 491       for (j=0,ne=ep; ne; ne=ne->ne_nextentry)
 492         plog(XLOG_DEBUG, "gen2 key %4d \"%s\" fi=%d ck=%d",
 493              j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie);
 494     }
 495     return 0;
 496   }
 497   return ESTALE;
 498 }