/****************************************************************************
 * fs/spiffs/src/spiffs_gc.c
 *
 *   Copyright (C) 2018 Gregory Nutt. All rights reserved.
 *   Author: Gregory Nutt <gnutt@nuttx.org>
 *
 * This is a port of version 0.3.7 of SPIFFS by Peter Andersion.  That
 * version was originally released under the MIT license but is here re-
 * released under the NuttX BSD license.
 *
 *   Copyright (c) 2013-2017 Peter Andersson (pelleplutt1976@gmail.com)
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. 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.
 * 3. Neither the name NuttX nor the names of its contributors may be
 *    used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "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
 * COPYRIGHT OWNER OR CONTRIBUTORS 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.
 *
 ****************************************************************************/

/****************************************************************************
 * Included Files
 ****************************************************************************/

#include <nuttx/config.h>

#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <debug.h>
#include <inttypes.h>

#include "spiffs.h"
#include "spiffs_core.h"
#include "spiffs_cache.h"
#include "spiffs_gc.h"

/****************************************************************************
 * Private Types
 ****************************************************************************/

enum spiffs_gc_clean_state_e
{
  FIND_OBJ_DATA,
  MOVE_OBJ_DATA,
  MOVE_OBJ_NDX,
  FINISHED
};

struct spiffs_gc_s
{
  enum spiffs_gc_clean_state_e state;
  int16_t cur_objid;
  int16_t cur_objndx_spndx;
  int16_t cur_objndx_pgndx;
  int16_t cur_data_pgndx;
  int stored_scan_entry_index;
  bool objid_found;
};

/****************************************************************************
 * Private Functions
 ****************************************************************************/

/****************************************************************************
 * Name: spiffs_gc_erase_block
 *
 * Description:
 *   Erases a logical block and updates the erase counter.
 *   If cache is enabled, all pages that might be cached in this block
 *   is dropped.
 *
 * Input Parameters:
 *   fs     - A reference to the SPIFFS volume object instance
 *   blkndx - The block index to erase
 *
 * Returned Value:
 *   Zero (OK) is returned on success; A negated errno value is returned on
 *   any failure.
 *
 ****************************************************************************/

static int spiffs_gc_erase_block(FAR struct spiffs_s *fs, int16_t blkndx)
{
  int ret;
  int i;

  spiffs_gcinfo("Erase block=%04x\n", blkndx);

  /* Erase the block */

  ret = spiffs_erase_block(fs, blkndx);
  if (ret < 0)
    {
      ferr("ERROR: spiffs_erase_block() blkndx=%d failed: %d\n",
           blkndx, ret);
    }

  /* Then remove the pages from the cache. */

  for (i = 0; i < SPIFFS_GEO_PAGES_PER_BLOCK(fs); i++)
    {
      spiffs_cache_drop_page(fs, SPIFFS_PAGE_FOR_BLOCK(fs, blkndx) + i);
    }

  return ret;
}

/****************************************************************************
 * Name: spiffs_gc_epage_stats
 *
 * Description:
 *   Checks if garbage collecting is necessary. If so a candidate block is
 *   found, cleansed and erased
 *
 *   This function will  try to make room for given amount of bytes in the
 *   filesystem by moving pages and erasing blocks.
 *
 *   If it is physically impossible, err_no will be set to -ENOSPC. If
 *   there already is this amount (or more) of free space, SPIFFS_gc will
 *   silently return. It is recommended to call statfs() before invoking
 *   this method in order to determine what amount of bytes to give.
 *
 *   NB: the garbage collector is automatically called when spiffs needs free
 *   pages. The reason for this function is to give possibility to do
 *   background tidying when user knows the system is idle.
 *
 * Input Parameters:
 *   fs            the file system struct
 *   len           amount of data that should be freed
 *
 * Returned Value:
 *   Zero (OK) is returned on success; A negated errno value is returned on
 *   any failure.  -ENODATA is returned if no blocks were deleted.
 *
 ****************************************************************************/

/* Updates page statistics for a block that is about to be erased */

static int spiffs_gc_epage_stats(FAR struct spiffs_s *fs, int16_t blkndx)
{
  FAR int16_t *objlu_buf = (int16_t *) fs->lu_work;
  uint32_t dele          = 0;
  uint32_t allo          = 0;
  int entries_per_page   = (SPIFFS_GEO_PAGE_SIZE(fs) / sizeof(int16_t));
  int cur_entry          = 0;
  int obj_lookup_page    = 0;
  int ret                = OK;

  /* Check each object lookup page */

  while (ret >= 0 && obj_lookup_page < (int)SPIFFS_OBJ_LOOKUP_PAGES(fs))
    {
      int entry_offset = obj_lookup_page * entries_per_page;
      ret = spiffs_cache_read(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ, 0,
                              blkndx * SPIFFS_GEO_BLOCK_SIZE(fs) +
                              SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
                              SPIFFS_GEO_PAGE_SIZE(fs), fs->lu_work);

      /* Check each entry */

      while (ret >= 0 &&
             cur_entry - entry_offset < entries_per_page &&
             cur_entry <
             (int)(SPIFFS_GEO_PAGES_PER_BLOCK(fs) -
                   SPIFFS_OBJ_LOOKUP_PAGES(fs)))
        {
          int16_t id = objlu_buf[cur_entry - entry_offset];

          if (id == SPIFFS_OBJID_FREE)
            {
            }
          else if (id == SPIFFS_OBJID_DELETED)
            {
              dele++;
            }
          else
            {
              allo++;
            }

          cur_entry++;
        }

      obj_lookup_page++;
    }

  spiffs_gcinfo("Wipe pallo=%" PRIu32 " pdele=%" PRIu32 "\n", allo,  dele);

  fs->alloc_pages   -= allo;
  fs->deleted_pages -= dele;
  return ret;
}

