readdir.c revision 277879
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 66static 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 */ 76static int 77key_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 */ 95static nfsentry * 96make_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 */ 205static int 206amfs_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 */ 373int 374amfs_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} 510