source: mainline/uspace/srv/fs/exfat/exfat_fat.c

/*
 * 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;
}

/**
 * @}
 */