path: root/src/ext4_xattr.c

/*
 * Copyright (c) 2017 Grzegorz Kostka (kostka.grzegorz@gmail.com)
 * Copyright (c) 2017 Kaho Ng (ngkaho1234@gmail.com)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 */

/** @addtogroup lwext4
 * @{
 */
/**
 * @file  ext4_xattr.c
 * @brief Extended Attribute manipulation.
 */

#include <ext4_config.h>
#include <ext4_debug.h>
#include <ext4_errno.h>
#include <ext4_misc.h>
#include <ext4_types.h>

#include <ext4_balloc.h>
#include <ext4_block_group.h>
#include <ext4_blockdev.h>
#include <ext4_crc32.h>
#include <ext4_fs.h>
#include <ext4_inode.h>
#include <ext4_super.h>
#include <ext4_trans.h>
#include <ext4_xattr.h>

#include <stdlib.h>
#include <string.h>

#if CONFIG_XATTR_ENABLE

/**
 * @file  ext4_xattr.c
 * @brief Extended Attribute Manipulation
 */

/* Extended Attribute(EA) */

/* Magic value in attribute blocks */
#define EXT4_XATTR_MAGIC        0xEA020000

/* Maximum number of references to one attribute block */
#define EXT4_XATTR_REFCOUNT_MAX     1024

/* Name indexes */
#define EXT4_XATTR_INDEX_USER           1
#define EXT4_XATTR_INDEX_POSIX_ACL_ACCESS   2
#define EXT4_XATTR_INDEX_POSIX_ACL_DEFAULT  3
#define EXT4_XATTR_INDEX_TRUSTED        4
#define EXT4_XATTR_INDEX_LUSTRE         5
#define EXT4_XATTR_INDEX_SECURITY           6
#define EXT4_XATTR_INDEX_SYSTEM         7
#define EXT4_XATTR_INDEX_RICHACL        8
#define EXT4_XATTR_INDEX_ENCRYPTION     9

#define EXT4_XATTR_PAD_BITS 2
#define EXT4_XATTR_PAD (1 << EXT4_XATTR_PAD_BITS)
#define EXT4_XATTR_ROUND (EXT4_XATTR_PAD - 1)
#define EXT4_XATTR_LEN(name_len)                                               \
    (((name_len) + EXT4_XATTR_ROUND + sizeof(struct ext4_xattr_entry)) &   \
     ~EXT4_XATTR_ROUND)
#define EXT4_XATTR_NEXT(entry)                                                 \
    ((struct ext4_xattr_entry *)((char *)(entry) +                         \
                     EXT4_XATTR_LEN((entry)->e_name_len)))
#define EXT4_XATTR_SIZE(size) (((size) + EXT4_XATTR_ROUND) & ~EXT4_XATTR_ROUND)
#define EXT4_XATTR_NAME(entry) ((char *)((entry) + 1))

#define EXT4_XATTR_IHDR(sb, raw_inode)                                         \
    ((struct ext4_xattr_ibody_header *)((char *)raw_inode +                \
                        EXT4_GOOD_OLD_INODE_SIZE +         \
                        ext4_inode_get_extra_isize(        \
                        sb, raw_inode)))
#define EXT4_XATTR_IFIRST(hdr) ((struct ext4_xattr_entry *)((hdr) + 1))

#define EXT4_XATTR_BHDR(block) ((struct ext4_xattr_header *)((block)->data))
#define EXT4_XATTR_ENTRY(ptr) ((struct ext4_xattr_entry *)(ptr))
#define EXT4_XATTR_BFIRST(block) EXT4_XATTR_ENTRY(EXT4_XATTR_BHDR(block) + 1)
#define EXT4_XATTR_IS_LAST_ENTRY(entry) (*(uint32_t *)(entry) == 0)

#define EXT4_ZERO_XATTR_VALUE ((void *)-1)

#pragma pack(push, 1)

struct ext4_xattr_header {
    uint32_t h_magic;   /* magic number for identification */
    uint32_t h_refcount;    /* reference count */
    uint32_t h_blocks;  /* number of disk blocks used */
    uint32_t h_hash;        /* hash value of all attributes */
    uint32_t h_checksum;    /* crc32c(uuid+id+xattrblock) */
                /* id = inum if refcount=1, blknum otherwise */
    uint32_t h_reserved[3]; /* zero right now */
};

struct ext4_xattr_ibody_header {
    uint32_t h_magic;   /* magic number for identification */
};

struct ext4_xattr_entry {
    uint8_t e_name_len; /* length of name */
    uint8_t e_name_index;   /* attribute name index */
    uint16_t e_value_offs;  /* offset in disk block of value */
    uint32_t e_value_block; /* disk block attribute is stored on (n/i) */
    uint32_t e_value_size;  /* size of attribute value */
    uint32_t e_hash;        /* hash value of name and value */
};

#pragma pack(pop)


#define NAME_HASH_SHIFT 5
#define VALUE_HASH_SHIFT 16

static inline void ext4_xattr_compute_hash(struct ext4_xattr_header *header,
					   struct ext4_xattr_entry *entry)
{
	uint32_t hash = 0;
	char *name = EXT4_XATTR_NAME(entry);
	int n;

	for (n = 0; n < entry->e_name_len; n++) {
		hash = (hash << NAME_HASH_SHIFT) ^
		       (hash >> (8 * sizeof(hash) - NAME_HASH_SHIFT)) ^ *name++;
	}

	if (entry->e_value_block == 0 && entry->e_value_size != 0) {
		uint32_t *value =
		    (uint32_t *)((char *)header + to_le16(entry->e_value_offs));
		for (n = (to_le32(entry->e_value_size) + EXT4_XATTR_ROUND) >>
			 EXT4_XATTR_PAD_BITS;
		     n; n--) {
			hash = (hash << VALUE_HASH_SHIFT) ^
			       (hash >> (8 * sizeof(hash) - VALUE_HASH_SHIFT)) ^
			       to_le32(*value++);
		}
	}
	entry->e_hash = to_le32(hash);
}

#define BLOCK_HASH_SHIFT 16

/*
 * ext4_xattr_rehash()
 *
 * Re-compute the extended attribute hash value after an entry has changed.
 */
