/*
 * Copyright (c) 2008 Jakub Jermar
 * Copyright (c) 2011 Oleg Romanenko
 * 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 exfat
 * @{
 */

/**
 * @file	exfat_fat.c
 * @brief	Functions that manipulate the File Allocation Table.
 */

#include "exfat_fat.h"
#include "exfat_bitmap.h"
#include "exfat.h"
#include "../../vfs/vfs.h"
#include <libfs.h>
#include <block.h>
#include <errno.h>
#include <byteorder.h>
#include <align.h>
#include <assert.h>
#include <fibril_synch.h>
#include <mem.h>
#include <stdlib.h>
#include <str.h>

/**
 * The fat_alloc_lock mutex protects all copies of the File Allocation Table
 * during allocation of clusters. The lock does not have to be held durring
 * deallocation of clusters.
 */
static FIBRIL_MUTEX_INITIALIZE(exfat_alloc_lock);

/** Walk the cluster chain.
 *
 * @param bs		Buffer holding the boot sector for the file.
 * @param service_id	Service ID of the device with the file.
 * @param firstc	First cluster to start the walk with.
 * @param lastc		If non-NULL, output argument hodling the last cluster
 *			number visited.
 * @param numc		If non-NULL, output argument holding the number of
 *			clusters seen during the walk.
 * @param max_clusters	Maximum number of clusters to visit.
 *
 * @return		EOK on success or an error code.
 */
errno_t
exfat_cluster_walk(exfat_bs_t *bs, service_id_t service_id,
    exfat_cluster_t firstc, exfat_cluster_t *lastc, uint32_t *numc,
    uint32_t max_clusters)
{
	uint32_t clusters = 0;
	exfat_cluster_t clst = firstc;
	errno_t rc;

	if (firstc < EXFAT_CLST_FIRST) {
		/* No space allocated to the file. */
		if (lastc)
			*lastc = firstc;
		if (numc)
			*numc = 0;
		return EOK;
	}

	while (clst != EXFAT_CLST_EOF && clusters < max_clusters) {
		assert(clst >= EXFAT_CLST_FIRST);
		if (lastc)
			*lastc = clst;	/* remember the last cluster number */

		rc = exfat_get_cluster(bs, service_id, clst, &clst);
		if (rc != EOK)
			return rc;

		assert(clst != EXFAT_CLST_BAD);
		clusters++;
	}

	if (lastc && clst != EXFAT_CLST_EOF)
		*lastc = clst;
	if (numc)
		*numc = clusters;

	return EOK;
}

/** Read block from file located on a exFAT file system.
 *
 * @param block		Pointer to a block pointer for storing result.
 * @param bs		Buffer holding the boot sector of the file system.
 * @param nodep		FAT node.
 * @param bn		Block number.
 * @param flags		Flags passed to libblock.
 *
 * @return		EOK on success or an error code.
 */
errno_t
exfat_block_get(block_t **block, exfat_bs_t *bs, exfat_node_t *nodep,
    aoff64_t bn, int flags)
{
	exfat_cluster_t firstc = nodep->firstc;
	exfat_cluster_t currc = 0;
	aoff64_t relbn = bn;
	errno_t rc;

	if (!nodep->size)
		return ELIMIT;

	if (nodep->fragmented) {
		if (((((nodep->size - 1) / BPS(bs)) / SPC(bs)) == bn / SPC(bs)) &&
		    nodep->lastc_cached_valid) {
			/*
			 * This is a request to read a block within the last cluster
			 * when fortunately we have the last cluster number cached.
			 */
			return block_get(block, nodep->idx->service_id, DATA_FS(bs) +
			    (nodep->lastc_cached_value - EXFAT_CLST_FIRST) * SPC(bs) +
			    (bn % SPC(bs)), flags);
		}

		if (nodep->currc_cached_valid && bn >= nodep->currc_cached_bn) {
			/*
			 * We can start with the cluster cached by the previous call to
			 * fat_block_get().
			 */
			firstc = nodep->currc_cached_value;
			relbn -= (nodep->currc_cached_bn / SPC(bs)) * SPC(bs);
		}
	}

	rc = exfat_block_get_by_clst(block, bs, nodep->idx->service_id,
	    nodep->fragmented, firstc, &currc, relbn, flags);
	if (rc != EOK)
		return rc;

	/*
	 * Update the "current" cluster cache.
	 */
	nodep->currc_cached_valid = true;
	nodep->currc_cached_bn = bn;
	nodep->currc_cached_value = currc;

	return rc;
}

