summaryrefslogtreecommitdiffstats
path: root/src/bftw.c
Commit message (Collapse)AuthorAgeFilesLines
* 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
* bftw: Reserve space in the cache before opening filesTavian Barnes2023-07-171-3/+15
| | | | | | | This fixes a storm of EMFILE retries observed with -j1 on a very large directory tree. Fixes: 7888fbababd22190e9f919fc272957426a27969e
* bftw: Pass the whole bftw_state to bftw_openat()Tavian Barnes2023-07-171-510/+451
| | | | | This required shuffling a lot of code around. Hopefully the new order makes more sense.
* bftw: Add bfs_dir allocation wrappersTavian Barnes2023-07-171-9/+19
|
* bftw: Try to close files asynchronouslyTavian Barnes2023-07-101-36/+139
|
* ioq: Implement async close() and closedir()Tavian Barnes2023-07-101-18/+23
|
* bftw: If the ioq is full, try to pop before ioq_opendir()Tavian Barnes2023-07-071-49/+82
|
* ioq: New ioq_cancel() functionTavian Barnes2023-06-261-0/+4
|
* dir: Arena-allocate directoriesTavian Barnes2023-06-201-8/+29
|
* bftw: Arena-allocate struct bftw_fileTavian Barnes2023-06-201-5/+11
|
* alloc: New header for memory allocation utilitiesTavian Barnes2023-06-201-3/+2
|
* bftw: Use an I/O queue to open directoriesTavian Barnes2023-06-131-7/+147
| | | | Parallelism is controlled by the new -j flag.
* bftw: Implement open file pinningTavian Barnes2023-06-121-32/+100
|
* dir: Add a flag to bfs_freedir() to force the fd to stay the sameTavian Barnes2023-06-121-2/+2
|
* list: Allow popping from an empty listTavian Barnes2023-05-241-16/+3
|
* list: Return the removed item from SLIST_POP()Tavian Barnes2023-05-201-4/+2
|
* Switch from assert() to bfs_assert()/bfs_verify()Tavian Barnes2023-05-181-14/+14
|
* config: Provide <stdalign.h> and <stdbool.h>Tavian Barnes2023-05-111-1/+0
| | | | In anticipation of C23, since those headers won't be necessary any more.
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-01 16:21:18 +0000