1## littlefs technical specification 2 3This is the technical specification of the little filesystem. This document 4covers the technical details of how the littlefs is stored on disk for 5introspection and tooling. This document assumes you are familiar with the 6design of the littlefs, for more info on how littlefs works check 7out [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 136One last thing to note before we get into the details around tag encoding. Each 137tag contains a valid bit used to indicate if the tag and containing commit is 138valid. This valid bit is the first bit found in the tag and the commit and can 139be used to tell if we've attempted to write to the remaining space in the 140block. 141 142Here's a more complete example of metadata block containing 4 entries: 143 144``` 145 .---------------------------------------. 146.-| revision count | tag ~A | \ 147| |-------------------+-------------------| | 148| | data A | | 149| | | | 150| |-------------------+-------------------| | 151| | tag AxB | data B | <--. | 152| |-------------------+ | | | 153| | | | +-- 1st commit 154| | +-------------------+---------| | | 155| | | tag BxC | | <-.| | 156| |---------+-------------------+ | || | 157| | data C | || | 158| | | || | 159| |-------------------+-------------------| || | 160| | tag CxCRC | CRC | || / 161| |-------------------+-------------------| || 162| | tag CRCxA' | data A' | || \ 163| |-------------------+ | || | 164| | | || | 165| | +-------------------+----| || +-- 2nd commit 166| | | tag CRCxA' | | || | 167| |--------------+-------------------+----| || | 168| | CRC | padding | || / 169| |--------------+----+-------------------| || 170| | tag CRCxA'' | data A'' | <---. \ 171| |-------------------+ | ||| | 172| | | ||| | 173| | +-------------------+---------| ||| | 174| | | tag A''xD | | < ||| | 175| |---------+-------------------+ | |||| +-- 3rd commit 176| | data D | |||| | 177| | +---------| |||| | 178| | | tag Dx| |||| | 179| |---------+-------------------+---------| |||| | 180| |CRC | CRC | | |||| / 181| |---------+-------------------+ | |||| 182| | unwritten storage | |||| more commits 183| | | |||| | 184| | | |||| v 185| | | |||| 186| | | |||| 187| '---------------------------------------' |||| 188'---------------------------------------' |||'- most recent A 189 ||'-- most recent B 190 |'--- most recent C 191 '---- most recent D 192``` 193 194## Metadata tags 195 196So in littlefs, 32-bit tags describe every type of metadata. And this means 197_every_ type of metadata, including file entries, directory fields, and 198global state. Even the CRCs used to mark the end of commits get their own tag. 199 200Because of this, the tag format contains some densely packed information. Note 201that there are multiple levels of types which break down into more info: 202 203``` 204[---- 32 ----] 205[1|-- 11 --|-- 10 --|-- 10 --] 206 ^. ^ . ^ ^- length 207 |. | . '------------ id 208 |. '-----.------------------ type (type3) 209 '.-----------.------------------ valid bit 210 [-3-|-- 8 --] 211 ^ ^- chunk 212 '------- type (type1) 213``` 214 215 216Before we go further, there's one important thing to note. These tags are 217**not** stored in little-endian. Tags stored in commits are actually stored 218in big-endian (and is the only thing in littlefs stored in big-endian). This 219little bit of craziness comes from the fact that the valid bit must be the 220first bit in a commit, and when converted to little-endian, the valid bit finds 221itself in byte 4. We could restructure the tag to store the valid bit lower, 222but, because none of the fields are byte-aligned, this would be more 223complicated than just storing the tag in big-endian. 224 225Another thing to note is that both the tags `0x00000000` and `0xffffffff` are 226invalid and can be used for null values. 227 228Metadata tag fields: 229 2301. **Valid bit (1-bit)** - Indicates if the tag is valid. 231 2322. **Type3 (11-bits)** - Type of the tag. This field is broken down further 233 into a 3-bit abstract type and an 8-bit chunk field. Note that the value 234 `0x000` is invalid and not assigned a type. 235 236 1. **Type1 (3-bits)** - Abstract type of the tag. Groups the tags into 237 8 categories that facilitate bitmasked lookups. 238 239 2. **Chunk (8-bits)** - Chunk field used for various purposes by the different 240 abstract types. type1+chunk+id form a unique identifier for each tag in the 241 metadata block. 242 2433. **Id (10-bits)** - File id associated with the tag. Each file in a metadata 244 block gets a unique id which is used to associate tags with that file. The 245 special value `0x3ff` is used for any tags that are not associated with a 246 file, such as directory and global metadata. 247 2484. **Length (10-bits)** - Length of the data in bytes. The special value 249 `0x3ff` indicates that this tag has been deleted. 250 251## Metadata types 252 253What follows is an exhaustive list of metadata in littlefs. 254 255--- 256#### `0x401` LFS_TYPE_CREATE 257 258Creates a new file with this id. Note that files in a metadata block 259don't necessarily need a create tag. All a create does is move over any 260files using this id. In this sense a create is similar to insertion into 261an imaginary array of files. 262 263The create and delete tags allow littlefs to keep files in a directory 264ordered alphabetically by filename. 265 266--- 267#### `0x4ff` LFS_TYPE_DELETE 268 269Deletes the file with this id. An inverse to create, this tag moves over 270any files neighboring this id similar to a deletion from an imaginary 271array of files. 272 273--- 274#### `0x0xx` LFS_TYPE_NAME 275 276Associates the id with a file name and file type. 277 278The data contains the file name stored as an ASCII string (may be expanded to 279UTF8 in the future). 280 281The chunk field in this tag indicates an 8-bit file type which can be one of 282the following. 283 284Currently, the name tag must precede any other tags associated with the id and 285can not be reassigned without deleting the file. 286 287Layout of the name tag: 288 289``` 290 tag data 291[-- 32 --][--- variable length ---] 292[1| 3| 8 | 10 | 10 ][--- (size * 8) ---] 293 ^ ^ ^ ^ ^- size ^- file name 294 | | | '------ id 295 | | '----------- file type 296 | '-------------- type1 (0x0) 297 '----------------- valid bit 298``` 299 300Name fields: 301 3021. **file type (8-bits)** - Type of the file. 303 3042. **file name** - File name stored as an ASCII string. 305 306--- 307#### `0x001` LFS_TYPE_REG 308 309Initializes the id + name as a regular file. 310 311How each file is stored depends on its struct tag, which is described below. 312 313--- 314#### `0x002` LFS_TYPE_DIR 315 316Initializes the id + name as a directory. 317 318Directories in littlefs are stored on disk as a linked-list of metadata pairs, 319each pair containing any number of files in alphabetical order. A pointer to 320the directory is stored in the struct tag, which is described below. 321 322--- 323#### `0x0ff` LFS_TYPE_SUPERBLOCK 324 325Initializes the id as a superblock entry. 326 327The superblock entry is a special entry used to store format-time configuration 328and identify the filesystem. 329 330The name is a bit of a misnomer. While the superblock entry serves the same 331purpose as a superblock found in other filesystems, in littlefs the superblock 332does not get a dedicated block. Instead, the superblock entry is duplicated 333across a linked-list of metadata pairs rooted on the blocks 0 and 1. The last 334metadata pair doubles as the root directory of the filesystem. 335 336``` 337 .--------. .--------. .--------. .--------. .--------. 338.| super |->| super |->| super |->| super |->| file B | 339|| block | || block | || block | || block | || file C | 340|| | || | || | || file A | || file D | 341|'--------' |'--------' |'--------' |'--------' |'--------' 342'--------' '--------' '--------' '--------' '--------' 343 344\----------------+----------------/ \----------+----------/ 345 superblock pairs root directory 346``` 347 348The filesystem starts with only the root directory. The superblock metadata 349pairs grow every time the root pair is compacted in order to prolong the 350life of the device exponentially. 351 352The contents of the superblock entry are stored in a name tag with the 353superblock type and an inline-struct tag. The name tag contains the magic 354string "littlefs", while the inline-struct tag contains version and 355configuration information. 356 357Layout of the superblock name tag and inline-struct tag: 358 359``` 360 tag data 361[-- 32 --][-- 32 --|-- 32 --] 362[1|- 11 -| 10 | 10 ][--- 64 ---] 363 ^ ^ ^ ^- size (8) ^- magic string ("littlefs") 364 | | '------ id (0) 365 | '------------ type (0x0ff) 366 '----------------- valid bit 367 368 tag data 369[-- 32 --][-- 32 --|-- 32 --|-- 32 --] 370[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --|-- 32 --] 371 ^ ^ ^ ^ ^- version ^- block size ^- block count 372 | | | | [-- 32 --|-- 32 --|-- 32 --] 373 | | | | [-- 32 --|-- 32 --|-- 32 --] 374 | | | | ^- name max ^- file max ^- attr max 375 | | | '- size (24) 376 | | '------ id (0) 377 | '------------ type (0x201) 378 '----------------- valid bit 379``` 380 381Superblock fields: 382 3831. **Magic string (8-bytes)** - Magic string indicating the presence of 384 littlefs on the device. Must be the string "littlefs". 385 3862. **Version (32-bits)** - The version of littlefs at format time. The version 387 is encoded in a 32-bit value with the upper 16-bits containing the major 388 version, and the lower 16-bits containing the minor version. 389 390 This specification describes version 2.0 (`0x00020000`). 391 3923. **Block size (32-bits)** - Size of the logical block size used by the 393 filesystem in bytes. 394 3954. **Block count (32-bits)** - Number of blocks in the filesystem. 396 3975. **Name max (32-bits)** - Maximum size of file names in bytes. 398 3996. **File max (32-bits)** - Maximum size of files in bytes. 400 4017. **Attr max (32-bits)** - Maximum size of file attributes in bytes. 402 403The superblock must always be the first entry (id 0) in a metadata pair as well 404as be the first entry written to the block. This means that the superblock 405entry can be read from a device using offsets alone. 406 407--- 408#### `0x2xx` LFS_TYPE_STRUCT 409 410Associates the id with an on-disk data structure. 411 412The exact layout of the data depends on the data structure type stored in the 413chunk field and can be one of the following. 414 415Any type of struct supersedes all other structs associated with the id. For 416example, appending a ctz-struct replaces an inline-struct on the same file. 417 418--- 419#### `0x200` LFS_TYPE_DIRSTRUCT 420 421Gives the id a directory data structure. 422 423Directories in littlefs are stored on disk as a linked-list of metadata pairs, 424each pair containing any number of files in alphabetical order. 425 426``` 427 | 428 v 429 .--------. .--------. .--------. .--------. .--------. .--------. 430.| file A |->| file D |->| file G |->| file I |->| file J |->| file M | 431|| file B | || file E | || file H | || | || file K | || file N | 432|| file C | || file F | || | || | || file L | || | 433|'--------' |'--------' |'--------' |'--------' |'--------' |'--------' 434'--------' '--------' '--------' '--------' '--------' '--------' 435``` 436 437The dir-struct tag contains only the pointer to the first metadata-pair in the 438directory. The directory size is not known without traversing the directory. 439 440The pointer to the next metadata-pair in the directory is stored in a tail tag, 441which is described below. 442 443Layout of the dir-struct tag: 444 445``` 446 tag data 447[-- 32 --][-- 32 --|-- 32 --] 448[1|- 11 -| 10 | 10 ][--- 64 ---] 449 ^ ^ ^ ^- size (8) ^- metadata pair 450 | | '------ id 451 | '------------ type (0x200) 452 '----------------- valid bit 453``` 454 455Dir-struct fields: 456 4571. **Metadata pair (8-bytes)** - Pointer to the first metadata-pair 458 in the directory. 459 460--- 461#### `0x201` LFS_TYPE_INLINESTRUCT 462 463Gives the id an inline data structure. 464 465Inline structs store small files that can fit in the metadata pair. In this 466case, the file data is stored directly in the tag's data area. 467 468Layout of the inline-struct tag: 469 470``` 471 tag data 472[-- 32 --][--- variable length ---] 473[1|- 11 -| 10 | 10 ][--- (size * 8) ---] 474 ^ ^ ^ ^- size ^- inline data 475 | | '------ id 476 | '------------ type (0x201) 477 '----------------- valid bit 478``` 479 480Inline-struct fields: 481 4821. **Inline data** - File data stored directly in the metadata-pair. 483 484--- 485#### `0x202` LFS_TYPE_CTZSTRUCT 486 487Gives the id a CTZ skip-list data structure. 488 489CTZ skip-lists store files that can not fit in the metadata pair. These files 490are stored in a skip-list in reverse, with a pointer to the head of the 491skip-list. Note that the head of the skip-list and the file size is enough 492information to read the file. 493 494How exactly CTZ skip-lists work is a bit complicated. A full explanation can be 495found in the [DESIGN.md](DESIGN.md#ctz-skip-lists). 496 497A quick summary: For every _n_‍th block where _n_ is divisible by 4982‍_ˣ_, that block contains a pointer to block _n_-2‍_ˣ_. 499These pointers are stored in increasing order of _x_ in each block of the file 500before the actual data. 501 502``` 503 | 504 v 505.--------. .--------. .--------. .--------. .--------. .--------. 506| A |<-| D |<-| G |<-| J |<-| M |<-| P | 507| B |<-| E |--| H |<-| K |--| N | | Q | 508| C |<-| F |--| I |--| L |--| O | | | 509'--------' '--------' '--------' '--------' '--------' '--------' 510 block 0 block 1 block 2 block 3 block 4 block 5 511 1 skip 2 skips 1 skip 3 skips 1 skip 512``` 513 514Note that the maximum number of pointers in a block is bounded by the maximum 515file size divided by the block size. With 32 bits for file size, this results 516in a minimum block size of 104 bytes. 517 518Layout of the CTZ-struct tag: 519 520``` 521 tag data 522[-- 32 --][-- 32 --|-- 32 --] 523[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --] 524 ^ ^ ^ ^ ^ ^- file size 525 | | | | '-------------------- file head 526 | | | '- size (8) 527 | | '------ id 528 | '------------ type (0x202) 529 '----------------- valid bit 530``` 531 532CTZ-struct fields: 533 5341. **File head (32-bits)** - Pointer to the block that is the head of the 535 file's CTZ skip-list. 536 5372. **File size (32-bits)** - Size of the file in bytes. 538 539--- 540#### `0x3xx` LFS_TYPE_USERATTR 541 542Attaches a user attribute to an id. 543 544littlefs has a concept of "user attributes". These are small user-provided 545attributes that can be used to store things like timestamps, hashes, 546permissions, etc. 547 548Each user attribute is uniquely identified by an 8-bit type which is stored in 549the chunk field, and the user attribute itself can be found in the tag's data. 550 551There are currently no standard user attributes and a portable littlefs 552implementation should work with any user attributes missing. 553 554Layout of the user-attr tag: 555 556``` 557 tag data 558[-- 32 --][--- variable length ---] 559[1| 3| 8 | 10 | 10 ][--- (size * 8) ---] 560 ^ ^ ^ ^ ^- size ^- attr data 561 | | | '------ id 562 | | '----------- attr type 563 | '-------------- type1 (0x3) 564 '----------------- valid bit 565``` 566 567User-attr fields: 568 5691. **Attr type (8-bits)** - Type of the user attributes. 570 5712. **Attr data** - The data associated with the user attribute. 572 573--- 574#### `0x6xx` LFS_TYPE_TAIL 575 576Provides the tail pointer for the metadata pair itself. 577 578The metadata pair's tail pointer is used in littlefs for a linked-list 579containing all metadata pairs. The chunk field contains the type of the tail, 580which indicates if the following metadata pair is a part of the directory 581(hard-tail) or only used to traverse the filesystem (soft-tail). 582 583``` 584 .--------. 585 .| dir A |-. 586 ||softtail| | 587.--------| |-' 588| |'--------' 589| '---|--|-' 590| .-' '-------------. 591| v v 592| .--------. .--------. .--------. 593'->| dir B |->| dir B |->| dir C | 594 ||hardtail| ||softtail| || | 595 || | || | || | 596 |'--------' |'--------' |'--------' 597 '--------' '--------' '--------' 598``` 599 600Currently any type supersedes any other preceding tails in the metadata pair, 601but this may change if additional metadata pair state is added. 602 603A note about the metadata pair linked-list: Normally, this linked-list contains 604every metadata pair in the filesystem. However, there are some operations that 605can cause this linked-list to become out of sync if a power-loss were to occur. 606When this happens, littlefs sets the "sync" flag in the global state. How 607exactly this flag is stored is described below. 608 609When the sync flag is set: 610 6111. The linked-list may contain an orphaned directory that has been removed in 612 the filesystem. 6132. The linked-list may contain a metadata pair with a bad block that has been 614 replaced in the filesystem. 615 616If the sync flag is set, the threaded linked-list must be checked for these 617errors before it can be used reliably. Note that the threaded linked-list can 618be ignored if littlefs is mounted read-only. 619 620Layout of the tail tag: 621 622``` 623 tag data 624[-- 32 --][-- 32 --|-- 32 --] 625[1| 3| 8 | 10 | 10 ][--- 64 ---] 626 ^ ^ ^ ^ ^- size (8) ^- metadata pair 627 | | | '------ id 628 | | '---------- tail type 629 | '------------- type1 (0x6) 630 '---------------- valid bit 631``` 632 633Tail fields: 634 6351. **Tail type (8-bits)** - Type of the tail pointer. 636 6372. **Metadata pair (8-bytes)** - Pointer to the next metadata-pair. 638 639--- 640#### `0x600` LFS_TYPE_SOFTTAIL 641 642Provides a tail pointer that points to the next metadata pair in the 643filesystem. 644 645In this case, the next metadata pair is not a part of our current directory 646and should only be followed when traversing the entire filesystem. 647 648--- 649#### `0x601` LFS_TYPE_HARDTAIL 650 651Provides a tail pointer that points to the next metadata pair in the 652directory. 653 654In this case, the next metadata pair belongs to the current directory. Note 655that because directories in littlefs are sorted alphabetically, the next 656metadata pair should only contain filenames greater than any filename in the 657current pair. 658 659--- 660#### `0x7xx` LFS_TYPE_GSTATE 661 662Provides delta bits for global state entries. 663 664littlefs has a concept of "global state". This is a small set of state that 665can be updated by a commit to _any_ metadata pair in the filesystem. 666 667The way this works is that the global state is stored as a set of deltas 668distributed across the filesystem such that the global state can be found by 669the xor-sum of these deltas. 670 671``` 672 .--------. .--------. .--------. .--------. .--------. 673.| |->| gdelta |->| |->| gdelta |->| gdelta | 674|| | || 0x23 | || | || 0xff | || 0xce | 675|| | || | || | || | || | 676|'--------' |'--------' |'--------' |'--------' |'--------' 677'--------' '----|---' '--------' '----|---' '----|---' 678 v v v 679 0x00 --> xor ------------------> xor ------> xor --> gstate = 0x12 680``` 681 682Note that storing globals this way is very expensive in terms of storage usage, 683so any global state should be kept very small. 684 685The size and format of each piece of global state depends on the type, which 686is stored in the chunk field. Currently, the only global state is move state, 687which is outlined below. 688 689--- 690#### `0x7ff` LFS_TYPE_MOVESTATE 691 692Provides delta bits for the global move state. 693 694The move state in littlefs is used to store info about operations that could 695cause to filesystem to go out of sync if the power is lost. The operations 696where this could occur is moves of files between metadata pairs and any 697operation that changes metadata pairs on the threaded linked-list. 698 699In the case of moves, the move state contains a tag + metadata pair describing 700the source of the ongoing move. If this tag is non-zero, that means that power 701was lost during a move, and the file exists in two different locations. If this 702happens, the source of the move should be considered deleted, and the move 703should be completed (the source should be deleted) before any other write 704operations to the filesystem. 705 706In the case of operations to the threaded linked-list, a single "sync" bit is 707used to indicate that a modification is ongoing. If this sync flag is set, the 708threaded linked-list will need to be checked for errors before it can be used 709reliably. The exact cases to check for are described above in the tail tag. 710 711Layout of the move state: 712 713``` 714 tag data 715[-- 32 --][-- 32 --|-- 32 --|-- 32 --] 716[1|- 11 -| 10 | 10 ][1|- 11 -| 10 | 10 |--- 64 ---] 717 ^ ^ ^ ^ ^ ^ ^ ^- padding (0) ^- metadata pair 718 | | | | | | '------ move id 719 | | | | | '------------ move type 720 | | | | '----------------- sync bit 721 | | | | 722 | | | '- size (12) 723 | | '------ id (0x3ff) 724 | '------------ type (0x7ff) 725 '----------------- valid bit 726``` 727 728Move state fields: 729 7301. **Sync bit (1-bit)** - Indicates if the metadata pair threaded linked-list 731 is in-sync. If set, the threaded linked-list should be checked for errors. 732 7332. **Move type (11-bits)** - Type of move being performed. Must be either 734 `0x000`, indicating no move, or `0x4ff` indicating the source file should 735 be deleted. 736 7373. **Move id (10-bits)** - The file id being moved. 738 7394. **Metadata pair (8-bytes)** - Pointer to the metadata-pair containing 740 the move. 741 742--- 743#### `0x5xx` LFS_TYPE_CRC 744 745Last but not least, the CRC tag marks the end of a commit and provides a 746checksum for any commits to the metadata block. 747 748The first 32-bits of the data contain a CRC-32 with a polynomial of 749`0x04c11db7` initialized with `0xffffffff`. This CRC provides a checksum for 750all metadata since the previous CRC tag, including the CRC tag itself. For 751the first commit, this includes the revision count for the metadata block. 752 753However, the size of the data is not limited to 32-bits. The data field may 754larger to pad the commit to the next program-aligned boundary. 755 756In addition, the CRC tag's chunk field contains a set of flags which can 757change the behaviour of commits. Currently the only flag in use is the lowest 758bit, which determines the expected state of the valid bit for any following 759tags. This is used to guarantee that unwritten storage in a metadata block 760will be detected as invalid. 761 762Layout of the CRC tag: 763 764``` 765 tag data 766[-- 32 --][-- 32 --|--- variable length ---] 767[1| 3| 8 | 10 | 10 ][-- 32 --|--- (size * 8 - 32) ---] 768 ^ ^ ^ ^ ^ ^- crc ^- padding 769 | | | | '- size 770 | | | '------ id (0x3ff) 771 | | '----------- valid state 772 | '-------------- type1 (0x5) 773 '----------------- valid bit 774``` 775 776CRC fields: 777 7781. **Valid state (1-bit)** - Indicates the expected value of the valid bit for 779 any tags in the next commit. 780 7812. **CRC (32-bits)** - CRC-32 with a polynomial of `0x04c11db7` initialized 782 with `0xffffffff`. 783 7843. **Padding** - Padding to the next program-aligned boundary. No guarantees 785 are made about the contents. 786 787--- 788
