/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *  http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <nffs/nffs.h>
#include <nffs/os.h>

/**
 * The size of the largest data block encountered during detection.  This is
 * used to ensure that the maximum block data size is not set lower than the
 * size of an existing block.
 */
static uint16_t nffs_restore_largest_block_data_len;

/**
 * Checks that each block a chain of data blocks was properly restored.
 *
 * @param last_block_entry      The entry corresponding to the last block in
 *                                  the chain.
 *
 * @return                      0 if the block chain is OK;
 *                              FS_ECORRUPT if corruption is detected;
 *                              nonzero on other error.
 */
static int
nffs_restore_validate_block_chain(struct nffs_hash_entry *last_block_entry)
{
    struct nffs_disk_block disk_block;
    struct nffs_hash_entry *cur;
    struct nffs_block block;
    uint32_t area_offset;
    uint8_t area_idx;
    int rc;

    cur = last_block_entry;

    while (cur != NULL) {
        if (nffs_hash_entry_is_dummy(cur)) {
            return FS_ENOENT;
        }

        nffs_flash_loc_expand(cur->nhe_flash_loc, &area_idx, &area_offset);

        rc = nffs_block_read_disk(area_idx, area_offset, &disk_block);
        if (rc != 0) {
            return rc;
        }

        rc = nffs_block_from_hash_entry(&block, cur);
        if (rc != 0) {
            return rc;
        }

        cur = block.nb_prev;
    }

    return 0;
}

static void
u32toa(char *dst, uint32_t val)
{
    uint8_t tmp;
    int idx = 0;
    int i;
    int print = 0;

    for (i = 0; i < 8; i++) {
        tmp = val >> 28;
        if (tmp || i == 7) {
            print = 1;
        }
        if (tmp < 10) {
            tmp += '0';
        } else {
            tmp += 'a' - 10;
        }
        if (print) {
            dst[idx++] = tmp;
        }
        val <<= 4;
    }
    dst[idx++] = '\0';
}

/**
 * If the specified inode entry is a dummy directory, this function moves
 * all its children to the lost+found directory.
 *
 * @param inode_entry           The parent inode to test and empty.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_migrate_orphan_children(struct nffs_inode_entry *inode_entry)
{
    struct nffs_inode_entry *lost_found_sub;
    struct nffs_inode_entry *child_entry;
    char buf[32];
    int rc;

    if (!nffs_hash_id_is_dir(inode_entry->nie_hash_entry.nhe_id)) {
        /* Not a directory. */
        return 0;
    }

    if (!nffs_inode_is_dummy(inode_entry)) {
        /* Not a dummy. */
        return 0;
    }

    if (SLIST_EMPTY(&inode_entry->nie_child_list)) {
        /* No children to migrate. */
        return 0;
    }

    /* Create a directory in lost+found to hold the dummy directory's
     * contents.
     */
    strcpy(buf, "/lost+found/");
    u32toa(&buf[strlen(buf)], inode_entry->nie_hash_entry.nhe_id);

    rc = nffs_path_new_dir(buf, &lost_found_sub);
    if (rc != 0 && rc != FS_EEXIST) {
        return rc;
    }

    /* Move each child into the new subdirectory. */
    while ((child_entry = SLIST_FIRST(&inode_entry->nie_child_list)) != NULL) {
        rc = nffs_inode_rename(child_entry, lost_found_sub, NULL);
        if (rc != 0) {
            return rc;
        }
    }

    return 0;
}

static int
nffs_restore_should_sweep_inode_entry(struct nffs_inode_entry *inode_entry,
                                      int *out_should_sweep)
{
    struct nffs_inode inode;
    int rc;


    /*
     * if this inode was tagged to have a dummy block entry and the
     * flag is still set, that means we didn't find the block and so
     * should remove this inode and all associated blocks.
     */
    if (nffs_inode_getflags(inode_entry, NFFS_INODE_FLAG_DUMMYLSTBLK)) {
        *out_should_sweep = 1;
        /*nffs_inode_inc_refcnt(inode_entry);*/
        inode_entry->nie_refcnt = 1;
        assert(inode_entry->nie_refcnt >= 1);
        return 0;
    }

    /*
     * This inode was originally created to hold a block that was restored
     * before the owning inode. If the flag is still set, it means we never
     * restored the inode from disk and so this entry should be deleted.
     */
    if (nffs_inode_getflags(inode_entry, NFFS_INODE_FLAG_DUMMYINOBLK)) {
        *out_should_sweep = 2;
        inode_entry->nie_refcnt = 1;
        assert(inode_entry->nie_refcnt >= 1);
        return 0;
    }

    /*
     * Determine if the inode is a dummy. Dummy inodes have a flash
     * location set to LOC_NONE and should have a flag set for the reason.
     * The presence of a dummy inode during the final sweep step indicates
     * file system corruption.  It's assumed that directories have
     * previously migrated all children to /lost+found.
     */
    if (nffs_inode_is_dummy(inode_entry)) {
        *out_should_sweep = 3;
        nffs_inode_inc_refcnt(inode_entry);
        assert(inode_entry->nie_refcnt >= 1);
        return 0;
    }

    /* Determine if the inode has been deleted.  If an inode has no parent (and
     * it isn't the root directory), it has been deleted from the disk and
     * should be swept from the RAM representation.
     */
    if (inode_entry->nie_hash_entry.nhe_id != NFFS_ID_ROOT_DIR) {
        rc = nffs_inode_from_entry(&inode, inode_entry);
        if (rc != 0 && rc != FS_ENOENT) {
            *out_should_sweep = 0;
            return rc;
        }
        if (inode.ni_parent == NULL) {
            *out_should_sweep = 4;
            return 0;
        }
    }

    /*
     * If this inode has been marked as deleted, we can unlink it here.
     *
     * XXX Note that the record of a deletion could be lost if garbage
     * collection erases the delete but leaves inode updates on other
     * partitions which can then be restored.
     */
    if (nffs_inode_getflags(inode_entry, NFFS_INODE_FLAG_DELETED)) {
        rc = nffs_inode_from_entry(&inode, inode_entry);
        if (rc != 0) {
            *out_should_sweep = 0;
            return rc;
        }
        *out_should_sweep = 5;
    }

    /* If this is a file inode, verify that all of its constituent blocks are
     * present.
     */
    if (nffs_hash_id_is_file(inode_entry->nie_hash_entry.nhe_id)) {
        rc = nffs_restore_validate_block_chain(
                inode_entry->nie_last_block_entry);
        if (rc == FS_ECORRUPT) {
            *out_should_sweep = 6;
            return 0;
        } else if (rc == FS_ENOENT) {
            *out_should_sweep = 7;
            return 0;
        } else if (rc != 0) {
            *out_should_sweep = 0;
            return rc;
        }
    }

    /* This is a valid inode; don't sweep it. */
    *out_should_sweep = 0;
    return 0;
}

