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 the metadata pair, and 445the name tag must always be the first tag in the metadata pair. This makes it 446so that the magic string "littlefs" will always reside at offset=8 in a valid 447littlefs superblock. 448 449--- 450#### `0x2xx` LFS_TYPE_STRUCT 451 452Associates the id with an on-disk data structure. 453 454The exact layout of the data depends on the data structure type stored in the 455chunk field and can be one of the following. 456 457Any type of struct supersedes all other structs associated with the id. For 458example, appending a ctz-struct replaces an inline-struct on the same file. 459 460--- 461#### `0x200` LFS_TYPE_DIRSTRUCT 462 463Gives the id a directory data structure. 464 465Directories in littlefs are stored on disk as a linked-list of metadata pairs, 466each pair containing any number of files in alphabetical order. 467 468``` 469 | 470 v 471 .--------. .--------. .--------. .--------. .--------. .--------. 472.| file A |->| file D |->| file G |->| file I |->| file J |->| file M | 473|| file B | || file E | || file H | || | || file K | || file N | 474|| file C | || file F | || | || | || file L | || | 475|'--------' |'--------' |'--------' |'--------' |'--------' |'--------' 476'--------' '--------' '--------' '--------' '--------' '--------' 477``` 478 479The dir-struct tag contains only the pointer to the first metadata-pair in the 480directory. The directory size is not known without traversing the directory. 481 482The pointer to the next metadata-pair in the directory is stored in a tail tag, 483which is described below. 484 485Layout of the dir-struct tag: 486 487``` 488 tag data 489[-- 32 --][-- 32 --|-- 32 --] 490[1|- 11 -| 10 | 10 ][--- 64 ---] 491 ^ ^ ^ ^- size (8) ^- metadata pair 492 | | '------ id 493 | '------------ type (0x200) 494 '----------------- valid bit 495``` 496 497Dir-struct fields: 498 4991. **Metadata pair (8-bytes)** - Pointer to the first metadata-pair 500 in the directory. 501 502--- 503#### `0x201` LFS_TYPE_INLINESTRUCT 504 505Gives the id an inline data structure. 506 507Inline structs store small files that can fit in the metadata pair. In this 508case, the file data is stored directly in the tag's data area. 509 510Layout of the inline-struct tag: 511 512``` 513 tag data 514[-- 32 --][--- variable length ---] 515[1|- 11 -| 10 | 10 ][--- (size * 8) ---] 516 ^ ^ ^ ^- size ^- inline data 517 | | '------ id 518 | '------------ type (0x201) 519 '----------------- valid bit 520``` 521 522Inline-struct fields: 523 5241. **Inline data** - File data stored directly in the metadata-pair. 525 526--- 527#### `0x202` LFS_TYPE_CTZSTRUCT 528 529Gives the id a CTZ skip-list data structure. 530 531CTZ skip-lists store files that can not fit in the metadata pair. These files 532are stored in a skip-list in reverse, with a pointer to the head of the 533skip-list. Note that the head of the skip-list and the file size is enough 534information to read the file. 535 536How exactly CTZ skip-lists work is a bit complicated. A full explanation can be 537found in the [DESIGN.md](DESIGN.md#ctz-skip-lists). 538 539A quick summary: For every _n_‍th block where _n_ is divisible by 5402‍_ˣ_, that block contains a pointer to block _n_-2‍_ˣ_. 541These pointers are stored in increasing order of _x_ in each block of the file 542before the actual data. 543 544``` 545 | 546 v 547.--------. .--------. .--------. .--------. .--------. .--------. 548| A |<-| D |<-| G |<-| J |<-| M |<-| P | 549| B |<-| E |--| H |<-| K |--| N | | Q | 550| C |<-| F |--| I |--| L |--| O | | | 551'--------' '--------' '--------' '--------' '--------' '--------' 552 block 0 block 1 block 2 block 3 block 4 block 5 553 1 skip 2 skips 1 skip 3 skips 1 skip 554``` 555 556Note that the maximum number of pointers in a block is bounded by the maximum 557file size divided by the block size. With 32 bits for file size, this results 558in a minimum block size of 104 bytes. 559 560Layout of the CTZ-struct tag: 561 562``` 563 tag data 564[-- 32 --][-- 32 --|-- 32 --] 565[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --] 566 ^ ^ ^ ^ ^ ^- file size 567 | | | | '-------------------- file head 568 | | | '- size (8) 569 | | '------ id 570 | '------------ type (0x202) 571 '----------------- valid bit 572``` 573 574CTZ-struct fields: 575 5761. **File head (32-bits)** - Pointer to the block that is the head of the 577 file's CTZ skip-list. 578 5792. **File size (32-bits)** - Size of the file in bytes. 580 581--- 582#### `0x3xx` LFS_TYPE_USERATTR 583 584Attaches a user attribute to an id. 585 586littlefs has a concept of "user attributes". These are small user-provided 587attributes that can be used to store things like timestamps, hashes, 588permissions, etc. 589 590Each user attribute is uniquely identified by an 8-bit type which is stored in 591the chunk field, and the user attribute itself can be found in the tag's data. 592 593There are currently no standard user attributes and a portable littlefs 594implementation should work with any user attributes missing. 595 596Layout of the user-attr tag: 597 598``` 599 tag data 600[-- 32 --][--- variable length ---] 601[1| 3| 8 | 10 | 10 ][--- (size * 8) ---] 602 ^ ^ ^ ^ ^- size ^- attr data 603 | | | '------ id 604 | | '----------- attr type 605 | '-------------- type1 (0x3) 606 '----------------- valid bit 607``` 608 609User-attr fields: 610 6111. **Attr type (8-bits)** - Type of the user attributes. 612 6132. **Attr data** - The data associated with the user attribute. 614 615--- 616#### `0x6xx` LFS_TYPE_TAIL 617 618Provides the tail pointer for the metadata pair itself. 619 620The metadata pair's tail pointer is used in littlefs for a linked-list 621containing all metadata pairs. The chunk field contains the type of the tail, 622which indicates if the following metadata pair is a part of the directory 623(hard-tail) or only used to traverse the filesystem (soft-tail). 624 625``` 626 .--------. 627 .| dir A |-. 628 ||softtail| | 629.--------| |-' 630| |'--------' 631| '---|--|-' 632| .-' '-------------. 633| v v 634| .--------. .--------. .--------. 635'->| dir B |->| dir B |->| dir C | 636 ||hardtail| ||softtail| || | 637 || | || | || | 638 |'--------' |'--------' |'--------' 639 '--------' '--------' '--------' 640``` 641 642Currently any type supersedes any other preceding tails in the metadata pair, 643but this may change if additional metadata pair state is added. 644 645A note about the metadata pair linked-list: Normally, this linked-list contains 646every metadata pair in the filesystem. However, there are some operations that 647can cause this linked-list to become out of sync if a power-loss were to occur. 648When this happens, littlefs sets the "sync" flag in the global state. How 649exactly this flag is stored is described below. 650 651When the sync flag is set: 652 6531. The linked-list may contain an orphaned directory that has been removed in 654 the filesystem. 6552. The linked-list may contain a metadata pair with a bad block that has been 656 replaced in the filesystem. 657 658If the sync flag is set, the threaded linked-list must be checked for these 659errors before it can be used reliably. Note that the threaded linked-list can 660be ignored if littlefs is mounted read-only. 661 662Layout of the tail tag: 663 664``` 665 tag data 666[-- 32 --][-- 32 --|-- 32 --] 667[1| 3| 8 | 10 | 10 ][--- 64 ---] 668 ^ ^ ^ ^ ^- size (8) ^- metadata pair 669 | | | '------ id 670 | | '---------- tail type 671 | '------------- type1 (0x6) 672 '---------------- valid bit 673``` 674 675Tail fields: 676 6771. **Tail type (8-bits)** - Type of the tail pointer. 678 6792. **Metadata pair (8-bytes)** - Pointer to the next metadata-pair. 680 681--- 682#### `0x600` LFS_TYPE_SOFTTAIL 683 684Provides a tail pointer that points to the next metadata pair in the 685filesystem. 686 687In this case, the next metadata pair is not a part of our current directory 688and should only be followed when traversing the entire filesystem. 689 690--- 691#### `0x601` LFS_TYPE_HARDTAIL 692 693Provides a tail pointer that points to the next metadata pair in the 694directory. 695 696In this case, the next metadata pair belongs to the current directory. Note 697that because directories in littlefs are sorted alphabetically, the next 698metadata pair should only contain filenames greater than any filename in the 699current pair. 700 701--- 702#### `0x7xx` LFS_TYPE_GSTATE 703 704Provides delta bits for global state entries. 705 706littlefs has a concept of "global state". This is a small set of state that 707can be updated by a commit to _any_ metadata pair in the filesystem. 708 709The way this works is that the global state is stored as a set of deltas 710distributed across the filesystem such that the global state can be found by 711the xor-sum of these deltas. 712 713``` 714 .--------. .--------. .--------. .--------. .--------. 715.| |->| gdelta |->| |->| gdelta |->| gdelta | 716|| | || 0x23 | || | || 0xff | || 0xce | 717|| | || | || | || | || | 718|'--------' |'--------' |'--------' |'--------' |'--------' 719'--------' '----|---' '--------' '----|---' '----|---' 720 v v v 721 0x00 --> xor ------------------> xor ------> xor --> gstate = 0x12 722``` 723 724Note that storing globals this way is very expensive in terms of storage usage, 725so any global state should be kept very small. 726 727The size and format of each piece of global state depends on the type, which 728is stored in the chunk field. Currently, the only global state is move state, 729which is outlined below. 730 731--- 732#### `0x7ff` LFS_TYPE_MOVESTATE 733 734Provides delta bits for the global move state. 735 736The move state in littlefs is used to store info about operations that could 737cause to filesystem to go out of sync if the power is lost. The operations 738where this could occur is moves of files between metadata pairs and any 739operation that changes metadata pairs on the threaded linked-list. 740 741In the case of moves, the move state contains a tag + metadata pair describing 742the source of the ongoing move. If this tag is non-zero, that means that power 743was lost during a move, and the file exists in two different locations. If this 744happens, the source of the move should be considered deleted, and the move 745should be completed (the source should be deleted) before any other write 746operations to the filesystem. 747 748In the case of operations to the threaded linked-list, a single "sync" bit is 749used to indicate that a modification is ongoing. If this sync flag is set, the 750threaded linked-list will need to be checked for errors before it can be used 751reliably. The exact cases to check for are described above in the tail tag. 752 753Layout of the move state: 754 755``` 756 tag data 757[-- 32 --][-- 32 --|-- 32 --|-- 32 --] 758[1|- 11 -| 10 | 10 ][1|- 11 -| 10 | 10 |--- 64 ---] 759 ^ ^ ^ ^ ^ ^ ^ ^- padding (0) ^- metadata pair 760 | | | | | | '------ move id 761 | | | | | '------------ move type 762 | | | | '----------------- sync bit 763 | | | | 764 | | | '- size (12) 765 | | '------ id (0x3ff) 766 | '------------ type (0x7ff) 767 '----------------- valid bit 768``` 769 770Move state fields: 771 7721. **Sync bit (1-bit)** - Indicates if the metadata pair threaded linked-list 773 is in-sync. If set, the threaded linked-list should be checked for errors. 774 7752. **Move type (11-bits)** - Type of move being performed. Must be either 776 `0x000`, indicating no move, or `0x4ff` indicating the source file should 777 be deleted. 778 7793. **Move id (10-bits)** - The file id being moved. 780 7814. **Metadata pair (8-bytes)** - Pointer to the metadata-pair containing 782 the move. 783 784--- 785#### `0x5xx` LFS_TYPE_CRC 786 787Last but not least, the CRC tag marks the end of a commit and provides a 788checksum for any commits to the metadata block. 789 790The first 32-bits of the data contain a CRC-32 with a polynomial of 791`0x04c11db7` initialized with `0xffffffff`. This CRC provides a checksum for 792all metadata since the previous CRC tag, including the CRC tag itself. For 793the first commit, this includes the revision count for the metadata block. 794 795However, the size of the data is not limited to 32-bits. The data field may 796larger to pad the commit to the next program-aligned boundary. 797 798In addition, the CRC tag's chunk field contains a set of flags which can 799change the behaviour of commits. Currently the only flag in use is the lowest 800bit, which determines the expected state of the valid bit for any following 801tags. This is used to guarantee that unwritten storage in a metadata block 802will be detected as invalid. 803 804Layout of the CRC tag: 805 806``` 807 tag data 808[-- 32 --][-- 32 --|--- variable length ---] 809[1| 3| 8 | 10 | 10 ][-- 32 --|--- (size * 8 - 32) ---] 810 ^ ^ ^ ^ ^ ^- crc ^- padding 811 | | | | '- size 812 | | | '------ id (0x3ff) 813 | | '----------- valid state 814 | '-------------- type1 (0x5) 815 '----------------- valid bit 816``` 817 818CRC fields: 819 8201. **Valid state (1-bit)** - Indicates the expected value of the valid bit for 821 any tags in the next commit. 822 8232. **CRC (32-bits)** - CRC-32 with a polynomial of `0x04c11db7` initialized 824 with `0xffffffff`. 825 8263. **Padding** - Padding to the next program-aligned boundary. No guarantees 827 are made about the contents. 828 829--- 830#### `0x5ff` LFS_TYPE_FCRC 831 832Added in lfs2.1, the optional FCRC tag contains a checksum of some amount of 833bytes in the next commit at the time it was erased. This allows us to ensure 834that we only ever program erased bytes, even if a previous commit failed due 835to power-loss. 836 837When programming a commit, the FCRC size must be at least as large as the 838program block size. However, the program block is not saved on disk, and can 839change between mounts, so the FCRC size on disk may be different than the 840current program block size. 841 842If the FCRC is missing or the checksum does not match, we must assume a 843commit was attempted but failed due to power-loss. 844 845Layout of the FCRC tag: 846 847``` 848 tag data 849[-- 32 --][-- 32 --|-- 32 --] 850[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --] 851 ^ ^ ^ ^ ^- fcrc size ^- fcrc 852 | | | '- size (8) 853 | | '------ id (0x3ff) 854 | '------------ type (0x5ff) 855 '----------------- valid bit 856``` 857 858FCRC fields: 859 8601. **FCRC size (32-bits)** - Number of bytes after this commit's CRC tag's 861 padding to include in the FCRC. 862 8632. **FCRC (32-bits)** - CRC of the bytes after this commit's CRC tag's padding 864 when erased. Like the CRC tag, this uses a CRC-32 with a polynomial of 865 `0x04c11db7` initialized with `0xffffffff`. 866 867--- 868
