Something went wrong. Try again.
A breadth-first version of the UNIX find command tavianator.com/projects/bfs.html
Something went wrong. Try again.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347// Copyright © Tavian Barnes <tavianator@tavianator.com>// SPDX-License-Identifier: 0BSD
/** * The bftw() implementation consists of the following components: * * - struct bftw_file: A file that has been encountered during the traversal. * They have reference-counted links to their parents in the directory tree. * * - struct bftw_list: A linked list of bftw_file's. * * - struct bftw_queue: A multi-stage queue of bftw_file's. * * - struct bftw_cache: An LRU list of bftw_file's with open file descriptors, * used for openat() to minimize the amount of path re-traversals. * * - struct bftw_state: Represents the current state of the traversal, allowing * various helper functions to take fewer parameters. */
#include "bftw.h"
#include "alloc.h"#include "bfs.h"#include "bfstd.h"#include "diag.h"#include "dir.h"#include "dstring.h"#include "ioq.h"#include "list.h"#include "mtab.h"#include "stat.h"#include "trie.h"
#include <errno.h>#include <fcntl.h>#include <stdlib.h>#include <string.h>#include <sys/stat.h>#include <sys/types.h>
/** Initialize a bftw_stat cache. */static void bftw_stat_init(struct bftw_stat *bufs, struct bfs_stat *stat_buf, struct bfs_stat *lstat_buf) { bufs->stat_buf = stat_buf; bufs->lstat_buf = lstat_buf; bufs->stat_err = -1; bufs->lstat_err = -1;}
/** Fill a bftw_stat cache from another one. */static void bftw_stat_fill(struct bftw_stat *dest, const struct bftw_stat *src) { if (dest->stat_err < 0 && src->stat_err >= 0) { dest->stat_buf = src->stat_buf; dest->stat_err = src->stat_err; }
if (dest->lstat_err < 0 && src->lstat_err >= 0) { dest->lstat_buf = src->lstat_buf; dest->lstat_err = src->lstat_err; }}
/** Cache a bfs_stat() result. */static void bftw_stat_cache(struct bftw_stat *bufs, enum bfs_stat_flags flags, const struct bfs_stat *buf, int err) { if (flags & BFS_STAT_NOFOLLOW) { bufs->lstat_buf = buf; bufs->lstat_err = err; if (err || !S_ISLNK(buf->mode)) { // Non-link, so share stat info bufs->stat_buf = buf; bufs->stat_err = err; } } else if (flags & BFS_STAT_TRYFOLLOW) { if (err) { bufs->stat_err = err; } else if (S_ISLNK(buf->mode)) { bufs->lstat_buf = buf; bufs->lstat_err = err; bufs->stat_err = ENOENT; } else { bufs->stat_buf = buf; bufs->stat_err = err; } } else { bufs->stat_buf = buf; bufs->stat_err = err; }}
/** Caching bfs_stat(). */static const struct bfs_stat *bftw_stat_impl(struct BFTW *ftwbuf, enum bfs_stat_flags flags) { struct bftw_stat *bufs = &ftwbuf->stat_bufs; struct bfs_stat *buf;
if (flags & BFS_STAT_NOFOLLOW) { buf = (struct bfs_stat *)bufs->lstat_buf; if (bufs->lstat_err == 0) { return buf; } else if (bufs->lstat_err > 0) { errno = bufs->lstat_err; return NULL; } } else { buf = (struct bfs_stat *)bufs->stat_buf; if (bufs->stat_err == 0) { return buf; } else if (bufs->stat_err > 0) { errno = bufs->stat_err; return NULL; } }
struct bfs_stat *ret; int err; if (bfs_stat(ftwbuf->at_fd, ftwbuf->at_path, flags, buf) == 0) { ret = buf; err = 0;#ifdef S_IFWHT } else if (errno == ENOENT && ftwbuf->type == BFS_WHT) { // This matches the behavior of FTS_WHITEOUT on BSD ret = memset(buf, 0, sizeof(*buf)); ret->mode = S_IFWHT; err = 0;#endif } else { ret = NULL; err = errno; }
bftw_stat_cache(bufs, flags, ret, err); return ret;}
const struct bfs_stat *bftw_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) { struct BFTW *mutbuf = (struct BFTW *)ftwbuf; const struct bfs_stat *ret;
if (flags & BFS_STAT_TRYFOLLOW) { ret = bftw_stat_impl(mutbuf, BFS_STAT_FOLLOW); if (!ret && errno_is_like(ENOENT)) { ret = bftw_stat_impl(mutbuf, BFS_STAT_NOFOLLOW); } } else { ret = bftw_stat_impl(mutbuf, flags); }
return ret;}
const struct bfs_stat *bftw_cached_stat(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) { const struct bftw_stat *bufs = &ftwbuf->stat_bufs;
if (flags & BFS_STAT_NOFOLLOW) { if (bufs->lstat_err == 0) { return bufs->lstat_buf; } } else if (bufs->stat_err == 0) { return bufs->stat_buf; } else if ((flags & BFS_STAT_TRYFOLLOW) && error_is_like(bufs->stat_err, ENOENT)) { if (bufs->lstat_err == 0) { return bufs->lstat_buf; } }
return NULL;}
enum bfs_type bftw_type(const struct BFTW *ftwbuf, enum bfs_stat_flags flags) { if (flags & BFS_STAT_NOFOLLOW) { if (ftwbuf->type == BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_NOFOLLOW)) { return ftwbuf->type; } } else if (flags & BFS_STAT_TRYFOLLOW) { if (ftwbuf->type != BFS_LNK || (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW)) { return ftwbuf->type; } } else { if (ftwbuf->type != BFS_LNK) { return ftwbuf->type; } else if (ftwbuf->stat_flags & BFS_STAT_TRYFOLLOW) { return BFS_ERROR; } }
const struct bfs_stat *statbuf = bftw_stat(ftwbuf, flags); if (statbuf) { return bfs_mode_to_type(statbuf->mode); } else { return BFS_ERROR; }}
/** * A file. */struct bftw_file { /** The parent directory, if any. */ struct bftw_file *parent; /** The root under which this file was found. */ struct bftw_file *root;
/** * List node for: * * bftw_queue::buffer * bftw_queue::waiting * bftw_file_open()::parents */ struct bftw_file *next;
/** * List node for: * * bftw_queue::ready * bftw_state::to_close */ struct { struct bftw_file *next; } ready;
/** * List node for bftw_cache. */ struct { struct bftw_file *prev; struct bftw_file *next; } lru;
/** This file's depth in the walk. */ size_t depth; /** Reference count (for ->parent). */ size_t refcount;
/** Pin count (for ->fd). */ size_t pincount; /** An open descriptor to this file, or -1. */ int fd; /** Whether this file has a pending ioq request. */ bool ioqueued; /** An open directory for this file, if any. */ struct bfs_dir *dir;
/** This file's type, if known. */ enum bfs_type type; /** The device number, for cycle detection. */ dev_t dev; /** The inode number, for cycle detection. */ ino_t ino;
/** Cached bfs_stat() info. */ struct bftw_stat stat_bufs;
/** The offset of this file in the full path. */ size_t nameoff; /** The length of the file's name. */ size_t namelen; /** The file's name. */ // [[_counted_by(namelen + 1)]] char name[];};
/** * A linked list of bftw_file's. */struct bftw_list { struct bftw_file *head; struct bftw_file **tail;};
/** * bftw_queue flags. */enum bftw_qflags { /** Track the sync/async service balance. */ BFTW_QBALANCE = 1 << 0, /** Buffer files before adding them to the queue. */ BFTW_QBUFFER = 1 << 1, /** Use LIFO (stack/DFS) ordering. */ BFTW_QLIFO = 1 << 2, /** Maintain a strict order. */ BFTW_QORDER = 1 << 3,};
/** * A queue of bftw_file's that may be serviced asynchronously. * * A bftw_queue comprises three linked lists each tracking different stages. * When BFTW_QBUFFER is set, files are initially pushed to the buffer: * * ╔═══╗ ╔═══╦═══╗ * buffer: ║ 𝘩 ║ ║ 𝘩 ║ 𝘪 ║ * ╠═══╬═══╦═══╗ ╠═══╬═══╬═══╗ * waiting: ║ e ║ f ║ g ║ → ║ e ║ f ║ g ║ * ╠═══╬═══╬═══╬═══╗ ╠═══╬═══╬═══╬═══╗ * ready: ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║ ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║ * ╚═══╩═══╩═══╩═══╝ ╚═══╩═══╩═══╩═══╝ * * When bftw_queue_flush() is called, the files in the buffer are appended to * the waiting list (or prepended, if BFTW_QLIFO is set): * * ╔═╗ * buffer: ║ ║ * ╠═╩═╦═══╦═══╦═══╦═══╗ * waiting: ║ e ║ f ║ g ║ h ║ i ║ * ╠═══╬═══╬═══╬═══╬═══╝ * ready: ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║ * ╚═══╩═══╩═══╩═══╝ * * Using the buffer gives a more natural ordering for BFTW_QLIFO, and allows * files to be sorted before adding them to the waiting list. If BFTW_QBUFFER * is not set, files are pushed directly to the waiting list instead. * * Files on the waiting list are waiting to be "serviced" asynchronously by the * ioq (for example, by an ioq_opendir() or ioq_stat() call). While they are * being serviced, they are detached from the queue by bftw_queue_detach() and * are not tracked by the queue at all: * * ╔═╗ * buffer: ║ ║ * ╠═╩═╦═══╦═══╗ ⎛ ┌───┬───┐ ⎞ * waiting: ║ g ║ h ║ i ║ ⎜ ioq: │ 𝓮 │ 𝓯 │ ⎟ * ╠═══╬═══╬═══╬═══╗ ⎝ └───┴───┘ ⎠ * ready: ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║ * ╚═══╩═══╩═══╩═══╝ * * When their async service is complete, files are reattached to the queue by * bftw_queue_attach(), this time on the ready list: * * ╔═╗ * buffer: ║ ║ * ╠═╩═╦═══╦═══╗ ⎛ ┌───┐ ⎞ * waiting: ║ g ║ h ║ i ║ ⎜ ioq: │ 𝓮 │ ⎟ * ╠═══╬═══╬═══╬═══╦═══╗ ⎝ └───┘ ⎠ * ready: ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║ 𝕗 ║ * ╚═══╩═══╩═══╩═══╩═══╝ * * Files are added to the ready list in the order they are finished by the ioq. * bftw_queue_pop() pops a file from the ready list if possible. Otherwise, it * pops from the waiting list, and the file must be serviced synchronously. * * However, if BFTW_QORDER is set, files must be popped in the exact order they * are added to the waiting list (to maintain sorted order). In this case, * files are added to the waiting and ready lists at the same time. The * file->ioqueued flag is set while it is in-service, so that bftw() can wait * for it to be truly ready before using it. * * ╔═╗ * buffer: ║ ║ * ╠═╩═╦═══╦═══╗ ⎛ ┌───┐ ⎞ * waiting: ║ g ║ h ║ i ║ ⎜ ioq: │ 𝓮 │ ⎟ * ╠═══╬═══╬═══╬═══╦═══╦═══╦═══╦═══╦═══╗ ⎝ └───┘ ⎠ * ready: ║ 𝕒 ║ 𝕓 ║ 𝕔 ║ 𝕕 ║ 𝓮 ║ 𝕗 ║ g ║ h ║ i ║ * ╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝ * * If BFTW_QBALANCE is set, queue->imbalance tracks the delta between async * service (negative) and synchronous service (positive). The queue is * considered "balanced" when this number is non-negative. Only a balanced * queue will perform any async service, ensuring work is fairly distributed * between the main thread and the ioq. * * BFTW_QBALANCE is only set for single-threaded ioqs. When an ioq has multiple * threads, it is faster to wait for the ioq to complete an operation than it is * to perform it on the main thread. */struct bftw_queue { /** Queue flags. */ enum bftw_qflags flags; /** A buffer of files to be enqueued together. */ struct bftw_list buffer; /** A list of files which are waiting to be serviced. */ struct bftw_list waiting; /** A list of already-serviced files. */ struct bftw_list ready; /** The current size of the queue. */ size_t size; /** The number of files currently in-service. */ size_t ioqueued; /** Tracks the imbalance between synchronous and async service. */ unsigned long imbalance;};
/** Initialize a queue. */static void bftw_queue_init(struct bftw_queue *queue, enum bftw_qflags flags) { queue->flags = flags; SLIST_INIT(&queue->buffer); SLIST_INIT(&queue->waiting); SLIST_INIT(&queue->ready); queue->size = 0; queue->ioqueued = 0; queue->imbalance = 0;}
/** Add a file to the queue. */static void bftw_queue_push(struct bftw_queue *queue, struct bftw_file *file) { if (queue->flags & BFTW_QBUFFER) { SLIST_APPEND(&queue->buffer, file); } else if (queue->flags & BFTW_QLIFO) { SLIST_PREPEND(&queue->waiting, file); if (queue->flags & BFTW_QORDER) { SLIST_PREPEND(&queue->ready, file, ready); } } else { SLIST_APPEND(&queue->waiting, file); if (queue->flags & BFTW_QORDER) { SLIST_APPEND(&queue->ready, file, ready); } }
++queue->size;}
/** Add any buffered files to the queue. */static void bftw_queue_flush(struct bftw_queue *queue) { if (!(queue->flags & BFTW_QBUFFER)) { return; }
if (queue->flags & BFTW_QORDER) { // When sorting, add files to the ready list at the same time // (and in the same order) as they are added to the waiting list struct bftw_file **cursor = (queue->flags & BFTW_QLIFO) ? &queue->ready.head : queue->ready.tail; for_slist (struct bftw_file, file, &queue->buffer) { cursor = SLIST_INSERT(&queue->ready, cursor, file, ready); } }
if (queue->flags & BFTW_QLIFO) { SLIST_EXTEND(&queue->buffer, &queue->waiting); }
SLIST_EXTEND(&queue->waiting, &queue->buffer);}
/** Check if the queue is properly balanced for async work. */static bool bftw_queue_balanced(const struct bftw_queue *queue) { if (queue->flags & BFTW_QBALANCE) { return (long)queue->imbalance >= 0; } else { return true; }}
/** Update the queue balance for (a)sync service. */static void bftw_queue_rebalance(struct bftw_queue *queue, bool async) { if (async) { --queue->imbalance; } else { ++queue->imbalance; }}
/** Detach the next waiting file. */static void bftw_queue_detach(struct bftw_queue *queue, struct bftw_file *file, bool async) { bfs_assert(!file->ioqueued);
if (file == SLIST_HEAD(&queue->buffer)) { // To maintain order, we can't detach any files until they're // added to the waiting/ready lists bfs_assert(!(queue->flags & BFTW_QORDER)); SLIST_POP(&queue->buffer); } else if (file == SLIST_HEAD(&queue->waiting)) { SLIST_POP(&queue->waiting); } else { bfs_bug("Detached file was not buffered or waiting"); }
if (async) { file->ioqueued = true; ++queue->ioqueued; bftw_queue_rebalance(queue, true); }}
/** Reattach a serviced file to the queue. */static void bftw_queue_attach(struct bftw_queue *queue, struct bftw_file *file, bool async) { if (async) { bfs_assert(file->ioqueued); file->ioqueued = false; --queue->ioqueued; } else { bfs_assert(!file->ioqueued); }
if (!(queue->flags & BFTW_QORDER)) { SLIST_APPEND(&queue->ready, file, ready); }}
/** Make a file ready immediately. */static void bftw_queue_skip(struct bftw_queue *queue, struct bftw_file *file) { bftw_queue_detach(queue, file, false); bftw_queue_attach(queue, file, false);}
/** Get the next waiting file. */static struct bftw_file *bftw_queue_waiting(const struct bftw_queue *queue) { if (!(queue->flags & BFTW_QBUFFER)) { return SLIST_HEAD(&queue->waiting); }
if (queue->flags & BFTW_QORDER) { // Don't detach files until they're on the waiting/ready lists return SLIST_HEAD(&queue->waiting); }
const struct bftw_list *prefix = &queue->waiting; const struct bftw_list *suffix = &queue->buffer; if (queue->flags & BFTW_QLIFO) { prefix = &queue->buffer; suffix = &queue->waiting; }
struct bftw_file *file = SLIST_HEAD(prefix); if (!file) { file = SLIST_HEAD(suffix); } return file;}
/** Get the next ready file. */static struct bftw_file *bftw_queue_ready(const struct bftw_queue *queue) { return SLIST_HEAD(&queue->ready);}
/** Pop a file from the queue. */static struct bftw_file *bftw_queue_pop(struct bftw_queue *queue) { // Don't pop until we've had a chance to sort the buffer bfs_assert(SLIST_EMPTY(&queue->buffer));
struct bftw_file *file = SLIST_POP(&queue->ready, ready);
if (!file || file == SLIST_HEAD(&queue->waiting)) { // If no files are ready, try the waiting list. Or, if // BFTW_QORDER is set, we may need to pop from both lists. file = SLIST_POP(&queue->waiting); }
if (file) { --queue->size; }
return file;}
/** * A cache of open directories. */struct bftw_cache { /** The head of the LRU list. */ struct bftw_file *head; /** The tail of the LRU list. */ struct bftw_file *tail; /** The insertion target for the LRU list. */ struct bftw_file *target; /** The remaining capacity of the LRU list. */ size_t capacity;
/** bftw_file arena. */ struct varena files;
/** bfs_dir arena. */ struct arena dirs; /** Remaining bfs_dir capacity. */ int dir_limit;
/** bfs_stat arena. */ struct arena stat_bufs;};
/** Initialize a cache. */static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) { LIST_INIT(cache); cache->target = NULL; cache->capacity = capacity;
VARENA_INIT(&cache->files, struct bftw_file, name);
bfs_dir_arena(&cache->dirs);
if (cache->capacity > 1024) { cache->dir_limit = 1024; } else { cache->dir_limit = capacity - 1; }
ARENA_INIT(&cache->stat_bufs, struct bfs_stat);}
/** Allocate a directory. */static struct bfs_dir *bftw_allocdir(struct bftw_cache *cache, bool force) { if (!force && cache->dir_limit <= 0) { errno = ENOMEM; return NULL; }
struct bfs_dir *dir = arena_alloc(&cache->dirs); if (dir) { --cache->dir_limit; } return dir;}
/** Free a directory. */static void bftw_freedir(struct bftw_cache *cache, struct bfs_dir *dir) { ++cache->dir_limit; arena_free(&cache->dirs, dir);}
/** Remove a bftw_file from the LRU list. */static void bftw_lru_remove(struct bftw_cache *cache, struct bftw_file *file) { if (cache->target == file) { cache->target = file->lru.prev; }
LIST_REMOVE(cache, file, lru);}
/** Remove a bftw_file from the cache. */static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) { bftw_lru_remove(cache, file); ++cache->capacity;}
/** Close a bftw_file. */static void bftw_file_close(struct bftw_cache *cache, struct bftw_file *file) { bfs_assert(file->fd >= 0); bfs_assert(file->pincount == 0);
if (file->dir) { bfs_closedir(file->dir); bftw_freedir(cache, file->dir); file->dir = NULL; } else { xclose(file->fd); }
file->fd = -1; bftw_cache_remove(cache, file);}
/** Pop the least recently used directory from the cache. */static int bftw_cache_pop(struct bftw_cache *cache) { struct bftw_file *file = cache->tail; if (!file) { return -1; }
bftw_file_close(cache, file); return 0;}
/** Add a bftw_file to the LRU list. */static void bftw_lru_add(struct bftw_cache *cache, struct bftw_file *file) { bfs_assert(file->fd >= 0);
LIST_INSERT(cache, cache->target, file, lru);
// Prefer to keep the root paths open by keeping them at the head of the list if (file->depth == 0) { cache->target = file; }}
/** Add a bftw_file to the cache. */static int bftw_cache_add(struct bftw_cache *cache, struct bftw_file *file) { bfs_assert(file->fd >= 0);
if (cache->capacity == 0 && bftw_cache_pop(cache) != 0) { bftw_file_close(cache, file); errno = EMFILE; return -1; }
bfs_assert(cache->capacity > 0); --cache->capacity;
bftw_lru_add(cache, file); return 0;}
/** Pin a cache entry so it won't be closed. */static void bftw_cache_pin(struct bftw_cache *cache, struct bftw_file *file) { bfs_assert(file->fd >= 0);
if (file->pincount++ == 0) { bftw_lru_remove(cache, file); }}
/** Unpin a cache entry. */static void bftw_cache_unpin(struct bftw_cache *cache, struct bftw_file *file) { bfs_assert(file->fd >= 0); bfs_assert(file->pincount > 0);
if (--file->pincount == 0) { bftw_lru_add(cache, file); }}
/** Compute the name offset of a child path. */static size_t bftw_child_nameoff(const struct bftw_file *parent) { size_t ret = parent->nameoff + parent->namelen; if (parent->name[parent->namelen - 1] != '/') { ++ret; } return ret;}
/** Destroy a cache. */static void bftw_cache_destroy(struct bftw_cache *cache) { bfs_assert(LIST_EMPTY(cache)); bfs_assert(!cache->target);
arena_destroy(&cache->stat_bufs); arena_destroy(&cache->dirs); varena_destroy(&cache->files);}
/** Create a new bftw_file. */static struct bftw_file *bftw_file_new(struct bftw_cache *cache, struct bftw_file *parent, const char *name) { size_t namelen = strlen(name); struct bftw_file *file = varena_alloc(&cache->files, namelen + 1); if (!file) { return NULL; }
file->parent = parent;
if (parent) { file->root = parent->root; file->depth = parent->depth + 1; file->nameoff = bftw_child_nameoff(parent); ++parent->refcount; } else { file->root = file; file->depth = 0; file->nameoff = 0; }
SLIST_ITEM_INIT(file); SLIST_ITEM_INIT(file, ready); LIST_ITEM_INIT(file, lru);
file->refcount = 1; file->pincount = 0; file->fd = -1; file->ioqueued = false; file->dir = NULL;
file->type = BFS_UNKNOWN; file->dev = -1; file->ino = -1;
bftw_stat_init(&file->stat_bufs, NULL, NULL);
file->namelen = namelen; memcpy(file->name, name, namelen + 1);
return file;}
/** Associate an open directory with a bftw_file. */static void bftw_file_set_dir(struct bftw_cache *cache, struct bftw_file *file, struct bfs_dir *dir) { bfs_assert(!file->dir); file->dir = dir;
if (file->fd >= 0) { bfs_assert(file->fd == bfs_dirfd(dir)); } else { file->fd = bfs_dirfd(dir); bftw_cache_add(cache, file); }}
/** Free a file's cached stat() buffers. */static void bftw_stat_recycle(struct bftw_cache *cache, struct bftw_file *file) { struct bftw_stat *bufs = &file->stat_bufs;
struct bfs_stat *stat_buf = (struct bfs_stat *)bufs->stat_buf; struct bfs_stat *lstat_buf = (struct bfs_stat *)bufs->lstat_buf; if (stat_buf) { arena_free(&cache->stat_bufs, stat_buf); } else if (lstat_buf) { arena_free(&cache->stat_bufs, lstat_buf); }
bftw_stat_init(bufs, NULL, NULL);}
/** Free a bftw_file. */static void bftw_file_free(struct bftw_cache *cache, struct bftw_file *file) { bfs_assert(file->refcount == 0);
if (file->fd >= 0) { bftw_file_close(cache, file); }
bftw_stat_recycle(cache, file);
varena_free(&cache->files, file, file->namelen + 1);}
/** * Holds the current state of the bftw() traversal. */struct bftw_state { /** The path(s) to start from. */ const char **paths; /** The number of starting paths. */ size_t npaths; /** bftw() callback. */ bftw_callback *callback; /** bftw() callback data. */ void *ptr; /** bftw() flags. */ enum bftw_flags flags; /** Search strategy. */ enum bftw_strategy strategy; /** The mount table. */ const struct bfs_mtab *mtab; /** bfs_opendir() flags. */ enum bfs_dir_flags dir_flags;
/** The appropriate errno value, if any. */ int error;
/** The cache of open directories. */ struct bftw_cache cache;
/** The async I/O queue. */ struct ioq *ioq; /** The number of I/O threads. */ size_t nthreads;
/** The queue of unpinned directories to unwrap. */ struct bftw_list to_close; /** The queue of files to visit. */ struct bftw_queue fileq; /** The queue of directories to open/read. */ struct bftw_queue dirq;
/** The current path. */ dchar *path; /** The current file. */ struct bftw_file *file; /** The previous file. */ struct bftw_file *previous;
/** The currently open directory. */ struct bfs_dir *dir; /** The current directory entry. */ struct bfs_dirent *de; /** Storage for the directory entry. */ struct bfs_dirent de_storage; /** Any error encountered while reading the directory. */ int direrror;
/** Extra data about the current file. */ struct BFTW ftwbuf; /** stat() buffer storage. */ struct bfs_stat stat_buf; /** lstat() buffer storage. */ struct bfs_stat lstat_buf;};
/** Check if we have to buffer files before visiting them. */static bool bftw_must_buffer(const struct bftw_state *state) { if (state->flags & BFTW_SORT) { // Have to buffer the files to sort them return true; }
if (state->strategy == BFTW_DFS && state->nthreads == 0) { // Without buffering, we would get a not-quite-depth-first // ordering: // // a // b // a/c // a/c/d // b/e // b/e/f // // This is okay for iterative deepening, since the caller only // sees files at the target depth. We also deem it okay for // parallel searches, since the order is unpredictable anyway. return true; }
if ((state->flags & BFTW_STAT) && state->nthreads > 1) { // We will be buffering every file anyway for ioq_stat() return true; }
return false;}
/** Initialize the bftw() state. */static int bftw_state_init(struct bftw_state *state, const struct bftw_args *args) { state->paths = args->paths; state->npaths = args->npaths; state->callback = args->callback; state->ptr = args->ptr; state->flags = args->flags; state->strategy = args->strategy; state->mtab = args->mtab; state->dir_flags = 0; state->error = 0;
if (args->nopenfd < 2) { errno = EMFILE; return -1; }
size_t nopenfd = args->nopenfd; size_t qdepth = 4096; size_t nthreads = args->nthreads;
#if BFS_WITH_LIBURING // io_uring uses one fd per ring, ioq uses one ring per thread if (nthreads >= nopenfd - 1) { nthreads = nopenfd - 2; } nopenfd -= nthreads;#endif
bftw_cache_init(&state->cache, nopenfd);
if (nthreads > 0) { state->ioq = ioq_create(qdepth, nthreads); if (!state->ioq) { return -1; } } else { state->ioq = NULL; } state->nthreads = nthreads;
if (bftw_must_buffer(state)) { state->flags |= BFTW_BUFFER; }
if (state->flags & BFTW_WHITEOUTS) { state->dir_flags |= BFS_DIR_WHITEOUTS; }
SLIST_INIT(&state->to_close);
enum bftw_qflags qflags = 0; if (state->strategy != BFTW_BFS) { qflags |= BFTW_QBUFFER | BFTW_QLIFO; } if (state->flags & BFTW_BUFFER) { qflags |= BFTW_QBUFFER; } if (state->flags & BFTW_SORT) { qflags |= BFTW_QORDER; } else if (nthreads == 1) { qflags |= BFTW_QBALANCE; } bftw_queue_init(&state->fileq, qflags);
if (state->strategy == BFTW_BFS || (state->flags & BFTW_BUFFER)) { // In breadth-first mode, or if we're already buffering files, // directories can be queued in FIFO order qflags &= ~(BFTW_QBUFFER | BFTW_QLIFO); } bftw_queue_init(&state->dirq, qflags);
state->path = NULL; state->file = NULL; state->previous = NULL;
state->dir = NULL; state->de = NULL; state->direrror = 0;
return 0;}
/** Queue a directory for unwrapping. */static void bftw_delayed_unwrap(struct bftw_state *state, struct bftw_file *file) { bfs_assert(file->dir);
if (!SLIST_ATTACHED(&state->to_close, file, ready)) { SLIST_APPEND(&state->to_close, file, ready); }}
/** Unpin a file's parent. */static void bftw_unpin_parent(struct bftw_state *state, struct bftw_file *file, bool unwrap) { struct bftw_file *parent = file->parent; if (!parent) { return; }
bftw_cache_unpin(&state->cache, parent);
if (unwrap && parent->dir && parent->pincount == 0) { bftw_delayed_unwrap(state, parent); }}
/** Pop a response from the I/O queue. */static int bftw_ioq_pop(struct bftw_state *state, bool block) { struct bftw_cache *cache = &state->cache; struct ioq *ioq = state->ioq; if (!ioq) { return -1; }
ioq_submit(ioq); struct ioq_ent *ent = ioq_pop(ioq, block); if (!ent) { return -1; }
struct bftw_file *file = ent->ptr; if (file) { bftw_unpin_parent(state, file, true); }
enum ioq_op op = ent->op; switch (op) { case IOQ_CLOSE: ++cache->capacity; break;
case IOQ_CLOSEDIR: ++cache->capacity; bftw_freedir(cache, ent->closedir.dir); break;
case IOQ_OPENDIR: ++cache->capacity;
if (ent->result >= 0) { bftw_file_set_dir(cache, file, ent->opendir.dir); } else { bftw_freedir(cache, ent->opendir.dir); }
bftw_queue_attach(&state->dirq, file, true); break;
case IOQ_STAT: if (ent->result >= 0) { bftw_stat_cache(&file->stat_bufs, ent->stat.flags, ent->stat.buf, 0); } else { arena_free(&cache->stat_bufs, ent->stat.buf); bftw_stat_cache(&file->stat_bufs, ent->stat.flags, NULL, -ent->result); }
bftw_queue_attach(&state->fileq, file, true); break;
default: bfs_bug("Unexpected ioq op %d", (int)op); break; }
ioq_free(ioq, ent); return op;}
/** Try to reserve space in the I/O queue. */static int bftw_ioq_reserve(struct bftw_state *state) { struct ioq *ioq = state->ioq; if (!ioq) { return -1; }
if (ioq_capacity(ioq) > 0) { return 0; }
// With more than one background thread, it's faster to wait on // background I/O than it is to do it on the main thread bool block = state->nthreads > 1; if (bftw_ioq_pop(state, block) < 0) { return -1; }
return 0;}
/** Try to reserve space in the cache. */static int bftw_cache_reserve(struct bftw_state *state) { struct bftw_cache *cache = &state->cache; if (cache->capacity > 0) { return 0; }
while (bftw_ioq_pop(state, true) >= 0) { if (cache->capacity > 0) { return 0; } }
if (bftw_cache_pop(cache) != 0) { errno = EMFILE; return -1; }
bfs_assert(cache->capacity > 0); return 0;}
/** Open a bftw_file relative to another one. */static int bftw_file_openat(struct bftw_state *state, struct bftw_file *file, struct bftw_file *base, const char *at_path) { bfs_assert(file->fd < 0);
struct bftw_cache *cache = &state->cache;
int at_fd = AT_FDCWD; if (base) { bftw_cache_pin(cache, base); at_fd = base->fd; }
int fd = -1; if (bftw_cache_reserve(state) != 0) { goto unpin; }
int flags = O_RDONLY | O_CLOEXEC | O_DIRECTORY; fd = openat(at_fd, at_path, flags);
if (fd < 0 && errno == EMFILE) { if (bftw_cache_pop(cache) == 0) { fd = openat(at_fd, at_path, flags); } cache->capacity = 1; }
unpin: if (base) { bftw_cache_unpin(cache, base); }
if (fd >= 0) { file->fd = fd; bftw_cache_add(cache, file); }
return fd;}
/** Open a bftw_file. */static int bftw_file_open(struct bftw_state *state, struct bftw_file *file, const char *path) { // Find the nearest open ancestor struct bftw_file *base = file; do { base = base->parent; } while (base && base->fd < 0);
const char *at_path = path; if (base) { at_path += bftw_child_nameoff(base); }
int fd = bftw_file_openat(state, file, base, at_path); if (fd >= 0 || !errno_is_like(ENAMETOOLONG)) { return fd; }
// Handle ENAMETOOLONG by manually traversing the path component-by-component struct bftw_list parents; SLIST_INIT(&parents);
// Reverse the chain of parents for (struct bftw_file *cur = file; cur != base; cur = cur->parent) { SLIST_PREPEND(&parents, cur); }
// Open each component relative to its parent drain_slist (struct bftw_file, cur, &parents) { if (!cur->parent || cur->parent->fd >= 0) { bftw_file_openat(state, cur, cur->parent, cur->name); } }
return file->fd;}
/** Close a directory, asynchronously if possible. */static int bftw_ioq_closedir(struct bftw_state *state, struct bfs_dir *dir) { if (bftw_ioq_reserve(state) == 0) { if (ioq_closedir(state->ioq, dir, NULL) == 0) { return 0; } }
struct bftw_cache *cache = &state->cache; int ret = bfs_closedir(dir); bftw_freedir(cache, dir); ++cache->capacity; return ret;}
/** Close a file descriptor, asynchronously if possible. */static int bftw_ioq_close(struct bftw_state *state, int fd) { if (bftw_ioq_reserve(state) == 0) { if (ioq_close(state->ioq, fd, NULL) == 0) { return 0; } }
struct bftw_cache *cache = &state->cache; int ret = xclose(fd); ++cache->capacity; return ret;}
/** Close a file, asynchronously if possible. */static int bftw_close(struct bftw_state *state, struct bftw_file *file) { bfs_assert(file->fd >= 0); bfs_assert(file->pincount == 0);
struct bfs_dir *dir = file->dir; int fd = file->fd;
bftw_lru_remove(&state->cache, file); file->dir = NULL; file->fd = -1;
if (dir) { return bftw_ioq_closedir(state, dir); } else { return bftw_ioq_close(state, fd); }}
/** Free an open directory. */static int bftw_unwrapdir(struct bftw_state *state, struct bftw_file *file) { struct bfs_dir *dir = file->dir; if (!dir) { return 0; }
struct bftw_cache *cache = &state->cache;
// Try to keep an open fd if any children exist bool reffed = file->refcount > 1; // Keep the fd the same if it's pinned bool pinned = file->pincount > 0;
#if BFS_USE_UNWRAPDIR if (reffed || pinned) { if (bfs_unwrapdir(dir) >= 0) { bftw_freedir(cache, dir); file->dir = NULL; return 0; } }#endif
if (pinned) { return -1; }
if (!reffed) { return bftw_close(state, file); }
// Make room for dup() bftw_cache_pin(cache, file); int ret = bftw_cache_reserve(state); bftw_cache_unpin(cache, file); if (ret != 0) { return ret; }
int fd = dup_cloexec(file->fd); if (fd < 0) { return -1; } --cache->capacity;
file->dir = NULL; file->fd = fd; return bftw_ioq_closedir(state, dir);}
/** Try to pin a file's parent. */static int bftw_pin_parent(struct bftw_state *state, struct bftw_file *file) { struct bftw_file *parent = file->parent; if (!parent) { return AT_FDCWD; }
int fd = parent->fd; if (fd < 0) { // Don't confuse failures with AT_FDCWD return (int)AT_FDCWD == -1 ? -2 : -1; }
bftw_cache_pin(&state->cache, parent); return fd;}
/** Open a directory asynchronously. */static int bftw_ioq_opendir(struct bftw_state *state, struct bftw_file *file) { struct bftw_cache *cache = &state->cache;
if (bftw_ioq_reserve(state) != 0) { goto fail; }
int dfd = bftw_pin_parent(state, file); if (dfd < 0 && dfd != (int)AT_FDCWD) { goto fail; }
if (bftw_cache_reserve(state) != 0) { goto unpin; }
struct bfs_dir *dir = bftw_allocdir(cache, false); if (!dir) { goto unpin; }
if (ioq_opendir(state->ioq, dir, dfd, file->name, state->dir_flags, file) != 0) { goto free; }
--cache->capacity; return 0;
free: bftw_freedir(cache, dir);unpin: bftw_unpin_parent(state, file, false);fail: return -1;}
/** Open a batch of directories asynchronously. */static void bftw_ioq_opendirs(struct bftw_state *state) { while (bftw_queue_balanced(&state->dirq)) { struct bftw_file *dir = bftw_queue_waiting(&state->dirq); if (!dir) { break; }
if (bftw_ioq_opendir(state, dir) == 0) { bftw_queue_detach(&state->dirq, dir, true); } else { break; } }}
/** Push a directory onto the queue. */static void bftw_push_dir(struct bftw_state *state, struct bftw_file *file) { bfs_assert(file->type == BFS_DIR); bftw_queue_push(&state->dirq, file); bftw_ioq_opendirs(state);}
/** Pop a file from a queue, then activate it. */static bool bftw_pop(struct bftw_state *state, struct bftw_queue *queue) { if (queue->size == 0) { return false; }
while (!bftw_queue_ready(queue) && queue->ioqueued > 0) { bool block = true; if (bftw_queue_waiting(queue) && state->nthreads == 1) { // With only one background thread, balance the work // between it and the main thread block = false; }
if (bftw_ioq_pop(state, block) < 0) { break; } }
struct bftw_file *file = bftw_queue_pop(queue); if (!file) { return false; }
while (file->ioqueued) { bftw_ioq_pop(state, true); }
state->file = file; return true;}
/** Pop a directory to read from the queue. */static bool bftw_pop_dir(struct bftw_state *state) { bfs_assert(!state->file);
if (state->flags & BFTW_SORT) { // Keep strict breadth-first order when sorting if (state->strategy == BFTW_BFS && bftw_queue_ready(&state->fileq)) { return false; } } else if (!bftw_queue_ready(&state->dirq)) { // Don't block if we have files ready to visit if (bftw_queue_ready(&state->fileq)) { return false; } }
return bftw_pop(state, &state->dirq);}
/** Figure out bfs_stat() flags. */static enum bfs_stat_flags bftw_stat_flags(const struct bftw_state *state, size_t depth) { enum bftw_flags mask = BFTW_FOLLOW_ALL; if (depth == 0) { mask |= BFTW_FOLLOW_ROOTS; }
if (state->flags & mask) { return BFS_STAT_TRYFOLLOW; } else { return BFS_STAT_NOFOLLOW; }}
/** Check if a stat() call is necessary. */static bool bftw_must_stat(const struct bftw_state *state, size_t depth, enum bfs_type type, const char *name) { if (state->flags & BFTW_STAT) { return true; }
switch (type) { case BFS_UNKNOWN: return true;
case BFS_DIR: return state->flags & (BFTW_DETECT_CYCLES | BFTW_SKIP_MOUNTS | BFTW_PRUNE_MOUNTS);
case BFS_LNK: if (!(bftw_stat_flags(state, depth) & BFS_STAT_NOFOLLOW)) { return true; } [[fallthrough]];
default:#if __linux__ if (state->mtab && bfs_might_be_mount(state->mtab, name)) { return true; }#endif return false; }}
/** stat() a file asynchronously. */static int bftw_ioq_stat(struct bftw_state *state, struct bftw_file *file) { if (bftw_ioq_reserve(state) != 0) { goto fail; }
int dfd = bftw_pin_parent(state, file); if (dfd < 0 && dfd != (int)AT_FDCWD) { goto fail; }
struct bftw_cache *cache = &state->cache; struct bfs_stat *buf = arena_alloc(&cache->stat_bufs); if (!buf) { goto unpin; }
enum bfs_stat_flags flags = bftw_stat_flags(state, file->depth); if (ioq_stat(state->ioq, dfd, file->name, flags, buf, file) != 0) { goto free; }
return 0;
free: arena_free(&cache->stat_bufs, buf);unpin: bftw_unpin_parent(state, file, false);fail: return -1;}
/** Check if we should stat() a file asynchronously. */static bool bftw_should_ioq_stat(struct bftw_state *state, struct bftw_file *file) { // POSIX wants the root paths to be processed in order // See https://www.austingroupbugs.net/view.php?id=1859 if (file->depth == 0) { return false; }
#ifdef S_IFWHT // ioq_stat() does not do whiteout emulation like bftw_stat_impl() if (file->type == BFS_WHT) { return false; }#endif
return bftw_must_stat(state, file->depth, file->type, file->name);}
/** Call stat() on files that need it. */static void bftw_stat_files(struct bftw_state *state) { while (true) { struct bftw_file *file = bftw_queue_waiting(&state->fileq); if (!file) { break; }
if (!bftw_should_ioq_stat(state, file)) { bftw_queue_skip(&state->fileq, file); continue; }
if (!bftw_queue_balanced(&state->fileq)) { break; }
if (bftw_ioq_stat(state, file) == 0) { bftw_queue_detach(&state->fileq, file, true); } else { break; } }}
/** Push a file onto the queue. */static void bftw_push_file(struct bftw_state *state, struct bftw_file *file) { bftw_queue_push(&state->fileq, file); bftw_stat_files(state);}
/** Pop a file to visit from the queue. */static bool bftw_pop_file(struct bftw_state *state) { bfs_assert(!state->file); return bftw_pop(state, &state->fileq);}
/** Add a path component to the path. */static void bftw_prepend_path(char *path, size_t nameoff, size_t namelen, const char *name) { if (nameoff > 0) { path[nameoff - 1] = '/'; } memcpy(path + nameoff, name, namelen);}
/** Build the path to the current file. */static int bftw_build_path(struct bftw_state *state, const char *name) { const struct bftw_file *file = state->file;
size_t nameoff, namelen; if (name) { nameoff = file ? bftw_child_nameoff(file) : 0; namelen = strlen(name); } else { nameoff = file->nameoff; namelen = file->namelen; }
size_t pathlen = nameoff + namelen; if (dstresize(&state->path, pathlen) != 0) { state->error = errno; return -1; }
// Try to find a common ancestor with the existing path const struct bftw_file *ancestor = state->previous; while (ancestor && ancestor->depth > file->depth) { ancestor = ancestor->parent; }
// Build the path backwards if (name) { bftw_prepend_path(state->path, nameoff, namelen, name); } while (file && file != ancestor) { bftw_prepend_path(state->path, file->nameoff, file->namelen, file->name);
if (ancestor && ancestor->depth == file->depth) { ancestor = ancestor->parent; } file = file->parent; }
state->previous = state->file; return 0;}
/** Open a bftw_file as a directory. */static struct bfs_dir *bftw_file_opendir(struct bftw_state *state, struct bftw_file *file, const char *path) { int fd = bftw_file_open(state, file, path); if (fd < 0) { return NULL; }
struct bftw_cache *cache = &state->cache; struct bfs_dir *dir = bftw_allocdir(cache, true); if (!dir) { return NULL; }
if (bfs_opendir(dir, fd, NULL, state->dir_flags) != 0) { bftw_freedir(cache, dir); return NULL; }
bftw_file_set_dir(cache, file, dir); return dir;}
/** Open the current directory. */static int bftw_opendir(struct bftw_state *state) { bfs_assert(!state->dir); bfs_assert(!state->de);
state->direrror = 0;
struct bftw_file *file = state->file; state->dir = file->dir; if (state->dir) { goto pin; }
if (bftw_build_path(state, NULL) != 0) { return -1; }
bftw_queue_rebalance(&state->dirq, false);
state->dir = bftw_file_opendir(state, file, state->path); if (!state->dir) { state->direrror = errno; return 0; }
pin: bftw_cache_pin(&state->cache, file); return 0;}
/** Read an entry from the current directory. */static int bftw_readdir(struct bftw_state *state) { if (!state->dir) { return -1; }
int ret = bfs_readdir(state->dir, &state->de_storage); if (ret > 0) { state->de = &state->de_storage; } else if (ret == 0) { state->de = NULL; } else { state->de = NULL; state->direrror = errno; }
return ret;}
/** Open a file if necessary. */static int bftw_ensure_open(struct bftw_state *state, struct bftw_file *file, const char *path) { int ret = file->fd;
if (ret < 0) { char *copy = strndup(path, file->nameoff + file->namelen); if (!copy) { return -1; }
ret = bftw_file_open(state, file, copy); free(copy); }
return ret;}
/** Initialize the buffers with data about the current path. */static void bftw_init_ftwbuf(struct bftw_state *state, enum bftw_visit visit) { struct bftw_file *file = state->file; const struct bfs_dirent *de = state->de;
struct BFTW *ftwbuf = &state->ftwbuf; ftwbuf->path = state->path; ftwbuf->root = file ? file->root->name : ftwbuf->path; ftwbuf->depth = 0; ftwbuf->visit = visit; ftwbuf->type = BFS_UNKNOWN; ftwbuf->error = state->direrror; ftwbuf->loopoff = 0; ftwbuf->at_fd = AT_FDCWD; ftwbuf->at_path = ftwbuf->path; bftw_stat_init(&ftwbuf->stat_bufs, &state->stat_buf, &state->lstat_buf);
struct bftw_file *parent = NULL; if (de) { parent = file; ftwbuf->depth = file->depth + 1; ftwbuf->type = de->type; ftwbuf->nameoff = bftw_child_nameoff(file); } else if (file) { parent = file->parent; ftwbuf->depth = file->depth; ftwbuf->type = file->type; ftwbuf->nameoff = file->nameoff; bftw_stat_fill(&ftwbuf->stat_bufs, &file->stat_bufs); }
if (parent) { // Try to ensure the immediate parent is open, to avoid ENAMETOOLONG if (bftw_ensure_open(state, parent, state->path) >= 0) { ftwbuf->at_fd = parent->fd; ftwbuf->at_path += ftwbuf->nameoff; } else { ftwbuf->error = errno; } }
if (ftwbuf->depth == 0) { // Compute the name offset for root paths like "foo/bar" ftwbuf->nameoff = xbaseoff(ftwbuf->path); }
ftwbuf->stat_flags = bftw_stat_flags(state, ftwbuf->depth);
if (ftwbuf->error != 0) { ftwbuf->type = BFS_ERROR; return; }
const struct bfs_stat *statbuf = NULL; if (bftw_must_stat(state, ftwbuf->depth, ftwbuf->type, ftwbuf->path + ftwbuf->nameoff)) { statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags); if (statbuf) { ftwbuf->type = bfs_mode_to_type(statbuf->mode); } else { ftwbuf->type = BFS_ERROR; ftwbuf->error = errno; return; } }
if (ftwbuf->type == BFS_DIR && (state->flags & BFTW_DETECT_CYCLES)) { for (const struct bftw_file *ancestor = parent; ancestor; ancestor = ancestor->parent) { if (ancestor->dev == statbuf->dev && ancestor->ino == statbuf->ino) { ftwbuf->type = BFS_ERROR; ftwbuf->error = ELOOP; ftwbuf->loopoff = ancestor->nameoff + ancestor->namelen; return; } } }}
/** Check if the current file is a mount point. */static bool bftw_is_mount(struct bftw_state *state, const char *name) { const struct bftw_file *file = state->file; if (!file) { return false; }
const struct bftw_file *parent = name ? file : file->parent; if (!parent) { return false; }
const struct BFTW *ftwbuf = &state->ftwbuf; const struct bfs_stat *statbuf = bftw_stat(ftwbuf, ftwbuf->stat_flags); return statbuf && statbuf->dev != parent->dev;}
/** Check if bfs_stat() was called from the main thread. */static bool bftw_stat_was_sync(const struct bftw_state *state, const struct bfs_stat *buf) { return buf == &state->stat_buf || buf == &state->lstat_buf;}
/** Invoke the callback. */static enum bftw_action bftw_call_back(struct bftw_state *state, const char *name, enum bftw_visit visit) { if (visit == BFTW_POST && !(state->flags & BFTW_POST_ORDER)) { return BFTW_PRUNE; }
if (bftw_build_path(state, name) != 0) { return BFTW_STOP; }
const struct BFTW *ftwbuf = &state->ftwbuf; bftw_init_ftwbuf(state, visit);
// Never give the callback BFS_ERROR unless BFTW_RECOVER is specified if (ftwbuf->type == BFS_ERROR && !(state->flags & BFTW_RECOVER)) { state->error = ftwbuf->error; return BFTW_STOP; }
enum bftw_action ret = BFTW_PRUNE; if ((state->flags & BFTW_SKIP_MOUNTS) && bftw_is_mount(state, name)) { goto done; }
ret = state->callback(ftwbuf, state->ptr); switch (ret) { case BFTW_CONTINUE: if (visit != BFTW_PRE || ftwbuf->type != BFS_DIR) { ret = BFTW_PRUNE; } else if (state->flags & BFTW_PRUNE_MOUNTS) { if (bftw_is_mount(state, name)) { ret = BFTW_PRUNE; } } break;
case BFTW_PRUNE: case BFTW_STOP: break;
default: state->error = EINVAL; return BFTW_STOP; }
done: if (state->fileq.flags & BFTW_QBALANCE) { // Detect any main-thread stat() calls to rebalance the queue const struct bfs_stat *buf = bftw_cached_stat(ftwbuf, BFS_STAT_FOLLOW); const struct bfs_stat *lbuf = bftw_cached_stat(ftwbuf, BFS_STAT_NOFOLLOW); if (bftw_stat_was_sync(state, buf) || bftw_stat_was_sync(state, lbuf)) { bftw_queue_rebalance(&state->fileq, false); } }
return ret;}
/** * Flags controlling which files get visited when done with a directory. */enum bftw_gc_flags { /** Don't visit anything. */ BFTW_VISIT_NONE = 0, /** Report directory errors. */ BFTW_VISIT_ERROR = 1 << 0, /** Visit the file itself. */ BFTW_VISIT_FILE = 1 << 1, /** Visit the file's ancestors. */ BFTW_VISIT_PARENTS = 1 << 2, /** Visit both the file and its ancestors. */ BFTW_VISIT_ALL = BFTW_VISIT_ERROR | BFTW_VISIT_FILE | BFTW_VISIT_PARENTS,};
/** Garbage collect the current file and its parents. */static int bftw_gc(struct bftw_state *state, enum bftw_gc_flags flags) { int ret = 0;
struct bftw_file *file = state->file; if (file) { if (state->dir) { bftw_cache_unpin(&state->cache, file); } if (file->dir) { bftw_delayed_unwrap(state, file); } } state->dir = NULL; state->de = NULL;
if (state->direrror != 0) { if (flags & BFTW_VISIT_ERROR) { if (bftw_call_back(state, NULL, BFTW_PRE) == BFTW_STOP) { ret = -1; flags = 0; } } else { state->error = state->direrror; } } state->direrror = 0;
drain_slist (struct bftw_file, dead, &state->to_close, ready) { bftw_unwrapdir(state, dead); }
enum bftw_gc_flags visit = BFTW_VISIT_FILE; while ((file = state->file)) { if (--file->refcount > 0) { state->file = NULL; break; }
if (flags & visit) { if (bftw_call_back(state, NULL, BFTW_POST) == BFTW_STOP) { ret = -1; flags = 0; } } visit = BFTW_VISIT_PARENTS;
struct bftw_file *parent = file->parent; if (state->previous == file) { state->previous = parent; } state->file = parent;
if (file->fd >= 0) { bftw_close(state, file); } bftw_file_free(&state->cache, file); }
return ret;}
/** Sort a bftw_list by filename. */static void bftw_list_sort(struct bftw_list *list) { if (!list->head || !list->head->next) { return; }
struct bftw_list left, right; SLIST_INIT(&left); SLIST_INIT(&right);
// Split for (struct bftw_file *hare = list->head; hare && (hare = hare->next); hare = hare->next) { struct bftw_file *tortoise = SLIST_POP(list); SLIST_APPEND(&left, tortoise); } SLIST_EXTEND(&right, list);
// Recurse bftw_list_sort(&left); bftw_list_sort(&right);
// Merge while (!SLIST_EMPTY(&left) && !SLIST_EMPTY(&right)) { struct bftw_file *lf = left.head; struct bftw_file *rf = right.head;
if (strcoll(lf->name, rf->name) <= 0) { SLIST_POP(&left); SLIST_APPEND(list, lf); } else { SLIST_POP(&right); SLIST_APPEND(list, rf); } } SLIST_EXTEND(list, &left); SLIST_EXTEND(list, &right);}
/** Flush all the queue buffers. */static void bftw_flush(struct bftw_state *state) { if (state->flags & BFTW_SORT) { bftw_list_sort(&state->fileq.buffer); } bftw_queue_flush(&state->fileq); bftw_stat_files(state);
bftw_queue_flush(&state->dirq); bftw_ioq_opendirs(state);
if (state->ioq) { ioq_submit(state->ioq); }}
/** Close the current directory. */static int bftw_closedir(struct bftw_state *state) { if (bftw_gc(state, BFTW_VISIT_ALL) != 0) { return -1; }
bftw_flush(state); return 0;}
/** Fill file identity information from an ftwbuf. */static void bftw_save_ftwbuf(struct bftw_file *file, const struct BFTW *ftwbuf) { file->type = ftwbuf->type;
const struct bfs_stat *statbuf = bftw_cached_stat(ftwbuf, ftwbuf->stat_flags); if (statbuf) { file->dev = statbuf->dev; file->ino = statbuf->ino; }}
/** Check if we should buffer a file instead of visiting it. */static bool bftw_buffer_file(const struct bftw_state *state, const struct bftw_file *file, const char *name) { if (!name) { // Already buffered return false; }
if (state->flags & BFTW_BUFFER) { return true; }
// If we need to call stat(), and can do it async, buffer this file if (!state->ioq) { return false; }
if (!bftw_queue_balanced(&state->fileq)) { // stat() would run synchronously anyway return false; }
size_t depth = file ? file->depth + 1 : 1; enum bfs_type type = state->de ? state->de->type : BFS_UNKNOWN; return bftw_must_stat(state, depth, type, name);}
/** Visit and/or enqueue the current file. */static int bftw_visit(struct bftw_state *state, const char *name) { struct bftw_cache *cache = &state->cache; struct bftw_file *file = state->file;
if (bftw_buffer_file(state, file, name)) { file = bftw_file_new(cache, file, name); if (!file) { state->error = errno; return -1; }
if (state->de) { file->type = state->de->type; }
bftw_push_file(state, file); return 0; }
switch (bftw_call_back(state, name, BFTW_PRE)) { case BFTW_CONTINUE: if (name) { file = bftw_file_new(cache, state->file, name); } else { state->file = NULL; } if (!file) { state->error = errno; return -1; }
bftw_save_ftwbuf(file, &state->ftwbuf); bftw_stat_recycle(cache, file); bftw_push_dir(state, file); return 0;
case BFTW_PRUNE: if (file && !name) { return bftw_gc(state, BFTW_VISIT_PARENTS); } else { return 0; }
default: if (file && !name) { bftw_gc(state, BFTW_VISIT_NONE); } return -1; }}
/** Drain a bftw_queue. */static void bftw_drain(struct bftw_state *state, struct bftw_queue *queue) { bftw_queue_flush(queue);
while (bftw_pop(state, queue)) { bftw_gc(state, BFTW_VISIT_NONE); }}
/** * Dispose of the bftw() state. * * @return * The bftw() return value. */static int bftw_state_destroy(struct bftw_state *state) { dstrfree(state->path);
struct ioq *ioq = state->ioq; if (ioq) { ioq_cancel(ioq); while (bftw_ioq_pop(state, true) >= 0); state->ioq = NULL; }
bftw_gc(state, BFTW_VISIT_NONE); bftw_drain(state, &state->dirq); bftw_drain(state, &state->fileq);
ioq_destroy(ioq);
bftw_cache_destroy(&state->cache);
errno = state->error; return state->error ? -1 : 0;}
/** * Shared implementation for all search strategies. */static int bftw_impl(struct bftw_state *state) { for (size_t i = 0; i < state->npaths; ++i) { if (bftw_visit(state, state->paths[i]) != 0) { return -1; } } bftw_flush(state);
while (true) { while (bftw_pop_dir(state)) { if (bftw_opendir(state) != 0) { return -1; } while (bftw_readdir(state) > 0) { if (bftw_visit(state, state->de->name) != 0) { return -1; } } if (bftw_closedir(state) != 0) { return -1; } }
if (!bftw_pop_file(state)) { break; } if (bftw_visit(state, NULL) != 0) { return -1; } bftw_flush(state); }
return 0;}
/** * bftw() implementation for simple breadth-/depth-first search. */static int bftw_walk(const struct bftw_args *args) { struct bftw_state state; if (bftw_state_init(&state, args) != 0) { return -1; }
bftw_impl(&state); return bftw_state_destroy(&state);}
/** * Iterative deepening search state. */struct bftw_ids_state { /** Nested walk state. */ struct bftw_state nested; /** The wrapped callback. */ bftw_callback *delegate; /** The wrapped callback arguments. */ void *ptr; /** Which visit this search corresponds to. */ enum bftw_visit visit; /** Whether to override the bftw_visit. */ bool force_visit; /** The current minimum depth (inclusive). */ size_t min_depth; /** The current maximum depth (exclusive). */ size_t max_depth; /** The set of pruned paths. */ struct trie pruned; /** Whether the bottom has been found. */ bool bottom;};
/** Iterative deepening callback function. */static enum bftw_action bftw_ids_callback(const struct BFTW *ftwbuf, void *ptr) { struct bftw_ids_state *state = ptr;
if (state->force_visit) { struct BFTW *mutbuf = (struct BFTW *)ftwbuf; mutbuf->visit = state->visit; }
if (ftwbuf->type == BFS_ERROR) { if (ftwbuf->depth + 1 >= state->min_depth) { return state->delegate(ftwbuf, state->ptr); } else { return BFTW_PRUNE; } }
if (ftwbuf->depth < state->min_depth) { if (trie_find_str(&state->pruned, ftwbuf->path)) { return BFTW_PRUNE; } else { return BFTW_CONTINUE; } } else if (state->visit == BFTW_POST) { if (trie_find_str(&state->pruned, ftwbuf->path)) { return BFTW_PRUNE; } }
enum bftw_action ret = BFTW_CONTINUE; if (ftwbuf->visit == state->visit) { ret = state->delegate(ftwbuf, state->ptr); }
switch (ret) { case BFTW_CONTINUE: if (ftwbuf->type == BFS_DIR && ftwbuf->depth + 1 >= state->max_depth) { state->bottom = false; ret = BFTW_PRUNE; } break;
case BFTW_PRUNE: if (ftwbuf->type == BFS_DIR) { if (!trie_insert_str(&state->pruned, ftwbuf->path)) { state->nested.error = errno; ret = BFTW_STOP; } } break;
case BFTW_STOP: break; }
return ret;}
/** Initialize iterative deepening state. */static int bftw_ids_init(struct bftw_ids_state *state, const struct bftw_args *args) { state->delegate = args->callback; state->ptr = args->ptr; state->visit = BFTW_PRE; state->force_visit = false; state->min_depth = 0; state->max_depth = 1; trie_init(&state->pruned); state->bottom = false;
struct bftw_args ids_args = *args; ids_args.callback = bftw_ids_callback; ids_args.ptr = state; ids_args.flags &= ~BFTW_POST_ORDER; return bftw_state_init(&state->nested, &ids_args);}
/** Finish an iterative deepening search. */static int bftw_ids_destroy(struct bftw_ids_state *state) { trie_destroy(&state->pruned); return bftw_state_destroy(&state->nested);}
/** * Iterative deepening bftw() wrapper. */static int bftw_ids(const struct bftw_args *args) { struct bftw_ids_state state; if (bftw_ids_init(&state, args) != 0) { return -1; }
while (!state.bottom) { state.bottom = true;
if (bftw_impl(&state.nested) != 0) { goto done; }
++state.min_depth; ++state.max_depth; }
if (args->flags & BFTW_POST_ORDER) { state.visit = BFTW_POST; state.force_visit = true;
while (state.min_depth > 0) { --state.max_depth; --state.min_depth;
if (bftw_impl(&state.nested) != 0) { goto done; } } }
done: return bftw_ids_destroy(&state);}
/** * Exponential deepening bftw() wrapper. */static int bftw_eds(const struct bftw_args *args) { struct bftw_ids_state state; if (bftw_ids_init(&state, args) != 0) { return -1; }
while (!state.bottom) { state.bottom = true;
if (bftw_impl(&state.nested) != 0) { goto done; }
state.min_depth = state.max_depth; state.max_depth *= 2; }
if (args->flags & BFTW_POST_ORDER) { state.visit = BFTW_POST; state.min_depth = 0; state.nested.flags |= BFTW_POST_ORDER;
bftw_impl(&state.nested); }
done: return bftw_ids_destroy(&state);}
int bftw(const struct bftw_args *args) { switch (args->strategy) { case BFTW_BFS: case BFTW_DFS: return bftw_walk(args); case BFTW_IDS: return bftw_ids(args); case BFTW_EDS: return bftw_eds(args); }
errno = EINVAL; return -1;}