/**
 * Performs a sweep of the RAM representation at the end of a successful
 * restore.  The sweep phase performs the following actions of each inode in
 * the file system:
 *     1. If the inode is a dummy directory, its children are migrated to the
 *        lost+found directory.
 *     2. Else if the inode is a dummy file, it is fully deleted from RAM.
 *     3. Else, a CRC check is performed on each of the inode's constituent
 *        blocks.  If corruption is detected, the inode is fully deleted from
 *        RAM.
 *
 * @return                      0 on success; nonzero on failure.
 */
int
nffs_restore_sweep(void)
{
    struct nffs_inode_entry *inode_entry;
    struct nffs_hash_entry *entry;
    struct nffs_hash_entry *next;
    struct nffs_hash_list *list;
    struct nffs_inode inode;
    struct nffs_block block;
    int del = 0;
    int rc;
    int i;

    /* Iterate through every object in the hash table, deleting all inodes that
     * should be removed.
     */
    for (i = 0; i < NFFS_HASH_SIZE; i++) {
        list = nffs_hash + i;

        entry = SLIST_FIRST(list);
        while (entry != NULL) {
            next = SLIST_NEXT(entry, nhe_next);
            if (nffs_hash_id_is_inode(entry->nhe_id)) {
                inode_entry = (struct nffs_inode_entry *)entry;

                /*
                 * If this is a dummy inode directory, the file system
                 * is corrupt.  Move the directory's children inodes to
                 * the lost+found directory.
                 */
                rc = nffs_restore_migrate_orphan_children(inode_entry);
                if (rc != 0) {
                    return rc;
                }

                /* Determine if this inode needs to be deleted. */
                rc = nffs_restore_should_sweep_inode_entry(inode_entry, &del);
                if (rc != 0) {
                    return rc;
                }

                rc = nffs_inode_from_entry(&inode, inode_entry);
                if (rc != 0 && rc != FS_ENOENT) {
                    return rc;
                }

                if (del) {

                    /* Remove the inode and all its children from RAM.  We
                     * expect some file system corruption; the children are
                     * subject to garbage collection and may not exist in the
                     * hash.  Remove what is actually present and ignore
                     * corruption errors.
                     */
                    rc = nffs_inode_unlink_from_ram_corrupt_ok(&inode, &next);
                    if (rc != 0) {
                        return rc;
                    }
                    next = SLIST_FIRST(list);
                }
            } else if (nffs_hash_id_is_block(entry->nhe_id)) {
                if (nffs_hash_id_is_dummy(entry->nhe_id)) {
                    del = 1;
                    nffs_block_delete_from_ram(entry);
                } else {
                    rc = nffs_block_from_hash_entry(&block, entry);
                    if (rc != 0 && rc != FS_ENOENT) {
                        del = 1;
                        nffs_block_delete_from_ram(entry);
                    }
                }
                if (del) {
                    del = 0;
                    next = SLIST_FIRST(list);
                }
            }

            entry = next;
        }
    }

    return 0;
}

/**
 * Creates a dummy inode and inserts it into the hash table.  A dummy inode is
 * a temporary placeholder for a real inode that has not been restored yet.
 * These are necessary so that the inter-object links can be maintained until
 * the absent inode is eventually restored.  Dummy inodes are identified by a
 * inaccessible flash location (NFFS_FLASH_LOC_NONE). When the real inode
 * is restored, this flash location will be udpated.
 *
 * @param id                    The ID of the dummy inode to create.
 * @param out_inode_entry       On success, the dummy inode gets written here.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_dummy_inode(uint32_t id,
                         struct nffs_inode_entry **out_inode_entry)
{
    struct nffs_inode_entry *inode_entry;

    inode_entry = nffs_inode_entry_alloc();
    if (inode_entry == NULL) {
        return FS_ENOMEM;
    }
    inode_entry->nie_hash_entry.nhe_id = id;
    inode_entry->nie_hash_entry.nhe_flash_loc = NFFS_FLASH_LOC_NONE;
    inode_entry->nie_refcnt = 0;
    inode_entry->nie_last_block_entry = NULL; /* lastblock not available yet */
    nffs_inode_setflags(inode_entry, NFFS_INODE_FLAG_DUMMY);

    nffs_hash_insert(&inode_entry->nie_hash_entry);

    *out_inode_entry = inode_entry;

    return 0;
}

