snapraid/cmdline/elem.c

// SPDX-License-Identifier: GPL-3.0-or-later
// Copyright (C) 2011 Andrea Mazzoleni

#include "os/portable.h"

#include "elem.h"
#include "support.h"
#include "state.h"
#include "util.h"

/****************************************************************************/
/* snapraid */

size_t BLOCK_HASH_SIZE = HASH_MAX;

struct snapraid_content* content_alloc(const char* path, uint64_t dev)
{
	struct snapraid_content* content;

	content = malloc_nofail(sizeof(struct snapraid_content));
	pathimport(content->content, sizeof(content->content), path);
	content->device = dev;

	return content;
}

void content_free(void* void_content)
{
	struct snapraid_content* content = void_content;

	free(content);
}

/**
 * Check that all wildcard character classes are terminated.
 *
 * Escaped '[' characters are literals and don't start a class.
 * Escape characters inside a class are literals, consistently with
 * match_class().
 */
static int filter_pattern_class_valid(const char* pattern)
{
	const char* i;
	int in_class = 0;

	for (i = pattern; *i; ++i) {
		if (in_class) {
			if (*i == ']')
				in_class = 0;
		} else {
#ifdef _WIN32
			if (*i == '^' && i[1] != 0) {
#else
			if (*i == '\\' && i[1] != 0) {
#endif
				++i;
			} else if (*i == '[') {
				in_class = 1;
			}
		}
	}

	return !in_class;
}

struct snapraid_filter* filter_alloc_file(int direction, const char* root, const char* pattern)
{
	struct snapraid_filter* filter;
	char* i;
	char* first;
	char* last;
	int token_is_valid;
	int token_is_filled;
	int token_dot_count;

	filter = malloc_nofail(sizeof(struct snapraid_filter));
	pathimport(filter->pattern, sizeof(filter->pattern), pattern);
	pathimport(filter->root, sizeof(filter->root), root);
	filter->direction = direction;

	/* reject unterminated wildcard character classes */
	if (!filter_pattern_class_valid(filter->pattern)) {
		free(filter);
		return 0;
	}

	/* reject the root directory and standalone absolute directory wildcard as invalid patterns */
	if (pathcmp(filter->pattern, "/") == 0 || pathcmp(filter->pattern, "/**/") == 0) {
		free(filter);
		return 0;
	}

	/* find first and last slash */
	first = 0;
	last = 0;

	/* reject invalid tokens, like "<empty>", "." and ".." */
	token_is_valid = 0;
	token_is_filled = 0;
	token_dot_count = 0;
	for (i = filter->pattern; *i; ++i) {
		if (*i == '/') {
			/* reject invalid tokens, but accept an empty one as first */
			if (!token_is_valid && (first != 0 || token_is_filled)) {
				free(filter);
				return 0;
			}
			token_is_valid = 0;
			token_is_filled = 0;
			token_dot_count = 0;

			/* update slash position */
			if (!first)
				first = i;
			last = i;
		} else if (*i != '.') {
			token_is_valid = 1;
			token_is_filled = 1;
		} else {
			token_is_filled = 1;
			++token_dot_count;
			if (token_dot_count >= 3)
				token_is_valid = 1;
		}
	}

	/* reject invalid tokens, but accept an empty one as last, but not if it's the only one */
	if (!token_is_valid && (first == 0 || token_is_filled)) {
		free(filter);
		return 0;
	}

	/* it's a file filter */
	filter->is_disk = 0;

	if (first == 0) {
		/* no slash */
		filter->is_abs = 0;
		filter->is_dir = 0;
	} else {
		if (first == filter->pattern) {
			/* slash at the start */
			filter->is_abs = 1;
		} else {
			/* no slash at the start */
			filter->is_abs = 0;
		}
		if (last[1] == 0) {
			/* slash at the end */
			filter->is_dir = 1;
			last[0] = 0; /* clear the slash */
		} else {
			/* no slash at the end */
			filter->is_dir = 0;
		}
	}

	return filter;
}

struct snapraid_filter* filter_alloc_disk(int direction, const char* pattern)
{
	struct snapraid_filter* filter;

	filter = malloc_nofail(sizeof(struct snapraid_filter));
	pathimport(filter->pattern, sizeof(filter->pattern), pattern);
	filter->direction = direction;

	/* reject unterminated wildcard character classes */
	if (!filter_pattern_class_valid(filter->pattern)) {
		free(filter);
		return 0;
	}

	/* it's a disk filter */
	filter->is_disk = 1;
	filter->is_abs = 0;
	filter->is_dir = 0;

	/* no empty pattern or slash allowed in disk names */
	if (filter->pattern[0] == 0 || strchr(filter->pattern, '/') != 0) {
		/* LCOV_EXCL_START */
		free(filter);
		return 0;
		/* LCOV_EXCL_STOP */
	}

	return filter;
}

void filter_free(void* filter)
{
	free(filter);
}

const char* filter_type(struct snapraid_filter* filter, char* out, size_t out_size)
{
	const char* direction;

	if (filter->direction < 0)
		direction = "exclude";
	else
		direction = "include";

	if (filter->is_disk)
		pathprint(out, out_size, "%s %s:", direction, filter->pattern);
	else if (filter->is_dir)
		pathprint(out, out_size, "%s %s/", direction, filter->pattern);
	else
		pathprint(out, out_size, "%s %s", direction, filter->pattern);

	return out;
}

/**
 * Apply a filter to the specified path
 *
 * @param filter The filter to apply.
 * @param reason Assign to it the filter that caused rejection.
 * @param path The path to filter.
 * @param is_dir if the path refers to a directory, otherwise to a file.
 * @return < 0 if the path is excluded, > 0 if the path is included, 0 if the filter doesn't apply.
 */
static int filter_apply(struct snapraid_filter* filter, struct snapraid_filter** reason, const char* path, int is_dir)
{
	if (filter->root[0] != 0) { /* if it's a local filter */
		if (!path_is_root_of(filter->root, path)) /* applies it only if it matches the root */
			return 0;
		/* advance the path to compare to make it local */
		path += strlen(filter->root);
	}

	/* if the filter is for files, it doesn't applies to directories */
	if (!filter->is_dir && is_dir)
		return 0;

	/*
	 * If the filter is for directories, it should be applied to all files inside
	 * that directory.
	 *
	 * This is done allowing a partial matching as far it ends at a directory separator
	 */
	int match_sub = filter->is_dir;

	int ret = 0;

	if (filter->is_abs) {
		/* preserve the skipped slash because it gives an initial ** its recursive meaning */
		if (wnmatch_sub_prev(filter->pattern + 1, path, match_sub, '/') == 0
			|| (is_dir && wnmatch_sub_prev(filter->pattern + 1, path, 0, '/') == 0))
			ret = filter->direction;
	} else {
		/* the path is relative, first try to match from the root */
		if (wnmatch_sub(filter->pattern, path, match_sub) == 0
			|| (is_dir && wnmatch_sub(filter->pattern, path, 0) == 0)) {
			ret = filter->direction;
		} else {
			/* then try to match after all the / presents */
			const char* slash = strchr(path, '/');
			while (slash) {
				if (wnmatch_sub(filter->pattern, slash + 1, match_sub) == 0
					|| (is_dir && wnmatch_sub(filter->pattern, slash + 1, 0) == 0)) {
					ret = filter->direction;
					break;
				}

				slash = strchr(slash + 1, '/');
			}
		}
	}

	if (reason != 0 && ret < 0)
		*reason = filter;

	return ret;
}

/**
 * Apply a list of filter to a specific disk/sub path
 *
 * @param filterlist The list of filter to apply
 * @param reason Assign to it the filter that caused rejection.
 * @param disk The disk that contain the path
 * @param sub The path in the disk
 * @param is_dir If the path refers to a directory, otherwise it's a file
 * @param is_def_include If no filter apply, if by default force the inclusion. Used to include directory by default.
 * @return < 0 if the path is excluded, == 0 if the path is included.
 */

static int filter_element(tommy_list* filterlist, struct snapraid_filter** reason, const char* disk, const char* sub, int is_dir, int is_def_include)
{
	tommy_node* i;

	/*
	 * The rule is that the latest filter defines the behaviour of paths
	 * that doesn't match any filter.
	 *
	 * If the latest filter is an 'exclusion' filter, the default is to include.
	 * If the latest filter is an 'inclusion' filter, the default is to exclude.
	 * If there are no filter, the default is to include.
	 */
	int default_direction = 1;

	/* for each filter */
	for (i = tommy_list_head(filterlist); i != 0; i = i->next) {
		int ret;
		struct snapraid_filter* filter = i->data;

		if (filter->is_disk) {
			if (wnmatch(filter->pattern, disk) == 0) {
				ret = filter->direction;
			} else {
				ret = 0;
			}
			if (reason != 0 && ret < 0)
				*reason = filter;
		} else {
			ret = filter_apply(filter, reason, sub, is_dir);
		}

		if (ret > 0) {
			/* include the file */
			return 0;
		} else if (ret < 0) {
			/* exclude the file */
			return -1;
		} else {
			/* default is opposite of the last filter */
			default_direction = -filter->direction;
			if (reason != 0 && default_direction < 0)
				*reason = filter;
			/* continue with the next one */
		}
	}

	/*
	 * Directories are always included by default, otherwise we cannot apply rules
	 * to the contained files
	 */
	if (is_def_include)
		return 0;

	/* files are excluded/included depending of the last rule processed */
	if (default_direction < 0)
		return -1;

	return 0;
}

int filter_path(tommy_list* filterlist, struct snapraid_filter** reason, const char* disk, const char* sub)
{
	return filter_element(filterlist, reason, disk, sub, 0, 0);
}

int filter_subdir(tommy_list* filterlist, struct snapraid_filter** reason, const char* disk, const char* sub)
{
	return filter_element(filterlist, reason, disk, sub, 1, 1);
}

int filter_emptydir(tommy_list* filterlist, struct snapraid_filter** reason, const char* disk, const char* sub)
{
	return filter_element(filterlist, reason, disk, sub, 1, 0);
}

int filter_existence(int filter_missing, const char* dir, const char* sub)
{
	char path[PATH_MAX];
	struct stat st;

	if (!filter_missing)
		return 0;

	/* we directly check if in the disk the file is present or not */
	pathprint(path, sizeof(path), "%s%s", dir, sub);

	if (lstat(path, &st) != 0) {
		/* if the file doesn't exist, we don't filter it out */
		if (errno == ENOENT || errno == ENOTDIR)
			return 0;
		/* LCOV_EXCL_START */
		log_fatal(errno, "Error in stat file '%s'. %s.\n", path, strerror(errno));
		exit(EXIT_FAILURE);
		/* LCOV_EXCL_STOP */
	}

	/* the file is present, so we filter it out */
	return 1;
}

int filter_correctness(int filter_error, tommy_arrayblkof* infoarr, struct snapraid_disk* disk, struct snapraid_file* file)
{
	block_off_t i;

	if (!filter_error)
		return 0;

	/* check each block of the file */
	for (i = 0; i < file->blockmax; ++i) {
		block_off_t parity_pos = fs_file2par_get(disk, file, i);
		snapraid_info info = info_get(infoarr, parity_pos);

		/* if the file has a bad block, don't exclude it */
		if (info_get_bad(info))
			return 0;
	}

	/* the file is correct, so we filter it out */
	return 1;
}

int filter_content(tommy_list* contentlist, const char* mount_point, size_t mount_point_len, const char* sub, size_t sub_len, const char* name)
{
	tommy_node* i;

	size_t name_len = strlen(name);

	for (i = tommy_list_head(contentlist); i != 0; i = i->next) {
		struct snapraid_content* content = i->data;
		const char* content_name;
		size_t content_name_len;
		const char* postfix;

		/* if the mount point doesn't match, it's a different disk */
		if (pathncmp(content->content, mount_point, mount_point_len) != 0)
			continue;

		/* if the sub dir doesn't match, it's a different dir */
		if (pathncmp(content->content + mount_point_len, sub, sub_len) != 0)
			continue;

		/* configured content filename in this directory */
		content_name = content->content + mount_point_len + sub_len;
		content_name_len = strlen(content_name);

		/* the scanned name must contain at least the complete configured content filename */
		if (name_len < content_name_len)
			continue;

		/* if the configured content filename doesn't match, it's a different name */
		if (pathncmp(name, content_name, content_name_len) != 0)
			continue;

		/* remaining part of the scanned name */
		postfix = name + content_name_len;

		/* if it's an exact match */
		if (*postfix == 0)
			return -1;

		/* exclude also the ".tmp" copy used to save it */
		if (pathcmp(postfix, ".tmp") == 0)
			return -1;

		/* exclude also the ".lock" file */
		if (pathcmp(postfix, ".lock") == 0)
			return -1;
	}

	return 0;
}

int filter_snapshot(int enable, const char* sub, const char* name)
{
	if (!enable)
		return 0;

	if (*sub == 0 && pathcmp(name, SNAPSHOT_CONTAINER) == 0)
		return -1;

	return 0;
}

struct snapraid_file* file_alloc_len(unsigned block_size, const char* sub, size_t sub_len, data_off_t size, uint64_t mtime_sec, int mtime_nsec, uint64_t inode)
{
	struct snapraid_file* file;
	block_off_t blockmax;

	blockmax = size / block_size;
	if (size % block_size != 0)
		++blockmax;

	if (blockmax > BLOCK_MAX) {
#if SIZE_MAX == UINT32_MAX
		log_fatal(ESOFT, "File '%s' with %" PRIu64 " blocks is too large for a 32-bit build. Use a 64-bit build or increase the block size.\n", sub, blockmax);
#else
		log_fatal(ESOFT, "File '%s' with %" PRIu64 " blocks is too large. Increase the block size.\n", sub, blockmax);
#endif
		exit(EXIT_FAILURE);
	}

	file = malloc_nofail(sizeof(struct snapraid_file) + sub_len + 1);
	file->sub = file->sub_inline;
	memcpy(file->sub, sub, sub_len);
	file->sub[sub_len] = 0;
	file->size = size;
	file->blockmax = blockmax;
	file->mtime_sec = mtime_sec;
	file->mtime_nsec = mtime_nsec;
	file->inode = inode;
	file->flag = 0;
	file->blockvec = nalloc_nofail(file->blockmax, block_sizeof());

	return file;
}

struct snapraid_file* file_dup(struct snapraid_file* copy)
{
	struct snapraid_file* file;
	block_off_t i;
	size_t sub_len;

	if (copy->blockmax > BLOCK_MAX) {
#if SIZE_MAX == UINT32_MAX
		log_fatal(ESOFT, "File '%s' with %" PRIu64 " blocks is too large for a 32-bit build. Use a 64-bit build or increase the block size.\n", copy->sub, copy->blockmax);
#else
		log_fatal(ESOFT, "File '%s' with %" PRIu64 " blocks is too large. Increase the block size.\n", copy->sub, copy->blockmax);
#endif
		exit(EXIT_FAILURE);
	}

	sub_len = strlen(copy->sub);
	file = malloc_nofail(sizeof(struct snapraid_file) + sub_len + 1);
	file->sub = file->sub_inline;
	memcpy(file->sub, copy->sub, sub_len);
	file->sub[sub_len] = 0;
	file->size = copy->size;
	file->blockmax = copy->blockmax;
	file->mtime_sec = copy->mtime_sec;
	file->mtime_nsec = copy->mtime_nsec;
	file->inode = copy->inode;
	file->flag = copy->flag;
	file->blockvec = nalloc_nofail(file->blockmax, block_sizeof());

	for (i = 0; i < file->blockmax; ++i) {
		struct snapraid_block* block = file_block(file, i);
		struct snapraid_block* copy_block = file_block(copy, i);
		block->state = copy_block->state;
		hash_copy(block->hash, copy_block->hash);
	}

	return file;
}

void file_free(void* void_file)
{
	struct snapraid_file* file = void_file;

	if (file->sub != file->sub_inline)
		free(file->sub);
	file->sub = 0;
	free(file->blockvec);
	file->blockvec = 0;
	free(file);
}

void file_rename(struct snapraid_file* file, const char* sub)
{
	if (file->sub != file->sub_inline)
		free(file->sub);

	file->sub = strdup_nofail(sub);
}

void file_copy(struct snapraid_file* src_file, struct snapraid_file* dst_file)
{
	block_off_t i;

	if (src_file->size != dst_file->size) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Copy file with different size\n");
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	if (src_file->mtime_sec != dst_file->mtime_sec) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Copy file with different mtime_sec\n");
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	if (src_file->mtime_nsec != dst_file->mtime_nsec) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Copy file with different mtime_nsec\n");
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	for (i = 0; i < dst_file->blockmax; ++i) {
		/* set a block with hash computed but without parity */
		block_state_set(file_block(dst_file, i), BLOCK_STATE_REP);

		/* copy the hash */
		hash_copy(file_block(dst_file, i)->hash, file_block(src_file, i)->hash);
	}

	file_flag_set(dst_file, FILE_IS_COPY);
}

const char* file_name(const struct snapraid_file* file)
{
	const char* r = strrchr(file->sub, '/');

	if (!r)
		r = file->sub;
	else
		++r;
	return r;
}

size_t file_block_size(struct snapraid_file* file, block_off_t file_pos, size_t block_size)
{
	/* if it's the last block */
	if (file_pos + 1 == file->blockmax) {
		size_t block_remainder;
		if (file->size == 0)
			return 0;
		block_remainder = file->size % block_size;
		if (block_remainder == 0)
			block_remainder = block_size;
		return block_remainder;
	}

	return block_size;
}

int file_block_is_last(struct snapraid_file* file, block_off_t file_pos)
{
	if (file_pos == 0 && file->blockmax == 0)
		return 1;

	if (file_pos >= file->blockmax) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: File block position over the max\n");
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	return file_pos == file->blockmax - 1;
}

int file_inode_compare_to_arg(const void* void_arg, const void* void_data)
{
	const uint64_t* arg = void_arg;
	const struct snapraid_file* file = void_data;

	if (*arg < file->inode)
		return -1;
	if (*arg > file->inode)
		return 1;
	return 0;
}

int file_inode_compare(const void* void_a, const void* void_b)
{
	const struct snapraid_file* file_a = void_a;
	const struct snapraid_file* file_b = void_b;

	if (file_a->inode < file_b->inode)
		return -1;
	if (file_a->inode > file_b->inode)
		return 1;
	return 0;
}

int file_path_compare(const void* void_a, const void* void_b)
{
	const struct snapraid_file* file_a = void_a;
	const struct snapraid_file* file_b = void_b;

	return strcmp(file_a->sub, file_b->sub);
}

int file_path_compare_to_arg(const void* void_arg, const void* void_data)
{
	const char* arg = void_arg;
	const struct snapraid_file* file = void_data;

	return strcmp(arg, file->sub);
}

int file_name_compare(const void* void_a, const void* void_b)
{
	const struct snapraid_file* file_a = void_a;
	const struct snapraid_file* file_b = void_b;
	const char* name_a = file_name(file_a);
	const char* name_b = file_name(file_b);

	return strcmp(name_a, name_b);
}

int file_stamp_compare(const void* void_a, const void* void_b)
{
	const struct snapraid_file* file_a = void_a;
	const struct snapraid_file* file_b = void_b;

	if (file_a->size < file_b->size)
		return -1;
	if (file_a->size > file_b->size)
		return 1;

	if (file_a->mtime_sec < file_b->mtime_sec)
		return -1;
	if (file_a->mtime_sec > file_b->mtime_sec)
		return 1;

	if (file_a->mtime_nsec < file_b->mtime_nsec)
		return -1;
	if (file_a->mtime_nsec > file_b->mtime_nsec)
		return 1;

	return 0;
}

int file_namestamp_compare(const void* void_a, const void* void_b)
{
	int ret;

	ret = file_name_compare(void_a, void_b);
	if (ret != 0)
		return ret;

	return file_stamp_compare(void_a, void_b);
}

int file_pathstamp_compare(const void* void_a, const void* void_b)
{
	int ret;

	ret = file_path_compare(void_a, void_b);
	if (ret != 0)
		return ret;

	return file_stamp_compare(void_a, void_b);
}

struct snapraid_extent* extent_alloc(block_off_t parity_pos, struct snapraid_file* file, block_off_t file_pos, block_off_t count)
{
	struct snapraid_extent* extent;

	if (count == 0) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Allocating empty extent for file '%s' at position '%" PRIu64 "/%" PRIu64 "'\n", file->sub, file_pos, file->blockmax);
		os_abort();
		/* LCOV_EXCL_STOP */
	}
	if (count > file->blockmax || file_pos > file->blockmax - count) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Allocating overflowing extent for file '%s' at position '%" PRIu64 ":%" PRIu64 "/%" PRIu64 "'\n", file->sub, file_pos, count, file->blockmax);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	extent = malloc_nofail(sizeof(struct snapraid_extent));
	extent->parity_pos = parity_pos;
	extent->file = file;
	extent->file_pos = file_pos;
	extent->count = count;

	return extent;
}

