lfs.c

00001 /*
00002  * The little filesystem
00003  *
00004  * Copyright (c) 2017, Arm Limited. All rights reserved.
00005  * SPDX-License-Identifier: BSD-3-Clause
00006  */
00007 #include "lfs.h"
00008 #include "lfs_util.h"
00009 
00010 #include <inttypes.h>
00011 
00012 
00013 /// Caching block device operations ///
00014 static int lfs_cache_read(lfs_t *lfs, lfs_cache_t *rcache,
00015         const lfs_cache_t *pcache, lfs_block_t block,
00016         lfs_off_t off, void *buffer, lfs_size_t size) {
00017     uint8_t *data = buffer;
00018     LFS_ASSERT(block < lfs->cfg->block_count);
00019 
00020     while (size > 0) {
00021         if (pcache && block == pcache->block && off >= pcache->off &&
00022                 off < pcache->off + lfs->cfg->prog_size) {
00023             // is already in pcache?
00024             lfs_size_t diff = lfs_min(size,
00025                     lfs->cfg->prog_size - (off-pcache->off));
00026             memcpy(data, &pcache->buffer[off-pcache->off], diff);
00027 
00028             data += diff;
00029             off += diff;
00030             size -= diff;
00031             continue;
00032         }
00033 
00034         if (block == rcache->block && off >= rcache->off &&
00035                 off < rcache->off + lfs->cfg->read_size) {
00036             // is already in rcache?
00037             lfs_size_t diff = lfs_min(size,
00038                     lfs->cfg->read_size - (off-rcache->off));
00039             memcpy(data, &rcache->buffer[off-rcache->off], diff);
00040 
00041             data += diff;
00042             off += diff;
00043             size -= diff;
00044             continue;
00045         }
00046 
00047         if (off % lfs->cfg->read_size == 0 && size >= lfs->cfg->read_size) {
00048             // bypass cache?
00049             lfs_size_t diff = size - (size % lfs->cfg->read_size);
00050             int err = lfs->cfg->read(lfs->cfg, block, off, data, diff);
00051             if (err) {
00052                 return err;
00053             }
00054 
00055             data += diff;
00056             off += diff;
00057             size -= diff;
00058             continue;
00059         }
00060 
00061         // load to cache, first condition can no longer fail
00062         rcache->block = block;
00063         rcache->off = off - (off % lfs->cfg->read_size);
00064         int err = lfs->cfg->read(lfs->cfg, rcache->block,
00065                 rcache->off, rcache->buffer, lfs->cfg->read_size);
00066         if (err) {
00067             return err;
00068         }
00069     }
00070 
00071     return 0;
00072 }
00073 
00074 static int lfs_cache_cmp(lfs_t *lfs, lfs_cache_t *rcache,
00075         const lfs_cache_t *pcache, lfs_block_t block,
00076         lfs_off_t off, const void *buffer, lfs_size_t size) {
00077     const uint8_t *data = buffer;
00078 
00079     for (lfs_off_t i = 0; i < size; i++) {
00080         uint8_t c;
00081         int err = lfs_cache_read(lfs, rcache, pcache,
00082                 block, off+i, &c, 1);
00083         if (err) {
00084             return err;
00085         }
00086 
00087         if (c != data[i]) {
00088             return false;
00089         }
00090     }
00091 
00092     return true;
00093 }
00094 
00095 static int lfs_cache_crc(lfs_t *lfs, lfs_cache_t *rcache,
00096         const lfs_cache_t *pcache, lfs_block_t block,
00097         lfs_off_t off, lfs_size_t size, uint32_t *crc) {
00098     for (lfs_off_t i = 0; i < size; i++) {
00099         uint8_t c;
00100         int err = lfs_cache_read(lfs, rcache, pcache,
00101                 block, off+i, &c, 1);
00102         if (err) {
00103             return err;
00104         }
00105 
00106         lfs_crc(crc, &c, 1);
00107     }
00108 
00109     return 0;
00110 }
00111 
00112 static inline void lfs_cache_drop(lfs_t *lfs, lfs_cache_t *rcache) {
00113     // do not zero, cheaper if cache is readonly or only going to be
00114     // written with identical data (during relocates)
00115     (void)lfs;
00116     rcache->block = 0xffffffff;
00117 }
00118 
00119 static inline void lfs_cache_zero(lfs_t *lfs, lfs_cache_t *pcache) {
00120     // zero to avoid information leak
00121     memset(pcache->buffer, 0xff, lfs->cfg->prog_size);
00122     pcache->block = 0xffffffff;
00123 }
00124 
00125 static int lfs_cache_flush(lfs_t *lfs,
00126         lfs_cache_t *pcache, lfs_cache_t *rcache) {
00127     if (pcache->block != 0xffffffff) {
00128         int err = lfs->cfg->prog(lfs->cfg, pcache->block,
00129                 pcache->off, pcache->buffer, lfs->cfg->prog_size);
00130         if (err) {
00131             return err;
00132         }
00133 
00134         if (rcache) {
00135             int res = lfs_cache_cmp(lfs, rcache, NULL, pcache->block,
00136                     pcache->off, pcache->buffer, lfs->cfg->prog_size);
00137             if (res < 0) {
00138                 return res;
00139             }
00140 
00141             if (!res) {
00142                 return LFS_ERR_CORRUPT;
00143             }
00144         }
00145 
00146         lfs_cache_zero(lfs, pcache);
00147     }
00148 
00149     return 0;
00150 }
00151 
00152 static int lfs_cache_prog(lfs_t *lfs, lfs_cache_t *pcache,
00153         lfs_cache_t *rcache, lfs_block_t block,
00154         lfs_off_t off, const void *buffer, lfs_size_t size) {
00155     const uint8_t *data = buffer;
00156     LFS_ASSERT(block < lfs->cfg->block_count);
00157 
00158     while (size > 0) {
00159         if (block == pcache->block && off >= pcache->off &&
00160                 off < pcache->off + lfs->cfg->prog_size) {
00161             // is already in pcache?
00162             lfs_size_t diff = lfs_min(size,
00163                     lfs->cfg->prog_size - (off-pcache->off));
00164             memcpy(&pcache->buffer[off-pcache->off], data, diff);
00165 
00166             data += diff;
00167             off += diff;
00168             size -= diff;
00169 
00170             if (off % lfs->cfg->prog_size == 0) {
00171                 // eagerly flush out pcache if we fill up
00172                 int err = lfs_cache_flush(lfs, pcache, rcache);
00173                 if (err) {
00174                     return err;
00175                 }
00176             }
00177 
00178             continue;
00179         }
00180 
00181         // pcache must have been flushed, either by programming and
00182         // entire block or manually flushing the pcache
00183         LFS_ASSERT(pcache->block == 0xffffffff);
00184 
00185         if (off % lfs->cfg->prog_size == 0 &&
00186                 size >= lfs->cfg->prog_size) {
00187             // bypass pcache?
00188             lfs_size_t diff = size - (size % lfs->cfg->prog_size);
00189             int err = lfs->cfg->prog(lfs->cfg, block, off, data, diff);
00190             if (err) {
00191                 return err;
00192             }
00193 
00194             if (rcache) {
00195                 int res = lfs_cache_cmp(lfs, rcache, NULL,
00196                         block, off, data, diff);
00197                 if (res < 0) {
00198                     return res;
00199                 }
00200 
00201                 if (!res) {
00202                     return LFS_ERR_CORRUPT;
00203                 }
00204             }
00205 
00206             data += diff;
00207             off += diff;
00208             size -= diff;
00209             continue;
00210         }
00211 
00212         // prepare pcache, first condition can no longer fail
00213         pcache->block = block;
00214         pcache->off = off - (off % lfs->cfg->prog_size);
00215     }
00216 
00217     return 0;
00218 }
00219 
00220 
00221 /// General lfs block device operations ///
00222 static int lfs_bd_read(lfs_t *lfs, lfs_block_t block,
00223         lfs_off_t off, void *buffer, lfs_size_t size) {
00224     // if we ever do more than writes to alternating pairs,
00225     // this may need to consider pcache
00226     return lfs_cache_read(lfs, &lfs->rcache, NULL,
00227             block, off, buffer, size);
00228 }
00229 
00230 static int lfs_bd_prog(lfs_t *lfs, lfs_block_t block,
00231         lfs_off_t off, const void *buffer, lfs_size_t size) {
00232     return lfs_cache_prog(lfs, &lfs->pcache, NULL,
00233             block, off, buffer, size);
00234 }
00235 
00236 static int lfs_bd_cmp(lfs_t *lfs, lfs_block_t block,
00237         lfs_off_t off, const void *buffer, lfs_size_t size) {
00238     return lfs_cache_cmp(lfs, &lfs->rcache, NULL, block, off, buffer, size);
00239 }
00240 
00241 static int lfs_bd_crc(lfs_t *lfs, lfs_block_t block,
00242         lfs_off_t off, lfs_size_t size, uint32_t *crc) {
00243     return lfs_cache_crc(lfs, &lfs->rcache, NULL, block, off, size, crc);
00244 }
00245 
00246 static int lfs_bd_erase(lfs_t *lfs, lfs_block_t block) {
00247     return lfs->cfg->erase(lfs->cfg, block);
00248 }
00249 
00250 static int lfs_bd_sync(lfs_t *lfs) {
00251     lfs_cache_drop(lfs, &lfs->rcache);
00252 
00253     int err = lfs_cache_flush(lfs, &lfs->pcache, NULL);
00254     if (err) {
00255         return err;
00256     }
00257 
00258     return lfs->cfg->sync(lfs->cfg);
00259 }
00260 
00261 
00262 /// Internal operations predeclared here ///
00263 int lfs_traverse(lfs_t *lfs, int (*cb)(void*, lfs_block_t), void *data);
00264 static int lfs_pred(lfs_t *lfs, const lfs_block_t dir[2], lfs_dir_t *pdir);
00265 static int lfs_parent(lfs_t *lfs, const lfs_block_t dir[2],
00266         lfs_dir_t *parent, lfs_entry_t *entry);
00267 static int lfs_moved(lfs_t *lfs, const void *e);
00268 static int lfs_relocate(lfs_t *lfs,
00269         const lfs_block_t oldpair[2], const lfs_block_t newpair[2]);
00270 int lfs_deorphan(lfs_t *lfs);
00271 
00272 
00273 /// Block allocator ///
00274 static int lfs_alloc_lookahead(void *p, lfs_block_t block) {
00275     lfs_t *lfs = p;
00276 
00277     lfs_block_t off = ((block - lfs->free.off)
00278             + lfs->cfg->block_count) % lfs->cfg->block_count;
00279 
00280     if (off < lfs->free.size) {
00281         lfs->free.buffer[off / 32] |= 1U << (off % 32);
00282     }
00283 
00284     return 0;
00285 }
00286 
00287 static int lfs_alloc(lfs_t *lfs, lfs_block_t *block) {
00288     while (true) {
00289         while (lfs->free.i != lfs->free.size) {
00290             lfs_block_t off = lfs->free.i;
00291             lfs->free.i += 1;
00292             lfs->free.ack -= 1;
00293 
00294             if (!(lfs->free.buffer[off / 32] & (1U << (off % 32)))) {
00295                 // found a free block
00296                 *block = (lfs->free.off + off) % lfs->cfg->block_count;
00297 
00298                 // eagerly find next off so an alloc ack can
00299                 // discredit old lookahead blocks
00300                 while (lfs->free.i != lfs->free.size &&
00301                         (lfs->free.buffer[lfs->free.i / 32]
00302                             & (1U << (lfs->free.i % 32)))) {
00303                     lfs->free.i += 1;
00304                     lfs->free.ack -= 1;
00305                 }
00306 
00307                 return 0;
00308             }
00309         }
00310 
00311         // check if we have looked at all blocks since last ack
00312         if (lfs->free.ack == 0) {
00313             LFS_WARN("No more free space %" PRIu32,
00314                     lfs->free.i + lfs->free.off);
00315             return LFS_ERR_NOSPC;
00316         }
00317 
00318         lfs->free.off = (lfs->free.off + lfs->free.size)
00319                 % lfs->cfg->block_count;
00320         lfs->free.size = lfs_min(lfs->cfg->lookahead, lfs->free.ack);
00321         lfs->free.i = 0;
00322 
00323         // find mask of free blocks from tree
00324         memset(lfs->free.buffer, 0, lfs->cfg->lookahead/8);
00325         int err = lfs_traverse(lfs, lfs_alloc_lookahead, lfs);
00326         if (err) {
00327             return err;
00328         }
00329     }
00330 }
00331 
00332 static void lfs_alloc_ack(lfs_t *lfs) {
00333     lfs->free.ack = lfs->cfg->block_count;
00334 }
00335 
00336 
00337 /// Endian swapping functions ///
00338 static void lfs_dir_fromle32(struct lfs_disk_dir *d) {
00339     d->rev     = lfs_fromle32(d->rev);
00340     d->size    = lfs_fromle32(d->size);
00341     d->tail[0] = lfs_fromle32(d->tail[0]);
00342     d->tail[1] = lfs_fromle32(d->tail[1]);
00343 }
00344 
00345 static void lfs_dir_tole32(struct lfs_disk_dir *d) {
00346     d->rev     = lfs_tole32(d->rev);
00347     d->size    = lfs_tole32(d->size);
00348     d->tail[0] = lfs_tole32(d->tail[0]);
00349     d->tail[1] = lfs_tole32(d->tail[1]);
00350 }
00351 
00352 static void lfs_entry_fromle32(struct lfs_disk_entry *d) {
00353     d->u.dir[0] = lfs_fromle32(d->u.dir[0]);
00354     d->u.dir[1] = lfs_fromle32(d->u.dir[1]);
00355 }
00356 
00357 static void lfs_entry_tole32(struct lfs_disk_entry *d) {
00358     d->u.dir[0] = lfs_tole32(d->u.dir[0]);
00359     d->u.dir[1] = lfs_tole32(d->u.dir[1]);
00360 }
00361 
00362 static void lfs_superblock_fromle32(struct lfs_disk_superblock *d) {
00363     d->root[0]     = lfs_fromle32(d->root[0]);
00364     d->root[1]     = lfs_fromle32(d->root[1]);
00365     d->block_size  = lfs_fromle32(d->block_size);
00366     d->block_count = lfs_fromle32(d->block_count);
00367     d->version     = lfs_fromle32(d->version);
00368 }
00369 
00370 static void lfs_superblock_tole32(struct lfs_disk_superblock *d) {
00371     d->root[0]     = lfs_tole32(d->root[0]);
00372     d->root[1]     = lfs_tole32(d->root[1]);
00373     d->block_size  = lfs_tole32(d->block_size);
00374     d->block_count = lfs_tole32(d->block_count);
00375     d->version     = lfs_tole32(d->version);
00376 }
00377 
00378 
00379 /// Metadata pair and directory operations ///
00380 static inline void lfs_pairswap(lfs_block_t pair[2]) {
00381     lfs_block_t t = pair[0];
00382     pair[0] = pair[1];
00383     pair[1] = t;
00384 }
00385 
00386 static inline bool lfs_pairisnull(const lfs_block_t pair[2]) {
00387     return pair[0] == 0xffffffff || pair[1] == 0xffffffff;
00388 }
00389 
00390 static inline int lfs_paircmp(
00391         const lfs_block_t paira[2],
00392         const lfs_block_t pairb[2]) {
00393     return !(paira[0] == pairb[0] || paira[1] == pairb[1] ||
00394              paira[0] == pairb[1] || paira[1] == pairb[0]);
00395 }
00396 
00397 static inline bool lfs_pairsync(
00398         const lfs_block_t paira[2],
00399         const lfs_block_t pairb[2]) {
00400     return (paira[0] == pairb[0] && paira[1] == pairb[1]) ||
00401            (paira[0] == pairb[1] && paira[1] == pairb[0]);
00402 }
00403 
00404 static inline lfs_size_t lfs_entry_size(const lfs_entry_t *entry) {
00405     return 4 + entry->d.elen + entry->d.alen + entry->d.nlen;
00406 }
00407 
00408 static int lfs_dir_alloc(lfs_t *lfs, lfs_dir_t *dir) {
00409     // allocate pair of dir blocks
00410     for (int i = 0; i < 2; i++) {
00411         int err = lfs_alloc(lfs, &dir->pair[i]);
00412         if (err) {
00413             return err;
00414         }
00415     }
00416 
00417     // rather than clobbering one of the blocks we just pretend
00418     // the revision may be valid
00419     int err = lfs_bd_read(lfs, dir->pair[0], 0, &dir->d.rev, 4);
00420     if (err && err != LFS_ERR_CORRUPT) {
00421         return err;
00422     }
00423 
00424     if (err != LFS_ERR_CORRUPT) {
00425         dir->d.rev = lfs_fromle32(dir->d.rev);
00426     }
00427 
00428     // set defaults
00429     dir->d.rev += 1;
00430     dir->d.size = sizeof(dir->d)+4;
00431     dir->d.tail[0] = 0xffffffff;
00432     dir->d.tail[1] = 0xffffffff;
00433     dir->off = sizeof(dir->d);
00434 
00435     // don't write out yet, let caller take care of that
00436     return 0;
00437 }
00438 
00439 static int lfs_dir_fetch(lfs_t *lfs,
00440         lfs_dir_t *dir, const lfs_block_t pair[2]) {
00441     // copy out pair, otherwise may be aliasing dir
00442     const lfs_block_t tpair[2] = {pair[0], pair[1]};
00443     bool valid = false;
00444 
00445     // check both blocks for the most recent revision
00446     for (int i = 0; i < 2; i++) {
00447         struct lfs_disk_dir test;
00448         int err = lfs_bd_read(lfs, tpair[i], 0, &test, sizeof(test));
00449         lfs_dir_fromle32(&test);
00450         if (err) {
00451             if (err == LFS_ERR_CORRUPT) {
00452                 continue;
00453             }
00454             return err;
00455         }
00456 
00457         if (valid && lfs_scmp(test.rev, dir->d.rev) < 0) {
00458             continue;
00459         }
00460 
00461         if ((0x7fffffff & test.size) < sizeof(test)+4 ||
00462             (0x7fffffff & test.size) > lfs->cfg->block_size) {
00463             continue;
00464         }
00465 
00466         uint32_t crc = 0xffffffff;
00467         lfs_dir_tole32(&test);
00468         lfs_crc(&crc, &test, sizeof(test));
00469         lfs_dir_fromle32(&test);
00470         err = lfs_bd_crc(lfs, tpair[i], sizeof(test),
00471                 (0x7fffffff & test.size) - sizeof(test), &crc);
00472         if (err) {
00473             if (err == LFS_ERR_CORRUPT) {
00474                 continue;
00475             }
00476             return err;
00477         }
00478 
00479         if (crc != 0) {
00480             continue;
00481         }
00482 
00483         valid = true;
00484 
00485         // setup dir in case it's valid
00486         dir->pair[0] = tpair[(i+0) % 2];
00487         dir->pair[1] = tpair[(i+1) % 2];
00488         dir->off = sizeof(dir->d);
00489         dir->d = test;
00490     }
00491 
00492     if (!valid) {
00493         LFS_ERROR("Corrupted dir pair at %" PRIu32 " %" PRIu32 ,
00494                 tpair[0], tpair[1]);
00495         return LFS_ERR_CORRUPT;
00496     }
00497 
00498     return 0;
00499 }
00500 
00501 struct lfs_region {
00502     lfs_off_t oldoff;
00503     lfs_size_t oldlen;
00504     const void *newdata;
00505     lfs_size_t newlen;
00506 };
00507 
00508 static int lfs_dir_commit(lfs_t *lfs, lfs_dir_t *dir,
00509         const struct lfs_region *regions, int count) {
00510     // increment revision count
00511     dir->d.rev += 1;
00512 
00513     // keep pairs in order such that pair[0] is most recent
00514     lfs_pairswap(dir->pair);
00515     for (int i = 0; i < count; i++) {
00516         dir->d.size += regions[i].newlen - regions[i].oldlen;
00517     }
00518 
00519     const lfs_block_t oldpair[2] = {dir->pair[0], dir->pair[1]};
00520     bool relocated = false;
00521 
00522     while (true) {
00523         if (true) {
00524             int err = lfs_bd_erase(lfs, dir->pair[0]);
00525             if (err) {
00526                 if (err == LFS_ERR_CORRUPT) {
00527                     goto relocate;
00528                 }
00529                 return err;
00530             }
00531 
00532             uint32_t crc = 0xffffffff;
00533             lfs_dir_tole32(&dir->d);
00534             lfs_crc(&crc, &dir->d, sizeof(dir->d));
00535             err = lfs_bd_prog(lfs, dir->pair[0], 0, &dir->d, sizeof(dir->d));
00536             lfs_dir_fromle32(&dir->d);
00537             if (err) {
00538                 if (err == LFS_ERR_CORRUPT) {
00539                     goto relocate;
00540                 }
00541                 return err;
00542             }
00543 
00544             int i = 0;
00545             lfs_off_t oldoff = sizeof(dir->d);
00546             lfs_off_t newoff = sizeof(dir->d);
00547             while (newoff < (0x7fffffff & dir->d.size)-4) {
00548                 if (i < count && regions[i].oldoff == oldoff) {
00549                     lfs_crc(&crc, regions[i].newdata, regions[i].newlen);
00550                     err = lfs_bd_prog(lfs, dir->pair[0],
00551                             newoff, regions[i].newdata, regions[i].newlen);
00552                     if (err) {
00553                         if (err == LFS_ERR_CORRUPT) {
00554                             goto relocate;
00555                         }
00556                         return err;
00557                     }
00558 
00559                     oldoff += regions[i].oldlen;
00560                     newoff += regions[i].newlen;
00561                     i += 1;
00562                 } else {
00563                     uint8_t data;
00564                     err = lfs_bd_read(lfs, oldpair[1], oldoff, &data, 1);
00565                     if (err) {
00566                         return err;
00567                     }
00568 
00569                     lfs_crc(&crc, &data, 1);
00570                     err = lfs_bd_prog(lfs, dir->pair[0], newoff, &data, 1);
00571                     if (err) {
00572                         if (err == LFS_ERR_CORRUPT) {
00573                             goto relocate;
00574                         }
00575                         return err;
00576                     }
00577 
00578                     oldoff += 1;
00579                     newoff += 1;
00580                 }
00581             }
00582 
00583             crc = lfs_tole32(crc);
00584             err = lfs_bd_prog(lfs, dir->pair[0], newoff, &crc, 4);
00585             crc = lfs_fromle32(crc);
00586             if (err) {
00587                 if (err == LFS_ERR_CORRUPT) {
00588                     goto relocate;
00589                 }
00590                 return err;
00591             }
00592 
00593             err = lfs_bd_sync(lfs);
00594             if (err) {
00595                 if (err == LFS_ERR_CORRUPT) {
00596                     goto relocate;
00597                 }
00598                 return err;
00599             }
00600 
00601             // successful commit, check checksum to make sure
00602             uint32_t ncrc = 0xffffffff;
00603             err = lfs_bd_crc(lfs, dir->pair[0], 0,
00604                     (0x7fffffff & dir->d.size)-4, &ncrc);
00605             if (err) {
00606                 return err;
00607             }
00608 
00609             if (ncrc != crc) {
00610                 goto relocate;
00611             }
00612         }
00613 
00614         break;
00615 relocate:
00616         //commit was corrupted
00617         LFS_DEBUG("Bad block at %" PRIu32, dir->pair[0]);
00618 
00619         // drop caches and prepare to relocate block
00620         relocated = true;
00621         lfs_cache_drop(lfs, &lfs->pcache);
00622 
00623         // can't relocate superblock, filesystem is now frozen
00624         if (lfs_paircmp(oldpair, (const lfs_block_t[2]){0, 1}) == 0) {
00625             LFS_WARN("Superblock %" PRIu32 " has become unwritable",
00626                     oldpair[0]);
00627             return LFS_ERR_CORRUPT;
00628         }
00629 
00630         // relocate half of pair
00631         int err = lfs_alloc(lfs, &dir->pair[0]);
00632         if (err) {
00633             return err;
00634         }
00635     }
00636 
00637     if (relocated) {
00638         // update references if we relocated
00639         LFS_DEBUG("Relocating %" PRIu32 " %" PRIu32 " to %" PRIu32 " %" PRIu32,
00640                 oldpair[0], oldpair[1], dir->pair[0], dir->pair[1]);
00641         int err = lfs_relocate(lfs, oldpair, dir->pair);
00642         if (err) {
00643             return err;
00644         }
00645     }
00646 
00647     // shift over any directories that are affected
00648     for (lfs_dir_t *d = lfs->dirs; d; d = d->next) {
00649         if (lfs_paircmp(d->pair, dir->pair) == 0) {
00650             d->pair[0] = dir->pair[0];
00651             d->pair[1] = dir->pair[1];
00652         }
00653     }
00654 
00655     return 0;
00656 }
00657 
00658 static int lfs_dir_update(lfs_t *lfs, lfs_dir_t *dir,
00659         lfs_entry_t *entry, const void *data) {
00660     lfs_entry_tole32(&entry->d);
00661     int err = lfs_dir_commit(lfs, dir, (struct lfs_region[]){
00662             {entry->off, sizeof(entry->d), &entry->d, sizeof(entry->d)},
00663             {entry->off+sizeof(entry->d), entry->d.nlen, data, entry->d.nlen}
00664         }, data ? 2 : 1);
00665     lfs_entry_fromle32(&entry->d);
00666     return err;
00667 }
00668 
00669 static int lfs_dir_append(lfs_t *lfs, lfs_dir_t *dir,
00670         lfs_entry_t *entry, const void *data) {
00671     // check if we fit, if top bit is set we do not and move on
00672     while (true) {
00673         if (dir->d.size + lfs_entry_size(entry) <= lfs->cfg->block_size) {
00674             entry->off = dir->d.size - 4;
00675 
00676             lfs_entry_tole32(&entry->d);
00677             int err = lfs_dir_commit(lfs, dir, (struct lfs_region[]){
00678                     {entry->off, 0, &entry->d, sizeof(entry->d)},
00679                     {entry->off, 0, data, entry->d.nlen}
00680                 }, 2);
00681             lfs_entry_fromle32(&entry->d);
00682             return err;
00683         }
00684 
00685         // we need to allocate a new dir block
00686         if (!(0x80000000 & dir->d.size)) {
00687             lfs_dir_t olddir = *dir;
00688             int err = lfs_dir_alloc(lfs, dir);
00689             if (err) {
00690                 return err;
00691             }
00692 
00693             dir->d.tail[0] = olddir.d.tail[0];
00694             dir->d.tail[1] = olddir.d.tail[1];
00695             entry->off = dir->d.size - 4;
00696             lfs_entry_tole32(&entry->d);
00697             err = lfs_dir_commit(lfs, dir, (struct lfs_region[]){
00698                     {entry->off, 0, &entry->d, sizeof(entry->d)},
00699                     {entry->off, 0, data, entry->d.nlen}
00700                 }, 2);
00701             lfs_entry_fromle32(&entry->d);
00702             if (err) {
00703                 return err;
00704             }
00705 
00706             olddir.d.size |= 0x80000000;
00707             olddir.d.tail[0] = dir->pair[0];
00708             olddir.d.tail[1] = dir->pair[1];
00709             return lfs_dir_commit(lfs, &olddir, NULL, 0);
00710         }
00711 
00712         int err = lfs_dir_fetch(lfs, dir, dir->d.tail);
00713         if (err) {
00714             return err;
00715         }
00716     }
00717 }
00718 
00719 static int lfs_dir_remove(lfs_t *lfs, lfs_dir_t *dir, lfs_entry_t *entry) {
00720     // check if we should just drop the directory block
00721     if ((dir->d.size & 0x7fffffff) == sizeof(dir->d)+4
00722             + lfs_entry_size(entry)) {
00723         lfs_dir_t pdir;
00724         int res = lfs_pred(lfs, dir->pair, &pdir);
00725         if (res < 0) {
00726             return res;
00727         }
00728 
00729         if (pdir.d.size & 0x80000000) {
00730             pdir.d.size &= dir->d.size | 0x7fffffff;
00731             pdir.d.tail[0] = dir->d.tail[0];
00732             pdir.d.tail[1] = dir->d.tail[1];
00733             return lfs_dir_commit(lfs, &pdir, NULL, 0);
00734         }
00735     }
00736 
00737     // shift out the entry
00738     int err = lfs_dir_commit(lfs, dir, (struct lfs_region[]){
00739             {entry->off, lfs_entry_size(entry), NULL, 0},
00740         }, 1);
00741     if (err) {
00742         return err;
00743     }
00744 
00745     // shift over any files/directories that are affected
00746     for (lfs_file_t *f = lfs->files; f; f = f->next) {
00747         if (lfs_paircmp(f->pair, dir->pair) == 0) {
00748             if (f->poff == entry->off) {
00749                 f->pair[0] = 0xffffffff;
00750                 f->pair[1] = 0xffffffff;
00751             } else if (f->poff > entry->off) {
00752                 f->poff -= lfs_entry_size(entry);
00753             }
00754         }
00755     }
00756 
00757     for (lfs_dir_t *d = lfs->dirs; d; d = d->next) {
00758         if (lfs_paircmp(d->pair, dir->pair) == 0) {
00759             if (d->off > entry->off) {
00760                 d->off -= lfs_entry_size(entry);
00761                 d->pos -= lfs_entry_size(entry);
00762             }
00763         }
00764     }
00765 
00766     return 0;
00767 }
00768 
00769 static int lfs_dir_next(lfs_t *lfs, lfs_dir_t *dir, lfs_entry_t *entry) {
00770     while (dir->off + sizeof(entry->d) > (0x7fffffff & dir->d.size)-4) {
00771         if (!(0x80000000 & dir->d.size)) {
00772             entry->off = dir->off;
00773             return LFS_ERR_NOENT;
00774         }
00775 
00776         int err = lfs_dir_fetch(lfs, dir, dir->d.tail);
00777         if (err) {
00778             return err;
00779         }
00780 
00781         dir->off = sizeof(dir->d);
00782         dir->pos += sizeof(dir->d) + 4;
00783     }
00784 
00785     int err = lfs_bd_read(lfs, dir->pair[0], dir->off,
00786             &entry->d, sizeof(entry->d));
00787     lfs_entry_fromle32(&entry->d);
00788     if (err) {
00789         return err;
00790     }
00791 
00792     entry->off = dir->off;
00793     dir->off += lfs_entry_size(entry);
00794     dir->pos += lfs_entry_size(entry);
00795     return 0;
00796 }
00797 
00798 static int lfs_dir_find(lfs_t *lfs, lfs_dir_t *dir,
00799         lfs_entry_t *entry, const char **path) {
00800     const char *pathname = *path;
00801     size_t pathlen;
00802     entry->d.type = LFS_TYPE_DIR;
00803     entry->d.elen = sizeof(entry->d) - 4;
00804     entry->d.alen = 0;
00805     entry->d.nlen = 0;
00806     entry->d.u.dir[0] = lfs->root[0];
00807     entry->d.u.dir[1] = lfs->root[1];
00808 
00809     while (true) {
00810 nextname:
00811         // skip slashes
00812         pathname += strspn(pathname, "/");
00813         pathlen = strcspn(pathname, "/");
00814 
00815         // skip '.' and root '..'
00816         if ((pathlen == 1 && memcmp(pathname, ".", 1) == 0) ||
00817             (pathlen == 2 && memcmp(pathname, "..", 2) == 0)) {
00818             pathname += pathlen;
00819             goto nextname;
00820         }
00821 
00822         // skip if matched by '..' in name
00823         const char *suffix = pathname + pathlen;
00824         size_t sufflen;
00825         int depth = 1;
00826         while (true) {
00827             suffix += strspn(suffix, "/");
00828             sufflen = strcspn(suffix, "/");
00829             if (sufflen == 0) {
00830                 break;
00831             }
00832 
00833             if (sufflen == 2 && memcmp(suffix, "..", 2) == 0) {
00834                 depth -= 1;
00835                 if (depth == 0) {
00836                     pathname = suffix + sufflen;
00837                     goto nextname;
00838                 }
00839             } else {
00840                 depth += 1;
00841             }
00842 
00843             suffix += sufflen;
00844         }
00845 
00846         // found path
00847         if (pathname[0] == '\0') {
00848             return 0;
00849         }
00850 
00851         // update what we've found
00852         *path = pathname;
00853 
00854         // continue on if we hit a directory
00855         if (entry->d.type != LFS_TYPE_DIR) {
00856             return LFS_ERR_NOTDIR;
00857         }
00858 
00859         int err = lfs_dir_fetch(lfs, dir, entry->d.u.dir);
00860         if (err) {
00861             return err;
00862         }
00863 
00864         // find entry matching name
00865         while (true) {
00866             err = lfs_dir_next(lfs, dir, entry);
00867             if (err) {
00868                 return err;
00869             }
00870 
00871             if (((0x7f & entry->d.type) != LFS_TYPE_REG &&
00872                  (0x7f & entry->d.type) != LFS_TYPE_DIR) ||
00873                 entry->d.nlen != pathlen) {
00874                 continue;
00875             }
00876 
00877             int res = lfs_bd_cmp(lfs, dir->pair[0],
00878                     entry->off + 4+entry->d.elen+entry->d.alen,
00879                     pathname, pathlen);
00880             if (res < 0) {
00881                 return res;
00882             }
00883 
00884             // found match
00885             if (res) {
00886                 break;
00887             }
00888         }
00889 
00890         // check that entry has not been moved
00891         if (entry->d.type & 0x80) {
00892             int moved = lfs_moved(lfs, &entry->d.u);
00893             if (moved < 0 || moved) {
00894                 return (moved < 0) ? moved : LFS_ERR_NOENT;
00895             }
00896 
00897             entry->d.type &= ~0x80;
00898         }
00899 
00900         // to next name
00901         pathname += pathlen;
00902     }
00903 }
00904 
00905 
00906 /// Top level directory operations ///
00907 int lfs_mkdir(lfs_t *lfs, const char *path) {
00908     // deorphan if we haven't yet, needed at most once after poweron
00909     if (!lfs->deorphaned) {
00910         int err = lfs_deorphan(lfs);
00911         if (err) {
00912             return err;
00913         }
00914     }
00915 
00916     // fetch parent directory
00917     lfs_dir_t cwd;
00918     lfs_entry_t entry;
00919     int err = lfs_dir_find(lfs, &cwd, &entry, &path);
00920     if (err != LFS_ERR_NOENT || strchr(path, '/') != NULL) {
00921         return err ? err : LFS_ERR_EXIST;
00922     }
00923 
00924     // build up new directory
00925     lfs_alloc_ack(lfs);
00926 
00927     lfs_dir_t dir;
00928     err = lfs_dir_alloc(lfs, &dir);
00929     if (err) {
00930         return err;
00931     }
00932     dir.d.tail[0] = cwd.d.tail[0];
00933     dir.d.tail[1] = cwd.d.tail[1];
00934 
00935     err = lfs_dir_commit(lfs, &dir, NULL, 0);
00936     if (err) {
00937         return err;
00938     }
00939 
00940     entry.d.type = LFS_TYPE_DIR;
00941     entry.d.elen = sizeof(entry.d) - 4;
00942     entry.d.alen = 0;
00943     entry.d.nlen = strlen(path);
00944     entry.d.u.dir[0] = dir.pair[0];
00945     entry.d.u.dir[1] = dir.pair[1];
00946 
00947     cwd.d.tail[0] = dir.pair[0];
00948     cwd.d.tail[1] = dir.pair[1];
00949 
00950     err = lfs_dir_append(lfs, &cwd, &entry, path);
00951     if (err) {
00952         return err;
00953     }
00954 
00955     lfs_alloc_ack(lfs);
00956     return 0;
00957 }
00958 
00959 int lfs_dir_open(lfs_t *lfs, lfs_dir_t *dir, const char *path) {
00960     dir->pair[0] = lfs->root[0];
00961     dir->pair[1] = lfs->root[1];
00962 
00963     lfs_entry_t entry;
00964     int err = lfs_dir_find(lfs, dir, &entry, &path);
00965     if (err) {
00966         return err;
00967     } else if (entry.d.type != LFS_TYPE_DIR) {
00968         return LFS_ERR_NOTDIR;
00969     }
00970 
00971     err = lfs_dir_fetch(lfs, dir, entry.d.u.dir);
00972     if (err) {
00973         return err;
00974     }
00975 
00976     // setup head dir
00977     // special offset for '.' and '..'
00978     dir->head[0] = dir->pair[0];
00979     dir->head[1] = dir->pair[1];
00980     dir->pos = sizeof(dir->d) - 2;
00981     dir->off = sizeof(dir->d);
00982 
00983     // add to list of directories
00984     dir->next = lfs->dirs;
00985     lfs->dirs = dir;
00986 
00987     return 0;
00988 }
00989 
00990 int lfs_dir_close(lfs_t *lfs, lfs_dir_t *dir) {
00991     // remove from list of directories
00992     for (lfs_dir_t **p = &lfs->dirs; *p; p = &(*p)->next) {
00993         if (*p == dir) {
00994             *p = dir->next;
00995             break;
00996         }
00997     }
00998 
00999     return 0;
01000 }
01001 
01002 int lfs_dir_read(lfs_t *lfs, lfs_dir_t *dir, struct lfs_info *info) {
01003     memset(info, 0, sizeof(*info));
01004 
01005     // special offset for '.' and '..'
01006     if (dir->pos == sizeof(dir->d) - 2) {
01007         info->type = LFS_TYPE_DIR;
01008         strcpy(info->name, ".");
01009         dir->pos += 1;
01010         return 1;
01011     } else if (dir->pos == sizeof(dir->d) - 1) {
01012         info->type = LFS_TYPE_DIR;
01013         strcpy(info->name, "..");
01014         dir->pos += 1;
01015         return 1;
01016     }
01017 
01018     lfs_entry_t entry;
01019     while (true) {
01020         int err = lfs_dir_next(lfs, dir, &entry);
01021         if (err) {
01022             return (err == LFS_ERR_NOENT) ? 0 : err;
01023         }
01024 
01025         if ((0x7f & entry.d.type) != LFS_TYPE_REG &&
01026             (0x7f & entry.d.type) != LFS_TYPE_DIR) {
01027             continue;
01028         }
01029 
01030         // check that entry has not been moved
01031         if (entry.d.type & 0x80) {
01032             int moved = lfs_moved(lfs, &entry.d.u);
01033             if (moved < 0) {
01034                 return moved;
01035             }
01036 
01037             if (moved) {
01038                 continue;
01039             }
01040 
01041             entry.d.type &= ~0x80;
01042         }
01043 
01044         break;
01045     }
01046 
01047     info->type = entry.d.type;
01048     if (info->type == LFS_TYPE_REG) {
01049         info->size = entry.d.u.file.size;
01050     }
01051 
01052     int err = lfs_bd_read(lfs, dir->pair[0],
01053             entry.off + 4+entry.d.elen+entry.d.alen,
01054             info->name, entry.d.nlen);
01055     if (err) {
01056         return err;
01057     }
01058 
01059     return 1;
01060 }
01061 
01062 int lfs_dir_seek(lfs_t *lfs, lfs_dir_t *dir, lfs_off_t off) {
01063     // simply walk from head dir
01064     int err = lfs_dir_rewind(lfs, dir);
01065     if (err) {
01066         return err;
01067     }
01068     dir->pos = off;
01069 
01070     while (off > (0x7fffffff & dir->d.size)) {
01071         off -= 0x7fffffff & dir->d.size;
01072         if (!(0x80000000 & dir->d.size)) {
01073             return LFS_ERR_INVAL;
01074         }
01075 
01076         err = lfs_dir_fetch(lfs, dir, dir->d.tail);
01077         if (err) {
01078             return err;
01079         }
01080     }
01081 
01082     dir->off = off;
01083     return 0;
01084 }
01085 
01086 lfs_soff_t lfs_dir_tell(lfs_t *lfs, lfs_dir_t *dir) {
01087     (void)lfs;
01088     return dir->pos;
01089 }
01090 
01091 int lfs_dir_rewind(lfs_t *lfs, lfs_dir_t *dir) {
01092     // reload the head dir
01093     int err = lfs_dir_fetch(lfs, dir, dir->head);
01094     if (err) {
01095         return err;
01096     }
01097 
01098     dir->pair[0] = dir->head[0];
01099     dir->pair[1] = dir->head[1];
01100     dir->pos = sizeof(dir->d) - 2;
01101     dir->off = sizeof(dir->d);
01102     return 0;
01103 }
01104 
01105 
01106 /// File index list operations ///
01107 static int lfs_ctz_index(lfs_t *lfs, lfs_off_t *off) {
01108     lfs_off_t size = *off;
01109     lfs_off_t b = lfs->cfg->block_size - 2*4;
01110     lfs_off_t i = size / b;
01111     if (i == 0) {
01112         return 0;
01113     }
01114 
01115     i = (size - 4*(lfs_popc(i-1)+2)) / b;
01116     *off = size - b*i - 4*lfs_popc(i);
01117     return i;
01118 }
01119 
01120 static int lfs_ctz_find(lfs_t *lfs,
01121         lfs_cache_t *rcache, const lfs_cache_t *pcache,
01122         lfs_block_t head, lfs_size_t size,
01123         lfs_size_t pos, lfs_block_t *block, lfs_off_t *off) {
01124     if (size == 0) {
01125         *block = 0xffffffff;
01126         *off = 0;
01127         return 0;
01128     }
01129 
01130     lfs_off_t current = lfs_ctz_index(lfs, &(lfs_off_t){size-1});
01131     lfs_off_t target = lfs_ctz_index(lfs, &pos);
01132 
01133     while (current > target) {
01134         lfs_size_t skip = lfs_min(
01135                 lfs_npw2(current-target+1) - 1,
01136                 lfs_ctz(current));
01137 
01138         int err = lfs_cache_read(lfs, rcache, pcache, head, 4*skip, &head, 4);
01139         head = lfs_fromle32(head);
01140         if (err) {
01141             return err;
01142         }
01143 
01144         LFS_ASSERT(head >= 2 && head <= lfs->cfg->block_count);
01145         current -= 1 << skip;
01146     }
01147 
01148     *block = head;
01149     *off = pos;
01150     return 0;
01151 }
01152 
01153 static int lfs_ctz_extend(lfs_t *lfs,
01154         lfs_cache_t *rcache, lfs_cache_t *pcache,
01155         lfs_block_t head, lfs_size_t size,
01156         lfs_block_t *block, lfs_off_t *off) {
01157     while (true) {
01158         // go ahead and grab a block
01159         lfs_block_t nblock;
01160         int err = lfs_alloc(lfs, &nblock);
01161         if (err) {
01162             return err;
01163         }
01164         LFS_ASSERT(nblock >= 2 && nblock <= lfs->cfg->block_count);
01165 
01166         if (true) {
01167             err = lfs_bd_erase(lfs, nblock);
01168             if (err) {
01169                 if (err == LFS_ERR_CORRUPT) {
01170                     goto relocate;
01171                 }
01172                 return err;
01173             }
01174 
01175             if (size == 0) {
01176                 *block = nblock;
01177                 *off = 0;
01178                 return 0;
01179             }
01180 
01181             size -= 1;
01182             lfs_off_t index = lfs_ctz_index(lfs, &size);
01183             size += 1;
01184 
01185             // just copy out the last block if it is incomplete
01186             if (size != lfs->cfg->block_size) {
01187                 for (lfs_off_t i = 0; i < size; i++) {
01188                     uint8_t data;
01189                     err = lfs_cache_read(lfs, rcache, NULL,
01190                             head, i, &data, 1);
01191                     if (err) {
01192                         return err;
01193                     }
01194 
01195                     err = lfs_cache_prog(lfs, pcache, rcache,
01196                             nblock, i, &data, 1);
01197                     if (err) {
01198                         if (err == LFS_ERR_CORRUPT) {
01199                             goto relocate;
01200                         }
01201                         return err;
01202                     }
01203                 }
01204 
01205                 *block = nblock;
01206                 *off = size;
01207                 return 0;
01208             }
01209 
01210             // append block
01211             index += 1;
01212             lfs_size_t skips = lfs_ctz(index) + 1;
01213 
01214             for (lfs_off_t i = 0; i < skips; i++) {
01215                 head = lfs_tole32(head);
01216                 err = lfs_cache_prog(lfs, pcache, rcache,
01217                         nblock, 4*i, &head, 4);
01218                 head = lfs_fromle32(head);
01219                 if (err) {
01220                     if (err == LFS_ERR_CORRUPT) {
01221                         goto relocate;
01222                     }
01223                     return err;
01224                 }
01225 
01226                 if (i != skips-1) {
01227                     err = lfs_cache_read(lfs, rcache, NULL,
01228                             head, 4*i, &head, 4);
01229                     head = lfs_fromle32(head);
01230                     if (err) {
01231                         return err;
01232                     }
01233                 }
01234 
01235                 LFS_ASSERT(head >= 2 && head <= lfs->cfg->block_count);
01236             }
01237 
01238             *block = nblock;
01239             *off = 4*skips;
01240             return 0;
01241         }
01242 
01243 relocate:
01244         LFS_DEBUG("Bad block at %" PRIu32, nblock);
01245 
01246         // just clear cache and try a new block
01247         lfs_cache_drop(lfs, &lfs->pcache);
01248     }
01249 }
01250 
01251 static int lfs_ctz_traverse(lfs_t *lfs,
01252         lfs_cache_t *rcache, const lfs_cache_t *pcache,
01253         lfs_block_t head, lfs_size_t size,
01254         int (*cb)(void*, lfs_block_t), void *data) {
01255     if (size == 0) {
01256         return 0;
01257     }
01258 
01259     lfs_off_t index = lfs_ctz_index(lfs, &(lfs_off_t){size-1});
01260 
01261     while (true) {
01262         int err = cb(data, head);
01263         if (err) {
01264             return err;
01265         }
01266 
01267         if (index == 0) {
01268             return 0;
01269         }
01270 
01271         lfs_block_t heads[2];
01272         int count = 2 - (index & 1);
01273         err = lfs_cache_read(lfs, rcache, pcache, head, 0, &heads, count*4);
01274         heads[0] = lfs_fromle32(heads[0]);
01275         heads[1] = lfs_fromle32(heads[1]);
01276         if (err) {
01277             return err;
01278         }
01279 
01280         for (int i = 0; i < count-1; i++) {
01281             err = cb(data, heads[i]);
01282             if (err) {
01283                 return err;
01284             }
01285         }
01286 
01287         head = heads[count-1];
01288         index -= count;
01289     }
01290 }
01291 
01292 
01293 /// Top level file operations ///
01294 int lfs_file_opencfg(lfs_t *lfs, lfs_file_t *file,
01295         const char *path, int flags,
01296         const struct lfs_file_config *cfg) {
01297     // deorphan if we haven't yet, needed at most once after poweron
01298     if ((flags & 3) != LFS_O_RDONLY && !lfs->deorphaned) {
01299         int err = lfs_deorphan(lfs);
01300         if (err) {
01301             return err;
01302         }
01303     }
01304 
01305     // allocate entry for file if it doesn't exist
01306     lfs_dir_t cwd;
01307     lfs_entry_t entry;
01308     int err = lfs_dir_find(lfs, &cwd, &entry, &path);
01309     if (err && (err != LFS_ERR_NOENT || strchr(path, '/') != NULL)) {
01310         return err;
01311     }
01312 
01313     if (err == LFS_ERR_NOENT) {
01314         if (!(flags & LFS_O_CREAT)) {
01315             return LFS_ERR_NOENT;
01316         }
01317 
01318         // create entry to remember name
01319         entry.d.type = LFS_TYPE_REG;
01320         entry.d.elen = sizeof(entry.d) - 4;
01321         entry.d.alen = 0;
01322         entry.d.nlen = strlen(path);
01323         entry.d.u.file.head = 0xffffffff;
01324         entry.d.u.file.size = 0;
01325         err = lfs_dir_append(lfs, &cwd, &entry, path);
01326         if (err) {
01327             return err;
01328         }
01329     } else if (entry.d.type == LFS_TYPE_DIR) {
01330         return LFS_ERR_ISDIR;
01331     } else if (flags & LFS_O_EXCL) {
01332         return LFS_ERR_EXIST;
01333     }
01334 
01335     // setup file struct
01336     file->cfg = cfg;
01337     file->pair[0] = cwd.pair[0];
01338     file->pair[1] = cwd.pair[1];
01339     file->poff = entry.off;
01340     file->head = entry.d.u.file.head;
01341     file->size = entry.d.u.file.size;
01342     file->flags = flags;
01343     file->pos = 0;
01344 
01345     if (flags & LFS_O_TRUNC) {
01346         if (file->size != 0) {
01347             file->flags |= LFS_F_DIRTY;
01348         }
01349         file->head = 0xffffffff;
01350         file->size = 0;
01351     }
01352 
01353     // allocate buffer if needed
01354     file->cache.block = 0xffffffff;
01355     if (file->cfg && file->cfg->buffer) {
01356         file->cache.buffer = file->cfg->buffer;
01357     } else if (lfs->cfg->file_buffer) {
01358         if (lfs->files) {
01359             // already in use
01360             return LFS_ERR_NOMEM;
01361         }
01362         file->cache.buffer = lfs->cfg->file_buffer;
01363     } else if ((file->flags & 3) == LFS_O_RDONLY) {
01364         file->cache.buffer = lfs_malloc(lfs->cfg->read_size);
01365         if (!file->cache.buffer) {
01366             return LFS_ERR_NOMEM;
01367         }
01368     } else {
01369         file->cache.buffer = lfs_malloc(lfs->cfg->prog_size);
01370         if (!file->cache.buffer) {
01371             return LFS_ERR_NOMEM;
01372         }
01373     }
01374 
01375     // zero to avoid information leak
01376     lfs_cache_zero(lfs, &file->cache);
01377 
01378     // add to list of files
01379     file->next = lfs->files;
01380     lfs->files = file;
01381 
01382     return 0;
01383 }
01384 
01385 int lfs_file_open(lfs_t *lfs, lfs_file_t *file,
01386         const char *path, int flags) {
01387     return lfs_file_opencfg(lfs, file, path, flags, NULL);
01388 }
01389 
01390 int lfs_file_close(lfs_t *lfs, lfs_file_t *file) {
01391     int err = lfs_file_sync(lfs, file);
01392 
01393     // remove from list of files
01394     for (lfs_file_t **p = &lfs->files; *p; p = &(*p)->next) {
01395         if (*p == file) {
01396             *p = file->next;
01397             break;
01398         }
01399     }
01400 
01401     // clean up memory
01402     if (!(file->cfg && file->cfg->buffer) && !lfs->cfg->file_buffer) {
01403         lfs_free(file->cache.buffer);
01404     }
01405 
01406     return err;
01407 }
01408 
01409 static int lfs_file_relocate(lfs_t *lfs, lfs_file_t *file) {
01410 relocate:
01411     LFS_DEBUG("Bad block at %" PRIu32, file->block);
01412 
01413     // just relocate what exists into new block
01414     lfs_block_t nblock;
01415     int err = lfs_alloc(lfs, &nblock);
01416     if (err) {
01417         return err;
01418     }
01419 
01420     err = lfs_bd_erase(lfs, nblock);
01421     if (err) {
01422         if (err == LFS_ERR_CORRUPT) {
01423             goto relocate;
01424         }
01425         return err;
01426     }
01427 
01428     // either read from dirty cache or disk
01429     for (lfs_off_t i = 0; i < file->off; i++) {
01430         uint8_t data;
01431         err = lfs_cache_read(lfs, &lfs->rcache, &file->cache,
01432                 file->block, i, &data, 1);
01433         if (err) {
01434             return err;
01435         }
01436 
01437         err = lfs_cache_prog(lfs, &lfs->pcache, &lfs->rcache,
01438                 nblock, i, &data, 1);
01439         if (err) {
01440             if (err == LFS_ERR_CORRUPT) {
01441                 goto relocate;
01442             }
01443             return err;
01444         }
01445     }
01446 
01447     // copy over new state of file
01448     memcpy(file->cache.buffer, lfs->pcache.buffer, lfs->cfg->prog_size);
01449     file->cache.block = lfs->pcache.block;
01450     file->cache.off = lfs->pcache.off;
01451     lfs_cache_zero(lfs, &lfs->pcache);
01452 
01453     file->block = nblock;
01454     return 0;
01455 }
01456 
01457 static int lfs_file_flush(lfs_t *lfs, lfs_file_t *file) {
01458     if (file->flags & LFS_F_READING) {
01459         // just drop read cache
01460         lfs_cache_drop(lfs, &file->cache);
01461         file->flags &= ~LFS_F_READING;
01462     }
01463 
01464     if (file->flags & LFS_F_WRITING) {
01465         lfs_off_t pos = file->pos;
01466 
01467         // copy over anything after current branch
01468         lfs_file_t orig = {
01469             .head = file->head,
01470             .size = file->size,
01471             .flags = LFS_O_RDONLY,
01472             .pos = file->pos,
01473             .cache = lfs->rcache,
01474         };
01475         lfs_cache_drop(lfs, &lfs->rcache);
01476 
01477         while (file->pos < file->size) {
01478             // copy over a byte at a time, leave it up to caching
01479             // to make this efficient
01480             uint8_t data;
01481             lfs_ssize_t res = lfs_file_read(lfs, &orig, &data, 1);
01482             if (res < 0) {
01483                 return res;
01484             }
01485 
01486             res = lfs_file_write(lfs, file, &data, 1);
01487             if (res < 0) {
01488                 return res;
01489             }
01490 
01491             // keep our reference to the rcache in sync
01492             if (lfs->rcache.block != 0xffffffff) {
01493                 lfs_cache_drop(lfs, &orig.cache);
01494                 lfs_cache_drop(lfs, &lfs->rcache);
01495             }
01496         }
01497 
01498         // write out what we have
01499         while (true) {
01500             int err = lfs_cache_flush(lfs, &file->cache, &lfs->rcache);
01501             if (err) {
01502                 if (err == LFS_ERR_CORRUPT) {
01503                     goto relocate;
01504                 }
01505                 return err;
01506             }
01507 
01508             break;
01509 relocate:
01510             err = lfs_file_relocate(lfs, file);
01511             if (err) {
01512                 return err;
01513             }
01514         }
01515 
01516         // actual file updates
01517         file->head = file->block;
01518         file->size = file->pos;
01519         file->flags &= ~LFS_F_WRITING;
01520         file->flags |= LFS_F_DIRTY;
01521 
01522         file->pos = pos;
01523     }
01524 
01525     return 0;
01526 }
01527 
01528 int lfs_file_sync(lfs_t *lfs, lfs_file_t *file) {
01529     int err = lfs_file_flush(lfs, file);
01530     if (err) {
01531         return err;
01532     }
01533 
01534     if ((file->flags & LFS_F_DIRTY) &&
01535             !(file->flags & LFS_F_ERRED) &&
01536             !lfs_pairisnull(file->pair)) {
01537         // update dir entry
01538         lfs_dir_t cwd;
01539         err = lfs_dir_fetch(lfs, &cwd, file->pair);
01540         if (err) {
01541             return err;
01542         }
01543 
01544         lfs_entry_t entry = {.off = file->poff};
01545         err = lfs_bd_read(lfs, cwd.pair[0], entry.off,
01546                 &entry.d, sizeof(entry.d));
01547         lfs_entry_fromle32(&entry.d);
01548         if (err) {
01549             return err;
01550         }
01551 
01552         LFS_ASSERT(entry.d.type == LFS_TYPE_REG);
01553         entry.d.u.file.head = file->head;
01554         entry.d.u.file.size = file->size;
01555 
01556         err = lfs_dir_update(lfs, &cwd, &entry, NULL);
01557         if (err) {
01558             return err;
01559         }
01560 
01561         file->flags &= ~LFS_F_DIRTY;
01562     }
01563 
01564     return 0;
01565 }
01566 
01567 lfs_ssize_t lfs_file_read(lfs_t *lfs, lfs_file_t *file,
01568         void *buffer, lfs_size_t size) {
01569     uint8_t *data = buffer;
01570     lfs_size_t nsize = size;
01571 
01572     if ((file->flags & 3) == LFS_O_WRONLY) {
01573         return LFS_ERR_BADF;
01574     }
01575 
01576     if (file->flags & LFS_F_WRITING) {
01577         // flush out any writes
01578         int err = lfs_file_flush(lfs, file);
01579         if (err) {
01580             return err;
01581         }
01582     }
01583 
01584     if (file->pos >= file->size) {
01585         // eof if past end
01586         return 0;
01587     }
01588 
01589     size = lfs_min(size, file->size - file->pos);
01590     nsize = size;
01591 
01592     while (nsize > 0) {
01593         // check if we need a new block
01594         if (!(file->flags & LFS_F_READING) ||
01595                 file->off == lfs->cfg->block_size) {
01596             int err = lfs_ctz_find(lfs, &file->cache, NULL,
01597                     file->head, file->size,
01598                     file->pos, &file->block, &file->off);
01599             if (err) {
01600                 return err;
01601             }
01602 
01603             file->flags |= LFS_F_READING;
01604         }
01605 
01606         // read as much as we can in current block
01607         lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off);
01608         int err = lfs_cache_read(lfs, &file->cache, NULL,
01609                 file->block, file->off, data, diff);
01610         if (err) {
01611             return err;
01612         }
01613 
01614         file->pos += diff;
01615         file->off += diff;
01616         data += diff;
01617         nsize -= diff;
01618     }
01619 
01620     return size;
01621 }
01622 
01623 lfs_ssize_t lfs_file_write(lfs_t *lfs, lfs_file_t *file,
01624         const void *buffer, lfs_size_t size) {
01625     const uint8_t *data = buffer;
01626     lfs_size_t nsize = size;
01627 
01628     if ((file->flags & 3) == LFS_O_RDONLY) {
01629         return LFS_ERR_BADF;
01630     }
01631 
01632     if (file->flags & LFS_F_READING) {
01633         // drop any reads
01634         int err = lfs_file_flush(lfs, file);
01635         if (err) {
01636             return err;
01637         }
01638     }
01639 
01640     if ((file->flags & LFS_O_APPEND) && file->pos < file->size) {
01641         file->pos = file->size;
01642     }
01643 
01644     if (!(file->flags & LFS_F_WRITING) && file->pos > file->size) {
01645         // fill with zeros
01646         lfs_off_t pos = file->pos;
01647         file->pos = file->size;
01648 
01649         while (file->pos < pos) {
01650             lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1);
01651             if (res < 0) {
01652                 return res;
01653             }
01654         }
01655     }
01656 
01657     while (nsize > 0) {
01658         // check if we need a new block
01659         if (!(file->flags & LFS_F_WRITING) ||
01660                 file->off == lfs->cfg->block_size) {
01661             if (!(file->flags & LFS_F_WRITING) && file->pos > 0) {
01662                 // find out which block we're extending from
01663                 int err = lfs_ctz_find(lfs, &file->cache, NULL,
01664                         file->head, file->size,
01665                         file->pos-1, &file->block, &file->off);
01666                 if (err) {
01667                     file->flags |= LFS_F_ERRED;
01668                     return err;
01669                 }
01670 
01671                 // mark cache as dirty since we may have read data into it
01672                 lfs_cache_zero(lfs, &file->cache);
01673             }
01674 
01675             // extend file with new blocks
01676             lfs_alloc_ack(lfs);
01677             int err = lfs_ctz_extend(lfs, &lfs->rcache, &file->cache,
01678                     file->block, file->pos,
01679                     &file->block, &file->off);
01680             if (err) {
01681                 file->flags |= LFS_F_ERRED;
01682                 return err;
01683             }
01684 
01685             file->flags |= LFS_F_WRITING;
01686         }
01687 
01688         // program as much as we can in current block
01689         lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off);
01690         while (true) {
01691             int err = lfs_cache_prog(lfs, &file->cache, &lfs->rcache,
01692                     file->block, file->off, data, diff);
01693             if (err) {
01694                 if (err == LFS_ERR_CORRUPT) {
01695                     goto relocate;
01696                 }
01697                 file->flags |= LFS_F_ERRED;
01698                 return err;
01699             }
01700 
01701             break;
01702 relocate:
01703             err = lfs_file_relocate(lfs, file);
01704             if (err) {
01705                 file->flags |= LFS_F_ERRED;
01706                 return err;
01707             }
01708         }
01709 
01710         file->pos += diff;
01711         file->off += diff;
01712         data += diff;
01713         nsize -= diff;
01714 
01715         lfs_alloc_ack(lfs);
01716     }
01717 
01718     file->flags &= ~LFS_F_ERRED;
01719     return size;
01720 }
01721 
01722 lfs_soff_t lfs_file_seek(lfs_t *lfs, lfs_file_t *file,
01723         lfs_soff_t off, int whence) {
01724     // write out everything beforehand, may be noop if rdonly
01725     int err = lfs_file_flush(lfs, file);
01726     if (err) {
01727         return err;
01728     }
01729 
01730     // update pos
01731     if (whence == LFS_SEEK_SET) {
01732         file->pos = off;
01733     } else if (whence == LFS_SEEK_CUR) {
01734         if (off < 0 && (lfs_off_t)-off > file->pos) {
01735             return LFS_ERR_INVAL;
01736         }
01737 
01738         file->pos = file->pos + off;
01739     } else if (whence == LFS_SEEK_END) {
01740         if (off < 0 && (lfs_off_t)-off > file->size) {
01741             return LFS_ERR_INVAL;
01742         }
01743 
01744         file->pos = file->size + off;
01745     }
01746 
01747     return file->pos;
01748 }
01749 
01750 int lfs_file_truncate(lfs_t *lfs, lfs_file_t *file, lfs_off_t size) {
01751     if ((file->flags & 3) == LFS_O_RDONLY) {
01752         return LFS_ERR_BADF;
01753     }
01754 
01755     lfs_off_t oldsize = lfs_file_size(lfs, file);
01756     if (size < oldsize) {
01757         // need to flush since directly changing metadata
01758         int err = lfs_file_flush(lfs, file);
01759         if (err) {
01760             return err;
01761         }
01762 
01763         // lookup new head in ctz skip list
01764         err = lfs_ctz_find(lfs, &file->cache, NULL,
01765                 file->head, file->size,
01766                 size, &file->head, &(lfs_off_t){0});
01767         if (err) {
01768             return err;
01769         }
01770 
01771         file->size = size;
01772         file->flags |= LFS_F_DIRTY;
01773     } else if (size > oldsize) {
01774         lfs_off_t pos = file->pos;
01775 
01776         // flush+seek if not already at end
01777         if (file->pos != oldsize) {
01778             int err = lfs_file_seek(lfs, file, 0, LFS_SEEK_END);
01779             if (err < 0) {
01780                 return err;
01781             }
01782         }
01783 
01784         // fill with zeros
01785         while (file->pos < size) {
01786             lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1);
01787             if (res < 0) {
01788                 return res;
01789             }
01790         }
01791 
01792         // restore pos
01793         int err = lfs_file_seek(lfs, file, pos, LFS_SEEK_SET);
01794         if (err < 0) {
01795             return err;
01796         }
01797     }
01798 
01799     return 0;
01800 }
01801 
01802 lfs_soff_t lfs_file_tell(lfs_t *lfs, lfs_file_t *file) {
01803     (void)lfs;
01804     return file->pos;
01805 }
01806 
01807 int lfs_file_rewind(lfs_t *lfs, lfs_file_t *file) {
01808     lfs_soff_t res = lfs_file_seek(lfs, file, 0, LFS_SEEK_SET);
01809     if (res < 0) {
01810         return res;
01811     }
01812 
01813     return 0;
01814 }
01815 
01816 lfs_soff_t lfs_file_size(lfs_t *lfs, lfs_file_t *file) {
01817     (void)lfs;
01818     if (file->flags & LFS_F_WRITING) {
01819         return lfs_max(file->pos, file->size);
01820     } else {
01821         return file->size;
01822     }
01823 }
01824 
01825 
01826 /// General fs operations ///
01827 int lfs_stat(lfs_t *lfs, const char *path, struct lfs_info *info) {
01828     lfs_dir_t cwd;
01829     lfs_entry_t entry;
01830     int err = lfs_dir_find(lfs, &cwd, &entry, &path);
01831     if (err) {
01832         return err;
01833     }
01834 
01835     memset(info, 0, sizeof(*info));
01836     info->type = entry.d.type;
01837     if (info->type == LFS_TYPE_REG) {
01838         info->size = entry.d.u.file.size;
01839     }
01840 
01841     if (lfs_paircmp(entry.d.u.dir, lfs->root) == 0) {
01842         strcpy(info->name, "/");
01843     } else {
01844         err = lfs_bd_read(lfs, cwd.pair[0],
01845                 entry.off + 4+entry.d.elen+entry.d.alen,
01846                 info->name, entry.d.nlen);
01847         if (err) {
01848             return err;
01849         }
01850     }
01851 
01852     return 0;
01853 }
01854 
01855 int lfs_remove(lfs_t *lfs, const char *path) {
01856     // deorphan if we haven't yet, needed at most once after poweron
01857     if (!lfs->deorphaned) {
01858         int err = lfs_deorphan(lfs);
01859         if (err) {
01860             return err;
01861         }
01862     }
01863 
01864     lfs_dir_t cwd;
01865     lfs_entry_t entry;
01866     int err = lfs_dir_find(lfs, &cwd, &entry, &path);
01867     if (err) {
01868         return err;
01869     }
01870 
01871     lfs_dir_t dir;
01872     if (entry.d.type == LFS_TYPE_DIR) {
01873         // must be empty before removal, checking size
01874         // without masking top bit checks for any case where
01875         // dir is not empty
01876         err = lfs_dir_fetch(lfs, &dir, entry.d.u.dir);
01877         if (err) {
01878             return err;
01879         } else if (dir.d.size != sizeof(dir.d)+4) {
01880             return LFS_ERR_NOTEMPTY;
01881         }
01882     }
01883 
01884     // remove the entry
01885     err = lfs_dir_remove(lfs, &cwd, &entry);
01886     if (err) {
01887         return err;
01888     }
01889 
01890     // if we were a directory, find pred, replace tail
01891     if (entry.d.type == LFS_TYPE_DIR) {
01892         int res = lfs_pred(lfs, dir.pair, &cwd);
01893         if (res < 0) {
01894             return res;
01895         }
01896 
01897         LFS_ASSERT(res); // must have pred
01898         cwd.d.tail[0] = dir.d.tail[0];
01899         cwd.d.tail[1] = dir.d.tail[1];
01900 
01901         err = lfs_dir_commit(lfs, &cwd, NULL, 0);
01902         if (err) {
01903             return err;
01904         }
01905     }
01906 
01907     return 0;
01908 }
01909 
01910 int lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath) {
01911     // deorphan if we haven't yet, needed at most once after poweron
01912     if (!lfs->deorphaned) {
01913         int err = lfs_deorphan(lfs);
01914         if (err) {
01915             return err;
01916         }
01917     }
01918 
01919     // find old entry
01920     lfs_dir_t oldcwd;
01921     lfs_entry_t oldentry;
01922     int err = lfs_dir_find(lfs, &oldcwd, &oldentry, &oldpath);
01923     if (err) {
01924         return err;
01925     }
01926 
01927     // allocate new entry
01928     lfs_dir_t newcwd;
01929     lfs_entry_t preventry;
01930     err = lfs_dir_find(lfs, &newcwd, &preventry, &newpath);
01931     if (err && (err != LFS_ERR_NOENT || strchr(newpath, '/') != NULL)) {
01932         return err;
01933     }
01934 
01935     bool prevexists = (err != LFS_ERR_NOENT);
01936     bool samepair = (lfs_paircmp(oldcwd.pair, newcwd.pair) == 0);
01937 
01938     // must have same type
01939     if (prevexists && preventry.d.type != oldentry.d.type) {
01940         return LFS_ERR_ISDIR;
01941     }
01942 
01943     lfs_dir_t dir;
01944     if (prevexists && preventry.d.type == LFS_TYPE_DIR) {
01945         // must be empty before removal, checking size
01946         // without masking top bit checks for any case where
01947         // dir is not empty
01948         err = lfs_dir_fetch(lfs, &dir, preventry.d.u.dir);
01949         if (err) {
01950             return err;
01951         } else if (dir.d.size != sizeof(dir.d)+4) {
01952             return LFS_ERR_NOTEMPTY;
01953         }
01954     }
01955 
01956     // mark as moving
01957     oldentry.d.type |= 0x80;
01958     err = lfs_dir_update(lfs, &oldcwd, &oldentry, NULL);
01959     if (err) {
01960         return err;
01961     }
01962 
01963     // update pair if newcwd == oldcwd
01964     if (samepair) {
01965         newcwd = oldcwd;
01966     }
01967 
01968     // move to new location
01969     lfs_entry_t newentry = preventry;
01970     newentry.d = oldentry.d;
01971     newentry.d.type &= ~0x80;
01972     newentry.d.nlen = strlen(newpath);
01973 
01974     if (prevexists) {
01975         err = lfs_dir_update(lfs, &newcwd, &newentry, newpath);
01976         if (err) {
01977             return err;
01978         }
01979     } else {
01980         err = lfs_dir_append(lfs, &newcwd, &newentry, newpath);
01981         if (err) {
01982             return err;
01983         }
01984     }
01985 
01986     // update pair if newcwd == oldcwd
01987     if (samepair) {
01988         oldcwd = newcwd;
01989     }
01990 
01991     // remove old entry
01992     err = lfs_dir_remove(lfs, &oldcwd, &oldentry);
01993     if (err) {
01994         return err;
01995     }
01996 
01997     // if we were a directory, find pred, replace tail
01998     if (prevexists && preventry.d.type == LFS_TYPE_DIR) {
01999         int res = lfs_pred(lfs, dir.pair, &newcwd);
02000         if (res < 0) {
02001             return res;
02002         }
02003 
02004         LFS_ASSERT(res); // must have pred
02005         newcwd.d.tail[0] = dir.d.tail[0];
02006         newcwd.d.tail[1] = dir.d.tail[1];
02007 
02008         err = lfs_dir_commit(lfs, &newcwd, NULL, 0);
02009         if (err) {
02010             return err;
02011         }
02012     }
02013 
02014     return 0;
02015 }
02016 
02017 
02018 /// Filesystem operations ///
02019 static void lfs_deinit(lfs_t *lfs) {
02020     // free allocated memory
02021     if (!lfs->cfg->read_buffer) {
02022         lfs_free(lfs->rcache.buffer);
02023     }
02024 
02025     if (!lfs->cfg->prog_buffer) {
02026         lfs_free(lfs->pcache.buffer);
02027     }
02028 
02029     if (!lfs->cfg->lookahead_buffer) {
02030         lfs_free(lfs->free.buffer);
02031     }
02032 }
02033 
02034 static int lfs_init(lfs_t *lfs, const struct lfs_config *cfg) {
02035     lfs->cfg = cfg;
02036 
02037     // setup read cache
02038     if (lfs->cfg->read_buffer) {
02039         lfs->rcache.buffer = lfs->cfg->read_buffer;
02040     } else {
02041         lfs->rcache.buffer = lfs_malloc(lfs->cfg->read_size);
02042         if (!lfs->rcache.buffer) {
02043             goto cleanup;
02044         }
02045     }
02046 
02047     // setup program cache
02048     if (lfs->cfg->prog_buffer) {
02049         lfs->pcache.buffer = lfs->cfg->prog_buffer;
02050     } else {
02051         lfs->pcache.buffer = lfs_malloc(lfs->cfg->prog_size);
02052         if (!lfs->pcache.buffer) {
02053             goto cleanup;
02054         }
02055     }
02056 
02057     // zero to avoid information leaks
02058     lfs_cache_zero(lfs, &lfs->rcache);
02059     lfs_cache_zero(lfs, &lfs->pcache);
02060 
02061     // setup lookahead, round down to nearest 32-bits
02062     LFS_ASSERT(lfs->cfg->lookahead % 32 == 0);
02063     LFS_ASSERT(lfs->cfg->lookahead > 0);
02064     if (lfs->cfg->lookahead_buffer) {
02065         lfs->free.buffer = lfs->cfg->lookahead_buffer;
02066     } else {
02067         lfs->free.buffer = lfs_malloc(lfs->cfg->lookahead/8);
02068         if (!lfs->free.buffer) {
02069             goto cleanup;
02070         }
02071     }
02072 
02073     // check that program and read sizes are multiples of the block size
02074     LFS_ASSERT(lfs->cfg->prog_size % lfs->cfg->read_size == 0);
02075     LFS_ASSERT(lfs->cfg->block_size % lfs->cfg->prog_size == 0);
02076 
02077     // check that the block size is large enough to fit ctz pointers
02078     LFS_ASSERT(4*lfs_npw2(0xffffffff / (lfs->cfg->block_size-2*4))
02079             <= lfs->cfg->block_size);
02080 
02081     // setup default state
02082     lfs->root[0] = 0xffffffff;
02083     lfs->root[1] = 0xffffffff;
02084     lfs->files = NULL;
02085     lfs->dirs = NULL;
02086     lfs->deorphaned = false;
02087 
02088     return 0;
02089 
02090 cleanup:
02091     lfs_deinit(lfs);
02092     return LFS_ERR_NOMEM;
02093 }
02094 
02095 int lfs_format(lfs_t *lfs, const struct lfs_config *cfg) {
02096     int err = lfs_init(lfs, cfg);
02097     if (err) {
02098         return err;
02099     }
02100 
02101     // create free lookahead
02102     memset(lfs->free.buffer, 0, lfs->cfg->lookahead/8);
02103     lfs->free.off = 0;
02104     lfs->free.size = lfs_min(lfs->cfg->lookahead, lfs->cfg->block_count);
02105     lfs->free.i = 0;
02106     lfs_alloc_ack(lfs);
02107 
02108     // create superblock dir
02109     lfs_dir_t superdir;
02110     err = lfs_dir_alloc(lfs, &superdir);
02111     if (err) {
02112         goto cleanup;
02113     }
02114 
02115     // write root directory
02116     lfs_dir_t root;
02117     err = lfs_dir_alloc(lfs, &root);
02118     if (err) {
02119         goto cleanup;
02120     }
02121 
02122     err = lfs_dir_commit(lfs, &root, NULL, 0);
02123     if (err) {
02124         goto cleanup;
02125     }
02126 
02127     lfs->root[0] = root.pair[0];
02128     lfs->root[1] = root.pair[1];
02129 
02130     // write superblocks
02131     lfs_superblock_t superblock = {
02132         .off = sizeof(superdir.d),
02133         .d.type = LFS_TYPE_SUPERBLOCK,
02134         .d.elen = sizeof(superblock.d) - sizeof(superblock.d.magic) - 4,
02135         .d.nlen = sizeof(superblock.d.magic),
02136         .d.version = LFS_DISK_VERSION,
02137         .d.magic = {"littlefs"},
02138         .d.block_size  = lfs->cfg->block_size,
02139         .d.block_count = lfs->cfg->block_count,
02140         .d.root = {lfs->root[0], lfs->root[1]},
02141     };
02142     superdir.d.tail[0] = root.pair[0];
02143     superdir.d.tail[1] = root.pair[1];
02144     superdir.d.size = sizeof(superdir.d) + sizeof(superblock.d) + 4;
02145 
02146     // write both pairs to be safe
02147     lfs_superblock_tole32(&superblock.d);
02148     bool valid = false;
02149     for (int i = 0; i < 2; i++) {
02150         err = lfs_dir_commit(lfs, &superdir, (struct lfs_region[]){
02151                 {sizeof(superdir.d), sizeof(superblock.d),
02152                  &superblock.d, sizeof(superblock.d)}
02153             }, 1);
02154         if (err && err != LFS_ERR_CORRUPT) {
02155             goto cleanup;
02156         }
02157 
02158         valid = valid || !err;
02159     }
02160 
02161     if (!valid) {
02162         err = LFS_ERR_CORRUPT;
02163         goto cleanup;
02164     }
02165 
02166     // sanity check that fetch works
02167     err = lfs_dir_fetch(lfs, &superdir, (const lfs_block_t[2]){0, 1});
02168     if (err) {
02169         goto cleanup;
02170     }
02171 
02172     lfs_alloc_ack(lfs);
02173 
02174 cleanup:
02175     lfs_deinit(lfs);
02176     return err;
02177 }
02178 
02179 int lfs_mount(lfs_t *lfs, const struct lfs_config *cfg) {
02180     int err = lfs_init(lfs, cfg);
02181     if (err) {
02182         return err;
02183     }
02184 
02185     // setup free lookahead
02186     lfs->free.off = 0;
02187     lfs->free.size = 0;
02188     lfs->free.i = 0;
02189     lfs_alloc_ack(lfs);
02190 
02191     // load superblock
02192     lfs_dir_t dir;
02193     lfs_superblock_t superblock;
02194     err = lfs_dir_fetch(lfs, &dir, (const lfs_block_t[2]){0, 1});
02195     if (err && err != LFS_ERR_CORRUPT) {
02196         goto cleanup;
02197     }
02198 
02199     if (!err) {
02200         err = lfs_bd_read(lfs, dir.pair[0], sizeof(dir.d),
02201                 &superblock.d, sizeof(superblock.d));
02202         lfs_superblock_fromle32(&superblock.d);
02203         if (err) {
02204             goto cleanup;
02205         }
02206 
02207         lfs->root[0] = superblock.d.root[0];
02208         lfs->root[1] = superblock.d.root[1];
02209     }
02210 
02211     if (err || memcmp(superblock.d.magic, "littlefs", 8) != 0) {
02212         LFS_ERROR("Invalid superblock at %d %d", 0, 1);
02213         err = LFS_ERR_CORRUPT;
02214         goto cleanup;
02215     }
02216 
02217     uint16_t major_version = (0xffff & (superblock.d.version >> 16));
02218     uint16_t minor_version = (0xffff & (superblock.d.version >>  0));
02219     if ((major_version != LFS_DISK_VERSION_MAJOR ||
02220          minor_version > LFS_DISK_VERSION_MINOR)) {
02221         LFS_ERROR("Invalid version %d.%d", major_version, minor_version);
02222         err = LFS_ERR_INVAL;
02223         goto cleanup;
02224     }
02225 
02226     return 0;
02227 
02228 cleanup:
02229 
02230     lfs_deinit(lfs);
02231     return err;
02232 }
02233 
02234 int lfs_unmount(lfs_t *lfs) {
02235     lfs_deinit(lfs);
02236     return 0;
02237 }
02238 
02239 
02240 /// Littlefs specific operations ///
02241 int lfs_traverse(lfs_t *lfs, int (*cb)(void*, lfs_block_t), void *data) {
02242     if (lfs_pairisnull(lfs->root)) {
02243         return 0;
02244     }
02245 
02246     // iterate over metadata pairs
02247     lfs_dir_t dir;
02248     lfs_entry_t entry;
02249     lfs_block_t cwd[2] = {0, 1};
02250 
02251     while (true) {
02252         for (int i = 0; i < 2; i++) {
02253             int err = cb(data, cwd[i]);
02254             if (err) {
02255                 return err;
02256             }
02257         }
02258 
02259         int err = lfs_dir_fetch(lfs, &dir, cwd);
02260         if (err) {
02261             return err;
02262         }
02263 
02264         // iterate over contents
02265         while (dir.off + sizeof(entry.d) <= (0x7fffffff & dir.d.size)-4) {
02266             err = lfs_bd_read(lfs, dir.pair[0], dir.off,
02267                     &entry.d, sizeof(entry.d));
02268             lfs_entry_fromle32(&entry.d);
02269             if (err) {
02270                 return err;
02271             }
02272 
02273             dir.off += lfs_entry_size(&entry);
02274             if ((0x70 & entry.d.type) == (0x70 & LFS_TYPE_REG)) {
02275                 err = lfs_ctz_traverse(lfs, &lfs->rcache, NULL,
02276                         entry.d.u.file.head, entry.d.u.file.size, cb, data);
02277                 if (err) {
02278                     return err;
02279                 }
02280             }
02281         }
02282 
02283         cwd[0] = dir.d.tail[0];
02284         cwd[1] = dir.d.tail[1];
02285 
02286         if (lfs_pairisnull(cwd)) {
02287             break;
02288         }
02289     }
02290 
02291     // iterate over any open files
02292     for (lfs_file_t *f = lfs->files; f; f = f->next) {
02293         if (f->flags & LFS_F_DIRTY) {
02294             int err = lfs_ctz_traverse(lfs, &lfs->rcache, &f->cache,
02295                     f->head, f->size, cb, data);
02296             if (err) {
02297                 return err;
02298             }
02299         }
02300 
02301         if (f->flags & LFS_F_WRITING) {
02302             int err = lfs_ctz_traverse(lfs, &lfs->rcache, &f->cache,
02303                     f->block, f->pos, cb, data);
02304             if (err) {
02305                 return err;
02306             }
02307         }
02308     }
02309 
02310     return 0;
02311 }
02312 
02313 static int lfs_pred(lfs_t *lfs, const lfs_block_t dir[2], lfs_dir_t *pdir) {
02314     if (lfs_pairisnull(lfs->root)) {
02315         return 0;
02316     }
02317 
02318     // iterate over all directory directory entries
02319     int err = lfs_dir_fetch(lfs, pdir, (const lfs_block_t[2]){0, 1});
02320     if (err) {
02321         return err;
02322     }
02323 
02324     while (!lfs_pairisnull(pdir->d.tail)) {
02325         if (lfs_paircmp(pdir->d.tail, dir) == 0) {
02326             return true;
02327         }
02328 
02329         err = lfs_dir_fetch(lfs, pdir, pdir->d.tail);
02330         if (err) {
02331             return err;
02332         }
02333     }
02334 
02335     return false;
02336 }
02337 
02338 static int lfs_parent(lfs_t *lfs, const lfs_block_t dir[2],
02339         lfs_dir_t *parent, lfs_entry_t *entry) {
02340     if (lfs_pairisnull(lfs->root)) {
02341         return 0;
02342     }
02343 
02344     parent->d.tail[0] = 0;
02345     parent->d.tail[1] = 1;
02346 
02347     // iterate over all directory directory entries
02348     while (!lfs_pairisnull(parent->d.tail)) {
02349         int err = lfs_dir_fetch(lfs, parent, parent->d.tail);
02350         if (err) {
02351             return err;
02352         }
02353 
02354         while (true) {
02355             err = lfs_dir_next(lfs, parent, entry);
02356             if (err && err != LFS_ERR_NOENT) {
02357                 return err;
02358             }
02359 
02360             if (err == LFS_ERR_NOENT) {
02361                 break;
02362             }
02363 
02364             if (((0x70 & entry->d.type) == (0x70 & LFS_TYPE_DIR)) &&
02365                  lfs_paircmp(entry->d.u.dir, dir) == 0) {
02366                 return true;
02367             }
02368         }
02369     }
02370 
02371     return false;
02372 }
02373 
02374 static int lfs_moved(lfs_t *lfs, const void *e) {
02375     if (lfs_pairisnull(lfs->root)) {
02376         return 0;
02377     }
02378 
02379     // skip superblock
02380     lfs_dir_t cwd;
02381     int err = lfs_dir_fetch(lfs, &cwd, (const lfs_block_t[2]){0, 1});
02382     if (err) {
02383         return err;
02384     }
02385 
02386     // iterate over all directory directory entries
02387     lfs_entry_t entry;
02388     while (!lfs_pairisnull(cwd.d.tail)) {
02389         err = lfs_dir_fetch(lfs, &cwd, cwd.d.tail);
02390         if (err) {
02391             return err;
02392         }
02393 
02394         while (true) {
02395             err = lfs_dir_next(lfs, &cwd, &entry);
02396             if (err && err != LFS_ERR_NOENT) {
02397                 return err;
02398             }
02399 
02400             if (err == LFS_ERR_NOENT) {
02401                 break;
02402             }
02403 
02404             if (!(0x80 & entry.d.type) &&
02405                  memcmp(&entry.d.u, e, sizeof(entry.d.u)) == 0) {
02406                 return true;
02407             }
02408         }
02409     }
02410 
02411     return false;
02412 }
02413 
02414 static int lfs_relocate(lfs_t *lfs,
02415         const lfs_block_t oldpair[2], const lfs_block_t newpair[2]) {
02416     // find parent
02417     lfs_dir_t parent;
02418     lfs_entry_t entry;
02419     int res = lfs_parent(lfs, oldpair, &parent, &entry);
02420     if (res < 0) {
02421         return res;
02422     }
02423 
02424     if (res) {
02425         // update disk, this creates a desync
02426         entry.d.u.dir[0] = newpair[0];
02427         entry.d.u.dir[1] = newpair[1];
02428 
02429         int err = lfs_dir_update(lfs, &parent, &entry, NULL);
02430         if (err) {
02431             return err;
02432         }
02433 
02434         // update internal root
02435         if (lfs_paircmp(oldpair, lfs->root) == 0) {
02436             LFS_DEBUG("Relocating root %" PRIu32 " %" PRIu32,
02437                     newpair[0], newpair[1]);
02438             lfs->root[0] = newpair[0];
02439             lfs->root[1] = newpair[1];
02440         }
02441 
02442         // clean up bad block, which should now be a desync
02443         return lfs_deorphan(lfs);
02444     }
02445 
02446     // find pred
02447     res = lfs_pred(lfs, oldpair, &parent);
02448     if (res < 0) {
02449         return res;
02450     }
02451 
02452     if (res) {
02453         // just replace bad pair, no desync can occur
02454         parent.d.tail[0] = newpair[0];
02455         parent.d.tail[1] = newpair[1];
02456 
02457         return lfs_dir_commit(lfs, &parent, NULL, 0);
02458     }
02459 
02460     // couldn't find dir, must be new
02461     return 0;
02462 }
02463 
02464 int lfs_deorphan(lfs_t *lfs) {
02465     lfs->deorphaned = true;
02466 
02467     if (lfs_pairisnull(lfs->root)) {
02468         return 0;
02469     }
02470 
02471     lfs_dir_t pdir = {.d.size = 0x80000000};
02472     lfs_dir_t cwd = {.d.tail[0] = 0, .d.tail[1] = 1};
02473 
02474     // iterate over all directory directory entries
02475     while (!lfs_pairisnull(cwd.d.tail)) {
02476         int err = lfs_dir_fetch(lfs, &cwd, cwd.d.tail);
02477         if (err) {
02478             return err;
02479         }
02480 
02481         // check head blocks for orphans
02482         if (!(0x80000000 & pdir.d.size)) {
02483             // check if we have a parent
02484             lfs_dir_t parent;
02485             lfs_entry_t entry;
02486             int res = lfs_parent(lfs, pdir.d.tail, &parent, &entry);
02487             if (res < 0) {
02488                 return res;
02489             }
02490 
02491             if (!res) {
02492                 // we are an orphan
02493                 LFS_DEBUG("Found orphan %" PRIu32 " %" PRIu32,
02494                         pdir.d.tail[0], pdir.d.tail[1]);
02495 
02496                 pdir.d.tail[0] = cwd.d.tail[0];
02497                 pdir.d.tail[1] = cwd.d.tail[1];
02498 
02499                 err = lfs_dir_commit(lfs, &pdir, NULL, 0);
02500                 if (err) {
02501                     return err;
02502                 }
02503 
02504                 break;
02505             }
02506 
02507             if (!lfs_pairsync(entry.d.u.dir, pdir.d.tail)) {
02508                 // we have desynced
02509                 LFS_DEBUG("Found desync %" PRIu32 " %" PRIu32,
02510                         entry.d.u.dir[0], entry.d.u.dir[1]);
02511 
02512                 pdir.d.tail[0] = entry.d.u.dir[0];
02513                 pdir.d.tail[1] = entry.d.u.dir[1];
02514 
02515                 err = lfs_dir_commit(lfs, &pdir, NULL, 0);
02516                 if (err) {
02517                     return err;
02518                 }
02519 
02520                 break;
02521             }
02522         }
02523 
02524         // check entries for moves
02525         lfs_entry_t entry;
02526         while (true) {
02527             err = lfs_dir_next(lfs, &cwd, &entry);
02528             if (err && err != LFS_ERR_NOENT) {
02529                 return err;
02530             }
02531 
02532             if (err == LFS_ERR_NOENT) {
02533                 break;
02534             }
02535 
02536             // found moved entry
02537             if (entry.d.type & 0x80) {
02538                 int moved = lfs_moved(lfs, &entry.d.u);
02539                 if (moved < 0) {
02540                     return moved;
02541                 }
02542 
02543                 if (moved) {
02544                     LFS_DEBUG("Found move %" PRIu32 " %" PRIu32,
02545                             entry.d.u.dir[0], entry.d.u.dir[1]);
02546                     err = lfs_dir_remove(lfs, &cwd, &entry);
02547                     if (err) {
02548                         return err;
02549                     }
02550                 } else {
02551                     LFS_DEBUG("Found partial move %" PRIu32 " %" PRIu32,
02552                             entry.d.u.dir[0], entry.d.u.dir[1]);
02553                     entry.d.type &= ~0x80;
02554                     err = lfs_dir_update(lfs, &cwd, &entry, NULL);
02555                     if (err) {
02556                         return err;
02557                     }
02558                 }
02559             }
02560         }
02561 
02562         memcpy(&pdir, &cwd, sizeof(pdir));
02563     }
02564 
02565     return 0;
02566 }