/** Read block from file located on a exFAT file system.
 *
 * @param block		Pointer to a block pointer for storing result.
 * @param bs		Buffer holding the boot sector of the file system.
 * @param service_id	Service ID of the file system.
 * @param fcl		First cluster used by the file. Can be zero if the file
 *			is empty.
 * @param clp		If not NULL, address where the cluster containing bn
 *			will be stored.
 *			stored
 * @param bn		Block number.
 * @param flags		Flags passed to libblock.
 *
 * @return		EOK on success or an error code.
 */
errno_t
exfat_block_get_by_clst(block_t **block, exfat_bs_t *bs,
    service_id_t service_id, bool fragmented, exfat_cluster_t fcl,
    exfat_cluster_t *clp, aoff64_t bn, int flags)
{
	uint32_t clusters;
	uint32_t max_clusters;
	exfat_cluster_t c = EXFAT_CLST_FIRST;
	errno_t rc;

	if (fcl < EXFAT_CLST_FIRST || fcl > DATA_CNT(bs) + 2)
		return ELIMIT;

	if (!fragmented) {
		rc = block_get(block, service_id, DATA_FS(bs) +
		    (fcl - EXFAT_CLST_FIRST) * SPC(bs) + bn, flags);
	} else {
		max_clusters = bn / SPC(bs);
		rc = exfat_cluster_walk(bs, service_id, fcl, &c, &clusters, max_clusters);
		if (rc != EOK)
			return rc;
		assert(clusters == max_clusters);

		rc = block_get(block, service_id, DATA_FS(bs) +
		    (c - EXFAT_CLST_FIRST) * SPC(bs) + (bn % SPC(bs)), flags);

		if (clp)
			*clp = c;
	}

	return rc;
}

/** Get cluster from the FAT.
 *
 * @param bs		Buffer holding the boot sector for the file system.
 * @param service_id	Service ID for the file system.
 * @param clst		Cluster which to get.
 * @param value		Output argument holding the value of the cluster.
 *
 * @return		EOK or an error code.
 */
errno_t
exfat_get_cluster(exfat_bs_t *bs, service_id_t service_id,
    exfat_cluster_t clst, exfat_cluster_t *value)
{
	block_t *b;
	aoff64_t offset;
	errno_t rc;

	offset = clst * sizeof(exfat_cluster_t);

	rc = block_get(&b, service_id, FAT_FS(bs) + offset / BPS(bs), BLOCK_FLAGS_NONE);
	if (rc != EOK)
		return rc;

	*value = uint32_t_le2host(*(uint32_t *)(b->data + offset % BPS(bs)));

	rc = block_put(b);

	return rc;
}

/** Set cluster in FAT.
 *
 * @param bs		Buffer holding the boot sector for the file system.
 * @param service_id	Service ID for the file system.
 * @param clst		Cluster which is to be set.
 * @param value		Value to set the cluster with.
 *
 * @return		EOK on success or an error code.
 */
errno_t
exfat_set_cluster(exfat_bs_t *bs, service_id_t service_id,
    exfat_cluster_t clst, exfat_cluster_t value)
{
	block_t *b;
	aoff64_t offset;
	errno_t rc;

	offset = clst * sizeof(exfat_cluster_t);

	rc = block_get(&b, service_id, FAT_FS(bs) + offset / BPS(bs), BLOCK_FLAGS_NONE);
	if (rc != EOK)
		return rc;

	*(uint32_t *)(b->data + offset % BPS(bs)) = host2uint32_t_le(value);

	b->dirty = true;	/* need to sync block */
	rc = block_put(b);
	return rc;
}

/** Allocate clusters in FAT.
 *
 * This function will attempt to allocate the requested number of clusters in
 * the FAT.  The FAT will be altered so that the allocated
 * clusters form an independent chain (i.e. a chain which does not belong to any
 * file yet).
 *
 * @param bs		Buffer holding the boot sector of the file system.
 * @param service_id	Service ID of the file system.
 * @param nclsts	Number of clusters to allocate.
 * @param mcl		Output parameter where the first cluster in the chain
 *			will be returned.
 * @param lcl		Output parameter where the last cluster in the chain
 *			will be returned.
 *
 * @return		EOK on success, an error code otherwise.
 */
