snapraid/cmdline/elem.h

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

#ifndef __ELEM_H
#define __ELEM_H

#include "util.h"
#include "support.h"
#include "tommyds/tommyhash.h"
#include "tommyds/tommylist.h"
#include "tommyds/tommytree.h"
#include "tommyds/tommyhashdyn.h"
#include "tommyds/tommyarray.h"
#include "tommyds/tommyarrayblkof.h"

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

/**
 * Maximum number of block positions in a data/parity disk span.
 *
 * With the default 256 KiB block size, this limits the maximum supported
 * size of the largest data/parity disk to:
 *
 *   32-bit:  2^27 blocks = 32 TiB
 *   64-bit:  2^42 blocks =  1 EiB
 *
 * The limit scales linearly with the configured block size. For example,
 * on 64-bit systems a 512 KiB block size allows 2 EiB per disk.
 *
 * This is an architectural sanity limit, not a memory-usage limit.
 * SnapRAID stores per-block metadata in memory, so practical configurations
 * will reach memory constraints long before BLOCK_MAX. The actual memory
 * requirement depends on block size, hash size, number of data disks, and
 * array layout.
 *
 * Based on historical HDD capacity growth, single disks are not expected
 * to approach 1 EiB before approximately the year 2100. If necessary,
 * larger disks can still be supported without changing BLOCK_MAX simply
 * by increasing the configured block size.
 */
#if SIZE_MAX == UINT32_MAX
#define BLOCK_MAX (1ULL << 27)
#else
#define BLOCK_MAX (1ULL << 42)
#endif

/**
 * Number of measures of the operation progress.
 */
#define PROGRESS_MAX 100

/**
 * Max UUID length.
 */
#define UUID_MAX 128

/**
 * Max filesystem type/label length
 */

#define FSINFO_MAX 64

/**
 * Invalid position.
 */
#define POS_NULL ((block_off_t)-1)

/**
 * Content file specification.
 */
struct snapraid_content {
	char content[PATH_MAX]; /**< Path of the content file. */
	uint64_t device; /**< Device identifier. */
	void* context; /**< Context used for multithread operations. */
	tommy_node node; /**< Next node in the list. */
};

/**
 * Filter for paths.
 */
struct snapraid_filter {
	char pattern[PATH_MAX]; /**< Filter pattern. */
	char root[PATH_MAX]; /**< If empty, it's a global pattern. If not empty, it's a local pattern that applies only to that dir. */
	int is_disk; /**< If the pattern is a disk one, otherwise it's a file pattern */
	int is_abs; /**< If the pattern is an absolute path (start with /), otherwise it's a relative one */
	int is_dir; /**< If the pattern is only for dir, otherwise it's only for file. */
	int direction; /**< If it's an inclusion (=1) or an exclusion (=-1). */
	tommy_node node; /**< Next node in the list. */
};

/**
 * Block pointer used to represent unused blocks.
 */
#define BLOCK_NULL 0

/**
 * This block is an empty one.
 * Note that an empty block is represent with ::BLOCK_NULL.
 */
#define BLOCK_STATE_EMPTY 0

/**
 * The block has both the hash and the parity computed.
 * This is the normal state of a saved block.
 *
 * The block hash is the hash of the CURRENT data.
 * The parity for this block IS valid.
 */
#define BLOCK_STATE_BLK 1

/**
 * The block is new and not yet hashed.
 * This happens when a new block overwrites a just removed block, or an empty
 * space.
 *
 * The block hash is the hash of the OLD data. Possible values are:
 * - ZERO -> The OLD block was empty
 * - INVALID -> The OLD block has an unknown hash
 * - Otherwise ->  The OLD block has this hash
 *
 * The parity for this block IS NOT valid, because it was computed with the old
 * data referenced by the hash.
 *
 * If the state is read from an incomplete sync, we don't really know if the
 * hash is referring to the data used to compute the parity, because the sync
 * process was interrupted at an unknown point, and the parity may or may not
 * be updated.
 */
#define BLOCK_STATE_CHG 2

/**
 * The block is new and hashed.
 * This happens when a new but hashed block overwrites a just removed block,
 * or an empty space.
 *
 * The block hash is the hash of the NEW data.
 * The parity for this block IS NOT valid.
 *
 * Note that when the file copy heuristic is enabled, the REP blocks may be set
 * using this heuristic, meaning that the hash may be wrong.
 * For this reason, when the ::force_nocopy flag is enabled, we convert all the REP blocks
 * to CHG, invalidating the stored hash.
 */
#define BLOCK_STATE_REP 3

/**
 * This block is a deleted one.
 * This happens when a file is deleted.
 *
 * The block hash is the hash of the OLD data. Possible values are:
 * - INVALID -> The OLD block has an unknown hash
 * - Otherwise ->  The OLD block has this hash
 *
 * The parity for this block IS NOT valid, because it was computed with the old
 * data referenced by the hash.
 *
 * If the state is read from an incomplete sync, we don't really know if the
 * hash is referring to the data used to compute the parity, because the sync
 * process was interrupted at an unknown point, and the parity may or may not
 * be updated.
 */
#define BLOCK_STATE_DELETED 4

/**
 * The block contains current data and a current hash, but its parity must be
 * rebuilt in place.
 *
 * The block hash is the hash of the CURRENT data.
 *
 * Physical parity for this block MUST NOT be trusted. It may still be correct,
 * may be missing, or may have been only partly rebuilt by an interrupted
 * --force-full sync.
 *
 * Unlike CHG and REP, this state does not permit automatic parity
 * reallocation. The existing data-to-parity mapping must be preserved.
 *
 * REBUILD is converted back to BLK only after the corresponding parity update
 * has completed and the normal sync durability ordering allows that progress
 * to be persisted.
 */
#define BLOCK_STATE_REBUILD 5

/**
 * Block hash size.
 *
 * At max HASH_MAX.
 */
extern size_t BLOCK_HASH_SIZE;

/**
 * Block of a file.
 */
