/*
 * Copyright (c) 2012 Frantisek Princ
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/** @addtogroup libext4
 * @{
 */ 

/**
 * @file	libext4_directory.c
 * @brief	Ext4 directory structure operations.
 */

#include <byteorder.h>
#include <errno.h>
#include <malloc.h>
#include <string.h>
#include "libext4.h"


/** Get i-node number from directory entry.
 *
 * @param de 	directory entry
 * @return		i-node number
 */
uint32_t ext4_directory_entry_ll_get_inode(ext4_directory_entry_ll_t *de)
{
	return uint32_t_le2host(de->inode);
}

/** Set i-node number to directory entry.
 *
 * @param de 	directory entry
 * @param inode	i-node number
 */
void ext4_directory_entry_ll_set_inode(ext4_directory_entry_ll_t *de,
		uint32_t inode)
{
	de->inode = host2uint32_t_le(inode);
}

/** Get directory entry length.
 *
 * @param de 	directory entry
 * @return		entry length
 */
uint16_t ext4_directory_entry_ll_get_entry_length(
		ext4_directory_entry_ll_t *de)
{
	return uint16_t_le2host(de->entry_length);
}

/** Set directory entry length.
 *
 * @param de 		directory entry
 * @param length	entry length
 */

void ext4_directory_entry_ll_set_entry_length(ext4_directory_entry_ll_t *de,
		uint16_t length)
{
	de->entry_length = host2uint16_t_le(length);
}

/** Get directory entry name length.
 *
 * @param sb	superblock
 * @param de 	directory entry
 * @return		entry name length
 */
uint16_t ext4_directory_entry_ll_get_name_length(
    ext4_superblock_t *sb, ext4_directory_entry_ll_t *de)
{
	if (ext4_superblock_get_rev_level(sb) == 0 &&
	    ext4_superblock_get_minor_rev_level(sb) < 5) {

		return ((uint16_t)de->name_length_high) << 8 |
			    ((uint16_t)de->name_length);

	}
	return de->name_length;

}

/** Set directory entry name length.
 *
 * @param sb		superblock
 * @param de 		directory entry
 * @param length	entry name length
 */
void ext4_directory_entry_ll_set_name_length(ext4_superblock_t *sb,
		ext4_directory_entry_ll_t *de, uint16_t length)
{
	de->name_length = (length << 8) >> 8;

	if (ext4_superblock_get_rev_level(sb) == 0 &&
		    ext4_superblock_get_minor_rev_level(sb) < 5) {

		de->name_length_high = length >> 8;
	}
}

/** Get i-node type of directory entry.
 *
 * @param sb	superblock
 * @param de 	directory entry
 * @return 		i-node type (file, dir, etc.)
 */
uint8_t ext4_directory_entry_ll_get_inode_type(
		ext4_superblock_t *sb, ext4_directory_entry_ll_t *de)
{
	if (ext4_superblock_get_rev_level(sb) > 0 ||
		    ext4_superblock_get_minor_rev_level(sb) >= 5) {

			return de->inode_type;
	}

	return EXT4_DIRECTORY_FILETYPE_UNKNOWN;

}

/** Set i-node type of directory entry.
 *
 * @param sb	superblock
 * @param de 	directory entry
 * @param type 	i-node type (file, dir, etc.)
 */
void ext4_directory_entry_ll_set_inode_type(
		ext4_superblock_t *sb, ext4_directory_entry_ll_t *de, uint8_t type)
{
	if (ext4_superblock_get_rev_level(sb) > 0 ||
			ext4_superblock_get_minor_rev_level(sb) >= 5) {

		de->inode_type = type;
	}

	/* else do nothing */

}

static int ext4_directory_iterator_seek(
		ext4_directory_iterator_t *, aoff64_t);
static int ext4_directory_iterator_set(
		ext4_directory_iterator_t *, uint32_t);


/** Initialize directory iterator.
 *
 * Set position to the first valid entry from the required position.
 *
 * @param it			pointer to iterator to be initialized
 * @param inode_ref		directory i-node
 * @param pos			position to start reading entries from
 * @return				error code
 */
int ext4_directory_iterator_init(ext4_directory_iterator_t *it,
		ext4_inode_ref_t *inode_ref, aoff64_t pos)
{
	it->inode_ref = inode_ref;
	it->current = NULL;
	it->current_offset = 0;
	it->current_block = NULL;

	return ext4_directory_iterator_seek(it, pos);
}