void extent_free(void* void_extent)
{
	struct snapraid_extent* extent = void_extent;

	free(extent);
}

__aligned(32)
int extent_parity_compare(const void* void_a, const void* void_b)
{
	const struct snapraid_extent* arg_a = void_a;
	const struct snapraid_extent* arg_b = void_b;

	if (arg_a->parity_pos < arg_b->parity_pos)
		return -1;
	if (arg_a->parity_pos > arg_b->parity_pos)
		return 1;

	return 0;
}

__aligned(32)
int extent_file_compare(const void* void_a, const void* void_b)
{
	const struct snapraid_extent* arg_a = void_a;
	const struct snapraid_extent* arg_b = void_b;
	uintptr_t file_a = (uintptr_t)arg_a->file;
	uintptr_t file_b = (uintptr_t)arg_b->file;

	/* cast to uintptr_t to avoid undefined behavior when comparing pointers to distinct heap allocations */
	if (file_a < file_b)
		return -1;
	if (file_a > file_b)
		return 1;

	if (arg_a->file_pos < arg_b->file_pos)
		return -1;
	if (arg_a->file_pos > arg_b->file_pos)
		return 1;

	return 0;
}

struct snapraid_link* link_alloc_len(const char* sub, size_t sub_len, const char* linkto, size_t linkto_len, unsigned link_flag)
{
	struct snapraid_link* slink;