/****************************************************************************
 * Name: spiffs_gc_find_candidate
 *
 * Description:
 *   Finds block candidates to erase
 *
 * Input Parameters:
 *   fs               - A reference to the SPIFFS volume object instance
 *   block_candidates - Memory to return an array of candidates
 *   candidate_count  - Memory to return the number of candidates
 *   fs_crammed       - True: Filesystem is full
 *
 * Returned Value:
 *   Zero (OK) is returned on success; A negated errno value is returned on
 *   any failure.  -ENODATA is returned if no blocks were deleted.
 *
 ****************************************************************************/

static int spiffs_gc_find_candidate(FAR struct spiffs_s *fs,
                                    FAR int16_t **block_candidates,
                                    FAR int *candidate_count,
                                    bool fs_crammed)
{
  FAR int32_t *cand_scores;
  FAR int16_t *objlu_buf  = (FAR int16_t *)fs->lu_work;
  FAR int16_t *cand_blocks;
  uint32_t blocks         = SPIFFS_GEO_BLOCK_COUNT(fs);
  int16_t cur_block       = 0;
  uint32_t cur_block_addr = 0;
  int entries_per_page;
  int max_candidates;
  int cur_entry           = 0;
  int ret                 = OK;

  /* Using fs->work area as sorted candidate memory,
   * (int16_t)cand_blkndx/(int32_t)score
   */

  max_candidates =
    MIN(SPIFFS_GEO_BLOCK_COUNT(fs),
        (SPIFFS_GEO_PAGE_SIZE(fs) - 8) /
         (sizeof(int16_t) + sizeof(int32_t)));
  *candidate_count = 0;
  memset(fs->work, 0xff, SPIFFS_GEO_PAGE_SIZE(fs));

  /* Divide up work area into block indices and scores */

  cand_blocks = (FAR int16_t *)fs->work;
  cand_scores =
    (FAR int32_t *)(fs->work + max_candidates * sizeof(int16_t));

  /* Align cand_scores on int32_t boundary */

  cand_scores =
    (FAR int32_t *)(((intptr_t)cand_scores + sizeof(intptr_t) - 1) &
                    ~(sizeof(intptr_t) - 1));

  *block_candidates = cand_blocks;

  entries_per_page = (SPIFFS_GEO_PAGE_SIZE(fs) / sizeof(int16_t));

  /* Check each block */

  while (ret >= 0 && blocks--)
    {
      uint16_t deleted_pages_in_block = 0;
      uint16_t used_pages_in_block    = 0;
      int obj_lookup_page             = 0;

      /* check each object lookup page */

      while (ret >= 0 &&
             obj_lookup_page < (int)SPIFFS_OBJ_LOOKUP_PAGES(fs))
        {
          int entry_offset = obj_lookup_page * entries_per_page;
          ret = spiffs_cache_read(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
                                  0, cur_block_addr +
                                  SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
                                  SPIFFS_GEO_PAGE_SIZE(fs), fs->lu_work);

          /* Check each entry */

          while (ret >= 0 &&
                 cur_entry - entry_offset < entries_per_page &&
                 cur_entry <
                 (int)(SPIFFS_GEO_PAGES_PER_BLOCK(fs) -
                       SPIFFS_OBJ_LOOKUP_PAGES(fs)))
            {
              int16_t id = objlu_buf[cur_entry - entry_offset];

              if (id == SPIFFS_OBJID_FREE)
                {
                  /* When a free entry is encountered, scan logic ensures
                   * that all following entries are free also
                   */

                  ret = 1;      /* Kill object lu loop */
                  break;
                }
              else if (id == SPIFFS_OBJID_DELETED)
                {
                  deleted_pages_in_block++;
                }
              else
                {
                  used_pages_in_block++;
                }

              cur_entry++;
            }

          obj_lookup_page++;
        }

      if (ret == 1)
        {
          ret = OK;
        }

      /* Calculate score and insert into candidate table stoneage sort, but
       * probably not so many blocks
       */

      if (ret >= 0 /* && deleted_pages_in_block > 0 */)
        {
          int32_t score;
          int16_t erase_count;
          int16_t erase_age;
          int candndx;

          /* Read erase count */

          ret = spiffs_cache_read(fs, SPIFFS_OP_C_READ | SPIFFS_OP_T_OBJ_LU2,
                                  0, SPIFFS_ERASE_COUNT_PADDR(fs, cur_block),
                                  sizeof(int16_t), (uint8_t *)&erase_count);
          if (ret < 0)
            {
              ferr("ERROR: spiffs_cache_read() failed: %d\n", ret);
              return ret;
            }

          /* Calculate the erase age */

          if (fs->max_erase_count > erase_count)
            {
              erase_age = fs->max_erase_count - erase_count;
            }
          else
            {
              erase_age =
                SPIFFS_OBJID_FREE - (erase_count - fs->max_erase_count);
            }

          score =
            deleted_pages_in_block * CONFIG_SPIFFS_GC_DELWGT +
            used_pages_in_block * CONFIG_SPIFFS_GC_USEDWGT +
            erase_age * (fs_crammed ? 0 : CONFIG_SPIFFS_GC_ERASEAGEWGT);

          candndx = 0;

          spiffs_gcinfo("blkndx=%04x del=%d use=%d score=%" PRIu32 "\n",
                        cur_block, deleted_pages_in_block,
                        used_pages_in_block, score);

          while (candndx < max_candidates)
            {
              if (cand_blocks[candndx] == (int16_t) - 1)
                {
                  cand_blocks[candndx] = cur_block;
                  cand_scores[candndx] = score;
                  break;
                }
              else if (cand_scores[candndx] < score)
                {
                  int reorder_candndx = max_candidates - 2;
                  while (reorder_candndx >= candndx)
                    {
                      cand_blocks[reorder_candndx + 1] =
                        cand_blocks[reorder_candndx];
                      cand_scores[reorder_candndx + 1] =
                        cand_scores[reorder_candndx];
                      reorder_candndx--;
                    }

                  cand_blocks[candndx] = cur_block;
                  cand_scores[candndx] = score;
                  break;
                }

              candndx++;
            }

          (*candidate_count)++;
        }

      cur_entry = 0;
      cur_block++;
      cur_block_addr += SPIFFS_GEO_BLOCK_SIZE(fs);
    }

  return ret;
}

