Lines Matching +full:- +full:i
3 A little fail-safe filesystem designed for microcontrollers.
6 | | | .---._____
7 .-----. | |
8 --|o |---| littlefs |
9 --| |---| |
10 '-----' '----------'
16 filesystem that is resilient to power-loss and flash wear without using
19 This document covers the high-level design of littlefs, how it is different
21 low-level details covering every bit on disk, check out [SPEC.md](SPEC.md).
25 The embedded systems littlefs targets are usually 32-bit microcontrollers with
36 [Wikipedia][wikipedia-flash] has more information on how exactly flash works.
46 1. **Power-loss resilience** - On these systems, power can be lost at any time.
51 1. **Wear leveling** - Writing to flash is destructive. If a filesystem
56 1. **Bounded RAM/ROM** - If the above requirements weren't enough, these
72 power-loss resilience and wear leveling, we can narrow these down to a handful
75 1. First we have the non-resilient, block based filesystems, such as [FAT] and
79 power-loss resilient, so updating a file is a simple as rewriting the blocks
83 .--------.
87 '--------'
88 .-' '-.
90 .--------. .--------.
94 '--------' '--------'
95 .-' .-' '-.
97 .--------. .--------. .--------.
101 '--------' '--------' '--------'
119 .--------.--------.--------.--------.--------.--------.--------.--------.
121 | | | |-> | | |
123 '--------'--------'--------'--------'--------'--------'--------'--------'
127 detect power-loss and fall back to the previous state by ignoring failed
132 process of cleaning up outdated data from the end of the log, I've yet to
150 .--------.--------.
151 .--------. | C'| D'| | E'|
152 | root |-->| | |-> | |
154 | | '--------'--------'
155 '--------'
156 .-' '-.
158 .--------. .--------.
162 '--------' '--------'
163 .-' .-' '-.
165 .--------. .--------. .--------.
169 '--------' '--------' '--------'
184 4. Last but not least we have copy-on-write (COW) filesystems, such as
192 .--------. .--------.
196 '--------' '--------'
197 .-' '-. | '-.
198 | .-------|------------------' v
199 v v v .--------.
200 .--------. .--------. | new B |
203 | | | | '--------'
204 '--------' '--------' .-' |
205 .-' .-' '-. .------------|------'
207 v v v v .--------.
208 .--------. .--------. .--------. | new D |
211 | | | | | | '--------'
212 '--------' '--------' '--------'
248 wear. This sort of copy-on-bounded-writes (CObW) still focuses wear, but at
256 This is the idea behind littlefs. At the sub-block level, littlefs is built
258 on the filesystem. At the super-block level, littlefs is a CObW tree of blocks
263 .--------.--------.
265 | | |-> |
267 '--------'--------'
268 .----' '--------------.
270 .--------.--------. .--------.--------.
272 | | |-> | | | E'|-> |
274 '--------'--------' '--------'--------'
275 .-' '--. | '------------------.
276 v v .-' v
277 .--------. .--------. v .--------.
278 | C | | D | .--------. write | new E |
281 '--------' '--------' | | '--------'
282 '--------' .-' |
283 .-' '-. .-------------|------'
285 .--------. .--------. .--------.
289 '--------' '--------' '--------'
318 revision count that we compare using [sequence arithmetic][wikipedia-sna]
325 | '--------------------.
326 '-. |
328 .--------.--------.--------.--------.--------.--------.--------.--------.
332 '--------'--------'--------'--------'--------'--------'--------'--------'
333 '--. .----'
335 metadata pair .----------------.----------------.
337 block 1 is |----------------|----------------|
339 |----------------|----------------|
341 |----------------|----------------|
342 | B | A''' | <- most recent A
343 |----------------|----------------|
345 |----------------|----------------|
347 |----------------| v |
348 '----------------'----------------'
352 power-loss resilience) requires two parts: redundancy and error detection.
354 use a 32-bit [CRC][wikipedia-crc]. Maintaining redundancy, on the other hand,
365 .----------------.----------------. .----------------.----------------.
367 |----------------|----------------| |----------------|----------------|
369 | v | | |----------------| |
371 | | | |----------------| |
378 '----------------'----------------' '----------------'----------------'
389 .----------------.----------------. .----------------.----------------.
391 |----------------|----------------| |----------------|----------------|
393 |----------------| | |----------------| |
395 |----------------| | |----------------| |
397 | v | | |----------------| |
399 | | | |----------------| |
401 | | | |----------------| |
402 '----------------'----------------' '----------------'----------------'
425 .----------------.----------------. .----------------.----------------.
427 |----------------|----------------| |----------------|----------------|
429 |----------------| | |----------------|----------------|
431 |----------------| | |----------------|----------------|
433 |----------------| | |----------------|----------------|
435 |----------------| | |----------------| v |
437 |----------------| | |----------------| |
438 '----------------'----------------' '----------------'----------------'
460 .----------------.----------------. .----------------.----------------.
462 |----------------|----------------| |----------------|----------------|
464 |----------------|----------------| |----------------|----------------|
466 |----------------|----------------| |----------------|----------------|
467 | B | checksum | | tail ---------------------.
468 |----------------|----------------| |----------------|----------------| |
470 |----------------| v | |----------------| | |
472 |----------------| | | v | | |
473 '----------------'----------------' '----------------'----------------' |
474 .----------------.---------'
476 .----------------.----------------.
478 |----------------|----------------|
480 |----------------| |
482 |----------------| |
484 |----------------| |
489 '----------------'----------------'
512 ![cost = n + n (s / d+1)][metadata-formula1]
517 ![s = r (size/n)][metadata-formula2]
519 ![d = (1 - r) (size/n)][metadata-formula3]
524 ![cost = n + n (r (size/n) / ((1-r) (size/n) + 1))][metadata-formula4]
529 ![Metadata pair update cost graph][metadata-cost-graph]
540 ---
542 If we look at metadata pairs and linked-lists of metadata pairs at a high
552 of 4x the original size. I imagine users would not be happy if they found
557 ## CTZ skip-lists
561 metadata pairs to store references to more dense, copy-on-write (COW) data
564 [Copy-on-write data structures][wikipedia-cow], also called purely functional
575 [B-trees][wikipedia-B-tree], which can not be traversed with constant RAM, and
576 [B+-trees][wikipedia-B+-tree], which are not possible to update with COW
579 ---
582 linked-list. Appending a block, which is the basis for writing files, means we
584 operation, which means we need to update the second-to-last block, and then the
585 third-to-last, and so on until we've copied out the entire file.
588 A linked-list
589 .--------. .--------. .--------. .--------. .--------. .--------.
590 | data 0 |->| data 1 |->| data 2 |->| data 4 |->| data 5 |->| data 6 |
593 '--------' '--------' '--------' '--------' '--------' '--------'
604 A backwards linked-list
605 .--------. .--------. .--------. .--------. .--------. .--------.
606 | data 0 |<-| data 1 |<-| data 2 |<-| data 4 |<-| data 5 |<-| data 6 |
609 '--------' '--------' '--------' '--------' '--------' '--------'
612 However, a backwards linked-list does have a rather glaring problem. Iterating
617 uses a multilayered linked-list often called a
618 [skip-list][wikipedia-skip-list]. However, unlike the most common type of
619 skip-list, littlefs's skip-lists are strictly deterministic built around some
620 interesting properties of the count-trailing-zeros (CTZ) instruction.
622 The rules CTZ skip-lists follow are that for every _n_‍th block where _n_
624 _n_-2‍_ˣ_. This means that each block contains anywhere from 1 to
626 skip-list.
628 The name comes from heavy use of the [CTZ instruction][wikipedia-ctz], which
629 lets us calculate the power-of-two factors efficiently. For a give block _n_,
633 A backwards CTZ skip-list
634 .--------. .--------. .--------. .--------. .--------. .--------.
635 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 |<-| data 4 |<-| data 5 |
636 | |<-| |--| |<-| |--| | | |
637 | |<-| |--| |--| |--| | | |
638 '--------' '--------' '--------' '--------' '--------' '--------'
641 The additional pointers let us navigate the data-structure on disk much more
647 .--------. .--------. .--------. .--------. .--------. .--------.
648 | data 0 | | data 1 |<-| data 2 | | data 3 | | data 4 |<-| data 5 |
649 | | | | | |<-| |--| | | |
651 '--------' '--------' '--------' '--------' '--------' '--------'
656 .--------. .--------. .--------. .--------. .--------. .--------.
657 | data 0 | | data 1 | | data 2 | | data 3 | | data 4 |<-| data 5 |
659 | |<-| |--| |--| |--| | | |
660 '--------' '--------' '--------' '--------' '--------' '--------'
676 ---
680 we store a CTZ skip-list in our metadata pairs?
683 linked-lists. Each linked-list skips twice as many blocks as the previous,
684 or from another perspective, each linked-list uses half as much storage as
689 ![lim,n->inf((1/n)sum,i,0->n(ctz(i)+1)) = sum,i,0->inf(1/2^i) = 2][ctz-formula1]
697 ![B = (w/8)ceil(log2(2^w / (B-2w/8)))][ctz-formula2]
702 1. 32-bit CTZ skip-list => minimum block size of 104 bytes
703 2. 64-bit CTZ skip-list => minimum block size of 448 bytes
705 littlefs uses a 32-bit word width, so our blocks can only overflow with
711 This last question is how do we store CTZ skip-lists? We need a pointer to the
712 head block, the size of the skip-list, the index of the head block, and our
719 word width in bits, ![n] be the index of the block in the skip-list, and
722 ![N = sum,i,0->n(B-(w/8)(ctz(i)+1))][ctz-formula3]
730 the [On-Line Encyclopedia of Integer Sequences (OEIS)][oeis], I managed to find
737 ![sum,i,0->n(ctz(i)+1) = 2n-popcount(n)][ctz-formula4]
747 handle deviations from this average. Of course, just to make sure I wrote a
748 quick script that verified this property for all 32-bit integers.
753 ![N = Bn - (w/8)(2n-popcount(n))][ctz-formula5]
755 Unfortunately, the popcount function is non-injective, so we can't solve this
762 ![n = floor((N-(w/8)popcount(N/(B-2w/8))) / (B-2w/8))][ctz-formula6]
768 ![off = N - (B-2w/8)n - (w/8)popcount(n)][ctz-formula7]
772 us store CTZ skip-lists with only a pointer and size.
774 CTZ skip-lists give us a COW data structure that is easily traversable in
777 storage overhead per block. In combination with metadata pairs, CTZ skip-lists
781 .--------.
785 |'--------'
786 '----|---'
788 .--------. .--------. .--------. .--------.
789 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 |
790 | |<-| |--| | | |
792 '--------' '--------' '--------' '--------'
796 .--------.
800 |'--------'
801 '----|---'
803 .--------. .--------. .--------. .--------.
804 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 |
805 | |<-| |--| | | |
807 '--------' '--------' '--------' '--------'
809 | | | .--------. .--------. .--------. .--------.
810 | | '----| new |<-| new |<-| new |<-| new |
811 | '----------------| data 2 |<-| data 3 |--| data 4 | | data 5 |
812 '------------------| |--| |--| | | |
813 '--------' '--------' '--------' '--------'
817 .--------.
821 |'--------'
822 '----|---'
824 .--------. .--------. .--------. .--------. |
825 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 | |
826 | |<-| |--| | | | |
828 '--------' '--------' '--------' '--------' |
830 | | | .--------. .--------. .--------. .--------.
831 | | '----| new |<-| new |<-| new |<-| new |
832 | '----------------| data 2 |<-| data 3 |--| data 4 | | data 5 |
833 '------------------| |--| |--| | | |
834 '--------' '--------' '--------' '--------'
840 block metadata pairs provide atomic updates, while CTZ skip-lists provide
847 In filesystem design, block allocation is often a second-class citizen, but in
863 .----.
866 '----'
867 v-------' '-------v
868 .----. . . .----.
871 '----' . . '----'
872 . . . . v--' '------------v---------v
873 . . . .----. . .----. .----.
876 . . . '----' . '----' '----'
878 .----.----.----.----.----.----.----.----.----.----.----.----.
881 '----'----'----'----'----'----'----'----'----'----'----'----'
883 '-------------------'----'-------------------'----'-- free blocks
892 high-risk error conditions.
894 ---
908 .----.----.----.----.----.----.----.----.----.----.----.----.
911 '----'----'----'----'----'----'----'----'----'----'----'----'
913 \---------------------------+----------------------------/
918 The block allocator in littlefs is a compromise between a disk-sized bitmap and
920 of a small, fixed-size bitmap called the lookahead buffer. During block
971 ---
989 left up to the filesystem's copy-on-bounded-writes (CObW) data structures. One
991 COW operation. The bounded-writes part is normally triggered by a counter, but
996 .----.
999 '----'
1000 v--' '----------------------v
1001 .----. .----.
1004 '----' '----'
1005 . . v---' .
1006 . . .----. .
1009 . . '----' .
1011 .----.----.----.----.----.----.----.----.----.----.
1014 '----'----'----'----'----'----'----'----'----'----'
1018 .----.
1021 '----'
1022 v--' '----------------------v
1023 .----. .----.
1026 '----' '----'
1027 . . v---' .
1028 . . .----. .
1031 . . '----' .
1033 .----.----.----.----.----.----.----.----.----.----.
1036 '----'----'----'----'----'----'----'----'----'----'
1040 .----.
1043 '----'
1044 v--' '----------------------v
1045 .----. .----.
1048 '----' '----'
1049 . . v---' .
1050 . . .----. .
1053 . . '----' .
1055 .----.----.----.----.----.----.----.----.----.----.
1058 '----'----'----'----'----'----'----'----'----'----'
1059 --------->
1062 .----.
1065 '----'
1066 v--' '----------------------v
1067 .----. .----.
1070 '----' '----'
1071 . . v---' .
1072 . . .----. . .----.
1075 . . '----' . '----'
1077 .----.----.----.----.----.----.----.----.----.----.
1080 '----'----'----'----'----'----'----'----'----'----'
1081 -------------->
1084 .----.
1087 '----'
1088 v--' '----------------------v
1089 .----. .----.
1092 '----' '----'
1093 . . v---' .
1094 . . .----. . .----.
1097 . . '----' . '----'
1099 .----.----.----.----.----.----.----.----.----.----.
1102 '----'----'----'----'----'----'----'----'----'----'
1106 .----.
1109 '----'
1110 v--' '----------------------v
1111 .----. .----. .----.
1114 '----' '----' '----'
1115 . . v---' . . .
1116 . . .----. . .----. .
1119 . . '----' . '----' .
1121 .----.----.----.----.----.----.----.----.----.----.
1124 '----'----'----'----'----'----'----'----'----'----'
1125 -------------->
1128 .----.
1131 '----'
1132 v--' '----------------------v
1133 .----. .----. .----.
1136 '----' '----' '----'
1137 . . . | . .---' .
1138 . . . '--------------v-------------v
1139 . . . . .----. . .----.
1142 . . . . '----' . '----'
1144 .----.----.----.----.----.----.----.----.----.----.
1147 '----'----'----'----'----'----'----'----'----'----'
1148 ------------> ------------------
1151 .----.
1154 '----'
1155 v--' '--v
1156 .----. .----.
1159 '----' '----'
1160 . . . '---------------------------v
1161 . . . . .----.
1164 . . . . '----'
1166 .----.----.----.----.----.----.----.----.----.----.
1169 '----'----'----'----'----'----'----'----'----'----'
1180 ---
1185 [error-correction-codes (ECC)][wikipedia-ecc].
1190 can detect: the [Hamming bound][wikipedia-hamming-bound]. As the number of
1208 ---
1225 1. [Dynamic wear leveling][wikipedia-dynamic-wear-leveling], where we
1229 2. [Static wear leveling][wikipedia-static-wear-leveling], where we
1253 ![Cumulative wear distribution graph][wear-distribution-graph]
1256 dependency on a power-independent random number generator, which must return
1266 .--------. \ probably random
1268 || | +-> crc ----------------------> xor
1270 |'--------' / |
1271 '---|--|-' |
1272 .-' '-------------------------. |
1274 | .--------------> xor ------------> xor
1277 .--------. \ ^ .--------. \ ^ .--------. \ ^
1278 .|metadata|-|--|-->|metadata| | | .|metadata| | |
1279 || | +--' || | +--' || | +--'
1281 |'--------' / |'--------' / |'--------' /
1282 '---|--|-' '----|---' '---|--|-'
1283 .-' '-. | .-' '-.
1285 .--------. .--------. .--------. .--------. .--------.
1289 '--------' '--------' '--------' '--------' '--------'
1297 ---
1304 [flash translation layer (FTL)][wikipedia-ftl] to get a small power resilient
1314 We've determined that CTZ skip-lists are pretty good at storing data compactly,
1316 a skip-list stored in a metadata pair that acts as an inode for the file.
1320 .--------.
1324 |'--------'
1325 '----|---'
1327 .--------. .--------. .--------. .--------.
1328 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 |
1329 | |<-| |--| | | |
1331 '--------' '--------' '--------' '--------'
1337 Consider a small 4-byte file. With a two block metadata-pair and one block for
1338 the CTZ skip-list, we find ourselves using a full 3 blocks. On most NOR flash
1344 .----------------. \
1346 ||----------------| \ |
1347 || skiplist ---. +- metadata |
1348 ||----------------| | / 4x8 bytes |
1350 ||----------------| | |
1351 || | | | +- metadata pair
1357 |'----------------' | |
1358 '----------------' | /
1359 .--------'
1361 .----------------. \ \
1362 | data | +- data |
1363 |----------------| / 4 bytes |
1367 | | +- data block
1374 '----------------' /
1391 .----------------.
1393 ||----------------|
1395 || A skiplist -----.
1396 ||----------------| | \
1397 || B name | | +- metadata
1398 || B skiplist ---. | | 4x8 bytes
1399 ||----------------| | | / 32 bytes
1401 ||----------------| | |
1404 |'----------------' | |
1405 '----------------' | |
1406 .----------------' |
1408 .----------------. .----------------. \ \
1409 | A data | | B data | +- data |
1410 | | |----------------| / 4 bytes |
1417 |----------------| | | |
1421 '----------------' '----------------' /
1425 attempts to use CTZ skip-lists for compact storage backfires. Metadata pairs
1437 .----------------.
1439 ||----------------|
1441 || A skiplist ---.
1442 ||----------------| | \
1443 || B name | | +- data
1445 ||----------------| | / 16 bytes
1447 ||----------------| |
1450 |'----------------' |
1451 '----------------' |
1452 .---------'
1454 .----------------.
1463 |----------------|
1467 '----------------'
1470 Once the file exceeds 1/4 the block size, we switch to a CTZ skip-list. This
1474 ![File storage cost graph][file-cost-graph]
1482 On their own, each directory is a linked-list of metadata pairs. This lets us
1489 .--------.
1493 |'--------'
1494 '---|--|-'
1495 .-' '-------------------------.
1497 .--------. .--------. .--------.
1498 .| dir A |------->| dir A | .| dir B |
1501 |'--------' |'--------' |'--------'
1502 '---|--|-' '----|---' '---|--|-'
1503 .-' '-. | .-' '-.
1505 .--------. .--------. .--------. .--------. .--------.
1509 '--------' '--------' '--------' '--------' '--------'
1517 skip-lists, we're not limited to strict COW operations. One thing we can do is
1518 thread a linked-list through our tree, explicitly enabling cheap traversal
1522 .--------.
1523 .| root |-.
1525 .-------|| |-'
1526 | |'--------'
1527 | '---|--|-'
1528 | .-' '-------------------------.
1530 | .--------. .--------. .--------.
1531 '->| dir A |------->| dir A |------->| dir B |
1534 |'--------' |'--------' |'--------'
1535 '---|--|-' '----|---' '---|--|-'
1536 .-' '-. | .-' '-.
1538 .--------. .--------. .--------. .--------. .--------.
1542 '--------' '--------' '--------' '--------' '--------'
1550 To work around this, our threaded linked-list has a bit of leeway. Instead of
1556 that maintain a filesystem tree threaded with a linked-list for traversal.
1561 .--------.
1562 .| root |-.
1564 .-------|| |-'
1565 | |'--------'
1566 | '---|--|-'
1567 | .-' '-.
1569 | .--------. .--------.
1570 '->| dir A |->| dir C |
1573 |'--------' |'--------'
1574 '--------' '--------'
1578 .--------.
1579 .| root |-.
1581 .-------|| |-'
1582 | |'--------'
1583 | '---|--|-'
1584 | .-' '-.
1586 | .--------. .--------.
1587 '->| dir A |--->| dir C |
1588 || | .->| |
1590 |'--------' | |'--------'
1591 '--------' | '--------'
1593 .--------. |
1594 .| dir B |-'
1597 |'--------'
1598 '--------'
1600 insert dir B into threaded linked-list, creating an orphan
1602 .--------.
1603 .| root |-.
1605 .-------|| |-'
1606 | |'--------'
1607 | '---|--|-'
1608 | .-' '-------------.
1610 | .--------. .--------. .--------.
1611 '->| dir A |->| dir B |->| dir C |
1614 |'--------' |'--------' |'--------'
1615 '--------' '--------' '--------'
1619 .--------.
1620 .| root |-.
1622 .-------------|| |-'
1623 | |'--------'
1624 | '--|-|-|-'
1625 | .------' | '-------.
1627 | .--------. .--------. .--------.
1628 '->| dir A |->| dir B |->| dir C |
1631 |'--------' |'--------' |'--------'
1632 '--------' '--------' '--------'
1638 .--------.
1639 .| root |-.
1641 .-------------|| |-'
1642 | |'--------'
1643 | '--|-|-|-'
1644 | .------' | '-------.
1646 | .--------. .--------. .--------.
1647 '->| dir A |->| dir B |->| dir C |
1650 |'--------' |'--------' |'--------'
1651 '--------' '--------' '--------'
1655 .--------.
1656 .| root |-.
1658 .-------|| |-'
1659 | |'--------'
1660 | '---|--|-'
1661 | .-' '-------------.
1663 | .--------. .--------. .--------.
1664 '->| dir A |->| dir B |->| dir C |
1667 |'--------' |'--------' |'--------'
1668 '--------' '--------' '--------'
1670 remove dir B from threaded linked-list, returning dir B to free blocks
1672 .--------.
1673 .| root |-.
1675 .-------|| |-'
1676 | |'--------'
1677 | '---|--|-'
1678 | .-' '-.
1680 | .--------. .--------.
1681 '->| dir A |->| dir C |
1684 |'--------' |'--------'
1685 '--------' '--------'
1692 threaded linked-list still contains the evicted block. We call this a
1693 half-orphan.
1696 .--------.
1697 .| root |-.
1699 .-------------|| |-'
1700 | |'--------'
1701 | '--|-|-|-'
1702 | .------' | '-------.
1704 | .--------. .--------. .--------.
1705 '->| dir A |->| dir B |->| dir C |
1708 |'--------' |'--------' |'--------'
1709 '--------' '--------' '--------'
1713 .--------.
1714 .| root |-.
1716 .----------------|| |-'
1717 | |'--------'
1718 | '-|-||-|-'
1719 | .--------' || '-----.
1721 | .--------. .--------. .--------.
1722 '->| dir A |---->| dir B |->| dir C |
1723 || |-. | | || |
1725 |'--------' | '--------' |'--------'
1726 '--------' | v '--------'
1727 | .--------.
1728 '->| dir B |
1731 '--------'
1735 .--------.
1736 .| root |-.
1738 .----------------|| |-'
1739 | |'--------'
1740 | '-|-||-|-'
1741 | .--------' || '-------.
1743 | .--------. .--------. .--------.
1744 '->| dir A |---->| dir B |--->| dir C |
1745 || |-. | | .->| |
1747 |'--------' | '--------' | |'--------'
1748 '--------' | v | '--------'
1749 | .--------. |
1750 '->| dir B | |
1753 '--------' |
1755 .--------. |
1756 | dir B |--'
1759 '--------'
1761 insert replacement in threaded linked-list, creating a half-orphan
1763 .--------.
1764 .| root |-.
1766 .----------------|| |-'
1767 | |'--------'
1768 | '-|-||-|-'
1769 | .--------' || '-------.
1771 | .--------. .--------. .--------.
1772 '->| dir A |---->| dir B |--->| dir C |
1773 || |-. | | .->| |
1775 |'--------' | '--------' | |'--------'
1776 '--------' | v | '--------'
1777 | .--------. |
1781 | '--------' |
1783 | .--------. |
1784 '->| dir B |--'
1787 '--------'
1791 .--------.
1792 .| root |-.
1794 .-------------|| |-'
1795 | |'--------'
1796 | '--|-|-|-'
1797 | .------' | '-------.
1799 | .--------. .--------. .--------.
1800 '->| dir A |->| dir B |->| dir C |
1803 |'--------' |'--------' |'--------'
1804 '--------' '--------' '--------'
1807 Finding orphans and half-orphans is expensive, requiring a _O(n²)_
1811 boot, and a read-only littlefs can ignore the threaded linked-list entirely.
1828 filesystems. As a filesystem designed for power-loss, it's important we get
1833 - We definitely can't just let power-loss result in duplicated or lost files.
1835 cases. We were only able to be lazy about the threaded linked-list because
1838 - Some filesystems propagate COW operations up the tree until a common parent
1842 - In a previous version of littlefs we tried to solve this problem by going
1852 ---
1866 .--------. .--------. .--------. .--------. .--------.
1867 .| |->| gdelta |->| |->| gdelta |->| gdelta |
1870 |'--------' |'--------' |'--------' |'--------' |'--------'
1871 '--------' '----|---' '--------' '----|---' '----|---'
1873 0x00 --> xor ------------------> xor ------> xor --> gstate 0x12
1882 .--------. .--------. .--------. .--------. .--------.
1883 .| |->| gdelta |->| |->| gdelta |->| gdelta |
1886 |'--------' |'--------' |'--------' |'--------' |'--------'
1887 '--------' '----|---' '--------' '--|---|-' '----|---'
1889 0x00 --> xor ----------------> xor -|------> xor --> gstate = 0x12
1892 change gstate to 0xab --> xor <------------|--------------------------'
1894 '------------> xor
1897 .--------. .--------. .--------. .--------. .--------.
1898 .| |->| gdelta |->| |->| gdelta |->| gdelta |
1901 |'--------' |'--------' |'--------' |'--------' |'--------'
1902 '--------' '----|---' '--------' '----|---' '----|---'
1904 0x00 --> xor ------------------> xor ------> xor --> gstate = 0xab
1918 ---
1925 .--------. gstate = no move
1926 .| root |-.
1928 .-------------|| |-'
1929 | |'--------'
1930 | '--|-|-|-'
1931 | .------' | '-------.
1933 | .--------. .--------. .--------.
1934 '->| dir A |->| dir B |->| dir C |
1937 |'--------' |'--------' |'--------'
1938 '----|---' '--------' '--------'
1940 .--------.
1944 '--------'
1948 .--------. gstate = moving file D in dir A (m1)
1949 .| root |-.
1951 .-------------|| |-'
1952 | |'--------'
1953 | '--|-|-|-'
1954 | .------' | '-------.
1956 | .--------. .--------. .--------.
1957 '->| dir A |->| dir B |->| dir C |
1960 |'--------' |'--------' |'--------'
1961 '----|---' '--------' '----|---'
1962 | .----------------'
1964 .--------.
1968 '--------'
1972 .--------. gstate = no move (m1^~m1)
1973 .| root |-.
1975 .-------------|| |-'
1976 | |'--------'
1977 | '--|-|-|-'
1978 | .------' | '-------.
1980 | .--------. .--------. .--------.
1981 '->| dir A |->| dir B |->| dir C |
1984 |'--------' |'--------' |'--------'
1985 '--------' '--------' '----|---'
1987 .--------.
1991 '--------'
2002 .--------. gstate = moving file D in dir A (m1)
2003 .| root |-. ^
2004 || |------------> xor
2005 .---------------|| |-' ^
2006 | |'--------' |
2007 | '--|-|-|-' |
2008 | .--------' | '---------. |
2010 | | .----------> xor --------> xor
2012 | .--------. | .--------. | .--------. |
2013 '->| dir A |-|->| dir B |-|->| dir C | |
2014 || |-' || |-' || gdelta |-'
2016 |'--------' |'--------' |'--------'
2017 '----|---' '--------' '----|---'
2018 | .---------------------'
2020 .--------.
2024 '--------'
2028 linked-list to consider, but leaving the threaded linked-list unchanged works
2032 .--------. gstate = no move (m1^~m1)
2033 .| root |-.
2035 .-------------|| |-'
2036 | |'--------'
2037 | '--|-|-|-'
2038 | .------' | '-------.
2040 | .--------. .--------. .--------.
2041 '->| dir A |->| dir B |->| dir C |
2044 |'--------' |'--------' |'--------'
2045 '--------' '--------' '----|---'
2047 .--------.
2051 '--------'
2055 .--------. gstate = moving dir B in root (m1^~m1^m2)
2056 .| root |-.
2058 .--------------|| |-'
2059 | |'--------'
2060 | '--|-|-|-'
2061 | .-------' | '----------.
2063 | .--------. | .--------.
2064 '->| dir A |-. | .->| dir C |
2067 |'--------' | | | |'--------'
2068 '--------' | | | '---|--|-'
2069 | | .-------' |
2071 | .--------. | .--------.
2072 '->| dir B |-' | file D |
2075 |'--------' '--------'
2076 '--------'
2080 .--------. gstate = no move (m1^~m1^m2^~m2)
2081 .| root |-.
2083 .-----------|| =~m2 |-'
2084 | |'--------'
2085 | '---|--|-'
2086 | .-----' '-----.
2088 | .--------. .--------.
2089 '->| dir A |-. .->| dir C |
2091 || =~m1 | | '-|| =m1^m2 |-------.
2092 |'--------' | |'--------' |
2093 '--------' | '---|--|-' |
2094 | .-' '-. |
2096 | .--------. .--------. |
2097 '->| dir B |--| file D |-'
2100 |'--------' '--------'
2101 '--------'
2115 [wikipedia-flash]: https://en.wikipedia.org/wiki/Flash_memory
2116 [wikipedia-sna]: https://en.wikipedia.org/wiki/Serial_number_arithmetic
2117 [wikipedia-crc]: https://en.wikipedia.org/wiki/Cyclic_redundancy_check
2118 [wikipedia-cow]: https://en.wikipedia.org/wiki/Copy-on-write
2119 [wikipedia-B-tree]: https://en.wikipedia.org/wiki/B-tree
2120 [wikipedia-B+-tree]: https://en.wikipedia.org/wiki/B%2B_tree
2121 [wikipedia-skip-list]: https://en.wikipedia.org/wiki/Skip_list
2122 [wikipedia-ctz]: https://en.wikipedia.org/wiki/Count_trailing_zeros
2123 [wikipedia-ecc]: https://en.wikipedia.org/wiki/Error_correction_code
2124 [wikipedia-hamming-bound]: https://en.wikipedia.org/wiki/Hamming_bound
2125 [wikipedia-dynamic-wear-leveling]: https://en.wikipedia.org/wiki/Wear_leveling#Dynamic_wear_leveling
2126 [wikipedia-static-wear-leveling]: https://en.wikipedia.org/wiki/Wear_leveling#Static_wear_leveling
2127 [wikipedia-ftl]: https://en.wikipedia.org/wiki/Flash_translation_layer
2135 [jffs]: https://www.sourceware.org/jffs2/jffs2-html
2136 [yaffs]: https://yaffs.net/documents/how-yaffs-works
2147 [metadata-formula1]: https://latex.codecogs.com/svg.latex?cost%20%3D%20n%20+%20n%20%5Cfrac%7Bs…
2148 [metadata-formula2]: https://latex.codecogs.com/svg.latex?s%20%3D%20r%20%5Cfrac%7Bsize%7D%7Bn%7D
2149 [metadata-formula3]: https://latex.codecogs.com/svg.latex?d%20%3D%20%281-r%29%20%5Cfrac%7Bsize%7D%7…
2150 [metadata-formula4]: https://latex.codecogs.com/svg.latex?cost%20%3D%20n%20+%20n%20%5Cfrac%7Br…
2152 …-formula1]: https://latex.codecogs.com/svg.latex?%5Clim_%7Bn%5Cto%5Cinfty%7D%5Cfrac%7B1%7D%7Bn%7D%…
2153 [ctz-formula2]: https://latex.codecogs.com/svg.latex?B%20%3D%20%5Cfrac%7Bw%7D%7B8%7D%5Cleft%5Clceil…
2154 [ctz-formula3]: https://latex.codecogs.com/svg.latex?N%20%3D%20%5Csum_i%5En%5Cleft%5BB-%5Cfrac%7Bw%…
2155 [ctz-formula4]: https://latex.codecogs.com/svg.latex?%5Csum_i%5En%5Cleft%28%5Ctext%7Bctz%7D%28i%29&…
2156 [ctz-formula5]: https://latex.codecogs.com/svg.latex?N%20%3D%20Bn%20-%20%5Cfrac%7Bw%7D%7B8%7D%5Clef…
2157 …-formula6]: https://latex.codecogs.com/svg.latex?n%20%3D%20%5Cleft%5Clfloor%5Cfrac%7BN-%5Cfrac%7Bw…
2158 [ctz-formula7]: https://latex.codecogs.com/svg.latex?%5Cmathit%7Boff%7D%20%3D%20N%20-%20%5Cleft%28B…
2171 [metadata-cost-graph]: https://raw.githubusercontent.com/geky/littlefs/gh-images/metadata-cost.svg?…
2172 [wear-distribution-graph]: https://raw.githubusercontent.com/geky/littlefs/gh-images/wear-distribut…
2173 [file-cost-graph]: https://raw.githubusercontent.com/geky/littlefs/gh-images/file-cost.svg?sanitize…