errno_t
exfat_alloc_clusters(exfat_bs_t *bs, service_id_t service_id, unsigned nclsts,
    exfat_cluster_t *mcl, exfat_cluster_t *lcl)
{
	exfat_cluster_t *lifo;    /* stack for storing free cluster numbers */
	unsigned found = 0;     /* top of the free cluster number stack */
	exfat_cluster_t clst;
	errno_t rc = EOK;

	lifo = (exfat_cluster_t *) malloc(nclsts * sizeof(exfat_cluster_t));
	if (!lifo)
		return ENOMEM;

	fibril_mutex_lock(&exfat_alloc_lock);
	for (clst = EXFAT_CLST_FIRST; clst < DATA_CNT(bs) + 2 && found < nclsts;
	    clst++) {
		/* Need to rewrite because of multiple exfat_bitmap_get calls */
		if (exfat_bitmap_is_free(bs, service_id, clst) == EOK) {
			/*
			 * The cluster is free. Put it into our stack
			 * of found clusters and mark it as non-free.
			 */
			lifo[found] = clst;
			rc = exfat_set_cluster(bs, service_id, clst,
			    (found == 0) ?  EXFAT_CLST_EOF : lifo[found - 1]);
			if (rc != EOK)
				goto exit_error;
			found++;
			rc = exfat_bitmap_set_cluster(bs, service_id, clst);
			if (rc != EOK)
				goto exit_error;

		}
	}

	if (rc == EOK && found == nclsts) {
		*mcl = lifo[found - 1];
		*lcl = lifo[0];
		free(lifo);
		fibril_mutex_unlock(&exfat_alloc_lock);
		return EOK;
	}

	rc = ENOSPC;

exit_error:

	/* If something wrong - free the clusters */
	while (found--) {
		(void) exfat_bitmap_clear_cluster(bs, service_id, lifo[found]);
		(void) exfat_set_cluster(bs, service_id, lifo[found], 0);
	}

	free(lifo);
	fibril_mutex_unlock(&exfat_alloc_lock);
	return rc;
}

/** Free clusters forming a cluster chain in FAT.
 *
 * @param bs		Buffer hodling the boot sector of the file system.
 * @param service_id	Service ID of the file system.
 * @param firstc	First cluster in the chain which is to be freed.
 *
 * @return		EOK on success or an error code.
 */
errno_t
exfat_free_clusters(exfat_bs_t *bs, service_id_t service_id, exfat_cluster_t firstc)
{
	exfat_cluster_t nextc;
	errno_t rc;

	/* Mark all clusters in the chain as free */
	while (firstc != EXFAT_CLST_EOF) {
		assert(firstc >= EXFAT_CLST_FIRST && firstc < EXFAT_CLST_BAD);
		rc = exfat_get_cluster(bs, service_id, firstc, &nextc);
		if (rc != EOK)
			return rc;
		rc = exfat_set_cluster(bs, service_id, firstc, 0);
		if (rc != EOK)
			return rc;
		rc = exfat_bitmap_clear_cluster(bs, service_id, firstc);
		if (rc != EOK)
			return rc;
		firstc = nextc;
	}

	return EOK;
}

/** Append a cluster chain to the last file cluster in FAT.
 *
 * @param bs		Buffer holding the boot sector of the file system.
 * @param nodep		Node representing the file.
 * @param mcl		First cluster of the cluster chain to append.
 * @param lcl		Last cluster of the cluster chain to append.
 *
 * @return		EOK on success or an error code.
 */
errno_t
exfat_append_clusters(exfat_bs_t *bs, exfat_node_t *nodep, exfat_cluster_t mcl,
    exfat_cluster_t lcl)
{
	service_id_t service_id = nodep->idx->service_id;
	exfat_cluster_t lastc = 0;
	errno_t rc;

	if (nodep->firstc == 0) {
		/* No clusters allocated to the node yet. */
		nodep->firstc = mcl;
		nodep->dirty = true;	/* need to sync node */
	} else {
		if (nodep->lastc_cached_valid) {
			lastc = nodep->lastc_cached_value;
			nodep->lastc_cached_valid = false;
		} else {
			rc = exfat_cluster_walk(bs, service_id, nodep->firstc,
			    &lastc, NULL, (uint16_t) -1);
			if (rc != EOK)
				return rc;
		}

		rc = exfat_set_cluster(bs, nodep->idx->service_id, lastc, mcl);
		if (rc != EOK)
			return rc;
	}

	nodep->lastc_cached_valid = true;
	nodep->lastc_cached_value = lcl;

	return EOK;
}

