diff options
60 files changed, 2029 insertions, 572 deletions
diff --git a/.github/diag.sh b/.github/diag.sh index fe78be8..d89e7a4 100755 --- a/.github/diag.sh +++ b/.github/diag.sh @@ -8,9 +8,13 @@ set -eu +SEDFLAGS="-En" +if sed -u 's/s/s/' </dev/null &>/dev/null; then + SEDFLAGS="${SEDFLAGS}u" +fi + filter() { - sed -E 's/^(([^:]*):([^:]*):([^:]*): (warning|error): (.*))$/::\5 file=\2,line=\3,col=\4,title=Compiler \5::\6\ -\1/' + sed $SEDFLAGS 'p; s/^([^:]*):([^:]*):([^:]*): (warning|error): (.*)$/::\4 file=\1,line=\2,col=\3,title=Compiler \4::\5/p' } exec "$@" > >(filter) 2> >(filter >&2) diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml index 20d3797..8e34313 100644 --- a/.github/workflows/ci.yml +++ b/.github/workflows/ci.yml @@ -3,8 +3,8 @@ name: CI on: [push, pull_request] jobs: - linux: - name: Linux + linux-x86: + name: Linux (x86) runs-on: ubuntu-24.04 @@ -35,8 +35,6 @@ jobs: sudo ln -s libacl.so.1 /lib/i386-linux-gnu/libacl.so sudo ln -s libcap.so.2 /lib/i386-linux-gnu/libcap.so sudo ln -s libonig.so.5 /lib/i386-linux-gnu/libonig.so - # Work around https://github.com/actions/runner-images/issues/9491 - sudo sysctl vm.mmap_rnd_bits=28 - name: Run tests run: | @@ -44,22 +42,51 @@ jobs: - uses: actions/upload-artifact@v4 with: - name: linux-config.log + name: linux-x86-config.log + path: distcheck-*/gen/config.log + + linux-arm: + name: Linux (Arm64) + + runs-on: ubuntu-24.04-arm + + steps: + - uses: actions/checkout@v4 + + - name: Install dependencies + run: | + sudo apt-get update -y + sudo apt-get install -y \ + expect \ + mandoc \ + acl \ + libacl1-dev \ + attr \ + libcap2-bin \ + libcap-dev \ + libonig-dev \ + liburing-dev + + - name: Run tests + run: | + .github/diag.sh make -j$(nproc) distcheck + + - uses: actions/upload-artifact@v4 + with: + name: linux-arm-config.log path: distcheck-*/gen/config.log macos: name: macOS - runs-on: macos-14 + runs-on: macos-15 steps: - uses: actions/checkout@v4 - name: Install dependencies run: | - brew install \ - bash \ - expect + brew install bash - name: Run tests run: | @@ -75,10 +102,10 @@ jobs: - uses: actions/checkout@v4 - name: Run tests - uses: cross-platform-actions/action@v0.25.0 + uses: cross-platform-actions/action@v0.27.0 with: operating_system: freebsd - version: "14.1" + version: "14.2" run: | sudo pkg install -y \ @@ -104,10 +131,10 @@ jobs: - uses: actions/checkout@v4 - name: Run tests - uses: cross-platform-actions/action@v0.25.0 + uses: cross-platform-actions/action@v0.27.0 with: operating_system: openbsd - version: "7.5" + version: "7.6" run: | sudo pkg_add \ @@ -133,10 +160,10 @@ jobs: - uses: actions/checkout@v4 - name: Run tests - uses: cross-platform-actions/action@v0.25.0 + uses: cross-platform-actions/action@v0.27.0 with: operating_system: netbsd - version: "10.0" + version: "10.1" run: | PATH="/sbin:/usr/sbin:$PATH" @@ -201,7 +228,7 @@ jobs: - name: Run tests uses: vmactions/omnios-vm@v1 with: - release: "r151048" + release: "r151052" usesh: true prepare: | @@ -1,4 +1,4 @@ -Copyright © 2015-2024 Tavian Barnes <tavianator@tavianator.com> and the bfs contributors +Copyright © 2015-2025 Tavian Barnes <tavianator@tavianator.com> and the bfs contributors Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted. @@ -45,7 +45,8 @@ BINS := \ bin/tests/mksock \ bin/tests/units \ bin/tests/xspawnee \ - bin/tests/xtouch + bin/tests/xtouch \ + bin/bench/ioq all: ${BINS} .PHONY: all @@ -215,6 +216,14 @@ ${DISTCHECKS}:: && ${MAKE} check TEST_FLAGS="--sudo --verbose=skipped" @test "$${GITHUB_ACTIONS-}" != true || printf '::endgroup::\n' +## Benchmarks (`make bench`) + +bench: bin/bench/ioq +.PHONY: bench + +bin/bench/ioq: obj/bench/ioq.o ${LIBBFS} +OBJS += obj/bench/ioq.o + ## Automatic dependency tracking # Rebuild when the configuration changes diff --git a/bench/ioq.c b/bench/ioq.c new file mode 100644 index 0000000..b3fbfbf --- /dev/null +++ b/bench/ioq.c @@ -0,0 +1,323 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +#include "atomic.h" +#include "bfs.h" +#include "bfstd.h" +#include "diag.h" +#include "ioq.h" +#include "sighook.h" +#include "xtime.h" + +#include <errno.h> +#include <locale.h> +#include <signal.h> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include <unistd.h> + +/** Which clock to use for benchmarking. */ +static clockid_t clockid = CLOCK_REALTIME; + +/** Get a current time measurement. */ +static void gettime(struct timespec *tp) { + int ret = clock_gettime(clockid, tp); + bfs_everify(ret == 0, "clock_gettime(%d)", (int)clockid); +} + +/** + * Time measurements. + */ +struct times { + /** The start time. */ + struct timespec start; + + /** Total requests started. */ + size_t pushed; + /** Total requests finished. */ + size_t popped; + + /** Number of timed requests (latency). */ + size_t timed_reqs; + /** The start time for the currently tracked request. */ + struct timespec req_start; + /** Whether a timed request is currently in flight. */ + bool timing; + + /** Latency measurements. */ + struct { + struct timespec min; + struct timespec max; + struct timespec sum; + } latency; +}; + +/** Initialize a timer. */ +static void times_init(struct times *times) { + *times = (struct times) { + .latency = { + .min = { .tv_sec = 1000 }, + }, + }; + gettime(×->start); +} + +/** Start timing a single request. */ +static void start_request(struct times *times) { + gettime(×->req_start); + times->timing = true; +} + +/** Finish timing a request. */ +static void finish_request(struct times *times) { + struct timespec elapsed; + gettime(&elapsed); + timespec_sub(&elapsed, ×->req_start); + + timespec_min(×->latency.min, &elapsed); + timespec_max(×->latency.max, &elapsed); + timespec_add(×->latency.sum, &elapsed); + + bfs_assert(times->timing); + times->timing = false; + ++times->timed_reqs; +} + +/** Add times to the totals, and reset the lap times. */ +static void times_lap(struct times *total, struct times *lap) { + total->pushed += lap->pushed; + total->popped += lap->popped; + total->timed_reqs += lap->timed_reqs; + + timespec_min(&total->latency.min, &lap->latency.min); + timespec_max(&total->latency.max, &lap->latency.max); + timespec_add(&total->latency.sum, &lap->latency.sum); + + times_init(lap); +} + +/** Print some times. */ +static void times_print(const struct times *times, long seconds) { + struct timespec elapsed; + gettime(&elapsed); + timespec_sub(&elapsed, ×->start); + + double fsec = timespec_ns(&elapsed) / 1.0e9; + double iops = times->popped / fsec; + double mean = timespec_ns(×->latency.sum) / times->timed_reqs; + double min = timespec_ns(×->latency.min); + double max = timespec_ns(×->latency.max); + + if (seconds > 0) { + printf("%9ld", seconds); + } else if (elapsed.tv_nsec >= 10 * 1000 * 1000) { + printf("%9.2f", fsec); + } else { + printf("%9.0f", fsec); + } + + printf(" │ %'17.0f │ %'15.0f ∈ [%'6.0f .. %'7.0f]\n", iops, mean, min, max); + fflush(stdout); +} + +/** Push an ioq request. */ +static bool push(struct ioq *ioq, enum ioq_nop_type type, struct times *lap) { + void *ptr = NULL; + + // Track latency for a small fraction of requests + if (!lap->timing && (lap->pushed + 1) % 128 == 0) { + start_request(lap); + ptr = lap; + } + + int ret = ioq_nop(ioq, type, ptr); + if (ret != 0) { + bfs_everify(errno == EAGAIN, "ioq_nop(%d)", (int)type); + return false; + } + + ++lap->pushed; + return true; +} + +/** Pop an ioq request. */ +static bool pop(struct ioq *ioq, struct times *lap, bool block) { + struct ioq_ent *ent = ioq_pop(ioq, block); + if (!ent) { + return false; + } + + if (ent->ptr) { + finish_request(lap); + } + + ioq_free(ioq, ent); + ++lap->popped; + return true; +} + +/** ^C flag. */ +static atomic bool quit = false; + +/** ^C hook. */ +static void ctrlc(int sig, siginfo_t *info, void *arg) { + store(&quit, true, relaxed); +} + +int main(int argc, char *argv[]) { + // Use CLOCK_MONOTONIC if available +#if defined(_POSIX_MONOTONIC_CLOCK) && _POSIX_MONOTONIC_CLOCK >= 0 + if (sysoption(MONOTONIC_CLOCK) > 0) { + clockid = CLOCK_MONOTONIC; + } +#endif + + // Enable thousands separators + setlocale(LC_ALL, ""); + + // -d: queue depth + long depth = 4096; + // -j: threads + long threads = 0; + // -t: timeout + double timeout = 5.0; + // -L|-H: ioq_nop() type + enum ioq_nop_type type = IOQ_NOP_LIGHT; + + const char *cmd = argc > 0 ? argv[0] : "ioq"; + int c; + while (c = getopt(argc, argv, ":d:j:t:LH"), c != -1) { + switch (c) { + case 'd': + if (xstrtol(optarg, NULL, 10, &depth) != 0) { + fprintf(stderr, "%s: Bad depth '%s': %s\n", cmd, optarg, errstr()); + return EXIT_FAILURE; + } + break; + case 'j': + if (xstrtol(optarg, NULL, 10, &threads) != 0) { + fprintf(stderr, "%s: Bad thread count '%s': %s\n", cmd, optarg, errstr()); + return EXIT_FAILURE; + } + break; + case 't': + if (xstrtod(optarg, NULL, &timeout) != 0) { + fprintf(stderr, "%s: Bad timeout '%s': %s\n", cmd, optarg, errstr()); + return EXIT_FAILURE; + } + break; + case 'L': + type = IOQ_NOP_LIGHT; + break; + case 'H': + type = IOQ_NOP_HEAVY; + break; + case ':': + fprintf(stderr, "%s: Missing argument to -%c\n", cmd, optopt); + return EXIT_FAILURE; + case '?': + fprintf(stderr, "%s: Unrecognized option -%c\n", cmd, optopt); + return EXIT_FAILURE; + } + } + + if (threads <= 0) { + threads = xsysconf(_SC_NPROCESSORS_ONLN); + if (threads > 8) { + threads = 8; + } + } + if (threads < 2) { + threads = 2; + } + --threads; + + // Listen for ^C to print the summary + struct sighook *hook = sighook(SIGINT, ctrlc, NULL, SH_CONTINUE | SH_ONESHOT); + + printf("I/O queue benchmark (%s)\n\n", bfs_version); + + printf("[-d] depth: %ld\n", depth); + printf("[-j] threads: %ld (including main)\n", threads + 1); + if (type == IOQ_NOP_HEAVY) { + printf("[-H] type: heavy (with syscalls)\n"); + } else { + printf("[-L] type: light (no syscalls)\n"); + } + printf("\n"); + + printf(" Time (s) │ Throughput (IO/s) │ Latency (ns/IO)\n"); + printf("══════════╪═══════════════════╪═════════════════\n"); + fflush(stdout); + + struct ioq *ioq = ioq_create(depth, threads); + bfs_everify(ioq, "ioq_create(%ld, %ld)", depth, threads); + + // Pre-allocate all the requests + while (ioq_capacity(ioq) > 0) { + int ret = ioq_nop(ioq, type, NULL); + bfs_everify(ret == 0, "ioq_nop(%d)", (int)type); + } + while (true) { + struct ioq_ent *ent = ioq_pop(ioq, true); + if (!ent) { + break; + } + ioq_free(ioq, ent); + } + + struct times total, lap; + times_init(&total); + lap = total; + + long seconds = 0; + while (!load(&quit, relaxed)) { + bool was_timing = lap.timing; + + for (int i = 0; i < 16; ++i) { + bool block = ioq_capacity(ioq) == 0; + if (!pop(ioq, &lap, block)) { + break; + } + } + + if (was_timing && !lap.timing) { + struct timespec elapsed; + gettime(&elapsed); + timespec_sub(&elapsed, &total.start); + + if (elapsed.tv_sec > seconds) { + seconds = elapsed.tv_sec; + times_print(&lap, seconds); + times_lap(&total, &lap); + } + + double ns = timespec_ns(&elapsed); + if (timeout > 0 && ns >= timeout * 1.0e9) { + break; + } + } + + for (int i = 0; i < 8; ++i) { + if (!push(ioq, type, &lap)) { + break; + } + } + ioq_submit(ioq); + } + + while (pop(ioq, &lap, true)); + times_lap(&total, &lap); + + if (load(&quit, relaxed)) { + printf("\r────^C────┼───────────────────┼─────────────────\n"); + } else { + printf("──────────┼───────────────────┼─────────────────\n"); + } + times_print(&total, 0); + + ioq_destroy(ioq); + sigunhook(hook); + return 0; +} diff --git a/build/flags.mk b/build/flags.mk index 2562e03..462f74b 100644 --- a/build/flags.mk +++ b/build/flags.mk @@ -8,7 +8,7 @@ include gen/vars.mk # Internal flags _CPPFLAGS := -Isrc -Igen -include src/prelude.h -_CFLAGS := -std=c17 -pthread +_CFLAGS := -std=c17 _LDFLAGS := _LDLIBS := @@ -16,6 +16,7 @@ _LDLIBS := LDLIBS,DragonFly := -lposix1e LDLIBS,Linux := -lrt LDLIBS,NetBSD := -lutil +LDLIBS,QNX := -lregex -lsocket LDLIBS,SunOS := -lsec -lsocket -lnsl _LDLIBS += ${LDLIBS,${OS}} @@ -29,6 +30,9 @@ _GCOV := ${TRUTHY,${GCOV}} _LINT := ${TRUTHY,${LINT}} _RELEASE := ${TRUTHY,${RELEASE}} +LTO ?= ${RELEASE} +_LTO := ${TRUTHY,${LTO}} + ASAN_CFLAGS,y := -fsanitize=address LSAN_CFLAGS,y := -fsanitize=leak MSAN_CFLAGS,y := -fsanitize=memory -fsanitize-memory-track-origins @@ -61,11 +65,14 @@ _CPPFLAGS += ${LINT_CPPFLAGS,${_LINT}} _CFLAGS += ${LINT_CFLAGS,${_LINT}} RELEASE_CPPFLAGS,y := -DNDEBUG -RELEASE_CFLAGS,y := -O3 -flto=auto +RELEASE_CFLAGS,y := -O3 _CPPFLAGS += ${RELEASE_CPPFLAGS,${_RELEASE}} _CFLAGS += ${RELEASE_CFLAGS,${_RELEASE}} +LTO_CFLAGS,y := -flto=auto +_CFLAGS += ${LTO_CFLAGS,${_LTO}} + # Configurable flags CFLAGS ?= -g -Wall @@ -90,7 +97,8 @@ AUTO_FLAGS := \ gen/flags/Wstrict-prototypes.mk \ gen/flags/Wundef-prefix.mk \ gen/flags/bind-now.mk \ - gen/flags/deps.mk + gen/flags/deps.mk \ + gen/flags/pthread.mk gen/flags.mk: ${AUTO_FLAGS} ${MSG} "[ GEN] $@" diff --git a/build/flags/pthread.c b/build/flags/pthread.c new file mode 100644 index 0000000..db09aa4 --- /dev/null +++ b/build/flags/pthread.c @@ -0,0 +1,8 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +/// _CFLAGS += -pthread + +int main(void) { + return 0; +} diff --git a/build/has/compound-literal-storage.c b/build/has/compound-literal-storage.c new file mode 100644 index 0000000..e2281e1 --- /dev/null +++ b/build/has/compound-literal-storage.c @@ -0,0 +1,6 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +int main(void) { + return (static int){0}; +} diff --git a/build/has/dprintf.c b/build/has/dprintf.c new file mode 100644 index 0000000..c206fa3 --- /dev/null +++ b/build/has/dprintf.c @@ -0,0 +1,8 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +#include <stdio.h> + +int main(void) { + return dprintf(1, "%s\n", "Hello world!"); +} diff --git a/build/has/pragma-nounroll.c b/build/has/pragma-nounroll.c new file mode 100644 index 0000000..2bdae14 --- /dev/null +++ b/build/has/pragma-nounroll.c @@ -0,0 +1,10 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +/// -Werror + +int main(void) { +#pragma nounroll + for (int i = 0; i < 100; ++i); + return 0; +} diff --git a/build/has/pthread-set-name-np.c b/build/has/pthread-set-name-np.c new file mode 100644 index 0000000..324aab9 --- /dev/null +++ b/build/has/pthread-set-name-np.c @@ -0,0 +1,10 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +#include <pthread.h> +#include <pthread_np.h> + +int main(void) { + pthread_set_name_np(pthread_self(), "name"); + return 0; +} diff --git a/build/has/pthread-setname-np.c b/build/has/pthread-setname-np.c new file mode 100644 index 0000000..a3b94c1 --- /dev/null +++ b/build/has/pthread-setname-np.c @@ -0,0 +1,8 @@ +// Copyright © Tavian Barnes <tavianator@tavianator.com> +// SPDX-License-Identifier: 0BSD + +#include <pthread.h> + +int main(void) { + return pthread_setname_np(pthread_self(), "name"); +} diff --git a/build/header.mk b/build/header.mk index f940e52..f8aee4b 100644 --- a/build/header.mk +++ b/build/header.mk @@ -19,7 +19,9 @@ HEADERS := \ gen/has/acl-is-trivial-np.h \ gen/has/acl-trivial.h \ gen/has/builtin-riscv-pause.h \ + gen/has/compound-literal-storage.h \ gen/has/confstr.h \ + gen/has/dprintf.h \ gen/has/extattr-get-file.h \ gen/has/extattr-get-link.h \ gen/has/extattr-list-file.h \ @@ -35,9 +37,12 @@ HEADERS := \ gen/has/getprogname.h \ gen/has/io-uring-max-workers.h \ gen/has/pipe2.h \ + gen/has/pragma-nounroll.h \ gen/has/posix-getdents.h \ gen/has/posix-spawn-addfchdir-np.h \ gen/has/posix-spawn-addfchdir.h \ + gen/has/pthread-set-name-np.h \ + gen/has/pthread-setname-np.h \ gen/has/st-acmtim.h \ gen/has/st-acmtimespec.h \ gen/has/st-birthtim.h \ diff --git a/build/version.sh b/build/version.sh index ba5447f..82b7389 100755 --- a/build/version.sh +++ b/build/version.sh @@ -14,5 +14,5 @@ if [ "${VERSION-}" ]; then elif [ -e "$DIR/.git" ] && command -v git >/dev/null 2>&1; then git -C "$DIR" describe --always --dirty else - echo "4.0.4" + echo "4.0.5" fi @@ -70,9 +70,16 @@ Any other arguments will be passed directly to the $MAKE invocation, e.g. EOF } +# Report a warning +warn() { + fmt="$1" + shift + printf "%s: warning: $fmt\\n" "$0" "$@" >&2 +} + # Report an argument parsing error invalid() { - printf 'error: Unrecognized option "%s"\n\n' "$1" >&2 + printf '%s: error: Unrecognized option "%s"\n\n' "$0" "$1" >&2 printf 'Run %s --help for more information.\n' "$0" >&2 exit 1 } @@ -88,7 +95,7 @@ nproc() { } # Save the ./configure command line for bfs --version -export CONFFLAGS="$*" +export CONFFLAGS="" # Default to `make` MAKE="${MAKE-make}" @@ -97,6 +104,13 @@ MAKE="${MAKE-make}" for arg; do shift + # Only add --options to CONFFLAGS, so we don't print FLAG=values twice in bfs --version + case "$arg" in + -*) + CONFFLAGS="${CONFFLAGS}${CONFFLAGS:+ }${arg}" + ;; + esac + # --[(enable|disable|with|without)-]$name[=$value] value="${arg#*=}" name="${arg%%=*}" @@ -136,7 +150,7 @@ for arg; do --enable-*) arg="--with-${arg#--*-}" ;; --disable-*) arg="--without-${arg#--*-}" ;; esac - printf 'warning: Treating "%s" like "%s"\n' "$old" "$arg" >&2 + warn 'Treating "%s" like "%s"' "$old" "$arg" ;; esac ;; @@ -150,7 +164,7 @@ for arg; do --enable-*|--disable-*) case "$name" in - release|asan|lsan|msan|tsan|ubsan|lint|gcov) + release|lto|asan|lsan|msan|tsan|ubsan|lint|gcov) set -- "$@" "$NAME=$yn" ;; *) @@ -175,13 +189,32 @@ for arg; do ;; --infodir=*|--build=*|--host=*|--target=*) - printf 'warning: Ignoring option "%s"\n' "$arg" >&2 + warn 'Ignoring option "%s"' "$arg" ;; MAKE=*) MAKE="$value" ;; + # Warn about MAKE variables that have documented configure flags + RELEASE=*|LTO=*|ASAN=*|LSAN=*|MSAN=*|TSAN=*|UBSAN=*|LINT=*|GCOV=*) + name=$(printf '%s' "$NAME" | tr 'A-Z_' 'a-z-') + warn '"%s" is deprecated; use --enable-%s' "$arg" "$name" + set -- "$@" "$arg" + ;; + + PREFIX=*|MANDIR=*|VERSION=*) + name=$(printf '%s' "$NAME" | tr 'A-Z_' 'a-z-') + warn '"%s" is deprecated; use --%s=%s' "$arg" "$name" "$value" + set -- "$@" "$arg" + ;; + + WITH_*=*) + name=$(printf '%s' "$NAME" | tr 'A-Z_' 'a-z-') + warn '"%s" is deprecated; use --%s' "$arg" "$name" + set -- "$@" "$arg" + ;; + # make flag (-j2) or variable (CC=clang) -*|*=*) set -- "$@" "$arg" diff --git a/docs/CHANGELOG.md b/docs/CHANGELOG.md index 7f3c7b7..ce011fe 100644 --- a/docs/CHANGELOG.md +++ b/docs/CHANGELOG.md @@ -1,12 +1,30 @@ 4.* === +4.0.5 +----- + +**January 18, 2025** + +### Bug fixes + +- Fixed a bug that could cause child processes (e.g. from `-exec`) to run with all signals blocked. + The bug was introduced in version 3.3. + ([`af207e7`](https://github.com/tavianator/bfs/commit/af207e702148e5c9ae08047d7a2dce6394653b62)) + +### Changes + +- Fixed the build against old liburing versions + ([#147](https://github.com/tavianator/bfs/issues/147)) + +- Async I/O performance optimizations + + 4.0.4 ----- **October 31, 2024** - ## Bug fixes - Fixed a man page typo @@ -1,4 +1,6 @@ -.TH BFS 1 2024-10-31 "bfs 4.0.4" +.\" Copyright © Tavian Barnes <tavianator@tavianator.com> +.\" SPDX-License-Identifier: 0BSD +.TH BFS 1 2025-01-18 "bfs 4.0.5" .SH NAME bfs \- breadth-first search for your files .SH SYNOPSIS @@ -90,7 +92,9 @@ Follow all symbolic links. Never follow symbolic links (the default). .TP .B \-E -Use extended regular expressions (same as \fB\-regextype \fIposix-extended\fR). +Use extended regular expressions (same as +.B \-regextype +.IR posix-extended ). .TP .B \-X Filter out files with @@ -109,19 +113,20 @@ The sorting takes place within each directory separately, which makes it differe but still provides a deterministic ordering. .TP .B \-x -Don't descend into other mount points (same as \fB\-xdev\fR). +Don't descend into other mount points (same as +.BR \-xdev ). .TP -\fB\-f \fIPATH\fR +.BI "\-f " PATH Treat .I PATH as a path to search (useful if it begins with a dash). .TP -\fB\-D \fIFLAG\fR +.BI "\-D " FLAG Turn on a debugging flag (see .B \-D .IR help ). .PP -\fB\-O\fIN\fR +.BI \-O N .RS Enable optimization level .I N @@ -177,14 +182,14 @@ Typically far faster than .IR ids . .RE .TP -\fB\-j\fIN\fR +.BI \-j N Search with .I N threads in parallel (default: number of CPUs, up to .IR 8 ). .SH OPERATORS .TP -\fB( \fIexpression \fB)\fR +.BI "( " expression " )" Parentheses are used for grouping expressions together. You'll probably have to write .B \e( @@ -194,18 +199,25 @@ to avoid the parentheses being interpreted by the shell. .PP \fB! \fIexpression\fR .br -\fB\-not \fIexpression\fR +.B \-not +.I expression .RS The "not" operator: returns the negation of the truth value of the .IR expression . -You may have to write \fB\e! \fIexpression\fR to avoid \fB!\fR being interpreted by the shell. +You may have to write \fB\e! \fIexpression\fR to avoid +.B ! +being interpreted by the shell. .RE .PP -\fIexpression\fR \fIexpression\fR +.I expression expression .br -\fIexpression \fB\-a \fIexpression\fR +.I expression +.B \-a +.I expression .br -\fIexpression \fB\-and \fIexpression\fR +.I expression +.B \-and +.I expression .RS Short-circuiting "and" operator: if the left-hand .I expression @@ -217,9 +229,13 @@ otherwise, returns .BR false . .RE .PP -\fIexpression \fB\-o \fIexpression\fR +.I expression +.B \-o +.I expression .br -\fIexpression \fB\-or \fIexpression\fR +.I expression +.B \-or +.I expression .RS Short-circuiting "or" operator: if the left-hand .I expression @@ -231,14 +247,14 @@ otherwise, returns .BR true . .RE .TP -\fIexpression \fB, \fIexpression\fR +.IB "expression " , " expression" The "comma" operator: evaluates the left-hand .I expression but discards the result, returning the right-hand .IR expression . .SH SPECIAL FORMS .TP -\fB\-exclude \fIexpression\fR +.BI "\-exclude " expression Exclude all paths matching the .I expression from the search. @@ -286,7 +302,7 @@ Search in post-order (descendents first). Follow all symbolic links (same as .BR \-L ). .TP -\fB\-files0\-from \fIFILE\fR +.BI "\-files0\-from " FILE Treat the NUL ('\e0')-separated paths in .I FILE as starting points for the search. @@ -295,9 +311,9 @@ Pass .I \- to read the paths from standard input. .PP -\fB\-ignore_readdir_race\fR +.B \-ignore_readdir_race .br -\fB\-noignore_readdir_race\fR +.B \-noignore_readdir_race .RS Whether to report an error if .B bfs @@ -305,9 +321,11 @@ detects that the file tree is modified during the search (default: .BR \-noignore_readdir_race ). .RE .PP -\fB\-maxdepth \fIN\fR +.B \-maxdepth +.I N .br -\fB\-mindepth \fIN\fR +.B \-mindepth +.I N .RS Ignore files deeper/shallower than .IR N . @@ -325,7 +343,7 @@ Exclude hidden files and directories. .B \-noleaf Ignored; for compatibility with GNU find. .TP -\fB\-regextype \fITYPE\fR +.BI "\-regextype " TYPE Use .IR TYPE -flavored regular expressions. @@ -403,13 +421,17 @@ Find files minutes ago. .RE .PP -\fB\-anewer \fIFILE\fR +.B \-anewer +.I FILE .br -\fB\-Bnewer \fIFILE\fR +.B \-Bnewer +.I FILE .br -\fB\-cnewer \fIFILE\fR +.B \-cnewer +.I FILE .br -\fB\-mnewer \fIFILE\fR +.B \-mnewer +.I FILE .RS Find files .BR a ccessed/ B irthed/ c hanged/ m odified @@ -418,13 +440,17 @@ more recently than was modified. .RE .PP -\fB\-asince \fITIME\fR +.B \-asince +.I TIME .br -\fB\-Bsince \fITIME\fR +.B \-Bsince +.I TIME .br -\fB\-csince \fITIME\fR +.B \-csince +.I TIME .br -\fB\-msince \fITIME\fR +.B \-msince +.I TIME .RS Find files .BR a ccessed/ B irthed/ c hanged/ m odified @@ -454,7 +480,7 @@ Find files with POSIX.1e .BR capabilities (7) set. .TP -\fB\-context \fIGLOB\fR +.BI "\-context " GLOB Find files whose SELinux context matches the .IR GLOB . .TP @@ -485,7 +511,7 @@ Always false/true. Find files with matching inode .BR FLAGS . .TP -\fB\-fstype \fITYPE\fR +.BI "\-fstype " TYPE Find files on file systems with the given .IR TYPE . .PP @@ -497,9 +523,11 @@ Find files owned by group/user ID .IR N . .RE .PP -\fB\-group \fINAME\fR +.B \-group +.I NAME .br -\fB\-user \fINAME\fR +.B \-user +.I NAME .RS Find files owned by the group/user .IR NAME . @@ -509,15 +537,20 @@ Find files owned by the group/user Find hidden files (those beginning with .IR . ). .PP -\fB\-ilname \fIGLOB\fR +.B \-ilname +.I GLOB .br -\fB\-iname \fIGLOB\fR +.B \-iname +.I GLOB .br -\fB\-ipath \fIGLOB\fR +.B \-ipath +.I GLOB .br -\fB\-iregex \fIREGEX\fR +.B \-iregex +.I REGEX .br -\fB\-iwholename \fIGLOB\fR +.B \-iwholename +.I GLOB .RS Case-insensitive versions of .BR \-lname / \-name / \-path / \-regex / \-wholename . @@ -532,19 +565,19 @@ Find files with .I N hard links. .TP -\fB\-lname \fIGLOB\fR +.BI "\-lname " GLOB Find symbolic links whose target matches the .IR GLOB . .TP -\fB\-name \fIGLOB\fR +.BI "\-name " GLOB Find files whose name matches the .IR GLOB . .TP -\fB\-newer \fIFILE\fR +.BI "\-newer " FILE Find files newer than .IR FILE . .TP -\fB\-newer\fIXY \fIREFERENCE\fR +.BI \-newer "XY REFERENCE" Find files whose .I X time is newer than the @@ -580,9 +613,11 @@ as an ISO 8601-style timestamp. For example: Find files owned by nonexistent groups/users. .RE .PP -\fB\-path \fIGLOB\fR +.B \-path +.I GLOB .br -\fB\-wholename \fIGLOB\fR +.B \-wholename +.I GLOB .RS Find files whose entire path matches the .IR GLOB . @@ -591,15 +626,15 @@ Find files whose entire path matches the \fB\-perm\fR [\fI\-+/\fR]\fIMODE\fR Find files with a matching mode. .TP -\fB\-regex \fIREGEX\fR +.BI "\-regex " REGEX Find files whose entire path matches the regular expression .IR REGEX . .TP -\fB\-samefile \fIFILE\fR +.BI "\-samefile " FILE Find hard links to .IR FILE . .TP -\fB\-since \fITIME\fR +.BI "\-since " TIME Find files modified since the ISO 8601-style timestamp .IR TIME . See @@ -678,7 +713,7 @@ days after they were changed. Find files with extended attributes .RB ( xattr (7)). .TP -\fB\-xattrname\fR \fINAME\fR +.BI "\-xattrname " NAME Find files with the extended attribute .IR NAME . .TP @@ -691,23 +726,27 @@ would not, and vice versa. .br .B \-rm .RS -Delete any found files (implies \fB-depth\fR). +Delete any found files (implies +.BR \-depth ). .RE .TP -\fB\-exec \fIcommand ... {} ;\fR +.BI "\-exec " "command ... {} ;" Execute a command. .TP -\fB\-exec \fIcommand ... {} +\fR +.BI "\-exec " "command ... {} +" Execute a command with multiple files at once. .TP -\fB\-ok \fIcommand ... {} ;\fR +.BI "\-ok " "command ... {} ;" Prompt the user whether to execute a command. .PP -\fB\-execdir \fIcommand ... {} ;\fR +.B \-execdir +.I command ... {} ; .br -\fB\-execdir \fIcommand ... {} +\fR +.B \-execdir +.I command ... {} + .br -\fB\-okdir \fIcommand ... {} ;\fR +.B \-okdir +.I command ... {} ; .RS Like .BR \-exec / \-ok , @@ -719,13 +758,17 @@ Exit immediately with the given status .RI ( 0 if unspecified). .PP -\fB\-fls \fIFILE\fR +.B \-fls +.I FILE .br -\fB\-fprint \fIFILE\fR +.B \-fprint +.I FILE .br -\fB\-fprint0 \fIFILE\fR +.B \-fprint0 +.I FILE .br -\fB\-fprintf \fIFILE FORMAT\fR +.B \-fprintf +.I FILE FORMAT .RS Like .BR \-ls / \-print / \-print0 / \-printf , @@ -734,7 +777,7 @@ but write to instead of standard output. .RE .TP -\fB\-limit \fIN\fR +.BI "\-limit " N Quit once this action is evaluated .I N times. @@ -755,7 +798,7 @@ Useful in conjunction with .B xargs .IR \-0 . .TP -\fB\-printf \fIFORMAT\fR +.BI "\-printf " FORMAT Print according to a format string (see .BR find (1)). These additional format directives are supported: @@ -901,7 +944,7 @@ is quoted to ensure the glob is processed by .B bfs rather than the shell. .TP -\fBbfs \-name access_log \-L \fI/var\fR +.BI "bfs \-name access_log \-L " /var Finds all files named .B access_log under @@ -910,7 +953,7 @@ following symbolic links. .B bfs allows flags and paths to appear anywhere on the command line. .TP -\fBbfs \fI~ \fB\-not \-user $USER\fR +.BI "bfs " ~ " \-not \-user $USER" Prints all files in your home directory not owned by you. .TP .B bfs \-xtype l diff --git a/src/alloc.c b/src/alloc.c index ef9f6ab..f505eda 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -106,7 +106,7 @@ void *reserve(void *ptr, size_t align, size_t size, size_t count) { // If we stayed within the same size class, reuse ptr. if (count & (count - 1)) { // Tell sanitizers about the new array element - sanitize_alloc((char *)ptr + old_size, size); + sanitize_resize(ptr, old_size, old_size + size, bit_ceil(count) * size); errno = 0; return ptr; } @@ -121,7 +121,7 @@ void *reserve(void *ptr, size_t align, size_t size, size_t count) { } // Pretend we only allocated one more element - sanitize_free((char *)ret + old_size + size, new_size - old_size - size); + sanitize_resize(ret, new_size, old_size + size, new_size); errno = 0; return ret; } @@ -304,8 +304,7 @@ void *varena_alloc(struct varena *varena, size_t count) { } // Tell the sanitizers the exact size of the allocated struct - sanitize_free(ret, arena->size); - sanitize_alloc(ret, varena_exact_size(varena, count)); + sanitize_resize(ret, arena->size, varena_exact_size(varena, count), arena->size); return ret; } @@ -317,15 +316,14 @@ void *varena_realloc(struct varena *varena, void *ptr, size_t old_count, size_t return NULL; } - size_t new_exact_size = varena_exact_size(varena, new_count); - size_t old_exact_size = varena_exact_size(varena, old_count); + size_t old_size = old_arena->size; + size_t new_size = new_arena->size; if (new_arena == old_arena) { - if (new_count < old_count) { - sanitize_free((char *)ptr + new_exact_size, old_exact_size - new_exact_size); - } else if (new_count > old_count) { - sanitize_alloc((char *)ptr + old_exact_size, new_exact_size - old_exact_size); - } + sanitize_resize(ptr, + varena_exact_size(varena, old_count), + varena_exact_size(varena, new_count), + new_size); return ptr; } @@ -334,17 +332,18 @@ void *varena_realloc(struct varena *varena, void *ptr, size_t old_count, size_t return NULL; } - size_t old_size = old_arena->size; - sanitize_alloc(ptr, old_size); + // Non-sanitized builds don't bother computing exact sizes, and just use + // the potentially-larger arena size for each size class instead. To + // allow the below memcpy() to work with the less-precise sizes, expand + // the old allocation to its full capacity. + sanitize_resize(ptr, varena_exact_size(varena, old_count), old_size, old_size); - size_t new_size = new_arena->size; size_t min_size = new_size < old_size ? new_size : old_size; memcpy(ret, ptr, min_size); arena_free(old_arena, ptr); - sanitize_free(ret, new_size); - sanitize_alloc(ret, new_exact_size); + sanitize_resize(ret, new_size, varena_exact_size(varena, new_count), new_size); return ret; } @@ -218,4 +218,15 @@ extern const char bfs_ldlibs[]; # define _target_clones(...) #endif +/** + * Optimization hint to not unroll a loop. + */ +#if BFS_HAS_PRAGMA_NOUNROLL +# define _nounroll _Pragma("nounroll") +#elif __GNUC__ && !__clang__ +# define _nounroll _Pragma("GCC unroll 0") +#else +# define _nounroll +#endif + #endif // BFS_H diff --git a/src/bfstd.c b/src/bfstd.c index b29fb7b..f2938ad 100644 --- a/src/bfstd.c +++ b/src/bfstd.c @@ -211,35 +211,77 @@ const char *xgetprogname(void) { return cmd; } -int xstrtoll(const char *str, char **end, int base, long long *value) { - // strtoll() skips leading spaces, but we want to reject them +/** Common prologue for xstrto*() wrappers. */ +static int xstrtox_prologue(const char *str) { + // strto*() skips leading spaces, but we want to reject them if (xisspace(str[0])) { errno = EINVAL; return -1; } - // If end is NULL, make sure the entire string is valid - bool entire = !end; - char *endp; - if (!end) { - end = &endp; - } - errno = 0; - long long result = strtoll(str, end, base); + return 0; +} + +/** Common epilogue for xstrto*() wrappers. */ +static int xstrtox_epilogue(const char *str, char **end, char *endp) { if (errno != 0) { return -1; } - if (*end == str || (entire && **end != '\0')) { + if (end) { + *end = endp; + } + + // If end is NULL, make sure the entire string is valid + if (endp == str || (!end && *endp != '\0')) { errno = EINVAL; return -1; } - *value = result; return 0; } +int xstrtol(const char *str, char **end, int base, long *value) { + if (xstrtox_prologue(str) != 0) { + return -1; + } + + char *endp; + *value = strtol(str, &endp, base); + return xstrtox_epilogue(str, end, endp); +} + +int xstrtoll(const char *str, char **end, int base, long long *value) { + if (xstrtox_prologue(str) != 0) { + return -1; + } + + char *endp; + *value = strtoll(str, &endp, base); + return xstrtox_epilogue(str, end, endp); +} + +int xstrtof(const char *str, char **end, float *value) { + if (xstrtox_prologue(str) != 0) { + return -1; + } + + char *endp; + *value = strtof(str, &endp); + return xstrtox_epilogue(str, end, endp); +} + +int xstrtod(const char *str, char **end, double *value) { + if (xstrtox_prologue(str) != 0) { + return -1; + } + + char *endp; + *value = strtod(str, &endp); + return xstrtox_epilogue(str, end, endp); +} + /** Compile and execute a regular expression for xrpmatch(). */ static int xrpregex(nl_item item, const char *response) { const char *pattern = nl_langinfo(item); @@ -482,7 +524,9 @@ int rlim_cmp(rlim_t a, rlim_t b) { } dev_t xmakedev(int ma, int mi) { -#ifdef makedev +#if __QNX__ + return makedev(0, ma, mi); +#elif defined(makedev) return makedev(ma, mi); #else return (ma << 8) | mi; @@ -736,35 +780,31 @@ size_t asciilen(const char *str) { } size_t asciinlen(const char *str, size_t n) { + const unsigned char *ustr = (const unsigned char *)str; size_t i = 0; -#if SIZE_WIDTH % 8 == 0 // Word-at-a-time isascii() - for (size_t word; i + sizeof(word) <= n; i += sizeof(word)) { - memcpy(&word, str + i, sizeof(word)); - - const size_t mask = (SIZE_MAX / 0xFF) << 7; // 0x808080... - word &= mask; - if (!word) { - continue; - } - -#if ENDIAN_NATIVE == ENDIAN_BIG - word = bswap(word); -#elif ENDIAN_NATIVE != ENDIAN_LITTLE - break; +#define CHUNK(n) CHUNK_(uint##n##_t, load8_leu##n) +#define CHUNK_(type, load8) \ + while (n - i >= sizeof(type)) { \ + type word = load8(ustr + i); \ + type mask = (((type)-1) / 0xFF) << 7; /* 0x808080.. */ \ + word &= mask; \ + i += trailing_zeros(word) / 8; \ + if (word) { \ + return i; \ + } \ + } + +#if SIZE_WIDTH >= 64 + CHUNK(64); #endif + CHUNK(32); + CHUNK(16); + CHUNK(8); - size_t first = trailing_zeros(word) / 8; - return i + first; - } -#endif - - for (; i < n; ++i) { - if (!xisascii(str[i])) { - break; - } - } +#undef CHUNK_ +#undef CHUNK return i; } diff --git a/src/bfstd.h b/src/bfstd.h index 97867fd..84f92ec 100644 --- a/src/bfstd.h +++ b/src/bfstd.h @@ -179,23 +179,26 @@ int open_cterm(int flags); const char *xgetprogname(void); /** + * Wrapper for strtol() that forbids leading spaces. + */ +int xstrtol(const char *str, char **end, int base, long *value); + +/** * Wrapper for strtoll() that forbids leading spaces. - * - * @str - * The string to parse. - * @end - * If non-NULL, will hold a pointer to the first invalid character. - * If NULL, the entire string must be valid. - * @base - * The base for the conversion, or 0 to auto-detect. - * @value - * Will hold the parsed integer value, on success. - * @return - * 0 on success, -1 on failure. */ int xstrtoll(const char *str, char **end, int base, long long *value); /** + * Wrapper for strtof() that forbids leading spaces. + */ +int xstrtof(const char *str, char **end, float *value); + +/** + * Wrapper for strtod() that forbids leading spaces. + */ +int xstrtod(const char *str, char **end, double *value); + +/** * Process a yes/no prompt. * * @return 1 for yes, 0 for no, and -1 for unknown. @@ -1008,6 +1008,7 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) { return -1; } + ioq_submit(ioq); struct ioq_ent *ent = ioq_pop(ioq, block); if (!ent) { return -1; @@ -1051,6 +1052,10 @@ static int bftw_ioq_pop(struct bftw_state *state, bool block) { bftw_queue_attach(&state->fileq, file, true); break; + + default: + bfs_bug("Unexpected ioq op %d", (int)op); + break; } ioq_free(ioq, ent); @@ -1953,6 +1958,10 @@ static void bftw_flush(struct bftw_state *state) { bftw_queue_flush(&state->dirq); bftw_ioq_opendirs(state); + + if (state->ioq) { + ioq_submit(state->ioq); + } } /** Close the current directory. */ @@ -148,7 +148,7 @@ # define INTMAX_WIDTH UINTMAX_WIDTH #endif -// C23 polyfill: byte order +// N3022 polyfill: byte order #ifdef __STDC_ENDIAN_LITTLE__ # define ENDIAN_LITTLE __STDC_ENDIAN_LITTLE__ @@ -250,6 +250,58 @@ static inline uint8_t bswap_u8(uint8_t n) { */ #define bswap(n) UINT_SELECT(n, bswap)(n) +#define LOAD8_LEU8(ptr, i, n) ((uint##n##_t)((const unsigned char *)ptr)[(i) / 8] << (i)) +#define LOAD8_BEU8(ptr, i, n) ((uint##n##_t)((const unsigned char *)ptr)[(i) / 8] << (n - (i) - 8)) + +/** Load a little-endian 8-bit word. */ +static inline uint8_t load8_leu8(const void *ptr) { + return LOAD8_LEU8(ptr, 0, 8); +} + +/** Load a big-endian 8-bit word. */ +static inline uint8_t load8_beu8(const void *ptr) { + return LOAD8_BEU8(ptr, 0, 8); +} + +#define LOAD8_LEU16(ptr, i, n) (LOAD8_LEU8(ptr, i, n) | LOAD8_LEU8(ptr, i + 8, n)) +#define LOAD8_BEU16(ptr, i, n) (LOAD8_BEU8(ptr, i, n) | LOAD8_BEU8(ptr, i + 8, n)) + +/** Load a little-endian 16-bit word. */ +static inline uint16_t load8_leu16(const void *ptr) { + return LOAD8_LEU16(ptr, 0, 16); +} + +/** Load a big-endian 16-bit word. */ +static inline uint16_t load8_beu16(const void *ptr) { + return LOAD8_BEU16(ptr, 0, 16); +} + +#define LOAD8_LEU32(ptr, i, n) (LOAD8_LEU16(ptr, i, n) | LOAD8_LEU16(ptr, i + 16, n)) +#define LOAD8_BEU32(ptr, i, n) (LOAD8_BEU16(ptr, i, n) | LOAD8_BEU16(ptr, i + 16, n)) + +/** Load a little-endian 32-bit word. */ +static inline uint32_t load8_leu32(const void *ptr) { + return LOAD8_LEU32(ptr, 0, 32); +} + +/** Load a big-endian 32-bit word. */ +static inline uint32_t load8_beu32(const void *ptr) { + return LOAD8_BEU32(ptr, 0, 32); +} + +#define LOAD8_LEU64(ptr, i, n) (LOAD8_LEU32(ptr, i, n) | LOAD8_LEU32(ptr, i + 32, n)) +#define LOAD8_BEU64(ptr, i, n) (LOAD8_BEU32(ptr, i, n) | LOAD8_BEU32(ptr, i + 32, n)) + +/** Load a little-endian 64-bit word. */ +static inline uint64_t load8_leu64(const void *ptr) { + return LOAD8_LEU64(ptr, 0, 64); +} + +/** Load a big-endian 64-bit word. */ +static inline uint64_t load8_beu64(const void *ptr) { + return LOAD8_BEU64(ptr, 0, 64); +} + // C23 polyfill: bit utilities #if __STDC_VERSION_STDBIT_H__ >= C23 diff --git a/src/color.c b/src/color.c index e7f0973..0cc950b 100644 --- a/src/color.c +++ b/src/color.c @@ -143,13 +143,7 @@ static int init_esc(struct colors *colors, const char *name, const char *value, *field = esc; - struct trie_leaf *leaf = trie_insert_str(&colors->names, name); - if (!leaf) { - return -1; - } - - leaf->value = field; - return 0; + return trie_set_str(&colors->names, name, field); } /** Check if an escape sequence is equal to a string. */ @@ -159,8 +153,7 @@ static bool esc_eq(const struct esc_seq *esc, const char *str, size_t len) { /** Get an escape sequence from the table. */ static struct esc_seq **get_esc(const struct colors *colors, const char *name) { - const struct trie_leaf *leaf = trie_find_str(&colors->names, name); - return leaf ? leaf->value : NULL; + return trie_get_str(&colors->names, name); } /** Append an escape sequence to a string. */ @@ -225,13 +218,7 @@ static int insert_ext(struct trie *trie, struct ext_color *ext) { } size_t len = ext->len + 1; - leaf = trie_insert_mem(trie, ext->ext, len); - if (!leaf) { - return -1; - } - - leaf->value = ext; - return 0; + return trie_set_mem(trie, ext->ext, len, ext); } /** Set the color for an extension. */ @@ -975,7 +962,7 @@ static const struct esc_seq *file_color(const struct colors *colors, const struc goto error; } - const struct bfs_stat *statbuf; + const struct bfs_stat *statbuf = NULL; const struct esc_seq *color = NULL; switch (type) { @@ -14,13 +14,26 @@ #include <stdarg.h> #include <stdio.h> #include <stdlib.h> +#include <unistd.h> + +/** + * Print an error using dprintf() if possible, because it's more likely to be + * async-signal-safe in practice. + */ +#if BFS_HAS_DPRINTF +# define eprintf(...) dprintf(STDERR_FILENO, __VA_ARGS__) +# define veprintf(...) vdprintf(STDERR_FILENO, __VA_ARGS__) +#else +# define eprintf(...) fprintf(stderr, __VA_ARGS__) +# define veprintf(...) vfprintf(stderr, __VA_ARGS__) +#endif /** bfs_diagf() implementation. */ _printf(2, 0) static void bfs_vdiagf(const struct bfs_loc *loc, const char *format, va_list args) { - fprintf(stderr, "%s: %s@%s:%d: ", xgetprogname(), loc->func, loc->file, loc->line); - vfprintf(stderr, format, args); - fprintf(stderr, "\n"); + eprintf("%s: %s@%s:%d: ", xgetprogname(), loc->func, loc->file, loc->line); + veprintf(format, args); + eprintf("\n"); } void bfs_diagf(const struct bfs_loc *loc, const char *format, ...) { @@ -27,7 +27,7 @@ struct bfs_loc { /** * Get the current source code location. */ -#if __STDC_VERSION__ >= C23 +#if BFS_HAS_COMPOUND_LITERAL_STORAGE # define bfs_location() (&(static const struct bfs_loc)BFS_LOC_INIT) #else # define bfs_location() (&(const struct bfs_loc)BFS_LOC_INIT) @@ -137,11 +137,9 @@ static const struct bfs_stat *eval_stat(struct bfs_eval *state) { * Get the difference (in seconds) between two struct timespecs. */ static time_t timespec_diff(const struct timespec *lhs, const struct timespec *rhs) { - time_t ret = lhs->tv_sec - rhs->tv_sec; - if (lhs->tv_nsec < rhs->tv_nsec) { - --ret; - } - return ret; + struct timespec diff = *lhs; + timespec_sub(&diff, rhs); + return diff.tv_sec; } bool bfs_expr_cmp(const struct bfs_expr *expr, long long n) { @@ -260,8 +258,7 @@ bool eval_newer(const struct bfs_expr *expr, struct bfs_eval *state) { return false; } - return time->tv_sec > expr->reftime.tv_sec - || (time->tv_sec == expr->reftime.tv_sec && time->tv_nsec > expr->reftime.tv_nsec); + return timespec_cmp(time, &expr->reftime) > 0; } /** @@ -703,6 +700,34 @@ static int print_owner(FILE *file, const char *name, uintmax_t id, int *width) { } } +/** Print a file's modification time. */ +static int print_time(FILE *file, time_t time, time_t now) { + struct tm tm; + if (!localtime_r(&time, &tm)) { + goto error; + } + + char time_str[256]; + size_t time_ret; + + time_t six_months_ago = now - 6 * 30 * 24 * 60 * 60; + time_t tomorrow = now + 24 * 60 * 60; + if (time <= six_months_ago || time >= tomorrow) { + time_ret = strftime(time_str, sizeof(time_str), "%b %e %Y", &tm); + } else { + time_ret = strftime(time_str, sizeof(time_str), "%b %e %H:%M", &tm); + } + + if (time_ret == 0) { + goto error; + } + + return fprintf(file, " %s", time_str); + +error: + return fprintf(file, " %jd", (intmax_t)time); +} + /** * -f?ls action. */ @@ -759,28 +784,11 @@ bool eval_fls(const struct bfs_expr *expr, struct bfs_eval *state) { time_t time = statbuf->mtime.tv_sec; time_t now = ctx->now.tv_sec; - time_t six_months_ago = now - 6 * 30 * 24 * 60 * 60; - time_t tomorrow = now + 24 * 60 * 60; - struct tm tm; - if (!localtime_r(&time, &tm)) { - goto error; - } - char time_str[256]; - size_t time_ret; - if (time <= six_months_ago || time >= tomorrow) { - time_ret = strftime(time_str, sizeof(time_str), "%b %e %Y", &tm); - } else { - time_ret = strftime(time_str, sizeof(time_str), "%b %e %H:%M", &tm); - } - if (time_ret == 0) { - errno = EOVERFLOW; - goto error; - } - if (cfprintf(cfile, " %s${rs}", time_str) < 0) { + if (print_time(file, time, now) < 0) { goto error; } - if (cfprintf(cfile, " %pP", ftwbuf) < 0) { + if (cfprintf(cfile, "${rs} %pP", ftwbuf) < 0) { goto error; } @@ -1047,21 +1055,6 @@ static int eval_gettime(struct bfs_eval *state, struct timespec *ts) { } /** - * Record an elapsed time. - */ -static void timespec_elapsed(struct timespec *elapsed, const struct timespec *start, const struct timespec *end) { - elapsed->tv_sec += end->tv_sec - start->tv_sec; - elapsed->tv_nsec += end->tv_nsec - start->tv_nsec; - if (elapsed->tv_nsec < 0) { - elapsed->tv_nsec += 1000000000L; - --elapsed->tv_sec; - } else if (elapsed->tv_nsec >= 1000000000L) { - elapsed->tv_nsec -= 1000000000L; - ++elapsed->tv_sec; - } -} - -/** * Evaluate an expression. */ static bool eval_expr(struct bfs_expr *expr, struct bfs_eval *state) { @@ -1079,7 +1072,8 @@ static bool eval_expr(struct bfs_expr *expr, struct bfs_eval *state) { if (time) { if (eval_gettime(state, &end) == 0) { - timespec_elapsed(&expr->elapsed, &start, &end); + timespec_sub(&end, &start); + timespec_add(&expr->elapsed, &end); } } @@ -136,6 +136,7 @@ #include <stdint.h> #include <stdlib.h> #include <sys/stat.h> +#include <unistd.h> #if BFS_WITH_LIBURING # include <liburing.h> @@ -259,17 +260,45 @@ static struct ioqq *ioqq_create(size_t size) { /** Get the monitor associated with a slot. */ static struct ioq_monitor *ioq_slot_monitor(struct ioqq *ioqq, ioq_slot *slot) { - size_t i = slot - ioqq->slots; + uint32_t i = slot - ioqq->slots; + + // Hash the index to de-correlate waiters + // https://nullprogram.com/blog/2018/07/31/ + // https://github.com/skeeto/hash-prospector/issues/19#issuecomment-1120105785 + i ^= i >> 16; + i *= UINT32_C(0x21f0aaad); + i ^= i >> 15; + i *= UINT32_C(0x735a2d97); + i ^= i >> 15; + return &ioqq->monitors[i & ioqq->monitor_mask]; } /** Atomically wait for a slot to change. */ _noinline static uintptr_t ioq_slot_wait(struct ioqq *ioqq, ioq_slot *slot, uintptr_t value) { + uintptr_t ret; + + // Try spinning a few times (with exponential backoff) before blocking + _nounroll + for (int i = 1; i < 1024; i *= 2) { + _nounroll + for (int j = 0; j < i; ++j) { + spin_loop(); + } + + // Check if the slot changed + ret = load(slot, relaxed); + if (ret != value) { + return ret; + } + } + + // Nothing changed, start blocking struct ioq_monitor *monitor = ioq_slot_monitor(ioqq, slot); mutex_lock(&monitor->mutex); - uintptr_t ret = load(slot, relaxed); + ret = load(slot, relaxed); if (ret != value) { goto done; } @@ -355,6 +384,14 @@ static bool ioq_slot_push(struct ioqq *ioqq, ioq_slot *slot, struct ioq_ent *ent static struct ioq_ent *ioq_slot_pop(struct ioqq *ioqq, ioq_slot *slot, bool block) { uintptr_t prev = load(slot, relaxed); while (true) { +#if __has_builtin(__builtin_prefetch) + // Optimistically prefetch the pointer in this slot. If this + // slot is not full, this will prefetch an invalid address, but + // experimentally this is worth it on both Intel (Alder Lake) + // and AMD (Zen 2). + __builtin_prefetch((void *)(prev << 1), 1 /* write */); +#endif + // empty → skip(1) // skip(n) → skip(n + 1) // full(ptr) → full(ptr - 1) @@ -409,13 +446,6 @@ static void ioqq_push_batch(struct ioqq *ioqq, struct ioq_ent *batch[], size_t s } while (size > 0); } -/** Pop an entry from the queue. */ -static struct ioq_ent *ioqq_pop(struct ioqq *ioqq, bool block) { - size_t i = fetch_add(&ioqq->tail, 1, relaxed); - ioq_slot *slot = &ioqq->slots[i & ioqq->slot_mask]; - return ioq_slot_pop(ioqq, slot, block); -} - /** Pop a batch of entries from the queue. */ static void ioqq_pop_batch(struct ioqq *ioqq, struct ioq_ent *batch[], size_t size, bool block) { size_t mask = ioqq->slot_mask; @@ -431,30 +461,77 @@ static void ioqq_pop_batch(struct ioqq *ioqq, struct ioq_ent *batch[], size_t si #define IOQ_BATCH (FALSE_SHARING_SIZE / sizeof(ioq_slot)) /** - * A batch of entries to send all at once. + * A batch of I/O queue entries. */ struct ioq_batch { - /** The current batch size. */ - size_t size; + /** The start of the batch. */ + size_t head; + /** The end of the batch. */ + size_t tail; /** The array of entries. */ struct ioq_ent *entries[IOQ_BATCH]; }; -/** Send the batch to a queue. */ +/** Reset a batch. */ +static void ioq_batch_reset(struct ioq_batch *batch) { + batch->head = batch->tail = 0; +} + +/** Check if a batch is empty. */ +static bool ioq_batch_empty(const struct ioq_batch *batch) { + return batch->head >= batch->tail; +} + +/** Send a batch to a queue. */ static void ioq_batch_flush(struct ioqq *ioqq, struct ioq_batch *batch) { - if (batch->size > 0) { - ioqq_push_batch(ioqq, batch->entries, batch->size); - batch->size = 0; + if (batch->tail > 0) { + ioqq_push_batch(ioqq, batch->entries, batch->tail); + ioq_batch_reset(batch); } } -/** An an entry to a batch, flushing if necessary. */ +/** Push an entry to a batch, flushing if necessary. */ static void ioq_batch_push(struct ioqq *ioqq, struct ioq_batch *batch, struct ioq_ent *ent) { - if (batch->size >= IOQ_BATCH) { + batch->entries[batch->tail++] = ent; + + if (batch->tail >= IOQ_BATCH) { ioq_batch_flush(ioqq, batch); } +} + +/** Fill a batch from a queue. */ +static bool ioq_batch_fill(struct ioqq *ioqq, struct ioq_batch *batch, bool block) { + ioqq_pop_batch(ioqq, batch->entries, IOQ_BATCH, block); + + ioq_batch_reset(batch); + for (size_t i = 0; i < IOQ_BATCH; ++i) { + struct ioq_ent *ent = batch->entries[i]; + if (ent) { + batch->entries[batch->tail++] = ent; + } + } + + return batch->tail > 0; +} + +/** Pop an entry from a batch, filling it first if necessary. */ +static struct ioq_ent *ioq_batch_pop(struct ioqq *ioqq, struct ioq_batch *batch, bool block) { + if (ioq_batch_empty(batch)) { + // For non-blocking pops, make sure that each ioq_batch_pop() + // corresponds to a single (amortized) increment of ioqq->head. + // Otherwise, we start skipping many slots and batching ends up + // degrading performance. + if (!block && batch->head < IOQ_BATCH) { + ++batch->head; + return NULL; + } + + if (!ioq_batch_fill(ioqq, batch, block)) { + return NULL; + } + } - batch->entries[batch->size++] = ent; + return batch->entries[batch->head++]; } /** Sentinel stop command. */ @@ -503,11 +580,16 @@ struct ioq { struct arena xbufs; #endif - /** Pending I/O requests. */ + /** Pending I/O request queue. */ struct ioqq *pending; - /** Ready I/O responses. */ + /** Ready I/O response queue. */ struct ioqq *ready; + /** Pending request batch. */ + struct ioq_batch pending_batch; + /** Ready request batch. */ + struct ioq_batch ready_batch; + /** The number of background threads. */ size_t nthreads; /** The background threads themselves. */ @@ -532,6 +614,14 @@ static bool ioq_check_cancel(struct ioq *ioq, struct ioq_ent *ent) { /** Dispatch a single request synchronously. */ static void ioq_dispatch_sync(struct ioq *ioq, struct ioq_ent *ent) { switch (ent->op) { + case IOQ_NOP: + if (ent->nop.type == IOQ_NOP_HEAVY) { + // A fast, no-op syscall + getppid(); + } + ent->result = 0; + return; + case IOQ_CLOSE: ent->result = try(xclose(ent->close.fd)); return; @@ -580,23 +670,161 @@ struct ioq_ring_state { struct ioq_batch ready; }; +/** Reap a single CQE. */ +static void ioq_reap_cqe(struct ioq_ring_state *state, struct io_uring_cqe *cqe) { + struct ioq *ioq = state->ioq; + + struct ioq_ent *ent = io_uring_cqe_get_data(cqe); + ent->result = cqe->res; + + if (ent->result < 0) { + goto push; + } + + switch (ent->op) { + case IOQ_OPENDIR: { + int fd = ent->result; + if (ioq_check_cancel(ioq, ent)) { + xclose(fd); + goto push; + } + + struct ioq_opendir *args = &ent->opendir; + ent->result = try(bfs_opendir(args->dir, fd, NULL, args->flags)); + if (ent->result >= 0) { + // TODO: io_uring_prep_getdents() + bfs_polldir(args->dir); + } else { + xclose(fd); + } + + break; + } + +#if BFS_USE_STATX + case IOQ_STAT: { + struct ioq_stat *args = &ent->stat; + ent->result = try(bfs_statx_convert(args->buf, args->xbuf)); + break; + } +#endif + + default: + break; + } + +push: + ioq_batch_push(ioq->ready, &state->ready, ent); +} + +/** Wait for submitted requests to complete. */ +static void ioq_ring_drain(struct ioq_ring_state *state, size_t wait_nr) { + struct ioq *ioq = state->ioq; + struct io_uring *ring = state->ring; + + bfs_assert(wait_nr <= state->submitted); + + while (state->submitted > 0) { + struct io_uring_cqe *cqe; + if (wait_nr > 0) { + io_uring_wait_cqes(ring, &cqe, wait_nr, NULL, NULL); + } + + unsigned int head; + size_t seen = 0; + io_uring_for_each_cqe (ring, head, cqe) { + ioq_reap_cqe(state, cqe); + ++seen; + } + + io_uring_cq_advance(ring, seen); + state->submitted -= seen; + + if (seen >= wait_nr) { + break; + } + wait_nr -= seen; + } + + ioq_batch_flush(ioq->ready, &state->ready); +} + +/** Submit prepped SQEs, and wait for some to complete. */ +static void ioq_ring_submit(struct ioq_ring_state *state) { + struct io_uring *ring = state->ring; + + size_t unreaped = state->prepped + state->submitted; + size_t wait_nr = 0; + + if (state->prepped == 0 && unreaped > 0) { + // If we have no new SQEs, wait for at least one old one to + // complete, to avoid livelock + wait_nr = 1; + } + + if (unreaped > ring->sq.ring_entries) { + // Keep the completion queue below half full + wait_nr = unreaped - ring->sq.ring_entries; + } + + // Submit all prepped SQEs + while (state->prepped > 0) { + int ret = io_uring_submit_and_wait(state->ring, wait_nr); + if (ret <= 0) { + continue; + } + + state->submitted += ret; + state->prepped -= ret; + if (state->prepped > 0) { + // In the unlikely event of a short submission, any SQE + // links will be broken. Wait for all SQEs to complete + // to preserve any ordering requirements. + ioq_ring_drain(state, state->submitted); + wait_nr = 0; + } + } + + // Drain all the CQEs we waited for (and any others that are ready) + ioq_ring_drain(state, wait_nr); +} + +/** Reserve space for a number of SQEs, submitting if necessary. */ +static void ioq_reserve_sqes(struct ioq_ring_state *state, unsigned int count) { + while (io_uring_sq_space_left(state->ring) < count) { + ioq_ring_submit(state); + } +} + +/** Get an SQE, submitting if necessary. */ +static struct io_uring_sqe *ioq_get_sqe(struct ioq_ring_state *state) { + ioq_reserve_sqes(state, 1); + return io_uring_get_sqe(state->ring); +} + /** Dispatch a single request asynchronously. */ static struct io_uring_sqe *ioq_dispatch_async(struct ioq_ring_state *state, struct ioq_ent *ent) { - struct io_uring *ring = state->ring; enum ioq_ring_ops ops = state->ops; struct io_uring_sqe *sqe = NULL; switch (ent->op) { + case IOQ_NOP: + if (ent->nop.type == IOQ_NOP_HEAVY) { + sqe = ioq_get_sqe(state); + io_uring_prep_nop(sqe); + } + return sqe; + case IOQ_CLOSE: if (ops & IOQ_RING_CLOSE) { - sqe = io_uring_get_sqe(ring); + sqe = ioq_get_sqe(state); io_uring_prep_close(sqe, ent->close.fd); } return sqe; case IOQ_OPENDIR: if (ops & IOQ_RING_OPENAT) { - sqe = io_uring_get_sqe(ring); + sqe = ioq_get_sqe(state); struct ioq_opendir *args = &ent->opendir; int flags = O_RDONLY | O_CLOEXEC | O_DIRECTORY; io_uring_prep_openat(sqe, args->dfd, args->path, flags, 0); @@ -606,7 +834,7 @@ static struct io_uring_sqe *ioq_dispatch_async(struct ioq_ring_state *state, str case IOQ_CLOSEDIR: #if BFS_USE_UNWRAPDIR if (ops & IOQ_RING_CLOSE) { - sqe = io_uring_get_sqe(ring); + sqe = ioq_get_sqe(state); io_uring_prep_close(sqe, bfs_unwrapdir(ent->closedir.dir)); } #endif @@ -615,10 +843,10 @@ static struct io_uring_sqe *ioq_dispatch_async(struct ioq_ring_state *state, str case IOQ_STAT: #if BFS_USE_STATX if (ops & IOQ_RING_STATX) { - sqe = io_uring_get_sqe(ring); + sqe = ioq_get_sqe(state); struct ioq_stat *args = &ent->stat; int flags = bfs_statx_flags(args->flags); - unsigned int mask = STATX_BASIC_STATS | STATX_BTIME; + unsigned int mask = bfs_statx_mask(); io_uring_prep_statx(sqe, args->dfd, args->path, flags, mask, args->xbuf); } #endif @@ -631,7 +859,7 @@ static struct io_uring_sqe *ioq_dispatch_async(struct ioq_ring_state *state, str /** Check if ioq_ring_reap() has work to do. */ static bool ioq_ring_empty(struct ioq_ring_state *state) { - return !state->prepped && !state->submitted && !state->ready.size; + return !state->prepped && !state->submitted && ioq_batch_empty(&state->ready); } /** Prep a single SQE. */ @@ -659,121 +887,52 @@ static bool ioq_ring_prep(struct ioq_ring_state *state) { } struct ioq *ioq = state->ioq; - struct io_uring *ring = state->ring; - struct ioq_ent *pending[IOQ_BATCH]; - - while (io_uring_sq_space_left(ring) >= IOQ_BATCH) { - bool block = ioq_ring_empty(state); - ioqq_pop_batch(ioq->pending, pending, IOQ_BATCH, block); - - bool any = false; - for (size_t i = 0; i < IOQ_BATCH; ++i) { - struct ioq_ent *ent = pending[i]; - if (ent == &IOQ_STOP) { - ioqq_push(ioq->pending, &IOQ_STOP); - state->stop = true; - goto done; - } else if (ent) { - ioq_prep_sqe(state, ent); - any = true; - } - } - - if (!any) { - break; - } - } - -done: - return !ioq_ring_empty(state); -} - -/** Reap a single CQE. */ -static void ioq_reap_cqe(struct ioq_ring_state *state, struct io_uring_cqe *cqe) { - struct ioq *ioq = state->ioq; - struct io_uring *ring = state->ring; - - struct ioq_ent *ent = io_uring_cqe_get_data(cqe); - ent->result = cqe->res; - io_uring_cqe_seen(ring, cqe); - --state->submitted; - - if (ent->result < 0) { - goto push; - } - switch (ent->op) { - case IOQ_OPENDIR: { - int fd = ent->result; - if (ioq_check_cancel(ioq, ent)) { - xclose(fd); - goto push; - } - - struct ioq_opendir *args = &ent->opendir; - ent->result = try(bfs_opendir(args->dir, fd, NULL, args->flags)); - if (ent->result >= 0) { - // TODO: io_uring_prep_getdents() - bfs_polldir(args->dir); - } else { - xclose(fd); - } + struct ioq_batch pending; + ioq_batch_reset(&pending); + while (true) { + bool block = ioq_ring_empty(state); + struct ioq_ent *ent = ioq_batch_pop(ioq->pending, &pending, block); + if (ent == &IOQ_STOP) { + ioqq_push(ioq->pending, ent); + state->stop = true; break; - } - -#if BFS_USE_STATX - case IOQ_STAT: { - struct ioq_stat *args = &ent->stat; - ent->result = try(bfs_statx_convert(args->buf, args->xbuf)); + } else if (ent) { + ioq_prep_sqe(state, ent); + } else { break; } -#endif - - default: - break; } -push: - ioq_batch_push(ioq->ready, &state->ready, ent); + bfs_assert(ioq_batch_empty(&pending)); + return !ioq_ring_empty(state); } -/** Reap a batch of CQEs. */ -static void ioq_ring_reap(struct ioq_ring_state *state) { - struct ioq *ioq = state->ioq; - struct io_uring *ring = state->ring; +/** io_uring worker loop. */ +static int ioq_ring_work(struct ioq_thread *thread) { + struct io_uring *ring = &thread->ring; - while (state->prepped) { - int ret = io_uring_submit_and_wait(ring, 1); - if (ret > 0) { - state->prepped -= ret; - state->submitted += ret; +#ifdef IORING_SETUP_R_DISABLED + if (ring->flags & IORING_SETUP_R_DISABLED) { + if (io_uring_enable_rings(ring) != 0) { + return -1; } } +#endif - while (state->submitted) { - struct io_uring_cqe *cqe; - if (io_uring_wait_cqe(ring, &cqe) < 0) { - continue; - } - - ioq_reap_cqe(state, cqe); - } - - ioq_batch_flush(ioq->ready, &state->ready); -} - -/** io_uring worker loop. */ -static void ioq_ring_work(struct ioq_thread *thread) { struct ioq_ring_state state = { .ioq = thread->parent, - .ring = &thread->ring, + .ring = ring, .ops = thread->ring_ops, }; while (ioq_ring_prep(&state)) { - ioq_ring_reap(&state); + ioq_ring_submit(&state); } + + ioq_ring_drain(&state, state.submitted); + return 0; } #endif // BFS_WITH_LIBURING @@ -782,30 +941,29 @@ static void ioq_ring_work(struct ioq_thread *thread) { static void ioq_sync_work(struct ioq_thread *thread) { struct ioq *ioq = thread->parent; - bool stop = false; - while (!stop) { - struct ioq_ent *pending[IOQ_BATCH]; - ioqq_pop_batch(ioq->pending, pending, IOQ_BATCH, true); - - struct ioq_batch ready; - ready.size = 0; - - for (size_t i = 0; i < IOQ_BATCH; ++i) { - struct ioq_ent *ent = pending[i]; - if (ent == &IOQ_STOP) { - ioqq_push(ioq->pending, &IOQ_STOP); - stop = true; - break; - } else if (ent) { - if (!ioq_check_cancel(ioq, ent)) { - ioq_dispatch_sync(ioq, ent); - } - ioq_batch_push(ioq->ready, &ready, ent); - } + struct ioq_batch pending, ready; + ioq_batch_reset(&pending); + ioq_batch_reset(&ready); + + while (true) { + if (ioq_batch_empty(&pending)) { + ioq_batch_flush(ioq->ready, &ready); + } + + struct ioq_ent *ent = ioq_batch_pop(ioq->pending, &pending, true); + if (ent == &IOQ_STOP) { + ioqq_push(ioq->pending, ent); + break; } - ioq_batch_flush(ioq->ready, &ready); + if (!ioq_check_cancel(ioq, ent)) { + ioq_dispatch_sync(ioq, ent); + } + ioq_batch_push(ioq->ready, &ready, ent); } + + bfs_assert(ioq_batch_empty(&pending)); + ioq_batch_flush(ioq->ready, &ready); } /** Background thread entry point. */ @@ -814,8 +972,9 @@ static void *ioq_work(void *ptr) { #if BFS_WITH_LIBURING if (thread->ring_err == 0) { - ioq_ring_work(thread); - return NULL; + if (ioq_ring_work(thread) == 0) { + return NULL; + } } #endif @@ -823,6 +982,27 @@ static void *ioq_work(void *ptr) { return NULL; } +#if BFS_WITH_LIBURING +/** Test whether some io_uring setup flags are supported. */ +static bool ioq_ring_probe_flags(struct io_uring_params *params, unsigned int flags) { + unsigned int saved = params->flags; + params->flags |= flags; + + struct io_uring ring; + int ret = io_uring_queue_init_params(2, &ring, params); + if (ret == 0) { + io_uring_queue_exit(&ring); + } + + if (ret == -EINVAL) { + params->flags = saved; + return false; + } + + return true; +} +#endif + /** Initialize io_uring thread state. */ static int ioq_ring_init(struct ioq *ioq, struct ioq_thread *thread) { #if BFS_WITH_LIBURING @@ -836,11 +1016,31 @@ static int ioq_ring_init(struct ioq *ioq, struct ioq_thread *thread) { return -1; } - // Share io-wq workers between rings struct io_uring_params params = {0}; + if (prev) { - params.flags |= IORING_SETUP_ATTACH_WQ; + // Share io-wq workers between rings + params.flags = prev->ring.flags | IORING_SETUP_ATTACH_WQ; params.wq_fd = prev->ring.ring_fd; + } else { +#ifdef IORING_SETUP_SUBMIT_ALL + // Don't abort submission just because an inline request fails + ioq_ring_probe_flags(¶ms, IORING_SETUP_SUBMIT_ALL); +#endif + +#ifdef IORING_SETUP_R_DISABLED + // Don't enable the ring yet (needed for SINGLE_ISSUER) + if (ioq_ring_probe_flags(¶ms, IORING_SETUP_R_DISABLED)) { +# ifdef IORING_SETUP_SINGLE_ISSUER + // Allow optimizations assuming only one task submits SQEs + ioq_ring_probe_flags(¶ms, IORING_SETUP_SINGLE_ISSUER); +# endif +# ifdef IORING_SETUP_DEFER_TASKRUN + // Don't interrupt us aggresively with completion events + ioq_ring_probe_flags(¶ms, IORING_SETUP_DEFER_TASKRUN); +# endif + } +#endif } // Use a page for each SQE ring @@ -902,7 +1102,8 @@ static void ioq_ring_exit(struct ioq_thread *thread) { } /** Create an I/O queue thread. */ -static int ioq_thread_create(struct ioq *ioq, struct ioq_thread *thread) { +static int ioq_thread_create(struct ioq *ioq, size_t i) { + struct ioq_thread *thread = &ioq->threads[i]; thread->parent = ioq; ioq_ring_init(ioq, thread); @@ -912,6 +1113,11 @@ static int ioq_thread_create(struct ioq *ioq, struct ioq_thread *thread) { return -1; } + char name[16]; + if (snprintf(name, sizeof(name), "ioq-%zu", i) >= 0) { + thread_setname(thread->id, name); + } + return 0; } @@ -946,7 +1152,7 @@ struct ioq *ioq_create(size_t depth, size_t nthreads) { ioq->nthreads = nthreads; for (size_t i = 0; i < nthreads; ++i) { - if (ioq_thread_create(ioq, &ioq->threads[i]) != 0) { + if (ioq_thread_create(ioq, i) != 0) { ioq->nthreads = i; goto fail; } @@ -988,6 +1194,18 @@ static struct ioq_ent *ioq_request(struct ioq *ioq, enum ioq_op op, void *ptr) { return ent; } +int ioq_nop(struct ioq *ioq, enum ioq_nop_type type, void *ptr) { + struct ioq_ent *ent = ioq_request(ioq, IOQ_NOP, ptr); + if (!ent) { + return -1; + } + + ent->nop.type = type; + + ioq_batch_push(ioq->pending, &ioq->pending_batch, ent); + return 0; +} + int ioq_close(struct ioq *ioq, int fd, void *ptr) { struct ioq_ent *ent = ioq_request(ioq, IOQ_CLOSE, ptr); if (!ent) { @@ -996,7 +1214,7 @@ int ioq_close(struct ioq *ioq, int fd, void *ptr) { ent->close.fd = fd; - ioqq_push(ioq->pending, ent); + ioq_batch_push(ioq->pending, &ioq->pending_batch, ent); return 0; } @@ -1012,7 +1230,7 @@ int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, args->path = path; args->flags = flags; - ioqq_push(ioq->pending, ent); + ioq_batch_push(ioq->pending, &ioq->pending_batch, ent); return 0; } @@ -1024,7 +1242,7 @@ int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr) { ent->closedir.dir = dir; - ioqq_push(ioq->pending, ent); + ioq_batch_push(ioq->pending, &ioq->pending_batch, ent); return 0; } @@ -1048,16 +1266,23 @@ int ioq_stat(struct ioq *ioq, int dfd, const char *path, enum bfs_stat_flags fla } #endif - ioqq_push(ioq->pending, ent); + ioq_batch_push(ioq->pending, &ioq->pending_batch, ent); return 0; } +void ioq_submit(struct ioq *ioq) { + ioq_batch_flush(ioq->pending, &ioq->pending_batch); +} + struct ioq_ent *ioq_pop(struct ioq *ioq, bool block) { + // Don't forget to submit before popping + bfs_assert(ioq_batch_empty(&ioq->pending_batch)); + if (ioq->size == 0) { return NULL; } - return ioqq_pop(ioq->ready, block); + return ioq_batch_pop(ioq->ready, &ioq->ready_batch, block); } void ioq_free(struct ioq *ioq, struct ioq_ent *ent) { @@ -1075,7 +1300,8 @@ void ioq_free(struct ioq *ioq, struct ioq_ent *ent) { void ioq_cancel(struct ioq *ioq) { if (!exchange(&ioq->cancel, true, relaxed)) { - ioqq_push(ioq->pending, &IOQ_STOP); + ioq_batch_push(ioq->pending, &ioq->pending_batch, &IOQ_STOP); + ioq_submit(ioq); } } @@ -8,6 +8,7 @@ #ifndef BFS_IOQ_H #define BFS_IOQ_H +#include "bfs.h" #include "dir.h" #include "stat.h" @@ -22,6 +23,8 @@ struct ioq; * I/O queue operations. */ enum ioq_op { + /** ioq_nop(). */ + IOQ_NOP, /** ioq_close(). */ IOQ_CLOSE, /** ioq_opendir(). */ @@ -33,18 +36,21 @@ enum ioq_op { }; /** - * The I/O queue implementation needs two tag bits in each pointer to a struct - * ioq_ent, so we need to ensure at least 4-byte alignment. The natural - * alignment is enough on most architectures, but not m68k, so over-align it. + * ioq_nop() types. */ -#define IOQ_ENT_ALIGN alignas(4) +enum ioq_nop_type { + /** A lightweight nop that avoids syscalls. */ + IOQ_NOP_LIGHT, + /** A heavyweight nop that involves a syscall. */ + IOQ_NOP_HEAVY, +}; /** * An I/O queue entry. */ struct ioq_ent { /** The I/O operation. */ - IOQ_ENT_ALIGN enum ioq_op op; + cache_align enum ioq_op op; /** The return value (on success) or negative error code (on failure). */ int result; @@ -54,6 +60,10 @@ struct ioq_ent { /** Operation-specific arguments. */ union { + /** ioq_nop() args. */ + struct ioq_nop { + enum ioq_nop_type type; + } nop; /** ioq_close() args. */ struct ioq_close { int fd; @@ -98,6 +108,20 @@ struct ioq *ioq_create(size_t depth, size_t nthreads); size_t ioq_capacity(const struct ioq *ioq); /** + * A no-op, for benchmarking. + * + * @ioq + * The I/O queue. + * @type + * The type of operation to perform. + * @ptr + * An arbitrary pointer to associate with the request. + * @return + * 0 on success, or -1 on failure. + */ +int ioq_nop(struct ioq *ioq, enum ioq_nop_type type, void *ptr); + +/** * Asynchronous close(). * * @ioq @@ -166,6 +190,11 @@ int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr); int ioq_stat(struct ioq *ioq, int dfd, const char *path, enum bfs_stat_flags flags, struct bfs_stat *buf, void *ptr); /** + * Submit any buffered requests. + */ +void ioq_submit(struct ioq *ioq); + +/** * Pop a response from the queue. * * @ioq @@ -377,21 +377,21 @@ // Scratch variables for the type-safe SLIST_REMOVE() implementation. // Not a pointer type due to https://github.com/llvm/llvm-project/issues/109718. _maybe_unused -static thread_local uintptr_t _slist_prev, _slist_next; +static thread_local uintptr_t slist_prev_, slist_next_; /** Suppress -Wunused-value. */ _maybe_unused -static inline void *_slist_cast(uintptr_t ptr) { +static inline void *slist_cast_(uintptr_t ptr) { return (void *)ptr; } #define SLIST_REMOVE__(list, cursor, next) \ - (_slist_prev = (uintptr_t)(void *)*cursor, \ - _slist_next = (uintptr_t)(void *)(*cursor)->next, \ + (slist_prev_ = (uintptr_t)(void *)*cursor, \ + slist_next_ = (uintptr_t)(void *)(*cursor)->next, \ (*cursor)->next = NULL, \ - *cursor = (void *)_slist_next, \ + *cursor = (void *)slist_next_, \ list->tail = *cursor ? list->tail : cursor, \ - _slist_cast(_slist_prev)) + slist_cast_(slist_prev_)) /** * Pop the head off a singly-linked list. @@ -256,10 +256,7 @@ static int bfs_mtab_fill_types(struct bfs_mtab *mtab) { continue; } - struct trie_leaf *leaf = trie_insert_mem(&mtab->types, &sb.dev, sizeof(sb.dev)); - if (leaf) { - leaf->value = mount->type; - } else { + if (trie_set_mem(&mtab->types, &sb.mnt_id, sizeof(sb.mnt_id), mount->type) != 0) { goto fail; } } @@ -282,9 +279,9 @@ const char *bfs_fstype(const struct bfs_mtab *mtab, const struct bfs_stat *statb } } - const struct trie_leaf *leaf = trie_find_mem(&mtab->types, &statbuf->dev, sizeof(statbuf->dev)); - if (leaf) { - return leaf->value; + const char *type = trie_get_mem(&mtab->types, &statbuf->mnt_id, sizeof(statbuf->mnt_id)); + if (type) { + return type; } else { return "unknown"; } diff --git a/src/prelude.h b/src/prelude.h index a0cc2a1..de89a6c 100644 --- a/src/prelude.h +++ b/src/prelude.h @@ -62,6 +62,11 @@ # define _POSIX_PTHREAD_SEMANTICS 1 #endif +/** QNX extensions. */ +#if __QNX__ +# define _QNX_SOURCE 1 +#endif + // Get the convenience macros that became standard spellings in C23 #if __STDC_VERSION__ < 202311L diff --git a/src/sanity.h b/src/sanity.h index 3f6020b..be77eef 100644 --- a/src/sanity.h +++ b/src/sanity.h @@ -20,11 +20,6 @@ #define SANITIZE_CALL__(macro, ptr, size, ...) \ macro(ptr, size) -/** - * Squelch unused variable warnings when not sanitizing. - */ -#define sanitize_ignore(ptr, size) ((void)(ptr), (void)(size)) - #if __SANITIZE_ADDRESS__ # include <sanitizer/asan_interface.h> @@ -42,9 +37,27 @@ */ #define sanitize_free(...) SANITIZE_CALL(__asan_poison_memory_region, __VA_ARGS__) +/** + * Adjust the size of an allocated region, for things like dynamic arrays. + * + * @ptr + * The memory region. + * @old + * The previous usable size of the region. + * @new + * The new usable size of the region. + * @cap + * The total allocated capacity of the region. + */ +static inline void sanitize_resize(const void *ptr, size_t old, size_t new, size_t cap) { + const char *beg = ptr; + __sanitizer_annotate_contiguous_container(beg, beg + cap, beg + old, beg + new); +} + #else -# define sanitize_alloc(...) SANITIZE_CALL(sanitize_ignore, __VA_ARGS__) -# define sanitize_free(...) SANITIZE_CALL(sanitize_ignore, __VA_ARGS__) +# define sanitize_alloc(...) ((void)0) +# define sanitize_free(...) ((void)0) +# define sanitize_resize(ptr, old, new, cap) ((void)0) #endif #if __SANITIZE_MEMORY__ @@ -65,8 +78,8 @@ #define sanitize_uninit(...) SANITIZE_CALL(__msan_allocated_memory, __VA_ARGS__) #else -# define sanitize_init(...) SANITIZE_CALL(sanitize_ignore, __VA_ARGS__) -# define sanitize_uninit(...) SANITIZE_CALL(sanitize_ignore, __VA_ARGS__) +# define sanitize_init(...) ((void)0) +# define sanitize_uninit(...) ((void)0) #endif /** diff --git a/src/sighook.c b/src/sighook.c index 0cc81fa..a87bed5 100644 --- a/src/sighook.c +++ b/src/sighook.c @@ -32,6 +32,10 @@ #include <stdlib.h> #include <unistd.h> +#if __linux__ +# include <sys/syscall.h> +#endif + // NetBSD opens a file descriptor for each sem_init() #if defined(_POSIX_SEMAPHORES) && !__NetBSD__ # define BFS_POSIX_SEMAPHORES _POSIX_SEMAPHORES @@ -245,62 +249,90 @@ static void *rcu_update(struct rcu *rcu, void *ptr) { return rcu_decode(arc_wait(prev)); } -struct sighook { - /** The signal being hooked, or 0 for atsigexit(). */ - int sig; - /** Signal hook flags. */ - enum sigflags flags; - /** The function to call. */ - sighook_fn *fn; - /** An argument to pass to the function. */ - void *arg; - - /** The RCU pointer to this hook. */ - struct rcu *self; - /** The next hook in the list. */ - struct rcu next; -}; - /** - * An RCU-protected linked list of signal hooks. + * An RCU-protected linked list. */ -struct siglist { - /** The first hook in the list. */ +struct rcu_list { + /** The first node in the list. */ struct rcu head; /** &last->next */ struct rcu *tail; }; -/** Initialize a siglist. */ -static void siglist_init(struct siglist *list) { +/** + * An rcu_list node. + */ +struct rcu_node { + /** The RCU pointer to this node. */ + struct rcu *self; + /** The next node in the list. */ + struct rcu next; +}; + +/** Initialize an rcu_list. */ +static void rcu_list_init(struct rcu_list *list) { rcu_init(&list->head, NULL); list->tail = &list->head; } -/** Append a hook to a linked list. */ -static void sigpush(struct siglist *list, struct sighook *hook) { - hook->self = list->tail; - list->tail = &hook->next; - rcu_init(&hook->next, NULL); - rcu_update(hook->self, hook); +/** Append to an rcu_list. */ +static void rcu_list_append(struct rcu_list *list, struct rcu_node *node) { + node->self = list->tail; + list->tail = &node->next; + rcu_init(&node->next, NULL); + rcu_update(node->self, node); } -/** Remove a hook from the linked list. */ -static void sigpop(struct siglist *list, struct sighook *hook) { - struct sighook *next = rcu_peek(&hook->next); - rcu_update(hook->self, next); +/** Remove from an rcu_list. */ +static void rcu_list_remove(struct rcu_list *list, struct rcu_node *node) { + struct rcu_node *next = rcu_peek(&node->next); + rcu_update(node->self, next); if (next) { - next->self = hook->self; + next->self = node->self; } else { list->tail = &list->head; } + rcu_destroy(&node->next); } +/** + * Iterate over an rcu_list. + * + * It is save to `break` out of this loop, but `return` or `goto` will lead to + * a missed arc_put(). + */ +#define for_rcu(type, node, list) \ + for_rcu_(type, node, (list), node##_slot_, node##_prev_, node##_done_) + +#define for_rcu_(type, node, list, slot, prev, done) \ + for (struct arc *slot, *prev, **done = NULL; !done; arc_put(slot), done = &slot) \ + for (type *node = rcu_read(&list->head, &slot); \ + node; \ + prev = slot, \ + node = rcu_read(&((struct rcu_node *)node)->next, &slot), \ + arc_put(prev)) + +struct sighook { + /** The RCU list node (must be the first field). */ + struct rcu_node node; + + /** The signal being hooked, or 0 for atsigexit(). */ + int sig; + /** Signal hook flags. */ + enum sigflags flags; + /** The function to call. */ + sighook_fn *fn; + /** An argument to pass to the function. */ + void *arg; + /** Flag for SH_ONESHOT. */ + atomic bool armed; +}; + /** The lists of signal hooks. */ -static struct siglist sighooks[64]; +static struct rcu_list sighooks[64]; /** Get the hook list for a particular signal. */ -static struct siglist *siglist(int sig) { +static struct rcu_list *siglist(int sig) { return &sighooks[sig % countof(sighooks)]; } @@ -336,22 +368,31 @@ static const int FATAL_SIGNALS[] = { SIGHUP, SIGILL, SIGINT, +#ifdef SIGIO + SIGIO, +#endif SIGPIPE, - SIGQUIT, - SIGSEGV, - SIGTERM, - SIGUSR1, - SIGUSR2, #ifdef SIGPOLL SIGPOLL, #endif #ifdef SIGPROF SIGPROF, #endif +#ifdef SIGPWR + SIGPWR, +#endif + SIGQUIT, + SIGSEGV, +#ifdef SIGSTKFLT + SIGSTKFLT, +#endif #ifdef SIGSYS SIGSYS, #endif + SIGTERM, SIGTRAP, + SIGUSR1, + SIGUSR2, #ifdef SIGVTALRM SIGVTALRM, #endif @@ -383,7 +424,9 @@ static bool is_fatal(int sig) { /** Reraise a fatal signal. */ _noreturn -static void reraise(int sig) { +static void reraise(siginfo_t *info) { + int sig = info->si_signo; + // Restore the default signal action if (signal(sig, SIG_DFL) == SIG_ERR) { goto fail; @@ -397,42 +440,70 @@ static void reraise(int sig) { goto fail; } +#if __linux__ + // On Linux, try to re-raise the exact siginfo_t (since 3.9, a process can + // signal itself with any siginfo_t) + pid_t tid = syscall(SYS_gettid); + syscall(SYS_rt_tgsigqueueinfo, getpid(), tid, sig, info); +#endif + raise(sig); fail: abort(); } +/** Check whether we should run a hook. */ +static bool should_run(int sig, struct sighook *hook) { + if (hook->sig != sig && hook->sig != 0) { + return false; + } + + if (hook->flags & SH_ONESHOT) { + if (!exchange(&hook->armed, false, relaxed)) { + return false; + } + } + + return true; +} + /** Find any matching hooks and run them. */ -static enum sigflags run_hooks(struct siglist *list, int sig, siginfo_t *info) { +static enum sigflags run_hooks(struct rcu_list *list, int sig, siginfo_t *info) { enum sigflags ret = 0; - struct arc *slot = NULL; - struct sighook *hook = rcu_read(&list->head, &slot); - while (hook) { - if (hook->sig == sig || hook->sig == 0) { + for_rcu (struct sighook, hook, list) { + if (should_run(sig, hook)) { hook->fn(sig, info, hook->arg); ret |= hook->flags; } - - struct arc *prev = slot; - hook = rcu_read(&hook->next, &slot); - arc_put(prev); } - arc_put(slot); return ret; } /** Dispatches a signal to the registered handlers. */ static void sigdispatch(int sig, siginfo_t *info, void *context) { - // https://pubs.opengroup.org/onlinepubs/9799919799/functions/V2_chap02.html#tag_16_04_03_03 + // If we get a fault (e.g. a "real" SIGSEGV, not something like + // kill(..., SIGSEGV)), don't try to run signal hooks, since we could be + // in an arbitrarily corrupted state. // - // The behavior of a process is undefined after it returns normally - // from a signal-catching function for a SIGBUS, SIGFPE, SIGILL, or - // SIGSEGV signal that was not generated by kill(), sigqueue(), or - // raise(). + // POSIX says that returning normally from a signal handler for a fault + // is undefined. But in practice, it's better to uninstall the handler + // and return, which will re-run the faulting instruction and cause us + // to die "correctly" (e.g. with a core dump pointing at the faulting + // instruction, not reraise()). if (is_fault(info)) { - reraise(sig); + // On macOS, we cannot reliably distinguish between faults and + // asynchronous signals. For example, pkill -SEGV bfs will + // result in si_code == SEGV_ACCERR. So we always re-raise the + // signal, because just returning would cause us to ignore + // asynchronous SIG{BUS,ILL,SEGV}. +#if !__APPLE__ + if (signal(sig, SIG_DFL) != SIG_ERR) { + return; + } +#endif + reraise(info); } // https://pubs.opengroup.org/onlinepubs/9799919799/functions/V2_chap02.html#tag_16_04_04 @@ -445,40 +516,58 @@ static void sigdispatch(int sig, siginfo_t *info, void *context) { int error = errno; // Run the normal hooks - struct siglist *list = siglist(sig); + struct rcu_list *list = siglist(sig); enum sigflags flags = run_hooks(list, sig, info); // Run the atsigexit() hooks, if we're exiting if (!(flags & SH_CONTINUE) && is_fatal(sig)) { list = siglist(0); run_hooks(list, sig, info); - reraise(sig); + reraise(info); } errno = error; } +/** A saved signal handler, for sigreset() to restore. */ +struct sigsave { + struct rcu_node node; + int sig; + struct sigaction action; +}; + +/** The list of saved signal handlers. */ +static struct rcu_list saved; +/** `saved` initialization status (since rcu_list_init() isn't atomic). */ +static atomic bool initialized = false; + /** Make sure our signal handler is installed for a given signal. */ static int siginit(int sig) { +#ifdef SA_RESTART +# define BFS_SA_RESTART SA_RESTART +#else +# define BFS_SA_RESTART 0 +#endif + static struct sigaction action = { .sa_sigaction = sigdispatch, - .sa_flags = SA_RESTART | SA_SIGINFO, + .sa_flags = BFS_SA_RESTART | SA_SIGINFO, }; static sigset_t signals; - static bool initialized = false; - if (!initialized) { + if (!load(&initialized, relaxed)) { if (sigemptyset(&signals) != 0 || sigemptyset(&action.sa_mask) != 0) { return -1; } for (size_t i = 0; i < countof(sighooks); ++i) { - siglist_init(&sighooks[i]); + rcu_list_init(&sighooks[i]); } - initialized = true; + rcu_list_init(&saved); + store(&initialized, true, release); } int installed = sigismember(&signals, sig); @@ -488,14 +577,32 @@ static int siginit(int sig) { return 0; } - if (sigaction(sig, &action, NULL) != 0) { + sigset_t updated = signals; + if (sigaddset(&updated, sig) != 0) { + return -1; + } + + struct sigaction original; + if (sigaction(sig, NULL, &original) != 0) { return -1; } - if (sigaddset(&signals, sig) != 0) { + struct sigsave *save = ALLOC(struct sigsave); + if (!save) { return -1; } + save->sig = sig; + save->action = original; + rcu_list_append(&saved, &save->node); + + if (sigaction(sig, &action, NULL) != 0) { + rcu_list_remove(&saved, &save->node); + free(save); + return -1; + } + + signals = updated; return 0; } @@ -510,9 +617,10 @@ static struct sighook *sighook_impl(int sig, sighook_fn *fn, void *arg, enum sig hook->flags = flags; hook->fn = fn; hook->arg = arg; + atomic_init(&hook->armed, true); - struct siglist *list = siglist(sig); - sigpush(list, hook); + struct rcu_list *list = siglist(sig); + rcu_list_append(list, &hook->node); return hook; } @@ -558,11 +666,27 @@ void sigunhook(struct sighook *hook) { mutex_lock(&sigmutex); - struct siglist *list = siglist(hook->sig); - sigpop(list, hook); + struct rcu_list *list = siglist(hook->sig); + rcu_list_remove(list, &hook->node); mutex_unlock(&sigmutex); - rcu_destroy(&hook->next); free(hook); } + +int sigreset(void) { + if (!load(&initialized, acquire)) { + return 0; + } + + int ret = 0; + + for_rcu (struct sigsave, save, &saved) { + if (sigaction(save->sig, &save->action, NULL) != 0) { + ret = -1; + break; + } + } + + return ret; +} diff --git a/src/sighook.h b/src/sighook.h index 3bece21..7149229 100644 --- a/src/sighook.h +++ b/src/sighook.h @@ -21,6 +21,8 @@ struct sighook; enum sigflags { /** Suppress the default action for this signal. */ SH_CONTINUE = 1 << 0, + /** Only run this hook once. */ + SH_ONESHOT = 1 << 1, }; /** @@ -70,4 +72,12 @@ struct sighook *atsigexit(sighook_fn *fn, void *arg); */ void sigunhook(struct sighook *hook); +/** + * Restore all signal handlers to their original dispositions (e.g. after fork()). + * + * @return + * 0 on success, -1 on failure. + */ +int sigreset(void); + #endif // BFS_SIGHOOK_H @@ -51,6 +51,8 @@ const char *bfs_stat_field_name(enum bfs_stat_field field) { return "change time"; case BFS_STAT_MTIME: return "modification time"; + case BFS_STAT_MNT_ID: + return "mount ID"; } bfs_bug("Unrecognized stat field %d", (int)field); @@ -101,6 +103,10 @@ void bfs_stat_convert(struct bfs_stat *dest, const struct stat *src) { dest->rdev = src->st_rdev; dest->mask |= BFS_STAT_RDEV; + // No mount IDs in regular stat(), so use the dev_t as an approximation + dest->mnt_id = dest->dev; + dest->mask |= BFS_STAT_MNT_ID; + #if BFS_HAS_ST_FLAGS dest->attrs = src->st_flags; dest->mask |= BFS_STAT_ATTRS; @@ -169,6 +175,17 @@ int bfs_statx_flags(enum bfs_stat_flags flags) { return ret; } +unsigned int bfs_statx_mask(void) { + unsigned int mask = STATX_BASIC_STATS | STATX_BTIME; +#ifdef STATX_MNT_ID + mask |= STATX_MNT_ID; +#endif +#ifdef STATX_MNT_ID_UNIQUE + mask |= STATX_MNT_ID_UNIQUE; +#endif + return mask; +} + int bfs_statx_convert(struct bfs_stat *dest, const struct statx *src) { // Callers shouldn't have to check anything except the times const unsigned int guaranteed = STATX_BASIC_STATS & ~(STATX_ATIME | STATX_CTIME | STATX_MTIME); @@ -209,6 +226,18 @@ int bfs_statx_convert(struct bfs_stat *dest, const struct statx *src) { dest->attrs = src->stx_attributes; dest->mask |= BFS_STAT_ATTRS; + dest->mnt_id = dest->dev; +#ifdef STATX_MNT_ID + unsigned int mnt_mask = STATX_MNT_ID; +# ifdef STATX_MNT_ID_UNIQUE + mnt_mask |= STATX_MNT_ID_UNIQUE; +# endif + if (src->stx_mask & mnt_mask) { + dest->mnt_id = src->stx_mnt_id; + } +#endif + dest->mask |= BFS_STAT_MNT_ID; + if (src->stx_mask & STATX_ATIME) { dest->atime.tv_sec = src->stx_atime.tv_sec; dest->atime.tv_nsec = src->stx_atime.tv_nsec; @@ -240,7 +269,7 @@ int bfs_statx_convert(struct bfs_stat *dest, const struct statx *src) { * bfs_stat() implementation backed by statx(). */ static int bfs_statx_impl(int at_fd, const char *at_path, int at_flags, struct bfs_stat *buf) { - unsigned int mask = STATX_BASIC_STATS | STATX_BTIME; + unsigned int mask = bfs_statx_mask(); struct statx xbuf; int ret = bfs_statx(at_fd, at_path, at_flags, mask, &xbuf); if (ret != 0) { @@ -14,6 +14,7 @@ #include "bfs.h" +#include <stdint.h> #include <sys/stat.h> #include <sys/types.h> #include <time.h> @@ -56,6 +57,7 @@ enum bfs_stat_field { BFS_STAT_BTIME = 1 << 11, BFS_STAT_CTIME = 1 << 12, BFS_STAT_MTIME = 1 << 13, + BFS_STAT_MNT_ID = 1 << 14, }; /** @@ -102,6 +104,8 @@ struct bfs_stat { blkcnt_t blocks; /** The device ID represented by this file. */ dev_t rdev; + /** The ID of the mount point containing this file. */ + uint64_t mnt_id; /** Attributes/flags set on the file. */ unsigned long long attrs; @@ -150,6 +154,11 @@ void bfs_stat_convert(struct bfs_stat *dest, const struct stat *src); int bfs_statx_flags(enum bfs_stat_flags flags); /** + * Get the default statx() mask. + */ +unsigned int bfs_statx_mask(void); + +/** * Convert struct statx to struct bfs_stat. */ int bfs_statx_convert(struct bfs_stat *dest, const struct statx *src); diff --git a/src/thread.c b/src/thread.c index d61ff8c..b3604f8 100644 --- a/src/thread.c +++ b/src/thread.c @@ -9,6 +9,10 @@ #include <errno.h> #include <pthread.h> +#if __has_include(<pthread_np.h>) +# include <pthread_np.h> +#endif + #define THREAD_FALLIBLE(expr) \ do { \ int err = expr; \ @@ -32,6 +36,14 @@ int thread_create(pthread_t *thread, const pthread_attr_t *attr, thread_fn *fn, THREAD_FALLIBLE(pthread_create(thread, attr, fn, arg)); } +void thread_setname(pthread_t thread, const char *name) { +#if BFS_HAS_PTHREAD_SETNAME_NP + pthread_setname_np(thread, name); +#elif BFS_HAS_PTHREAD_SET_NAME_NP + pthread_set_name_np(thread, name); +#endif +} + void thread_join(pthread_t thread, void **ret) { THREAD_INFALLIBLE(pthread_join(thread, ret)); } diff --git a/src/thread.h b/src/thread.h index 7d12468..3dd8422 100644 --- a/src/thread.h +++ b/src/thread.h @@ -22,6 +22,11 @@ typedef void *thread_fn(void *arg); int thread_create(pthread_t *thread, const pthread_attr_t *attr, thread_fn *fn, void *arg); /** + * Set the name of a thread. + */ +void thread_setname(pthread_t thread, const char *name); + +/** * Wrapper for pthread_join(). */ void thread_join(pthread_t thread, void **ret); @@ -173,16 +173,16 @@ void trie_init(struct trie *trie) { /** Extract the nibble at a certain offset from a byte sequence. */ static unsigned char trie_key_nibble(const void *key, size_t length, size_t offset) { const unsigned char *bytes = key; - size_t byte = offset >> 1; + size_t byte = offset / 2; bfs_assert(byte < length); // A branchless version of // if (offset & 1) { - // return bytes[byte] >> 4; - // } else { // return bytes[byte] & 0xF; + // } else { + // return bytes[byte] >> 4; // } - unsigned int shift = (offset & 1) << 2; + unsigned int shift = 4 * ((offset + 1) % 2); return (bytes[byte] >> shift) & 0xF; } @@ -191,6 +191,12 @@ static unsigned char trie_leaf_nibble(const struct trie_leaf *leaf, size_t offse return trie_key_nibble(leaf->key, leaf->length, offset); } +/** Get the number of children of an internal node. */ +_trie_clones +static unsigned int trie_node_size(const struct trie_node *node) { + return count_ones((unsigned int)node->bitmap); +} + /** * Finds a leaf in the trie that matches the key at every branch. If the key * exists in the trie, the representative will match the searched key. But @@ -202,19 +208,20 @@ _trie_clones static struct trie_leaf *trie_representative(const struct trie *trie, const void *key, size_t length) { uintptr_t ptr = trie->root; - size_t offset = 0; + size_t offset = 0, limit = 2 * length; while (trie_is_node(ptr)) { struct trie_node *node = trie_decode_node(ptr); offset += node->offset; unsigned int index = 0; - if ((offset >> 1) < length) { + if (offset < limit) { unsigned char nibble = trie_key_nibble(key, length, offset); unsigned int bit = 1U << nibble; - // bits = bitmap & bit ? bitmap & (bit - 1) : 0 - unsigned int mask = -!!(node->bitmap & bit); - unsigned int bits = node->bitmap & (bit - 1) & mask; - index = count_ones(bits); + unsigned int map = node->bitmap; + unsigned int bits = map & (bit - 1); + unsigned int mask = -!!(map & bit); + // index = (map & bit) ? count_ones(bits) : 0; + index = count_ones(bits) & mask; } ptr = node->children[index]; } @@ -240,6 +247,16 @@ struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t return trie_find_mem_impl(trie, key, length); } +void *trie_get_str(const struct trie *trie, const char *key) { + const struct trie_leaf *leaf = trie_find_str(trie, key); + return leaf ? leaf->value : NULL; +} + +void *trie_get_mem(const struct trie *trie, const void *key, size_t length) { + const struct trie_leaf *leaf = trie_find_mem(trie, key, length); + return leaf ? leaf->value : NULL; +} + _trie_clones static struct trie_leaf *trie_find_postfix_impl(const struct trie *trie, const char *key) { size_t length = strlen(key); @@ -296,18 +313,18 @@ static struct trie_leaf *trie_find_prefix_impl(const struct trie *trie, const ch size_t skip = 0; size_t length = strlen(key) + 1; - size_t offset = 0; + size_t offset = 0, limit = 2 * length; while (trie_is_node(ptr)) { struct trie_node *node = trie_decode_node(ptr); offset += node->offset; - if ((offset >> 1) >= length) { + if (offset >= limit) { return best; } struct trie_leaf *leaf = trie_terminal_leaf(node); if (trie_check_prefix(leaf, skip, key, length)) { best = leaf; - skip = offset >> 1; + skip = offset / 2; } unsigned char nibble = trie_key_nibble(key, length, offset); @@ -370,16 +387,10 @@ static struct trie_node *trie_node_realloc(struct trie *trie, struct trie_node * /** Free a node. */ static void trie_node_free(struct trie *trie, struct trie_node *node, size_t size) { - bfs_assert(size == (size_t)count_ones(node->bitmap)); + bfs_assert(size == trie_node_size(node)); varena_free(&trie->nodes, node, size); } -#if ENDIAN_NATIVE == ENDIAN_LITTLE -# define TRIE_BSWAP(n) (n) -#elif ENDIAN_NATIVE == ENDIAN_BIG -# define TRIE_BSWAP(n) bswap(n) -#endif - /** Find the offset of the first nibble that differs between two keys. */ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t length) { if (!rep) { @@ -393,32 +404,32 @@ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t const char *rep_bytes = rep->key; const char *key_bytes = key; - size_t i = 0; - for (size_t chunk = sizeof(chunk); i + chunk <= length; i += chunk) { - size_t rep_chunk, key_chunk; - memcpy(&rep_chunk, rep_bytes + i, sizeof(rep_chunk)); - memcpy(&key_chunk, key_bytes + i, sizeof(key_chunk)); - - if (rep_chunk != key_chunk) { -#ifdef TRIE_BSWAP - size_t diff = TRIE_BSWAP(rep_chunk ^ key_chunk); - i *= 2; - i += trailing_zeros(diff) / 4; - return i; -#else - break; -#endif - } + size_t ret = 0, i = 0; + +#define CHUNK(n) CHUNK_(uint##n##_t, load8_beu##n) +#define CHUNK_(type, load8) \ + while (length - i >= sizeof(type)) { \ + type rep_chunk = load8(rep_bytes + i); \ + type key_chunk = load8(key_bytes + i); \ + type diff = rep_chunk ^ key_chunk; \ + ret += leading_zeros(diff) / 4; \ + if (diff) { \ + return ret; \ + } \ + i += sizeof(type); \ } - for (; i < length; ++i) { - unsigned char diff = rep_bytes[i] ^ key_bytes[i]; - if (diff) { - return 2 * i + !(diff & 0xF); - } - } +#if SIZE_WIDTH >= 64 + CHUNK(64); +#endif + CHUNK(32); + CHUNK(16); + CHUNK(8); + +#undef CHUNK_ +#undef CHUNK - return 2 * i; + return ret; } /** @@ -446,7 +457,7 @@ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t _trie_clones static struct trie_leaf *trie_node_insert(struct trie *trie, uintptr_t *ptr, struct trie_leaf *leaf, unsigned char nibble) { struct trie_node *node = trie_decode_node(*ptr); - unsigned int size = count_ones(node->bitmap); + unsigned int size = trie_node_size(node); // Double the capacity every power of two if (has_single_bit(size)) { @@ -626,6 +637,26 @@ struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t len return trie_insert_mem_impl(trie, key, length); } +int trie_set_str(struct trie *trie, const char *key, const void *value) { + struct trie_leaf *leaf = trie_insert_str(trie, key); + if (leaf) { + leaf->value = (void *)value; + return 0; + } else { + return -1; + } +} + +int trie_set_mem(struct trie *trie, const void *key, size_t length, const void *value) { + struct trie_leaf *leaf = trie_insert_mem(trie, key, length); + if (leaf) { + leaf->value = (void *)value; + return 0; + } else { + return -1; + } +} + /** Free a chain of singleton nodes. */ static void trie_free_singletons(struct trie *trie, uintptr_t ptr) { while (trie_is_node(ptr)) { @@ -711,7 +742,7 @@ static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) { struct trie_node *node = trie_decode_node(*parent); trie_free_singletons(trie, node->children[child_index]); - unsigned int parent_size = count_ones(node->bitmap); + unsigned int parent_size = trie_node_size(node); bfs_assert(parent_size > 1); if (parent_size == 2 && trie_collapse_node(trie, parent, node, child_index) == 0) { return; @@ -70,6 +70,32 @@ struct trie_leaf *trie_find_str(const struct trie *trie, const char *key); struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t length); /** + * Get the value associated with a string key. + * + * @trie + * The trie to search. + * @key + * The key to look up. + * @return + * The found value, or NULL if the key is not present. + */ +void *trie_get_str(const struct trie *trie, const char *key); + +/** + * Get the value associated with a fixed-size key. + * + * @trie + * The trie to search. + * @key + * The key to look up. + * @length + * The length of the key in bytes. + * @return + * The found value, or NULL if the key is not present. + */ +void *trie_get_mem(const struct trie *trie, const void *key, size_t length); + +/** * Find the shortest leaf that starts with a given key. * * @trie @@ -120,6 +146,36 @@ struct trie_leaf *trie_insert_str(struct trie *trie, const char *key); struct trie_leaf *trie_insert_mem(struct trie *trie, const void *key, size_t length); /** + * Set the value for a string key. + * + * @trie + * The trie to modify. + * @key + * The key to insert. + * @value + * The value to set. + * @return + * 0 on success, -1 on error. + */ +int trie_set_str(struct trie *trie, const char *key, const void *value); + +/** + * Set the value for a fixed-size key. + * + * @trie + * The trie to modify. + * @key + * The key to insert. + * @length + * The length of the key in bytes. + * @value + * The value to set. + * @return + * 0 on success, -1 on error. + */ +int trie_set_mem(struct trie *trie, const void *key, size_t length, const void *value); + +/** * Remove a leaf from a trie. * * @trie diff --git a/src/xspawn.c b/src/xspawn.c index b3eed79..3fa4e60 100644 --- a/src/xspawn.c +++ b/src/xspawn.c @@ -8,6 +8,7 @@ #include "bfstd.h" #include "diag.h" #include "list.h" +#include "sighook.h" #include <errno.h> #include <fcntl.h> @@ -535,7 +536,7 @@ static bool bfs_use_posix_spawn(const struct bfs_resolver *res, const struct bfs /** Actually exec() the new process. */ _noreturn -static void bfs_spawn_exec(struct bfs_resolver *res, const struct bfs_spawn *ctx, char **argv, char **envp, int pipefd[2]) { +static void bfs_spawn_exec(struct bfs_resolver *res, const struct bfs_spawn *ctx, char **argv, char **envp, const sigset_t *mask, int pipefd[2]) { xclose(pipefd[0]); for_slist (const struct bfs_spawn_action, action, ctx) { @@ -596,6 +597,18 @@ static void bfs_spawn_exec(struct bfs_resolver *res, const struct bfs_spawn *ctx goto fail; } + // Reset signal handlers to their original values before we unblock + // signals, so that handlers don't run in both the parent and the child + if (sigreset() != 0) { + goto fail; + } + + // Restore the original signal mask for the child process + errno = pthread_sigmask(SIG_SETMASK, mask, NULL); + if (errno != 0) { + goto fail; + } + execve(res->exe, argv, envp); fail:; @@ -635,7 +648,7 @@ static pid_t bfs_fork_spawn(struct bfs_resolver *res, const struct bfs_spawn *ct #endif if (pid == 0) { // Child - bfs_spawn_exec(res, ctx, argv, envp, pipefd); + bfs_spawn_exec(res, ctx, argv, envp, &old_mask, pipefd); } // Restore the original signal mask diff --git a/src/xtime.c b/src/xtime.c index 49d7c36..6b8a141 100644 --- a/src/xtime.c +++ b/src/xtime.c @@ -354,6 +354,59 @@ error: return -1; } +/** One nanosecond. */ +static const long NS = 1000L * 1000 * 1000; + +void timespec_add(struct timespec *lhs, const struct timespec *rhs) { + lhs->tv_sec += rhs->tv_sec; + lhs->tv_nsec += rhs->tv_nsec; + if (lhs->tv_nsec >= NS) { + lhs->tv_nsec -= NS; + lhs->tv_sec += 1; + } +} + +void timespec_sub(struct timespec *lhs, const struct timespec *rhs) { + lhs->tv_sec -= rhs->tv_sec; + lhs->tv_nsec -= rhs->tv_nsec; + if (lhs->tv_nsec < 0) { + lhs->tv_nsec += NS; + lhs->tv_sec -= 1; + } +} + +int timespec_cmp(const struct timespec *lhs, const struct timespec *rhs) { + if (lhs->tv_sec < rhs->tv_sec) { + return -1; + } else if (lhs->tv_sec > rhs->tv_sec) { + return 1; + } + + if (lhs->tv_nsec < rhs->tv_nsec) { + return -1; + } else if (lhs->tv_nsec > rhs->tv_nsec) { + return 1; + } + + return 0; +} + +void timespec_min(struct timespec *dest, const struct timespec *src) { + if (timespec_cmp(src, dest) < 0) { + *dest = *src; + } +} + +void timespec_max(struct timespec *dest, const struct timespec *src) { + if (timespec_cmp(src, dest) > 0) { + *dest = *src; + } +} + +double timespec_ns(const struct timespec *ts) { + return 1.0e9 * ts->tv_sec + ts->tv_nsec; +} + #if defined(_POSIX_TIMERS) && BFS_HAS_TIMER_CREATE # define BFS_POSIX_TIMERS _POSIX_TIMERS #else diff --git a/src/xtime.h b/src/xtime.h index 2927a2e..b76fef2 100644 --- a/src/xtime.h +++ b/src/xtime.h @@ -47,6 +47,42 @@ int xtimegm(struct tm *tm, time_t *timep); int xgetdate(const char *str, struct timespec *result); /** + * Add to a timespec. + */ +void timespec_add(struct timespec *lhs, const struct timespec *rhs); + +/** + * Subtract from a timespec. + */ +void timespec_sub(struct timespec *lhs, const struct timespec *rhs); + +/** + * Compare two timespecs. + * + * @return + * An integer with the sign of (*lhs - *rhs). + */ +int timespec_cmp(const struct timespec *lhs, const struct timespec *rhs); + +/** + * Update a minimum timespec. + */ +void timespec_min(struct timespec *dest, const struct timespec *src); + +/** + * Update a maximum timespec. + */ +void timespec_max(struct timespec *dest, const struct timespec *src); + +/** + * Convert a timespec to floating point. + * + * @return + * The value in nanoseconds. + */ +double timespec_ns(const struct timespec *ts); + +/** * A timer. */ struct timer; diff --git a/tests/bit.c b/tests/bit.c index 5a3871d..09d470b 100644 --- a/tests/bit.c +++ b/tests/bit.c @@ -64,7 +64,7 @@ static_assert(INTMAX_MAX == IWIDTH_MAX(INTMAX_WIDTH)); bfs_check((a) == (b), "(0x%jX) %s != %s (0x%jX)", (uintmax_t)(a), #a, #b, (uintmax_t)(b)) void check_bit(void) { - const char *str = "\x1\x2\x3\x4"; + const char *str = "\x1\x2\x3\x4\x5\x6\x7\x8"; uint32_t word; memcpy(&word, str, sizeof(word)); @@ -88,6 +88,15 @@ void check_bit(void) { (void)bswap(0UL); (void)bswap(0ULL); + check_eq(load8_beu8(str), 0x01); + check_eq(load8_leu8(str), 0x01); + check_eq(load8_beu16(str), 0x0102); + check_eq(load8_leu16(str), 0x0201); + check_eq(load8_beu32(str), 0x01020304); + check_eq(load8_leu32(str), 0x04030201); + check_eq(load8_beu64(str), 0x0102030405060708ULL); + check_eq(load8_leu64(str), 0x0807060504030201ULL); + check_eq(count_ones(0x0U), 0); check_eq(count_ones(0x1U), 1); check_eq(count_ones(0x2U), 1); diff --git a/tests/color.sh b/tests/color.sh index 4f4312e..9e2e0f6 100644 --- a/tests/color.sh +++ b/tests/color.sh @@ -46,9 +46,7 @@ show_bar() { # Name the pipe deterministically based on the ttyname, so that concurrent # tests.sh runs on the same terminal (e.g. make -jN check) cooperate - local pipe - pipe=$(printf '%s' "$TTY" | tr '/' '-') - pipe="${TMPDIR:-/tmp}/bfs$pipe.bar" + local pipe="${TMPDIR:-/tmp}/bfs${TTY//\//-}.bar" if mkfifo "$pipe" 2>/dev/null; then # We won the race, create the background process to manage the bar @@ -78,7 +76,7 @@ hide_bar() { # The background process that muxes multiple status bars for one TTY bar_proc() { # Read from the pipe, write to the TTY - exec <"$1" >"$TTY" + exec <"$1" >/dev/tty # Delete the pipe when done defer rm "$1" @@ -133,7 +131,7 @@ bar_proc() { # Resize the status bar resize_bar() { # Bash gets $LINES from stderr, so if it's redirected use tput instead - TTY_HEIGHT="${LINES:-$(tput lines 2>"$TTY")}" + TTY_HEIGHT="${LINES:-$(tput lines 2>/dev/tty)}" if ((BAR_HEIGHT == 0)); then return diff --git a/tests/getopts.sh b/tests/getopts.sh index 5214e9f..255f2fa 100644 --- a/tests/getopts.sh +++ b/tests/getopts.sh @@ -23,7 +23,6 @@ VERBOSE_TESTS=0 # Print usage information usage() { - local pad=$(printf "%*s" ${#0} "") color cat <<EOF Usage: ${GRN}$0${RST} [${BLU}-j${RST}${BLD}N${RST}] [${BLU}--make${RST}=${BLD}MAKE${RST}] [${BLU}--bfs${RST}=${BLD}path/to/bfs${RST}] [${BLU}--sudo${RST}[=${BLD}COMMAND${RST}]] diff --git a/tests/gnu/fls_overflow.sh b/tests/gnu/fls_overflow.sh new file mode 100644 index 0000000..d3447a2 --- /dev/null +++ b/tests/gnu/fls_overflow.sh @@ -0,0 +1,4 @@ +# Regression test: times that overflow localtime() should still print +cd "$TEST" +"$XTOUCH" -t "@1111111111111111111" overflow +invoke_bfs . -fls "$OUT" diff --git a/tests/gnu/fstype_btrfs_subvol.out b/tests/gnu/fstype_btrfs_subvol.out new file mode 100644 index 0000000..8871fb9 --- /dev/null +++ b/tests/gnu/fstype_btrfs_subvol.out @@ -0,0 +1,4 @@ +mnt +mnt/file +mnt/subvol +mnt/subvol/file diff --git a/tests/gnu/fstype_btrfs_subvol.sh b/tests/gnu/fstype_btrfs_subvol.sh new file mode 100644 index 0000000..71df45c --- /dev/null +++ b/tests/gnu/fstype_btrfs_subvol.sh @@ -0,0 +1,25 @@ +# Test that -fstype works in btrfs subvolumes + +command -v btrfs &>/dev/null || skip + +cd "$TEST" + +# Make a btrfs filesystem image +truncate -s128M img +mkfs.btrfs img >&2 + +# Mount it +mkdir mnt +bfs_sudo mount img mnt || skip +defer bfs_sudo umount mnt + +# Make it owned by us +bfs_sudo chown "$(id -u):$(id -g)" mnt + +# Create a subvolume inside it +btrfs subvolume create mnt/subvol >&2 + +# Make a file in and outside the subvolume +"$XTOUCH" mnt/file mnt/subvol/file + +bfs_diff mnt -fstype btrfs -print -o -printf '%p %F\n' diff --git a/tests/gnu/ignore_readdir_race_rmdir.out b/tests/gnu/ignore_readdir_race_rmdir.out new file mode 100644 index 0000000..ede8749 --- /dev/null +++ b/tests/gnu/ignore_readdir_race_rmdir.out @@ -0,0 +1,2 @@ +./bar +./foo diff --git a/tests/gnu/ignore_readdir_race_rmdir.sh b/tests/gnu/ignore_readdir_race_rmdir.sh new file mode 100644 index 0000000..87f36a9 --- /dev/null +++ b/tests/gnu/ignore_readdir_race_rmdir.sh @@ -0,0 +1,5 @@ +cd "$TEST" +"$XTOUCH" -p foo/ bar/ + +# Check that -ignore_readdir_race suppresses errors from opendir() +bfs_diff . -ignore_readdir_race -mindepth 1 -print -name foo -exec rmdir {} \; diff --git a/tests/ioq.c b/tests/ioq.c index f067436..1a0da97 100644 --- a/tests/ioq.c +++ b/tests/ioq.c @@ -49,6 +49,7 @@ static void check_ioq_push_block(void) { int ret = ioq_opendir(ioq, dir, AT_FDCWD, ".", 0, NULL); bfs_everify(ret == 0, "ioq_opendir()"); } + ioq_submit(ioq); bfs_verify(ioq_capacity(ioq) == 0); // Now cancel the queue, pushing an additional IOQ_STOP message diff --git a/tests/posix/exec_sigmask.out b/tests/posix/exec_sigmask.out new file mode 100644 index 0000000..bb646f3 --- /dev/null +++ b/tests/posix/exec_sigmask.out @@ -0,0 +1 @@ +SigBlk: 0000000000000000 diff --git a/tests/posix/exec_sigmask.sh b/tests/posix/exec_sigmask.sh new file mode 100644 index 0000000..d1192a4 --- /dev/null +++ b/tests/posix/exec_sigmask.sh @@ -0,0 +1,16 @@ +# Regression test: restore the signal mask after fork() + +cd "$TEST" +mkfifo p1 p2 + +{ + # Get the PID of `sh` + read -r pid <p1 + # Send SIGTERM -- this will hang forever if signals are blocked + kill $pid +} & + +# Write the `sh` PID to p1, then hang reading p2 until we're killed +! invoke_bfs p1 -exec sh -c 'echo $$ >p1 && read -r _ <p2' {} + || fail + +wait diff --git a/tests/run.sh b/tests/run.sh index 164790e..e3a4e3f 100644 --- a/tests/run.sh +++ b/tests/run.sh @@ -415,8 +415,13 @@ make_xattrs() { # Get the Unix epoch time in seconds epoch_time() { - # https://stackoverflow.com/a/12746260/502399 - awk 'BEGIN { srand(); print srand(); }' + if [ "${EPOCHSECONDS:-}" ]; then + # Added in bash 5 + printf '%d' "$EPOCHSECONDS" + else + # https://stackoverflow.com/a/12746260/502399 + awk 'BEGIN { srand(); print srand(); }' + fi } ## Snapshot testing diff --git a/tests/sighook.c b/tests/sighook.c index 0cb8de2..82e0ae5 100644 --- a/tests/sighook.c +++ b/tests/sighook.c @@ -4,28 +4,40 @@ #include "tests.h" #include "atomic.h" +#include "bfstd.h" #include "sighook.h" #include "thread.h" #include "xtime.h" -#include <stddef.h> #include <errno.h> #include <pthread.h> #include <signal.h> +#include <stddef.h> +#include <stdlib.h> +#include <sys/wait.h> +#include <unistd.h> /** Counts SIGALRM deliveries. */ static atomic size_t count = 0; -/** Keeps the background thread alive. */ -static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; -static pthread_cond_t cond = PTHREAD_COND_INITIALIZER; -static bool done = false; - /** SIGALRM handler. */ static void alrm_hook(int sig, siginfo_t *info, void *arg) { fetch_add(&count, 1, relaxed); } +/** SH_ONESHOT counter. */ +static atomic size_t shots = 0; + +/** SH_ONESHOT hook. */ +static void alrm_oneshot(int sig, siginfo_t *info, void *arg) { + fetch_add(&shots, 1, relaxed); +} + +/** Keeps the background thread alive. */ +static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; +static pthread_cond_t cond = PTHREAD_COND_INITIALIZER; +static bool done = false; + /** Background thread that receives signals. */ static void *hook_thread(void *ptr) { mutex_lock(&mutex); @@ -54,41 +66,62 @@ static int block_signal(int sig, sigset_t *old) { return 0; } -void check_sighook(void) { - struct sighook *hook = sighook(SIGALRM, alrm_hook, NULL, SH_CONTINUE); - if (!bfs_echeck(hook, "sighook(SIGALRM)")) { - return; - } +/** Tests for sighook(). */ +static void check_hooks(void) { + struct sighook *hook = NULL; + struct sighook *oneshot = NULL; - // Check that we can unregister and re-register a hook - sigunhook(hook); hook = sighook(SIGALRM, alrm_hook, NULL, SH_CONTINUE); if (!bfs_echeck(hook, "sighook(SIGALRM)")) { return; } - // Create a timer that sends SIGALRM every 100 microseconds - struct timespec ival = { .tv_nsec = 100 * 1000 }; - struct timer *timer = xtimer_start(&ival); - if (!bfs_echeck(timer)) { - goto unhook; - } - - // Create a background thread to receive signals + // Create a background thread to receive SIGALRM pthread_t thread; if (!bfs_echeck(thread_create(&thread, NULL, hook_thread, NULL) == 0)) { - goto untime; + goto unhook; } // Block SIGALRM in this thread so the handler runs concurrently with // sighook()/sigunhook() sigset_t mask; if (!bfs_echeck(block_signal(SIGALRM, &mask) == 0)) { - goto untime; + goto unthread; + } + + // Check that we can unregister and re-register a hook + sigunhook(hook); + hook = sighook(SIGALRM, alrm_hook, NULL, SH_CONTINUE); + if (!bfs_echeck(hook, "sighook(SIGALRM)")) { + goto unblock; + } + + // Test SH_ONESHOT + oneshot = sighook(SIGALRM, alrm_oneshot, NULL, SH_ONESHOT); + if (!bfs_echeck(oneshot, "sighook(SH_ONESHOT)")) { + goto unblock; + } + + // Create a timer that sends SIGALRM every 100 microseconds + const struct timespec ival = { .tv_nsec = 100 * 1000 }; + struct timer *timer = xtimer_start(&ival); + if (!bfs_echeck(timer, "xtimer_start()")) { + goto unblock; } // Rapidly register/unregister SIGALRM hooks - while (load(&count, relaxed) < 1000) { + size_t alarms; + while (alarms = load(&count, relaxed), alarms < 1000) { + size_t nshots = load(&shots, relaxed); + bfs_check(nshots <= 1); + if (alarms > 1) { + bfs_check(nshots == 1); + } + if (alarms >= 500) { + sigunhook(oneshot); + oneshot = NULL; + } + struct sighook *next = sighook(SIGALRM, alrm_hook, NULL, SH_CONTINUE); if (!bfs_echeck(next, "sighook(SIGALRM)")) { break; @@ -98,20 +131,98 @@ void check_sighook(void) { hook = next; } + // Stop the timer + xtimer_stop(timer); +unblock: + // Restore the old signal mask + errno = pthread_sigmask(SIG_SETMASK, &mask, NULL); + bfs_echeck(errno == 0, "pthread_sigmask()"); +unthread: // Quit the background thread mutex_lock(&mutex); done = true; mutex_unlock(&mutex); cond_signal(&cond); thread_join(thread, NULL); - - // Restore the old signal mask - errno = pthread_sigmask(SIG_SETMASK, &mask, NULL); - bfs_echeck(errno == 0, "pthread_sigmask()"); -untime: - // Stop the timer - xtimer_stop(timer); unhook: - // Unregister the SIGALRM hook + // Unregister the SIGALRM hooks + sigunhook(oneshot); sigunhook(hook); } + +/** atsigexit() hook. */ +static void exit_hook(int sig, siginfo_t *info, void *arg) { + // Write the signal that's killing us to the pipe + int *pipes = arg; + if (xwrite(pipes[1], &sig, sizeof(sig)) != sizeof(sig)) { + abort(); + } +} + +/** Tests for atsigexit(). */ +static void check_sigexit(int sig) { + // To wait for the child to call atsigexit() + int ready[2]; + bfs_everify(pipe(ready) == 0); + + // Written in the atsigexit() handler + int killed[2]; + bfs_everify(pipe(killed) == 0); + + pid_t pid; + bfs_everify((pid = fork()) >= 0); + + if (pid > 0) { + // Parent + xclose(ready[1]); + xclose(killed[1]); + + // Wait for the child to call atsigexit() + char c; + bfs_everify(xread(ready[0], &c, 1) == 1); + + // Kill the child with the signal + bfs_everify(kill(pid, sig) == 0); + + // Check that the child died to the right signal + int wstatus; + if (bfs_echeck(xwaitpid(pid, &wstatus, 0) == pid)) { + bfs_check(WIFSIGNALED(wstatus) && WTERMSIG(wstatus) == sig); + } + + // Check that the signal hook wrote the signal number to the pipe + int hsig; + if (bfs_echeck(xread(killed[0], &hsig, sizeof(hsig)) == sizeof(hsig))) { + bfs_check(hsig == sig); + } + } else { + // Child + xclose(ready[0]); + xclose(killed[0]); + + // exit_hook() will write to killed[1] + bfs_everify(atsigexit(exit_hook, killed) != NULL); + + // Tell the parent we're ready + bfs_everify(xwrite(ready[1], "A", 1) == 1); + + // Wait until we're killed + const struct timespec dur = { .tv_nsec = 1 }; + while (true) { + nanosleep(&dur, NULL); + } + } +} + +void check_sighook(void) { + check_hooks(); + + check_sigexit(SIGINT); + check_sigexit(SIGQUIT); + check_sigexit(SIGPIPE); + + // macOS cannot distinguish between sync and async SIG{BUS,ILL,SEGV} +#if !__APPLE__ + check_sigexit(SIGSEGV); +#endif +} diff --git a/tests/stddirs.sh b/tests/stddirs.sh index 1183970..1569fee 100644 --- a/tests/stddirs.sh +++ b/tests/stddirs.sh @@ -151,7 +151,7 @@ make_stddirs() { if ((CLEAN)); then defer clean_stddirs else - printf "Test files saved to ${BLD}%s${RST}\n" "$TMP" + color printf "Test files saved to ${BLD}%s${RST}\n" "$TMP" fi chown "$(id -u):$(id -g)" "$TMP" diff --git a/tests/trie.c b/tests/trie.c index 6e6024a..59bde40 100644 --- a/tests/trie.c +++ b/tests/trie.c @@ -39,6 +39,10 @@ static const char *keys[] = { ">>>>>>", ">>><<<", ">>>", + + "AAAAAAA", + "AAAAAAAB", + "AAAAAAAa", }; static const size_t nkeys = countof(keys); diff --git a/tests/xtouch.c b/tests/xtouch.c index e7c2e00..5d65a4c 100644 --- a/tests/xtouch.c +++ b/tests/xtouch.c @@ -217,11 +217,8 @@ int main(int argc, char *argv[]) { } if (marg) { - char *end; - long mode = strtol(marg, &end, 8); - // https://github.com/llvm/llvm-project/issues/64946 - sanitize_init(&end); - if (*marg && !*end && mode >= 0 && mode < 01000) { + long mode; + if (xstrtol(marg, NULL, 8, &mode) == 0 && mode >= 0 && mode < 01000) { args.fmode = args.dmode = mode; } else { fprintf(stderr, "%s: Invalid mode '%s'\n", cmd, marg); |