bftw: Make sure we don't close a directory while we unwrap it

bftw_cache_reserve() can lead to bftw_cache_pop(), which could close the
directory we're trying to unwrap!  If that happened, we would try
dup_cloexec(-1), which would fail with EBADF, so there was no observable
bug.  But it's better to avoid the whole situation.

bftw: Fix to_close list corruption with !BFS_USE_UNWRAPDIR

It's possible for pincount to drop to zero, then get incremented and
drop back to zero again.  If this happens, we shouldn't add it to the
to_close list twice.

This should fix the intermittent hang on the macOS CI.

Fixes: 815798e1eea7fc8dacd5acab40202ec4d251d517

list: Assert that we're not inserting already-attached nodes

diag: Move enum debug_flags out of ctx.h

bftw: Don't force buffering for parallel dfs

bftw: Fix unbuffered depth-first searches

bftw() implements depth-first search by appending files to a batch, then
prepending the batch to the queue.  When we switched to separate file/
directory queues, this was only implemented for the file queue.
Unbuffered searches don't use the file queue, so they were all breadth-
first in practice.

This meant that iterative deepening (-S ids) was actually "iterative
deepening *breadth*-first search," a horrible strategy with no advantage
over regular breadth-first search.  Now it performs iterative deepening
*depth*-first search, which at least limits its memory consumption.

Fixes: c1b16b49988ecff17ae30978ea14798d95b80018

bftw: Let iterative deepening work depth-first when sorting

bench: Default to --strategies=rust

bench: New --jobs benchmark

bench: Group by strategy in comparison mode

bench: Don't print paths in the --strategies benchmark

bench: Allow format specifiers in (sub)group headers

bar: Replace volatile sig_atomic_t with actual atomics

alloc: Test allocation size overflows

tests/bfs/status: Try to test SIGWINCH

tests: Check for expect_unbuffer too

That's where FreeBSD installs it.

tests: New bfs_pty wrapper for unbuffer

ci: Install expect for unbuffer

tests/bfs: Add a test that runs -status

tests/bfs: Add tests for color autodetection

tests: Respect $NO_COLOR

README: Realign badges

A recent GitHub change broke the nice alignment of the badges to the top
heading, so just put the badges underneath it for now.

bfstd: Add a thread-safe wrapper for strerror()

thread: Define thread_local

config: Fold !__FreeBSD__ into BFS_USE_SYS_CAPABILITY_H

dstring: Limit the special dchar typedef to lint builds

Clang still thinks that alignof(dstr[1]) == 2, so out of an abundance of
caution, don't mess with dchar alignment in normal builds.

build: New lint flag

thread: s/call_once/invoke_once/

call_once() is a reserved identifier from C11.

ci/freebsd: Use tailscale ssh

ci/macos: Don't install coreutils

Since we build our own touch(1) implementation, we no longer need to
work around the macOS bug.

tests: Fix make_deep() on FreeBSD

I keep forgetting that PATH_MAX is only 1024 there.

Merge branch 'io-uring'

Merge branch 'benchmarks'

tests: Don't cd into paths longer than PATH_MAX

This fixes a warning on at least Alpine Linux that looks like

    cd: error retrieving current directory: getcwd: cannot access parent directories: Filename too long

ioq: Use io_uring

Closes #65.

build: Add liburing on Linux

bench: Add a README

bench: Add benchmarking script

bench: New script to clone a git repo without file contents

tests/xtouch: Try creating the immediate parent first

Formatting fixes

bit: Fix UINTPTR_WIDTH typo

bit: Use predefined __*_WIDTH__ macros if we can

dstring: New dchar typedef for dynamic strings

ci/freebsd: Switch to Tailscale OAuth

Use the new list macros

list: New for_[s]list() macros

list: Unify formatting

list: New [S]LIST_EMPTY() macros

list: New [S]LIST_ITEM_INIT() macros

list: Use (void)(...) rather than do { ... } while (0)

This makes everything usable in expression contexts.

README: Add Guix and OpenBSD packages

bftw: Share the bftw_state between iterations of ids/eds

parse: Give more ephemeral_fds to -no{user,group}

Fewer than 3 can lead to

    Assertion failed: (retval->write_queue != -1), function __open_cached_connection, file /usr/src/lib/libc/net/nscachedcli.c, line 224.

on a FreeBSD system with LDAP accounts.

Release 3.0.2

bfstd: Work around a FreeBSD-specific msan issue

Link: https://github.com/llvm/llvm-project/issues/65532

bfstd: Skip a whole loop in dollar_quote() if possible

bfstd: Fix printable_len() off-by-one

If xmbrtowc() fails, or if xiswprint() is false, then we shouldn't
include that wide char in the printable length.

Fixes: 19c96abe0a1ee56cf206fd5e87defb1fd3e0daa5