struct snapraid_block {
	unsigned char state; /**< State of the block. */

	/**
	 * Hash of the block.
	 *
	 * The effective stored size is BLOCK_HASH_SIZE.
	 */
	unsigned char hash[HASH_MAX];
};

/**
 * If a file is present in the disk.
 * It's used only in scan to detect present and missing files.
 */
#define FILE_IS_PRESENT 0x01

/**
 * If it's an excluded file from the processing.
 * It's used in both check and fix to mark files to exclude from the processing.
 */
#define FILE_IS_EXCLUDED 0x02

/**
 * If a fix was attempted but it failed.
 * It's used only in fix to mark that some data is unrecoverable.
 */
#define FILE_IS_DAMAGED 0x04

/**
 * If a fix was done.
 * It's used only in fix to mark that some data was recovered.
 */
#define FILE_IS_FIXED 0x08

/**
 * If the file was originally missing, and it was created in the fix process.
 * It's used only in fix to mark files recovered from scratch,
 * meaning that they don't have any previous content.
 * This is important because it means that deleting them, you are not going
 * to lose something that cannot be recovered.
 * Note that excluded files won't ever get this flag.
 */
#define FILE_IS_CREATED 0x10

/**
 * If the file has completed its processing, meaning that it won't be opened anymore.
 * It's used only in fix to mark when we finish processing one file.
 * Note that excluded files won't ever get this flag.
 */
#define FILE_IS_FINISHED 0x20

/**
 * If the file hash was obtained from a file copy
 * identified by the same name, size and stamp.
 */
#define FILE_IS_COPY 0x40

/**
 * If the file was opened.
 * It's used in fix to detect if it's the first time a file is opened.
 */
#define FILE_IS_OPENED 0x80

/**
 * If the file is modified from the latest sync.
 * It's used in fix to store the state of the file before being modified.
 */
#define FILE_IS_UNSYNCED 0x100

/**
 * If the current recovery attempt was actually moved to the .unrecoverable name.
 * It's used only in fix to track the physical quarantine state independently
 * from FILE_IS_DAMAGED.
 */
#define FILE_IS_QUARANTINED 0x200

/**
 * The file is deleted.
 * This happens when a file is deleted from the array,
 * but it's keep inside the parity until the next sync.
 *
 * During the file-system check we needs this information,
 * because deleted files may be present only partially.
 */
#define FILE_IS_DELETED 0x400

/**
 * The file is missing.
 * This happens in fix/check when a file is cannot be opened,
 * and marking it as such prevents to retry to open it again.
 */
#define FILE_IS_MISSING 0x800

#define FILE_IS_HARDLINK 0x1000 /**< If it's an hardlink. */
#define FILE_IS_SYMLINK 0x2000 /**< If it's a file symlink. */
#define FILE_IS_SYMDIR 0x4000 /**< If it's a dir symlink for Windows. Not yet supported. */
#define FILE_IS_JUNCTION 0x8000 /**< If it's a junction for Windows. Not yet supported. */
#define FILE_IS_LINK_MASK 0xF000 /**< Mask for link type. */

/**
 * Flag to indicate the old version of a modified file during scanning.
 */
#define FILE_IS_MODIFIED_OLD 0x10000

/**
 * Flag to indicate the new version of a modified file during scanning.
 */
#define FILE_IS_MODIFIED_NEW 0x20000

/**
 * Flag to indicate the old version of a kept file being reallocated during scanning.
 */
#define FILE_IS_REALLOC_OLD 0x40000

/**
 * Flag to indicate the new version of a kept file being reallocated during scanning.
 */
#define FILE_IS_REALLOC_NEW 0x80000

/**
 * Flag to indicate that an existing file was discovered on the disk during Phase 1.
 */
#define FILE_IS_DISCOVERED 0x100000

/**
 * During scan if the file is found missing and relocated to another place
 *
 * This is used to avoid to report it "removed".
 */
#define FILE_IS_RELOCATED 0x1000000

/**
 * File.
 */
struct snapraid_file {
	int64_t mtime_sec; /**< Modification time. */
	uint64_t inode; /**< Inode. */
	data_off_t size; /**< Size of the file. */
	struct snapraid_block* blockvec; /**< All the blocks of the file. */
	block_off_t blockmax; /**< Number of blocks. */
	char* sub; /**< Sub path of the file. Without the disk dir. The disk is implicit. */
	int mtime_nsec; /**< Modification time nanoseconds. In the range 0 <= x < 1,000,000,000, or STAT_NSEC_INVALID if not present. */
	uint32_t flag; /**< FILE_IS_* flags. */

	/* nodes for data structures */
	tommy_node nodelist;
	tommy_hashdyn_node nodeset;
	tommy_hashdyn_node pathset;
	tommy_hashdyn_node stampset;

	char sub_inline[]; /**< Inline storage for the initial sub path. */
};

/**
 * Symbolic Link.
 */
struct snapraid_link {
	unsigned flag; /**< FILE_IS_* flags. */
	char* sub; /**< Sub path of the file. Without the disk dir. The disk is implicit. */
	char* linkto; /**< Link to. */

	/* nodes for data structures */
	tommy_node nodelist;
	tommy_hashdyn_node nodeset;
};

/**
 * Dir.
 */
struct snapraid_dir {
	unsigned flag; /**< FILE_IS_* flags. */
	char* sub; /**< Sub path of the file. Without the disk dir. The disk is implicit. */

	/* nodes for data structures */
	tommy_node nodelist;
	tommy_hashdyn_node nodeset;
};

/**
 * Deallocated block.
 */
struct snapraid_dealloc_block {
	unsigned char prev; /**< If the hash uses the previous hash generation. */
	unsigned char hash[HASH_MAX]; /**< Hash of the block. Only BLOCK_HASH_SIZE bytes are significant. */
};

/**
 * Deallocated file.
 */
