/*********************************************************************
* 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. Since the number of open file descriptors is limited, the
* 'dircache' maintains a priority queue of open 'dircache_entry's, ordered by
* their reference counts to keep the most-referenced parent directories open.
*
* 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;
/** Reference count. */
size_t refcount;
/** Index in the priority queue. */
size_t heap_index;
/** An open file descriptor to this directory, or -1. */
int fd;
/** 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 {
/** A min-heap of open entries, ordered by refcount. */
struct dircache_entry **heap;
/** Current heap size. */
size_t size;
/** Maximum heap size. */
size_t capacity;
};
/** Initialize a dircache. */
static int dircache_init(struct dircache *cache, size_t capacity) {
cache->heap = malloc(capacity*sizeof(struct dircache_entry *));
if (!cache->heap) {
return -1;
}
cache->size = 0;
cache->capacity = capacity;
return 0;
}
/** Destroy a dircache. */
static void dircache_free(struct dircache *cache) {
assert(cache->size == 0);
free(cache->heap);
}
/** Move an entry to a particular place in the heap. */
static void dircache_heap_move(struct dircache *cache, struct dircache_entry *entry, size_t i) {
cache->heap[i] = entry;
entry->heap_index = i;
}
/** Bubble an entry up the heap. */
static void dircache_bubble_up(struct dircache *cache, struct dircache_entry *entry) {
size_t i = entry->heap_index;
while (i > 0) {
size_t pi = (