	slink = malloc_nofail(sizeof(struct snapraid_link));
	slink->sub = strndup_nofail(sub, sub_len);
	slink->linkto = strndup_nofail(linkto, linkto_len);
	slink->flag = link_flag;

	return slink;
}

void link_free(void* void_link)
{
	struct snapraid_link* slink = void_link;

	free(slink->sub);
	free(slink->linkto);
	free(slink);
}

int link_name_compare_to_arg(const void* void_arg, const void* void_data)
{
	const char* arg = void_arg;
	const struct snapraid_link* slink = void_data;

	return strcmp(arg, slink->sub);
}

int link_alpha_compare(const void* void_a, const void* void_b)
{
	const struct snapraid_link* slink_a = void_a;
	const struct snapraid_link* slink_b = void_b;

	return strcmp(slink_a->sub, slink_b->sub);
}

struct snapraid_dir* dir_alloc_len(const char* sub, size_t sub_len)
{
	struct snapraid_dir* dir;

	dir = malloc_nofail(sizeof(struct snapraid_dir));
	dir->sub = strndup_nofail(sub, sub_len);
	dir->flag = 0;

	return dir;
}

void dir_free(void* void_dir)
{
	struct snapraid_dir* dir = void_dir;

	free(dir->sub);
	free(dir);
}

