index : cgit

/*
 * The cache that lets a repeated request be answered from disk instead of
 * being rendered again. A slot is one file named after the hash of the
 * request key, holding that key and then the page it rendered to, and a lock
 * file beside it is where a replacement page is written before being renamed
 * over the slot. Only the process holding that lock rebuilds a slot, so a
 * request arriving while a stale slot is being rebuilt is served the stale
 * page, and a request with no usable slot at all renders straight to the
 * client without caching anything.
 */

#include "cache.h"
#include "cgit.h"
#include "html.h"
#include "shared.h"
#ifdef HAVE_LINUX_SENDFILE
#include <sys/sendfile.h>
#endif

// One read of a slot file. The stored key has to be recognised out of a
// single such read, so this also bounds how long a cacheable key can be, see
// key_fits_slot.
#define CACHE_BUFSIZE (1024 * 4)

// A slot is named by this many hex digits of the key hash, which is also how
// cache_ls tells slots from the lock files sitting beside them.
#define SLOT_NAME_LEN 8

// The 32 bit FNV-1 offset basis and prime.
#define FNV_OFFSET 0x811c9dc5
#define FNV_PRIME  0x01000193

/*
 * Cache trouble goes to stderr, which under CGI is the web server's error
 * log, so that it cannot land in the middle of the page being written to
 * stdout.
 */
__attribute__((format (printf,1,2)))
static void log_error(const char *format, ...)
{
	va_list args;
	va_start(args, format);
	vfprintf(stderr, format, args);
	va_end(args);
}

struct cache_slot {
	const char *key;
	size_t keylen;
	int ttl;
	cache_fill_fn fn;
	int cache_fd;
	int lock_fd;
	int saved_stdout;
	const char *path;
	const char *lock_path;
	int key_matches;
	// Set when the fill was abandoned part way through, meaning the error
	// page has already reached the visitor and nothing more may be served
	// after it, not the lock file and not the stale copy still open.
	int abandoned;
	// The slot as it was when it was opened, or the lock file once
	// fill_slot has written a page into it.
	struct stat st;
	// How much of the slot was read into buf, not the size of buf.
	int buflen;
	char buf[CACHE_BUFSIZE];
};

static int open_slot(struct cache_slot *slot)
{
	char *nul;
	ssize_t keylen = -1;

	slot->cache_fd = open(slot->path, O_RDONLY);
	if (slot->cache_fd == -1)
		return errno;

	if (fstat(slot->cache_fd, &slot->st))
		return errno;

	slot->buflen = xread(slot->cache_fd, slot->buf, sizeof(slot->buf));
	if (slot->buflen < 0)
		return errno;

	nul = memchr(slot->buf, 0, slot->buflen);
	if (nul)
		keylen = nul - slot->buf;

	if (slot->key)
		slot->key_matches = keylen >= 0 &&
		    (size_t)keylen == slot->keylen &&
		    !memcmp(slot->key, slot->buf, keylen + 1);

	return 0;
}

/*
 * A key longer than the buffer above can never be read back by open_slot, so
 * a slot keyed on one would never match and every such request would
 * regenerate its page while still writing a slot nothing can use.
 */
static int key_fits_slot(const char *key)
{
	return strlen(key) + 1 <= CACHE_BUFSIZE;
}

static int close_slot(struct cache_slot *slot)
{
	int err = 0;
	if (slot->cache_fd > 0) {
		if (close(slot->cache_fd))
			err = errno;
		else
			slot->cache_fd = -1;
	}
	return err;
}

static int print_slot(struct cache_slot *slot)
{
	off_t off;
#ifdef HAVE_LINUX_SENDFILE
	off_t size;
#endif

	off = slot->keylen + 1;

#ifdef HAVE_LINUX_SENDFILE
	size = slot->st.st_size;

	do {
		ssize_t ret;
		ret = sendfile(STDOUT_FILENO, slot->cache_fd, &off, size - off);
		if (ret < 0) {
			if (errno == EAGAIN || errno == EINTR)
				continue;
			// EINVAL and ENOSYS mean this kernel or this pair of
			// descriptors cannot do sendfile at all, so fall back
			// to the read and write loop rather than fail the
			// request.
			if (errno == EINVAL || errno == ENOSYS)
				break;
			return errno;
		}
		if (off == size)
			return 0;
	} while (1);
#endif

	if (lseek(slot->cache_fd, off, SEEK_SET) != off)
		return errno;

	do {
		ssize_t ret;
		ret = xread(slot->cache_fd, slot->buf, sizeof(slot->buf));
		if (ret < 0)
			return errno;
		if (ret == 0)
			return 0;
		if (write_in_full(STDOUT_FILENO, slot->buf, ret) < 0)
			return errno;
	} while (1);
}

