Climatcontroll_Main

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

Repository details

Type:	Program
Mbed OS support:	Mbed OS
Created:	13 Apr 2018
Imports:	1
Forks:	0
Commits:	1
Dependents:	0
Dependencies:	1
Followers:	1
Important changes to repositories hosted on mbed.com

lfs.c

Repository toolbox

Repository details

Important Information for this Arm website

Important changes to repositories hosted on mbed.com

lfs.c

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning
