// 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_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 "bfstd.h"
#include "config.h"
#include "dir.h"
#include "dstring.h"
#include "list.h"
#include "mtab.h"
#include "stat.h"
#include "trie.h"
#include <assert.h>
#include <errno.h>
#include <fcntl.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
/**
* 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;
/** The next file in the queue, if any. */
struct bftw_file *next;
/** LRU list links. */
struct {
struct bftw_file *prev;
struct bftw_file *next;
} lru;
/** This file's depth in the walk. */
size_t depth;
/** Reference count. */
size_t refcount;
/** An open descriptor to this file, or -1. */
int fd;
/** 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;
/** 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. */
char name[];
};
/**
* A linked list of bftw_file's.
*/
struct bftw_list {
struct bftw_file *head;
struct bftw_file **tail;
};
/**
* 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;
};
/** Initialize a cache. */
static void bftw_cache_init(struct bftw_cache *cache, size_t capacity) {
LIST_INIT(cache);
cache->target = NULL;
cache->capacity = capacity;
}
/** Remove a bftw_file from the cache. */
static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_file *file) {
if (cache->target == file) {
cache->target = file->lru.prev;
}
LIST_REMOVE(cache, file,