/****************************************************************************
 * Name: spiffs_gc_clean
 *
 * Description:
 *   Empties given block by moving all data into free pages of another block
 *   Strategy:
 *     loop:
 *     - Scan object lookup for object data pages.
 *     - For first found id, check spndx and load corresponding object index
 *       page to memory.
 *     - Push object scan lookup entry index.
 *         Rescan object lookup, find data pages with same id and referenced
 *           by same object index.
 *         Move data page, update object index in memory.
 *         When reached end of lookup, store updated object index.
 *     - Pop object scan lookup entry index.
 *     - Repeat loop until end of object lookup.
 *     - Scan object lookup again for remaining object index pages, move to
 *       new page in other block.
 *
 * Input Parameters:
 *   fs            the file system struct
 *   len           amount of data that should be freed
 *
 * Returned Value:
 *   Zero (OK) is returned on success; A negated errno value is returned on
 *   any failure.  -ENODATA is returned if no blocks were deleted.
 *
 ****************************************************************************/

static int spiffs_gc_clean(FAR struct spiffs_s *fs, int16_t blkndx)
{
  const int entries_per_page = (SPIFFS_GEO_PAGE_SIZE(fs) / sizeof(int16_t));
  int ret = OK;

  /* This is the global localizer being pushed and popped */

  struct spiffs_gc_s gc;                 /* Our stack frame/state */
  FAR int16_t *objlu_buf;
  FAR struct spiffs_pgobj_ndxheader_s *objhdr;
  FAR struct spiffs_page_objndx_s *objndx;
  int16_t cur_pgndx      = 0;
  int cur_entry          = 0;

  spiffs_gcinfo("Cleaning block %04x\n", blkndx);

  memset(&gc, 0, sizeof(struct spiffs_gc_s));
  gc.state  = FIND_OBJ_DATA;

  objlu_buf = (FAR int16_t *)fs->lu_work;
  objhdr    = (FAR struct spiffs_pgobj_ndxheader_s *)fs->work;
  objndx    = (struct spiffs_page_objndx_s *)fs->work;

  if (fs->free_blkndx == blkndx)
    {
      /* Move free cursor to next block, cannot use free pages from the block
       * we want to clean
       */

      fs->free_blkndx = (blkndx + 1) % SPIFFS_GEO_BLOCK_COUNT(fs);
      fs->free_entry = 0;
      spiffs_gcinfo("Move free cursor to block=%04x\n", fs->free_blkndx);
    }

  while (ret >= 0 && gc.state != FINISHED)
    {
      int obj_lookup_page;
      uint8_t scan;

      spiffs_gcinfo("state=%d entry=%d\n", gc.state, cur_entry);

      gc.objid_found  = false;  /* Reset (to no found data page) */

      /* Scan through lookup pages */

      obj_lookup_page = cur_entry / entries_per_page;
      scan            = 1;

      /* Check each object lookup page */

      while (scan && ret >= 0 &&
             obj_lookup_page < (int)SPIFFS_OBJ_LOOKUP_PAGES(fs))
        {
          int entry_offset = obj_lookup_page * entries_per_page;

          ret = spiffs_cache_read(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
                                  0, blkndx * SPIFFS_GEO_BLOCK_SIZE(fs) +
                                  SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
                                  SPIFFS_GEO_PAGE_SIZE(fs), fs->lu_work);

          /* Check each object lookup entry */

          while (scan && ret >= 0 &&
                 cur_entry - entry_offset < entries_per_page &&
                 cur_entry <
                 (int)(SPIFFS_GEO_PAGES_PER_BLOCK(fs) -
                       SPIFFS_OBJ_LOOKUP_PAGES(fs)))
            {
              int16_t id = objlu_buf[cur_entry - entry_offset];

              cur_pgndx =
                SPIFFS_OBJ_LOOKUP_ENTRY_TO_PGNDX(fs, blkndx, cur_entry);

              /* Act upon object id depending on gc state */

              switch (gc.state)
                {
                case FIND_OBJ_DATA:

                  /* Find a data page. */

                  if (id != SPIFFS_OBJID_DELETED &&
                      id != SPIFFS_OBJID_FREE &&
                      ((id & SPIFFS_OBJID_NDXFLAG) == 0))
                    {
                      /* Found a data page, stop scanning and handle in
                       * switch case below
                       */

                      spiffs_gcinfo(
                        "Found data page, state=%d, objid=%04x\n",
                        gc.state, id);

                      gc.objid_found    = true;
                      gc.cur_objid      = id;
                      gc.cur_data_pgndx = cur_pgndx;
                      scan              = 0;
                    }
                  break;

                case MOVE_OBJ_DATA:

                  /* Evacuate found data pages for corresponding object index
                   * we have in memory, update memory representation
                   */

                  if (id == gc.cur_objid)
                    {
                      struct spiffs_page_header_s phdr;

                      ret = spiffs_cache_read(fs,
                                      SPIFFS_OP_T_OBJ_LU2 | SPIFFS_OP_C_READ,
                                      0, SPIFFS_PAGE_TO_PADDR(fs, cur_pgndx),
                                      sizeof(struct spiffs_page_header_s),
                                      (FAR uint8_t *)&phdr);
                      if (ret < 0)
                        {
                          ferr("ERROR: spiffs_cache_read() failed: %d\n",
                               ret);
                          return ret;
                        }

                      spiffs_gcinfo("Found data page %04x:%04x @%04x\n",
                                    gc.cur_objid, phdr.spndx, cur_pgndx);

                      if (SPIFFS_OBJNDX_ENTRY_SPNDX(fs, phdr.spndx) !=
                          gc.cur_objndx_spndx)
                        {
                          spiffs_gcinfo(
                            "No objndx spndx match, take in another run\n");
                        }
                      else
                        {
                          int16_t new_data_pgndx;
                          if (phdr.flags & SPIFFS_PH_FLAG_DELET)
                            {
                              /* Move page */

                              ret = spiffs_page_move(fs, 0, 0, id, &phdr,
                                                 cur_pgndx, &new_data_pgndx);

                              spiffs_gcinfo(
                                "Move objndx=%04x:%04x page=%04x to %04x\n",
                                gc.cur_objid, phdr.spndx,
                                cur_pgndx, new_data_pgndx);

                              if (ret < 0)
                                {
                                  ferr("ERROR: spiffs_page_move(): %d\n",
                                       ret);
                                  return ret;
                                }

                              /* Move wipes obj_lu, reload it */

                              ret =
                                spiffs_cache_read(fs,
                                   SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
                                   0,
                                   blkndx * SPIFFS_GEO_BLOCK_SIZE(fs) +
                                   SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
                                   SPIFFS_GEO_PAGE_SIZE(fs),
                                   fs->lu_work);
                              if (ret < 0)
                                {
                                  ferr("ERROR: spiffs_cache_read(): %d\n",
                                       ret);
                                  return ret;
                                }
                            }
                          else
                            {
                              /* Page is deleted but not deleted in lookup.
                               * Scrap it - might seem unnecessary as we will
                               * erase this block, but we might get aborted
                               */

                              spiffs_gcinfo(
                                "Wipe objndx=%04x:%04x page=%04x\n",
                                id, phdr.spndx, cur_pgndx);

                              ret = spiffs_page_delete(fs, cur_pgndx);
                              if (ret < 0)
                                {
                                  ferr("ERROR: spiffs_page_delete(): %d\n",
                                       ret);
                                  return ret;
                                }

                              new_data_pgndx = SPIFFS_OBJID_FREE;
                            }

                          /* Update memory representation of object index
                           * page with new data page
                           */

                          if (gc.cur_objndx_spndx == 0)
                            {
                              /* Update object index header page */

                              ((FAR int16_t *)((FAR uint8_t *)objhdr +
                                 sizeof(struct spiffs_pgobj_ndxheader_s)))
                                 [phdr.spndx] = new_data_pgndx;

                              spiffs_gcinfo(
                                "Wrote page=%04x to objhdr entry=%04x\n",
                                new_data_pgndx,
                                (int)SPIFFS_OBJNDX_ENTRY(fs, phdr.spndx));
                            }
                          else
                            {
                              /* Update object index page */

                              ((FAR int16_t *)((FAR uint8_t *)objndx +
                                sizeof(struct spiffs_page_objndx_s)))
                                  [SPIFFS_OBJNDX_ENTRY(fs, phdr.spndx)] =
                                    new_data_pgndx;

                              spiffs_gcinfo(
                                "Wrote page=%04x to objndx entry=%04x\n",
                                new_data_pgndx,
                                (int)SPIFFS_OBJNDX_ENTRY(fs, phdr.spndx));
                            }
                        }
                    }
                  break;

                case MOVE_OBJ_NDX:

                  /* Find and evacuate object index pages */

                  if (id != SPIFFS_OBJID_DELETED &&
                      id != SPIFFS_OBJID_FREE &&
                      (id & SPIFFS_OBJID_NDXFLAG) != 0)
                    {
                      /* Found an index object id */

                      struct spiffs_page_header_s phdr;
                      int16_t new_pgndx;

                      /* Load header */

                      ret = spiffs_cache_read(fs,
                                      SPIFFS_OP_T_OBJ_LU2 | SPIFFS_OP_C_READ,
                                      0,
                                      SPIFFS_PAGE_TO_PADDR(fs, cur_pgndx),
                                      sizeof(struct spiffs_page_header_s),
                                      (FAR uint8_t *)&phdr);
                      if (ret < 0)
                        {
                          ferr("ERROR: spiffs_cache_read() failed: %d\n",
                               ret);
                          return ret;
                        }

                      if (phdr.flags & SPIFFS_PH_FLAG_DELET)
                        {
                          /* Move page */

                          ret = spiffs_page_move(fs, 0, 0, id, &phdr,
                                                 cur_pgndx, &new_pgndx);

                          spiffs_gcinfo(
                            "Move objndx=%04x:%04x page=%04x to %04x\n",
                            id, phdr.spndx, cur_pgndx, new_pgndx);

                          if (ret < 0)
                            {
                              ferr("ERROR: spiffs_page_move() failed: %d\n",
                                   ret);
                              return ret;
                            }

                          spiffs_fobj_event(fs,
                                    (FAR struct spiffs_page_objndx_s *)&phdr,
                                    SPIFFS_EV_NDXMOV, id,
                                    phdr.spndx, new_pgndx, 0);

                          /* Move wipes obj_lu, reload it */

                          ret =
                            spiffs_cache_read(fs,
                                   SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
                                   0,
                                   blkndx * SPIFFS_GEO_BLOCK_SIZE(fs) +
                                   SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
                                   SPIFFS_GEO_PAGE_SIZE(fs), fs->lu_work);
                          if (ret < 0)
                            {
                              ferr("ERROR: spiffs_cache_read() failed: %d\n",
                                   ret);
                              return ret;
                            }
                        }
                      else
                        {
                          /* Page is deleted but not deleted in lookup, scrap
                           * it - might seem unnecessary as we will erase
                           * this block, but we might get aborted
                           */

                          spiffs_gcinfo("Wipe objndx=%04x:%04x page=%04x\n",
                                        id, phdr.spndx, cur_pgndx);

                          ret = spiffs_page_delete(fs, cur_pgndx);
                          if (ret < 0)
                            {
                              ferr("ERROR: spiffs_fobj_event() failed: %d\n",
                                   ret);
                              return ret;
                            }

                          spiffs_fobj_event(fs, NULL,
                                            SPIFFS_EV_NDXDEL, id,
                                            phdr.spndx, cur_pgndx, 0);
                        }
                    }
                  break;

                default:
                  scan = 0;
                  break;
                }

              cur_entry++;
            }

          obj_lookup_page++;    /* No need to check scan variable here,
                                 * obj_lookup_page is set in start of loop
                                 */
        }

      if (ret < 0)
        {
          break;
        }

      /* State finalization and switch */

      switch (gc.state)
        {
        case FIND_OBJ_DATA:
          if (gc.objid_found)
            {
              struct spiffs_page_header_s phdr;
              int16_t objndx_pgndx;

              /* Handle found data page.  Find out corresponding objndx page
               * and load it to memory
               */

              gc.stored_scan_entry_index = cur_entry; /* Push cursor */
              cur_entry                  = 0;         /* Sestart scan from start */
              gc.state                   = MOVE_OBJ_DATA;

              ret = spiffs_cache_read(fs,
                                      SPIFFS_OP_T_OBJ_LU2 | SPIFFS_OP_C_READ,
                                      0, SPIFFS_PAGE_TO_PADDR(fs, cur_pgndx),
                                      sizeof(struct spiffs_page_header_s),
                                      (FAR uint8_t *)&phdr);
              if (ret < 0)
                {
                  ferr("ERROR: spiffs_fobj_event() failed: %d\n", ret);
                  return ret;
                }

              gc.cur_objndx_spndx =
                SPIFFS_OBJNDX_ENTRY_SPNDX(fs, phdr.spndx);

              spiffs_gcinfo("Find objndx spndx=%04x\n", gc.cur_objndx_spndx);

              ret = spiffs_objlu_find_id_and_span(fs,
                                         gc.cur_objid | SPIFFS_OBJID_NDXFLAG,
                                         gc.cur_objndx_spndx, 0,
                                         &objndx_pgndx);
              if (ret == -ENOENT)
                {
                  /* On borked systems we might get an ERR_NOT_FOUND here -
                   * this is handled by simply deleting the page as it is not
                   * referenced from anywhere
                   */

                  spiffs_gcinfo("objndx not found! Wipe page %04x\n",
                                gc.cur_data_pgndx);

                  ret = spiffs_page_delete(fs, gc.cur_data_pgndx);
                  if (ret < 0)
                    {
                      ferr("ERROR: spiffs_page_delete() failed: %d\n", ret);
                      return ret;
                    }

                  /* Then we restore states and continue scanning for data
                   * pages
                   */

                  cur_entry = gc.stored_scan_entry_index;  /* pop cursor */
                  gc.state  = FIND_OBJ_DATA;
                  break;
                }

              if (ret < 0)
                {
                  return ret;
                }

              spiffs_gcinfo("Found object index at page=%04x\n",
                            objndx_pgndx);

              ret = spiffs_cache_read(fs,
                                      SPIFFS_OP_T_OBJ_LU2 | SPIFFS_OP_C_READ,
                                      0,
                                      SPIFFS_PAGE_TO_PADDR(fs, objndx_pgndx),
                                      SPIFFS_GEO_PAGE_SIZE(fs), fs->work);
              if (ret < 0)
                {
                  ferr("ERROR: spiffs_cache_read() failed: %d\n", ret);
                  return ret;
                }

              /* Cannot allow a gc if the presumed index in fact is no
               * index, a check must run or lot of data may be lost
               */

              ret = spiffs_validate_objndx(&objndx->phdr,
                                         gc.cur_objid | SPIFFS_OBJID_NDXFLAG,
                                         gc.cur_objndx_spndx);
              if (ret < 0)
                {
                  ferr("ERROR: spiffs_validate_objndx() failed: %d\n", ret);
                  return ret;
                }

              gc.cur_objndx_pgndx = objndx_pgndx;
            }
          else
            {
              /* No more data pages found, passed through all block, start
               * evacuating object indices
               */

              gc.state  = MOVE_OBJ_NDX;
              cur_entry = 0;    /* Restart entry scan index */
            }
          break;

        case MOVE_OBJ_DATA:
          {
            int16_t new_objndx_pgndx;

            /* Store modified objndx (hdr) page residing in memory now that
             * all data pages belonging to this object index and residing in
             * the block we want to evacuate
             */

            gc.state  = FIND_OBJ_DATA;
            cur_entry = gc.stored_scan_entry_index;     /* pop cursor */

            if (gc.cur_objndx_spndx == 0)
              {
                /* Store object index header page */

                ret = spiffs_fobj_update_ndxhdr(fs, 0,
                                         gc.cur_objid | SPIFFS_OBJID_NDXFLAG,
                                         gc.cur_objndx_pgndx, fs->work, 0,
                                         0, &new_objndx_pgndx);

                spiffs_gcinfo("Store modified objhdr page=%04x:%04x\n",
                              new_objndx_pgndx, 0);

                if (ret < 0)
                  {
                    ferr("ERROR: spiffs_fobj_update_ndxhdr() failed: %d\n",
                         ret);
                    return ret;
                  }
              }
            else
              {
                /* Store object index page */

                ret =  spiffs_page_move(fs, 0, fs->work,
                                        gc.cur_objid | SPIFFS_OBJID_NDXFLAG,
                                        0, gc.cur_objndx_pgndx,
                                        &new_objndx_pgndx);

                spiffs_gcinfo("Store modified objndx page=%04x:%04x\n",
                              new_objndx_pgndx, objndx->phdr.spndx);

                if (ret < 0)
                  {
                    ferr("ERROR: spiffs_page_move() failed: %d\n", ret);
                    return ret;
                  }

                spiffs_fobj_event(fs,
                                 (FAR struct spiffs_page_objndx_s *)fs->work,
                                 SPIFFS_EV_NDXUPD, gc.cur_objid,
                                 objndx->phdr.spndx,
                                 new_objndx_pgndx, 0);
              }
          }
          break;

        case MOVE_OBJ_NDX:
          /* Scanned through all blocks, no more object indices found - our
           * work here is done
           */

          gc.state = FINISHED;
          break;

        default:
          cur_entry = 0;
          break;
        }

      spiffs_gcinfo("state=%d\n", gc.state);
    }

  return ret;
}