static void ext4_xattr_rehash(struct ext4_xattr_header *header,
			      struct ext4_xattr_entry *entry)
{
	struct ext4_xattr_entry *here;
	uint32_t hash = 0;

	ext4_xattr_compute_hash(header, entry);
	here = EXT4_XATTR_ENTRY(header + 1);
	while (!EXT4_XATTR_IS_LAST_ENTRY(here)) {
		if (!here->e_hash) {
			/* Block is not shared if an entry's hash value == 0 */
			hash = 0;
			break;
		}
		hash = (hash << BLOCK_HASH_SHIFT) ^
		       (hash >> (8 * sizeof(hash) - BLOCK_HASH_SHIFT)) ^
		       to_le32(here->e_hash);
		here = EXT4_XATTR_NEXT(here);
	}
	header->h_hash = to_le32(hash);
}

#if CONFIG_META_CSUM_ENABLE
static uint32_t ext4_xattr_block_checksum(struct ext4_inode_ref *inode_ref,
					  ext4_fsblk_t blocknr,
					  struct ext4_xattr_header *header)
{
	uint32_t checksum = 0;
	uint64_t le64_blocknr = blocknr;
	struct ext4_sblock *sb = &inode_ref->fs->sb;

	if (ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM)) {
		uint32_t orig_checksum;

		/* Preparation: temporarily set bg checksum to 0 */
		orig_checksum = header->h_checksum;
		header->h_checksum = 0;
		/* First calculate crc32 checksum against fs uuid */
		checksum =
		    ext4_crc32c(EXT4_CRC32_INIT, sb->uuid, sizeof(sb->uuid));
		/* Then calculate crc32 checksum block number */
		checksum =
		    ext4_crc32c(checksum, &le64_blocknr, sizeof(le64_blocknr));
		/* Finally calculate crc32 checksum against
		 * the entire xattr block */
		checksum =
		    ext4_crc32c(checksum, header, ext4_sb_get_block_size(sb));
		header->h_checksum = orig_checksum;
	}
	return checksum;
}
#else
#define ext4_xattr_block_checksum(...) 0
#endif

static void ext4_xattr_set_block_checksum(struct ext4_inode_ref *inode_ref,
					  ext4_fsblk_t blocknr __unused,
					  struct ext4_xattr_header *header)
{
	struct ext4_sblock *sb = &inode_ref->fs->sb;
	if (!ext4_sb_feature_ro_com(sb, EXT4_FRO_COM_METADATA_CSUM))
		return;

	header->h_checksum =
	    ext4_xattr_block_checksum(inode_ref, blocknr, header);
}

struct xattr_prefix {
	const char *prefix;
	uint8_t name_index;
};

static const struct xattr_prefix prefix_tbl[] = {
    {"user.", EXT4_XATTR_INDEX_USER},
    {"system.posix_acl_access", EXT4_XATTR_INDEX_POSIX_ACL_ACCESS},
    {"system.posix_acl_default", EXT4_XATTR_INDEX_POSIX_ACL_DEFAULT},
    {"trusted.", EXT4_XATTR_INDEX_TRUSTED},
    {"security.", EXT4_XATTR_INDEX_SECURITY},
    {"system.", EXT4_XATTR_INDEX_SYSTEM},
    {"system.richacl", EXT4_XATTR_INDEX_RICHACL},
    {NULL, 0},
};

const char *ext4_extract_xattr_name(const char *full_name, size_t full_name_len,
				    uint8_t *name_index, size_t *name_len,
				    bool *found)
{
	int i;
	ext4_assert(name_index);
	ext4_assert(found);

	*found = false;

	if (!full_name_len) {
		if (name_len)
			*name_len = 0;

		return NULL;
	}

	for (i = 0; prefix_tbl[i].prefix; i++) {
		size_t prefix_len = strlen(prefix_tbl[i].prefix);
		if (full_name_len >= prefix_len &&
		    !memcmp(full_name, prefix_tbl[i].prefix, prefix_len)) {
			bool require_name =
			    prefix_tbl[i].prefix[prefix_len - 1] == '.';
			*name_index = prefix_tbl[i].name_index;
			if (name_len)
				*name_len = full_name_len - prefix_len;

			if (!(full_name_len - prefix_len) && require_name)
				return NULL;

			*found = true;
			if (require_name)
				return full_name + prefix_len;

			return NULL;
		}
	}
	if (name_len)
		*name_len = 0;

	return NULL;
}

const char *ext4_get_xattr_name_prefix(uint8_t name_index,
				       size_t *ret_prefix_len)
{
	int i;

	for (i = 0; prefix_tbl[i].prefix; i++) {
		size_t prefix_len = strlen(prefix_tbl[i].prefix);
		if (prefix_tbl[i].name_index == name_index) {
			if (ret_prefix_len)
				*ret_prefix_len = prefix_len;

			return prefix_tbl[i].prefix;
		}
	}
	if (ret_prefix_len)
		*ret_prefix_len = 0;

	return NULL;
}

static const char ext4_xattr_empty_value;

/**
 * @brief Insert/Remove/Modify the given entry
 *
 * @param i The information of the given EA entry
 * @param s Search context block
 * @param dry_run Do not modify the content of the buffer
 *
 * @return Return EOK when finished, ENOSPC when there is no enough space
 */
static int ext4_xattr_set_entry(struct ext4_xattr_info *i,
				struct ext4_xattr_search *s, bool dry_run)
{
	struct ext4_xattr_entry *last;
	size_t free, min_offs = (char *)s->end - (char *)s->base,
		     name_len = i->name_len;

	/*
	 * If the entry is going to be removed but not found, return 0 to
	 * indicate success.
	 */
	if (!i->value && s->not_found)
		return EOK;

	/* Compute min_offs and last. */
	last = s->first;
	for (; !EXT4_XATTR_IS_LAST_ENTRY(last); last = EXT4_XATTR_NEXT(last)) {
		if (last->e_value_size) {
			size_t offs = to_le16(last->e_value_offs);
			if (offs < min_offs)
				min_offs = offs;
		}
	}

	/* Calculate free space in the block. */
	free = min_offs - ((char *)last - (char *)s->base) - sizeof(uint32_t);
	if (!s->not_found)
		free += EXT4_XATTR_SIZE(s->here->e_value_size) +
			EXT4_XATTR_LEN(s->here->e_name_len);

