[PATCH v2] io: ftw: Use state stack instead of recursion (BZ 33882)
DJ Delorie
dj@redhat.com
Sat Mar 28 02:29:03 GMT 2026
Adhemerval Zanella <adhemerval.zanella@linaro.org> writes:
> The current implementation of ftw relies on recursion to traverse
> directories (ftw_dir calls process_entry, which calls ftw_dir). In deep
> directory trees, this could lead to a stack overflow (as demonstrated by
> the new tst-nftw-bz33882.c test).
Needs some spelling fixes and comments added, but otherwise LGTM.
Reviewed-by: DJ Delorie <dj@redhat.com>
> This patch refactors ftw to use an explicit, heap-allocated stack to
> manage directory traversal:
>
> * The 'struct ftw_frame' encapsulates the state of a single directory
> level (directory stream, stat buffer, previous base offset, and
> current state).
>
> * The ftw_dir is rewritten to use a loop instead of recursion and
> an iterative loop to enable immediate state transitions without
> function call overhead.
>
> The patch also cleans up some unused definitions and assumptions (e.g.,
> free-clobbering errno) and fixes a UB when handling the ftw callback.
> diff --git a/io/ftw.c b/io/ftw.c
> index d29734813d..a54736a47e 100644
> --- a/io/ftw.c
> +++ b/io/ftw.c
> @@ -16,116 +16,17 @@
> License along with the GNU C Library; if not, see
> <https://www.gnu.org/licenses/>. */
>
> -#ifdef HAVE_CONFIG_H
> -# include <config.h>
> -#endif
So... you're basicaly replacing whole parts of the file, it seems ;-)
> -#include <errno.h>
> +#include <assert.h>
> +#include <dirent.h>
> #include <fcntl.h>
> #include <ftw.h>
> -#include <limits.h>
> -#include <search.h>
> -#include <stdlib.h>
> -#include <string.h>
> -#include <unistd.h>
> #include <not-cancel.h>
> +#include <search.h>
> +#include <unistd.h>
> #include <sys/param.h>
> -#ifdef _LIBC
> -# include <include/sys/stat.h>
> -#else
> -# include <sys/stat.h>
> -#endif
Ok.
> -#if ! _LIBC && !HAVE_DECL_STPCPY && !defined stpcpy
And we no longer support wherever the original ftw.c came from...
> +enum ftw_frame_state
> +{
> + FTW_STATE_INIT = 0,
> + FTW_STATE_STREAM_LOOP,
> + FTW_STATE_CONTENT_LOOP,
> + FTW_STATE_CLEANUP
> +};
These could use some comments?
> +/* Keep track of visited directories. */
> +struct ftw_frame
> +{
> + struct dir_data dir;
> + struct STRUCT_STAT st;
> + int previous_base;
> + char *runp;
> + enum ftw_frame_state state;
> +};
ok.
> +struct ftw_stack
> +{
> + struct ftw_frame **stack;
> + size_t num_blocks;
> + ssize_t top;
> +};
ok.
> +typedef union
> +{
> + NFTW_FUNC_T nftw_func;
> + FTW_FUNC_T ftw_func;
> +} func_callback_t;
Ok.
> const int *cvt_arr;
>
> /* Callback function. We always use the `nftw' form. */
> - NFTW_FUNC_T func;
> + bool is_nftw;
> + func_callback_t func;
Ok.
> object. This is needed when not using FTW_PHYS. */
> void *known_objects;
> };
> +#define CALL_FUNC(__ftw_data, __fp, __sb, __f, __ftw) \
> + ((__ftw_data)->is_nftw ? (__ftw_data)->func.nftw_func (__fp, __sb, __f, __ftw) \
> + : (__ftw_data)->func.ftw_func (__fp, __sb, __f))
Ok.
>
> static int
> process_entry (struct ftw_data *data, struct dir_data *dir, const char *name,
> - size_t namlen, int d_type)
> + size_t namlen, struct STRUCT_STAT *out_st, bool *descend)
> {
> struct STRUCT_STAT st;
> int result = 0;
> int flag = 0;
> size_t new_buflen;
>
> + *descend = false;
> +
Ok.
> || (!find_object (data, &st)
> /* Remember the object. */
> && (result = add_object (data, &st)) == 0))
> - result = ftw_dir (data, &st, dir);
> + {
> + *out_st = st;
> + *descend = true;
> + }
Ok.
> }
> else
> - result = (*data->func) (data->dirbuf, &st, data->cvt_arr[flag],
> - &data->ftw);
> + result = CALL_FUNC (data, data->dirbuf, &st, data->cvt_arr[flag],
> + &data->ftw);
> }
Ok.
> -static int
> -__attribute ((noinline))
> -ftw_dir (struct ftw_data *data, struct STRUCT_STAT *st, struct dir_data *old_dir)
> +/* The ftw_framw are kept as chucked array to minimize the reallocation cost
> + when the stack grows (since it contains STRUCT_STAT and extra metadata).
> + New chunks of ftw_framw are allocated and only freed when ftw returns. */
s/framw/frame/g
s/chucked/chunked/
> +enum
> {
> - struct dir_data dir;
> - struct dirent64 *d;
> - int previous_base = data->ftw.base;
> - int result;
> - char *startp;
> + FTW_STACK_CHUNCK_BLOCKS = 1, /* Number of initial allocated chuncks. */
> + FTW_STACK_CHUNK_SIZE = 32 /* Number of stack frames allocated per
> + chunck. */
> +};
s/chunck/chunk/
Unless you're doing this intentionally, in which case... choose a better
name please ;-)
> +static inline struct ftw_frame *
> +frame_stack_get (struct ftw_stack *ftwst, int adj)
> +{
> + return &ftwst->stack[(ftwst->top + adj) / FTW_STACK_CHUNK_SIZE]
> + [(ftwst->top + adj) % FTW_STACK_CHUNK_SIZE];
> +}
Same basic page-table-style memory allocation system we've used
elsewhere. Ok.
> +static inline void
> +frame_stack_reset_top (struct ftw_stack *fwtst, const struct STRUCT_STAT *st)
> +{
> + struct ftw_frame *frame = frame_stack_get (fwtst, 0);
> + frame->st = *st;
> + frame->state = FTW_STATE_INIT;
> + frame->dir.stream = NULL;
> + frame->dir.content = NULL;
> + frame->dir.streamfd = -1;
> +}
Ok.
> +static bool
> +frame_stack_init (struct ftw_stack *ftwst, const struct STRUCT_STAT *st)
> +{
> + ftwst->num_blocks = FTW_STACK_CHUNCK_BLOCKS;
> + ftwst->stack = malloc (FTW_STACK_CHUNCK_BLOCKS * sizeof (*ftwst->stack));
> + if (ftwst->stack == NULL)
> + return false;
> +
> + ftwst->stack[0] = malloc (FTW_STACK_CHUNK_SIZE * sizeof (struct ftw_frame));
> + if (ftwst->stack[0] == NULL)
> + free (ftwst->stack);
> + return false;
> }
>
> + ftwst->top = 0;
> + frame_stack_reset_top (ftwst, st);
> + return true;
> +}
Ok.
> +static void
> +frame_stack_free (struct ftw_stack *ftwst)
> +{
> + for (size_t i = 0; i < ftwst->num_blocks; i++)
> + free (ftwst->stack[i]);
> + free (ftwst->stack);
> +}
Assumes free(NULL) is ok, which it is, so ok.
> +static bool
> +frame_stack_add (struct ftw_stack *ftwst, const struct STRUCT_STAT *st)
> +{
> + if (ftwst->top + 1 >= ftwst->num_blocks * FTW_STACK_CHUNK_SIZE)
> {
> + size_t new_blocks = ftwst->num_blocks + 1;
> + struct ftw_frame **new_stack = realloc (
> + ftwst->stack, new_blocks * sizeof (*ftwst->stack));
> +
> + if (new_stack == NULL)
> + return false;
> + ftwst->stack = new_stack;
> + ftwst->stack[ftwst->num_blocks] = malloc (
> + FTW_STACK_CHUNK_SIZE * sizeof (struct ftw_frame));
> + if (ftwst->stack[ftwst->num_blocks] == NULL)
> + return false;
> + ftwst->num_blocks = new_blocks;
> + }
> + ftwst->top++;
> + frame_stack_reset_top (ftwst, st);
> + return true;
> +}
Ok.
> +static void
> +frame_closedir (struct ftw_data *data, struct ftw_frame *frame)
> +{
> + int save_err = errno;
> + assert (frame->dir.content == NULL);
> + __closedir (frame->dir.stream);
> + frame->dir.streamfd = -1;
> + __set_errno (save_err);
> + if (data->actdir-- == 0)
> + data->actdir = data->maxdir - 1;
> + data->dirstreams[data->actdir] = NULL;
> + frame->dir.stream = NULL;
> +}
Ok.
> +static int
> +ftw_dir (struct ftw_data *data, const struct STRUCT_STAT *st)
> +{
> + struct ftw_stack ftwst;
> + if (!frame_stack_init (&ftwst, st))
> + return -1;
> +
> + int result = 0;
> +
Ok.
> + while (ftwst.top >= 0)
> + {
> + struct ftw_frame *frame = frame_stack_get (&ftwst, 0);
> + struct dir_data *old_dir = (ftwst.top > 0)
> + ? &frame_stack_get (&ftwst, -1)->dir : NULL;
> +
> + if (frame->state == FTW_STATE_INIT)
> {
> + frame->previous_base = data->ftw.base;
> + result = open_dir_stream (
> + old_dir == NULL ? NULL : &old_dir->streamfd, data, &frame->dir);
> + if (result != 0)
> {
> + if (errno == EACCES)
> + result = CALL_FUNC (data, data->dirbuf, &frame->st, FTW_DNR,
> + &data->ftw);
> + ftwst.top--;
> + /* Intercept FTW_SKIP_SUBTREE when popping frame */
> + if (ftwst.top >= 0 && (data->flags & FTW_ACTIONRETVAL)
> + && result == FTW_SKIP_SUBTREE)
> + result = 0;
> + continue;
> + }
Ok.
> + if (!(data->flags & FTW_DEPTH))
> + {
> + result = CALL_FUNC (data, data->dirbuf, &frame->st, FTW_D,
> + &data->ftw);
> + if (result != 0)
> + goto state0_fail;
> + }
Ok.
> + if (data->flags & FTW_CHDIR)
> + {
> + if (__fchdir (__dirfd (frame->dir.stream)) < 0)
> + {
> + result = -1;
> + state0_fail:
> + frame_closedir (data, frame);
> + ftwst.top--;
> + /* Intercept FTW_SKIP_SUBTREE when popping frame. */
> + if (ftwst.top >= 0 && (data->flags & FTW_ACTIONRETVAL)
> + && result == FTW_SKIP_SUBTREE)
> + result = 0;
> + continue;
> + }
> + }
Ok.
> + ++data->ftw.level;
> + char *startp = strchr (data->dirbuf, '\0');
> + assert (startp != data->dirbuf);
> + if (startp[-1] != '/')
> + *startp++ = '/';
> + data->ftw.base = startp - data->dirbuf;
> +
> + frame->state = FTW_STATE_STREAM_LOOP;
> + frame->runp = frame->dir.content;
> + }
Ok.
> + else if (frame->state == FTW_STATE_STREAM_LOOP)
> + {
> + if (result != 0)
> + {
> + frame->state = FTW_STATE_CLEANUP;
> + continue;
> + }
> +
> + if (frame->dir.stream == NULL)
> + {
> + frame->state = FTW_STATE_CONTENT_LOOP;
> + frame->runp = frame->dir.content;
> + continue;
> + }
Ok.
> + struct dirent64 *d = __readdir64 (frame->dir.stream);
> + if (d != NULL)
> + {
> + struct STRUCT_STAT child_st;
> + bool descend = false;
> + result = process_entry (data, &frame->dir, d->d_name, NAMLEN (d),
> + &child_st, &descend);
> +
> + if (result == 0 && descend)
> + {
> + if (!frame_stack_add (&ftwst, &child_st))
> + {
> + result = -1;
> + frame->state = FTW_STATE_CLEANUP;
> + }
> + continue;
> + }
> + else if (result != 0)
> + {
> + frame->state = FTW_STATE_CLEANUP;
> + continue;
> + }
> }
> else
> + frame->state = FTW_STATE_CLEANUP;
> + }
Ok.
> + else if (frame->state == FTW_STATE_CONTENT_LOOP)
> + {
> + if (result != 0)
Where is this "result" coming from? Needs a comment.
> + {
> + frame->state = FTW_STATE_CLEANUP;
> + continue;
> + }
> +
> + if (frame->runp != NULL && *frame->runp != '\0')
> + {
> + char *endp = strchr (frame->runp, '\0');
> + struct STRUCT_STAT child_st;
> + bool descend = false;
> +
> + result = process_entry (data, &frame->dir, frame->runp,
> + endp - frame->runp, &child_st,
> + &descend);
> + frame->runp = endp + 1;
> +
> + if (result == 0 && descend)
> + {
> + if (!frame_stack_add (&ftwst, &child_st))
> + {
> + result = -1;
> + frame->state = FTW_STATE_CLEANUP;
> + }
> + continue;
> + }
> + else if (result != 0)
> + {
> + frame->state = FTW_STATE_CLEANUP;
> + continue;
> + }
> + }
> + else
> + frame->state = FTW_STATE_CLEANUP;
> + }
Ok.
> + else if (frame->state == FTW_STATE_CLEANUP)
> + {
> + if (frame->dir.stream != NULL)
> + frame_closedir (data, frame);
> + else if (frame->dir.content != NULL)
> + {
> + free (frame->dir.content);
> + frame->dir.content = NULL;
> + }
ok.
> + if ((data->flags & FTW_ACTIONRETVAL) && result == FTW_SKIP_SIBLINGS)
> + result = 0;
> +
> + data->dirbuf[data->ftw.base - 1] = '\0';
> + --data->ftw.level;
> + data->ftw.base = frame->previous_base;
> +
> + if (result == 0 && (data->flags & FTW_DEPTH))
> + result
> + = CALL_FUNC (data, data->dirbuf, &frame->st, FTW_DP,
> + &data->ftw);
> +
> + if (old_dir != NULL && (data->flags & FTW_CHDIR)
> + && (result == 0
> + || ((data->flags & FTW_ACTIONRETVAL)
> + && (result != -1 && result != FTW_STOP))))
> + {
> + int done = 0;
> + if (old_dir->stream != NULL)
> + if (__fchdir (__dirfd (old_dir->stream)) == 0)
> + done = 1;
> +
> + if (!done)
> + {
> + if (data->ftw.base == 1)
> + {
> + if (__chdir ("/") < 0)
> + result = -1;
> + }
> + else if (__chdir ("..") < 0)
> + result = -1;
> + }
> + }
> +
> + ftwst.top--;
> + /* Intercept FTW_SKIP_SUBTREE when popping frame. */
> + if (ftwst.top >= 0 && (data->flags & FTW_ACTIONRETVAL)
> + && result == FTW_SKIP_SUBTREE)
> + result = 0;
> }
> }
>
> + frame_stack_free (&ftwst);
> +
> return result;
> }
Ok.
>
> static int
> +ftw_startup (const char *dir, bool is_nftw, func_callback_t func,
> + int descriptors, int flags)
> {
> struct ftw_data data = { .dirstreams = NULL };
> struct STRUCT_STAT st;
> int result = 0;
> - int save_err;
> int cwdfd = -1;
> char *cwd = NULL;
> char *cp;
Ok.
>
> - /* This assignment might seem to be strange but it is what we want.
> - The trick is that the first three arguments to the `ftw' and
> - `nftw' callback functions are equal. Therefore we can call in
> - every case the callback using the format of the `nftw' version
> - and get the correct result since the stack layout for a function
> - call in C allows this. */
> - data.func = (NFTW_FUNC_T) func;
> + data.is_nftw = is_nftw;
> + data.func = func;
Ok.
> && errno == ENOENT
> && LSTAT (name, &st) == 0
> && S_ISLNK (st.st_mode))
> - result = (*data.func) (data.dirbuf, &st, data.cvt_arr[FTW_SLN],
> - &data.ftw);
> + result = CALL_FUNC (&data, data.dirbuf, &st, data.cvt_arr[FTW_SLN],
> + &data.ftw);
Ok.
> if (result == 0)
> - result = ftw_dir (&data, &st, NULL);
> + result = ftw_dir (&data, &st);
Ok.
> - result = (*data.func) (data.dirbuf, &st, data.cvt_arr[flag],
> - &data.ftw);
> + result = CALL_FUNC (&data, data.dirbuf, &st, data.cvt_arr[flag],
> + &data.ftw);
Ok.
>
> /* Free all memory. */
> out_fail:
> - save_err = errno;
> __tdestroy (data.known_objects, free);
> free (data.dirstreams);
> - __set_errno (save_err);
>
> return result;
> }
Ok. free() no longer changes errno...
> int
> FTW_NAME (const char *path, FTW_FUNC_T func, int descriptors)
> {
> - return ftw_startup (path, 0, func, descriptors, 0);
> + return ftw_startup (path, false, (func_callback_t) { .ftw_func = func },
> + descriptors, 0);
> }
Ok.
> #ifndef NFTW_OLD_NAME
> int
> NFTW_NAME (const char *path, NFTW_FUNC_T func, int descriptors, int flags)
> {
> - return ftw_startup (path, 1, func, descriptors, flags);
> + return ftw_startup (path, true, (func_callback_t) { .nftw_func = func },
> + descriptors, flags);
> }
Ok.
> - return ftw_startup (path, 1, func, descriptors, flags);
> + return ftw_startup (path, true, (func_callback_t) { .nftw_func = func },
> + descriptors, flags);
Ok.
> NFTW_OLD_NAME (const char *path, NFTW_FUNC_T func, int descriptors, int flags)
> {
> flags &= (FTW_PHYS | FTW_MOUNT | FTW_CHDIR | FTW_DEPTH);
> - return ftw_startup (path, 1, func, descriptors, flags);
> + return ftw_startup (path, true, (func_callback_t) { .nftw_func = func },
> + descriptors, flags);
Ok.
> diff --git a/io/tst-nftw-bz33882.c b/io/tst-nftw-bz33882.c
> +/* Check if nested directory level does not overflow the stack (BZ #33882)
> + Copyright (C) 2026 Free Software Foundation, Inc.
> + This file is part of the GNU C Library.
> +
> + The GNU C Library is free software; you can redistribute it and/or
> + modify it under the terms of the GNU Lesser General Public
> + License as published by the Free Software Foundation; either
> + version 2.1 of the License, or (at your option) any later version.
> +
> + The GNU C Library is distributed in the hope that it will be useful,
> + but WITHOUT ANY WARRANTY; without even the implied warranty of
> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + Lesser General Public License for more details.
> +
> + You should have received a copy of the GNU Lesser General Public
> + License along with the GNU C Library; if not, see
> + <https://www.gnu.org/licenses/>. */
> +
> +#include <errno.h>
> +#include <ftw.h>
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <support/check.h>
> +#include <support/support.h>
> +#include <support/temp_file.h>
> +#include <support/xunistd.h>
> +#include <sys/resource.h>
Ok.
> +/* Typical stack frame for a recursive function is 64–256 bytes, with a nested
> + depth of 5000 would required around 640Kb of stack space. */
> +enum { nested_depth = 5000 };
> +enum { stack_limit_kb = 512 };
> +
> +/* Short name to maximize depth/path ratio. */
> +static const char dir_name[] = "d";
> +
> +static void
> +do_cleanup (void)
> +{
> + xchdir ("..");
> + for (int i = 0; i < nested_depth; i++)
> + {
> + remove (dir_name);
> + xchdir ("..");
> + }
> + remove (dir_name);
> +}
> +#define CLEANUP_HANDLER do_cleanup
Ok.
> +static void
> +check_mkdir (const char *path)
> +{
> + int r = mkdir (path, 0700);
> + /* Some filesystem such as overlayfs does not support larger path required
> + to trigger the internal buffer reallocation. */
> + if (r != 0)
> + {
> + if (errno == ENAMETOOLONG)
> + FAIL_UNSUPPORTED ("the filesystem does not support the required"
> + "large path");
> + else
> + FAIL_EXIT1 ("mkdir (\"%s\", 0%o): %m", path, 0700);
> + }
> +}
We have xmkdirp() that could do this, too, other than the large path check.
> +static int
> +my_func (const char *file, const struct stat *sb, int flag, struct FTW *ftwbuf)
> +{
> + return 0;
> +}
Ok.
> +/* Set the RLIMIT_AS limit to the value in *LIMIT. */
> +static void
> +xsetrlimit_stack (const struct rlimit *limit)
> +{
> + if (setrlimit (RLIMIT_STACK, limit) != 0)
> + FAIL_EXIT1 ("setrlimit (RLIMIT_STACK, %lu): %m",
> + (unsigned long) limit->rlim_cur);
> +}
Ok. Was this checked on Hurd?
> +static int
> +do_test (void)
> +{
> + xsetrlimit_stack (&(struct rlimit) { .rlim_cur = stack_limit_kb * 1024,
> + .rlim_max = stack_limit_kb * 1024 });
> +
> + char *tempdir = support_create_temp_directory ("tst-bz33882");
> +
> + xchdir (tempdir);
> + for (int i = 0; i < nested_depth; i++)
> + {
> + check_mkdir (dir_name);
> + xchdir (dir_name);
> + }
> +
> + TEST_COMPARE (nftw (tempdir, my_func, 20, 0), 0);
> +
> + free (tempdir);
> +
> + do_cleanup ();
> +
> + return 0;
> +}
> +
> +#include <support/test-driver.c>
Ok.
More information about the Libc-alpha
mailing list