static int serve_slot(struct cache_slot *slot)
{
	int err;

	err = print_slot(slot);
	if (err)
		log_error("[cgit] error printing cache %s: %s (%d)\n",
			  slot->path,
			  strerror(err),
			  err);
	return err;
}

static int is_expired(struct cache_slot *slot)
{
	if (slot->ttl < 0)
		return 0;
	return slot->st.st_mtime + slot->ttl * SECONDS_PER_MINUTE < time(NULL);
}

/*
 * A stat that fails counts as modified, so that the caller leaves alone a file
 * it was unable to look at.
 */
static int is_modified(struct cache_slot *slot)
{
	struct stat current;

	if (stat(slot->path, &current))
		return 1;
	return (current.st_ino != slot->st.st_ino ||
		current.st_mtime != slot->st.st_mtime ||
		current.st_size != slot->st.st_size);
}

static int close_lock(struct cache_slot *slot)
{
	int err = 0;
	if (slot->lock_fd > 0) {
		if (close(slot->lock_fd))
			err = errno;
		else
			slot->lock_fd = -1;
	}
	return err;
}

/*
 * The lock file becomes the slot once it is renamed, so it has to open with
 * the key the same way a slot does. The lock is taken without blocking,
 * because failing to get it is how a second process learns that this slot is
 * already being rebuilt, so it returns an errno instead of waiting.
 */
static int lock_slot(struct cache_slot *slot)
{
	struct flock lock = {
		.l_type = F_WRLCK,
		.l_whence = SEEK_SET,
		.l_start = 0,
		.l_len = 0,
	};
	struct stat held, named;

	slot->lock_fd = open(slot->lock_path, O_RDWR | O_CREAT,
			     S_IRUSR | S_IWUSR);
	if (slot->lock_fd == -1)
		return errno;
	if (fcntl(slot->lock_fd, F_SETLK, &lock) < 0) {
		int saved_errno = errno;
		close(slot->lock_fd);
		slot->lock_fd = -1;
		return saved_errno;
	}
	// The lock landed on whatever inode the path named at open. A holder
	// finishing in between renames that inode into place as the live
	// slot, so truncating it on the strength of the stale descriptor
	// would tear down the page other requests are reading. Once the path
	// is confirmed to still name this file the rename can no longer
	// happen, because doing so takes the lock now held here.
	if (fstat(slot->lock_fd, &held) || stat(slot->lock_path, &named) ||
	    held.st_ino != named.st_ino || held.st_dev != named.st_dev) {
		close(slot->lock_fd);
		slot->lock_fd = -1;
		return EAGAIN;
	}
	// A run that died before its rename leaves the lock file behind, so
	// start from empty now that nobody else can be writing it.
	if (ftruncate(slot->lock_fd, 0) < 0)
		return errno;
	if (xwrite(slot->lock_fd, slot->key, slot->keylen + 1) < 0)
		return errno;
	return 0;
}

static int unlock_slot(struct cache_slot *slot, int replace_old_slot)
{
	int err;

	if (replace_old_slot)
		err = rename(slot->lock_path, slot->path);
	else
		err = unlink(slot->lock_path);

	if (slot->saved_stdout >= 0) {
		dup2(slot->saved_stdout, STDOUT_FILENO);
		close(slot->saved_stdout);
		slot->saved_stdout = -1;
	}

	if (err)
		return errno;

	return 0;
}

// Only one slot is ever being filled at a time, so a single pointer is enough
// for cache_abandon_fill to find its way back to the client.
static struct cache_slot *slot_being_filled;