/** Chop off node clusters in FAT.
 *
 * @param bs		Buffer holding the boot sector of the file system.
 * @param nodep		FAT node where the chopping will take place.
 * @param lcl		Last cluster which will remain in the node. If this
 *			argument is FAT_CLST_RES0, then all clusters will
 *			be chopped off.
 *
 * @return		EOK on success or an error code.
 */
errno_t exfat_chop_clusters(exfat_bs_t *bs, exfat_node_t *nodep, exfat_cluster_t lcl)
{
	errno_t rc;
	service_id_t service_id = nodep->idx->service_id;

	/*
	 * Invalidate cached cluster numbers.
	 */
	nodep->lastc_cached_valid = false;
	if (nodep->currc_cached_value != lcl)
		nodep->currc_cached_valid = false;

	if (lcl == 0) {
		/* The node will have zero size and no clusters allocated. */
		rc = exfat_free_clusters(bs, service_id, nodep->firstc);
		if (rc != EOK)
			return rc;
		nodep->firstc = 0;
		nodep->dirty = true;		/* need to sync node */
	} else {
		exfat_cluster_t nextc;

		rc = exfat_get_cluster(bs, service_id, lcl, &nextc);
		if (rc != EOK)
			return rc;

		/* Terminate the cluster chain */
		rc = exfat_set_cluster(bs, service_id, lcl, EXFAT_CLST_EOF);
		if (rc != EOK)
			return rc;

		/* Free all following clusters. */
		rc = exfat_free_clusters(bs, service_id, nextc);
		if (rc != EOK)
			return rc;
	}

	/*
	 * Update and re-enable the last cluster cache.
	 */
	nodep->lastc_cached_valid = true;
	nodep->lastc_cached_value = lcl;

	return EOK;
}

errno_t
exfat_zero_cluster(exfat_bs_t *bs, service_id_t service_id, exfat_cluster_t c)
{
	size_t i;
	block_t *b;
	errno_t rc;

	for (i = 0; i < SPC(bs); i++) {
		rc = exfat_block_get_by_clst(&b, bs, service_id, false, c, NULL,
		    i, BLOCK_FLAGS_NOREAD);
		if (rc != EOK)
			return rc;
		memset(b->data, 0, BPS(bs));
		b->dirty = true;
		rc = block_put(b);
		if (rc != EOK)
			return rc;
	}

	return EOK;
}

errno_t
exfat_read_uctable(exfat_bs_t *bs, exfat_node_t *nodep, uint8_t *uctable)
{
	size_t i, blocks, count;
	block_t *b;
	errno_t rc;
	blocks = ROUND_UP(nodep->size, BPS(bs)) / BPS(bs);
	count = BPS(bs);

	for (i = 0; i < blocks; i++) {
		rc = exfat_block_get(&b, bs, nodep, i, BLOCK_FLAGS_NOREAD);
		if (rc != EOK)
			return rc;
		if (i == blocks - 1)
			count = nodep->size - i * BPS(bs);
		memcpy(uctable, b->data, count);
		uctable += count;
		rc = block_put(b);
		if (rc != EOK)
			return rc;
	}

	return EOK;
}

/** Perform basic sanity checks on the file system.
 *
 * Verify if values of boot sector fields are sane. Also verify media
 * descriptor. This is used to rule out cases when a device obviously
 * does not contain a exfat file system.
 */
errno_t exfat_sanity_check(exfat_bs_t *bs)
{
	if (str_cmp((char const *)bs->oem_name, "EXFAT   "))
		return ENOTSUP;
	else if (uint16_t_le2host(bs->signature) != 0xAA55)
		return ENOTSUP;
	else if (uint32_t_le2host(bs->fat_sector_count) == 0)
		return ENOTSUP;
	else if (uint32_t_le2host(bs->data_clusters) == 0)
		return ENOTSUP;
	else if (bs->fat_count != 1)
		return ENOTSUP;
	else if ((bs->bytes_per_sector + bs->sec_per_cluster) > 25) {
		/* exFAT does not support cluster size > 32 Mb */
		return ENOTSUP;
	}
	return EOK;
}

/**
 * @}
 */