1 /****************************************************************************
2 * bfs *
3 * Copyright (C) 2015-2022 Tavian Barnes <tavianator@tavianator.com> *
4 * *
5 * Permission to use, copy, modify, and/or distribute this software for any *
6 * purpose with or without fee is hereby granted. *
7 * *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF *
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR *
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES *
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN *
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF *
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. *
15 ****************************************************************************/
16
17 /**
18 * The bftw() implementation consists of the following components:
19 *
20 * - struct bftw_file: A file that has been encountered during the traversal.
21 * They have reference-counted links to their parents in the directory tree.
22 *
23 * - struct bftw_cache: Holds bftw_file's with open file descriptors, used for
24 * openat() to minimize the amount of path re-traversals that need to happen.
25 * Currently implemented as a priority queue based on depth and reference
26 * count.
27 *
28 * - struct bftw_queue: The queue of bftw_file's left to explore. Implemented
29 * as a simple circular buffer.
30 *
31 * - struct bftw_state: Represents the current state of the traversal, allowing
32 * various helper functions to take fewer parameters.
33 */
34
35 #include "bftw.h"
36 #include "dir.h"
37 #include "darray.h"
38 #include "dstring.h"
39 #include "mtab.h"
40 #include "stat.h"
41 #include "trie.h"
42 #include "util.h"
43 #include <assert.h>
44 #include <errno.h>
45 #include <fcntl.h>
46 #include <stdbool.h>
47 #include <stdlib.h>
48 #include <string.h>
49 #include <sys/stat.h>
50 #include <unistd.h>
51
52 /**
53 * A file.
54 */
55 struct bftw_file {
56 /** The parent directory, if any. */
57 struct bftw_file *parent;
58 /** The root under which this file was found. */
59 struct bftw_file *root;
60 /** The next file in the queue, if any. */
61 struct bftw_file *next;
62
63 /** This file's depth in the walk. */
64 size_t depth;
65 /** Reference count. */
66 size_t refcount;
67 /** Index in the bftw_cache priority queue. */
68 size_t heap_index;
69
70 /** An open descriptor to this file, or -1. */
71 int fd;
72
73 /** This file's type, if known. */
74 enum bfs_type type;
75 /** The device number, for cycle detection. */
76 dev_t dev;
77 /** The inode number, for cycle detection. */
78 ino_t ino;
79
80 /** The offset of this file in the full path. */
81 size_t nameoff;
82 /** The length of the file's name. */
83 size_t namelen;
84 /** The file's name. */
85 char name[];
86 };
87
88 /**
89 * A cache of open directories.
90 */
91 struct bftw_cache {
92 /** A min-heap of open directories. */
93 struct bftw_file **heap;
94 /** Maximum heap size. */
95 size_t capacity;
96 };
97
98 /** Initialize a cache. */
bftw_cache_init(struct bftw_cache * cache,size_t capacity)99 static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
100 cache->heap = NULL;
101 cache->capacity = capacity;
102 }
103
104 /** Destroy a cache. */
bftw_cache_destroy(struct bftw_cache * cache)105 static void bftw_cache_destroy(struct bftw_cache *cache) {
106 assert(darray_length(cache->heap) == 0);
107 darray_free(cache->heap);
108 }
109
110 /** Check if two heap entries are in heap order. */
bftw_heap_check(const struct bftw_file * parent,const struct bftw_file * child)111 static bool bftw_heap_check(const struct bftw_file *parent, const struct bftw_file *child) {
112 if (parent->depth > child->depth) {
113 return true;
114 } else if (parent->depth < child->depth) {
115 return false;
116 } else {
117 return parent->refcount <= child->refcount;
118 }
119 }
120
121 /** Move a bftw_file to a particular place in the heap. */
bftw_heap_move(struct bftw_cache * cache,struct bftw_file * file,size_t i)122 static void bftw_heap_move(struct bftw_cache *cache, struct bftw_file *file, size_t i) {
123 cache->heap[i] = file;
124 file->heap_index = i;
125 }
126
127 /** Bubble an entry up the heap. */
bftw_heap_bubble_up(struct bftw_cache * cache,struct bftw_file * file)128 static void bftw_heap_bubble_up(struct bftw_cache *cache, struct bftw_file *file) {
129 size_t i = file->heap_index;
130
131 while (i > 0) {
132 size_t pi = (i - 1)/2;
133 struct bftw_file *parent = cache->heap[pi];
134 if (bftw_heap_check(parent, file)) {
135 break;
136 }
137
138 bftw_heap_move(cache, parent, i);
139 i = pi;
140 }
141
142 bftw_heap_move(cache, file, i);
143 }
144
145 /** Bubble an entry down the heap. */
bftw_heap_bubble_down(struct bftw_cache * cache,struct bftw_file * file)146 static void bftw_heap_bubble_down(struct bftw_cache *cache, struct bftw_file *file) {
147 size_t i = file->heap_index;
148 size_t size = darray_length(cache->heap);
149
150 while (true) {
151 size_t ci = 2*i + 1;
152 if (ci >= size) {
153 break;
154 }
155
156 struct bftw_file *child = cache->heap[ci];
157
158 size_t ri = ci + 1;
159 if (ri < size) {
160 struct bftw_file *right = cache->heap[ri];
161 if (!bftw_heap_check(child, right)) {
162 ci = ri;
163 child = right;
164 }
165 }
166
167 if (bftw_heap_check(file, child)) {
168 break;
169 }
170
171 bftw_heap_move(cache, child, i);
172 i = ci;
173 }
174
175 bftw_heap_move(cache, file, i);
176 }
177
178 /** Bubble an entry up or down the heap. */
bftw_heap_bubble(struct bftw_cache * cache,struct bftw_file * file)179 static void bftw_heap_bubble(struct bftw_cache *cache, struct bftw_file *file) {
180 size_t i = file->heap_index;
181
182 if (i > 0) {
183 size_t pi = (i - 1)/2;
184 struct bftw_file *parent = cache->heap[pi];
185 if (!bftw_heap_check(parent, file)) {
186 bftw_heap_bubble_up(cache, file);
187 return;
188 }
189 }
190
191 bftw_heap_bubble_down(cache, file);
192 }
193
194 /** Increment a bftw_file's reference count. */
bftw_file_incref(struct bftw_cache * cache,struct bftw_file * file)195 static size_t bftw_file_incref(struct bftw_cache *cache, struct bftw_file *file) {
196 size_t ret = ++file->refcount;
197 if (file->fd >= 0) {
198 bftw_heap_bubble_down(cache, file);
199 }
200 return ret;
201 }
202
203 /** Decrement a bftw_file's reference count. */
bftw_file_decref(struct bftw_cache * cache,struct bftw_file * file)204 static size_t bftw_file_decref(struct bftw_cache *cache, struct bftw_file *file) {
205 size_t ret = --file->refcount;
206 if (file->fd >= 0) {
207 bftw_heap_bubble_up(cache, file);
208 }
209 return ret;
210 }
211
212 /** Check if the cache is full. */
bftw_cache_full(const struct bftw_cache * cache)213 static bool bftw_cache_full(const struct bftw_cache *cache) {
214 return darray_length(cache->heap) == cache->capacity;
215 }
216
217 /** Add a bftw_file to the cache. */
bftw_cache_add(struct bftw_cache * cache,struct bftw_file * file)218 static int bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) {
219 assert(!bftw_cache_full(cache));
220 assert(file->fd >= 0);
221
222 size_t size = darray_length(cache->heap);
223 if (DARRAY_PUSH(&cache->heap, &file) != 0) {
224 return -1;
225 }
226
227 file->heap_index = size;
228 bftw_heap_bubble_up(cache, file);
229
230 return 0;
231 }
232
233 /** Remove a bftw_file from the cache. */
bftw_cache_remove(struct bftw_cache * cache,struct bftw_file * file)234 static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) {
235 struct bftw_file *last = DARRAY_POP(cache->heap);
236 if (last != file) {
237 last->heap_index = file->heap_index;
238 bftw_heap_bubble(cache, last);
239 }
240 }
241
242 /** Close a bftw_file. */
bftw_file_close(struct bftw_cache * cache,struct bftw_file * file)243 static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) {
244 assert(file->fd >= 0);
245
246 bftw_cache_remove(cache, file);
247
248 xclose(file->fd);
249 file->fd = -1;
250 }
251
252 /** Pop a directory from the cache. */
bftw_cache_pop(struct bftw_cache * cache)253 static void bftw_cache_pop(struct bftw_cache *cache) {
254 bftw_file_close(cache, cache->heap[0]);
255 }
256
257 /**
258 * Shrink the cache, to recover from EMFILE.
259 *
260 * @param cache
261 * The cache in question.
262 * @param saved
263 * A bftw_file that must be preserved.
264 * @return
265 * 0 if successfully shrunk, otherwise -1.
266 */
bftw_cache_shrink(struct bftw_cache * cache,const struct bftw_file * saved)267 static int bftw_cache_shrink(struct bftw_cache *cache, const struct bftw_file *saved) {
268 int ret = -1;
269 struct bftw_file *file = NULL;
270 size_t size = darray_length(cache->heap);
271
272 if (size >= 1) {
273 file = cache->heap[0];
274 if (file == saved && size >= 2) {
275 file = cache->heap[1];
276 }
277 }
278
279 if (file && file != saved) {
280 bftw_file_close(cache, file);
281 ret = 0;
282 }
283
284 cache->capacity = darray_length(cache->heap);
285 return ret;
286 }
287
288 /** Compute the name offset of a child path. */
bftw_child_nameoff(const struct bftw_file * parent)289 static size_t bftw_child_nameoff(const struct bftw_file *parent) {
290 size_t ret = parent->nameoff + parent->namelen;
291 if (parent->name[parent->namelen - 1] != '/') {
292 ++ret;
293 }
294 return ret;
295 }
296
297 /** Create a new bftw_file. */
bftw_file_new(struct bftw_cache * cache,struct bftw_file * parent,const char * name)298 static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_file *parent, const char *name) {
299 size_t namelen = strlen(name);
300 size_t size = BFS_FLEX_SIZEOF(struct bftw_file, name, namelen + 1);
301
302 struct bftw_file *file = malloc(size);
303 if (!file) {
304 return NULL;
305 }
306
307 file->parent = parent;
308
309 if (parent) {
310 file->root = parent->root;
311 file->depth = parent->depth + 1;
312 file->nameoff = bftw_child_nameoff(parent);
313 bftw_file_incref(cache, parent);
314 } else {
315 file->root = file;
316 file->depth = 0;
317 file->nameoff = 0;
318 }
319
320 file->next = NULL;
321
322 file->refcount = 1;
323 file->fd = -1;
324
325 file->type = BFS_UNKNOWN;
326 file->dev = -1;
327 file->ino = -1;
328
329 file->namelen = namelen;
330 memcpy(file->name, name, namelen + 1);
331
332 return file;
333 }
334
335 /**
336 * Open a bftw_file relative to another one.
337 *
338 * @param cache
339 * The cache to hold the file.
340 * @param file
341 * The file to open.
342 * @param base
343 * The base directory for the relative path (may be NULL).
344 * @param at_fd
345 * The base file descriptor, AT_FDCWD if base == NULL.
346 * @param at_path
347 * The relative path to the file.
348 * @return
349 * The opened file descriptor, or negative on error.
350 */
bftw_file_openat(struct bftw_cache * cache,struct bftw_file * file,const struct bftw_file * base,const char * at_path)351 static int bftw_file_openat(struct bftw_cache *cache, struct bftw_file *file, const struct bftw_file *base, const char *at_path) {
352 assert(file->fd < 0);
353
354 int at_fd = AT_FDCWD;
355 if (base) {
356 at_fd = base->fd;
357 assert(at_fd >= 0);
358 }
359
360 int flags = O_RDONLY | O_CLOEXEC | O_DIRECTORY;
361 int fd = openat(at_fd, at_path, flags);
362
363 if (fd < 0 && errno == EMFILE) {
364 if (bftw_cache_shrink(cache, base) == 0) {
365 fd = openat(at_fd, at_path, flags);
366 }
367 }
368
369 if (fd >= 0) {
370 if (bftw_cache_full(cache)) {
371 bftw_cache_pop(cache);
372 }
373
374 file->fd = fd;
375 if (bftw_cache_add(cache, file) != 0) {
376 close_quietly(fd);
377 file->fd = -1;
378 return -1;
379 }
380 }
381
382 return fd;
383 }
384
385 /**
386 * Open a bftw_file.
387 *
388 * @param cache
389 * The cache to hold the file.
390 * @param file
391 * The file to open.
392 * @param path
393 * The full path to the file.
394 * @return
395 * The opened file descriptor, or negative on error.
396 */
bftw_file_open(struct bftw_cache * cache,struct bftw_file * file,const char * path)397 static int bftw_file_open(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
398 // Find the nearest open ancestor
399 struct bftw_file *base = file;
400 do {
401 base = base->parent;
402 } while (base && base->fd < 0);
403
404 const char *at_path = path;
405 if (base) {
406 at_path += bftw_child_nameoff(base);
407 }
408
409 int fd = bftw_file_openat(cache, file, base, at_path);
410 if (fd >= 0 || errno != ENAMETOOLONG) {
411 return fd;
412 }
413
414 // Handle ENAMETOOLONG by manually traversing the path component-by-component
415
416 // Use the ->next linked list to temporarily hold the reversed parent
417 // chain between base and file
418 struct bftw_file *cur;
419 for (cur = file; cur->parent != base; cur = cur->parent) {
420 cur->parent->next = cur;
421 }
422
423 // Open the files in the chain one by one
424 for (base = cur; base; base = base->next) {
425 fd = bftw_file_openat(cache, base, base->parent, base->name);
426 if (fd < 0 || base == file) {
427 break;
428 }
429 }
430
431 // Clear out the linked list
432 for (struct bftw_file *next = cur->next; cur != file; cur = next, next = next->next) {
433 cur->next = NULL;
434 }
435
436 return fd;
437 }
438
439 /**
440 * Open a bftw_file as a directory.
441 *
442 * @param cache
443 * The cache to hold the file.
444 * @param file
445 * The directory to open.
446 * @param path
447 * The full path to the directory.
448 * @return
449 * The opened directory, or NULL on error.
450 */
bftw_file_opendir(struct bftw_cache * cache,struct bftw_file * file,const char * path)451 static struct bfs_dir *bftw_file_opendir(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
452 int fd = bftw_file_open(cache, file, path);
453 if (fd < 0) {
454 return NULL;
455 }
456
457 return bfs_opendir(fd, NULL);
458 }
459
460 /** Free a bftw_file. */
bftw_file_free(struct bftw_cache * cache,struct bftw_file * file)461 static void bftw_file_free(struct bftw_cache *cache, struct bftw_file *file) {
462 assert(file->refcount == 0);
463
464 if (file->fd >= 0) {
465 bftw_file_close(cache, file);
466 }
467
468 free(file);
469 }
470
471 /**
472 * A queue of bftw_file's to examine.
473 */
474 struct bftw_queue {
475 /** The head of the queue. */
476 struct bftw_file *head;
477 /** The insertion target. */
478 struct bftw_file **target;
479 };
480
481 /** Initialize a bftw_queue. */
bftw_queue_init(struct bftw_queue * queue)482 static void bftw_queue_init(struct bftw_queue *queue) {
483 queue->head = NULL;
484 queue->target = &queue->head;
485 }
486
487 /** Add a file to a bftw_queue. */
bftw_queue_push(struct bftw_queue * queue,struct bftw_file * file)488 static void bftw_queue_push(struct bftw_queue *queue, struct bftw_file *file) {
489 assert(file->next == NULL);
490
491 file->next = *queue->target;
492 *queue->target = file;
493 queue->target = &file->next;
494 }
495
496 /** Pop the next file from the head of the queue. */
bftw_queue_pop(struct bftw_queue * queue)497 static struct bftw_file *bftw_queue_pop(struct bftw_queue *queue) {
498 struct bftw_file *file = queue->head;
499 queue->head = file->next;
500 file->next = NULL;
501 if (queue->target == &file->next) {
502 queue->target = &queue->head;
503 }
504 return file;
505 }
506
507 /** The split phase of mergesort. */
bftw_sort_split(struct bftw_file ** head,struct bftw_file ** tail)508 static struct bftw_file **bftw_sort_split(struct bftw_file **head, struct bftw_file **tail) {
509 struct bftw_file **tortoise = head, **hare = head;
510
511 while (*hare != *tail) {
512 tortoise = &(*tortoise)->next;
513 hare = &(*hare)->next;
514 if (*hare != *tail) {
515 hare = &(*hare)->next;
516 }
517 }
518
519 return tortoise;
520 }
521
522 /** The merge phase of mergesort. */
bftw_sort_merge(struct bftw_file ** head,struct bftw_file ** mid,struct bftw_file ** tail)523 static struct bftw_file **bftw_sort_merge(struct bftw_file **head, struct bftw_file **mid, struct bftw_file **tail) {
524 struct bftw_file *left = *head, *right = *mid, *end = *tail;
525 *mid = NULL;
526 *tail = NULL;
527
528 while (left || right) {
529 struct bftw_file *next;
530 if (left && (!right || strcoll(left->name, right->name) <= 0)) {
531 next = left;
532 left = left->next;
533 } else {
534 next = right;
535 right = right->next;
536 }
537
538 *head = next;
539 head = &next->next;
540 }
541
542 *head = end;
543 return head;
544 }
545
546 /**
547 * Sort a (sub-)list of files.
548 *
549 * @param head
550 * The head of the (sub-)list to sort.
551 * @param tail
552 * The tail of the (sub-)list to sort.
553 * @return
554 * The new tail of the (sub-)list.
555 */
bftw_sort_files(struct bftw_file ** head,struct bftw_file ** tail)556 static struct bftw_file **bftw_sort_files(struct bftw_file **head, struct bftw_file **tail) {
557 struct bftw_file **mid = bftw_sort_split(head, tail);
558 if (*mid == *head || *mid == *tail) {
559 return tail;
560 }
561
562 mid = bftw_sort_files(head, mid);
563 tail = bftw_sort_files(mid, tail);
564
565 return bftw_sort_merge(head, mid, tail);
566 }
567
568 /**
569 * Holds the current state of the bftw() traversal.
570 */
571 struct bftw_state {
572 /** bftw() callback. */
573 bftw_callback *callback;
574 /** bftw() callback data. */
575 void *ptr;
576 /** bftw() flags. */
577 enum bftw_flags flags;
578 /** Search strategy. */
579 enum bftw_strategy strategy;
580 /** The mount table. */
581 const struct bfs_mtab *mtab;
582
583 /** The appropriate errno value, if any. */
584 int error;
585
586 /** The cache of open directories. */
587 struct bftw_cache cache;
588 /** The queue of directories left to explore. */
589 struct bftw_queue queue;
590 /** The start of the current batch of files. */
591 struct bftw_file **batch;
592
593 /** The current path. */
594 char *path;
595 /** The current file. */
596 struct bftw_file *file;
597 /** The previous file. */
598 struct bftw_file *previous;
599
600 /** The currently open directory. */
601 struct bfs_dir *dir;
602 /** The current directory entry. */
603 struct bfs_dirent *de;
604 /** Storage for the directory entry. */
605 struct bfs_dirent de_storage;
606 /** Any error encountered while reading the directory. */
607 int direrror;
608
609 /** Extra data about the current file. */
610 struct BFTW ftwbuf;
611 };
612
613 /**
614 * Initialize the bftw() state.
615 */
bftw_state_init(struct bftw_state * state,const struct bftw_args * args)616 static int bftw_state_init(struct bftw_state *state, const struct bftw_args *args) {
617 state->callback = args->callback;
618 state->ptr = args->ptr;
619 state->flags = args->flags;
620 state->strategy = args->strategy;
621 state->mtab = args->mtab;
622
623 state->error = 0;
624
625 if (args->nopenfd < 2) {
626 errno = EMFILE;
627 return -1;
628 }
629
630 state->path = dstralloc(0);
631 if (!state->path) {
632 return -1;
633 }
634
635 // Reserve 1 fd for the open bfs_dir
636 bftw_cache_init(&state->cache, args->nopenfd - 1);
637 bftw_queue_init(&state->queue);
638 state->batch = NULL;
639
640 state->file = NULL;
641 state->previous = NULL;
642
643 state->dir = NULL;
644 state->de = NULL;
645 state->direrror = 0;
646
647 return 0;
648 }
649
650 /** Cached bfs_stat(). */
bftw_stat_impl(struct BFTW * ftwbuf,struct bftw_stat * cache,enum bfs_stat_flags flags)651 static const struct bfs_stat *bftw_stat_impl(struct BFTW *ftwbuf, struct bftw_stat *cache, enum bfs_stat_flags flags) {
652 if (!cache->buf) {
653 if (cache->error) {
654 errno = cache->error;
655 } else if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, flags, &cache->storage) == 0) {
656 cache->buf = &cache->storage;
657 } else {
658 cache->error = errno;
659 }
660 }
661
662 return cache->buf;
663 }
664
bftw_stat(const struct BFTW * ftwbuf,enum bfs_stat_flags flags)665 const struct bfs_stat *bftw_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
666 struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
667 const struct bfs_stat *ret;
668
669 if (flags & BFS_STAT_NOFOLLOW) {
670 ret = bftw_stat_impl(mutbuf, &mutbuf->lstat_cache, BFS_STAT_NOFOLLOW);
671 if (ret && !S_ISLNK(ret->mode) && !mutbuf->stat_cache.buf) {
672 // Non-link, so share stat info
673 mutbuf->stat_cache.buf = ret;
674 }
675 } else {
676 ret = bftw_stat_impl(mutbuf, &mutbuf->stat_cache, BFS_STAT_FOLLOW);
677 if (!ret && (flags & BFS_STAT_TRYFOLLOW) && is_nonexistence_error(errno)) {
678 ret = bftw_stat_impl(mutbuf, &mutbuf->lstat_cache, BFS_STAT_NOFOLLOW);
679 }
680 }
681
682 return ret;
683 }
684
bftw_cached_stat(const struct BFTW * ftwbuf,enum bfs_stat_flags flags)685 const struct bfs_stat *bftw_cached_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
686 if (flags & BFS_STAT_NOFOLLOW) {
687 return ftwbuf->lstat_cache.buf;
688 } else if (ftwbuf->stat_cache.buf) {
689 return ftwbuf->stat_cache.buf;
690 } else if ((flags & BFS_STAT_TRYFOLLOW) && is_nonexistence_error(ftwbuf->stat_cache.error)) {
691 return ftwbuf->lstat_cache.buf;
692 } else {
693 return NULL;
694 }
695 }
696
bftw_type(const struct BFTW * ftwbuf,enum bfs_stat_flags flags)697 enum bfs_type bftw_type(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) {
698 if (flags & BFS_STAT_NOFOLLOW) {
699 if (ftwbuf->type == BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
700 return ftwbuf->type;
701 }
702 } else if (flags & BFS_STAT_TRYFOLLOW) {
703 if (ftwbuf->type != BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW)) {
704 return ftwbuf->type;
705 }
706 } else {
707 if (ftwbuf->type != BFS_LNK) {
708 return ftwbuf->type;
709 } else if (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW) {
710 return BFS_ERROR;
711 }
712 }
713
714 const struct bfs_stat *statbuf = bftw_stat(ftwbuf, flags);
715 if (statbuf) {
716 return bfs_mode_to_type(statbuf->mode);
717 } else {
718 return BFS_ERROR;
719 }
720 }
721
722 /**
723 * Update the path for the current file.
724 */
bftw_update_path(struct bftw_state * state,const char * name)725 static int bftw_update_path(struct bftw_state *state, const char *name) {
726 const struct bftw_file *file = state->file;
727 size_t length = file ? file->nameoff + file->namelen : 0;
728
729 assert(dstrlen(state->path) >= length);
730 dstresize(&state->path, length);
731
732 if (name) {
733 if (length > 0 && state->path[length - 1] != '/') {
734 if (dstrapp(&state->path, '/') != 0) {
735 return -1;
736 }
737 }
738 if (dstrcat(&state->path, name) != 0) {
739 return -1;
740 }
741 }
742
743 return 0;
744 }
745
746 /** Check if a stat() call is needed for this visit. */
bftw_need_stat(const struct bftw_state * state)747 static bool bftw_need_stat(const struct bftw_state *state) {
748 if (state->flags & BFTW_STAT) {
749 return true;
750 }
751
752 const struct BFTW *ftwbuf = &state->ftwbuf;
753 if (ftwbuf->type == BFS_UNKNOWN) {
754 return true;
755 }
756
757 if (ftwbuf->type == BFS_LNK && !(ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
758 return true;
759 }
760
761 if (ftwbuf->type == BFS_DIR) {
762 if (state->flags & (BFTW_DETECT_CYCLES | BFTW_SKIP_MOUNTS | BFTW_PRUNE_MOUNTS)) {
763 return true;
764 }
765 #if __linux__
766 } else if (state->mtab) {
767 // Linux fills in d_type from the underlying inode, even when
768 // the directory entry is a bind mount point. In that case, we
769 // need to stat() to get the correct type. We don't need to
770 // check for directories because they can only be mounted over
771 // by other directories.
772 if (bfs_might_be_mount(state->mtab, ftwbuf->path)) {
773 return true;
774 }
775 #endif
776 }
777
778 return false;
779 }
780
781 /** Initialize bftw_stat cache. */
bftw_stat_init(struct bftw_stat * cache)782 static void bftw_stat_init(struct bftw_stat *cache) {
783 cache->buf = NULL;
784 cache->error = 0;
785 }
786
787 /**
788 * Open a file if necessary.
789 *
790 * @param file
791 * The file to open.
792 * @param path
793 * The path to that file or one of its descendants.
794 * @return
795 * The opened file descriptor, or -1 on error.
796 */
bftw_ensure_open(struct bftw_cache * cache,struct bftw_file * file,const char * path)797 static int bftw_ensure_open(struct bftw_cache *cache, struct bftw_file *file, const char *path) {
798 int ret = file->fd;
799
800 if (ret < 0) {
801 char *copy = strndup(path, file->nameoff + file->namelen);
802 if (!copy) {
803 return -1;
804 }
805
806 ret = bftw_file_open(cache, file, copy);
807 free(copy);
808 }
809
810 return ret;
811 }
812
813 /**
814 * Initialize the buffers with data about the current path.
815 */
bftw_init_ftwbuf(struct bftw_state * state,enum bftw_visit visit)816 static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) {
817 struct bftw_file *file = state->file;
818 const struct bfs_dirent *de = state->de;
819
820 struct BFTW *ftwbuf = &state->ftwbuf;
821 ftwbuf->path = state->path;
822 ftwbuf->root = file ? file->root->name : ftwbuf->path;
823 ftwbuf->depth = 0;
824 ftwbuf->visit = visit;
825 ftwbuf->type = BFS_UNKNOWN;
826 ftwbuf->error = state->direrror;
827 ftwbuf->at_fd = AT_FDCWD;
828 ftwbuf->at_path = ftwbuf->path;
829 ftwbuf->stat_flags = BFS_STAT_NOFOLLOW;
830 bftw_stat_init(&ftwbuf->lstat_cache);
831 bftw_stat_init(&ftwbuf->stat_cache);
832
833 struct bftw_file *parent = NULL;
834 if (de) {
835 parent = file;
836 ftwbuf->depth = file->depth + 1;
837 ftwbuf->type = de->type;
838 ftwbuf->nameoff = bftw_child_nameoff(file);
839 } else if (file) {
840 parent = file->parent;
841 ftwbuf->depth = file->depth;
842 ftwbuf->type = file->type;
843 ftwbuf->nameoff = file->nameoff;
844 }
845
846 if (parent) {
847 // Try to ensure the immediate parent is open, to avoid ENAMETOOLONG
848 if (bftw_ensure_open(&state->cache, parent, state->path) >= 0) {
849 ftwbuf->at_fd = parent->fd;
850 ftwbuf->at_path += ftwbuf->nameoff;
851 } else {
852 ftwbuf->error = errno;
853 }
854 }
855
856 if (ftwbuf->depth == 0) {
857 // Compute the name offset for root paths like "foo/bar"
858 ftwbuf->nameoff = xbasename(ftwbuf->path) - ftwbuf->path;
859 }
860
861 if (ftwbuf->error != 0) {
862 ftwbuf->type = BFS_ERROR;
863 return;
864 }
865
866 int follow_flags = BFTW_FOLLOW_ALL;
867 if (ftwbuf->depth == 0) {
868 follow_flags |= BFTW_FOLLOW_ROOTS;
869 }
870 bool follow = state->flags & follow_flags;
871 if (follow) {
872 ftwbuf->stat_flags = BFS_STAT_TRYFOLLOW;
873 }
874
875 const struct bfs_stat *statbuf = NULL;
876 if (bftw_need_stat(state)) {
877 statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
878 if (statbuf) {
879 ftwbuf->type = bfs_mode_to_type(statbuf->mode);
880 } else {
881 ftwbuf->type = BFS_ERROR;
882 ftwbuf->error = errno;
883 return;
884 }
885 }
886
887 if (ftwbuf->type == BFS_DIR && (state->flags & BFTW_DETECT_CYCLES)) {
888 for (const struct bftw_file *ancestor = parent; ancestor; ancestor = ancestor->parent) {
889 if (ancestor->dev == statbuf->dev && ancestor->ino == statbuf->ino) {
890 ftwbuf->type = BFS_ERROR;
891 ftwbuf->error = ELOOP;
892 return;
893 }
894 }
895 }
896 }
897
898 /** Check if the current file is a mount point. */
bftw_is_mount(struct bftw_state * state,const char * name)899 static bool bftw_is_mount(struct bftw_state *state, const char *name) {
900 const struct bftw_file *file = state->file;
901 if (!file) {
902 return false;
903 }
904
905 const struct bftw_file *parent = name ? file : file->parent;
906 if (!parent) {
907 return false;
908 }
909
910 const struct BFTW *ftwbuf = &state->ftwbuf;
911 const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags);
912 return statbuf && statbuf->dev != parent->dev;
913 }
914
915 /** Fill file identity information from an ftwbuf. */
bftw_fill_id(struct bftw_file * file,const struct BFTW * ftwbuf)916 static void bftw_fill_id(struct bftw_file *file, const struct BFTW *ftwbuf) {
917 const struct bfs_stat *statbuf = ftwbuf->stat_cache.buf;
918 if (!statbuf || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) {
919 statbuf = ftwbuf->lstat_cache.buf;
920 }
921 if (statbuf) {
922 file->dev = statbuf->dev;
923 file->ino = statbuf->ino;
924 }
925 }
926
927 /**
928 * Visit a path, invoking the callback.
929 */
bftw_visit(struct bftw_state * state,const char * name,enum bftw_visit visit)930 static enum bftw_action bftw_visit(struct bftw_state *state, const char *name, enum bftw_visit visit) {
931 if (bftw_update_path(state, name) != 0) {
932 state->error = errno;
933 return BFTW_STOP;
934 }
935
936 const struct BFTW *ftwbuf = &state->ftwbuf;
937 bftw_init_ftwbuf(state, visit);
938
939 // Never give the callback BFS_ERROR unless BFTW_RECOVER is specified
940 if (ftwbuf->type == BFS_ERROR && !(state->flags & BFTW_RECOVER)) {
941 state->error = ftwbuf->error;
942 return BFTW_STOP;
943 }
944
945 if ((state->flags & BFTW_SKIP_MOUNTS) && bftw_is_mount(state, name)) {
946 return BFTW_PRUNE;
947 }
948
949 enum bftw_action ret = state->callback(ftwbuf, state->ptr);
950 switch (ret) {
951 case BFTW_CONTINUE:
952 break;
953 case BFTW_PRUNE:
954 case BFTW_STOP:
955 goto done;
956 default:
957 state->error = EINVAL;
958 return BFTW_STOP;
959 }
960
961 if (visit != BFTW_PRE || ftwbuf->type != BFS_DIR) {
962 ret = BFTW_PRUNE;
963 goto done;
964 }
965
966 if ((state->flags & BFTW_PRUNE_MOUNTS) && bftw_is_mount(state, name)) {
967 ret = BFTW_PRUNE;
968 goto done;
969 }
970
971 done:
972 if (state->file && !name) {
973 bftw_fill_id(state->file, ftwbuf);
974 }
975
976 return ret;
977 }
978
979 /**
980 * Push a new file onto the queue.
981 */
bftw_push(struct bftw_state * state,const char * name,bool fill_id)982 static int bftw_push(struct bftw_state *state, const char *name, bool fill_id) {
983 struct bftw_file *parent = state->file;
984 struct bftw_file *file = bftw_file_new(&state->cache, parent, name);
985 if (!file) {
986 state->error = errno;
987 return -1;
988 }
989
990 if (state->de) {
991 file->type = state->de->type;
992 }
993
994 if (fill_id) {
995 bftw_fill_id(file, &state->ftwbuf);
996 }
997
998 bftw_queue_push(&state->queue, file);
999
1000 return 0;
1001 }
1002
1003 /**
1004 * Build the path to the current file.
1005 */
bftw_build_path(struct bftw_state * state)1006 static int bftw_build_path(struct bftw_state *state) {
1007 const struct bftw_file *file = state->file;
1008
1009 size_t pathlen = file->nameoff + file->namelen;
1010 if (dstresize(&state->path, pathlen) != 0) {
1011 state->error = errno;
1012 return -1;
1013 }
1014
1015 // Try to find a common ancestor with the existing path
1016 const struct bftw_file *ancestor = state->previous;
1017 while (ancestor && ancestor->depth > file->depth) {
1018 ancestor = ancestor->parent;
1019 }
1020
1021 // Build the path backwards
1022 while (file && file != ancestor) {
1023 if (file->nameoff > 0) {
1024 state->path[file->nameoff - 1] = '/';
1025 }
1026 memcpy(state->path + file->nameoff, file->name, file->namelen);
1027
1028 if (ancestor && ancestor->depth == file->depth) {
1029 ancestor = ancestor->parent;
1030 }
1031 file = file->parent;
1032 }
1033
1034 state->previous = state->file;
1035 return 0;
1036 }
1037
1038 /**
1039 * Pop the next file from the queue.
1040 */
bftw_pop(struct bftw_state * state)1041 static int bftw_pop(struct bftw_state *state) {
1042 if (!state->queue.head) {
1043 return 0;
1044 }
1045
1046 state->file = bftw_queue_pop(&state->queue);
1047
1048 if (bftw_build_path(state) != 0) {
1049 return -1;
1050 }
1051
1052 return 1;
1053 }
1054
1055 /**
1056 * Open the current directory.
1057 */
bftw_opendir(struct bftw_state * state)1058 static void bftw_opendir(struct bftw_state *state) {
1059 assert(!state->dir);
1060 assert(!state->de);
1061
1062 state->direrror = 0;
1063
1064 state->dir = bftw_file_opendir(&state->cache, state->file, state->path);
1065 if (!state->dir) {
1066 state->direrror = errno;
1067 }
1068 }
1069
1070 /**
1071 * Read an entry from the current directory.
1072 */
bftw_readdir(struct bftw_state * state)1073 static int bftw_readdir(struct bftw_state *state) {
1074 if (!state->dir) {
1075 return -1;
1076 }
1077
1078 int ret = bfs_readdir(state->dir, &state->de_storage);
1079 if (ret > 0) {
1080 state->de = &state->de_storage;
1081 } else if (ret == 0) {
1082 state->de = NULL;
1083 } else {
1084 state->de = NULL;
1085 state->direrror = errno;
1086 }
1087
1088 return ret;
1089 }
1090
1091 /**
1092 * Flags controlling which files get visited when done with a directory.
1093 */
1094 enum bftw_gc_flags {
1095 /** Don't visit anything. */
1096 BFTW_VISIT_NONE = 0,
1097 /** Visit the file itself. */
1098 BFTW_VISIT_FILE = 1 << 0,
1099 /** Visit the file's ancestors. */
1100 BFTW_VISIT_PARENTS = 1 << 1,
1101 /** Visit both the file and its ancestors. */
1102 BFTW_VISIT_ALL = BFTW_VISIT_FILE | BFTW_VISIT_PARENTS,
1103 };
1104
1105 /**
1106 * Close the current directory.
1107 */
bftw_closedir(struct bftw_state * state,enum bftw_gc_flags flags)1108 static enum bftw_action bftw_closedir(struct bftw_state *state, enum bftw_gc_flags flags) {
1109 struct bftw_file *file = state->file;
1110 enum bftw_action ret = BFTW_CONTINUE;
1111
1112 if (state->dir) {
1113 assert(file->fd >= 0);
1114
1115 if (file->refcount > 1) {
1116 // Keep the fd around if any subdirectories exist
1117 file->fd = bfs_freedir(state->dir);
1118 } else {
1119 bfs_closedir(state->dir);
1120 file->fd = -1;
1121 }
1122
1123 if (file->fd < 0) {
1124 bftw_cache_remove(&state->cache, file);
1125 }
1126 }
1127
1128 state->de = NULL;
1129 state->dir = NULL;
1130
1131 if (state->direrror != 0) {
1132 if (flags & BFTW_VISIT_FILE) {
1133 ret = bftw_visit(state, NULL, BFTW_PRE);
1134 } else {
1135 state->error = state->direrror;
1136 }
1137 state->direrror = 0;
1138 }
1139
1140 return ret;
1141 }
1142
1143 /**
1144 * Finalize and free a file we're done with.
1145 */
bftw_gc_file(struct bftw_state * state,enum bftw_gc_flags flags)1146 static enum bftw_action bftw_gc_file(struct bftw_state *state, enum bftw_gc_flags flags) {
1147 enum bftw_action ret = BFTW_CONTINUE;
1148
1149 if (!(state->flags & BFTW_POST_ORDER)) {
1150 flags = 0;
1151 }
1152 bool visit = flags & BFTW_VISIT_FILE;
1153
1154 while (state->file) {
1155 if (bftw_file_decref(&state->cache, state->file) > 0) {
1156 state->file = NULL;
1157 break;
1158 }
1159
1160 if (visit && bftw_visit(state, NULL, BFTW_POST) == BFTW_STOP) {
1161 ret = BFTW_STOP;
1162 flags &= ~BFTW_VISIT_PARENTS;
1163 }
1164 visit = flags & BFTW_VISIT_PARENTS;
1165
1166 struct bftw_file *parent = state->file->parent;
1167 if (state->previous == state->file) {
1168 state->previous = parent;
1169 }
1170 bftw_file_free(&state->cache, state->file);
1171 state->file = parent;
1172 }
1173
1174 return ret;
1175 }
1176
1177 /**
1178 * Drain all the entries from a bftw_queue.
1179 */
bftw_drain_queue(struct bftw_state * state,struct bftw_queue * queue)1180 static void bftw_drain_queue(struct bftw_state *state, struct bftw_queue *queue) {
1181 while (queue->head) {
1182 state->file = bftw_queue_pop(queue);
1183 bftw_gc_file(state, BFTW_VISIT_NONE);
1184 }
1185 }
1186
1187 /**
1188 * Dispose of the bftw() state.
1189 *
1190 * @return
1191 * The bftw() return value.
1192 */
bftw_state_destroy(struct bftw_state * state)1193 static int bftw_state_destroy(struct bftw_state *state) {
1194 dstrfree(state->path);
1195
1196 bftw_closedir(state, BFTW_VISIT_NONE);
1197
1198 bftw_gc_file(state, BFTW_VISIT_NONE);
1199 bftw_drain_queue(state, &state->queue);
1200
1201 bftw_cache_destroy(&state->cache);
1202
1203 errno = state->error;
1204 return state->error ? -1 : 0;
1205 }
1206
1207 /** Start a batch of files. */
bftw_batch_start(struct bftw_state * state)1208 static void bftw_batch_start(struct bftw_state *state) {
1209 if (state->strategy == BFTW_DFS) {
1210 state->queue.target = &state->queue.head;
1211 }
1212 state->batch = state->queue.target;
1213 }
1214
1215 /** Finish adding a batch of files. */
bftw_batch_finish(struct bftw_state * state)1216 static void bftw_batch_finish(struct bftw_state *state) {
1217 if (state->flags & BFTW_SORT) {
1218 state->queue.target = bftw_sort_files(state->batch, state->queue.target);
1219 }
1220 }
1221
1222 /**
1223 * Streaming mode: visit files as they are encountered.
1224 */
bftw_stream(const struct bftw_args * args)1225 static int bftw_stream(const struct bftw_args *args) {
1226 struct bftw_state state;
1227 if (bftw_state_init(&state, args) != 0) {
1228 return -1;
1229 }
1230
1231 assert(!(state.flags & BFTW_SORT));
1232
1233 bftw_batch_start(&state);
1234 for (size_t i = 0; i < args->npaths; ++i) {
1235 const char *path = args->paths[i];
1236
1237 switch (bftw_visit(&state, path, BFTW_PRE)) {
1238 case BFTW_CONTINUE:
1239 break;
1240 case BFTW_PRUNE:
1241 continue;
1242 case BFTW_STOP:
1243 goto done;
1244 }
1245
1246 if (bftw_push(&state, path, true) != 0) {
1247 goto done;
1248 }
1249 }
1250 bftw_batch_finish(&state);
1251
1252 while (bftw_pop(&state) > 0) {
1253 bftw_opendir(&state);
1254
1255 bftw_batch_start(&state);
1256 while (bftw_readdir(&state) > 0) {
1257 const char *name = state.de->name;
1258
1259 switch (bftw_visit(&state, name, BFTW_PRE)) {
1260 case BFTW_CONTINUE:
1261 break;
1262 case BFTW_PRUNE:
1263 continue;
1264 case BFTW_STOP:
1265 goto done;
1266 }
1267
1268 if (bftw_push(&state, name, true) != 0) {
1269 goto done;
1270 }
1271 }
1272 bftw_batch_finish(&state);
1273
1274 if (bftw_closedir(&state, BFTW_VISIT_ALL) == BFTW_STOP) {
1275 goto done;
1276 }
1277 if (bftw_gc_file(&state, BFTW_VISIT_ALL) == BFTW_STOP) {
1278 goto done;
1279 }
1280 }
1281
1282 done:
1283 return bftw_state_destroy(&state);
1284 }
1285
1286 /**
1287 * Batching mode: queue up all children before visiting them.
1288 */
bftw_batch(const struct bftw_args * args)1289 static int bftw_batch(const struct bftw_args *args) {
1290 struct bftw_state state;
1291 if (bftw_state_init(&state, args) != 0) {
1292 return -1;
1293 }
1294
1295 bftw_batch_start(&state);
1296 for (size_t i = 0; i < args->npaths; ++i) {
1297 if (bftw_push(&state, args->paths[i], false) != 0) {
1298 goto done;
1299 }
1300 }
1301 bftw_batch_finish(&state);
1302
1303 while (bftw_pop(&state) > 0) {
1304 enum bftw_gc_flags gcflags = BFTW_VISIT_ALL;
1305
1306 switch (bftw_visit(&state, NULL, BFTW_PRE)) {
1307 case BFTW_CONTINUE:
1308 break;
1309 case BFTW_PRUNE:
1310 gcflags &= ~BFTW_VISIT_FILE;
1311 goto next;
1312 case BFTW_STOP:
1313 goto done;
1314 }
1315
1316 bftw_opendir(&state);
1317
1318 bftw_batch_start(&state);
1319 while (bftw_readdir(&state) > 0) {
1320 if (bftw_push(&state, state.de->name, false) != 0) {
1321 goto done;
1322 }
1323 }
1324 bftw_batch_finish(&state);
1325
1326 if (bftw_closedir(&state, gcflags) == BFTW_STOP) {
1327 goto done;
1328 }
1329
1330 next:
1331 if (bftw_gc_file(&state, gcflags) == BFTW_STOP) {
1332 goto done;
1333 }
1334 }
1335
1336 done:
1337 return bftw_state_destroy(&state);
1338 }
1339
1340 /** Select bftw_stream() or bftw_batch() appropriately. */
bftw_auto(const struct bftw_args * args)1341 static int bftw_auto(const struct bftw_args *args) {
1342 if (args->flags & BFTW_SORT) {
1343 return bftw_batch(args);
1344 } else {
1345 return bftw_stream(args);
1346 }
1347 }
1348
1349 /**
1350 * Iterative deepening search state.
1351 */
1352 struct bftw_ids_state {
1353 /** The wrapped callback. */
1354 bftw_callback *delegate;
1355 /** The wrapped callback arguments. */
1356 void *ptr;
1357 /** Which visit this search corresponds to. */
1358 enum bftw_visit visit;
1359 /** Whether to override the bftw_visit. */
1360 bool force_visit;
1361 /** The current minimum depth (inclusive). */
1362 size_t min_depth;
1363 /** The current maximum depth (exclusive). */
1364 size_t max_depth;
1365 /** The set of pruned paths. */
1366 struct trie pruned;
1367 /** An error code to report. */
1368 int error;
1369 /** Whether the bottom has been found. */
1370 bool bottom;
1371 /** Whether to quit the search. */
1372 bool quit;
1373 };
1374
1375 /** Iterative deepening callback function. */
bftw_ids_callback(const struct BFTW * ftwbuf,void * ptr)1376 static enum bftw_action bftw_ids_callback(const struct BFTW *ftwbuf, void *ptr) {
1377 struct bftw_ids_state *state = ptr;
1378
1379 if (state->force_visit) {
1380 struct BFTW *mutbuf = (struct BFTW *)ftwbuf;
1381 mutbuf->visit = state->visit;
1382 }
1383
1384 if (ftwbuf->type == BFS_ERROR) {
1385 if (ftwbuf->depth + 1 >= state->min_depth) {
1386 return state->delegate(ftwbuf, state->ptr);
1387 } else {
1388 return BFTW_PRUNE;
1389 }
1390 }
1391
1392 if (ftwbuf->depth < state->min_depth) {
1393 if (trie_find_str(&state->pruned, ftwbuf->path)) {
1394 return BFTW_PRUNE;
1395 } else {
1396 return BFTW_CONTINUE;
1397 }
1398 } else if (state->visit == BFTW_POST) {
1399 if (trie_find_str(&state->pruned, ftwbuf->path)) {
1400 return BFTW_PRUNE;
1401 }
1402 }
1403
1404 enum bftw_action ret = BFTW_CONTINUE;
1405 if (ftwbuf->visit == state->visit) {
1406 ret = state->delegate(ftwbuf, state->ptr);
1407 }
1408
1409 switch (ret) {
1410 case BFTW_CONTINUE:
1411 if (ftwbuf->type == BFS_DIR && ftwbuf->depth + 1 >= state->max_depth) {
1412 state->bottom = false;
1413 ret = BFTW_PRUNE;
1414 }
1415 break;
1416 case BFTW_PRUNE:
1417 if (ftwbuf->type == BFS_DIR) {
1418 if (!trie_insert_str(&state->pruned, ftwbuf->path)) {
1419 state->error = errno;
1420 state->quit = true;
1421 ret = BFTW_STOP;
1422 }
1423 }
1424 break;
1425 case BFTW_STOP:
1426 state->quit = true;
1427 break;
1428 }
1429
1430 return ret;
1431 }
1432
1433 /** Initialize iterative deepening state. */
bftw_ids_init(const struct bftw_args * args,struct bftw_ids_state * state,struct bftw_args * ids_args)1434 static void bftw_ids_init(const struct bftw_args *args, struct bftw_ids_state *state, struct bftw_args *ids_args) {
1435 state->delegate = args->callback;
1436 state->ptr = args->ptr;
1437 state->visit = BFTW_PRE;
1438 state->force_visit = false;
1439 state->min_depth = 0;
1440 state->max_depth = 1;
1441 trie_init(&state->pruned);
1442 state->error = 0;
1443 state->bottom = false;
1444 state->quit = false;
1445
1446 *ids_args = *args;
1447 ids_args->callback = bftw_ids_callback;
1448 ids_args->ptr = state;
1449 ids_args->flags &= ~BFTW_POST_ORDER;
1450 ids_args->strategy = BFTW_DFS;
1451 }
1452
1453 /** Finish an iterative deepening search. */
bftw_ids_finish(struct bftw_ids_state * state)1454 static int bftw_ids_finish(struct bftw_ids_state *state) {
1455 int ret = 0;
1456
1457 if (state->error) {
1458 ret = -1;
1459 } else {
1460 state->error = errno;
1461 }
1462
1463 trie_destroy(&state->pruned);
1464
1465 errno = state->error;
1466 return ret;
1467 }
1468
1469 /**
1470 * Iterative deepening bftw() wrapper.
1471 */
bftw_ids(const struct bftw_args * args)1472 static int bftw_ids(const struct bftw_args *args) {
1473 struct bftw_ids_state state;
1474 struct bftw_args ids_args;
1475 bftw_ids_init(args, &state, &ids_args);
1476
1477 while (!state.quit && !state.bottom) {
1478 state.bottom = true;
1479
1480 if (bftw_auto(&ids_args) != 0) {
1481 state.error = errno;
1482 state.quit = true;
1483 }
1484
1485 ++state.min_depth;
1486 ++state.max_depth;
1487 }
1488
1489 if (args->flags & BFTW_POST_ORDER) {
1490 state.visit = BFTW_POST;
1491 state.force_visit = true;
1492
1493 while (!state.quit && state.min_depth > 0) {
1494 --state.max_depth;
1495 --state.min_depth;
1496
1497 if (bftw_auto(&ids_args) != 0) {
1498 state.error = errno;
1499 state.quit = true;
1500 }
1501 }
1502 }
1503
1504 return bftw_ids_finish(&state);
1505 }
1506
1507 /**
1508 * Exponential deepening bftw() wrapper.
1509 */
bftw_eds(const struct bftw_args * args)1510 static int bftw_eds(const struct bftw_args *args) {
1511 struct bftw_ids_state state;
1512 struct bftw_args ids_args;
1513 bftw_ids_init(args, &state, &ids_args);
1514
1515 while (!state.quit && !state.bottom) {
1516 state.bottom = true;
1517
1518 if (bftw_auto(&ids_args) != 0) {
1519 state.error = errno;
1520 state.quit = true;
1521 }
1522
1523 state.min_depth = state.max_depth;
1524 state.max_depth *= 2;
1525 }
1526
1527 if (!state.quit && (args->flags & BFTW_POST_ORDER)) {
1528 state.visit = BFTW_POST;
1529 state.min_depth = 0;
1530 ids_args.flags |= BFTW_POST_ORDER;
1531
1532 if (bftw_auto(&ids_args) != 0) {
1533 state.error = errno;
1534 }
1535 }
1536
1537 return bftw_ids_finish(&state);
1538 }
1539
bftw(const struct bftw_args * args)1540 int bftw(const struct bftw_args *args) {
1541 switch (args->strategy) {
1542 case BFTW_BFS:
1543 return bftw_auto(args);
1544 case BFTW_DFS:
1545 return bftw_batch(args);
1546 case BFTW_IDS:
1547 return bftw_ids(args);
1548 case BFTW_EDS:
1549 return bftw_eds(args);
1550 }
1551
1552 errno = EINVAL;
1553 return -1;
1554 }
1555