1## littlefs technical specification 2 3This is the technical specification of the little filesystem with on-disk 4version lfs2.1. This document covers the technical details of how the littlefs 5is stored on disk for introspection and tooling. This document assumes you are 6familiar with the design of the littlefs, for more info on how littlefs works 7check out [DESIGN.md](DESIGN.md). 8 9``` 10 | | | .---._____ 11 .-----. | | 12--|o |---| littlefs | 13--| |---| | 14 '-----' '----------' 15 | | | 16``` 17 18## Some quick notes 19 20- littlefs is a block-based filesystem. The disk is divided into an array of 21 evenly sized blocks that are used as the logical unit of storage. 22 23- Block pointers are stored in 32 bits, with the special value `0xffffffff` 24 representing a null block address. 25 26- In addition to the logical block size (which usually matches the erase 27 block size), littlefs also uses a program block size and read block size. 28 These determine the alignment of block device operations, but don't need 29 to be consistent for portability. 30 31- By default, all values in littlefs are stored in little-endian byte order. 32 33## Directories / Metadata pairs 34 35Metadata pairs form the backbone of littlefs and provide a system for 36distributed atomic updates. Even the superblock is stored in a metadata pair. 37 38As their name suggests, a metadata pair is stored in two blocks, with one block 39providing a backup during erase cycles in case power is lost. These two blocks 40are not necessarily sequential and may be anywhere on disk, so a "pointer" to a 41metadata pair is stored as two block pointers. 42 43On top of this, each metadata block behaves as an appendable log, containing a 44variable number of commits. Commits can be appended to the metadata log in 45order to update the metadata without requiring an erase cycles. Note that 46successive commits may supersede the metadata in previous commits. Only the 47most recent metadata should be considered valid. 48 49The high-level layout of a metadata block is fairly simple: 50 51``` 52 .---------------------------------------. 53.-| revision count | entries | \ 54| |-------------------+ | | 55| | | | 56| | | +-- 1st commit 57| | | | 58| | +-------------------| | 59| | | CRC | / 60| |-------------------+-------------------| 61| | entries | \ 62| | | | 63| | | +-- 2nd commit 64| | +-------------------+--------------| | 65| | | CRC | padding | / 66| |----+-------------------+--------------| 67| | entries | \ 68| | | | 69| | | +-- 3rd commit 70| | +-------------------+---------| | 71| | | CRC | | / 72| |---------+-------------------+ | 73| | unwritten storage | more commits 74| | | | 75| | | v 76| | | 77| | | 78| '---------------------------------------' 79'---------------------------------------' 80``` 81 82Each metadata block contains a 32-bit revision count followed by a number of 83commits. Each commit contains a variable number of metadata entries followed 84by a 32-bit CRC. 85 86Note also that entries aren't necessarily word-aligned. This allows us to 87store metadata more compactly, however we can only write to addresses that are 88aligned to our program block size. This means each commit may have padding for 89alignment. 90 91Metadata block fields: 92 931. **Revision count (32-bits)** - Incremented every erase cycle. If both blocks 94 contain valid commits, only the block with the most recent revision count 95 should be used. Sequence comparison must be used to avoid issues with 96 integer overflow. 97 982. **CRC (32-bits)** - Detects corruption from power-loss or other write 99 issues. Uses a CRC-32 with a polynomial of `0x04c11db7` initialized 100 with `0xffffffff`. 101 102Entries themselves are stored as a 32-bit tag followed by a variable length 103blob of data. But exactly how these tags are stored is a little bit tricky. 104 105Metadata blocks support both forward and backward iteration. In order to do 106this without duplicating the space for each tag, neighboring entries have their 107tags XORed together, starting with `0xffffffff`. 108 109``` 110 Forward iteration Backward iteration 111 112.-------------------. 0xffffffff .-------------------. 113| revision count | | | revision count | 114|-------------------| v |-------------------| 115| tag ~A |---> xor -> tag A | tag ~A |---> xor -> 0xffffffff 116|-------------------| | |-------------------| ^ 117| data A | | | data A | | 118| | | | | | 119| | | | | | 120|-------------------| v |-------------------| | 121| tag AxB |---> xor -> tag B | tag AxB |---> xor -> tag A 122|-------------------| | |-------------------| ^ 123| data B | | | data B | | 124| | | | | | 125| | | | | | 126|-------------------| v |-------------------| | 127| tag BxC |---> xor -> tag C | tag BxC |---> xor -> tag B 128|-------------------| |-------------------| ^ 129| data C | | data C | | 130| | | | tag C 131| | | | 132| | | | 133'-------------------' '-------------------' 134``` 135 136Here's a more complete example of metadata block containing 4 entries: 137 138``` 139 .---------------------------------------. 140.-| revision count | tag ~A | \ 141| |-------------------+-------------------| | 142| | data A | | 143| | | | 144| |-------------------+-------------------| | 145| | tag AxB | data B | <--. | 146| |-------------------+ | | | 147| | | | +-- 1st commit 148| | +-------------------+---------| | | 149| | | tag BxC | | <-.| | 150| |---------+-------------------+ | || | 151| | data C | || | 152| | | || | 153| |-------------------+-------------------| || | 154| | tag CxCRC | CRC | || / 155| |-------------------+-------------------| || 156| | tag CRCxA' | data A' | || \ 157| |-------------------+ | || | 158| | | || | 159| | +-------------------+----| || +-- 2nd commit 160| | | tag CRCxA' | | || | 161| |--------------+-------------------+----| || | 162| | CRC | padding | || / 163| |--------------+----+-------------------| || 164| | tag CRCxA'' | data A'' | <---. \ 165| |-------------------+ | ||| | 166| | | ||| | 167| | +-------------------+---------| ||| | 168| | | tag A''xD | | < ||| | 169| |---------+-------------------+ | |||| +-- 3rd commit 170| | data D | |||| | 171| | +---------| |||| | 172| | | tag Dx| |||| | 173| |---------+-------------------+---------| |||| | 174| |CRC | CRC | | |||| / 175| |---------+-------------------+ | |||| 176| | unwritten storage | |||| more commits 177| | | |||| | 178| | | |||| v 179| | | |||| 180| | | |||| 181| '---------------------------------------' |||| 182'---------------------------------------' |||'- most recent A 183 ||'-- most recent B 184 |'--- most recent C 185 '---- most recent D 186``` 187 188Two things to note before we get into the details around tag encoding: 189 1901. Each tag contains a valid bit used to indicate if the tag and containing 191 commit is valid. After XORing, this bit should always be zero. 192 193 At the end of each commit, the valid bit of the previous tag is XORed 194 with the lowest bit in the type field of the CRC tag. This allows 195 the CRC tag to force the next commit to fail the valid bit test if it 196 has not yet been written to. 197 1982. The valid bit alone is not enough info to know if the next commit has been 199 erased. We don't know the order bits will be programmed in a program block, 200 so it's possible that the next commit had an attempted program that left the 201 valid bit unchanged. 202 203 To ensure we only ever program erased bytes, each commit can contain an 204 optional forward-CRC (FCRC). An FCRC contains a checksum of some amount of 205 bytes in the next commit at the time it was erased. 206 207 ``` 208 .-------------------. \ \ 209 | revision count | | | 210 |-------------------| | | 211 | metadata | | | 212 | | +---. +-- current commit 213 | | | | | 214 |-------------------| | | | 215 | FCRC ---|-. | | 216 |-------------------| / | | | 217 | CRC -----|-' / 218 |-------------------| | 219 | padding | | padding (does't need CRC) 220 | | | 221 |-------------------| \ | \ 222 | erased? | +-' | 223 | | | | +-- next commit 224 | v | / | 225 | | / 226 | | 227 '-------------------' 228 ``` 229 230 If the FCRC is missing or the checksum does not match, we must assume a 231 commit was attempted but failed due to power-loss. 232 233 Note that end-of-block commits do not need an FCRC. 234 235## Metadata tags 236 237So in littlefs, 32-bit tags describe every type of metadata. And this means 238_every_ type of metadata, including file entries, directory fields, and 239global state. Even the CRCs used to mark the end of commits get their own tag. 240 241Because of this, the tag format contains some densely packed information. Note 242that there are multiple levels of types which break down into more info: 243 244``` 245[---- 32 ----] 246[1|-- 11 --|-- 10 --|-- 10 --] 247 ^. ^ . ^ ^- length 248 |. | . '------------ id 249 |. '-----.------------------ type (type3) 250 '.-----------.------------------ valid bit 251 [-3-|-- 8 --] 252 ^ ^- chunk 253 '------- type (type1) 254``` 255 256 257Before we go further, there's one important thing to note. These tags are 258**not** stored in little-endian. Tags stored in commits are actually stored 259in big-endian (and is the only thing in littlefs stored in big-endian). This 260little bit of craziness comes from the fact that the valid bit must be the 261first bit in a commit, and when converted to little-endian, the valid bit finds 262itself in byte 4. We could restructure the tag to store the valid bit lower, 263but, because none of the fields are byte-aligned, this would be more 264complicated than just storing the tag in big-endian. 265 266Another thing to note is that both the tags `0x00000000` and `0xffffffff` are 267invalid and can be used for null values. 268 269Metadata tag fields: 270 2711. **Valid bit (1-bit)** - Indicates if the tag is valid. 272 2732. **Type3 (11-bits)** - Type of the tag. This field is broken down further 274 into a 3-bit abstract type and an 8-bit chunk field. Note that the value 275 `0x000` is invalid and not assigned a type. 276 277 1. **Type1 (3-bits)** - Abstract type of the tag. Groups the tags into 278 8 categories that facilitate bitmasked lookups. 279 280 2. **Chunk (8-bits)** - Chunk field used for various purposes by the different 281 abstract types. type1+chunk+id form a unique identifier for each tag in the 282 metadata block. 283 2843. **Id (10-bits)** - File id associated with the tag. Each file in a metadata 285 block gets a unique id which is used to associate tags with that file. The 286 special value `0x3ff` is used for any tags that are not associated with a 287 file, such as directory and global metadata. 288 2894. **Length (10-bits)** - Length of the data in bytes. The special value 290 `0x3ff` indicates that this tag has been deleted. 291 292## Metadata types 293 294What follows is an exhaustive list of metadata in littlefs. 295 296--- 297#### `0x401` LFS_TYPE_CREATE 298 299Creates a new file with this id. Note that files in a metadata block 300don't necessarily need a create tag. All a create does is move over any 301files using this id. In this sense a create is similar to insertion into 302an imaginary array of files. 303 304The create and delete tags allow littlefs to keep files in a directory 305ordered alphabetically by filename. 306 307--- 308#### `0x4ff` LFS_TYPE_DELETE 309 310Deletes the file with this id. An inverse to create, this tag moves over 311any files neighboring this id similar to a deletion from an imaginary 312array of files. 313 314--- 315#### `0x0xx` LFS_TYPE_NAME 316 317Associates the id with a file name and file type. 318 319The data contains the file name stored as an ASCII string (may be expanded to 320UTF8 in the future). 321 322The chunk field in this tag indicates an 8-bit file type which can be one of 323the following. 324 325Currently, the name tag must precede any other tags associated with the id and 326can not be reassigned without deleting the file. 327 328Layout of the name tag: 329 330``` 331 tag data 332[-- 32 --][--- variable length ---] 333[1| 3| 8 | 10 | 10 ][--- (size * 8) ---] 334 ^ ^ ^ ^ ^- size ^- file name 335 | | | '------ id 336 | | '----------- file type 337 | '-------------- type1 (0x0) 338 '----------------- valid bit 339``` 340 341Name fields: 342 3431. **file type (8-bits)** - Type of the file. 344 3452. **file name** - File name stored as an ASCII string. 346 347--- 348#### `0x001` LFS_TYPE_REG 349 350Initializes the id + name as a regular file. 351 352How each file is stored depends on its struct tag, which is described below. 353 354--- 355#### `0x002` LFS_TYPE_DIR 356 357Initializes the id + name as a directory. 358 359Directories in littlefs are stored on disk as a linked-list of metadata pairs, 360each pair containing any number of files in alphabetical order. A pointer to 361the directory is stored in the struct tag, which is described below. 362 363--- 364#### `0x0ff` LFS_TYPE_SUPERBLOCK 365 366Initializes the id as a superblock entry. 367 368The superblock entry is a special entry used to store format-time configuration 369and identify the filesystem. 370 371The name is a bit of a misnomer. While the superblock entry serves the same 372purpose as a superblock found in other filesystems, in littlefs the superblock 373does not get a dedicated block. Instead, the superblock entry is duplicated 374across a linked-list of metadata pairs rooted on the blocks 0 and 1. The last 375metadata pair doubles as the root directory of the filesystem. 376 377``` 378 .--------. .--------. .--------. .--------. .--------. 379.| super |->| super |->| super |->| super |->| file B | 380|| block | || block | || block | || block | || file C | 381|| | || | || | || file A | || file D | 382|'--------' |'--------' |'--------' |'--------' |'--------' 383'--------' '--------' '--------' '--------' '--------' 384 385\----------------+----------------/ \----------+----------/ 386 superblock pairs root directory 387``` 388 389The filesystem starts with only the root directory. The superblock metadata 390pairs grow every time the root pair is compacted in order to prolong the 391life of the device exponentially. 392 393The contents of the superblock entry are stored in a name tag with the 394superblock type and an inline-struct tag. The name tag contains the magic 395string "littlefs", while the inline-struct tag contains version and 396configuration information. 397 398Layout of the superblock name tag and inline-struct tag: 399 400``` 401 tag data 402[-- 32 --][-- 32 --|-- 32 --] 403[1|- 11 -| 10 | 10 ][--- 64 ---] 404 ^ ^ ^ ^- size (8) ^- magic string ("littlefs") 405 | | '------ id (0) 406 | '------------ type (0x0ff) 407 '----------------- valid bit 408 409 tag data 410[-- 32 --][-- 32 --|-- 32 --|-- 32 --] 411[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --|-- 32 --] 412 ^ ^ ^ ^ ^- version ^- block size ^- block count 413 | | | | [-- 32 --|-- 32 --|-- 32 --] 414 | | | | [-- 32 --|-- 32 --|-- 32 --] 415 | | | | ^- name max ^- file max ^- attr max 416 | | | '- size (24) 417 | | '------ id (0) 418 | '------------ type (0x201) 419 '----------------- valid bit 420``` 421 422Superblock fields: 423 4241. **Magic string (8-bytes)** - Magic string indicating the presence of 425 littlefs on the device. Must be the string "littlefs". 426 4272. **Version (32-bits)** - The version of littlefs at format time. The version 428 is encoded in a 32-bit value with the upper 16-bits containing the major 429 version, and the lower 16-bits containing the minor version. 430 431 This specification describes version 2.0 (`0x00020000`). 432 4333. **Block size (32-bits)** - Size of the logical block size used by the 434 filesystem in bytes. 435 4364. **Block count (32-bits)** - Number of blocks in the filesystem. 437 4385. **Name max (32-bits)** - Maximum size of file names in bytes. 439 4406. **File max (32-bits)** - Maximum size of files in bytes. 441 4427. **Attr max (32-bits)** - Maximum size of file attributes in bytes. 443 444The superblock must always be the first entry (id 0) in a metadata pair as well 445as be the first entry written to the block. This means that the superblock 446entry can be read from a device using offsets alone. 447 448--- 449#### `0x2xx` LFS_TYPE_STRUCT 450 451Associates the id with an on-disk data structure. 452 453The exact layout of the data depends on the data structure type stored in the 454chunk field and can be one of the following. 455 456Any type of struct supersedes all other structs associated with the id. For 457example, appending a ctz-struct replaces an inline-struct on the same file. 458 459--- 460#### `0x200` LFS_TYPE_DIRSTRUCT 461 462Gives the id a directory data structure. 463 464Directories in littlefs are stored on disk as a linked-list of metadata pairs, 465each pair containing any number of files in alphabetical order. 466 467``` 468 | 469 v 470 .--------. .--------. .--------. .--------. .--------. .--------. 471.| file A |->| file D |->| file G |->| file I |->| file J |->| file M | 472|| file B | || file E | || file H | || | || file K | || file N | 473|| file C | || file F | || | || | || file L | || | 474|'--------' |'--------' |'--------' |'--------' |'--------' |'--------' 475'--------' '--------' '--------' '--------' '--------' '--------' 476``` 477 478The dir-struct tag contains only the pointer to the first metadata-pair in the 479directory. The directory size is not known without traversing the directory. 480 481The pointer to the next metadata-pair in the directory is stored in a tail tag, 482which is described below. 483 484Layout of the dir-struct tag: 485 486``` 487 tag data 488[-- 32 --][-- 32 --|-- 32 --] 489[1|- 11 -| 10 | 10 ][--- 64 ---] 490 ^ ^ ^ ^- size (8) ^- metadata pair 491 | | '------ id 492 | '------------ type (0x200) 493 '----------------- valid bit 494``` 495 496Dir-struct fields: 497 4981. **Metadata pair (8-bytes)** - Pointer to the first metadata-pair 499 in the directory. 500 501--- 502#### `0x201` LFS_TYPE_INLINESTRUCT 503 504Gives the id an inline data structure. 505 506Inline structs store small files that can fit in the metadata pair. In this 507case, the file data is stored directly in the tag's data area. 508 509Layout of the inline-struct tag: 510 511``` 512 tag data 513[-- 32 --][--- variable length ---] 514[1|- 11 -| 10 | 10 ][--- (size * 8) ---] 515 ^ ^ ^ ^- size ^- inline data 516 | | '------ id 517 | '------------ type (0x201) 518 '----------------- valid bit 519``` 520 521Inline-struct fields: 522 5231. **Inline data** - File data stored directly in the metadata-pair. 524 525--- 526#### `0x202` LFS_TYPE_CTZSTRUCT 527 528Gives the id a CTZ skip-list data structure. 529 530CTZ skip-lists store files that can not fit in the metadata pair. These files 531are stored in a skip-list in reverse, with a pointer to the head of the 532skip-list. Note that the head of the skip-list and the file size is enough 533information to read the file. 534 535How exactly CTZ skip-lists work is a bit complicated. A full explanation can be 536found in the [DESIGN.md](DESIGN.md#ctz-skip-lists). 537 538A quick summary: For every _n_‍th block where _n_ is divisible by 5392‍_ˣ_, that block contains a pointer to block _n_-2‍_ˣ_. 540These pointers are stored in increasing order of _x_ in each block of the file 541before the actual data. 542 543``` 544 | 545 v 546.--------. .--------. .--------. .--------. .--------. .--------. 547| A |<-| D |<-| G |<-| J |<-| M |<-| P | 548| B |<-| E |--| H |<-| K |--| N | | Q | 549| C |<-| F |--| I |--| L |--| O | | | 550'--------' '--------' '--------' '--------' '--------' '--------' 551 block 0 block 1 block 2 block 3 block 4 block 5 552 1 skip 2 skips 1 skip 3 skips 1 skip 553``` 554 555Note that the maximum number of pointers in a block is bounded by the maximum 556file size divided by the block size. With 32 bits for file size, this results 557in a minimum block size of 104 bytes. 558 559Layout of the CTZ-struct tag: 560 561``` 562 tag data 563[-- 32 --][-- 32 --|-- 32 --] 564[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --] 565 ^ ^ ^ ^ ^ ^- file size 566 | | | | '-------------------- file head 567 | | | '- size (8) 568 | | '------ id 569 | '------------ type (0x202) 570 '----------------- valid bit 571``` 572 573CTZ-struct fields: 574 5751. **File head (32-bits)** - Pointer to the block that is the head of the 576 file's CTZ skip-list. 577 5782. **File size (32-bits)** - Size of the file in bytes. 579 580--- 581#### `0x3xx` LFS_TYPE_USERATTR 582 583Attaches a user attribute to an id. 584 585littlefs has a concept of "user attributes". These are small user-provided 586attributes that can be used to store things like timestamps, hashes, 587permissions, etc. 588 589Each user attribute is uniquely identified by an 8-bit type which is stored in 590the chunk field, and the user attribute itself can be found in the tag's data. 591 592There are currently no standard user attributes and a portable littlefs 593implementation should work with any user attributes missing. 594 595Layout of the user-attr tag: 596 597``` 598 tag data 599[-- 32 --][--- variable length ---] 600[1| 3| 8 | 10 | 10 ][--- (size * 8) ---] 601 ^ ^ ^ ^ ^- size ^- attr data 602 | | | '------ id 603 | | '----------- attr type 604 | '-------------- type1 (0x3) 605 '----------------- valid bit 606``` 607 608User-attr fields: 609 6101. **Attr type (8-bits)** - Type of the user attributes. 611 6122. **Attr data** - The data associated with the user attribute. 613 614--- 615#### `0x6xx` LFS_TYPE_TAIL 616 617Provides the tail pointer for the metadata pair itself. 618 619The metadata pair's tail pointer is used in littlefs for a linked-list 620containing all metadata pairs. The chunk field contains the type of the tail, 621which indicates if the following metadata pair is a part of the directory 622(hard-tail) or only used to traverse the filesystem (soft-tail). 623 624``` 625 .--------. 626 .| dir A |-. 627 ||softtail| | 628.--------| |-' 629| |'--------' 630| '---|--|-' 631| .-' '-------------. 632| v v 633| .--------. .--------. .--------. 634'->| dir B |->| dir B |->| dir C | 635 ||hardtail| ||softtail| || | 636 || | || | || | 637 |'--------' |'--------' |'--------' 638 '--------' '--------' '--------' 639``` 640 641Currently any type supersedes any other preceding tails in the metadata pair, 642but this may change if additional metadata pair state is added. 643 644A note about the metadata pair linked-list: Normally, this linked-list contains 645every metadata pair in the filesystem. However, there are some operations that 646can cause this linked-list to become out of sync if a power-loss were to occur. 647When this happens, littlefs sets the "sync" flag in the global state. How 648exactly this flag is stored is described below. 649 650When the sync flag is set: 651 6521. The linked-list may contain an orphaned directory that has been removed in 653 the filesystem. 6542. The linked-list may contain a metadata pair with a bad block that has been 655 replaced in the filesystem. 656 657If the sync flag is set, the threaded linked-list must be checked for these 658errors before it can be used reliably. Note that the threaded linked-list can 659be ignored if littlefs is mounted read-only. 660 661Layout of the tail tag: 662 663``` 664 tag data 665[-- 32 --][-- 32 --|-- 32 --] 666[1| 3| 8 | 10 | 10 ][--- 64 ---] 667 ^ ^ ^ ^ ^- size (8) ^- metadata pair 668 | | | '------ id 669 | | '---------- tail type 670 | '------------- type1 (0x6) 671 '---------------- valid bit 672``` 673 674Tail fields: 675 6761. **Tail type (8-bits)** - Type of the tail pointer. 677 6782. **Metadata pair (8-bytes)** - Pointer to the next metadata-pair. 679 680--- 681#### `0x600` LFS_TYPE_SOFTTAIL 682 683Provides a tail pointer that points to the next metadata pair in the 684filesystem. 685 686In this case, the next metadata pair is not a part of our current directory 687and should only be followed when traversing the entire filesystem. 688 689--- 690#### `0x601` LFS_TYPE_HARDTAIL 691 692Provides a tail pointer that points to the next metadata pair in the 693directory. 694 695In this case, the next metadata pair belongs to the current directory. Note 696that because directories in littlefs are sorted alphabetically, the next 697metadata pair should only contain filenames greater than any filename in the 698current pair. 699 700--- 701#### `0x7xx` LFS_TYPE_GSTATE 702 703Provides delta bits for global state entries. 704 705littlefs has a concept of "global state". This is a small set of state that 706can be updated by a commit to _any_ metadata pair in the filesystem. 707 708The way this works is that the global state is stored as a set of deltas 709distributed across the filesystem such that the global state can be found by 710the xor-sum of these deltas. 711 712``` 713 .--------. .--------. .--------. .--------. .--------. 714.| |->| gdelta |->| |->| gdelta |->| gdelta | 715|| | || 0x23 | || | || 0xff | || 0xce | 716|| | || | || | || | || | 717|'--------' |'--------' |'--------' |'--------' |'--------' 718'--------' '----|---' '--------' '----|---' '----|---' 719 v v v 720 0x00 --> xor ------------------> xor ------> xor --> gstate = 0x12 721``` 722 723Note that storing globals this way is very expensive in terms of storage usage, 724so any global state should be kept very small. 725 726The size and format of each piece of global state depends on the type, which 727is stored in the chunk field. Currently, the only global state is move state, 728which is outlined below. 729 730--- 731#### `0x7ff` LFS_TYPE_MOVESTATE 732 733Provides delta bits for the global move state. 734 735The move state in littlefs is used to store info about operations that could 736cause to filesystem to go out of sync if the power is lost. The operations 737where this could occur is moves of files between metadata pairs and any 738operation that changes metadata pairs on the threaded linked-list. 739 740In the case of moves, the move state contains a tag + metadata pair describing 741the source of the ongoing move. If this tag is non-zero, that means that power 742was lost during a move, and the file exists in two different locations. If this 743happens, the source of the move should be considered deleted, and the move 744should be completed (the source should be deleted) before any other write 745operations to the filesystem. 746 747In the case of operations to the threaded linked-list, a single "sync" bit is 748used to indicate that a modification is ongoing. If this sync flag is set, the 749threaded linked-list will need to be checked for errors before it can be used 750reliably. The exact cases to check for are described above in the tail tag. 751 752Layout of the move state: 753 754``` 755 tag data 756[-- 32 --][-- 32 --|-- 32 --|-- 32 --] 757[1|- 11 -| 10 | 10 ][1|- 11 -| 10 | 10 |--- 64 ---] 758 ^ ^ ^ ^ ^ ^ ^ ^- padding (0) ^- metadata pair 759 | | | | | | '------ move id 760 | | | | | '------------ move type 761 | | | | '----------------- sync bit 762 | | | | 763 | | | '- size (12) 764 | | '------ id (0x3ff) 765 | '------------ type (0x7ff) 766 '----------------- valid bit 767``` 768 769Move state fields: 770 7711. **Sync bit (1-bit)** - Indicates if the metadata pair threaded linked-list 772 is in-sync. If set, the threaded linked-list should be checked for errors. 773 7742. **Move type (11-bits)** - Type of move being performed. Must be either 775 `0x000`, indicating no move, or `0x4ff` indicating the source file should 776 be deleted. 777 7783. **Move id (10-bits)** - The file id being moved. 779 7804. **Metadata pair (8-bytes)** - Pointer to the metadata-pair containing 781 the move. 782 783--- 784#### `0x5xx` LFS_TYPE_CRC 785 786Last but not least, the CRC tag marks the end of a commit and provides a 787checksum for any commits to the metadata block. 788 789The first 32-bits of the data contain a CRC-32 with a polynomial of 790`0x04c11db7` initialized with `0xffffffff`. This CRC provides a checksum for 791all metadata since the previous CRC tag, including the CRC tag itself. For 792the first commit, this includes the revision count for the metadata block. 793 794However, the size of the data is not limited to 32-bits. The data field may 795larger to pad the commit to the next program-aligned boundary. 796 797In addition, the CRC tag's chunk field contains a set of flags which can 798change the behaviour of commits. Currently the only flag in use is the lowest 799bit, which determines the expected state of the valid bit for any following 800tags. This is used to guarantee that unwritten storage in a metadata block 801will be detected as invalid. 802 803Layout of the CRC tag: 804 805``` 806 tag data 807[-- 32 --][-- 32 --|--- variable length ---] 808[1| 3| 8 | 10 | 10 ][-- 32 --|--- (size * 8 - 32) ---] 809 ^ ^ ^ ^ ^ ^- crc ^- padding 810 | | | | '- size 811 | | | '------ id (0x3ff) 812 | | '----------- valid state 813 | '-------------- type1 (0x5) 814 '----------------- valid bit 815``` 816 817CRC fields: 818 8191. **Valid state (1-bit)** - Indicates the expected value of the valid bit for 820 any tags in the next commit. 821 8222. **CRC (32-bits)** - CRC-32 with a polynomial of `0x04c11db7` initialized 823 with `0xffffffff`. 824 8253. **Padding** - Padding to the next program-aligned boundary. No guarantees 826 are made about the contents. 827 828--- 829#### `0x5ff` LFS_TYPE_FCRC 830 831Added in lfs2.1, the optional FCRC tag contains a checksum of some amount of 832bytes in the next commit at the time it was erased. This allows us to ensure 833that we only ever program erased bytes, even if a previous commit failed due 834to power-loss. 835 836When programming a commit, the FCRC size must be at least as large as the 837program block size. However, the program block is not saved on disk, and can 838change between mounts, so the FCRC size on disk may be different than the 839current program block size. 840 841If the FCRC is missing or the checksum does not match, we must assume a 842commit was attempted but failed due to power-loss. 843 844Layout of the FCRC tag: 845 846``` 847 tag data 848[-- 32 --][-- 32 --|-- 32 --] 849[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --] 850 ^ ^ ^ ^ ^- fcrc size ^- fcrc 851 | | | '- size (8) 852 | | '------ id (0x3ff) 853 | '------------ type (0x5ff) 854 '----------------- valid bit 855``` 856 857FCRC fields: 858 8591. **FCRC size (32-bits)** - Number of bytes after this commit's CRC tag's 860 padding to include in the FCRC. 861 8622. **FCRC (32-bits)** - CRC of the bytes after this commit's CRC tag's padding 863 when erased. Like the CRC tag, this uses a CRC-32 with a polynomial of 864 `0x04c11db7` initialized with `0xffffffff`. 865 866--- 867