/**
 * Determines if an already-restored inode should be replaced by another inode
 * just read from flash.  This function should only be called if both inodes
 * share the same ID.  The existing inode gets replaced if:
 *     o It is a dummy inode.
 *     o Its sequence number is less than that of the new inode.
 *
 * @param old_inode_entry       The already-restored inode to test.
 * @param disk_inode            The inode just read from flash.
 * @param out_should_replace    On success, 0=don't replace; 1=do replace.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_inode_gets_replaced(struct nffs_inode_entry *old_inode_entry,
                                 const struct nffs_disk_inode *disk_inode,
                                 int *out_should_replace)
{
    struct nffs_inode old_inode;
    int rc;

    assert(old_inode_entry->nie_hash_entry.nhe_id == disk_inode->ndi_id);


    if (nffs_inode_is_dummy(old_inode_entry)) {
        NFFS_LOG(DEBUG, "inode_gets_replaced dummy!\n");
        *out_should_replace = 1;
        return 0;
    }

    /*
     * inode is known to be obsolete and needs to be replaced no matter what
     */
    if (nffs_inode_getflags(old_inode_entry, NFFS_INODE_FLAG_OBSOLETE)) {
        NFFS_LOG(DEBUG, "inode_gets_replaced obsolete\n");
        *out_should_replace = 2;
        return 0;
    }

    rc = nffs_inode_from_entry(&old_inode, old_inode_entry);
    if (rc != 0) {
        *out_should_replace = 0;
        return rc;
    }

    if (old_inode.ni_seq < disk_inode->ndi_seq) {
        NFFS_LOG(DEBUG, "inode_gets_replaced seq\n");
        *out_should_replace = 3;
        return 0;
    }

    if (old_inode.ni_seq == disk_inode->ndi_seq) {
        /* This is a duplicate of a previously-read inode.  This should never
         * happen.
         */
        *out_should_replace = 0;
        return FS_EEXIST;
    }

    *out_should_replace = 0;
    return 0;
}