int dir_name_compare(const void* void_arg, const void* void_data)
{
	const char* arg = void_arg;
	const struct snapraid_dir* dir = void_data;

	return strcmp(arg, dir->sub);
}

struct snapraid_dealloc* dealloc_alloc_len(unsigned block_size, const char* sub, size_t sub_len, data_off_t size, int64_t mtime_sec, int32_t mtime_nsec)
{
	struct snapraid_dealloc* dealloc;
	block_off_t blockmax;

	blockmax = size / block_size;
	if (size % block_size != 0)
		++blockmax;

	if (blockmax > BLOCK_MAX) {
#if SIZE_MAX == UINT32_MAX
		log_fatal(ESOFT, "File '%s' with %" PRIu64 " blocks is too large for a 32-bit build. Use a 64-bit build or increase the block size.\n", sub, blockmax);
#else
		log_fatal(ESOFT, "File '%s' with %" PRIu64 " blocks is too large. Increase the block size.\n", sub, blockmax);
#endif
		exit(EXIT_FAILURE);
	}

	dealloc = malloc_nofail(sizeof(struct snapraid_dealloc) + blockmax * sizeof(struct snapraid_dealloc_block));
	dealloc->sub = strndup_nofail(sub, sub_len);
	dealloc->size = size;
	dealloc->mtime_sec = mtime_sec;
	dealloc->mtime_nsec = mtime_nsec;
	dealloc->blockmax = blockmax;

	return dealloc;
}

void dealloc_import(tommy_arrayblkof* infoarr, struct snapraid_disk* disk, struct snapraid_dealloc* dealloc, struct snapraid_file* file)
{
	assert(dealloc->blockmax == file->blockmax);

	/* for all the blocks of the file */
	for (block_off_t i = 0; i < dealloc->blockmax; ++i) {
		struct snapraid_block* block = fs_file2block_get(file, i);
		struct snapraid_dealloc_block* dealloc_block = &dealloc->block[i];
		unsigned block_state = block_state_get(block);

		switch (block_state) {
		case BLOCK_STATE_BLK :
		case BLOCK_STATE_REP :
		case BLOCK_STATE_REBUILD : {
			block_off_t parity_pos = fs_file2par_find(disk, file, i);
			snapraid_info info;

			if (parity_pos == POS_NULL) {
				/* LCOV_EXCL_START */
				log_fatal(EINTERNAL, "Internal inconsistency: Missing parity position for dealloc block %" PRIu64 "\n", i);
				os_abort();
				/* LCOV_EXCL_STOP */
			}

			info = info_get(infoarr, parity_pos);
			dealloc_block->prev = info_get_rehash(info);
			hash_copy(dealloc_block->hash, block->hash);
			break;
		}
		case BLOCK_STATE_CHG :
			dealloc_block->prev = 0;
			hash_invalid_set(dealloc_block->hash);
			break;
		default :
			/* LCOV_EXCL_START */
			log_fatal(EINTERNAL, "Internal inconsistency: State for dealloc block %" PRIu64 " state %u\n", i, block_state);
			os_abort();
			/* LCOV_EXCL_STOP */
		}
	}
}

void dealloc_free(void* void_dealloc)
{
	struct snapraid_dealloc* dealloc = void_dealloc;

	free(dealloc->sub);
	free(dealloc);
}

struct snapraid_disk* disk_alloc(const char* name, const char* dir, uint64_t dev, const char* uuid, int skip_access)
{
	struct snapraid_disk* disk;
	unsigned i;

	disk = malloc_nofail(sizeof(struct snapraid_disk));
	pathcpy(disk->name, sizeof(disk->name), name);
	pathimport(disk->mount_point, sizeof(disk->mount_point), dir);
	pathcpy(disk->uuid, sizeof(disk->uuid), uuid);

	/* ensure that the dir terminate with "/" if it isn't empty */
	pathslash(disk->mount_point, sizeof(disk->mount_point));

	/* no snapshot by default */
	memset(&disk->fss, 0, sizeof(disk->fss));
	pathcpy(disk->dir, sizeof(disk->dir), disk->mount_point);

#if HAVE_THREAD
	disk->single_thread = 0;
	thread_mutex_init(&disk->fs_mutex);
#endif

	disk->smartctl[0] = 0;
	disk->smartctl_info[0] = 0;
	for (i = 0; i < SMART_IGNORE_MAX; ++i) {
		disk->smartignore[i].attr_index = 0;
		disk->smartignore[i].attr_name[0] = 0;
	}
	disk->fstype[0] = 0;
	disk->fslabel[0] = 0;
	disk->mount_device = dev;
	disk->tick = 0;
	disk->cached_blocks = 0;
	disk->progress_file = 0;
	disk->total_blocks = 0;
	disk->free_blocks = 0;
	disk->first_free_block = 0;
	disk->has_volatile_inodes = 0;
	disk->has_volatile_hardlinks = 0;
	disk->has_different_uuid = 0;
	disk->has_unsupported_uuid = *uuid == 0; /* empty UUID means unsupported */
	disk->had_empty_uuid = 0;
	disk->mapping_idx = -1;
	disk->skip_access = skip_access;
	tommy_list_init(&disk->filelist);
	tommy_list_init(&disk->deletedlist);
	tommy_hashdyn_init(&disk->inodeset);
	tommy_hashdyn_init(&disk->pathset);
	tommy_hashdyn_init(&disk->stampset);
	tommy_list_init(&disk->linklist);
	tommy_hashdyn_init(&disk->linkset);
	tommy_list_init(&disk->dirlist);
	tommy_hashdyn_init(&disk->dirset);
	tommy_list_init(&disk->dealloclist);
	tommy_tree_init(&disk->fs_parity, extent_parity_compare);
	tommy_tree_init(&disk->fs_file, extent_file_compare);
	disk->fs_last = 0;

