1 /* $NetBSD: readdir.c,v 1.1.1.2 2009/03/20 20:26:50 christos Exp $ */ 2 3 /* 4 * Copyright (c) 1997-2009 Erez Zadok 5 * Copyright (c) 1990 Jan-Simon Pendry 6 * Copyright (c) 1990 Imperial College of Science, Technology & Medicine 7 * Copyright (c) 1990 The Regents of the University of California. 8 * All rights reserved. 9 * 10 * This code is derived from software contributed to Berkeley by 11 * Jan-Simon Pendry at Imperial College, London. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. All advertising materials mentioning features or use of this software 22 * must display the following acknowledgment: 23 * This product includes software developed by the University of 24 * California, Berkeley and its contributors. 25 * 4. Neither the name of the University nor the names of its contributors 26 * may be used to endorse or promote products derived from this software 27 * without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 39 * SUCH DAMAGE. 40 * 41 * 42 * File: am-utils/amd/readdir.c 43 * 44 */ 45 46 47 #ifdef HAVE_CONFIG_H 48 # include <config.h> 49 #endif /* HAVE_CONFIG_H */ 50 #include <am_defs.h> 51 #include <amd.h> 52 53 54 /**************************************************************************** 55 *** MACROS *** 56 ****************************************************************************/ 57 #define DOT_DOT_COOKIE (u_int) 1 58 #define MAX_CHAIN 2048 59 60 61 /**************************************************************************** 62 *** FORWARD DEFINITIONS *** 63 ****************************************************************************/ 64 static int key_already_in_chain(char *keyname, const nfsentry *chain); 65 static nfsentry *make_entry_chain(am_node *mp, const nfsentry *current_chain, int fully_browsable); 66 static int amfs_readdir_browsable(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count, int fully_browsable); 67 68 69 /**************************************************************************** 70 *** FUNCTIONS *** 71 ****************************************************************************/ 72 /* 73 * Was: NEW_TOPLVL_READDIR 74 * Search a chain for an entry with some name. 75 * -Erez Zadok <ezk@cs.columbia.edu> 76 */ 77 static int 78 key_already_in_chain(char *keyname, const nfsentry *chain) 79 { 80 const nfsentry *tmpchain = chain; 81 82 while (tmpchain) { 83 if (keyname && tmpchain->ne_name && STREQ(keyname, tmpchain->ne_name)) 84 return 1; 85 tmpchain = tmpchain->ne_nextentry; 86 } 87 88 return 0; 89 } 90 91 92 /* 93 * Create a chain of entries which are not linked. 94 * -Erez Zadok <ezk@cs.columbia.edu> 95 */ 96 static nfsentry * 97 make_entry_chain(am_node *mp, const nfsentry *current_chain, int fully_browsable) 98 { 99 static u_int last_cookie = (u_int) 2; /* monotonically increasing */ 100 static nfsentry chain[MAX_CHAIN]; 101 static int max_entries = MAX_CHAIN; 102 char *key; 103 int num_entries = 0, i; 104 u_int preflen = 0; 105 nfsentry *retval = (nfsentry *) NULL; 106 mntfs *mf; 107 mnt_map *mmp; 108 109 if (!mp) { 110 plog(XLOG_DEBUG, "make_entry_chain: mp is (NULL)"); 111 return retval; 112 } 113 mf = mp->am_mnt; 114 if (!mf) { 115 plog(XLOG_DEBUG, "make_entry_chain: mp->am_mnt is (NULL)"); 116 return retval; 117 } 118 mmp = (mnt_map *) mf->mf_private; 119 if (!mmp) { 120 plog(XLOG_DEBUG, "make_entry_chain: mp->am_mnt->mf_private is (NULL)"); 121 return retval; 122 } 123 124 if (mp->am_pref) 125 preflen = strlen(mp->am_pref); 126 127 /* iterate over keys */ 128 for (i = 0; i < NKVHASH; i++) { 129 kv *k; 130 for (k = mmp->kvhash[i]; k ; k = k->next) { 131 132 /* 133 * Skip unwanted entries which are either not real entries or 134 * very difficult to interpret (wildcards...) This test needs 135 * lots of improvement. Any takers? 136 */ 137 key = k->key; 138 if (!key) 139 continue; 140 141 /* Skip '/defaults' */ 142 if (STREQ(key, "/defaults")) 143 continue; 144 145 /* Skip '*' */ 146 if (!fully_browsable && strchr(key, '*')) 147 continue; 148 149 /* 150 * If the map has a prefix-string then check if the key starts with 151 * this string, and if it does, skip over this prefix. If it has a 152 * prefix and it doesn't match the start of the key, skip it. 153 */ 154 if (preflen) { 155 if (preflen > strlen(key)) 156 continue; 157 if (!NSTREQ(key, mp->am_pref, preflen)) 158 continue; 159 key += preflen; 160 } 161 162 /* no more '/' are allowed, unless browsable_dirs=full was used */ 163 if (!fully_browsable && strchr(key, '/')) 164 continue; 165 166 /* no duplicates allowed */ 167 if (key_already_in_chain(key, current_chain)) 168 continue; 169 170 /* fill in a cell and link the entry */ 171 if (num_entries >= max_entries) { 172 /* out of space */ 173 plog(XLOG_DEBUG, "make_entry_chain: no more space in chain"); 174 if (num_entries > 0) { 175 chain[num_entries - 1].ne_nextentry = NULL; 176 retval = &chain[0]; 177 } 178 return retval; 179 } 180 181 /* we have space. put entry in next cell */ 182 ++last_cookie; 183 chain[num_entries].ne_fileid = (u_int) last_cookie; 184 *(u_int *) chain[num_entries].ne_cookie = (u_int) 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 = NULL; 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 *(u_int *) ep[0].ne_cookie = 0; 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 = NULL; 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 plog(XLOG_DEBUG, "gen2+ key %4d \"%s\" fi=%d ck=%d", 307 j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie); 308 plog(XLOG_DEBUG, "EOF is %d", dp->dl_eof); 309 } 310 return 0; 311 } /* end of "if (gen == 0)" statement */ 312 313 dlog("amfs_readdir_browsable: real child"); 314 315 if (gen == DOT_DOT_COOKIE) { 316 dlog("amfs_readdir_browsable: End of readdir in %s", 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 366 /* 367 * This readdir function which call a special version of it that allows 368 * browsing if browsable_dirs=yes was set on the map. 369 */ 370 int 371 amfs_generic_readdir(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count) 372 { 373 u_int gen = *(u_int *) cookie; 374 am_node *xp; 375 mntent_t mnt; 376 377 dp->dl_eof = FALSE; /* assume readdir not done */ 378 379 /* check if map is browsable */ 380 if (mp->am_mnt && mp->am_mnt->mf_mopts) { 381 mnt.mnt_opts = mp->am_mnt->mf_mopts; 382 if (amu_hasmntopt(&mnt, "fullybrowsable")) 383 return amfs_readdir_browsable(mp, cookie, dp, ep, count, TRUE); 384 if (amu_hasmntopt(&mnt, "browsable")) 385 return amfs_readdir_browsable(mp, cookie, dp, ep, count, FALSE); 386 } 387 388 /* when gen is 0, we start reading from the beginning of the directory */ 389 if (gen == 0) { 390 /* 391 * In the default instance (which is used to start a search) we return 392 * "." and "..". 393 * 394 * This assumes that the count is big enough to allow both "." and ".." 395 * to be returned in a single packet. If it isn't (which would be 396 * fairly unbelievable) then tough. 397 */ 398 dlog("amfs_generic_readdir: default search"); 399 /* 400 * Check for enough room. This is extremely approximate but is more 401 * than enough space. Really need 2 times: 402 * 4byte fileid 403 * 4byte cookie 404 * 4byte name length 405 * 4byte name 406 * plus the dirlist structure */ 407 if (count < (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp)))) 408 return EINVAL; 409 410 xp = next_nonerror_node(mp->am_child); 411 dp->dl_entries = ep; 412 413 /* construct "." */ 414 ep[0].ne_fileid = mp->am_gen; 415 ep[0].ne_name = "."; 416 ep[0].ne_nextentry = &ep[1]; 417 *(u_int *) ep[0].ne_cookie = 0; 418 419 /* construct ".." */ 420 if (mp->am_parent) 421 ep[1].ne_fileid = mp->am_parent->am_gen; 422 else 423 ep[1].ne_fileid = mp->am_gen; 424 ep[1].ne_name = ".."; 425 ep[1].ne_nextentry = NULL; 426 *(u_int *) ep[1].ne_cookie = (xp ? xp->am_gen : DOT_DOT_COOKIE); 427 428 if (!xp) 429 dp->dl_eof = TRUE; /* by default assume readdir done */ 430 431 if (amuDebug(D_READDIR)) { 432 nfsentry *ne; 433 int j; 434 for (j = 0, ne = ep; ne; ne = ne->ne_nextentry) 435 plog(XLOG_DEBUG, "gen1 key %4d \"%s\" fi=%d ck=%d", 436 j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie); 437 } 438 return 0; 439 } 440 dlog("amfs_generic_readdir: real child"); 441 442 if (gen == DOT_DOT_COOKIE) { 443 dlog("amfs_generic_readdir: End of readdir in %s", mp->am_path); 444 dp->dl_eof = TRUE; 445 dp->dl_entries = NULL; 446 if (amuDebug(D_READDIR)) 447 plog(XLOG_DEBUG, "end of readdir eof=TRUE, dl_entries=0\n"); 448 return 0; 449 } 450 451 /* non-browsable directories code */ 452 xp = mp->am_child; 453 while (xp && xp->am_gen != gen) 454 xp = xp->am_osib; 455 456 if (xp) { 457 int nbytes = count / 2; /* conservative */ 458 int todo = MAX_READDIR_ENTRIES; 459 460 dp->dl_entries = ep; 461 do { 462 am_node *xp_next = next_nonerror_node(xp->am_osib); 463 464 if (xp_next) { 465 *(u_int *) ep->ne_cookie = xp_next->am_gen; 466 } else { 467 *(u_int *) ep->ne_cookie = DOT_DOT_COOKIE; 468 dp->dl_eof = TRUE; 469 } 470 471 ep->ne_fileid = xp->am_gen; 472 ep->ne_name = xp->am_name; 473 nbytes -= sizeof(*ep) + 1; 474 if (xp->am_name) 475 nbytes -= strlen(xp->am_name); 476 477 xp = xp_next; 478 479 if (nbytes > 0 && !dp->dl_eof && todo > 1) { 480 ep->ne_nextentry = ep + 1; 481 ep++; 482 --todo; 483 } else { 484 todo = 0; 485 } 486 } while (todo > 0); 487 488 ep->ne_nextentry = NULL; 489 490 if (amuDebug(D_READDIR)) { 491 nfsentry *ne; 492 int j; 493 for (j=0,ne=ep; ne; ne=ne->ne_nextentry) 494 plog(XLOG_DEBUG, "gen2 key %4d \"%s\" fi=%d ck=%d", 495 j++, ne->ne_name, ne->ne_fileid, *(u_int *)ne->ne_cookie); 496 } 497 return 0; 498 } 499 return ESTALE; 500 } 501