struct snapraid_dealloc {
	char* sub; /**< Sub path of the file. Without the disk dir. The disk is implicit. */
	data_off_t size; /**< Size of the file. */
	int64_t mtime_sec; /**< Modification time. */
	int mtime_nsec; /**< Modification time nanoseconds. In the range 0 <= x < 1,000,000,000, or STAT_NSEC_INVALID if not present. */
	block_off_t blockmax; /**< Number of blocks. */

	/* nodes for data structures */
	tommy_node nodelist;

	struct snapraid_dealloc_block block[]; /**< Blocks of the file. */
};

/**
 * Chunk.
 *
 * A extent represents a fragment of a file mapped into the parity.
 */
struct snapraid_extent {
	struct snapraid_file* file; /**< File containing this extent. */
	block_off_t parity_pos; /**< Parity position. */
	block_off_t file_pos; /**< Position in the file. */
	block_off_t count; /**< Number of sequential blocks in the file and parity. */
	tommy_tree_node parity_node; /**< Tree sorted by <parity_pos>. */
	tommy_tree_node file_node; /**< Tree sorter by <file,file_pos>. */
};

/**
 * Other disk.
 */
struct snapraid_extra {
	char name[PATH_MAX]; /**< Name of the disk. */
	char dir[PATH_MAX]; /**< Mount point of the disk. It always terminates with /. */
	char smartctl[SMARTCTL_MAX]; /**< Custom option for smartctl. Empty means auto. */
	char smartctl_info[SMARTCTL_MAX]; /**< Info options for smartctl. Empty means -a. */
	struct smartignore_struct smartignore[SMART_IGNORE_MAX]; /**< Smart attributes to ignore for this device. */
	char uuid[UUID_MAX]; /**< UUID of the disk. They are probed during the config reading. */
	char fstype[FSINFO_MAX]; /**< Filesystem type */
	char fslabel[FSINFO_MAX]; /**< Filesystem label */

	uint64_t device; /**< Device identifier. */

	/* nodes for data structures */
	tommy_node node;
};

/**
 * Data disk.
 */
struct snapraid_disk {
	char name[PATH_MAX]; /**< Name of the disk. */

	/**
	 * Configured mount point of the disk.
	 *
	 * It always terminates with /
	 */
	char mount_point[PATH_MAX];

	/**
	 * Effective mount point of the disk.
	 *
	 * It could be either the real mount point or a snapshot.
	 * It always terminates with /
	 */
	char dir[PATH_MAX];

	/**
	 * Snapshot context
	 */
	struct fssnapshot_struct fss;

	char smartctl[SMARTCTL_MAX]; /**< Custom option for smartctl. Empty means auto. */
	char smartctl_info[SMARTCTL_MAX]; /**< Info options for smartctl. Empty means -a. */
	struct smartignore_struct smartignore[SMART_IGNORE_MAX]; /**< Smart attributes to ignore for this device. */
	char uuid[UUID_MAX]; /**< UUID of the disk. They are probed during the config reading. */
	char fstype[FSINFO_MAX]; /**< Filesystem type */
	char fslabel[FSINFO_MAX]; /**< Filesystem label */

	uint64_t mount_device; /**< Device identifier of the mount_point. */
	block_off_t total_blocks; /**< Number of total blocks. */
	block_off_t free_blocks; /**< Number of free blocks at the last sync. */

	uint64_t tick; /**< Usage time. */
	uint64_t progress_tick[PROGRESS_MAX]; /**< Last ticks of progress. */
	unsigned cached_blocks; /**< Number of IO blocks cached. */
	struct snapraid_file* progress_file; /**< File in progress. */

	/**
	 * First free searching block.
	 * Note that it doesn't necessarily point at the first free block,
	 * but it just tell you that no free block is present before this position.
	 */
	block_off_t first_free_block;

	int has_volatile_inodes; /**< If the underline file-system has not persistent inodes. */
	int has_volatile_hardlinks; /**< If the underline file-system has not synchronized metadata for hardlink (NTFS). */
	int has_different_uuid; /**< If the disk has a different UUID, meaning that it is not the same file-system. */
	int has_unsupported_uuid; /**< If the disk doesn't report UUID, meaning it's not supported. */
	int had_empty_uuid; /**< If the disk had an empty UUID, meaning that it's a new disk. */
	int mapping_idx; /**< Index in the mapping vector. Used only as buffer when writing the content file. */
	int skip_access; /**< If the disk is inaccessible and it should be skipped. */

#if HAVE_THREAD
	int single_thread; /**< Running in single thread, and then not needing the mutex */

	/**
	 * Mutex for protecting the filesystem structure.
	 *
	 * Specifically, this protects ::fs_parity, ::fs_file, and ::fs_last,
	 * meaning that it protects only extents.
	 *
	 * Files, links and dirs are not protected as they are not expected to
	 * change during multithread processing.
	 */
	thread_mutex_t fs_mutex;

#endif

	/**
	 * Mapping of extents in the parity.
	 * Sorted by <parity_pos> and by <file,file_pos>
	 */
	tommy_tree fs_parity;
	tommy_tree fs_file;

	/**
	 * Last extent we accessed.
	 * It's used to optimize access of sequential blocks.
	 */
	struct snapraid_extent* fs_last;

	/**
	 * List of all the snapraid_file for the disk.
	 */
	tommy_list filelist;

	/**
	 * List of all the deleted file for the disk.
	 *
	 * These files are kept allocated, because the blocks are still referenced in
	 * the ::blockarr.
	 */
	tommy_list deletedlist;

	tommy_hashdyn inodeset; /**< Hashtable by inode of all the files. */
	tommy_hashdyn pathset; /**< Hashtable by path of all the files. */
	tommy_hashdyn stampset; /**< Hashtable by stamp (size and time) of all the files. */
	tommy_list linklist; /**< List of all the links. */
	tommy_hashdyn linkset; /**< Hashtable by name of all the links. */
	tommy_list dirlist; /**< List of all the empty dirs. */
	tommy_hashdyn dirset; /**< Hashtable by name of all the empty dirs. */
	tommy_list dealloclist; /**< List of all the deallocs. */