/**
 * Determines if the specified inode should be added to the RAM representation
 * and adds it if appropriate.
 *
 * @param disk_inode            The inode just read from flash.
 * @param area_idx              The index of the area containing the inode.
 * @param area_offset           The offset within the area of the inode.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_inode(const struct nffs_disk_inode *disk_inode, uint8_t area_idx,
                   uint32_t area_offset)
{
    struct nffs_inode_entry *inode_entry;
    struct nffs_inode_entry *parent;
    struct nffs_inode inode;
    struct nffs_hash_entry *lastblock_entry = NULL;
    int new_inode;
    int do_add;
    int rc;

    new_inode = 0;

    /* Check the inode's CRC.  If the inode is corrupt, discard it. */
    rc = nffs_crc_disk_inode_validate(disk_inode, area_idx, area_offset);
    if (rc != 0) {
        goto err;
    }

    inode_entry = nffs_hash_find_inode(disk_inode->ndi_id);

    /*
     * Inode has already been restored. Determine whether this version
     * from disk should replace the previous version referenced in RAM.
     */
    if (inode_entry != NULL) {

        if (disk_inode->ndi_flags & NFFS_INODE_FLAG_DELETED) {
            /*
             * Restore this inode even though deleted on disk
             * so the additional restored blocks have a place to go
             */
            NFFS_LOG(DEBUG, "restoring deleted inode %x\n",
                     (unsigned int)disk_inode->ndi_id);
            nffs_inode_setflags(inode_entry, NFFS_INODE_FLAG_DELETED);
        }

        /*
         * inodes get replaced if they're dummy entries (i.e. allocated
         * as place holders until the actual inode is restored), or this is
         * a more recent version of the inode which supercedes the old.
         */
        rc = nffs_restore_inode_gets_replaced(inode_entry, disk_inode, &do_add);
        if (rc != 0) {
            goto err;
        }

        if (do_add) { /* replace in this case */
            if (!nffs_inode_is_dummy(inode_entry)) {
                /*
                 * if it's not a dummy, read block from flash
                 */
                rc = nffs_inode_from_entry(&inode, inode_entry);
                if (rc != 0) {
                    return rc;
                }

                /*
                 * inode is known to be obsolete
                 */
                if (nffs_inode_getflags(inode_entry, 
                                        NFFS_INODE_FLAG_OBSOLETE)) {
                    nffs_inode_unsetflags(inode_entry,
                                          NFFS_INODE_FLAG_OBSOLETE);
                }

                if (inode.ni_parent != NULL) {
                    nffs_inode_remove_child(&inode);
                }

                /*
                 * If this is a delete record, subsequent inode and restore
                 * records from flash may be ignored.
                 * If the parent is NULL, this inode has been deleted. (old)
                 * XXX if we could count on delete records for every inode,
                 * we wouldn't need to check for the root directory looking
                 * like a delete record because of it's parent ID.
                 */
                if (inode_entry->nie_hash_entry.nhe_id != NFFS_ID_ROOT_DIR) {
                    if (disk_inode->ndi_flags & NFFS_INODE_FLAG_DELETED ||
                        disk_inode->ndi_parent_id == NFFS_ID_NONE) {

                        nffs_inode_setflags(inode_entry,
                                            NFFS_INODE_FLAG_DELETED);
                    }
                }

            } else {
                /*
                 * The existing inode entry was added as dummy.
                 * The restore operation clears that state.
                 */

                /* If it's a directory, it was added as a parent to
                 * one of it's children who were restored first.
                 */
                if (nffs_inode_getflags(inode_entry, 
                                         NFFS_INODE_FLAG_DUMMYPARENT)) {
                    assert(nffs_hash_id_is_dir(inode_entry->nie_hash_entry.nhe_id));
                    nffs_inode_unsetflags(inode_entry, 
                                         NFFS_INODE_FLAG_DUMMYPARENT);
                }

                /*
                 * If it's a file, it was added to store a lastblock
                 */
                if (nffs_inode_getflags(inode_entry, 
                                         NFFS_INODE_FLAG_DUMMYINOBLK)) {
                    assert(nffs_hash_id_is_file(inode_entry->nie_hash_entry.nhe_id));
                    nffs_inode_unsetflags(inode_entry, 
                                         NFFS_INODE_FLAG_DUMMYINOBLK);
                }

                /*
                 * Also, since it's a dummy, clear this flag too
                 */
                if (nffs_inode_getflags(inode_entry, NFFS_INODE_FLAG_DUMMY)) {
                    nffs_inode_unsetflags(inode_entry, NFFS_INODE_FLAG_DUMMY);
                }
            }
 
            /*
             * Update location to reference new location in flash
             */
            inode_entry->nie_hash_entry.nhe_flash_loc =
                                    nffs_flash_loc(area_idx, area_offset);
        }
        
    } else {
        inode_entry = nffs_inode_entry_alloc();
        if (inode_entry == NULL) {
            rc = FS_ENOMEM;
            goto err;
        }
        new_inode = 1;
        do_add = 1;

        inode_entry->nie_hash_entry.nhe_id = disk_inode->ndi_id;
        inode_entry->nie_hash_entry.nhe_flash_loc =
                              nffs_flash_loc(area_idx, area_offset);
        inode_entry->nie_last_block_entry = NULL; /* for now */

        nffs_hash_insert(&inode_entry->nie_hash_entry);
    }

    /*
     * inode object has been restored and the entry is in the hash
     * Check whether the lastblock and parent have also been restored
     * and link up or allocate dummy entries as appropriate.
     */
    if (do_add) {
        inode_entry->nie_refcnt = 1;

        if (disk_inode->ndi_flags & NFFS_INODE_FLAG_DELETED) {
            /*
             * Restore this inode even though deleted on disk
             * so the additional restored blocks have a place to go
             */
            NFFS_LOG(DEBUG, "restoring deleted inode %x\n",
                     (unsigned int)disk_inode->ndi_id);
            nffs_inode_setflags(inode_entry, NFFS_INODE_FLAG_DELETED);
        }

        /*
         * Inode has a lastblock on disk.
         * Add reference to last block entry if in hash table
         * otherwise add a dummy block entry for later update
         */
        if (disk_inode->ndi_lastblock_id != NFFS_ID_NONE &&
                nffs_hash_id_is_file(inode_entry->nie_hash_entry.nhe_id)) {
            lastblock_entry =
              nffs_hash_find_block(disk_inode->ndi_lastblock_id);

            /*
             * Lastblock has already been restored.
             */
            if (lastblock_entry != NULL) {
                if (lastblock_entry->nhe_id == disk_inode->ndi_lastblock_id) {
                    inode_entry->nie_last_block_entry = lastblock_entry;
                }

            } else {
                /*
                 * Insert a temporary reference to a 'dummy' block entry
                 * When block is restored, it will update this dummy and
                 * the entry of this inode is updated to flash location
                 */
                rc = nffs_block_entry_reserve(&lastblock_entry);
                if (lastblock_entry == NULL) {
                    rc = FS_ENOMEM;
                    goto err;
                }

                lastblock_entry->nhe_id = disk_inode->ndi_lastblock_id;
                lastblock_entry->nhe_flash_loc = NFFS_FLASH_LOC_NONE;
                inode_entry->nie_last_block_entry = lastblock_entry;
                nffs_inode_setflags(inode_entry, NFFS_INODE_FLAG_DUMMYLSTBLK);
                nffs_hash_insert(lastblock_entry);

                if (lastblock_entry->nhe_id >= nffs_hash_next_block_id) {
                    nffs_hash_next_block_id = lastblock_entry->nhe_id + 1;
                }
            }
        }

        if (disk_inode->ndi_parent_id != NFFS_ID_NONE) {
            
            parent = nffs_hash_find_inode(disk_inode->ndi_parent_id);
            /*
             * The parent directory for this inode hasn't been restored yet.
             * Add a dummy directory so it can be added as a child.
             * When the parent inode is restored, it's hash entry will be
             * updated with the flash location.
             */
            if (parent == NULL) {
                rc = nffs_restore_dummy_inode(disk_inode->ndi_parent_id,
                                             &parent);
                /*
                 * Set the dummy parent flag in the new parent.
                 * It's turned off above when restored.
                 */
                nffs_inode_setflags(parent, NFFS_INODE_FLAG_DUMMYPARENT);
                if (rc != 0) {
                    goto err;
                }
            }

            rc = nffs_inode_add_child(parent, inode_entry);
            if (rc != 0) {
                goto err;
            }
        } 

        if (inode_entry->nie_hash_entry.nhe_id == NFFS_ID_ROOT_DIR) {
            nffs_root_dir = inode_entry;
            nffs_inode_setflags(nffs_root_dir, NFFS_INODE_FLAG_INTREE);
        }
    }

    if (nffs_hash_id_is_file(inode_entry->nie_hash_entry.nhe_id)) {
        NFFS_LOG(DEBUG, "restoring file; id=0x%08x\n",
                 (unsigned int)inode_entry->nie_hash_entry.nhe_id);
        if (inode_entry->nie_hash_entry.nhe_id >= nffs_hash_next_file_id) {
            nffs_hash_next_file_id = inode_entry->nie_hash_entry.nhe_id + 1;
        }
    } else {
        NFFS_LOG(DEBUG, "restoring dir; id=0x%08x\n",
                 (unsigned int)inode_entry->nie_hash_entry.nhe_id);
        if (inode_entry->nie_hash_entry.nhe_id >= nffs_hash_next_dir_id) {
            nffs_hash_next_dir_id = inode_entry->nie_hash_entry.nhe_id + 1;
        }
    }

    return 0;

