Lines Matching +full:- +full:i
10 | | | .---._____
11 .-----. | |
12 --|o |---| littlefs |
13 --| |---| |
14 '-----' '----------'
20 - littlefs is a block-based filesystem. The disk is divided into an array of
23 - Block pointers are stored in 32 bits, with the special value `0xffffffff`
26 - In addition to the logical block size (which usually matches the erase
31 - By default, all values in littlefs are stored in little-endian byte order.
49 The high-level layout of a metadata block is fairly simple:
52 .---------------------------------------.
53 .-| revision count | entries | \
54 | |-------------------+ | |
56 | | | +-- 1st commit
58 | | +-------------------| |
60 | |-------------------+-------------------|
63 | | | +-- 2nd commit
64 | | +-------------------+--------------| |
66 | |----+-------------------+--------------|
69 | | | +-- 3rd commit
70 | | +-------------------+---------| |
72 | |---------+-------------------+ |
78 | '---------------------------------------'
79 '---------------------------------------'
82 Each metadata block contains a 32-bit revision count followed by a number of
84 by a 32-bit CRC.
86 Note also that entries aren't necessarily word-aligned. This allows us to
93 1. **Revision count (32-bits)** - Incremented every erase cycle. If both blocks
98 2. **CRC (32-bits)** - Detects corruption from power-loss or other write
99 issues. Uses a CRC-32 with a polynomial of `0x04c11db7` initialized
102 Entries themselves are stored as a 32-bit tag followed by a variable length
112 .-------------------. 0xffffffff .-------------------.
114 |-------------------| v |-------------------|
115 | tag ~A |---> xor -> tag A | tag ~A |---> xor -> 0xffffffff
116 |-------------------| | |-------------------| ^
120 |-------------------| v |-------------------| |
121 | tag AxB |---> xor -> tag B | tag AxB |---> xor -> tag A
122 |-------------------| | |-------------------| ^
126 |-------------------| v |-------------------| |
127 | tag BxC |---> xor -> tag C | tag BxC |---> xor -> tag B
128 |-------------------| |-------------------| ^
133 '-------------------' '-------------------'
145 .---------------------------------------.
146 .-| revision count | tag ~A | \
147 | |-------------------+-------------------| |
150 | |-------------------+-------------------| |
151 | | tag AxB | data B | <--. |
152 | |-------------------+ | | |
153 | | | | +-- 1st commit
154 | | +-------------------+---------| | |
155 | | | tag BxC | | <-.| |
156 | |---------+-------------------+ | || |
159 | |-------------------+-------------------| || |
161 | |-------------------+-------------------| ||
163 | |-------------------+ | || |
165 | | +-------------------+----| || +-- 2nd commit
167 | |--------------+-------------------+----| || |
169 | |--------------+----+-------------------| ||
170 | | tag CRCxA'' | data A'' | <---. \
171 | |-------------------+ | ||| |
173 | | +-------------------+---------| ||| |
175 | |---------+-------------------+ | |||| +-- 3rd commit
177 | | +---------| |||| |
179 | |---------+-------------------+---------| |||| |
181 | |---------+-------------------+ | ||||
187 | '---------------------------------------' ||||
188 '---------------------------------------' |||'- most recent A
189 ||'-- most recent B
190 |'--- most recent C
191 '---- most recent D
196 So in littlefs, 32-bit tags describe every type of metadata. And this means
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)
217 **not** stored in little-endian. Tags stored in commits are actually stored
218 in big-endian (and is the only thing in littlefs stored in big-endian). This
220 first bit in a commit, and when converted to little-endian, the valid bit finds
222 but, because none of the fields are byte-aligned, this would be more
223 complicated than just storing the tag in big-endian.
230 1. **Valid bit (1-bit)** - Indicates if the tag is valid.
232 2. **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
236 3. **Type1 (3-bits)** - Abstract type of the tag. Groups the tags into
239 4. **Chunk (8-bits)** - Chunk field used for various purposes by the different
243 5. **Id (10-bits)** - File id associated with the tag. Each file in a metadata
248 6. **Length (10-bits)** - Length of the data in bytes. The special value
255 ---
266 ---
273 ---
281 The chunk field in this tag indicates an 8-bit file type which can be one of
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
302 1. **file type (8-bits)** - Type of the file.
304 2. **file name** - File name stored as an ASCII string.
306 ---
313 ---
318 Directories in littlefs are stored on disk as a linked-list of metadata pairs,
322 ---
327 The superblock entry is a special entry used to store format-time configuration
333 across a linked-list of metadata pairs rooted on the blocks 0 and 1. The last
337 .--------. .--------. .--------. .--------. .--------.
338 .| super |->| super |->| super |->| super |->| file B |
341 |'--------' |'--------' |'--------' |'--------' |'--------'
342 '--------' '--------' '--------' '--------' '--------'
344 \----------------+----------------/ \----------+----------/
353 superblock type and an inline-struct tag. The name tag contains the magic
354 string "littlefs", while the inline-struct tag contains version and
357 Layout of the superblock name tag and inline-struct tag:
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
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
383 1. **Magic string (8-bytes)** - Magic string indicating the presence of
386 2. **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.
392 3. **Block size (32-bits)** - Size of the logical block size used by the
395 4. **Block count (32-bits)** - Number of blocks in the filesystem.
397 5. **Name max (32-bits)** - Maximum size of file names in bytes.
399 6. **File max (32-bits)** - Maximum size of files in bytes.
401 7. **Attr max (32-bits)** - Maximum size of file attributes in bytes.
407 ---
410 Associates the id with an on-disk data structure.
416 example, appending a ctz-struct replaces an inline-struct on the same file.
418 ---
423 Directories in littlefs are stored on disk as a linked-list of metadata pairs,
429 .--------. .--------. .--------. .--------. .--------. .--------.
430 .| file A |->| file D |->| file G |->| file I |->| file J |->| file M |
433 |'--------' |'--------' |'--------' |'--------' |'--------' |'--------'
434 '--------' '--------' '--------' '--------' '--------' '--------'
437 The dir-struct tag contains only the pointer to the first metadata-pair in the
440 The pointer to the next metadata-pair in the directory is stored in a tail tag,
443 Layout of the dir-struct tag:
447 [-- 32 --][-- 32 --|-- 32 --]
448 [1|- 11 -| 10 | 10 ][--- 64 ---]
449 ^ ^ ^ ^- size (8) ^- metadata pair
450 | | '------ id
451 | '------------ type (0x200)
452 '----------------- valid bit
455 Dir-struct fields:
457 1. **Metadata pair (8-bytes)** - Pointer to the first metadata-pair
460 ---
468 Layout of the inline-struct tag:
472 [-- 32 --][--- variable length ---]
473 [1|- 11 -| 10 | 10 ][--- (size * 8) ---]
474 ^ ^ ^ ^- size ^- inline data
475 | | '------ id
476 | '------------ type (0x201)
477 '----------------- valid bit
480 Inline-struct fields:
482 1. **Inline data** - File data stored directly in the metadata-pair.
484 ---
487 Gives the id a CTZ skip-list data structure.
489 CTZ skip-lists store files that can not fit in the metadata pair. These files
490 are stored in a skip-list in reverse, with a pointer to the head of the
491 skip-list. Note that the head of the skip-list and the file size is enough
494 How exactly CTZ skip-lists work is a bit complicated. A full explanation can be
495 found in the [DESIGN.md](DESIGN.md#ctz-skip-lists).
498 2‍_ˣ_, that block contains a pointer to block _n_-2‍_ˣ_.
505 .--------. .--------. .--------. .--------. .--------. .--------.
506 | A |<-| D |<-| G |<-| J |<-| M |<-| P |
507 | B |<-| E |--| H |<-| K |--| N | | Q |
508 | C |<-| F |--| I |--| L |--| O | | |
509 '--------' '--------' '--------' '--------' '--------' '--------'
518 Layout of the CTZ-struct tag:
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
532 CTZ-struct fields:
534 1. **File head (32-bits)** - Pointer to the block that is the head of the
535 file's CTZ skip-list.
537 2. **File size (32-bits)** - Size of the file in bytes.
539 ---
544 littlefs has a concept of "user attributes". These are small user-provided
548 Each user attribute is uniquely identified by an 8-bit type which is stored in
554 Layout of the user-attr tag:
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
567 User-attr fields:
569 1. **Attr type (8-bits)** - Type of the user attributes.
571 2. **Attr data** - The data associated with the user attribute.
573 ---
578 The metadata pair's tail pointer is used in littlefs for a linked-list
581 (hard-tail) or only used to traverse the filesystem (soft-tail).
584 .--------.
585 .| dir A |-.
587 .--------| |-'
588 | |'--------'
589 | '---|--|-'
590 | .-' '-------------.
592 | .--------. .--------. .--------.
593 '->| dir B |->| dir B |->| dir C |
596 |'--------' |'--------' |'--------'
597 '--------' '--------' '--------'
603 A note about the metadata pair linked-list: Normally, this linked-list contains
605 can cause this linked-list to become out of sync if a power-loss were to occur.
611 1. The linked-list may contain an orphaned directory that has been removed in
613 2. The linked-list may contain a metadata pair with a bad block that has been
616 If the sync flag is set, the threaded linked-list must be checked for these
617 errors before it can be used reliably. Note that the threaded linked-list can
618 be ignored if littlefs is mounted read-only.
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
635 1. **Tail type (8-bits)** - Type of the tail pointer.
637 2. **Metadata pair (8-bytes)** - Pointer to the next metadata-pair.
639 ---
648 ---
659 ---
669 the xor-sum of these deltas.
672 .--------. .--------. .--------. .--------. .--------.
673 .| |->| gdelta |->| |->| gdelta |->| gdelta |
676 |'--------' |'--------' |'--------' |'--------' |'--------'
677 '--------' '----|---' '--------' '----|---' '----|---'
679 0x00 --> xor ------------------> xor ------> xor --> gstate = 0x12
689 ---
697 operation that changes metadata pairs on the threaded linked-list.
700 the source of the ongoing move. If this tag is non-zero, that means that power
706 In the case of operations to the threaded linked-list, a single "sync" bit is
708 threaded linked-list will need to be checked for errors before it can be used
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
722 | | | '- size (12)
723 | | '------ id (0x3ff)
724 | '------------ type (0x7ff)
725 '----------------- valid bit
730 1. **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.
733 2. **Move type (11-bits)** - Type of move being performed. Must be either
737 3. **Move id (10-bits)** - The file id being moved.
739 4. **Metadata pair (8-bytes)** - Pointer to the metadata-pair containing
742 ---
748 The first 32-bits of the data contain a CRC-32 with a polynomial of
753 However, the size of the data is not limited to 32-bits. The data field may
754 larger to pad the commit to the next program-aligned boundary.
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
778 1. **Valid state (1-bit)** - Indicates the expected value of the valid bit for
781 2. **CRC (32-bits)** - CRC-32 with a polynomial of `0x04c11db7` initialized
784 3. **Padding** - Padding to the next program-aligned boundary. No guarantees
787 ---