summaryrefslogtreecommitdiffstats
path: root/src/bftw.c
Commit message (Collapse)AuthorAgeFilesLines
* alloc: Don't require the old size in varena_realloc()Tavian Barnes2024-11-021-1/+1
| | | | Instead, just look up which arena contains the pointer.
* Fix spellingTavian Barnes2024-09-231-1/+1
|
* list: New drain_slist() macroTavian Barnes2024-09-191-5/+6
|
* build: Move feature test macros to prelude.hTavian Barnes2024-08-281-1/+0
| | | | | | This replaces the explicit CPPFLAGS list in flags.mk with just `-include src/prelude.h`, shortening our compiler command lines and allowing them to be easily documented.
* prelude: Split bfs-specific utilities into new bfs.h headerTavian Barnes2024-08-281-0/+3
|
* bftw: Handle a hypothetical platform where AT_FDCWD == -1Tavian Barnes2024-08-281-2/+2
|
* prelude: s/fallthru/_fallthrough/ for consistency with other attributesTavian Barnes2024-08-091-1/+1
|
* bftw: Only resize the string once in bftw_build_path()Tavian Barnes2024-06-181-19/+22
|
* eval: Print more information on filesystem loopsTavian Barnes2024-05-271-0/+2
|
* configure: Use --with/--without for librariesTavian Barnes2024-05-241-1/+1
|
* Cast AT_FDCWD to int for comparisonsTavian Barnes2024-05-171-3/+3
| | | | | Some platforms define AT_FDCWD to a constant like 0xFFFAFDCD that gets typed as an unsigned int.
* Rename config.h to prelude.hTavian Barnes2024-04-191-1/+1
|
* bftw: Use a signed integer for dir_limitTavian Barnes2024-03-221-25/+8
|
* Re-run include-what-you-useTavian Barnes2024-03-111-0/+1
|
* bftw: Document which bftw_file nodes go with which listsTavian Barnes2024-02-141-3/+17
|
* bftw: stat() files asynchronouslyTavian Barnes2024-02-061-191/+486
|
* mtab: Take the basename directly in bfs_might_be_mount()Tavian Barnes2024-02-051-1/+1
| | | | This avoids some hot xbaseoff() calls.
* bftw: Always block in bftw_pop_dir() with multiple threadsTavian Barnes2024-02-011-11/+22
|
* bftw: Don't immediately pin open directoriesTavian Barnes2024-02-011-4/+5
| | | | | | | It is undesirable to close a directory that we haven't read yet to free up cache capacity, but it's worse to fail to open the next directory because too many upcoming directories are pinned. This could happen when sorting, because then we can't prioritize the already-opened ones.
* bftw: Allow forcing bfs_dir allocation from the main threadTavian Barnes2024-02-011-12/+35
| | | | | | | | | When sorting, we can be forced to pop an unopened directory. If enough other directories are already open, that can lead to ENOMEM when we try to open it synchronously. To avoid this, force allocations from the main thread to be attempted even if they would go over the limit. Also, fix the accounting in bftw_allocdir() if allocation fails.
* bftw: Kill trivial bftw_queue_balance() helperTavian Barnes2024-02-011-7/+2
|
* bftw: Actually stop if the callback returns BFTW_STOPTavian Barnes2024-01-311-1/+1
| | | | | | Otherwise, bftw_ids() or bftw_eds() might keep going! Fixes: 5f16169 ("bftw: Share the bftw_state between iterations of ids/eds")
* bftw: Optimize -s -j2 searchesTavian Barnes2024-01-311-2/+1
| | | | | Maintaining balance and strict ordering at the same time forces too much work onto the main thread.
* bftw: Use a bftw_queue for files tooTavian Barnes2024-01-311-26/+31
|
* bftw: New bftw_queue abstractionTavian Barnes2024-01-311-74/+292
|
* ioq: Implement ioq_stat()Tavian Barnes2024-01-181-0/+3
|
* ioq: Use the negative errno conventionTavian Barnes2024-01-131-1/+1
|
* bfstd: New {error,errno}_is_like() functionsTavian Barnes2024-01-131-15/+3
| | | | | | | We used to have is_nonexistence_error() to consistently treat ENOENT and ENOTDIR the same. Recently, we started considering EFAULT the same as ENAMETOOLONG on DragonFly BSD to work around a kernel bug. Unify both of these behind a more generic interface.
* Work around DragonFly BSD kernel bugTavian Barnes2024-01-041-1/+13
| | | | | | | | | DragonFly's x86_64 assembly implementation of copyinstr() checks the wrong pointer when deciding whether to return EFAULT or ENAMETOOLONG, causing it to always return EFAULT for overlong paths. Work around it by treating EFAULT the same as ENAMETOOLONG on DragonFly. Link: https://twitter.com/tavianator/status/1742991411203485713
* ioq: Implement a better non-blocking popTavian Barnes2023-11-091-1/+1
|
* bftw: Improve ioq balancing logicTavian Barnes2023-11-011-13/+22
|
* bftw: Leave work for the main thread if profitableTavian Barnes2023-10-311-4/+13
|
* bftw: New flag to control whiteout visibilityTavian Barnes2023-10-171-2/+16
|
* dir: Add a flags parameter to bfs_opendir()Tavian Barnes2023-10-171-2/+2
|
* bftw: Make sure we don't close a directory while we unwrap itTavian Barnes2023-10-121-2/+6
| | | | | | | bftw_cache_reserve() can lead to bftw_cache_pop(), which could close the directory we're trying to unwrap! If that happened, we would try dup_cloexec(-1), which would fail with EBADF, so there was no observable bug. But it's better to avoid the whole situation.
* bftw: Fix to_close list corruption with !BFS_USE_UNWRAPDIRTavian Barnes2023-10-121-6/+13
| | | | | | | | | | It's possible for pincount to drop to zero, then get incremented and drop back to zero again. If this happens, we shouldn't add it to the to_close list twice. This should fix the intermittent hang on the macOS CI. Fixes: 815798e1eea7fc8dacd5acab40202ec4d251d517
* bftw: Don't force buffering for parallel dfsTavian Barnes2023-10-121-5/+30
|
* bftw: Fix unbuffered depth-first searchesTavian Barnes2023-10-121-15/+41
| | | | | | | | | | | | | | | bftw() implements depth-first search by appending files to a batch, then prepending the batch to the queue. When we switched to separate file/ directory queues, this was only implemented for the file queue. Unbuffered searches don't use the file queue, so they were all breadth- first in practice. This meant that iterative deepening (-S ids) was actually "iterative deepening *breadth*-first search," a horrible strategy with no advantage over regular breadth-first search. Now it performs iterative deepening *depth*-first search, which at least limits its memory consumption. Fixes: c1b16b49988ecff17ae30978ea14798d95b80018
* bftw: Let iterative deepening work depth-first when sortingTavian Barnes2023-10-121-1/+1
|
* ioq: Use io_uringTavian Barnes2023-10-021-5/+18
| | | | Closes #65.
* dstring: New dchar typedef for dynamic stringsTavian Barnes2023-09-261-1/+1
|
* Use the new list macrosTavian Barnes2023-09-251-13/+11
|
* bftw: Share the bftw_state between iterations of ids/edsTavian Barnes2023-09-131-72/+71
|
* bftw: Enforce the dirlimit strictlyTavian Barnes2023-09-061-19/+17
| | | | | | The previous accounting didn't fully control the number of allocated bfs_dirs, as the dirlimit was incremented once we popped the directory, not when we freed it.
* bftw: Use bftw_file->next for multiple listsTavian Barnes2023-07-181-29/+21
| | | | | A file can be on the to_open and to_read lists at the same time, but otherwise only one list, so we can save memory by sharing the pointers.
* bftw: Use a larger ioq depthTavian Barnes2023-07-181-22/+12
| | | | | | | Now that the dirlimit provides backpressure on the number of open directories, we can use a uniformly larger queue depth for increased performance. The current parameters were tuned with a small grid search on my workstation.
* bftw: Add a queue of directories to unwrapTavian Barnes2023-07-181-7/+22
| | | | | | | | For !BFS_USE_UNWRAPDIR, if a file is still pinned in bftw_closedir(), it has to stay open until its pincount drops to zero. Since this happens in bftw_ioq_pop(), we can't immediately call bftw_unwrapdir() as that adds to the ioq. Instead, add it to a list that gets drained by the next bftw_gc().
* bftw: Add dirs to the end of the queue in bftw_ioq_pop()Tavian Barnes2023-07-181-11/+25
| | | | | | I tried this before in #105 but it led to performance regressions. The key to avoiding those regressions is to put some backpressure on how many bfs_dir's can be allocated simultaneously.
* bftw: Use separate queues for open and closed directoriesTavian Barnes2023-07-171-89/+115
|
* bftw: Check that file->fd == bfs_dirfd(file->dir) earlierTavian Barnes2023-07-171-2/+3
| | | | | | | This has the potential to fail on at least one known platform: macports with the legacysupport implementation of fdopendir(). Link: https://github.com/macports/macports-ports/pull/19047#issuecomment-1636059809
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-23 05:20:59 +0000