void cache_abandon_fill(void)
{
	struct cache_slot *slot = slot_being_filled;

	if (!slot)
		return;
	slot_being_filled = NULL;
	slot->abandoned = 1;

	// The page is sitting in html.c's buffer and in stdio's, and both are
	// emptied while stdout still points at the lock file, so the half
	// rendered page goes into the file about to be removed rather than
	// reaching the client ahead of whatever is written next.
	html_flush();
	fflush(stdout);

	if (slot->saved_stdout >= 0) {
		dup2(slot->saved_stdout, STDOUT_FILENO);
		close(slot->saved_stdout);
		slot->saved_stdout = -1;
	}
	unlink(slot->lock_path);
}

/*
 * Renders with stdout pointed at the lock file, and on success or failure
 * alike it is unlock_slot that gives stdout back.
 */
static int fill_slot(struct cache_slot *slot)
{
	slot->saved_stdout = dup(STDOUT_FILENO);
	if (slot->saved_stdout == -1)
		return errno;

	if (dup2(slot->lock_fd, STDOUT_FILENO) == -1)
		return errno;

	slot_being_filled = slot;
	slot->fn();
	slot_being_filled = NULL;

	// The page is sitting in html.c's buffer and then in stdio's, and all
	// of it has to reach the lock file before that file is renamed into
	// place. After an abandoned fill stdout is the client again and this
	// same flush delivers the tail of the error page instead.
	html_flush();
	if (fflush(stdout))
		return errno;

	if (slot->abandoned)
		return 0;

	// print_slot takes the length of what it copies from here, and what
	// it copies after a fill is the lock file rather than the old slot.
	if (fstat(slot->lock_fd, &slot->st))
		return errno;

	return 0;
}

/*
 * Giving up is always a valid outcome, because the caller still has the
 * expired copy open and can serve that.
 */
static void refresh_slot(struct cache_slot *slot)
{
	if (lock_slot(slot))
		return;

	// If another process replaced the slot between open_slot and
	// lock_slot, the copy already open is served rather than the newer
	// one, which would mean opening that file and comparing the key in it,
	// not worth a second descriptor and read on every expiry.
	if (is_modified(slot) || fill_slot(slot)) {
		unlock_slot(slot, 0);
		close_lock(slot);
	} else if (slot->abandoned) {
		// The abandoned fill answered the visitor itself and removed
		// the lock file, so only the descriptor is left to clean up.
		close_lock(slot);
	} else {
		close_slot(slot);
		unlock_slot(slot, 1);
		slot->cache_fd = slot->lock_fd;
	}
}

static int process_slot(struct cache_slot *slot)
{
	int err;

	err = open_slot(slot);
	if (!err && slot->key_matches) {
		if (is_expired(slot))
			refresh_slot(slot);
		// A refresh the error page abandoned has already answered the
		// visitor, and serving the stale copy still open would append
		// a second page to that answer.
		if (slot->abandoned) {
			close_slot(slot);
			return 0;
		}
		err = serve_slot(slot);
		close_slot(slot);
		return err;
	}

	// A slot that opened cleanly but holds another key is a collision,
	// and two popular pages sharing one slot evict each other on every
	// alternating visit. Nothing else makes that visible, because the
	// cache keeps working and only quietly stops helping.
	if (!err)
		log_error("[cgit] cache slot %s holds a different key, "
			  "consider a larger cache-size\n", slot->path);

	// If any part of creating a slot fails the page is still rendered
	// straight to the client and the caller is told the request succeeded,
	// because it did.
	close_slot(slot);
	if ((err = lock_slot(slot)) != 0) {
		log_error("[cgit] Unable to lock slot %s: %s (%d)\n",
			  slot->lock_path, strerror(err), err);
		slot->fn();
		return 0;
	}

	if ((err = fill_slot(slot)) != 0) {
		log_error("[cgit] Unable to fill slot %s: %s (%d)\n",
			  slot->lock_path, strerror(err), err);
		unlock_slot(slot, 0);
		close_lock(slot);
		// Rendering again is only right when nothing was delivered,
		// and an abandoned fill has already sent the error page.
		if (!slot->abandoned)
			slot->fn();
		return 0;
	}

	if (slot->abandoned) {
		close_lock(slot);
		return 0;
	}

	// Opening the slot by name after the rename could land on a file a
	// concurrent writer put there for a different key, so what gets
	// printed is the descriptor still open on the lock file.
	slot->cache_fd = slot->lock_fd;
	unlock_slot(slot, 1);
	err = serve_slot(slot);
	close_slot(slot);
	return err;
}

