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 ****************************************************************************/
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);
65
66 static 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 */
76 static int
key_already_in_chain(char * keyname,const nfsentry * chain)77 key_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 */
95 static nfsentry *
make_entry_chain(am_node * mp,const nfsentry * current_chain,int fully_browsable)96 make_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 */
205 static int
amfs_readdir_browsable(am_node * mp,nfscookie cookie,nfsdirlist * dp,nfsentry * ep,u_int count,int fully_browsable)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 (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 */
373 int
amfs_generic_readdir(am_node * mp,nfscookie cookie,nfsdirlist * dp,nfsentry * ep,u_int count)374 amfs_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