1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1990, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 * $OpenBSD: fts.c,v 1.22 1999/10/03 19:22:22 millert Exp $
32 */
33
34 #include "namespace.h"
35 #include <sys/param.h>
36 #include <sys/mount.h>
37 #include <sys/stat.h>
38
39 #include <dirent.h>
40 #include <errno.h>
41 #include <fcntl.h>
42 #include <fts.h>
43 #include <stdalign.h>
44 #include <stdlib.h>
45 #include <string.h>
46 #include <unistd.h>
47 #include "un-namespace.h"
48
49 #include "gen-private.h"
50
51 #ifdef __BLOCKS__
52 #include <Block.h>
53 #else
54 #include "block_abi.h"
55 typedef DECLARE_BLOCK(int, fts_block,
56 const FTSENT * const *, const FTSENT * const *);
57 void qsort_b(void *, size_t, size_t, fts_block);
58 #endif /* __BLOCKS__ */
59 /* only present if linked with blocks runtime */
60 void *_Block_copy(const void *) __weak_symbol;
61 void _Block_release(const void *) __weak_symbol;
62 extern void *_NSConcreteGlobalBlock[] __weak_symbol;
63
64 static FTSENT *fts_alloc(FTS *, char *, size_t);
65 static FTSENT *fts_build(FTS *, int);
66 static void fts_lfree(FTSENT *);
67 static void fts_load(FTS *, FTSENT *);
68 static size_t fts_maxarglen(char * const *);
69 static void fts_padjust(FTS *, FTSENT *);
70 static int fts_palloc(FTS *, size_t);
71 static FTSENT *fts_sort(FTS *, FTSENT *, size_t);
72 static int fts_stat(FTS *, FTSENT *, int, int);
73 static int fts_safe_changedir(FTS *, FTSENT *, int, char *);
74 static int fts_ufslinks(FTS *, const FTSENT *);
75
76 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
77
78 #define CLR(opt) (sp->fts_options &= ~(opt))
79 #define ISSET(opt) (sp->fts_options & (opt))
80 #define SET(opt) (sp->fts_options |= (opt))
81
82 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
83
84 /* fts_build flags */
85 #define BCHILD 1 /* fts_children */
86 #define BNAMES 2 /* fts_children, names only */
87 #define BREAD 3 /* fts_read */
88
89 /*
90 * Internal representation of an FTS, including extra implementation
91 * details. The FTS returned from fts_open points to this structure's
92 * ftsp_fts member (and can be cast to an _fts_private as required)
93 */
94 struct _fts_private {
95 FTS ftsp_fts;
96 struct statfs ftsp_statfs;
97 dev_t ftsp_dev;
98 int ftsp_linksreliable;
99 };
100
101 /*
102 * The "FTS_NOSTAT" option can avoid a lot of calls to stat(2) if it
103 * knows that a directory could not possibly have subdirectories. This
104 * is decided by looking at the link count: a subdirectory would
105 * increment its parent's link count by virtue of its own ".." entry.
106 * This assumption only holds for UFS-like filesystems that implement
107 * links and directories this way, so we must punt for others.
108 */
109
110 static const char *ufslike_filesystems[] = {
111 "ufs",
112 "zfs",
113 "nfs",
114 "ext2fs",
115 0
116 };
117
118 static FTS *
__fts_open(FTS * sp,char * const * argv)119 __fts_open(FTS *sp, char * const *argv)
120 {
121 FTSENT *p, *root;
122 FTSENT *parent, *tmp;
123 size_t len, nitems;
124
125 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
126 if (ISSET(FTS_LOGICAL))
127 SET(FTS_NOCHDIR);
128
129 /* NOSTAT_TYPE implies NOSTAT */
130 if (ISSET(FTS_NOSTAT_TYPE))
131 SET(FTS_NOSTAT);
132
133 /*
134 * Start out with 1K of path space, and enough, in any case,
135 * to hold the user's paths.
136 */
137 if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
138 goto mem1;
139
140 /* Allocate/initialize root's parent. */
141 if ((parent = fts_alloc(sp, "", 0)) == NULL)
142 goto mem2;
143 parent->fts_level = FTS_ROOTPARENTLEVEL;
144
145 /* Shush, GCC. */
146 tmp = NULL;
147
148 /* Allocate/initialize root(s). */
149 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
150 len = strlen(*argv);
151
152 p = fts_alloc(sp, *argv, len);
153 p->fts_level = FTS_ROOTLEVEL;
154 p->fts_parent = parent;
155 p->fts_accpath = p->fts_name;
156 p->fts_info = fts_stat(sp, p,
157 ISSET(FTS_COMFOLLOWDIR) ? -1 : ISSET(FTS_COMFOLLOW),
158 -1);
159
160 /* Command-line "." and ".." are real directories. */
161 if (p->fts_info == FTS_DOT)
162 p->fts_info = FTS_D;
163
164 /*
165 * If comparison routine supplied, traverse in sorted
166 * order; otherwise traverse in the order specified.
167 */
168 if (sp->fts_compar) {
169 p->fts_link = root;
170 root = p;
171 } else {
172 p->fts_link = NULL;
173 if (root == NULL)
174 tmp = root = p;
175 else {
176 tmp->fts_link = p;
177 tmp = p;
178 }
179 }
180 }
181 if (sp->fts_compar && nitems > 1)
182 root = fts_sort(sp, root, nitems);
183
184 /*
185 * Allocate a dummy pointer and make fts_read think that we've just
186 * finished the node before the root(s); set p->fts_info to FTS_INIT
187 * so that everything about the "current" node is ignored.
188 */
189 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
190 goto mem3;
191 sp->fts_cur->fts_link = root;
192 sp->fts_cur->fts_info = FTS_INIT;
193
194 /*
195 * If using chdir(2), grab a file descriptor pointing to dot to ensure
196 * that we can get back here; this could be avoided for some paths,
197 * but almost certainly not worth the effort. Slashes, symbolic links,
198 * and ".." are all fairly nasty problems. Note, if we can't get the
199 * descriptor we run anyway, just more slowly.
200 */
201 if (!ISSET(FTS_NOCHDIR) &&
202 (sp->fts_rfd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0)
203 SET(FTS_NOCHDIR);
204
205 return (sp);
206
207 mem3: fts_lfree(root);
208 free(parent);
209 mem2: free(sp->fts_path);
210 mem1: free(sp);
211 return (NULL);
212 }
213
214 FTS *
fts_open(char * const * argv,int options,int (* compar)(const FTSENT * const *,const FTSENT * const *))215 fts_open(char * const *argv, int options,
216 int (*compar)(const FTSENT * const *, const FTSENT * const *))
217 {
218 struct _fts_private *priv;
219 FTS *sp;
220
221 /* Options check. */
222 if (options & ~FTS_OPTIONMASK) {
223 errno = EINVAL;
224 return (NULL);
225 }
226
227 /* fts_open() requires at least one path */
228 if (*argv == NULL) {
229 errno = EINVAL;
230 return (NULL);
231 }
232
233 /* Allocate/initialize the stream. */
234 if ((priv = calloc(1, sizeof(*priv))) == NULL)
235 return (NULL);
236 sp = &priv->ftsp_fts;
237 sp->fts_compar = compar;
238 sp->fts_options = options;
239
240 return (__fts_open(sp, argv));
241 }
242
243 #ifdef __BLOCKS__
244 FTS *
245 fts_open_b(char * const *argv, int options,
246 int (^compar)(const FTSENT * const *, const FTSENT * const *))
247 #else
248 FTS *
249 fts_open_b(char * const *argv, int options, fts_block compar)
250 #endif /* __BLOCKS__ */
251 {
252 struct _fts_private *priv;
253 FTS *sp;
254
255 /* No blocks, no problems. */
256 if (compar == NULL)
257 return (fts_open(argv, options, NULL));
258
259 /* Avoid segfault if blocks runtime is missing. */
260 if (_Block_copy == NULL) {
261 errno = ENOSYS;
262 return (NULL);
263 }
264
265 /* Options check. */
266 if (options & ~FTS_OPTIONMASK) {
267 errno = EINVAL;
268 return (NULL);
269 }
270
271 /* fts_open() requires at least one path */
272 if (*argv == NULL) {
273 errno = EINVAL;
274 return (NULL);
275 }
276
277 /* Allocate/initialize the stream. */
278 if ((priv = calloc(1, sizeof(*priv))) == NULL)
279 return (NULL);
280 sp = &priv->ftsp_fts;
281 #ifdef __BLOCKS__
282 compar = Block_copy(compar);
283 #else
284 if (compar->isa != &_NSConcreteGlobalBlock)
285 compar = _Block_copy(compar);
286 #endif /* __BLOCKS__ */
287 if (compar == NULL) {
288 free(priv);
289 return (NULL);
290 }
291 sp->fts_compar_b = compar;
292 sp->fts_options = options | FTS_COMPAR_B;
293
294 if ((sp = __fts_open(sp, argv)) == NULL) {
295 #ifdef __BLOCKS__
296 Block_release(compar);
297 #else
298 if (compar->isa != &_NSConcreteGlobalBlock)
299 _Block_release(compar);
300 #endif /* __BLOCKS__ */
301 }
302 return (sp);
303 }
304
305 static void
fts_load(FTS * sp,FTSENT * p)306 fts_load(FTS *sp, FTSENT *p)
307 {
308 size_t len;
309 char *cp;
310
311 /*
312 * Load the stream structure for the next traversal. Since we don't
313 * actually enter the directory until after the preorder visit, set
314 * the fts_accpath field specially so the chdir gets done to the right
315 * place and the user can access the first node. From fts_open it's
316 * known that the path will fit.
317 */
318 len = p->fts_pathlen = p->fts_namelen;
319 memmove(sp->fts_path, p->fts_name, len + 1);
320 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
321 len = strlen(++cp);
322 memmove(p->fts_name, cp, len + 1);
323 p->fts_namelen = len;
324 }
325 p->fts_accpath = p->fts_path = sp->fts_path;
326 sp->fts_dev = p->fts_dev;
327 }
328
329 int
fts_close(FTS * sp)330 fts_close(FTS *sp)
331 {
332 FTSENT *freep, *p;
333 int saved_errno;
334
335 /*
336 * This still works if we haven't read anything -- the dummy structure
337 * points to the root list, so we step through to the end of the root
338 * list which has a valid parent pointer.
339 */
340 if (sp->fts_cur) {
341 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
342 freep = p;
343 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
344 free(freep);
345 }
346 free(p);
347 }
348
349 /* Free up child linked list, sort array, path buffer. */
350 if (sp->fts_child)
351 fts_lfree(sp->fts_child);
352 if (sp->fts_array)
353 free(sp->fts_array);
354 free(sp->fts_path);
355
356 /* Free up any block pointer. */
357 if (ISSET(FTS_COMPAR_B) && sp->fts_compar_b != NULL) {
358 #ifdef __BLOCKS__
359 Block_release(sp->fts_compar_b);
360 #else
361 if (((fts_block)(sp->fts_compar_b))->isa !=
362 &_NSConcreteGlobalBlock)
363 _Block_release(sp->fts_compar_b);
364 #endif /* __BLOCKS__ */
365 }
366
367 /* Return to original directory, save errno if necessary. */
368 if (!ISSET(FTS_NOCHDIR)) {
369 saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
370 (void)_close(sp->fts_rfd);
371
372 /* Set errno and return. */
373 if (saved_errno != 0) {
374 /* Free up the stream pointer. */
375 free(sp);
376 errno = saved_errno;
377 return (-1);
378 }
379 }
380
381 /* Free up the stream pointer. */
382 free(sp);
383 return (0);
384 }
385
386 /*
387 * Special case of "/" at the end of the path so that slashes aren't
388 * appended which would cause paths to be written as "....//foo".
389 */
390 #define NAPPEND(p) \
391 (p->fts_path[p->fts_pathlen - 1] == '/' \
392 ? p->fts_pathlen - 1 : p->fts_pathlen)
393
394 FTSENT *
fts_read(FTS * sp)395 fts_read(FTS *sp)
396 {
397 FTSENT *p, *tmp;
398 int instr;
399 char *t;
400 int saved_errno;
401
402 /* If finished or unrecoverable error, return NULL. */
403 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
404 return (NULL);
405
406 /* Set current node pointer. */
407 p = sp->fts_cur;
408
409 /* Save and zero out user instructions. */
410 instr = p->fts_instr;
411 p->fts_instr = FTS_NOINSTR;
412
413 /* Any type of file may be re-visited; re-stat and re-turn. */
414 if (instr == FTS_AGAIN) {
415 p->fts_info = fts_stat(sp, p, 0, -1);
416 return (p);
417 }
418
419 /*
420 * Following a symlink -- SLNONE test allows application to see
421 * SLNONE and recover. If indirecting through a symlink, have
422 * keep a pointer to current location. If unable to get that
423 * pointer, follow fails.
424 */
425 if (instr == FTS_FOLLOW &&
426 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
427 p->fts_info = fts_stat(sp, p, 1, -1);
428 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
429 if ((p->fts_symfd = _open(".", O_RDONLY | O_CLOEXEC,
430 0)) < 0) {
431 p->fts_errno = errno;
432 p->fts_info = FTS_ERR;
433 } else
434 p->fts_flags |= FTS_SYMFOLLOW;
435 }
436 return (p);
437 }
438
439 /* Directory in pre-order. */
440 if (p->fts_info == FTS_D) {
441 /* If skipped or crossed mount point, do post-order visit. */
442 if (instr == FTS_SKIP ||
443 (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
444 if (p->fts_flags & FTS_SYMFOLLOW)
445 (void)_close(p->fts_symfd);
446 if (sp->fts_child) {
447 fts_lfree(sp->fts_child);
448 sp->fts_child = NULL;
449 }
450 p->fts_info = FTS_DP;
451 return (p);
452 }
453
454 /* Rebuild if only read the names and now traversing. */
455 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
456 CLR(FTS_NAMEONLY);
457 fts_lfree(sp->fts_child);
458 sp->fts_child = NULL;
459 }
460
461 /*
462 * Cd to the subdirectory.
463 *
464 * If have already read and now fail to chdir, whack the list
465 * to make the names come out right, and set the parent errno
466 * so the application will eventually get an error condition.
467 * Set the FTS_DONTCHDIR flag so that when we logically change
468 * directories back to the parent we don't do a chdir.
469 *
470 * If haven't read do so. If the read fails, fts_build sets
471 * FTS_STOP or the fts_info field of the node.
472 */
473 if (sp->fts_child != NULL) {
474 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
475 p->fts_errno = errno;
476 p->fts_flags |= FTS_DONTCHDIR;
477 for (p = sp->fts_child; p != NULL;
478 p = p->fts_link)
479 p->fts_accpath =
480 p->fts_parent->fts_accpath;
481 }
482 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
483 if (ISSET(FTS_STOP))
484 return (NULL);
485 return (p);
486 }
487 p = sp->fts_child;
488 sp->fts_child = NULL;
489 goto name;
490 }
491
492 /* Move to the next node on this level. */
493 next: tmp = p;
494 if ((p = p->fts_link) != NULL) {
495 /*
496 * If reached the top, return to the original directory (or
497 * the root of the tree), and load the paths for the next root.
498 */
499 if (p->fts_level == FTS_ROOTLEVEL) {
500 if (FCHDIR(sp, sp->fts_rfd)) {
501 SET(FTS_STOP);
502 return (NULL);
503 }
504 free(tmp);
505 fts_load(sp, p);
506 return (sp->fts_cur = p);
507 }
508
509 /*
510 * User may have called fts_set on the node. If skipped,
511 * ignore. If followed, get a file descriptor so we can
512 * get back if necessary.
513 */
514 if (p->fts_instr == FTS_SKIP) {
515 free(tmp);
516 goto next;
517 }
518 if (p->fts_instr == FTS_FOLLOW) {
519 p->fts_info = fts_stat(sp, p, 1, -1);
520 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
521 if ((p->fts_symfd =
522 _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) {
523 p->fts_errno = errno;
524 p->fts_info = FTS_ERR;
525 } else
526 p->fts_flags |= FTS_SYMFOLLOW;
527 }
528 p->fts_instr = FTS_NOINSTR;
529 }
530
531 free(tmp);
532
533 name: t = sp->fts_path + NAPPEND(p->fts_parent);
534 *t++ = '/';
535 memmove(t, p->fts_name, p->fts_namelen + 1);
536 return (sp->fts_cur = p);
537 }
538
539 /* Move up to the parent node. */
540 p = tmp->fts_parent;
541
542 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
543 /*
544 * Done; free everything up and set errno to 0 so the user
545 * can distinguish between error and EOF.
546 */
547 free(tmp);
548 free(p);
549 errno = 0;
550 return (sp->fts_cur = NULL);
551 }
552
553 /* NUL terminate the pathname. */
554 sp->fts_path[p->fts_pathlen] = '\0';
555
556 /*
557 * Return to the parent directory. If at a root node or came through
558 * a symlink, go back through the file descriptor. Otherwise, cd up
559 * one directory.
560 */
561 if (p->fts_level == FTS_ROOTLEVEL) {
562 if (FCHDIR(sp, sp->fts_rfd)) {
563 SET(FTS_STOP);
564 return (NULL);
565 }
566 } else if (p->fts_flags & FTS_SYMFOLLOW) {
567 if (FCHDIR(sp, p->fts_symfd)) {
568 saved_errno = errno;
569 (void)_close(p->fts_symfd);
570 errno = saved_errno;
571 SET(FTS_STOP);
572 return (NULL);
573 }
574 (void)_close(p->fts_symfd);
575 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
576 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
577 SET(FTS_STOP);
578 return (NULL);
579 }
580 free(tmp);
581 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
582 return (sp->fts_cur = p);
583 }
584
585 /*
586 * Fts_set takes the stream as an argument although it's not used in this
587 * implementation; it would be necessary if anyone wanted to add global
588 * semantics to fts using fts_set. An error return is allowed for similar
589 * reasons.
590 */
591 /* ARGSUSED */
592 int
fts_set(FTS * sp,FTSENT * p,int instr)593 fts_set(FTS *sp, FTSENT *p, int instr)
594 {
595 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
596 instr != FTS_NOINSTR && instr != FTS_SKIP) {
597 errno = EINVAL;
598 return (1);
599 }
600 p->fts_instr = instr;
601 return (0);
602 }
603
604 FTSENT *
fts_children(FTS * sp,int instr)605 fts_children(FTS *sp, int instr)
606 {
607 FTSENT *p;
608 int fd, rc, serrno;
609
610 if (instr != 0 && instr != FTS_NAMEONLY) {
611 errno = EINVAL;
612 return (NULL);
613 }
614
615 /* Set current node pointer. */
616 p = sp->fts_cur;
617
618 /*
619 * Errno set to 0 so user can distinguish empty directory from
620 * an error.
621 */
622 errno = 0;
623
624 /* Fatal errors stop here. */
625 if (ISSET(FTS_STOP))
626 return (NULL);
627
628 /* Return logical hierarchy of user's arguments. */
629 if (p->fts_info == FTS_INIT)
630 return (p->fts_link);
631
632 /*
633 * If not a directory being visited in pre-order, stop here. Could
634 * allow FTS_DNR, assuming the user has fixed the problem, but the
635 * same effect is available with FTS_AGAIN.
636 */
637 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
638 return (NULL);
639
640 /* Free up any previous child list. */
641 if (sp->fts_child != NULL)
642 fts_lfree(sp->fts_child);
643
644 if (instr == FTS_NAMEONLY) {
645 SET(FTS_NAMEONLY);
646 instr = BNAMES;
647 } else
648 instr = BCHILD;
649
650 /*
651 * If using chdir on a relative path and called BEFORE fts_read does
652 * its chdir to the root of a traversal, we can lose -- we need to
653 * chdir into the subdirectory, and we don't know where the current
654 * directory is, so we can't get back so that the upcoming chdir by
655 * fts_read will work.
656 */
657 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
658 ISSET(FTS_NOCHDIR))
659 return (sp->fts_child = fts_build(sp, instr));
660
661 if ((fd = _open(".", O_RDONLY | O_CLOEXEC, 0)) < 0)
662 return (NULL);
663 sp->fts_child = fts_build(sp, instr);
664 serrno = (sp->fts_child == NULL) ? errno : 0;
665 rc = fchdir(fd);
666 if (rc < 0 && serrno == 0)
667 serrno = errno;
668 (void)_close(fd);
669 errno = serrno;
670 if (rc < 0)
671 return (NULL);
672 return (sp->fts_child);
673 }
674
675 #ifndef fts_get_clientptr
676 #error "fts_get_clientptr not defined"
677 #endif
678
679 void *
680 (fts_get_clientptr)(FTS *sp)
681 {
682
683 return (fts_get_clientptr(sp));
684 }
685
686 #ifndef fts_get_stream
687 #error "fts_get_stream not defined"
688 #endif
689
690 FTS *
691 (fts_get_stream)(FTSENT *p)
692 {
693 return (fts_get_stream(p));
694 }
695
696 void
fts_set_clientptr(FTS * sp,void * clientptr)697 fts_set_clientptr(FTS *sp, void *clientptr)
698 {
699
700 sp->fts_clientptr = clientptr;
701 }
702
703 static struct dirent *
fts_safe_readdir(DIR * dirp,int * readdir_errno)704 fts_safe_readdir(DIR *dirp, int *readdir_errno)
705 {
706 struct dirent *ret;
707
708 errno = 0;
709 if (!dirp)
710 return (NULL);
711 ret = readdir(dirp);
712 *readdir_errno = errno;
713 return (ret);
714 }
715
716 /*
717 * This is the tricky part -- do not casually change *anything* in here. The
718 * idea is to build the linked list of entries that are used by fts_children
719 * and fts_read. There are lots of special cases.
720 *
721 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
722 * set and it's a physical walk (so that symbolic links can't be directories),
723 * we can do things quickly. First, if it's a 4.4BSD file system, the type
724 * of the file is in the directory entry. Otherwise, we assume that the number
725 * of subdirectories in a node is equal to the number of links to the parent.
726 * The former skips all stat calls. The latter skips stat calls in any leaf
727 * directories and for any files after the subdirectories in the directory have
728 * been found, cutting the stat calls by about 2/3.
729 */
730 static FTSENT *
fts_build(FTS * sp,int type)731 fts_build(FTS *sp, int type)
732 {
733 struct dirent *dp;
734 FTSENT *p, *head;
735 FTSENT *cur, *tail;
736 DIR *dirp;
737 void *oldaddr;
738 char *cp;
739 int cderrno, descend, oflag, saved_errno, nostat, doadjust,
740 readdir_errno;
741 long level;
742 long nlinks; /* has to be signed because -1 is a magic value */
743 size_t dnamlen, len, maxlen, nitems;
744
745 /* Set current node pointer. */
746 cur = sp->fts_cur;
747
748 /*
749 * Open the directory for reading. If this fails, we're done.
750 * If being called from fts_read, set the fts_info field.
751 */
752 if (ISSET(FTS_WHITEOUT))
753 oflag = DTF_NODUP;
754 else
755 oflag = DTF_HIDEW | DTF_NODUP;
756 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
757 if (type == BREAD) {
758 cur->fts_info = FTS_DNR;
759 cur->fts_errno = errno;
760 }
761 return (NULL);
762 }
763
764 /*
765 * Nlinks is the number of possible entries of type directory in the
766 * directory if we're cheating on stat calls, 0 if we're not doing
767 * any stat calls at all, -1 if we're doing stats on everything.
768 */
769 if (type == BNAMES) {
770 nlinks = 0;
771 /* Be quiet about nostat, GCC. */
772 nostat = 0;
773 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
774 if (fts_ufslinks(sp, cur))
775 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
776 else
777 nlinks = -1;
778 nostat = 1;
779 } else {
780 nlinks = -1;
781 nostat = 0;
782 }
783
784 #ifdef notdef
785 (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
786 (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
787 ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
788 #endif
789 /*
790 * If we're going to need to stat anything or we want to descend
791 * and stay in the directory, chdir. If this fails we keep going,
792 * but set a flag so we don't chdir after the post-order visit.
793 * We won't be able to stat anything, but we can still return the
794 * names themselves. Note, that since fts_read won't be able to
795 * chdir into the directory, it will have to return different path
796 * names than before, i.e. "a/b" instead of "b". Since the node
797 * has already been visited in pre-order, have to wait until the
798 * post-order visit to return the error. There is a special case
799 * here, if there was nothing to stat then it's not an error to
800 * not be able to stat. This is all fairly nasty. If a program
801 * needed sorted entries or stat information, they had better be
802 * checking FTS_NS on the returned nodes.
803 */
804 cderrno = 0;
805 if (nlinks || type == BREAD) {
806 if (fts_safe_changedir(sp, cur, _dirfd(dirp), NULL)) {
807 if (nlinks && type == BREAD)
808 cur->fts_errno = errno;
809 cur->fts_flags |= FTS_DONTCHDIR;
810 descend = 0;
811 cderrno = errno;
812 } else
813 descend = 1;
814 } else
815 descend = 0;
816
817 /*
818 * Figure out the max file name length that can be stored in the
819 * current path -- the inner loop allocates more path as necessary.
820 * We really wouldn't have to do the maxlen calculations here, we
821 * could do them in fts_read before returning the path, but it's a
822 * lot easier here since the length is part of the dirent structure.
823 *
824 * If not changing directories set a pointer so that can just append
825 * each new name into the path.
826 */
827 len = NAPPEND(cur);
828 if (ISSET(FTS_NOCHDIR)) {
829 cp = sp->fts_path + len;
830 *cp++ = '/';
831 } else {
832 /* GCC, you're too verbose. */
833 cp = NULL;
834 }
835 len++;
836 maxlen = sp->fts_pathlen - len;
837
838 level = cur->fts_level + 1;
839
840 /* Read the directory, attaching each entry to the `link' pointer. */
841 doadjust = 0;
842 readdir_errno = 0;
843 for (head = tail = NULL, nitems = 0;
844 (dp = fts_safe_readdir(dirp, &readdir_errno));) {
845 dnamlen = dp->d_namlen;
846 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
847 continue;
848
849 if ((p = fts_alloc(sp, dp->d_name, dnamlen)) == NULL)
850 goto mem1;
851 if (dnamlen >= maxlen) { /* include space for NUL */
852 oldaddr = sp->fts_path;
853 if (fts_palloc(sp, dnamlen + len + 1)) {
854 /*
855 * No more memory for path or structures. Save
856 * errno, free up the current structure and the
857 * structures already allocated.
858 */
859 mem1: saved_errno = errno;
860 if (p)
861 free(p);
862 fts_lfree(head);
863 (void)closedir(dirp);
864 cur->fts_info = FTS_ERR;
865 SET(FTS_STOP);
866 errno = saved_errno;
867 return (NULL);
868 }
869 /* Did realloc() change the pointer? */
870 if (oldaddr != sp->fts_path) {
871 doadjust = 1;
872 if (ISSET(FTS_NOCHDIR))
873 cp = sp->fts_path + len;
874 }
875 maxlen = sp->fts_pathlen - len;
876 }
877
878 p->fts_level = level;
879 p->fts_parent = sp->fts_cur;
880 p->fts_pathlen = len + dnamlen;
881
882 if (dp->d_type == DT_WHT)
883 p->fts_flags |= FTS_ISW;
884
885 if (cderrno) {
886 if (nlinks) {
887 p->fts_info = FTS_NS;
888 p->fts_errno = cderrno;
889 } else
890 p->fts_info = FTS_NSOK;
891 p->fts_accpath = cur->fts_accpath;
892 } else if (nlinks == 0 || (nostat &&
893 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)) {
894 p->fts_accpath =
895 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
896 p->fts_info = FTS_NSOK;
897 } else {
898 /* Build a file name for fts_stat to stat. */
899 if (ISSET(FTS_NOCHDIR)) {
900 p->fts_accpath = p->fts_path;
901 memmove(cp, p->fts_name, p->fts_namelen + 1);
902 p->fts_info = fts_stat(sp, p, 0, _dirfd(dirp));
903 } else {
904 p->fts_accpath = p->fts_name;
905 p->fts_info = fts_stat(sp, p, 0, -1);
906 }
907
908 /* Decrement link count if applicable. */
909 if (nlinks > 0 && (p->fts_info == FTS_D ||
910 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
911 --nlinks;
912 }
913 if (p->fts_info == FTS_NSOK && ISSET(FTS_NOSTAT_TYPE)) {
914 switch (dp->d_type) {
915 case DT_FIFO:
916 case DT_CHR:
917 case DT_BLK:
918 case DT_SOCK:
919 p->fts_info = FTS_DEFAULT;
920 break;
921 case DT_REG:
922 p->fts_info = FTS_F;
923 break;
924 case DT_LNK:
925 p->fts_info = FTS_SL;
926 break;
927 case DT_WHT:
928 p->fts_info = FTS_W;
929 break;
930 }
931 }
932
933 /* We walk in directory order so "ls -f" doesn't get upset. */
934 p->fts_link = NULL;
935 if (head == NULL)
936 head = tail = p;
937 else {
938 tail->fts_link = p;
939 tail = p;
940 }
941 ++nitems;
942 }
943
944 if (readdir_errno) {
945 cur->fts_errno = readdir_errno;
946 /*
947 * If we've not read any items yet, treat
948 * the error as if we can't access the dir.
949 */
950 cur->fts_info = nitems ? FTS_ERR : FTS_DNR;
951 }
952
953 if (dirp)
954 (void)closedir(dirp);
955
956 /*
957 * If realloc() changed the address of the path, adjust the
958 * addresses for the rest of the tree and the dir list.
959 */
960 if (doadjust)
961 fts_padjust(sp, head);
962
963 /*
964 * If not changing directories, reset the path back to original
965 * state.
966 */
967 if (ISSET(FTS_NOCHDIR))
968 sp->fts_path[cur->fts_pathlen] = '\0';
969
970 /*
971 * If descended after called from fts_children or after called from
972 * fts_read and nothing found, get back. At the root level we use
973 * the saved fd; if one of fts_open()'s arguments is a relative path
974 * to an empty directory, we wind up here with no other way back. If
975 * can't get back, we're done.
976 */
977 if (descend && (type == BCHILD || !nitems) &&
978 (cur->fts_level == FTS_ROOTLEVEL ?
979 FCHDIR(sp, sp->fts_rfd) :
980 fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
981 fts_lfree(head);
982 cur->fts_info = FTS_ERR;
983 SET(FTS_STOP);
984 return (NULL);
985 }
986
987 /* If didn't find anything, return NULL. */
988 if (!nitems) {
989 if (type == BREAD &&
990 cur->fts_info != FTS_DNR && cur->fts_info != FTS_ERR)
991 cur->fts_info = FTS_DP;
992 return (NULL);
993 }
994
995 /* Sort the entries. */
996 if (sp->fts_compar && nitems > 1)
997 head = fts_sort(sp, head, nitems);
998 return (head);
999 }
1000
1001 static int
fts_stat(FTS * sp,FTSENT * p,int follow,int dfd)1002 fts_stat(FTS *sp, FTSENT *p, int follow, int dfd)
1003 {
1004 FTSENT *t;
1005 dev_t dev;
1006 ino_t ino;
1007 struct stat *sbp, sb;
1008 int ret, saved_errno;
1009 const char *path;
1010
1011 if (dfd == -1) {
1012 path = p->fts_accpath;
1013 dfd = AT_FDCWD;
1014 } else {
1015 path = p->fts_name;
1016 }
1017
1018 /* If user needs stat info, stat buffer already allocated. */
1019 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
1020
1021 /* Check for whiteout. */
1022 if (p->fts_flags & FTS_ISW) {
1023 if (sbp != &sb) {
1024 memset(sbp, '\0', sizeof(*sbp));
1025 sbp->st_mode = S_IFWHT;
1026 }
1027 return (FTS_W);
1028 }
1029
1030 /*
1031 * If doing a logical walk, or caller requested FTS_COMFOLLOW, do
1032 * a full stat(2). If that fails, do an lstat(2) to check for a
1033 * non-existent symlink. If that fails, set the errno from the
1034 * stat(2) call.
1035 *
1036 * As a special case, if stat(2) succeeded but the target is not a
1037 * directory and follow is negative (indicating FTS_COMFOLLOWDIR
1038 * rather than FTS_COMFOLLOW), we also revert to lstat(2).
1039 */
1040 if (ISSET(FTS_LOGICAL) || follow) {
1041 if ((ret = fstatat(dfd, path, sbp, 0)) != 0 ||
1042 (follow < 0 && !S_ISDIR(sbp->st_mode))) {
1043 saved_errno = errno;
1044 if (fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {
1045 p->fts_errno = saved_errno;
1046 goto err;
1047 }
1048 errno = 0;
1049 if (ret != 0 && S_ISLNK(sbp->st_mode))
1050 return (FTS_SLNONE);
1051 }
1052 } else if (fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {
1053 p->fts_errno = errno;
1054 err: memset(sbp, 0, sizeof(struct stat));
1055 return (FTS_NS);
1056 }
1057
1058 if (S_ISDIR(sbp->st_mode)) {
1059 /*
1060 * Set the device/inode. Used to find cycles and check for
1061 * crossing mount points. Also remember the link count, used
1062 * in fts_build to limit the number of stat calls. It is
1063 * understood that these fields are only referenced if fts_info
1064 * is set to FTS_D.
1065 */
1066 dev = p->fts_dev = sbp->st_dev;
1067 ino = p->fts_ino = sbp->st_ino;
1068 p->fts_nlink = sbp->st_nlink;
1069
1070 if (ISDOT(p->fts_name))
1071 return (FTS_DOT);
1072
1073 /*
1074 * Cycle detection is done by brute force when the directory
1075 * is first encountered. If the tree gets deep enough or the
1076 * number of symbolic links to directories is high enough,
1077 * something faster might be worthwhile.
1078 */
1079 for (t = p->fts_parent;
1080 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1081 if (ino == t->fts_ino && dev == t->fts_dev) {
1082 p->fts_cycle = t;
1083 return (FTS_DC);
1084 }
1085 return (FTS_D);
1086 }
1087 if (S_ISLNK(sbp->st_mode))
1088 return (FTS_SL);
1089 if (S_ISREG(sbp->st_mode))
1090 return (FTS_F);
1091 return (FTS_DEFAULT);
1092 }
1093
1094 static FTSENT *
fts_sort(FTS * sp,FTSENT * head,size_t nitems)1095 fts_sort(FTS *sp, FTSENT *head, size_t nitems)
1096 {
1097 FTSENT **ap, *p;
1098
1099 /*
1100 * Construct an array of pointers to the structures and call qsort(3).
1101 * Reassemble the array in the order returned by qsort. If unable to
1102 * sort for memory reasons, return the directory entries in their
1103 * current order. Allocate enough space for the current needs plus
1104 * 40 so don't realloc one entry at a time.
1105 */
1106 if (nitems > sp->fts_nitems) {
1107 sp->fts_nitems = nitems + 40;
1108 if ((sp->fts_array = reallocf(sp->fts_array,
1109 sp->fts_nitems * sizeof(FTSENT *))) == NULL) {
1110 sp->fts_nitems = 0;
1111 return (head);
1112 }
1113 }
1114 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1115 *ap++ = p;
1116 if (ISSET(FTS_COMPAR_B)) {
1117 #ifdef __BLOCKS__
1118 qsort_b(sp->fts_array, nitems, sizeof(FTSENT *),
1119 (int (^)(const void *, const void *))sp->fts_compar_b);
1120 #else
1121 qsort_b(sp->fts_array, nitems, sizeof(FTSENT *),
1122 sp->fts_compar_b);
1123 #endif /* __BLOCKS__ */
1124 } else {
1125 qsort(sp->fts_array, nitems, sizeof(FTSENT *),
1126 (int (*)(const void *, const void *))sp->fts_compar);
1127 }
1128 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1129 ap[0]->fts_link = ap[1];
1130 ap[0]->fts_link = NULL;
1131 return (head);
1132 }
1133
1134 static FTSENT *
fts_alloc(FTS * sp,char * name,size_t namelen)1135 fts_alloc(FTS *sp, char *name, size_t namelen)
1136 {
1137 FTSENT *p;
1138 size_t len;
1139
1140 /*
1141 * The file name is a variable length array and no stat structure is
1142 * necessary if the user has set the nostat bit. Allocate the FTSENT
1143 * structure, the file name and the stat structure in one chunk, but
1144 * be careful that the stat structure is reasonably aligned.
1145 */
1146 len = sizeof(FTSENT) + namelen + 1;
1147 if (!ISSET(FTS_NOSTAT)) {
1148 len = roundup(len, alignof(struct stat));
1149 p = calloc(1, len + sizeof(struct stat));
1150 } else {
1151 p = calloc(1, len);
1152 }
1153 if (p == NULL)
1154 return (NULL);
1155
1156 p->fts_symfd = -1;
1157 p->fts_path = sp->fts_path;
1158 p->fts_name = (char *)(p + 1);
1159 p->fts_namelen = namelen;
1160 p->fts_instr = FTS_NOINSTR;
1161 if (!ISSET(FTS_NOSTAT))
1162 p->fts_statp = (struct stat *)((char *)p + len);
1163 p->fts_fts = sp;
1164 memcpy(p->fts_name, name, namelen);
1165
1166 return (p);
1167 }
1168
1169 static void
fts_lfree(FTSENT * head)1170 fts_lfree(FTSENT *head)
1171 {
1172 FTSENT *p;
1173
1174 /* Free a linked list of structures. */
1175 while ((p = head)) {
1176 head = head->fts_link;
1177 free(p);
1178 }
1179 }
1180
1181 /*
1182 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
1183 * Most systems will allow creation of paths much longer than MAXPATHLEN, even
1184 * though the kernel won't resolve them. Add the size (not just what's needed)
1185 * plus 256 bytes so don't realloc the path 2 bytes at a time.
1186 */
1187 static int
fts_palloc(FTS * sp,size_t more)1188 fts_palloc(FTS *sp, size_t more)
1189 {
1190
1191 sp->fts_pathlen += more + 256;
1192 sp->fts_path = reallocf(sp->fts_path, sp->fts_pathlen);
1193 return (sp->fts_path == NULL);
1194 }
1195
1196 /*
1197 * When the path is realloc'd, have to fix all of the pointers in structures
1198 * already returned.
1199 */
1200 static void
fts_padjust(FTS * sp,FTSENT * head)1201 fts_padjust(FTS *sp, FTSENT *head)
1202 {
1203 FTSENT *p;
1204 char *addr = sp->fts_path;
1205
1206 #define ADJUST(p) do { \
1207 if ((p)->fts_accpath != (p)->fts_name) { \
1208 (p)->fts_accpath = \
1209 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1210 } \
1211 (p)->fts_path = addr; \
1212 } while (0)
1213 /* Adjust the current set of children. */
1214 for (p = sp->fts_child; p; p = p->fts_link)
1215 ADJUST(p);
1216
1217 /* Adjust the rest of the tree, including the current level. */
1218 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1219 ADJUST(p);
1220 p = p->fts_link ? p->fts_link : p->fts_parent;
1221 }
1222 }
1223
1224 static size_t
fts_maxarglen(char * const * argv)1225 fts_maxarglen(char * const *argv)
1226 {
1227 size_t len, max;
1228
1229 for (max = 0; *argv; ++argv)
1230 if ((len = strlen(*argv)) > max)
1231 max = len;
1232 return (max + 1);
1233 }
1234
1235 /*
1236 * Change to dir specified by fd or p->fts_accpath without getting
1237 * tricked by someone changing the world out from underneath us.
1238 * Assumes p->fts_dev and p->fts_ino are filled in.
1239 */
1240 static int
fts_safe_changedir(FTS * sp,FTSENT * p,int fd,char * path)1241 fts_safe_changedir(FTS *sp, FTSENT *p, int fd, char *path)
1242 {
1243 int ret, oerrno, newfd;
1244 struct stat sb;
1245 struct statfs sf;
1246
1247 newfd = fd;
1248 if (ISSET(FTS_NOCHDIR))
1249 return (0);
1250 if (fd < 0 && (newfd = _open(path, O_RDONLY | O_DIRECTORY |
1251 O_CLOEXEC, 0)) < 0)
1252 return (-1);
1253 if (_fstat(newfd, &sb)) {
1254 ret = -1;
1255 goto bail;
1256 }
1257 if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
1258 if (_fstatfs(newfd, &sf) != 0 ||
1259 (sf.f_flags & MNT_AUTOMOUNTED) == 0) {
1260 errno = ENOENT; /* disinformation */
1261 ret = -1;
1262 goto bail;
1263 }
1264 /* autofs might did the mount under us, accept. */
1265 p->fts_dev = sb.st_dev;
1266 p->fts_ino = sb.st_ino;
1267 }
1268 ret = fchdir(newfd);
1269 bail:
1270 oerrno = errno;
1271 if (fd < 0)
1272 (void)_close(newfd);
1273 errno = oerrno;
1274 return (ret);
1275 }
1276
1277 /*
1278 * Check if the filesystem for "ent" has UFS-style links.
1279 */
1280 static int
fts_ufslinks(FTS * sp,const FTSENT * ent)1281 fts_ufslinks(FTS *sp, const FTSENT *ent)
1282 {
1283 struct _fts_private *priv;
1284 const char **cpp;
1285
1286 priv = (struct _fts_private *)sp;
1287 /*
1288 * If this node's device is different from the previous, grab
1289 * the filesystem information, and decide on the reliability
1290 * of the link information from this filesystem for stat(2)
1291 * avoidance.
1292 */
1293 if (priv->ftsp_dev != ent->fts_dev) {
1294 if (statfs(ent->fts_path, &priv->ftsp_statfs) != -1) {
1295 priv->ftsp_dev = ent->fts_dev;
1296 priv->ftsp_linksreliable = 0;
1297 for (cpp = ufslike_filesystems; *cpp; cpp++) {
1298 if (strcmp(priv->ftsp_statfs.f_fstypename,
1299 *cpp) == 0) {
1300 priv->ftsp_linksreliable = 1;
1301 break;
1302 }
1303 }
1304 } else {
1305 priv->ftsp_linksreliable = 0;
1306 }
1307 }
1308 return (priv->ftsp_linksreliable);
1309 }
1310