/** Jump to the next valid entry
 *
 * @param it	initialized iterator
 * @return 		error code
 */
int ext4_directory_iterator_next(ext4_directory_iterator_t *it)
{
	uint16_t skip;

	assert(it->current != NULL);

	skip = ext4_directory_entry_ll_get_entry_length(it->current);

	return ext4_directory_iterator_seek(it, it->current_offset + skip);
}

/** Seek to next valid directory entry.
 *
 * Here can be jumped to the next data block.
 *
 * @param it	initialized iterator
 * @param pos	position of the next entry
 * @return		error code
 */
int ext4_directory_iterator_seek(ext4_directory_iterator_t *it, aoff64_t pos)
{
	int rc;

	uint64_t size = ext4_inode_get_size(
			it->inode_ref->fs->superblock, it->inode_ref->inode);

	/* The iterator is not valid until we seek to the desired position */
	it->current = NULL;

	/* Are we at the end? */
	if (pos >= size) {
		if (it->current_block) {
			rc = block_put(it->current_block);
			it->current_block = NULL;
			if (rc != EOK) {
				return rc;
			}
		}

		it->current_offset = pos;
		return EOK;
	}

	/* Compute next block address */
	uint32_t block_size = ext4_superblock_get_block_size(
			it->inode_ref->fs->superblock);
	aoff64_t current_block_idx = it->current_offset / block_size;
	aoff64_t next_block_idx = pos / block_size;

	/* If we don't have a block or are moving accross block boundary,
	 * we need to get another block
	 */
	if (it->current_block == NULL || current_block_idx != next_block_idx) {
		if (it->current_block) {
			rc = block_put(it->current_block);
			it->current_block = NULL;
			if (rc != EOK) {
				return rc;
			}
		}

		uint32_t next_block_phys_idx;
		rc = ext4_filesystem_get_inode_data_block_index(it->inode_ref,
				next_block_idx, &next_block_phys_idx);
		if (rc != EOK) {
			return rc;
		}

		rc = block_get(&it->current_block, it->inode_ref->fs->device,
				next_block_phys_idx, BLOCK_FLAGS_NONE);
		if (rc != EOK) {
			it->current_block = NULL;
			return rc;
		}
	}

	it->current_offset = pos;

	return ext4_directory_iterator_set(it, block_size);
}

/** Do some checks before returning iterator.
 *
 * @param it			iterator to be checked
 * @param block_size 	size of data block
 * @return				error code
 */
static int ext4_directory_iterator_set(ext4_directory_iterator_t *it,
    uint32_t block_size)
{

	it->current = NULL;

	uint32_t offset_in_block = it->current_offset % block_size;

	/* Ensure proper alignment */
	if ((offset_in_block % 4) != 0) {
		return EIO;
	}

	/* Ensure that the core of the entry does not overflow the block */
	if (offset_in_block > block_size - 8) {
		return EIO;
	}

	ext4_directory_entry_ll_t *entry = it->current_block->data + offset_in_block;

	/* Ensure that the whole entry does not overflow the block */
	uint16_t length = ext4_directory_entry_ll_get_entry_length(entry);
	if (offset_in_block + length > block_size) {
		return EIO;
	}

	/* Ensure the name length is not too large */
	if (ext4_directory_entry_ll_get_name_length(it->inode_ref->fs->superblock,
	    entry) > length-8) {
		return EIO;
	}

	/* Everything OK - "publish" the entry */
	it->current = entry;
	return EOK;
}


/** Uninitialize directory iterator.
 *
 * Release all allocated structures.
 *
 * @param it	iterator to be finished
 * @return		error code
 */
int ext4_directory_iterator_fini(ext4_directory_iterator_t *it)
{
	int rc;

	it->inode_ref = NULL;
	it->current = NULL;

	if (it->current_block) {
		rc = block_put(it->current_block);
		if (rc != EOK) {
			return rc;
		}
	}

	return EOK;
}

/**	Write directory entry to concrete data block.
 *
 * @param sb		superblock
 * @param entry		pointer to entry to be written
 * @param entry_len	lenght of new entry
 * @param child		child i-node to be written to new entry
 * @param name		name of the new entry
 * @param name_len	length of entry name
 */
