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