	if (i->value) {
		/* See whether there is enough space to hold new entry */
		if (free <
		    EXT4_XATTR_SIZE(i->value_len) + EXT4_XATTR_LEN(name_len))
			return ENOSPC;
	}

	/* Return EOK now if we do not intend to modify the content. */
	if (dry_run)
		return EOK;

	/* First remove the old entry's data part */
	if (!s->not_found) {
		size_t value_offs = to_le16(s->here->e_value_offs);
		void *value = (char *)s->base + value_offs;
		void *first_value = (char *)s->base + min_offs;
		size_t value_size =
		    EXT4_XATTR_SIZE(to_le32(s->here->e_value_size));

		if (value_offs) {
			/* Remove the data part. */
			memmove((char *)first_value + value_size, first_value,
				(char *)value - (char *)first_value);

			/* Zero the gap created */
			memset(first_value, 0, value_size);

			/*
			 * Calculate the new min_offs after removal of the old
			 * entry's data part
			 */
			min_offs += value_size;
		}

		/*
		 * Adjust the value offset of entries which has value offset
		 * prior to the s->here. The offset of these entries won't be
		 * shifted if the size of the entry we removed is zero.
		 */
		for (last = s->first; !EXT4_XATTR_IS_LAST_ENTRY(last);
		     last = EXT4_XATTR_NEXT(last)) {
			size_t offs = to_le16(last->e_value_offs);

			/* For zero-value-length entry, offs will be zero. */
			if (offs < value_offs)
				last->e_value_offs = to_le16(offs + value_size);
		}
	}

	/* If caller wants us to insert... */
	if (i->value) {
		size_t value_offs;
		if (i->value_len)
			value_offs = min_offs - EXT4_XATTR_SIZE(i->value_len);
		else
			value_offs = 0;

		if (!s->not_found) {
			struct ext4_xattr_entry *here = s->here;

			/* Reuse the current entry we have got */
			here->e_value_offs = to_le16(value_offs);
			here->e_value_size = to_le32(i->value_len);
		} else {
			/* Insert a new entry */
			last->e_name_len = (uint8_t)name_len;
			last->e_name_index = i->name_index;
			last->e_value_offs = to_le16(value_offs);
			last->e_value_block = 0;
			last->e_value_size = to_le32(i->value_len);
			memcpy(EXT4_XATTR_NAME(last), i->name, name_len);

			/* Set valid last entry indicator */
			*(uint32_t *)EXT4_XATTR_NEXT(last) = 0;

			s->here = last;
		}

		/* Insert the value's part */
		if (value_offs) {
			memcpy((char *)s->base + value_offs, i->value,
			       i->value_len);

			/* Clear the padding bytes if there is */
			if (EXT4_XATTR_SIZE(i->value_len) != i->value_len)
				memset((char *)s->base + value_offs +
					   i->value_len,
				       0, EXT4_XATTR_SIZE(i->value_len) -
					      i->value_len);
		}
	} else {
		size_t shift_offs;

		/* Remove the whole entry */
		shift_offs = (char *)EXT4_XATTR_NEXT(s->here) - (char *)s->here;
		memmove(s->here, EXT4_XATTR_NEXT(s->here),
			(char *)last + sizeof(uint32_t) -
			    (char *)EXT4_XATTR_NEXT(s->here));

		/* Zero the gap created */
		memset((char *)last - shift_offs + sizeof(uint32_t), 0,
		       shift_offs);

		s->here = NULL;
	}

	return EOK;
}

static inline bool ext4_xattr_is_empty(struct ext4_xattr_search *s)
{
	if (!EXT4_XATTR_IS_LAST_ENTRY(s->first))
		return false;

	return true;
}

/**
 * @brief Find the entry according to given information
 *
 * @param i The information of the EA entry to be found,
 * 	    including name_index, name and the length of name
 * @param s Search context block
 */
static void ext4_xattr_find_entry(struct ext4_xattr_info *i,
				  struct ext4_xattr_search *s)
{
	struct ext4_xattr_entry *entry = NULL;

	s->not_found = true;
	s->here = NULL;

	/*
	 * Find the wanted EA entry by simply comparing the namespace,
	 * name and the length of name.
	 */
	for (entry = s->first; !EXT4_XATTR_IS_LAST_ENTRY(entry);
	     entry = EXT4_XATTR_NEXT(entry)) {
		size_t name_len = entry->e_name_len;
		const char *name = EXT4_XATTR_NAME(entry);
		if (name_len == i->name_len &&
		    entry->e_name_index == i->name_index &&
		    !memcmp(name, i->name, name_len)) {
			s->here = entry;
			s->not_found = false;
			i->value_len = to_le32(entry->e_value_size);
			if (i->value_len)
				i->value = (char *)s->base +
					   to_le16(entry->e_value_offs);
			else
				i->value = NULL;

			return;
		}
	}
}

/**
 * @brief Check whether the xattr block's content is valid
 *
 * @param inode_ref Inode reference
 * @param block     The block buffer to be validated
 *
 * @return true if @block is valid, false otherwise.
 */
static bool ext4_xattr_is_block_valid(struct ext4_inode_ref *inode_ref,
				      struct ext4_block *block)
{

	void *base = block->data,
	     *end = block->data + ext4_sb_get_block_size(&inode_ref->fs->sb);
	size_t min_offs = (char *)end - (char *)base;
	struct ext4_xattr_header *header = EXT4_XATTR_BHDR(block);
	struct ext4_xattr_entry *entry = EXT4_XATTR_BFIRST(block);

	/*
	 * Check whether the magic number in the header is correct.
	 */
	if (header->h_magic != to_le32(EXT4_XATTR_MAGIC))
		return false;

	/*
	 * The in-kernel filesystem driver only supports 1 block currently.
	 */
	if (header->h_blocks != to_le32(1))
		return false;

