diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/alloc.c | 56 | ||||
| -rw-r--r-- | src/alloc.h | 194 | ||||
| -rw-r--r-- | src/atomic.h | 4 | ||||
| -rw-r--r-- | src/bar.c | 18 | ||||
| -rw-r--r-- | src/bar.h | 4 | ||||
| -rw-r--r-- | src/bfs.h | 138 | ||||
| -rw-r--r-- | src/bfstd.c | 311 | ||||
| -rw-r--r-- | src/bfstd.h | 195 | ||||
| -rw-r--r-- | src/bftw.c | 28 | ||||
| -rw-r--r-- | src/bftw.h | 18 | ||||
| -rw-r--r-- | src/bit.h | 97 | ||||
| -rw-r--r-- | src/color.c | 651 | ||||
| -rw-r--r-- | src/color.h | 18 | ||||
| -rw-r--r-- | src/ctx.c | 22 | ||||
| -rw-r--r-- | src/ctx.h | 18 | ||||
| -rw-r--r-- | src/diag.c | 31 | ||||
| -rw-r--r-- | src/diag.h | 130 | ||||
| -rw-r--r-- | src/dir.h | 20 | ||||
| -rw-r--r-- | src/dstring.c | 22 | ||||
| -rw-r--r-- | src/dstring.h | 153 | ||||
| -rw-r--r-- | src/eval.c | 204 | ||||
| -rw-r--r-- | src/eval.h | 6 | ||||
| -rw-r--r-- | src/exec.c | 2 | ||||
| -rw-r--r-- | src/exec.h | 12 | ||||
| -rw-r--r-- | src/expr.c | 3 | ||||
| -rw-r--r-- | src/expr.h | 5 | ||||
| -rw-r--r-- | src/fsade.c | 15 | ||||
| -rw-r--r-- | src/fsade.h | 14 | ||||
| -rw-r--r-- | src/ioq.c | 547 | ||||
| -rw-r--r-- | src/ioq.h | 85 | ||||
| -rw-r--r-- | src/list.h | 361 | ||||
| -rw-r--r-- | src/mtab.c | 27 | ||||
| -rw-r--r-- | src/mtab.h | 8 | ||||
| -rw-r--r-- | src/opt.c | 81 | ||||
| -rw-r--r-- | src/opt.h | 2 | ||||
| -rw-r--r-- | src/parse.c | 419 | ||||
| -rw-r--r-- | src/parse.h | 4 | ||||
| -rw-r--r-- | src/prelude.h | 33 | ||||
| -rw-r--r-- | src/printf.c | 8 | ||||
| -rw-r--r-- | src/printf.h | 12 | ||||
| -rw-r--r-- | src/pwcache.h | 24 | ||||
| -rw-r--r-- | src/sanity.h | 45 | ||||
| -rw-r--r-- | src/sighook.c | 268 | ||||
| -rw-r--r-- | src/sighook.h | 28 | ||||
| -rw-r--r-- | src/stat.c | 31 | ||||
| -rw-r--r-- | src/stat.h | 17 | ||||
| -rw-r--r-- | src/thread.c | 21 | ||||
| -rw-r--r-- | src/thread.h | 5 | ||||
| -rw-r--r-- | src/trie.c | 248 | ||||
| -rw-r--r-- | src/trie.h | 89 | ||||
| -rw-r--r-- | src/typo.h | 4 | ||||
| -rw-r--r-- | src/xregex.h | 16 | ||||
| -rw-r--r-- | src/xspawn.c | 99 | ||||
| -rw-r--r-- | src/xspawn.h | 10 | ||||
| -rw-r--r-- | src/xtime.c | 150 | ||||
| -rw-r--r-- | src/xtime.h | 75 |
56 files changed, 3360 insertions, 1746 deletions
diff --git a/src/alloc.c b/src/alloc.c index 223d737..3cf9026 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -20,24 +20,22 @@ # define ALLOC_MAX (SIZE_MAX / 2) #endif -/** Portable aligned_alloc()/posix_memalign(). */ +/** posix_memalign() wrapper. */ static void *xmemalign(size_t align, size_t size) { bfs_assert(has_single_bit(align)); bfs_assert(align >= sizeof(void *)); - bfs_assert(is_aligned(align, size)); -#if BFS_HAS_ALIGNED_ALLOC - return aligned_alloc(align, size); -#else + // Since https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2072.htm, + // aligned_alloc() doesn't require the size to be a multiple of align. + // But the sanitizers don't know about that yet, so always use + // posix_memalign(). void *ptr = NULL; errno = posix_memalign(&ptr, align, size); return ptr; -#endif } void *alloc(size_t align, size_t size) { bfs_assert(has_single_bit(align)); - bfs_assert(is_aligned(align, size)); if (size > ALLOC_MAX) { errno = EOVERFLOW; @@ -53,7 +51,6 @@ void *alloc(size_t align, size_t size) { void *zalloc(size_t align, size_t size) { bfs_assert(has_single_bit(align)); - bfs_assert(is_aligned(align, size)); if (size > ALLOC_MAX) { errno = EOVERFLOW; @@ -73,8 +70,6 @@ void *zalloc(size_t align, size_t size) { void *xrealloc(void *ptr, size_t align, size_t old_size, size_t new_size) { bfs_assert(has_single_bit(align)); - bfs_assert(is_aligned(align, old_size)); - bfs_assert(is_aligned(align, new_size)); if (new_size == 0) { free(ptr); @@ -108,10 +103,10 @@ void *reserve(void *ptr, size_t align, size_t size, size_t count) { size_t old_size = size * count; // Capacity is doubled every power of two, from 0→1, 1→2, 2→4, etc. - // If we stayed within the same size class, re-use ptr. + // 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; } @@ -126,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; } @@ -178,7 +173,7 @@ void arena_init(struct arena *arena, size_t align, size_t size) { } /** Allocate a new slab. */ -_cold +[[_cold]] static int slab_alloc(struct arena *arena) { // Make the initial allocation size ~4K size_t size = 4096; @@ -233,6 +228,7 @@ void arena_free(struct arena *arena, void *ptr) { union chunk *chunk = ptr; chunk_set_next(arena, chunk, arena->chunks); arena->chunks = chunk; + sanitize_uninit(chunk, arena->size); sanitize_free(chunk, arena->size); } @@ -252,7 +248,7 @@ void arena_destroy(struct arena *arena) { sanitize_uninit(arena); } -void varena_init(struct varena *varena, size_t align, size_t min, size_t offset, size_t size) { +void varena_init(struct varena *varena, size_t align, size_t offset, size_t size) { varena->align = align; varena->offset = offset; varena->size = size; @@ -261,7 +257,7 @@ void varena_init(struct varena *varena, size_t align, size_t min, size_t offset, // The smallest size class is at least as many as fit in the smallest // aligned allocation size - size_t min_count = (flex_size(align, min, offset, size, 1) - offset + size - 1) / size; + size_t min_count = (flex_size(align, offset, size, 1) - offset + size - 1) / size; varena->shift = bit_width(min_count - 1); } @@ -274,7 +270,7 @@ static size_t varena_size_class(struct varena *varena, size_t count) { /** Get the exact size of a flexible struct. */ static size_t varena_exact_size(const struct varena *varena, size_t count) { - return flex_size(varena->align, 0, varena->offset, varena->size, count); + return flex_size(varena->align, varena->offset, varena->size, count); } /** Get the arena for the given array length. */ @@ -308,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; } @@ -321,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; } @@ -338,16 +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((char *)ptr + old_exact_size, old_size - old_exact_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((char *)ret + new_exact_size, new_size - new_exact_size); + sanitize_resize(ret, new_size, varena_exact_size(varena, new_count), new_size); return ret; } diff --git a/src/alloc.h b/src/alloc.h index 7b97b8c..4f21ed0 100644 --- a/src/alloc.h +++ b/src/alloc.h @@ -14,124 +14,139 @@ #include <stddef.h> #include <stdlib.h> +#define IS_ALIGNED(align, size) \ + (((size) & ((align) - 1)) == 0) + /** Check if a size is properly aligned. */ static inline bool is_aligned(size_t align, size_t size) { - return (size & (align - 1)) == 0; + return IS_ALIGNED(align, size); } +#define ALIGN_FLOOR(align, size) \ + ((size) & ~((align) - 1)) + /** Round down to a multiple of an alignment. */ static inline size_t align_floor(size_t align, size_t size) { - return size & ~(align - 1); + return ALIGN_FLOOR(align, size); } +#define ALIGN_CEIL(align, size) \ + ((((size) - 1) | ((align) - 1)) + 1) + /** Round up to a multiple of an alignment. */ static inline size_t align_ceil(size_t align, size_t size) { - return align_floor(align, size + align - 1); + return ALIGN_CEIL(align, size); } /** - * Saturating array size. - * - * @param align - * Array element alignment. - * @param size - * Array element size. - * @param count - * Array element count. - * @return - * size * count, saturating to the maximum aligned value on overflow. + * Saturating size addition. */ -static inline size_t array_size(size_t align, size_t size, size_t count) { +static inline size_t size_add(size_t lhs, size_t rhs) { + size_t ret = lhs + rhs; + return ret >= lhs ? ret : (size_t)-1; +} + +/** + * Saturating size multiplication. + */ +static inline size_t size_mul(size_t size, size_t count) { size_t ret = size * count; - return ret / size == count ? ret : ~(align - 1); + return ret / size == count ? ret : (size_t)-1; } /** Saturating array sizeof. */ #define sizeof_array(type, count) \ - array_size(alignof(type), sizeof(type), count) + size_mul(sizeof(type), count) /** Size of a struct/union field. */ #define sizeof_member(type, member) \ sizeof(((type *)NULL)->member) /** + * @internal + * Our flexible struct size calculations assume that structs have the minimum + * trailing padding to align the type properly. A pathological ABI that adds + * extra padding would result in us under-allocating space for those structs, + * so we static_assert() that no such padding exists. + */ +#define ASSERT_FLEX_ABI(type, member) \ + ASSERT_FLEX_ABI_( \ + ALIGN_CEIL(alignof(type), offsetof(type, member)) >= sizeof(type), \ + "Unexpected tail padding in " #type) + +/** + * @internal + * The contortions here allow static_assert() to be used in expressions, rather + * than just declarations. + */ +#define ASSERT_FLEX_ABI_(...) \ + ((void)sizeof(struct { char _; static_assert(__VA_ARGS__); })) + +/** * Saturating flexible struct size. * - * @param align + * @align * Struct alignment. - * @param min - * Minimum struct size. - * @param offset + * @offset * Flexible array member offset. - * @param size + * @size * Flexible array element size. - * @param count + * @count * Flexible array element count. * @return * The size of the struct with count flexible array elements. Saturates * to the maximum aligned value on overflow. */ -static inline size_t flex_size(size_t align, size_t min, size_t offset, size_t size, size_t count) { - size_t ret = size * count; - size_t overflow = ret / size != count; - - size_t extra = offset + align - 1; - ret += extra; - overflow |= ret < extra; - ret |= -overflow; +static inline size_t flex_size(size_t align, size_t offset, size_t size, size_t count) { + size_t ret = size_mul(size, count); + ret = size_add(ret, offset + align - 1); ret = align_floor(align, ret); - - // Make sure flex_sizeof(type, member, 0) >= sizeof(type), even if the - // type has more padding than necessary for alignment - if (min > align_ceil(align, offset)) { - ret = ret < min ? min : ret; - } - return ret; } /** * Computes the size of a flexible struct. * - * @param type + * @type * The type of the struct containing the flexible array. - * @param member + * @member * The name of the flexible array member. - * @param count + * @count * The length of the flexible array. * @return * The size of the struct with count flexible array elements. Saturates * to the maximum aligned value on overflow. */ #define sizeof_flex(type, member, count) \ - flex_size(alignof(type), sizeof(type), offsetof(type, member), sizeof_member(type, member[0]), count) + (ASSERT_FLEX_ABI(type, member), flex_size( \ + alignof(type), offsetof(type, member), sizeof_member(type, member[0]), count)) /** * General memory allocator. * - * @param align + * @align * The required alignment. - * @param size + * @size * The size of the allocation. * @return * The allocated memory, or NULL on failure. */ -_malloc(free, 1) -_aligned_alloc(1, 2) +[[_malloc(free, 1)]] +[[_aligned_alloc(1, 2)]] void *alloc(size_t align, size_t size); /** * Zero-initialized memory allocator. * - * @param align + * @align * The required alignment. - * @param size + * @size * The size of the allocation. * @return * The allocated memory, or NULL on failure. */ -_malloc(free, 1) -_aligned_alloc(1, 2) +[[_malloc(free, 1)]] +[[_aligned_alloc(1, 2)]] void *zalloc(size_t align, size_t size); /** Allocate memory for the given type. */ @@ -161,19 +176,19 @@ void *zalloc(size_t align, size_t size); /** * Alignment-aware realloc(). * - * @param ptr + * @ptr * The pointer to reallocate. - * @param align + * @align * The required alignment. - * @param old_size + * @old_size * The previous allocation size. - * @param new_size + * @new_size * The new allocation size. * @return * The reallocated memory, or NULL on failure. */ -_aligned_alloc(2, 4) -_nodiscard +[[_nodiscard]] +[[_aligned_alloc(2, 4)]] void *xrealloc(void *ptr, size_t align, size_t old_size, size_t new_size); /** Reallocate memory for an array. */ @@ -187,11 +202,11 @@ void *xrealloc(void *ptr, size_t align, size_t old_size, size_t new_size); /** * Reserve space for one more element in a dynamic array. * - * @param ptr + * @ptr * The pointer to reallocate. - * @param align + * @align * The required alignment. - * @param count + * @count * The current size of the array. * @return * The reallocated memory, on both success *and* failure. On success, @@ -199,17 +214,17 @@ void *xrealloc(void *ptr, size_t align, size_t old_size, size_t new_size); * for (count + 1) elements. On failure, errno will be non-zero, and * ptr will returned unchanged. */ -_nodiscard +[[_nodiscard]] void *reserve(void *ptr, size_t align, size_t size, size_t count); /** * Convenience macro to grow a dynamic array. * - * @param type + * @type * The array element type. - * @param type **ptr + * @type **ptr * A pointer to the array. - * @param size_t *count + * @size_t *count * A pointer to the array's size. * @return * On success, a pointer to the newly reserved array element, i.e. @@ -257,7 +272,7 @@ void arena_free(struct arena *arena, void *ptr); /** * Allocate an object out of the arena. */ -_malloc(arena_free, 2) +[[_malloc(arena_free, 2)]] void *arena_alloc(struct arena *arena); /** @@ -291,40 +306,39 @@ struct varena { /** * Initialize a varena for a struct with the given layout. * - * @param varena + * @varena * The varena to initialize. - * @param align + * @align * alignof(type) - * @param min - * sizeof(type) - * @param offset + * @offset * offsetof(type, flexible_array) - * @param size + * @size * sizeof(flexible_array[i]) */ -void varena_init(struct varena *varena, size_t align, size_t min, size_t offset, size_t size); +void varena_init(struct varena *varena, size_t align, size_t offset, size_t size); /** * Initialize a varena for the given type and flexible array. * - * @param varena + * @varena * The varena to initialize. - * @param type + * @type * A struct type containing a flexible array. - * @param member + * @member * The name of the flexible array member. */ #define VARENA_INIT(varena, type, member) \ - varena_init(varena, alignof(type), sizeof(type), offsetof(type, member), sizeof_member(type, member[0])) + (ASSERT_FLEX_ABI(type, member), varena_init( \ + varena, alignof(type), offsetof(type, member), sizeof_member(type, member[0]))) /** * Free an arena-allocated flexible struct. * - * @param varena + * @varena * The that allocated the object. - * @param ptr + * @ptr * The object to free. - * @param count + * @count * The length of the flexible array. */ void varena_free(struct varena *varena, void *ptr, size_t count); @@ -332,46 +346,46 @@ void varena_free(struct varena *varena, void *ptr, size_t count); /** * Arena-allocate a flexible struct. * - * @param varena + * @varena * The varena to allocate from. - * @param count + * @count * The length of the flexible array. * @return * The allocated struct, or NULL on failure. */ -_malloc(varena_free, 2) +[[_malloc(varena_free, 2)]] void *varena_alloc(struct varena *varena, size_t count); /** * Resize a flexible struct. * - * @param varena + * @varena * The varena to allocate from. - * @param ptr + * @ptr * The object to resize. - * @param old_count - * The old array lenth. - * @param new_count + * @old_count + * The old array length. + * @new_count * The new array length. * @return * The resized struct, or NULL on failure. */ -_nodiscard +[[_nodiscard]] void *varena_realloc(struct varena *varena, void *ptr, size_t old_count, size_t new_count); /** * Grow a flexible struct by an arbitrary amount. * - * @param varena + * @varena * The varena to allocate from. - * @param ptr + * @ptr * The object to resize. - * @param count + * @count * Pointer to the flexible array length. * @return * The resized struct, or NULL on failure. */ -_nodiscard +[[_nodiscard]] void *varena_grow(struct varena *varena, void *ptr, size_t *count); /** diff --git a/src/atomic.h b/src/atomic.h index 2682c29..5c2826f 100644 --- a/src/atomic.h +++ b/src/atomic.h @@ -20,9 +20,9 @@ /** * Shorthand for atomic_load_explicit(). * - * @param obj + * @obj * A pointer to the atomic object. - * @param order + * @order * The memory ordering to use, without the memory_order_ prefix. * @return * The loaded value. @@ -18,7 +18,6 @@ #include <stdio.h> #include <stdlib.h> #include <string.h> -#include <sys/ioctl.h> #include <termios.h> #include <unistd.h> @@ -33,25 +32,14 @@ struct bfs_bar { /** Get the terminal size, if possible. */ static int bfs_bar_getsize(struct bfs_bar *bar) { -#if BFS_HAS_TCGETWINSIZE || defined(TIOCGWINSZ) struct winsize ws; - -# if BFS_HAS_TCGETWINSIZE - int ret = tcgetwinsize(bar->fd, &ws); -# else - int ret = ioctl(bar->fd, TIOCGWINSZ, &ws); -# endif - if (ret != 0) { - return ret; + if (xtcgetwinsize(bar->fd, &ws) != 0) { + return -1; } store(&bar->width, ws.ws_col, relaxed); store(&bar->height, ws.ws_row, relaxed); return 0; -#else - errno = ENOTSUP; - return -1; -#endif } /** Write a string to the status bar (async-signal-safe). */ @@ -139,7 +127,7 @@ static void bfs_bar_sigexit(int sig, siginfo_t *info, void *arg) { } /** printf() to the status bar with a single write(). */ -_printf(2, 3) +[[_printf(2, 3)]] static int bfs_bar_printf(struct bfs_bar *bar, const char *format, ...) { va_list args; va_start(args, format); @@ -27,9 +27,9 @@ unsigned int bfs_bar_width(const struct bfs_bar *bar); /** * Update the status bar message. * - * @param bar + * @bar * The status bar to update. - * @param str + * @str * The string to display. * @return * 0 on success, -1 on failure. @@ -8,6 +8,9 @@ #ifndef BFS_H #define BFS_H +#include <assert.h> // For __GLIBC__ +#include <stddef.h> // For offsetof + // Standard versions /** Possible __STDC_VERSION__ values. */ @@ -33,10 +36,15 @@ #ifndef BFS_COMMAND # define BFS_COMMAND "bfs" #endif + #ifndef BFS_HOMEPAGE # define BFS_HOMEPAGE "https://tavianator.com/projects/bfs.html" #endif +#ifndef BFS_LINT +# define BFS_LINT false +#endif + // This is a symbol instead of a literal so we don't have to rebuild everything // when the version number changes extern const char bfs_version[]; @@ -48,15 +56,36 @@ extern const char bfs_cflags[]; extern const char bfs_ldflags[]; extern const char bfs_ldlibs[]; -// Get __GLIBC__ -#include <assert.h> - // Fundamental utilities /** - * Get the length of an array. + * Given `ptr = &t->member`, return `t`. + */ +#define container_of(ptr, type, member) \ + (container_of_typecheck(ptr, type, member), \ + (type *)((char *)ptr - offsetof(type, member))) + +#define container_of_typecheck(ptr, type, field) \ + (void)sizeof(ptr - &((type *)NULL)->field) + +/** + * A preprocessor conditional. + * + * BFS_VA_IF(A)(B)(C) => B + * BFS_VA_IF( )(B)(C) => C */ -#define countof(...) (sizeof(__VA_ARGS__) / sizeof(0[__VA_ARGS__])) +#define BFS_VA_IF(...) BFS_VA_IF_AB ## __VA_OPT__(C) +// BFS_VA_IF(A)(B)(C) => BFS_VA_IF_ABC(B)(C) +// BFS_VA_IF( )(B)(C) => BFS_VA_IF_AB(B)(C) + +#define BFS_VA_IF_ABC(...) __VA_ARGS__ BFS_VA_IGNORE +// BFS_VA_IF_ABC(B)(C) => B BFS_VA_IGNORE(C) + +#define BFS_VA_IF_AB(...) BFS_VA_REPEAT +// BFS_VA_IF_AB(B)(C) => BFS_VA_REPEAT(C) + +#define BFS_VA_IGNORE(...) +#define BFS_VA_REPEAT(...) __VA_ARGS__ /** * False sharing/destructive interference/largest cache line size. @@ -84,19 +113,12 @@ extern const char bfs_ldlibs[]; // Wrappers for attributes /** - * Silence warnings about switch/case fall-throughs. - */ -#if __has_attribute(fallthrough) -# define _fallthrough __attribute__((fallthrough)) -#else -# define _fallthrough ((void)0) -#endif - -/** * Silence warnings about unused declarations. */ -#if __has_attribute(unused) -# define _maybe_unused __attribute__((unused)) +#if __has_c_attribute(maybe_unused) +# define _maybe_unused maybe_unused +#elif __has_c_attribute(gnu::unused) +# define _maybe_unused gnu::unused #else # define _maybe_unused #endif @@ -104,8 +126,10 @@ extern const char bfs_ldlibs[]; /** * Warn if a value is unused. */ -#if __has_attribute(warn_unused_result) -# define _nodiscard __attribute__((warn_unused_result)) +#if __has_c_attribute(nodiscard) +# define _nodiscard nodiscard +#elif __has_c_attribute(gnu::warn_unused_result) +# define _nodiscard gnu::warn_unused_result #else # define _nodiscard #endif @@ -113,35 +137,38 @@ extern const char bfs_ldlibs[]; /** * Hint to avoid inlining a function. */ -#if __has_attribute(noinline) -# define _noinline __attribute__((noinline)) +#if __has_c_attribute(gnu::noinline) +# define _noinline gnu::noinline #else # define _noinline #endif /** - * Marks a non-returning function. + * Hint that a function is unlikely to be called. */ -#if __STDC_VERSION__ >= C23 -# define _noreturn [[noreturn]] +#if __has_c_attribute(gnu::cold) +# define _cold _noinline, gnu::cold #else -# define _noreturn _Noreturn +# define _cold _noinline #endif /** - * Hint that a function is unlikely to be called. + * Marks a non-returning function. */ -#if __has_attribute(cold) -# define _cold _noinline __attribute__((cold)) +#if __has_c_attribute(noreturn) +# define _noreturn noreturn +#elif __has_c_attribute(gnu::noreturn) +# define _noreturn gnu::noreturn #else -# define _cold _noinline +# define _noreturn #endif + /** * Adds compiler warnings for bad printf()-style function calls, if supported. */ -#if __has_attribute(format) -# define _printf(fmt, args) __attribute__((format(printf, fmt, args))) +#if __has_c_attribute(gnu::format) +# define _printf(fmt, args) gnu::format(printf, fmt, args) #else # define _printf(fmt, args) #endif @@ -149,8 +176,8 @@ extern const char bfs_ldlibs[]; /** * Annotates functions that potentially modify and return format strings. */ -#if __has_attribute(format_arg) -# define _format_arg(arg) __attribute__((format_arg(arg))) +#if __has_c_attribute(gnu::format_arg) +# define _format_arg(arg) gnu::format_arg(arg) #else # define _format_arg(arg) #endif @@ -158,11 +185,11 @@ extern const char bfs_ldlibs[]; /** * Annotates allocator-like functions. */ -#if __has_attribute(malloc) +#if __has_c_attribute(gnu::malloc) # if __GNUC__ >= 11 && !__OPTIMIZE__ // malloc(deallocator) disables inlining on GCC -# define _malloc(...) _nodiscard __attribute__((malloc(__VA_ARGS__))) +# define _malloc(...) _nodiscard, gnu::malloc(__VA_ARGS__) # else -# define _malloc(...) _nodiscard __attribute__((malloc)) +# define _malloc(...) _nodiscard, gnu::malloc # endif #else # define _malloc(...) _nodiscard @@ -171,8 +198,8 @@ extern const char bfs_ldlibs[]; /** * Specifies that a function returns allocations with a given alignment. */ -#if __has_attribute(alloc_align) -# define _alloc_align(param) __attribute__((alloc_align(param))) +#if __has_c_attribute(gnu::alloc_align) +# define _alloc_align(param) gnu::alloc_align(param) #else # define _alloc_align(param) #endif @@ -180,8 +207,8 @@ extern const char bfs_ldlibs[]; /** * Specifies that a function returns allocations with a given size. */ -#if __has_attribute(alloc_size) -# define _alloc_size(...) __attribute__((alloc_size(__VA_ARGS__))) +#if __has_c_attribute(gnu::alloc_size) +# define _alloc_size(...) gnu::alloc_size(__VA_ARGS__) #else # define _alloc_size(...) #endif @@ -189,7 +216,7 @@ extern const char bfs_ldlibs[]; /** * Shorthand for _alloc_align() and _alloc_size(). */ -#define _aligned_alloc(align, ...) _alloc_align(align) _alloc_size(__VA_ARGS__) +#define _aligned_alloc(align, ...) _alloc_align(align), _alloc_size(__VA_ARGS__) /** * Check if function multiversioning via GNU indirect functions (ifunc) is supported. @@ -197,8 +224,13 @@ extern const char bfs_ldlibs[]; * Disabled on TSan due to https://github.com/google/sanitizers/issues/342. */ #ifndef BFS_USE_TARGET_CLONES -# if __has_attribute(target_clones) && (__GLIBC__ || __FreeBSD__) && !__SANITIZE_THREAD__ +# if __has_c_attribute(gnu::target_clones) \ + && (__GLIBC__ || __FreeBSD__) \ + && !__SANITIZE_THREAD__ \ + && !__SANITIZE_TYPE__ # define BFS_USE_TARGET_CLONES true +# else +# define BFS_USE_TARGET_CLONES false # endif #endif @@ -206,9 +238,31 @@ extern const char bfs_ldlibs[]; * Apply the target_clones attribute, if available. */ #if BFS_USE_TARGET_CLONES -# define _target_clones(...) __attribute__((target_clones(__VA_ARGS__))) +# define _target_clones(...) gnu::target_clones(__VA_ARGS__) #else # define _target_clones(...) #endif +/** + * Mark the size of a flexible array member. + */ +#if __has_c_attribute(clang::counted_by) +# define _counted_by(...) clang::counted_by(__VA_ARGS__) +#elif __has_c_attribute(gnu::counted_by) +# define _counted_by(...) gnu::counted_by(__VA_ARGS__) +#else +# define _counted_by(...) +#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..b78af7a 100644 --- a/src/bfstd.c +++ b/src/bfstd.c @@ -17,15 +17,18 @@ #include <locale.h> #include <nl_types.h> #include <pthread.h> +#include <sched.h> #include <stddef.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> +#include <sys/ioctl.h> #include <sys/resource.h> #include <sys/stat.h> #include <sys/types.h> #include <sys/wait.h> +#include <termios.h> #include <unistd.h> #include <wchar.h> @@ -186,16 +189,6 @@ char *xgetdelim(FILE *file, char delim) { } } -int open_cterm(int flags) { - char path[L_ctermid]; - if (ctermid(path) == NULL || strlen(path) == 0) { - errno = ENOTTY; - return -1; - } - - return open(path, flags); -} - const char *xgetprogname(void) { const char *cmd = NULL; #if BFS_HAS_GETPROGNAME @@ -211,35 +204,171 @@ 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; } + errno = 0; + 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) { + *end = endp; + } + // If end is NULL, make sure the entire string is valid - bool entire = !end; + if (endp == str || (!end && *endp != '\0')) { + errno = EINVAL; + return -1; + } + + return 0; +} + +int xstrtos(const char *str, char **end, int base, short *value) { + long n; + if (xstrtol(str, end, base, &n) != 0) { + return -1; + } + + if (n < SHRT_MIN || n > SHRT_MAX) { + errno = ERANGE; + return -1; + } + + *value = n; + return 0; +} + +int xstrtoi(const char *str, char **end, int base, int *value) { + long n; + if (xstrtol(str, end, base, &n) != 0) { + return -1; + } + + if (n < INT_MIN || n > INT_MAX) { + errno = ERANGE; + return -1; + } + + *value = n; + return 0; +} + +int xstrtol(const char *str, char **end, int base, long *value) { + if (xstrtox_prologue(str) != 0) { + return -1; + } + char *endp; - if (!end) { - end = &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; } - errno = 0; - long long result = strtoll(str, end, base); - if (errno != 0) { + 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; } - if (*end == str || (entire && **end != '\0')) { - errno = EINVAL; + 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); +} + +int xstrtous(const char *str, char **end, int base, unsigned short *value) { + unsigned long n; + if (xstrtoul(str, end, base, &n) != 0) { return -1; } - *value = result; + if (n > USHRT_MAX) { + errno = ERANGE; + return -1; + } + + *value = n; return 0; } +int xstrtoui(const char *str, char **end, int base, unsigned int *value) { + unsigned long n; + if (xstrtoul(str, end, base, &n) != 0) { + return -1; + } + + if (n > UINT_MAX) { + errno = ERANGE; + return -1; + } + + *value = n; + return 0; +} + +/** Common epilogue for xstrtou*() wrappers. */ +static int xstrtoux_epilogue(const char *str, char **end, char *endp) { + if (xstrtox_epilogue(str, end, endp) != 0) { + return -1; + } + + if (str[0] == '-') { + errno = ERANGE; + return -1; + } + + return 0; +} + +int xstrtoul(const char *str, char **end, int base, unsigned long *value) { + if (xstrtox_prologue(str) != 0) { + return -1; + } + + char *endp; + *value = strtoul(str, &endp, base); + return xstrtoux_epilogue(str, end, endp); +} + +int xstrtoull(const char *str, char **end, int base, unsigned long long *value) { + if (xstrtox_prologue(str) != 0) { + return -1; + } + + char *endp; + *value = strtoull(str, &endp, base); + return xstrtoux_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 +611,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; @@ -513,6 +644,32 @@ pid_t xwaitpid(pid_t pid, int *status, int flags) { return ret; } +int open_cterm(int flags) { + char path[L_ctermid]; + if (ctermid(path) == NULL || strlen(path) == 0) { + errno = ENOTTY; + return -1; + } + + return open(path, flags); +} + +int xtcgetwinsize(int fd, struct winsize *ws) { +#if BFS_HAS_TCGETWINSIZE + return tcgetwinsize(fd, ws); +#else + return ioctl(fd, TIOCGWINSZ, ws); +#endif +} + +int xtcsetwinsize(int fd, const struct winsize *ws) { +#if BFS_HAS_TCSETWINSIZE + return tcsetwinsize(fd, ws); +#else + return ioctl(fd, TIOCSWINSZ, ws); +#endif +} + int dup_cloexec(int fd) { #ifdef F_DUPFD_CLOEXEC return fcntl(fd, F_DUPFD_CLOEXEC, 0); @@ -731,41 +888,103 @@ long xsysconf(int name) { return ret; } -size_t asciilen(const char *str) { - return asciinlen(str, strlen(str)); -} +#if BFS_HAS_SCHED_GETAFFINITY +/** Get the CPU count in an affinity mask of the given size. */ +static long bfs_sched_getaffinity(size_t size) { + cpu_set_t set, *pset = &set; -size_t asciinlen(const char *str, size_t n) { - size_t i = 0; + if (size > sizeof(set)) { + pset = malloc(size); + if (!pset) { + return -1; + } + } -#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)); + long ret = -1; + if (sched_getaffinity(0, size, pset) == 0) { +# ifdef CPU_COUNT_S + ret = CPU_COUNT_S(size, pset); +# else + bfs_assert(size <= sizeof(set)); + ret = CPU_COUNT(pset); +# endif + } - const size_t mask = (SIZE_MAX / 0xFF) << 7; // 0x808080... - word &= mask; - if (!word) { - continue; - } + if (pset != &set) { + free(pset); + } + return ret; +} +#endif + +long nproc(void) { + long ret = 0; -#if ENDIAN_NATIVE == ENDIAN_BIG - word = bswap(word); -#elif ENDIAN_NATIVE != ENDIAN_LITTLE +#if BFS_HAS_SCHED_GETAFFINITY + size_t size = sizeof(cpu_set_t); + do { + ret = bfs_sched_getaffinity(size); + +# ifdef CPU_COUNT_S + // On Linux, sched_getaffinity(2) says: + // + // When working on systems with large kernel CPU affinity masks, one must + // dynamically allocate the mask argument (see CPU_ALLOC(3)). Currently, + // the only way to do this is by probing for the size of the required mask + // using sched_getaffinity() calls with increasing mask sizes (until the + // call does not fail with the error EINVAL). + size *= 2; +# else + // No support for dynamically-sized CPU masks break; +# endif + } while (ret < 0 && errno == EINVAL); #endif - size_t first = trailing_zeros(word) / 8; - return i + first; + if (ret < 1) { + ret = xsysconf(_SC_NPROCESSORS_ONLN); } -#endif - for (; i < n; ++i) { - if (!xisascii(str[i])) { - break; - } + if (ret < 1) { + ret = 1; } + return ret; +} + +size_t asciilen(const char *str) { + return asciinlen(str, strlen(str)); +} + +size_t asciinlen(const char *str, size_t n) { + const unsigned char *ustr = (const unsigned char *)str; + size_t i = 0; + + // Word-at-a-time isascii() +#define CHUNK(n) CHUNK_(uint##n##_t, load8_leu##n) +#define CHUNK_(type, load8) \ + (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 + while CHUNK(64); + if CHUNK(32); +#else + while CHUNK(32); +#endif + if CHUNK(16); + if CHUNK(8); + +#undef CHUNK_ +#undef CHUNK + return i; } diff --git a/src/bfstd.h b/src/bfstd.h index 557f253..15dd949 100644 --- a/src/bfstd.h +++ b/src/bfstd.h @@ -48,9 +48,9 @@ * Check if an error code is "like" another one. For example, ENOTDIR is * like ENOENT because they can both be triggered by non-existent paths. * - * @param error + * @error * The error code to check. - * @param category + * @category * The category to test for. Known categories include ENOENT and * ENAMETOOLONG. * @return @@ -66,7 +66,7 @@ bool errno_is_like(int category); /** * Apply the "negative errno" convention. * - * @param ret + * @ret * The return value of the attempted operation. * @return * ret, if non-negative, otherwise -errno. @@ -106,7 +106,7 @@ int try(int ret); /** * Re-entrant dirname() variant that always allocates a copy. * - * @param path + * @path * The path in question. * @return * The parent directory of the path. @@ -116,7 +116,7 @@ char *xdirname(const char *path); /** * Re-entrant basename() variant that always allocates a copy. * - * @param path + * @path * The path in question. * @return * The final component of the path. @@ -126,7 +126,7 @@ char *xbasename(const char *path); /** * Find the offset of the final component of a path. * - * @param path + * @path * The path in question. * @return * The offset of the basename. @@ -138,9 +138,9 @@ size_t xbaseoff(const char *path); /** * fopen() variant that takes open() style flags. * - * @param path + * @path * The path to open. - * @param flags + * @flags * Flags to pass to open(). */ FILE *xfopen(const char *path, int flags); @@ -148,9 +148,9 @@ FILE *xfopen(const char *path, int flags); /** * Convenience wrapper for getdelim(). * - * @param file + * @file * The file to read. - * @param delim + * @delim * The delimiter character to split on. * @return * The read chunk (without the delimiter), allocated with malloc(). @@ -158,16 +158,6 @@ FILE *xfopen(const char *path, int flags); */ char *xgetdelim(FILE *file, char delim); -/** - * Open the controlling terminal. - * - * @param flags - * The open() flags. - * @return - * An open file descriptor, or -1 on failure. - */ -int open_cterm(int flags); - // #include <stdlib.h> /** @@ -179,23 +169,56 @@ int open_cterm(int flags); const char *xgetprogname(void); /** + * Like xstrtol(), but for short. + */ +int xstrtos(const char *str, char **end, int base, short *value); + +/** + * Like xstrtol(), but for int. + */ +int xstrtoi(const char *str, char **end, int base, int *value); + +/** + * 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. - * - * @param str - * The string to parse. - * @param end - * If non-NULL, will hold a pointer to the first invalid character. - * If NULL, the entire string must be valid. - * @param base - * The base for the conversion, or 0 to auto-detect. - * @param 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); /** + * Like xstrtoul(), but for unsigned short. + */ +int xstrtous(const char *str, char **end, int base, unsigned short *value); + +/** + * Like xstrtoul(), but for unsigned int. + */ +int xstrtoui(const char *str, char **end, int base, unsigned int *value); + +/** + * Wrapper for strtoul() that forbids leading spaces, negatives. + */ +int xstrtoul(const char *str, char **end, int base, unsigned long *value); + +/** + * Wrapper for strtoull() that forbids leading spaces, negatives. + */ +int xstrtoull(const char *str, char **end, int base, unsigned 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. @@ -212,9 +235,9 @@ size_t asciilen(const char *str); /** * Get the length of the pure-ASCII prefix of a string. * - * @param str + * @str * The string to check. - * @param n + * @n * The maximum prefix length. */ size_t asciinlen(const char *str, size_t n); @@ -222,9 +245,9 @@ size_t asciinlen(const char *str, size_t n); /** * Allocate a copy of a region of memory. * - * @param src + * @src * The memory region to copy. - * @param size + * @size * The size of the memory region. * @return * A copy of the region, allocated with malloc(), or NULL on failure. @@ -234,12 +257,12 @@ void *xmemdup(const void *src, size_t size); /** * A nice string copying function. * - * @param dest + * @dest * The NUL terminator of the destination string, or `end` if it is * already truncated. - * @param end + * @end * The end of the destination buffer. - * @param src + * @src * The string to copy from. * @return * The new NUL terminator of the destination, or `end` on truncation. @@ -249,14 +272,14 @@ char *xstpecpy(char *dest, char *end, const char *src); /** * A nice string copying function. * - * @param dest + * @dest * The NUL terminator of the destination string, or `end` if it is * already truncated. - * @param end + * @end * The end of the destination buffer. - * @param src + * @src * The string to copy from. - * @param n + * @n * The maximum number of characters to copy. * @return * The new NUL terminator of the destination, or `end` on truncation. @@ -266,7 +289,7 @@ char *xstpencpy(char *dest, char *end, const char *src, size_t n); /** * Thread-safe strerror(). * - * @param errnum + * @errnum * An error number. * @return * A string describing that error, which remains valid until the next @@ -282,9 +305,9 @@ const char *errstr(void); /** * Format a mode like ls -l (e.g. -rw-r--r--). * - * @param mode + * @mode * The mode to format. - * @param str + * @str * The string to hold the formatted mode. */ void xstrmode(mode_t mode, char str[11]); @@ -339,12 +362,35 @@ int xminor(dev_t dev); */ pid_t xwaitpid(pid_t pid, int *status, int flags); +#include <sys/ioctl.h> // May be necessary for struct winsize +#include <termios.h> + +/** + * Open the controlling terminal. + * + * @flags + * The open() flags. + * @return + * An open file descriptor, or -1 on failure. + */ +int open_cterm(int flags); + +/** + * tcgetwinsize()/ioctl(TIOCGWINSZ) wrapper. + */ +int xtcgetwinsize(int fd, struct winsize *ws); + +/** + * tcsetwinsize()/ioctl(TIOCSWINSZ) wrapper. + */ +int xtcsetwinsize(int fd, const struct winsize *ws); + // #include <unistd.h> /** * Like dup(), but set the FD_CLOEXEC flag. * - * @param fd + * @fd * The file descriptor to duplicate. * @return * A duplicated file descriptor, or -1 on failure. @@ -354,7 +400,7 @@ int dup_cloexec(int fd); /** * Like pipe(), but set the FD_CLOEXEC flag. * - * @param pipefd + * @pipefd * The array to hold the two file descriptors. * @return * 0 on success, -1 on failure. @@ -383,7 +429,7 @@ size_t xwrite(int fd, const void *buf, size_t nbytes); /** * close() variant that preserves errno. * - * @param fd + * @fd * The file descriptor to close. */ void close_quietly(int fd); @@ -391,7 +437,7 @@ void close_quietly(int fd); /** * close() wrapper that asserts the file descriptor is valid. * - * @param fd + * @fd * The file descriptor to close. * @return * 0 on success, or -1 on error. @@ -406,11 +452,11 @@ int xfaccessat(int fd, const char *path, int amode); /** * readlinkat() wrapper that dynamically allocates the result. * - * @param fd + * @fd * The base directory descriptor. - * @param path + * @path * The path to the link, relative to fd. - * @param size + * @size * An estimate for the size of the link name (pass 0 if unknown). * @return * The target of the link, allocated with malloc(), or NULL on failure. @@ -420,7 +466,7 @@ char *xreadlinkat(int fd, const char *path, size_t size); /** * Wrapper for confstr() that allocates with malloc(). * - * @param name + * @name * The ID of the confstr to look up. * @return * The value of the confstr, or NULL on failure. @@ -430,12 +476,12 @@ char *xconfstr(int name); /** * Portability wrapper for strtofflags(). * - * @param str + * @str * The string to parse. The pointee will be advanced to the first * invalid position on error. - * @param set + * @set * The flags that are set in the string. - * @param clear + * @clear * The flags that are cleared in the string. * @return * 0 on success, -1 on failure. @@ -452,7 +498,7 @@ long xsysconf(int name); * * [1]: https://pubs.opengroup.org/onlinepubs/9799919799/basedefs/V1_chap02.html#tag_02_01_06 * - * @param name + * @name * The symbolic name of the POSIX option (e.g. SPAWN). * @return * The value of the option, either -1 or a date like 202405. @@ -460,18 +506,23 @@ long xsysconf(int name); #define sysoption(name) \ (_POSIX_##name == 0 ? xsysconf(_SC_##name) : _POSIX_##name) +/** + * Get the number of CPU threads available to the current process. + */ +long nproc(void); + #include <wchar.h> /** * Error-recovering mbrtowc() wrapper. * - * @param str + * @str * The string to convert. - * @param i + * @i * The current index. - * @param len + * @len * The length of the string. - * @param mb + * @mb * The multi-byte decoding state. * @return * The wide character at index *i, or WEOF if decoding fails. In either @@ -482,7 +533,7 @@ wint_t xmbrtowc(const char *str, size_t *i, size_t len, mbstate_t *mb); /** * wcswidth() variant that works on narrow strings. * - * @param str + * @str * The string to measure. * @return * The likely width of that string in a terminal. @@ -534,13 +585,13 @@ enum wesc_flags { /** * Escape a string as a single shell word. * - * @param dest + * @dest * The destination string to fill. - * @param end + * @end * The end of the destination buffer. - * @param src + * @src * The string to escape. - * @param flags + * @flags * Controls which characters to escape. * @return * The new NUL terminator of the destination, or `end` on truncation. @@ -550,15 +601,15 @@ char *wordesc(char *dest, char *end, const char *str, enum wesc_flags flags); /** * Escape a string as a single shell word. * - * @param dest + * @dest * The destination string to fill. - * @param end + * @end * The end of the destination buffer. - * @param src + * @src * The string to escape. - * @param n + * @n * The maximum length of the string. - * @param flags + * @flags * Controls which characters to escape. * @return * The new NUL terminator of the destination, or `end` on truncation. @@ -253,6 +253,7 @@ struct bftw_file { /** The length of the file's name. */ size_t namelen; /** The file's name. */ + // [[_counted_by(namelen + 1)]] char name[]; }; @@ -448,7 +449,7 @@ static void bftw_queue_rebalance(struct bftw_queue *queue, bool async) { } } -/** Detatch the next waiting file. */ +/** Detach the next waiting file. */ static void bftw_queue_detach(struct bftw_queue *queue, struct bftw_file *file, bool async) { bfs_assert(!file->ioqueued); @@ -1008,6 +1009,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 +1053,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); @@ -1162,12 +1168,13 @@ static int bftw_file_open(struct bftw_state *state, struct bftw_file *file, cons struct bftw_list parents; SLIST_INIT(&parents); - struct bftw_file *cur; - for (cur = file; cur != base; cur = cur->parent) { + // Reverse the chain of parents + for (struct bftw_file *cur = file; cur != base; cur = cur->parent) { SLIST_PREPEND(&parents, cur); } - while ((cur = SLIST_POP(&parents))) { + // Open each component relative to its parent + drain_slist (struct bftw_file, cur, &parents) { if (!cur->parent || cur->parent->fd >= 0) { bftw_file_openat(state, cur, cur->parent, cur->name); } @@ -1433,7 +1440,7 @@ static bool bftw_must_stat(const struct bftw_state *state, size_t depth, enum bf if (!(bftw_stat_flags(state, depth) & BFS_STAT_NOFOLLOW)) { return true; } - _fallthrough; + [[fallthrough]]; default: #if __linux__ @@ -1479,7 +1486,8 @@ fail: /** Check if we should stat() a file asynchronously. */ static bool bftw_should_ioq_stat(struct bftw_state *state, struct bftw_file *file) { - // To avoid surprising users too much, process the roots in order + // POSIX wants the root paths to be processed in order + // See https://www.austingroupbugs.net/view.php?id=1859 if (file->depth == 0) { return false; } @@ -1870,8 +1878,8 @@ static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) { } state->direrror = 0; - while ((file = SLIST_POP(&state->to_close, ready))) { - bftw_unwrapdir(state, file); + drain_slist (struct bftw_file, dead, &state->to_close, ready) { + bftw_unwrapdir(state, dead); } enum bftw_gc_flags visit = BFTW_VISIT_FILE; @@ -1952,6 +1960,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. */ @@ -75,9 +75,9 @@ struct BFTW { * Get bfs_stat() info for a file encountered during bftw(), caching the result * whenever possible. * - * @param ftwbuf + * @ftwbuf * bftw() data for the file to stat. - * @param flags + * @flags * flags for bfs_stat(). Pass ftwbuf->stat_flags for the default flags. * @return * A pointer to a bfs_stat() buffer, or NULL if the call failed. @@ -88,9 +88,9 @@ const struct bfs_stat *bftw_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags * Get bfs_stat() info for a file encountered during bftw(), if it has already * been cached. * - * @param ftwbuf + * @ftwbuf * bftw() data for the file to stat. - * @param flags + * @flags * flags for bfs_stat(). Pass ftwbuf->stat_flags for the default flags. * @return * A pointer to a bfs_stat() buffer, or NULL if no stat info is cached. @@ -102,9 +102,9 @@ const struct bfs_stat *bftw_cached_stat(const struct BFTW *ftwbuf, enum bfs_stat * whether to follow links. This function will avoid calling bfs_stat() if * possible. * - * @param ftwbuf + * @ftwbuf * bftw() data for the file to check. - * @param flags + * @flags * flags for bfs_stat(). Pass ftwbuf->stat_flags for the default flags. * @return * The type of the file, or BFS_ERROR if an error occurred. @@ -126,9 +126,9 @@ enum bftw_action { /** * Callback function type for bftw(). * - * @param ftwbuf + * @ftwbuf * Data about the current file. - * @param ptr + * @ptr * The pointer passed to bftw(). * @return * An action value. @@ -211,7 +211,7 @@ struct bftw_args { * Like ftw(3) and nftw(3), this function walks a directory tree recursively, * and invokes a callback for each path it encounters. * - * @param args + * @args * The arguments that control the walk. * @return * 0 on success, or -1 on failure. @@ -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__ @@ -198,15 +198,35 @@ static inline uint8_t bswap_u8(uint8_t n) { return n; } -/** - * Reverse the byte order of an integer. - */ -#define bswap(n) \ - _Generic((n), \ - uint8_t: bswap_u8, \ - uint16_t: bswap_u16, \ - uint32_t: bswap_u32, \ - uint64_t: bswap_u64)(n) +#if UCHAR_WIDTH == 8 +# define bswap_uc bswap_u8 +#endif + +#if USHRT_WIDTH == 16 +# define bswap_us bswap_u16 +#elif USHRT_WIDTH == 32 +# define bswap_us bswap_u32 +#elif USHRT_WIDTH == 64 +# define bswap_us bswap_u64 +#endif + +#if UINT_WIDTH == 16 +# define bswap_ui bswap_u16 +#elif UINT_WIDTH == 32 +# define bswap_ui bswap_u32 +#elif UINT_WIDTH == 64 +# define bswap_ui bswap_u64 +#endif + +#if ULONG_WIDTH == 32 +# define bswap_ul bswap_u32 +#elif ULONG_WIDTH == 64 +# define bswap_ul bswap_u64 +#endif + +#if ULLONG_WIDTH == 64 +# define bswap_ull bswap_u64 +#endif // Define an overload for each unsigned type #define UINT_OVERLOADS(macro) \ @@ -225,6 +245,63 @@ static inline uint8_t bswap_u8(uint8_t n) { unsigned long: name##_ul, \ unsigned long long: name##_ull) +/** + * Reverse the byte order of an integer. + */ +#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 7f653b0..2d0fc9c 100644 --- a/src/color.c +++ b/src/color.c @@ -31,7 +31,8 @@ struct esc_seq { /** The length of the escape sequence. */ size_t len; - /** The escape sequence iteself, without a terminating NUL. */ + /** The escape sequence itself, without a terminating NUL. */ + [[_counted_by(len)]] char seq[]; }; @@ -48,6 +49,7 @@ struct ext_color { /** Whether the comparison should be case-sensitive. */ bool case_sensitive; /** The extension to match (NUL-terminated). */ + // [[_counted_by(len + 1)]] char ext[]; }; @@ -103,6 +105,8 @@ struct colors { struct esc_seq *pipe; struct esc_seq *socket; + struct esc_seq *dataless; + /** A mapping from color names (fi, di, ln, etc.) to struct fields. */ struct trie names; @@ -143,13 +147,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 +157,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. */ @@ -168,26 +165,32 @@ static int cat_esc(dchar **dstr, const struct esc_seq *seq) { return dstrxcat(dstr, seq->seq, seq->len); } -/** Set a named escape sequence. */ -static int set_esc(struct colors *colors, const char *name, dchar *value) { - struct esc_seq **field = get_esc(colors, name); - if (!field) { - return 0; +/** Set an escape sequence field. */ +static int set_esc_field(struct colors *colors, struct esc_seq **field, const dchar *value) { + struct esc_seq *seq = NULL; + if (value) { + seq = new_esc(colors, value, dstrlen(value)); + if (!seq) { + return -1; + } } if (*field) { free_esc(colors, *field); - *field = NULL; } + *field = seq; - if (value) { - *field = new_esc(colors, value, dstrlen(value)); - if (!*field) { - return -1; - } + return 0; +} + +/** Set a named escape sequence. */ +static int set_esc(struct colors *colors, const char *name, const dchar *value) { + struct esc_seq **field = get_esc(colors, name); + if (!field) { + return 0; } - return 0; + return set_esc_field(colors, field, value); } /** Reverse a string, to turn suffix matches into prefix matches. */ @@ -225,18 +228,22 @@ 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. */ static int set_ext(struct colors *colors, dchar *key, dchar *value) { size_t len = dstrlen(key); + + // Embedded NUL bytes in extensions can lead to a non-prefix-free + // set of strings, e.g. {".gz", "\0.gz"} would be transformed to + // {"zg.\0", "zg.\0\0"} (showing the implicit terminating NUL). + // Our trie implementation only supports prefix-free key sets, but + // luckily '\0' cannot appear in filenames so we can ignore them. + if (memchr(key, '\0', len)) { + return 0; + } + struct ext_color *ext = varena_alloc(&colors->ext_arena, len + 1); if (!ext) { return -1; @@ -277,9 +284,9 @@ fail: /** * The "smart case" algorithm. * - * @param ext + * @ext * The current extension being added. - * @param iext + * @iext * The previous case-insensitive match, if any, for the same extension. * @return * Whether this extension should become case-sensitive. @@ -359,9 +366,8 @@ static int build_iext_trie(struct colors *colors) { /** * Find a color by an extension. */ -static const struct esc_seq *get_ext(const struct colors *colors, const char *filename) { +static const struct esc_seq *get_ext(const struct colors *colors, const char *filename, size_t name_len) { size_t ext_len = colors->ext_len; - size_t name_len = strlen(filename); if (name_len < ext_len) { ext_len = name_len; } @@ -370,7 +376,8 @@ static const struct esc_seq *get_ext(const struct colors *colors, const char *fi char buf[256]; char *copy; if (ext_len < sizeof(buf)) { - copy = memcpy(buf, suffix, ext_len + 1); + copy = memcpy(buf, suffix, ext_len); + copy[ext_len] = '\0'; } else { copy = strndup(suffix, ext_len); if (!copy) { @@ -418,13 +425,13 @@ static const struct esc_seq *get_ext(const struct colors *colors, const char *fi * * See man dir_colors. * - * @param str + * @str * A dstring to fill with the unescaped chunk. - * @param value + * @value * The value to parse. - * @param end + * @end * The character that marks the end of the chunk. - * @param[out] next + * @next[out] * Will be set to the next chunk. * @return * 0 on success, -1 on failure. @@ -610,6 +617,109 @@ fail: return ret; } +/** Parse the FreeBSD $LSCOLORS format. */ +static int parse_bsd_ls_colors(struct colors *colors, const char *lscolors) { + static const char *fg_codes[256] = { + // 0-7: deprecated aliases for a-h + ['0'] = "30", ['1'] = "31", ['2'] = "32", ['3'] = "33", + ['4'] = "34", ['5'] = "35", ['6'] = "36", ['7'] = "37", + // a-h: first 8 ANSI foreground colors + ['a'] = "30", ['b'] = "31", ['c'] = "32", ['d'] = "33", + ['e'] = "34", ['f'] = "35", ['g'] = "36", ['h'] = "37", + // x: default foreground + ['x'] = "39", + // A-H: bold foreground colors + ['A'] = "1;30", ['B'] = "1;31", ['C'] = "1;32", ['D'] = "1;33", + ['E'] = "1;34", ['F'] = "1;35", ['G'] = "1;36", ['H'] = "1;37", + // X: bold default foreground + ['X'] = "1;39", + }; + + static const char *bg_codes[256] = { + // 0-7: deprecated aliases for a-h + ['0'] = "40", ['1'] = "41", ['2'] = "42", ['3'] = "43", + ['4'] = "44", ['5'] = "45", ['6'] = "46", ['7'] = "47", + // a-h: first 8 ANSI background colors + ['a'] = "40", ['b'] = "41", ['c'] = "42", ['d'] = "43", + ['e'] = "44", ['f'] = "45", ['g'] = "46", ['h'] = "47", + // x: default background + ['x'] = "49", + // A-H: background colors + underline + ['A'] = "4;40", ['B'] = "4;41", ['C'] = "4;42", ['D'] = "4;43", + ['E'] = "4;44", ['F'] = "4;45", ['G'] = "4;46", ['H'] = "4;47", + // X: default background + underline + ['X'] = "4;49", + }; + + // Please refer to https://man.freebsd.org/cgi/man.cgi?ls(1)#ENVIRONMENT + char complete_colors[] = "exfxcxdxbxegedabagacadah"; + + // For short $LSCOLORS, use the default colors for the rest + size_t max = strlen(complete_colors); + size_t len = strnlen(lscolors, max); + memcpy(complete_colors, lscolors, len); + + struct esc_seq **keys[] = { + &colors->directory, + &colors->link, + &colors->socket, + &colors->pipe, + &colors->executable, + &colors->blockdev, + &colors->chardev, + &colors->setuid, + &colors->setgid, + &colors->sticky_other_writable, + &colors->other_writable, + &colors->dataless, + }; + + dchar *buf = dstralloc(8); + if (!buf) { + return -1; + } + + int ret = -1; + for (size_t i = 0; i < countof(keys); ++i) { + uint8_t fg = complete_colors[2 * i]; + uint8_t bg = complete_colors[2 * i + 1]; + + const char *fg_code = fg_codes[fg]; + const char *bg_code = bg_codes[bg]; + + dstrshrink(buf, 0); + if (fg_code) { + if (dstrcat(&buf, fg_code) != 0) { + goto fail; + } + } + if (fg_code && bg_code) { + if (dstrcat(&buf, ";") != 0) { + goto fail; + } + } + if (bg_code) { + if (dstrcat(&buf, bg_code) != 0) { + goto fail; + } + } + + const dchar *value = dstrlen(buf) > 0 ? buf : NULL; + if (set_esc_field(colors, keys[i], value) != 0) { + goto fail; + } + } + + ret = 0; +fail: + dstrfree(buf); + return ret; +} + +static bool str_isset(const char *str) { + return str && *str; +} + struct colors *parse_colors(void) { struct colors *colors = ALLOC(struct colors); if (!colors) { @@ -675,16 +785,28 @@ struct colors *parse_colors(void) { fail = fail || init_esc(colors, "pi", "33", &colors->pipe); fail = fail || init_esc(colors, "so", "01;35", &colors->socket); + colors->dataless = NULL; + if (fail) { goto fail; } - if (parse_gnu_ls_colors(colors, getenv("LS_COLORS")) != 0) { - goto fail; - } - if (parse_gnu_ls_colors(colors, getenv("BFS_COLORS")) != 0) { - goto fail; + const char *gnu_colors = getenv("LS_COLORS"); + const char *bfs_colors = getenv("BFS_COLORS"); + const char *bsd_colors = getenv("LSCOLORS"); + if (str_isset(gnu_colors) || str_isset(bfs_colors)) { + if (parse_gnu_ls_colors(colors, gnu_colors) != 0) { + goto fail; + } + if (parse_gnu_ls_colors(colors, bfs_colors) != 0) { + goto fail; + } + } else if (str_isset(bsd_colors)) { + if (parse_bsd_ls_colors(colors, bsd_colors) != 0) { + goto fail; + } } + if (build_iext_trie(colors) != 0) { goto fail; } @@ -771,44 +893,245 @@ int cfclose(CFILE *cfile) { return ret; } +bool colors_need_stat(const struct colors *colors) { + return colors->setuid || colors->setgid || colors->executable || colors->multi_hard + || colors->sticky_other_writable || colors->other_writable || colors->sticky; +} + +/** A colorable file path. */ +struct cpath { + /** The full path to color. */ + const char *path; + /** The basename offset of the last valid component. */ + size_t nameoff; + /** The end offset of the last valid component. */ + size_t valid; + /** The total length of the path. */ + size_t len; + + /** The bftw() buffer. */ + const struct BFTW *ftwbuf; + /** bfs_stat() flags for the final component. */ + enum bfs_stat_flags flags; + /** A bfs_stat() buffer, filled in when 0 < valid < len. */ + struct bfs_stat statbuf; +}; + +/** Move the valid range of a path backwards. */ +static void cpath_retreat(struct cpath *cpath) { + const char *path = cpath->path; + size_t nameoff = cpath->nameoff; + size_t valid = cpath->valid; + + if (valid > 0 && path[valid - 1] == '/') { + // Try without trailing slashes, to distinguish "notdir/" from "notdir" + do { + --valid; + } while (valid > 0 && path[valid - 1] == '/'); + + nameoff = valid; + while (nameoff > 0 && path[nameoff - 1] != '/') { + --nameoff; + } + } else { + // Remove the last component and try again + valid = nameoff; + } + + cpath->nameoff = nameoff; + cpath->valid = valid; +} + +/** Initialize a struct cpath. */ +static int cpath_init(struct cpath *cpath, const char *path, const struct BFTW *ftwbuf, enum bfs_stat_flags flags) { + // Normally there are only two components to color: + // + // nameoff valid + // v v + // path/to/filename + // --------+------- + // ${di} ${fi} + // + // Error cases also usually have two components: + // + // valid, + // nameoff + // v + // path/to/nowhere + // --------+------ + // ${di} ${mi} + // + // But with ENOTDIR, there may be three: + // + // nameoff valid + // v v + // path/to/filename/nowhere + // --------+-------+------- + // ${di} ${fi} ${mi} + + cpath->path = path; + cpath->len = strlen(path); + cpath->ftwbuf = ftwbuf; + cpath->flags = flags; + + cpath->valid = cpath->len; + if (path == ftwbuf->path) { + cpath->nameoff = ftwbuf->nameoff; + } else { + cpath->nameoff = xbaseoff(path); + } + + if (bftw_type(ftwbuf, flags) != BFS_ERROR) { + return 0; + } + + cpath_retreat(cpath); + + // Find the base path. For symlinks like + // + // path/to/symlink -> nested/file + // + // this will be something like + // + // path/to/nested/file + int at_fd = AT_FDCWD; + dchar *at_path = NULL; + if (path == ftwbuf->path) { + if (ftwbuf->depth > 0) { + // The parent must have existed to get here + return 0; + } + } else { + // We're in print_link_target(), so resolve relative to the link's parent directory + at_fd = ftwbuf->at_fd; + if (at_fd == (int)AT_FDCWD && path[0] != '/') { + at_path = dstrxdup(ftwbuf->path, ftwbuf->nameoff); + if (!at_path) { + return -1; + } + } + } + + if (!at_path) { + at_path = dstralloc(cpath->valid); + if (!at_path) { + return -1; + } + } + if (dstrxcat(&at_path, path, cpath->valid) != 0) { + dstrfree(at_path); + return -1; + } + + size_t at_off = dstrlen(at_path) - cpath->valid; + + // Find the longest valid path prefix + while (cpath->valid > 0) { + if (bfs_stat(at_fd, at_path, BFS_STAT_FOLLOW, &cpath->statbuf) == 0) { + break; + } + + cpath_retreat(cpath); + dstrshrink(at_path, at_off + cpath->valid); + } + + dstrfree(at_path); + return 0; +} + +/** Get the bfs_stat() buffer for the last valid component. */ +static const struct bfs_stat *cpath_stat(const struct cpath *cpath) { + if (cpath->valid == cpath->len) { + return bftw_stat(cpath->ftwbuf, cpath->flags); + } else { + return &cpath->statbuf; + } +} + +/** Check if a path has non-trivial capabilities. */ +static bool cpath_has_capabilities(const struct cpath *cpath) { + if (cpath->valid == cpath->len) { + return bfs_check_capabilities(cpath->ftwbuf) > 0; + } else { + // TODO: implement capability checks for arbitrary paths + return false; + } +} + /** Check if a symlink is broken. */ -static bool is_link_broken(const struct BFTW *ftwbuf) { +static bool cpath_is_broken(const struct cpath *cpath) { + if (cpath->valid < cpath->len) { + // A valid parent can't be a broken link + return false; + } + + const struct BFTW *ftwbuf = cpath->ftwbuf; if (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW) { return xfaccessat(ftwbuf->at_fd, ftwbuf->at_path, F_OK) != 0; } else { + // A link encountered with BFS_STAT_TRYFOLLOW must be broken return true; } } -bool colors_need_stat(const struct colors *colors) { - return colors->setuid || colors->setgid || colors->executable || colors->multi_hard - || colors->sticky_other_writable || colors->other_writable || colors->sticky; +/** Check if we need a statbuf to colorize a file. */ +static bool must_stat(const struct colors *colors, enum bfs_type type) { + switch (type) { + case BFS_REG: + if (colors->setuid || colors->setgid || colors->executable || colors->multi_hard) { + return true; + } + +#ifdef ST_DATALESS + if (colors->dataless) { + return true; + } +#endif + + return false; + + case BFS_DIR: + if (colors->sticky_other_writable || colors->other_writable || colors->sticky) { + return true; + } + + return false; + + default: + return false; + } } /** Get the color for a file. */ -static const struct esc_seq *file_color(const struct colors *colors, const char *filename, const struct BFTW *ftwbuf, enum bfs_stat_flags flags) { - enum bfs_type type = bftw_type(ftwbuf, flags); +static const struct esc_seq *file_color(const struct colors *colors, const struct cpath *cpath) { + enum bfs_type type; + if (cpath->valid == cpath->len) { + type = bftw_type(cpath->ftwbuf, cpath->flags); + } else { + type = bfs_mode_to_type(cpath->statbuf.mode); + } + if (type == BFS_ERROR) { goto error; } const struct bfs_stat *statbuf = NULL; + if (must_stat(colors, type)) { + statbuf = cpath_stat(cpath); + if (!statbuf) { + goto error; + } + } + const struct esc_seq *color = NULL; switch (type) { case BFS_REG: - if (colors->setuid || colors->setgid || colors->executable || colors->multi_hard) { - statbuf = bftw_stat(ftwbuf, flags); - if (!statbuf) { - goto error; - } - } - if (colors->setuid && (statbuf->mode & 04000)) { color = colors->setuid; } else if (colors->setgid && (statbuf->mode & 02000)) { color = colors->setgid; - } else if (colors->capable && bfs_check_capabilities(ftwbuf) > 0) { + } else if (colors->capable && cpath_has_capabilities(cpath)) { color = colors->capable; } else if (colors->executable && (statbuf->mode & 00111)) { color = colors->executable; @@ -816,8 +1139,16 @@ static const struct esc_seq *file_color(const struct colors *colors, const char color = colors->multi_hard; } +#ifdef SF_DATALESS + if (!color && colors->dataless && (statbuf->attrs & SF_DATALESS)) { + color = colors->dataless; + } +#endif + if (!color) { - color = get_ext(colors, filename); + const char *name = cpath->path + cpath->nameoff; + size_t namelen = cpath->valid - cpath->nameoff; + color = get_ext(colors, name, namelen); } if (!color) { @@ -827,13 +1158,6 @@ static const struct esc_seq *file_color(const struct colors *colors, const char break; case BFS_DIR: - if (colors->sticky_other_writable || colors->other_writable || colors->sticky) { - statbuf = bftw_stat(ftwbuf, flags); - if (!statbuf) { - goto error; - } - } - if (colors->sticky_other_writable && (statbuf->mode & 01002) == 01002) { color = colors->sticky_other_writable; } else if (colors->other_writable && (statbuf->mode & 00002)) { @@ -847,7 +1171,7 @@ static const struct esc_seq *file_color(const struct colors *colors, const char break; case BFS_LNK: - if (colors->orphan && is_link_broken(ftwbuf)) { + if (colors->orphan && cpath_is_broken(cpath)) { color = colors->orphan; } else { color = colors->link; @@ -934,6 +1258,10 @@ static int print_wordesc(CFILE *cfile, const char *str, size_t n, enum wesc_flag /** Print a string with an optional color. */ static int print_colored(CFILE *cfile, const struct esc_seq *esc, const char *str, size_t len) { + if (len == 0) { + return 0; + } + if (print_esc(cfile, esc) != 0) { return -1; } @@ -950,112 +1278,42 @@ static int print_colored(CFILE *cfile, const struct esc_seq *esc, const char *st return 0; } -/** Find the offset of the first broken path component. */ -static ssize_t first_broken_offset(const char *path, const struct BFTW *ftwbuf, enum bfs_stat_flags flags, size_t max) { - ssize_t ret = max; - bfs_assert(ret >= 0); - - if (bftw_type(ftwbuf, flags) != BFS_ERROR) { - goto out; - } - - dchar *at_path; - int at_fd; - if (path == ftwbuf->path) { - if (ftwbuf->depth == 0) { - at_fd = AT_FDCWD; - at_path = dstrxdup(path, max); - } else { - // The parent must have existed to get here - goto out; - } - } else { - // We're in print_link_target(), so resolve relative to the link's parent directory - at_fd = ftwbuf->at_fd; - if (at_fd == (int)AT_FDCWD && path[0] != '/') { - at_path = dstrxdup(ftwbuf->path, ftwbuf->nameoff); - if (at_path && dstrxcat(&at_path, path, max) != 0) { - ret = -1; - goto out_path; - } - } else { - at_path = dstrxdup(path, max); - } - } - - if (!at_path) { - ret = -1; - goto out; - } - - while (ret > 0) { - if (xfaccessat(at_fd, at_path, F_OK) == 0) { - break; - } - - size_t len = dstrlen(at_path); - while (ret && at_path[len - 1] == '/') { - --len, --ret; - } - if (errno != ENOTDIR) { - while (ret && at_path[len - 1] != '/') { - --len, --ret; - } - } - - dstresize(&at_path, len); - } - -out_path: - dstrfree(at_path); -out: - return ret; -} - /** Print a path with colors. */ static int print_path_colored(CFILE *cfile, const char *path, const struct BFTW *ftwbuf, enum bfs_stat_flags flags) { - size_t nameoff; - if (path == ftwbuf->path) { - nameoff = ftwbuf->nameoff; - } else { - nameoff = xbaseoff(path); - } - - const char *name = path + nameoff; - size_t pathlen = nameoff + strlen(name); - - ssize_t broken = first_broken_offset(path, ftwbuf, flags, nameoff); - if (broken < 0) { + struct cpath cpath; + if (cpath_init(&cpath, path, ftwbuf, flags) != 0) { return -1; } - size_t split = broken; const struct colors *colors = cfile->colors; const struct esc_seq *dirs_color = colors->directory; - const struct esc_seq *name_color; + const struct esc_seq *name_color = NULL; + const struct esc_seq *err_color = colors->missing; + if (!err_color) { + err_color = colors->orphan; + } - if (split < nameoff) { - name_color = colors->missing; - if (!name_color) { - name_color = colors->orphan; - } - } else { - name_color = file_color(cfile->colors, path + nameoff, ftwbuf, flags); + if (cpath.nameoff < cpath.valid) { + name_color = file_color(colors, &cpath); if (name_color == dirs_color) { - split = pathlen; + cpath.nameoff = cpath.valid; } } - if (split > 0) { - if (print_colored(cfile, dirs_color, path, split) != 0) { - return -1; - } + if (print_colored(cfile, dirs_color, path, cpath.nameoff) != 0) { + return -1; } - if (split < pathlen) { - if (print_colored(cfile, name_color, path + split, pathlen - split) != 0) { - return -1; - } + const char *name = path + cpath.nameoff; + size_t name_len = cpath.valid - cpath.nameoff; + if (print_colored(cfile, name_color, name, name_len) != 0) { + return -1; + } + + const char *tail = path + cpath.valid; + size_t tail_len = cpath.len - cpath.valid; + if (print_colored(cfile, err_color, tail, tail_len) != 0) { + return -1; } return 0; @@ -1063,8 +1321,18 @@ static int print_path_colored(CFILE *cfile, const char *path, const struct BFTW /** Print a file name with colors. */ static int print_name_colored(CFILE *cfile, const char *name, const struct BFTW *ftwbuf, enum bfs_stat_flags flags) { - const struct esc_seq *esc = file_color(cfile->colors, name, ftwbuf, flags); - return print_colored(cfile, esc, name, strlen(name)); + size_t len = strlen(name); + const struct cpath cpath = { + .path = name, + .nameoff = 0, + .valid = len, + .len = len, + .ftwbuf = ftwbuf, + .flags = flags, + }; + + const struct esc_seq *esc = file_color(cfile->colors, &cpath); + return print_colored(cfile, esc, name, cpath.len); } /** Print the name of a file with the appropriate colors. */ @@ -1121,9 +1389,36 @@ static int print_link_target(CFILE *cfile, const struct BFTW *ftwbuf) { } /** Format some colored output to the buffer. */ -_printf(2, 3) +[[_printf(2, 3)]] static int cbuff(CFILE *cfile, const char *format, ...); +/** Print an expression's name, for diagnostics. */ +static int print_expr_name(CFILE *cfile, const struct bfs_expr *expr) { + switch (expr->kind) { + case BFS_FLAG: + return cbuff(cfile, "${cyn}%pq${rs}", expr->argv[0]); + case BFS_OPERATOR: + return cbuff(cfile, "${red}%pq${rs}", expr->argv[0]); + default: + return cbuff(cfile, "${blu}%pq${rs}", expr->argv[0]); + } +} + +/** Print an expression's args, for diagnostics. */ +static int print_expr_args(CFILE *cfile, const struct bfs_expr *expr) { + if (print_expr_name(cfile, expr) != 0) { + return -1; + } + + for (size_t i = 1; i < expr->argc; ++i) { + if (cbuff(cfile, " ${bld}%pq${rs}", expr->argv[i]) < 0) { + return -1; + } + } + + return 0; +} + /** Dump a parsed expression tree, for debugging. */ static int print_expr(CFILE *cfile, const struct bfs_expr *expr, bool verbose, int depth) { if (depth >= 2) { @@ -1138,28 +1433,10 @@ static int print_expr(CFILE *cfile, const struct bfs_expr *expr, bool verbose, i return -1; } - int ret; - switch (expr->kind) { - case BFS_FLAG: - ret = cbuff(cfile, "${cyn}%pq${rs}", expr->argv[0]); - break; - case BFS_OPERATOR: - ret = cbuff(cfile, "${red}%pq${rs}", expr->argv[0]); - break; - default: - ret = cbuff(cfile, "${blu}%pq${rs}", expr->argv[0]); - break; - } - if (ret < 0) { + if (print_expr_args(cfile, expr) != 0) { return -1; } - for (size_t i = 1; i < expr->argc; ++i) { - if (cbuff(cfile, " ${bld}%pq${rs}", expr->argv[i]) < 0) { - return -1; - } - } - if (verbose) { double rate = 0.0, time = 0.0; if (expr->evaluations) { @@ -1196,7 +1473,7 @@ static int print_expr(CFILE *cfile, const struct bfs_expr *expr, bool verbose, i return 0; } -_printf(2, 0) +[[_printf(2, 0)]] static int cvbuff(CFILE *cfile, const char *format, va_list args) { const struct colors *colors = cfile->colors; @@ -1297,6 +1574,16 @@ static int cvbuff(CFILE *cfile, const char *format, va_list args) { return -1; } break; + case 'x': + if (print_expr_args(cfile, va_arg(args, const struct bfs_expr *)) != 0) { + return -1; + } + break; + case 'X': + if (print_expr_name(cfile, va_arg(args, const struct bfs_expr *)) != 0) { + return -1; + } + break; default: goto invalid; @@ -1389,7 +1676,7 @@ int cvfprintf(CFILE *cfile, const char *format, va_list args) { } } - dstresize(&cfile->buffer, 0); + dstrshrink(cfile->buffer, 0); return ret; } diff --git a/src/color.h b/src/color.h index 38f5ad7..d5e437c 100644 --- a/src/color.h +++ b/src/color.h @@ -54,11 +54,11 @@ typedef struct CFILE { /** * Wrap an existing file into a colored stream. * - * @param file + * @file * The underlying file. - * @param colors + * @colors * The color table to use if file is a TTY. - * @param close + * @close * Whether to close the underlying stream when this stream is closed. * @return * A colored wrapper around file. @@ -68,7 +68,7 @@ CFILE *cfwrap(FILE *file, const struct colors *colors, bool close); /** * Close a colored file. * - * @param cfile + * @cfile * The colored file to close. * @return * 0 on success, -1 on failure. @@ -78,9 +78,9 @@ int cfclose(CFILE *cfile); /** * Colored, formatted output. * - * @param cfile + * @cfile * The colored stream to print to. - * @param format + * @format * A printf()-style format string, supporting these format specifiers: * * %c: A single character @@ -95,19 +95,21 @@ int cfclose(CFILE *cfile); * %pL: A colored link target, from a const struct BFTW * argument * %pe: Dump a const struct bfs_expr *, for debugging. * %pE: Dump a const struct bfs_expr * in verbose form, for debugging. + * %px: Print a const struct bfs_expr * with syntax highlighting. + * %pX: Print the name of a const struct bfs_expr *, without arguments. * %%: A literal '%' * ${cc}: Change the color to 'cc' * $$: A literal '$' * @return * 0 on success, -1 on failure. */ -_printf(2, 3) +[[_printf(2, 3)]] int cfprintf(CFILE *cfile, const char *format, ...); /** * cfprintf() variant that takes a va_list. */ -_printf(2, 0) +[[_printf(2, 0)]] int cvfprintf(CFILE *cfile, const char *format, va_list args); /** @@ -24,20 +24,6 @@ #include <time.h> #include <unistd.h> -/** Get the initial value for ctx->threads (-j). */ -static int bfs_nproc(void) { - long nproc = xsysconf(_SC_NPROCESSORS_ONLN); - - if (nproc < 1) { - nproc = 1; - } else if (nproc > 8) { - // Not much speedup after 8 threads - nproc = 8; - } - - return nproc; -} - struct bfs_ctx *bfs_ctx_new(void) { struct bfs_ctx *ctx = ZALLOC(struct bfs_ctx); if (!ctx) { @@ -50,9 +36,14 @@ struct bfs_ctx *bfs_ctx_new(void) { ctx->maxdepth = INT_MAX; ctx->flags = BFTW_RECOVER; ctx->strategy = BFTW_BFS; - ctx->threads = bfs_nproc(); ctx->optlevel = 3; + ctx->threads = nproc(); + if (ctx->threads > 8) { + // Not much speedup after 8 threads + ctx->threads = 8; + } + trie_init(&ctx->files); ctx->umask = umask(0); @@ -295,6 +286,7 @@ int bfs_ctx_free(struct bfs_ctx *ctx) { } free(ctx->paths); + free(ctx->kinds); free(ctx->argv); free(ctx); } @@ -29,6 +29,8 @@ struct bfs_ctx { size_t argc; /** The unparsed command line arguments. */ char **argv; + /** The argument token kinds. */ + enum bfs_kind *kinds; /** The root paths. */ const char **paths; @@ -129,7 +131,7 @@ struct bfs_ctx *bfs_ctx_new(void); /** * Get the mount table. * - * @param ctx + * @ctx * The bfs context. * @return * The cached mount table, or NULL on failure. @@ -139,11 +141,11 @@ const struct bfs_mtab *bfs_ctx_mtab(const struct bfs_ctx *ctx); /** * Deduplicate an opened file. * - * @param ctx + * @ctx * The bfs context. - * @param cfile + * @cfile * The opened file. - * @param path + * @path * The path to the opened file (or NULL for standard streams). * @return * If the same file was opened previously, that file is returned. If cfile is a new file, @@ -154,7 +156,7 @@ struct CFILE *bfs_ctx_dedup(struct bfs_ctx *ctx, struct CFILE *cfile, const char /** * Flush any caches for consistency with external processes. * - * @param ctx + * @ctx * The bfs context. */ void bfs_ctx_flush(const struct bfs_ctx *ctx); @@ -162,9 +164,9 @@ void bfs_ctx_flush(const struct bfs_ctx *ctx); /** * Dump the parsed command line. * - * @param ctx + * @ctx * The bfs context. - * @param flag + * @flag * The -D flag that triggered the dump. */ void bfs_ctx_dump(const struct bfs_ctx *ctx, enum debug_flags flag); @@ -172,7 +174,7 @@ void bfs_ctx_dump(const struct bfs_ctx *ctx, enum debug_flags flag); /** * Free a bfs context. * - * @param ctx + * @ctx * The context to free. * @return * 0 on success, -1 if any errors occurred. @@ -14,27 +14,30 @@ #include <stdarg.h> #include <stdio.h> #include <stdlib.h> - -/** 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"); -} - -void bfs_diagf(const struct bfs_loc *loc, const char *format, ...) { +#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 veprintf(...) vdprintf(STDERR_FILENO, __VA_ARGS__) +#else +# define veprintf(...) vfprintf(stderr, __VA_ARGS__) +#endif + +void bfs_diagf(const char *format, ...) { va_list args; va_start(args, format); - bfs_vdiagf(loc, format, args); + veprintf(format, args); va_end(args); } -_noreturn -void bfs_abortf(const struct bfs_loc *loc, const char *format, ...) { +[[_noreturn]] +void bfs_abortf(const char *format, ...) { va_list args; va_start(args, format); - bfs_vdiagf(loc, format, args); + veprintf(format, args); va_end(args); abort(); @@ -14,69 +14,61 @@ #include <stdarg.h> /** - * A source code location. + * Wrap a diagnostic format string so it looks like + * + * bfs: func@src/file.c:0: Message */ -struct bfs_loc { - const char *file; - int line; - const char *func; -}; - -#define BFS_LOC_INIT { .file = __FILE__, .line = __LINE__, .func = __func__ } +// Use (format) ? "..." : "" so the format string is required +#define BFS_DIAG_FORMAT_(format) \ + ((format) ? "%s: %s@%s:%d: " format "%s" : "") /** - * Get the current source code location. + * Add arguments to match a BFS_DIAG_FORMAT string. */ -#if __STDC_VERSION__ >= C23 -# define bfs_location() (&(static const struct bfs_loc)BFS_LOC_INIT) -#else -# define bfs_location() (&(const struct bfs_loc)BFS_LOC_INIT) -#endif +#define BFS_DIAG_ARGS_(...) \ + xgetprogname(), __func__, __FILE__, __LINE__, __VA_ARGS__ __VA_OPT__(,) "\n" /** - * Print a low-level diagnostic message to standard error, formatted like - * - * bfs: func@src/file.c:0: Message + * Print a low-level diagnostic message to standard error. */ -_printf(2, 3) -void bfs_diagf(const struct bfs_loc *loc, const char *format, ...); +[[_printf(1, 2)]] +void bfs_diagf(const char *format, ...); /** * Unconditional diagnostic message. */ -#define bfs_diag(...) bfs_diagf(bfs_location(), __VA_ARGS__) +#define bfs_diag(format, ...) \ + bfs_diagf(BFS_DIAG_FORMAT_(format), BFS_DIAG_ARGS_(__VA_ARGS__)) /** * Print a diagnostic message including the last error. */ -#define bfs_ediag(...) \ - bfs_ediag_("" __VA_ARGS__, errstr()) - -#define bfs_ediag_(format, ...) \ - bfs_diag(sizeof(format) > 1 ? format ": %s" : "%s", __VA_ARGS__) +#define bfs_ediag(format, ...) \ + BFS_VA_IF(format) \ + (bfs_diag(format ": %s", __VA_ARGS__ __VA_OPT__(,) errstr())) \ + (bfs_diag("%s", errstr())) /** * Print a message to standard error and abort. */ -_cold -_printf(2, 3) -_noreturn -void bfs_abortf(const struct bfs_loc *loc, const char *format, ...); +[[_cold]] +[[_printf(1, 2)]] +[[_noreturn]] +void bfs_abortf(const char *format, ...); /** * Unconditional abort with a message. */ -#define bfs_abort(...) \ - bfs_abortf(bfs_location(), __VA_ARGS__) +#define bfs_abort(format, ...) \ + bfs_abortf(BFS_DIAG_FORMAT_(format), BFS_DIAG_ARGS_(__VA_ARGS__)) /** * Abort with a message including the last error. */ -#define bfs_eabort(...) \ - bfs_eabort_("" __VA_ARGS__, errstr()) - -#define bfs_eabort_(format, ...) \ - bfs_abort(sizeof(format) > 1 ? format ": %s" : "%s", __VA_ARGS__) +#define bfs_eabort(format, ...) \ + BFS_VA_IF(__VA_ARGS__) \ + (bfs_abort(format ": %s", __VA_ARGS__ __VA_OPT__(,) errstr())) \ + (bfs_abort("%s", errstr())) /** * Abort in debug builds; no-op in release builds. @@ -92,28 +84,18 @@ void bfs_abortf(const struct bfs_loc *loc, const char *format, ...); /** * Unconditional assert. */ -#define bfs_verify(...) \ - bfs_verify_(#__VA_ARGS__, __VA_ARGS__, "", "") - -#define bfs_verify_(str, cond, format, ...) \ - ((cond) ? (void)0 : bfs_abort( \ - sizeof(format) > 1 \ - ? "%.0s" format "%s%s" \ - : "Assertion failed: `%s`%s", \ - str, __VA_ARGS__)) +#define bfs_verify(cond, ...) \ + ((cond) ? (void)0 : BFS_VA_IF(__VA_ARGS__) \ + (bfs_abort(__VA_ARGS__)) \ + (bfs_abort("Assertion failed: `%s`", #cond))) /** * Unconditional assert, including the last error. */ -#define bfs_everify(...) \ - bfs_everify_(#__VA_ARGS__, __VA_ARGS__, "", errstr()) - -#define bfs_everify_(str, cond, format, ...) \ - ((cond) ? (void)0 : bfs_abort( \ - sizeof(format) > 1 \ - ? "%.0s" format "%s: %s" \ - : "Assertion failed: `%s`: %s", \ - str, __VA_ARGS__)) +#define bfs_everify(cond, ...) \ + ((cond) ? (void)0 : BFS_VA_IF(__VA_ARGS__) \ + (bfs_eabort(__VA_ARGS__)) \ + (bfs_eabort("Assertion failed: `%s`", #cond))) /** * Assert in debug builds; no-op in release builds. @@ -159,14 +141,14 @@ const char *debug_flag_name(enum debug_flags flag); /** * Like perror(), but decorated like bfs_error(). */ -_cold +[[_cold]] void bfs_perror(const struct bfs_ctx *ctx, const char *str); /** * Shorthand for printing error messages. */ -_cold -_printf(2, 3) +[[_cold]] +[[_printf(2, 3)]] void bfs_error(const struct bfs_ctx *ctx, const char *format, ...); /** @@ -174,8 +156,8 @@ void bfs_error(const struct bfs_ctx *ctx, const char *format, ...); * * @return Whether a warning was printed. */ -_cold -_printf(2, 3) +[[_cold]] +[[_printf(2, 3)]] bool bfs_warning(const struct bfs_ctx *ctx, const char *format, ...); /** @@ -183,71 +165,71 @@ bool bfs_warning(const struct bfs_ctx *ctx, const char *format, ...); * * @return Whether a debug message was printed. */ -_cold -_printf(3, 4) +[[_cold]] +[[_printf(3, 4)]] bool bfs_debug(const struct bfs_ctx *ctx, enum debug_flags flag, const char *format, ...); /** * bfs_error() variant that takes a va_list. */ -_cold -_printf(2, 0) +[[_cold]] +[[_printf(2, 0)]] void bfs_verror(const struct bfs_ctx *ctx, const char *format, va_list args); /** * bfs_warning() variant that takes a va_list. */ -_cold -_printf(2, 0) +[[_cold]] +[[_printf(2, 0)]] bool bfs_vwarning(const struct bfs_ctx *ctx, const char *format, va_list args); /** * bfs_debug() variant that takes a va_list. */ -_cold -_printf(3, 0) +[[_cold]] +[[_printf(3, 0)]] bool bfs_vdebug(const struct bfs_ctx *ctx, enum debug_flags flag, const char *format, va_list args); /** * Print the error message prefix. */ -_cold +[[_cold]] void bfs_error_prefix(const struct bfs_ctx *ctx); /** * Print the warning message prefix. */ -_cold +[[_cold]] bool bfs_warning_prefix(const struct bfs_ctx *ctx); /** * Print the debug message prefix. */ -_cold +[[_cold]] bool bfs_debug_prefix(const struct bfs_ctx *ctx, enum debug_flags flag); /** * Highlight parts of the command line in an error message. */ -_cold +[[_cold]] void bfs_argv_error(const struct bfs_ctx *ctx, const bool args[]); /** * Highlight parts of an expression in an error message. */ -_cold +[[_cold]] void bfs_expr_error(const struct bfs_ctx *ctx, const struct bfs_expr *expr); /** * Highlight parts of the command line in a warning message. */ -_cold +[[_cold]] bool bfs_argv_warning(const struct bfs_ctx *ctx, const bool args[]); /** * Highlight parts of an expression in a warning message. */ -_cold +[[_cold]] bool bfs_expr_warning(const struct bfs_ctx *ctx, const struct bfs_expr *expr); #endif // BFS_DIAG_H @@ -21,6 +21,8 @@ # define BFS_USE_GETDENTS true # elif __linux__ || __FreeBSD__ # define BFS_USE_GETDENTS (BFS_HAS_GETDENTS || BFS_HAS_GETDENTS64 | BFS_HAS_GETDENTS64_SYSCALL) +# else +# define BFS_USE_GETDENTS false # endif #endif @@ -87,7 +89,7 @@ struct arena; /** * Initialize an arena for directories. * - * @param arena + * @arena * The arena to initialize. */ void bfs_dir_arena(struct arena *arena); @@ -105,14 +107,14 @@ enum bfs_dir_flags { /** * Open a directory. * - * @param dir + * @dir * The allocated directory. - * @param at_fd + * @at_fd * The base directory for path resolution. - * @param at_path + * @at_path * The path of the directory to open, relative to at_fd. Pass NULL to * open at_fd itself. - * @param flags + * @flags * Flags that control which directory entries are listed. * @return * 0 on success, or -1 on failure. @@ -127,7 +129,7 @@ int bfs_dirfd(const struct bfs_dir *dir); /** * Performs any I/O necessary for the next bfs_readdir() call. * - * @param dir + * @dir * The directory to poll. * @return * 1 on success, 0 on EOF, or -1 on failure. @@ -137,9 +139,9 @@ int bfs_polldir(struct bfs_dir *dir); /** * Read a directory entry. * - * @param dir + * @dir * The directory to read. - * @param[out] dirent + * @dirent[out] * The directory entry to populate. * @return * 1 on success, 0 on EOF, or -1 on failure. @@ -165,7 +167,7 @@ int bfs_closedir(struct bfs_dir *dir); /** * Detach the file descriptor from an open directory. * - * @param dir + * @dir * The directory to detach. * @return * The file descriptor of the directory. diff --git a/src/dstring.c b/src/dstring.c index af499fd..5addb77 100644 --- a/src/dstring.c +++ b/src/dstring.c @@ -23,6 +23,7 @@ struct dstring { /** Length of the string, *excluding* the terminating NUL. */ size_t len; /** The string itself. */ + [[_counted_by(cap)]] alignas(dchar) char str[]; }; @@ -46,6 +47,13 @@ static dchar *dstrdata(struct dstring *header) { return (char *)header + DSTR_OFFSET; } +/** Set the length of a dynamic string. */ +static void dstrsetlen(struct dstring *header, size_t len) { + bfs_assert(len < header->cap); + header->len = len; + header->str[len] = '\0'; +} + /** Allocate a dstring with the given contents. */ static dchar *dstralloc_impl(size_t cap, size_t len, const char *str) { // Avoid reallocations for small strings @@ -59,11 +67,10 @@ static dchar *dstralloc_impl(size_t cap, size_t len, const char *str) { } header->cap = cap; - header->len = len; + dstrsetlen(header, len); - char *ret = dstrdata(header); + dchar *ret = dstrdata(header); memcpy(ret, str, len); - ret[len] = '\0'; return ret; } @@ -121,11 +128,16 @@ int dstresize(dchar **dstr, size_t len) { } struct dstring *header = dstrheader(*dstr); - header->len = len; - header->str[len] = '\0'; + dstrsetlen(header, len); return 0; } +void dstrshrink(dchar *dstr, size_t len) { + struct dstring *header = dstrheader(dstr); + bfs_assert(len <= header->len); + dstrsetlen(header, len); +} + int dstrcat(dchar **dest, const char *src) { return dstrxcat(dest, src, strlen(src)); } diff --git a/src/dstring.h b/src/dstring.h index 79458e4..8765f6e 100644 --- a/src/dstring.h +++ b/src/dstring.h @@ -16,14 +16,14 @@ /** Marker type for dynamic strings. */ #if BFS_LINT && __clang__ -// Abuse __attribute__(aligned) to make a type that allows +// Abuse [[gnu::aligned]] to make a type that allows // // dchar * -> char * // // conversions, but warns (with Clang's -Walign-mismatch) on // // char * -> dchar * -typedef __attribute__((aligned(alignof(size_t)))) char dchar; +typedef char dchar [[gnu::aligned(alignof(size_t))]]; #else typedef char dchar; #endif @@ -31,7 +31,7 @@ typedef char dchar; /** * Free a dynamic string. * - * @param dstr + * @dstr * The string to free. */ void dstrfree(dchar *dstr); @@ -39,56 +39,56 @@ void dstrfree(dchar *dstr); /** * Allocate a dynamic string. * - * @param cap + * @cap * The initial capacity of the string. */ -_malloc(dstrfree, 1) +[[_malloc(dstrfree, 1)]] dchar *dstralloc(size_t cap); /** * Create a dynamic copy of a string. * - * @param str + * @str * The NUL-terminated string to copy. */ -_malloc(dstrfree, 1) +[[_malloc(dstrfree, 1)]] dchar *dstrdup(const char *str); /** * Create a length-limited dynamic copy of a string. * - * @param str + * @str * The string to copy. - * @param n + * @n * The maximum number of characters to copy from str. */ -_malloc(dstrfree, 1) +[[_malloc(dstrfree, 1)]] dchar *dstrndup(const char *str, size_t n); /** * Create a dynamic copy of a dynamic string. * - * @param dstr + * @dstr * The dynamic string to copy. */ -_malloc(dstrfree, 1) +[[_malloc(dstrfree, 1)]] dchar *dstrddup(const dchar *dstr); /** * Create an exact-sized dynamic copy of a string. * - * @param str + * @str * The string to copy. - * @param len + * @len * The length of the string, which may include internal NUL bytes. */ -_malloc(dstrfree, 1) +[[_malloc(dstrfree, 1)]] dchar *dstrxdup(const char *str, size_t len); /** * Get a dynamic string's length. * - * @param dstr + * @dstr * The string to measure. * @return * The length of dstr. @@ -98,9 +98,9 @@ size_t dstrlen(const dchar *dstr); /** * Reserve some capacity in a dynamic string. * - * @param dstr + * @dstr * The dynamic string to preallocate. - * @param cap + * @cap * The new capacity for the string. * @return * 0 on success, -1 on failure. @@ -110,219 +110,246 @@ int dstreserve(dchar **dstr, size_t cap); /** * Resize a dynamic string. * - * @param dstr + * @dstr * The dynamic string to resize. - * @param len + * @len * The new length for the dynamic string. * @return * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstresize(dchar **dstr, size_t len); /** + * Shrink a dynamic string. + * + * @dstr + * The dynamic string to shrink. + * @len + * The new length. Must not be greater than the current length. + */ +void dstrshrink(dchar *dstr, size_t len); + +/** * Append to a dynamic string. * - * @param dest + * @dest * The destination dynamic string. - * @param src + * @src * The string to append. * @return 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrcat(dchar **dest, const char *src); /** * Append to a dynamic string. * - * @param dest + * @dest * The destination dynamic string. - * @param src + * @src * The string to append. - * @param n + * @n * The maximum number of characters to take from src. * @return * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrncat(dchar **dest, const char *src, size_t n); /** * Append a dynamic string to another dynamic string. * - * @param dest + * @dest * The destination dynamic string. - * @param src + * @src * The dynamic string to append. * @return * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrdcat(dchar **dest, const dchar *src); /** * Append to a dynamic string. * - * @param dest + * @dest * The destination dynamic string. - * @param src + * @src * The string to append. - * @param len + * @len * The exact number of characters to take from src. * @return * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrxcat(dchar **dest, const char *src, size_t len); /** * Append a single character to a dynamic string. * - * @param str + * @str * The string to append to. - * @param c + * @c * The character to append. * @return * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrapp(dchar **str, char c); /** * Copy a string into a dynamic string. * - * @param dest + * @dest * The destination dynamic string. - * @param src + * @src * The string to copy. * @returns * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrcpy(dchar **dest, const char *str); /** * Copy a dynamic string into another one. * - * @param dest + * @dest * The destination dynamic string. - * @param src + * @src * The dynamic string to copy. * @returns * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrdcpy(dchar **dest, const dchar *str); /** * Copy a string into a dynamic string. * - * @param dest + * @dest * The destination dynamic string. - * @param src + * @src * The dynamic string to copy. - * @param n + * @n * The maximum number of characters to take from src. * @returns * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrncpy(dchar **dest, const char *str, size_t n); /** * Copy a string into a dynamic string. * - * @param dest + * @dest * The destination dynamic string. - * @param src + * @src * The dynamic string to copy. - * @param len + * @len * The exact number of characters to take from src. * @returns * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrxcpy(dchar **dest, const char *str, size_t len); /** * Create a dynamic string from a format string. * - * @param format + * @format * The format string to fill in. - * @param ... + * @... * Any arguments for the format string. * @return * The created string, or NULL on failure. */ -_printf(1, 2) +[[_nodiscard]] +[[_printf(1, 2)]] dchar *dstrprintf(const char *format, ...); /** * Create a dynamic string from a format string and a va_list. * - * @param format + * @format * The format string to fill in. - * @param args + * @args * The arguments for the format string. * @return * The created string, or NULL on failure. */ -_printf(1, 0) +[[_nodiscard]] +[[_printf(1, 0)]] dchar *dstrvprintf(const char *format, va_list args); /** * Format some text onto the end of a dynamic string. * - * @param str + * @str * The destination dynamic string. - * @param format + * @format * The format string to fill in. - * @param ... + * @... * Any arguments for the format string. * @return * 0 on success, -1 on failure. */ -_printf(2, 3) +[[_nodiscard]] +[[_printf(2, 3)]] int dstrcatf(dchar **str, const char *format, ...); /** * Format some text from a va_list onto the end of a dynamic string. * - * @param str + * @str * The destination dynamic string. - * @param format + * @format * The format string to fill in. - * @param args + * @args * The arguments for the format string. * @return * 0 on success, -1 on failure. */ -_printf(2, 0) +[[_nodiscard]] +[[_printf(2, 0)]] int dstrvcatf(dchar **str, const char *format, va_list args); /** * Concatenate while shell-escaping. * - * @param dest + * @dest * The destination dynamic string. - * @param str + * @str * The string to escape. - * @param flags + * @flags * Flags for wordesc(). * @return * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrescat(dchar **dest, const char *str, enum wesc_flags flags); /** * Concatenate while shell-escaping. * - * @param dest + * @dest * The destination dynamic string. - * @param str + * @str * The string to escape. - * @param n + * @n * The maximum length of the string. - * @param flags + * @flags * Flags for wordesc(). * @return * 0 on success, -1 on failure. */ +[[_nodiscard]] int dstrnescat(dchar **dest, const char *str, size_t n, enum wesc_flags flags); /** * Repeat a string n times. */ +[[_nodiscard]] dchar *dstrepeat(const char *str, size_t n); #endif // BFS_DSTRING_H @@ -28,6 +28,7 @@ #include "stat.h" #include "trie.h" #include "xregex.h" +#include "xtime.h" #include <errno.h> #include <fcntl.h> @@ -42,6 +43,7 @@ #include <string.h> #include <strings.h> #include <sys/resource.h> +#include <sys/time.h> #include <sys/types.h> #include <time.h> #include <unistd.h> @@ -65,7 +67,7 @@ struct bfs_eval { /** * Print an error message. */ -_printf(2, 3) +[[_printf(2, 3)]] static void eval_error(struct bfs_eval *state, const char *format, ...) { const struct bfs_ctx *ctx = state->ctx; @@ -135,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) { @@ -258,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; } /** @@ -280,10 +279,10 @@ bool eval_time(const struct bfs_expr *expr, struct bfs_eval *state) { switch (expr->time_unit) { case BFS_DAYS: diff /= 60 * 24; - _fallthrough; + [[fallthrough]]; case BFS_MINUTES: diff /= 60; - _fallthrough; + [[fallthrough]]; case BFS_SECONDS: break; } @@ -409,7 +408,7 @@ static int eval_exec_finish(const struct bfs_expr *expr, const struct bfs_ctx *c if (expr->eval_fn == eval_exec) { if (bfs_exec_finish(expr->exec) != 0) { if (errno != 0) { - bfs_error(ctx, "%s %s: %s.\n", expr->argv[0], expr->argv[1], errstr()); + bfs_error(ctx, "${blu}%pq${rs} ${bld}%pq${rs}: %s.\n", expr->argv[0], expr->argv[1], errstr()); } ret = -1; } @@ -430,7 +429,7 @@ static int eval_exec_finish(const struct bfs_expr *expr, const struct bfs_ctx *c bool eval_exec(const struct bfs_expr *expr, struct bfs_eval *state) { bool ret = bfs_exec(expr->exec, state->ftwbuf) == 0; if (errno != 0) { - eval_error(state, "%s %s: %s.\n", expr->argv[0], expr->argv[1], errstr()); + eval_error(state, "${blu}%pq${rs} ${bld}%pq${rs}: %s.\n", expr->argv[0], expr->argv[1], errstr()); } return ret; } @@ -701,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. */ @@ -757,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; } @@ -1045,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) { @@ -1077,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); } } @@ -1146,20 +1142,7 @@ bool eval_comma(const struct bfs_expr *expr, struct bfs_eval *state) { } /** Update the status bar. */ -static void eval_status(struct bfs_eval *state, struct bfs_bar *bar, struct timespec *last_status, size_t count) { - struct timespec now; - if (eval_gettime(state, &now) == 0) { - struct timespec elapsed = {0}; - timespec_elapsed(&elapsed, last_status, &now); - - // Update every 0.1s - if (elapsed.tv_sec > 0 || elapsed.tv_nsec >= 100000000L) { - *last_status = now; - } else { - return; - } - } - +static void eval_status(struct bfs_eval *state, struct bfs_bar *bar, size_t count) { size_t width = bfs_bar_width(bar); if (width < 3) { return; @@ -1175,7 +1158,7 @@ static void eval_status(struct bfs_eval *state, struct bfs_bar *bar, struct time size_t rhslen = xstrwidth(rhs); if (3 + rhslen > width) { - dstresize(&rhs, 0); + dstrshrink(rhs, 0); rhslen = 0; } @@ -1219,7 +1202,7 @@ static void eval_status(struct bfs_eval *state, struct bfs_bar *bar, struct time } pathwidth += cwidth; } - dstresize(&status, lhslen); + dstrshrink(status, lhslen); if (dstrcat(&status, "...") != 0) { goto out; @@ -1389,9 +1372,13 @@ struct callback_args { /** The status bar. */ struct bfs_bar *bar; - /** The time of the last status update. */ - struct timespec last_status; - /** Flag set by SIGINFO hook. */ + /** The SIGALRM hook. */ + struct sighook *alrm_hook; + /** The interval timer. */ + struct timer *timer; + /** Flag set by SIGALRM. */ + atomic bool alrm_flag; + /** Flag set by SIGINFO. */ atomic bool info_flag; /** The number of files visited so far. */ @@ -1406,6 +1393,64 @@ struct callback_args { int ret; }; +/** Update the status bar in response to SIGALRM. */ +static void eval_sigalrm(int sig, siginfo_t *info, void *ptr) { + struct callback_args *args = ptr; + store(&args->alrm_flag, true, relaxed); +} + +/** Show/hide the bar in response to SIGINFO. */ +static void eval_siginfo(int sig, siginfo_t *info, void *ptr) { + struct callback_args *args = ptr; + store(&args->info_flag, true, relaxed); +} + +/** Show the status bar. */ +static void eval_show_bar(struct callback_args *args) { + args->alrm_hook = sighook(SIGALRM, eval_sigalrm, args, SH_CONTINUE); + if (!args->alrm_hook) { + goto fail; + } + + args->bar = bfs_bar_show(); + if (!args->bar) { + goto fail; + } + + // Update the bar every 0.1s + struct timespec ival = { .tv_nsec = 100 * 1000 * 1000 }; + args->timer = xtimer_start(&ival); + if (!args->timer) { + goto fail; + } + + // Update the bar immediately + store(&args->alrm_flag, true, relaxed); + + return; + +fail: + bfs_warning(args->ctx, "Couldn't show status bar: %s.\n\n", errstr()); + + bfs_bar_hide(args->bar); + args->bar = NULL; + + sigunhook(args->alrm_hook); + args->alrm_hook = NULL; +} + +/** Hide the status bar. */ +static void eval_hide_bar(struct callback_args *args) { + xtimer_stop(args->timer); + args->timer = NULL; + + sigunhook(args->alrm_hook); + args->alrm_hook = NULL; + + bfs_bar_hide(args->bar); + args->bar = NULL; +} + /** * bftw() callback. */ @@ -1426,18 +1471,14 @@ static enum bftw_action eval_callback(const struct BFTW *ftwbuf, void *ptr) { // Check whether SIGINFO was delivered and show/hide the bar if (exchange(&args->info_flag, false, relaxed)) { if (args->bar) { - bfs_bar_hide(args->bar); - args->bar = NULL; + eval_hide_bar(args); } else { - args->bar = bfs_bar_show(); - if (!args->bar) { - bfs_warning(ctx, "Couldn't show status bar: %s.\n", errstr()); - } + eval_show_bar(args); } } - if (args->bar) { - eval_status(&state, args->bar, &args->last_status, args->count); + if (exchange(&args->alrm_flag, false, relaxed)) { + eval_status(&state, args->bar, args->count); } if (ftwbuf->type == BFS_ERROR) { @@ -1509,12 +1550,6 @@ done: return state.action; } -/** Show/hide the bar in response to SIGINFO. */ -static void eval_siginfo(int sig, siginfo_t *info, void *ptr) { - struct callback_args *args = ptr; - store(&args->info_flag, true, relaxed); -} - /** Raise RLIMIT_NOFILE if possible, and return the new limit. */ static int raise_fdlimit(struct bfs_ctx *ctx) { rlim_t cur = ctx->orig_nofile.rlim_cur; @@ -1671,10 +1706,7 @@ int bfs_eval(struct bfs_ctx *ctx) { }; if (ctx->status) { - args.bar = bfs_bar_show(); - if (!args.bar) { - bfs_warning(ctx, "Couldn't show status bar: %s.\n\n", errstr()); - } + eval_show_bar(&args); } #ifdef SIGINFO @@ -1752,7 +1784,9 @@ int bfs_eval(struct bfs_ctx *ctx) { } sigunhook(info_hook); - bfs_bar_hide(args.bar); + if (args.bar) { + eval_hide_bar(&args); + } if (ctx->ignore_errors && args.nerrors > 0) { bfs_warning(ctx, "Suppressed errors: %zu\n", args.nerrors); @@ -20,9 +20,9 @@ struct bfs_eval; /** * Expression evaluation function. * - * @param expr + * @expr * The current expression. - * @param state + * @state * The current evaluation state. * @return * The result of the test. @@ -32,7 +32,7 @@ typedef bool bfs_eval_fn(const struct bfs_expr *expr, struct bfs_eval *state); /** * Evaluate the command line. * - * @param ctx + * @ctx * The bfs context to evaluate. * @return * EXIT_SUCCESS on success, otherwise on failure. @@ -24,7 +24,7 @@ #include <unistd.h> /** Print some debugging info. */ -_printf(2, 3) +[[_printf(2, 3)]] static void bfs_exec_debug(const struct bfs_exec *execbuf, const char *format, ...) { const struct bfs_ctx *ctx = execbuf->ctx; @@ -67,11 +67,11 @@ struct bfs_exec { /** * Parse an exec action. * - * @param argv + * @argv * The (bfs) command line argument to parse. - * @param flags + * @flags * Any flags for this exec action. - * @param ctx + * @ctx * The bfs context. * @return * The parsed exec action, or NULL on failure. @@ -81,9 +81,9 @@ struct bfs_exec *bfs_exec_parse(const struct bfs_ctx *ctx, char **argv, enum bfs /** * Execute the command for a file. * - * @param execbuf + * @execbuf * The parsed exec action. - * @param ftwbuf + * @ftwbuf * The bftw() data for the current file. * @return 0 if the command succeeded, -1 if it failed. If the command could * be executed, -1 is returned, and errno will be non-zero. For @@ -94,7 +94,7 @@ int bfs_exec(struct bfs_exec *execbuf, const struct BFTW *ftwbuf); /** * Finish executing any commands. * - * @param execbuf + * @execbuf * The parsed exec action. * @return 0 on success, -1 if any errors were encountered. */ @@ -68,8 +68,7 @@ void bfs_expr_append(struct bfs_expr *expr, struct bfs_expr *child) { } void bfs_expr_extend(struct bfs_expr *expr, struct bfs_exprs *children) { - while (!SLIST_EMPTY(children)) { - struct bfs_expr *child = SLIST_POP(children); + drain_slist (struct bfs_expr, child, children) { bfs_expr_append(expr, child); } } @@ -19,6 +19,9 @@ * Argument/token/expression kinds. */ enum bfs_kind { + /** A regular argument. */ + BFS_ARG, + /** A flag (-H, -L, etc.). */ BFS_FLAG, @@ -146,7 +149,7 @@ struct bfs_expr { /** Total time spent running this predicate. */ struct timespec elapsed; - /** Auxilliary data for the evaluation function. */ + /** Auxiliary data for the evaluation function. */ union { /** Child expressions. */ struct bfs_exprs children; diff --git a/src/fsade.c b/src/fsade.c index 30b3018..3d4c8ba 100644 --- a/src/fsade.c +++ b/src/fsade.c @@ -36,11 +36,18 @@ # define BFS_USE_XATTR true #endif +#ifndef BFS_USE_EXTATTR +# define BFS_USE_EXTATTR false +#endif +#ifndef BFS_USE_XATTR +# define BFS_USE_XATTR false +#endif + /** * Many of the APIs used here don't have *at() variants, but we can try to * emulate something similar if /proc/self/fd is available. */ -_maybe_unused +[[_maybe_unused]] static const char *fake_at(const struct BFTW *ftwbuf) { static atomic int proc_works = -1; @@ -74,7 +81,7 @@ fail: return ftwbuf->path; } -_maybe_unused +[[_maybe_unused]] static void free_fake_at(const struct BFTW *ftwbuf, const char *path) { if (path != ftwbuf->path) { dstrfree((dchar *)path); @@ -84,7 +91,7 @@ static void free_fake_at(const struct BFTW *ftwbuf, const char *path) { /** * Check if an error was caused by the absence of support or data for a feature. */ -_maybe_unused +[[_maybe_unused]] static bool is_absence_error(int error) { // If the OS doesn't support the feature, it's obviously not enabled for // any files @@ -164,7 +171,7 @@ static int bfs_acl_entry(acl_t acl, int which, acl_entry_t *entry) { } /** Unified interface for acl_get_tag_type(). */ -_maybe_unused +[[_maybe_unused]] static int bfs_acl_tag_type(acl_entry_t entry, acl_tag_t *tag) { #if BFS_HAS_ACL_GET_TAG_TYPE return acl_get_tag_type(entry, tag); diff --git a/src/fsade.h b/src/fsade.h index 77cf82a..fbe02d8 100644 --- a/src/fsade.h +++ b/src/fsade.h @@ -19,6 +19,8 @@ #if __has_include(<sys/extattr.h>) || __has_include(<sys/xattr.h>) # define BFS_CAN_CHECK_XATTRS true +#else +# define BFS_CAN_CHECK_XATTRS false #endif struct BFTW; @@ -26,7 +28,7 @@ struct BFTW; /** * Check if a file has a non-trivial Access Control List. * - * @param ftwbuf + * @ftwbuf * The file to check. * @return * 1 if it does, 0 if it doesn't, or -1 if an error occurred. @@ -36,7 +38,7 @@ int bfs_check_acl(const struct BFTW *ftwbuf); /** * Check if a file has a non-trivial capability set. * - * @param ftwbuf + * @ftwbuf * The file to check. * @return * 1 if it does, 0 if it doesn't, or -1 if an error occurred. @@ -46,7 +48,7 @@ int bfs_check_capabilities(const struct BFTW *ftwbuf); /** * Check if a file has any extended attributes set. * - * @param ftwbuf + * @ftwbuf * The file to check. * @return * 1 if it does, 0 if it doesn't, or -1 if an error occurred. @@ -56,9 +58,9 @@ int bfs_check_xattrs(const struct BFTW *ftwbuf); /** * Check if a file has an extended attribute with the given name. * - * @param ftwbuf + * @ftwbuf * The file to check. - * @param name + * @name * The name of the xattr to check. * @return * 1 if it does, 0 if it doesn't, or -1 if an error occurred. @@ -68,7 +70,7 @@ int bfs_check_xattr_named(const struct BFTW *ftwbuf, const char *name); /** * Get a file's SELinux context * - * @param ftwbuf + * @ftwbuf * The file to check. * @return * The file's SELinux context, or NULL on failure. @@ -136,6 +136,7 @@ #include <stdint.h> #include <stdlib.h> #include <sys/stat.h> +#include <unistd.h> #if BFS_WITH_LIBURING # include <liburing.h> @@ -202,6 +203,7 @@ struct ioqq { cache_align atomic size_t tail; /** The circular buffer itself. */ + // [[_counted_by(slot_mask + 1)]] cache_align ioq_slot slots[]; }; @@ -259,17 +261,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 +[[_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; } @@ -294,7 +324,7 @@ done: } /** Wake up any threads waiting on a slot. */ -_noinline +[[_noinline]] static void ioq_slot_wake(struct ioqq *ioqq, ioq_slot *slot) { struct ioq_monitor *monitor = ioq_slot_monitor(ioqq, slot); @@ -355,6 +385,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 +447,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 +462,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,14 +581,20 @@ 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. */ + [[_counted_by(nthreads)]] struct ioq_thread threads[]; }; @@ -532,6 +616,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 +672,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 +836,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 +845,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 +861,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 +889,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 +943,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); } - 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; + } + + 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 +974,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 +984,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 +1018,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 aggressively with completion events + ioq_ring_probe_flags(¶ms, IORING_SETUP_DEFER_TASKRUN); +# endif + } +#endif } // Use a page for each SQE ring @@ -878,6 +1080,7 @@ static int ioq_ring_init(struct ioq *ioq, struct ioq_thread *thread) { return -1; } +#if BFS_HAS_IO_URING_MAX_WORKERS // Limit the number of io_uring workers unsigned int values[] = { ioq->nthreads, // [IO_WQ_BOUND] @@ -886,6 +1089,8 @@ static int ioq_ring_init(struct ioq *ioq, struct ioq_thread *thread) { io_uring_register_iowq_max_workers(&thread->ring, values); #endif +#endif // BFS_WITH_LIBURING + return 0; } @@ -899,7 +1104,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); @@ -909,6 +1115,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; } @@ -943,7 +1154,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; } @@ -985,6 +1196,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) { @@ -993,7 +1216,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; } @@ -1009,7 +1232,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; } @@ -1021,7 +1244,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; } @@ -1045,16 +1268,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) { @@ -1072,7 +1302,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; @@ -83,9 +93,9 @@ struct ioq_ent { /** * Create an I/O queue. * - * @param depth + * @depth * The maximum depth of the queue. - * @param nthreads + * @nthreads * The maximum number of background threads. * @return * The new I/O queue, or NULL on failure. @@ -98,13 +108,27 @@ 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(). * - * @param ioq + * @ioq * The I/O queue. - * @param fd + * @fd * The fd to close. - * @param ptr + * @ptr * An arbitrary pointer to associate with the request. * @return * 0 on success, or -1 on failure. @@ -114,17 +138,17 @@ int ioq_close(struct ioq *ioq, int fd, void *ptr); /** * Asynchronous bfs_opendir(). * - * @param ioq + * @ioq * The I/O queue. - * @param dir + * @dir * The allocated directory. - * @param dfd + * @dfd * The base file descriptor. - * @param path + * @path * The path to open, relative to dfd. - * @param flags + * @flags * Flags that control which directory entries are listed. - * @param ptr + * @ptr * An arbitrary pointer to associate with the request. * @return * 0 on success, or -1 on failure. @@ -134,11 +158,11 @@ int ioq_opendir(struct ioq *ioq, struct bfs_dir *dir, int dfd, const char *path, /** * Asynchronous bfs_closedir(). * - * @param ioq + * @ioq * The I/O queue. - * @param dir + * @dir * The directory to close. - * @param ptr + * @ptr * An arbitrary pointer to associate with the request. * @return * 0 on success, or -1 on failure. @@ -148,17 +172,17 @@ int ioq_closedir(struct ioq *ioq, struct bfs_dir *dir, void *ptr); /** * Asynchronous bfs_stat(). * - * @param ioq + * @ioq * The I/O queue. - * @param dfd + * @dfd * The base file descriptor. - * @param path + * @path * The path to stat, relative to dfd. - * @param flags + * @flags * Flags that affect the lookup. - * @param buf + * @buf * A place to store the stat buffer, if successful. - * @param ptr + * @ptr * An arbitrary pointer to associate with the request. * @return * 0 on success, or -1 on failure. @@ -166,9 +190,14 @@ 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. * - * @param ioq + * @ioq * The I/O queue. * @return * The next response, or NULL. @@ -178,9 +207,9 @@ struct ioq_ent *ioq_pop(struct ioq *ioq, bool block); /** * Free a queue entry. * - * @param ioq + * @ioq * The I/O queue. - * @param ent + * @ent * The entry to free. */ void ioq_free(struct ioq *ioq, struct ioq_ent *ent); @@ -82,6 +82,7 @@ #ifndef BFS_LIST_H #define BFS_LIST_H +#include "bfs.h" #include "diag.h" #include <stddef.h> @@ -90,7 +91,7 @@ /** * Initialize a singly-linked list. * - * @param list + * @list * The list to initialize. * * --- @@ -117,80 +118,25 @@ /** * Initialize a singly-linked list item. * - * @param item + * @item * The item to initialize. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. - * - * --- - * - * We play some tricks with variadic macros to handle the optional parameter: - * - * SLIST_ITEM_INIT(item) => item->next = NULL - * SLIST_ITEM_INIT(item, node) => item->node.next = NULL - * - * The first trick is that - * - * #define SLIST_ITEM_INIT(item, ...) - * - * won't work because both commas are required (until C23; see N3033). As a - * workaround, we dispatch to another macro and add a trailing comma. - * - * SLIST_ITEM_INIT(item) => SLIST_ITEM_INIT_(item, ) - * SLIST_ITEM_INIT(item, node) => SLIST_ITEM_INIT_(item, node, ) */ -#define SLIST_ITEM_INIT(...) \ - SLIST_ITEM_INIT_(__VA_ARGS__, ) +#define SLIST_ITEM_INIT(item, ...) \ + SLIST_ITEM_INIT_((item), LIST_NEXT_(__VA_ARGS__)) -/** - * Now we need a way to generate either ->next or ->node.next depending on - * whether the node parameter was passed. The approach is based on - * - * #define FOO(...) BAR(__VA_ARGS__, 1, 2, ) - * #define BAR(x, y, z, ...) z - * - * FOO(a) => 2 - * FOO(a, b) => 1 - * - * The LIST_NEXT_() macro uses this technique: - * - * LIST_NEXT_() => LIST_NODE_(next, ) - * LIST_NEXT_(node, ) => LIST_NODE_(next, node, ) - */ -#define LIST_NEXT_(...) \ - LIST_NODE_(next, __VA_ARGS__) +#define SLIST_ITEM_INIT_(item, next) \ + LIST_VOID_(item->next = NULL) /** - * LIST_NODE_() dispatches to yet another macro: + * Get the projection for an item's next pointer. * - * LIST_NODE_(next, ) => LIST_NODE__(next, , . , , ) - * LIST_NODE_(next, node, ) => LIST_NODE__(next, node, , . , , ) - */ -#define LIST_NODE_(dir, ...) \ - LIST_NODE__(dir, __VA_ARGS__, . , , ) - -/** - * And finally, LIST_NODE__() adds the node and the dot if necessary. - * - * dir node ignored dot - * v v v v - * LIST_NODE__(next, , . , , ) => next - * LIST_NODE__(next, node, , . , , ) => node . next - * ^ ^ ^ ^ - * dir node ignored dot + * LIST_NEXT_() => next + * LIST_NEXT_(node) => node.next */ -#define LIST_NODE__(dir, node, ignored, dot, ...) \ - node dot dir - -/** - * SLIST_ITEM_INIT_() uses LIST_NEXT_() to generate the right name for the list - * node, and finally delegates to the actual implementation. - */ -#define SLIST_ITEM_INIT_(item, ...) \ - SLIST_ITEM_INIT__((item), LIST_NEXT_(__VA_ARGS__)) - -#define SLIST_ITEM_INIT__(item, next) \ - LIST_VOID_(item->next = NULL) +#define LIST_NEXT_(node) \ + BFS_VA_IF(node)(node.next)(next) /** * Type-checking macro for singly-linked lists. @@ -201,7 +147,7 @@ /** * Get the head of a singly-linked list. * - * @param list + * @list * The list in question. * @return * The first item in the list. @@ -219,74 +165,58 @@ (!SLIST_HEAD(list)) /** - * Like container_of(), but using the head pointer instead of offsetof() since - * we don't have the type around. - */ -#define SLIST_CONTAINER_(tail, head, next) \ - (void *)((char *)tail - ((char *)&head->next - (char *)head)) - -/** * Get the tail of a singly-linked list. * - * @param list + * @list * The list in question. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * @return * The last item in the list. */ -#define SLIST_TAIL(...) \ - SLIST_TAIL_(__VA_ARGS__, ) - -#define SLIST_TAIL_(list, ...) \ - SLIST_TAIL__((list), LIST_NEXT_(__VA_ARGS__)) +#define SLIST_TAIL(list, ...) \ + SLIST_TAIL_((list), LIST_NEXT_(__VA_ARGS__)) -#define SLIST_TAIL__(list, next) \ - (list->head ? SLIST_CONTAINER_(list->tail, list->head, next) : NULL) +#define SLIST_TAIL_(list, next) \ + (list->head ? container_of(list->tail, typeof(*list->head), next) : NULL) /** * Check if an item is attached to a singly-linked list. * - * @param list + * @list * The list to check. - * @param item + * @item * The item to check. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * @return * Whether the item is attached to the list. */ -#define SLIST_ATTACHED(list, ...) \ - SLIST_ATTACHED_(list, __VA_ARGS__, ) +#define SLIST_ATTACHED(list, item, ...) \ + SLIST_ATTACHED_((list), (item), LIST_NEXT_(__VA_ARGS__)) -#define SLIST_ATTACHED_(list, item, ...) \ - SLIST_ATTACHED__((list), (item), LIST_NEXT_(__VA_ARGS__)) - -#define SLIST_ATTACHED__(list, item, next) \ +#define SLIST_ATTACHED_(list, item, next) \ (item->next || list->tail == &item->next) /** * Insert an item into a singly-linked list. * - * @param list + * @list * The list to modify. - * @param cursor + * @cursor * A pointer to the item to insert after, e.g. &list->head or list->tail. - * @param item + * @item * The item to insert. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * @return * A cursor for the next item. */ -#define SLIST_INSERT(list, cursor, ...) \ - SLIST_INSERT_(list, cursor, __VA_ARGS__, ) - -#define SLIST_INSERT_(list, cursor, item, ...) \ - SLIST_INSERT__((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__)) +#define SLIST_INSERT(list, cursor, item, ...) \ + SLIST_INSERT_((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__)) -#define SLIST_INSERT__(list, cursor, item, next) \ - (bfs_assert(!SLIST_ATTACHED__(list, item, next)), \ +#define SLIST_INSERT_(list, cursor, item, next) \ + (bfs_assert(!SLIST_ATTACHED_(list, item, next)), \ item->next = *cursor, \ *cursor = item, \ list->tail = item->next ? list->tail : &item->next, \ @@ -295,43 +225,37 @@ /** * Add an item to the tail of a singly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to append. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. */ -#define SLIST_APPEND(list, ...) \ - SLIST_APPEND_(list, __VA_ARGS__, ) - -#define SLIST_APPEND_(list, item, ...) \ - LIST_VOID_(SLIST_INSERT_(list, (list)->tail, item, __VA_ARGS__)) +#define SLIST_APPEND(list, item, ...) \ + LIST_VOID_(SLIST_INSERT(list, (list)->tail, item, __VA_ARGS__)) /** * Add an item to the head of a singly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to prepend. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. */ -#define SLIST_PREPEND(list, ...) \ - SLIST_PREPEND_(list, __VA_ARGS__, ) - -#define SLIST_PREPEND_(list, item, ...) \ - LIST_VOID_(SLIST_INSERT_(list, &(list)->head, item, __VA_ARGS__)) +#define SLIST_PREPEND(list, item, ...) \ + LIST_VOID_(SLIST_INSERT(list, &(list)->head, item, __VA_ARGS__)) /** * Splice a singly-linked list into another. * - * @param dest + * @dest * The destination list. - * @param cursor + * @cursor * A pointer to the item to splice after, e.g. &list->head or list->tail. - * @param src + * @src * The source list. */ #define SLIST_SPLICE(dest, cursor, src) \ @@ -346,9 +270,9 @@ /** * Add an entire singly-linked list to the tail of another. * - * @param dest + * @dest * The destination list. - * @param src + * @src * The source list. */ #define SLIST_EXTEND(dest, src) \ @@ -357,27 +281,24 @@ /** * Remove an item from a singly-linked list. * - * @param list + * @list * The list to modify. - * @param cursor + * @cursor * A pointer to the item to remove, either &list->head or &prev->next. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. * @return * The removed item. */ -#define SLIST_REMOVE(list, ...) \ - SLIST_REMOVE_(list, __VA_ARGS__, ) - -#define SLIST_REMOVE_(list, cursor, ...) \ - SLIST_REMOVE__((list), (cursor), LIST_NEXT_(__VA_ARGS__)) +#define SLIST_REMOVE(list, cursor, ...) \ + SLIST_REMOVE_((list), (cursor), LIST_NEXT_(__VA_ARGS__)) -#define SLIST_REMOVE__(list, cursor, next) \ +#define SLIST_REMOVE_(list, cursor, next) \ (list->tail = (*cursor)->next ? list->tail : cursor, \ - slist_remove_impl(*cursor, cursor, &(*cursor)->next, sizeof(*cursor))) + (typeof(*cursor))slist_remove_(*cursor, cursor, &(*cursor)->next, sizeof(*cursor))) // Helper for SLIST_REMOVE() -static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_t size) { +static inline void *slist_remove_(void *ret, void *cursor, void *next, size_t size) { // ret = *cursor; // *cursor = ret->next; memcpy(cursor, next, size); @@ -389,49 +310,55 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Pop the head off a singly-linked list. * - * @param list + * @list * The list to modify. - * @param node (optional) + * @node (optional) * If specified, use head->node.next rather than head->next. * @return * The popped item, or NULL if the list was empty. */ -#define SLIST_POP(...) \ - SLIST_POP_(__VA_ARGS__, ) - -#define SLIST_POP_(list, ...) \ - SLIST_POP__((list), __VA_ARGS__) - -#define SLIST_POP__(list, ...) \ - (list->head ? SLIST_REMOVE_(list, &list->head, __VA_ARGS__) : NULL) +#define SLIST_POP(list, ...) \ + ((list)->head ? SLIST_REMOVE(list, &(list)->head, __VA_ARGS__) : NULL) /** * Loop over the items in a singly-linked list. * - * @param type + * @type * The list item type. - * @param item + * @item * The induction variable name. - * @param list + * @list * The list to iterate. - * @param node (optional) + * @node (optional) * If specified, use head->node.next rather than head->next. */ -#define for_slist(type, item, ...) \ - for_slist_(type, item, __VA_ARGS__, ) - -#define for_slist_(type, item, list, ...) \ - for_slist__(type, item, (list), LIST_NEXT_(__VA_ARGS__)) +#define for_slist(type, item, list, ...) \ + for_slist_(type, item, (list), LIST_NEXT_(__VA_ARGS__)) -#define for_slist__(type, item, list, next) \ - for (type *item = list->head, *_next; \ - item && (SLIST_CHECK_(list), _next = item->next, true); \ +#define for_slist_(type, item, list, next) \ + for (type *item = SLIST_HEAD(list), *_next; \ + item && (_next = item->next, true); \ item = _next) /** + * Loop over a singly-linked list, popping each item. + * + * @type + * The list item type. + * @item + * The induction variable name. + * @list + * The list to drain. + * @node (optional) + * If specified, use head->node.next rather than head->next. + */ +#define drain_slist(type, item, list, ...) \ + for (type *item; (item = SLIST_POP(list, __VA_ARGS__));) + +/** * Initialize a doubly-linked list. * - * @param list + * @list * The list to initialize. */ #define LIST_INIT(list) \ @@ -441,27 +368,24 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ LIST_VOID_(list->head = list->tail = NULL) /** - * LIST_PREV_() => prev - * LIST_PREV_(node, ) => node.prev + * LIST_PREV_() => prev + * LIST_PREV_(node) => node.prev */ -#define LIST_PREV_(...) \ - LIST_NODE_(prev, __VA_ARGS__) +#define LIST_PREV_(node) \ + BFS_VA_IF(node)(node.prev)(prev) /** * Initialize a doubly-linked list item. * - * @param item + * @item * The item to initialize. - * @param node (optional) + * @node (optional) * If specified, use item->node.next rather than item->next. */ -#define LIST_ITEM_INIT(...) \ - LIST_ITEM_INIT_(__VA_ARGS__, ) +#define LIST_ITEM_INIT(item, ...) \ + LIST_ITEM_INIT_((item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) -#define LIST_ITEM_INIT_(item, ...) \ - LIST_ITEM_INIT__((item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) - -#define LIST_ITEM_INIT__(item, prev, next) \ +#define LIST_ITEM_INIT_(item, prev, next) \ LIST_VOID_(item->prev = item->next = NULL) /** @@ -474,78 +398,69 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ * Check if a doubly-linked list is empty. */ #define LIST_EMPTY(list) \ - LIST_EMPTY_((list)) - -#define LIST_EMPTY_(list) \ - (LIST_CHECK_(list), !list->head) + (LIST_CHECK_(list), !(list)->head) /** * Add an item to the tail of a doubly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to append. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. */ -#define LIST_APPEND(list, ...) \ - LIST_INSERT(list, (list)->tail, __VA_ARGS__) +#define LIST_APPEND(list, item, ...) \ + LIST_INSERT(list, (list)->tail, item, __VA_ARGS__) /** * Add an item to the head of a doubly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to prepend. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. */ -#define LIST_PREPEND(list, ...) \ - LIST_INSERT(list, NULL, __VA_ARGS__) +#define LIST_PREPEND(list, item, ...) \ + LIST_INSERT(list, NULL, item, __VA_ARGS__) /** * Check if an item is attached to a doubly-linked list. * - * @param list + * @list * The list to check. - * @param item + * @item * The item to check. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. * @return * Whether the item is attached to the list. */ -#define LIST_ATTACHED(list, ...) \ - LIST_ATTACHED_(list, __VA_ARGS__, ) - -#define LIST_ATTACHED_(list, item, ...) \ - LIST_ATTACHED__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) +#define LIST_ATTACHED(list, item, ...) \ + LIST_ATTACHED_((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) -#define LIST_ATTACHED__(list, item, prev, next) \ +#define LIST_ATTACHED_(list, item, prev, next) \ (item->prev || item->next || list->head == item || list->tail == item) /** * Insert into a doubly-linked list after the given cursor. * - * @param list + * @list * The list to modify. - * @param cursor + * @cursor * Insert after this element. - * @param item + * @item * The item to insert. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. */ -#define LIST_INSERT(list, cursor, ...) \ - LIST_INSERT_(list, cursor, __VA_ARGS__, ) +#define LIST_INSERT(list, cursor, item, ...) \ + LIST_INSERT_((list), (cursor), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) -#define LIST_INSERT_(list, cursor, item, ...) \ - LIST_INSERT__((list), (cursor), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) - -#define LIST_INSERT__(list, cursor, item, prev, next) LIST_VOID_( \ - bfs_assert(!LIST_ATTACHED__(list, item, prev, next)), \ +#define LIST_INSERT_(list, cursor, item, prev, next) LIST_VOID_( \ + bfs_assert(!LIST_ATTACHED_(list, item, prev, next)), \ item->prev = cursor, \ item->next = cursor ? cursor->next : list->head, \ *(item->prev ? &item->prev->next : &list->head) = item, \ @@ -554,20 +469,17 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Remove an item from a doubly-linked list. * - * @param list + * @list * The list to modify. - * @param item + * @item * The item to remove. - * @param node (optional) + * @node (optional) * If specified, use item->node.{prev,next} rather than item->{prev,next}. */ -#define LIST_REMOVE(list, ...) \ - LIST_REMOVE_(list, __VA_ARGS__, ) - -#define LIST_REMOVE_(list, item, ...) \ - LIST_REMOVE__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) +#define LIST_REMOVE(list, item, ...) \ + LIST_REMOVE_((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__)) -#define LIST_REMOVE__(list, item, prev, next) LIST_VOID_( \ +#define LIST_REMOVE_(list, item, prev, next) LIST_VOID_( \ *(item->prev ? &item->prev->next : &list->head) = item->next, \ *(item->next ? &item->next->prev : &list->tail) = item->prev, \ item->prev = item->next = NULL) @@ -575,24 +487,21 @@ static inline void *slist_remove_impl(void *ret, void *cursor, void *next, size_ /** * Loop over the items in a doubly-linked list. * - * @param type + * @type * The list item type. - * @param item + * @item * The induction variable name. - * @param list + * @list * The list to iterate. - * @param node (optional) + * @node (optional) * If specified, use head->node.next rather than head->next. */ -#define for_list(type, item, ...) \ - for_list_(type, item, __VA_ARGS__, ) - -#define for_list_(type, item, list, ...) \ - for_list__(type, item, (list), LIST_NEXT_(__VA_ARGS__)) +#define for_list(type, item, list, ...) \ + for_list_(type, item, (list), LIST_NEXT_(__VA_ARGS__)) -#define for_list__(type, item, list, next) \ - for (type *item = list->head, *_next; \ - item && (LIST_CHECK_(list), _next = item->next, true); \ +#define for_list_(type, item, list, next) \ + for (type *item = (LIST_CHECK_(list), list->head), *_next; \ + item && (_next = item->next, true); \ item = _next) #endif // BFS_LIST_H @@ -15,12 +15,14 @@ #include <string.h> #include <sys/types.h> -#if !defined(BFS_USE_MNTENT) && BFS_HAS_GETMNTENT_1 -# define BFS_USE_MNTENT true -#elif !defined(BFS_USE_MNTINFO) && BFS_HAS_GETMNTINFO -# define BFS_USE_MNTINFO true -#elif !defined(BFS_USE_MNTTAB) && BFS_HAS_GETMNTENT_2 -# define BFS_USE_MNTTAB true +#ifndef BFS_USE_MNTENT +# define BFS_USE_MNTENT BFS_HAS_GETMNTENT_1 +#endif +#ifndef BFS_USE_MNTINFO +# define BFS_USE_MNTINFO (!BFS_USE_MNTENT && BFS_HAS_GETMNTINFO) +#endif +#ifndef BFS_USE_MNTTAB +# define BFS_USE_MNTTAB (!BFS_USE_MNTINFO && BFS_HAS_GETMNTENT_2) #endif #if BFS_USE_MNTENT @@ -67,7 +69,7 @@ struct bfs_mtab { /** * Add an entry to the mount table. */ -_maybe_unused +[[_maybe_unused]] static int bfs_mtab_add(struct bfs_mtab *mtab, const char *path, const char *type) { size_t path_size = strlen(path) + 1; size_t type_size = strlen(type) + 1; @@ -254,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; } } @@ -280,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"; } @@ -26,9 +26,9 @@ struct bfs_mtab *bfs_mtab_parse(void); /** * Determine the file system type that a file is on. * - * @param mtab + * @mtab * The current mount table. - * @param statbuf + * @statbuf * The bfs_stat() buffer for the file in question. * @return * The type of file system containing this file, "unknown" if not known, @@ -39,9 +39,9 @@ const char *bfs_fstype(const struct bfs_mtab *mtab, const struct bfs_stat *statb /** * Check if a file could be a mount point. * - * @param mtab + * @mtab * The current mount table. - * @param name + * @name * The name of the file to check. * @return * Whether the named file could be a mount point. @@ -122,7 +122,7 @@ static const char *const pred_names[] = { }; /** - * A contrained integer range. + * A constrained integer range. */ struct df_range { /** The (inclusive) minimum value. */ @@ -374,7 +374,7 @@ struct bfs_opt { }; /** Log an optimization. */ -_printf(2, 3) +[[_printf(2, 3)]] static bool opt_debug(struct bfs_opt *opt, const char *format, ...) { if (bfs_debug_prefix(opt->ctx, DEBUG_OPT)) { for (int i = 0; i < opt->depth; ++i) { @@ -392,7 +392,7 @@ static bool opt_debug(struct bfs_opt *opt, const char *format, ...) { } /** Log a recursive call. */ -_printf(2, 3) +[[_printf(2, 3)]] static bool opt_enter(struct bfs_opt *opt, const char *format, ...) { int depth = opt->depth; if (depth > 0) { @@ -412,7 +412,7 @@ static bool opt_enter(struct bfs_opt *opt, const char *format, ...) { } /** Log a recursive return. */ -_printf(2, 3) +[[_printf(2, 3)]] static bool opt_leave(struct bfs_opt *opt, const char *format, ...) { bool debug = false; int depth = opt->depth; @@ -436,7 +436,7 @@ static bool opt_leave(struct bfs_opt *opt, const char *format, ...) { } /** Log a shallow visit. */ -_printf(2, 3) +[[_printf(2, 3)]] static bool opt_visit(struct bfs_opt *opt, const char *format, ...) { int depth = opt->depth; if (depth > 0) { @@ -456,7 +456,7 @@ static bool opt_visit(struct bfs_opt *opt, const char *format, ...) { } /** Log the deletion of an expression. */ -_printf(2, 3) +[[_printf(2, 3)]] static bool opt_delete(struct bfs_opt *opt, const char *format, ...) { int depth = opt->depth; @@ -618,7 +618,7 @@ static bool is_const(const struct bfs_expr *expr) { } /** Warn about an expression. */ -_printf(3, 4) +[[_printf(3, 4)]] static bool opt_warning(const struct bfs_opt *opt, const struct bfs_expr *expr, const char *format, ...) { if (!opt->warn) { return false; @@ -737,9 +737,7 @@ static struct bfs_expr *visit_and(struct bfs_opt *opt, struct bfs_expr *expr, co df_init_bottom(&opt->after_false); struct bfs_opt nested = *opt; - while (!SLIST_EMPTY(&children)) { - struct bfs_expr *child = SLIST_POP(&children); - + drain_slist (struct bfs_expr, child, &children) { if (SLIST_EMPTY(&children)) { nested.ignore_result = opt->ignore_result; } else { @@ -771,9 +769,7 @@ static struct bfs_expr *visit_or(struct bfs_opt *opt, struct bfs_expr *expr, con df_init_bottom(&opt->after_true); struct bfs_opt nested = *opt; - while (!SLIST_EMPTY(&children)) { - struct bfs_expr *child = SLIST_POP(&children); - + drain_slist (struct bfs_expr, child, &children) { if (SLIST_EMPTY(&children)) { nested.ignore_result = opt->ignore_result; } else { @@ -803,9 +799,7 @@ static struct bfs_expr *visit_comma(struct bfs_opt *opt, struct bfs_expr *expr, struct bfs_opt nested = *opt; - while (!SLIST_EMPTY(&children)) { - struct bfs_expr *child = SLIST_POP(&children); - + drain_slist (struct bfs_expr, child, &children) { if (SLIST_EMPTY(&children)) { nested.ignore_result = opt->ignore_result; } else { @@ -1384,8 +1378,7 @@ static struct bfs_expr *sink_not_andor(struct bfs_opt *opt, struct bfs_expr *exp struct bfs_exprs children; foster_children(expr, &children); - struct bfs_expr *child; - while ((child = SLIST_POP(&children))) { + drain_slist (struct bfs_expr, child, &children) { opt_enter(opt, "%pe\n", child); child = negate_expr(opt, child, argv); @@ -1412,8 +1405,7 @@ static struct bfs_expr *sink_not_comma(struct bfs_opt *opt, struct bfs_expr *exp struct bfs_exprs children; foster_children(expr, &children); - struct bfs_expr *child; - while ((child = SLIST_POP(&children))) { + drain_slist (struct bfs_expr, child, &children) { if (SLIST_EMPTY(&children)) { opt_enter(opt, "%pe\n", child); opt_debug(opt, "sink\n"); @@ -1441,7 +1433,6 @@ static struct bfs_expr *canonicalize_not(struct bfs_opt *opt, struct bfs_expr *e if (rhs->eval_fn == eval_not) { opt_debug(opt, "double negation\n"); - rhs = only_child(expr); return only_child(rhs); } else if (rhs->eval_fn == eval_and || rhs->eval_fn == eval_or) { return sink_not_andor(opt, expr); @@ -1463,8 +1454,7 @@ static struct bfs_expr *canonicalize_assoc(struct bfs_opt *opt, struct bfs_expr struct bfs_exprs flat; SLIST_INIT(&flat); - struct bfs_expr *child; - while ((child = SLIST_POP(&children))) { + drain_slist (struct bfs_expr, child, &children) { if (child->eval_fn == expr->eval_fn) { struct bfs_expr *head = SLIST_HEAD(&child->children); struct bfs_expr *tail = SLIST_TAIL(&child->children); @@ -1572,8 +1562,7 @@ static struct bfs_expr *reorder_andor(struct bfs_opt *opt, struct bfs_expr *expr struct bfs_exprs pure; SLIST_INIT(&pure); - struct bfs_expr *child; - while ((child = SLIST_POP(&children))) { + drain_slist (struct bfs_expr, child, &children) { if (child->pure) { SLIST_APPEND(&pure, child); } else { @@ -1634,14 +1623,19 @@ static void data_flow_icmp(struct bfs_opt *opt, const struct bfs_expr *expr, enu /** Transfer function for -{execut,read,writ}able. */ static struct bfs_expr *data_flow_access(struct bfs_opt *opt, struct bfs_expr *expr, const struct visitor *visitor) { - if (expr->num & R_OK) { + switch (expr->num) { + case R_OK: data_flow_pred(opt, READABLE_PRED, true); - } - if (expr->num & W_OK) { + break; + case W_OK: data_flow_pred(opt, WRITABLE_PRED, true); - } - if (expr->num & X_OK) { + break; + case X_OK: data_flow_pred(opt, EXECUTABLE_PRED, true); + break; + default: + bfs_bug("Unknown access() mode %lld", expr->num); + break; } return expr; @@ -1666,7 +1660,7 @@ static struct bfs_expr *data_flow_gid(struct bfs_opt *opt, struct bfs_expr *expr gid_t gid = range->min; bool nogroup = !bfs_getgrgid(opt->ctx->groups, gid); if (errno == 0) { - data_flow_pred(opt, NOGROUP_PRED, nogroup); + constrain_pred(&opt->after_true.preds[NOGROUP_PRED], nogroup); } } @@ -1740,7 +1734,7 @@ static struct bfs_expr *data_flow_uid(struct bfs_opt *opt, struct bfs_expr *expr uid_t uid = range->min; bool nouser = !bfs_getpwuid(opt->ctx->users, uid); if (errno == 0) { - data_flow_pred(opt, NOUSER_PRED, nouser); + constrain_pred(&opt->after_true.preds[NOUSER_PRED], nouser); } } @@ -1975,8 +1969,7 @@ static struct bfs_expr *lift_andor_not(struct bfs_opt *opt, struct bfs_expr *exp struct bfs_exprs children; foster_children(expr, &children); - struct bfs_expr *child; - while ((child = SLIST_POP(&children))) { + drain_slist (struct bfs_expr, child, &children) { opt_enter(opt, "%pe\n", child); child = negate_expr(opt, child, &fake_not_arg); @@ -2022,9 +2015,7 @@ static struct bfs_expr *simplify_and(struct bfs_opt *opt, struct bfs_expr *expr, struct bfs_exprs children; foster_children(expr, &children); - while (!SLIST_EMPTY(&children)) { - struct bfs_expr *child = SLIST_POP(&children); - + drain_slist (struct bfs_expr, child, &children) { if (child == ignorable) { ignore = true; } @@ -2045,8 +2036,8 @@ static struct bfs_expr *simplify_and(struct bfs_opt *opt, struct bfs_expr *expr, bfs_expr_append(expr, child); if (child->always_false) { - while ((child = SLIST_POP(&children))) { - opt_delete(opt, "%pe [short-circuit]\n", child); + drain_slist (struct bfs_expr, dead, &children) { + opt_delete(opt, "%pe [short-circuit]\n", dead); } } } @@ -2071,9 +2062,7 @@ static struct bfs_expr *simplify_or(struct bfs_opt *opt, struct bfs_expr *expr, struct bfs_exprs children; foster_children(expr, &children); - while (!SLIST_EMPTY(&children)) { - struct bfs_expr *child = SLIST_POP(&children); - + drain_slist (struct bfs_expr, child, &children) { if (child == ignorable) { ignore = true; } @@ -2094,8 +2083,8 @@ static struct bfs_expr *simplify_or(struct bfs_opt *opt, struct bfs_expr *expr, bfs_expr_append(expr, child); if (child->always_true) { - while ((child = SLIST_POP(&children))) { - opt_delete(opt, "%pe [short-circuit]\n", child); + drain_slist (struct bfs_expr, dead, &children) { + opt_delete(opt, "%pe [short-circuit]\n", dead); } } } @@ -2117,9 +2106,7 @@ static struct bfs_expr *simplify_comma(struct bfs_opt *opt, struct bfs_expr *exp struct bfs_exprs children; foster_children(expr, &children); - while (!SLIST_EMPTY(&children)) { - struct bfs_expr *child = SLIST_POP(&children); - + drain_slist (struct bfs_expr, child, &children) { if (opt->level >= 2 && child->pure && !SLIST_EMPTY(&children)) { if (!opt_ignore(opt, child, true)) { return NULL; @@ -13,7 +13,7 @@ struct bfs_ctx; /** * Apply optimizations to the command line. * - * @param ctx + * @ctx * The bfs context to optimize. * @return * 0 if successful, -1 on error. diff --git a/src/parse.c b/src/parse.c index 42f71cc..febab7f 100644 --- a/src/parse.c +++ b/src/parse.c @@ -84,8 +84,6 @@ struct bfs_parser { enum use_color use_color; /** Whether a -print action is implied. */ bool implicit_print; - /** Whether the default root "." should be used. */ - bool implicit_root; /** Whether the expression has started. */ bool expr_started; /** Whether an information option like -help or -version was passed. */ @@ -95,20 +93,20 @@ struct bfs_parser { /** The last non-path argument. */ char **last_arg; - /** A "-depth"-type argument, if any. */ - char **depth_arg; - /** A "-limit" argument, if any. */ - char **limit_arg; - /** A "-prune" argument, if any. */ - char **prune_arg; - /** A "-mount" argument, if any. */ - char **mount_arg; - /** An "-xdev" argument, if any. */ - char **xdev_arg; - /** A "-files0-from -" argument, if any. */ - char **files0_stdin_arg; - /** An "-ok"-type expression, if any. */ - const struct bfs_expr *ok_expr; + /** A "-depth"-type expression, if any. */ + const struct bfs_expr *depth_expr; + /** A "-limit" expression, if any. */ + const struct bfs_expr *limit_expr; + /** A "-prune" expression, if any. */ + const struct bfs_expr *prune_expr; + /** A "-mount" expression, if any. */ + const struct bfs_expr *mount_expr; + /** An "-xdev" expression, if any. */ + const struct bfs_expr *xdev_expr; + /** A "-files0-from" expression, if any. */ + const struct bfs_expr *files0_expr; + /** An expression that consumes stdin, if any. */ + const struct bfs_expr *stdin_expr; /** The current time (maybe modified by -daystart). */ struct timespec now; @@ -140,7 +138,7 @@ static void highlight_args(const struct bfs_ctx *ctx, char **argv, size_t argc, /** * Print an error message during parsing. */ -_printf(2, 3) +[[_printf(2, 3)]] static void parse_error(const struct bfs_parser *parser, const char *format, ...) { const struct bfs_ctx *ctx = parser->ctx; @@ -158,7 +156,7 @@ static void parse_error(const struct bfs_parser *parser, const char *format, ... /** * Print an error about some command line arguments. */ -_printf(4, 5) +[[_printf(4, 5)]] static void parse_argv_error(const struct bfs_parser *parser, char **argv, size_t argc, const char *format, ...) { const struct bfs_ctx *ctx = parser->ctx; @@ -176,14 +174,14 @@ static void parse_argv_error(const struct bfs_parser *parser, char **argv, size_ /** * Print an error about conflicting command line arguments. */ -_printf(6, 7) -static void parse_conflict_error(const struct bfs_parser *parser, char **argv1, size_t argc1, char **argv2, size_t argc2, const char *format, ...) { +[[_printf(4, 5)]] +static void parse_conflict_error(const struct bfs_parser *parser, const struct bfs_expr *expr1, const struct bfs_expr *expr2, const char *format, ...) { const struct bfs_ctx *ctx = parser->ctx; bool highlight[ctx->argc]; init_highlight(ctx, highlight); - highlight_args(ctx, argv1, argc1, highlight); - highlight_args(ctx, argv2, argc2, highlight); + highlight_args(ctx, expr1->argv, expr1->argc, highlight); + highlight_args(ctx, expr2->argv, expr2->argc, highlight); bfs_argv_error(ctx, highlight); va_list args; @@ -195,7 +193,7 @@ static void parse_conflict_error(const struct bfs_parser *parser, char **argv1, /** * Print an error about an expression. */ -_printf(3, 4) +[[_printf(3, 4)]] static void parse_expr_error(const struct bfs_parser *parser, const struct bfs_expr *expr, const char *format, ...) { const struct bfs_ctx *ctx = parser->ctx; @@ -210,7 +208,7 @@ static void parse_expr_error(const struct bfs_parser *parser, const struct bfs_e /** * Print a warning message during parsing. */ -_printf(2, 3) +[[_printf(2, 3)]] static bool parse_warning(const struct bfs_parser *parser, const char *format, ...) { const struct bfs_ctx *ctx = parser->ctx; @@ -231,14 +229,14 @@ static bool parse_warning(const struct bfs_parser *parser, const char *format, . /** * Print a warning about conflicting command line arguments. */ -_printf(6, 7) -static bool parse_conflict_warning(const struct bfs_parser *parser, char **argv1, size_t argc1, char **argv2, size_t argc2, const char *format, ...) { +[[_printf(4, 5)]] +static bool parse_conflict_warning(const struct bfs_parser *parser, const struct bfs_expr *expr1, const struct bfs_expr *expr2, const char *format, ...) { const struct bfs_ctx *ctx = parser->ctx; bool highlight[ctx->argc]; init_highlight(ctx, highlight); - highlight_args(ctx, argv1, argc1, highlight); - highlight_args(ctx, argv2, argc2, highlight); + highlight_args(ctx, expr1->argv, expr1->argc, highlight); + highlight_args(ctx, expr2->argv, expr2->argc, highlight); if (!bfs_argv_warning(ctx, highlight)) { return false; } @@ -253,7 +251,7 @@ static bool parse_conflict_warning(const struct bfs_parser *parser, char **argv1 /** * Print a warning about an expression. */ -_printf(3, 4) +[[_printf(3, 4)]] static bool parse_expr_warning(const struct bfs_parser *parser, const struct bfs_expr *expr, const char *format, ...) { const struct bfs_ctx *ctx = parser->ctx; @@ -269,6 +267,21 @@ static bool parse_expr_warning(const struct bfs_parser *parser, const struct bfs } /** + * Report an error if stdin is already consumed, then consume it. + */ +static bool consume_stdin(struct bfs_parser *parser, const struct bfs_expr *expr) { + if (parser->stdin_expr) { + parse_conflict_error(parser, parser->stdin_expr, expr, + "%pX and %pX can't both use standard input.\n", + parser->stdin_expr, expr); + return false; + } + + parser->stdin_expr = expr; + return true; +} + +/** * Allocate a new expression. */ static struct bfs_expr *parse_new_expr(const struct bfs_parser *parser, bfs_eval_fn *eval_fn, size_t argc, char **argv, enum bfs_kind kind) { @@ -383,6 +396,8 @@ static struct bfs_expr *parse_expr(struct bfs_parser *parser); * Advance by a single token. */ static char **parser_advance(struct bfs_parser *parser, enum bfs_kind kind, size_t argc) { + struct bfs_ctx *ctx = parser->ctx; + if (kind != BFS_FLAG && kind != BFS_PATH) { parser->expr_started = true; } @@ -391,6 +406,9 @@ static char **parser_advance(struct bfs_parser *parser, enum bfs_kind kind, size parser->last_arg = parser->argv; } + size_t i = parser->argv - ctx->argv; + ctx->kinds[i] = kind; + char **argv = parser->argv; parser->argv += argc; return argv; @@ -414,7 +432,6 @@ static int parse_root(struct bfs_parser *parser, const char *path) { return -1; } - parser->implicit_root = false; return 0; } @@ -978,16 +995,16 @@ static struct bfs_expr *parse_time(struct bfs_parser *parser, int field, int arg switch (*tail) { case 'w': time *= 7; - _fallthrough; + [[fallthrough]]; case 'd': time *= 24; - _fallthrough; + [[fallthrough]]; case 'h': time *= 60; - _fallthrough; + [[fallthrough]]; case 'm': time *= 60; - _fallthrough; + [[fallthrough]]; case 's': break; default: @@ -1158,22 +1175,33 @@ static struct bfs_expr *parse_daystart(struct bfs_parser *parser, int arg1, int * Parse -delete. */ static struct bfs_expr *parse_delete(struct bfs_parser *parser, int arg1, int arg2) { + struct bfs_expr *expr = parse_nullary_action(parser, eval_delete); + if (!expr) { + return NULL; + } + struct bfs_ctx *ctx = parser->ctx; ctx->flags |= BFTW_POST_ORDER; ctx->dangerous = true; - parser->depth_arg = parser->argv; - - return parse_nullary_action(parser, eval_delete); + parser->depth_expr = expr; + return expr; } /** * Parse -d. */ -static struct bfs_expr *parse_depth(struct bfs_parser *parser, int arg1, int arg2) { +static struct bfs_expr *parse_depth(struct bfs_parser *parser, int flag, int arg2) { + struct bfs_expr *expr = flag + ? parse_nullary_flag(parser) + : parse_nullary_option(parser); + if (!expr) { + return NULL; + } + parser->ctx->flags |= BFTW_POST_ORDER; - parser->depth_arg = parser->argv; - return parse_nullary_flag(parser); + parser->depth_expr = expr; + return expr; } /** @@ -1219,6 +1247,41 @@ static struct bfs_expr *parse_empty(struct bfs_parser *parser, int arg1, int arg return expr; } +/** Check for unsafe relative paths in $PATH. */ +static const char *unsafe_path(const struct bfs_exec *execbuf) { + if (!(execbuf->flags & BFS_EXEC_CHDIR)) { + // Not -execdir or -okdir + return NULL; + } + + const char *exe = execbuf->tmpl_argv[0]; + if (strchr(exe, '/')) { + // No $PATH lookups for /foo or foo/bar + return NULL; + } + + if (strstr(exe, "{}")) { + // Substituted paths always contain a / + return NULL; + } + + const char *path = getenv("PATH"); + while (path) { + if (path[0] != '/') { + // Relative $PATH component! + return path; + } + + path = strchr(path, ':'); + if (path) { + ++path; + } + } + + // No relative components in $PATH + return NULL; +} + /** * Parse -exec(dir)?/-ok(dir)?. */ @@ -1241,29 +1304,21 @@ static struct bfs_expr *parse_exec(struct bfs_parser *parser, int flags, int arg // For pipe() in bfs_spawn() expr->ephemeral_fds = 2; - if (execbuf->flags & BFS_EXEC_CHDIR) { - // Check for relative paths in $PATH - const char *path = getenv("PATH"); - while (path) { - if (*path != '/') { - size_t len = strcspn(path, ":"); - char *comp = strndup(path, len); - if (comp) { - parse_expr_error(parser, expr, - "This action would be unsafe, since ${bld}$$PATH${rs} contains the relative path ${bld}%pq${rs}\n", comp); - free(comp); - } else { - parse_perror(parser, "strndup()"); - } - return NULL; - } - - path = strchr(path, ':'); - if (path) { - ++path; - } + const char *unsafe = unsafe_path(execbuf); + if (unsafe) { + size_t len = strcspn(unsafe, ":"); + char *comp = strndup(unsafe, len); + if (comp) { + parse_expr_error(parser, expr, + "This action would be unsafe, since ${bld}$$PATH${rs} contains the relative path ${bld}%pq${rs}\n", comp); + free(comp); + } else { + parse_perror(parser, "strndup()"); } + return NULL; + } + if (execbuf->flags & BFS_EXEC_CHDIR) { // To dup() the parent directory if (execbuf->flags & BFS_EXEC_MULTI) { ++expr->persistent_fds; @@ -1273,7 +1328,9 @@ static struct bfs_expr *parse_exec(struct bfs_parser *parser, int flags, int arg } if (execbuf->flags & BFS_EXEC_CONFIRM) { - parser->ok_expr = expr; + if (!consume_stdin(parser, expr)) { + return NULL; + } } else { ctx->dangerous = true; } @@ -1304,11 +1361,17 @@ static struct bfs_expr *parse_exit(struct bfs_parser *parser, int arg1, int arg2 * Parse -f PATH. */ static struct bfs_expr *parse_f(struct bfs_parser *parser, int arg1, int arg2) { + struct bfs_ctx *ctx = parser->ctx; + struct bfs_expr *expr = parse_unary_flag(parser); if (!expr) { return NULL; } + // Mark the path as a path, not a regular argument + size_t i = expr->argv - ctx->argv; + ctx->kinds[i + 1] = BFS_PATH; + if (parse_root(parser, expr->argv[1]) != 0) { return NULL; } @@ -1325,50 +1388,14 @@ static struct bfs_expr *parse_files0_from(struct bfs_parser *parser, int arg1, i return NULL; } - const char *from = expr->argv[1]; - - FILE *file; - if (strcmp(from, "-") == 0) { - file = stdin; - } else { - file = xfopen(from, O_RDONLY | O_CLOEXEC); - } - if (!file) { - parse_expr_error(parser, expr, "%s.\n", errstr()); - return NULL; - } - - while (true) { - char *path = xgetdelim(file, '\0'); - if (!path) { - if (errno) { - goto fail; - } else { - break; - } - } - - int ret = parse_root(parser, path); - free(path); - if (ret != 0) { - goto fail; - } - } - - if (file == stdin) { - parser->files0_stdin_arg = expr->argv; - } else { - fclose(file); - } - - parser->implicit_root = false; + // For compatibility with GNU find, + // + // bfs -files0-from a -files0-from b + // + // should *only* use b, not a. So stash the expression here and only + // process the last one at the end of parsing. + parser->files0_expr = expr; return expr; - -fail: - if (file != stdin) { - fclose(file); - } - return NULL; } /** @@ -1638,11 +1665,11 @@ static struct bfs_expr *parse_limit(struct bfs_parser *parser, int arg1, int arg } if (expr->num <= 0) { - parse_expr_error(parser, expr, "The ${blu}%s${rs} must be at least ${bld}1${rs}.\n", expr->argv[0]); + parse_expr_error(parser, expr, "The %pX must be at least ${bld}1${rs}.\n", expr); return NULL; } - parser->limit_arg = expr->argv; + parser->limit_expr = expr; return expr; } @@ -1676,7 +1703,7 @@ static struct bfs_expr *parse_mount(struct bfs_parser *parser, int arg1, int arg } parser->ctx->flags |= BFTW_SKIP_MOUNTS; - parser->mount_arg = expr->argv; + parser->mount_expr = expr; return expr; } @@ -1855,9 +1882,15 @@ static struct bfs_expr *parse_nohidden(struct bfs_parser *parser, int arg1, int * Parse -noleaf. */ static struct bfs_expr *parse_noleaf(struct bfs_parser *parser, int arg1, int arg2) { - parse_warning(parser, "${ex}%s${rs} does not apply the optimization that ${blu}%s${rs} inhibits.\n\n", - BFS_COMMAND, parser->argv[0]); - return parse_nullary_option(parser); + struct bfs_expr *expr = parse_nullary_option(parser); + if (!expr) { + return NULL; + } + + parse_expr_warning(parser, expr, + "${ex}%s${rs} does not apply the optimization that %px inhibits.\n\n", + BFS_COMMAND, expr); + return expr; } /** @@ -1940,7 +1973,7 @@ static int parse_mode(const struct bfs_parser *parser, const char *mode, struct who = 0; mask = 0777; state = MODE_WHO; - _fallthrough; + [[fallthrough]]; case MODE_WHO: switch (*i) { @@ -1967,7 +2000,7 @@ static int parse_mode(const struct bfs_parser *parser, const char *mode, struct case MODE_EQUALS: expr->file_mode &= ~who; expr->dir_mode &= ~who; - _fallthrough; + [[fallthrough]]; case MODE_PLUS: expr->file_mode |= file_change; expr->dir_mode |= dir_change; @@ -1977,7 +2010,7 @@ static int parse_mode(const struct bfs_parser *parser, const char *mode, struct expr->dir_mode &= ~dir_change; break; } - _fallthrough; + [[fallthrough]]; case MODE_ACTION: if (who == 0) { @@ -2062,7 +2095,7 @@ static int parse_mode(const struct bfs_parser *parser, const char *mode, struct break; case 'x': file_change |= mask & 0111; - _fallthrough; + [[fallthrough]]; case 'X': dir_change |= mask & 0111; break; @@ -2125,7 +2158,7 @@ static struct bfs_expr *parse_perm(struct bfs_parser *parser, int field, int arg ++mode; break; } - _fallthrough; + [[fallthrough]]; default: expr->mode_cmp = BFS_MODE_EQUAL; break; @@ -2193,8 +2226,13 @@ static struct bfs_expr *parse_printx(struct bfs_parser *parser, int arg1, int ar * Parse -prune. */ static struct bfs_expr *parse_prune(struct bfs_parser *parser, int arg1, int arg2) { - parser->prune_arg = parser->argv; - return parse_nullary_action(parser, eval_prune); + struct bfs_expr *expr = parse_nullary_action(parser, eval_prune); + if (!expr) { + return NULL; + } + + parser->prune_expr = expr; + return expr; } /** @@ -2572,9 +2610,14 @@ static struct bfs_expr *parse_xattrname(struct bfs_parser *parser, int arg1, int * Parse -xdev. */ static struct bfs_expr *parse_xdev(struct bfs_parser *parser, int arg1, int arg2) { + struct bfs_expr *expr = parse_nullary_option(parser); + if (!expr) { + return NULL; + } + parser->ctx->flags |= BFTW_PRUNE_MOUNTS; - parser->xdev_arg = parser->argv; - return parse_nullary_option(parser); + parser->xdev_expr = expr; + return expr; } /** @@ -3048,10 +3091,10 @@ static const struct table_entry parse_table[] = { {"-context", BFS_TEST, parse_context, true}, {"-csince", BFS_TEST, parse_since, BFS_STAT_CTIME}, {"-ctime", BFS_TEST, parse_time, BFS_STAT_CTIME}, - {"-d", BFS_FLAG, parse_depth}, + {"-d", BFS_FLAG, parse_depth, true}, {"-daystart", BFS_OPTION, parse_daystart}, {"-delete", BFS_ACTION, parse_delete}, - {"-depth", BFS_OPTION, parse_depth_n}, + {"-depth", BFS_OPTION, parse_depth_n, false}, {"-empty", BFS_TEST, parse_empty}, {"-exclude", BFS_OPERATOR}, {"-exec", BFS_ACTION, parse_exec, 0}, @@ -3503,6 +3546,73 @@ static struct bfs_expr *parse_expr(struct bfs_parser *parser) { return expr; } +/** Handle -files0-from after parsing. */ +static int parse_files0_roots(struct bfs_parser *parser) { + const struct bfs_ctx *ctx = parser->ctx; + const struct bfs_expr *expr = parser->files0_expr; + + if (ctx->npaths > 0) { + bool highlight[ctx->argc]; + init_highlight(ctx, highlight); + highlight_args(ctx, expr->argv, expr->argc, highlight); + + for (size_t i = 0; i < ctx->argc; ++i) { + if (ctx->kinds[i] == BFS_PATH) { + highlight[i] = true; + } + } + + bfs_argv_error(ctx, highlight); + bfs_error(ctx, "Cannot combine %pX with explicit root paths.\n", expr); + return -1; + } + + const char *from = expr->argv[1]; + + FILE *file; + if (strcmp(from, "-") == 0) { + if (!consume_stdin(parser, expr)) { + return -1; + } + file = stdin; + } else { + file = xfopen(from, O_RDONLY | O_CLOEXEC); + } + if (!file) { + parse_expr_error(parser, expr, "%s.\n", errstr()); + return -1; + } + + while (true) { + char *path = xgetdelim(file, '\0'); + if (!path) { + if (errno) { + goto fail; + } else { + break; + } + } + + int ret = parse_root(parser, path); + free(path); + if (ret != 0) { + goto fail; + } + } + + if (file != stdin) { + fclose(file); + } + + return 0; + +fail: + if (file != stdin) { + fclose(file); + } + return -1; +} + /** * Parse the top-level expression. */ @@ -3528,12 +3638,22 @@ static struct bfs_expr *parse_whole_expr(struct bfs_parser *parser) { return NULL; } + if (parser->files0_expr) { + if (parse_files0_roots(parser) != 0) { + return NULL; + } + } else if (ctx->npaths == 0) { + if (parse_root(parser, ".") != 0) { + return NULL; + } + } + if (parser->implicit_print) { - char **limit = parser->limit_arg; + const struct bfs_expr *limit = parser->limit_expr; if (limit) { - parse_argv_error(parser, parser->limit_arg, 2, - "With ${blu}%s${rs}, you must specify an action explicitly; for example, ${blu}-print${rs} ${blu}%s${rs} ${bld}%s${rs}.\n", - limit[0], limit[0], limit[1]); + parse_expr_error(parser, limit, + "With %pX, you must specify an action explicitly; for example, ${blu}-print${rs} %px.\n", + limit, limit); return NULL; } @@ -3549,16 +3669,16 @@ static struct bfs_expr *parse_whole_expr(struct bfs_parser *parser) { } } - if (parser->mount_arg && parser->xdev_arg) { - parse_conflict_warning(parser, parser->mount_arg, 1, parser->xdev_arg, 1, - "${blu}%s${rs} is redundant in the presence of ${blu}%s${rs}.\n\n", - parser->xdev_arg[0], parser->mount_arg[0]); + if (parser->mount_expr && parser->xdev_expr) { + parse_conflict_warning(parser, parser->mount_expr, parser->xdev_expr, + "%px is redundant in the presence of %px.\n\n", + parser->xdev_expr, parser->mount_expr); } - if (ctx->warn && parser->depth_arg && parser->prune_arg) { - parse_conflict_warning(parser, parser->depth_arg, 1, parser->prune_arg, 1, - "${blu}%s${rs} does not work in the presence of ${blu}%s${rs}.\n", - parser->prune_arg[0], parser->depth_arg[0]); + if (ctx->warn && parser->depth_expr && parser->prune_expr) { + parse_conflict_warning(parser, parser->depth_expr, parser->prune_expr, + "%px does not work in the presence of %px.\n", + parser->prune_expr, parser->depth_expr); if (ctx->interactive) { bfs_warning(ctx, "Do you want to continue? "); @@ -3570,13 +3690,6 @@ static struct bfs_expr *parse_whole_expr(struct bfs_parser *parser) { fprintf(stderr, "\n"); } - if (parser->ok_expr && parser->files0_stdin_arg) { - parse_conflict_error(parser, parser->ok_expr->argv, parser->ok_expr->argc, parser->files0_stdin_arg, 2, - "${blu}%s${rs} conflicts with ${blu}%s${rs} ${bld}%s${rs}.\n", - parser->ok_expr->argv[0], parser->files0_stdin_arg[0], parser->files0_stdin_arg[1]); - return NULL; - } - return expr; } @@ -3758,6 +3871,12 @@ struct bfs_ctx *bfs_parse_cmdline(int argc, char *argv[]) { goto fail; } + ctx->kinds = ZALLOC_ARRAY(enum bfs_kind, argc); + if (!ctx->kinds) { + perror("zalloc()"); + goto fail; + } + enum use_color use_color = COLOR_AUTO; const char *no_color = getenv("NO_COLOR"); if (no_color && *no_color) { @@ -3806,16 +3925,14 @@ struct bfs_ctx *bfs_parse_cmdline(int argc, char *argv[]) { .stdout_tty = stdout_tty, .use_color = use_color, .implicit_print = true, - .implicit_root = true, .just_info = false, .excluding = false, .last_arg = NULL, - .depth_arg = NULL, - .prune_arg = NULL, - .mount_arg = NULL, - .xdev_arg = NULL, - .files0_stdin_arg = NULL, - .ok_expr = NULL, + .depth_expr = NULL, + .prune_expr = NULL, + .mount_expr = NULL, + .xdev_expr = NULL, + .stdin_expr = NULL, .now = ctx->now, }; @@ -3844,12 +3961,6 @@ struct bfs_ctx *bfs_parse_cmdline(int argc, char *argv[]) { goto fail; } - if (ctx->npaths == 0 && parser.implicit_root) { - if (parse_root(&parser, ".") != 0) { - goto fail; - } - } - if ((ctx->flags & BFTW_FOLLOW_ALL) && !ctx->unique) { // We need bftw() to detect cycles unless -unique does it for us ctx->flags |= BFTW_DETECT_CYCLES; diff --git a/src/parse.h b/src/parse.h index 6895c9f..fcc8234 100644 --- a/src/parse.h +++ b/src/parse.h @@ -11,9 +11,9 @@ /** * Parse the command line. * - * @param argc + * @argc * The number of arguments. - * @param argv + * @argv * The arguments to parse. * @return * A new bfs context, or NULL on failure. diff --git a/src/prelude.h b/src/prelude.h index a0cc2a1..51f1505 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 @@ -72,23 +77,26 @@ /** _Bool => bool, true, false */ #include <stdbool.h> -/** - * C23 deprecates `noreturn void` in favour of `[[noreturn]] void`, so we expose - * _noreturn instead with the other attributes in "bfs.h". - */ -// #include <stdnoreturn.h> - /** Part of <threads.h>, but we don't use anything else from it. */ #define thread_local _Thread_local +/** Get the type of an expression. */ +#define typeof __typeof__ +/** Get the unqualified type of an expression. */ +#define typeof_unqual __typeof_unqual__ + #endif // !C23 -// Feature detection +// Future C standard backports -// https://clang.llvm.org/docs/LanguageExtensions.html#has-attribute -#ifndef __has_attribute -# define __has_attribute(attr) false -#endif +/** + * Get the length of an array. + * + * https://www.open-std.org/JTC1/SC22/WG14/www/docs/n3469.htm + */ +#define countof(...) (sizeof(__VA_ARGS__) / sizeof(0[__VA_ARGS__])) + +// Feature detection // https://clang.llvm.org/docs/LanguageExtensions.html#has-builtin #ifndef __has_builtin @@ -121,5 +129,8 @@ #if __has_feature(thread_sanitizer) && !defined(__SANITIZE_THREAD__) # define __SANITIZE_THREAD__ true #endif +#if __has_feature(type_sanitizer) && !defined(__SANITIZE_TYPE__) +# define __SANITIZE_TYPE__ true +#endif #endif // BFS_PRELUDE_H diff --git a/src/printf.c b/src/printf.c index 30ec201..f9fca64 100644 --- a/src/printf.c +++ b/src/printf.c @@ -91,7 +91,7 @@ static bool should_color(CFILE *cfile, const struct bfs_fmt *fmt) { (void)ret /** Return a dynamic format string. */ -_format_arg(2) +[[_format_arg(2)]] static const char *dyn_fmt(const char *str, const char *fake) { bfs_assert(strcmp(str + strlen(str) - strlen(fake) + 1, fake + 1) == 0, "Mismatched format specifiers: '%s' vs. '%s'", str, fake); @@ -99,7 +99,7 @@ static const char *dyn_fmt(const char *str, const char *fake) { } /** Wrapper for fprintf(). */ -_printf(3, 4) +[[_printf(3, 4)]] static int bfs_fprintf(CFILE *cfile, const struct bfs_fmt *fmt, const char *fake, ...) { va_list args; va_start(args, fake); @@ -562,7 +562,7 @@ static int bfs_printf_Y(CFILE *cfile, const struct bfs_fmt *fmt, const struct BF } /** %Z: SELinux context */ -_maybe_unused +[[_maybe_unused]] static int bfs_printf_Z(CFILE *cfile, const struct bfs_fmt *fmt, const struct BFTW *ftwbuf) { char *con = bfs_getfilecon(ftwbuf); if (!con) { @@ -708,7 +708,7 @@ int bfs_printf_parse(const struct bfs_ctx *ctx, struct bfs_expr *expr, const cha case '+': case ' ': must_be_numeric = true; - _fallthrough; + [[fallthrough]]; case '-': if (strchr(fmt.str, c)) { bfs_expr_error(ctx, expr); diff --git a/src/printf.h b/src/printf.h index 2bff087..e8d862e 100644 --- a/src/printf.h +++ b/src/printf.h @@ -22,11 +22,11 @@ struct bfs_printf; /** * Parse a -printf format string. * - * @param ctx + * @ctx * The bfs context. - * @param expr + * @expr * The expression to fill in. - * @param format + * @format * The format string to parse. * @return * 0 on success, -1 on failure. @@ -36,11 +36,11 @@ int bfs_printf_parse(const struct bfs_ctx *ctx, struct bfs_expr *expr, const cha /** * Evaluate a parsed format string. * - * @param cfile + * @cfile * The CFILE to print to. - * @param format + * @format * The parsed printf format. - * @param ftwbuf + * @ftwbuf * The bftw() data for the current file. * @return * 0 on success, -1 on failure. diff --git a/src/pwcache.h b/src/pwcache.h index b6c0b67..d7c602d 100644 --- a/src/pwcache.h +++ b/src/pwcache.h @@ -27,9 +27,9 @@ struct bfs_users *bfs_users_new(void); /** * Get a user entry by name. * - * @param users + * @users * The user cache. - * @param name + * @name * The username to look up. * @return * The matching user, or NULL if not found (errno == 0) or an error @@ -40,9 +40,9 @@ const struct passwd *bfs_getpwnam(struct bfs_users *users, const char *name); /** * Get a user entry by ID. * - * @param users + * @users * The user cache. - * @param uid + * @uid * The ID to look up. * @return * The matching user, or NULL if not found (errno == 0) or an error @@ -53,7 +53,7 @@ const struct passwd *bfs_getpwuid(struct bfs_users *users, uid_t uid); /** * Flush a user cache. * - * @param users + * @users * The cache to flush. */ void bfs_users_flush(struct bfs_users *users); @@ -61,7 +61,7 @@ void bfs_users_flush(struct bfs_users *users); /** * Free a user cache. * - * @param users + * @users * The user cache to free. */ void bfs_users_free(struct bfs_users *users); @@ -82,9 +82,9 @@ struct bfs_groups *bfs_groups_new(void); /** * Get a group entry by name. * - * @param groups + * @groups * The group cache. - * @param name + * @name * The group name to look up. * @return * The matching group, or NULL if not found (errno == 0) or an error @@ -95,9 +95,9 @@ const struct group *bfs_getgrnam(struct bfs_groups *groups, const char *name); /** * Get a group entry by ID. * - * @param groups + * @groups * The group cache. - * @param uid + * @uid * The ID to look up. * @return * The matching group, or NULL if not found (errno == 0) or an error @@ -108,7 +108,7 @@ const struct group *bfs_getgrgid(struct bfs_groups *groups, gid_t gid); /** * Flush a group cache. * - * @param groups + * @groups * The cache to flush. */ void bfs_groups_flush(struct bfs_groups *groups); @@ -116,7 +116,7 @@ void bfs_groups_flush(struct bfs_groups *groups); /** * Free a group cache. * - * @param groups + * @groups * The group cache to free. */ void bfs_groups_free(struct bfs_groups *groups); diff --git a/src/sanity.h b/src/sanity.h index 0b770cf..cc8043f 100644 --- a/src/sanity.h +++ b/src/sanity.h @@ -8,16 +8,18 @@ #ifndef BFS_SANITY_H #define BFS_SANITY_H +#include "bfs.h" #include <stddef.h> -// Call macro(ptr, size) or macro(ptr, sizeof(*ptr)) -#define SANITIZE_CALL(...) \ - SANITIZE_CALL_(__VA_ARGS__, ) +/** Get the default size for a sanitize macro call. */ +#define SANITIZE_SIZE_(ptr, size) \ + BFS_VA_IF(size)(size)(sizeof(*ptr)) -#define SANITIZE_CALL_(macro, ptr, ...) \ - SANITIZE_CALL__(macro, ptr, __VA_ARGS__ sizeof(*(ptr)), ) +// Call macro(ptr, size) or macro(ptr, sizeof(*ptr)) +#define SANITIZE_CALL(macro, ptr, ...) \ + SANITIZE_CALL_(macro, ptr, SANITIZE_SIZE_(ptr, __VA_ARGS__)) -#define SANITIZE_CALL__(macro, ptr, size, ...) \ +#define SANITIZE_CALL_(macro, ptr, size) \ macro(ptr, size) #if __SANITIZE_ADDRESS__ @@ -37,9 +39,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_uninit -# define sanitize_free sanitize_uninit +# define sanitize_alloc(...) ((void)0) +# define sanitize_free(...) ((void)0) +# define sanitize_resize(ptr, old, new, cap) ((void)0) #endif #if __SANITIZE_MEMORY__ @@ -60,16 +80,11 @@ #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 /** - * Squelch unused variable warnings when not sanitizing. - */ -#define sanitize_ignore(ptr, size) ((void)(ptr), (void)(size)) - -/** * Initialize a variable, unless sanitizers would detect uninitialized uses. */ #if __SANITIZE_MEMORY__ diff --git a/src/sighook.c b/src/sighook.c index 4356fdb..42bd811 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,60 +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)]; } @@ -334,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 @@ -380,8 +423,10 @@ static bool is_fatal(int sig) { } /** Reraise a fatal signal. */ -_noreturn -static void reraise(int sig) { +[[_noreturn]] +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; @@ -395,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 @@ -443,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); @@ -486,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; } @@ -508,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; } @@ -556,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 74d18c0..7149229 100644 --- a/src/sighook.h +++ b/src/sighook.h @@ -21,17 +21,19 @@ struct sighook; enum sigflags { /** Suppress the default action for this signal. */ SH_CONTINUE = 1 << 0, + /** Only run this hook once. */ + SH_ONESHOT = 1 << 1, }; /** * A signal hook callback. Hooks are executed from a signal handler, so must * only call async-signal-safe functions. * - * @param sig + * @sig * The signal number. - * @param info + * @info * Additional information about the signal. - * @param arg + * @arg * An arbitrary pointer passed to the hook. */ typedef void sighook_fn(int sig, siginfo_t *info, void *arg); @@ -39,13 +41,13 @@ typedef void sighook_fn(int sig, siginfo_t *info, void *arg); /** * Install a hook for a signal. * - * @param sig + * @sig * The signal to hook. - * @param fn + * @fn * The function to call. - * @param arg + * @arg * An argument passed to the function. - * @param flags + * @flags * Flags for the new hook. * @return * The installed hook, or NULL on failure. @@ -56,9 +58,9 @@ struct sighook *sighook(int sig, sighook_fn *fn, void *arg, enum sigflags flags) * On a best-effort basis, invoke the given hook just before the program is * abnormally terminated by a signal. * - * @param fn + * @fn * The function to call. - * @param arg + * @arg * An argument passed to the function. * @return * The installed hook, or NULL on failure. @@ -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; @@ -119,14 +123,14 @@ struct bfs_stat { /** * Facade over fstatat(). * - * @param at_fd + * @at_fd * The base file descriptor for the lookup. - * @param at_path + * @at_path * The path to stat, relative to at_fd. Pass NULL to fstat() at_fd * itself. - * @param flags + * @flags * Flags that affect the lookup. - * @param[out] buf + * @buf[out] * A place to store the stat buffer, if successful. * @return * 0 on success, -1 on error. @@ -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..8607bca 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; \ @@ -20,18 +24,25 @@ } \ } while (0) -#define THREAD_INFALLIBLE(...) \ - THREAD_INFALLIBLE_(__VA_ARGS__, 0, ) +#define THREAD_INFALLIBLE(expr, ...) \ + THREAD_INFALLIBLE_(expr, BFS_VA_IF(__VA_ARGS__)(__VA_ARGS__)(0)) -#define THREAD_INFALLIBLE_(expr, allowed, ...) \ +#define THREAD_INFALLIBLE_(expr, allowed) \ int err = expr; \ - bfs_verify(err == 0 || err == allowed, "%s: %s", #expr, xstrerror(err)); \ - (void)0 + bfs_verify(err == 0 || err == allowed, "%s: %s", #expr, xstrerror(err)) int thread_create(pthread_t *thread, const pthread_attr_t *attr, thread_fn *fn, void *arg) { 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); @@ -129,37 +129,38 @@ struct trie_node { * tag to distinguish internal nodes from leaves. This is safe as long * as all dynamic allocations are aligned to more than a single byte. */ + // [[_counted_by(count_ones(bitmap))]] uintptr_t children[]; }; -/** Check if an encoded pointer is to a leaf. */ -static bool trie_is_leaf(uintptr_t ptr) { +/** Check if an encoded pointer is to an internal node. */ +static bool trie_is_node(uintptr_t ptr) { return ptr & 1; } -/** Decode a pointer to a leaf. */ -static struct trie_leaf *trie_decode_leaf(uintptr_t ptr) { - bfs_assert(trie_is_leaf(ptr)); - return (struct trie_leaf *)(ptr ^ 1); +/** Decode a pointer to an internal node. */ +static struct trie_node *trie_decode_node(uintptr_t ptr) { + bfs_assert(trie_is_node(ptr)); + return (struct trie_node *)(ptr - 1); } -/** Encode a pointer to a leaf. */ -static uintptr_t trie_encode_leaf(const struct trie_leaf *leaf) { - uintptr_t ptr = (uintptr_t)leaf ^ 1; - bfs_assert(trie_is_leaf(ptr)); +/** Encode a pointer to an internal node. */ +static uintptr_t trie_encode_node(const struct trie_node *node) { + uintptr_t ptr = (uintptr_t)node + 1; + bfs_assert(trie_is_node(ptr)); return ptr; } -/** Decode a pointer to an internal node. */ -static struct trie_node *trie_decode_node(uintptr_t ptr) { - bfs_assert(!trie_is_leaf(ptr)); - return (struct trie_node *)ptr; +/** Decode a pointer to a leaf. */ +static struct trie_leaf *trie_decode_leaf(uintptr_t ptr) { + bfs_assert(!trie_is_node(ptr)); + return (struct trie_leaf *)ptr; } -/** Encode a pointer to an internal node. */ -static uintptr_t trie_encode_node(const struct trie_node *node) { - uintptr_t ptr = (uintptr_t)node; - bfs_assert(!trie_is_leaf(ptr)); +/** Encode a pointer to a leaf. */ +static uintptr_t trie_encode_leaf(const struct trie_leaf *leaf) { + uintptr_t ptr = (uintptr_t)leaf; + bfs_assert(!trie_is_node(ptr)); return ptr; } @@ -171,20 +172,32 @@ 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 offset) { +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; } +/** Extract the nibble at a certain offset from a leaf. */ +static unsigned char trie_leaf_nibble(const struct trie_leaf *leaf, size_t offset) { + 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 @@ -192,26 +205,24 @@ static unsigned char trie_key_nibble(const void *key, size_t offset) { * that case, the first mismatch between the key and the representative will be * the depth at which to make a new branch to insert the key. */ -_trie_clones +[[_trie_clones]] static struct trie_leaf *trie_representative(const struct trie *trie, const void *key, size_t length) { uintptr_t ptr = trie->root; - if (!ptr) { - return NULL; - } - size_t offset = 0; - while (!trie_is_leaf(ptr)) { + 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) { - unsigned char nibble = trie_key_nibble(key, offset); + 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]; } @@ -223,7 +234,7 @@ struct trie_leaf *trie_find_str(const struct trie *trie, const char *key) { return trie_find_mem(trie, key, strlen(key) + 1); } -_trie_clones +[[_trie_clones]] static struct trie_leaf *trie_find_mem_impl(const struct trie *trie, const void *key, size_t length) { struct trie_leaf *rep = trie_representative(trie, key, length); if (rep && rep->length == length && memcmp(rep->key, key, length) == 0) { @@ -237,7 +248,17 @@ struct trie_leaf *trie_find_mem(const struct trie *trie, const void *key, size_t return trie_find_mem_impl(trie, key, length); } -_trie_clones +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); struct trie_leaf *rep = trie_representative(trie, key, length + 1); @@ -263,10 +284,10 @@ static struct trie_leaf *trie_terminal_leaf(const struct trie_node *node) { } uintptr_t ptr = node->children[0]; - if (trie_is_leaf(ptr)) { - return trie_decode_leaf(ptr); - } else { + if (trie_is_node(ptr)) { node = trie_decode_node(ptr); + } else { + return trie_decode_leaf(ptr); } } @@ -282,7 +303,7 @@ static bool trie_check_prefix(struct trie_leaf *leaf, size_t skip, const char *k } } -_trie_clones +[[_trie_clones]] static struct trie_leaf *trie_find_prefix_impl(const struct trie *trie, const char *key) { uintptr_t ptr = trie->root; if (!ptr) { @@ -293,21 +314,21 @@ 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; - while (!trie_is_leaf(ptr)) { + 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, offset); + unsigned char nibble = trie_key_nibble(key, length, offset); unsigned int bit = 1U << nibble; if (node->bitmap & bit) { unsigned int index = count_ones(node->bitmap & (bit - 1)); @@ -367,16 +388,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) { @@ -390,32 +405,34 @@ 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; + size_t ret = 0, i = 0; + +#define CHUNK(n) CHUNK_(uint##n##_t, load8_beu##n) +#define CHUNK_(type, load8) \ + (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); \ + } + +#if SIZE_WIDTH >= 64 + while CHUNK(64); + if CHUNK(32); #else - break; + while CHUNK(32); #endif - } - } + if CHUNK(16); + if CHUNK(8); - for (; i < length; ++i) { - unsigned char diff = rep_bytes[i] ^ key_bytes[i]; - if (diff) { - return 2 * i + !(diff & 0xF); - } - } +#undef CHUNK_ +#undef CHUNK - return 2 * i; + return ret; } /** @@ -440,10 +457,10 @@ static size_t trie_mismatch(const struct trie_leaf *rep, const void *key, size_t * | Z * +--->... */ -_trie_clones +[[_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)) { @@ -494,10 +511,10 @@ static struct trie_leaf *trie_node_insert(struct trie *trie, uintptr_t *ptr, str * | Y * +--->key */ -static uintptr_t *trie_jump(struct trie *trie, uintptr_t *ptr, const char *key, size_t *offset) { +static uintptr_t *trie_jump(struct trie *trie, uintptr_t *ptr, size_t *offset) { // We only ever need to jump to leaf nodes, since internal nodes are // guaranteed to be within OFFSET_MAX anyway - bfs_assert(trie_is_leaf(*ptr)); + struct trie_leaf *leaf = trie_decode_leaf(*ptr); struct trie_node *node = trie_node_alloc(trie, 1); if (!node) { @@ -507,7 +524,7 @@ static uintptr_t *trie_jump(struct trie *trie, uintptr_t *ptr, const char *key, *offset += OFFSET_MAX; node->offset = OFFSET_MAX; - unsigned char nibble = trie_key_nibble(key, *offset); + unsigned char nibble = trie_leaf_nibble(leaf, *offset); node->bitmap = 1 << nibble; node->children[0] = *ptr; @@ -533,8 +550,8 @@ static uintptr_t *trie_jump(struct trie *trie, uintptr_t *ptr, const char *key, * +--->leaf */ static struct trie_leaf *trie_split(struct trie *trie, uintptr_t *ptr, struct trie_leaf *leaf, struct trie_leaf *rep, size_t offset, size_t mismatch) { - unsigned char key_nibble = trie_key_nibble(leaf->key, mismatch); - unsigned char rep_nibble = trie_key_nibble(rep->key, mismatch); + unsigned char key_nibble = trie_leaf_nibble(leaf, mismatch); + unsigned char rep_nibble = trie_leaf_nibble(rep, mismatch); bfs_assert(key_nibble != rep_nibble); struct trie_node *node = trie_node_alloc(trie, 2); @@ -546,7 +563,7 @@ static struct trie_leaf *trie_split(struct trie *trie, uintptr_t *ptr, struct tr node->bitmap = (1 << key_nibble) | (1 << rep_nibble); size_t delta = mismatch - offset; - if (!trie_is_leaf(*ptr)) { + if (trie_is_node(*ptr)) { struct trie_node *child = trie_decode_node(*ptr); child->offset -= delta; } @@ -563,12 +580,18 @@ struct trie_leaf *trie_insert_str(struct trie *trie, const char *key) { return trie_insert_mem(trie, key, strlen(key) + 1); } -_trie_clones +[[_trie_clones]] static struct trie_leaf *trie_insert_mem_impl(struct trie *trie, const void *key, size_t length) { struct trie_leaf *rep = trie_representative(trie, key, length); size_t mismatch = trie_mismatch(rep, key, length); - if (mismatch >= (length << 1)) { + size_t misbyte = mismatch / 2; + if (misbyte >= length) { + bfs_assert(misbyte == length); return rep; + } else if (rep && misbyte >= rep->length) { + bfs_bug("trie keys must be prefix-free"); + errno = EINVAL; + return NULL; } struct trie_leaf *leaf = trie_leaf_alloc(trie, key, length); @@ -583,14 +606,14 @@ static struct trie_leaf *trie_insert_mem_impl(struct trie *trie, const void *key size_t offset = 0; uintptr_t *ptr = &trie->root; - while (!trie_is_leaf(*ptr)) { + while (trie_is_node(*ptr)) { struct trie_node *node = trie_decode_node(*ptr); if (offset + node->offset > mismatch) { break; } offset += node->offset; - unsigned char nibble = trie_key_nibble(key, offset); + unsigned char nibble = trie_leaf_nibble(leaf, offset); unsigned int bit = 1U << nibble; if (node->bitmap & bit) { bfs_assert(offset < mismatch); @@ -603,7 +626,7 @@ static struct trie_leaf *trie_insert_mem_impl(struct trie *trie, const void *key } while (mismatch - offset > OFFSET_MAX) { - ptr = trie_jump(trie, ptr, key, &offset); + ptr = trie_jump(trie, ptr, &offset); if (!ptr) { trie_leaf_free(trie, leaf); return NULL; @@ -617,9 +640,29 @@ 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_leaf(ptr)) { + while (trie_is_node(ptr)) { struct trie_node *node = trie_decode_node(ptr); // Make sure the bitmap is a power of two, i.e. it has just one child @@ -651,7 +694,7 @@ static void trie_free_singletons(struct trie *trie, uintptr_t ptr) { */ static int trie_collapse_node(struct trie *trie, uintptr_t *parent, struct trie_node *parent_node, unsigned int child_index) { uintptr_t other = parent_node->children[child_index ^ 1]; - if (!trie_is_leaf(other)) { + if (trie_is_node(other)) { struct trie_node *other_node = trie_decode_node(other); if (other_node->offset + parent_node->offset <= OFFSET_MAX) { other_node->offset += parent_node->offset; @@ -661,22 +704,21 @@ static int trie_collapse_node(struct trie *trie, uintptr_t *parent, struct trie_ } *parent = other; - trie_node_free(trie, parent_node, 1); + trie_node_free(trie, parent_node, 2); return 0; } -_trie_clones +[[_trie_clones]] static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) { uintptr_t *child = &trie->root; uintptr_t *parent = NULL; unsigned int child_bit = 0, child_index = 0; size_t offset = 0; - while (!trie_is_leaf(*child)) { + while (trie_is_node(*child)) { struct trie_node *node = trie_decode_node(*child); offset += node->offset; - bfs_assert((offset >> 1) < leaf->length); - unsigned char nibble = trie_key_nibble(leaf->key, offset); + unsigned char nibble = trie_leaf_nibble(leaf, offset); unsigned int bit = 1U << nibble; unsigned int bitmap = node->bitmap; bfs_assert(bitmap & bit); @@ -701,19 +743,19 @@ static void trie_remove_impl(struct trie *trie, struct trie_leaf *leaf) { } struct trie_node *node = trie_decode_node(*parent); - child = node->children + child_index; - trie_free_singletons(trie, *child); + trie_free_singletons(trie, node->children[child_index]); - node->bitmap ^= child_bit; - unsigned int parent_size = count_ones(node->bitmap); - bfs_assert(parent_size > 0); - if (parent_size == 1 && trie_collapse_node(trie, parent, node, child_index) == 0) { + 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; } - if (child_index < parent_size) { - memmove(child, child + 1, (parent_size - child_index) * sizeof(*child)); + for (size_t i = child_index; i + 1 < parent_size; ++i) { + node->children[i] = node->children[i + 1]; } + node->bitmap &= ~child_bit; + --parent_size; if (has_single_bit(parent_size)) { node = trie_node_realloc(trie, node, 2 * parent_size, parent_size); @@ -21,6 +21,7 @@ struct trie_leaf { /** The length of the key in bytes. */ size_t length; /** The key itself, stored inline. */ + [[_counted_by(length)]] char key[]; }; @@ -46,9 +47,9 @@ void trie_init(struct trie *trie); /** * Find the leaf for a string key. * - * @param trie + * @trie * The trie to search. - * @param key + * @key * The key to look up. * @return * The found leaf, or NULL if the key is not present. @@ -58,11 +59,11 @@ struct trie_leaf *trie_find_str(const struct trie *trie, const char *key); /** * Find the leaf for a fixed-size key. * - * @param trie + * @trie * The trie to search. - * @param key + * @key * The key to look up. - * @param length + * @length * The length of the key in bytes. * @return * The found leaf, or NULL if the key is not present. @@ -70,11 +71,37 @@ 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. * - * @param trie + * @trie * The trie to search. - * @param key + * @key * The key to look up. * @return * A leaf that starts with the given key, or NULL. @@ -84,9 +111,9 @@ struct trie_leaf *trie_find_postfix(const struct trie *trie, const char *key); /** * Find the leaf that is the longest prefix of the given key. * - * @param trie + * @trie * The trie to search. - * @param key + * @key * The key to look up. * @return * The longest prefix match for the given key, or NULL. @@ -96,9 +123,9 @@ struct trie_leaf *trie_find_prefix(const struct trie *trie, const char *key); /** * Insert a string key into the trie. * - * @param trie + * @trie * The trie to modify. - * @param key + * @key * The key to insert. * @return * The inserted leaf, or NULL on failure. @@ -108,11 +135,11 @@ struct trie_leaf *trie_insert_str(struct trie *trie, const char *key); /** * Insert a fixed-size key into the trie. * - * @param trie + * @trie * The trie to modify. - * @param key + * @key * The key to insert. - * @param length + * @length * The length of the key in bytes. * @return * The inserted leaf, or NULL on failure. @@ -120,11 +147,41 @@ 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. * - * @param trie + * @trie * The trie to modify. - * @param leaf + * @leaf * The leaf to remove. */ void trie_remove(struct trie *trie, struct trie_leaf *leaf); @@ -7,9 +7,9 @@ /** * Find the "typo" distance between two strings. * - * @param actual + * @actual * The actual string typed by the user. - * @param expected + * @expected * The expected valid string. * @return The distance between the two strings. */ diff --git a/src/xregex.h b/src/xregex.h index 750db24..c4504ee 100644 --- a/src/xregex.h +++ b/src/xregex.h @@ -42,13 +42,13 @@ enum bfs_regexec_flags { /** * Wrapper for regcomp() that supports additional regex types. * - * @param[out] preg + * @preg[out] * Will hold the compiled regex. - * @param pattern + * @pattern * The regular expression to compile. - * @param type + * @type * The regular expression syntax to use. - * @param flags + * @flags * Regex compilation flags. * @return * 0 on success, -1 on failure. @@ -58,11 +58,11 @@ int bfs_regcomp(struct bfs_regex **preg, const char *pattern, enum bfs_regex_typ /** * Wrapper for regexec(). * - * @param regex + * @regex * The regular expression to execute. - * @param str + * @str * The string to match against. - * @param flags + * @flags * Regex execution flags. * @return * 1 for a match, 0 for no match, -1 on failure. @@ -77,7 +77,7 @@ void bfs_regfree(struct bfs_regex *regex); /** * Get a human-readable regex error message. * - * @param regex + * @regex * The compiled regex. * @return * A human-readable description of the error, which should be free()'d. diff --git a/src/xspawn.c b/src/xspawn.c index b3eed79..efa2219 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> @@ -118,7 +119,7 @@ int bfs_spawn_destroy(struct bfs_spawn *ctx) { #if BFS_POSIX_SPAWN >= 0 /** Set some posix_spawnattr flags. */ -_maybe_unused +[[_maybe_unused]] static int bfs_spawn_addflags(struct bfs_spawn *ctx, short flags) { short prev; errno = posix_spawnattr_getflags(&ctx->attr, &prev); @@ -231,12 +232,28 @@ int bfs_spawn_adddup2(struct bfs_spawn *ctx, int oldfd, int newfd) { */ #define BFS_POSIX_SPAWNP_AFTER_FCHDIR !(__APPLE__ || __NetBSD__) +/** + * NetBSD even resolves the executable before file actions with posix_spawn()! + */ +#define BFS_POSIX_SPAWN_AFTER_FCHDIR !__NetBSD__ + int bfs_spawn_addfchdir(struct bfs_spawn *ctx, int fd) { struct bfs_spawn_action *action = bfs_spawn_action(BFS_SPAWN_FCHDIR); if (!action) { return -1; } +#if __APPLE__ + // macOS has a bug that causes EBADF when an fchdir() action refers to a + // file opened by the file actions + for_slist (struct bfs_spawn_action, prev, ctx) { + if (fd == prev->out_fd) { + bfs_spawn_clear_posix(ctx); + break; + } + } +#endif + #if BFS_HAS_POSIX_SPAWN_ADDFCHDIR # define BFS_POSIX_SPAWN_ADDFCHDIR posix_spawn_file_actions_addfchdir #elif BFS_HAS_POSIX_SPAWN_ADDFCHDIR_NP @@ -400,18 +417,40 @@ static bool bfs_resolve_relative(const struct bfs_resolver *res) { return false; } +/** Check if the actions include fchdir(). */ +static bool bfs_spawn_will_chdir(const struct bfs_spawn *ctx) { + if (ctx) { + for_slist (const struct bfs_spawn_action, action, ctx) { + if (action->op == BFS_SPAWN_FCHDIR) { + return true; + } + } + } + + return false; +} + +/** Check if we can call xfaccessat() before file actions. */ +static bool bfs_can_access_early(const struct bfs_resolver *res, const struct bfs_spawn *ctx) { + if (res->exe[0] == '/') { + return true; + } + + if (bfs_spawn_will_chdir(ctx)) { + return false; + } + + return true; +} + /** Check if we can resolve the executable before file actions. */ static bool bfs_can_resolve_early(const struct bfs_resolver *res, const struct bfs_spawn *ctx) { if (!bfs_resolve_relative(res)) { return true; } - if (ctx) { - for_slist (const struct bfs_spawn_action, action, ctx) { - if (action->op == BFS_SPAWN_FCHDIR) { - return false; - } - } + if (bfs_spawn_will_chdir(ctx)) { + return false; } return true; @@ -441,17 +480,19 @@ static int bfs_resolve_early(struct bfs_resolver *res, const char *exe, const st }; if (bfs_can_skip_resolve(res, ctx)) { - // Do this check eagerly, even though posix_spawn()/execv() also - // would, because: - // - // - faccessat() is faster than fork()/clone() + execv() - // - posix_spawn() is not guaranteed to report ENOENT - if (xfaccessat(AT_FDCWD, exe, X_OK) == 0) { - res->done = true; - return 0; - } else { - return -1; + if (bfs_can_access_early(res, ctx)) { + // Do this check eagerly, even though posix_spawn()/execv() also + // would, because: + // + // - faccessat() is faster than fork()/clone() + execv() + // - posix_spawn() is not guaranteed to report ENOENT + if (xfaccessat(AT_FDCWD, exe, X_OK) != 0) { + return -1; + } } + + res->done = true; + return 0; } res->path = getenv("PATH"); @@ -528,14 +569,20 @@ static bool bfs_use_posix_spawn(const struct bfs_resolver *res, const struct bfs } #endif +#if !BFS_POSIX_SPAWN_AFTER_FCHDIR + if (res->exe[0] != '/' && bfs_spawn_will_chdir(ctx)) { + return false; + } +#endif + return true; } #endif // BFS_POSIX_SPAWN >= 0 /** 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]) { +[[_noreturn]] +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 +643,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 +694,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/xspawn.h b/src/xspawn.h index 9cfbaf7..3c74ccd 100644 --- a/src/xspawn.h +++ b/src/xspawn.h @@ -109,13 +109,13 @@ int bfs_spawn_setrlimit(struct bfs_spawn *ctx, int resource, const struct rlimit /** * Spawn a new process. * - * @param exe + * @exe * The executable to run. - * @param ctx + * @ctx * The context for the new process. - * @param argv + * @argv * The arguments for the new process. - * @param envp + * @envp * The environment variables for the new process (NULL for the current * environment). * @return @@ -127,7 +127,7 @@ pid_t bfs_spawn(const char *exe, const struct bfs_spawn *ctx, char **argv, char * Look up an executable in the current PATH, as BFS_SPAWN_USE_PATH or execvp() * would do. * - * @param exe + * @exe * The name of the binary to execute. Bare names without a '/' will be * searched on the provided PATH. * @return diff --git a/src/xtime.c b/src/xtime.c index dd9b60f..6b8a141 100644 --- a/src/xtime.c +++ b/src/xtime.c @@ -3,9 +3,11 @@ #include "xtime.h" +#include "alloc.h" #include "bfs.h" #include "bfstd.h" #include "diag.h" +#include "sanity.h" #include <errno.h> #include <limits.h> @@ -351,3 +353,151 @@ invalid: 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 +# define BFS_POSIX_TIMERS (-1) +#endif + +struct timer { +#if BFS_POSIX_TIMERS >= 0 + /** The POSIX timer. */ + timer_t timer; +#endif + /** Whether to use timer_create() or setitimer(). */ + bool legacy; +}; + +struct timer *xtimer_start(const struct timespec *interval) { + struct timer *timer = ALLOC(struct timer); + if (!timer) { + return NULL; + } + +#if BFS_POSIX_TIMERS >= 0 + if (sysoption(TIMERS)) { + clockid_t clock = CLOCK_REALTIME; + +#if defined(_POSIX_MONOTONIC_CLOCK) && _POSIX_MONOTONIC_CLOCK >= 0 + if (sysoption(MONOTONIC_CLOCK) > 0) { + clock = CLOCK_MONOTONIC; + } +#endif + + if (timer_create(clock, NULL, &timer->timer) != 0) { + goto fail; + } + + // https://github.com/llvm/llvm-project/issues/111847 + sanitize_init(&timer->timer); + + struct itimerspec spec = { + .it_value = *interval, + .it_interval = *interval, + }; + if (timer_settime(timer->timer, 0, &spec, NULL) != 0) { + timer_delete(timer->timer); + goto fail; + } + + timer->legacy = false; + return timer; + } +#endif + +#if BFS_POSIX_TIMERS <= 0 + struct timeval tv = { + .tv_sec = interval->tv_sec, + .tv_usec = (interval->tv_nsec + 999) / 1000, + }; + struct itimerval ival = { + .it_value = tv, + .it_interval = tv, + }; + if (setitimer(ITIMER_REAL, &ival, NULL) != 0) { + goto fail; + } + + timer->legacy = true; + return timer; +#endif + +fail: + free(timer); + return NULL; +} + +void xtimer_stop(struct timer *timer) { + if (!timer) { + return; + } + + if (timer->legacy) { +#if BFS_POSIX_TIMERS <= 0 + struct itimerval ival = {0}; + int ret = setitimer(ITIMER_REAL, &ival, NULL); + bfs_everify(ret == 0, "setitimer()"); +#endif + } else { +#if BFS_POSIX_TIMERS >= 0 + int ret = timer_delete(timer->timer); + bfs_everify(ret == 0, "timer_delete()"); +#endif + } + + free(timer); +} diff --git a/src/xtime.h b/src/xtime.h index a3547a7..b76fef2 100644 --- a/src/xtime.h +++ b/src/xtime.h @@ -13,9 +13,9 @@ /** * mktime() wrapper that reports errors more reliably. * - * @param[in,out] tm - * The struct tm to convert. - * @param[out] timep + * @tm[in,out] + * The struct tm to convert and normalize. + * @timep[out] * A pointer to the result. * @return * 0 on success, -1 on failure. @@ -25,9 +25,9 @@ int xmktime(struct tm *tm, time_t *timep); /** * A portable timegm(), the inverse of gmtime(). * - * @param[in,out] tm - * The struct tm to convert. - * @param[out] timep + * @tm[in,out] + * The struct tm to convert and normalize. + * @timep[out] * A pointer to the result. * @return * 0 on success, -1 on failure. @@ -37,13 +37,72 @@ int xtimegm(struct tm *tm, time_t *timep); /** * Parse an ISO 8601-style timestamp. * - * @param[in] str + * @str * The string to parse. - * @param[out] result + * @result[out] * A pointer to the result. * @return * 0 on success, -1 on failure. */ 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; + +/** + * Start a timer. + * + * @interval + * The regular interval at which to send SIGALRM. + * @return + * The new timer on success, otherwise NULL. + */ +struct timer *xtimer_start(const struct timespec *interval); + +/** + * Stop a timer. + * + * @timer + * The timer to stop. + */ +void xtimer_stop(struct timer *timer); + #endif // BFS_XTIME_H |