	/* nodes for data structures */
	tommy_node node;
};

/**
 * Disk mapping.
 */
struct snapraid_map {
	char name[PATH_MAX]; /**< Name of the disk. */
	char content_uuid[UUID_MAX]; /**< UUID of the disk. Empty if unknown. They are read from the content file. */
	block_off_t total_blocks; /**< Number of total blocks. */
	block_off_t free_blocks; /**< Number of free blocks at last 'sync'. */
	unsigned position; /**< Position of the disk in the parity. */

	/* nodes for data structures */
	tommy_node node;
};

/**
 * Max number of parity split.
 */
#define SPLIT_MAX 8

/**
 * Invalid parity size.
 *
 * This value identifies new parity levels or splits
 * added in the configuration, for example when
 * creating a new parity level with 'fix'.
 * Given that 'fix' doesn't write the content file,
 * the new size will be written only at the next
 * 'sync'.
 */
#define PARITY_SIZE_INVALID -1LL

/**
 * Parity split.
 */
struct snapraid_split {
	char path[PATH_MAX]; /**< Path of the parity file. */
	char uuid[UUID_MAX]; /**< UUID of the disk. Empty if unknown. They are probed during the config reading. */
	char content_uuid[UUID_MAX]; /**< UUID read from the content file. */
	char fstype[FSINFO_MAX]; /**< Filesystem type */
	char fslabel[FSINFO_MAX]; /**< Filesystem label */

	/**
	 * Size of the parity split.
	 * Only the latest not zero size is allowed to grow.
	 * If the value is unset, it's PARITY_SIZE_INVALID.
	 */
	data_off_t size;

	uint64_t device; /**< Device identifier of the parity. */
};

/**
 * Parity.
 */
struct snapraid_parity {
	struct snapraid_split split_map[SPLIT_MAX]; /**< Parity splits. */
	unsigned split_mac; /**< Number of parity splits. */
	char smartctl[SMARTCTL_MAX]; /**< Custom option for smartctl. Empty means auto. */
	char smartctl_info[SMARTCTL_MAX]; /**< Info options for smartctl. Empty means -a. */
	struct smartignore_struct smartignore[SMART_IGNORE_MAX]; /**< Smart attributes to ignore for this device. */
	block_off_t total_blocks; /**< Number of total blocks. */
	block_off_t free_blocks; /**< Number of free blocks at the last sync. */
	int is_excluded_by_filter; /**< If the parity is excluded by filters. */
	int skip_access; /**< If at least one of the parity disk is inaccessible and it should be skipped. */
	uint64_t tick; /**< Usage time. */
	uint64_t progress_tick[PROGRESS_MAX]; /**< Last cpu ticks of progress. */
	unsigned cached_blocks; /**< Number of IO blocks cached. */
};

/**
 * Info.
 */
typedef uint64_t snapraid_info;

/**
 * Allocate a content.
 */
struct snapraid_content* content_alloc(const char* path, uint64_t dev);

/**
 * Deallocate a content.
 */
void content_free(void* void_content);

/**
 * Allocate a filter pattern for files and directories.
 */
struct snapraid_filter* filter_alloc_file(int is_include, const char* root, const char* pattern);

/**
 * Allocate a filter pattern for disks.
 */
struct snapraid_filter* filter_alloc_disk(int is_include, const char* pattern);

/**
 * Deallocate an exclusion.
 */
void filter_free(void* filter);

/**
 * Filter type description.
 */
const char* filter_type(struct snapraid_filter* filter, char* out, size_t out_size);

/**
 * Filter hidden files.
 * Return !=0 if it matches and it should be excluded.
 */
static inline int filter_hidden(int enable, struct dirent* dd)
{
	if (enable && dirent_hidden(dd)) {
		return 1; /* filter out */
	}

	return 0;
}

/**
 * Filter a path using a list of filters.
 * For each element of the path all the filters are applied, until the first one that matches.
 * Return !=0 if it should be excluded.
 */
int filter_path(tommy_list* filterlist, struct snapraid_filter** reason, const char* disk, const char* sub);

/**
 * Filter a file/link/dir if missing.
 * This call imply a disk check for the file presence.
 * Return !=0 if the file is present and it should be excluded.
 */
int filter_existence(int filter_missing, const char* dir, const char* sub);

/**
 * Filter a file if bad.
 * Return !=0 if the file is correct and it should be excluded.
 */
int filter_correctness(int filter_error, tommy_arrayblkof* infoarr, struct snapraid_disk* disk, struct snapraid_file* file);

/**
 * Filter a dir using a list of filters.
 * For each element of the path all the filters are applied, until the first one that matches.
 * Thesesdir are always by included by default, to allow to apply rules at the contained files.
 * Return !=0 if should be excluded.
 */
int filter_subdir(tommy_list* filterlist, struct snapraid_filter** reason, const char* disk, const char* sub);

/**
 * Filter a dir using a list of filters.
 * For each element of the path all the filters are applied, until the first one that matches.
 * Return !=0 if should be excluded.
 */
int filter_emptydir(tommy_list* filterlist, struct snapraid_filter** reason, const char* disk, const char* sub);

/**
 * Filter a path if it's a content file.
 * Return !=0 if should be excluded.
 */
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);

/**
 * Filter a path that is in a snapshot
 * Return !=0 if should be excluded.
 */
int filter_snapshot(int enable, const char* sub, const char* name);

/**
 * Copy a block hash using the configured hash size.
 *
 * Keep the common full-size case explicit so the compiler can inline a fixed
 * 16-byte copy instead of emitting a call to memcpy() with a runtime size.
 */
static __always_inline void* hash_copy(void* dst, const void* src)
{
	if (BLOCK_HASH_SIZE == HASH_MAX)
		return memcpy(dst, src, HASH_MAX);
	else
		return memcpy(dst, src, BLOCK_HASH_SIZE);
}