	/*
	 * Check if those entries are maliciously corrupted to inflict harm
	 * upon us.
	 */
	for (; !EXT4_XATTR_IS_LAST_ENTRY(entry);
	     entry = EXT4_XATTR_NEXT(entry)) {
		if (!to_le32(entry->e_value_size) &&
		    to_le16(entry->e_value_offs))
			return false;

		if ((char *)base + to_le16(entry->e_value_offs) +
			to_le32(entry->e_value_size) >
		    (char *)end)
			return false;

		/*
		 * The name length field should also be correct,
		 * also there should be an 4-byte zero entry at the
		 * end.
		 */
		if ((char *)EXT4_XATTR_NEXT(entry) + sizeof(uint32_t) >
		    (char *)end)
			return false;

		if (to_le32(entry->e_value_size)) {
			size_t offs = to_le16(entry->e_value_offs);
			if (offs < min_offs)
				min_offs = offs;
		}
	}
	/*
	 * Entry field and data field do not override each other.
	 */
	if ((char *)base + min_offs < (char *)entry + sizeof(uint32_t))
		return false;

	return true;
}

/**
 * @brief Check whether the inode buffer's content is valid
 *
 * @param inode_ref Inode reference
 *
 * @return true if the inode buffer is valid, false otherwise.
 */
static bool ext4_xattr_is_ibody_valid(struct ext4_inode_ref *inode_ref)
{
	size_t min_offs;
	void *base, *end;
	struct ext4_fs *fs = inode_ref->fs;
	struct ext4_xattr_ibody_header *iheader;
	struct ext4_xattr_entry *entry;
	size_t inode_size = ext4_get16(&fs->sb, inode_size);

	iheader = EXT4_XATTR_IHDR(&fs->sb, inode_ref->inode);
	entry = EXT4_XATTR_IFIRST(iheader);
	base = iheader;
	end = (char *)inode_ref->inode + inode_size;
	min_offs = (char *)end - (char *)base;

	/*
	 * Check whether the magic number in the header is correct.
	 */
	if (iheader->h_magic != to_le32(EXT4_XATTR_MAGIC))
		return false;

	/*
	 * Check if those entries are maliciously corrupted to inflict harm
	 * upon us.
	 */
	for (; !EXT4_XATTR_IS_LAST_ENTRY(entry);
	     entry = EXT4_XATTR_NEXT(entry)) {
		if (!to_le32(entry->e_value_size) &&
		    to_le16(entry->e_value_offs))
			return false;

		if ((char *)base + to_le16(entry->e_value_offs) +
			to_le32(entry->e_value_size) >
		    (char *)end)
			return false;

		/*
		 * The name length field should also be correct,
		 * also there should be an 4-byte zero entry at the
		 * end.
		 */
		if ((char *)EXT4_XATTR_NEXT(entry) + sizeof(uint32_t) >
		    (char *)end)
			return false;

		if (to_le32(entry->e_value_size)) {
			size_t offs = to_le16(entry->e_value_offs);
			if (offs < min_offs)
				min_offs = offs;
		}
	}
	/*
	 * Entry field and data field do not override each other.
	 */
	if ((char *)base + min_offs < (char *)entry + sizeof(uint32_t))
		return false;

	return true;
}

/**
 * @brief An EA entry finder for inode buffer
 */
struct ext4_xattr_finder {
	/**
	 * @brief The information of the EA entry to be find
	 */
	struct ext4_xattr_info i;

	/**
	 * @brief Search context block of the current search
	 */
	struct ext4_xattr_search s;

	/**
	 * @brief Inode reference to the corresponding inode
	 */
	struct ext4_inode_ref *inode_ref;
};

static void ext4_xattr_ibody_initialize(struct ext4_inode_ref *inode_ref)
{
	struct ext4_xattr_ibody_header *header;
	struct ext4_fs *fs = inode_ref->fs;
	size_t extra_isize =
	    ext4_inode_get_extra_isize(&fs->sb, inode_ref->inode);
	size_t inode_size = ext4_get16(&fs->sb, inode_size);
	if (!extra_isize)
		return;

	header = EXT4_XATTR_IHDR(&fs->sb, inode_ref->inode);
	memset(header, 0, inode_size - EXT4_GOOD_OLD_INODE_SIZE - extra_isize);
	header->h_magic = to_le32(EXT4_XATTR_MAGIC);
	inode_ref->dirty = true;
}

/**
 * @brief Initialize a given xattr block
 *
 * @param inode_ref Inode reference
 * @param block xattr block buffer
 */
static void ext4_xattr_block_initialize(struct ext4_inode_ref *inode_ref,
					struct ext4_block *block)
{
	struct ext4_xattr_header *header;
	struct ext4_fs *fs = inode_ref->fs;

	memset(block->data, 0, ext4_sb_get_block_size(&fs->sb));

	header = EXT4_XATTR_BHDR(block);
	header->h_magic = to_le32(EXT4_XATTR_MAGIC);
	header->h_refcount = to_le32(1);
	header->h_blocks = to_le32(1);

	ext4_trans_set_block_dirty(block->buf);
}

static void ext4_xattr_block_init_search(struct ext4_inode_ref *inode_ref,
					 struct ext4_xattr_search *s,
					 struct ext4_block *block)
{
	s->base = block->data;
	s->end = block->data + ext4_sb_get_block_size(&inode_ref->fs->sb);
	s->first = EXT4_XATTR_BFIRST(block);
	s->here = NULL;
	s->not_found = true;
}

/**
 * @brief Find an EA entry inside a xattr block
 *
 * @param inode_ref Inode reference
 * @param finder    The caller-provided finder block with
 * 		    information filled
 * @param block     The block buffer to be looked into
 *
 * @return Return EOK no matter the entry is found or not.
 * 	   If the IO operation or the buffer validation failed,
 * 	   return other value.
 */
static int ext4_xattr_block_find_entry(struct ext4_inode_ref *inode_ref,
				       struct ext4_xattr_finder *finder,
				       struct ext4_block *block)
{
	int ret = EOK;

	/* Initialize the caller-given finder */
	finder->inode_ref = inode_ref;
	memset(&finder->s, 0, sizeof(finder->s));

	if (ret != EOK)
		return ret;

	/* Check the validity of the buffer */
	if (!ext4_xattr_is_block_valid(inode_ref, block))
		return EIO;

	ext4_xattr_block_init_search(inode_ref, &finder->s, block);
	ext4_xattr_find_entry(&finder->i, &finder->s);
	return EOK;
}

/**
 * @brief Find an EA entry inside an inode's extra space
 *
 * @param inode_ref Inode reference
 * @param finder    The caller-provided finder block with
 * 		    information filled
 *
 * @return Return EOK no matter the entry is found or not.
 * 	   If the IO operation or the buffer validation failed,
 * 	   return other value.
 */
