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 largest page a slot may keep, with zero for no bound, and whether
	// the fill went past it, in which case the lock file is served and then
	// dropped instead of published.
	size_t max_bytes;
	int oversized;
	// 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 = read_in_full(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 be written but never match.
 */
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;
		}
		// Zero means the file ended short of the size it had when it
		// was opened, and the read loop below finds that end.
		if (ret == 0)
			break;
		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);
	// A client that went away mid-page is not trouble worth a line.
	if (err && err != EPIPE)
		log_error("[cgit] Unable to send slot %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;
	// Widened before the multiply, since a ttl in the tens of millions of
	// minutes overflows an int.
	return slot->st.st_mtime + (time_t)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, and once the path is confirmed to still name this file that
	// rename can no longer happen, because it takes the lock 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 (write_in_full(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 cache_abandon_fill finds
// it here.
static struct cache_slot *slot_being_filled;

/*
 * Copies the page the lock file holds so far to stdout, which by then is the
 * client again.
 */
static void replay_lock_file(struct cache_slot *slot)
{
	off_t off = slot->keylen + 1;
	ssize_t got;

	if (lseek(slot->lock_fd, off, SEEK_SET) != off)
		return;
	while ((got = xread(slot->lock_fd, slot->buf, sizeof(slot->buf))) > 0) {
		if (write_in_full(STDOUT_FILENO, slot->buf, got) < 0)
			return;
	}
}

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

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

	// What git wrote through stdio joins the lock file first, then the
	// file is played back so the visitor gets the page up to the point it
	// stopped. The buffer in html.c is the caller's to flush, since a
	// caller that could not write it must not try again here.
	fflush(stdout);

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

/*
 * The page is served from the descriptor either way, so a failed rename only
 * costs the next request a render.
 */
static void publish_slot(struct cache_slot *slot)
{
	int err = unlock_slot(slot, 1);

	if (err)
		log_error("[cgit] Unable to publish cache slot %s: %s (%d)\n", slot->path,
			strerror(err), err);
}

/*
 * 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;
	// A filter program that outlives the request must not hold the client
	// connection open.
	fcntl(slot->saved_stdout, F_SETFD, FD_CLOEXEC);

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

	slot_being_filled = slot;
	slot->fn();

	// All of the page has to reach the lock file before it is renamed
	// into place, and a write that fails on this last flush still finds
	// the slot to abandon, so the page goes to the visitor rather than
	// nowhere. After an abandoned fill stdout is the client again and
	// this same flush delivers the tail of the error page instead.
	html_flush();
	slot_being_filled = NULL;
	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;
	slot->oversized = slot->max_bytes && (size_t)slot->st.st_size > slot->max_bytes;

	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.
	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);
		if (slot->oversized) {
			// The expired copy goes too, or every later request
			// would refill it and drop the result again.
			unlink(slot->path);
			unlock_slot(slot, 0);
		} else {
			publish_slot(slot);
		}
		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.
	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;
	if (slot->oversized)
		unlock_slot(slot, 0);
	else
		publish_slot(slot);
	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 const char *format_time(const char *format, time_t when)
{
	static char buf[64];
	struct tm tm;

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

/*
 * The accumulator is unsigned long, so on a 64 bit host this is not the
 * published FNV-1 value. Only slot selection depends on it.
 */
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, size_t max_bytes,
	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.max_bytes = max_bytes;
	slot.oversized = 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 read.
	struct cache_slot slot = { 0 };
	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 %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))) {
		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 %s: %s (%d)\n", slot_path.buf, strerror(err), err);
			close_slot(&slot);
			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;
}