err:
    if (new_inode) {
        assert(nffs_inode_getflags(inode_entry, NFFS_INODE_FLAG_INHASH));
        nffs_hash_remove(&inode_entry->nie_hash_entry);
        nffs_inode_entry_free(inode_entry);
    }
    return rc;
}

/**
 * Indicates whether the specified data block is superseded by the just-read
 * disk data block.  A data block supersedes another if its ID is equal and its
 * sequence number is greater than that of the other block.
 *
 * @param out_should_replace    On success, 0 or 1 gets written here, to
 *                                  indicate whether replacement should occur.
 * @param old_block             The data block which has already been read and
 *                                  converted to its RAM representation.  This
 *                                  is the block that may be superseded.
 * @param disk_block            The disk data block that was just read from
 *                                  flash.  This is the block which may
 *                                  supersede the other.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_block_gets_replaced(const struct nffs_block *old_block,
                                 const struct nffs_disk_block *disk_block,
                                 int *out_should_replace)
{
    assert(old_block->nb_hash_entry->nhe_id == disk_block->ndb_id);

    if (nffs_block_is_dummy(old_block->nb_hash_entry)) {
        assert(0);
        *out_should_replace = 1;
        return 0;
    }

    if (old_block->nb_seq < disk_block->ndb_seq) {
        *out_should_replace = 2;
        return 0;
    }

    if (old_block->nb_seq == disk_block->ndb_seq) {
        /* This is a duplicate of an previously-read block.  This should never
         * happen.
         */
        return FS_EEXIST;
    }

    *out_should_replace = 0;
    return 0;
}

/**
 * Populates the nffs RAM state with the memory representation of the specified
 * disk data block.
 *
 * @param disk_block            The source disk block to insert.
 * @param area_idx              The ID of the area containing the block.
 * @param area_offset           The area_offset within the area of the block.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_block(const struct nffs_disk_block *disk_block, uint8_t area_idx,
                   uint32_t area_offset)
{
    struct nffs_inode_entry *inode_entry;
    struct nffs_hash_entry *entry;
    struct nffs_block block;
    int do_replace;
    int new_block;
    int rc;

    new_block = 0;

    /* Check the block's CRC.  If the block is corrupt, discard it.  If this
     * block would have superseded another, the old block becomes current.
     */
    rc = nffs_crc_disk_block_validate(disk_block, area_idx, area_offset);
    if (rc != 0) {
        goto err;
    }

    entry = nffs_hash_find_block(disk_block->ndb_id);
    if (entry != NULL) {

        rc = nffs_block_from_hash_entry_no_ptrs(&block, entry);
        if (rc != 0 && rc != FS_ENOENT) {
            goto err;
        }

        /*
         * If the old block reference is for a 'dummy' block, it was added
         * because the owning inode's lastblock was not yet restored.
         * Update the block hash entry and inode to reference the entry.
         */
        if (nffs_block_is_dummy(entry)) {

            assert(entry->nhe_id == disk_block->ndb_id);

            /*
             * Entry is no longer dummy as it references the correct location
             */
            entry->nhe_flash_loc = nffs_flash_loc(area_idx, area_offset);

            inode_entry = nffs_hash_find_inode(disk_block->ndb_inode_id);

            /*
             * Turn off flags in previously restored inode recording the
             * allocation of a dummy block
             */
            if (inode_entry) {
                nffs_inode_unsetflags(inode_entry, NFFS_INODE_FLAG_DUMMYLSTBLK);
            }
        }

        rc = nffs_restore_block_gets_replaced(&block, disk_block,
                                              &do_replace);
        if (rc != 0) {
            goto err;
        }

        if (!do_replace) {
            /* The new block is superseded by the old; nothing to do. */
            return 0;
        }

        /*
         * update the existing hash entry to reference the new flash location
         */
        entry->nhe_flash_loc = nffs_flash_loc(area_idx, area_offset);

    } else {
        entry = nffs_block_entry_alloc();
        if (entry == NULL) {
            rc = FS_ENOMEM;
            goto err;
        }
        new_block = 1;
        entry->nhe_id = disk_block->ndb_id;
        entry->nhe_flash_loc = nffs_flash_loc(area_idx, area_offset);

        /* The block is ready to be inserted into the hash. */

        nffs_hash_insert(entry);

        if (disk_block->ndb_id >= nffs_hash_next_block_id) {
            nffs_hash_next_block_id = disk_block->ndb_id + 1;
        }
    }

    /* Make sure the maximum block data size is not set lower than the size of
     * an existing block.
     */
    if (disk_block->ndb_data_len > nffs_restore_largest_block_data_len) {
        nffs_restore_largest_block_data_len = disk_block->ndb_data_len;
    }

    NFFS_LOG(DEBUG, "restoring block; id=0x%08x seq=%u inode_id=%u prev_id=%u "
             "data_len=%u\n",
             (unsigned int)disk_block->ndb_id,
             (unsigned int)disk_block->ndb_seq,
             (unsigned int)disk_block->ndb_inode_id,
             (unsigned int)disk_block->ndb_prev_id,
             disk_block->ndb_data_len);

    inode_entry = nffs_hash_find_inode(disk_block->ndb_inode_id);

    if (inode_entry == NULL) {
        /*
         * Owning inode not yet restored.
         * Allocate a dummy inode which temporarily owns this block.
         * It is not yet linked to a parent.
         */
        rc = nffs_restore_dummy_inode(disk_block->ndb_inode_id, &inode_entry);
        if (rc != 0) {
            goto err;
        }
        /*
         * Record that this inode was created because a block was restored
         * before the inode
         */
        nffs_inode_setflags(inode_entry, NFFS_INODE_FLAG_DUMMYINOBLK);
        inode_entry->nie_last_block_entry = entry;
    } else {
        if (nffs_inode_getflags(inode_entry, NFFS_INODE_FLAG_DELETED)) {
            /*
             * don't restore blocks for deleted inodes
             */
            rc = FS_ENOENT;
            goto err;
        }
    }

    return 0;