	return disk;
}

void disk_free(void* void_disk)
{
	struct snapraid_disk* disk = void_disk;

	tommy_list_foreach(&disk->filelist, file_free);
	tommy_list_foreach(&disk->deletedlist, file_free);
	tommy_tree_foreach(&disk->fs_file, extent_free);
	tommy_hashdyn_done(&disk->inodeset);
	tommy_hashdyn_done(&disk->pathset);
	tommy_hashdyn_done(&disk->stampset);
	tommy_list_foreach(&disk->linklist, link_free);
	tommy_hashdyn_done(&disk->linkset);
	tommy_list_foreach(&disk->dirlist, dir_free);
	tommy_hashdyn_done(&disk->dirset);
	tommy_list_foreach(&disk->dealloclist, dealloc_free);

#if HAVE_THREAD
	thread_mutex_destroy(&disk->fs_mutex);
#endif

	free(disk);
}

struct snapraid_extra* extra_alloc(const char* name, const char* dir, uint64_t dev, const char* uuid)
{
	struct snapraid_extra* extra;
	unsigned i;

	extra = malloc_nofail(sizeof(struct snapraid_extra));
	pathcpy(extra->name, sizeof(extra->name), name);
	pathimport(extra->dir, sizeof(extra->dir), dir);
	pathcpy(extra->uuid, sizeof(extra->uuid), uuid);

	/* ensure that the dir terminate with "/" if it isn't empty */
	pathslash(extra->dir, sizeof(extra->dir));

	extra->smartctl[0] = 0;
	extra->smartctl_info[0] = 0;
	for (i = 0; i < SMART_IGNORE_MAX; ++i) {
		extra->smartignore[i].attr_index = 0;
		extra->smartignore[i].attr_name[0] = 0;
	}
	extra->fstype[0] = 0;
	extra->fslabel[0] = 0;
	extra->device = dev;

	return extra;
}

void extra_free(void* void_extra)
{
	struct snapraid_extra* extra = void_extra;

	free(extra);
}

static inline void fs_lock(struct snapraid_disk* disk)
{
#if HAVE_THREAD
	if (!disk->single_thread)
		thread_mutex_lock(&disk->fs_mutex);
#else
	(void)disk;
#endif
}

static inline void fs_unlock(struct snapraid_disk* disk)
{
#if HAVE_THREAD
	if (!disk->single_thread)
		thread_mutex_unlock(&disk->fs_mutex);
#else
	(void)disk;
#endif
}

struct extent_disk_empty {
	block_off_t blockmax;
};

/**
 * Compare the extent if inside the specified blockmax.
 */
static int extent_disk_empty_compare_unlock(const void* void_a, const void* void_b)
{
	const struct extent_disk_empty* arg_a = void_a;
	const struct snapraid_extent* arg_b = void_b;

	/* if the block is inside the specified blockmax, it's found */
	if (arg_a->blockmax > arg_b->parity_pos)
		return 0;

	/* otherwise search for a smaller one */
	return -1;
}

int fs_is_empty(struct snapraid_disk* disk, block_off_t blockmax)
{
	struct extent_disk_empty arg = { blockmax };

	/*
	 * If there is an element, it's not empty
	 * even if links and dirs have no block allocation
	 */
	if (!tommy_list_empty(&disk->filelist))
		return 0;
	if (!tommy_list_empty(&disk->linklist))
		return 0;
	if (!tommy_list_empty(&disk->dirlist))
		return 0;
	if (!tommy_list_empty(&disk->dealloclist))
		return 0;

	fs_lock(disk);

	/* search for any extent inside blockmax */
	if (tommy_tree_search_compare(&disk->fs_parity, extent_disk_empty_compare_unlock, &arg) != 0) {
		fs_unlock(disk);
		return 0;
	}

	/* finally, it's empty */
	fs_unlock(disk);
	return 1;
}

struct extent_disk_size {
	block_off_t size;
};

/**
 * Compare the extent by highest parity position.
 *
 * The maximum parity position is stored as size.
 */
static int extent_disk_size_compare_unlock(const void* void_a, const void* void_b)
{
	struct extent_disk_size* arg_a = (void*)void_a;
	const struct snapraid_extent* arg_b = void_b;

	/* get the maximum size */
	if (arg_a->size < arg_b->parity_pos + arg_b->count)
		arg_a->size = arg_b->parity_pos + arg_b->count;

	/* search always for a bigger one */
	return 1;
}

block_off_t fs_size(struct snapraid_disk* disk)
{
	struct extent_disk_size arg = { 0 };

	fs_lock(disk);

	tommy_tree_search_compare(&disk->fs_parity, extent_disk_size_compare_unlock, &arg);

	fs_unlock(disk);

	return arg.size;
}

struct extent_check {
	const struct snapraid_extent* prev;
	int result;
};

static void extent_parity_check_foreach_unlock(void* void_arg, void* void_obj)
{
	struct extent_check* arg = void_arg;
	const struct snapraid_extent* obj = void_obj;
	const struct snapraid_extent* prev = arg->prev;

	/* set the next previous block */
	arg->prev = obj;

	/* stop reporting if too many errors */
	if (arg->result > 100) {
		/* LCOV_EXCL_START */
		return;
		/* LCOV_EXCL_STOP */
	}

	if (obj->count == 0) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Parity count zero for file '%s' at '%" PRIu64 "'\n",
			obj->file->sub, obj->parity_pos);
		++arg->result;
		return;
		/* LCOV_EXCL_STOP */
	}

	/* check only if there is a previous block */
	if (!prev)
		return;

	/* check the order */
	if (prev->parity_pos >= obj->parity_pos) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Parity order for files '%s' at '%" PRIu64 ":%" PRIu64 "' and '%s' at '%" PRIu64 ":%" PRIu64 "'\n",
			prev->file->sub, prev->parity_pos, prev->count, obj->file->sub, obj->parity_pos, obj->count);
		++arg->result;
		return;
		/* LCOV_EXCL_STOP */
	}

	/* check that the extents don't overlap */
	if (obj->parity_pos - prev->parity_pos < prev->count) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Parity overlap for files '%s' at '%" PRIu64 ":%" PRIu64 "' and '%s' at '%" PRIu64 ":%" PRIu64 "'\n",
			prev->file->sub, prev->parity_pos, prev->count, obj->file->sub, obj->parity_pos, obj->count);
		++arg->result;
		return;
		/* LCOV_EXCL_STOP */
	}
}