void ext4_directory_write_entry(ext4_superblock_t *sb,
		ext4_directory_entry_ll_t *entry, uint16_t entry_len,
		ext4_inode_ref_t *child, const char *name, size_t name_len)
{

	/* Check maximum entry length */
	uint32_t block_size = ext4_superblock_get_block_size(sb);
	assert(entry_len <= block_size);

	/* Set basic attributes */
	ext4_directory_entry_ll_set_inode(entry, child->index);
	ext4_directory_entry_ll_set_entry_length(entry, entry_len);
	ext4_directory_entry_ll_set_name_length(sb, entry, name_len);

	/* Write name */
	memcpy(entry->name, name, name_len);

	/* Set type of entry */
	if (ext4_inode_is_type(sb, child->inode, EXT4_INODE_MODE_DIRECTORY)) {
		ext4_directory_entry_ll_set_inode_type(
				sb, entry, EXT4_DIRECTORY_FILETYPE_DIR);
	} else {
		ext4_directory_entry_ll_set_inode_type(
				sb, entry, EXT4_DIRECTORY_FILETYPE_REG_FILE);
	}

}

/** Add new entry to the directory.
 *
 * @param parent	directory i-node
 * @param name		name of new entry
 * @param child		i-node to be referenced from new entry
 * @return			error code
 */