/**
 * Check if the specified hash is invalid.
 *
 * An invalid hash is represented with all bytes at 0x00.
 *
 * If working with reduced hash lengths, this function always return 0.
 */
static inline int hash_is_invalid(const unsigned char* hash)
{
	size_t i;

	/* if the hash is reduced, we cannot grant that it's a specific kind of hash */
	if (BLOCK_HASH_SIZE != HASH_MAX)
		return 0;

	for (i = 0; i < HASH_MAX; ++i)
		if (hash[i] != 0x00)
			return 0;

	return 1;
}

/**
 * Check if the specified hash represent the zero block.
 *
 * A zero hash is represented with all bytes at 0xFF.
 *
 * If working with reduced hash lengths, this function always return 0.
 */
static inline int hash_is_zero(const unsigned char* hash)
{
	size_t i;

	/* if the hash is reduced, we cannot grant that it's a specific kind of hash */
	if (BLOCK_HASH_SIZE != HASH_MAX)
		return 0;

	for (i = 0; i < BLOCK_HASH_SIZE; ++i)
		if (hash[i] != 0xFF)
			return 0;

	return 1;
}

/**
 * Check if the specified hash is unequivocally representing the data.
 *
 * If working with reduced hash lengths, this function always return 0.
 */
static inline int hash_is_unique(const unsigned char* hash)
{
	/* if the hash is reduced, we cannot grant that it's a specific kind of hash */
	if (BLOCK_HASH_SIZE != HASH_MAX)
		return 0;

	return !hash_is_zero(hash) && !hash_is_invalid(hash);
}

/**
 * Set the hash to the special INVALID value.
 */
static inline void hash_invalid_set(unsigned char* hash)
{
	memset(hash, 0x00, BLOCK_HASH_SIZE);
}

/**
 * Set the hash to the special ZERO value.
 */
static inline void hash_zero_set(unsigned char* hash)
{
	memset(hash, 0xFF, BLOCK_HASH_SIZE);
}

/**
 * Allocated space for block.
 */
static inline size_t block_sizeof(void)
{
	return 1 + BLOCK_HASH_SIZE;
}

/**
 * Get the state of the block.
 *
 * For this function, it's allowed to pass a NULL block
 * pointer than results in the BLOCK_STATE_EMPTY state.
 */
static inline unsigned block_state_get(const struct snapraid_block* block)
{
	if (block == BLOCK_NULL)
		return BLOCK_STATE_EMPTY;

	return block->state;
}

/**
 * Set the state of the block.
 */
static inline void block_state_set(struct snapraid_block* block, unsigned state)
{
	block->state = state;
}

/**
 * Check if the specified block has an updated hash.
 *
 * Note that EMPTY / CHG / DELETED return 0.
 */
static inline int block_has_updated_hash(const struct snapraid_block* block)
{
	unsigned state = block_state_get(block);

	return state == BLOCK_STATE_BLK
	       || state == BLOCK_STATE_REP
	       || state == BLOCK_STATE_REBUILD;
}

/**
 * Check if the specified block is part of a file.
 *
 * Note that EMPTY / DELETED return 0.
 */
static inline int block_has_file(const struct snapraid_block* block)
{
	unsigned state = block_state_get(block);

	return state == BLOCK_STATE_BLK
	       || state == BLOCK_STATE_CHG
	       || state == BLOCK_STATE_REP
	       || state == BLOCK_STATE_REBUILD;
}

/**
 * Check if the block has an invalid parity than needs to be updated.
 *
 * Note that EMPTY / BLK return 0.
 */
static inline int block_has_invalid_parity(const struct snapraid_block* block)
{
	unsigned state = block_state_get(block);

	return state == BLOCK_STATE_DELETED
	       || state == BLOCK_STATE_CHG
	       || state == BLOCK_STATE_REP
	       || state == BLOCK_STATE_REBUILD;
}

/**
 * Check if the block is part of a file with valid parity.
 *
 * Note that anything different than BLK return 0.
 */
static inline int block_has_file_and_valid_parity(const struct snapraid_block* block)
{
	unsigned state = block_state_get(block);

	return state == BLOCK_STATE_BLK;
}

/**
 * Check if a live block with invalid parity may participate in automatic
 * parity reallocation.
 *
 * REBUILD is deliberately excluded because it requires an in-place parity
 * rebuild preserving the existing data-to-parity mapping.
 */
static inline int block_has_reallocatable_parity(const struct snapraid_block* block)
{
	unsigned state = block_state_get(block);

	return state == BLOCK_STATE_CHG
	       || state == BLOCK_STATE_REP;
}

static inline int file_flag_has(const struct snapraid_file* file, unsigned mask)
{
	return (file->flag & mask) == mask;
}

static inline void file_flag_set(struct snapraid_file* file, unsigned mask)
{
	file->flag |= mask;
}

static inline void file_flag_clear(struct snapraid_file* file, unsigned mask)
{
	file->flag &= ~mask;
}

/**
 * Allocate a file without initializing its blocks.
 */
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);
static inline struct snapraid_file* file_alloc(unsigned block_size, const char* sub, data_off_t size, uint64_t mtime_sec, int mtime_nsec, uint64_t inode)
{
	return file_alloc_len(block_size, sub, strlen(sub), size, mtime_sec, mtime_nsec, inode);
}

/**
 * Duplicate a file.
 */
struct snapraid_file* file_dup(struct snapraid_file* copy);

/**
 * Deallocate a file.
 */
void file_free(void* void_file);

/**
 * Rename a file.
 */
void file_rename(struct snapraid_file* file, const char* sub);

/**
 * Copy a file.
 */
void file_copy(struct snapraid_file* src_file, struct snapraid_file* dest_file);

/**
 * Return the block at the specified position.
 *
 * Note that the block size if a runtime value.
 */
static inline struct snapraid_block* file_block(struct snapraid_file* file, block_off_t pos)
{
	unsigned char* ptr = (unsigned char*)file->blockvec;

	return (struct snapraid_block*)(ptr + pos * block_sizeof());
}