static void extent_file_check_end_unlock(struct extent_check* arg, const struct snapraid_extent* prev)
{
	/* stop reporting if too many errors */
	if (arg->result > 100) {
		/* LCOV_EXCL_START */
		return;
		/* LCOV_EXCL_STOP */
	}

	if (file_flag_has(prev->file, FILE_IS_DELETED)) {
		/* check that the extent doesn't overflow the file */
		if (prev->count > prev->file->blockmax || prev->file_pos > prev->file->blockmax - prev->count) {
			/* LCOV_EXCL_START */
			log_fatal(EINTERNAL, "Internal inconsistency: Delete end for file '%s' at '%" PRIu64 ":%" PRIu64 "' overflowing size '%" PRIu64 "'\n",
				prev->file->sub, prev->file_pos, prev->count, prev->file->blockmax);
			++arg->result;
			return;
			/* LCOV_EXCL_STOP */
		}
	} else {
		/* check that the extent ends the file */
		if (prev->file_pos + prev->count != prev->file->blockmax) {
			/* LCOV_EXCL_START */
			log_fatal(EINTERNAL, "Internal inconsistency: File end for file '%s' at '%" PRIu64 ":%" PRIu64 "' instead of size '%" PRIu64 "'\n",
				prev->file->sub, prev->file_pos, prev->count, prev->file->blockmax);
			++arg->result;
			return;
			/* LCOV_EXCL_STOP */
		}
	}
}

static void extent_file_check_foreach_unlock(void* void_arg, void* void_obj)
{
	struct extent_check* arg = void_arg;
	const struct snapraid_extent* obj = void_obj;
	const struct snapraid_extent* prev = arg->prev;

	/* set the next previous block */
	arg->prev = obj;

	/* stop reporting if too many errors */
	if (arg->result > 100) {
		/* LCOV_EXCL_START */
		return;
		/* LCOV_EXCL_STOP */
	}

	if (obj->count == 0) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: File count zero for file '%s' at '%" PRIu64 "'\n",
			obj->file->sub, obj->file_pos);
		++arg->result;
		return;
		/* LCOV_EXCL_STOP */
	}

	/* note that for deleted files, some extents may be missing */

	/* if the files are different */
	if (!prev || prev->file != obj->file) {
		if (prev != 0)
			extent_file_check_end_unlock(arg, prev);

		if (file_flag_has(obj->file, FILE_IS_DELETED)) {
			/* check that the extent doesn't overflow the file */
			if (obj->count > obj->file->blockmax || obj->file_pos > obj->file->blockmax - obj->count) {
				/* LCOV_EXCL_START */
				log_fatal(EINTERNAL, "Internal inconsistency: Delete start for file '%s' at '%" PRIu64 ":%" PRIu64 "' overflowing size '%" PRIu64 "'\n",
					obj->file->sub, obj->file_pos, obj->count, obj->file->blockmax);
				++arg->result;
				return;
				/* LCOV_EXCL_STOP */
			}
		} else {
			/* check that the extent starts the file */
			if (obj->file_pos != 0) {
				/* LCOV_EXCL_START */
				log_fatal(EINTERNAL, "Internal inconsistency: File start for file '%s' at '%" PRIu64 ":%" PRIu64 "'\n",
					obj->file->sub, obj->file_pos, obj->count);
				++arg->result;
				return;
				/* LCOV_EXCL_STOP */
			}
		}
	} else {
		/* check the order */
		if (prev->file_pos >= obj->file_pos) {
			/* LCOV_EXCL_START */
			log_fatal(EINTERNAL, "Internal inconsistency: File order for file '%s' at '%" PRIu64 ":%" PRIu64 "' and at '%" PRIu64 ":%" PRIu64 "'\n",
				prev->file->sub, prev->file_pos, prev->count, obj->file_pos, obj->count);
			++arg->result;
			return;
			/* LCOV_EXCL_STOP */
		}

		if (file_flag_has(obj->file, FILE_IS_DELETED)) {
			/* check that the extents don't overlap */
			if (obj->file_pos - prev->file_pos < prev->count) {
				/* LCOV_EXCL_START */
				log_fatal(EINTERNAL, "Internal inconsistency: Delete sequence for file '%s' at '%" PRIu64 ":%" PRIu64 "' and at '%" PRIu64 ":%" PRIu64 "'\n",
					prev->file->sub, prev->file_pos, prev->count, obj->file_pos, obj->count);
				++arg->result;
				return;
				/* LCOV_EXCL_STOP */
			}
		} else {
			/* check that the extents are sequential */
			if (prev->file_pos + prev->count != obj->file_pos) {
				/* LCOV_EXCL_START */
				log_fatal(EINTERNAL, "Internal inconsistency: File sequence for file '%s' at '%" PRIu64 ":%" PRIu64 "' and at '%" PRIu64 ":%" PRIu64 "'\n",
					prev->file->sub, prev->file_pos, prev->count, obj->file_pos, obj->count);
				++arg->result;
				return;
				/* LCOV_EXCL_STOP */
			}
		}
	}
}

int fs_check(struct snapraid_disk* disk)
{
	struct extent_check arg;

	/* error count starts from 0 */
	arg.result = 0;

	fs_lock(disk);

	/* check parity sequence */
	arg.prev = 0;
	tommy_tree_foreach_arg(&disk->fs_parity, extent_parity_check_foreach_unlock, &arg);

	/* check file sequence */
	arg.prev = 0;
	tommy_tree_foreach_arg(&disk->fs_file, extent_file_check_foreach_unlock, &arg);
	if (arg.prev != 0)
		extent_file_check_end_unlock(&arg, arg.prev);

	fs_unlock(disk);

	if (arg.result != 0)
		return -1;

	return 0;
}

struct extent_parity_inside {
	block_off_t parity_pos;
};

/**
 * Compare the extent if containing the specified parity position.
 */
static int extent_parity_inside_compare_unlock(const void* void_a, const void* void_b)
{
	const struct extent_parity_inside* arg_a = void_a;
	const struct snapraid_extent* arg_b = void_b;

	if (arg_a->parity_pos < arg_b->parity_pos)
		return -1;
	if (arg_a->parity_pos - arg_b->parity_pos >= arg_b->count)
		return 1;

	return 0;
}

struct snapraid_extent* fs_par2extent_find_next(struct snapraid_disk* disk, block_off_t parity_pos)
{
	struct extent_parity_inside arg = { parity_pos };
	struct snapraid_extent* extent;

	fs_lock(disk);

	/* non-overlapping extents let this search find the containing extent or the next one */
	extent = tommy_tree_search_greater_equal_compare(&disk->fs_parity, extent_parity_inside_compare_unlock, &arg);

	fs_unlock(disk);
	return extent;
}

/**
 * Search the extent at the specified parity position.
 * The search is optimized for sequential accesses.
 * \return If not found return 0
 */
static struct snapraid_extent* fs_par2extent_get_unlock(struct snapraid_disk* disk, struct snapraid_extent** fs_last, block_off_t parity_pos)
{
	struct snapraid_extent* extent;

	/* check if the last accessed extent matches */
	if (*fs_last
		&& parity_pos >= (*fs_last)->parity_pos
		&& parity_pos - (*fs_last)->parity_pos < (*fs_last)->count
	) {
		extent = *fs_last;
	} else {
		struct extent_parity_inside arg = { parity_pos };
		extent = tommy_tree_search_compare(&disk->fs_parity, extent_parity_inside_compare_unlock, &arg);
	}

	if (!extent)
		return 0;

	/* store the last accessed extent */
	*fs_last = extent;

	return extent;
}

