/*********************************************************************
* bfs *
* Copyright (C) 2015 Tavian Barnes <tavianator@tavianator.com> *
* *
* This program is free software. It comes without any warranty, to *
* the extent permitted by applicable law. You can redistribute it *
* and/or modify it under the terms of the Do What The Fuck You Want *
* To Public License, Version 2, as published by Sam Hocevar. See *
* the COPYING file or http://www.wtfpl.net/ for more details. *
*********************************************************************/
/**
* bftw() implementation.
*
* The goal of this implementation is to avoid re-traversal by using openat() as
* much as possible. The 'dircache' attempts to accomplish this by storing a
* hierarchy of 'dircache_entry's, along with an LRU list of recently accessed
* entries. Every entry in the LRU list has an open DIR *; to open an entry, we
* traverse its chain of parents, hoping to find an open one. The size of the
* LRU list is limited, because so are the available file descriptors.
*
* The 'dirqueue' is a simple FIFO of 'dircache_entry's left to explore.
*/
#include "bftw.h"
#include <assert.h>
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
/**
* Simple dynamically-sized string type.
*/
struct dynstr {
char *str;
size_t length;
size_t capacity;
};
/** Initialize a dynstr. */
static void dynstr_init(struct dynstr *dstr) {
dstr->str = NULL;
dstr->length = 0;
dstr->capacity = 0;
}
/** Grow a dynstr to the given capacity if necessary. */
static int dynstr_grow(struct dynstr *dstr, size_t length) {
if (length >= dstr->capacity) {
size_t new_capacity = 3*(length + 1)/2;
char *new_str = realloc(dstr->str, new_capacity);
if (!new_str) {
return -1;
}
dstr->str = new_str;
dstr->capacity = new_capacity;
}
return 0;
}
/** Concatenate a string to a dynstr at the given position. */
static int dynstr_concat(struct dynstr *dstr, size_t pos, const char *more) {
size_t morelen = strlen(more);
size_t length = pos + morelen;
if (dynstr_grow(dstr, length) != 0) {
return -1;
}
memcpy(dstr->str + pos, more, morelen + 1);
dstr->length = length;
return 0;
}
/** Free a dynstr. */
static void dynstr_free(struct dynstr *dstr) {
free(dstr->str);
}
/**
* A single entry in the dircache.
*/
struct dircache_entry {
/** The parent entry, if any. */
struct dircache_entry *parent;
/** This directory's depth in the walk. */
size_t depth;
/** Previous node in the LRU list. */
struct dircache_entry *lru_prev;
/** Next node in the LRU list. */
struct dircache_entry *lru_next;
/** The DIR pointer, if open. */
DIR *dir;
/** Reference count. */
size_t refcount;
/** The device number, for cycle detection. */
dev_t dev;
/** The inode number, for cycle detection. */
ino_t ino;
/** The offset of this directory in the full path. */
size_t nameoff;
/** The length of the directory's name. */
size_t namelen;
/** The directory's name. */
char name[];
};
/**
* A directory cache.
*/
struct dircache {
/** Most recently used entry. */
struct dircache_entry *lru_head;
/** Least recently used entry. */
struct dircache_entry *lru_tail;
/** Remaining LRU list capacity. */
size_t lru_remaining;
};
/** Initialize a dircache. */
static void dircache_init(struct dircache *cache, size_t lru_size) {
assert(lru_size > 0);
cache->lru_head = cache->lru_tail = NULL;
cache->lru_remaining = lru_size;
}
/** Add an entry to the dircache. */
static struct dircache_entry *dircache_add(struct dircache *cache, struct dircache_entry *parent, const char *name) {
size_t namelen = strlen(name);
size_t size = sizeof(struct dircache_entry) + namelen + 1;
bool needs_slash = false;
if (namelen == 0 || name[namelen - 1] != '/') {
needs_slash = true;
++size;
}
struct dircache_entry *entry = malloc(size);
if (!entry) {
return NULL;
}
entry->parent = parent;
if (parent) {
entry->depth = parent->depth + 1;
entry->nameoff = parent->nameoff + parent->namelen;
} else {
entry->depth = 0;
entry->nameoff = 0;
}
entry->lru_prev = entry->lru_next = NULL;
entry->dir = NULL;
entry->refcount = 1;
memcpy(entry->name, name, namelen);
if (needs_slash) {
entry->name[namelen++] = '/';
}
entry->name[namelen]