/*********************************************************************
* 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 "dstring.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>
/**
* 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 = (i - 1)/2;
struct dircache_entry *parent = cache->heap[pi];
if (entry->refcount >= parent->refcount) {
break;
}
dircache_heap_move(cache, parent, i);
i = pi;
}
dircache_heap_move(cache, entry, i);
}
/** Bubble an entry down the heap. */
static void dircache_bubble_down(struct dircache *cache, struct dircache_entry *entry) {
size_t i = entry->heap_index;
while (true) {
size_t ci = 2*i + 1;
if (ci >= cache->size) {
break;
}
struct dircache_entry *child = cache->heap[ci];
size_t ri = ci + 1;
if (ri < cache->size) {
struct dircache_entry *right = cache->heap[ri];
if (child->refcount > right->refcount) {
ci = ri;
child = right;
}
}
dircache_heap_move(cache, child, i);
i = ci;
}
dircache_heap_move(cache, entry, i);
}
/** Increment a dircache_entry's reference count. */
static void dircache_entry_incref(struct dircache *cache, struct dircache_entry *entry) {
++entry->refcount;
if (entry->fd >= 0) {
dircache_bubble_down(cache, entry);
}
}
/** Decrement a dircache_entry's reference count. */
static void dircache_entry_decref(struct dircache *cache, struct dircache_entry *entry) {
--entry->refcount;
if (entry->fd >=