path: root/map.c

/* See LICENSE file for copyright and license details. */
#include "common.h"


void
add_span(struct status *status, off_t off, off_t amount, size_t blocksize, int try_join)
{
	off_t end = off + amount;

	while ((off_t)(blocksize >> 1) >= amount)
		blocksize >>= 1;

	if (try_join) {
		if (off == status->spans[status->nspans - 1U].end || end == status->spans[status->nspans - 1U].start) {
			status->spans[status->nspans - 1U].start = MIN(off, status->spans[status->nspans - 1U].start);
			status->spans[status->nspans - 1U].end = MAX(end, status->spans[status->nspans - 1U].end);
			status->spans[status->nspans - 1U].bad += amount;
			status->spans[status->nspans - 1U].blocksize = MAX(blocksize, status->spans[status->nspans - 1U].blocksize);
			return;
		}
	}

	if (status->nspans == status->spans_size) {
		status->spans_size += 1024;
		status->spans = ereallocarray(status->spans, status->spans_size, sizeof(*status->spans));
	}

	status->spans[status->nspans].start = off;
	status->spans[status->nspans].end = end;
	status->spans[status->nspans].bad = amount;
	status->spans[status->nspans].blocksize = blocksize;
	status->nspans++;
}


void
dump_map(int fd, const struct status *status, const char *fname)
{
	size_t i;
	int r;

	if (status->nspans == status->span_off)
		return;

	for (i = status->span_off; i < status->nspans; i++) {
		r = dprintf(fd, "%s%jx-%jx/%zx",
		            i ? "," : "0x",
		            (uintmax_t)status->spans[i].start,
		            (uintmax_t)status->spans[i].end,
		            status->spans[i].blocksize);
		if (r < 0)
			goto fail;
	}
	r = dprintf(fd, "\n");
	if (r < 0)
		goto fail;

	return;

fail:
	eprintf("dprintf %s:", fname);
}


off_t
measure_map_dump(const struct status *status)
{
	size_t i;
	int r;
	off_t ret = 1;

	if (status->nspans == status->span_off)
		return 0;

	for (i = status->span_off; i < status->nspans; i++) {
		r = snprintf(NULL, 0, "%s%jx-%jx/%zx",
		             i ? "," : "0x",
		             (uintmax_t)status->spans[i].start,
		             (uintmax_t)status->spans[i].end,
		             status->spans[i].blocksize);
		if (r < 0)
			eprintf("snprintf:");
		ret += r;
	}

	return ret;
}


static int
spancmp(const void *av, const void *bv)
{
	const struct span *a = av, *b = bv;
	return a->start < b->start ? -1 : a->start > b->start;
}