static int ext4_xattr_ibody_find_entry(struct ext4_inode_ref *inode_ref,
				       struct ext4_xattr_finder *finder)
{
	struct ext4_fs *fs = inode_ref->fs;
	struct ext4_xattr_ibody_header *iheader;
	size_t extra_isize =
	    ext4_inode_get_extra_isize(&fs->sb, inode_ref->inode);
	size_t inode_size = ext4_get16(&fs->sb, inode_size);

	/* Initialize the caller-given finder */
	finder->inode_ref = inode_ref;
	memset(&finder->s, 0, sizeof(finder->s));

	/*
	 * If there is no extra inode space
	 * set ext4_xattr_ibody_finder::s::not_found to true and return EOK
	 */
	if (!extra_isize) {
		finder->s.not_found = true;
		return EOK;
	}

	/* Check the validity of the buffer */
	if (!ext4_xattr_is_ibody_valid(inode_ref))
		return EIO;

	iheader = EXT4_XATTR_IHDR(&fs->sb, inode_ref->inode);
	finder->s.base = EXT4_XATTR_IFIRST(iheader);
	finder->s.end = (char *)inode_ref->inode + inode_size;
	finder->s.first = EXT4_XATTR_IFIRST(iheader);
	ext4_xattr_find_entry(&finder->i, &finder->s);
	return EOK;
}

/**
 * @brief Try to allocate a block holding EA entries.
 *
 * @param inode_ref Inode reference
 *
 * @return Error code
 */
static int ext4_xattr_try_alloc_block(struct ext4_inode_ref *inode_ref)
{
	int ret = EOK;

	ext4_fsblk_t xattr_block = 0;
	xattr_block =
	    ext4_inode_get_file_acl(inode_ref->inode, &inode_ref->fs->sb);

	/*
	 * Only allocate a xattr block when there is no xattr block
	 * used by the inode.
	 */
	if (!xattr_block) {
		ext4_fsblk_t goal = ext4_fs_inode_to_goal_block(inode_ref);

		ret = ext4_balloc_alloc_block(inode_ref, goal, &xattr_block);
		if (ret != EOK)
			goto Finish;

		ext4_inode_set_file_acl(inode_ref->inode, &inode_ref->fs->sb,
					xattr_block);
	}

Finish:
	return ret;
}

/**
 * @brief Try to free a block holding EA entries.
 *
 * @param inode_ref Inode reference
 *
 * @return Error code
 */
static void ext4_xattr_try_free_block(struct ext4_inode_ref *inode_ref)
{
	ext4_fsblk_t xattr_block;
	xattr_block =
	    ext4_inode_get_file_acl(inode_ref->inode, &inode_ref->fs->sb);
	/*
	 * Free the xattr block used by the inode when there is one.
	 */
	if (xattr_block) {
		ext4_inode_set_file_acl(inode_ref->inode, &inode_ref->fs->sb,
					0);
		ext4_balloc_free_block(inode_ref, xattr_block);
		inode_ref->dirty = true;
	}
}

/**
 * @brief Put a list of EA entries into a caller-provided buffer
 * 	  In order to make sure that @list buffer can fit in the data,
 * 	  the routine should be called twice.
 *
 * @param inode_ref Inode reference
 * @param list A caller-provided buffer to hold a list of EA entries.
 * 	       If list == NULL, list_len will contain the size of
 * 	       the buffer required to hold these entries
 * @param list_len The length of the data written to @list
 * @return Error code
 */
int ext4_xattr_list(struct ext4_inode_ref *inode_ref,
		    struct ext4_xattr_list_entry *list, size_t *list_len)
{
	int ret = EOK;
	size_t buf_len = 0;
	struct ext4_fs *fs = inode_ref->fs;
	struct ext4_xattr_ibody_header *iheader;
	size_t extra_isize =
	    ext4_inode_get_extra_isize(&fs->sb, inode_ref->inode);
	struct ext4_block block;
	bool block_loaded = false;
	ext4_fsblk_t xattr_block = 0;
	struct ext4_xattr_entry *entry;
	struct ext4_xattr_list_entry *list_prev = NULL;
	xattr_block = ext4_inode_get_file_acl(inode_ref->inode, &fs->sb);

	/*
	 * If there is extra inode space and the xattr buffer in the
	 * inode is valid.
	 */
	if (extra_isize && ext4_xattr_is_ibody_valid(inode_ref)) {
		iheader = EXT4_XATTR_IHDR(&fs->sb, inode_ref->inode);
		entry = EXT4_XATTR_IFIRST(iheader);

		/*
		 * The format of the list should be like this:
		 *
		 * name_len indicates the length in bytes of the name
		 * of the EA entry. The string is null-terminated.
		 *
		 * list->name => (char *)(list + 1);
		 * list->next => (void *)((char *)(list + 1) + name_len + 1);
		 */
		for (; !EXT4_XATTR_IS_LAST_ENTRY(entry);
		     entry = EXT4_XATTR_NEXT(entry)) {
			size_t name_len = entry->e_name_len;
			if (list) {
				list->name_index = entry->e_name_index;
				list->name_len = name_len;
				list->name = (char *)(list + 1);
				memcpy(list->name, EXT4_XATTR_NAME(entry),
				       list->name_len);

				if (list_prev)
					list_prev->next = list;

				list_prev = list;
				list = (struct ext4_xattr_list_entry
					    *)(list->name + name_len + 1);
			}

			/*
			 * Size calculation by pointer arithmetics.
			 */
			buf_len +=
			    (char *)((struct ext4_xattr_list_entry *)0 + 1) +
			    name_len + 1 -
			    (char *)(struct ext4_xattr_list_entry *)0;
		}
	}

