Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
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.