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