	/*
	 * If there is a xattr block used by the inode
	 */
	if (xattr_block) {
		ret = ext4_trans_block_get(fs->bdev, &block, xattr_block);
		if (ret != EOK)
			goto out;

		block_loaded = true;

		/*
		 * As we don't allow the content in the block being invalid,
		 * bail out.
		 */
		if (!ext4_xattr_is_block_valid(inode_ref, &block)) {
			ret = EIO;
			goto out;
		}

		entry = EXT4_XATTR_BFIRST(&block);

		/*
		 * The format of the list should be like this:
		 *
		 * name_len indicates the length in bytes of the name
		 * of the EA entry. The string is null-terminated.
		 *
		 * list->name => (char *)(list + 1);
		 * list->next => (void *)((char *)(list + 1) + name_len + 1);
		 *
		 * Same as above actually.
		 */
		for (; !EXT4_XATTR_IS_LAST_ENTRY(entry);
		     entry = EXT4_XATTR_NEXT(entry)) {
			size_t name_len = entry->e_name_len;
			if (list) {
				list->name_index = entry->e_name_index;
				list->name_len = name_len;
				list->name = (char *)(list + 1);
				memcpy(list->name, EXT4_XATTR_NAME(entry),
				       list->name_len);

				if (list_prev)
					list_prev->next = list;

				list_prev = list;
				list = (struct ext4_xattr_list_entry
					    *)(list->name + name_len + 1);
			}

			/*
			 * Size calculation by pointer arithmetics.
			 */
			buf_len +=
			    (char *)((struct ext4_xattr_list_entry *)0 + 1) +
			    name_len + 1 -
			    (char *)(struct ext4_xattr_list_entry *)0;
		}
	}
	if (list_prev)
		list_prev->next = NULL;
out:
	if (ret == EOK && list_len)
		*list_len = buf_len;

	if (block_loaded)
		ext4_block_set(fs->bdev, &block);

	return ret;
}

/**
 * @brief Query EA entry's value with given name-index and name
 *
 * @param inode_ref Inode reference
 * @param name_index Name-index
 * @param name Name of the EA entry to be queried
 * @param name_len Length of name in bytes
 * @param buf Output buffer to hold content
 * @param buf_len Output buffer's length
 * @param data_len The length of data of the EA entry found
 *
 * @return Error code
 */
int ext4_xattr_get(struct ext4_inode_ref *inode_ref, uint8_t name_index,
		   const char *name, size_t name_len, void *buf, size_t buf_len,
		   size_t *data_len)
{
	int ret = EOK;
	struct ext4_xattr_finder ibody_finder;
	struct ext4_xattr_finder block_finder;
	struct ext4_xattr_info i;
	size_t value_len = 0;
	size_t value_offs = 0;
	struct ext4_fs *fs = inode_ref->fs;
	ext4_fsblk_t xattr_block;
	xattr_block = ext4_inode_get_file_acl(inode_ref->inode, &fs->sb);

	i.name_index = name_index;
	i.name = name;
	i.name_len = name_len;
	i.value = 0;
	i.value_len = 0;
	if (data_len)
		*data_len = 0;

	ibody_finder.i = i;
	ret = ext4_xattr_ibody_find_entry(inode_ref, &ibody_finder);
	if (ret != EOK)
		goto out;

	if (!ibody_finder.s.not_found) {
		value_len = to_le32(ibody_finder.s.here->e_value_size);
		value_offs = to_le32(ibody_finder.s.here->e_value_offs);
		if (buf_len && buf) {
			void *data_loc =
			    (char *)ibody_finder.s.base + value_offs;
			memcpy(buf, data_loc,
			       (buf_len < value_len) ? buf_len : value_len);
		}
	} else {
		struct ext4_block block;

		/* Return ENODATA if there is no EA block */
		if (!xattr_block) {
			ret = ENODATA;
			goto out;
		}

		block_finder.i = i;
		ret = ext4_trans_block_get(fs->bdev, &block, xattr_block);
		if (ret != EOK)
			goto out;

		ret = ext4_xattr_block_find_entry(inode_ref, &block_finder,
						  &block);
		if (ret != EOK) {
			ext4_block_set(fs->bdev, &block);
			goto out;
		}

		/* Return ENODATA if entry is not found */
		if (block_finder.s.not_found) {
			ext4_block_set(fs->bdev, &block);
			ret = ENODATA;
			goto out;
		}

		value_len = to_le32(block_finder.s.here->e_value_size);
		value_offs = to_le32(block_finder.s.here->e_value_offs);
		if (buf_len && buf) {
			void *data_loc =
			    (char *)block_finder.s.base + value_offs;
			memcpy(buf, data_loc,
			       (buf_len < value_len) ? buf_len : value_len);
		}

		/*
		 * Free the xattr block buffer returned by
		 * ext4_xattr_block_find_entry.
		 */
		ext4_block_set(fs->bdev, &block);
	}

out:
	if (ret == EOK && data_len)
		*data_len = value_len;

	return ret;
}

/**
 * @brief Try to copy the content of an xattr block to a newly-allocated
 * 	  block. If the operation fails, the block buffer provided by
 * 	  caller will be freed
 *
 * @param inode_ref Inode reference
 * @param block The block buffer reference
 * @param new_block The newly-allocated block buffer reference
 * @param orig_block The block number of @block
 * @param allocated a new block is allocated
 *
 * @return Error code
 */
static int ext4_xattr_copy_new_block(struct ext4_inode_ref *inode_ref,
				     struct ext4_block *block,
				     struct ext4_block *new_block,
				     ext4_fsblk_t *orig_block, bool *allocated)
{
	int ret = EOK;
	ext4_fsblk_t xattr_block = 0;
	struct ext4_xattr_header *header;
	struct ext4_fs *fs = inode_ref->fs;
	header = EXT4_XATTR_BHDR(block);

	if (orig_block)
		*orig_block = block->lb_id;

	if (allocated)
		*allocated = false;

	/* Only do copy when a block is referenced by more than one inode. */
	if (to_le32(header->h_refcount) > 1) {
		ext4_fsblk_t goal = ext4_fs_inode_to_goal_block(inode_ref);

		/* Allocate a new block to be used by this inode */
		ret = ext4_balloc_alloc_block(inode_ref, goal, &xattr_block);
		if (ret != EOK)
			goto out;

		ret = ext4_trans_block_get(fs->bdev, new_block, xattr_block);
		if (ret != EOK)
			goto out;

		/* Copy the content of the whole block */
		memcpy(new_block->data, block->data,
		       ext4_sb_get_block_size(&inode_ref->fs->sb));

		/*
		 * Decrement the reference count of the original xattr block
		 * by one
		 */
		header->h_refcount = to_le32(to_le32(header->h_refcount) - 1);
		ext4_trans_set_block_dirty(block->buf);
		ext4_trans_set_block_dirty(new_block->buf);

		header = EXT4_XATTR_BHDR(new_block);
		header->h_refcount = to_le32(1);

		if (allocated)
			*allocated = true;
	}
out:
	if (xattr_block) {
		if (ret != EOK)
			ext4_balloc_free_block(inode_ref, xattr_block);
		else {
			/*
			 * Modify the in-inode pointer to point to the new xattr block
			 */
			ext4_inode_set_file_acl(inode_ref->inode, &fs->sb, xattr_block);
			inode_ref->dirty = true;
		}
	}

	return ret;
}