/****************************************************************************
 * Public Functions
 ****************************************************************************/

/****************************************************************************
 * Name: spiffs_gc_quick
 *
 * Description:
 *   Searches for blocks where all entries are deleted - if one is found,
 *   the block is erased. Compared to the non-quick gc, the quick one ensures
 *   that no updates are needed on existing objects on pages that are erased.
 *
 * Input Parameters:
 *   fs             - A reference to the SPIFFS volume object instance
 *   max_free_pages - The maximum pages to free
 *
 * Returned Value:
 *   Zero (OK) is returned on success; A negated errno value is returned on
 *   any failure.  -ENODATA is returned if no blocks were deleted.
 *
 ****************************************************************************/

int spiffs_gc_quick(FAR struct spiffs_s *fs, uint16_t max_free_pages)
{
  FAR int16_t *objlu_buf  = (int16_t *) fs->lu_work;
  uint32_t cur_block_addr = 0;
  uint32_t blocks         = SPIFFS_GEO_BLOCK_COUNT(fs);
  int16_t cur_block       = 0;
  int entries_per_page    = (SPIFFS_GEO_PAGE_SIZE(fs) / sizeof(int16_t));
  int cur_entry           = 0;
  int ret                 = OK;

  spiffs_gcinfo("max_free_pages=%u\n", max_free_pages);
#ifdef CONFIG_SPIFFS_GCDBG
  fs->stats_gc_runs++;
#endif

  /* Find fully deleted blocks */

  while (ret >= 0 && blocks--)
    {
      uint16_t deleted_pages_in_block = 0;
      uint16_t free_pages_in_block = 0;
      int obj_lookup_page = 0;

      /* Check each object lookup page */

      while (ret >= 0 &&
             obj_lookup_page < (int)SPIFFS_OBJ_LOOKUP_PAGES(fs))
        {
          int entry_offset = obj_lookup_page * entries_per_page;

          ret = spiffs_cache_read(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
                                  0, cur_block_addr +
                                  SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
                                  SPIFFS_GEO_PAGE_SIZE(fs), fs->lu_work);

          /* Check each entry */

          while (ret >= 0 &&
                 cur_entry - entry_offset < entries_per_page &&
                 cur_entry <
                 (int)(SPIFFS_GEO_PAGES_PER_BLOCK(fs) -
                       SPIFFS_OBJ_LOOKUP_PAGES(fs)))
            {
              int16_t id = objlu_buf[cur_entry - entry_offset];

              if (id == SPIFFS_OBJID_DELETED)
                {
                  deleted_pages_in_block++;
                }
              else if (id == SPIFFS_OBJID_FREE)
                {
                  /* Kill scan, go for next block */

                  free_pages_in_block++;
                  if (free_pages_in_block > max_free_pages)
                    {
                      obj_lookup_page = SPIFFS_OBJ_LOOKUP_PAGES(fs);
                      ret = 1;  /* Kill object lu loop */
                      break;
                    }
                }
              else
                {
                  /* Kill scan, go for next block */

                  obj_lookup_page = SPIFFS_OBJ_LOOKUP_PAGES(fs);
                  ret = 1;      /* Kill object lu loop */
                  break;
                }

              cur_entry++;
            }

          obj_lookup_page++;
        }

      if (ret == 1)
        {
          ret = OK;
        }

      if (ret >= 0 &&
          deleted_pages_in_block + free_pages_in_block ==
          SPIFFS_GEO_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs) &&
          free_pages_in_block <= max_free_pages)
        {
          /* Found a fully deleted block */

          fs->deleted_pages -= deleted_pages_in_block;
          ret = spiffs_gc_erase_block(fs, cur_block);
          return ret;
        }

      cur_entry = 0;
      cur_block++;
      cur_block_addr += SPIFFS_GEO_BLOCK_SIZE(fs);
    }

  if (ret >= 0)
    {
      /* No deleted blocks */

      ret = -ENODATA;
    }

  return ret;
}