int ext4_directory_add_entry(ext4_inode_ref_t * parent,
		const char *name, ext4_inode_ref_t *child)
{
	int rc;

	ext4_filesystem_t *fs = parent->fs;

	/* Index adding (if allowed) */
	if (ext4_superblock_has_feature_compatible(fs->superblock, EXT4_FEATURE_COMPAT_DIR_INDEX) &&
			ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {

		rc = ext4_directory_dx_add_entry(parent, child, name);

		/* Check if index is not corrupted */
		if (rc != EXT4_ERR_BAD_DX_DIR) {

			if (rc != EOK) {
				return rc;
			}

			return EOK;
		}

		/* Needed to clear dir index flag if corrupted */
		ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
		parent->dirty = true;

		EXT4FS_DBG("index is corrupted - doing linear algorithm, index flag cleared");
	}

	/* Linear algorithm */

	uint32_t iblock = 0, fblock = 0;
	uint32_t block_size = ext4_superblock_get_block_size(fs->superblock);
	uint32_t inode_size = ext4_inode_get_size(fs->superblock, parent->inode);
	uint32_t total_blocks = inode_size / block_size;

	uint32_t name_len = strlen(name);

	/* Find block, where is space for new entry and try to add */
	bool success = false;
	for (iblock = 0; iblock < total_blocks; ++iblock) {

		rc = ext4_filesystem_get_inode_data_block_index(parent, iblock, &fblock);
		if (rc != EOK) {
			return rc;
		}

		block_t *block;
		rc = block_get(&block, fs->device, fblock, BLOCK_FLAGS_NONE);
		if (rc != EOK) {
			return rc;
		}

		/* If adding is successful, function can finish */
		rc = ext4_directory_try_insert_entry(fs->superblock, block, child, name, name_len);
		if (rc == EOK) {
			success = true;
		}

		rc = block_put(block);
		if (rc != EOK) {
			return rc;
		}

		if (success) {
			return EOK;
		}
	}

	/* No free block found - needed to allocate next data block */

	iblock = 0;
	fblock = 0;
	rc = ext4_filesystem_append_inode_block(parent, &fblock, &iblock);
	if (rc != EOK) {
		return rc;
	}

	/* Load new block */
	block_t *new_block;
	rc = block_get(&new_block, fs->device, fblock, BLOCK_FLAGS_NOREAD);
	if (rc != EOK) {
		return rc;
	}

	/* Fill block with zeroes */
	memset(new_block->data, 0, block_size);
	ext4_directory_entry_ll_t *block_entry = new_block->data;
	ext4_directory_write_entry(fs->superblock, block_entry, block_size, child, name, name_len);

	/* Save new block */
	new_block->dirty = true;
	rc = block_put(new_block);
	if (rc != EOK) {
		return rc;
	}

	return EOK;
}

/** Find directory entry with passed name.
 *
 * @param result	result structure to be returned if entry found
 * @param parent	directory i-node
 * @param name		name of entry to be found
 * @return 			error code
 */
int ext4_directory_find_entry(ext4_directory_search_result_t *result,
		ext4_inode_ref_t *parent, const char *name)
{
	int rc;
	uint32_t name_len = strlen(name);

	ext4_superblock_t *sb = parent->fs->superblock;

	/* Index search */
	if (ext4_superblock_has_feature_compatible(sb, EXT4_FEATURE_COMPAT_DIR_INDEX) &&
			ext4_inode_has_flag(parent->inode, EXT4_INODE_FLAG_INDEX)) {

		rc = ext4_directory_dx_find_entry(result, parent, name_len, name);

		/* Check if index is not corrupted */
		if (rc != EXT4_ERR_BAD_DX_DIR) {

			if (rc != EOK) {
				return rc;
			}
			return EOK;
		}

		/* Needed to clear dir index flag if corrupted */
		ext4_inode_clear_flag(parent->inode, EXT4_INODE_FLAG_INDEX);
		parent->dirty = true;

		EXT4FS_DBG("index is corrupted - doing linear search");
	}

	/* Linear algorithm */

	uint32_t iblock, fblock;
	uint32_t block_size = ext4_superblock_get_block_size(sb);
	uint32_t inode_size = ext4_inode_get_size(sb, parent->inode);
	uint32_t total_blocks = inode_size / block_size;

	/* Walk through all data blocks */
	for (iblock = 0; iblock < total_blocks; ++iblock) {

		/* Load block address */
		rc = ext4_filesystem_get_inode_data_block_index(parent, iblock, &fblock);
		if (rc != EOK) {
			return rc;
		}

		/* Load data block */
		block_t *block;
		rc = block_get(&block, parent->fs->device, fblock, BLOCK_FLAGS_NONE);
		if (rc != EOK) {
			return rc;
		}

		/* Try to find entry in block */
		ext4_directory_entry_ll_t *res_entry;
		rc = ext4_directory_find_in_block(block, sb, name_len, name, &res_entry);
		if (rc == EOK) {
			result->block = block;
			result->dentry = res_entry;
			return EOK;
		}

		/* Entry not found - put block and continue to the next block */

		rc = block_put(block);
		if (rc != EOK) {
			return rc;
		}
	}

	/* Entry was not found */

	result->block = NULL;
	result->dentry =  NULL;

	return ENOENT;
}


/** Remove directory entry.
 *
 * @param parent	directory i-node
 * @param name		name of the entry to be removed
 * @return			error code
 */
int ext4_directory_remove_entry(ext4_inode_ref_t *parent, const char *name)
{
	int rc;

	/* Check if removing from directory */
	if (!ext4_inode_is_type(parent->fs->superblock, parent->inode,
	    EXT4_INODE_MODE_DIRECTORY)) {
		return ENOTDIR;
	}

	/* Try to find entry */
	ext4_directory_search_result_t result;
	rc  = ext4_directory_find_entry(&result, parent, name);
	if (rc != EOK) {
		return rc;
	}

	/* Invalidate entry */
	ext4_directory_entry_ll_set_inode(result.dentry, 0);

	/* Store entry position in block */
	uint32_t pos = (void *)result.dentry - result.block->data;

	/* If entry is not the first in block, it must be merged
	 * with previous entry
	 */
	if (pos != 0) {

		uint32_t offset = 0;

		/* Start from the first entry in block */
		ext4_directory_entry_ll_t *tmp_dentry = result.block->data;
		uint16_t tmp_dentry_length =
				ext4_directory_entry_ll_get_entry_length(tmp_dentry);

		/* Find direct predecessor of removed entry */
		while ((offset + tmp_dentry_length) < pos) {
			offset += ext4_directory_entry_ll_get_entry_length(tmp_dentry);
			tmp_dentry = result.block->data + offset;
			tmp_dentry_length =
					ext4_directory_entry_ll_get_entry_length(tmp_dentry);
		}

		assert(tmp_dentry_length + offset == pos);

		/* Add to removed entry length to predecessor's length */
		uint16_t del_entry_length =
				ext4_directory_entry_ll_get_entry_length(result.dentry);
		ext4_directory_entry_ll_set_entry_length(tmp_dentry,
				tmp_dentry_length + del_entry_length);

	}

	result.block->dirty = true;

	return ext4_directory_destroy_result(&result);
}

/** Try to insert entry to concrete data block.
 *
 * @param sb			superblock
 * @param target_block	block to try to insert entry to
 * @param child			child i-node to be inserted by new entry
 * @param name			name of the new entry
 * @param name_len		length of the new entry name
 * @return				error code
 */
int ext4_directory_try_insert_entry(ext4_superblock_t *sb,
		block_t *target_block, ext4_inode_ref_t *child,
		const char *name, uint32_t name_len)
{
	/* Compute required length entry and align it to 4 bytes */
   	uint32_t block_size = ext4_superblock_get_block_size(sb);
   	uint16_t required_len = sizeof(ext4_fake_directory_entry_t) + name_len;
   	if ((required_len % 4) != 0) {
   		required_len += 4 - (required_len % 4);
   	}

   	/* Initialize pointers, stop means to upper bound */
   	ext4_directory_entry_ll_t *dentry = target_block->data;
   	ext4_directory_entry_ll_t *stop = target_block->data + block_size;

   	/* Walk through the block and check for invalid entries
   	 * or entries with free space for new entry
   	 */
   	while (dentry < stop) {

   		uint32_t inode = ext4_directory_entry_ll_get_inode(dentry);
   		uint16_t rec_len = ext4_directory_entry_ll_get_entry_length(dentry);

   		/* If invalid and large enough entry, use it */
   		if ((inode == 0) && (rec_len >= required_len)) {
   			ext4_directory_write_entry(sb, dentry, rec_len, child, name, name_len);
   			target_block->dirty = true;
   			return EOK;
   		}

   		/* Valid entry, try to split it */
   		if (inode != 0) {
   			uint16_t used_name_len =
   					ext4_directory_entry_ll_get_name_length(sb, dentry);

   			uint16_t used_space =
   					sizeof(ext4_fake_directory_entry_t) + used_name_len;
   			if ((used_name_len % 4) != 0) {
   				used_space += 4 - (used_name_len % 4);
   			}
   			uint16_t free_space = rec_len - used_space;

   			/* There is free space for new entry */
   			if (free_space >= required_len) {

   				/* Cut tail of current entry */
   				ext4_directory_entry_ll_set_entry_length(dentry, used_space);
   				ext4_directory_entry_ll_t *new_entry =
   						(void *)dentry + used_space;
   				ext4_directory_write_entry(sb, new_entry,
   						free_space, child, name, name_len);

   				target_block->dirty = true;
				return EOK;
   			}
   		}

   		/* Jump to the next entry */
   		dentry = (void *)dentry + rec_len;
   	}

   	/* No free space found for new entry */

   	return ENOSPC;
}

/** Try to find entry in block by name.
 *
 * @param block		block containing entries
 * @param sb		superblock
 * @param name_len	length of entry name
 * @param name		name of entry to be found
 * @param res_entry	output pointer to found entry, NULL if not found
 * @return			error code
 */
int ext4_directory_find_in_block(block_t *block,
		ext4_superblock_t *sb, size_t name_len, const char *name,
		ext4_directory_entry_ll_t **res_entry)
{
	/* Start from the first entry in block */
	ext4_directory_entry_ll_t *dentry = (ext4_directory_entry_ll_t *)block->data;
	/*Set upper bound for cycling */
	uint8_t *addr_limit = block->data + ext4_superblock_get_block_size(sb);

	/* Walk through the block and check entries */
	while ((uint8_t *)dentry < addr_limit) {

		/* Termination condition */
		if ((uint8_t*) dentry + name_len > addr_limit) {
			break;
		}

		/* Valid entry - check it */
		if (dentry->inode != 0) {

			/* For more effectivity compare firstly only lengths */
			if (name_len == ext4_directory_entry_ll_get_name_length(sb, dentry)) {
				/* Compare names */
				if (bcmp((uint8_t *)name, dentry->name, name_len) == 0) {
					*res_entry = dentry;
					return EOK;
				}
			}
		}

		uint16_t dentry_len = ext4_directory_entry_ll_get_entry_length(dentry);

		/* Corrupted entry */
		if (dentry_len == 0) {
			return EINVAL;
		}

		/* Jump to next entry */
		dentry = (ext4_directory_entry_ll_t *)((uint8_t *)dentry + dentry_len);
	}

	/* Entry not found */
	return ENOENT;
}

/** Simple function to release allocated data from result.
 *
 * @param result	search result to destroy
 * @return			error code
 */
int ext4_directory_destroy_result(ext4_directory_search_result_t *result)
{
	if (result->block) {
		return block_put(result->block);
	}

	return EOK;
}

/**
 * @}
 */