|
|
Message-ID: <20261119170644.GF5716@brightrain.aerifal.cx>
Date: Thu, 19 Nov 2026 12:06:44 -0500
From: Rich Felker <dalias@...c.org>
To: illiliti <ilt@...s.net>
Cc: musl@...ts.openwall.com
Subject: Re: [PATCH v2] Add fts
On Thu, Nov 19, 2026 at 02:39:39PM +0300, illiliti wrote:
> >From 225b22b340f78e48d5753c2b13bc5c746d9767c4 Mon Sep 17 00:00:00 2001
> From: illiliti <ilt@...s.net>
> Date: Mon, 21 Sep 2026 18:31:18 +0300
> Subject: [PATCH v2] fts: import NetBSD implementation
>
> Based on netbsd src commit: 4733d6b621fff273d4877afa40fd0cad73fe9b62
> ---
> include/fts.h | 151 +++++++
> src/misc/fts.c | 1076 ++++++++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 1227 insertions(+)
> create mode 100644 include/fts.h
> create mode 100644 src/misc/fts.c
>
> diff --git a/include/fts.h b/include/fts.h
> new file mode 100644
> index 00000000..45f3a8cc
> --- /dev/null
> +++ b/include/fts.h
> @@ -0,0 +1,151 @@
> +/*
> + * Copyright (c) 1989, 1993
> + * The Regents of the University of California. All rights reserved.
> + *
> + * Redistribution and use in source and binary forms, with or without
> + * modification, are permitted provided that the following conditions
> + * are met:
> + * 1. Redistributions of source code must retain the above copyright
> + * notice, this list of conditions and the following disclaimer.
> + * 2. Redistributions in binary form must reproduce the above copyright
> + * notice, this list of conditions and the following disclaimer in the
> + * documentation and/or other materials provided with the distribution.
> + * 3. Neither the name of the University nor the names of its contributors
> + * may be used to endorse or promote products derived from this software
> + * without specific prior written permission.
> + *
> + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
> + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
> + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
> + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
> + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
> + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
> + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
> + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
> + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
> + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> + * SUCH DAMAGE.
> + */
> +
> +#ifndef _FTS_H_
> +#define _FTS_H_
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include <stdint.h>
> +#include <sys/stat.h>
> +
> +#ifndef __fts_stat_t
> +#define __fts_stat_t struct stat
> +#endif
> +#ifndef __fts_nlink_t
> +#define __fts_nlink_t nlink_t
> +#endif
> +#ifndef __fts_ino_t
> +#define __fts_ino_t ino_t
> +#endif
> +#ifndef __fts_length_t
> +#define __fts_length_t unsigned int
> +#endif
> +#ifndef __fts_number_t
> +#define __fts_number_t int64_t
> +#endif
> +#ifndef __fts_dev_t
> +#define __fts_dev_t dev_t
> +#endif
> +#ifndef __fts_level_t
> +#define __fts_level_t int
> +#endif
All of these can be dropped. Only a few are used anywhere but inside
the struct definition, and the ones used outside of there are ones
that definitely can't even change (stat and ino_t).
> +typedef struct {
> + struct _ftsent *fts_cur; /* current node */
> + struct _ftsent *fts_child; /* linked list of children */
> + struct _ftsent **fts_array; /* sort array */
> + dev_t fts_dev; /* starting device # */
> + char *fts_path; /* path for this descent */
> + int fts_rfd; /* fd for root */
> + unsigned int fts_pathlen; /* sizeof(path) */
> + unsigned int fts_nitems; /* elements in the sort array */
> + int (*fts_compar) /* compare function */
> + (const struct _ftsent **, const struct _ftsent **);
> +
> +#define FTS_COMFOLLOW 0x001 /* follow command line symlinks */
> +#define FTS_LOGICAL 0x002 /* logical walk */
> +#define FTS_NOCHDIR 0x004 /* don't change directories */
> +#define FTS_NOSTAT 0x008 /* don't get stat info */
> +#define FTS_PHYSICAL 0x010 /* physical walk */
> +#define FTS_SEEDOT 0x020 /* return dot and dot-dot */
> +#define FTS_XDEV 0x040 /* don't cross devices */
> +#define FTS_WHITEOUT 0x080 /* return whiteout information */
> +#define FTS_OPTIONMASK 0x0ff /* valid user option mask */
> +
> +#define FTS_NAMEONLY 0x100 /* (private) child names only */
> +#define FTS_STOP 0x200 /* (private) unrecoverable error */
> + int fts_options; /* fts_open options, global flags */
> +} FTS;
> +
> +typedef struct _ftsent {
> + struct _ftsent *fts_cycle; /* cycle node */
> + struct _ftsent *fts_parent; /* parent directory */
> + struct _ftsent *fts_link; /* next file in directory */
> + __fts_number_t fts_number; /* local numeric value */
> + void *fts_pointer; /* local address value */
> + char *fts_accpath; /* access path */
> + char *fts_path; /* root path */
> + int fts_errno; /* errno for this node */
> + int fts_symfd; /* fd for symlink */
> + __fts_length_t fts_pathlen; /* strlen(fts_path) */
> + __fts_length_t fts_namelen; /* strlen(fts_name) */
> +
> + __fts_ino_t fts_ino; /* inode */
> + __fts_dev_t fts_dev; /* device */
> + __fts_nlink_t fts_nlink; /* link count */
> +
> +#define FTS_ROOTPARENTLEVEL -1
> +#define FTS_ROOTLEVEL 0
> + __fts_level_t fts_level; /* depth (-1 to N) */
> +
> +#define FTS_D 1 /* preorder directory */
> +#define FTS_DC 2 /* directory that causes cycles */
> +#define FTS_DEFAULT 3 /* none of the above */
> +#define FTS_DNR 4 /* unreadable directory */
> +#define FTS_DOT 5 /* dot or dot-dot */
> +#define FTS_DP 6 /* postorder directory */
> +#define FTS_ERR 7 /* error; errno is set */
> +#define FTS_F 8 /* regular file */
> +#define FTS_INIT 9 /* initialized only */
> +#define FTS_NS 10 /* stat(2) failed */
> +#define FTS_NSOK 11 /* no stat(2) requested */
> +#define FTS_SL 12 /* symbolic link */
> +#define FTS_SLNONE 13 /* symbolic link without target */
> +#define FTS_W 14 /* whiteout object */
> + unsigned short fts_info; /* user flags for FTSENT structure */
> +
> +#define FTS_DONTCHDIR 0x01 /* don't chdir .. to the parent */
> +#define FTS_SYMFOLLOW 0x02 /* followed a symlink to get here */
> +#define FTS_ISW 0x04 /* this is a whiteout object */
> + unsigned short fts_flags; /* private flags for FTSENT structure */
> +
> +#define FTS_AGAIN 1 /* read node again */
> +#define FTS_FOLLOW 2 /* follow symbolic link */
> +#define FTS_NOINSTR 3 /* no instructions */
> +#define FTS_SKIP 4 /* discard node */
> + unsigned short fts_instr; /* fts_set() instructions */
> +
> + __fts_stat_t *fts_statp; /* stat(2) information */
> + char fts_name[]; /* file name */
> +} FTSENT;
For public headers we don't include comments (intent is to avoid
copyrightable content) because they are intended to be public domain
and not affect copyright status of .o files built against them, and we
generally don't intersperse macros and struct definitions like this.
The header we merge should be one that doesn't need a copyright
notice.
> diff --git a/src/misc/fts.c b/src/misc/fts.c
> new file mode 100644
> index 00000000..65446209
> --- /dev/null
> +++ b/src/misc/fts.c
> @@ -0,0 +1,1076 @@
> +/*-
> + * Copyright (c) 1990, 1993, 1994
> + * The Regents of the University of California. All rights reserved.
> + *
> + * Redistribution and use in source and binary forms, with or without
> + * modification, are permitted provided that the following conditions
> + * are met:
> + * 1. Redistributions of source code must retain the above copyright
> + * notice, this list of conditions and the following disclaimer.
> + * 2. Redistributions in binary form must reproduce the above copyright
> + * notice, this list of conditions and the following disclaimer in the
> + * documentation and/or other materials provided with the distribution.
> + * 3. Neither the name of the University nor the names of its contributors
> + * may be used to endorse or promote products derived from this software
> + * without specific prior written permission.
> + *
> + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
> + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
> + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
> + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
> + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
> + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
> + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
> + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
> + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
> + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
> + * SUCH DAMAGE.
> + */
> +
> +#include <sys/param.h>
sys/param.h is not intended or okay for use in libc. It's some legacy
stuff provided for applications. Whatever is coming from it should be
obtained from the standard location.
> +#include <sys/stat.h>
> +
> +#include <assert.h>
> +#include <dirent.h>
> +#include <errno.h>
> +#include <fcntl.h>
> +#include <fts.h>
> +#include <stdlib.h>
> +#include <string.h>
> +#include <unistd.h>
> +
> +static FTSENT *fts_alloc(FTS *, const char *, size_t);
> +static FTSENT *fts_build(FTS *, int);
> +static void fts_free(FTSENT *);
> +static void fts_lfree(FTSENT *);
> +static void fts_load(FTS *, FTSENT *);
> +static size_t fts_maxarglen(char * const *);
> +static size_t fts_pow2(size_t);
> +static int fts_palloc(FTS *, size_t);
> +static void fts_padjust(FTS *, FTSENT *);
> +static FTSENT *fts_sort(FTS *, FTSENT *, size_t);
> +static unsigned short fts_stat(FTS *, FTSENT *, int);
> +static int fts_safe_changedir(const FTS *, const FTSENT *, int,
> + const char *);
> +
> +#ifndef ftsent_namelen_truncate
> +#define ftsent_namelen_truncate(a) \
> + ((a) > UINT_MAX ? UINT_MAX : (unsigned int)(a))
> +#endif
> +#ifndef ftsent_pathlen_truncate
> +#define ftsent_pathlen_truncate(a) \
> + ((a) > UINT_MAX ? UINT_MAX : (unsigned int)(a))
> +#endif
> +#ifndef fts_pathlen_truncate
> +#define fts_pathlen_truncate(a) \
> + ((a) > UINT_MAX ? UINT_MAX : (unsigned int)(a))
> +#endif
> +#ifndef fts_nitems_truncate
> +#define fts_nitems_truncate(a) \
> + ((a) > UINT_MAX ? UINT_MAX : (unsigned int)(a))
> +#endif
I'm confused why these truncations exist at all. NAME_MAX and PATH_MAX
are small finite numbers, but even if they weren't, "data does not
fit" seems like it should be a condition that results in reporting an
error, not silently truncating it and potentially colliding with
another name.
> +#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
> +
> +#define CLR(opt) (sp->fts_options &= ~(opt))
> +#define ISSET(opt) (sp->fts_options & (opt))
> +#define SET(opt) (sp->fts_options |= (opt))
> +
> +#define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path))
> +#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
> +
> +/* fts_build flags */
> +#define BCHILD 1 /* fts_children */
> +#define BNAMES 2 /* fts_children, names only */
> +#define BREAD 3 /* fts_read */
> +
> +FTS *
> +fts_open(char * const *argv, int options,
> + int (*compar)(const FTSENT **, const FTSENT **))
> +{
> + FTS *sp;
> + FTSENT *p, *root;
> + size_t nitems;
> + FTSENT *parent, *tmp = NULL; /* pacify gcc */
> + size_t len;
> +
> + /* Options check. */
> + if (options & ~FTS_OPTIONMASK) {
> + errno = EINVAL;
> + return (NULL);
> + }
> +
> + /* At least one path must be specified. */
> + if (*argv == NULL) {
> + errno = EINVAL;
> + return (NULL);
> + }
> +
> + /* Allocate/initialize the stream */
> + if ((sp = calloc(1, sizeof(FTS))) == NULL)
> + return (NULL);
> + sp->fts_compar = compar;
> + sp->fts_options = options;
> +
> + /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
> + if (ISSET(FTS_LOGICAL))
> + SET(FTS_NOCHDIR);
> +
> + /*
> + * Start out with 1K of path space, and enough, in any case,
> + * to hold the user's paths.
> + */
> + if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
MAXPATHLEN looks like one of the things from sys/param.h. It's
PATH_MAX from limits.h. Is there a reason it's being used as the
default starting space? It doesn't seem conceptually related. Where is
the 1k in the comment coming from?
> + * When the path is realloc'd, have to fix all of the pointers in structures
> + * already returned.
> + */
> +static void
> +fts_padjust(FTS *sp, FTSENT *head)
> +{
> + FTSENT *p;
> + char *addr;
> +
> +#define ADJUST(p) do { \
> + if ((p)->fts_accpath != (p)->fts_name) \
> + (p)->fts_accpath = \
> + addr + ((p)->fts_accpath - (p)->fts_path); \
> + (p)->fts_path = addr; \
> +} while (0)
This is undefined behavior, doing pointer arithmetic on pointers which
are no longer valid. There are hacks to fix this but the cleanest fix
is probably not using realloc at all and just malloc+copy+free. That's
what realloc will almost surely do anyway.
> + * Change to dir specified by fd or p->fts_accpath without getting
> + * tricked by someone changing the world out from underneath us.
> + * Assumes p->fts_dev and p->fts_ino are filled in.
> + */
> +static int
> +fts_safe_changedir(const FTS *sp, const FTSENT *p, int fd, const char *path)
> +{
> + int oldfd = fd, ret = -1;
> + __fts_stat_t sb;
> +
> + if (ISSET(FTS_NOCHDIR))
> + return 0;
> +
> + if (oldfd < 0 && (fd = open(path, O_RDONLY | O_CLOEXEC)) == -1)
> + return -1;
> +
> + if (fstat(fd, &sb) == -1)
> + goto bail;
> +
> + if (sb.st_ino != p->fts_ino || sb.st_dev != p->fts_dev) {
> + errno = ENOENT;
> + goto bail;
> + }
> +
> + ret = fchdir(fd);
> +
> +bail:
> + if (oldfd < 0) {
> + int save_errno = errno;
> + (void)close(fd);
> + errno = save_errno;
> + }
> + return ret;
> +}
At least from what I can tell looking at the documentation, chdir is
just an optimization not a behavior guaranteed to the calling
application. I do not think we should support it at all. It's
thread-unsafe and library-unsafe. If we want the same optimization it
can be done in a modern way with the *at() functions as an enhancement.
I have not reviewed all of the code, but the above were the things
that stuck out at me on a first read of the squashed patch.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.