summaryrefslogtreecommitdiffstats
path: root/src/bftw.c
Commit message (Collapse)AuthorAgeFilesLines
* 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.
* config: s/BFS_FALLTHROUGH/fallthru/Tavian Barnes2023-05-101-1/+1
|
* config: s/BFS_FLEX_SIZEOF/flex_sizeof/Tavian Barnes2023-05-101-1/+1
|
* bftw: Use separate dir/file queuesTavian Barnes2023-05-051-218/+176
|
* bftw: Merge bftw_closedir() into bftw_gc()Tavian Barnes2023-04-121-59/+47
|
* list: Use macros instead of type-erased listsTavian Barnes2023-03-311-42/+94
|
* list: New helper macros for converting entries to itemsTavian Barnes2023-03-291-13/+5
|
* bftw: Use list.h for the queue and LRU listsTavian Barnes2023-03-291-218/+93
|
* bftw: Refactor bftw_queueTavian Barnes2023-03-281-88/+55
|
* Replace license boilerplate with SPDX tagsTavian Barnes2023-01-251-15/+2
| | | | | | | And while I'm at it, remove years from copyright declarations. Link: https://spdx.dev/about/ Link: https://daniel.haxx.se/blog/2023/01/08/copyright-without-years/
* bfstd: New wrappers for dirname()/basename()Tavian Barnes2023-01-191-1/+1
|
* Fix includesTavian Barnes2022-11-061-2/+1
|
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-24 12:29:56 +0000