readdir.c revision 174294
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 ****************************************************************************/ 62static int key_already_in_chain(char *keyname, const nfsentry *chain); 63static nfsentry *make_entry_chain(am_node *mp, const nfsentry *current_chain, int fully_browsable); 64static 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 */ 75static int 76key_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 */ 94static nfsentry * 95make_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 */ 203static int 204amfs_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 */ 368int 369amfs_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} 499