bfstd: Fix an OOB string index in xmbrtowc()

This bug could be reproduced with something like

    $ bfs -samefile $'\xFA\xFA'
    bfs: error: bfs: dstrnescat@src/dstring.c:252: wordesc() result truncated

or worse, with -DNDEBUG,

    $ bfs -samefile $'.....................\xFA\xFA'
    bfs: error: bfs -samefile $'.....................\xFA\xFA\x00\x55\x53\x45\x52\x3D\x74\x61\x76\x69\x61\x6E\x61\x74\x6F\x72
    bfs: error:               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    bfs: error: No such file or directory.

which prints the memory after the end of the string (in this case, the
environment variable USER=tavianator).

The bug was caused by the line `*i += len`, which was intended to be
`*i = len`.  But actually, the right behaviour seems to be `*i += 1`.

Fixes: 19c96abe0a1ee56cf206fd5e87defb1fd3e0daa5

bftw: Enforce the dirlimit strictly

The previous accounting didn't fully control the number of allocated
bfs_dirs, as the dirlimit was incremented once we popped the directory,
not when we freed it.

bfs uses the C17 standard version

`bfs` uses C17 since 3.0

pwcache: Don't use _SC_GET{PW,GR}_R_SIZE_MAX

They tend be 1024, which is a lot of memory per user/group.  128 is
usually enough, so start there instead.

pwcache: Arena-allocate struct passwd/group

alloc: New varena_grow() function

trie: New trie_clear() function

alloc: New [v]arena_clear() functions

Work around https://github.com/llvm/llvm-project/issues/64946

ioq: New ioq_slot_monitor() helper

docs/bfs.1: Document each -regextype

docs/bfs.1: Document that -help/-version exit immediately

docs/bfs.1: Don't unnecessarily quote {}

docs/bfs.1: Clarify the effects of $POSIXLY_CORRECT

docs/bfs.1: Document use of $PATH

docs/bfs.1: Document that -prune does not work together with -depth

docs/bfs.1: Document the -type d,f syntax

docs/bfs.1: Use a bulleted list for -size units

docs/bfs.1: Give an example with a space separating date from time

docs/bfs.1: Make bold/italic formatting more consistent

tests: Add missing .out file

parse: Allow -files0-from an empty set of paths

This follows a behaviour change in GNU findutils 4.9.0.

bfstd: Don't label a declaration

stat: Don't check for statx() mask bits we already checked for

bfstd: Check multiple chars at once for isascii()

bfstd: Speed up wordesc() by caching isprint()/isspace()

bit: Add a cast to squelch -Wsign-compare

I see this only with musl-gcc for some reason.

README: Official Homebrew formula

An official `bfs` formula has been added to Homebrew now.

README.md: fix reversed examples

Rename Makefile to GNUmakefile

README: Add official Arch Linux package

CFLAGS adjustment in Makefile

`-flto` to `-flto=auto` to eliminate `using serial compilation of 3 LTRANS jobs` gcc warning
see https://stackoverflow.com/questions/72218980/gcc-v12-1-warning-about-serial-compilation

Release 3.0.1

bftw: Use bftw_file->next for multiple lists

A file can be on the to_open and to_read lists at the same time, but
otherwise only one list, so we can save memory by sharing the pointers.

bftw: Use a larger ioq depth

Now that the dirlimit provides backpressure on the number of open
directories, we can use a uniformly larger queue depth for increased
performance.  The current parameters were tuned with a small grid search
on my workstation.

bftw: Add a queue of directories to unwrap

For !BFS_USE_UNWRAPDIR, if a file is still pinned in bftw_closedir(), it
has to stay open until its pincount drops to zero.  Since this happens
in bftw_ioq_pop(), we can't immediately call bftw_unwrapdir() as that
adds to the ioq.  Instead, add it to a list that gets drained by the
next bftw_gc().

bftw: Add dirs to the end of the queue in bftw_ioq_pop()

I tried this before in #105 but it led to performance regressions.  The
key to avoiding those regressions is to put some backpressure on how
many bfs_dir's can be allocated simultaneously.

bftw: Use separate queues for open and closed directories

bftw: Check that file->fd == bfs_dirfd(file->dir) earlier

This has the potential to fail on at least one known platform: macports
with the legacysupport implementation of fdopendir().

Link: https://github.com/macports/macports-ports/pull/19047#issuecomment-1636059809

bftw: Reserve space in the cache before opening files

This fixes a storm of EMFILE retries observed with -j1 on a very large
directory tree.

Fixes: 7888fbababd22190e9f919fc272957426a27969e

bftw: Pass the whole bftw_state to bftw_openat()

This required shuffling a lot of code around.  Hopefully the new order
makes more sense.

bftw: Add bfs_dir allocation wrappers