struct extent_file_inside {
	struct snapraid_file* file;
	block_off_t file_pos;
};

/**
 * Compare the extent if containing the specified file position.
 */
static int extent_file_inside_compare_unlock(const void* void_a, const void* void_b)
{
	const struct extent_file_inside* arg_a = void_a;
	const struct snapraid_extent* arg_b = void_b;
	uintptr_t file_a = (uintptr_t)arg_a->file;
	uintptr_t file_b = (uintptr_t)arg_b->file;

	/* cast to uintptr_t to avoid undefined behavior when comparing pointers to distinct heap allocations */
	if (file_a < file_b)
		return -1;
	if (file_a > file_b)
		return 1;

	if (arg_a->file_pos < arg_b->file_pos)
		return -1;
	if (arg_a->file_pos - arg_b->file_pos >= arg_b->count)
		return 1;

	return 0;
}

/**
 * Search the extent at the specified file position.
 * The search is optimized for sequential accesses.
 * \return If not found return 0
 */
static struct snapraid_extent* fs_file2extent_get_unlock(struct snapraid_disk* disk, struct snapraid_extent** fs_last, struct snapraid_file* file, block_off_t file_pos)
{
	struct snapraid_extent* extent;

	/* check if the last accessed extent matches */
	if (*fs_last
		&& file == (*fs_last)->file
		&& file_pos >= (*fs_last)->file_pos
		&& file_pos - (*fs_last)->file_pos < (*fs_last)->count
	) {
		extent = *fs_last;
	} else {
		struct extent_file_inside arg = { file, file_pos };
		extent = tommy_tree_search_compare(&disk->fs_file, extent_file_inside_compare_unlock, &arg);
	}

	if (!extent)
		return 0;

	/* store the last accessed extent */
	*fs_last = extent;

	return extent;
}

struct snapraid_file* fs_par2file_find(struct snapraid_disk* disk, block_off_t parity_pos, block_off_t* file_pos)
{
	struct snapraid_extent* extent;
	struct snapraid_file* file;

	fs_lock(disk);

	extent = fs_par2extent_get_unlock(disk, &disk->fs_last, parity_pos);

	if (!extent) {
		fs_unlock(disk);
		return 0;
	}

	if (file_pos)
		*file_pos = extent->file_pos + (parity_pos - extent->parity_pos);

	file = extent->file;

	fs_unlock(disk);
	return file;
}

block_off_t fs_file2par_find_run(struct snapraid_disk* disk, struct snapraid_file* file, block_off_t file_pos, block_off_t* count)
{
	struct snapraid_extent* extent;
	block_off_t ret;

	fs_lock(disk);

	extent = fs_file2extent_get_unlock(disk, &disk->fs_last, file, file_pos);
	if (!extent) {
		fs_unlock(disk);
		return POS_NULL;
	}

	if (count)
		*count = extent->count - (file_pos - extent->file_pos);

	ret = extent->parity_pos + (file_pos - extent->file_pos);

	fs_unlock(disk);
	return ret;
}

block_off_t fs_file2par_find(struct snapraid_disk* disk, struct snapraid_file* file, block_off_t file_pos)
{
	return fs_file2par_find_run(disk, file, file_pos, 0);
}

/**
 * Allocate a run of file blocks mapping it to a run of parity positions.
 *
 * If the block is contiguous with the previous block of the file and follows
 * the current extent in parity space, the existing extent is extended in-place.
 * Otherwise, a new extent is created and inserted into the parity and file trees.
 *
 * Callers ensure allocations are sequential and do not overwrite live blocks.
 * To keep run allocation fast, full overlap checks across all existing
 * extents are omitted here; global non-overlap and complete coverage invariants
 * are verified in batch by fs_check() at major checkpoints (after read/scan,
 * before write).
 */
void fs_allocate(struct snapraid_disk* disk, block_off_t parity_pos, struct snapraid_file* file, block_off_t file_pos, block_off_t count)
{
	struct snapraid_extent* extent;
	struct snapraid_extent* parity_extent;
	struct snapraid_extent* file_extent;

	if (count > BLOCK_MAX || parity_pos > BLOCK_MAX - count) {
		/* LCOV_EXCL_START */
#if SIZE_MAX == UINT32_MAX
		log_fatal(ESOFT, "Parity range %" PRIu64 ":%" PRIu64 " is too large for a 32-bit build. Use a 64-bit build or increase the block size.\n", parity_pos, count);
#else
		log_fatal(ESOFT, "Parity range %" PRIu64 ":%" PRIu64 " is too large. Increase the block size.\n", parity_pos, count);
#endif
		exit(EXIT_FAILURE);
		/* LCOV_EXCL_STOP */
	}
	if (count > file->blockmax || file_pos > file->blockmax - count) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Allocating file '%s' at position '%" PRIu64 ":%" PRIu64 "/%" PRIu64 "' in disk '%s'\n", file->sub, file_pos, count, file->blockmax, disk->name);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	fs_lock(disk);

	if (file_pos > 0) {
		/* search an existing extent for the previous file_pos */
		extent = fs_file2extent_get_unlock(disk, &disk->fs_last, file, file_pos - 1);

		if (extent != 0 && parity_pos == extent->parity_pos + extent->count) {
			/* ensure that we are extending the extent at the end */
			if (file_pos != extent->file_pos + extent->count) {
				/* LCOV_EXCL_START */
				log_fatal(EINTERNAL, "Internal inconsistency: Allocating file '%s' at position '%" PRIu64 "/%" PRIu64 "' in the middle of extent '%" PRIu64 ":%" PRIu64 "' in disk '%s'\n", file->sub, file_pos, file->blockmax, extent->file_pos, extent->count, disk->name);
				os_abort();
				/* LCOV_EXCL_STOP */
			}

			/* extend the existing extent with the whole run */
			extent->count += count;

			fs_unlock(disk);
			return;
		}
	}

	/* a extent doesn't exist, and we have to create a new one */
	extent = extent_alloc(parity_pos, file, file_pos, count);

	/* insert the extent in the trees */
	parity_extent = tommy_tree_insert_unique(&disk->fs_parity, &extent->parity_node, extent);
	file_extent = tommy_tree_insert_unique(&disk->fs_file, &extent->file_node, extent);

	if (parity_extent != extent || file_extent != extent) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Allocating file '%s' at position '%" PRIu64 "/%" PRIu64 "' for existing extent '%" PRIu64 ":%" PRIu64 "' in disk '%s'\n", file->sub, file_pos, file->blockmax, extent->file_pos, extent->count, disk->name);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	/* store the last accessed extent */
	disk->fs_last = extent;

	fs_unlock(disk);
}

