src/bftw.c

   1 // Copyright © Tavian Barnes <tavianator@tavianator.com>
   2 // SPDX-License-Identifier: 0BSD
   3
   4 /**
   5  * The bftw() implementation consists of the following components:
   6  *
   7  * - struct bftw_file: A file that has been encountered during the traversal.
   8  *   They have reference-counted links to their parents in the directory tree.
   9  *
  10  * - struct bftw_list: A linked list of bftw_file's.
  11  *
  12  * - struct bftw_cache: An LRU list of bftw_file's with open file descriptors,
  13  *   used for openat() to minimize the amount of path re-traversals.
  14  *
  15  * - struct bftw_state: Represents the current state of the traversal, allowing
  16  *   various helper functions to take fewer parameters.
  17  */
  18
  19 #include "bftw.h"
  20 #include "alloc.h"
  21 #include "bfstd.h"
  22 #include "config.h"
  23 #include "diag.h"
  24 #include "dir.h"
  25 #include "dstring.h"
  26 #include "ioq.h"
  27 #include "list.h"
  28 #include "mtab.h"
  29 #include "stat.h"
  30 #include "trie.h"
  31 #include <errno.h>
  32 #include <fcntl.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35 #include <sys/stat.h>
  36
  37 /** Caching bfs_stat(). */
  38 static const struct bfs_stat *bftw_stat_impl(struct BFTW *ftwbuf, struct bftw_stat *cache, enum bfs_stat_flags flags) {
  39         if (!cache->buf) {
  40                 if (cache->error) {
  41                         errno = cache->error;
  42                 } else if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, flags, &cache->storage) == 0) {
  43                         cache->buf = &cache->storage;
  44 #ifdef S_IFWHT
  45                 } else if (errno == ENOENT && ftwbuf->type == BFS_WHT) {
  46                         // This matches the behavior of FTS_WHITEOUT on BSD
  47                         memset(&cache->storage, 0, sizeof(cache->storage));
  48                         cache->storage.mode = S_IFWHT;
  49                         cache->buf = &cache->storage;
  50 #endif
  51                 } else {
  52                         cache->error = errno;
  53                 }
  54         }
  55
  56         return cache->buf;
  57 }
  58
  59 const struct bfs_stat *bftw_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
  60         struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
  61         const struct bfs_stat *ret;
  62
  63         if (flags & BFS_STAT_NOFOLLOW) {
  64                 ret = bftw_stat_impl(mutbuf, &mutbuf->lstat_cache, BFS_STAT_NOFOLLOW);
  65                 if (ret && !S_ISLNK(ret->mode) && !mutbuf->stat_cache.buf) {
  66                         // Non-link, so share stat info
  67                         mutbuf->stat_cache.buf = ret;
  68                 }
  69         } else {
  70                 ret = bftw_stat_impl(mutbuf, &mutbuf->stat_cache, BFS_STAT_FOLLOW);
  71                 if (!ret && (flags & BFS_STAT_TRYFOLLOW) && is_nonexistence_error(errno)) {
  72                         ret = bftw_stat_impl(mutbuf, &mutbuf->lstat_cache, BFS_STAT_NOFOLLOW);
  73                 }
  74         }
  75
  76         return ret;
  77 }
  78
  79 const struct bfs_stat *bftw_cached_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
  80         if (flags & BFS_STAT_NOFOLLOW) {
  81                 return ftwbuf->lstat_cache.buf;
  82         } else if (ftwbuf->stat_cache.buf) {
  83                 return ftwbuf->stat_cache.buf;
  84         } else if ((flags & BFS_STAT_TRYFOLLOW) && is_nonexistence_error(ftwbuf->stat_cache.error)) {
  85                 return ftwbuf->lstat_cache.buf;
  86         } else {
  87                 return NULL;
  88         }
  89 }
  90
  91 enum bfs_type bftw_type(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
  92         if (flags & BFS_STAT_NOFOLLOW) {
  93                 if (ftwbuf->type == BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
  94                         return ftwbuf->type;
  95                 }
  96         } else if (flags & BFS_STAT_TRYFOLLOW) {
  97                 if (ftwbuf->type != BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW)) {
  98                         return ftwbuf->type;
  99                 }
 100         } else {
 101                 if (ftwbuf->type != BFS_LNK) {
 102                         return ftwbuf->type;
 103                 } else if (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW) {
 104                         return BFS_ERROR;
 105                 }
 106         }
 107
 108         const struct bfs_stat *statbuf = bftw_stat(ftwbuf, flags);
 109         if (statbuf) {
 110                 return bfs_mode_to_type(statbuf->mode);
 111         } else {
 112                 return BFS_ERROR;
 113         }
 114 }
 115
 116 /**
 117  * A file.
 118  */
 119 struct bftw_file {
 120         /** The parent directory, if any. */
 121         struct bftw_file *parent;
 122         /** The root under which this file was found. */
 123         struct bftw_file *root;
 124
 125         /** The next file to open/close/visit. */
 126         struct bftw_file *next;
 127         /** The next directory to read. */
 128         struct { struct bftw_file *next; } to_read;
 129
 130         /** LRU list node. */
 131         struct {
 132                 struct bftw_file *prev;
 133                 struct bftw_file *next;
 134         } lru;
 135
 136         /** This file's depth in the walk. */
 137         size_t depth;
 138         /** Reference count (for ->parent). */
 139         size_t refcount;
 140
 141         /** Pin count (for ->fd). */
 142         size_t pincount;
 143         /** An open descriptor to this file, or -1. */
 144         int fd;
 145         /** Whether this file has a pending ioq request. */
 146         bool ioqueued;
 147         /** An open directory for this file, if any. */
 148         struct bfs_dir *dir;
 149
 150         /** This file's type, if known. */
 151         enum bfs_type type;
 152         /** The device number, for cycle detection. */
 153         dev_t dev;
 154         /** The inode number, for cycle detection. */
 155         ino_t ino;
 156
 157         /** The offset of this file in the full path. */
 158         size_t nameoff;
 159         /** The length of the file's name. */
 160         size_t namelen;
 161         /** The file's name. */
 162         char name[];
 163 };
 164
 165 /**
 166  * A linked list of bftw_file's.
 167  */
 168 struct bftw_list {
 169         struct bftw_file *head;
 170         struct bftw_file **tail;
 171 };
 172
 173 /**
 174  * A cache of open directories.
 175  */
 176 struct bftw_cache {
 177         /** The head of the LRU list. */
 178         struct bftw_file *head;
 179         /** The tail of the LRU list. */
 180         struct bftw_file *tail;
 181         /** The insertion target for the LRU list. */
 182         struct bftw_file *target;
 183         /** The remaining capacity of the LRU list. */
 184         size_t capacity;
 185
 186         /** bftw_file arena. */
 187         struct varena files;
 188         /** bfs_dir arena. */
 189         struct arena dirs;
 190         /** Remaining bfs_dir capacity. */
 191         size_t dirlimit;
 192 };
 193
 194 /** Initialize a cache. */
 195 static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
 196         LIST_INIT(cache);
 197         cache->target = NULL;
 198         cache->capacity = capacity;
 199
 200         VARENA_INIT(&cache->files, struct bftw_file, name);
 201         bfs_dir_arena(&cache->dirs);
 202
 203         cache->dirlimit = capacity - 1;
 204         if (cache->dirlimit > 1024) {
 205                 cache->dirlimit = 1024;
 206         }
 207 }
 208
 209 /** Allocate a directory. */
 210 static struct bfs_dir *bftw_allocdir(struct bftw_cache *cache) {
 211         if (cache->dirlimit == 0) {
 212                 errno = ENOMEM;
 213                 return NULL;
 214         }
 215         --cache->dirlimit;
 216
 217         return arena_alloc(&cache->dirs);
 218 }
 219
 220 /** Free a directory. */
 221 static void bftw_freedir(struct bftw_cache *cache, struct bfs_dir *dir) {
 222         ++cache->dirlimit;
 223         arena_free(&cache->dirs, dir);
 224 }
 225
 226 /** Remove a bftw_file from the LRU list. */
 227 static void bftw_lru_remove(struct bftw_cache *cache, struct bftw_file *file) {
 228         if (cache->target == file) {
 229                 cache->target = file->lru.prev;
 230         }
 231
 232         LIST_REMOVE(cache, file, lru);
 233 }
 234
 235 /** Remove a bftw_file from the cache. */
 236 static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) {
 237         bftw_lru_remove(cache, file);
 238         ++cache->capacity;
 239 }
 240
 241 /** Close a bftw_file. */
 242 static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) {
 243         bfs_assert(file->fd >= 0);
 244         bfs_assert(file->pincount == 0);
 245
 246         if (file->dir) {
 247                 bfs_closedir(file->dir);
 248                 bftw_freedir(cache, file->dir);
 249                 file->dir = NULL;
 250         } else {
 251                 xclose(file->fd);
 252         }
 253
 254         file->fd = -1;
 255         bftw_cache_remove(cache, file);
 256 }
 257
 258 /** Pop the least recently used directory from the cache. */
 259 static int bftw_cache_pop(struct bftw_cache *cache) {
 260         struct bftw_file *file = cache->tail;
 261         if (!file) {
 262                 return -1;
 263         }
 264
 265         bftw_file_close(cache, file);
 266         return 0;
 267 }
 268
 269 /** Add a bftw_file to the LRU list. */
 270 static void bftw_lru_add(struct bftw_cache *cache, struct bftw_file *file) {
 271         bfs_assert(file->fd >= 0);
 272
 273         LIST_INSERT(cache, cache->target, file, lru);
 274
 275         // Prefer to keep the root paths open by keeping them at the head of the list
 276         if (file->depth == 0) {
 277                 cache->target = file;
 278         }
 279 }
 280
 281 /** Add a bftw_file to the cache. */
 282 static int bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) {
 283         bfs_assert(file->fd >= 0);
 284
 285         if (cache->capacity == 0 && bftw_cache_pop(cache) != 0) {
 286                 bftw_file_close(cache, file);
 287                 errno = EMFILE;
 288                 return -1;
 289         }
 290
 291         bfs_assert(cache->capacity > 0);
 292         --cache->capacity;
 293
 294         bftw_lru_add(cache, file);
 295         return 0;
 296 }
 297
 298 /** Pin a cache entry so it won't be closed. */
 299 static void bftw_cache_pin(struct bftw_cache *cache, struct bftw_file *file) {
 300         bfs_assert(file->fd >= 0);
 301
 302         if (file->pincount++ == 0) {
 303                 bftw_lru_remove(cache, file);
 304         }
 305 }
 306
 307 /** Unpin a cache entry. */
 308 static void bftw_cache_unpin(struct bftw_cache *cache, struct bftw_file *file) {
 309         bfs_assert(file->fd >= 0);
 310         bfs_assert(file->pincount > 0);
 311
 312         if (--file->pincount == 0) {
 313                 bftw_lru_add(cache, file);
 314         }
 315 }
 316
 317 /** Compute the name offset of a child path. */
 318 static size_t bftw_child_nameoff(const struct bftw_file *parent) {
 319         size_t ret = parent->nameoff + parent->namelen;
 320         if (parent->name[parent->namelen - 1] != '/') {
 321                 ++ret;
 322         }
 323         return ret;
 324 }
 325
 326 /** Destroy a cache. */
 327 static void bftw_cache_destroy(struct bftw_cache *cache) {
 328         bfs_assert(LIST_EMPTY(cache));
 329         bfs_assert(!cache->target);
 330
 331         varena_destroy(&cache->files);
 332         arena_destroy(&cache->dirs);
 333 }
 334
 335 /** Create a new bftw_file. */
 336 static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_file *parent, const char *name) {
 337         size_t namelen = strlen(name);
 338         struct bftw_file *file = varena_alloc(&cache->files, namelen + 1);
 339         if (!file) {
 340                 return NULL;
 341         }
 342
 343         file->parent = parent;
 344
 345         if (parent) {
 346                 file->root = parent->root;
 347                 file->depth = parent->depth + 1;
 348                 file->nameoff = bftw_child_nameoff(parent);
 349                 ++parent->refcount;
 350         } else {
 351                 file->root = file;
 352                 file->depth = 0;
 353                 file->nameoff = 0;
 354         }
 355
 356         SLIST_ITEM_INIT(file);
 357         SLIST_ITEM_INIT(file, to_read);
 358         LIST_ITEM_INIT(file, lru);
 359
 360         file->refcount = 1;
 361         file->pincount = 0;
 362         file->fd = -1;
 363         file->ioqueued = false;
 364         file->dir = NULL;
 365
 366         file->type = BFS_UNKNOWN;
 367         file->dev = -1;
 368         file->ino = -1;
 369
 370         file->namelen = namelen;
 371         memcpy(file->name, name, namelen + 1);
 372
 373         return file;
 374 }
 375
 376 /** Associate an open directory with a bftw_file. */
 377 static void bftw_file_set_dir(struct bftw_cache *cache, struct bftw_file *file, struct bfs_dir *dir) {
 378         bfs_assert(!file->dir);
 379         file->dir = dir;
 380
 381         if (file->fd >= 0) {
 382                 bfs_assert(file->fd == bfs_dirfd(dir));
 383         } else {
 384                 file->fd = bfs_dirfd(dir);
 385                 bftw_cache_add(cache, file);
 386         }
 387
 388         bftw_cache_pin(cache, file);
 389 }
 390
 391 /** Free a bftw_file. */
 392 static void bftw_file_free(struct bftw_cache *cache, struct bftw_file *file) {
 393         bfs_assert(file->refcount == 0);
 394
 395         if (file->fd >= 0) {
 396                 bftw_file_close(cache, file);
 397         }
 398
 399         varena_free(&cache->files, file, file->namelen + 1);
 400 }
 401
 402 /**
 403  * Holds the current state of the bftw() traversal.
 404  */
 405 struct bftw_state {
 406         /** The path(s) to start from. */
 407         const char **paths;
 408         /** The number of starting paths. */
 409         size_t npaths;
 410         /** bftw() callback. */
 411         bftw_callback *callback;
 412         /** bftw() callback data. */
 413         void *ptr;
 414         /** bftw() flags. */
 415         enum bftw_flags flags;
 416         /** Search strategy. */
 417         enum bftw_strategy strategy;
 418         /** The mount table. */
 419         const struct bfs_mtab *mtab;
 420         /** bfs_opendir() flags. */
 421         enum bfs_dir_flags dir_flags;
 422
 423         /** The appropriate errno value, if any. */
 424         int error;
 425
 426         /** The cache of open directories. */
 427         struct bftw_cache cache;
 428
 429         /** The async I/O queue. */
 430         struct ioq *ioq;
 431         /** The number of I/O threads. */
 432         size_t nthreads;
 433         /** Tracks the imbalance between main thread and background I/O. */
 434         long imbalance;
 435
 436         /** A batch of directories to open. */
 437         struct bftw_list dir_batch;
 438         /** The queue of directories to open. */
 439         struct bftw_list to_open;
 440         /** The queue of directories to read. */
 441         struct bftw_list to_read;
 442         /** The queue of unpinned directories to unwrap. */
 443         struct bftw_list to_close;
 444
 445         /** A batch of files to enqueue. */
 446         struct bftw_list file_batch;
 447         /** The queue of files to visit. */
 448         struct bftw_list to_visit;
 449
 450         /** The current path. */
 451         dchar *path;
 452         /** The current file. */
 453         struct bftw_file *file;
 454         /** The previous file. */
 455         struct bftw_file *previous;
 456
 457         /** The currently open directory. */
 458         struct bfs_dir *dir;
 459         /** The current directory entry. */
 460         struct bfs_dirent *de;
 461         /** Storage for the directory entry. */
 462         struct bfs_dirent de_storage;
 463         /** Any error encountered while reading the directory. */
 464         int direrror;
 465
 466         /** Extra data about the current file. */
 467         struct BFTW ftwbuf;
 468 };
 469
 470 /** Check if we have to buffer files before visiting them. */
 471 static bool bftw_must_buffer(const struct bftw_state *state) {
 472         if (state->flags & BFTW_SORT) {
 473                 // Have to buffer the files to sort them
 474                 return true;
 475         }
 476
 477         if (state->strategy == BFTW_DFS && state->nthreads == 0) {
 478                 // Without buffering, we would get a not-quite-depth-first
 479                 // ordering:
 480                 //
 481                 //     a
 482                 //     b
 483                 //     a/c
 484                 //     a/c/d
 485                 //     b/e
 486                 //     b/e/f
 487                 //
 488                 // This is okay for iterative deepening, since the caller only
 489                 // sees files at the target depth.  We also deem it okay for
 490                 // parallel searches, since the order is unpredictable anyway.
 491                 return true;
 492         }
 493
 494         return false;
 495 }
 496
 497 /** Initialize the bftw() state. */
 498 static int bftw_state_init(struct bftw_state *state, const struct bftw_args *args) {
 499         state->paths = args->paths;
 500         state->npaths = args->npaths;
 501         state->callback = args->callback;
 502         state->ptr = args->ptr;
 503         state->flags = args->flags;
 504         state->strategy = args->strategy;
 505         state->mtab = args->mtab;
 506         state->dir_flags = 0;
 507         state->error = 0;
 508
 509         if (args->nopenfd < 2) {
 510                 errno = EMFILE;
 511                 return -1;
 512         }
 513
 514         size_t nopenfd = args->nopenfd;
 515         size_t qdepth = 4096;
 516         size_t nthreads = args->nthreads;
 517
 518 #if BFS_USE_LIBURING
 519         // io_uring uses one fd per ring, ioq uses one ring per thread
 520         if (nthreads >= nopenfd - 1) {
 521                 nthreads = nopenfd - 2;
 522         }
 523         nopenfd -= nthreads;
 524 #endif
 525
 526         bftw_cache_init(&state->cache, nopenfd);
 527
 528         if (nthreads > 0) {
 529                 state->ioq = ioq_create(qdepth, nthreads);
 530                 if (!state->ioq) {
 531                         return -1;
 532                 }
 533         } else {
 534                 state->ioq = NULL;
 535         }
 536         state->nthreads = nthreads;
 537
 538         if (bftw_must_buffer(state)) {
 539                 state->flags |= BFTW_BUFFER;
 540         }
 541
 542         if (state->flags & BFTW_WHITEOUTS) {
 543                 state->dir_flags |= BFS_DIR_WHITEOUTS;
 544         }
 545
 546         state->imbalance = 0;
 547
 548         SLIST_INIT(&state->dir_batch);
 549         SLIST_INIT(&state->to_open);
 550         SLIST_INIT(&state->to_read);
 551         SLIST_INIT(&state->to_close);
 552
 553         SLIST_INIT(&state->file_batch);
 554         SLIST_INIT(&state->to_visit);
 555
 556         state->path = NULL;
 557         state->file = NULL;
 558         state->previous = NULL;
 559
 560         state->dir = NULL;
 561         state->de = NULL;
 562         state->direrror = 0;
 563
 564         return 0;
 565 }
 566
 567 /** Unpin a directory, and possibly queue it for unwrapping. */
 568 static void bftw_unpin_dir(struct bftw_state *state, struct bftw_file *file, bool force) {
 569         bftw_cache_unpin(&state->cache, file);
 570
 571         if (file->dir && (force || file->pincount == 0)) {
 572                 if (!SLIST_ATTACHED(&state->to_close, file)) {
 573                         SLIST_APPEND(&state->to_close, file);
 574                 }
 575         }
 576 }
 577
 578 /** Adjust the I/O queue balance. */
 579 static void bftw_ioq_balance(struct bftw_state *state, long delta) {
 580         // Avoid signed overflow
 581         state->imbalance = (unsigned long)state->imbalance + (unsigned long)delta;
 582 }
 583
 584 /** Pop a response from the I/O queue. */
 585 static int bftw_ioq_pop(struct bftw_state *state, bool block) {
 586         struct ioq *ioq = state->ioq;
 587         if (!ioq) {
 588                 return -1;
 589         }
 590
 591         struct ioq_ent *ent = block ? ioq_pop(ioq) : ioq_trypop(ioq);
 592         if (!ent) {
 593                 return -1;
 594         }
 595
 596         struct bftw_cache *cache = &state->cache;
 597         struct bftw_file *file;
 598         struct bftw_file *parent;
 599         struct bfs_dir *dir;
 600
 601         enum ioq_op op = ent->op;
 602         switch (op) {
 603         case IOQ_CLOSE:
 604                 ++cache->capacity;
 605                 break;
 606
 607         case IOQ_CLOSEDIR:
 608                 ++cache->capacity;
 609                 dir = ent->closedir.dir;
 610                 bftw_freedir(cache, dir);
 611                 break;
 612
 613         case IOQ_OPENDIR:
 614                 file = ent->ptr;
 615                 file->ioqueued = false;
 616
 617                 ++cache->capacity;
 618                 parent = file->parent;
 619                 if (parent) {
 620                         bftw_unpin_dir(state, parent, false);
 621                 }
 622
 623                 dir = ent->opendir.dir;
 624                 if (ent->ret == 0) {
 625                         bftw_file_set_dir(cache, file, dir);
 626                 } else {
 627                         bftw_freedir(cache, dir);
 628                 }
 629
 630                 if (!(state->flags & BFTW_SORT)) {
 631                         SLIST_APPEND(&state->to_read, file, to_read);
 632                 }
 633                 break;
 634         }
 635
 636         ioq_free(ioq, ent);
 637         return op;
 638 }
 639
 640 /** Try to reserve space in the I/O queue. */
 641 static int bftw_ioq_reserve(struct bftw_state *state) {
 642         struct ioq *ioq = state->ioq;
 643         if (!ioq) {
 644                 return -1;
 645         }
 646
 647         // With only one background thread, we should balance I/O between it and
 648         // the main thread.  With more than one background thread, it's faster
 649         // to wait on background I/O than it is to do it on the main thread.
 650         bool balance = state->nthreads <= 1;
 651         if (balance && state->imbalance < 0) {
 652                 return -1;
 653         }
 654
 655         if (ioq_capacity(ioq) > 0) {
 656                 return 0;
 657         }
 658
 659         if (bftw_ioq_pop(state, !balance) < 0) {
 660                 return -1;
 661         }
 662
 663         return 0;
 664 }
 665
 666 /** Try to reserve space in the cache. */
 667 static int bftw_cache_reserve(struct bftw_state *state) {
 668         struct bftw_cache *cache = &state->cache;
 669         if (cache->capacity > 0) {
 670                 return 0;
 671         }
 672
 673         while (bftw_ioq_pop(state, true) >= 0) {
 674                 if (cache->capacity > 0) {
 675                         return 0;
 676                 }
 677         }
 678
 679         if (bftw_cache_pop(cache) != 0) {
 680                 errno = EMFILE;
 681                 return -1;
 682         }
 683
 684         bfs_assert(cache->capacity > 0);
 685         return 0;
 686 }
 687
 688 /** Open a bftw_file relative to another one. */
 689 static int bftw_file_openat(struct bftw_state *state, struct bftw_file *file, struct bftw_file *base, const char *at_path) {
 690         bfs_assert(file->fd < 0);
 691
 692         struct bftw_cache *cache = &state->cache;
 693
 694         int at_fd = AT_FDCWD;
 695         if (base) {
 696                 bftw_cache_pin(cache, base);
 697                 at_fd = base->fd;
 698         }
 699
 700         int fd = -1;
 701         if (bftw_cache_reserve(state) != 0) {
 702                 goto unpin;
 703         }
 704
 705         int flags = O_RDONLY | O_CLOEXEC | O_DIRECTORY;
 706         fd = openat(at_fd, at_path, flags);
 707
 708         if (fd < 0 && errno == EMFILE) {
 709                 if (bftw_cache_pop(cache) == 0) {
 710                         fd = openat(at_fd, at_path, flags);
 711                 }
 712                 cache->capacity = 1;
 713         }
 714
 715 unpin:
 716         if (base) {
 717                 bftw_cache_unpin(cache, base);
 718         }
 719
 720         if (fd >= 0) {
 721                 file->fd = fd;
 722                 bftw_cache_add(cache, file);
 723         }
 724
 725         return fd;
 726 }
 727
 728 /** Open a bftw_file. */
 729 static int bftw_file_open(struct bftw_state *state, struct bftw_file *file, const char *path) {
 730         // Find the nearest open ancestor
 731         struct bftw_file *base = file;
 732         do {
 733                 base = base->parent;
 734         } while (base && base->fd < 0);
 735
 736         const char *at_path = path;
 737         if (base) {
 738                 at_path += bftw_child_nameoff(base);
 739         }
 740
 741         int fd = bftw_file_openat(state, file, base, at_path);
 742         if (fd >= 0 || errno != ENAMETOOLONG) {
 743                 return fd;
 744         }
 745
 746         // Handle ENAMETOOLONG by manually traversing the path component-by-component
 747         struct bftw_list parents;
 748         SLIST_INIT(&parents);
 749
 750         struct bftw_file *cur;
 751         for (cur = file; cur != base; cur = cur->parent) {
 752                 SLIST_PREPEND(&parents, cur);
 753         }
 754
 755         while ((cur = SLIST_POP(&parents))) {
 756                 if (!cur->parent || cur->parent->fd >= 0) {
 757                         bftw_file_openat(state, cur, cur->parent, cur->name);
 758                 }
 759         }
 760
 761         return file->fd;
 762 }
 763
 764 /** Close a directory, asynchronously if possible. */
 765 static int bftw_ioq_closedir(struct bftw_state *state, struct bfs_dir *dir) {
 766         if (bftw_ioq_reserve(state) == 0) {
 767                 if (ioq_closedir(state->ioq, dir, NULL) == 0) {
 768                         return 0;
 769                 }
 770         }
 771
 772         struct bftw_cache *cache = &state->cache;
 773         int ret = bfs_closedir(dir);
 774         bftw_freedir(cache, dir);
 775         ++cache->capacity;
 776         return ret;
 777 }
 778
 779 /** Close a file descriptor, asynchronously if possible. */
 780 static int bftw_ioq_close(struct bftw_state *state, int fd) {
 781         if (bftw_ioq_reserve(state) == 0) {
 782                 if (ioq_close(state->ioq, fd, NULL) == 0) {
 783                         return 0;
 784                 }
 785         }
 786
 787         struct bftw_cache *cache = &state->cache;
 788         int ret = xclose(fd);
 789         ++cache->capacity;
 790         return ret;
 791 }
 792
 793 /** Close a file, asynchronously if possible. */
 794 static int bftw_close(struct bftw_state *state, struct bftw_file *file) {
 795         bfs_assert(file->fd >= 0);
 796         bfs_assert(file->pincount == 0);
 797
 798         struct bfs_dir *dir = file->dir;
 799         int fd = file->fd;
 800
 801         bftw_lru_remove(&state->cache, file);
 802         file->dir = NULL;
 803         file->fd = -1;
 804
 805         if (dir) {
 806                 return bftw_ioq_closedir(state, dir);
 807         } else {
 808                 return bftw_ioq_close(state, fd);
 809         }
 810 }
 811
 812 /** Free an open directory. */
 813 static int bftw_unwrapdir(struct bftw_state *state, struct bftw_file *file) {
 814         struct bfs_dir *dir = file->dir;
 815         if (!dir) {
 816                 return 0;
 817         }
 818
 819         struct bftw_cache *cache = &state->cache;
 820
 821         // Try to keep an open fd if any children exist
 822         bool reffed = file->refcount > 1;
 823         // Keep the fd the same if it's pinned
 824         bool pinned = file->pincount > 0;
 825
 826 #if BFS_USE_UNWRAPDIR
 827         if (reffed || pinned) {
 828                 bfs_unwrapdir(dir);
 829                 bftw_freedir(cache, dir);
 830                 file->dir = NULL;
 831                 return 0;
 832         }
 833 #else
 834         if (pinned) {
 835                 return -1;
 836         }
 837 #endif
 838
 839         if (!reffed) {
 840                 return bftw_close(state, file);
 841         }
 842
 843         // Make room for dup()
 844         bftw_cache_pin(cache, file);
 845         int ret = bftw_cache_reserve(state);
 846         bftw_cache_unpin(cache, file);
 847         if (ret != 0) {
 848                 return ret;
 849         }
 850
 851         int fd = dup_cloexec(file->fd);
 852         if (fd < 0) {
 853                 return -1;
 854         }
 855         --cache->capacity;
 856
 857         file->dir = NULL;
 858         file->fd = fd;
 859         return bftw_ioq_closedir(state, dir);
 860 }
 861
 862 /** Open a directory asynchronously. */
 863 static int bftw_ioq_opendir(struct bftw_state *state, struct bftw_file *file) {
 864         if (bftw_ioq_reserve(state) != 0) {
 865                 goto fail;
 866         }
 867
 868         int dfd = AT_FDCWD;
 869         struct bftw_cache *cache = &state->cache;
 870         struct bftw_file *parent = file->parent;
 871         if (parent) {
 872                 dfd = parent->fd;
 873                 if (dfd < 0) {
 874                         goto fail;
 875                 }
 876                 bftw_cache_pin(cache, parent);
 877         }
 878
 879         if (bftw_cache_reserve(state) != 0) {
 880                 goto unpin;
 881         }
 882
 883         struct bfs_dir *dir = bftw_allocdir(cache);
 884         if (!dir) {
 885                 goto unpin;
 886         }
 887
 888         if (ioq_opendir(state->ioq, dir, dfd, file->name, state->dir_flags, file) != 0) {
 889                 goto free;
 890         }
 891
 892         file->ioqueued = true;
 893         --cache->capacity;
 894         bftw_ioq_balance(state, -1);
 895         return 0;
 896
 897 free:
 898         bftw_freedir(cache, dir);
 899 unpin:
 900         if (parent) {
 901                 bftw_cache_unpin(cache, parent);
 902         }
 903 fail:
 904         return -1;
 905 }
 906
 907 /** Open a batch of directories asynchronously. */
 908 static void bftw_ioq_opendirs(struct bftw_state *state, struct bftw_list *queue) {
 909         for_slist (struct bftw_file, dir, queue) {
 910                 if (bftw_ioq_opendir(state, dir) != 0) {
 911                         break;
 912                 }
 913                 SLIST_POP(queue);
 914         }
 915 }
 916
 917 /** Push a directory onto the queue. */
 918 static void bftw_push_dir(struct bftw_state *state, struct bftw_file *file) {
 919         bfs_assert(file->type == BFS_DIR);
 920
 921         struct bftw_list *queue;
 922         if (state->strategy == BFTW_BFS || (state->flags & BFTW_BUFFER)) {
 923                 // In breadth-first mode, or if we're already buffering files,
 924                 // we can push directly to the to_open queue
 925                 queue = &state->to_open;
 926         } else {
 927                 // For a depth-first, unbuffered search, add directories to a
 928                 // batch, then push the patch to the front of the queue
 929                 queue = &state->dir_batch;
 930         }
 931
 932         SLIST_APPEND(queue, file);
 933
 934         if (state->flags & BFTW_SORT) {
 935                 // When sorting, directories are kept in order on the to_read
 936                 // list; otherwise, they are only added once they are open
 937                 SLIST_APPEND(&state->to_read, file, to_read);
 938         }
 939
 940         bftw_ioq_opendirs(state, queue);
 941 }
 942
 943 /** Pop a directory to read from the queue. */
 944 static bool bftw_pop_dir(struct bftw_state *state) {
 945         bfs_assert(!state->file);
 946
 947         struct bftw_cache *cache = &state->cache;
 948         bool have_files = !SLIST_EMPTY(&state->to_visit);
 949
 950         if (state->flags & BFTW_SORT) {
 951                 // Keep strict breadth-first order when sorting
 952                 if (state->strategy == BFTW_BFS && have_files) {
 953                         return false;
 954                 }
 955         } else {
 956                 while (SLIST_EMPTY(&state->to_read)) {
 957                         // Block if we have no other files/dirs to visit, or no room in the cache
 958                         bool have_dirs = !SLIST_EMPTY(&state->to_open);
 959                         bool have_room = cache->capacity > 0 && cache->dirlimit > 0;
 960                         bool block = !(have_dirs || have_files) || !have_room;
 961
 962                         if (bftw_ioq_pop(state, block) < 0) {
 963                                 break;
 964                         }
 965                 }
 966         }
 967
 968         struct bftw_file *file = SLIST_POP(&state->to_read, to_read);
 969         if (!file || file == state->to_open.head) {
 970                 file = SLIST_POP(&state->to_open);
 971         }
 972         if (!file) {
 973                 return false;
 974         }
 975
 976         while (file->ioqueued) {
 977                 bftw_ioq_pop(state, true);
 978         }
 979
 980         state->file = file;
 981         return true;
 982 }
 983
 984 /** Pop a file to visit from the queue. */
 985 static bool bftw_pop_file(struct bftw_state *state) {
 986         bfs_assert(!state->file);
 987         state->file = SLIST_POP(&state->to_visit);
 988         return state->file;
 989 }
 990
 991 /** Build the path to the current file. */
 992 static int bftw_build_path(struct bftw_state *state, const char *name) {
 993         const struct bftw_file *file = state->file;
 994
 995         size_t pathlen = file ? file->nameoff + file->namelen : 0;
 996         if (dstresize(&state->path, pathlen) != 0) {
 997                 state->error = errno;
 998                 return -1;
 999         }
1000
1001         // Try to find a common ancestor with the existing path
1002         const struct bftw_file *ancestor = state->previous;
1003         while (ancestor && ancestor->depth > file->depth) {
1004                 ancestor = ancestor->parent;
1005         }
1006
1007         // Build the path backwards
1008         while (file && file != ancestor) {
1009                 if (file->nameoff > 0) {
1010                         state->path[file->nameoff - 1] = '/';
1011                 }
1012                 memcpy(state->path + file->nameoff, file->name, file->namelen);
1013
1014                 if (ancestor && ancestor->depth == file->depth) {
1015                         ancestor = ancestor->parent;
1016                 }
1017                 file = file->parent;
1018         }
1019
1020         state->previous = state->file;
1021
1022         if (name) {
1023                 if (pathlen > 0 && state->path[pathlen - 1] != '/') {
1024                         if (dstrapp(&state->path, '/') != 0) {
1025                                 state->error = errno;
1026                                 return -1;
1027                         }
1028                 }
1029                 if (dstrcat(&state->path, name) != 0) {
1030                         state->error = errno;
1031                         return -1;
1032                 }
1033         }
1034
1035         return 0;
1036 }
1037
1038 /** Open a bftw_file as a directory. */
1039 static struct bfs_dir *bftw_file_opendir(struct bftw_state *state, struct bftw_file *file, const char *path) {
1040         int fd = bftw_file_open(state, file, path);
1041         if (fd < 0) {
1042                 return NULL;
1043         }
1044
1045         struct bftw_cache *cache = &state->cache;
1046         struct bfs_dir *dir = bftw_allocdir(cache);
1047         if (!dir) {
1048                 return NULL;
1049         }
1050
1051         bftw_ioq_balance(state, +1);
1052
1053         if (bfs_opendir(dir, fd, NULL, state->dir_flags) != 0) {
1054                 bftw_freedir(cache, dir);
1055                 return NULL;
1056         }
1057
1058         bftw_file_set_dir(cache, file, dir);
1059         return dir;
1060 }
1061
1062 /** Open the current directory. */
1063 static int bftw_opendir(struct bftw_state *state) {
1064         bfs_assert(!state->dir);
1065         bfs_assert(!state->de);
1066
1067         state->direrror = 0;
1068
1069         struct bftw_file *file = state->file;
1070         state->dir = file->dir;
1071         if (state->dir) {
1072                 return 0;
1073         }
1074
1075         if (bftw_build_path(state, NULL) != 0) {
1076                 return -1;
1077         }
1078
1079         state->dir = bftw_file_opendir(state, file, state->path);
1080         if (!state->dir) {
1081                 state->direrror = errno;
1082         }
1083
1084         return 0;
1085 }
1086
1087 /** Read an entry from the current directory. */
1088 static int bftw_readdir(struct bftw_state *state) {
1089         if (!state->dir) {
1090                 return -1;
1091         }
1092
1093         int ret = bfs_readdir(state->dir, &state->de_storage);
1094         if (ret > 0) {
1095                 state->de = &state->de_storage;
1096         } else if (ret == 0) {
1097                 state->de = NULL;
1098         } else {
1099                 state->de = NULL;
1100                 state->direrror = errno;
1101         }
1102
1103         return ret;
1104 }
1105
1106 /** Check if a stat() call is needed for this visit. */
1107 static bool bftw_need_stat(const struct bftw_state *state) {
1108         if (state->flags & BFTW_STAT) {
1109                 return true;
1110         }
1111
1112         const struct BFTW *ftwbuf = &state->ftwbuf;
1113         if (ftwbuf->type == BFS_UNKNOWN) {
1114                 return true;
1115         }
1116
1117         if (ftwbuf->type == BFS_LNK && !(ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
1118                 return true;
1119         }
1120
1121         if (ftwbuf->type == BFS_DIR) {
1122                 if (state->flags & (BFTW_DETECT_CYCLES | BFTW_SKIP_MOUNTS | BFTW_PRUNE_MOUNTS)) {
1123                         return true;
1124                 }
1125 #if __linux__
1126         } else if (state->mtab) {
1127                 // Linux fills in d_type from the underlying inode, even when
1128                 // the directory entry is a bind mount point.  In that case, we
1129                 // need to stat() to get the correct type.  We don't need to
1130                 // check for directories because they can only be mounted over
1131                 // by other directories.
1132                 if (bfs_might_be_mount(state->mtab, ftwbuf->path)) {
1133                         return true;
1134                 }
1135 #endif
1136         }
1137
1138         return false;
1139 }
1140
1141 /** Initialize bftw_stat cache. */
1142 static void bftw_stat_init(struct bftw_stat *cache) {
1143         cache->buf = NULL;
1144         cache->error = 0;
1145 }
1146
1147 /** Open a file if necessary. */
1148 static int bftw_ensure_open(struct bftw_state *state, struct bftw_file *file, const char *path) {
1149         int ret = file->fd;
1150
1151         if (ret < 0) {
1152                 char *copy = strndup(path, file->nameoff + file->namelen);
1153                 if (!copy) {
1154                         return -1;
1155                 }
1156
1157                 ret = bftw_file_open(state, file, copy);
1158                 free(copy);
1159         }
1160
1161         return ret;
1162 }
1163
1164 /** Initialize the buffers with data about the current path. */
1165 static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
1166         struct bftw_file *file = state->file;
1167         const struct bfs_dirent *de = state->de;
1168
1169         struct BFTW *ftwbuf = &state->ftwbuf;
1170         ftwbuf->path = state->path;
1171         ftwbuf->root = file ? file->root->name : ftwbuf->path;
1172         ftwbuf->depth = 0;
1173         ftwbuf->visit = visit;
1174         ftwbuf->type = BFS_UNKNOWN;
1175         ftwbuf->error = state->direrror;
1176         ftwbuf->at_fd = AT_FDCWD;
1177         ftwbuf->at_path = ftwbuf->path;
1178         ftwbuf->stat_flags = BFS_STAT_NOFOLLOW;
1179         bftw_stat_init(&ftwbuf->lstat_cache);
1180         bftw_stat_init(&ftwbuf->stat_cache);
1181
1182         struct bftw_file *parent = NULL;
1183         if (de) {
1184                 parent = file;
1185                 ftwbuf->depth = file->depth + 1;
1186                 ftwbuf->type = de->type;
1187                 ftwbuf->nameoff = bftw_child_nameoff(file);
1188         } else if (file) {
1189                 parent = file->parent;
1190                 ftwbuf->depth = file->depth;
1191                 ftwbuf->type = file->type;
1192                 ftwbuf->nameoff = file->nameoff;
1193         }
1194
1195         if (parent) {
1196                 // Try to ensure the immediate parent is open, to avoid ENAMETOOLONG
1197                 if (bftw_ensure_open(state, parent, state->path) >= 0) {
1198                         ftwbuf->at_fd = parent->fd;
1199                         ftwbuf->at_path += ftwbuf->nameoff;
1200                 } else {
1201                         ftwbuf->error = errno;
1202                 }
1203         }
1204
1205         if (ftwbuf->depth == 0) {
1206                 // Compute the name offset for root paths like "foo/bar"
1207                 ftwbuf->nameoff = xbaseoff(ftwbuf->path);
1208         }
1209
1210         if (ftwbuf->error != 0) {
1211                 ftwbuf->type = BFS_ERROR;
1212                 return;
1213         }
1214
1215         int follow_flags = BFTW_FOLLOW_ALL;
1216         if (ftwbuf->depth == 0) {
1217                 follow_flags |= BFTW_FOLLOW_ROOTS;
1218         }
1219         bool follow = state->flags & follow_flags;
1220         if (follow) {
1221                 ftwbuf->stat_flags = BFS_STAT_TRYFOLLOW;
1222         }
1223
1224         const struct bfs_stat *statbuf = NULL;
1225         if (bftw_need_stat(state)) {
1226                 statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
1227                 if (statbuf) {
1228                         ftwbuf->type = bfs_mode_to_type(statbuf->mode);
1229                 } else {
1230                         ftwbuf->type = BFS_ERROR;
1231                         ftwbuf->error = errno;
1232                         return;
1233                 }
1234         }
1235
1236         if (ftwbuf->type == BFS_DIR && (state->flags & BFTW_DETECT_CYCLES)) {
1237                 for (const struct bftw_file *ancestor = parent; ancestor; ancestor = ancestor->parent) {
1238                         if (ancestor->dev == statbuf->dev && ancestor->ino == statbuf->ino) {
1239                                 ftwbuf->type = BFS_ERROR;
1240                                 ftwbuf->error = ELOOP;
1241                                 return;
1242                         }
1243                 }
1244         }
1245 }
1246
1247 /** Check if the current file is a mount point. */
1248 static bool bftw_is_mount(struct bftw_state *state, const char *name) {
1249         const struct bftw_file *file = state->file;
1250         if (!file) {
1251                 return false;
1252         }
1253
1254         const struct bftw_file *parent = name ? file : file->parent;
1255         if (!parent) {
1256                 return false;
1257         }
1258
1259         const struct BFTW *ftwbuf = &state->ftwbuf;
1260         const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
1261         return statbuf && statbuf->dev != parent->dev;
1262 }
1263
1264 /** Invoke the callback. */
1265 static enum bftw_action bftw_call_back(struct bftw_state *state, const char *name, enum bftw_visit visit) {
1266         if (visit == BFTW_POST && !(state->flags & BFTW_POST_ORDER)) {
1267                 return BFTW_PRUNE;
1268         }
1269
1270         if (bftw_build_path(state, name) != 0) {
1271                 return BFTW_STOP;
1272         }
1273
1274         const struct BFTW *ftwbuf = &state->ftwbuf;
1275         bftw_init_ftwbuf(state, visit);
1276
1277         // Never give the callback BFS_ERROR unless BFTW_RECOVER is specified
1278         if (ftwbuf->type == BFS_ERROR && !(state->flags & BFTW_RECOVER)) {
1279                 state->error = ftwbuf->error;
1280                 return BFTW_STOP;
1281         }
1282
1283         if ((state->flags & BFTW_SKIP_MOUNTS) && bftw_is_mount(state, name)) {
1284                 return BFTW_PRUNE;
1285         }
1286
1287         enum bftw_action ret = state->callback(ftwbuf, state->ptr);
1288         switch (ret) {
1289         case BFTW_CONTINUE:
1290                 if (visit != BFTW_PRE) {
1291                         return BFTW_PRUNE;
1292                 }
1293                 if (ftwbuf->type != BFS_DIR) {
1294                         return BFTW_PRUNE;
1295                 }
1296                 if ((state->flags & BFTW_PRUNE_MOUNTS) && bftw_is_mount(state, name)) {
1297                         return BFTW_PRUNE;
1298                 }
1299                 fallthru;
1300         case BFTW_PRUNE:
1301         case BFTW_STOP:
1302                 return ret;
1303
1304         default:
1305                 state->error = EINVAL;
1306                 return BFTW_STOP;
1307         }
1308 }
1309
1310 /**
1311  * Flags controlling which files get visited when done with a directory.
1312  */
1313 enum bftw_gc_flags {
1314         /** Don't visit anything. */
1315         BFTW_VISIT_NONE = 0,
1316         /** Report directory errors. */
1317         BFTW_VISIT_ERROR = 1 << 0,
1318         /** Visit the file itself. */
1319         BFTW_VISIT_FILE = 1 << 1,
1320         /** Visit the file's ancestors. */
1321         BFTW_VISIT_PARENTS = 1 << 2,
1322         /** Visit both the file and its ancestors. */
1323         BFTW_VISIT_ALL = BFTW_VISIT_ERROR | BFTW_VISIT_FILE | BFTW_VISIT_PARENTS,
1324 };
1325
1326 /** Garbage collect the current file and its parents. */
1327 static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) {
1328         int ret = 0;
1329
1330         struct bftw_file *file = state->file;
1331         if (file && file->dir) {
1332                 bftw_unpin_dir(state, file, true);
1333         }
1334         state->dir = NULL;
1335         state->de = NULL;
1336
1337         if (state->direrror != 0) {
1338                 if (flags & BFTW_VISIT_ERROR) {
1339                         if (bftw_call_back(state, NULL, BFTW_PRE) == BFTW_STOP) {
1340                                 ret = -1;
1341                                 flags = 0;
1342                         }
1343                 } else {
1344                         state->error = state->direrror;
1345                 }
1346         }
1347         state->direrror = 0;
1348
1349         while ((file = SLIST_POP(&state->to_close))) {
1350                 bftw_unwrapdir(state, file);
1351         }
1352
1353         enum bftw_gc_flags visit = BFTW_VISIT_FILE;
1354         while ((file = state->file)) {
1355                 if (--file->refcount > 0) {
1356                         state->file = NULL;
1357                         break;
1358                 }
1359
1360                 if (flags & visit) {
1361                         if (bftw_call_back(state, NULL, BFTW_POST) == BFTW_STOP) {
1362                                 ret = -1;
1363                                 flags = 0;
1364                         }
1365                 }
1366                 visit = BFTW_VISIT_PARENTS;
1367
1368                 struct bftw_file *parent = file->parent;
1369                 if (state->previous == file) {
1370                         state->previous = parent;
1371                 }
1372                 state->file = parent;
1373
1374                 if (file->fd >= 0) {
1375                         bftw_close(state, file);
1376                 }
1377                 bftw_file_free(&state->cache, file);
1378         }
1379
1380         return ret;
1381 }
1382
1383 /** Sort a bftw_list by filename. */
1384 static void bftw_list_sort(struct bftw_list *list) {
1385         if (!list->head || !list->head->next) {
1386                 return;
1387         }
1388
1389         struct bftw_list left, right;
1390         SLIST_INIT(&left);
1391         SLIST_INIT(&right);
1392
1393         // Split
1394         for (struct bftw_file *hare = list->head; hare && (hare = hare->next); hare = hare->next) {
1395                 struct bftw_file *tortoise = SLIST_POP(list);
1396                 SLIST_APPEND(&left, tortoise);
1397         }
1398         SLIST_EXTEND(&right, list);
1399
1400         // Recurse
1401         bftw_list_sort(&left);
1402         bftw_list_sort(&right);
1403
1404         // Merge
1405         while (!SLIST_EMPTY(&left) && !SLIST_EMPTY(&right)) {
1406                 struct bftw_file *lf = left.head;
1407                 struct bftw_file *rf = right.head;
1408
1409                 if (strcoll(lf->name, rf->name) <= 0) {
1410                         SLIST_POP(&left);
1411                         SLIST_APPEND(list, lf);
1412                 } else {
1413                         SLIST_POP(&right);
1414                         SLIST_APPEND(list, rf);
1415                 }
1416         }
1417         SLIST_EXTEND(list, &left);
1418         SLIST_EXTEND(list, &right);
1419 }
1420
1421 /** Finish adding a batch of files. */
1422 static void bftw_batch_finish(struct bftw_state *state) {
1423         if (state->flags & BFTW_SORT) {
1424                 bftw_list_sort(&state->file_batch);
1425         }
1426
1427         if (state->strategy != BFTW_BFS) {
1428                 SLIST_EXTEND(&state->dir_batch, &state->to_open);
1429                 SLIST_EXTEND(&state->file_batch, &state->to_visit);
1430         }
1431
1432         SLIST_EXTEND(&state->to_open, &state->dir_batch);
1433         SLIST_EXTEND(&state->to_visit, &state->file_batch);
1434
1435         bftw_ioq_opendirs(state, &state->to_open);
1436 }
1437
1438 /** Close the current directory. */
1439 static int bftw_closedir(struct bftw_state *state) {
1440         if (bftw_gc(state, BFTW_VISIT_ALL) != 0) {
1441                 return -1;
1442         }
1443
1444         bftw_batch_finish(state);
1445         return 0;
1446 }
1447
1448 /** Fill file identity information from an ftwbuf. */
1449 static void bftw_save_ftwbuf(struct bftw_file *file, const struct BFTW *ftwbuf) {
1450         file->type = ftwbuf->type;
1451
1452         const struct bfs_stat *statbuf = ftwbuf->stat_cache.buf;
1453         if (!statbuf || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
1454                 statbuf = ftwbuf->lstat_cache.buf;
1455         }
1456         if (statbuf) {
1457                 file->dev = statbuf->dev;
1458                 file->ino = statbuf->ino;
1459         }
1460 }
1461
1462 /** Visit and/or enqueue the current file. */
1463 static int bftw_visit(struct bftw_state *state, const char *name) {
1464         struct bftw_file *file = state->file;
1465
1466         if (name && (state->flags & BFTW_BUFFER)) {
1467                 file = bftw_file_new(&state->cache, file, name);
1468                 if (!file) {
1469                         state->error = errno;
1470                         return -1;
1471                 }
1472
1473                 if (state->de) {
1474                         file->type = state->de->type;
1475                 }
1476
1477                 SLIST_APPEND(&state->file_batch, file);
1478                 return 0;
1479         }
1480
1481         switch (bftw_call_back(state, name, BFTW_PRE)) {
1482         case BFTW_CONTINUE:
1483                 if (name) {
1484                         file = bftw_file_new(&state->cache, state->file, name);
1485                 } else {
1486                         state->file = NULL;
1487                 }
1488                 if (!file) {
1489                         state->error = errno;
1490                         return -1;
1491                 }
1492
1493                 bftw_save_ftwbuf(file, &state->ftwbuf);
1494                 bftw_push_dir(state, file);
1495                 return 0;
1496
1497         case BFTW_PRUNE:
1498                 if (file && !name) {
1499                         return bftw_gc(state, BFTW_VISIT_PARENTS);
1500                 } else {
1501                         return 0;
1502                 }
1503
1504         default:
1505                 return -1;
1506         }
1507 }
1508
1509 /**
1510  * Dispose of the bftw() state.
1511  *
1512  * @return
1513  *         The bftw() return value.
1514  */
1515 static int bftw_state_destroy(struct bftw_state *state) {
1516         dstrfree(state->path);
1517
1518         struct ioq *ioq = state->ioq;
1519         if (ioq) {
1520                 ioq_cancel(ioq);
1521                 while (bftw_ioq_pop(state, true) >= 0);
1522                 state->ioq = NULL;
1523         }
1524
1525         SLIST_EXTEND(&state->to_open, &state->dir_batch);
1526         SLIST_EXTEND(&state->to_visit, &state->file_batch);
1527         do {
1528                 bftw_gc(state, BFTW_VISIT_NONE);
1529         } while (bftw_pop_dir(state) || bftw_pop_file(state));
1530
1531         ioq_destroy(ioq);
1532
1533         bftw_cache_destroy(&state->cache);
1534
1535         errno = state->error;
1536         return state->error ? -1 : 0;
1537 }
1538
1539 /**
1540  * Shared implementation for all search strategies.
1541  */
1542 static int bftw_impl(struct bftw_state *state) {
1543         for (size_t i = 0; i < state->npaths; ++i) {
1544                 if (bftw_visit(state, state->paths[i]) != 0) {
1545                         return -1;
1546                 }
1547         }
1548         bftw_batch_finish(state);
1549
1550         while (true) {
1551                 while (bftw_pop_dir(state)) {
1552                         if (bftw_opendir(state) != 0) {
1553                                 return -1;
1554                         }
1555                         while (bftw_readdir(state) > 0) {
1556                                 if (bftw_visit(state, state->de->name) != 0) {
1557                                         return -1;
1558                                 }
1559                         }
1560                         if (bftw_closedir(state) != 0) {
1561                                 return -1;
1562                         }
1563                 }
1564
1565                 if (!bftw_pop_file(state)) {
1566                         break;
1567                 }
1568                 if (bftw_visit(state, NULL) != 0) {
1569                         break;
1570                 }
1571         }
1572
1573         return 0;
1574 }
1575
1576 /**
1577  * bftw() implementation for simple breadth-/depth-first search.
1578  */
1579 static int bftw_walk(const struct bftw_args *args) {
1580         struct bftw_state state;
1581         if (bftw_state_init(&state, args) != 0) {
1582                 return -1;
1583         }
1584
1585         bftw_impl(&state);
1586         return bftw_state_destroy(&state);
1587 }
1588
1589 /**
1590  * Iterative deepening search state.
1591  */
1592 struct bftw_ids_state {
1593         /** Nested walk state. */
1594         struct bftw_state nested;
1595         /** The wrapped callback. */
1596         bftw_callback *delegate;
1597         /** The wrapped callback arguments. */
1598         void *ptr;
1599         /** Which visit this search corresponds to. */
1600         enum bftw_visit visit;
1601         /** Whether to override the bftw_visit. */
1602         bool force_visit;
1603         /** The current minimum depth (inclusive). */
1604         size_t min_depth;
1605         /** The current maximum depth (exclusive). */
1606         size_t max_depth;
1607         /** The set of pruned paths. */
1608         struct trie pruned;
1609         /** Whether the bottom has been found. */
1610         bool bottom;
1611 };
1612
1613 /** Iterative deepening callback function. */
1614 static enum bftw_action bftw_ids_callback(const struct BFTW *ftwbuf, void *ptr) {
1615         struct bftw_ids_state *state = ptr;
1616
1617         if (state->force_visit) {
1618                 struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
1619                 mutbuf->visit = state->visit;
1620         }
1621
1622         if (ftwbuf->type == BFS_ERROR) {
1623                 if (ftwbuf->depth + 1 >= state->min_depth) {
1624                         return state->delegate(ftwbuf, state->ptr);
1625                 } else {
1626                         return BFTW_PRUNE;
1627                 }
1628         }
1629
1630         if (ftwbuf->depth < state->min_depth) {
1631                 if (trie_find_str(&state->pruned, ftwbuf->path)) {
1632                         return BFTW_PRUNE;
1633                 } else {
1634                         return BFTW_CONTINUE;
1635                 }
1636         } else if (state->visit == BFTW_POST) {
1637                 if (trie_find_str(&state->pruned, ftwbuf->path)) {
1638                         return BFTW_PRUNE;
1639                 }
1640         }
1641
1642         enum bftw_action ret = BFTW_CONTINUE;
1643         if (ftwbuf->visit == state->visit) {
1644                 ret = state->delegate(ftwbuf, state->ptr);
1645         }
1646
1647         switch (ret) {
1648         case BFTW_CONTINUE:
1649                 if (ftwbuf->type == BFS_DIR && ftwbuf->depth + 1 >= state->max_depth) {
1650                         state->bottom = false;
1651                         ret = BFTW_PRUNE;
1652                 }
1653                 break;
1654
1655         case BFTW_PRUNE:
1656                 if (ftwbuf->type == BFS_DIR) {
1657                         if (!trie_insert_str(&state->pruned, ftwbuf->path)) {
1658                                 state->nested.error = errno;
1659                                 ret = BFTW_STOP;
1660                         }
1661                 }
1662                 break;
1663
1664         case BFTW_STOP:
1665                 break;
1666         }
1667
1668         return ret;
1669 }
1670
1671 /** Initialize iterative deepening state. */
1672 static int bftw_ids_init(struct bftw_ids_state *state, const struct bftw_args *args) {
1673         state->delegate = args->callback;
1674         state->ptr = args->ptr;
1675         state->visit = BFTW_PRE;
1676         state->force_visit = false;
1677         state->min_depth = 0;
1678         state->max_depth = 1;
1679         trie_init(&state->pruned);
1680         state->bottom = false;
1681
1682         struct bftw_args ids_args = *args;
1683         ids_args.callback = bftw_ids_callback;
1684         ids_args.ptr = state;
1685         ids_args.flags &= ~BFTW_POST_ORDER;
1686         return bftw_state_init(&state->nested, &ids_args);
1687 }
1688
1689 /** Finish an iterative deepening search. */
1690 static int bftw_ids_destroy(struct bftw_ids_state *state) {
1691         trie_destroy(&state->pruned);
1692         return bftw_state_destroy(&state->nested);
1693 }
1694
1695 /**
1696  * Iterative deepening bftw() wrapper.
1697  */
1698 static int bftw_ids(const struct bftw_args *args) {
1699         struct bftw_ids_state state;
1700         if (bftw_ids_init(&state, args) != 0) {
1701                 return -1;
1702         }
1703
1704         while (!state.bottom) {
1705                 state.bottom = true;
1706
1707                 if (bftw_impl(&state.nested) != 0) {
1708                         goto done;
1709                 }
1710
1711                 ++state.min_depth;
1712                 ++state.max_depth;
1713         }
1714
1715         if (args->flags & BFTW_POST_ORDER) {
1716                 state.visit = BFTW_POST;
1717                 state.force_visit = true;
1718
1719                 while (state.min_depth > 0) {
1720                         --state.max_depth;
1721                         --state.min_depth;
1722
1723                         if (bftw_impl(&state.nested) != 0) {
1724                                 goto done;
1725                         }
1726                 }
1727         }
1728
1729 done:
1730         return bftw_ids_destroy(&state);
1731 }
1732
1733 /**
1734  * Exponential deepening bftw() wrapper.
1735  */
1736 static int bftw_eds(const struct bftw_args *args) {
1737         struct bftw_ids_state state;
1738         if (bftw_ids_init(&state, args) != 0) {
1739                 return -1;
1740         }
1741
1742         while (!state.bottom) {
1743                 state.bottom = true;
1744
1745                 if (bftw_impl(&state.nested) != 0) {
1746                         goto done;
1747                 }
1748
1749                 state.min_depth = state.max_depth;
1750                 state.max_depth *= 2;
1751         }
1752
1753         if (args->flags & BFTW_POST_ORDER) {
1754                 state.visit = BFTW_POST;
1755                 state.min_depth = 0;
1756                 state.nested.flags |= BFTW_POST_ORDER;
1757
1758                 bftw_impl(&state.nested);
1759         }
1760
1761 done:
1762         return bftw_ids_destroy(&state);
1763 }
1764
1765 int bftw(const struct bftw_args *args) {
1766         switch (args->strategy) {
1767         case BFTW_BFS:
1768         case BFTW_DFS:
1769                 return bftw_walk(args);
1770         case BFTW_IDS:
1771                 return bftw_ids(args);
1772         case BFTW_EDS:
1773                 return bftw_eds(args);
1774         }
1775
1776         errno = EINVAL;
1777         return -1;
1778 }