Kenji Arai / mbed-os_TYBLE16

Dependents:   TYBLE16_simple_data_logger TYBLE16_MP3_Air

Embed: (wiki syntax)

« Back to documentation index

Show/hide line numbers lfs.c Source File

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 (!lfs->moving && 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_drop(lfs, &file->cache);
01377     if ((file->flags & 3) != LFS_O_RDONLY) {
01378         lfs_cache_zero(lfs, &file->cache);
01379     }
01380 
01381     // add to list of files
01382     file->next = lfs->files;
01383     lfs->files = file;
01384 
01385     return 0;
01386 }
01387 
01388 int lfs_file_open(lfs_t *lfs, lfs_file_t *file,
01389         const char *path, int flags) {
01390     return lfs_file_opencfg(lfs, file, path, flags, NULL);
01391 }
01392 
01393 int lfs_file_close(lfs_t *lfs, lfs_file_t *file) {
01394     int err = lfs_file_sync(lfs, file);
01395 
01396     // remove from list of files
01397     for (lfs_file_t **p = &lfs->files; *p; p = &(*p)->next) {
01398         if (*p == file) {
01399             *p = file->next;
01400             break;
01401         }
01402     }
01403 
01404     // clean up memory
01405     if (!(file->cfg && file->cfg->buffer) && !lfs->cfg->file_buffer) {
01406         lfs_free(file->cache.buffer);
01407     }
01408 
01409     return err;
01410 }
01411 
01412 static int lfs_file_relocate(lfs_t *lfs, lfs_file_t *file) {
01413 relocate:
01414     LFS_DEBUG("Bad block at %" PRIu32, file->block);
01415 
01416     // just relocate what exists into new block
01417     lfs_block_t nblock;
01418     int err = lfs_alloc(lfs, &nblock);
01419     if (err) {
01420         return err;
01421     }
01422 
01423     err = lfs_bd_erase(lfs, nblock);
01424     if (err) {
01425         if (err == LFS_ERR_CORRUPT) {
01426             goto relocate;
01427         }
01428         return err;
01429     }
01430 
01431     // either read from dirty cache or disk
01432     for (lfs_off_t i = 0; i < file->off; i++) {
01433         uint8_t data;
01434         err = lfs_cache_read(lfs, &lfs->rcache, &file->cache,
01435                 file->block, i, &data, 1);
01436         if (err) {
01437             return err;
01438         }
01439 
01440         err = lfs_cache_prog(lfs, &lfs->pcache, &lfs->rcache,
01441                 nblock, i, &data, 1);
01442         if (err) {
01443             if (err == LFS_ERR_CORRUPT) {
01444                 goto relocate;
01445             }
01446             return err;
01447         }
01448     }
01449 
01450     // copy over new state of file
01451     memcpy(file->cache.buffer, lfs->pcache.buffer, lfs->cfg->prog_size);
01452     file->cache.block = lfs->pcache.block;
01453     file->cache.off = lfs->pcache.off;
01454     lfs_cache_zero(lfs, &lfs->pcache);
01455 
01456     file->block = nblock;
01457     return 0;
01458 }
01459 
01460 static int lfs_file_flush(lfs_t *lfs, lfs_file_t *file) {
01461     if (file->flags & LFS_F_READING) {
01462         // just drop read cache
01463         lfs_cache_drop(lfs, &file->cache);
01464         file->flags &= ~LFS_F_READING;
01465     }
01466 
01467     if (file->flags & LFS_F_WRITING) {
01468         lfs_off_t pos = file->pos;
01469 
01470         // copy over anything after current branch
01471         lfs_file_t orig = {
01472             .head = file->head,
01473             .size = file->size,
01474             .flags = LFS_O_RDONLY,
01475             .pos = file->pos,
01476             .cache = lfs->rcache,
01477         };
01478         lfs_cache_drop(lfs, &lfs->rcache);
01479 
01480         while (file->pos < file->size) {
01481             // copy over a byte at a time, leave it up to caching
01482             // to make this efficient
01483             uint8_t data;
01484             lfs_ssize_t res = lfs_file_read(lfs, &orig, &data, 1);
01485             if (res < 0) {
01486                 return res;
01487             }
01488 
01489             res = lfs_file_write(lfs, file, &data, 1);
01490             if (res < 0) {
01491                 return res;
01492             }
01493 
01494             // keep our reference to the rcache in sync
01495             if (lfs->rcache.block != 0xffffffff) {
01496                 lfs_cache_drop(lfs, &orig.cache);
01497                 lfs_cache_drop(lfs, &lfs->rcache);
01498             }
01499         }
01500 
01501         // write out what we have
01502         while (true) {
01503             int err = lfs_cache_flush(lfs, &file->cache, &lfs->rcache);
01504             if (err) {
01505                 if (err == LFS_ERR_CORRUPT) {
01506                     goto relocate;
01507                 }
01508                 return err;
01509             }
01510 
01511             break;
01512 relocate:
01513             err = lfs_file_relocate(lfs, file);
01514             if (err) {
01515                 return err;
01516             }
01517         }
01518 
01519         // actual file updates
01520         file->head = file->block;
01521         file->size = file->pos;
01522         file->flags &= ~LFS_F_WRITING;
01523         file->flags |= LFS_F_DIRTY;
01524 
01525         file->pos = pos;
01526     }
01527 
01528     return 0;
01529 }
01530 
01531 int lfs_file_sync(lfs_t *lfs, lfs_file_t *file) {
01532     int err = lfs_file_flush(lfs, file);
01533     if (err) {
01534         return err;
01535     }
01536 
01537     if ((file->flags & LFS_F_DIRTY) &&
01538             !(file->flags & LFS_F_ERRED) &&
01539             !lfs_pairisnull(file->pair)) {
01540         // update dir entry
01541         lfs_dir_t cwd;
01542         err = lfs_dir_fetch(lfs, &cwd, file->pair);
01543         if (err) {
01544             return err;
01545         }
01546 
01547         lfs_entry_t entry = {.off = file->poff};
01548         err = lfs_bd_read(lfs, cwd.pair[0], entry.off,
01549                 &entry.d, sizeof(entry.d));
01550         lfs_entry_fromle32(&entry.d);
01551         if (err) {
01552             return err;
01553         }
01554 
01555         LFS_ASSERT(entry.d.type == LFS_TYPE_REG);
01556         entry.d.u.file.head = file->head;
01557         entry.d.u.file.size = file->size;
01558 
01559         err = lfs_dir_update(lfs, &cwd, &entry, NULL);
01560         if (err) {
01561             return err;
01562         }
01563 
01564         file->flags &= ~LFS_F_DIRTY;
01565     }
01566 
01567     return 0;
01568 }
01569 
01570 lfs_ssize_t lfs_file_read(lfs_t *lfs, lfs_file_t *file,
01571         void *buffer, lfs_size_t size) {
01572     uint8_t *data = buffer;
01573     lfs_size_t nsize = size;
01574 
01575     if ((file->flags & 3) == LFS_O_WRONLY) {
01576         return LFS_ERR_BADF;
01577     }
01578 
01579     if (file->flags & LFS_F_WRITING) {
01580         // flush out any writes
01581         int err = lfs_file_flush(lfs, file);
01582         if (err) {
01583             return err;
01584         }
01585     }
01586 
01587     if (file->pos >= file->size) {
01588         // eof if past end
01589         return 0;
01590     }
01591 
01592     size = lfs_min(size, file->size - file->pos);
01593     nsize = size;
01594 
01595     while (nsize > 0) {
01596         // check if we need a new block
01597         if (!(file->flags & LFS_F_READING) ||
01598                 file->off == lfs->cfg->block_size) {
01599             int err = lfs_ctz_find(lfs, &file->cache, NULL,
01600                     file->head, file->size,
01601                     file->pos, &file->block, &file->off);
01602             if (err) {
01603                 return err;
01604             }
01605 
01606             file->flags |= LFS_F_READING;
01607         }
01608 
01609         // read as much as we can in current block
01610         lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off);
01611         int err = lfs_cache_read(lfs, &file->cache, NULL,
01612                 file->block, file->off, data, diff);
01613         if (err) {
01614             return err;
01615         }
01616 
01617         file->pos += diff;
01618         file->off += diff;
01619         data += diff;
01620         nsize -= diff;
01621     }
01622 
01623     return size;
01624 }
01625 
01626 lfs_ssize_t lfs_file_write(lfs_t *lfs, lfs_file_t *file,
01627         const void *buffer, lfs_size_t size) {
01628     const uint8_t *data = buffer;
01629     lfs_size_t nsize = size;
01630 
01631     if ((file->flags & 3) == LFS_O_RDONLY) {
01632         return LFS_ERR_BADF;
01633     }
01634 
01635     if (file->flags & LFS_F_READING) {
01636         // drop any reads
01637         int err = lfs_file_flush(lfs, file);
01638         if (err) {
01639             return err;
01640         }
01641     }
01642 
01643     if ((file->flags & LFS_O_APPEND) && file->pos < file->size) {
01644         file->pos = file->size;
01645     }
01646 
01647     if (file->pos + size > LFS_FILE_MAX) {
01648         // larger than file limit?
01649         return LFS_ERR_FBIG;
01650     }
01651 
01652     if (!(file->flags & LFS_F_WRITING) && file->pos > file->size) {
01653         // fill with zeros
01654         lfs_off_t pos = file->pos;
01655         file->pos = file->size;
01656 
01657         while (file->pos < pos) {
01658             lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1);
01659             if (res < 0) {
01660                 return res;
01661             }
01662         }
01663     }
01664 
01665     while (nsize > 0) {
01666         // check if we need a new block
01667         if (!(file->flags & LFS_F_WRITING) ||
01668                 file->off == lfs->cfg->block_size) {
01669             if (!(file->flags & LFS_F_WRITING) && file->pos > 0) {
01670                 // find out which block we're extending from
01671                 int err = lfs_ctz_find(lfs, &file->cache, NULL,
01672                         file->head, file->size,
01673                         file->pos-1, &file->block, &file->off);
01674                 if (err) {
01675                     file->flags |= LFS_F_ERRED;
01676                     return err;
01677                 }
01678 
01679                 // mark cache as dirty since we may have read data into it
01680                 lfs_cache_zero(lfs, &file->cache);
01681             }
01682 
01683             // extend file with new blocks
01684             lfs_alloc_ack(lfs);
01685             int err = lfs_ctz_extend(lfs, &lfs->rcache, &file->cache,
01686                     file->block, file->pos,
01687                     &file->block, &file->off);
01688             if (err) {
01689                 file->flags |= LFS_F_ERRED;
01690                 return err;
01691             }
01692 
01693             file->flags |= LFS_F_WRITING;
01694         }
01695 
01696         // program as much as we can in current block
01697         lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off);
01698         while (true) {
01699             int err = lfs_cache_prog(lfs, &file->cache, &lfs->rcache,
01700                     file->block, file->off, data, diff);
01701             if (err) {
01702                 if (err == LFS_ERR_CORRUPT) {
01703                     goto relocate;
01704                 }
01705                 file->flags |= LFS_F_ERRED;
01706                 return err;
01707             }
01708 
01709             break;
01710 relocate:
01711             err = lfs_file_relocate(lfs, file);
01712             if (err) {
01713                 file->flags |= LFS_F_ERRED;
01714                 return err;
01715             }
01716         }
01717 
01718         file->pos += diff;
01719         file->off += diff;
01720         data += diff;
01721         nsize -= diff;
01722 
01723         lfs_alloc_ack(lfs);
01724     }
01725 
01726     file->flags &= ~LFS_F_ERRED;
01727     return size;
01728 }
01729 
01730 lfs_soff_t lfs_file_seek(lfs_t *lfs, lfs_file_t *file,
01731         lfs_soff_t off, int whence) {
01732     // write out everything beforehand, may be noop if rdonly
01733     int err = lfs_file_flush(lfs, file);
01734     if (err) {
01735         return err;
01736     }
01737 
01738     // find new pos
01739     lfs_soff_t npos = file->pos;
01740     if (whence == LFS_SEEK_SET) {
01741         npos = off;
01742     } else if (whence == LFS_SEEK_CUR) {
01743         npos = file->pos + off;
01744     } else if (whence == LFS_SEEK_END) {
01745         npos = file->size + off;
01746     }
01747 
01748     if (npos < 0 || npos > LFS_FILE_MAX) {
01749         // file position out of range
01750         return LFS_ERR_INVAL;
01751     }
01752 
01753     // update pos
01754     file->pos = npos;
01755     return npos;
01756 }
01757 
01758 int lfs_file_truncate(lfs_t *lfs, lfs_file_t *file, lfs_off_t size) {
01759     if ((file->flags & 3) == LFS_O_RDONLY) {
01760         return LFS_ERR_BADF;
01761     }
01762 
01763     lfs_off_t oldsize = lfs_file_size(lfs, file);
01764     if (size < oldsize) {
01765         // need to flush since directly changing metadata
01766         int err = lfs_file_flush(lfs, file);
01767         if (err) {
01768             return err;
01769         }
01770 
01771         // lookup new head in ctz skip list
01772         err = lfs_ctz_find(lfs, &file->cache, NULL,
01773                 file->head, file->size,
01774                 size, &file->head, &(lfs_off_t){0});
01775         if (err) {
01776             return err;
01777         }
01778 
01779         file->size = size;
01780         file->flags |= LFS_F_DIRTY;
01781     } else if (size > oldsize) {
01782         lfs_off_t pos = file->pos;
01783 
01784         // flush+seek if not already at end
01785         if (file->pos != oldsize) {
01786             int err = lfs_file_seek(lfs, file, 0, LFS_SEEK_END);
01787             if (err < 0) {
01788                 return err;
01789             }
01790         }
01791 
01792         // fill with zeros
01793         while (file->pos < size) {
01794             lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1);
01795             if (res < 0) {
01796                 return res;
01797             }
01798         }
01799 
01800         // restore pos
01801         int err = lfs_file_seek(lfs, file, pos, LFS_SEEK_SET);
01802         if (err < 0) {
01803             return err;
01804         }
01805     }
01806 
01807     return 0;
01808 }
01809 
01810 lfs_soff_t lfs_file_tell(lfs_t *lfs, lfs_file_t *file) {
01811     (void)lfs;
01812     return file->pos;
01813 }
01814 
01815 int lfs_file_rewind(lfs_t *lfs, lfs_file_t *file) {
01816     lfs_soff_t res = lfs_file_seek(lfs, file, 0, LFS_SEEK_SET);
01817     if (res < 0) {
01818         return res;
01819     }
01820 
01821     return 0;
01822 }
01823 
01824 lfs_soff_t lfs_file_size(lfs_t *lfs, lfs_file_t *file) {
01825     (void)lfs;
01826     if (file->flags & LFS_F_WRITING) {
01827         return lfs_max(file->pos, file->size);
01828     } else {
01829         return file->size;
01830     }
01831 }
01832 
01833 
01834 /// General fs operations ///
01835 int lfs_stat(lfs_t *lfs, const char *path, struct lfs_info *info) {
01836     lfs_dir_t cwd;
01837     lfs_entry_t entry;
01838     int err = lfs_dir_find(lfs, &cwd, &entry, &path);
01839     if (err) {
01840         return err;
01841     }
01842 
01843     memset(info, 0, sizeof(*info));
01844     info->type = entry.d.type;
01845     if (info->type == LFS_TYPE_REG) {
01846         info->size = entry.d.u.file.size;
01847     }
01848 
01849     if (lfs_paircmp(entry.d.u.dir, lfs->root) == 0) {
01850         strcpy(info->name, "/");
01851     } else {
01852         err = lfs_bd_read(lfs, cwd.pair[0],
01853                 entry.off + 4+entry.d.elen+entry.d.alen,
01854                 info->name, entry.d.nlen);
01855         if (err) {
01856             return err;
01857         }
01858     }
01859 
01860     return 0;
01861 }
01862 
01863 int lfs_remove(lfs_t *lfs, const char *path) {
01864     // deorphan if we haven't yet, needed at most once after poweron
01865     if (!lfs->deorphaned) {
01866         int err = lfs_deorphan(lfs);
01867         if (err) {
01868             return err;
01869         }
01870     }
01871 
01872     lfs_dir_t cwd;
01873     lfs_entry_t entry;
01874     int err = lfs_dir_find(lfs, &cwd, &entry, &path);
01875     if (err) {
01876         return err;
01877     }
01878 
01879     lfs_dir_t dir;
01880     if (entry.d.type == LFS_TYPE_DIR) {
01881         // must be empty before removal, checking size
01882         // without masking top bit checks for any case where
01883         // dir is not empty
01884         err = lfs_dir_fetch(lfs, &dir, entry.d.u.dir);
01885         if (err) {
01886             return err;
01887         } else if (dir.d.size != sizeof(dir.d)+4) {
01888             return LFS_ERR_NOTEMPTY;
01889         }
01890     }
01891 
01892     // remove the entry
01893     err = lfs_dir_remove(lfs, &cwd, &entry);
01894     if (err) {
01895         return err;
01896     }
01897 
01898     // if we were a directory, find pred, replace tail
01899     if (entry.d.type == LFS_TYPE_DIR) {
01900         int res = lfs_pred(lfs, dir.pair, &cwd);
01901         if (res < 0) {
01902             return res;
01903         }
01904 
01905         LFS_ASSERT(res); // must have pred
01906         cwd.d.tail[0] = dir.d.tail[0];
01907         cwd.d.tail[1] = dir.d.tail[1];
01908 
01909         err = lfs_dir_commit(lfs, &cwd, NULL, 0);
01910         if (err) {
01911             return err;
01912         }
01913     }
01914 
01915     return 0;
01916 }
01917 
01918 int lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath) {
01919     // deorphan if we haven't yet, needed at most once after poweron
01920     if (!lfs->deorphaned) {
01921         int err = lfs_deorphan(lfs);
01922         if (err) {
01923             return err;
01924         }
01925     }
01926 
01927     // find old entry
01928     lfs_dir_t oldcwd;
01929     lfs_entry_t oldentry;
01930     int err = lfs_dir_find(lfs, &oldcwd, &oldentry, &(const char *){oldpath});
01931     if (err) {
01932         return err;
01933     }
01934 
01935     // mark as moving
01936     oldentry.d.type |= 0x80;
01937     err = lfs_dir_update(lfs, &oldcwd, &oldentry, NULL);
01938     if (err) {
01939         return err;
01940     }
01941 
01942     // allocate new entry
01943     lfs_dir_t newcwd;
01944     lfs_entry_t preventry;
01945     err = lfs_dir_find(lfs, &newcwd, &preventry, &newpath);
01946     if (err && (err != LFS_ERR_NOENT || strchr(newpath, '/') != NULL)) {
01947         return err;
01948     }
01949 
01950     // must have same type
01951     bool prevexists = (err != LFS_ERR_NOENT);
01952     if (prevexists && preventry.d.type != (0x7f & oldentry.d.type)) {
01953         return LFS_ERR_ISDIR;
01954     }
01955 
01956     lfs_dir_t dir;
01957     if (prevexists && preventry.d.type == LFS_TYPE_DIR) {
01958         // must be empty before removal, checking size
01959         // without masking top bit checks for any case where
01960         // dir is not empty
01961         err = lfs_dir_fetch(lfs, &dir, preventry.d.u.dir);
01962         if (err) {
01963             return err;
01964         } else if (dir.d.size != sizeof(dir.d)+4) {
01965             return LFS_ERR_NOTEMPTY;
01966         }
01967     }
01968 
01969     // move to new location
01970     lfs_entry_t newentry = preventry;
01971     newentry.d = oldentry.d;
01972     newentry.d.type &= ~0x80;
01973     newentry.d.nlen = strlen(newpath);
01974 
01975     if (prevexists) {
01976         err = lfs_dir_update(lfs, &newcwd, &newentry, newpath);
01977         if (err) {
01978             return err;
01979         }
01980     } else {
01981         err = lfs_dir_append(lfs, &newcwd, &newentry, newpath);
01982         if (err) {
01983             return err;
01984         }
01985     }
01986 
01987     // fetch old pair again in case dir block changed
01988     lfs->moving = true;
01989     err = lfs_dir_find(lfs, &oldcwd, &oldentry, &oldpath);
01990     if (err) {
01991         return err;
01992     }
01993     lfs->moving = false;
01994 
01995     // remove old entry
01996     err = lfs_dir_remove(lfs, &oldcwd, &oldentry);
01997     if (err) {
01998         return err;
01999     }
02000 
02001     // if we were a directory, find pred, replace tail
02002     if (prevexists && preventry.d.type == LFS_TYPE_DIR) {
02003         int res = lfs_pred(lfs, dir.pair, &newcwd);
02004         if (res < 0) {
02005             return res;
02006         }
02007 
02008         LFS_ASSERT(res); // must have pred
02009         newcwd.d.tail[0] = dir.d.tail[0];
02010         newcwd.d.tail[1] = dir.d.tail[1];
02011 
02012         err = lfs_dir_commit(lfs, &newcwd, NULL, 0);
02013         if (err) {
02014             return err;
02015         }
02016     }
02017 
02018     return 0;
02019 }
02020 
02021 
02022 /// Filesystem operations ///
02023 static void lfs_deinit(lfs_t *lfs) {
02024     // free allocated memory
02025     if (!lfs->cfg->read_buffer) {
02026         lfs_free(lfs->rcache.buffer);
02027     }
02028 
02029     if (!lfs->cfg->prog_buffer) {
02030         lfs_free(lfs->pcache.buffer);
02031     }
02032 
02033     if (!lfs->cfg->lookahead_buffer) {
02034         lfs_free(lfs->free.buffer);
02035     }
02036 }
02037 
02038 static int lfs_init(lfs_t *lfs, const struct lfs_config *cfg) {
02039     lfs->cfg = cfg;
02040 
02041     // setup read cache
02042     if (lfs->cfg->read_buffer) {
02043         lfs->rcache.buffer = lfs->cfg->read_buffer;
02044     } else {
02045         lfs->rcache.buffer = lfs_malloc(lfs->cfg->read_size);
02046         if (!lfs->rcache.buffer) {
02047             goto cleanup;
02048         }
02049     }
02050 
02051     // setup program cache
02052     if (lfs->cfg->prog_buffer) {
02053         lfs->pcache.buffer = lfs->cfg->prog_buffer;
02054     } else {
02055         lfs->pcache.buffer = lfs_malloc(lfs->cfg->prog_size);
02056         if (!lfs->pcache.buffer) {
02057             goto cleanup;
02058         }
02059     }
02060 
02061     // zero to avoid information leaks
02062     lfs_cache_zero(lfs, &lfs->pcache);
02063     lfs_cache_drop(lfs, &lfs->rcache);
02064 
02065     // setup lookahead, round down to nearest 32-bits
02066     LFS_ASSERT(lfs->cfg->lookahead % 32 == 0);
02067     LFS_ASSERT(lfs->cfg->lookahead > 0);
02068     if (lfs->cfg->lookahead_buffer) {
02069         lfs->free.buffer = lfs->cfg->lookahead_buffer;
02070     } else {
02071         lfs->free.buffer = lfs_malloc(lfs->cfg->lookahead/8);
02072         if (!lfs->free.buffer) {
02073             goto cleanup;
02074         }
02075     }
02076 
02077     // check that program and read sizes are multiples of the block size
02078     LFS_ASSERT(lfs->cfg->prog_size % lfs->cfg->read_size == 0);
02079     LFS_ASSERT(lfs->cfg->block_size % lfs->cfg->prog_size == 0);
02080 
02081     // check that the block size is large enough to fit ctz pointers
02082     LFS_ASSERT(4*lfs_npw2(0xffffffff / (lfs->cfg->block_size-2*4))
02083             <= lfs->cfg->block_size);
02084 
02085     // setup default state
02086     lfs->root[0] = 0xffffffff;
02087     lfs->root[1] = 0xffffffff;
02088     lfs->files = NULL;
02089     lfs->dirs = NULL;
02090     lfs->deorphaned = false;
02091     lfs->moving = false;
02092 
02093     return 0;
02094 
02095 cleanup:
02096     lfs_deinit(lfs);
02097     return LFS_ERR_NOMEM;
02098 }
02099 
02100 int lfs_format(lfs_t *lfs, const struct lfs_config *cfg) {
02101     int err = 0;
02102     if (true) {
02103         err = lfs_init(lfs, cfg);
02104         if (err) {
02105             return err;
02106         }
02107 
02108         // create free lookahead
02109         memset(lfs->free.buffer, 0, lfs->cfg->lookahead/8);
02110         lfs->free.off = 0;
02111         lfs->free.size = lfs_min(lfs->cfg->lookahead, lfs->cfg->block_count);
02112         lfs->free.i = 0;
02113         lfs_alloc_ack(lfs);
02114 
02115         // create superblock dir
02116         lfs_dir_t superdir;
02117         err = lfs_dir_alloc(lfs, &superdir);
02118         if (err) {
02119             goto cleanup;
02120         }
02121 
02122         // write root directory
02123         lfs_dir_t root;
02124         err = lfs_dir_alloc(lfs, &root);
02125         if (err) {
02126             goto cleanup;
02127         }
02128 
02129         err = lfs_dir_commit(lfs, &root, NULL, 0);
02130         if (err) {
02131             goto cleanup;
02132         }
02133 
02134         lfs->root[0] = root.pair[0];
02135         lfs->root[1] = root.pair[1];
02136 
02137         // write superblocks
02138         lfs_superblock_t superblock = {
02139             .off = sizeof(superdir.d),
02140             .d.type = LFS_TYPE_SUPERBLOCK,
02141             .d.elen = sizeof(superblock.d) - sizeof(superblock.d.magic) - 4,
02142             .d.nlen = sizeof(superblock.d.magic),
02143             .d.version = LFS_DISK_VERSION,
02144             .d.magic = {"littlefs"},
02145             .d.block_size  = lfs->cfg->block_size,
02146             .d.block_count = lfs->cfg->block_count,
02147             .d.root = {lfs->root[0], lfs->root[1]},
02148         };
02149         superdir.d.tail[0] = root.pair[0];
02150         superdir.d.tail[1] = root.pair[1];
02151         superdir.d.size = sizeof(superdir.d) + sizeof(superblock.d) + 4;
02152 
02153         // write both pairs to be safe
02154         lfs_superblock_tole32(&superblock.d);
02155         bool valid = false;
02156         for (int i = 0; i < 2; i++) {
02157             err = lfs_dir_commit(lfs, &superdir, (struct lfs_region[]){
02158                     {sizeof(superdir.d), sizeof(superblock.d),
02159                      &superblock.d, sizeof(superblock.d)}
02160                 }, 1);
02161             if (err && err != LFS_ERR_CORRUPT) {
02162                 goto cleanup;
02163             }
02164 
02165             valid = valid || !err;
02166         }
02167 
02168         if (!valid) {
02169             err = LFS_ERR_CORRUPT;
02170             goto cleanup;
02171         }
02172 
02173         // sanity check that fetch works
02174         err = lfs_dir_fetch(lfs, &superdir, (const lfs_block_t[2]){0, 1});
02175         if (err) {
02176             goto cleanup;
02177         }
02178 
02179         lfs_alloc_ack(lfs);
02180     }
02181 
02182 cleanup:
02183     lfs_deinit(lfs);
02184     return err;
02185 }
02186 
02187 int lfs_mount(lfs_t *lfs, const struct lfs_config *cfg) {
02188     int err = 0;
02189     if (true) {
02190         err = lfs_init(lfs, cfg);
02191         if (err) {
02192             return err;
02193         }
02194 
02195         // setup free lookahead
02196         lfs->free.off = 0;
02197         lfs->free.size = 0;
02198         lfs->free.i = 0;
02199         lfs_alloc_ack(lfs);
02200 
02201         // load superblock
02202         lfs_dir_t dir;
02203         lfs_superblock_t superblock;
02204         err = lfs_dir_fetch(lfs, &dir, (const lfs_block_t[2]){0, 1});
02205         if (err && err != LFS_ERR_CORRUPT) {
02206             goto cleanup;
02207         }
02208 
02209         if (!err) {
02210             err = lfs_bd_read(lfs, dir.pair[0], sizeof(dir.d),
02211                     &superblock.d, sizeof(superblock.d));
02212             lfs_superblock_fromle32(&superblock.d);
02213             if (err) {
02214                 goto cleanup;
02215             }
02216 
02217             lfs->root[0] = superblock.d.root[0];
02218             lfs->root[1] = superblock.d.root[1];
02219         }
02220 
02221         if (err || memcmp(superblock.d.magic, "littlefs", 8) != 0) {
02222             LFS_ERROR("Invalid superblock at %d %d", 0, 1);
02223             err = LFS_ERR_CORRUPT;
02224             goto cleanup;
02225         }
02226 
02227         uint16_t major_version = (0xffff & (superblock.d.version >> 16));
02228         uint16_t minor_version = (0xffff & (superblock.d.version >>  0));
02229         if ((major_version != LFS_DISK_VERSION_MAJOR ||
02230              minor_version > LFS_DISK_VERSION_MINOR)) {
02231             LFS_ERROR("Invalid version %d.%d", major_version, minor_version);
02232             err = LFS_ERR_INVAL;
02233             goto cleanup;
02234         }
02235 
02236         return 0;
02237     }
02238 
02239 cleanup:
02240 
02241     lfs_deinit(lfs);
02242     return err;
02243 }
02244 
02245 int lfs_unmount(lfs_t *lfs) {
02246     lfs_deinit(lfs);
02247     return 0;
02248 }
02249 
02250 
02251 /// Littlefs specific operations ///
02252 int lfs_traverse(lfs_t *lfs, int (*cb)(void*, lfs_block_t), void *data) {
02253     if (lfs_pairisnull(lfs->root)) {
02254         return 0;
02255     }
02256 
02257     // iterate over metadata pairs
02258     lfs_dir_t dir;
02259     lfs_entry_t entry;
02260     lfs_block_t cwd[2] = {0, 1};
02261 
02262     while (true) {
02263         for (int i = 0; i < 2; i++) {
02264             int err = cb(data, cwd[i]);
02265             if (err) {
02266                 return err;
02267             }
02268         }
02269 
02270         int err = lfs_dir_fetch(lfs, &dir, cwd);
02271         if (err) {
02272             return err;
02273         }
02274 
02275         // iterate over contents
02276         while (dir.off + sizeof(entry.d) <= (0x7fffffff & dir.d.size)-4) {
02277             err = lfs_bd_read(lfs, dir.pair[0], dir.off,
02278                     &entry.d, sizeof(entry.d));
02279             lfs_entry_fromle32(&entry.d);
02280             if (err) {
02281                 return err;
02282             }
02283 
02284             dir.off += lfs_entry_size(&entry);
02285             if ((0x70 & entry.d.type) == (0x70 & LFS_TYPE_REG)) {
02286                 err = lfs_ctz_traverse(lfs, &lfs->rcache, NULL,
02287                         entry.d.u.file.head, entry.d.u.file.size, cb, data);
02288                 if (err) {
02289                     return err;
02290                 }
02291             }
02292         }
02293 
02294         cwd[0] = dir.d.tail[0];
02295         cwd[1] = dir.d.tail[1];
02296 
02297         if (lfs_pairisnull(cwd)) {
02298             break;
02299         }
02300     }
02301 
02302     // iterate over any open files
02303     for (lfs_file_t *f = lfs->files; f; f = f->next) {
02304         if (f->flags & LFS_F_DIRTY) {
02305             int err = lfs_ctz_traverse(lfs, &lfs->rcache, &f->cache,
02306                     f->head, f->size, cb, data);
02307             if (err) {
02308                 return err;
02309             }
02310         }
02311 
02312         if (f->flags & LFS_F_WRITING) {
02313             int err = lfs_ctz_traverse(lfs, &lfs->rcache, &f->cache,
02314                     f->block, f->pos, cb, data);
02315             if (err) {
02316                 return err;
02317             }
02318         }
02319     }
02320 
02321     return 0;
02322 }
02323 
02324 static int lfs_pred(lfs_t *lfs, const lfs_block_t dir[2], lfs_dir_t *pdir) {
02325     if (lfs_pairisnull(lfs->root)) {
02326         return 0;
02327     }
02328 
02329     // iterate over all directory directory entries
02330     int err = lfs_dir_fetch(lfs, pdir, (const lfs_block_t[2]){0, 1});
02331     if (err) {
02332         return err;
02333     }
02334 
02335     while (!lfs_pairisnull(pdir->d.tail)) {
02336         if (lfs_paircmp(pdir->d.tail, dir) == 0) {
02337             return true;
02338         }
02339 
02340         err = lfs_dir_fetch(lfs, pdir, pdir->d.tail);
02341         if (err) {
02342             return err;
02343         }
02344     }
02345 
02346     return false;
02347 }
02348 
02349 static int lfs_parent(lfs_t *lfs, const lfs_block_t dir[2],
02350         lfs_dir_t *parent, lfs_entry_t *entry) {
02351     if (lfs_pairisnull(lfs->root)) {
02352         return 0;
02353     }
02354 
02355     parent->d.tail[0] = 0;
02356     parent->d.tail[1] = 1;
02357 
02358     // iterate over all directory directory entries
02359     while (!lfs_pairisnull(parent->d.tail)) {
02360         int err = lfs_dir_fetch(lfs, parent, parent->d.tail);
02361         if (err) {
02362             return err;
02363         }
02364 
02365         while (true) {
02366             err = lfs_dir_next(lfs, parent, entry);
02367             if (err && err != LFS_ERR_NOENT) {
02368                 return err;
02369             }
02370 
02371             if (err == LFS_ERR_NOENT) {
02372                 break;
02373             }
02374 
02375             if (((0x70 & entry->d.type) == (0x70 & LFS_TYPE_DIR)) &&
02376                  lfs_paircmp(entry->d.u.dir, dir) == 0) {
02377                 return true;
02378             }
02379         }
02380     }
02381 
02382     return false;
02383 }
02384 
02385 static int lfs_moved(lfs_t *lfs, const void *e) {
02386     if (lfs_pairisnull(lfs->root)) {
02387         return 0;
02388     }
02389 
02390     // skip superblock
02391     lfs_dir_t cwd;
02392     int err = lfs_dir_fetch(lfs, &cwd, (const lfs_block_t[2]){0, 1});
02393     if (err) {
02394         return err;
02395     }
02396 
02397     // iterate over all directory directory entries
02398     lfs_entry_t entry;
02399     while (!lfs_pairisnull(cwd.d.tail)) {
02400         err = lfs_dir_fetch(lfs, &cwd, cwd.d.tail);
02401         if (err) {
02402             return err;
02403         }
02404 
02405         while (true) {
02406             err = lfs_dir_next(lfs, &cwd, &entry);
02407             if (err && err != LFS_ERR_NOENT) {
02408                 return err;
02409             }
02410 
02411             if (err == LFS_ERR_NOENT) {
02412                 break;
02413             }
02414 
02415             if (!(0x80 & entry.d.type) &&
02416                  memcmp(&entry.d.u, e, sizeof(entry.d.u)) == 0) {
02417                 return true;
02418             }
02419         }
02420     }
02421 
02422     return false;
02423 }
02424 
02425 static int lfs_relocate(lfs_t *lfs,
02426         const lfs_block_t oldpair[2], const lfs_block_t newpair[2]) {
02427     // find parent
02428     lfs_dir_t parent;
02429     lfs_entry_t entry;
02430     int res = lfs_parent(lfs, oldpair, &parent, &entry);
02431     if (res < 0) {
02432         return res;
02433     }
02434 
02435     if (res) {
02436         // update disk, this creates a desync
02437         entry.d.u.dir[0] = newpair[0];
02438         entry.d.u.dir[1] = newpair[1];
02439 
02440         int err = lfs_dir_update(lfs, &parent, &entry, NULL);
02441         if (err) {
02442             return err;
02443         }
02444 
02445         // update internal root
02446         if (lfs_paircmp(oldpair, lfs->root) == 0) {
02447             LFS_DEBUG("Relocating root %" PRIu32 " %" PRIu32,
02448                     newpair[0], newpair[1]);
02449             lfs->root[0] = newpair[0];
02450             lfs->root[1] = newpair[1];
02451         }
02452 
02453         // clean up bad block, which should now be a desync
02454         return lfs_deorphan(lfs);
02455     }
02456 
02457     // find pred
02458     res = lfs_pred(lfs, oldpair, &parent);
02459     if (res < 0) {
02460         return res;
02461     }
02462 
02463     if (res) {
02464         // just replace bad pair, no desync can occur
02465         parent.d.tail[0] = newpair[0];
02466         parent.d.tail[1] = newpair[1];
02467 
02468         return lfs_dir_commit(lfs, &parent, NULL, 0);
02469     }
02470 
02471     // couldn't find dir, must be new
02472     return 0;
02473 }
02474 
02475 int lfs_deorphan(lfs_t *lfs) {
02476     lfs->deorphaned = true;
02477 
02478     if (lfs_pairisnull(lfs->root)) {
02479         return 0;
02480     }
02481 
02482     lfs_dir_t pdir = {.d.size = 0x80000000};
02483     lfs_dir_t cwd = {.d.tail[0] = 0, .d.tail[1] = 1};
02484 
02485     // iterate over all directory directory entries
02486     for (lfs_size_t i = 0; i < lfs->cfg->block_count; i++) {
02487         if (lfs_pairisnull(cwd.d.tail)) {
02488             return 0;
02489         }
02490 
02491         int err = lfs_dir_fetch(lfs, &cwd, cwd.d.tail);
02492         if (err) {
02493             return err;
02494         }
02495 
02496         // check head blocks for orphans
02497         if (!(0x80000000 & pdir.d.size)) {
02498             // check if we have a parent
02499             lfs_dir_t parent;
02500             lfs_entry_t entry;
02501             int res = lfs_parent(lfs, pdir.d.tail, &parent, &entry);
02502             if (res < 0) {
02503                 return res;
02504             }
02505 
02506             if (!res) {
02507                 // we are an orphan
02508                 LFS_DEBUG("Found orphan %" PRIu32 " %" PRIu32,
02509                         pdir.d.tail[0], pdir.d.tail[1]);
02510 
02511                 pdir.d.tail[0] = cwd.d.tail[0];
02512                 pdir.d.tail[1] = cwd.d.tail[1];
02513 
02514                 err = lfs_dir_commit(lfs, &pdir, NULL, 0);
02515                 if (err) {
02516                     return err;
02517                 }
02518 
02519                 return 0;
02520             }
02521 
02522             if (!lfs_pairsync(entry.d.u.dir, pdir.d.tail)) {
02523                 // we have desynced
02524                 LFS_DEBUG("Found desync %" PRIu32 " %" PRIu32,
02525                         entry.d.u.dir[0], entry.d.u.dir[1]);
02526 
02527                 pdir.d.tail[0] = entry.d.u.dir[0];
02528                 pdir.d.tail[1] = entry.d.u.dir[1];
02529 
02530                 err = lfs_dir_commit(lfs, &pdir, NULL, 0);
02531                 if (err) {
02532                     return err;
02533                 }
02534 
02535                 return 0;
02536             }
02537         }
02538 
02539         // check entries for moves
02540         lfs_entry_t entry;
02541         while (true) {
02542             err = lfs_dir_next(lfs, &cwd, &entry);
02543             if (err && err != LFS_ERR_NOENT) {
02544                 return err;
02545             }
02546 
02547             if (err == LFS_ERR_NOENT) {
02548                 break;
02549             }
02550 
02551             // found moved entry
02552             if (entry.d.type & 0x80) {
02553                 int moved = lfs_moved(lfs, &entry.d.u);
02554                 if (moved < 0) {
02555                     return moved;
02556                 }
02557 
02558                 if (moved) {
02559                     LFS_DEBUG("Found move %" PRIu32 " %" PRIu32,
02560                             entry.d.u.dir[0], entry.d.u.dir[1]);
02561                     err = lfs_dir_remove(lfs, &cwd, &entry);
02562                     if (err) {
02563                         return err;
02564                     }
02565                 } else {
02566                     LFS_DEBUG("Found partial move %" PRIu32 " %" PRIu32,
02567                             entry.d.u.dir[0], entry.d.u.dir[1]);
02568                     entry.d.type &= ~0x80;
02569                     err = lfs_dir_update(lfs, &cwd, &entry, NULL);
02570                     if (err) {
02571                         return err;
02572                     }
02573                 }
02574             }
02575         }
02576 
02577         memcpy(&pdir, &cwd, sizeof(pdir));
02578     }
02579 
02580     // If we reached here, we have more directory pairs than blocks in the
02581     // filesystem... So something must be horribly wrong
02582     return LFS_ERR_CORRUPT;
02583 }