/****************************************************************************
 * Name: spiffs_gc_check
 *
 * Description:
 *   Checks if garbage collecting is necessary. If so a candidate block is
 *   found, cleansed and erased
 *
 *   This function will  try to make room for given amount of bytes in the
 *   filesystem by moving pages and erasing blocks.
 *
 *   If it is physically impossible, err_no will be set to -ENOSPC. If
 *   there already is this amount (or more) of free space, SPIFFS_gc will
 *   silently return. It is recommended to call statfs() before invoking
 *   this method in order to determine what amount of bytes to give.
 *
 *   NB: the garbage collector is automatically called when spiffs needs free
 *   pages. The reason for this function is to give possibility to do
 *   background tidying when user knows the system is idle.
 *
 * Input Parameters:
 *   fs            the file system struct
 *   len           amount of data that should be freed
 *
 * Returned Value:
 *   Zero (OK) is returned on success; A negated errno value is returned on
 *   any failure.  -ENODATA is returned if no blocks were deleted.
 *
 ****************************************************************************/

int spiffs_gc_check(FAR struct spiffs_s *fs, off_t len)
{
  int32_t free_pages;
  uint32_t needed_pages;
  int tries = 0;
  int ret;

  /* Get the number of free pages */

  free_pages = (SPIFFS_GEO_PAGES_PER_BLOCK(fs) -
                SPIFFS_OBJ_LOOKUP_PAGES(fs)) *
                (SPIFFS_GEO_BLOCK_COUNT(fs) - 2) -
                fs->alloc_pages - fs->deleted_pages;

  spiffs_gcinfo("len=%ld free_blocks=%lu free_pages=%ld\n",
                (long)len, (unsigned long)fs->free_blocks,
                (long)free_pages);

  if (fs->free_blocks > 3 &&
      (int32_t)len < free_pages * (int32_t)SPIFFS_DATA_PAGE_SIZE(fs))
    {
      spiffs_gcinfo("Sufficient free space is available  Do nothing.\n");
      return OK;
    }

  /* Get the number of pages needed */

  needed_pages = (len + SPIFFS_DATA_PAGE_SIZE(fs) - 1) /
                 SPIFFS_DATA_PAGE_SIZE(fs);

#if 0
  if (fs->free_blocks <= 2 && (int32_t)needed_pages > free_pages)
    {
      spiffs_gcinfo("Full freeblk=%d needed=%d free=%d dele=%d\n",
                    fs->free_blocks, needed_pages, free_pages,
                    fs->deleted_pages);
      return -ENOSPC;
    }
#endif

  if ((int32_t)needed_pages > (int32_t)(free_pages + fs->deleted_pages))
    {
      spiffs_gcinfo("Full freeblk=%" PRIu32 " needed=%" PRIu32 " "
                    "free=%" PRIu32 " dele=%" PRIu32 "\n",
                    fs->free_blocks, needed_pages, free_pages,
                    fs->deleted_pages);
      return -ENOSPC;
    }

  do
    {
      FAR int16_t *cands;
      int count;
      int16_t cand;
      int32_t prev_free_pages = free_pages;

      spiffs_gcinfo("#%d: run gc free_blocks=%" PRIu32 " pfree="
                    "%" PRIu32 " pallo=%" PRIu32 " pdele=%" PRIu32 ""
                    " [%" PRIu32 "] len=%" PRIuOFF " of %" PRIu32 "\n",
                    tries, fs->free_blocks, free_pages,
                    fs->alloc_pages, fs->deleted_pages,
                    (free_pages + fs->alloc_pages + fs->deleted_pages),
                    len, (uint32_t)(free_pages * SPIFFS_DATA_PAGE_SIZE(fs)));

      /* If the fs is crammed, ignore block age when selecting candidate -
       * kind of a bad state
       */

      ret = spiffs_gc_find_candidate(fs, &cands, &count, free_pages <= 0);
      if (ret < 0)
        {
          ferr("ERROR: spiffs_gc_find_candidate() failed: %d\n", ret);
          return ret;
        }

      if (count == 0)
        {
          spiffs_gcinfo("No candidates, return\n");
          return (int32_t) needed_pages < free_pages ? OK : -ENOSPC;
        }

#ifdef CONFIG_SPIFFS_GCDBG
      fs->stats_gc_runs++;
#endif
      cand = cands[0];

      ret = spiffs_gc_clean(fs, cand);

      spiffs_gcinfo("Cleaning block %d, result=%d\n", cand, ret);

      if (ret < 0)
        {
          ferr("ERROR: spiffs_gc_clean() failed: %d\n", ret);
          return ret;
        }

      ret = spiffs_gc_epage_stats(fs, cand);
      if (ret < 0)
        {
          ferr("ERROR: spiffs_gc_epage_stats() failed: %d\n", ret);
          return ret;
        }

      ret = spiffs_gc_erase_block(fs, cand);
      if (ret < 0)
        {
          ferr("ERROR: spiffs_gc_erase_block() failed: %d\n", ret);
          return ret;
        }

      free_pages = (SPIFFS_GEO_PAGES_PER_BLOCK(fs) -
                    SPIFFS_OBJ_LOOKUP_PAGES(fs)) *
                    (SPIFFS_GEO_BLOCK_COUNT(fs) - 2) -
                    fs->alloc_pages - fs->deleted_pages;

      if (prev_free_pages <= 0 && prev_free_pages == free_pages)
        {
          /* Abort early to reduce wear, at least tried once */

          spiffs_gcinfo("Early abort, no result on gc when fs crammed\n");
          break;
        }
    }
  while (++tries < CONFIG_SPIFFS_GC_MAXRUNS &&
         (fs->free_blocks <= 2 ||
          (int32_t) len > free_pages * (int32_t) SPIFFS_DATA_PAGE_SIZE(fs)));

  /* Re-calculate the number of free pages */

  free_pages = (SPIFFS_GEO_PAGES_PER_BLOCK(fs) -
                SPIFFS_OBJ_LOOKUP_PAGES(fs)) *
                (SPIFFS_GEO_BLOCK_COUNT(fs) - 2) -
                fs->alloc_pages - fs->deleted_pages;

  if ((int32_t) len > free_pages * (int32_t)SPIFFS_DATA_PAGE_SIZE(fs))
    {
      ret = -ENOSPC;
    }

  spiffs_gcinfo("Finished, %" PRIu32 " dirty, blocks, %" PRIu32 " "
                "free, %" PRIu32 " pages free, %d tries, ret=%d\n",
                fs->alloc_pages + fs->deleted_pages,
                fs->free_blocks, free_pages, tries, ret);

  return ret;
}