void fs_deallocate(struct snapraid_disk* disk, block_off_t parity_pos)
{
	struct snapraid_extent* extent;
	struct snapraid_extent* second_extent;
	struct snapraid_extent* parity_extent;
	struct snapraid_extent* file_extent;
	block_off_t first_count, second_count;

	fs_lock(disk);

	extent = fs_par2extent_get_unlock(disk, &disk->fs_last, parity_pos);
	if (!extent) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Deallocating parity position '%" PRIu64 "' for not existing extent in disk '%s'\n", parity_pos, disk->name);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	/* if it's the only block of the extent, delete it */
	if (extent->count == 1) {
		/* remove from the trees */
		tommy_tree_remove(&disk->fs_parity, extent);
		tommy_tree_remove(&disk->fs_file, extent);

		/* deallocate */
		extent_free(extent);

		/* clear the last accessed extent */
		disk->fs_last = 0;

		fs_unlock(disk);
		return;
	}

	/* if it's at the start of the extent, shrink the extent */
	if (parity_pos == extent->parity_pos) {
		/*
		 * Note that modifying parity_pos and file_pos in-place is safe
		 * because extents never overlap. Shrinking the start of the extent
		 * keeps the relative sorted order of all nodes completely unchanged,
		 * preserving the tree invariants without delete/insert overhead.
		 */
		++extent->parity_pos;
		++extent->file_pos;
		--extent->count;

		fs_unlock(disk);
		return;
	}

	/* if it's at the end of the extent, shrink the extent */
	if (parity_pos == extent->parity_pos + extent->count - 1) {
		--extent->count;

		fs_unlock(disk);
		return;
	}

	/* otherwise it's in the middle */
	first_count = parity_pos - extent->parity_pos;
	second_count = extent->count - first_count - 1;

	/* adjust the first extent */
	extent->count = first_count;

	/* allocate the second extent */
	second_extent = extent_alloc(extent->parity_pos + first_count + 1, extent->file, extent->file_pos + first_count + 1, second_count);

	/* insert the extent in the trees */
	parity_extent = tommy_tree_insert_unique(&disk->fs_parity, &second_extent->parity_node, second_extent);
	file_extent = tommy_tree_insert_unique(&disk->fs_file, &second_extent->file_node, second_extent);

	if (parity_extent != second_extent || file_extent != second_extent) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Deallocating parity position '%" PRIu64 "' for splitting extent '%" PRIu64 ":%" PRIu64 "' in disk '%s'\n", parity_pos, second_extent->file_pos, second_extent->count, disk->name);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	/* store the last accessed extent */
	disk->fs_last = second_extent;

	fs_unlock(disk);
}

struct snapraid_block* fs_file2block_get(struct snapraid_file* file, block_off_t file_pos)
{
	if (file_pos >= file->blockmax) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Dereferencing file '%s' at position '%" PRIu64 "/%" PRIu64 "'\n", file->sub, file_pos, file->blockmax);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	return file_block(file, file_pos);
}

struct snapraid_block* fs_par2block_find(struct snapraid_disk* disk, block_off_t parity_pos)
{
	struct snapraid_file* file;
	block_off_t file_pos;

	file = fs_par2file_find(disk, parity_pos, &file_pos);
	if (file == 0)
		return BLOCK_NULL;

	return fs_file2block_get(file, file_pos);
}

struct snapraid_map* map_alloc(const char* name, unsigned position, block_off_t total_blocks, block_off_t free_blocks, const char* uuid)
{
	struct snapraid_map* map;

	map = malloc_nofail(sizeof(struct snapraid_map));
	pathcpy(map->name, sizeof(map->name), name);
	map->position = position;
	map->total_blocks = total_blocks;
	map->free_blocks = free_blocks;
	pathcpy(map->content_uuid, sizeof(map->content_uuid), uuid);

	return map;
}

void map_free(void* void_map)
{
	struct snapraid_map* map = void_map;

	free(map);
}

/****************************************************************************/
/* bucket */

static int bucket_cmp(const void* void_a, const void* void_b)
{
	const struct snapraid_bucket* a = void_a;
	const struct snapraid_bucket* b = void_b;
	if (a->time_at < b->time_at)
		return -1;
	if (a->time_at > b->time_at)
		return 1;
	return 0;
}

void bucket_free(void* void_bucket)
{
	struct snapraid_bucket* bucket = void_bucket;

	free(bucket);
}

void bucket_insert(tommy_hashdyn* bucket_hash, time_t time_at, block_off_t count, int justsynced)
{
	tommy_hash_t hash = tommy_inthash_u64(time_at);
	tommy_node* i = tommy_hashdyn_bucket(bucket_hash, hash);
	while (i) {
		struct snapraid_bucket* entry = i->data;
		if (entry->time_at == time_at) {
			if (justsynced)
				entry->count_justsynced += count;
			else
				entry->count_scrubbed += count;
			return;
		}
		i = i->next;
	}

	struct snapraid_bucket* entry = malloc_nofail(sizeof(struct snapraid_bucket));
	entry->time_at = time_at;
	if (justsynced) {
		entry->count_justsynced = count;
		entry->count_scrubbed = 0;
	} else {
		entry->count_justsynced = 0;
		entry->count_scrubbed = count;
	}

	tommy_hashdyn_insert(bucket_hash, &entry->node, entry, hash);
}

void bucket_to_list(tommy_hashdyn* bucket_hash, tommy_list* bucket_list, block_off_t* bucketcount)
{
	/* clear previous list */
	tommy_list_foreach(bucket_list, bucket_free);
	tommy_list_init(bucket_list);

	log_tag("list:bucket_begin\n");

	log_tag("bucket:count:%" PRIu64 "\n", (uint64_t)tommy_hashdyn_count(bucket_hash));

	tommy_hashdyn_to_list(bucket_hash, bucket_list);

	tommy_list_sort(bucket_list, bucket_cmp);

	block_off_t count = 0;
	for (tommy_node* i = tommy_list_head(bucket_list); i != 0; i = i->next) {
		struct snapraid_bucket* entry = i->data;
		count += entry->count_scrubbed + entry->count_justsynced;
		log_tag("bucket:entry:%" PRIu64 ":%" PRIu64 ":%" PRIu64 "\n", (uint64_t)entry->time_at, entry->count_scrubbed, entry->count_justsynced);
	}

	log_tag("bucket:block_count:%" PRIu64 "\n", count);

	log_tag("list:bucket_end\n");

	*bucketcount = count;
}

/****************************************************************************/
/* format */

int FMT_MODE = FMT_FILE;

/**
 * Format a file path for poll reference
 */
const char* fmt_poll(const struct snapraid_disk* disk, const char* str)
{
	(void)disk;
	return esc_shell(str, esc_buf());
}

/**
 * Format a path name for terminal reference
 */
const char* fmt_term(const struct snapraid_disk* disk, const char* str)
{
	const char* out[3];

	switch (FMT_MODE) {
	case FMT_FILE :
	default :
		return esc_shell(str, esc_buf());
	case FMT_DISK :
		out[0] = disk->name;
		out[1] = ":";
		out[2] = str;
		return esc_shell_multi(out, 3, esc_buf());
	case FMT_PATH :
		out[0] = disk->mount_point;
		out[1] = str;
		return esc_shell_multi(out, 2, esc_buf());
	}
}

const char* fmt_size(uint64_t size, char* buffer, size_t buffer_size)
{
	if (size >= 10ULL * TERA)
		snprintf(buffer, buffer_size, "%" PRIu64 " T", size / TERA);
	else if (size >= 10ULL * GIGA)
		snprintf(buffer, buffer_size, "%" PRIu64 " G", size / GIGA);
	else if (size >= 10 * MEGA)
		snprintf(buffer, buffer_size, "%" PRIu64 " M", size / MEGA);
	else if (size >= 10 * KILO)
		snprintf(buffer, buffer_size, "%" PRIu64 " k", size / KILO);
	else
		snprintf(buffer, buffer_size, "%" PRIu64 " ", size);

	return buffer;
}