/**
 * @brief Given an EA entry's name, remove the EA entry
 *
 * @param inode_ref Inode reference
 * @param name_index Name-index
 * @param name Name of the EA entry to be removed
 * @param name_len Length of name in bytes
 *
 * @return Error code
 */
int ext4_xattr_remove(struct ext4_inode_ref *inode_ref, uint8_t name_index,
		      const char *name, size_t name_len)
{
	int ret = EOK;
	struct ext4_block block;
	struct ext4_xattr_finder ibody_finder;
	struct ext4_xattr_finder block_finder;
	bool use_block = false;
	bool block_loaded = false;
	struct ext4_xattr_info i;
	struct ext4_fs *fs = inode_ref->fs;
	ext4_fsblk_t xattr_block;

	xattr_block = ext4_inode_get_file_acl(inode_ref->inode, &fs->sb);

	i.name_index = name_index;
	i.name = name;
	i.name_len = name_len;
	i.value = NULL;
	i.value_len = 0;

	ibody_finder.i = i;
	block_finder.i = i;

	ret = ext4_xattr_ibody_find_entry(inode_ref, &ibody_finder);
	if (ret != EOK)
		goto out;

	if (ibody_finder.s.not_found && xattr_block) {
		ret = ext4_trans_block_get(fs->bdev, &block, xattr_block);
		if (ret != EOK)
			goto out;

		block_loaded = true;
		block_finder.i = i;
		ret = ext4_xattr_block_find_entry(inode_ref, &block_finder,
						  &block);
		if (ret != EOK)
			goto out;

		/* Return ENODATA if entry is not found */
		if (block_finder.s.not_found) {
			ret = ENODATA;
			goto out;
		}
		use_block = true;
	}

	if (use_block) {
		bool allocated = false;
		struct ext4_block new_block;

		/*
		 * There will be no effect when the xattr block is only referenced
		 * once.
		 */
		ret = ext4_xattr_copy_new_block(inode_ref, &block, &new_block,
						&xattr_block, &allocated);
		if (ret != EOK)
			goto out;

		if (!allocated) {
			/* Prevent double-freeing */
			block_loaded = false;
			new_block = block;
		}

		ret = ext4_xattr_block_find_entry(inode_ref, &block_finder,
						  &new_block);
		if (ret != EOK)
			goto out;

		/* Now remove the entry */
		ext4_xattr_set_entry(&i, &block_finder.s, false);

		if (ext4_xattr_is_empty(&block_finder.s)) {
			ext4_block_set(fs->bdev, &new_block);
			ext4_xattr_try_free_block(inode_ref);
		} else {
			struct ext4_xattr_header *header =
			    EXT4_XATTR_BHDR(&new_block);
			header = EXT4_XATTR_BHDR(&new_block);
			ext4_assert(block_finder.s.first);
			ext4_xattr_rehash(header, block_finder.s.first);
			ext4_xattr_set_block_checksum(inode_ref,
						      block.lb_id,
						      header);

			ext4_trans_set_block_dirty(new_block.buf);
			ext4_block_set(fs->bdev, &new_block);
		}

	} else {
		/* Now remove the entry */
		ext4_xattr_set_entry(&i, &block_finder.s, false);
		inode_ref->dirty = true;
	}
out:
	if (block_loaded)
		ext4_block_set(fs->bdev, &block);

	return ret;
}

/**
 * @brief Insert/overwrite an EA entry into/in a xattr block
 *
 * @param inode_ref Inode reference
 * @param i The information of the given EA entry
 *
 * @return Error code
 */
static int ext4_xattr_block_set(struct ext4_inode_ref *inode_ref,
				struct ext4_xattr_info *i,
				bool no_insert)
{
	int ret = EOK;
	bool allocated = false;
	struct ext4_fs *fs = inode_ref->fs;
	struct ext4_block block, new_block;
	ext4_fsblk_t orig_xattr_block;

	orig_xattr_block = ext4_inode_get_file_acl(inode_ref->inode, &fs->sb);

	ext4_assert(i->value);
	if (!orig_xattr_block) {
		struct ext4_xattr_search s;
		struct ext4_xattr_header *header;

		/* If insertion of new entry is not allowed... */
		if (no_insert) {
			ret = ENODATA;
			goto out;
		}

		ret = ext4_xattr_try_alloc_block(inode_ref);
		if (ret != EOK)
			goto out;

		orig_xattr_block =
		    ext4_inode_get_file_acl(inode_ref->inode, &fs->sb);
		ret = ext4_trans_block_get(fs->bdev, &block, orig_xattr_block);
		if (ret != EOK) {
			ext4_xattr_try_free_block(inode_ref);
			goto out;
		}

		ext4_xattr_block_initialize(inode_ref, &block);
		ext4_xattr_block_init_search(inode_ref, &s, &block);

		ret = ext4_xattr_set_entry(i, &s, false);
		if (ret == EOK) {
			header = EXT4_XATTR_BHDR(&block);

			ext4_assert(s.here);
			ext4_assert(s.first);
			ext4_xattr_compute_hash(header, s.here);
			ext4_xattr_rehash(header, s.first);
			ext4_xattr_set_block_checksum(inode_ref,
						      block.lb_id,
						      header);
			ext4_trans_set_block_dirty(block.buf);
		}
		ext4_block_set(fs->bdev, &block);
		if (ret != EOK)
			ext4_xattr_try_free_block(inode_ref);

	} else {
		struct ext4_xattr_finder finder;
		struct ext4_xattr_header *header;
		finder.i = *i;
		ret = ext4_trans_block_get(fs->bdev, &block, orig_xattr_block);
		if (ret != EOK)
			goto out;

		header = EXT4_XATTR_BHDR(&block);

		/*
		 * Consider the following case when insertion of new
		 * entry is not allowed
		 */
		if (to_le32(header->h_refcount) > 1 && no_insert) {
			/*
			 * There are other people referencing the
			 * same xattr block
			 */
			ret = ext4_xattr_block_find_entry(inode_ref, &finder, &block);
			if (ret != EOK) {
				ext4_block_set(fs->bdev, &block);
				goto out;
			}
			if (finder.s.not_found) {
				ext4_block_set(fs->bdev, &block);
				ret = ENODATA;
				goto out;
			}
		}

		/*
		 * There will be no effect when the xattr block is only referenced
		 * once.
		 */
		ret = ext4_xattr_copy_new_block(inode_ref, &block, &new_block,
						&orig_xattr_block, &allocated);
		if (ret != EOK) {
			ext4_block_set(fs->bdev, &block);
			goto out;
		}

		if (allocated) {
			ext4_block_set(fs->bdev, &block);
			new_block = block;
		}

		ret = ext4_xattr_block_find_entry(inode_ref, &finder, &block);
		if (ret != EOK) {
			ext4_block_set(fs->bdev, &block);
			goto out;
		}

		ret = ext4_xattr_set_entry(i, &finder.s, false);
		if (ret == EOK) {
			header = EXT4_XATTR_BHDR(&block);

			ext4_assert(finder.s.here);
			ext4_assert(finder.s.first);
			ext4_xattr_compute_hash(header, finder.s.here);
			ext4_xattr_rehash(header, finder.s.first);
			ext4_xattr_set_block_checksum(inode_ref,
						      block.lb_id,
						      header);
			ext4_trans_set_block_dirty(block.buf);
		}
		ext4_block_set(fs->bdev, &block);
	}
out:
	return ret;
}