// The result lives in a static buffer and is only good until the next call.
static char *format_time(const char *format, time_t when)
{
	static char buf[64];
	struct tm tm;

	if (!when)
		return NULL;
	gmtime_r(&when, &tm);
	strftime(buf, sizeof(buf) - 1, format, &tm);
	return buf;
}

/*
 * The accumulator is an unsigned long rather than a fixed 32 bit type, so on a
 * 64 bit host this is not the published FNV-1 value. All that decides is which
 * slot a key lands in, and nothing outside a single build has to agree on the
 * answer.
 */
unsigned long cache_hash_str(const char *str)
{
	unsigned long h = FNV_OFFSET;
	unsigned char *s = (unsigned char *)str;

	if (!s)
		return h;

	while (*s) {
		h *= FNV_PRIME;
		h ^= *s++;
	}
	return h;
}

int cache_process(int size, const char *path, const char *key, int ttl,
		  cache_fill_fn fn)
{
	unsigned long hash;
	int i;
	struct strbuf slot_path = STRBUF_INIT;
	struct strbuf lock_path = STRBUF_INIT;
	struct cache_slot slot;
	int result;

	if (size <= 0 || ttl == 0) {
		fn();
		return 0;
	}

	if (!path) {
		log_error("[cgit] Cache path not specified, caching is disabled\n");
		fn();
		return 0;
	}
	if (!key)
		key = "";
	if (!key_fits_slot(key)) {
		log_error("[cgit] Cache key too long for a slot, caching is "
			  "disabled for this request\n");
		fn();
		return 0;
	}
	hash = cache_hash_str(key) % size;
	strbuf_addstr(&slot_path, path);
	strbuf_ensure_end(&slot_path, '/');
	for (i = 0; i < SLOT_NAME_LEN; i++) {
		strbuf_addf(&slot_path, "%x", (unsigned char)(hash & 0xf));
		hash >>= 4;
	}
	strbuf_addbuf(&lock_path, &slot_path);
	strbuf_addstr(&lock_path, ".lock");
	slot.fn = fn;
	slot.ttl = ttl;
	slot.saved_stdout = -1;
	slot.abandoned = 0;
	slot.path = slot_path.buf;
	slot.lock_path = lock_path.buf;
	slot.key = key;
	slot.keylen = strlen(key);
	result = process_slot(&slot);

	strbuf_release(&slot_path);
	strbuf_release(&lock_path);
	return result;
}

int cache_ls(const char *path)
{
	DIR *dir;
	struct dirent *ent;
	int err = 0;
	// A NULL key leaves open_slot with nothing to compare against, so
	// every slot it opens is simply read.
	struct cache_slot slot = { NULL };
	struct strbuf slot_path = STRBUF_INIT;
	size_t prefixlen;
	char *nul;
	int keylen;

	if (!path) {
		log_error("[cgit] cache path not specified\n");
		return -1;
	}
	dir = opendir(path);
	if (!dir) {
		err = errno;
		log_error("[cgit] unable to open path %s: %s (%d)\n",
			  path, strerror(err), err);
		return err;
	}
	strbuf_addstr(&slot_path, path);
	strbuf_ensure_end(&slot_path, '/');
	prefixlen = slot_path.len;
	while ((ent = readdir(dir)) != NULL) {
		if (strlen(ent->d_name) != SLOT_NAME_LEN)
			continue;
		strbuf_setlen(&slot_path, prefixlen);
		strbuf_addstr(&slot_path, ent->d_name);
		slot.path = slot_path.buf;
		if ((err = open_slot(&slot)) != 0) {
			log_error("[cgit] unable to open path %s: %s (%d)\n",
				  slot_path.buf, strerror(err), err);
			continue;
		}
		// A truncated or corrupt slot may hold no NUL, so the print is
		// bounded by what was read and cannot run off the end.
		nul = memchr(slot.buf, 0, slot.buflen);
		keylen = nul ? (int)(nul - slot.buf) : slot.buflen;
		htmlf("%s %s %10"PRIuMAX" %.*s\n",
		      slot_path.buf,
		      format_time("%Y-%m-%d %H:%M:%S",
				  slot.st.st_mtime),
		      (uintmax_t)slot.st.st_size,
		      keylen, slot.buf);
		close_slot(&slot);
	}
	closedir(dir);
	strbuf_release(&slot_path);
	return 0;
}