+/rtos

git clone https://git.julia.blue/+/rtos

Vivek MalneediMerge branch 'master' of github.com:EE445M-Sp20/lab-6-vm22967_jbr2558ee4080a

master
150.8 KiB4873 linesraw
1/*
2 * The little filesystem
3 *
4 * Copyright (c) 2017, Arm Limited. All rights reserved.
5 * SPDX-License-Identifier: BSD-3-Clause
6 */
7#include "lfs.h"
8#include "lfs_util.h"
9
10#define LFS_BLOCK_NULL ((lfs_block_t)-1)
11#define LFS_BLOCK_INLINE ((lfs_block_t)-2)
12
13/// Caching block device operations ///
14static inline void lfs_cache_drop(lfs_t* lfs, lfs_cache_t* rcache) {
15    // do not zero, cheaper if cache is readonly or only going to be
16    // written with identical data (during relocates)
17    (void)lfs;
18    rcache->block = LFS_BLOCK_NULL;
19}
20
21static inline void lfs_cache_zero(lfs_t* lfs, lfs_cache_t* pcache) {
22    // zero to avoid information leak
23    memset(pcache->buffer, 0xff, lfs->cfg->cache_size);
24    pcache->block = LFS_BLOCK_NULL;
25}
26
27static int lfs_bd_read(lfs_t* lfs, const lfs_cache_t* pcache,
28                       lfs_cache_t* rcache, lfs_size_t hint, lfs_block_t block,
29                       lfs_off_t off, void* buffer, lfs_size_t size) {
30    uint8_t* data = buffer;
31    if (block >= lfs->cfg->block_count || off + size > lfs->cfg->block_size) {
32        return LFS_ERR_CORRUPT;
33    }
34
35    while (size > 0) {
36        lfs_size_t diff = size;
37
38        if (pcache && block == pcache->block &&
39            off < pcache->off + pcache->size) {
40            if (off >= pcache->off) {
41                // is already in pcache?
42                diff = lfs_min(diff, pcache->size - (off - pcache->off));
43                memcpy(data, &pcache->buffer[off - pcache->off], diff);
44
45                data += diff;
46                off += diff;
47                size -= diff;
48                continue;
49            }
50
51            // pcache takes priority
52            diff = lfs_min(diff, pcache->off - off);
53        }
54
55        if (block == rcache->block && off < rcache->off + rcache->size) {
56            if (off >= rcache->off) {
57                // is already in rcache?
58                diff = lfs_min(diff, rcache->size - (off - rcache->off));
59                memcpy(data, &rcache->buffer[off - rcache->off], diff);
60
61                data += diff;
62                off += diff;
63                size -= diff;
64                continue;
65            }
66
67            // rcache takes priority
68            diff = lfs_min(diff, rcache->off - off);
69        }
70
71        if (size >= hint && off % lfs->cfg->read_size == 0 &&
72            size >= lfs->cfg->read_size) {
73            // bypass cache?
74            diff = lfs_aligndown(diff, lfs->cfg->read_size);
75            int err = lfs->cfg->read(lfs->cfg, block, off, data, diff);
76            if (err) {
77                return err;
78            }
79
80            data += diff;
81            off += diff;
82            size -= diff;
83            continue;
84        }
85
86        // load to cache, first condition can no longer fail
87        LFS_ASSERT(block < lfs->cfg->block_count);
88        rcache->block = block;
89        rcache->off = lfs_aligndown(off, lfs->cfg->read_size);
90        rcache->size =
91            lfs_min(lfs_min(lfs_alignup(off + hint, lfs->cfg->read_size),
92                            lfs->cfg->block_size) -
93                        rcache->off,
94                    lfs->cfg->cache_size);
95        int err = lfs->cfg->read(lfs->cfg, rcache->block, rcache->off,
96                                 rcache->buffer, rcache->size);
97        LFS_ASSERT(err <= 0);
98        if (err) {
99            return err;
100        }
101    }
102
103    return 0;
104}
105
106enum {
107    LFS_CMP_EQ = 0,
108    LFS_CMP_LT = 1,
109    LFS_CMP_GT = 2,
110};
111
112static int lfs_bd_cmp(lfs_t* lfs, const lfs_cache_t* pcache,
113                      lfs_cache_t* rcache, lfs_size_t hint, lfs_block_t block,
114                      lfs_off_t off, const void* buffer, lfs_size_t size) {
115    const uint8_t* data = buffer;
116
117    for (lfs_off_t i = 0; i < size; i++) {
118        uint8_t dat;
119        int err =
120            lfs_bd_read(lfs, pcache, rcache, hint - i, block, off + i, &dat, 1);
121        if (err) {
122            return err;
123        }
124
125        if (dat != data[i]) {
126            return (dat < data[i]) ? LFS_CMP_LT : LFS_CMP_GT;
127        }
128    }
129
130    return LFS_CMP_EQ;
131}
132
133static int lfs_bd_flush(lfs_t* lfs, lfs_cache_t* pcache, lfs_cache_t* rcache,
134                        bool validate) {
135    if (pcache->block != LFS_BLOCK_NULL && pcache->block != LFS_BLOCK_INLINE) {
136        LFS_ASSERT(pcache->block < lfs->cfg->block_count);
137        lfs_size_t diff = lfs_alignup(pcache->size, lfs->cfg->prog_size);
138        int err = lfs->cfg->prog(lfs->cfg, pcache->block, pcache->off,
139                                 pcache->buffer, diff);
140        LFS_ASSERT(err <= 0);
141        if (err) {
142            return err;
143        }
144
145        if (validate) {
146            // check data on disk
147            lfs_cache_drop(lfs, rcache);
148            int res = lfs_bd_cmp(lfs, NULL, rcache, diff, pcache->block,
149                                 pcache->off, pcache->buffer, diff);
150            if (res < 0) {
151                return res;
152            }
153
154            if (res != LFS_CMP_EQ) {
155                return LFS_ERR_CORRUPT;
156            }
157        }
158
159        lfs_cache_zero(lfs, pcache);
160    }
161
162    return 0;
163}
164
165static int lfs_bd_sync(lfs_t* lfs, lfs_cache_t* pcache, lfs_cache_t* rcache,
166                       bool validate) {
167    lfs_cache_drop(lfs, rcache);
168
169    int err = lfs_bd_flush(lfs, pcache, rcache, validate);
170    if (err) {
171        return err;
172    }
173
174    err = lfs->cfg->sync(lfs->cfg);
175    LFS_ASSERT(err <= 0);
176    return err;
177}
178
179static int lfs_bd_prog(lfs_t* lfs, lfs_cache_t* pcache, lfs_cache_t* rcache,
180                       bool validate, lfs_block_t block, lfs_off_t off,
181                       const void* buffer, lfs_size_t size) {
182    const uint8_t* data = buffer;
183    LFS_ASSERT(block == LFS_BLOCK_INLINE || block < lfs->cfg->block_count);
184    LFS_ASSERT(off + size <= lfs->cfg->block_size);
185
186    while (size > 0) {
187        if (block == pcache->block && off >= pcache->off &&
188            off < pcache->off + lfs->cfg->cache_size) {
189            // already fits in pcache?
190            lfs_size_t diff =
191                lfs_min(size, lfs->cfg->cache_size - (off - pcache->off));
192            memcpy(&pcache->buffer[off - pcache->off], data, diff);
193
194            data += diff;
195            off += diff;
196            size -= diff;
197
198            pcache->size = lfs_max(pcache->size, off - pcache->off);
199            if (pcache->size == lfs->cfg->cache_size) {
200                // eagerly flush out pcache if we fill up
201                int err = lfs_bd_flush(lfs, pcache, rcache, validate);
202                if (err) {
203                    return err;
204                }
205            }
206
207            continue;
208        }
209
210        // pcache must have been flushed, either by programming and
211        // entire block or manually flushing the pcache
212        LFS_ASSERT(pcache->block == LFS_BLOCK_NULL);
213
214        // prepare pcache, first condition can no longer fail
215        pcache->block = block;
216        pcache->off = lfs_aligndown(off, lfs->cfg->prog_size);
217        pcache->size = 0;
218    }
219
220    return 0;
221}
222
223static int lfs_bd_erase(lfs_t* lfs, lfs_block_t block) {
224    LFS_ASSERT(block < lfs->cfg->block_count);
225    int err = lfs->cfg->erase(lfs->cfg, block);
226    LFS_ASSERT(err <= 0);
227    return err;
228}
229
230/// Small type-level utilities ///
231// operations on block pairs
232static inline void lfs_pair_swap(lfs_block_t pair[2]) {
233    lfs_block_t t = pair[0];
234    pair[0] = pair[1];
235    pair[1] = t;
236}
237
238static inline bool lfs_pair_isnull(const lfs_block_t pair[2]) {
239    return pair[0] == LFS_BLOCK_NULL || pair[1] == LFS_BLOCK_NULL;
240}
241
242static inline int lfs_pair_cmp(const lfs_block_t paira[2],
243                               const lfs_block_t pairb[2]) {
244    return !(paira[0] == pairb[0] || paira[1] == pairb[1] ||
245             paira[0] == pairb[1] || paira[1] == pairb[0]);
246}
247
248static inline bool lfs_pair_sync(const lfs_block_t paira[2],
249                                 const lfs_block_t pairb[2]) {
250    return (paira[0] == pairb[0] && paira[1] == pairb[1]) ||
251           (paira[0] == pairb[1] && paira[1] == pairb[0]);
252}
253
254static inline void lfs_pair_fromle32(lfs_block_t pair[2]) {
255    pair[0] = lfs_fromle32(pair[0]);
256    pair[1] = lfs_fromle32(pair[1]);
257}
258
259static inline void lfs_pair_tole32(lfs_block_t pair[2]) {
260    pair[0] = lfs_tole32(pair[0]);
261    pair[1] = lfs_tole32(pair[1]);
262}
263
264// operations on 32-bit entry tags
265typedef uint32_t lfs_tag_t;
266typedef int32_t lfs_stag_t;
267
268#define LFS_MKTAG(type, id, size)                                              \
269    (((lfs_tag_t)(type) << 20) | ((lfs_tag_t)(id) << 10) | (lfs_tag_t)(size))
270
271#define LFS_MKTAG_IF(cond, type, id, size)                                     \
272    ((cond) ? LFS_MKTAG(type, id, size) : LFS_MKTAG(LFS_FROM_NOOP, 0, 0))
273
274#define LFS_MKTAG_IF_ELSE(cond, type1, id1, size1, type2, id2, size2)          \
275    ((cond) ? LFS_MKTAG(type1, id1, size1) : LFS_MKTAG(type2, id2, size2))
276
277static inline bool lfs_tag_isvalid(lfs_tag_t tag) {
278    return !(tag & 0x80000000);
279}
280
281static inline bool lfs_tag_isdelete(lfs_tag_t tag) {
282    return ((int32_t)(tag << 22) >> 22) == -1;
283}
284
285static inline uint16_t lfs_tag_type1(lfs_tag_t tag) {
286    return (tag & 0x70000000) >> 20;
287}
288
289static inline uint16_t lfs_tag_type3(lfs_tag_t tag) {
290    return (tag & 0x7ff00000) >> 20;
291}
292
293static inline uint8_t lfs_tag_chunk(lfs_tag_t tag) {
294    return (tag & 0x0ff00000) >> 20;
295}
296
297static inline int8_t lfs_tag_splice(lfs_tag_t tag) {
298    return (int8_t)lfs_tag_chunk(tag);
299}
300
301static inline uint16_t lfs_tag_id(lfs_tag_t tag) {
302    return (tag & 0x000ffc00) >> 10;
303}
304
305static inline lfs_size_t lfs_tag_size(lfs_tag_t tag) {
306    return tag & 0x000003ff;
307}
308
309static inline lfs_size_t lfs_tag_dsize(lfs_tag_t tag) {
310    return sizeof(tag) + lfs_tag_size(tag + lfs_tag_isdelete(tag));
311}
312
313// operations on attributes in attribute lists
314struct lfs_mattr {
315    lfs_tag_t tag;
316    const void* buffer;
317};
318
319struct lfs_diskoff {
320    lfs_block_t block;
321    lfs_off_t off;
322};
323
324#define LFS_MKATTRS(...)                                                       \
325    (struct lfs_mattr[]){__VA_ARGS__},                                         \
326        sizeof((struct lfs_mattr[]){__VA_ARGS__}) / sizeof(struct lfs_mattr)
327
328// operations on global state
329static inline void lfs_gstate_xor(lfs_gstate_t* a, const lfs_gstate_t* b) {
330    for (int i = 0; i < 3; i++) {
331        ((uint32_t*)a)[i] ^= ((const uint32_t*)b)[i];
332    }
333}
334
335static inline bool lfs_gstate_iszero(const lfs_gstate_t* a) {
336    for (int i = 0; i < 3; i++) {
337        if (((uint32_t*)a)[i] != 0) {
338            return false;
339        }
340    }
341    return true;
342}
343
344static inline bool lfs_gstate_hasorphans(const lfs_gstate_t* a) {
345    return lfs_tag_size(a->tag);
346}
347
348static inline uint8_t lfs_gstate_getorphans(const lfs_gstate_t* a) {
349    return lfs_tag_size(a->tag);
350}
351
352static inline bool lfs_gstate_hasmove(const lfs_gstate_t* a) {
353    return lfs_tag_type1(a->tag);
354}
355
356static inline bool lfs_gstate_hasmovehere(const lfs_gstate_t* a,
357                                          const lfs_block_t* pair) {
358    return lfs_tag_type1(a->tag) && lfs_pair_cmp(a->pair, pair) == 0;
359}
360
361static inline void lfs_gstate_fromle32(lfs_gstate_t* a) {
362    a->tag = lfs_fromle32(a->tag);
363    a->pair[0] = lfs_fromle32(a->pair[0]);
364    a->pair[1] = lfs_fromle32(a->pair[1]);
365}
366
367static inline void lfs_gstate_tole32(lfs_gstate_t* a) {
368    a->tag = lfs_tole32(a->tag);
369    a->pair[0] = lfs_tole32(a->pair[0]);
370    a->pair[1] = lfs_tole32(a->pair[1]);
371}
372
373// other endianness operations
374static void lfs_ctz_fromle32(struct lfs_ctz* ctz) {
375    ctz->head = lfs_fromle32(ctz->head);
376    ctz->size = lfs_fromle32(ctz->size);
377}
378
379static void lfs_ctz_tole32(struct lfs_ctz* ctz) {
380    ctz->head = lfs_tole32(ctz->head);
381    ctz->size = lfs_tole32(ctz->size);
382}
383
384static inline void lfs_superblock_fromle32(lfs_superblock_t* superblock) {
385    superblock->version = lfs_fromle32(superblock->version);
386    superblock->block_size = lfs_fromle32(superblock->block_size);
387    superblock->block_count = lfs_fromle32(superblock->block_count);
388    superblock->name_max = lfs_fromle32(superblock->name_max);
389    superblock->file_max = lfs_fromle32(superblock->file_max);
390    superblock->attr_max = lfs_fromle32(superblock->attr_max);
391}
392
393static inline void lfs_superblock_tole32(lfs_superblock_t* superblock) {
394    superblock->version = lfs_tole32(superblock->version);
395    superblock->block_size = lfs_tole32(superblock->block_size);
396    superblock->block_count = lfs_tole32(superblock->block_count);
397    superblock->name_max = lfs_tole32(superblock->name_max);
398    superblock->file_max = lfs_tole32(superblock->file_max);
399    superblock->attr_max = lfs_tole32(superblock->attr_max);
400}
401
402/// Internal operations predeclared here ///
403static int lfs_dir_commit(lfs_t* lfs, lfs_mdir_t* dir,
404                          const struct lfs_mattr* attrs, int attrcount);
405static int lfs_dir_compact(lfs_t* lfs, lfs_mdir_t* dir,
406                           const struct lfs_mattr* attrs, int attrcount,
407                           lfs_mdir_t* source, uint16_t begin, uint16_t end);
408static int lfs_file_outline(lfs_t* lfs, lfs_file_t* file);
409static int lfs_file_flush(lfs_t* lfs, lfs_file_t* file);
410static void lfs_fs_preporphans(lfs_t* lfs, int8_t orphans);
411static void lfs_fs_prepmove(lfs_t* lfs, uint16_t id, const lfs_block_t pair[2]);
412static int lfs_fs_pred(lfs_t* lfs, const lfs_block_t dir[2], lfs_mdir_t* pdir);
413static lfs_stag_t lfs_fs_parent(lfs_t* lfs, const lfs_block_t dir[2],
414                                lfs_mdir_t* parent);
415static int lfs_fs_relocate(lfs_t* lfs, const lfs_block_t oldpair[2],
416                           lfs_block_t newpair[2]);
417int lfs_fs_traverseraw(lfs_t* lfs, int (*cb)(void* data, lfs_block_t block),
418                       void* data, bool includeorphans);
419static int lfs_fs_forceconsistency(lfs_t* lfs);
420static int lfs_deinit(lfs_t* lfs);
421#ifdef LFS_MIGRATE
422static int lfs1_traverse(lfs_t* lfs, int (*cb)(void*, lfs_block_t), void* data);
423#endif
424
425/// Block allocator ///
426static int lfs_alloc_lookahead(void* p, lfs_block_t block) {
427    lfs_t* lfs = (lfs_t*)p;
428    lfs_block_t off = ((block - lfs->free.off) + lfs->cfg->block_count) %
429                      lfs->cfg->block_count;
430
431    if (off < lfs->free.size) {
432        lfs->free.buffer[off / 32] |= 1U << (off % 32);
433    }
434
435    return 0;
436}
437
438static void lfs_alloc_ack(lfs_t* lfs) {
439    lfs->free.ack = lfs->cfg->block_count;
440}
441
442// Invalidate the lookahead buffer. This is done during mounting and
443// failed traversals
444static void lfs_alloc_reset(lfs_t* lfs) {
445    lfs->free.off = lfs->seed % lfs->cfg->block_size;
446    lfs->free.size = 0;
447    lfs->free.i = 0;
448    lfs_alloc_ack(lfs);
449}
450
451static int lfs_alloc(lfs_t* lfs, lfs_block_t* block) {
452    while (true) {
453        while (lfs->free.i != lfs->free.size) {
454            lfs_block_t off = lfs->free.i;
455            lfs->free.i += 1;
456            lfs->free.ack -= 1;
457
458            if (!(lfs->free.buffer[off / 32] & (1U << (off % 32)))) {
459                // found a free block
460                *block = (lfs->free.off + off) % lfs->cfg->block_count;
461
462                // eagerly find next off so an alloc ack can
463                // discredit old lookahead blocks
464                while (lfs->free.i != lfs->free.size &&
465                       (lfs->free.buffer[lfs->free.i / 32] &
466                        (1U << (lfs->free.i % 32)))) {
467                    lfs->free.i += 1;
468                    lfs->free.ack -= 1;
469                }
470
471                return 0;
472            }
473        }
474
475        // check if we have looked at all blocks since last ack
476        if (lfs->free.ack == 0) {
477            LFS_ERROR("No more free space %" PRIu32,
478                      lfs->free.i + lfs->free.off);
479            return LFS_ERR_NOSPC;
480        }
481
482        lfs->free.off =
483            (lfs->free.off + lfs->free.size) % lfs->cfg->block_count;
484        lfs->free.size = lfs_min(8 * lfs->cfg->lookahead_size, lfs->free.ack);
485        lfs->free.i = 0;
486
487        // find mask of free blocks from tree
488        memset(lfs->free.buffer, 0, lfs->cfg->lookahead_size);
489        int err = lfs_fs_traverseraw(lfs, lfs_alloc_lookahead, lfs, true);
490        if (err) {
491            lfs_alloc_reset(lfs);
492            return err;
493        }
494    }
495}
496
497/// Metadata pair and directory operations ///
498static lfs_stag_t lfs_dir_getslice(lfs_t* lfs, const lfs_mdir_t* dir,
499                                   lfs_tag_t gmask, lfs_tag_t gtag,
500                                   lfs_off_t goff, void* gbuffer,
501                                   lfs_size_t gsize) {
502    lfs_off_t off = dir->off;
503    lfs_tag_t ntag = dir->etag;
504    lfs_stag_t gdiff = 0;
505
506    if (lfs_gstate_hasmovehere(&lfs->gdisk, dir->pair) &&
507        lfs_tag_id(gmask) != 0 &&
508        lfs_tag_id(lfs->gdisk.tag) <= lfs_tag_id(gtag)) {
509        // synthetic moves
510        gdiff -= LFS_MKTAG(0, 1, 0);
511    }
512
513    // iterate over dir block backwards (for faster lookups)
514    while (off >= sizeof(lfs_tag_t) + lfs_tag_dsize(ntag)) {
515        off -= lfs_tag_dsize(ntag);
516        lfs_tag_t tag = ntag;
517        int err = lfs_bd_read(lfs, NULL, &lfs->rcache, sizeof(ntag),
518                              dir->pair[0], off, &ntag, sizeof(ntag));
519        if (err) {
520            return err;
521        }
522
523        ntag = (lfs_frombe32(ntag) ^ tag) & 0x7fffffff;
524
525        if (lfs_tag_id(gmask) != 0 && lfs_tag_type1(tag) == LFS_TYPE_SPLICE &&
526            lfs_tag_id(tag) <= lfs_tag_id(gtag - gdiff)) {
527            if (tag == (LFS_MKTAG(LFS_TYPE_CREATE, 0, 0) |
528                        (LFS_MKTAG(0, 0x3ff, 0) & (gtag - gdiff)))) {
529                // found where we were created
530                return LFS_ERR_NOENT;
531            }
532
533            // move around splices
534            gdiff += LFS_MKTAG(0, lfs_tag_splice(tag), 0);
535        }
536
537        if ((gmask & tag) == (gmask & (gtag - gdiff))) {
538            if (lfs_tag_isdelete(tag)) {
539                return LFS_ERR_NOENT;
540            }
541
542            lfs_size_t diff = lfs_min(lfs_tag_size(tag), gsize);
543            err = lfs_bd_read(lfs, NULL, &lfs->rcache, diff, dir->pair[0],
544                              off + sizeof(tag) + goff, gbuffer, diff);
545            if (err) {
546                return err;
547            }
548
549            memset((uint8_t*)gbuffer + diff, 0, gsize - diff);
550
551            return tag + gdiff;
552        }
553    }
554
555    return LFS_ERR_NOENT;
556}
557
558static lfs_stag_t lfs_dir_get(lfs_t* lfs, const lfs_mdir_t* dir,
559                              lfs_tag_t gmask, lfs_tag_t gtag, void* buffer) {
560    return lfs_dir_getslice(lfs, dir, gmask, gtag, 0, buffer,
561                            lfs_tag_size(gtag));
562}
563
564static int lfs_dir_getread(lfs_t* lfs, const lfs_mdir_t* dir,
565                           const lfs_cache_t* pcache, lfs_cache_t* rcache,
566                           lfs_size_t hint, lfs_tag_t gmask, lfs_tag_t gtag,
567                           lfs_off_t off, void* buffer, lfs_size_t size) {
568    uint8_t* data = buffer;
569    if (off + size > lfs->cfg->block_size) {
570        return LFS_ERR_CORRUPT;
571    }
572
573    while (size > 0) {
574        lfs_size_t diff = size;
575
576        if (pcache && pcache->block == LFS_BLOCK_INLINE &&
577            off < pcache->off + pcache->size) {
578            if (off >= pcache->off) {
579                // is already in pcache?
580                diff = lfs_min(diff, pcache->size - (off - pcache->off));
581                memcpy(data, &pcache->buffer[off - pcache->off], diff);
582
583                data += diff;
584                off += diff;
585                size -= diff;
586                continue;
587            }
588
589            // pcache takes priority
590            diff = lfs_min(diff, pcache->off - off);
591        }
592
593        if (rcache->block == LFS_BLOCK_INLINE &&
594            off < rcache->off + rcache->size) {
595            if (off >= rcache->off) {
596                // is already in rcache?
597                diff = lfs_min(diff, rcache->size - (off - rcache->off));
598                memcpy(data, &rcache->buffer[off - rcache->off], diff);
599
600                data += diff;
601                off += diff;
602                size -= diff;
603                continue;
604            }
605
606            // rcache takes priority
607            diff = lfs_min(diff, rcache->off - off);
608        }
609
610        // load to cache, first condition can no longer fail
611        rcache->block = LFS_BLOCK_INLINE;
612        rcache->off = lfs_aligndown(off, lfs->cfg->read_size);
613        rcache->size = lfs_min(lfs_alignup(off + hint, lfs->cfg->read_size),
614                               lfs->cfg->cache_size);
615        int err = lfs_dir_getslice(lfs, dir, gmask, gtag, rcache->off,
616                                   rcache->buffer, rcache->size);
617        if (err < 0) {
618            return err;
619        }
620    }
621
622    return 0;
623}
624
625static int lfs_dir_traverse_filter(void* p, lfs_tag_t tag, const void* buffer) {
626    lfs_tag_t* filtertag = p;
627    (void)buffer;
628
629    // which mask depends on unique bit in tag structure
630    uint32_t mask = (tag & LFS_MKTAG(0x100, 0, 0)) ? LFS_MKTAG(0x7ff, 0x3ff, 0)
631                                                   : LFS_MKTAG(0x700, 0x3ff, 0);
632
633    // check for redundancy
634    if ((mask & tag) == (mask & *filtertag) || lfs_tag_isdelete(*filtertag) ||
635        (LFS_MKTAG(0x7ff, 0x3ff, 0) & tag) ==
636            (LFS_MKTAG(LFS_TYPE_DELETE, 0, 0) |
637             (LFS_MKTAG(0, 0x3ff, 0) & *filtertag))) {
638        return true;
639    }
640
641    // check if we need to adjust for created/deleted tags
642    if (lfs_tag_type1(tag) == LFS_TYPE_SPLICE &&
643        lfs_tag_id(tag) <= lfs_tag_id(*filtertag)) {
644        *filtertag += LFS_MKTAG(0, lfs_tag_splice(tag), 0);
645    }
646
647    return false;
648}
649
650static int lfs_dir_traverse(
651    lfs_t* lfs, const lfs_mdir_t* dir, lfs_off_t off, lfs_tag_t ptag,
652    const struct lfs_mattr* attrs, int attrcount, lfs_tag_t tmask,
653    lfs_tag_t ttag, uint16_t begin, uint16_t end, int16_t diff,
654    int (*cb)(void* data, lfs_tag_t tag, const void* buffer), void* data) {
655    // iterate over directory and attrs
656    while (true) {
657        lfs_tag_t tag;
658        const void* buffer;
659        struct lfs_diskoff disk;
660        if (off + lfs_tag_dsize(ptag) < dir->off) {
661            off += lfs_tag_dsize(ptag);
662            int err = lfs_bd_read(lfs, NULL, &lfs->rcache, sizeof(tag),
663                                  dir->pair[0], off, &tag, sizeof(tag));
664            if (err) {
665                return err;
666            }
667
668            tag = (lfs_frombe32(tag) ^ ptag) | 0x80000000;
669            disk.block = dir->pair[0];
670            disk.off = off + sizeof(lfs_tag_t);
671            buffer = &disk;
672            ptag = tag;
673        } else if (attrcount > 0) {
674            tag = attrs[0].tag;
675            buffer = attrs[0].buffer;
676            attrs += 1;
677            attrcount -= 1;
678        } else {
679            return 0;
680        }
681
682        lfs_tag_t mask = LFS_MKTAG(0x7ff, 0, 0);
683        if ((mask & tmask & tag) != (mask & tmask & ttag)) {
684            continue;
685        }
686
687        // do we need to filter? inlining the filtering logic here allows
688        // for some minor optimizations
689        if (lfs_tag_id(tmask) != 0) {
690            // scan for duplicates and update tag based on creates/deletes
691            int filter =
692                lfs_dir_traverse(lfs, dir, off, ptag, attrs, attrcount, 0, 0, 0,
693                                 0, 0, lfs_dir_traverse_filter, &tag);
694            if (filter < 0) {
695                return filter;
696            }
697
698            if (filter) {
699                continue;
700            }
701
702            // in filter range?
703            if (!(lfs_tag_id(tag) >= begin && lfs_tag_id(tag) < end)) {
704                continue;
705            }
706        }
707
708        // handle special cases for mcu-side operations
709        if (lfs_tag_type3(tag) == LFS_FROM_NOOP) {
710            // do nothing
711        } else if (lfs_tag_type3(tag) == LFS_FROM_MOVE) {
712            uint16_t fromid = lfs_tag_size(tag);
713            uint16_t toid = lfs_tag_id(tag);
714            int err = lfs_dir_traverse(
715                lfs, buffer, 0, 0xffffffff, NULL, 0, LFS_MKTAG(0x600, 0x3ff, 0),
716                LFS_MKTAG(LFS_TYPE_STRUCT, 0, 0), fromid, fromid + 1,
717                toid - fromid + diff, cb, data);
718            if (err) {
719                return err;
720            }
721        } else if (lfs_tag_type3(tag) == LFS_FROM_USERATTRS) {
722            for (unsigned i = 0; i < lfs_tag_size(tag); i++) {
723                const struct lfs_attr* a = buffer;
724                int err = cb(data,
725                             LFS_MKTAG(LFS_TYPE_USERATTR + a[i].type,
726                                       lfs_tag_id(tag) + diff, a[i].size),
727                             a[i].buffer);
728                if (err) {
729                    return err;
730                }
731            }
732        } else {
733            int err = cb(data, tag + LFS_MKTAG(0, diff, 0), buffer);
734            if (err) {
735                return err;
736            }
737        }
738    }
739}
740
741static lfs_stag_t
742lfs_dir_fetchmatch(lfs_t* lfs, lfs_mdir_t* dir, const lfs_block_t pair[2],
743                   lfs_tag_t fmask, lfs_tag_t ftag, uint16_t* id,
744                   int (*cb)(void* data, lfs_tag_t tag, const void* buffer),
745                   void* data) {
746    // we can find tag very efficiently during a fetch, since we're already
747    // scanning the entire directory
748    lfs_stag_t besttag = -1;
749
750    // if either block address is invalid we return LFS_ERR_CORRUPT here,
751    // otherwise later writes to the pair could fail
752    if (pair[0] >= lfs->cfg->block_count || pair[1] >= lfs->cfg->block_count) {
753        return LFS_ERR_CORRUPT;
754    }
755
756    // find the block with the most recent revision
757    uint32_t revs[2] = {0, 0};
758    int r = 0;
759    for (int i = 0; i < 2; i++) {
760        int err = lfs_bd_read(lfs, NULL, &lfs->rcache, sizeof(revs[i]), pair[i],
761                              0, &revs[i], sizeof(revs[i]));
762        revs[i] = lfs_fromle32(revs[i]);
763        if (err && err != LFS_ERR_CORRUPT) {
764            return err;
765        }
766
767        if (err != LFS_ERR_CORRUPT &&
768            lfs_scmp(revs[i], revs[(i + 1) % 2]) > 0) {
769            r = i;
770        }
771    }
772
773    dir->pair[0] = pair[(r + 0) % 2];
774    dir->pair[1] = pair[(r + 1) % 2];
775    dir->rev = revs[(r + 0) % 2];
776    dir->off = 0; // nonzero = found some commits
777
778    // now scan tags to fetch the actual dir and find possible match
779    for (int i = 0; i < 2; i++) {
780        lfs_off_t off = 0;
781        lfs_tag_t ptag = 0xffffffff;
782
783        uint16_t tempcount = 0;
784        lfs_block_t temptail[2] = {LFS_BLOCK_NULL, LFS_BLOCK_NULL};
785        bool tempsplit = false;
786        lfs_stag_t tempbesttag = besttag;
787
788        dir->rev = lfs_tole32(dir->rev);
789        uint32_t crc = lfs_crc(0xffffffff, &dir->rev, sizeof(dir->rev));
790        dir->rev = lfs_fromle32(dir->rev);
791
792        while (true) {
793            // extract next tag
794            lfs_tag_t tag;
795            off += lfs_tag_dsize(ptag);
796            int err = lfs_bd_read(lfs, NULL, &lfs->rcache, lfs->cfg->block_size,
797                                  dir->pair[0], off, &tag, sizeof(tag));
798            if (err) {
799                if (err == LFS_ERR_CORRUPT) {
800                    // can't continue?
801                    dir->erased = false;
802                    break;
803                }
804                return err;
805            }
806
807            crc = lfs_crc(crc, &tag, sizeof(tag));
808            tag = lfs_frombe32(tag) ^ ptag;
809
810            // next commit not yet programmed or we're not in valid range
811            if (!lfs_tag_isvalid(tag)) {
812                dir->erased = (lfs_tag_type1(ptag) == LFS_TYPE_CRC &&
813                               dir->off % lfs->cfg->prog_size == 0);
814                break;
815            } else if (off + lfs_tag_dsize(tag) > lfs->cfg->block_size) {
816                dir->erased = false;
817                break;
818            }
819
820            ptag = tag;
821
822            if (lfs_tag_type1(tag) == LFS_TYPE_CRC) {
823                // check the crc attr
824                uint32_t dcrc;
825                err = lfs_bd_read(lfs, NULL, &lfs->rcache, lfs->cfg->block_size,
826                                  dir->pair[0], off + sizeof(tag), &dcrc,
827                                  sizeof(dcrc));
828                if (err) {
829                    if (err == LFS_ERR_CORRUPT) {
830                        dir->erased = false;
831                        break;
832                    }
833                    return err;
834                }
835                dcrc = lfs_fromle32(dcrc);
836
837                if (crc != dcrc) {
838                    dir->erased = false;
839                    break;
840                }
841
842                // reset the next bit if we need to
843                ptag ^= (lfs_tag_t)(lfs_tag_chunk(tag) & 1U) << 31;
844
845                // toss our crc into the filesystem seed for
846                // pseudorandom numbers
847                lfs->seed ^= crc;
848
849                // update with what's found so far
850                besttag = tempbesttag;
851                dir->off = off + lfs_tag_dsize(tag);
852                dir->etag = ptag;
853                dir->count = tempcount;
854                dir->tail[0] = temptail[0];
855                dir->tail[1] = temptail[1];
856                dir->split = tempsplit;
857
858                // reset crc
859                crc = 0xffffffff;
860                continue;
861            }
862
863            // crc the entry first, hopefully leaving it in the cache
864            for (lfs_off_t j = sizeof(tag); j < lfs_tag_dsize(tag); j++) {
865                uint8_t dat;
866                err = lfs_bd_read(lfs, NULL, &lfs->rcache, lfs->cfg->block_size,
867                                  dir->pair[0], off + j, &dat, 1);
868                if (err) {
869                    if (err == LFS_ERR_CORRUPT) {
870                        dir->erased = false;
871                        break;
872                    }
873                    return err;
874                }
875
876                crc = lfs_crc(crc, &dat, 1);
877            }
878
879            // directory modification tags?
880            if (lfs_tag_type1(tag) == LFS_TYPE_NAME) {
881                // increase count of files if necessary
882                if (lfs_tag_id(tag) >= tempcount) {
883                    tempcount = lfs_tag_id(tag) + 1;
884                }
885            } else if (lfs_tag_type1(tag) == LFS_TYPE_SPLICE) {
886                tempcount += lfs_tag_splice(tag);
887
888                if (tag == (LFS_MKTAG(LFS_TYPE_DELETE, 0, 0) |
889                            (LFS_MKTAG(0, 0x3ff, 0) & tempbesttag))) {
890                    tempbesttag |= 0x80000000;
891                } else if (tempbesttag != -1 &&
892                           lfs_tag_id(tag) <= lfs_tag_id(tempbesttag)) {
893                    tempbesttag += LFS_MKTAG(0, lfs_tag_splice(tag), 0);
894                }
895            } else if (lfs_tag_type1(tag) == LFS_TYPE_TAIL) {
896                tempsplit = (lfs_tag_chunk(tag) & 1);
897
898                err =
899                    lfs_bd_read(lfs, NULL, &lfs->rcache, lfs->cfg->block_size,
900                                dir->pair[0], off + sizeof(tag), &temptail, 8);
901                if (err) {
902                    if (err == LFS_ERR_CORRUPT) {
903                        dir->erased = false;
904                        break;
905                    }
906                }
907                lfs_pair_fromle32(temptail);
908            }
909
910            // found a match for our fetcher?
911            if ((fmask & tag) == (fmask & ftag)) {
912                int res =
913                    cb(data, tag,
914                       &(struct lfs_diskoff){dir->pair[0], off + sizeof(tag)});
915                if (res < 0) {
916                    if (res == LFS_ERR_CORRUPT) {
917                        dir->erased = false;
918                        break;
919                    }
920                    return res;
921                }
922
923                if (res == LFS_CMP_EQ) {
924                    // found a match
925                    tempbesttag = tag;
926                } else if ((LFS_MKTAG(0x7ff, 0x3ff, 0) & tag) ==
927                           (LFS_MKTAG(0x7ff, 0x3ff, 0) & tempbesttag)) {
928                    // found an identical tag, but contents didn't match
929                    // this must mean that our besttag has been overwritten
930                    tempbesttag = -1;
931                } else if (res == LFS_CMP_GT &&
932                           lfs_tag_id(tag) <= lfs_tag_id(tempbesttag)) {
933                    // found a greater match, keep track to keep things sorted
934                    tempbesttag = tag | 0x80000000;
935                }
936            }
937        }
938
939        // consider what we have good enough
940        if (dir->off > 0) {
941            // synthetic move
942            if (lfs_gstate_hasmovehere(&lfs->gdisk, dir->pair)) {
943                if (lfs_tag_id(lfs->gdisk.tag) == lfs_tag_id(besttag)) {
944                    besttag |= 0x80000000;
945                } else if (besttag != -1 &&
946                           lfs_tag_id(lfs->gdisk.tag) < lfs_tag_id(besttag)) {
947                    besttag -= LFS_MKTAG(0, 1, 0);
948                }
949            }
950
951            // found tag? or found best id?
952            if (id) {
953                *id = lfs_min(lfs_tag_id(besttag), dir->count);
954            }
955
956            if (lfs_tag_isvalid(besttag)) {
957                return besttag;
958            } else if (lfs_tag_id(besttag) < dir->count) {
959                return LFS_ERR_NOENT;
960            } else {
961                return 0;
962            }
963        }
964
965        // failed, try the other block?
966        lfs_pair_swap(dir->pair);
967        dir->rev = revs[(r + 1) % 2];
968    }
969
970    LFS_ERROR("Corrupted dir pair at {0x%" PRIx32 ", 0x%" PRIx32 "}",
971              dir->pair[0], dir->pair[1]);
972    return LFS_ERR_CORRUPT;
973}
974
975static int lfs_dir_fetch(lfs_t* lfs, lfs_mdir_t* dir,
976                         const lfs_block_t pair[2]) {
977    // note, mask=-1, tag=-1 can never match a tag since this
978    // pattern has the invalid bit set
979    return (int)lfs_dir_fetchmatch(lfs, dir, pair, (lfs_tag_t)-1, (lfs_tag_t)-1,
980                                   NULL, NULL, NULL);
981}
982
983static int lfs_dir_getgstate(lfs_t* lfs, const lfs_mdir_t* dir,
984                             lfs_gstate_t* gstate) {
985    lfs_gstate_t temp;
986    lfs_stag_t res =
987        lfs_dir_get(lfs, dir, LFS_MKTAG(0x7ff, 0, 0),
988                    LFS_MKTAG(LFS_TYPE_MOVESTATE, 0, sizeof(temp)), &temp);
989    if (res < 0 && res != LFS_ERR_NOENT) {
990        return res;
991    }
992
993    if (res != LFS_ERR_NOENT) {
994        // xor together to find resulting gstate
995        lfs_gstate_fromle32(&temp);
996        lfs_gstate_xor(gstate, &temp);
997    }
998
999    return 0;
1000}
1001
1002static int lfs_dir_getinfo(lfs_t* lfs, lfs_mdir_t* dir, uint16_t id,
1003                           struct lfs_info* info) {
1004    if (id == 0x3ff) {
1005        // special case for root
1006        strcpy(info->name, "/");
1007        info->type = LFS_TYPE_DIR;
1008        return 0;
1009    }
1010
1011    lfs_stag_t tag = lfs_dir_get(
1012        lfs, dir, LFS_MKTAG(0x780, 0x3ff, 0),
1013        LFS_MKTAG(LFS_TYPE_NAME, id, lfs->name_max + 1), info->name);
1014    if (tag < 0) {
1015        return (int)tag;
1016    }
1017
1018    info->type = lfs_tag_type3(tag);
1019
1020    struct lfs_ctz ctz;
1021    tag = lfs_dir_get(lfs, dir, LFS_MKTAG(0x700, 0x3ff, 0),
1022                      LFS_MKTAG(LFS_TYPE_STRUCT, id, sizeof(ctz)), &ctz);
1023    if (tag < 0) {
1024        return (int)tag;
1025    }
1026    lfs_ctz_fromle32(&ctz);
1027
1028    if (lfs_tag_type3(tag) == LFS_TYPE_CTZSTRUCT) {
1029        info->size = ctz.size;
1030    } else if (lfs_tag_type3(tag) == LFS_TYPE_INLINESTRUCT) {
1031        info->size = lfs_tag_size(tag);
1032    }
1033
1034    return 0;
1035}
1036
1037struct lfs_dir_find_match {
1038    lfs_t* lfs;
1039    const void* name;
1040    lfs_size_t size;
1041};
1042
1043static int lfs_dir_find_match(void* data, lfs_tag_t tag, const void* buffer) {
1044    struct lfs_dir_find_match* name = data;
1045    lfs_t* lfs = name->lfs;
1046    const struct lfs_diskoff* disk = buffer;
1047
1048    // compare with disk
1049    lfs_size_t diff = lfs_min(name->size, lfs_tag_size(tag));
1050    int res = lfs_bd_cmp(lfs, NULL, &lfs->rcache, diff, disk->block, disk->off,
1051                         name->name, diff);
1052    if (res != LFS_CMP_EQ) {
1053        return res;
1054    }
1055
1056    // only equal if our size is still the same
1057    if (name->size != lfs_tag_size(tag)) {
1058        return (name->size < lfs_tag_size(tag)) ? LFS_CMP_LT : LFS_CMP_GT;
1059    }
1060
1061    // found a match!
1062    return LFS_CMP_EQ;
1063}
1064
1065static lfs_stag_t lfs_dir_find(lfs_t* lfs, lfs_mdir_t* dir, const char** path,
1066                               uint16_t* id) {
1067    // we reduce path to a single name if we can find it
1068    const char* name = *path;
1069    if (id) {
1070        *id = 0x3ff;
1071    }
1072
1073    // default to root dir
1074    lfs_stag_t tag = LFS_MKTAG(LFS_TYPE_DIR, 0x3ff, 0);
1075    dir->tail[0] = lfs->root[0];
1076    dir->tail[1] = lfs->root[1];
1077
1078    while (true) {
1079    nextname:
1080        // skip slashes
1081        name += strspn(name, "/");
1082        lfs_size_t namelen = strcspn(name, "/");
1083
1084        // skip '.' and root '..'
1085        if ((namelen == 1 && memcmp(name, ".", 1) == 0) ||
1086            (namelen == 2 && memcmp(name, "..", 2) == 0)) {
1087            name += namelen;
1088            goto nextname;
1089        }
1090
1091        // skip if matched by '..' in name
1092        const char* suffix = name + namelen;
1093        lfs_size_t sufflen;
1094        int depth = 1;
1095        while (true) {
1096            suffix += strspn(suffix, "/");
1097            sufflen = strcspn(suffix, "/");
1098            if (sufflen == 0) {
1099                break;
1100            }
1101
1102            if (sufflen == 2 && memcmp(suffix, "..", 2) == 0) {
1103                depth -= 1;
1104                if (depth == 0) {
1105                    name = suffix + sufflen;
1106                    goto nextname;
1107                }
1108            } else {
1109                depth += 1;
1110            }
1111
1112            suffix += sufflen;
1113        }
1114
1115        // found path
1116        if (name[0] == '\0') {
1117            return tag;
1118        }
1119
1120        // update what we've found so far
1121        *path = name;
1122
1123        // only continue if we hit a directory
1124        if (lfs_tag_type3(tag) != LFS_TYPE_DIR) {
1125            return LFS_ERR_NOTDIR;
1126        }
1127
1128        // grab the entry data
1129        if (lfs_tag_id(tag) != 0x3ff) {
1130            lfs_stag_t res = lfs_dir_get(
1131                lfs, dir, LFS_MKTAG(0x700, 0x3ff, 0),
1132                LFS_MKTAG(LFS_TYPE_STRUCT, lfs_tag_id(tag), 8), dir->tail);
1133            if (res < 0) {
1134                return res;
1135            }
1136            lfs_pair_fromle32(dir->tail);
1137        }
1138
1139        // find entry matching name
1140        while (true) {
1141            tag = lfs_dir_fetchmatch(
1142                lfs, dir, dir->tail, LFS_MKTAG(0x780, 0, 0),
1143                LFS_MKTAG(LFS_TYPE_NAME, 0, namelen),
1144                // are we last name?
1145                (strchr(name, '/') == NULL) ? id : NULL, lfs_dir_find_match,
1146                &(struct lfs_dir_find_match){lfs, name, namelen});
1147            if (tag < 0) {
1148                return tag;
1149            }
1150
1151            if (tag) {
1152                break;
1153            }
1154
1155            if (!dir->split) {
1156                return LFS_ERR_NOENT;
1157            }
1158        }
1159
1160        // to next name
1161        name += namelen;
1162    }
1163}
1164
1165// commit logic
1166struct lfs_commit {
1167    lfs_block_t block;
1168    lfs_off_t off;
1169    lfs_tag_t ptag;
1170    uint32_t crc;
1171
1172    lfs_off_t begin;
1173    lfs_off_t end;
1174};
1175
1176static int lfs_dir_commitprog(lfs_t* lfs, struct lfs_commit* commit,
1177                              const void* buffer, lfs_size_t size) {
1178    int err = lfs_bd_prog(lfs, &lfs->pcache, &lfs->rcache, false, commit->block,
1179                          commit->off, (const uint8_t*)buffer, size);
1180    if (err) {
1181        return err;
1182    }
1183
1184    commit->crc = lfs_crc(commit->crc, buffer, size);
1185    commit->off += size;
1186    return 0;
1187}
1188
1189static int lfs_dir_commitattr(lfs_t* lfs, struct lfs_commit* commit,
1190                              lfs_tag_t tag, const void* buffer) {
1191    // check if we fit
1192    lfs_size_t dsize = lfs_tag_dsize(tag);
1193    if (commit->off + dsize > commit->end) {
1194        return LFS_ERR_NOSPC;
1195    }
1196
1197    // write out tag
1198    lfs_tag_t ntag = lfs_tobe32((tag & 0x7fffffff) ^ commit->ptag);
1199    int err = lfs_dir_commitprog(lfs, commit, &ntag, sizeof(ntag));
1200    if (err) {
1201        return err;
1202    }
1203
1204    if (!(tag & 0x80000000)) {
1205        // from memory
1206        err = lfs_dir_commitprog(lfs, commit, buffer, dsize - sizeof(tag));
1207        if (err) {
1208            return err;
1209        }
1210    } else {
1211        // from disk
1212        const struct lfs_diskoff* disk = buffer;
1213        for (lfs_off_t i = 0; i < dsize - sizeof(tag); i++) {
1214            // rely on caching to make this efficient
1215            uint8_t dat;
1216            err = lfs_bd_read(lfs, NULL, &lfs->rcache, dsize - sizeof(tag) - i,
1217                              disk->block, disk->off + i, &dat, 1);
1218            if (err) {
1219                return err;
1220            }
1221
1222            err = lfs_dir_commitprog(lfs, commit, &dat, 1);
1223            if (err) {
1224                return err;
1225            }
1226        }
1227    }
1228
1229    commit->ptag = tag & 0x7fffffff;
1230    return 0;
1231}
1232
1233static int lfs_dir_commitcrc(lfs_t* lfs, struct lfs_commit* commit) {
1234    const lfs_off_t off1 = commit->off;
1235    const uint32_t crc1 = commit->crc;
1236    // align to program units
1237    const lfs_off_t end =
1238        lfs_alignup(off1 + 2 * sizeof(uint32_t), lfs->cfg->prog_size);
1239
1240    // create crc tags to fill up remainder of commit, note that
1241    // padding is not crced, which lets fetches skip padding but
1242    // makes committing a bit more complicated
1243    while (commit->off < end) {
1244        lfs_off_t off = commit->off + sizeof(lfs_tag_t);
1245        lfs_off_t noff = lfs_min(end - off, 0x3fe) + off;
1246        if (noff < end) {
1247            noff = lfs_min(noff, end - 2 * sizeof(uint32_t));
1248        }
1249
1250        // read erased state from next program unit
1251        lfs_tag_t tag = 0xffffffff;
1252        int err = lfs_bd_read(lfs, NULL, &lfs->rcache, sizeof(tag),
1253                              commit->block, noff, &tag, sizeof(tag));
1254        if (err && err != LFS_ERR_CORRUPT) {
1255            return err;
1256        }
1257
1258        // build crc tag
1259        bool reset = ~lfs_frombe32(tag) >> 31;
1260        tag = LFS_MKTAG(LFS_TYPE_CRC + reset, 0x3ff, noff - off);
1261
1262        // write out crc
1263        uint32_t footer[2];
1264        footer[0] = lfs_tobe32(tag ^ commit->ptag);
1265        commit->crc = lfs_crc(commit->crc, &footer[0], sizeof(footer[0]));
1266        footer[1] = lfs_tole32(commit->crc);
1267        err = lfs_bd_prog(lfs, &lfs->pcache, &lfs->rcache, false, commit->block,
1268                          commit->off, &footer, sizeof(footer));
1269        if (err) {
1270            return err;
1271        }
1272
1273        commit->off += sizeof(tag) + lfs_tag_size(tag);
1274        commit->ptag = tag ^ ((lfs_tag_t)reset << 31);
1275        commit->crc = 0xffffffff; // reset crc for next "commit"
1276    }
1277
1278    // flush buffers
1279    int err = lfs_bd_sync(lfs, &lfs->pcache, &lfs->rcache, false);
1280    if (err) {
1281        return err;
1282    }
1283
1284    // successful commit, check checksums to make sure
1285    lfs_off_t off = commit->begin;
1286    lfs_off_t noff = off1 + sizeof(uint32_t);
1287    while (off < end) {
1288        uint32_t crc = 0xffffffff;
1289        for (lfs_off_t i = off; i < noff + sizeof(uint32_t); i++) {
1290            // check against written crc, may catch blocks that
1291            // become readonly and match our commit size exactly
1292            if (i == off1 && crc != crc1) {
1293                return LFS_ERR_CORRUPT;
1294            }
1295
1296            // leave it up to caching to make this efficient
1297            uint8_t dat;
1298            err = lfs_bd_read(lfs, NULL, &lfs->rcache,
1299                              noff + sizeof(uint32_t) - i, commit->block, i,
1300                              &dat, 1);
1301            if (err) {
1302                return err;
1303            }
1304
1305            crc = lfs_crc(crc, &dat, 1);
1306        }
1307
1308        // detected write error?
1309        if (crc != 0) {
1310            return LFS_ERR_CORRUPT;
1311        }
1312
1313        // skip padding
1314        off = lfs_min(end - noff, 0x3fe) + noff;
1315        if (off < end) {
1316            off = lfs_min(off, end - 2 * sizeof(uint32_t));
1317        }
1318        noff = off + sizeof(uint32_t);
1319    }
1320
1321    return 0;
1322}
1323
1324static int lfs_dir_alloc(lfs_t* lfs, lfs_mdir_t* dir) {
1325    // allocate pair of dir blocks (backwards, so we write block 1 first)
1326    for (int i = 0; i < 2; i++) {
1327        int err = lfs_alloc(lfs, &dir->pair[(i + 1) % 2]);
1328        if (err) {
1329            return err;
1330        }
1331    }
1332
1333    // zero for reproducability in case initial block is unreadable
1334    dir->rev = 0;
1335
1336    // rather than clobbering one of the blocks we just pretend
1337    // the revision may be valid
1338    int err = lfs_bd_read(lfs, NULL, &lfs->rcache, sizeof(dir->rev),
1339                          dir->pair[0], 0, &dir->rev, sizeof(dir->rev));
1340    dir->rev = lfs_fromle32(dir->rev);
1341    if (err && err != LFS_ERR_CORRUPT) {
1342        return err;
1343    }
1344
1345    // make sure we don't immediately evict
1346    dir->rev += dir->rev & 1;
1347
1348    // set defaults
1349    dir->off = sizeof(dir->rev);
1350    dir->etag = 0xffffffff;
1351    dir->count = 0;
1352    dir->tail[0] = LFS_BLOCK_NULL;
1353    dir->tail[1] = LFS_BLOCK_NULL;
1354    dir->erased = false;
1355    dir->split = false;
1356
1357    // don't write out yet, let caller take care of that
1358    return 0;
1359}
1360
1361static int lfs_dir_drop(lfs_t* lfs, lfs_mdir_t* dir, lfs_mdir_t* tail) {
1362    // steal state
1363    int err = lfs_dir_getgstate(lfs, tail, &lfs->gdelta);
1364    if (err) {
1365        return err;
1366    }
1367
1368    // steal tail
1369    lfs_pair_tole32(tail->tail);
1370    err = lfs_dir_commit(
1371        lfs, dir,
1372        LFS_MKATTRS(
1373            {LFS_MKTAG(LFS_TYPE_TAIL + tail->split, 0x3ff, 8), tail->tail}));
1374    lfs_pair_fromle32(tail->tail);
1375    if (err) {
1376        return err;
1377    }
1378
1379    return 0;
1380}
1381
1382static int lfs_dir_split(lfs_t* lfs, lfs_mdir_t* dir,
1383                         const struct lfs_mattr* attrs, int attrcount,
1384                         lfs_mdir_t* source, uint16_t split, uint16_t end) {
1385    // create tail directory
1386    lfs_alloc_ack(lfs);
1387    lfs_mdir_t tail;
1388    int err = lfs_dir_alloc(lfs, &tail);
1389    if (err) {
1390        return err;
1391    }
1392
1393    tail.split = dir->split;
1394    tail.tail[0] = dir->tail[0];
1395    tail.tail[1] = dir->tail[1];
1396
1397    err = lfs_dir_compact(lfs, &tail, attrs, attrcount, source, split, end);
1398    if (err) {
1399        return err;
1400    }
1401
1402    dir->tail[0] = tail.pair[0];
1403    dir->tail[1] = tail.pair[1];
1404    dir->split = true;
1405
1406    // update root if needed
1407    if (lfs_pair_cmp(dir->pair, lfs->root) == 0 && split == 0) {
1408        lfs->root[0] = tail.pair[0];
1409        lfs->root[1] = tail.pair[1];
1410    }
1411
1412    return 0;
1413}
1414
1415static int lfs_dir_commit_size(void* p, lfs_tag_t tag, const void* buffer) {
1416    lfs_size_t* size = p;
1417    (void)buffer;
1418
1419    *size += lfs_tag_dsize(tag);
1420    return 0;
1421}
1422
1423struct lfs_dir_commit_commit {
1424    lfs_t* lfs;
1425    struct lfs_commit* commit;
1426};
1427
1428static int lfs_dir_commit_commit(void* p, lfs_tag_t tag, const void* buffer) {
1429    struct lfs_dir_commit_commit* commit = p;
1430    return lfs_dir_commitattr(commit->lfs, commit->commit, tag, buffer);
1431}
1432
1433static int lfs_dir_compact(lfs_t* lfs, lfs_mdir_t* dir,
1434                           const struct lfs_mattr* attrs, int attrcount,
1435                           lfs_mdir_t* source, uint16_t begin, uint16_t end) {
1436    // save some state in case block is bad
1437    const lfs_block_t oldpair[2] = {dir->pair[0], dir->pair[1]};
1438    bool relocated = false;
1439    bool tired = false;
1440
1441    // should we split?
1442    while (end - begin > 1) {
1443        // find size
1444        lfs_size_t size = 0;
1445        int err = lfs_dir_traverse(lfs, source, 0, 0xffffffff, attrs, attrcount,
1446                                   LFS_MKTAG(0x400, 0x3ff, 0),
1447                                   LFS_MKTAG(LFS_TYPE_NAME, 0, 0), begin, end,
1448                                   -begin, lfs_dir_commit_size, &size);
1449        if (err) {
1450            return err;
1451        }
1452
1453        // space is complicated, we need room for tail, crc, gstate,
1454        // cleanup delete, and we cap at half a block to give room
1455        // for metadata updates.
1456        if (end - begin < 0xff &&
1457            size <= lfs_min(lfs->cfg->block_size - 36,
1458                            lfs_alignup(lfs->cfg->block_size / 2,
1459                                        lfs->cfg->prog_size))) {
1460            break;
1461        }
1462
1463        // can't fit, need to split, we should really be finding the
1464        // largest size that fits with a small binary search, but right now
1465        // it's not worth the code size
1466        uint16_t split = (end - begin) / 2;
1467        err = lfs_dir_split(lfs, dir, attrs, attrcount, source, begin + split,
1468                            end);
1469        if (err) {
1470            // if we fail to split, we may be able to overcompact, unless
1471            // we're too big for even the full block, in which case our
1472            // only option is to error
1473            if (err == LFS_ERR_NOSPC && size <= lfs->cfg->block_size - 36) {
1474                break;
1475            }
1476            return err;
1477        }
1478
1479        end = begin + split;
1480    }
1481
1482    // increment revision count
1483    dir->rev += 1;
1484    // If our revision count == n * block_cycles, we should force a relocation,
1485    // this is how littlefs wear-levels at the metadata-pair level. Note that we
1486    // actually use (block_cycles+1)|1, this is to avoid two corner cases:
1487    // 1. block_cycles = 1, which would prevent relocations from terminating
1488    // 2. block_cycles = 2n, which, due to aliasing, would only ever relocate
1489    //    one metadata block in the pair, effectively making this useless
1490    if (lfs->cfg->block_cycles > 0 &&
1491        (dir->rev % ((lfs->cfg->block_cycles + 1) | 1) == 0)) {
1492        if (lfs_pair_cmp(dir->pair, (const lfs_block_t[2]){0, 1}) == 0) {
1493            // oh no! we're writing too much to the superblock,
1494            // should we expand?
1495            lfs_ssize_t res = lfs_fs_size(lfs);
1496            if (res < 0) {
1497                return res;
1498            }
1499
1500            // do we have extra space? littlefs can't reclaim this space
1501            // by itself, so expand cautiously
1502            if ((lfs_size_t)res < lfs->cfg->block_count / 2) {
1503                LFS_DEBUG("Expanding superblock at rev %" PRIu32, dir->rev);
1504                int err = lfs_dir_split(lfs, dir, attrs, attrcount, source,
1505                                        begin, end);
1506                if (err && err != LFS_ERR_NOSPC) {
1507                    return err;
1508                }
1509
1510                // welp, we tried, if we ran out of space there's not much
1511                // we can do, we'll error later if we've become frozen
1512                if (!err) {
1513                    end = begin;
1514                }
1515            }
1516#ifdef LFS_MIGRATE
1517        } else if (lfs->lfs1) {
1518            // do not proactively relocate blocks during migrations, this
1519            // can cause a number of failure states such: clobbering the
1520            // v1 superblock if we relocate root, and invalidating directory
1521            // pointers if we relocate the head of a directory. On top of
1522            // this, relocations increase the overall complexity of
1523            // lfs_migration, which is already a delicate operation.
1524#endif
1525        } else {
1526            // we're writing too much, time to relocate
1527            tired = true;
1528            goto relocate;
1529        }
1530    }
1531
1532    // begin loop to commit compaction to blocks until a compact sticks
1533    while (true) {
1534        {
1535            // setup commit state
1536            struct lfs_commit commit = {
1537                .block = dir->pair[1],
1538                .off = 0,
1539                .ptag = 0xffffffff,
1540                .crc = 0xffffffff,
1541
1542                .begin = 0,
1543                .end = lfs->cfg->block_size - 8,
1544            };
1545
1546            // erase block to write to
1547            int err = lfs_bd_erase(lfs, dir->pair[1]);
1548            if (err) {
1549                if (err == LFS_ERR_CORRUPT) {
1550                    goto relocate;
1551                }
1552                return err;
1553            }
1554
1555            // write out header
1556            dir->rev = lfs_tole32(dir->rev);
1557            err = lfs_dir_commitprog(lfs, &commit, &dir->rev, sizeof(dir->rev));
1558            dir->rev = lfs_fromle32(dir->rev);
1559            if (err) {
1560                if (err == LFS_ERR_CORRUPT) {
1561                    goto relocate;
1562                }
1563                return err;
1564            }
1565
1566            // traverse the directory, this time writing out all unique tags
1567            err = lfs_dir_traverse(
1568                lfs, source, 0, 0xffffffff, attrs, attrcount,
1569                LFS_MKTAG(0x400, 0x3ff, 0), LFS_MKTAG(LFS_TYPE_NAME, 0, 0),
1570                begin, end, -begin, lfs_dir_commit_commit,
1571                &(struct lfs_dir_commit_commit){lfs, &commit});
1572            if (err) {
1573                if (err == LFS_ERR_CORRUPT) {
1574                    goto relocate;
1575                }
1576                return err;
1577            }
1578
1579            // commit tail, which may be new after last size check
1580            if (!lfs_pair_isnull(dir->tail)) {
1581                lfs_pair_tole32(dir->tail);
1582                err = lfs_dir_commitattr(
1583                    lfs, &commit,
1584                    LFS_MKTAG(LFS_TYPE_TAIL + dir->split, 0x3ff, 8), dir->tail);
1585                lfs_pair_fromle32(dir->tail);
1586                if (err) {
1587                    if (err == LFS_ERR_CORRUPT) {
1588                        goto relocate;
1589                    }
1590                    return err;
1591                }
1592            }
1593
1594            // bring over gstate?
1595            lfs_gstate_t delta = {0};
1596            if (!relocated) {
1597                lfs_gstate_xor(&delta, &lfs->gdisk);
1598                lfs_gstate_xor(&delta, &lfs->gstate);
1599            }
1600            lfs_gstate_xor(&delta, &lfs->gdelta);
1601            delta.tag &= ~LFS_MKTAG(0, 0, 0x3ff);
1602
1603            err = lfs_dir_getgstate(lfs, dir, &delta);
1604            if (err) {
1605                return err;
1606            }
1607
1608            if (!lfs_gstate_iszero(&delta)) {
1609                lfs_gstate_tole32(&delta);
1610                err = lfs_dir_commitattr(
1611                    lfs, &commit,
1612                    LFS_MKTAG(LFS_TYPE_MOVESTATE, 0x3ff, sizeof(delta)),
1613                    &delta);
1614                if (err) {
1615                    if (err == LFS_ERR_CORRUPT) {
1616                        goto relocate;
1617                    }
1618                    return err;
1619                }
1620            }
1621
1622            // complete commit with crc
1623            err = lfs_dir_commitcrc(lfs, &commit);
1624            if (err) {
1625                if (err == LFS_ERR_CORRUPT) {
1626                    goto relocate;
1627                }
1628                return err;
1629            }
1630
1631            // successful compaction, swap dir pair to indicate most recent
1632            LFS_ASSERT(commit.off % lfs->cfg->prog_size == 0);
1633            lfs_pair_swap(dir->pair);
1634            dir->count = end - begin;
1635            dir->off = commit.off;
1636            dir->etag = commit.ptag;
1637            // update gstate
1638            lfs->gdelta = (lfs_gstate_t){0};
1639            if (!relocated) {
1640                lfs->gdisk = lfs->gstate;
1641            }
1642        }
1643        break;
1644
1645    relocate:
1646        // commit was corrupted, drop caches and prepare to relocate block
1647        relocated = true;
1648        lfs_cache_drop(lfs, &lfs->pcache);
1649        if (!tired) {
1650            LFS_DEBUG("Bad block at 0x%" PRIx32, dir->pair[1]);
1651        }
1652
1653        // can't relocate superblock, filesystem is now frozen
1654        if (lfs_pair_cmp(dir->pair, (const lfs_block_t[2]){0, 1}) == 0) {
1655            LFS_WARN("Superblock 0x%" PRIx32 " has become unwritable",
1656                     dir->pair[1]);
1657            return LFS_ERR_NOSPC;
1658        }
1659
1660        // relocate half of pair
1661        int err = lfs_alloc(lfs, &dir->pair[1]);
1662        if (err && (err != LFS_ERR_NOSPC || !tired)) {
1663            return err;
1664        }
1665
1666        tired = false;
1667        continue;
1668    }
1669
1670    if (relocated) {
1671        // update references if we relocated
1672        LFS_DEBUG("Relocating {0x%" PRIx32 ", 0x%" PRIx32 "} "
1673                  "-> {0x%" PRIx32 ", 0x%" PRIx32 "}",
1674                  oldpair[0], oldpair[1], dir->pair[0], dir->pair[1]);
1675        int err = lfs_fs_relocate(lfs, oldpair, dir->pair);
1676        if (err) {
1677            return err;
1678        }
1679    }
1680
1681    return 0;
1682}
1683
1684static int lfs_dir_commit(lfs_t* lfs, lfs_mdir_t* dir,
1685                          const struct lfs_mattr* attrs, int attrcount) {
1686    // check for any inline files that aren't RAM backed and
1687    // forcefully evict them, needed for filesystem consistency
1688    for (lfs_file_t* f = (lfs_file_t*)lfs->mlist; f; f = f->next) {
1689        if (dir != &f->m && lfs_pair_cmp(f->m.pair, dir->pair) == 0 &&
1690            f->type == LFS_TYPE_REG && (f->flags & LFS_F_INLINE) &&
1691            f->ctz.size > lfs->cfg->cache_size) {
1692            int err = lfs_file_outline(lfs, f);
1693            if (err) {
1694                return err;
1695            }
1696
1697            err = lfs_file_flush(lfs, f);
1698            if (err) {
1699                return err;
1700            }
1701        }
1702    }
1703
1704    // calculate changes to the directory
1705    lfs_mdir_t olddir = *dir;
1706    bool hasdelete = false;
1707    for (int i = 0; i < attrcount; i++) {
1708        if (lfs_tag_type3(attrs[i].tag) == LFS_TYPE_CREATE) {
1709            dir->count += 1;
1710        } else if (lfs_tag_type3(attrs[i].tag) == LFS_TYPE_DELETE) {
1711            LFS_ASSERT(dir->count > 0);
1712            dir->count -= 1;
1713            hasdelete = true;
1714        } else if (lfs_tag_type1(attrs[i].tag) == LFS_TYPE_TAIL) {
1715            dir->tail[0] = ((lfs_block_t*)attrs[i].buffer)[0];
1716            dir->tail[1] = ((lfs_block_t*)attrs[i].buffer)[1];
1717            dir->split = (lfs_tag_chunk(attrs[i].tag) & 1);
1718            lfs_pair_fromle32(dir->tail);
1719        }
1720    }
1721
1722    // should we actually drop the directory block?
1723    if (hasdelete && dir->count == 0) {
1724        lfs_mdir_t pdir;
1725        int err = lfs_fs_pred(lfs, dir->pair, &pdir);
1726        if (err && err != LFS_ERR_NOENT) {
1727            *dir = olddir;
1728            return err;
1729        }
1730
1731        if (err != LFS_ERR_NOENT && pdir.split) {
1732            err = lfs_dir_drop(lfs, &pdir, dir);
1733            if (err) {
1734                *dir = olddir;
1735                return err;
1736            }
1737        }
1738    }
1739
1740    if (dir->erased || dir->count >= 0xff) {
1741        // try to commit
1742        struct lfs_commit commit = {
1743            .block = dir->pair[0],
1744            .off = dir->off,
1745            .ptag = dir->etag,
1746            .crc = 0xffffffff,
1747
1748            .begin = dir->off,
1749            .end = lfs->cfg->block_size - 8,
1750        };
1751
1752        // traverse attrs that need to be written out
1753        lfs_pair_tole32(dir->tail);
1754        int err =
1755            lfs_dir_traverse(lfs, dir, dir->off, dir->etag, attrs, attrcount, 0,
1756                             0, 0, 0, 0, lfs_dir_commit_commit,
1757                             &(struct lfs_dir_commit_commit){lfs, &commit});
1758        lfs_pair_fromle32(dir->tail);
1759        if (err) {
1760            if (err == LFS_ERR_NOSPC || err == LFS_ERR_CORRUPT) {
1761                goto compact;
1762            }
1763            *dir = olddir;
1764            return err;
1765        }
1766
1767        // commit any global diffs if we have any
1768        lfs_gstate_t delta = {0};
1769        lfs_gstate_xor(&delta, &lfs->gstate);
1770        lfs_gstate_xor(&delta, &lfs->gdisk);
1771        lfs_gstate_xor(&delta, &lfs->gdelta);
1772        delta.tag &= ~LFS_MKTAG(0, 0, 0x3ff);
1773        if (!lfs_gstate_iszero(&delta)) {
1774            err = lfs_dir_getgstate(lfs, dir, &delta);
1775            if (err) {
1776                *dir = olddir;
1777                return err;
1778            }
1779
1780            lfs_gstate_tole32(&delta);
1781            err = lfs_dir_commitattr(
1782                lfs, &commit,
1783                LFS_MKTAG(LFS_TYPE_MOVESTATE, 0x3ff, sizeof(delta)), &delta);
1784            if (err) {
1785                if (err == LFS_ERR_NOSPC || err == LFS_ERR_CORRUPT) {
1786                    goto compact;
1787                }
1788                *dir = olddir;
1789                return err;
1790            }
1791        }
1792
1793        // finalize commit with the crc
1794        err = lfs_dir_commitcrc(lfs, &commit);
1795        if (err) {
1796            if (err == LFS_ERR_NOSPC || err == LFS_ERR_CORRUPT) {
1797                goto compact;
1798            }
1799            *dir = olddir;
1800            return err;
1801        }
1802
1803        // successful commit, update dir
1804        LFS_ASSERT(commit.off % lfs->cfg->prog_size == 0);
1805        dir->off = commit.off;
1806        dir->etag = commit.ptag;
1807        // and update gstate
1808        lfs->gdisk = lfs->gstate;
1809        lfs->gdelta = (lfs_gstate_t){0};
1810    } else {
1811    compact:
1812        // fall back to compaction
1813        lfs_cache_drop(lfs, &lfs->pcache);
1814
1815        int err =
1816            lfs_dir_compact(lfs, dir, attrs, attrcount, dir, 0, dir->count);
1817        if (err) {
1818            *dir = olddir;
1819            return err;
1820        }
1821    }
1822
1823    // this complicated bit of logic is for fixing up any active
1824    // metadata-pairs that we may have affected
1825    //
1826    // note we have to make two passes since the mdir passed to
1827    // lfs_dir_commit could also be in this list, and even then
1828    // we need to copy the pair so they don't get clobbered if we refetch
1829    // our mdir.
1830    for (struct lfs_mlist* d = lfs->mlist; d; d = d->next) {
1831        if (&d->m != dir && lfs_pair_cmp(d->m.pair, olddir.pair) == 0) {
1832            d->m = *dir;
1833            for (int i = 0; i < attrcount; i++) {
1834                if (lfs_tag_type3(attrs[i].tag) == LFS_TYPE_DELETE &&
1835                    d->id == lfs_tag_id(attrs[i].tag)) {
1836                    d->m.pair[0] = LFS_BLOCK_NULL;
1837                    d->m.pair[1] = LFS_BLOCK_NULL;
1838                } else if (lfs_tag_type3(attrs[i].tag) == LFS_TYPE_DELETE &&
1839                           d->id > lfs_tag_id(attrs[i].tag)) {
1840                    d->id -= 1;
1841                    if (d->type == LFS_TYPE_DIR) {
1842                        ((lfs_dir_t*)d)->pos -= 1;
1843                    }
1844                } else if (lfs_tag_type3(attrs[i].tag) == LFS_TYPE_CREATE &&
1845                           d->id >= lfs_tag_id(attrs[i].tag)) {
1846                    d->id += 1;
1847                    if (d->type == LFS_TYPE_DIR) {
1848                        ((lfs_dir_t*)d)->pos += 1;
1849                    }
1850                }
1851            }
1852        }
1853    }
1854
1855    for (struct lfs_mlist* d = lfs->mlist; d; d = d->next) {
1856        if (lfs_pair_cmp(d->m.pair, olddir.pair) == 0) {
1857            while (d->id >= d->m.count && d->m.split) {
1858                // we split and id is on tail now
1859                d->id -= d->m.count;
1860                int err = lfs_dir_fetch(lfs, &d->m, d->m.tail);
1861                if (err) {
1862                    return err;
1863                }
1864            }
1865        }
1866    }
1867
1868    return 0;
1869}
1870
1871/// Top level directory operations ///
1872int lfs_mkdir(lfs_t* lfs, const char* path) {
1873    LFS_TRACE("lfs_mkdir(%p, \"%s\")", (void*)lfs, path);
1874    // deorphan if we haven't yet, needed at most once after poweron
1875    int err = lfs_fs_forceconsistency(lfs);
1876    if (err) {
1877        LFS_TRACE("lfs_mkdir -> %d", err);
1878        return err;
1879    }
1880
1881    struct lfs_mlist cwd;
1882    cwd.next = lfs->mlist;
1883    uint16_t id;
1884    err = lfs_dir_find(lfs, &cwd.m, &path, &id);
1885    if (!(err == LFS_ERR_NOENT && id != 0x3ff)) {
1886        LFS_TRACE("lfs_mkdir -> %d", (err < 0) ? err : LFS_ERR_EXIST);
1887        return (err < 0) ? err : LFS_ERR_EXIST;
1888    }
1889
1890    // check that name fits
1891    lfs_size_t nlen = strlen(path);
1892    if (nlen > lfs->name_max) {
1893        LFS_TRACE("lfs_mkdir -> %d", LFS_ERR_NAMETOOLONG);
1894        return LFS_ERR_NAMETOOLONG;
1895    }
1896
1897    // build up new directory
1898    lfs_alloc_ack(lfs);
1899    lfs_mdir_t dir;
1900    err = lfs_dir_alloc(lfs, &dir);
1901    if (err) {
1902        LFS_TRACE("lfs_mkdir -> %d", err);
1903        return err;
1904    }
1905
1906    // find end of list
1907    lfs_mdir_t pred = cwd.m;
1908    while (pred.split) {
1909        err = lfs_dir_fetch(lfs, &pred, pred.tail);
1910        if (err) {
1911            LFS_TRACE("lfs_mkdir -> %d", err);
1912            return err;
1913        }
1914    }
1915
1916    // setup dir
1917    lfs_pair_tole32(pred.tail);
1918    err = lfs_dir_commit(
1919        lfs, &dir,
1920        LFS_MKATTRS({LFS_MKTAG(LFS_TYPE_SOFTTAIL, 0x3ff, 8), pred.tail}));
1921    lfs_pair_fromle32(pred.tail);
1922    if (err) {
1923        LFS_TRACE("lfs_mkdir -> %d", err);
1924        return err;
1925    }
1926
1927    // current block end of list?
1928    if (cwd.m.split) {
1929        // update tails, this creates a desync
1930        lfs_fs_preporphans(lfs, +1);
1931
1932        // it's possible our predecessor has to be relocated, and if
1933        // our parent is our predecessor's predecessor, this could have
1934        // caused our parent to go out of date, fortunately we can hook
1935        // ourselves into littlefs to catch this
1936        cwd.type = 0;
1937        cwd.id = 0;
1938        lfs->mlist = &cwd;
1939
1940        lfs_pair_tole32(dir.pair);
1941        err = lfs_dir_commit(
1942            lfs, &pred,
1943            LFS_MKATTRS({LFS_MKTAG(LFS_TYPE_SOFTTAIL, 0x3ff, 8), dir.pair}));
1944        lfs_pair_fromle32(dir.pair);
1945        if (err) {
1946            lfs->mlist = cwd.next;
1947            LFS_TRACE("lfs_mkdir -> %d", err);
1948            return err;
1949        }
1950
1951        lfs->mlist = cwd.next;
1952        lfs_fs_preporphans(lfs, -1);
1953    }
1954
1955    // now insert into our parent block
1956    lfs_pair_tole32(dir.pair);
1957    err = lfs_dir_commit(
1958        lfs, &cwd.m,
1959        LFS_MKATTRS({LFS_MKTAG(LFS_TYPE_CREATE, id, 0), NULL},
1960                    {LFS_MKTAG(LFS_TYPE_DIR, id, nlen), path},
1961                    {LFS_MKTAG(LFS_TYPE_DIRSTRUCT, id, 8), dir.pair},
1962                    {LFS_MKTAG_IF(!cwd.m.split, LFS_TYPE_SOFTTAIL, 0x3ff, 8),
1963                     dir.pair}));
1964    lfs_pair_fromle32(dir.pair);
1965    if (err) {
1966        LFS_TRACE("lfs_mkdir -> %d", err);
1967        return err;
1968    }
1969
1970    LFS_TRACE("lfs_mkdir -> %d", 0);
1971    return 0;
1972}
1973
1974int lfs_dir_open(lfs_t* lfs, lfs_dir_t* dir, const char* path) {
1975    LFS_TRACE("lfs_dir_open(%p, %p, \"%s\")", (void*)lfs, (void*)dir, path);
1976    lfs_stag_t tag = lfs_dir_find(lfs, &dir->m, &path, NULL);
1977    if (tag < 0) {
1978        LFS_TRACE("lfs_dir_open -> %" PRId32, tag);
1979        return tag;
1980    }
1981
1982    if (lfs_tag_type3(tag) != LFS_TYPE_DIR) {
1983        LFS_TRACE("lfs_dir_open -> %d", LFS_ERR_NOTDIR);
1984        return LFS_ERR_NOTDIR;
1985    }
1986
1987    lfs_block_t pair[2];
1988    if (lfs_tag_id(tag) == 0x3ff) {
1989        // handle root dir separately
1990        pair[0] = lfs->root[0];
1991        pair[1] = lfs->root[1];
1992    } else {
1993        // get dir pair from parent
1994        lfs_stag_t res =
1995            lfs_dir_get(lfs, &dir->m, LFS_MKTAG(0x700, 0x3ff, 0),
1996                        LFS_MKTAG(LFS_TYPE_STRUCT, lfs_tag_id(tag), 8), pair);
1997        if (res < 0) {
1998            LFS_TRACE("lfs_dir_open -> %" PRId32, res);
1999            return res;
2000        }
2001        lfs_pair_fromle32(pair);
2002    }
2003
2004    // fetch first pair
2005    int err = lfs_dir_fetch(lfs, &dir->m, pair);
2006    if (err) {
2007        LFS_TRACE("lfs_dir_open -> %d", err);
2008        return err;
2009    }
2010
2011    // setup entry
2012    dir->head[0] = dir->m.pair[0];
2013    dir->head[1] = dir->m.pair[1];
2014    dir->id = 0;
2015    dir->pos = 0;
2016
2017    // add to list of mdirs
2018    dir->type = LFS_TYPE_DIR;
2019    dir->next = (lfs_dir_t*)lfs->mlist;
2020    lfs->mlist = (struct lfs_mlist*)dir;
2021
2022    LFS_TRACE("lfs_dir_open -> %d", 0);
2023    return 0;
2024}
2025
2026int lfs_dir_close(lfs_t* lfs, lfs_dir_t* dir) {
2027    LFS_TRACE("lfs_dir_close(%p, %p)", (void*)lfs, (void*)dir);
2028    // remove from list of mdirs
2029    for (struct lfs_mlist** p = &lfs->mlist; *p; p = &(*p)->next) {
2030        if (*p == (struct lfs_mlist*)dir) {
2031            *p = (*p)->next;
2032            break;
2033        }
2034    }
2035
2036    LFS_TRACE("lfs_dir_close -> %d", 0);
2037    return 0;
2038}
2039
2040int lfs_dir_read(lfs_t* lfs, lfs_dir_t* dir, struct lfs_info* info) {
2041    LFS_TRACE("lfs_dir_read(%p, %p, %p)", (void*)lfs, (void*)dir, (void*)info);
2042    memset(info, 0, sizeof(*info));
2043
2044    // special offset for '.' and '..'
2045    if (dir->pos == 0) {
2046        info->type = LFS_TYPE_DIR;
2047        strcpy(info->name, ".");
2048        dir->pos += 1;
2049        LFS_TRACE("lfs_dir_read -> %d", true);
2050        return true;
2051    } else if (dir->pos == 1) {
2052        info->type = LFS_TYPE_DIR;
2053        strcpy(info->name, "..");
2054        dir->pos += 1;
2055        LFS_TRACE("lfs_dir_read -> %d", true);
2056        return true;
2057    }
2058
2059    while (true) {
2060        if (dir->id == dir->m.count) {
2061            if (!dir->m.split) {
2062                LFS_TRACE("lfs_dir_read -> %d", false);
2063                return false;
2064            }
2065
2066            int err = lfs_dir_fetch(lfs, &dir->m, dir->m.tail);
2067            if (err) {
2068                LFS_TRACE("lfs_dir_read -> %d", err);
2069                return err;
2070            }
2071
2072            dir->id = 0;
2073        }
2074
2075        int err = lfs_dir_getinfo(lfs, &dir->m, dir->id, info);
2076        if (err && err != LFS_ERR_NOENT) {
2077            LFS_TRACE("lfs_dir_read -> %d", err);
2078            return err;
2079        }
2080
2081        dir->id += 1;
2082        if (err != LFS_ERR_NOENT) {
2083            break;
2084        }
2085    }
2086
2087    dir->pos += 1;
2088    LFS_TRACE("lfs_dir_read -> %d", true);
2089    return true;
2090}
2091
2092int lfs_dir_seek(lfs_t* lfs, lfs_dir_t* dir, lfs_off_t off) {
2093    LFS_TRACE("lfs_dir_seek(%p, %p, %" PRIu32 ")", (void*)lfs, (void*)dir, off);
2094    // simply walk from head dir
2095    int err = lfs_dir_rewind(lfs, dir);
2096    if (err) {
2097        LFS_TRACE("lfs_dir_seek -> %d", err);
2098        return err;
2099    }
2100
2101    // first two for ./..
2102    dir->pos = lfs_min(2, off);
2103    off -= dir->pos;
2104
2105    // skip superblock entry
2106    dir->id = (off > 0 && lfs_pair_cmp(dir->head, lfs->root) == 0);
2107
2108    while (off > 0) {
2109        int diff = lfs_min(dir->m.count - dir->id, off);
2110        dir->id += diff;
2111        dir->pos += diff;
2112        off -= diff;
2113
2114        if (dir->id == dir->m.count) {
2115            if (!dir->m.split) {
2116                LFS_TRACE("lfs_dir_seek -> %d", LFS_ERR_INVAL);
2117                return LFS_ERR_INVAL;
2118            }
2119
2120            err = lfs_dir_fetch(lfs, &dir->m, dir->m.tail);
2121            if (err) {
2122                LFS_TRACE("lfs_dir_seek -> %d", err);
2123                return err;
2124            }
2125
2126            dir->id = 0;
2127        }
2128    }
2129
2130    LFS_TRACE("lfs_dir_seek -> %d", 0);
2131    return 0;
2132}
2133
2134lfs_soff_t lfs_dir_tell(lfs_t* lfs, lfs_dir_t* dir) {
2135    LFS_TRACE("lfs_dir_tell(%p, %p)", (void*)lfs, (void*)dir);
2136    (void)lfs;
2137    LFS_TRACE("lfs_dir_tell -> %" PRId32, dir->pos);
2138    return dir->pos;
2139}
2140
2141int lfs_dir_rewind(lfs_t* lfs, lfs_dir_t* dir) {
2142    LFS_TRACE("lfs_dir_rewind(%p, %p)", (void*)lfs, (void*)dir);
2143    // reload the head dir
2144    int err = lfs_dir_fetch(lfs, &dir->m, dir->head);
2145    if (err) {
2146        LFS_TRACE("lfs_dir_rewind -> %d", err);
2147        return err;
2148    }
2149
2150    dir->id = 0;
2151    dir->pos = 0;
2152    LFS_TRACE("lfs_dir_rewind -> %d", 0);
2153    return 0;
2154}
2155
2156/// File index list operations ///
2157static int lfs_ctz_index(lfs_t* lfs, lfs_off_t* off) {
2158    lfs_off_t size = *off;
2159    lfs_off_t b = lfs->cfg->block_size - 2 * 4;
2160    lfs_off_t i = size / b;
2161    if (i == 0) {
2162        return 0;
2163    }
2164
2165    i = (size - 4 * (lfs_popc(i - 1) + 2)) / b;
2166    *off = size - b * i - 4 * lfs_popc(i);
2167    return i;
2168}
2169
2170static int lfs_ctz_find(lfs_t* lfs, const lfs_cache_t* pcache,
2171                        lfs_cache_t* rcache, lfs_block_t head, lfs_size_t size,
2172                        lfs_size_t pos, lfs_block_t* block, lfs_off_t* off) {
2173    if (size == 0) {
2174        *block = LFS_BLOCK_NULL;
2175        *off = 0;
2176        return 0;
2177    }
2178
2179    lfs_off_t current = lfs_ctz_index(lfs, &(lfs_off_t){size - 1});
2180    lfs_off_t target = lfs_ctz_index(lfs, &pos);
2181
2182    while (current > target) {
2183        lfs_size_t skip =
2184            lfs_min(lfs_npw2(current - target + 1) - 1, lfs_ctz(current));
2185
2186        int err = lfs_bd_read(lfs, pcache, rcache, sizeof(head), head, 4 * skip,
2187                              &head, sizeof(head));
2188        head = lfs_fromle32(head);
2189        if (err) {
2190            return err;
2191        }
2192
2193        current -= 1 << skip;
2194    }
2195
2196    *block = head;
2197    *off = pos;
2198    return 0;
2199}
2200
2201static int lfs_ctz_extend(lfs_t* lfs, lfs_cache_t* pcache, lfs_cache_t* rcache,
2202                          lfs_block_t head, lfs_size_t size, lfs_block_t* block,
2203                          lfs_off_t* off) {
2204    while (true) {
2205        // go ahead and grab a block
2206        lfs_block_t nblock;
2207        int err = lfs_alloc(lfs, &nblock);
2208        if (err) {
2209            return err;
2210        }
2211
2212        {
2213            err = lfs_bd_erase(lfs, nblock);
2214            if (err) {
2215                if (err == LFS_ERR_CORRUPT) {
2216                    goto relocate;
2217                }
2218                return err;
2219            }
2220
2221            if (size == 0) {
2222                *block = nblock;
2223                *off = 0;
2224                return 0;
2225            }
2226
2227            lfs_size_t noff = size - 1;
2228            lfs_off_t index = lfs_ctz_index(lfs, &noff);
2229            noff = noff + 1;
2230
2231            // just copy out the last block if it is incomplete
2232            if (noff != lfs->cfg->block_size) {
2233                for (lfs_off_t i = 0; i < noff; i++) {
2234                    uint8_t data;
2235                    err = lfs_bd_read(lfs, NULL, rcache, noff - i, head, i,
2236                                      &data, 1);
2237                    if (err) {
2238                        return err;
2239                    }
2240
2241                    err = lfs_bd_prog(lfs, pcache, rcache, true, nblock, i,
2242                                      &data, 1);
2243                    if (err) {
2244                        if (err == LFS_ERR_CORRUPT) {
2245                            goto relocate;
2246                        }
2247                        return err;
2248                    }
2249                }
2250
2251                *block = nblock;
2252                *off = noff;
2253                return 0;
2254            }
2255
2256            // append block
2257            index += 1;
2258            lfs_size_t skips = lfs_ctz(index) + 1;
2259            lfs_block_t nhead = head;
2260            for (lfs_off_t i = 0; i < skips; i++) {
2261                nhead = lfs_tole32(nhead);
2262                err = lfs_bd_prog(lfs, pcache, rcache, true, nblock, 4 * i,
2263                                  &nhead, 4);
2264                nhead = lfs_fromle32(nhead);
2265                if (err) {
2266                    if (err == LFS_ERR_CORRUPT) {
2267                        goto relocate;
2268                    }
2269                    return err;
2270                }
2271
2272                if (i != skips - 1) {
2273                    err = lfs_bd_read(lfs, NULL, rcache, sizeof(nhead), nhead,
2274                                      4 * i, &nhead, sizeof(nhead));
2275                    nhead = lfs_fromle32(nhead);
2276                    if (err) {
2277                        return err;
2278                    }
2279                }
2280            }
2281
2282            *block = nblock;
2283            *off = 4 * skips;
2284            return 0;
2285        }
2286
2287    relocate:
2288        LFS_DEBUG("Bad block at 0x%" PRIx32, nblock);
2289
2290        // just clear cache and try a new block
2291        lfs_cache_drop(lfs, pcache);
2292    }
2293}
2294
2295static int lfs_ctz_traverse(lfs_t* lfs, const lfs_cache_t* pcache,
2296                            lfs_cache_t* rcache, lfs_block_t head,
2297                            lfs_size_t size, int (*cb)(void*, lfs_block_t),
2298                            void* data) {
2299    if (size == 0) {
2300        return 0;
2301    }
2302
2303    lfs_off_t index = lfs_ctz_index(lfs, &(lfs_off_t){size - 1});
2304
2305    while (true) {
2306        int err = cb(data, head);
2307        if (err) {
2308            return err;
2309        }
2310
2311        if (index == 0) {
2312            return 0;
2313        }
2314
2315        lfs_block_t heads[2];
2316        int count = 2 - (index & 1);
2317        err = lfs_bd_read(lfs, pcache, rcache, count * sizeof(head), head, 0,
2318                          &heads, count * sizeof(head));
2319        heads[0] = lfs_fromle32(heads[0]);
2320        heads[1] = lfs_fromle32(heads[1]);
2321        if (err) {
2322            return err;
2323        }
2324
2325        for (int i = 0; i < count - 1; i++) {
2326            err = cb(data, heads[i]);
2327            if (err) {
2328                return err;
2329            }
2330        }
2331
2332        head = heads[count - 1];
2333        index -= count;
2334    }
2335}
2336
2337/// Top level file operations ///
2338int lfs_file_opencfg(lfs_t* lfs, lfs_file_t* file, const char* path, int flags,
2339                     const struct lfs_file_config* cfg) {
2340    LFS_TRACE("lfs_file_opencfg(%p, %p, \"%s\", %x, %p {"
2341              ".buffer=%p, .attrs=%p, .attr_count=%" PRIu32 "})",
2342              (void*)lfs, (void*)file, path, flags, (void*)cfg, cfg->buffer,
2343              (void*)cfg->attrs, cfg->attr_count);
2344
2345    // deorphan if we haven't yet, needed at most once after poweron
2346    if ((flags & 3) != LFS_O_RDONLY) {
2347        int err = lfs_fs_forceconsistency(lfs);
2348        if (err) {
2349            LFS_TRACE("lfs_file_opencfg -> %d", err);
2350            return err;
2351        }
2352    }
2353
2354    // setup simple file details
2355    int err;
2356    file->cfg = cfg;
2357    file->flags = flags | LFS_F_OPENED;
2358    file->pos = 0;
2359    file->off = 0;
2360    file->cache.buffer = NULL;
2361
2362    // allocate entry for file if it doesn't exist
2363    lfs_stag_t tag = lfs_dir_find(lfs, &file->m, &path, &file->id);
2364    if (tag < 0 && !(tag == LFS_ERR_NOENT && file->id != 0x3ff)) {
2365        err = tag;
2366        goto cleanup;
2367    }
2368
2369    // get id, add to list of mdirs to catch update changes
2370    file->type = LFS_TYPE_REG;
2371    file->next = (lfs_file_t*)lfs->mlist;
2372    lfs->mlist = (struct lfs_mlist*)file;
2373
2374    if (tag == LFS_ERR_NOENT) {
2375        if (!(flags & LFS_O_CREAT)) {
2376            err = LFS_ERR_NOENT;
2377            goto cleanup;
2378        }
2379
2380        // check that name fits
2381        lfs_size_t nlen = strlen(path);
2382        if (nlen > lfs->name_max) {
2383            err = LFS_ERR_NAMETOOLONG;
2384            goto cleanup;
2385        }
2386
2387        // get next slot and create entry to remember name
2388        err = lfs_dir_commit(
2389            lfs, &file->m,
2390            LFS_MKATTRS({LFS_MKTAG(LFS_TYPE_CREATE, file->id, 0), NULL},
2391                        {LFS_MKTAG(LFS_TYPE_REG, file->id, nlen), path},
2392                        {LFS_MKTAG(LFS_TYPE_INLINESTRUCT, file->id, 0), NULL}));
2393        if (err) {
2394            err = LFS_ERR_NAMETOOLONG;
2395            goto cleanup;
2396        }
2397
2398        tag = LFS_MKTAG(LFS_TYPE_INLINESTRUCT, 0, 0);
2399    } else if (flags & LFS_O_EXCL) {
2400        err = LFS_ERR_EXIST;
2401        goto cleanup;
2402    } else if (lfs_tag_type3(tag) != LFS_TYPE_REG) {
2403        err = LFS_ERR_ISDIR;
2404        goto cleanup;
2405    } else if (flags & LFS_O_TRUNC) {
2406        // truncate if requested
2407        tag = LFS_MKTAG(LFS_TYPE_INLINESTRUCT, file->id, 0);
2408        file->flags |= LFS_F_DIRTY;
2409    } else {
2410        // try to load what's on disk, if it's inlined we'll fix it later
2411        tag = lfs_dir_get(lfs, &file->m, LFS_MKTAG(0x700, 0x3ff, 0),
2412                          LFS_MKTAG(LFS_TYPE_STRUCT, file->id, 8), &file->ctz);
2413        if (tag < 0) {
2414            err = tag;
2415            goto cleanup;
2416        }
2417        lfs_ctz_fromle32(&file->ctz);
2418    }
2419
2420    // fetch attrs
2421    for (unsigned i = 0; i < file->cfg->attr_count; i++) {
2422        if ((file->flags & 3) != LFS_O_WRONLY) {
2423            lfs_stag_t res = lfs_dir_get(
2424                lfs, &file->m, LFS_MKTAG(0x7ff, 0x3ff, 0),
2425                LFS_MKTAG(LFS_TYPE_USERATTR + file->cfg->attrs[i].type,
2426                          file->id, file->cfg->attrs[i].size),
2427                file->cfg->attrs[i].buffer);
2428            if (res < 0 && res != LFS_ERR_NOENT) {
2429                err = res;
2430                goto cleanup;
2431            }
2432        }
2433
2434        if ((file->flags & 3) != LFS_O_RDONLY) {
2435            if (file->cfg->attrs[i].size > lfs->attr_max) {
2436                err = LFS_ERR_NOSPC;
2437                goto cleanup;
2438            }
2439
2440            file->flags |= LFS_F_DIRTY;
2441        }
2442    }
2443
2444    // allocate buffer if needed
2445    if (file->cfg->buffer) {
2446        file->cache.buffer = file->cfg->buffer;
2447    } else {
2448        file->cache.buffer = lfs_malloc(lfs->cfg->cache_size);
2449        if (!file->cache.buffer) {
2450            err = LFS_ERR_NOMEM;
2451            goto cleanup;
2452        }
2453    }
2454
2455    // zero to avoid information leak
2456    lfs_cache_zero(lfs, &file->cache);
2457
2458    if (lfs_tag_type3(tag) == LFS_TYPE_INLINESTRUCT) {
2459        // load inline files
2460        file->ctz.head = LFS_BLOCK_INLINE;
2461        file->ctz.size = lfs_tag_size(tag);
2462        file->flags |= LFS_F_INLINE;
2463        file->cache.block = file->ctz.head;
2464        file->cache.off = 0;
2465        file->cache.size = lfs->cfg->cache_size;
2466
2467        // don't always read (may be new/trunc file)
2468        if (file->ctz.size > 0) {
2469            lfs_stag_t res =
2470                lfs_dir_get(lfs, &file->m, LFS_MKTAG(0x700, 0x3ff, 0),
2471                            LFS_MKTAG(LFS_TYPE_STRUCT, file->id,
2472                                      lfs_min(file->cache.size, 0x3fe)),
2473                            file->cache.buffer);
2474            if (res < 0) {
2475                err = res;
2476                goto cleanup;
2477            }
2478        }
2479    }
2480
2481    LFS_TRACE("lfs_file_opencfg -> %d", 0);
2482    return 0;
2483
2484cleanup:
2485    // clean up lingering resources
2486    file->flags |= LFS_F_ERRED;
2487    lfs_file_close(lfs, file);
2488    LFS_TRACE("lfs_file_opencfg -> %d", err);
2489    return err;
2490}
2491
2492int lfs_file_open(lfs_t* lfs, lfs_file_t* file, const char* path, int flags) {
2493    LFS_TRACE("lfs_file_open(%p, %p, \"%s\", %x)", (void*)lfs, (void*)file,
2494              path, flags);
2495    static const struct lfs_file_config defaults = {0};
2496    int err = lfs_file_opencfg(lfs, file, path, flags, &defaults);
2497    LFS_TRACE("lfs_file_open -> %d", err);
2498    return err;
2499}
2500
2501int lfs_file_close(lfs_t* lfs, lfs_file_t* file) {
2502    LFS_TRACE("lfs_file_close(%p, %p)", (void*)lfs, (void*)file);
2503    LFS_ASSERT(file->flags & LFS_F_OPENED);
2504
2505    int err = lfs_file_sync(lfs, file);
2506
2507    // remove from list of mdirs
2508    for (struct lfs_mlist** p = &lfs->mlist; *p; p = &(*p)->next) {
2509        if (*p == (struct lfs_mlist*)file) {
2510            *p = (*p)->next;
2511            break;
2512        }
2513    }
2514
2515    // clean up memory
2516    if (!file->cfg->buffer && file->cache.buffer) {
2517        lfs_free(file->cache.buffer);
2518    }
2519
2520    file->flags &= ~LFS_F_OPENED;
2521    LFS_TRACE("lfs_file_close -> %d", err);
2522    return err;
2523}
2524
2525static int lfs_file_relocate(lfs_t* lfs, lfs_file_t* file) {
2526    LFS_ASSERT(file->flags & LFS_F_OPENED);
2527
2528    while (true) {
2529        // just relocate what exists into new block
2530        lfs_block_t nblock;
2531        int err = lfs_alloc(lfs, &nblock);
2532        if (err) {
2533            return err;
2534        }
2535
2536        err = lfs_bd_erase(lfs, nblock);
2537        if (err) {
2538            if (err == LFS_ERR_CORRUPT) {
2539                goto relocate;
2540            }
2541            return err;
2542        }
2543
2544        // either read from dirty cache or disk
2545        for (lfs_off_t i = 0; i < file->off; i++) {
2546            uint8_t data;
2547            if (file->flags & LFS_F_INLINE) {
2548                err = lfs_dir_getread(
2549                    lfs, &file->m,
2550                    // note we evict inline files before they can be dirty
2551                    NULL, &file->cache, file->off - i,
2552                    LFS_MKTAG(0xfff, 0x1ff, 0),
2553                    LFS_MKTAG(LFS_TYPE_INLINESTRUCT, file->id, 0), i, &data, 1);
2554                if (err) {
2555                    return err;
2556                }
2557            } else {
2558                err = lfs_bd_read(lfs, &file->cache, &lfs->rcache,
2559                                  file->off - i, file->block, i, &data, 1);
2560                if (err) {
2561                    return err;
2562                }
2563            }
2564
2565            err = lfs_bd_prog(lfs, &lfs->pcache, &lfs->rcache, true, nblock, i,
2566                              &data, 1);
2567            if (err) {
2568                if (err == LFS_ERR_CORRUPT) {
2569                    goto relocate;
2570                }
2571                return err;
2572            }
2573        }
2574
2575        // copy over new state of file
2576        memcpy(file->cache.buffer, lfs->pcache.buffer, lfs->cfg->cache_size);
2577        file->cache.block = lfs->pcache.block;
2578        file->cache.off = lfs->pcache.off;
2579        file->cache.size = lfs->pcache.size;
2580        lfs_cache_zero(lfs, &lfs->pcache);
2581
2582        file->block = nblock;
2583        file->flags |= LFS_F_WRITING;
2584        return 0;
2585
2586    relocate:
2587        LFS_DEBUG("Bad block at 0x%" PRIx32, nblock);
2588
2589        // just clear cache and try a new block
2590        lfs_cache_drop(lfs, &lfs->pcache);
2591    }
2592}
2593
2594static int lfs_file_outline(lfs_t* lfs, lfs_file_t* file) {
2595    file->off = file->pos;
2596    lfs_alloc_ack(lfs);
2597    int err = lfs_file_relocate(lfs, file);
2598    if (err) {
2599        return err;
2600    }
2601
2602    file->flags &= ~LFS_F_INLINE;
2603    return 0;
2604}
2605
2606static int lfs_file_flush(lfs_t* lfs, lfs_file_t* file) {
2607    LFS_ASSERT(file->flags & LFS_F_OPENED);
2608
2609    if (file->flags & LFS_F_READING) {
2610        if (!(file->flags & LFS_F_INLINE)) {
2611            lfs_cache_drop(lfs, &file->cache);
2612        }
2613        file->flags &= ~LFS_F_READING;
2614    }
2615
2616    if (file->flags & LFS_F_WRITING) {
2617        lfs_off_t pos = file->pos;
2618
2619        if (!(file->flags & LFS_F_INLINE)) {
2620            // copy over anything after current branch
2621            lfs_file_t orig = {
2622                .ctz.head = file->ctz.head,
2623                .ctz.size = file->ctz.size,
2624                .flags = LFS_O_RDONLY | LFS_F_OPENED,
2625                .pos = file->pos,
2626                .cache = lfs->rcache,
2627            };
2628            lfs_cache_drop(lfs, &lfs->rcache);
2629
2630            while (file->pos < file->ctz.size) {
2631                // copy over a byte at a time, leave it up to caching
2632                // to make this efficient
2633                uint8_t data;
2634                lfs_ssize_t res = lfs_file_read(lfs, &orig, &data, 1);
2635                if (res < 0) {
2636                    return res;
2637                }
2638
2639                res = lfs_file_write(lfs, file, &data, 1);
2640                if (res < 0) {
2641                    return res;
2642                }
2643
2644                // keep our reference to the rcache in sync
2645                if (lfs->rcache.block != LFS_BLOCK_NULL) {
2646                    lfs_cache_drop(lfs, &orig.cache);
2647                    lfs_cache_drop(lfs, &lfs->rcache);
2648                }
2649            }
2650
2651            // write out what we have
2652            while (true) {
2653                int err = lfs_bd_flush(lfs, &file->cache, &lfs->rcache, true);
2654                if (err) {
2655                    if (err == LFS_ERR_CORRUPT) {
2656                        goto relocate;
2657                    }
2658                    return err;
2659                }
2660
2661                break;
2662
2663            relocate:
2664                LFS_DEBUG("Bad block at 0x%" PRIx32, file->block);
2665                err = lfs_file_relocate(lfs, file);
2666                if (err) {
2667                    return err;
2668                }
2669            }
2670        } else {
2671            file->pos = lfs_max(file->pos, file->ctz.size);
2672        }
2673
2674        // actual file updates
2675        file->ctz.head = file->block;
2676        file->ctz.size = file->pos;
2677        file->flags &= ~LFS_F_WRITING;
2678        file->flags |= LFS_F_DIRTY;
2679
2680        file->pos = pos;
2681    }
2682
2683    return 0;
2684}
2685
2686int lfs_file_sync(lfs_t* lfs, lfs_file_t* file) {
2687    LFS_TRACE("lfs_file_sync(%p, %p)", (void*)lfs, (void*)file);
2688    LFS_ASSERT(file->flags & LFS_F_OPENED);
2689
2690    if (file->flags & LFS_F_ERRED) {
2691        // it's not safe to do anything if our file errored
2692        LFS_TRACE("lfs_file_sync -> %d", 0);
2693        return 0;
2694    }
2695
2696    int err = lfs_file_flush(lfs, file);
2697    if (err) {
2698        file->flags |= LFS_F_ERRED;
2699        LFS_TRACE("lfs_file_sync -> %d", err);
2700        return err;
2701    }
2702
2703    if ((file->flags & LFS_F_DIRTY) && !lfs_pair_isnull(file->m.pair)) {
2704        // update dir entry
2705        uint16_t type;
2706        const void* buffer;
2707        lfs_size_t size;
2708        struct lfs_ctz ctz;
2709        if (file->flags & LFS_F_INLINE) {
2710            // inline the whole file
2711            type = LFS_TYPE_INLINESTRUCT;
2712            buffer = file->cache.buffer;
2713            size = file->ctz.size;
2714        } else {
2715            // update the ctz reference
2716            type = LFS_TYPE_CTZSTRUCT;
2717            // copy ctz so alloc will work during a relocate
2718            ctz = file->ctz;
2719            lfs_ctz_tole32(&ctz);
2720            buffer = &ctz;
2721            size = sizeof(ctz);
2722        }
2723
2724        // commit file data and attributes
2725        err = lfs_dir_commit(
2726            lfs, &file->m,
2727            LFS_MKATTRS(
2728                {LFS_MKTAG(type, file->id, size), buffer},
2729                {LFS_MKTAG(LFS_FROM_USERATTRS, file->id, file->cfg->attr_count),
2730                 file->cfg->attrs}));
2731        if (err) {
2732            file->flags |= LFS_F_ERRED;
2733            LFS_TRACE("lfs_file_sync -> %d", err);
2734            return err;
2735        }
2736
2737        file->flags &= ~LFS_F_DIRTY;
2738    }
2739
2740    LFS_TRACE("lfs_file_sync -> %d", 0);
2741    return 0;
2742}
2743
2744lfs_ssize_t lfs_file_read(lfs_t* lfs, lfs_file_t* file, void* buffer,
2745                          lfs_size_t size) {
2746    LFS_TRACE("lfs_file_read(%p, %p, %p, %" PRIu32 ")", (void*)lfs, (void*)file,
2747              buffer, size);
2748    LFS_ASSERT(file->flags & LFS_F_OPENED);
2749    LFS_ASSERT((file->flags & 3) != LFS_O_WRONLY);
2750
2751    uint8_t* data = buffer;
2752    lfs_size_t nsize = size;
2753
2754    if (file->flags & LFS_F_WRITING) {
2755        // flush out any writes
2756        int err = lfs_file_flush(lfs, file);
2757        if (err) {
2758            LFS_TRACE("lfs_file_read -> %d", err);
2759            return err;
2760        }
2761    }
2762
2763    if (file->pos >= file->ctz.size) {
2764        // eof if past end
2765        LFS_TRACE("lfs_file_read -> %d", 0);
2766        return 0;
2767    }
2768
2769    size = lfs_min(size, file->ctz.size - file->pos);
2770    nsize = size;
2771
2772    while (nsize > 0) {
2773        // check if we need a new block
2774        if (!(file->flags & LFS_F_READING) ||
2775            file->off == lfs->cfg->block_size) {
2776            if (!(file->flags & LFS_F_INLINE)) {
2777                int err = lfs_ctz_find(lfs, NULL, &file->cache, file->ctz.head,
2778                                       file->ctz.size, file->pos, &file->block,
2779                                       &file->off);
2780                if (err) {
2781                    LFS_TRACE("lfs_file_read -> %d", err);
2782                    return err;
2783                }
2784            } else {
2785                file->block = LFS_BLOCK_INLINE;
2786                file->off = file->pos;
2787            }
2788
2789            file->flags |= LFS_F_READING;
2790        }
2791
2792        // read as much as we can in current block
2793        lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off);
2794        if (file->flags & LFS_F_INLINE) {
2795            int err = lfs_dir_getread(
2796                lfs, &file->m, NULL, &file->cache, lfs->cfg->block_size,
2797                LFS_MKTAG(0xfff, 0x1ff, 0),
2798                LFS_MKTAG(LFS_TYPE_INLINESTRUCT, file->id, 0), file->off, data,
2799                diff);
2800            if (err) {
2801                LFS_TRACE("lfs_file_read -> %d", err);
2802                return err;
2803            }
2804        } else {
2805            int err = lfs_bd_read(lfs, NULL, &file->cache, lfs->cfg->block_size,
2806                                  file->block, file->off, data, diff);
2807            if (err) {
2808                LFS_TRACE("lfs_file_read -> %d", err);
2809                return err;
2810            }
2811        }
2812
2813        file->pos += diff;
2814        file->off += diff;
2815        data += diff;
2816        nsize -= diff;
2817    }
2818
2819    LFS_TRACE("lfs_file_read -> %" PRId32, size);
2820    return size;
2821}
2822
2823lfs_ssize_t lfs_file_write(lfs_t* lfs, lfs_file_t* file, const void* buffer,
2824                           lfs_size_t size) {
2825    LFS_TRACE("lfs_file_write(%p, %p, %p, %" PRIu32 ")", (void*)lfs,
2826              (void*)file, buffer, size);
2827    LFS_ASSERT(file->flags & LFS_F_OPENED);
2828    LFS_ASSERT((file->flags & 3) != LFS_O_RDONLY);
2829
2830    const uint8_t* data = buffer;
2831    lfs_size_t nsize = size;
2832
2833    if (file->flags & LFS_F_READING) {
2834        // drop any reads
2835        int err = lfs_file_flush(lfs, file);
2836        if (err) {
2837            LFS_TRACE("lfs_file_write -> %d", err);
2838            return err;
2839        }
2840    }
2841
2842    if ((file->flags & LFS_O_APPEND) && file->pos < file->ctz.size) {
2843        file->pos = file->ctz.size;
2844    }
2845
2846    if (file->pos + size > lfs->file_max) {
2847        // Larger than file limit?
2848        LFS_TRACE("lfs_file_write -> %d", LFS_ERR_FBIG);
2849        return LFS_ERR_FBIG;
2850    }
2851
2852    if (!(file->flags & LFS_F_WRITING) && file->pos > file->ctz.size) {
2853        // fill with zeros
2854        lfs_off_t pos = file->pos;
2855        file->pos = file->ctz.size;
2856
2857        while (file->pos < pos) {
2858            lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1);
2859            if (res < 0) {
2860                LFS_TRACE("lfs_file_write -> %" PRId32, res);
2861                return res;
2862            }
2863        }
2864    }
2865
2866    if ((file->flags & LFS_F_INLINE) &&
2867        lfs_max(file->pos + nsize, file->ctz.size) >
2868            lfs_min(0x3fe,
2869                    lfs_min(lfs->cfg->cache_size, lfs->cfg->block_size / 8))) {
2870        // inline file doesn't fit anymore
2871        int err = lfs_file_outline(lfs, file);
2872        if (err) {
2873            file->flags |= LFS_F_ERRED;
2874            LFS_TRACE("lfs_file_write -> %d", err);
2875            return err;
2876        }
2877    }
2878
2879    while (nsize > 0) {
2880        // check if we need a new block
2881        if (!(file->flags & LFS_F_WRITING) ||
2882            file->off == lfs->cfg->block_size) {
2883            if (!(file->flags & LFS_F_INLINE)) {
2884                if (!(file->flags & LFS_F_WRITING) && file->pos > 0) {
2885                    // find out which block we're extending from
2886                    int err = lfs_ctz_find(
2887                        lfs, NULL, &file->cache, file->ctz.head, file->ctz.size,
2888                        file->pos - 1, &file->block, &file->off);
2889                    if (err) {
2890                        file->flags |= LFS_F_ERRED;
2891                        LFS_TRACE("lfs_file_write -> %d", err);
2892                        return err;
2893                    }
2894
2895                    // mark cache as dirty since we may have read data into it
2896                    lfs_cache_zero(lfs, &file->cache);
2897                }
2898
2899                // extend file with new blocks
2900                lfs_alloc_ack(lfs);
2901                int err =
2902                    lfs_ctz_extend(lfs, &file->cache, &lfs->rcache, file->block,
2903                                   file->pos, &file->block, &file->off);
2904                if (err) {
2905                    file->flags |= LFS_F_ERRED;
2906                    LFS_TRACE("lfs_file_write -> %d", err);
2907                    return err;
2908                }
2909            } else {
2910                file->block = LFS_BLOCK_INLINE;
2911                file->off = file->pos;
2912            }
2913
2914            file->flags |= LFS_F_WRITING;
2915        }
2916
2917        // program as much as we can in current block
2918        lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off);
2919        while (true) {
2920            int err = lfs_bd_prog(lfs, &file->cache, &lfs->rcache, true,
2921                                  file->block, file->off, data, diff);
2922            if (err) {
2923                if (err == LFS_ERR_CORRUPT) {
2924                    goto relocate;
2925                }
2926                file->flags |= LFS_F_ERRED;
2927                LFS_TRACE("lfs_file_write -> %d", err);
2928                return err;
2929            }
2930
2931            break;
2932        relocate:
2933            err = lfs_file_relocate(lfs, file);
2934            if (err) {
2935                file->flags |= LFS_F_ERRED;
2936                LFS_TRACE("lfs_file_write -> %d", err);
2937                return err;
2938            }
2939        }
2940
2941        file->pos += diff;
2942        file->off += diff;
2943        data += diff;
2944        nsize -= diff;
2945
2946        lfs_alloc_ack(lfs);
2947    }
2948
2949    file->flags &= ~LFS_F_ERRED;
2950    LFS_TRACE("lfs_file_write -> %" PRId32, size);
2951    return size;
2952}
2953
2954lfs_soff_t lfs_file_seek(lfs_t* lfs, lfs_file_t* file, lfs_soff_t off,
2955                         int whence) {
2956    LFS_TRACE("lfs_file_seek(%p, %p, %" PRId32 ", %d)", (void*)lfs, (void*)file,
2957              off, whence);
2958    LFS_ASSERT(file->flags & LFS_F_OPENED);
2959
2960    // write out everything beforehand, may be noop if rdonly
2961    int err = lfs_file_flush(lfs, file);
2962    if (err) {
2963        LFS_TRACE("lfs_file_seek -> %d", err);
2964        return err;
2965    }
2966
2967    // find new pos
2968    lfs_off_t npos = file->pos;
2969    if (whence == LFS_SEEK_SET) {
2970        npos = off;
2971    } else if (whence == LFS_SEEK_CUR) {
2972        npos = file->pos + off;
2973    } else if (whence == LFS_SEEK_END) {
2974        npos = file->ctz.size + off;
2975    }
2976
2977    if (npos > lfs->file_max) {
2978        // file position out of range
2979        LFS_TRACE("lfs_file_seek -> %d", LFS_ERR_INVAL);
2980        return LFS_ERR_INVAL;
2981    }
2982
2983    // update pos
2984    file->pos = npos;
2985    LFS_TRACE("lfs_file_seek -> %" PRId32, npos);
2986    return npos;
2987}
2988
2989int lfs_file_truncate(lfs_t* lfs, lfs_file_t* file, lfs_off_t size) {
2990    LFS_TRACE("lfs_file_truncate(%p, %p, %" PRIu32 ")", (void*)lfs, (void*)file,
2991              size);
2992    LFS_ASSERT(file->flags & LFS_F_OPENED);
2993    LFS_ASSERT((file->flags & 3) != LFS_O_RDONLY);
2994
2995    if (size > LFS_FILE_MAX) {
2996        LFS_TRACE("lfs_file_truncate -> %d", LFS_ERR_INVAL);
2997        return LFS_ERR_INVAL;
2998    }
2999
3000    lfs_off_t pos = file->pos;
3001    lfs_off_t oldsize = lfs_file_size(lfs, file);
3002    if (size < oldsize) {
3003        // need to flush since directly changing metadata
3004        int err = lfs_file_flush(lfs, file);
3005        if (err) {
3006            LFS_TRACE("lfs_file_truncate -> %d", err);
3007            return err;
3008        }
3009
3010        // lookup new head in ctz skip list
3011        err = lfs_ctz_find(lfs, NULL, &file->cache, file->ctz.head,
3012                           file->ctz.size, size, &file->block, &file->off);
3013        if (err) {
3014            LFS_TRACE("lfs_file_truncate -> %d", err);
3015            return err;
3016        }
3017
3018        file->ctz.head = file->block;
3019        file->ctz.size = size;
3020        file->flags |= LFS_F_DIRTY | LFS_F_READING;
3021    } else if (size > oldsize) {
3022        // flush+seek if not already at end
3023        if (file->pos != oldsize) {
3024            lfs_soff_t res = lfs_file_seek(lfs, file, 0, LFS_SEEK_END);
3025            if (res < 0) {
3026                LFS_TRACE("lfs_file_truncate -> %" PRId32, res);
3027                return (int)res;
3028            }
3029        }
3030
3031        // fill with zeros
3032        while (file->pos < size) {
3033            lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1);
3034            if (res < 0) {
3035                LFS_TRACE("lfs_file_truncate -> %" PRId32, res);
3036                return (int)res;
3037            }
3038        }
3039    }
3040
3041    // restore pos
3042    lfs_soff_t res = lfs_file_seek(lfs, file, pos, LFS_SEEK_SET);
3043    if (res < 0) {
3044        LFS_TRACE("lfs_file_truncate -> %" PRId32, res);
3045        return (int)res;
3046    }
3047
3048    LFS_TRACE("lfs_file_truncate -> %d", 0);
3049    return 0;
3050}
3051
3052lfs_soff_t lfs_file_tell(lfs_t* lfs, lfs_file_t* file) {
3053    LFS_TRACE("lfs_file_tell(%p, %p)", (void*)lfs, (void*)file);
3054    LFS_ASSERT(file->flags & LFS_F_OPENED);
3055    (void)lfs;
3056    LFS_TRACE("lfs_file_tell -> %" PRId32, file->pos);
3057    return file->pos;
3058}
3059
3060int lfs_file_rewind(lfs_t* lfs, lfs_file_t* file) {
3061    LFS_TRACE("lfs_file_rewind(%p, %p)", (void*)lfs, (void*)file);
3062    lfs_soff_t res = lfs_file_seek(lfs, file, 0, LFS_SEEK_SET);
3063    if (res < 0) {
3064        LFS_TRACE("lfs_file_rewind -> %" PRId32, res);
3065        return (int)res;
3066    }
3067
3068    LFS_TRACE("lfs_file_rewind -> %d", 0);
3069    return 0;
3070}
3071
3072lfs_soff_t lfs_file_size(lfs_t* lfs, lfs_file_t* file) {
3073    LFS_TRACE("lfs_file_size(%p, %p)", (void*)lfs, (void*)file);
3074    LFS_ASSERT(file->flags & LFS_F_OPENED);
3075    (void)lfs;
3076    if (file->flags & LFS_F_WRITING) {
3077        LFS_TRACE("lfs_file_size -> %" PRId32,
3078                  lfs_max(file->pos, file->ctz.size));
3079        return lfs_max(file->pos, file->ctz.size);
3080    } else {
3081        LFS_TRACE("lfs_file_size -> %" PRId32, file->ctz.size);
3082        return file->ctz.size;
3083    }
3084}
3085
3086/// General fs operations ///
3087int lfs_stat(lfs_t* lfs, const char* path, struct lfs_info* info) {
3088    LFS_TRACE("lfs_stat(%p, \"%s\", %p)", (void*)lfs, path, (void*)info);
3089    lfs_mdir_t cwd;
3090    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path, NULL);
3091    if (tag < 0) {
3092        LFS_TRACE("lfs_stat -> %" PRId32, tag);
3093        return (int)tag;
3094    }
3095
3096    int err = lfs_dir_getinfo(lfs, &cwd, lfs_tag_id(tag), info);
3097    LFS_TRACE("lfs_stat -> %d", err);
3098    return err;
3099}
3100
3101int lfs_remove(lfs_t* lfs, const char* path) {
3102    LFS_TRACE("lfs_remove(%p, \"%s\")", (void*)lfs, path);
3103    // deorphan if we haven't yet, needed at most once after poweron
3104    int err = lfs_fs_forceconsistency(lfs);
3105    if (err) {
3106        LFS_TRACE("lfs_remove -> %d", err);
3107        return err;
3108    }
3109
3110    lfs_mdir_t cwd;
3111    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path, NULL);
3112    if (tag < 0 || lfs_tag_id(tag) == 0x3ff) {
3113        LFS_TRACE("lfs_remove -> %" PRId32, (tag < 0) ? tag : LFS_ERR_INVAL);
3114        return (tag < 0) ? (int)tag : LFS_ERR_INVAL;
3115    }
3116
3117    struct lfs_mlist dir;
3118    dir.next = lfs->mlist;
3119    if (lfs_tag_type3(tag) == LFS_TYPE_DIR) {
3120        // must be empty before removal
3121        lfs_block_t pair[2];
3122        lfs_stag_t res =
3123            lfs_dir_get(lfs, &cwd, LFS_MKTAG(0x700, 0x3ff, 0),
3124                        LFS_MKTAG(LFS_TYPE_STRUCT, lfs_tag_id(tag), 8), pair);
3125        if (res < 0) {
3126            LFS_TRACE("lfs_remove -> %" PRId32, res);
3127            return (int)res;
3128        }
3129        lfs_pair_fromle32(pair);
3130
3131        err = lfs_dir_fetch(lfs, &dir.m, pair);
3132        if (err) {
3133            LFS_TRACE("lfs_remove -> %d", err);
3134            return err;
3135        }
3136
3137        if (dir.m.count > 0 || dir.m.split) {
3138            LFS_TRACE("lfs_remove -> %d", LFS_ERR_NOTEMPTY);
3139            return LFS_ERR_NOTEMPTY;
3140        }
3141
3142        // mark fs as orphaned
3143        lfs_fs_preporphans(lfs, +1);
3144
3145        // I know it's crazy but yes, dir can be changed by our parent's
3146        // commit (if predecessor is child)
3147        dir.type = 0;
3148        dir.id = 0;
3149        lfs->mlist = &dir;
3150    }
3151
3152    // delete the entry
3153    err = lfs_dir_commit(
3154        lfs, &cwd,
3155        LFS_MKATTRS({LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(tag), 0), NULL}));
3156    if (err) {
3157        lfs->mlist = dir.next;
3158        LFS_TRACE("lfs_remove -> %d", err);
3159        return err;
3160    }
3161
3162    lfs->mlist = dir.next;
3163    if (lfs_tag_type3(tag) == LFS_TYPE_DIR) {
3164        // fix orphan
3165        lfs_fs_preporphans(lfs, -1);
3166
3167        err = lfs_fs_pred(lfs, dir.m.pair, &cwd);
3168        if (err) {
3169            LFS_TRACE("lfs_remove -> %d", err);
3170            return err;
3171        }
3172
3173        err = lfs_dir_drop(lfs, &cwd, &dir.m);
3174        if (err) {
3175            LFS_TRACE("lfs_remove -> %d", err);
3176            return err;
3177        }
3178    }
3179
3180    LFS_TRACE("lfs_remove -> %d", 0);
3181    return 0;
3182}
3183
3184int lfs_rename(lfs_t* lfs, const char* oldpath, const char* newpath) {
3185    LFS_TRACE("lfs_rename(%p, \"%s\", \"%s\")", (void*)lfs, oldpath, newpath);
3186
3187    // deorphan if we haven't yet, needed at most once after poweron
3188    int err = lfs_fs_forceconsistency(lfs);
3189    if (err) {
3190        LFS_TRACE("lfs_rename -> %d", err);
3191        return err;
3192    }
3193
3194    // find old entry
3195    lfs_mdir_t oldcwd;
3196    lfs_stag_t oldtag = lfs_dir_find(lfs, &oldcwd, &oldpath, NULL);
3197    if (oldtag < 0 || lfs_tag_id(oldtag) == 0x3ff) {
3198        LFS_TRACE("lfs_rename -> %" PRId32,
3199                  (oldtag < 0) ? oldtag : LFS_ERR_INVAL);
3200        return (oldtag < 0) ? (int)oldtag : LFS_ERR_INVAL;
3201    }
3202
3203    // find new entry
3204    lfs_mdir_t newcwd;
3205    uint16_t newid;
3206    lfs_stag_t prevtag = lfs_dir_find(lfs, &newcwd, &newpath, &newid);
3207    if ((prevtag < 0 || lfs_tag_id(prevtag) == 0x3ff) &&
3208        !(prevtag == LFS_ERR_NOENT && newid != 0x3ff)) {
3209        LFS_TRACE("lfs_rename -> %" PRId32,
3210                  (prevtag < 0) ? prevtag : LFS_ERR_INVAL);
3211        return (prevtag < 0) ? (int)prevtag : LFS_ERR_INVAL;
3212    }
3213
3214    // if we're in the same pair there's a few special cases...
3215    bool samepair = (lfs_pair_cmp(oldcwd.pair, newcwd.pair) == 0);
3216    uint16_t newoldid = lfs_tag_id(oldtag);
3217
3218    struct lfs_mlist prevdir;
3219    prevdir.next = lfs->mlist;
3220    if (prevtag == LFS_ERR_NOENT) {
3221        // check that name fits
3222        lfs_size_t nlen = strlen(newpath);
3223        if (nlen > lfs->name_max) {
3224            LFS_TRACE("lfs_rename -> %d", LFS_ERR_NAMETOOLONG);
3225            return LFS_ERR_NAMETOOLONG;
3226        }
3227
3228        // there is a small chance we are being renamed in the same
3229        // directory/ to an id less than our old id, the global update
3230        // to handle this is a bit messy
3231        if (samepair && newid <= newoldid) {
3232            newoldid += 1;
3233        }
3234    } else if (lfs_tag_type3(prevtag) != lfs_tag_type3(oldtag)) {
3235        LFS_TRACE("lfs_rename -> %d", LFS_ERR_ISDIR);
3236        return LFS_ERR_ISDIR;
3237    } else if (samepair && newid == newoldid) {
3238        // we're renaming to ourselves??
3239        LFS_TRACE("lfs_rename -> %d", 0);
3240        return 0;
3241    } else if (lfs_tag_type3(prevtag) == LFS_TYPE_DIR) {
3242        // must be empty before removal
3243        lfs_block_t prevpair[2];
3244        lfs_stag_t res =
3245            lfs_dir_get(lfs, &newcwd, LFS_MKTAG(0x700, 0x3ff, 0),
3246                        LFS_MKTAG(LFS_TYPE_STRUCT, newid, 8), prevpair);
3247        if (res < 0) {
3248            LFS_TRACE("lfs_rename -> %" PRId32, res);
3249            return (int)res;
3250        }
3251        lfs_pair_fromle32(prevpair);
3252
3253        // must be empty before removal
3254        err = lfs_dir_fetch(lfs, &prevdir.m, prevpair);
3255        if (err) {
3256            LFS_TRACE("lfs_rename -> %d", err);
3257            return err;
3258        }
3259
3260        if (prevdir.m.count > 0 || prevdir.m.split) {
3261            LFS_TRACE("lfs_rename -> %d", LFS_ERR_NOTEMPTY);
3262            return LFS_ERR_NOTEMPTY;
3263        }
3264
3265        // mark fs as orphaned
3266        lfs_fs_preporphans(lfs, +1);
3267
3268        // I know it's crazy but yes, dir can be changed by our parent's
3269        // commit (if predecessor is child)
3270        prevdir.type = 0;
3271        prevdir.id = 0;
3272        lfs->mlist = &prevdir;
3273    }
3274
3275    if (!samepair) {
3276        lfs_fs_prepmove(lfs, newoldid, oldcwd.pair);
3277    }
3278
3279    // move over all attributes
3280    err = lfs_dir_commit(
3281        lfs, &newcwd,
3282        LFS_MKATTRS(
3283            {LFS_MKTAG_IF(prevtag != LFS_ERR_NOENT, LFS_TYPE_DELETE, newid, 0),
3284             NULL},
3285            {LFS_MKTAG(LFS_TYPE_CREATE, newid, 0), NULL},
3286            {LFS_MKTAG(lfs_tag_type3(oldtag), newid, strlen(newpath)), newpath},
3287            {LFS_MKTAG(LFS_FROM_MOVE, newid, lfs_tag_id(oldtag)), &oldcwd},
3288            {LFS_MKTAG_IF(samepair, LFS_TYPE_DELETE, newoldid, 0), NULL}));
3289    if (err) {
3290        lfs->mlist = prevdir.next;
3291        LFS_TRACE("lfs_rename -> %d", err);
3292        return err;
3293    }
3294
3295    // let commit clean up after move (if we're different! otherwise move
3296    // logic already fixed it for us)
3297    if (!samepair && lfs_gstate_hasmove(&lfs->gstate)) {
3298        // prep gstate and delete move id
3299        lfs_fs_prepmove(lfs, 0x3ff, NULL);
3300        err = lfs_dir_commit(
3301            lfs, &oldcwd,
3302            LFS_MKATTRS(
3303                {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(oldtag), 0), NULL}));
3304        if (err) {
3305            lfs->mlist = prevdir.next;
3306            LFS_TRACE("lfs_rename -> %d", err);
3307            return err;
3308        }
3309    }
3310
3311    lfs->mlist = prevdir.next;
3312    if (prevtag != LFS_ERR_NOENT && lfs_tag_type3(prevtag) == LFS_TYPE_DIR) {
3313        // fix orphan
3314        lfs_fs_preporphans(lfs, -1);
3315
3316        err = lfs_fs_pred(lfs, prevdir.m.pair, &newcwd);
3317        if (err) {
3318            LFS_TRACE("lfs_rename -> %d", err);
3319            return err;
3320        }
3321
3322        err = lfs_dir_drop(lfs, &newcwd, &prevdir.m);
3323        if (err) {
3324            LFS_TRACE("lfs_rename -> %d", err);
3325            return err;
3326        }
3327    }
3328
3329    LFS_TRACE("lfs_rename -> %d", 0);
3330    return 0;
3331}
3332
3333lfs_ssize_t lfs_getattr(lfs_t* lfs, const char* path, uint8_t type,
3334                        void* buffer, lfs_size_t size) {
3335    LFS_TRACE("lfs_getattr(%p, \"%s\", %" PRIu8 ", %p, %" PRIu32 ")",
3336              (void*)lfs, path, type, buffer, size);
3337    lfs_mdir_t cwd;
3338    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path, NULL);
3339    if (tag < 0) {
3340        LFS_TRACE("lfs_getattr -> %" PRId32, tag);
3341        return tag;
3342    }
3343
3344    uint16_t id = lfs_tag_id(tag);
3345    if (id == 0x3ff) {
3346        // special case for root
3347        id = 0;
3348        int err = lfs_dir_fetch(lfs, &cwd, lfs->root);
3349        if (err) {
3350            LFS_TRACE("lfs_getattr -> %d", err);
3351            return err;
3352        }
3353    }
3354
3355    tag = lfs_dir_get(
3356        lfs, &cwd, LFS_MKTAG(0x7ff, 0x3ff, 0),
3357        LFS_MKTAG(LFS_TYPE_USERATTR + type, id, lfs_min(size, lfs->attr_max)),
3358        buffer);
3359    if (tag < 0) {
3360        if (tag == LFS_ERR_NOENT) {
3361            LFS_TRACE("lfs_getattr -> %d", LFS_ERR_NOATTR);
3362            return LFS_ERR_NOATTR;
3363        }
3364
3365        LFS_TRACE("lfs_getattr -> %" PRId32, tag);
3366        return tag;
3367    }
3368
3369    size = lfs_tag_size(tag);
3370    LFS_TRACE("lfs_getattr -> %" PRId32, size);
3371    return size;
3372}
3373
3374static int lfs_commitattr(lfs_t* lfs, const char* path, uint8_t type,
3375                          const void* buffer, lfs_size_t size) {
3376    lfs_mdir_t cwd;
3377    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path, NULL);
3378    if (tag < 0) {
3379        return tag;
3380    }
3381
3382    uint16_t id = lfs_tag_id(tag);
3383    if (id == 0x3ff) {
3384        // special case for root
3385        id = 0;
3386        int err = lfs_dir_fetch(lfs, &cwd, lfs->root);
3387        if (err) {
3388            return err;
3389        }
3390    }
3391
3392    return lfs_dir_commit(
3393        lfs, &cwd,
3394        LFS_MKATTRS({LFS_MKTAG(LFS_TYPE_USERATTR + type, id, size), buffer}));
3395}
3396
3397int lfs_setattr(lfs_t* lfs, const char* path, uint8_t type, const void* buffer,
3398                lfs_size_t size) {
3399    LFS_TRACE("lfs_setattr(%p, \"%s\", %" PRIu8 ", %p, %" PRIu32 ")",
3400              (void*)lfs, path, type, buffer, size);
3401    if (size > lfs->attr_max) {
3402        LFS_TRACE("lfs_setattr -> %d", LFS_ERR_NOSPC);
3403        return LFS_ERR_NOSPC;
3404    }
3405
3406    int err = lfs_commitattr(lfs, path, type, buffer, size);
3407    LFS_TRACE("lfs_setattr -> %d", err);
3408    return err;
3409}
3410
3411int lfs_removeattr(lfs_t* lfs, const char* path, uint8_t type) {
3412    LFS_TRACE("lfs_removeattr(%p, \"%s\", %" PRIu8 ")", (void*)lfs, path, type);
3413    int err = lfs_commitattr(lfs, path, type, NULL, 0x3ff);
3414    LFS_TRACE("lfs_removeattr -> %d", err);
3415    return err;
3416}
3417
3418/// Filesystem operations ///
3419static int lfs_init(lfs_t* lfs, const struct lfs_config* cfg) {
3420    lfs->cfg = cfg;
3421    int err = 0;
3422
3423    // validate that the lfs-cfg sizes were initiated properly before
3424    // performing any arithmetic logics with them
3425    LFS_ASSERT(lfs->cfg->read_size != 0);
3426    LFS_ASSERT(lfs->cfg->prog_size != 0);
3427    LFS_ASSERT(lfs->cfg->cache_size != 0);
3428
3429    // check that block size is a multiple of cache size is a multiple
3430    // of prog and read sizes
3431    LFS_ASSERT(lfs->cfg->cache_size % lfs->cfg->read_size == 0);
3432    LFS_ASSERT(lfs->cfg->cache_size % lfs->cfg->prog_size == 0);
3433    LFS_ASSERT(lfs->cfg->block_size % lfs->cfg->cache_size == 0);
3434
3435    // check that the block size is large enough to fit ctz pointers
3436    LFS_ASSERT(4 * lfs_npw2(0xffffffff / (lfs->cfg->block_size - 2 * 4)) <=
3437               lfs->cfg->block_size);
3438
3439    // block_cycles = 0 is no longer supported.
3440    //
3441    // block_cycles is the number of erase cycles before littlefs evicts
3442    // metadata logs as a part of wear leveling. Suggested values are in the
3443    // range of 100-1000, or set block_cycles to -1 to disable block-level
3444    // wear-leveling.
3445    LFS_ASSERT(lfs->cfg->block_cycles != 0);
3446
3447    // setup read cache
3448    if (lfs->cfg->read_buffer) {
3449        lfs->rcache.buffer = lfs->cfg->read_buffer;
3450    } else {
3451        lfs->rcache.buffer = lfs_malloc(lfs->cfg->cache_size);
3452        if (!lfs->rcache.buffer) {
3453            err = LFS_ERR_NOMEM;
3454            goto cleanup;
3455        }
3456    }
3457
3458    // setup program cache
3459    if (lfs->cfg->prog_buffer) {
3460        lfs->pcache.buffer = lfs->cfg->prog_buffer;
3461    } else {
3462        lfs->pcache.buffer = lfs_malloc(lfs->cfg->cache_size);
3463        if (!lfs->pcache.buffer) {
3464            err = LFS_ERR_NOMEM;
3465            goto cleanup;
3466        }
3467    }
3468
3469    // zero to avoid information leaks
3470    lfs_cache_zero(lfs, &lfs->rcache);
3471    lfs_cache_zero(lfs, &lfs->pcache);
3472
3473    // setup lookahead, must be multiple of 64-bits, 32-bit aligned
3474    LFS_ASSERT(lfs->cfg->lookahead_size > 0);
3475    LFS_ASSERT(lfs->cfg->lookahead_size % 8 == 0 &&
3476               (uintptr_t)lfs->cfg->lookahead_buffer % 4 == 0);
3477    if (lfs->cfg->lookahead_buffer) {
3478        lfs->free.buffer = lfs->cfg->lookahead_buffer;
3479    } else {
3480        lfs->free.buffer = lfs_malloc(lfs->cfg->lookahead_size);
3481        if (!lfs->free.buffer) {
3482            err = LFS_ERR_NOMEM;
3483            goto cleanup;
3484        }
3485    }
3486
3487    // check that the size limits are sane
3488    LFS_ASSERT(lfs->cfg->name_max <= LFS_NAME_MAX);
3489    lfs->name_max = lfs->cfg->name_max;
3490    if (!lfs->name_max) {
3491        lfs->name_max = LFS_NAME_MAX;
3492    }
3493
3494    LFS_ASSERT(lfs->cfg->file_max <= LFS_FILE_MAX);
3495    lfs->file_max = lfs->cfg->file_max;
3496    if (!lfs->file_max) {
3497        lfs->file_max = LFS_FILE_MAX;
3498    }
3499
3500    LFS_ASSERT(lfs->cfg->attr_max <= LFS_ATTR_MAX);
3501    lfs->attr_max = lfs->cfg->attr_max;
3502    if (!lfs->attr_max) {
3503        lfs->attr_max = LFS_ATTR_MAX;
3504    }
3505
3506    // setup default state
3507    lfs->root[0] = LFS_BLOCK_NULL;
3508    lfs->root[1] = LFS_BLOCK_NULL;
3509    lfs->mlist = NULL;
3510    lfs->seed = 0;
3511    lfs->gdisk = (lfs_gstate_t){0};
3512    lfs->gstate = (lfs_gstate_t){0};
3513    lfs->gdelta = (lfs_gstate_t){0};
3514#ifdef LFS_MIGRATE
3515    lfs->lfs1 = NULL;
3516#endif
3517
3518    return 0;
3519
3520cleanup:
3521    lfs_deinit(lfs);
3522    return err;
3523}
3524
3525static int lfs_deinit(lfs_t* lfs) {
3526    // free allocated memory
3527    if (!lfs->cfg->read_buffer) {
3528        lfs_free(lfs->rcache.buffer);
3529    }
3530
3531    if (!lfs->cfg->prog_buffer) {
3532        lfs_free(lfs->pcache.buffer);
3533    }
3534
3535    if (!lfs->cfg->lookahead_buffer) {
3536        lfs_free(lfs->free.buffer);
3537    }
3538
3539    return 0;
3540}
3541
3542int lfs_format(lfs_t* lfs, const struct lfs_config* cfg) {
3543    LFS_TRACE("lfs_format(%p, %p {.context=%p, "
3544              ".read=%p, .prog=%p, .erase=%p, .sync=%p, "
3545              ".read_size=%" PRIu32 ", .prog_size=%" PRIu32 ", "
3546              ".block_size=%" PRIu32 ", .block_count=%" PRIu32 ", "
3547              ".block_cycles=%" PRIu32 ", .cache_size=%" PRIu32 ", "
3548              ".lookahead_size=%" PRIu32 ", .read_buffer=%p, "
3549              ".prog_buffer=%p, .lookahead_buffer=%p, "
3550              ".name_max=%" PRIu32 ", .file_max=%" PRIu32 ", "
3551              ".attr_max=%" PRIu32 "})",
3552              (void*)lfs, (void*)cfg, cfg->context, (void*)(uintptr_t)cfg->read,
3553              (void*)(uintptr_t)cfg->prog, (void*)(uintptr_t)cfg->erase,
3554              (void*)(uintptr_t)cfg->sync, cfg->read_size, cfg->prog_size,
3555              cfg->block_size, cfg->block_count, cfg->block_cycles,
3556              cfg->cache_size, cfg->lookahead_size, cfg->read_buffer,
3557              cfg->prog_buffer, cfg->lookahead_buffer, cfg->name_max,
3558              cfg->file_max, cfg->attr_max);
3559    int err = 0;
3560    {
3561        err = lfs_init(lfs, cfg);
3562        if (err) {
3563            LFS_TRACE("lfs_format -> %d", err);
3564            return err;
3565        }
3566
3567        // create free lookahead
3568        memset(lfs->free.buffer, 0, lfs->cfg->lookahead_size);
3569        lfs->free.off = 0;
3570        lfs->free.size =
3571            lfs_min(8 * lfs->cfg->lookahead_size, lfs->cfg->block_count);
3572        lfs->free.i = 0;
3573        lfs_alloc_ack(lfs);
3574
3575        // create root dir
3576        lfs_mdir_t root;
3577        err = lfs_dir_alloc(lfs, &root);
3578        if (err) {
3579            goto cleanup;
3580        }
3581
3582        // write one superblock
3583        lfs_superblock_t superblock = {
3584            .version = LFS_DISK_VERSION,
3585            .block_size = lfs->cfg->block_size,
3586            .block_count = lfs->cfg->block_count,
3587            .name_max = lfs->name_max,
3588            .file_max = lfs->file_max,
3589            .attr_max = lfs->attr_max,
3590        };
3591
3592        lfs_superblock_tole32(&superblock);
3593        err = lfs_dir_commit(
3594            lfs, &root,
3595            LFS_MKATTRS(
3596                {LFS_MKTAG(LFS_TYPE_CREATE, 0, 0), NULL},
3597                {LFS_MKTAG(LFS_TYPE_SUPERBLOCK, 0, 8), "littlefs"},
3598                {LFS_MKTAG(LFS_TYPE_INLINESTRUCT, 0, sizeof(superblock)),
3599                 &superblock}));
3600        if (err) {
3601            goto cleanup;
3602        }
3603
3604        // sanity check that fetch works
3605        err = lfs_dir_fetch(lfs, &root, (const lfs_block_t[2]){0, 1});
3606        if (err) {
3607            goto cleanup;
3608        }
3609
3610        // force compaction to prevent accidentally mounting any
3611        // older version of littlefs that may live on disk
3612        root.erased = false;
3613        err = lfs_dir_commit(lfs, &root, NULL, 0);
3614        if (err) {
3615            goto cleanup;
3616        }
3617    }
3618
3619cleanup:
3620    lfs_deinit(lfs);
3621    LFS_TRACE("lfs_format -> %d", err);
3622    return err;
3623}
3624
3625int lfs_mount(lfs_t* lfs, const struct lfs_config* cfg) {
3626    LFS_TRACE("lfs_mount(%p, %p {.context=%p, "
3627              ".read=%p, .prog=%p, .erase=%p, .sync=%p, "
3628              ".read_size=%" PRIu32 ", .prog_size=%" PRIu32 ", "
3629              ".block_size=%" PRIu32 ", .block_count=%" PRIu32 ", "
3630              ".block_cycles=%" PRIu32 ", .cache_size=%" PRIu32 ", "
3631              ".lookahead_size=%" PRIu32 ", .read_buffer=%p, "
3632              ".prog_buffer=%p, .lookahead_buffer=%p, "
3633              ".name_max=%" PRIu32 ", .file_max=%" PRIu32 ", "
3634              ".attr_max=%" PRIu32 "})",
3635              (void*)lfs, (void*)cfg, cfg->context, (void*)(uintptr_t)cfg->read,
3636              (void*)(uintptr_t)cfg->prog, (void*)(uintptr_t)cfg->erase,
3637              (void*)(uintptr_t)cfg->sync, cfg->read_size, cfg->prog_size,
3638              cfg->block_size, cfg->block_count, cfg->block_cycles,
3639              cfg->cache_size, cfg->lookahead_size, cfg->read_buffer,
3640              cfg->prog_buffer, cfg->lookahead_buffer, cfg->name_max,
3641              cfg->file_max, cfg->attr_max);
3642    int err = lfs_init(lfs, cfg);
3643    if (err) {
3644        LFS_TRACE("lfs_mount -> %d", err);
3645        return err;
3646    }
3647
3648    // scan directory blocks for superblock and any global updates
3649    lfs_mdir_t dir = {.tail = {0, 1}};
3650    lfs_block_t cycle = 0;
3651    while (!lfs_pair_isnull(dir.tail)) {
3652        if (cycle >= lfs->cfg->block_count / 2) {
3653            // loop detected
3654            err = LFS_ERR_CORRUPT;
3655            goto cleanup;
3656        }
3657        cycle += 1;
3658
3659        // fetch next block in tail list
3660        lfs_stag_t tag = lfs_dir_fetchmatch(
3661            lfs, &dir, dir.tail, LFS_MKTAG(0x7ff, 0x3ff, 0),
3662            LFS_MKTAG(LFS_TYPE_SUPERBLOCK, 0, 8), NULL, lfs_dir_find_match,
3663            &(struct lfs_dir_find_match){lfs, "littlefs", 8});
3664        if (tag < 0) {
3665            err = tag;
3666            goto cleanup;
3667        }
3668
3669        // has superblock?
3670        if (tag && !lfs_tag_isdelete(tag)) {
3671            // update root
3672            lfs->root[0] = dir.pair[0];
3673            lfs->root[1] = dir.pair[1];
3674
3675            // grab superblock
3676            lfs_superblock_t superblock;
3677            tag = lfs_dir_get(
3678                lfs, &dir, LFS_MKTAG(0x7ff, 0x3ff, 0),
3679                LFS_MKTAG(LFS_TYPE_INLINESTRUCT, 0, sizeof(superblock)),
3680                &superblock);
3681            if (tag < 0) {
3682                err = tag;
3683                goto cleanup;
3684            }
3685            lfs_superblock_fromle32(&superblock);
3686
3687            // check version
3688            uint16_t major_version = (0xffff & (superblock.version >> 16));
3689            uint16_t minor_version = (0xffff & (superblock.version >> 0));
3690            if ((major_version != LFS_DISK_VERSION_MAJOR ||
3691                 minor_version > LFS_DISK_VERSION_MINOR)) {
3692                LFS_ERROR("Invalid version v%" PRIu16 ".%" PRIu16,
3693                          major_version, minor_version);
3694                err = LFS_ERR_INVAL;
3695                goto cleanup;
3696            }
3697
3698            // check superblock configuration
3699            if (superblock.name_max) {
3700                if (superblock.name_max > lfs->name_max) {
3701                    LFS_ERROR("Unsupported name_max (%" PRIu32 " > %" PRIu32
3702                              ")",
3703                              superblock.name_max, lfs->name_max);
3704                    err = LFS_ERR_INVAL;
3705                    goto cleanup;
3706                }
3707
3708                lfs->name_max = superblock.name_max;
3709            }
3710
3711            if (superblock.file_max) {
3712                if (superblock.file_max > lfs->file_max) {
3713                    LFS_ERROR("Unsupported file_max (%" PRIu32 " > %" PRIu32
3714                              ")",
3715                              superblock.file_max, lfs->file_max);
3716                    err = LFS_ERR_INVAL;
3717                    goto cleanup;
3718                }
3719
3720                lfs->file_max = superblock.file_max;
3721            }
3722
3723            if (superblock.attr_max) {
3724                if (superblock.attr_max > lfs->attr_max) {
3725                    LFS_ERROR("Unsupported attr_max (%" PRIu32 " > %" PRIu32
3726                              ")",
3727                              superblock.attr_max, lfs->attr_max);
3728                    err = LFS_ERR_INVAL;
3729                    goto cleanup;
3730                }
3731
3732                lfs->attr_max = superblock.attr_max;
3733            }
3734        }
3735
3736        // has gstate?
3737        err = lfs_dir_getgstate(lfs, &dir, &lfs->gstate);
3738        if (err) {
3739            goto cleanup;
3740        }
3741    }
3742
3743    // found superblock?
3744    if (lfs_pair_isnull(lfs->root)) {
3745        err = LFS_ERR_INVAL;
3746        goto cleanup;
3747    }
3748
3749    // update littlefs with gstate
3750    if (!lfs_gstate_iszero(&lfs->gstate)) {
3751        LFS_DEBUG("Found pending gstate 0x%08" PRIx32 "%08" PRIx32 "%08" PRIx32,
3752                  lfs->gstate.tag, lfs->gstate.pair[0], lfs->gstate.pair[1]);
3753    }
3754    lfs->gstate.tag += !lfs_tag_isvalid(lfs->gstate.tag);
3755    lfs->gdisk = lfs->gstate;
3756
3757    // setup free lookahead
3758    lfs_alloc_reset(lfs);
3759
3760    LFS_TRACE("lfs_mount -> %d", 0);
3761    return 0;
3762
3763cleanup:
3764    lfs_unmount(lfs);
3765    LFS_TRACE("lfs_mount -> %d", err);
3766    return err;
3767}
3768
3769int lfs_unmount(lfs_t* lfs) {
3770    LFS_TRACE("lfs_unmount(%p)", (void*)lfs);
3771    int err = lfs_deinit(lfs);
3772    LFS_TRACE("lfs_unmount -> %d", err);
3773    return err;
3774}
3775
3776/// Filesystem filesystem operations ///
3777int lfs_fs_traverseraw(lfs_t* lfs, int (*cb)(void* data, lfs_block_t block),
3778                       void* data, bool includeorphans) {
3779    // iterate over metadata pairs
3780    lfs_mdir_t dir = {.tail = {0, 1}};
3781
3782#ifdef LFS_MIGRATE
3783    // also consider v1 blocks during migration
3784    if (lfs->lfs1) {
3785        int err = lfs1_traverse(lfs, cb, data);
3786        if (err) {
3787            return err;
3788        }
3789
3790        dir.tail[0] = lfs->root[0];
3791        dir.tail[1] = lfs->root[1];
3792    }
3793#endif
3794
3795    lfs_block_t cycle = 0;
3796    while (!lfs_pair_isnull(dir.tail)) {
3797        if (cycle >= lfs->cfg->block_count / 2) {
3798            // loop detected
3799            return LFS_ERR_CORRUPT;
3800        }
3801        cycle += 1;
3802
3803        for (int i = 0; i < 2; i++) {
3804            int err = cb(data, dir.tail[i]);
3805            if (err) {
3806                return err;
3807            }
3808        }
3809
3810        // iterate through ids in directory
3811        int err = lfs_dir_fetch(lfs, &dir, dir.tail);
3812        if (err) {
3813            return err;
3814        }
3815
3816        for (uint16_t id = 0; id < dir.count; id++) {
3817            struct lfs_ctz ctz;
3818            lfs_stag_t tag =
3819                lfs_dir_get(lfs, &dir, LFS_MKTAG(0x700, 0x3ff, 0),
3820                            LFS_MKTAG(LFS_TYPE_STRUCT, id, sizeof(ctz)), &ctz);
3821            if (tag < 0) {
3822                if (tag == LFS_ERR_NOENT) {
3823                    continue;
3824                }
3825                return tag;
3826            }
3827            lfs_ctz_fromle32(&ctz);
3828
3829            if (lfs_tag_type3(tag) == LFS_TYPE_CTZSTRUCT) {
3830                err = lfs_ctz_traverse(lfs, NULL, &lfs->rcache, ctz.head,
3831                                       ctz.size, cb, data);
3832                if (err) {
3833                    return err;
3834                }
3835            } else if (includeorphans &&
3836                       lfs_tag_type3(tag) == LFS_TYPE_DIRSTRUCT) {
3837                for (int i = 0; i < 2; i++) {
3838                    err = cb(data, (&ctz.head)[i]);
3839                    if (err) {
3840                        return err;
3841                    }
3842                }
3843            }
3844        }
3845    }
3846
3847    // iterate over any open files
3848    for (lfs_file_t* f = (lfs_file_t*)lfs->mlist; f; f = f->next) {
3849        if (f->type != LFS_TYPE_REG) {
3850            continue;
3851        }
3852
3853        if ((f->flags & LFS_F_DIRTY) && !(f->flags & LFS_F_INLINE)) {
3854            int err = lfs_ctz_traverse(lfs, &f->cache, &lfs->rcache,
3855                                       f->ctz.head, f->ctz.size, cb, data);
3856            if (err) {
3857                return err;
3858            }
3859        }
3860
3861        if ((f->flags & LFS_F_WRITING) && !(f->flags & LFS_F_INLINE)) {
3862            int err = lfs_ctz_traverse(lfs, &f->cache, &lfs->rcache, f->block,
3863                                       f->pos, cb, data);
3864            if (err) {
3865                return err;
3866            }
3867        }
3868    }
3869
3870    return 0;
3871}
3872
3873int lfs_fs_traverse(lfs_t* lfs, int (*cb)(void* data, lfs_block_t block),
3874                    void* data) {
3875    LFS_TRACE("lfs_fs_traverse(%p, %p, %p)", (void*)lfs, (void*)(uintptr_t)cb,
3876              data);
3877    int err = lfs_fs_traverseraw(lfs, cb, data, true);
3878    LFS_TRACE("lfs_fs_traverse -> %d", 0);
3879    return err;
3880}
3881
3882static int lfs_fs_pred(lfs_t* lfs, const lfs_block_t pair[2],
3883                       lfs_mdir_t* pdir) {
3884    // iterate over all directory directory entries
3885    pdir->tail[0] = 0;
3886    pdir->tail[1] = 1;
3887    lfs_block_t cycle = 0;
3888    while (!lfs_pair_isnull(pdir->tail)) {
3889        if (cycle >= lfs->cfg->block_count / 2) {
3890            // loop detected
3891            return LFS_ERR_CORRUPT;
3892        }
3893        cycle += 1;
3894
3895        if (lfs_pair_cmp(pdir->tail, pair) == 0) {
3896            return 0;
3897        }
3898
3899        int err = lfs_dir_fetch(lfs, pdir, pdir->tail);
3900        if (err) {
3901            return err;
3902        }
3903    }
3904
3905    return LFS_ERR_NOENT;
3906}
3907
3908struct lfs_fs_parent_match {
3909    lfs_t* lfs;
3910    const lfs_block_t pair[2];
3911};
3912
3913static int lfs_fs_parent_match(void* data, lfs_tag_t tag, const void* buffer) {
3914    struct lfs_fs_parent_match* find = data;
3915    lfs_t* lfs = find->lfs;
3916    const struct lfs_diskoff* disk = buffer;
3917    (void)tag;
3918
3919    lfs_block_t child[2];
3920    int err = lfs_bd_read(lfs, &lfs->pcache, &lfs->rcache, lfs->cfg->block_size,
3921                          disk->block, disk->off, &child, sizeof(child));
3922    if (err) {
3923        return err;
3924    }
3925
3926    lfs_pair_fromle32(child);
3927    return (lfs_pair_cmp(child, find->pair) == 0) ? LFS_CMP_EQ : LFS_CMP_LT;
3928}
3929
3930static lfs_stag_t lfs_fs_parent(lfs_t* lfs, const lfs_block_t pair[2],
3931                                lfs_mdir_t* parent) {
3932    // use fetchmatch with callback to find pairs
3933    parent->tail[0] = 0;
3934    parent->tail[1] = 1;
3935    lfs_block_t cycle = 0;
3936    while (!lfs_pair_isnull(parent->tail)) {
3937        if (cycle >= lfs->cfg->block_count / 2) {
3938            // loop detected
3939            return LFS_ERR_CORRUPT;
3940        }
3941        cycle += 1;
3942
3943        lfs_stag_t tag = lfs_dir_fetchmatch(
3944            lfs, parent, parent->tail, LFS_MKTAG(0x7ff, 0, 0x3ff),
3945            LFS_MKTAG(LFS_TYPE_DIRSTRUCT, 0, 8), NULL, lfs_fs_parent_match,
3946            &(struct lfs_fs_parent_match){lfs, {pair[0], pair[1]}});
3947        if (tag && tag != LFS_ERR_NOENT) {
3948            return tag;
3949        }
3950    }
3951
3952    return LFS_ERR_NOENT;
3953}
3954
3955static int lfs_fs_relocate(lfs_t* lfs, const lfs_block_t oldpair[2],
3956                           lfs_block_t newpair[2]) {
3957    // update internal root
3958    if (lfs_pair_cmp(oldpair, lfs->root) == 0) {
3959        lfs->root[0] = newpair[0];
3960        lfs->root[1] = newpair[1];
3961    }
3962
3963    // update internally tracked dirs
3964    for (struct lfs_mlist* d = lfs->mlist; d; d = d->next) {
3965        if (lfs_pair_cmp(oldpair, d->m.pair) == 0) {
3966            d->m.pair[0] = newpair[0];
3967            d->m.pair[1] = newpair[1];
3968        }
3969
3970        if (d->type == LFS_TYPE_DIR &&
3971            lfs_pair_cmp(oldpair, ((lfs_dir_t*)d)->head) == 0) {
3972            ((lfs_dir_t*)d)->head[0] = newpair[0];
3973            ((lfs_dir_t*)d)->head[1] = newpair[1];
3974        }
3975    }
3976
3977    // find parent
3978    lfs_mdir_t parent;
3979    lfs_stag_t tag = lfs_fs_parent(lfs, oldpair, &parent);
3980    if (tag < 0 && tag != LFS_ERR_NOENT) {
3981        return tag;
3982    }
3983
3984    if (tag != LFS_ERR_NOENT) {
3985        // update disk, this creates a desync
3986        lfs_fs_preporphans(lfs, +1);
3987
3988        // fix pending move in this pair? this looks like an optimization but
3989        // is in fact _required_ since relocating may outdate the move.
3990        uint16_t moveid = 0x3ff;
3991        if (lfs_gstate_hasmovehere(&lfs->gstate, parent.pair)) {
3992            moveid = lfs_tag_id(lfs->gstate.tag);
3993            LFS_DEBUG("Fixing move while relocating "
3994                      "{0x%" PRIx32 ", 0x%" PRIx32 "} 0x%" PRIx16 "\n",
3995                      parent.pair[0], parent.pair[1], moveid);
3996            lfs_fs_prepmove(lfs, 0x3ff, NULL);
3997            if (moveid < lfs_tag_id(tag)) {
3998                tag -= LFS_MKTAG(0, 1, 0);
3999            }
4000        }
4001
4002        lfs_pair_tole32(newpair);
4003        int err = lfs_dir_commit(
4004            lfs, &parent,
4005            LFS_MKATTRS(
4006                {LFS_MKTAG_IF(moveid != 0x3ff, LFS_TYPE_DELETE, moveid, 0),
4007                 NULL},
4008                {tag, newpair}));
4009        lfs_pair_fromle32(newpair);
4010        if (err) {
4011            return err;
4012        }
4013
4014        // next step, clean up orphans
4015        lfs_fs_preporphans(lfs, -1);
4016    }
4017
4018    // find pred
4019    int err = lfs_fs_pred(lfs, oldpair, &parent);
4020    if (err && err != LFS_ERR_NOENT) {
4021        return err;
4022    }
4023
4024    // if we can't find dir, it must be new
4025    if (err != LFS_ERR_NOENT) {
4026        // fix pending move in this pair? this looks like an optimization but
4027        // is in fact _required_ since relocating may outdate the move.
4028        uint16_t moveid = 0x3ff;
4029        if (lfs_gstate_hasmovehere(&lfs->gstate, parent.pair)) {
4030            moveid = lfs_tag_id(lfs->gstate.tag);
4031            LFS_DEBUG("Fixing move while relocating "
4032                      "{0x%" PRIx32 ", 0x%" PRIx32 "} 0x%" PRIx16 "\n",
4033                      parent.pair[0], parent.pair[1], moveid);
4034            lfs_fs_prepmove(lfs, 0x3ff, NULL);
4035        }
4036
4037        // replace bad pair, either we clean up desync, or no desync occured
4038        lfs_pair_tole32(newpair);
4039        err = lfs_dir_commit(
4040            lfs, &parent,
4041            LFS_MKATTRS(
4042                {LFS_MKTAG_IF(moveid != 0x3ff, LFS_TYPE_DELETE, moveid, 0),
4043                 NULL},
4044                {LFS_MKTAG(LFS_TYPE_TAIL + parent.split, 0x3ff, 8), newpair}));
4045        lfs_pair_fromle32(newpair);
4046        if (err) {
4047            return err;
4048        }
4049    }
4050
4051    return 0;
4052}
4053
4054static void lfs_fs_preporphans(lfs_t* lfs, int8_t orphans) {
4055    LFS_ASSERT(lfs_tag_size(lfs->gstate.tag) > 0 || orphans >= 0);
4056    lfs->gstate.tag += orphans;
4057    lfs->gstate.tag = ((lfs->gstate.tag & ~LFS_MKTAG(0x800, 0, 0)) |
4058                       ((uint32_t)lfs_gstate_hasorphans(&lfs->gstate) << 31));
4059}
4060
4061static void lfs_fs_prepmove(lfs_t* lfs, uint16_t id,
4062                            const lfs_block_t pair[2]) {
4063    lfs->gstate.tag = ((lfs->gstate.tag & ~LFS_MKTAG(0x7ff, 0x3ff, 0)) |
4064                       ((id != 0x3ff) ? LFS_MKTAG(LFS_TYPE_DELETE, id, 0) : 0));
4065    lfs->gstate.pair[0] = (id != 0x3ff) ? pair[0] : 0;
4066    lfs->gstate.pair[1] = (id != 0x3ff) ? pair[1] : 0;
4067}
4068
4069static int lfs_fs_demove(lfs_t* lfs) {
4070    if (!lfs_gstate_hasmove(&lfs->gdisk)) {
4071        return 0;
4072    }
4073
4074    // Fix bad moves
4075    LFS_DEBUG("Fixing move {0x%" PRIx32 ", 0x%" PRIx32 "} 0x%" PRIx16,
4076              lfs->gdisk.pair[0], lfs->gdisk.pair[1],
4077              lfs_tag_id(lfs->gdisk.tag));
4078
4079    // fetch and delete the moved entry
4080    lfs_mdir_t movedir;
4081    int err = lfs_dir_fetch(lfs, &movedir, lfs->gdisk.pair);
4082    if (err) {
4083        return err;
4084    }
4085
4086    // prep gstate and delete move id
4087    uint16_t moveid = lfs_tag_id(lfs->gdisk.tag);
4088    lfs_fs_prepmove(lfs, 0x3ff, NULL);
4089    err = lfs_dir_commit(
4090        lfs, &movedir,
4091        LFS_MKATTRS({LFS_MKTAG(LFS_TYPE_DELETE, moveid, 0), NULL}));
4092    if (err) {
4093        return err;
4094    }
4095
4096    return 0;
4097}
4098
4099static int lfs_fs_deorphan(lfs_t* lfs) {
4100    if (!lfs_gstate_hasorphans(&lfs->gstate)) {
4101        return 0;
4102    }
4103
4104    // Fix any orphans
4105    lfs_mdir_t pdir = {.split = true, .tail = {0, 1}};
4106    lfs_mdir_t dir;
4107
4108    // iterate over all directory directory entries
4109    while (!lfs_pair_isnull(pdir.tail)) {
4110        int err = lfs_dir_fetch(lfs, &dir, pdir.tail);
4111        if (err) {
4112            return err;
4113        }
4114
4115        // check head blocks for orphans
4116        if (!pdir.split) {
4117            // check if we have a parent
4118            lfs_mdir_t parent;
4119            lfs_stag_t tag = lfs_fs_parent(lfs, pdir.tail, &parent);
4120            if (tag < 0 && tag != LFS_ERR_NOENT) {
4121                return tag;
4122            }
4123
4124            if (tag == LFS_ERR_NOENT) {
4125                // we are an orphan
4126                LFS_DEBUG("Fixing orphan {0x%" PRIx32 ", 0x%" PRIx32 "}",
4127                          pdir.tail[0], pdir.tail[1]);
4128
4129                err = lfs_dir_drop(lfs, &pdir, &dir);
4130                if (err) {
4131                    return err;
4132                }
4133
4134                // refetch tail
4135                continue;
4136            }
4137
4138            lfs_block_t pair[2];
4139            lfs_stag_t res = lfs_dir_get(lfs, &parent,
4140                                         LFS_MKTAG(0x7ff, 0x3ff, 0), tag, pair);
4141            if (res < 0) {
4142                return res;
4143            }
4144            lfs_pair_fromle32(pair);
4145
4146            if (!lfs_pair_sync(pair, pdir.tail)) {
4147                // we have desynced
4148                LFS_DEBUG("Fixing half-orphan {0x%" PRIx32 ", 0x%" PRIx32 "} "
4149                          "-> {0x%" PRIx32 ", 0x%" PRIx32 "}",
4150                          pdir.tail[0], pdir.tail[1], pair[0], pair[1]);
4151
4152                lfs_pair_tole32(pair);
4153                err = lfs_dir_commit(
4154                    lfs, &pdir,
4155                    LFS_MKATTRS(
4156                        {LFS_MKTAG(LFS_TYPE_SOFTTAIL, 0x3ff, 8), pair}));
4157                lfs_pair_fromle32(pair);
4158                if (err) {
4159                    return err;
4160                }
4161
4162                // refetch tail
4163                continue;
4164            }
4165        }
4166
4167        pdir = dir;
4168    }
4169
4170    // mark orphans as fixed
4171    lfs_fs_preporphans(lfs, -lfs_gstate_getorphans(&lfs->gstate));
4172    return 0;
4173}
4174
4175static int lfs_fs_forceconsistency(lfs_t* lfs) {
4176    int err = lfs_fs_demove(lfs);
4177    if (err) {
4178        return err;
4179    }
4180
4181    err = lfs_fs_deorphan(lfs);
4182    if (err) {
4183        return err;
4184    }
4185
4186    return 0;
4187}
4188
4189static int lfs_fs_size_count(void* p, lfs_block_t block) {
4190    (void)block;
4191    lfs_size_t* size = p;
4192    *size += 1;
4193    return 0;
4194}
4195
4196lfs_ssize_t lfs_fs_size(lfs_t* lfs) {
4197    LFS_TRACE("lfs_fs_size(%p)", (void*)lfs);
4198    lfs_size_t size = 0;
4199    int err = lfs_fs_traverseraw(lfs, lfs_fs_size_count, &size, false);
4200    if (err) {
4201        LFS_TRACE("lfs_fs_size -> %d", err);
4202        return err;
4203    }
4204
4205    LFS_TRACE("lfs_fs_size -> %d", err);
4206    return size;
4207}
4208
4209#ifdef LFS_MIGRATE
4210////// Migration from littelfs v1 below this //////
4211
4212/// Version info ///
4213
4214// Software library version
4215// Major (top-nibble), incremented on backwards incompatible changes
4216// Minor (bottom-nibble), incremented on feature additions
4217#define LFS1_VERSION 0x00010007
4218#define LFS1_VERSION_MAJOR (0xffff & (LFS1_VERSION >> 16))
4219#define LFS1_VERSION_MINOR (0xffff & (LFS1_VERSION >> 0))
4220
4221// Version of On-disk data structures
4222// Major (top-nibble), incremented on backwards incompatible changes
4223// Minor (bottom-nibble), incremented on feature additions
4224#define LFS1_DISK_VERSION 0x00010001
4225#define LFS1_DISK_VERSION_MAJOR (0xffff & (LFS1_DISK_VERSION >> 16))
4226#define LFS1_DISK_VERSION_MINOR (0xffff & (LFS1_DISK_VERSION >> 0))
4227
4228/// v1 Definitions ///
4229
4230// File types
4231enum lfs1_type {
4232    LFS1_TYPE_REG = 0x11,
4233    LFS1_TYPE_DIR = 0x22,
4234    LFS1_TYPE_SUPERBLOCK = 0x2e,
4235};
4236
4237typedef struct lfs1 {
4238    lfs_block_t root[2];
4239} lfs1_t;
4240
4241typedef struct lfs1_entry {
4242    lfs_off_t off;
4243
4244    struct lfs1_disk_entry {
4245        uint8_t type;
4246        uint8_t elen;
4247        uint8_t alen;
4248        uint8_t nlen;
4249        union {
4250            struct {
4251                lfs_block_t head;
4252                lfs_size_t size;
4253            } file;
4254            lfs_block_t dir[2];
4255        } u;
4256    } d;
4257} lfs1_entry_t;
4258
4259typedef struct lfs1_dir {
4260    struct lfs1_dir* next;
4261    lfs_block_t pair[2];
4262    lfs_off_t off;
4263
4264    lfs_block_t head[2];
4265    lfs_off_t pos;
4266
4267    struct lfs1_disk_dir {
4268        uint32_t rev;
4269        lfs_size_t size;
4270        lfs_block_t tail[2];
4271    } d;
4272} lfs1_dir_t;
4273
4274typedef struct lfs1_superblock {
4275    lfs_off_t off;
4276
4277    struct lfs1_disk_superblock {
4278        uint8_t type;
4279        uint8_t elen;
4280        uint8_t alen;
4281        uint8_t nlen;
4282        lfs_block_t root[2];
4283        uint32_t block_size;
4284        uint32_t block_count;
4285        uint32_t version;
4286        char magic[8];
4287    } d;
4288} lfs1_superblock_t;
4289
4290/// Low-level wrappers v1->v2 ///
4291static void lfs1_crc(uint32_t* crc, const void* buffer, size_t size) {
4292    *crc = lfs_crc(*crc, buffer, size);
4293}
4294
4295static int lfs1_bd_read(lfs_t* lfs, lfs_block_t block, lfs_off_t off,
4296                        void* buffer, lfs_size_t size) {
4297    // if we ever do more than writes to alternating pairs,
4298    // this may need to consider pcache
4299    return lfs_bd_read(lfs, &lfs->pcache, &lfs->rcache, size, block, off,
4300                       buffer, size);
4301}
4302
4303static int lfs1_bd_crc(lfs_t* lfs, lfs_block_t block, lfs_off_t off,
4304                       lfs_size_t size, uint32_t* crc) {
4305    for (lfs_off_t i = 0; i < size; i++) {
4306        uint8_t c;
4307        int err = lfs1_bd_read(lfs, block, off + i, &c, 1);
4308        if (err) {
4309            return err;
4310        }
4311
4312        lfs1_crc(crc, &c, 1);
4313    }
4314
4315    return 0;
4316}
4317
4318/// Endian swapping functions ///
4319static void lfs1_dir_fromle32(struct lfs1_disk_dir* d) {
4320    d->rev = lfs_fromle32(d->rev);
4321    d->size = lfs_fromle32(d->size);
4322    d->tail[0] = lfs_fromle32(d->tail[0]);
4323    d->tail[1] = lfs_fromle32(d->tail[1]);
4324}
4325
4326static void lfs1_dir_tole32(struct lfs1_disk_dir* d) {
4327    d->rev = lfs_tole32(d->rev);
4328    d->size = lfs_tole32(d->size);
4329    d->tail[0] = lfs_tole32(d->tail[0]);
4330    d->tail[1] = lfs_tole32(d->tail[1]);
4331}
4332
4333static void lfs1_entry_fromle32(struct lfs1_disk_entry* d) {
4334    d->u.dir[0] = lfs_fromle32(d->u.dir[0]);
4335    d->u.dir[1] = lfs_fromle32(d->u.dir[1]);
4336}
4337
4338static void lfs1_entry_tole32(struct lfs1_disk_entry* d) {
4339    d->u.dir[0] = lfs_tole32(d->u.dir[0]);
4340    d->u.dir[1] = lfs_tole32(d->u.dir[1]);
4341}
4342
4343static void lfs1_superblock_fromle32(struct lfs1_disk_superblock* d) {
4344    d->root[0] = lfs_fromle32(d->root[0]);
4345    d->root[1] = lfs_fromle32(d->root[1]);
4346    d->block_size = lfs_fromle32(d->block_size);
4347    d->block_count = lfs_fromle32(d->block_count);
4348    d->version = lfs_fromle32(d->version);
4349}
4350
4351///// Metadata pair and directory operations ///
4352static inline lfs_size_t lfs1_entry_size(const lfs1_entry_t* entry) {
4353    return 4 + entry->d.elen + entry->d.alen + entry->d.nlen;
4354}
4355
4356static int lfs1_dir_fetch(lfs_t* lfs, lfs1_dir_t* dir,
4357                          const lfs_block_t pair[2]) {
4358    // copy out pair, otherwise may be aliasing dir
4359    const lfs_block_t tpair[2] = {pair[0], pair[1]};
4360    bool valid = false;
4361
4362    // check both blocks for the most recent revision
4363    for (int i = 0; i < 2; i++) {
4364        struct lfs1_disk_dir test;
4365        int err = lfs1_bd_read(lfs, tpair[i], 0, &test, sizeof(test));
4366        lfs1_dir_fromle32(&test);
4367        if (err) {
4368            if (err == LFS_ERR_CORRUPT) {
4369                continue;
4370            }
4371            return err;
4372        }
4373
4374        if (valid && lfs_scmp(test.rev, dir->d.rev) < 0) {
4375            continue;
4376        }
4377
4378        if ((0x7fffffff & test.size) < sizeof(test) + 4 ||
4379            (0x7fffffff & test.size) > lfs->cfg->block_size) {
4380            continue;
4381        }
4382
4383        uint32_t crc = 0xffffffff;
4384        lfs1_dir_tole32(&test);
4385        lfs1_crc(&crc, &test, sizeof(test));
4386        lfs1_dir_fromle32(&test);
4387        err = lfs1_bd_crc(lfs, tpair[i], sizeof(test),
4388                          (0x7fffffff & test.size) - sizeof(test), &crc);
4389        if (err) {
4390            if (err == LFS_ERR_CORRUPT) {
4391                continue;
4392            }
4393            return err;
4394        }
4395
4396        if (crc != 0) {
4397            continue;
4398        }
4399
4400        valid = true;
4401
4402        // setup dir in case it's valid
4403        dir->pair[0] = tpair[(i + 0) % 2];
4404        dir->pair[1] = tpair[(i + 1) % 2];
4405        dir->off = sizeof(dir->d);
4406        dir->d = test;
4407    }
4408
4409    if (!valid) {
4410        LFS_ERROR("Corrupted dir pair at {0x%" PRIx32 ", 0x%" PRIx32 "}",
4411                  tpair[0], tpair[1]);
4412        return LFS_ERR_CORRUPT;
4413    }
4414
4415    return 0;
4416}
4417
4418static int lfs1_dir_next(lfs_t* lfs, lfs1_dir_t* dir, lfs1_entry_t* entry) {
4419    while (dir->off + sizeof(entry->d) > (0x7fffffff & dir->d.size) - 4) {
4420        if (!(0x80000000 & dir->d.size)) {
4421            entry->off = dir->off;
4422            return LFS_ERR_NOENT;
4423        }
4424
4425        int err = lfs1_dir_fetch(lfs, dir, dir->d.tail);
4426        if (err) {
4427            return err;
4428        }
4429
4430        dir->off = sizeof(dir->d);
4431        dir->pos += sizeof(dir->d) + 4;
4432    }
4433
4434    int err =
4435        lfs1_bd_read(lfs, dir->pair[0], dir->off, &entry->d, sizeof(entry->d));
4436    lfs1_entry_fromle32(&entry->d);
4437    if (err) {
4438        return err;
4439    }
4440
4441    entry->off = dir->off;
4442    dir->off += lfs1_entry_size(entry);
4443    dir->pos += lfs1_entry_size(entry);
4444    return 0;
4445}
4446
4447/// littlefs v1 specific operations ///
4448int lfs1_traverse(lfs_t* lfs, int (*cb)(void*, lfs_block_t), void* data) {
4449    if (lfs_pair_isnull(lfs->lfs1->root)) {
4450        return 0;
4451    }
4452
4453    // iterate over metadata pairs
4454    lfs1_dir_t dir;
4455    lfs1_entry_t entry;
4456    lfs_block_t cwd[2] = {0, 1};
4457
4458    while (true) {
4459        for (int i = 0; i < 2; i++) {
4460            int err = cb(data, cwd[i]);
4461            if (err) {
4462                return err;
4463            }
4464        }
4465
4466        int err = lfs1_dir_fetch(lfs, &dir, cwd);
4467        if (err) {
4468            return err;
4469        }
4470
4471        // iterate over contents
4472        while (dir.off + sizeof(entry.d) <= (0x7fffffff & dir.d.size) - 4) {
4473            err = lfs1_bd_read(lfs, dir.pair[0], dir.off, &entry.d,
4474                               sizeof(entry.d));
4475            lfs1_entry_fromle32(&entry.d);
4476            if (err) {
4477                return err;
4478            }
4479
4480            dir.off += lfs1_entry_size(&entry);
4481            if ((0x70 & entry.d.type) == (0x70 & LFS1_TYPE_REG)) {
4482                err = lfs_ctz_traverse(lfs, NULL, &lfs->rcache,
4483                                       entry.d.u.file.head, entry.d.u.file.size,
4484                                       cb, data);
4485                if (err) {
4486                    return err;
4487                }
4488            }
4489        }
4490
4491        // we also need to check if we contain a threaded v2 directory
4492        lfs_mdir_t dir2 = {.split = true, .tail = {cwd[0], cwd[1]}};
4493        while (dir2.split) {
4494            err = lfs_dir_fetch(lfs, &dir2, dir2.tail);
4495            if (err) {
4496                break;
4497            }
4498
4499            for (int i = 0; i < 2; i++) {
4500                err = cb(data, dir2.pair[i]);
4501                if (err) {
4502                    return err;
4503                }
4504            }
4505        }
4506
4507        cwd[0] = dir.d.tail[0];
4508        cwd[1] = dir.d.tail[1];
4509
4510        if (lfs_pair_isnull(cwd)) {
4511            break;
4512        }
4513    }
4514
4515    return 0;
4516}
4517
4518static int lfs1_moved(lfs_t* lfs, const void* e) {
4519    if (lfs_pair_isnull(lfs->lfs1->root)) {
4520        return 0;
4521    }
4522
4523    // skip superblock
4524    lfs1_dir_t cwd;
4525    int err = lfs1_dir_fetch(lfs, &cwd, (const lfs_block_t[2]){0, 1});
4526    if (err) {
4527        return err;
4528    }
4529
4530    // iterate over all directory directory entries
4531    lfs1_entry_t entry;
4532    while (!lfs_pair_isnull(cwd.d.tail)) {
4533        err = lfs1_dir_fetch(lfs, &cwd, cwd.d.tail);
4534        if (err) {
4535            return err;
4536        }
4537
4538        while (true) {
4539            err = lfs1_dir_next(lfs, &cwd, &entry);
4540            if (err && err != LFS_ERR_NOENT) {
4541                return err;
4542            }
4543
4544            if (err == LFS_ERR_NOENT) {
4545                break;
4546            }
4547
4548            if (!(0x80 & entry.d.type) &&
4549                memcmp(&entry.d.u, e, sizeof(entry.d.u)) == 0) {
4550                return true;
4551            }
4552        }
4553    }
4554
4555    return false;
4556}
4557
4558/// Filesystem operations ///
4559static int lfs1_mount(lfs_t* lfs, struct lfs1* lfs1,
4560                      const struct lfs_config* cfg) {
4561    int err = 0;
4562    {
4563        err = lfs_init(lfs, cfg);
4564        if (err) {
4565            return err;
4566        }
4567
4568        lfs->lfs1 = lfs1;
4569        lfs->lfs1->root[0] = LFS_BLOCK_NULL;
4570        lfs->lfs1->root[1] = LFS_BLOCK_NULL;
4571
4572        // setup free lookahead
4573        lfs->free.off = 0;
4574        lfs->free.size = 0;
4575        lfs->free.i = 0;
4576        lfs_alloc_ack(lfs);
4577
4578        // load superblock
4579        lfs1_dir_t dir;
4580        lfs1_superblock_t superblock;
4581        err = lfs1_dir_fetch(lfs, &dir, (const lfs_block_t[2]){0, 1});
4582        if (err && err != LFS_ERR_CORRUPT) {
4583            goto cleanup;
4584        }
4585
4586        if (!err) {
4587            err = lfs1_bd_read(lfs, dir.pair[0], sizeof(dir.d), &superblock.d,
4588                               sizeof(superblock.d));
4589            lfs1_superblock_fromle32(&superblock.d);
4590            if (err) {
4591                goto cleanup;
4592            }
4593
4594            lfs->lfs1->root[0] = superblock.d.root[0];
4595            lfs->lfs1->root[1] = superblock.d.root[1];
4596        }
4597
4598        if (err || memcmp(superblock.d.magic, "littlefs", 8) != 0) {
4599            LFS_ERROR("Invalid superblock at {0x%" PRIx32 ", 0x%" PRIx32 "}", 0,
4600                      1);
4601            err = LFS_ERR_CORRUPT;
4602            goto cleanup;
4603        }
4604
4605        uint16_t major_version = (0xffff & (superblock.d.version >> 16));
4606        uint16_t minor_version = (0xffff & (superblock.d.version >> 0));
4607        if ((major_version != LFS1_DISK_VERSION_MAJOR ||
4608             minor_version > LFS1_DISK_VERSION_MINOR)) {
4609            LFS_ERROR("Invalid version v%d.%d", major_version, minor_version);
4610            err = LFS_ERR_INVAL;
4611            goto cleanup;
4612        }
4613
4614        return 0;
4615    }
4616
4617cleanup:
4618    lfs_deinit(lfs);
4619    return err;
4620}
4621
4622static int lfs1_unmount(lfs_t* lfs) {
4623    return lfs_deinit(lfs);
4624}
4625
4626/// v1 migration ///
4627int lfs_migrate(lfs_t* lfs, const struct lfs_config* cfg) {
4628    LFS_TRACE("lfs_migrate(%p, %p {.context=%p, "
4629              ".read=%p, .prog=%p, .erase=%p, .sync=%p, "
4630              ".read_size=%" PRIu32 ", .prog_size=%" PRIu32 ", "
4631              ".block_size=%" PRIu32 ", .block_count=%" PRIu32 ", "
4632              ".block_cycles=%" PRIu32 ", .cache_size=%" PRIu32 ", "
4633              ".lookahead_size=%" PRIu32 ", .read_buffer=%p, "
4634              ".prog_buffer=%p, .lookahead_buffer=%p, "
4635              ".name_max=%" PRIu32 ", .file_max=%" PRIu32 ", "
4636              ".attr_max=%" PRIu32 "})",
4637              (void*)lfs, (void*)cfg, cfg->context, (void*)(uintptr_t)cfg->read,
4638              (void*)(uintptr_t)cfg->prog, (void*)(uintptr_t)cfg->erase,
4639              (void*)(uintptr_t)cfg->sync, cfg->read_size, cfg->prog_size,
4640              cfg->block_size, cfg->block_count, cfg->block_cycles,
4641              cfg->cache_size, cfg->lookahead_size, cfg->read_buffer,
4642              cfg->prog_buffer, cfg->lookahead_buffer, cfg->name_max,
4643              cfg->file_max, cfg->attr_max);
4644    struct lfs1 lfs1;
4645    int err = lfs1_mount(lfs, &lfs1, cfg);
4646    if (err) {
4647        LFS_TRACE("lfs_migrate -> %d", err);
4648        return err;
4649    }
4650
4651    {
4652        // iterate through each directory, copying over entries
4653        // into new directory
4654        lfs1_dir_t dir1;
4655        lfs_mdir_t dir2;
4656        dir1.d.tail[0] = lfs->lfs1->root[0];
4657        dir1.d.tail[1] = lfs->lfs1->root[1];
4658        while (!lfs_pair_isnull(dir1.d.tail)) {
4659            // iterate old dir
4660            err = lfs1_dir_fetch(lfs, &dir1, dir1.d.tail);
4661            if (err) {
4662                goto cleanup;
4663            }
4664
4665            // create new dir and bind as temporary pretend root
4666            err = lfs_dir_alloc(lfs, &dir2);
4667            if (err) {
4668                goto cleanup;
4669            }
4670
4671            dir2.rev = dir1.d.rev;
4672            dir1.head[0] = dir1.pair[0];
4673            dir1.head[1] = dir1.pair[1];
4674            lfs->root[0] = dir2.pair[0];
4675            lfs->root[1] = dir2.pair[1];
4676
4677            err = lfs_dir_commit(lfs, &dir2, NULL, 0);
4678            if (err) {
4679                goto cleanup;
4680            }
4681
4682            while (true) {
4683                lfs1_entry_t entry1;
4684                err = lfs1_dir_next(lfs, &dir1, &entry1);
4685                if (err && err != LFS_ERR_NOENT) {
4686                    goto cleanup;
4687                }
4688
4689                if (err == LFS_ERR_NOENT) {
4690                    break;
4691                }
4692
4693                // check that entry has not been moved
4694                if (entry1.d.type & 0x80) {
4695                    int moved = lfs1_moved(lfs, &entry1.d.u);
4696                    if (moved < 0) {
4697                        err = moved;
4698                        goto cleanup;
4699                    }
4700
4701                    if (moved) {
4702                        continue;
4703                    }
4704
4705                    entry1.d.type &= ~0x80;
4706                }
4707
4708                // also fetch name
4709                char name[LFS_NAME_MAX + 1];
4710                memset(name, 0, sizeof(name));
4711                err =
4712                    lfs1_bd_read(lfs, dir1.pair[0],
4713                                 entry1.off + 4 + entry1.d.elen + entry1.d.alen,
4714                                 name, entry1.d.nlen);
4715                if (err) {
4716                    goto cleanup;
4717                }
4718
4719                bool isdir = (entry1.d.type == LFS1_TYPE_DIR);
4720
4721                // create entry in new dir
4722                err = lfs_dir_fetch(lfs, &dir2, lfs->root);
4723                if (err) {
4724                    goto cleanup;
4725                }
4726
4727                uint16_t id;
4728                err = lfs_dir_find(lfs, &dir2, &(const char*){name}, &id);
4729                if (!(err == LFS_ERR_NOENT && id != 0x3ff)) {
4730                    err = (err < 0) ? err : LFS_ERR_EXIST;
4731                    goto cleanup;
4732                }
4733
4734                lfs1_entry_tole32(&entry1.d);
4735                err = lfs_dir_commit(
4736                    lfs, &dir2,
4737                    LFS_MKATTRS({LFS_MKTAG(LFS_TYPE_CREATE, id, 0)},
4738                                {LFS_MKTAG_IF_ELSE(isdir, LFS_TYPE_DIR, id,
4739                                                   entry1.d.nlen, LFS_TYPE_REG,
4740                                                   id, entry1.d.nlen),
4741                                 name},
4742                                {LFS_MKTAG_IF_ELSE(isdir, LFS_TYPE_DIRSTRUCT,
4743                                                   id, sizeof(entry1.d.u),
4744                                                   LFS_TYPE_CTZSTRUCT, id,
4745                                                   sizeof(entry1.d.u)),
4746                                 &entry1.d.u}));
4747                lfs1_entry_fromle32(&entry1.d);
4748                if (err) {
4749                    goto cleanup;
4750                }
4751            }
4752
4753            if (!lfs_pair_isnull(dir1.d.tail)) {
4754                // find last block and update tail to thread into fs
4755                err = lfs_dir_fetch(lfs, &dir2, lfs->root);
4756                if (err) {
4757                    goto cleanup;
4758                }
4759
4760                while (dir2.split) {
4761                    err = lfs_dir_fetch(lfs, &dir2, dir2.tail);
4762                    if (err) {
4763                        goto cleanup;
4764                    }
4765                }
4766
4767                lfs_pair_tole32(dir2.pair);
4768                err = lfs_dir_commit(
4769                    lfs, &dir2,
4770                    LFS_MKATTRS(
4771                        {LFS_MKTAG(LFS_TYPE_SOFTTAIL, 0x3ff, 8), dir1.d.tail}));
4772                lfs_pair_fromle32(dir2.pair);
4773                if (err) {
4774                    goto cleanup;
4775                }
4776            }
4777
4778            // Copy over first block to thread into fs. Unfortunately
4779            // if this fails there is not much we can do.
4780            LFS_DEBUG("Migrating {0x%" PRIx32 ", 0x%" PRIx32 "} "
4781                      "-> {0x%" PRIx32 ", 0x%" PRIx32 "}",
4782                      lfs->root[0], lfs->root[1], dir1.head[0], dir1.head[1]);
4783
4784            err = lfs_bd_erase(lfs, dir1.head[1]);
4785            if (err) {
4786                goto cleanup;
4787            }
4788
4789            err = lfs_dir_fetch(lfs, &dir2, lfs->root);
4790            if (err) {
4791                goto cleanup;
4792            }
4793
4794            for (lfs_off_t i = 0; i < dir2.off; i++) {
4795                uint8_t dat;
4796                err = lfs_bd_read(lfs, NULL, &lfs->rcache, dir2.off,
4797                                  dir2.pair[0], i, &dat, 1);
4798                if (err) {
4799                    goto cleanup;
4800                }
4801
4802                err = lfs_bd_prog(lfs, &lfs->pcache, &lfs->rcache, true,
4803                                  dir1.head[1], i, &dat, 1);
4804                if (err) {
4805                    goto cleanup;
4806                }
4807            }
4808
4809            err = lfs_bd_flush(lfs, &lfs->pcache, &lfs->rcache, true);
4810            if (err) {
4811                goto cleanup;
4812            }
4813        }
4814
4815        // Create new superblock. This marks a successful migration!
4816        err = lfs1_dir_fetch(lfs, &dir1, (const lfs_block_t[2]){0, 1});
4817        if (err) {
4818            goto cleanup;
4819        }
4820
4821        dir2.pair[0] = dir1.pair[0];
4822        dir2.pair[1] = dir1.pair[1];
4823        dir2.rev = dir1.d.rev;
4824        dir2.off = sizeof(dir2.rev);
4825        dir2.etag = 0xffffffff;
4826        dir2.count = 0;
4827        dir2.tail[0] = lfs->lfs1->root[0];
4828        dir2.tail[1] = lfs->lfs1->root[1];
4829        dir2.erased = false;
4830        dir2.split = true;
4831
4832        lfs_superblock_t superblock = {
4833            .version = LFS_DISK_VERSION,
4834            .block_size = lfs->cfg->block_size,
4835            .block_count = lfs->cfg->block_count,
4836            .name_max = lfs->name_max,
4837            .file_max = lfs->file_max,
4838            .attr_max = lfs->attr_max,
4839        };
4840
4841        lfs_superblock_tole32(&superblock);
4842        err = lfs_dir_commit(
4843            lfs, &dir2,
4844            LFS_MKATTRS(
4845                {LFS_MKTAG(LFS_TYPE_CREATE, 0, 0)},
4846                {LFS_MKTAG(LFS_TYPE_SUPERBLOCK, 0, 8), "littlefs"},
4847                {LFS_MKTAG(LFS_TYPE_INLINESTRUCT, 0, sizeof(superblock)),
4848                 &superblock}));
4849        if (err) {
4850            goto cleanup;
4851        }
4852
4853        // sanity check that fetch works
4854        err = lfs_dir_fetch(lfs, &dir2, (const lfs_block_t[2]){0, 1});
4855        if (err) {
4856            goto cleanup;
4857        }
4858
4859        // force compaction to prevent accidentally mounting v1
4860        dir2.erased = false;
4861        err = lfs_dir_commit(lfs, &dir2, NULL, 0);
4862        if (err) {
4863            goto cleanup;
4864        }
4865    }
4866
4867cleanup:
4868    lfs1_unmount(lfs);
4869    LFS_TRACE("lfs_migrate -> %d", err);
4870    return err;
4871}
4872
4873#endif