/**
 * Return the name of the file, without the dir.
 */
const char* file_name(const struct snapraid_file* file);

/**
 * Check if the block is the last in the file.
 */
int file_block_is_last(struct snapraid_file* file, block_off_t file_pos);

/**
 * Get the size in bytes of the block.
 * If it's the last block of a file it could be less than block_size.
 */
size_t file_block_size(struct snapraid_file* file, block_off_t file_pos, size_t block_size);

/**
 * Compare a file with an inode.
 */
int file_inode_compare_to_arg(const void* void_arg, const void* void_data);

/**
 * Compare files by inode.
 */
int file_inode_compare(const void* void_a, const void* void_b);

/**
 * Compare files by path.
 */
int file_path_compare(const void* void_a, const void* void_b);

/**
 * Compute the hash of a file inode.
 */
static inline tommy_hash_t file_inode_hash(uint64_t inode)
{
	return tommy_inthash_u64(inode);
}

/**
 * Compare a file with a path.
 */
int file_path_compare_to_arg(const void* void_arg, const void* void_data);

/**
 * Compare a file with another file for name, stamp, and both.
 */
int file_name_compare(const void* void_a, const void* void_b);
int file_stamp_compare(const void* void_a, const void* void_b);
int file_namestamp_compare(const void* void_a, const void* void_b);
int file_pathstamp_compare(const void* void_a, const void* void_b);

/**
 * Compute the hash of a file path with known length.
 */
static inline tommy_hash_t file_path_hash_len(const char* sub, size_t len)
{
#if TOMMY_SIZE_BIT == 64
	return tommy_hash_u64(0, sub, len);
#else
	return tommy_hash_u32(0, sub, len);
#endif
}

/**
 * Compute the hash of a file path.
 */
static inline tommy_hash_t file_path_hash(const char* sub)
{
	return file_path_hash_len(sub, strlen(sub));
}

/**
 * Compute the hash of a file stamp.
 */
static inline tommy_hash_t file_stamp_hash(data_off_t size, int64_t mtime_sec, int mtime_nsec)
{
#if TOMMY_SIZE_BIT == 64
	return tommy_inthash_u64((uint64_t)size ^ tommy_inthash_u64((uint64_t)mtime_sec ^ (uint64_t)(uint32_t)mtime_nsec));
#else
	return tommy_inthash_u32((tommy_uint32_t)size ^ tommy_inthash_u32((tommy_uint32_t)mtime_sec ^ tommy_inthash_u32(mtime_nsec)));
#endif
}

/**
 * Allocate a extent.
 */
struct snapraid_extent* extent_alloc(block_off_t parity_pos, struct snapraid_file* file, block_off_t file_pos, block_off_t count);

/**
 * Deallocate a extent.
 */
void extent_free(void* void_extent);

/**
 * Compare extent by parity position.
 */
int extent_parity_compare(const void* void_a, const void* void_b);

/**
 * Compare extent by file and file position.
 */
int extent_file_compare(const void* void_a, const void* void_b);

static inline int link_flag_has(const struct snapraid_link* slink, unsigned mask)
{
	return (slink->flag & mask) == mask;
}

static inline void link_flag_set(struct snapraid_link* slink, unsigned mask)
{
	slink->flag |= mask;
}

static inline void link_flag_clear(struct snapraid_link* slink, unsigned mask)
{
	slink->flag &= ~mask;
}

static inline void link_flag_let(struct snapraid_link* slink, unsigned flag, unsigned mask)
{
	slink->flag &= ~mask;
	slink->flag |= flag & mask;
}

static inline unsigned link_flag_get(struct snapraid_link* slink, unsigned mask)
{
	return slink->flag & mask;
}

/**
 * Allocate a link.
 */
struct snapraid_link* link_alloc_len(const char* name, size_t name_len, const char* slink, size_t slink_len, unsigned link_flag);
static inline struct snapraid_link* link_alloc(const char* name, const char* slink, unsigned link_flag)
{
	return link_alloc_len(name, strlen(name), slink, strlen(slink), link_flag);
}

/**
 * Deallocate a link.
 */
void link_free(void* void_link);

/**
 * Compare a link with a name.
 */
int link_name_compare_to_arg(const void* void_arg, const void* void_data);

/**
 * Compare links by path.
 */
int link_alpha_compare(const void* void_a, const void* void_b);

/**
 * Compute the hash of a link name with known length.
 */
static inline tommy_hash_t link_name_hash_len(const char* name, size_t len)
{
#if TOMMY_SIZE_BIT == 64
	return tommy_hash_u64(0, name, len);
#else
	return tommy_hash_u32(0, name, len);
#endif
}

/**
 * Compute the hash of a link name.
 */
static inline tommy_hash_t link_name_hash(const char* name)
{
	return link_name_hash_len(name, strlen(name));
}

static inline int dir_flag_has(const struct snapraid_dir* dir, unsigned mask)
{
	return (dir->flag & mask) == mask;
}

static inline void dir_flag_set(struct snapraid_dir* dir, unsigned mask)
{
	dir->flag |= mask;
}

static inline void dir_flag_clear(struct snapraid_dir* dir, unsigned mask)
{
	dir->flag &= ~mask;
}

/**
 * Allocate a dir.
 */
struct snapraid_dir* dir_alloc_len(const char* name, size_t name_len);
static inline struct snapraid_dir* dir_alloc(const char* name)
{
	return dir_alloc_len(name, strlen(name));
}

/**
 * Deallocate a dir.
 */
void dir_free(void* void_dir);

/**
 * Compare a dir with a name.
 */
int dir_name_compare(const void* void_arg, const void* void_data);

/**
 * Compute the hash of a dir name with known length.
 */
static inline tommy_hash_t dir_name_hash_len(const char* name, size_t len)
{
#if TOMMY_SIZE_BIT == 64
	return tommy_hash_u64(0, name, len);
#else
	return tommy_hash_u32(0, name, len);
#endif
}