off_t
load_map(int fd, struct status *status, enum direction direction, const char *fname)
{
	char buf[8UL << 10], *end;
	size_t off = 0;
	size_t p = 0, start = 0, i, j;
	ssize_t r;
	int empty = 1, state = 0, ended = 0;
	uintmax_t v1 = 0, v2 = 0, v3 = 0, *vp;
	struct span refspan = status->spans[0], t;
	off_t preshredded, min_start;

	for (;;) {
		r = read(fd, &buf[off], sizeof(buf) - off);
		if (r <= 0) {
			if (!r)
				break;
			if (errno == EINTR)
				continue;
			eprintf("read %s:", fname);
		}
		off += (size_t)r;
		if (empty) {
			if (off < 2)
				continue;
			status->nspans = 0;
			empty = 0;
			if (buf[0] != '0' || buf[1] != 'x')
				goto invalid;
			p = 2U;
		}
		if (ended)
			goto invalid;

		while (p < off) {
			switch (state) {
			case 0:
				errno = 0;
				/* fall through */
			case 2:
			case 4:
				start = p;
				if (!isxdigit(buf[p]))
					goto invalid;
				p++;
				state += 1;
				break;
			case 1:
				vp = &v1;
				goto value;
			case 3:
				vp = &v2;
				goto value;
			case 5:
				vp = &v3;
			value:
				if (isxdigit(buf[p])) {
					p++;
					break;
				}
				if (state == 1) {
					if (buf[p] != '-')
						goto invalid;
					state += 1;
				} else {
					if (state == 3 && buf[p] == '/') {
						state += 1;
					} else if (buf[p] == ',') {
						v3 = refspan.blocksize;
						state += 3;
					} else if (buf[p] == '\n') {
						v3 = refspan.blocksize;
						state += 3;
						ended = 1;
					} else {
						goto invalid;
					}
					
				}
				buf[p++] = '\0';
				*vp = strtoumax(&buf[start], &end, 16);
				if (errno || *end)
					goto invalid;
				if (state == 6) {
					state = 0;
					if (v1 >= v2 || v2 > (uintmax_t)OFF_MAX)
						goto invalid;
					if (v3 > v2 - v1)
						v3 = v2 - v1;
					if (v3 > (uintmax_t)SIZE_MAX)
						v3 = ((uintmax_t)SIZE_MAX >> 1) + 1U;
					if (v3 > refspan.blocksize)
						v3 = refspan.blocksize;

					if ((off_t)v1 < refspan.start || (off_t)v2 > refspan.end)
						eprintf("%s: contains out of bounds span", fname);

					if (status->nspans == status->spans_size) {
						status->spans_size += 1024;
						status->spans = ereallocarray(status->spans, status->spans_size,
						                              sizeof(*status->spans));
					}

					status->spans[status->nspans].start = (off_t)v1;
					status->spans[status->nspans].end = (off_t)v2;
					status->spans[status->nspans].bad = 0;
					status->spans[status->nspans].blocksize = (size_t)v3;
					status->nspans++;
				}
				break;
			}
		}

		off = 0;
	}

	if (!ended)
		eprintf("%s: truncated file content", fname);

	if (empty)
		return 0;

	qsort(status->spans, status->nspans, sizeof(*status->spans), &spancmp);
	min_start = -1;
	preshredded = refspan.end - refspan.start;
	for (i = 0; i < status->nspans; i++) {
		if (status->spans[i].start < min_start)
			goto invalid;
		if (status->spans[i].start == min_start &&
		    status->spans[i].blocksize == status->spans[i - 1U].blocksize) {
			status->spans[i - 1U].end = status->spans[i].end;
			memmove(&status->spans[i], &status->spans[i + 1U],
			        (--status->nspans - i) * sizeof(*status->spans));
			i--;
		}
		min_start = status->spans[i].end;
		preshredded -= status->spans[i].end - status->spans[i].start;
	}
	if (direction == BACKWARDS) {
		for (i = 0, j = status->nspans; --j > i; i++) {
			t = status->spans[i];
			status->spans[i] = status->spans[j];
			status->spans[j] = t;
		}
	}
		
	return preshredded;

invalid:
	eprintf("%s: invalid file content", fname);
}


void
update_map(int fd, const struct status *status, const char *fname)
{
#define STR(S) (S), sizeof(S) - 1U

	static char dots[4096] = {0};

	off_t old_len, new_len, pos;
	ssize_t r;

	if (!dots[0])
		memset(dots, '.', sizeof(dots));

	old_len = lseek(fd, 0, SEEK_CUR);
	if (old_len < 0)
		eprintf("lseek %s 0 SEEK_CUR:", fname);

	new_len = measure_map_dump(status);

	pos = old_len;
	if (pos < new_len) {
		while (pos < new_len - 1) {
			r = write(fd, dots, (size_t)MIN((off_t)sizeof(dots), new_len - 1 - pos));
			if (r < 0) {
				if (errno == EINTR)
					continue;
				eprintf("write %s:", fname);
			}
			pos += (off_t)r;
		}
		do {
			r = write(fd, "\n", 1U);
		} while (r < 0 && errno == EINTR);
		if (r < 0)
			eprintf("write %s:", fname);
	}

	writeall(fd, STR(">> FIRST LINE IS CORRECT UNLESS THE AS ANOTHER NOTICE BELOW THIS ONE >>\n"), fname);

	filecpy(fd, 0, old_len, fname);

	writeall(fd, STR(">> LINE ABOVE IS THE CORRECT ONE >>\n"), fname);

	for (;;) {
		if (!fdatasync(fd))
			break;
		if (errno != EINTR)
			eprintf("fdatasync %s:", fname);
	}

	if (lseek(fd, 0, SEEK_SET))
		eprintf("lseek %s 0 SEEK_SET:", fname);

	dump_map(fd, status, fname);

	pos = lseek(fd, 0, SEEK_CUR);
	if (pos < 0)
		eprintf("lseek %s 0 SEEK_CUR:", fname);

	for (;;) {
		if (!ftruncate(fd, pos))
			break;
		if (errno != EINTR)
			eprintf("ftruncate %s %ji:", fname, (intmax_t)pos);
	}

	for (;;) {
		if (!fsync(fd))
			break;
		if (errno != EINTR)
			eprintf("fsync %s:", fname);
	}

#undef STR
}