/*
 * Copyright (C) 2007-2009 Andre Noll <maan@tuebingen.mpg.de>
 *
 * Licensed under the GPL v2. For licencing details see COPYING.
 */

/** \file fsck.c The program used to check an osl table. */

#include <sys/stat.h>
#include <sys/types.h>
#include <dirent.h>
#include <lopsub.h>
#include <assert.h>
#include <pwd.h>

#include "log.h"
#include "osl.h"
#include "util.h"
#include "osl_core.h"
#include "oslfsck.lsg.h"

static struct lls_parse_result *lpr;
#define CMD_PTR (lls_cmd(0, oslfsck_suite))
#define OPT_RESULT(_name) \
	(lls_opt_result(LSG_OSLFSCK_OSLFSCK_OPT_ ## _name, lpr))
#define OPT_GIVEN(_name) (lls_opt_given(OPT_RESULT(_name)))
#define OPT_STRING_VAL(_name) (lls_string_val(0, OPT_RESULT(_name)))
#define OPT_UINT32_VAL(_name) (lls_uint32_val(0, OPT_RESULT(_name)))

#define FSCK_ERRORS \
	FSCK_ERROR(RANGE_VIOLATION, "range violation detected, very bad"), \
	FSCK_ERROR(NOT_A_REGULAR_FILE, "not a regular file"), \
	FSCK_ERROR(SYNTAX, "fsck syntax error"), \
	FSCK_ERROR(ACCESS, "permission denied"), \
	FSCK_ERROR(CHDIR, "could not change directory"), \
	FSCK_ERROR(OPENDIR, "could not open directory"),

#define FSCK_ERROR_BIT 29
#define FSCK_ERROR(num, txt) E_FSCK_ ## num
enum {
	FSCK_DUMMY = (1 << FSCK_ERROR_BIT) - 1,
	FSCK_ERRORS
};
#undef FSCK_ERROR
#define FSCK_ERROR(num, txt) txt
static const char *fsck_errors[] = {
	FSCK_ERRORS
};

static const char *fsck_strerror(int num)
{
	if (num & (1 << FSCK_ERROR_BIT))
		return fsck_errors[num & ((1 << FSCK_ERROR_BIT) - 1)];
	return osl_strerror(num);
}

extern int loglevel;

/* taken from git */
static signed char hexval_table[256] = {
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 00-07 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 08-0f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 10-17 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 18-1f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 20-27 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 28-2f */
	  0,  1,  2,  3,  4,  5,  6,  7,		/* 30-37 */
	  8,  9, -1, -1, -1, -1, -1, -1,		/* 38-3f */
	 -1, 10, 11, 12, 13, 14, 15, -1,		/* 40-47 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 48-4f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 50-57 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 58-5f */
	 -1, 10, 11, 12, 13, 14, 15, -1,		/* 60-67 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 68-67 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 70-77 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 78-7f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 80-87 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 88-8f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 90-97 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* 98-9f */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* a0-a7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* a8-af */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* b0-b7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* b8-bf */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* c0-c7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* c8-cf */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* d0-d7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* d8-df */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* e0-e7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* e8-ef */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* f0-f7 */
	 -1, -1, -1, -1, -1, -1, -1, -1,		/* f8-ff */
};

static int asc_to_hash(const char *asc_hash, int len, HASH_TYPE *hash)
{
	int i = 0;
	const unsigned char *asc = (const unsigned char *) asc_hash;

	while (*asc && i++ < len) {
		unsigned int val = (hexval_table[asc[0]] << 4) | hexval_table[asc[1]];
		if (val & ~0xff)
			return -1;
		*hash++ = val;
		asc += 2;

	}
	return 1;
}

static int _write_all(int fd, const char *buf, size_t len)
{
	return write_all(fd, buf, &len);
}

/*
 * Wrapper for malloc().
 *
 * \param size The desired new size.
 *
 * A wrapper for malloc(3) which exits on errors.
 *
 * \return A pointer to the allocated memory, which is suitably aligned for any
 * kind of variable.
 *
 * \sa malloc(3).
 */
__must_check __malloc static void *fsck_malloc(size_t size)
{
	assert(size);
	void *p = malloc(size);

	if (!p) {
		EMERG_LOG("malloc failed (size = %zu),  aborting\n",
			size);
		exit(EXIT_FAILURE);
	}
	return p;
}

/**
 * Allocate memory and fill with zeros.
 *
 * \param size The desired new size.
 *
 * A wrapper for calloc(3) which exits on errors.
 *
 * \return A pointer to the allocated and zeroed-out memory, which is suitably
 * aligned for any kind of variable.
 *
 * \sa calloc(3)
 */
__must_check __malloc static void *fsck_calloc(size_t size)
{
	void *ret = fsck_malloc(size);

	memset(ret, 0, size);
	return ret;
}

/**
 * Save version of strdup().
 *
 * \param s The string to be duplicated.
 *
 * A wrapper for strdup(3). It calls \p exit(EXIT_FAILURE) on errors, i.e.
 * there is no need to check the return value in the caller.
 *
 * \return A pointer to the duplicated string. If \p s was the NULL pointer,
 * an pointer to an empty string is returned.
 *
 * \sa strdup(3)
 */
__must_check __malloc static char *fsck_strdup(const char *s)
{
	char *ret;

	if ((ret = strdup(s? s: "")))
		return ret;
	EMERG_LOG("strdup failed, aborting\n");
	exit(EXIT_FAILURE);
}

/**
 * Compare two osl objects pointing to unsigned integers of 32 bit size.
 *
 * \param obj1 Pointer to the first integer.
 * \param obj2 Pointer to the second integer.
 *
 * \return The values required for an osl compare function.
 *
 * \sa osl_compare_func, osl_hash_compare().
 */
static int uint32_compare(const struct osl_object *obj1, const struct osl_object *obj2)
{
	uint32_t d1 = read_u32((const char *)obj1->data);
	uint32_t d2 = read_u32((const char *)obj2->data);

	if (d1 < d2)
		return 1;
	if (d1 > d2)
		return -1;
	return 0;
}

/**
 * A wrapper for fchdir().
 *
 * \param fd An open file descriptor.
 *
 * \return Standard.
 */
static inline int __fchdir(int fd)
{
	if (fchdir(fd) >= 0)
		return 1;
	return errno == EACCES? -E_FSCK_ACCESS : -E_FSCK_CHDIR;
}

/**
 * Wrapper for chdir(2).
 *
 * \param path The specified directory.
 *
 * \return Standard.
 */
_static_inline_ int __chdir(const char *path)
{
	if (chdir(path) >= 0)
		return 1;
	return errno == EACCES? -E_FSCK_ACCESS : -E_FSCK_CHDIR;
}

/**
 * Save the cwd and open a given directory.
 *
 * \param dirname Path to the directory to open.
 * \param dir Result pointer.
 * \param cwd File descriptor of the current working directory.
 *
 * \return Standard.
 *
 * Opening the current directory (".") and calling fchdir() to return is
 * usually faster and more reliable than saving cwd in some buffer and calling
 * chdir() afterwards.
 *
 * If \a cwd is not \p NULL "." is opened and the resulting file descriptor is
 * stored in \a cwd. If the function returns success, and \a cwd is not \p
 * NULL, the caller must close this file descriptor (probably after calling
 * fchdir(*cwd)).
 *
 * On errors, the function undos everything, so the caller needs neither close
 * any files, nor change back to the original working directory.
 *
 * \sa getcwd(3).
 *
 */
static int fsck_opendir(const char *dirname, DIR **dir, int *cwd)
{
	int ret;

	if (cwd) {
		ret = osl_open(".", O_RDONLY, 0);
		if (ret < 0)
			return ret;
		*cwd = ret;
	}
	ret = __chdir(dirname);
	if (ret < 0)
		goto close_cwd;
	*dir = opendir(".");
	if (*dir)
		return 1;
	ret = errno == EACCES? -E_FSCK_ACCESS : -E_FSCK_OPENDIR;
	/* Ignore return value of fchdir() and close(). We're busted anyway. */
	if (cwd) {
		int __a_unused ret2 = fchdir(*cwd); /* STFU, gcc */
	}
close_cwd:
	if (cwd)
		close(*cwd);
	return ret;
}



/**
 * Traverse the given directory recursively.
 *
 * \param dirname The directory to traverse.
 * \param func The function to call for each entry.
 * \param private_data Pointer to an arbitrary data structure.
 *
 * For each regular file under \a dirname, the supplied function \a func is
 * called.  The full path of the regular file and the \a private_data pointer
 * are passed to \a func. Directories for which the calling process has no
 * permissions to change to are silently ignored.
 *
 * \return Standard.
 */
static int for_each_file_in_dir(const char *dirname,
		int (*func)(const char *, void *), void *private_data)
{
	DIR *dir;
	struct dirent *entry;
	int cwd_fd, ret2, ret = fsck_opendir(dirname, &dir, &cwd_fd);

	if (ret < 0)
		return ret == -E_FSCK_ACCESS? 1 : ret;
	/* scan cwd recursively */
	while ((entry = readdir(dir))) {
		mode_t m;
		char *tmp;
		struct stat s;

		if (!strcmp(entry->d_name, "."))
			continue;
		if (!strcmp(entry->d_name, ".."))
			continue;
		if (lstat(entry->d_name, &s) == -1)
			continue;
		m = s.st_mode;
		if (!S_ISREG(m) && !S_ISDIR(m))
			continue;
		tmp = make_message("%s/%s", dirname, entry->d_name);
		if (!S_ISDIR(m)) {
			ret = func(tmp, private_data);
			free(tmp);
			if (ret < 0)
				goto out;
			continue;
		}
		/* directory */
		ret = for_each_file_in_dir(tmp, func, private_data);
		free(tmp);
		if (ret < 0)
			goto out;
	}
	ret = 1;
out:
	closedir(dir);
	ret2 = __fchdir(cwd_fd);
	if (ret2 < 0 && ret >= 0)
		ret = ret2;
	close(cwd_fd);
	return ret;
}

/*
 * check for object boundary violations
 *
 * test whether the range pointed to by the index entry for a given cell is
 * contained in mapped data file. This should always be the case. Otherwise
 * we are in real trouble.
 */
static int check_range(struct osl_table *t, uint32_t row_num, uint32_t col_num)
{
	char *index_entry;
	struct osl_object obj;
	struct osl_column *col;
	int ret;
	char *map_start, *obj_start;

	ret = get_cell_index(t, row_num, col_num, &index_entry);
	if (ret < 0)
		return ret;
	ret = get_mapped_object(t, col_num, row_num, &obj);
	if (ret < 0)
		return ret;
	col = t->columns + col_num;
	obj_start = obj.data;
	map_start = col->data_map.data;
//	INFO_LOG("obj: %p..%p\n", obj_start, obj_start + obj.size);
//	INFO_LOG("map: %p..%p\n", map_start, map_start + col->data_map.size);
	if (obj_start < map_start || obj_start + obj.size > map_start + col->data_map.size) {
		CRIT_LOG("range violation in row %u, col %u\n", row_num,
			col_num);
		return -E_FSCK_RANGE_VIOLATION;
	}
	DEBUG_LOG("col %u: ok\n", col_num);
	return 1;
}

static int fsck_mark_row_invalid(struct osl_table *t, int i)
{
	if (OPT_GIVEN(DRY_RUN))
		return 0;
	return mark_row_invalid(t, i);
}

/*
 * check all cells of the given table for boundary violations
 */
static int check_index_ranges(struct osl_table *t)
{
	int ret;
	unsigned k, n;

	INFO_LOG("checking for range violations in index\n");
	//DEBUG_LOG("%d rows. %d columns\n", t->num_rows, t->desc->num_columns);
	t->num_invalid_rows = 0;
	for (n = 0; n < t->num_rows; n++) {
		const struct osl_column_description *cd;

		if (row_is_invalid(t, n)) {
			t->num_invalid_rows++;
			continue;
		}
		FOR_EACH_MAPPED_COLUMN(k, t, cd) {
			ret = check_range(t, n, k);
			if (ret < 0) {
				if (ret != -E_FSCK_RANGE_VIOLATION)
					goto err;
				ret = fsck_mark_row_invalid(t, n);
				if (ret < 0)
					goto err;
				t->num_invalid_rows++;
				break;
			}
		}

	}
	if (t->num_invalid_rows)
		NOTICE_LOG("ranges OK. %d invalid row(s) detected\n",
			t->num_invalid_rows);
	else
		INFO_LOG("no invalid rows, no range violations, good\n");
	return 1;
err:
	return ret;
}

static int move_index_entry(struct osl_table *t, uint32_t dest, uint32_t src)
{
	char *dest_ie, *src_ie;
	int ret = get_row_index(t, dest, &dest_ie);

	if (ret < 0)
		return ret;
	ret = get_row_index(t, src, &src_ie);
	if (ret < 0)
		return ret;
	INFO_LOG("moving entry #%u to position %u\n", src, dest);
	memcpy(dest_ie, src_ie, t->row_index_size);
	return 1;
}

static int map_index(const struct osl_table_description *desc, struct osl_object *map)
{
	char *filename = index_filename(desc);
	int ret;

	ret = mmap_full_file(filename, O_RDWR, &map->data, &map->size, NULL);
	DEBUG_LOG("mapping index %s: ret: %d, size: %zu\n", filename, ret, map->size);
	free(filename);
	return ret;
}

static int prune_invalid_rows_from_index(struct osl_table *t)
{
	uint32_t top = 0, bottom;
	char *filename;
	int ret;

	if (!t->num_invalid_rows) {
		INFO_LOG("all rows are valid, good\n");
		return 1;
	}
	NOTICE_LOG("index contains %u invalid row(s) (%d bytes)\n",
		t->num_invalid_rows, t->row_index_size * t->num_invalid_rows);
	if (OPT_GIVEN(DRY_RUN))
		return 0;
	NOTICE_LOG("removing invalid rows from index\n");
	bottom = t->num_rows - 1;
	while (top < bottom) {
		if (!row_is_invalid(t, top)) {
			top++;
			continue;
		}
		while (bottom > top) {
			if (row_is_invalid(t, bottom)) {
				bottom--;
				continue;
			}
			/* move bottom index entry to top */
			move_index_entry(t, top, bottom);
			bottom--;
			top++;
			break;
		}
	}
	DEBUG_LOG("unmapping index\n");
	osl_munmap(t->index_map.data, t->index_map.size);
	filename = index_filename(t->desc);
	ret = truncate_file(filename, t->row_index_size
		* t->num_invalid_rows);
	free(filename);
	if (ret < 0)
		return ret;
	ret = map_index(t->desc, &t->index_map);
	if (ret < 0)
		return ret;
	t->num_rows = table_num_rows(t);
	return 1;
}

static int check_for_invalid_objects(struct osl_table *t, uint32_t **lost_bytes)
{
	int ret;
	unsigned k, n;
	const struct osl_column_description *cd;
	uint32_t *loss = fsck_malloc(sizeof(uint32_t) * t->desc->num_columns);

	INFO_LOG("looking for mapped objects not contained in index\n");
	/* first count used bytes */
	FOR_EACH_MAPPED_COLUMN(k, t, cd) {
		loss[k] = t->columns[k].data_map.size;
		DEBUG_LOG("column %i data map: %zu bytes\n", k,
			t->columns[k].data_map.size);
		for (n = 0; n < t->num_rows; n++) {
			struct osl_object obj;
			ret = get_mapped_object(t, k, n, &obj);
			if (ret < 0)
				goto err;
			loss[k] -= obj.size;
		}
	}
	ret = 0;
	FOR_EACH_MAPPED_COLUMN(k, t, cd) {
		if (loss[k]) {
			NOTICE_LOG("column %u contains %u lost bytes\n",
				k, loss[k]);
			ret = 1;
		}
	}
	if (!ret)
		INFO_LOG("all mapped objects are valid, good\n");
	*lost_bytes = loss;
	return ret;
err:
	free(loss);
	return ret;
}

/* prune_invalid_rows() must be run on the table before calling this */
static int prune_mapped_column(struct osl_table *t, uint32_t col_num, int fd)
{
	int ret;
	unsigned n;
	uint32_t written = 0;
	struct osl_column *col = t->columns + col_num;

	INFO_LOG("pruning col %u\n", col_num);
	for (n = 0; n < t->num_rows; n++) {
		struct osl_object obj;
		char *index_entry;

		DEBUG_LOG("checking row %u/%u\n", n, t->num_rows);
		ret = get_mapped_object(t, col_num, n, &obj);
		if (ret < 0)
			return ret;
		ret = _write_all(fd, (char *)(obj.data), obj.size);
		if (ret < 0)
			return ret;
		written += obj.size;
		ret = get_row_index(t, n, &index_entry);
		if (ret < 0)
			return ret;
		update_cell_index(index_entry, col, written, obj.size);
	}
	return 1;
}

static int prune_objects(struct osl_table *t, uint32_t *lost_bytes)
{
	int i, ret;
	const struct osl_column_description *cd;
	char **col_filenames = fsck_calloc(t->desc->num_columns * sizeof(char *));
	char **new_col_filenames = fsck_calloc(t->desc->num_columns * sizeof(char *));
	char *idx_filename = index_filename(t->desc);
	char *old_idx_filename = make_message("%s.bak", idx_filename);
	int fd;

	NOTICE_LOG("removing unreferenced objects from data files\n");
	/* first make a copy of the index */
	DEBUG_LOG("opening %s\n", old_idx_filename);
	ret = osl_open(old_idx_filename, O_WRONLY | O_CREAT | O_TRUNC, 0644);
	if (ret < 0)
		goto out_free;
	fd = ret;
	ret = _write_all(fd, t->index_map.data, t->index_map.size);
	close(fd);
	if (ret < 0)
		goto out_free;
	FOR_EACH_MAPPED_COLUMN(i, t, cd) {
		if (!lost_bytes[i])
			continue;
		col_filenames[i] = column_filename(t, i);
		new_col_filenames[i] = make_message("%s.fsck", col_filenames[i]);
		ret = osl_open(new_col_filenames[i], O_WRONLY | O_CREAT | O_EXCL, 0644);
		if (ret < 0)
			goto out_unlink_data;
		fd = ret;
		ret = prune_mapped_column(t, i, fd);
		close(fd);
		if (ret < 0)
			goto out_unlink_data;
	}
	ret = unmap_table(t, OSL_MARK_CLEAN);
	if (ret < 0)
		goto out_unlink_data;
	FOR_EACH_MAPPED_COLUMN(i, t, cd) {
		if (!lost_bytes[i])
			continue;
		ret = osl_rename(new_col_filenames[i], col_filenames[i]);
		if (ret < 0) { /* we're kinda screwed here */
			CRIT_LOG("rename of col %i failed: %s\n", i,
				osl_strerror(errno));
			goto out_free;
		}
	}
	unlink(old_idx_filename);
	ret = map_table(t, 0);
	goto out_free;
out_unlink_data:
	FOR_EACH_MAPPED_COLUMN(i, t, cd)
		unlink(new_col_filenames[i]);
out_free:
	free(old_idx_filename);
	free(idx_filename);
	FOR_EACH_MAPPED_COLUMN(i, t, cd) {
		free(col_filenames[i]);
		free(new_col_filenames[i]);
	}
	free(col_filenames);
	free(new_col_filenames);
	return ret;
}

static struct osl_column_description hash_tree_table_cols[] = {
	{
		.storage_type = OSL_NO_STORAGE,
		.storage_flags = OSL_RBTREE | OSL_FIXED_SIZE | OSL_UNIQUE,
		.name = "hash",
		.compare_function = uint32_compare,
		.data_size = HASH_SIZE
	},
};

static const struct osl_table_description hash_tree_table_desc = {
	.dir = "/", /* irrelevant */
	.name = "hash_tree",
	.num_columns = 1,
	.flags = 0,
	.column_descriptions = hash_tree_table_cols
};

/**
 * The hash_tree table contains all hashes of the disk storage name column.
 * of each row. It is used for checking if a disk storage file has a reference
 * in the table.
 */
static struct osl_table *hash_tree_table;
static HASH_TYPE *hashes;

static int check_disk_storage_column(struct osl_table *t, int row_num,
		int col_num, char *ds_name, unsigned *num_missing_objects)
{
	int ret;
	struct stat statbuf;
	char *path = disk_storage_path(t, col_num, ds_name);
	unsigned dsnc = t->disk_storage_name_column;
	struct osl_object obj;

	DEBUG_LOG("checking if %s is a regular file\n", path);
	ret = stat(path, &statbuf);
	if (ret < 0 && errno == ENOENT) {
		struct osl_row *row;
		(*num_missing_objects)++;
		ERROR_LOG("row %d: object %s is missing\n", row_num, path);
		ret = 0;
		if (OPT_GIVEN(DRY_RUN))
			goto out;
		NOTICE_LOG("trying to delete row %d\n", row_num);
		ret = osl_get_row(t, dsnc, &obj, &row);
		if (ret < 0) {
			CRIT_LOG("unable to get row %d\n", row_num);
			fsck_mark_row_invalid(t, row_num);
			CRIT_LOG("Please re-run fsck\n");
			goto out;
		}
		ret = osl_del_row(t, row);
		if (ret < 0)
			goto out;
	}
out:
	free(path);
	if (ret < 0)
		return ret;
	ret = -E_FSCK_NOT_A_REGULAR_FILE;
	if (!(S_IFREG & statbuf.st_mode))
		return ret;
	return 1;
}

static int check_disk_storage_presence(struct osl_table *t)
{
	int ret;
	unsigned k, n;
	struct osl_object obj, hash_obj = {.size = HASH_SIZE};
	char *ds_name;
	const struct osl_column_description *cd;
	unsigned dsnc = t->disk_storage_name_column, missing_objects = 0;

	if (!t->num_rows)
		return 1;
	hashes = fsck_malloc(t->num_rows * HASH_SIZE);
	INFO_LOG("looking for missing disk storage objects\n");
	for (k = 0; k < t->num_rows; k++) {
		if (row_is_invalid(t, k))
			continue;
		ret = get_mapped_object(t, dsnc, k, &obj);
		if (ret < 0)
			return ret;
		hash_object(t, &obj, hashes + k * HASH_SIZE);
		hash_obj.data = hashes + k * HASH_SIZE;
		osl_add_row(hash_tree_table, &hash_obj);
		ds_name = disk_storage_name_of_hash(t, hashes + k * HASH_SIZE);
		FOR_EACH_DISK_STORAGE_COLUMN(n, t, cd) {
			ret = check_disk_storage_column(t, k, n, ds_name,
				&missing_objects);
			if (ret < 0)
				goto err;
		}
		free(ds_name);
	}
	if (!missing_objects)
		INFO_LOG("all referenced disk storage objects exist, good\n");
	else
		NOTICE_LOG("%d missing object(s)\n", missing_objects);
	return missing_objects;
err:
	free(ds_name);
	return ret;
}

static int dummy_compare(const struct osl_object *obj1, const struct osl_object *obj2)
{
	if (obj1 < obj2)
		return -1;
	if (obj1 > obj2)
		return 1;
	return 0;
}

static unsigned files_pruned;

static int prune_disk_storage_file(const char *path, void *private_data)
{
	HASH_TYPE hash[HASH_SIZE];
	uint8_t flags = *(uint8_t *)private_data;
	struct osl_object obj = {.data = hash, .size = HASH_SIZE};
	struct osl_row *row;
	int ret = -1;
	size_t len = strlen(path);


	DEBUG_LOG("path: %s\n", path);
	if (flags & OSL_LARGE_TABLE) {
		if (len < HASH_SIZE * 2 + 2)
			goto invalid;
//		NOTICE_LOG("p: %s\n", path + len - 2 * HASH_SIZE - 1);
		ret = asc_to_hash(path + len - 2 * HASH_SIZE - 1, 1, hash);
		if (ret < 0)
			goto invalid;
		ret = asc_to_hash(path + len - 2 * HASH_SIZE + 2, HASH_SIZE - 1,
			hash + 1);
		if (ret < 0)
			goto invalid;
//		INFO_LOG("high: %x, low: %x, hash: %x\n", high, low, hash);
	} else {
		if (len < 2 * HASH_SIZE + 1)
			goto invalid;
		ret = asc_to_hash(path + len - 2 * HASH_SIZE, 2 * HASH_SIZE, hash);
		if (ret < 0)
			goto invalid;
//		INFO_LOG("hash: %x\n", hash);
	}
#if 0
{
	char asc[2 * HASH_SIZE + 1];
	hash_to_asc(hash, asc);
	NOTICE_LOG("before: %s\nafter: %s\n", path, asc);
}
#endif
	ret = osl_get_row(hash_tree_table, 0, &obj, &row);
	if (ret >= 0)
		return 1;
	NOTICE_LOG("unreferenced file in hash dir: %s\n", path);
	goto remove;
invalid:
	ERROR_LOG("could not read hash value of %s\n", path);
remove:
	if (OPT_GIVEN(DRY_RUN))
		return 0;
	NOTICE_LOG("removing %s\n", path);
	unlink(path);
	files_pruned++;
	return 1;
}

static int prune_disk_storage_files(struct osl_table *t)
{
	int i, ret = 1;
	const struct osl_column_description *cd;

	INFO_LOG("looking for unreferenced disk storage files\n");
	FOR_EACH_DISK_STORAGE_COLUMN(i, t, cd) {
		char *dirname = column_filename(t, i);
		uint8_t flags = t->desc->flags;
		ret = for_each_file_in_dir(dirname, prune_disk_storage_file,
			&flags);
		free(dirname);
	}
	if (files_pruned)
		NOTICE_LOG("%u disk storage files deleted\n",
			files_pruned);
	else
		INFO_LOG("all files are are referenced, good\n");
	return ret;
}

static int check_disk_storage_columns(struct osl_table *t)
{
	int ret, i;
	const struct osl_column_description *cd;

	if (!t->num_disk_storage_columns) {
		INFO_LOG("no disk storage columns in table '%s', "
			"skipping checks\n", t->desc->name);
		return 1;
	}
	FOR_EACH_COLUMN(i, t->desc, cd)
		t->desc->column_descriptions[i].compare_function = dummy_compare;
	ret = init_rbtrees(t);
	if (ret < 0)
		return ret;
	INFO_LOG("creating rbtree for disk storage hash values\n");
	ret = osl_open_table(&hash_tree_table_desc, &hash_tree_table);
	if (ret < 0)
		goto out;
	ret = check_disk_storage_presence(t);
	if (ret < 0)
		goto out_close_hash_tree;
	ret = prune_disk_storage_files(t);
out_close_hash_tree:
	osl_close_table(hash_tree_table, 0);
	free(hashes);
	hashes = NULL;
out:
	clear_rbtrees(t); /* TODO why are we doing that here? Seems odd */
	return ret;
}

static void set_dummy_contents(struct osl_table_description *desc)
{
	int i;
	struct osl_column_description *cd;

	for (i = 0; i < desc->num_columns; i++) {
		cd = get_column_description(desc, i);
		cd->compare_function = dummy_compare;
	}
}

static int fsck_init(struct osl_table_description *desc, struct osl_table **t)
{
	struct osl_object map;
	int version, ret = map_index(desc, &map);

	if (ret < 0)
		goto out;
	ret = read_table_desc(&map, desc); /* checks table version */
	if (ret < 0) {
		osl_munmap(map.data, map.size);
		goto out;
	}
	version = ret;
	set_dummy_contents(desc);
	ret = init_table_structure(desc, t);
	if (ret < 0) {
		osl_munmap(map.data, map.size);
		goto out;
	}
	(*t)->version = version;
	DEBUG_LOG("unmapping index\n");
	osl_munmap(map.data, map.size);
	if (OPT_GIVEN(FORCE))
		ret = map_table(*t, (MAP_TBL_FL_IGNORE_DIRTY));
	else
		ret = map_table(*t, 0);
	if (ret >= 0) {
		(*t)->num_rows = table_num_rows(*t);
		DEBUG_LOG("index header size: %d\n", (*t)->index_header_size);
		DEBUG_LOG("row index size: %d\n", (*t)->row_index_size);
	}
out:
	return ret;
}

static void fsck_cleanup(struct osl_table *t)
{
	int i;

	if (!t)
		return;
	if (t->desc->column_descriptions) {
		struct osl_column_description *cd;
		for (i = 0; i < t->desc->num_columns; i++) {
			cd = get_column_description(t->desc, i);
			free((char*)cd->name);
		}
		free(t->desc->column_descriptions);
	}
	free(t->columns);
	free(t);

}

#define ST_CASE(st) case st: return #st

static const char *get_asc_storage_type(enum osl_storage_type st)
{
	switch (st) {
		ST_CASE(OSL_MAPPED_STORAGE);
		ST_CASE(OSL_DISK_STORAGE);
		ST_CASE(OSL_NO_STORAGE);
	}
	return NULL;
}

#define APPEND_ASC_SF(sf, flag, str) do { if (sf & flag) { \
	if (str) str = make_message("%s%s", str, " | " # flag); \
	else str = fsck_strdup(#flag); }} while (0)


static char *get_asc_storage_flags(enum osl_storage_type sf)
{
	char *asc_sf = NULL;

	APPEND_ASC_SF(sf, OSL_RBTREE, asc_sf);
	APPEND_ASC_SF(sf, OSL_FIXED_SIZE, asc_sf);
	APPEND_ASC_SF(sf, OSL_UNIQUE, asc_sf);
	return asc_sf;
}

static int dump_table_desc(struct osl_table *t, int fd)
{
	const struct osl_table_description *desc = t->desc;
	int ret, i;
	struct osl_column_description *cd;
	char *msg = make_message("static struct osl_column_description cols[] = {\n");
	ret = _write_all(fd, msg, strlen(msg));
	if (ret < 0)
		return ret;
	free(msg);
	FOR_EACH_COLUMN(i, desc, cd) {
		const char *asc_st;
		msg = make_message("\t[%d] = {\n", i);
		ret = _write_all(fd, msg, strlen(msg));
		if (ret < 0)
			return ret;
		free(msg);
		asc_st = get_asc_storage_type(cd->storage_type);
		msg = make_message("\t\t.storage_type = %s,\n", asc_st);
		ret = _write_all(fd, msg, strlen(msg));
		if (ret < 0)
			return ret;
		free(msg);
		if (cd->storage_flags) {
			char *asc_sf = get_asc_storage_flags(cd->storage_flags);
			msg = make_message("\t\t,storage_flags = %s,\n", asc_sf);
			free(asc_sf);
			ret = _write_all(fd, msg, strlen(msg));
			if (ret < 0)
				return ret;
			free(msg);
		}
		if (cd->storage_flags & OSL_FIXED_SIZE) {
			msg = make_message("\t\t.data_size = %u,\n", cd->data_size);
			ret = _write_all(fd, msg, strlen(msg));
			if (ret < 0)
				return ret;
			free(msg);
		}
		msg = make_message("\t\t.name = \"%s\",\n", cd->name);
		ret = _write_all(fd, msg, strlen(msg));
		if (ret < 0)
			return ret;
		free(msg);
		if (cd->storage_flags & OSL_RBTREE) {
			msg = make_message("\t\t.compare_function = compare_func,\n");
			ret = _write_all(fd, msg, strlen(msg));
			if (ret < 0)
				return ret;
			free(msg);
		}
		msg = make_message("\t},\n");
		ret = _write_all(fd, msg, strlen(msg));
		if (ret < 0)
			return ret;
		free(msg);
	}
	msg = make_message("};\n");
	ret = _write_all(fd, msg, strlen(msg));
	if (ret < 0)
		return ret;
	free(msg);
	return 1;
}

static int dump_row(struct osl_table *t, unsigned row_num, const char *row_dir)
{
	int ret, i;
	const struct osl_column_description *cd;
	unsigned dsnc;
	struct osl_object obj;
	char *ds_name;
	HASH_TYPE hash[HASH_SIZE];
	char *filename;

	FOR_EACH_MAPPED_COLUMN(i, t, cd) {
		ret = get_mapped_object(t, i, row_num, &obj);
		if (ret < 0)
			return ret;
		filename = make_message("%s/col_%03u", row_dir, i);
		ret = write_file(filename, obj.data, obj.size);
		free(filename);
		if (ret < 0)
			return ret;
	}
	if (!t->num_disk_storage_columns)
		return 1;
	dsnc = t->disk_storage_name_column;
	ret = get_mapped_object(t, dsnc, row_num, &obj);
	if (ret < 0)
		return ret;
	hash_object(t, &obj, hash);
	ds_name = disk_storage_name_of_hash(t, hash);
	FOR_EACH_DISK_STORAGE_COLUMN(i, t, cd) {
		filename = disk_storage_path(t, i, ds_name);
		ret = mmap_full_file(filename, O_RDONLY, &obj.data, &obj.size, NULL);
		free(filename);
		if (ret < 0)
			goto out;
		filename = make_message("%s/col_%03u", row_dir, i);
		ret = write_file(filename, obj.data, obj.size);
		free(filename);
		if (ret < 0)
			goto out;
	}
	ret = 1;
out:
	free(ds_name);
	return ret;
}

static int dump_rows(char *dump_dir, struct osl_table *t)
{
	unsigned i;
	char *current_dir = NULL;
	int ret = 0;

	for (i = 0; i < t->num_rows; i++) {
		char *row_dir;
		if (row_is_invalid(t, i))
			continue;
		if (!(i % 1000)) {
			free(current_dir);
			current_dir = make_message("%s/rows_%u-%u", dump_dir, i, i + 999);
			NOTICE_LOG("dumping rows %u - %u\n", i, i + 999);
			ret = osl_mkdir(current_dir, 0777);
			if (ret < 0 && ret != -E_OSL_DIR_EXISTS)
				goto out;
		}
		row_dir = make_message("%s/row_%03u", current_dir, i);
		ret = osl_mkdir(row_dir, 0777);
		if (ret < 0 && ret != -E_OSL_DIR_EXISTS) {
			free(row_dir);
			goto out;
		}
		ret = dump_row(t, i, row_dir);
		free(row_dir);
		if (ret < 0)
			goto out;
	}
out:
	free(current_dir);
	return ret;
}

static int dump_table(const char *dump_dir, struct osl_table_description *desc)
{
	struct osl_table *t = NULL;
	int fd, ret = fsck_init(desc, &t);
	char *desc_file;
	char *table_dump_dir = NULL;

	if (ret < 0)
		goto out;
	ret = osl_mkdir(dump_dir, 0777);
	if (ret < 0 && ret != -E_OSL_DIR_EXISTS)
		goto out;
	table_dump_dir = make_message("%s/%s", dump_dir, desc->name);
	ret = osl_mkdir(table_dump_dir, 0777);
	if (ret < 0 && ret != -E_OSL_DIR_EXISTS)
		goto out;
	desc_file = make_message("%s/table_description.c", table_dump_dir);
	ret = osl_open(desc_file, O_WRONLY | O_CREAT | O_EXCL, 0644);
	free(desc_file);
	if (ret < 0)
		goto out;
	fd = ret;
	ret = dump_table_desc(t, fd);
	close(fd);
	if (ret < 0)
		goto out;
	ret = dump_rows(table_dump_dir, t);
out:
	free(table_dump_dir);
	fsck_cleanup(t);
	return ret;
}

static int fsck(struct osl_table_description *desc)
{
	int ret;
	struct osl_table *t = NULL;
	uint32_t *lost_bytes = NULL;

	ret = fsck_init(desc, &t);
	if (ret < 0)
		goto out;
	ret = check_index_ranges(t);
	if (ret < 0)
		goto out_unmap;
	ret = check_disk_storage_columns(t);
	if (ret < 0)
		goto out_unmap;
	ret = prune_invalid_rows_from_index(t);
	if (ret < 0)
		goto out_unmap;
	ret = check_for_invalid_objects(t, &lost_bytes);
	if (ret < 0)
		goto out_unmap;
	if (ret > 0 && !OPT_GIVEN(DRY_RUN)) {
		/* at least one mapped data file needs pruning */
		ret = prune_objects(t, lost_bytes);
		if (ret < 0)
			goto out_unmap;
	}
	free(lost_bytes);
out_unmap:
	unmap_table(t, OSL_MARK_CLEAN);
out:
	fsck_cleanup(t);
	return ret;
}

static int check_table(const char *db_dir, const char *table_name)
{
	struct osl_table_description desc = {
		.column_descriptions = NULL,
		.dir = db_dir,
		.name = table_name
	};
	int ret;

	INFO_LOG("checking table %s\n", table_name);
	if (!OPT_GIVEN(NO_FSCK)) {
		ret = fsck(&desc);
		if (ret < 0)
			goto out;
	}
	ret = 1;
	if (!OPT_GIVEN(DUMP_DIR) || !*OPT_STRING_VAL(DUMP_DIR))
		goto out;
	ret = dump_table(OPT_STRING_VAL(DUMP_DIR), &desc);
out:
	if (ret < 0)
		ERROR_LOG("failed to check table %s: %s\n", table_name,
			fsck_strerror(-ret));
	else
		NOTICE_LOG("successfully checked table %s\n", table_name);
	return ret;
}

static int check_all_tables(const char *db_dir)
{
	DIR *dir;
	struct dirent *entry;
	int cwd_fd, ret2, ret = fsck_opendir(db_dir, &dir, &cwd_fd);

	if (ret < 0)
		return ret;
	while ((entry = readdir(dir))) {
		mode_t m;
		struct stat s;
		if (!strcmp(entry->d_name, "."))
			continue;
		if (!strcmp(entry->d_name, ".."))
			continue;
		if (lstat(entry->d_name, &s) == -1)
			continue;
		m = s.st_mode;
		if (!S_ISDIR(m))
			continue;
		ret = check_table(db_dir, entry->d_name);
		if (ret < 0)
			break;
	}
	closedir(dir);
	ret2 = __fchdir(cwd_fd);
	if (ret2 < 0 && ret >= 0)
		ret = ret2;
	close(cwd_fd);
	return ret;
}

int main(int argc, char **argv)
{
	int ret;
	unsigned n;
	char *errctx = NULL;
	const char *dd;

	loglevel = 0;
	ret = lls_parse(argc, argv, CMD_PTR, &lpr, &errctx);
	if (ret < 0) {
		if (errctx)
			ERROR_LOG("%s\n", errctx);
		EMERG_LOG("%s\n", lls_strerror(-ret));
		exit(EXIT_FAILURE);
	}
	loglevel = OPT_UINT32_VAL(LOGLEVEL);
	if (OPT_GIVEN(DETAILED_HELP)) {
		printf("%s\n", lls_long_help(CMD_PTR));
		exit(EXIT_SUCCESS);
	}
	if (OPT_GIVEN(HELP)) {
		printf("%s\n", lls_short_help(CMD_PTR));
		exit(EXIT_SUCCESS);
	}
	if (OPT_GIVEN(VERSION)) {
		printf(
			"oslfsck " OSL_VERSION "\n"
			"Copyright (C) 2008-2009 Andre Noll\n"
			"This is free software with ABSOLUTELY NO WARRANTY."
			" See COPYING for details.\n"
			"Written by Andre Noll.\n"
			"Report bugs to <maan@tuebingen.mpg.de>.\n"
		);
		exit(EXIT_SUCCESS);
	}
	dd = OPT_STRING_VAL(DATABASE_DIR);
	if (!dd) {
		EMERG_LOG("--database-dir: mandatory option not given\n");
		exit(EXIT_FAILURE);
	}
	INFO_LOG("database dir: %s\n", dd);
	if (lls_num_inputs(lpr) == 0) {
		ret = check_all_tables(dd);
		goto out;
	}
	for (n = 0; n < lls_num_inputs(lpr); n++) {
		ret = check_table(dd, lls_input(n, lpr));
		if (ret < 0)
			break;
	}
out:
	if (ret < 0) {
		ERROR_LOG("%s\n", fsck_strerror(-ret));
		if (loglevel > 1)
			EMERG_LOG("re-run with \"--loglevel %d\" to increase verbosity\n",
				loglevel - 1);
	} else
		NOTICE_LOG("success\n");
	return ret < 0? EXIT_FAILURE : EXIT_SUCCESS;
}