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