err:
    if (new_block) {
        nffs_hash_remove(entry);
        nffs_block_entry_free(entry);
    }
    return rc;
}

/**
 * Populates the nffs RAM state with the memory representation of the specified
 * disk object.
 *
 * @param disk_object           The source disk object to convert.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_object(const struct nffs_disk_object *disk_object)
{
    int rc;

    switch (disk_object->ndo_type) {
    case NFFS_OBJECT_TYPE_INODE:
        rc = nffs_restore_inode(&disk_object->ndo_disk_inode,
                                disk_object->ndo_area_idx,
                                disk_object->ndo_offset);
        break;

    case NFFS_OBJECT_TYPE_BLOCK:
        rc = nffs_restore_block(&disk_object->ndo_disk_block,
                                disk_object->ndo_area_idx,
                                disk_object->ndo_offset);
        break;

    default:
        rc = FS_EINVAL;
        break;
    }

    return rc;
}

/**
 * Reads a single disk object from flash.
 *
 * @param area_idx              The area to read the object from.
 * @param area_offset           The offset within the area to read from.
 * @param out_disk_object       On success, the restored object gets written
 *                                  here.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_disk_object(int area_idx, uint32_t area_offset,
                         struct nffs_disk_object *out_disk_object)
{
    int rc;

    memset(out_disk_object, 0, sizeof *out_disk_object);

    rc = nffs_flash_read(area_idx, area_offset,
                         &out_disk_object->ndo_un_obj,
                         sizeof(out_disk_object->ndo_un_obj));
    if (rc != 0) {
        return rc;
    }
    STATS_INC(nffs_stats, nffs_readcnt_object);

    if (nffs_hash_id_is_inode(out_disk_object->ndo_disk_inode.ndi_id)) {
        out_disk_object->ndo_type = NFFS_OBJECT_TYPE_INODE;

    } else if (nffs_hash_id_is_block(out_disk_object->ndo_disk_block.ndb_id)) {
        out_disk_object->ndo_type = NFFS_OBJECT_TYPE_BLOCK;

    } else if (out_disk_object->ndo_disk_block.ndb_id == NFFS_ID_NONE) {
        return FS_EEMPTY;

    } else {
        return FS_ECORRUPT;
    }

    out_disk_object->ndo_area_idx = area_idx;
    out_disk_object->ndo_offset = area_offset;

    return 0;
}

/**
 * Calculates the disk space occupied by the specified disk object.
 *
 * @param disk_object
 */
static int
nffs_restore_disk_object_size(const struct nffs_disk_object *disk_object)
{
    switch (disk_object->ndo_type) {
    case NFFS_OBJECT_TYPE_INODE:
        return sizeof disk_object->ndo_disk_inode +
                      disk_object->ndo_disk_inode.ndi_filename_len;

    case NFFS_OBJECT_TYPE_BLOCK:
        return sizeof disk_object->ndo_disk_block +
                      disk_object->ndo_disk_block.ndb_data_len;

    default:
        assert(0);
        return 1;
    }
}

/**
 * Reads the specified area from disk and loads its contents into the RAM
 * representation.
 *
 * @param area_idx              The index of the area to read.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_area_contents(int area_idx)
{
    struct nffs_disk_object disk_object;
    struct nffs_area *area;
    int rc;

    area = nffs_areas + area_idx;

    area->na_cur = sizeof (struct nffs_disk_area);
    while (1) {
        rc = nffs_restore_disk_object(area_idx, area->na_cur,  &disk_object);
        switch (rc) {
        case 0:

            /* Valid object; restore it into the RAM representation. */
            rc = nffs_restore_object(&disk_object);

            /*
             * If the restore fails the CRC check, the object length field
             * can't be trusted so just start looking for the next valid
             * object in the flash area.
             * XXX Deal with file system corruption
             */
            if (rc == FS_ECORRUPT) {
                area->na_cur++;
            } else {
                STATS_INC(nffs_stats, nffs_object_count); /* restored objects */
                area->na_cur += nffs_restore_disk_object_size(&disk_object);
            }
            break;

        case FS_ECORRUPT:
            /*
             * Invalid object; keep scanning for a valid object ID and CRC
             * Can nffs_restore_disk_object return FS_ECORRUPT? XXX
             */
            area->na_cur++;
            break;

        case FS_EEMPTY:
        case FS_EOFFSET:
            /* End of disk encountered; area fully restored. */
            return 0;

        default:
            return rc;
        }
    }
}

