lfs.c

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