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.
8 * This code is derived from software contributed to Berkeley by
9 * Jan-Simon Pendry at Imperial College, London.
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
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.
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
40 * File: am-utils/amd/readdir.c
47 #endif /* HAVE_CONFIG_H */
52 /****************************************************************************
54 ****************************************************************************/
55 #define DOT_DOT_COOKIE (u_int) 1
56 #define MAX_CHAIN 2048
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);
67 /****************************************************************************
69 ****************************************************************************/
71 * Was: NEW_TOPLVL_READDIR
72 * Search a chain for an entry with some name.
73 * -Erez Zadok <ezk@cs.columbia.edu>
76 key_already_in_chain(char *keyname, const nfsentry *chain)
78 const nfsentry *tmpchain = chain;
81 if (keyname && tmpchain->ne_name && STREQ(keyname, tmpchain->ne_name))
83 tmpchain = tmpchain->ne_nextentry;
91 * Create a chain of entries which are not linked.
92 * -Erez Zadok <ezk@cs.columbia.edu>
95 make_entry_chain(am_node *mp, const nfsentry *current_chain, int fully_browsable)
97 static u_int last_cookie = (u_int) 2; /* monotonically increasing */
98 static nfsentry chain[MAX_CHAIN];
99 static int max_entries = MAX_CHAIN;
101 int num_entries = 0, i;
103 nfsentry *retval = (nfsentry *) NULL;
108 plog(XLOG_DEBUG, "make_entry_chain: mp is (NULL)");
113 plog(XLOG_DEBUG, "make_entry_chain: mp->am_mnt is (NULL)");
116 mmp = (mnt_map *) mf->mf_private;
118 plog(XLOG_DEBUG, "make_entry_chain: mp->am_mnt->mf_private is (NULL)");
123 preflen = strlen(mp->am_pref);
125 /* iterate over keys */
126 for (i = 0; i < NKVHASH; i++) {
128 for (k = mmp->kvhash[i]; k ; k = k->next) {
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?
139 /* Skip '/defaults' */
140 if (STREQ(key, "/defaults"))
144 if (!fully_browsable && strchr(key, '*'))
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.
153 if (preflen > strlen(key))
155 if (!NSTREQ(key, mp->am_pref, preflen))
160 /* no more '/' are allowed, unless browsable_dirs=full was used */
161 if (!fully_browsable && strchr(key, '/'))
164 /* no duplicates allowed */
165 if (key_already_in_chain(key, current_chain))
168 /* fill in a cell and link the entry */
169 if (num_entries >= max_entries) {
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;
179 /* we have space. put entry in next cell */
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];
188 } /* end of "while (k)" */
189 } /* end of "for (i ... NKVHASH ..." */
191 /* terminate chain */
192 if (num_entries > 0) {
193 chain[num_entries - 1].ne_nextentry = 0;
202 /* This one is called only if map is browsable */
204 amfs_readdir_browsable(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count, int fully_browsable)
206 u_int gen = *(u_int *) cookie;
208 static nfsentry *te, *te_next;
211 dp->dl_eof = FALSE; /* assume readdir not done */
213 if (amuDebug(D_READDIR))
214 plog(XLOG_DEBUG, "amfs_readdir_browsable gen=%u, count=%d",
219 * In the default instance (which is used to start a search) we return
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.
226 dlog("amfs_readdir_browsable: default search");
228 * Check for enough room. This is extremely approximate but is more
229 * than enough space. Really need 2 times:
234 * plus the dirlist structure */
235 if (count < (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp))))
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
245 chain_length = count / 128;
247 /* reset static state counters */
253 ep[0].ne_fileid = mp->am_gen;
255 ep[0].ne_nextentry = &ep[1];
256 *(u_int *) ep[0].ne_cookie = 0;
260 ep[1].ne_fileid = mp->am_parent->am_gen;
262 ep[1].ne_fileid = mp->am_gen;
264 ep[1].ne_name = "..";
265 ep[1].ne_nextentry = 0;
266 *(u_int *) ep[1].ne_cookie = DOT_DOT_COOKIE;
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.
274 te = make_entry_chain(mp, dp->dl_entries, fully_browsable);
277 if (amuDebug(D_READDIR)) {
279 for (j = 0, ne = te; ne; ne = ne->ne_nextentry)
280 plog(XLOG_DEBUG, "gen1 key %4d \"%s\"", j++, ne->ne_name);
283 /* return only "chain_length" entries */
285 for (i=1; i<chain_length; ++i) {
286 te_next = te_next->ne_nextentry;
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 */
296 dp->dl_eof = TRUE; /* tell readdir that's it */
298 ep[1].ne_nextentry = te; /* append this chunk of "te" chain */
299 if (amuDebug(D_READDIR)) {
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);
309 } /* end of "if (gen == 0)" statement */
311 dlog("amfs_readdir_browsable: real child");
313 if (gen == DOT_DOT_COOKIE) {
314 dlog("amfs_readdir_browsable: End of readdir in %s", mp->am_path);
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.
328 te = te_next; /* reset 'te' from last saved te_next */
329 if (!te) { /* another indicator of end of readdir */
334 * compute # of entries to send in this chain.
335 * heuristics: 128 bytes per entry.
337 chain_length = count / 128;
339 /* return only "chain_length" entries */
340 for (i = 1; i < chain_length; ++i) {
341 te_next = te_next->ne_nextentry;
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 */
351 ep = te; /* send next chunk of "te" chain */
353 if (amuDebug(D_READDIR)) {
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);
365 * This readdir function which call a special version of it that allows
366 * browsing if browsable_dirs=yes was set on the map.
369 amfs_generic_readdir(am_node *mp, nfscookie cookie, nfsdirlist *dp, nfsentry *ep, u_int count)
371 u_int gen = *(u_int *) cookie;
375 dp->dl_eof = FALSE; /* assume readdir not done */
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);
386 /* when gen is 0, we start reading from the beginning of the directory */
389 * In the default instance (which is used to start a search) we return
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.
396 dlog("amfs_generic_readdir: default search");
398 * Check for enough room. This is extremely approximate but is more
399 * than enough space. Really need 2 times:
404 * plus the dirlist structure */
405 if (count < (2 * (2 * (sizeof(*ep) + sizeof("..") + 4) + sizeof(*dp))))
408 xp = next_nonerror_node(mp->am_child);
412 ep[0].ne_fileid = mp->am_gen;
414 ep[0].ne_nextentry = &ep[1];
415 *(u_int *) ep[0].ne_cookie = 0;
419 ep[1].ne_fileid = mp->am_parent->am_gen;
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);
427 dp->dl_eof = TRUE; /* by default assume readdir done */
429 if (amuDebug(D_READDIR)) {
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);
438 dlog("amfs_generic_readdir: real child");
440 if (gen == DOT_DOT_COOKIE) {
441 dlog("amfs_generic_readdir: End of readdir in %s", mp->am_path);
444 if (amuDebug(D_READDIR))
445 plog(XLOG_DEBUG, "end of readdir eof=TRUE, dl_entries=0\n");
449 /* non-browsable directories code */
451 while (xp && xp->am_gen != gen)
455 int nbytes = count / 2; /* conservative */
456 int todo = MAX_READDIR_ENTRIES;
460 am_node *xp_next = next_nonerror_node(xp->am_osib);
463 *(u_int *) ep->ne_cookie = xp_next->am_gen;
465 *(u_int *) ep->ne_cookie = DOT_DOT_COOKIE;
469 ep->ne_fileid = xp->am_gen;
470 ep->ne_name = xp->am_name;
471 nbytes -= sizeof(*ep) + 1;
473 nbytes -= strlen(xp->am_name);
477 if (nbytes > 0 && !dp->dl_eof && todo > 1) {
478 ep->ne_nextentry = ep + 1;
486 ep->ne_nextentry = 0;
488 if (amuDebug(D_READDIR)) {
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);