/**
 * Reads and parses one area header.  This function does not read the area's
 * contents.
 *
 * @param out_is_scratch        On success, 0 or 1 gets written here,
 *                                  indicating whether the area is a scratch
 *                                  area.
 * @param area_offset           The flash offset of the start of the area.
 *
 * @return                      0 on success;
 *                              nonzero on failure.
 */
static int
nffs_restore_detect_one_area(uint8_t flash_id, uint32_t area_offset,
                             struct nffs_disk_area *out_disk_area)
{
    int rc;

    STATS_INC(nffs_stats, nffs_readcnt_detect);
    rc = nffs_os_flash_read(flash_id, area_offset, out_disk_area,
                        sizeof *out_disk_area);
    if (rc != 0) {
        return FS_EHW;
    }

    if (!nffs_area_magic_is_set(out_disk_area)) {
        return FS_ECORRUPT;
    }

    if (!nffs_area_is_current_version(out_disk_area)) {
        return FS_EUNEXP;
    }

    return 0;
}

/**
 * Repairs the effects of a corrupt scratch area.  Scratch area corruption can
 * occur when the system resets while a garbage collection cycle is in
 * progress.
 *
 * @return                      0 on success; nonzero on failure.
 */
static int
nffs_restore_corrupt_scratch(void)
{
    struct nffs_inode_entry *inode_entry;
    struct nffs_hash_entry *entry;
    struct nffs_hash_entry *next;
    uint32_t area_offset;
    uint16_t good_idx;
    uint16_t bad_idx;
    uint8_t area_idx;
    int rc;
    int i;

    /* Search for a pair of areas with identical IDs.  If found, these areas
     * represent the source and destination areas of a garbage collection
     * cycle.  The shorter of the two areas was the destination area.  Since
     * the garbage collection cycle did not finish, the source area contains a
     * more complete set of objects than the destination area.
     *
     * good_idx = index of source area.
     * bad_idx  = index of destination area; this will be turned into the
     *            scratch area.
     */
    rc = nffs_area_find_corrupt_scratch(&good_idx, &bad_idx);
    if (rc != 0) {
        return rc;
    }

    /* Invalidate all objects resident in the bad area. */
    for (i = 0; i < NFFS_HASH_SIZE; i++) {
        entry = SLIST_FIRST(&nffs_hash[i]);
        while (entry != NULL) {
            next = SLIST_NEXT(entry, nhe_next);

            nffs_flash_loc_expand(entry->nhe_flash_loc,
                                 &area_idx, &area_offset);
            if (area_idx == bad_idx) {
                if (nffs_hash_id_is_block(entry->nhe_id)) {
                    rc = nffs_block_delete_from_ram(entry);
                    if (rc != 0) {
                        return rc;
                    }
                } else {
                    inode_entry = (struct nffs_inode_entry *)entry;
                    nffs_inode_setflags(inode_entry, NFFS_INODE_FLAG_OBSOLETE);
                }
            }

            entry = next;
        }
    }

    /* Now that the objects in the scratch area have been invalidated, reload
     * everything from the good area.
     */
    rc = nffs_restore_area_contents(good_idx);
    if (rc != 0) {
        return rc;
    }

    /* Convert the bad area into a scratch area. */
    rc = nffs_format_area(bad_idx, 1);
    if (rc != 0) {
        return rc;
    }
    nffs_scratch_area_idx = bad_idx;

    return 0;
}

static void
nffs_log_contents(void)
{
#if MYNEWT_VAL(LOG_LEVEL) > LOG_LEVEL_DEBUG
    return;
#endif

    struct nffs_inode_entry *inode_entry;
    struct nffs_hash_entry *entry;
    struct nffs_hash_entry *next;
    struct nffs_block block;
    struct nffs_inode inode;
    int rc;
    int i;

    NFFS_HASH_FOREACH(entry, i, next) {
        if (nffs_hash_id_is_block(entry->nhe_id)) {
            rc = nffs_block_from_hash_entry(&block, entry);
            assert(rc == 0 || rc == FS_ENOENT);
            NFFS_LOG(DEBUG, "block; id=%u inode_id=",
                     (unsigned int)entry->nhe_id);
            if (block.nb_inode_entry == NULL) {
                NFFS_LOG(DEBUG, "null ");
            } else {
                NFFS_LOG(DEBUG, "%u ",
                     (unsigned int)block.nb_inode_entry->nie_hash_entry.nhe_id);
            }

            NFFS_LOG(DEBUG, "prev_id=");
            if (block.nb_prev == NULL) {
                NFFS_LOG(DEBUG, "null ");
            } else {
                NFFS_LOG(DEBUG, "%u ", (unsigned int)block.nb_prev->nhe_id);
            }

            NFFS_LOG(DEBUG, "data_len=%u\n", block.nb_data_len);
        } else {
            inode_entry = (void *)entry;
            rc = nffs_inode_from_entry(&inode, inode_entry);
            if (rc == FS_ENOENT) {
                NFFS_LOG(DEBUG, "DUMMY file; id=%x ref=%d block_id=",
                         (unsigned int)entry->nhe_id, inode_entry->nie_refcnt);
                if (inode_entry->nie_last_block_entry == NULL) {
                    NFFS_LOG(DEBUG, "null");
                } else {
                    NFFS_LOG(DEBUG, "%x",
                     (unsigned int)inode_entry->nie_last_block_entry->nhe_id);
                }
            } else if (rc != 0) {
                continue;
            }
            /*assert(rc == 0);*/

            if (nffs_hash_id_is_file(entry->nhe_id)) {
                NFFS_LOG(DEBUG, "file; id=%u name=%.3s block_id=",
                         (unsigned int)entry->nhe_id, inode.ni_filename);
                if (inode_entry->nie_last_block_entry == NULL) {
                    NFFS_LOG(DEBUG, "null");
                } else {
                    NFFS_LOG(DEBUG, "%u",
                     (unsigned int)inode_entry->nie_last_block_entry->nhe_id);
                }
                NFFS_LOG(DEBUG, "\n");
            } else {
                inode_entry = (void *)entry;
                NFFS_LOG(DEBUG, "dir; id=%u name=%.3s\n",
                         (unsigned int)entry->nhe_id, inode.ni_filename);

            }
        }
    }
}