/**
 * @brief Remove an EA entry from a xattr block
 *
 * @param inode_ref Inode reference
 * @param i The information of the given EA entry
 *
 * @return Error code
 */
static int ext4_xattr_block_remove(struct ext4_inode_ref *inode_ref,
				   struct ext4_xattr_info *i)
{
	int ret = EOK;
	bool allocated = false;
	const void *value = i->value;
	struct ext4_fs *fs = inode_ref->fs;
	struct ext4_xattr_finder finder;
	struct ext4_block block, new_block;
	struct ext4_xattr_header *header;
	ext4_fsblk_t orig_xattr_block;
	orig_xattr_block = ext4_inode_get_file_acl(inode_ref->inode, &fs->sb);

	ext4_assert(orig_xattr_block);
	ret = ext4_trans_block_get(fs->bdev, &block, orig_xattr_block);
	if (ret != EOK)
		goto out;

	/*
	 * There will be no effect when the xattr block is only referenced
	 * once.
	 */
	ret = ext4_xattr_copy_new_block(inode_ref, &block, &new_block,
					&orig_xattr_block, &allocated);
	if (ret != EOK) {
		ext4_block_set(fs->bdev, &block);
		goto out;
	}

	if (allocated) {
		ext4_block_set(fs->bdev, &block);
		block = new_block;
	}

	ext4_xattr_block_find_entry(inode_ref, &finder, &block);

	if (!finder.s.not_found) {
		i->value = NULL;
		ret = ext4_xattr_set_entry(i, &finder.s, false);
		i->value = value;

		header = EXT4_XATTR_BHDR(&block);
		ext4_assert(finder.s.first);
		ext4_xattr_rehash(header, finder.s.first);
		ext4_xattr_set_block_checksum(inode_ref,
					      block.lb_id,
					      header);
		ext4_trans_set_block_dirty(block.buf);
	}

	ext4_block_set(fs->bdev, &block);
out:
	return ret;
}

/**
 * @brief Insert an EA entry into a given inode reference
 *
 * @param inode_ref Inode reference
 * @param name_index Name-index
 * @param name Name of the EA entry to be inserted
 * @param name_len Length of name in bytes
 * @param value Input buffer to hold content
 * @param value_len Length of input content
 *
 * @return Error code
 */
int ext4_xattr_set(struct ext4_inode_ref *inode_ref, uint8_t name_index,
		   const char *name, size_t name_len, const void *value,
		   size_t value_len)
{
	int ret = EOK;
	struct ext4_fs *fs = inode_ref->fs;
	struct ext4_xattr_finder ibody_finder;
	struct ext4_xattr_info i;
	bool block_found = false;
	ext4_fsblk_t orig_xattr_block;
	size_t extra_isize =
	    ext4_inode_get_extra_isize(&fs->sb, inode_ref->inode);

	i.name_index = name_index;
	i.name = name;
	i.name_len = name_len;
	i.value = (value_len) ? value : &ext4_xattr_empty_value;
	i.value_len = value_len;

	ibody_finder.i = i;

	orig_xattr_block = ext4_inode_get_file_acl(inode_ref->inode, &fs->sb);

	/*
	 * Even if entry is not found, search context block inside the
	 * finder is still valid and can be used to insert entry.
	 */
	ret = ext4_xattr_ibody_find_entry(inode_ref, &ibody_finder);
	if (ret != EOK) {
		ext4_xattr_ibody_initialize(inode_ref);
		ext4_xattr_ibody_find_entry(inode_ref, &ibody_finder);
	}

	if (ibody_finder.s.not_found) {
		if (orig_xattr_block) {
			block_found = true;
			ret = ext4_xattr_block_set(inode_ref, &i, true);
			if (ret == ENOSPC)
				goto try_insert;
			else if (ret == ENODATA)
				goto try_insert;
			else if (ret != EOK)
				goto out;

		} else
			goto try_insert;

	} else {
	try_insert:
		/* Only try to set entry in ibody if inode is sufficiently large */
		if (extra_isize)
			ret = ext4_xattr_set_entry(&i, &ibody_finder.s, false);
		else
			ret = ENOSPC;

		if (ret == ENOSPC) {
			if (!block_found) {
				ret = ext4_xattr_block_set(inode_ref, &i, false);
				ibody_finder.i.value = NULL;
				ext4_xattr_set_entry(&ibody_finder.i,
						     &ibody_finder.s, false);
				inode_ref->dirty = true;
			}

		} else if (ret == EOK) {
			if (block_found)
				ret = ext4_xattr_block_remove(inode_ref, &i);

			inode_ref->dirty = true;
		}
	}

out:
	return ret;
}

#endif

/**
 * @}
 */