Lines Matching +full:commit +full:- +full:tree
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
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,
364 commit A
365 .----------------.----------------. .----------------.----------------.
367 |----------------|----------------| |----------------|----------------|
369 | v | | |----------------| |
371 | | | |----------------| |
378 '----------------'----------------' '----------------'----------------'
383 operation. What we can do instead is group multiple entries into a commit
388 commit B and A'
389 .----------------.----------------. .----------------.----------------.
391 |----------------|----------------| |----------------|----------------|
393 |----------------| | |----------------| |
395 |----------------| | |----------------| |
397 | v | | |----------------| |
399 | | | |----------------| |
401 | | | |----------------| |
402 '----------------'----------------' '----------------'----------------'
418 the revision count. Because we can commit multiple entries at once, we can
420 loss. It's only when the commit's checksum is written that the compacted
424 commit B', need to compact
425 .----------------.----------------. .----------------.----------------.
427 |----------------|----------------| |----------------|----------------|
429 |----------------| | |----------------|----------------|
431 |----------------| | |----------------|----------------|
433 |----------------| | |----------------|----------------|
435 |----------------| | |----------------| v |
437 |----------------| | |----------------| |
438 '----------------'----------------' '----------------'----------------'
455 and then inserting the tail pointer during the commit to the original
459 commit C and D, need to split
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
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]
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 '--------' '--------' '--------' '--------'
815 commit to metadata pair
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 ---
897 through every block on storage and check each one against our filesystem tree;
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
1485 directory pointers in our metadata pairs, which gives us a directory tree, much
1489 .--------.
1493 |'--------'
1494 '---|--|-'
1495 .-' '-------------------------.
1497 .--------. .--------. .--------.
1498 .| dir A |------->| dir A | .| dir B |
1501 |'--------' |'--------' |'--------'
1502 '---|--|-' '----|---' '---|--|-'
1503 .-' '-. | .-' '-.
1505 .--------. .--------. .--------. .--------. .--------.
1509 '--------' '--------' '--------' '--------' '--------'
1513 [RAM]. The directory tree is a tree, and the unfortunate fact is you can't
1514 traverse a tree with constant RAM.
1516 Fortunately, the elements of our tree are metadata pairs, so unlike CTZ
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 '--------' '--------' '--------' '--------' '--------'
1546 whenever we want to manipulate the directory tree, multiple pointers need to be
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.
1558 Adding a directory to our tree:
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 '--------' '--------'
1688 In addition to normal directory tree operations, we can use orphans to evict
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.
1815 while manipulating the directory tree (foreshadowing!).
1823 In littlefs we can atomically commit to directories, but we can't create
1824 an atomic commit that spans multiple directories. The filesystem must go
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
1839 is found. Unfortunately this interacts poorly with our threaded tree and
1842 - In a previous version of littlefs we tried to solve this problem by going
1852 ---
1856 entries in one commit gives us a powerful tool for crafting complex atomic
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 [ctz-formula1]: https://latex.codecogs.com/svg.latex?%5Clim_%7Bn%5Cto%5Cinfty%7D%5Cfrac%7B1%7D%7Bn%…
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…