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