/**
 * Compute the hash of a dir name.
 */
static inline tommy_hash_t dir_name_hash(const char* name)
{
	return dir_name_hash_len(name, strlen(name));
}

/**
 * Allocate a dealloc.
 */
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);
static inline struct snapraid_dealloc* dealloc_alloc(unsigned block_size, const char* sub, data_off_t size, int64_t mtime_sec, int32_t mtime_nsec)
{
	return dealloc_alloc_len(block_size, sub, strlen(sub), size, mtime_sec, mtime_nsec);
}

/**
 * Deallocate a dealloc.
 */
void dealloc_free(void* void_dealloc);

/**
 * Import file hash in the dealloc.
 */
void dealloc_import(tommy_arrayblkof* infoarr, struct snapraid_disk* disk, struct snapraid_dealloc* dealloc, struct snapraid_file* file);

/**
 * Allocate a disk.
 */
struct snapraid_disk* disk_alloc(const char* name, const char* dir, uint64_t dev, const char* uuid, int skip_access);

/**
 * Deallocate a disk.
 */
void disk_free(void* void_disk);

/**
 * Allocate a extra disk.
 */
struct snapraid_extra* extra_alloc(const char* name, const char* dir, uint64_t dev, const char* uuid);

/**
 * Deallocate a other disk.
 */
void extra_free(void* void_extra);

/**
 * Get the size of the disk in blocks.
 */
block_off_t fs_size(struct snapraid_disk* disk);

/**
 * Check if a disk is totally empty and can be discarded from the content file.
 * A disk is empty if it doesn't contain any file, symlink, hardlink or dir
 * and without any DELETED block.
 * The blockmax is used to limit the search of DELETED block up to blockmax.
 */
int fs_is_empty(struct snapraid_disk* disk, block_off_t blockmax);

/**
 * Check the file-system for errors.
 * Return 0 if it's OK.
 */
int fs_check(struct snapraid_disk* disk);

/**
 * Allocate a run of parity positions for the specified file positions.
 *
 * After this call you can use the par2file/par2block operations
 * to query the relation.
 *
 * \note This function is NOT thread-safe as it uses the disk cache. +
 */
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);

/**
 * Deallocate the parity position.
 *
 * After this call the par2file/par2block operations
 * won't find anymore the parity association.
 *
 * \note This function is NOT thread-safe as it uses the disk cache.
 */
void fs_deallocate(struct snapraid_disk* disk, block_off_t pos);

/**
 * Get the block from the file position.
 */
struct snapraid_block* fs_file2block_get(struct snapraid_file* file, block_off_t file_pos);

/**
 * Find the first extent ending after the specified parity position.
 * Return 0 if no such extent exists. The caller must ensure that the extent
 * trees remain unchanged while using the returned extent or its tree node.
 */
struct snapraid_extent* fs_par2extent_find_next(struct snapraid_disk* disk, block_off_t parity_pos);

/**
 * Get the file position from the parity position.
 * Return 0 if no file is using it.
 */
struct snapraid_file* fs_par2file_find(struct snapraid_disk* disk, block_off_t parity_pos, block_off_t* file_pos);

/**
 * Get the file position from the parity position.
 */
static inline struct snapraid_file* fs_par2file_get(struct snapraid_disk* disk, block_off_t parity_pos, block_off_t* file_pos)
{
	struct snapraid_file* ret;

	ret = fs_par2file_find(disk, parity_pos, file_pos);
	if (ret == 0) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Deresolving parity to file at position '%" PRIu64 "' in disk '%s'\n", parity_pos, disk->name);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	return ret;
}

/**
 * Get the parity position from the file position.
 * Return POS_NULL if no parity is allocated.
 */
block_off_t fs_file2par_find(struct snapraid_disk* disk, struct snapraid_file* file, block_off_t file_pos);

/**
 * Get the parity position from the file position. If count is specified, return
 * the number of blocks remaining in the same extent, including the current one.
 * Return POS_NULL if no parity is allocated.
 */
block_off_t fs_file2par_find_run(struct snapraid_disk* disk, struct snapraid_file* file, block_off_t file_pos, block_off_t* count);

/**
 * Get the parity position and the number of blocks remaining in the same extent,
 * including the current one, from the file position.
 */
static inline block_off_t fs_file2par_get_run(struct snapraid_disk* disk, struct snapraid_file* file, block_off_t file_pos, block_off_t* count)
{
	block_off_t ret;

	ret = fs_file2par_find_run(disk, file, file_pos, count);
	if (ret == POS_NULL) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Resolving file '%s' at position '%" PRIu64 "/%" PRIu64 "' in disk '%s'\n", file->sub, file_pos, file->blockmax, disk->name);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	return ret;
}

/**
 * Get the parity position from the file position.
 */
static inline block_off_t fs_file2par_get(struct snapraid_disk* disk, struct snapraid_file* file, block_off_t file_pos)
{
	return fs_file2par_get_run(disk, file, file_pos, 0);
}

/**
 * Get the block from the parity position.
 * Return BLOCK_NULL==0 if the block is over the end of the disk or not used.
 */
struct snapraid_block* fs_par2block_find(struct snapraid_disk* disk, block_off_t parity_pos);

/**
 * Get the block from the parity position.
 */
static inline struct snapraid_block* fs_par2block_get(struct snapraid_disk* disk, block_off_t parity_pos)
{
	struct snapraid_block* ret;

	ret = fs_par2block_find(disk, parity_pos);
	if (ret == BLOCK_NULL) {
		/* LCOV_EXCL_START */
		log_fatal(EINTERNAL, "Internal inconsistency: Deresolving parity to block at position '%" PRIu64 "' in disk '%s'\n", parity_pos, disk->name);
		os_abort();
		/* LCOV_EXCL_STOP */
	}

	return ret;
}

/**
 * Allocate a disk mapping.
 * Uses uuid="" if not available.
 */
