summaryrefslogtreecommitdiffstats
path: root/src/bftw.c
Commit message (Collapse)AuthorAgeFilesLines
* 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
|
* bfstd: Rename from util and reorganize itTavian Barnes2022-11-061-1/+1
|
* Source / Include Folder (#88)トトも2022-04-161-0/+1494
Moved Source Files Into `src` Folder
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-12 11:14:53 +0000