|
|
Message-ID: <41af2e02-5cd7-4f5d-8bd8-59d28b7be584@envs.net>
Date: Fri, 20 Nov 2026 13:23:21 +0300
From: illiliti <ilt@...s.net>
To: Rich Felker <dalias@...c.org>
Cc: musl@...ts.openwall.com
Subject: Re: [PATCH v2] Add fts
On 11/19/26 8:06 PM, Rich Felker wrote:
> 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).
Alright, I'll drop them. I'll also use size_t where applicable.
>
>> +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.
Will fix.
>
>> 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.
Agreed, truncation sounds like a bad idea in general. I'll look into it.
>
>> +#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?
I guess it's just some old 4.4BSD path limit. Sorry for this, I'll modernize
the codebase, so you don't have to stumble upon these ancient quirks anymore.
>
>> + * 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.
Agreed.
>
>> + * 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.
*at() functions are actually a great idea. I'll see what I can do.
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.