armsrc/spiffs_gc.c

   1 //-----------------------------------------------------------------------------
   2 // Borrowed initially from https://github.com/pellepl/spiffs
   3 // Copyright (c) 2013-2017 Peter Andersson (pelleplutt1976 at gmail.com)
   4 // Copyright (C) Proxmark3 contributors. See AUTHORS.md for details.
   5 //
   6 // This program is free software: you can redistribute it and/or modify
   7 // it under the terms of the GNU General Public License as published by
   8 // the Free Software Foundation, either version 3 of the License, or
   9 // (at your option) any later version.
  10 //
  11 // This program is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15 //
  16 // See LICENSE.txt for the text of the license.
  17 //-----------------------------------------------------------------------------
  18 #include "spiffs.h"
  19 #include "spiffs_nucleus.h"
  20
  21 #if !SPIFFS_READ_ONLY
  22
  23 // Erases a logical block and updates the erase counter.
  24 // If cache is enabled, all pages that might be cached in this block
  25 // is dropped.
  26 static s32_t spiffs_gc_erase_block(
  27     spiffs *fs,
  28     spiffs_block_ix bix) {
  29     s32_t res;
  30
  31     SPIFFS_GC_DBG("gc: erase block "_SPIPRIbl"\n", bix);
  32     res = spiffs_erase_block(fs, bix);
  33     SPIFFS_CHECK_RES(res);
  34
  35 #if SPIFFS_CACHE
  36     {
  37         u32_t i;
  38         for (i = 0; i < SPIFFS_PAGES_PER_BLOCK(fs); i++) {
  39             spiffs_cache_drop_page(fs, SPIFFS_PAGE_FOR_BLOCK(fs, bix) + i);
  40         }
  41     }
  42 #endif
  43     return res;
  44 }
  45
  46 // Searches for blocks where all entries are deleted - if one is found,
  47 // the block is erased. Compared to the non-quick gc, the quick one ensures
  48 // that no updates are needed on existing objects on pages that are erased.
  49 s32_t spiffs_gc_quick(
  50     spiffs *fs, u16_t max_free_pages) {
  51     s32_t res = SPIFFS_OK;
  52     u32_t blocks = fs->block_count;
  53     spiffs_block_ix cur_block = 0;
  54     u32_t cur_block_addr = 0;
  55     int cur_entry = 0;
  56     spiffs_obj_id *obj_lu_buf = (spiffs_obj_id *)fs->lu_work;
  57
  58     SPIFFS_GC_DBGF("gc_quick: running\n");
  59 #if SPIFFS_GC_STATS
  60     fs->stats_gc_runs++;
  61 #endif
  62
  63     int entries_per_page = (SPIFFS_CFG_LOG_PAGE_SZ(fs) / sizeof(spiffs_obj_id));
  64
  65     // find fully deleted blocks
  66     // check each block
  67     while (res == SPIFFS_OK && blocks--) {
  68         u16_t deleted_pages_in_block = 0;
  69         u16_t free_pages_in_block = 0;
  70
  71         int obj_lookup_page = 0;
  72         // check each object lookup page
  73         while (res == SPIFFS_OK && obj_lookup_page < (int)SPIFFS_OBJ_LOOKUP_PAGES(fs)) {
  74             int entry_offset = obj_lookup_page * entries_per_page;
  75             res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
  76                              0, cur_block_addr + SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page), SPIFFS_CFG_LOG_PAGE_SZ(fs), fs->lu_work);
  77             // check each entry
  78             while (res == SPIFFS_OK &&
  79                     cur_entry - entry_offset < entries_per_page &&
  80                     cur_entry < (int)(SPIFFS_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs))) {
  81                 spiffs_obj_id obj_id = obj_lu_buf[cur_entry - entry_offset];
  82                 if (obj_id == SPIFFS_OBJ_ID_DELETED) {
  83                     deleted_pages_in_block++;
  84                 } else if (obj_id == SPIFFS_OBJ_ID_FREE) {
  85                     // kill scan, go for next block
  86                     free_pages_in_block++;
  87                     if (free_pages_in_block > max_free_pages) {
  88                         obj_lookup_page = SPIFFS_OBJ_LOOKUP_PAGES(fs);
  89                         res = 1; // kill object lu loop
  90                         break;
  91                     }
  92                 }  else {
  93                     // kill scan, go for next block
  94                     obj_lookup_page = SPIFFS_OBJ_LOOKUP_PAGES(fs);
  95                     res = 1; // kill object lu loop
  96                     break;
  97                 }
  98                 cur_entry++;
  99             } // per entry
 100             obj_lookup_page++;
 101         } // per object lookup page
 102         if (res == 1) res = SPIFFS_OK;
 103
 104         if (res == SPIFFS_OK &&
 105                 deleted_pages_in_block + free_pages_in_block == SPIFFS_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs) &&
 106                 free_pages_in_block <= max_free_pages) {
 107             // found a fully deleted block
 108             fs->stats_p_deleted -= deleted_pages_in_block;
 109             res = spiffs_gc_erase_block(fs, cur_block);
 110             return res;
 111         }
 112
 113         cur_entry = 0;
 114         cur_block++;
 115         cur_block_addr += SPIFFS_CFG_LOG_BLOCK_SZ(fs);
 116     } // per block
 117
 118     if (res == SPIFFS_OK) {
 119         res = SPIFFS_ERR_NO_DELETED_BLOCKS;
 120     }
 121     return res;
 122 }
 123
 124 // Checks if garbage collecting is necessary. If so a candidate block is found,
 125 // cleansed and erased
 126 s32_t spiffs_gc_check(
 127     spiffs *fs,
 128     u32_t len) {
 129     s32_t res;
 130     s32_t free_pages =
 131         (SPIFFS_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs)) * (fs->block_count - 2)
 132         - fs->stats_p_allocated - fs->stats_p_deleted;
 133     int tries = 0;
 134
 135     if (fs->free_blocks > 3 &&
 136             (s32_t)len < free_pages * (s32_t)SPIFFS_DATA_PAGE_SIZE(fs)) {
 137         return SPIFFS_OK;
 138     }
 139
 140     u32_t needed_pages = (len + SPIFFS_DATA_PAGE_SIZE(fs) - 1) / SPIFFS_DATA_PAGE_SIZE(fs);
 141 //  if (fs->free_blocks <= 2 && (s32_t)needed_pages > free_pages) {
 142 //    SPIFFS_GC_DBG("gc: full freeblk:"_SPIPRIi" needed:"_SPIPRIi" free:"_SPIPRIi" dele:"_SPIPRIi"\n", fs->free_blocks, needed_pages, free_pages, fs->stats_p_deleted);
 143 //    return SPIFFS_ERR_FULL;
 144 //  }
 145     if ((s32_t)needed_pages > (s32_t)(free_pages + fs->stats_p_deleted)) {
 146         SPIFFS_GC_DBG("gc_check: full freeblk:"_SPIPRIi" needed:"_SPIPRIi" free:"_SPIPRIi" dele:"_SPIPRIi"\n", fs->free_blocks, needed_pages, free_pages, fs->stats_p_deleted);
 147         return SPIFFS_ERR_FULL;
 148     }
 149
 150     do {
 151         SPIFFS_GC_DBG("\ngc_check #"_SPIPRIi": run gc free_blocks:"_SPIPRIi" pfree:"_SPIPRIi" pallo:"_SPIPRIi" pdele:"_SPIPRIi" ["_SPIPRIi"] len:"_SPIPRIi" of "_SPIPRIi"\n",
 152                       tries,
 153                       fs->free_blocks, free_pages, fs->stats_p_allocated, fs->stats_p_deleted, (free_pages + fs->stats_p_allocated + fs->stats_p_deleted),
 154                       len, (u32_t)(free_pages * SPIFFS_DATA_PAGE_SIZE(fs)));
 155
 156         spiffs_block_ix *cands;
 157         int count;
 158         spiffs_block_ix cand;
 159         s32_t prev_free_pages = free_pages;
 160         // if the fs is crammed, ignore block age when selecting candidate - kind of a bad state
 161         res = spiffs_gc_find_candidate(fs, &cands, &count, free_pages <= 0);
 162         SPIFFS_CHECK_RES(res);
 163         if (count == 0) {
 164             SPIFFS_GC_DBGF("gc_check: no candidates, return\n");
 165             return (s32_t)needed_pages < free_pages ? SPIFFS_OK : SPIFFS_ERR_FULL;
 166         }
 167 #if SPIFFS_GC_STATS
 168         fs->stats_gc_runs++;
 169 #endif
 170         cand = cands[0];
 171         fs->cleaning = 1;
 172         //SPIFFS_GC_DBG("gcing: cleaning block "_SPIPRIi"\n", cand);
 173         res = spiffs_gc_clean(fs, cand);
 174         fs->cleaning = 0;
 175         if (res < 0) {
 176             SPIFFS_GC_DBG("gc_check: cleaning block "_SPIPRIi", result "_SPIPRIi"\n", cand, res);
 177         } else {
 178             SPIFFS_GC_DBG("gc_check: cleaning block "_SPIPRIi", result "_SPIPRIi"\n", cand, res);
 179         }
 180         SPIFFS_CHECK_RES(res);
 181
 182         res = spiffs_gc_erase_page_stats(fs, cand);
 183         SPIFFS_CHECK_RES(res);
 184
 185         res = spiffs_gc_erase_block(fs, cand);
 186         SPIFFS_CHECK_RES(res);
 187
 188         free_pages =
 189             (SPIFFS_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs)) * (fs->block_count - 2)
 190             - fs->stats_p_allocated - fs->stats_p_deleted;
 191
 192         if (prev_free_pages <= 0 && prev_free_pages == free_pages) {
 193             // abort early to reduce wear, at least tried once
 194             SPIFFS_GC_DBGF("gc_check: early abort, no result on gc when fs crammed\n");
 195             break;
 196         }
 197
 198     } while (++tries < SPIFFS_GC_MAX_RUNS && (fs->free_blocks <= 2 ||
 199                                               (s32_t)len > free_pages * (s32_t)SPIFFS_DATA_PAGE_SIZE(fs)));
 200
 201     free_pages =
 202         (SPIFFS_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs)) * (fs->block_count - 2)
 203         - fs->stats_p_allocated - fs->stats_p_deleted;
 204     if ((s32_t)len > free_pages * (s32_t)SPIFFS_DATA_PAGE_SIZE(fs)) {
 205         res = SPIFFS_ERR_FULL;
 206     }
 207
 208     SPIFFS_GC_DBG("gc_check: finished, "_SPIPRIi" dirty, blocks "_SPIPRIi" free, "_SPIPRIi" pages free, "_SPIPRIi" tries, res "_SPIPRIi"\n",
 209                   fs->stats_p_allocated + fs->stats_p_deleted,
 210                   fs->free_blocks, free_pages, tries, res);
 211
 212     return res;
 213 }
 214
 215 // Updates page statistics for a block that is about to be erased
 216 s32_t spiffs_gc_erase_page_stats(
 217     spiffs *fs,
 218     spiffs_block_ix bix) {
 219     s32_t res = SPIFFS_OK;
 220     int obj_lookup_page = 0;
 221     int entries_per_page = (SPIFFS_CFG_LOG_PAGE_SZ(fs) / sizeof(spiffs_obj_id));
 222     spiffs_obj_id *obj_lu_buf = (spiffs_obj_id *)fs->lu_work;
 223     int cur_entry = 0;
 224     u32_t dele = 0;
 225     u32_t allo = 0;
 226
 227     // check each object lookup page
 228     while (res == SPIFFS_OK && obj_lookup_page < (int)SPIFFS_OBJ_LOOKUP_PAGES(fs)) {
 229         int entry_offset = obj_lookup_page * entries_per_page;
 230         res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
 231                          0, bix * SPIFFS_CFG_LOG_BLOCK_SZ(fs) + SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page), SPIFFS_CFG_LOG_PAGE_SZ(fs), fs->lu_work);
 232         // check each entry
 233         while (res == SPIFFS_OK &&
 234                 cur_entry - entry_offset < entries_per_page && cur_entry < (int)(SPIFFS_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs))) {
 235             spiffs_obj_id obj_id = obj_lu_buf[cur_entry - entry_offset];
 236             if (obj_id == SPIFFS_OBJ_ID_FREE) {
 237             } else if (obj_id == SPIFFS_OBJ_ID_DELETED) {
 238                 dele++;
 239             } else {
 240                 allo++;
 241             }
 242             cur_entry++;
 243         } // per entry
 244         obj_lookup_page++;
 245     } // per object lookup page
 246     SPIFFS_GC_DBG("gc_check: wipe pallo:"_SPIPRIi" pdele:"_SPIPRIi"\n", allo, dele);
 247     fs->stats_p_allocated -= allo;
 248     fs->stats_p_deleted -= dele;
 249     return res;
 250 }
 251
 252 // Finds block candidates to erase
 253 s32_t spiffs_gc_find_candidate(
 254     spiffs *fs,
 255     spiffs_block_ix **block_candidates,
 256     int *candidate_count,
 257     char fs_crammed) {
 258     s32_t res = SPIFFS_OK;
 259     u32_t blocks = fs->block_count;
 260     spiffs_block_ix cur_block = 0;
 261     u32_t cur_block_addr = 0;
 262     spiffs_obj_id *obj_lu_buf = (spiffs_obj_id *)fs->lu_work;
 263     int cur_entry = 0;
 264
 265     // using fs->work area as sorted candidate memory, (spiffs_block_ix)cand_bix/(s32_t)score
 266     int max_candidates = MIN(fs->block_count, (SPIFFS_CFG_LOG_PAGE_SZ(fs) - 8) / (sizeof(spiffs_block_ix) + sizeof(s32_t)));
 267     *candidate_count = 0;
 268     memset(fs->work, 0xff, SPIFFS_CFG_LOG_PAGE_SZ(fs));
 269
 270     // divide up work area into block indices and scores
 271     spiffs_block_ix *cand_blocks = (spiffs_block_ix *)fs->work;
 272     s32_t *cand_scores = (s32_t *)(fs->work + max_candidates * sizeof(spiffs_block_ix));
 273
 274     // align cand_scores on s32_t boundary
 275     cand_scores = (s32_t *)(((intptr_t)cand_scores + sizeof(intptr_t) - 1) & ~(sizeof(intptr_t) - 1));
 276
 277     *block_candidates = cand_blocks;
 278
 279     int entries_per_page = (SPIFFS_CFG_LOG_PAGE_SZ(fs) / sizeof(spiffs_obj_id));
 280
 281     // check each block
 282     while (res == SPIFFS_OK && blocks--) {
 283         u16_t deleted_pages_in_block = 0;
 284         u16_t used_pages_in_block = 0;
 285
 286         int obj_lookup_page = 0;
 287         // check each object lookup page
 288         while (res == SPIFFS_OK && obj_lookup_page < (int)SPIFFS_OBJ_LOOKUP_PAGES(fs)) {
 289             int entry_offset = obj_lookup_page * entries_per_page;
 290             res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
 291                              0, cur_block_addr + SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page), SPIFFS_CFG_LOG_PAGE_SZ(fs), fs->lu_work);
 292             // check each entry
 293             while (res == SPIFFS_OK &&
 294                     cur_entry - entry_offset < entries_per_page &&
 295                     cur_entry < (int)(SPIFFS_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs))) {
 296                 spiffs_obj_id obj_id = obj_lu_buf[cur_entry - entry_offset];
 297                 if (obj_id == SPIFFS_OBJ_ID_FREE) {
 298                     // when a free entry is encountered, scan logic ensures that all following entries are free also
 299                     res = 1; // kill object lu loop
 300                     break;
 301                 } else  if (obj_id == SPIFFS_OBJ_ID_DELETED) {
 302                     deleted_pages_in_block++;
 303                 } else {
 304                     used_pages_in_block++;
 305                 }
 306                 cur_entry++;
 307             } // per entry
 308             obj_lookup_page++;
 309         } // per object lookup page
 310         if (res == 1) res = SPIFFS_OK;
 311
 312         // calculate score and insert into candidate table
 313         // stoneage sort, but probably not so many blocks
 314         if (res == SPIFFS_OK /*&& deleted_pages_in_block > 0*/) {
 315             // read erase count
 316             spiffs_obj_id erase_count;
 317             res = _spiffs_rd(fs, SPIFFS_OP_C_READ | SPIFFS_OP_T_OBJ_LU2, 0,
 318                              SPIFFS_ERASE_COUNT_PADDR(fs, cur_block),
 319                              sizeof(spiffs_obj_id), (u8_t *)&erase_count);
 320             SPIFFS_CHECK_RES(res);
 321
 322             spiffs_obj_id erase_age;
 323             if (fs->max_erase_count > erase_count) {
 324                 erase_age = fs->max_erase_count - erase_count;
 325             } else {
 326                 erase_age = SPIFFS_OBJ_ID_FREE - (erase_count - fs->max_erase_count);
 327             }
 328
 329             s32_t score =
 330                 deleted_pages_in_block * SPIFFS_GC_HEUR_W_DELET +
 331                 used_pages_in_block * SPIFFS_GC_HEUR_W_USED +
 332                 erase_age * (fs_crammed ? 0 : SPIFFS_GC_HEUR_W_ERASE_AGE);
 333             int cand_ix = 0;
 334             SPIFFS_GC_DBG("gc_check: bix:"_SPIPRIbl" del:"_SPIPRIi" use:"_SPIPRIi" score:"_SPIPRIi"\n", cur_block, deleted_pages_in_block, used_pages_in_block, score);
 335             while (cand_ix < max_candidates) {
 336                 if (cand_blocks[cand_ix] == (spiffs_block_ix) - 1) {
 337                     cand_blocks[cand_ix] = cur_block;
 338                     cand_scores[cand_ix] = score;
 339                     break;
 340                 } else if (cand_scores[cand_ix] < score) {
 341                     int reorder_cand_ix = max_candidates - 2;
 342                     while (reorder_cand_ix >= cand_ix) {
 343                         cand_blocks[reorder_cand_ix + 1] = cand_blocks[reorder_cand_ix];
 344                         cand_scores[reorder_cand_ix + 1] = cand_scores[reorder_cand_ix];
 345                         reorder_cand_ix--;
 346                     }
 347                     cand_blocks[cand_ix] = cur_block;
 348                     cand_scores[cand_ix] = score;
 349                     break;
 350                 }
 351                 cand_ix++;
 352             }
 353             (*candidate_count)++;
 354         }
 355
 356         cur_entry = 0;
 357         cur_block++;
 358         cur_block_addr += SPIFFS_CFG_LOG_BLOCK_SZ(fs);
 359     } // per block
 360
 361     return res;
 362 }
 363
 364 typedef enum {
 365     FIND_OBJ_DATA,
 366     MOVE_OBJ_DATA,
 367     MOVE_OBJ_IX,
 368     FINISHED
 369 } spiffs_gc_clean_state;
 370
 371 typedef struct {
 372     spiffs_gc_clean_state state;
 373     spiffs_obj_id cur_obj_id;
 374     spiffs_span_ix cur_objix_spix;
 375     spiffs_page_ix cur_objix_pix;
 376     spiffs_page_ix cur_data_pix;
 377     int stored_scan_entry_index;
 378     u8_t obj_id_found;
 379 } spiffs_gc;
 380
 381 // Empties given block by moving all data into free pages of another block
 382 // Strategy:
 383 //   loop:
 384 //   scan object lookup for object data pages
 385 //   for first found id, check spix and load corresponding object index page to memory
 386 //   push object scan lookup entry index
 387 //     rescan object lookup, find data pages with same id and referenced by same object index
 388 //     move data page, update object index in memory
 389 //     when reached end of lookup, store updated object index
 390 //   pop object scan lookup entry index
 391 //   repeat loop until end of object lookup
 392 //   scan object lookup again for remaining object index pages, move to new page in other block
 393 //
 394 s32_t spiffs_gc_clean(spiffs *fs, spiffs_block_ix bix) {
 395     s32_t res = SPIFFS_OK;
 396     const int entries_per_page = (SPIFFS_CFG_LOG_PAGE_SZ(fs) / sizeof(spiffs_obj_id));
 397     // this is the global localizer being pushed and popped
 398     int cur_entry = 0;
 399     spiffs_obj_id *obj_lu_buf = (spiffs_obj_id *)fs->lu_work;
 400     spiffs_gc gc; // our stack frame/state
 401     spiffs_page_ix cur_pix = 0;
 402     spiffs_page_object_ix_header *objix_hdr = (spiffs_page_object_ix_header *)fs->work;
 403     spiffs_page_object_ix *objix = (spiffs_page_object_ix *)fs->work;
 404
 405     SPIFFS_GC_DBG("gc_clean: cleaning block "_SPIPRIbl"\n", bix);
 406
 407     memset(&gc, 0, sizeof(spiffs_gc));
 408     gc.state = FIND_OBJ_DATA;
 409
 410     if (fs->free_cursor_block_ix == bix) {
 411         // move free cursor to next block, cannot use free pages from the block we want to clean
 412         fs->free_cursor_block_ix = (bix + 1) % fs->block_count;
 413         fs->free_cursor_obj_lu_entry = 0;
 414         SPIFFS_GC_DBG("gc_clean: move free cursor to block "_SPIPRIbl"\n", fs->free_cursor_block_ix);
 415     }
 416
 417     while (res == SPIFFS_OK && gc.state != FINISHED) {
 418         SPIFFS_GC_DBG("gc_clean: state = "_SPIPRIi" entry:"_SPIPRIi"\n", gc.state, cur_entry);
 419         gc.obj_id_found = 0; // reset (to no found data page)
 420
 421         // scan through lookup pages
 422         int obj_lookup_page = cur_entry / entries_per_page;
 423         u8_t scan = 1;
 424         // check each object lookup page
 425         while (scan && res == SPIFFS_OK && obj_lookup_page < (int)SPIFFS_OBJ_LOOKUP_PAGES(fs)) {
 426             int entry_offset = obj_lookup_page * entries_per_page;
 427             res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
 428                              0, bix * SPIFFS_CFG_LOG_BLOCK_SZ(fs) + SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
 429                              SPIFFS_CFG_LOG_PAGE_SZ(fs), fs->lu_work);
 430             // check each object lookup entry
 431             while (scan && res == SPIFFS_OK &&
 432                     cur_entry - entry_offset < entries_per_page && cur_entry < (int)(SPIFFS_PAGES_PER_BLOCK(fs) - SPIFFS_OBJ_LOOKUP_PAGES(fs))) {
 433                 spiffs_obj_id obj_id = obj_lu_buf[cur_entry - entry_offset];
 434                 cur_pix = SPIFFS_OBJ_LOOKUP_ENTRY_TO_PIX(fs, bix, cur_entry);
 435
 436                 // act upon object id depending on gc state
 437                 switch (gc.state) {
 438                     case FIND_OBJ_DATA:
 439                         // find a data page
 440                         if (obj_id != SPIFFS_OBJ_ID_DELETED && obj_id != SPIFFS_OBJ_ID_FREE &&
 441                                 ((obj_id & SPIFFS_OBJ_ID_IX_FLAG) == 0)) {
 442                             // found a data page, stop scanning and handle in switch case below
 443                             SPIFFS_GC_DBG("gc_clean: FIND_DATA state:"_SPIPRIi" - found obj id "_SPIPRIid"\n", gc.state, obj_id);
 444                             gc.obj_id_found = 1;
 445                             gc.cur_obj_id = obj_id;
 446                             gc.cur_data_pix = cur_pix;
 447                             scan = 0;
 448                         }
 449                         break;
 450                     case MOVE_OBJ_DATA:
 451                         // evacuate found data pages for corresponding object index we have in memory,
 452                         // update memory representation
 453                         if (obj_id == gc.cur_obj_id) {
 454                             spiffs_page_header p_hdr;
 455                             res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU2 | SPIFFS_OP_C_READ,
 456                                              0, SPIFFS_PAGE_TO_PADDR(fs, cur_pix), sizeof(spiffs_page_header), (u8_t *)&p_hdr);
 457                             SPIFFS_CHECK_RES(res);
 458                             SPIFFS_GC_DBG("gc_clean: MOVE_DATA found data page "_SPIPRIid":"_SPIPRIsp" @ "_SPIPRIpg"\n", gc.cur_obj_id, p_hdr.span_ix, cur_pix);
 459                             if (SPIFFS_OBJ_IX_ENTRY_SPAN_IX(fs, p_hdr.span_ix) != gc.cur_objix_spix) {
 460                                 SPIFFS_GC_DBGF("gc_clean: MOVE_DATA no objix spix match, take in another run\n");
 461                             } else {
 462                                 spiffs_page_ix new_data_pix;
 463                                 if (p_hdr.flags & SPIFFS_PH_FLAG_DELET) {
 464                                     // move page
 465                                     res = spiffs_page_move(fs, 0, 0, obj_id, &p_hdr, cur_pix, &new_data_pix);
 466                                     SPIFFS_GC_DBG("gc_clean: MOVE_DATA move objix "_SPIPRIid":"_SPIPRIsp" page "_SPIPRIpg" to "_SPIPRIpg"\n", gc.cur_obj_id, p_hdr.span_ix, cur_pix, new_data_pix);
 467                                     SPIFFS_CHECK_RES(res);
 468                                     // move wipes obj_lu, reload it
 469                                     res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
 470                                                      0, bix * SPIFFS_CFG_LOG_BLOCK_SZ(fs) + SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
 471                                                      SPIFFS_CFG_LOG_PAGE_SZ(fs), fs->lu_work);
 472                                     SPIFFS_CHECK_RES(res);
 473                                 } else {
 474                                     // page is deleted but not deleted in lookup, scrap it -
 475                                     // might seem unnecessary as we will erase this block, but
 476                                     // we might get aborted
 477                                     SPIFFS_GC_DBG("gc_clean: MOVE_DATA wipe objix "_SPIPRIid":"_SPIPRIsp" page "_SPIPRIpg"\n", obj_id, p_hdr.span_ix, cur_pix);
 478                                     res = spiffs_page_delete(fs, cur_pix);
 479                                     SPIFFS_CHECK_RES(res);
 480                                     new_data_pix = SPIFFS_OBJ_ID_FREE;
 481                                 }
 482                                 // update memory representation of object index page with new data page
 483                                 if (gc.cur_objix_spix == 0) {
 484                                     // update object index header page
 485                                     ((spiffs_page_ix *)((u8_t *)objix_hdr + sizeof(spiffs_page_object_ix_header)))[p_hdr.span_ix] = new_data_pix;
 486                                     SPIFFS_GC_DBG("gc_clean: MOVE_DATA wrote page "_SPIPRIpg" to objix_hdr entry "_SPIPRIsp" in mem\n", new_data_pix, (spiffs_span_ix)SPIFFS_OBJ_IX_ENTRY(fs, p_hdr.span_ix));
 487                                 } else {
 488                                     // update object index page
 489                                     ((spiffs_page_ix *)((u8_t *)objix + sizeof(spiffs_page_object_ix)))[SPIFFS_OBJ_IX_ENTRY(fs, p_hdr.span_ix)] = new_data_pix;
 490                                     SPIFFS_GC_DBG("gc_clean: MOVE_DATA wrote page "_SPIPRIpg" to objix entry "_SPIPRIsp" in mem\n", new_data_pix, (spiffs_span_ix)SPIFFS_OBJ_IX_ENTRY(fs, p_hdr.span_ix));
 491                                 }
 492                             }
 493                         }
 494                         break;
 495                     case MOVE_OBJ_IX:
 496                         // find and evacuate object index pages
 497                         if (obj_id != SPIFFS_OBJ_ID_DELETED && obj_id != SPIFFS_OBJ_ID_FREE &&
 498                                 (obj_id & SPIFFS_OBJ_ID_IX_FLAG)) {
 499                             // found an index object id
 500                             spiffs_page_header p_hdr;
 501                             spiffs_page_ix new_pix;
 502                             // load header
 503                             res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU2 | SPIFFS_OP_C_READ,
 504                                              0, SPIFFS_PAGE_TO_PADDR(fs, cur_pix), sizeof(spiffs_page_header), (u8_t *)&p_hdr);
 505                             SPIFFS_CHECK_RES(res);
 506                             if (p_hdr.flags & SPIFFS_PH_FLAG_DELET) {
 507                                 // move page
 508                                 res = spiffs_page_move(fs, 0, 0, obj_id, &p_hdr, cur_pix, &new_pix);
 509                                 SPIFFS_GC_DBG("gc_clean: MOVE_OBJIX move objix "_SPIPRIid":"_SPIPRIsp" page "_SPIPRIpg" to "_SPIPRIpg"\n", obj_id, p_hdr.span_ix, cur_pix, new_pix);
 510                                 SPIFFS_CHECK_RES(res);
 511                                 spiffs_cb_object_event(fs, (spiffs_page_object_ix *)&p_hdr,
 512                                                        SPIFFS_EV_IX_MOV, obj_id, p_hdr.span_ix, new_pix, 0);
 513                                 // move wipes obj_lu, reload it
 514                                 res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU | SPIFFS_OP_C_READ,
 515                                                  0, bix * SPIFFS_CFG_LOG_BLOCK_SZ(fs) + SPIFFS_PAGE_TO_PADDR(fs, obj_lookup_page),
 516                                                  SPIFFS_CFG_LOG_PAGE_SZ(fs), fs->lu_work);
 517                                 SPIFFS_CHECK_RES(res);
 518                             } else {
 519                                 // page is deleted but not deleted in lookup, scrap it -
 520                                 // might seem unnecessary as we will erase this block, but
 521                                 // we might get aborted
 522                                 SPIFFS_GC_DBG("gc_clean: MOVE_OBJIX wipe objix "_SPIPRIid":"_SPIPRIsp" page "_SPIPRIpg"\n", obj_id, p_hdr.span_ix, cur_pix);
 523                                 res = spiffs_page_delete(fs, cur_pix);
 524                                 if (res == SPIFFS_OK) {
 525                                     spiffs_cb_object_event(fs, (spiffs_page_object_ix *)0,
 526                                                            SPIFFS_EV_IX_DEL, obj_id, p_hdr.span_ix, cur_pix, 0);
 527                                 }
 528                             }
 529                             SPIFFS_CHECK_RES(res);
 530                         }
 531                         break;
 532                     default:
 533                         scan = 0;
 534                         break;
 535                 } // switch gc state
 536                 cur_entry++;
 537             } // per entry
 538             obj_lookup_page++; // no need to check scan variable here, obj_lookup_page is set in start of loop
 539         } // per object lookup page
 540         if (res != SPIFFS_OK) break;
 541
 542         // state finalization and switch
 543         switch (gc.state) {
 544             case FIND_OBJ_DATA:
 545                 if (gc.obj_id_found) {
 546                     // handle found data page -
 547                     // find out corresponding obj ix page and load it to memory
 548                     spiffs_page_header p_hdr;
 549                     spiffs_page_ix objix_pix;
 550                     gc.stored_scan_entry_index = cur_entry; // push cursor
 551                     cur_entry = 0; // restart scan from start
 552                     gc.state = MOVE_OBJ_DATA;
 553                     res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU2 | SPIFFS_OP_C_READ,
 554                                      0, SPIFFS_PAGE_TO_PADDR(fs, cur_pix), sizeof(spiffs_page_header), (u8_t *)&p_hdr);
 555                     SPIFFS_CHECK_RES(res);
 556                     gc.cur_objix_spix = SPIFFS_OBJ_IX_ENTRY_SPAN_IX(fs, p_hdr.span_ix);
 557                     SPIFFS_GC_DBG("gc_clean: FIND_DATA find objix span_ix:"_SPIPRIsp"\n", gc.cur_objix_spix);
 558                     res = spiffs_obj_lu_find_id_and_span(fs, gc.cur_obj_id | SPIFFS_OBJ_ID_IX_FLAG, gc.cur_objix_spix, 0, &objix_pix);
 559                     if (res == SPIFFS_ERR_NOT_FOUND) {
 560                         // on borked systems we might get an ERR_NOT_FOUND here -
 561                         // this is handled by simply deleting the page as it is not referenced
 562                         // from anywhere
 563                         SPIFFS_GC_DBG("gc_clean: FIND_OBJ_DATA objix not found! Wipe page "_SPIPRIpg"\n", gc.cur_data_pix);
 564                         res = spiffs_page_delete(fs, gc.cur_data_pix);
 565                         SPIFFS_CHECK_RES(res);
 566                         // then we restore states and continue scanning for data pages
 567                         cur_entry = gc.stored_scan_entry_index; // pop cursor
 568                         gc.state = FIND_OBJ_DATA;
 569                         break; // done
 570                     }
 571                     SPIFFS_CHECK_RES(res);
 572                     SPIFFS_GC_DBG("gc_clean: FIND_DATA found object index at page "_SPIPRIpg"\n", objix_pix);
 573                     res = _spiffs_rd(fs, SPIFFS_OP_T_OBJ_LU2 | SPIFFS_OP_C_READ,
 574                                      0, SPIFFS_PAGE_TO_PADDR(fs, objix_pix), SPIFFS_CFG_LOG_PAGE_SZ(fs), fs->work);
 575                     SPIFFS_CHECK_RES(res);
 576                     // cannot allow a gc if the presumed index in fact is no index, a
 577                     // check must run or lot of data may be lost
 578                     SPIFFS_VALIDATE_OBJIX(objix->p_hdr, gc.cur_obj_id | SPIFFS_OBJ_ID_IX_FLAG, gc.cur_objix_spix);
 579                     gc.cur_objix_pix = objix_pix;
 580                 } else {
 581                     // no more data pages found, passed thru all block, start evacuating object indices
 582                     gc.state = MOVE_OBJ_IX;
 583                     cur_entry = 0; // restart entry scan index
 584                 }
 585                 break;
 586             case MOVE_OBJ_DATA: {
 587                 // store modified objix (hdr) page residing in memory now that all
 588                 // data pages belonging to this object index and residing in the block
 589                 // we want to evacuate
 590                 spiffs_page_ix new_objix_pix;
 591                 gc.state = FIND_OBJ_DATA;
 592                 cur_entry = gc.stored_scan_entry_index; // pop cursor
 593                 if (gc.cur_objix_spix == 0) {
 594                     // store object index header page
 595                     res = spiffs_object_update_index_hdr(fs, 0, gc.cur_obj_id | SPIFFS_OBJ_ID_IX_FLAG, gc.cur_objix_pix, fs->work, 0, 0, 0, &new_objix_pix);
 596                     SPIFFS_GC_DBG("gc_clean: MOVE_DATA store modified objix_hdr page, "_SPIPRIpg":"_SPIPRIsp"\n", new_objix_pix, 0);
 597                     SPIFFS_CHECK_RES(res);
 598                 } else {
 599                     // store object index page
 600                     res = spiffs_page_move(fs, 0, fs->work, gc.cur_obj_id | SPIFFS_OBJ_ID_IX_FLAG, 0, gc.cur_objix_pix, &new_objix_pix);
 601                     SPIFFS_GC_DBG("gc_clean: MOVE_DATA store modified objix page, "_SPIPRIpg":"_SPIPRIsp"\n", new_objix_pix, objix->p_hdr.span_ix);
 602                     SPIFFS_CHECK_RES(res);
 603                     spiffs_cb_object_event(fs, (spiffs_page_object_ix *)fs->work,
 604                                            SPIFFS_EV_IX_UPD, gc.cur_obj_id, objix->p_hdr.span_ix, new_objix_pix, 0);
 605                 }
 606             }
 607             break;
 608             case MOVE_OBJ_IX:
 609                 // scanned thru all block, no more object indices found - our work here is done
 610                 gc.state = FINISHED;
 611                 break;
 612             default:
 613                 cur_entry = 0;
 614                 break;
 615         } // switch gc.state
 616         SPIFFS_GC_DBG("gc_clean: state-> "_SPIPRIi"\n", gc.state);
 617     } // while state != FINISHED
 618
 619
 620     return res;
 621 }
 622
 623 #endif // !SPIFFS_READ_ONLY