struct snapraid_map* map_alloc(const char* name, unsigned position, block_off_t total_blocks, block_off_t free_blocks, const char* uuid);

/**
 * Deallocate a disk mapping.
 */
void map_free(void* void_map);

/**
 * Mask used to store additional information in the info bits.
 *
 * These bits reduce the granularity of the time in the memory representation.
 */
#define INFO_MASK ((snapraid_info)0x7)

/**
 * Make an info.
 */
static inline snapraid_info info_make(time_t last_access, int error, int rehash, int justsynced)
{
	/* clear the lowest bits as reserved for other information */
	snapraid_info info = last_access & ~INFO_MASK;

	if (error != 0)
		info |= 0x1;
	if (rehash != 0)
		info |= 0x2;
	if (justsynced != 0)
		info |= 0x4;
	return info;
}

/**
 * Extract the time information.
 * This is the last time when the block was know to be correct.
 * The "scrubbed" info tells if the time is referring at the latest sync or scrub.
 */
static inline time_t info_get_time(snapraid_info info)
{
	return info & ~INFO_MASK;
}

/**
 * Extract the error information.
 * Report if the block address had some problem.
 */
static inline int info_get_bad(snapraid_info info)
{
	return (info & 0x1) != 0;
}

/**
 * Extract the rehash information.
 * Report if the block address is using the old hash and needs to be rehashed.
 */
static inline int info_get_rehash(snapraid_info info)
{
	return (info & 0x2) != 0;
}

/**
 * Extract the scrubbed information.
 * Report if the block address was never scrubbed.
 */
static inline int info_get_justsynced(snapraid_info info)
{
	return (info & 0x4) != 0;
}

/**
 * Mark the block address as with error.
 */
static inline snapraid_info info_set_bad(snapraid_info info)
{
	return info | 0x1;
}

/**
 * Mark the block address as with rehash.
 */
static inline snapraid_info info_set_rehash(snapraid_info info)
{
	return info | 0x2;
}

/**
 * Set the info at the specified position.
 * The position is allocated if not yet done.
 */
static inline void info_set(tommy_arrayblkof* array, block_off_t pos, snapraid_info info)
{
	tommy_arrayblkof_grow(array, pos + 1);

	memcpy(tommy_arrayblkof_ref(array, pos), &info, sizeof(snapraid_info));
}

/**
 * Get the info at the specified position.
 * For not allocated position, 0 is returned.
 */
static inline snapraid_info info_get(tommy_arrayblkof* array, block_off_t pos)
{
	snapraid_info info;

	if (pos >= tommy_arrayblkof_size(array))
		return 0;

	memcpy(&info, tommy_arrayblkof_ref(array, pos), sizeof(snapraid_info));

	return info;
}

/**
 * Set a run of info values.
 *
 * Grow the array once and process each internal block directly, avoiding the
 * per-position grow and lookup performed by info_set().
 */
__aligned_loops(64)
static inline void info_set_run(tommy_arrayblkof* array, block_off_t pos, block_off_t count, snapraid_info info)
{
	tommy_arrayblkof_grow(array, pos + count);

	while (count) {
		block_off_t offset = pos % TOMMY_ARRAYBLKOF_SIZE;
		block_off_t run = TOMMY_ARRAYBLKOF_SIZE - offset;
		snapraid_info* data;
		block_off_t i;

		if (run > count)
			run = count;

		data = tommy_arrayblkof_ref(array, pos);
		for (i = 0; i < run; ++i)
			data[i] = info;

		pos += run;
		count -= run;
	}
}

/**
 * Get the value and length of an info run, up to count positions.
 *
 * Unallocated positions have the same zero value returned by info_get().
 * Process allocated storage a block at a time to avoid resolving every array
 * position independently.
 */
static inline block_off_t info_get_run(tommy_arrayblkof* array, block_off_t pos, block_off_t count, snapraid_info* info)
{
	block_off_t size = tommy_arrayblkof_size(array);
	block_off_t total = 0;

	if (pos >= size) {
		*info = 0;
		return count;
	}

	memcpy(info, tommy_arrayblkof_ref(array, pos), sizeof(snapraid_info));

	while (total < count && pos + total < size) {
		block_off_t current = pos + total;
		block_off_t offset = current % TOMMY_ARRAYBLKOF_SIZE;
		block_off_t run = TOMMY_ARRAYBLKOF_SIZE - offset;
		snapraid_info* data;
		block_off_t i;

		if (run > count - total)
			run = count - total;
		if (run > size - current)
			run = size - current;

		data = tommy_arrayblkof_ref(array, current);
		for (i = 0; i < run; ++i)
			if (data[i] != *info)
				return total + i;

		total += run;
	}

	/* info_get() returns zero for the whole unallocated tail */
	if (total < count && *info == 0)
		return count;

	return total;
}

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

struct snapraid_bucket {
	time_t time_at; /**< Time of the scrub */
	block_off_t count_scrubbed; /**< Number of blocks scrubbed */
	block_off_t count_justsynced; /**< Number of blocks justsynced */
	tommy_node node;
};

void bucket_free(void* void_bucket);

/**
 * Insert an bucket record into the hashtable
 */
void bucket_insert(tommy_hashdyn* bucket_hash, time_t time_at, block_off_t count, int justsynced);

/**
 * Convert the bucket hashtable to a sorted list
 */
void bucket_to_list(tommy_hashdyn* bucket_hash, tommy_list* bucket_list, block_off_t* bucketcount);

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

#define FMT_FILE 0 /**< Print only the file. */
#define FMT_DISK 1 /**< Print the disk name and the file. */
#define FMT_PATH 2 /**< Print the full path. */

extern int FMT_MODE;

/**
 * Format a file path for poll reference
 */
const char* fmt_poll(const struct snapraid_disk* disk, const char* str);

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

/**
 * Format a size adding suffix K/M/G/T
 */
const char* fmt_size(uint64_t size, char* buffer, size_t buffer_size);

#endif