/**
 * Searches for a valid nffs file system among the specified areas.  This
 * function succeeds if a file system is detected among any subset of the
 * supplied areas.  If the area set does not contain a valid file system,
 * a new one can be created via a call to nffs_format().
 *
 * @param area_descs        The area set to search.  This array must be
 *                              terminated with a 0-length area.
 *
 * @return                  0 on success;
 *                          FS_ECORRUPT if no valid file system was detected;
 *                          other nonzero on error.
 */
int
nffs_restore_full(const struct nffs_area_desc *area_descs)
{
    struct nffs_disk_area disk_area;
    int cur_area_idx;
    int use_area;
    int rc;
    int i;

    /* Start from a clean state. */
    rc = nffs_misc_reset();
    if (rc) {
        return rc;
    }
    nffs_restore_largest_block_data_len = 0;
    nffs_current_area_descs = (struct nffs_area_desc*) area_descs;

    /* Read each area from flash. */
    for (i = 0; area_descs[i].nad_length != 0; i++) {
        if (i > NFFS_CONFIG_MAX_AREAS) {
            rc = FS_EINVAL;
            goto err;
        }

        rc = nffs_restore_detect_one_area(area_descs[i].nad_flash_id,
                                          area_descs[i].nad_offset,
                                          &disk_area);
        switch (rc) {
        case 0:
            use_area = 1;
            break;

        case FS_EUNEXP:    /* not formatted with current on-disk NFFS format */
        case FS_ECORRUPT:
            use_area = 0;
            break;

        default:
            goto err;
        }

        if (use_area) {
            if (disk_area.nda_id == NFFS_AREA_ID_NONE &&
                nffs_scratch_area_idx != NFFS_AREA_ID_NONE) {

                /* Don't allow more than one scratch area. */
                use_area = 0;
            }
        }

        if (use_area) {
            /* Populate RAM with a representation of this area. */
            cur_area_idx = nffs_num_areas;

            rc = nffs_misc_set_num_areas(nffs_num_areas + 1);
            if (rc != 0) {
                goto err;
            }

            nffs_areas[cur_area_idx].na_offset = area_descs[i].nad_offset;
            nffs_areas[cur_area_idx].na_length = area_descs[i].nad_length;
            nffs_areas[cur_area_idx].na_flash_id = area_descs[i].nad_flash_id;
            nffs_areas[cur_area_idx].na_gc_seq = disk_area.nda_gc_seq;
            nffs_areas[cur_area_idx].na_id = disk_area.nda_id;

            if (disk_area.nda_id == NFFS_AREA_ID_NONE) {
                nffs_areas[cur_area_idx].na_cur = NFFS_AREA_OFFSET_ID;
                nffs_scratch_area_idx = cur_area_idx;
            } else {
                nffs_areas[cur_area_idx].na_cur =
                    sizeof (struct nffs_disk_area);
                nffs_restore_area_contents(cur_area_idx);
            }
        }
    }

    /* All areas have been restored from flash. */

    if (nffs_scratch_area_idx == NFFS_AREA_ID_NONE) {
        /* No scratch area.  The system may have been rebooted in the middle of
         * a garbage collection cycle.  Look for a candidate scratch area.
         */
        rc = nffs_restore_corrupt_scratch();
        if (rc != 0) {
            if (rc == FS_ENOENT) {
                rc = FS_ECORRUPT;
            }
            goto err;
        }
    }

    /* Ensure this file system contains a valid scratch area. */
    rc = nffs_misc_validate_scratch();
    if (rc != 0) {
        goto err;
    }

    /* Make sure the file system contains a valid root directory. */
    rc = nffs_misc_validate_root_dir();
    if (rc != 0) {
        goto err;
    }

    /* Ensure there is a "/lost+found" directory. */
    rc = nffs_misc_create_lost_found_dir();
    if (rc != 0) {
        goto err;
    }

    /* Delete from RAM any objects that were invalidated when subsequent areas
     * were restored.
     */
    nffs_restore_sweep();

    /* Set the maximum data block size according to the size of the smallest
     * area.
     */
    rc = nffs_misc_set_max_block_data_len(nffs_restore_largest_block_data_len);
    if (rc != 0) {
        goto err;
    }

    NFFS_LOG(DEBUG, "CONTENTS\n");
    nffs_log_contents();

    return 0;

err:
    nffs_misc_reset();
    return rc;
}