## Техническая спецификация LittleFS
Это техническая спецификация файловой системы LittleFS с версией на диске lfs2.1. Этот документ описывает технические детали того, как LittleFS хранится на диске для интроспекции и инструментовки. Предполагается, что вы знакомы с дизайном LittleFS, для получения дополнительной информации о том, как работает LittleFS, ознакомьтесь с [DESIGN.md](DESIGN.md).
```
| | | .---._____
.-----. | |
--|o |---| littlefs |
--| |---| |
'-----' '----------'
| | |
```
## Некоторые быстрые заметки
- LittleFS — это блочная файловая система. Диск разделён на массив блоков одинакового размера, которые используются в качестве логической единицы хранения.
- Указатели блоков хранятся в 32 битах, специальное значение `0xffffffff` представляет нулевой адрес блока.
- Помимо логического размера блока (который обычно соответствует размеру стираемого блока), LittleFS также использует размер программного блока и размер читаемого блока. Они определяют выравнивание операций блочного устройства, но не обязательно должны быть согласованы для обеспечения переносимости.
- По умолчанию все значения в LittleFS хранятся в порядке байтов с прямым порядком.
## Пары каталогов / метаданных
Пары метаданных образуют основу LittleFS и обеспечивают систему распределённых атомарных обновлений. Даже суперблок хранится в паре метаданных.
Как следует из названия, пара метаданных хранится в двух блоках, один из которых обеспечивает резервную копию во время циклов стирания на случай потери питания. Эти два блока не обязательно последовательны и могут находиться где угодно на диске, поэтому «указатель» на пару метаданных хранится как два указателя блоков.
Кроме того, каждый блок метаданных ведёт себя как добавляемый журнал, содержащий переменное количество коммитов. Коммиты можно добавлять в журнал метаданных, чтобы обновлять метаданные без необходимости циклов стирания. Обратите внимание, что последующие коммиты могут заменять метаданные в предыдущих коммитах. Только самые последние метаданные следует считать действительными.
Высокоуровневая структура блока метаданных довольно проста:
```
.---------------------------------------.
.-| revision count | entries | \
| |-------------------+ | |
| | | |
| | | +-- 1st commit
| | | |
| | +-------------------| |
| | | CRC | /
| |-------------------+-------------------|
| | entries | \
| | | |
| | | +-- 2nd commit
| | +-------------------+--------------| |
| | | CRC | padding | /
| |----+-------------------+--------------|
| | entries | \
| | | |
| | | +-- 3rd commit
| | +-------------------+---------| |
| | | CRC | | /
| |---------+-------------------+ |
| | unwritten storage | more commits
| | | |
| | | v
| | |
| '---------------------------------------'
'---------------------------------------'
```
Каждый блок метаданных содержит 32-битный счётчик ревизий, за которым следует несколько коммитов. Каждый коммит содержит переменное число записей метаданных, за которыми следует 32-битная контрольная сумма циклическим избыточным кодом (CRC).
Также обратите внимание, что записи не обязательно выровнены по словам. Это позволяет нам хранить метаданные более компактно, однако мы можем писать только по адресам, выровненным по нашему размеру программного блока. Это означает, что каждый коммит может иметь заполнение для выравнивания.
Поля блока метаданных:
1. **Счётчик ревизий (32 бита)** — увеличивается при каждом цикле стирания. Если оба блока содержат действительные коммиты, следует использовать только блок с самым последним счётчиком ревизий. Для избежания проблем с целочисленным переполнением необходимо использовать сравнение последовательностей.
2. **Контрольная сумма циклическим избыточным кодом** — используется для проверки целостности данных. (32-бит)** — обнаруживает повреждение из-за потери питания или других проблем с записью. Использует CRC-32 с полиномом 0x04c11db7, инициализированный значением 0xffffffff.
Записи хранятся как 32-битный тег, за которым следует блок данных переменной длины. Но то, как именно эти теги хранятся, немного сложнее.
Блоки метаданных поддерживают как прямую, так и обратную итерацию. Чтобы сделать это без дублирования пространства для каждого тега, соседние записи имеют свои теги, которые XORed вместе, начиная с 0xffffffff.
```
Прямая итерация Обратная итерация
.-------------------. 0xffffffff .-------------------.
| revision count | | | revision count |
|-------------------| v |-------------------|
| tag ~A |---> xor -> tag A | tag ~A |---> xor -> 0xffffffff
|-------------------| | |-------------------| ^
| data A | | | data A | |
| | | | | |
| | | | | |
|-------------------| v |-------------------| |
| tag AxB |---> xor -> tag B | tag AxB |---> xor -> tag A
|-------------------| | |-------------------| ^
| data B | | | data B | |
| | | | | |
| | | | | |
|-------------------| v |-------------------| |
| tag BxC |---> xor -> tag C | tag BxC |---> xor -> tag B
|-------------------| |-------------------| ^
| data C | | data C | |
| | | | tag C
| | | |
| | | |
'-------------------' '-------------------'
```
Вот более полный пример блока метаданных, содержащего 4 записи:
```
.---------------------------------------.
.-| revision count | tag ~A | \
| |-------------------+-------------------| |
| | data A | |
| | | |
| |-------------------+-------------------| |
| | tag AxB | data B | <--. |
| |-------------------+ | | |
| | | | +-- 1st commit
| | +-------------------+---------| | |
| | | tag BxC | | <-.| |
| |---------+-------------------+ | || |
| | data C | || |
| | | || |
| |-------------------+-------------------| || |
| | tag CxCRC | CRC | || /
| |-------------------+-------------------| ||
| | tag CRCxA' | data A' | || \
| |-------------------+ | || |
| | | || |
| | +-------------------+----| || +-- 2nd commit
| | | tag CRCxA' | | || |
| |--------------+-------------------+----| || |
| | CRC | padding | || /
| |--------------+----+-------------------| ||
| | tag CRCxA'' | data A'' | <---. \
| |-------------------+ | ||| |
| | | ||| |
| | +-------------------+---------| ||| |
| | | tag A''xD | | < ||| |
| |---------+-------------------+ | |||| +-- 3rd commit
| | data D | |||| |
| | +---------| |||| |
| | | tag Dx| |||| |
| |---------+-------------------+---------| |||| |
| |CRC | В 3-битный абстрактный тип и 8-битное поле чанка. Обратите внимание, что значение `0x000` является недопустимым и не присваивается типу.
1. **Тип 1 (3 бита)** — абстрактный тип тега. Группирует теги в 8 категорий, которые облегчают поиск с использованием битовых масок.
2. **Чанк (8 бит)** — поле чанка используется для различных целей различными абстрактными типами. Тип 1 + чанк + идентификатор образуют уникальный идентификатор каждого тега в блоке метаданных.
3. **Идентификатор (10 бит)** — идентификатор файла, связанный с тегом. Каждый файл в блоке метаданных получает уникальный идентификатор, который используется для связывания тегов с этим файлом. Специальное значение `0x3ff` используется для любых тегов, которые не связаны с файлом, таких как каталог и глобальные метаданные.
4. **Длина (10 бит)** — длина данных в байтах. Специальное значение `0x3ff` указывает на то, что этот тег был удалён.
## Типы метаданных
Далее следует исчерпывающий список метаданных в littlefs.
---
#### `0x401` LFS_TYPE_CREATE
Создаёт новый файл с этим идентификатором. Обратите внимание, что файлы в блоке метаданных необязательно должны иметь тег создания. Всё, что делает создание, это перемещает любые файлы, использующие этот идентификатор. В этом смысле создание похоже на вставку в воображаемый массив файлов.
Теги создания и удаления позволяют littlefs хранить файлы в каталоге, упорядоченные по алфавиту по имени файла.
---
#### `0x4ff` LFS_TYPE_DELETE
Удаляет файл с этим идентификатором. Обратное созданию, этот тег перемещает любые соседние файлы этого идентификатора, подобно удалению из воображаемого массива файлов.
---
#### `0x0xx` LFS_TYPE_NAME
Связывает идентификатор с именем файла и типом файла.
Данные содержат имя файла, хранящееся в виде строки ASCII (в будущем может быть расширено до UTF8).
Поле чанка в этом теге указывает 8-битовый тип файла, который может быть одним из следующих.
В настоящее время тег имени должен предшествовать любым другим тегам, связанным с идентификатором, и не может быть переназначен без удаления файла.
Расположение тега имени:
```
tag data
[-- 32 --][--- variable length ---]
[1| 3| 8 | 10 | 10 ][--- (size * 8) ---]
^ ^ ^ ^ ^- size ^- file name
| | | '------ id
| | '----------- file type
| '-------------- type1 (0x0)
'----------------- valid bit
```
Поля имени:
* **тип файла (8 бит)** — тип файла;
* **имя файла** — имя файла хранится в виде строки ASCII.
---
#### `0x001` LFS_TYPE_REG
Инициализирует идентификатор + имя как обычный файл.
Способ хранения каждого файла зависит от его структурного тега, который описан ниже.
---
#### `0x002` LFS_TYPE_DIR
Инициализирует идентификатор + имя как каталог.
Каталоги в littlefs хранятся на диске в виде связанного списка пар метаданных, каждая пара содержит любое количество файлов в алфавитном порядке. Указатель на каталог хранится в структурном теге, который описан ниже.
---
#### `0x0ff` LFS_TYPE_SUPERBLOCK
Инициализирует идентификатор как запись суперблока.
Запись суперблока — это специальная запись, используемая для хранения конфигурации времени форматирования и идентификации файловой системы.
Название немного вводит в заблуждение. Хотя запись суперблока служит той же цели, что и суперблок, найденный в других файловых системах, в littlefs суперблок не получает выделенный блок. Вместо этого запись суперблока дублируется через связанный список пар метаданных, корни которых находятся на блоках 0 и 1. Последняя пара метаданных также служит корневым каталогом файловой системы.
```
.--------. .--------. .--------. .--------. .--------.
.| super |->| super |->| super |->| super |->| file B |
|| block | || block | || block | || block | || file C |
|| | || | || | || file A | || file D |
|'--------' |'--------' |'--------' |'--------' |'--------'
'--------' '--------' '--------' '--------' '--------'
\----------------+----------------/ \----------+----------/
superblock pairs root directory
```
Файловая система начинается только с корневого каталога. Пары метаданных суперблока растут каждый раз, когда корневая пара сжимается, чтобы экспоненциально продлить срок службы устройства. **LFS_TYPE_INLINESTRUCT**
Даёт идентификатор встроенной структуре данных.
Встроенные структуры хранят небольшие файлы, которые могут поместиться в пару метаданных. В этом случае данные файла хранятся непосредственно в области данных тега.
Расположение тега inline-struct:
```
tag data
[-- 32 --][--- variable length ---]
[1|- 11 -| 10 | 10 ][--- (size * 8) ---]
^ ^ ^ ^- размер ^- встроенные данные
| | | '------ идентификатор
| | '------------ тип (0x201)
| '----------------- бит валидности
'-------------------- действителен
```
Поля inline-структуры:
1. **Встроенные данные** — данные файла, хранящиеся непосредственно в паре метаданных.
---
**$0x202$ LFS_TYPE_CTZSTRUCT**
Даёт идентификатор структуре данных списка пропуска CTZ.
Списки пропуска CTZ хранят файлы, которые не помещаются в пару метаданных. Эти файлы хранятся в обратном порядке в списке пропуска, с указателем на начало списка пропуска. Обратите внимание, что начала списка пропуска и размера файла достаточно для чтения файла.
Как именно работают списки пропуска CTZ, немного сложнее. Подробное объяснение можно найти в DESIGN.md#ctz-skip-lists.
Краткое резюме: для каждого $n$-го блока, где $n$ делится на $2^\prime$, этот блок содержит указатель на блок $n-2^\prime$. Эти указатели хранятся в порядке возрастания $x$ в каждом блоке файла перед фактическими данными.
```
|
v
.--------. .--------. .--------. .--------. .--------. .--------.
| A |<-| D |<-| G |<-| J |<-| M |<-| P |
| B |<-| E |--| H |<-| K |--| N | | Q |
| C |<-| F |--| I |--| L |--| O | | |
'--------' '--------' '--------' '--------' '--------' '--------'
block 0 block 1 block 2 block 3 block 4 block 5
1 skip 2 skips 1 skip 3 skips 1 skip
```
Обратите внимание, что максимальное количество указателей в блоке ограничено максимальным размером файла, делённым на размер блока. При 32 битах для размера файла это приводит к минимальному размеру блока 104 байта.
Расположение CTZ-структуры тега:
```
tag data
[-- 32 --][-- 32 --|-- 32 --]
[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --]
^ ^ ^ ^ ^ ^- размер файла
| | | | '-------------------- голова файла
| | | '- размер (8)
| | '------ идентификатор
| '------------ тип (0x202)
'----------------- бит валидности
```
Полями CTZ-структуры являются:
1. **Голова файла (32-бит)** — указатель на блок, который является головой списка пропуска файла CTZ.
2. **Размер файла (32-бит)** — размер файла в байтах.
---
**$0x3xx$ LFS_TYPE_USERATTR**
Прикрепляет атрибут пользователя к идентификатору.
littlefs имеет концепцию «атрибутов пользователя». Это небольшие атрибуты, предоставляемые пользователем, которые можно использовать для хранения таких вещей, как временные метки, хэши, разрешения и т. д.
Каждый атрибут пользователя однозначно идентифицируется 8-битным типом, который хранится в поле chunk, а сам атрибут пользователя можно найти в данных тега.
Стандартных атрибутов пользователя в настоящее время нет, и портативная реализация littlefs должна работать с любыми отсутствующими атрибутами пользователя.
Расположение пользовательского тега attr:
```
tag data
[-- 32 --][--- variable length ---]
[1| 3| 8 | 10 | 10 ][--- (size * 8) ---]
^ ^ ^ ^ ^- размер ^- данные аттрибута
| | | '------ идентификатор
| | '----------- тип атрибута
| '-------------- тип1 (0x3)
'----------------- бит валидности
```
Атрибуты пользователя:
1. **Тип атрибута (8-бит)** — тип атрибутов пользователя.
2. **Данные атрибута** — данные, связанные с атрибутом пользователя.
---
**$0x6xx$ LFS_TYPE_TAIL**
Предоставляет хвостовой указатель для самой пары метаданных.
Хвостовой указатель пары метаданных используется в littlefs для связанного списка, содержащего все пары метаданных. Поле chunk содержит тип хвоста. **Который указывает, является ли следующая пара метаданных частью каталога (hard-tail) или используется только для обхода файловой системы (soft-tail).**
```
.--------.
.| dir A |-.
||softtail| |
.--------| |-'
| |'--------'
| '---|--|-'
| .-' '-------------.
| v v
| .--------. .--------. .--------.
'->| dir B |->| dir B |->| dir C |
||hardtail| ||softtail| || |
|| | || | || |
|'--------' |'--------' |'--------'
'--------' '--------' '--------'
```
В настоящее время любой тип превосходит любой другой предыдущий хвост в паре метаданных, но это может измениться, если будет добавлено дополнительное состояние пары метаданных.
**Примечание о связанном списке пар метаданных**: Обычно этот связанный список содержит каждую пару метаданных в файловой системе. Однако есть некоторые операции, которые могут привести к рассинхронизации этого связанного списка в случае потери питания. Когда это происходит, littlefs устанавливает флаг «sync» в глобальном состоянии. Как именно хранится этот флаг, описано ниже.
Когда установлен флаг синхронизации:
1. Связанный список может содержать осиротевший каталог, который был удалён в файловой системе.
2. Связанный список может содержать пару метаданных с повреждённым блоком, который был заменён в файловой системе.
Если установлен флаг синхронизации, связанный список с потоками должен быть проверен на наличие этих ошибок, прежде чем его можно будет надёжно использовать. Обратите внимание, что связанным списком с потоками можно пренебречь, если littlefs смонтирован только для чтения.
**Расположение тега хвоста:**
```
tag data
[-- 32 --][-- 32 --|-- 32 --]
[1| 3| 8 | 10 | 10 ][--- 64 ---]
^ ^ ^ ^ ^- размер (8) ^- пара метаданных
| | | '------ идентификатор
| | '---------- тип хвоста
| '------------- тип1 (0x6)
'---------------- действительный бит
```
**Поля хвоста:**
1. **Тип хвоста (8 бит)** — тип указателя хвоста.
2. **Пара метаданных (8 байт)** — указатель на следующую пару метаданных.
---
#### `0x600` LFS_TYPE_SOFTTAIL
Предоставляет указатель хвоста, который указывает на следующую пару метаданных в файловой системе. В этом случае следующая пара метаданных не является частью нашего текущего каталога и должна использоваться только при обходе всей файловой системы.
---
#### `0x601` LFS_TYPE_HARDTAIL
Предоставляет указатель хвоста, указывающий на следующую пару метаданных в каталоге. В этом случае следующая пара метаданных принадлежит текущему каталогу. Обратите внимание: поскольку каталоги в littlefs сортируются в алфавитном порядке, следующая пара метаданных должна содержать только имена файлов, превышающие любое имя файла в текущей паре.
---
#### `0x7xx` LFS_TYPE_GSTATE
Предоставляет биты дельты для записей глобального состояния.
littlefs имеет концепцию «глобального состояния». Это небольшой набор состояний, которые можно обновить путём фиксации в *любой* паре метаданных в файловой системе. Это работает так: глобальное состояние хранится как набор дельт, распределённых по файловой системе таким образом, чтобы глобальное состояние можно было найти по сумме XOR этих дельт.
```
.--------. .--------. .--------. .--------. .--------.
.| |->| gdelta |->| |->| gdelta |->| gdelta |
|| | || 0x23 | || | || 0xff | || 0xce |
|| | || | || | || | || |
|'--------' |'--------' |'--------' |'--------' |'--------'
'--------' '----|---' '--------' '----|---' '----|---'
v v v
0x00 --> xor ------------------> xor ------> xor --> gstate = 0x12
```
Обратите внимание, что хранение глобальных данных таким способом очень затратно с точки зрения использования памяти, поэтому любое глобальное состояние должно быть очень небольшим. Размер и формат каждого фрагмента глобального состояния зависит от типа, который хранится в поле фрагмента. В настоящее время единственным глобальным состоянием является состояние перемещения, которое описано ниже.
---
#### `0x7ff` LFS_TYPE_MOVESTATE
Предоставляет биты дельты для глобального состояния перемещения.
Состояние перемещения в littlefs используется для хранения информации об операциях, которые могли бы привести к рассогласованию файловой системы в случае потери питания. Операции, в которых это могло произойти... **occur is moves of files between metadata pairs and any operation that changes metadata pairs on the threaded linked-list.**
В случае перемещений состояние перемещения содержит тег + пару метаданных, описывающих источник текущего перемещения. Если этот тег не равен нулю, это означает, что во время перемещения произошло отключение питания и файл существует в двух разных местах. В этом случае источник перемещения следует считать удалённым, а перемещение должно быть завершено (источник должен быть удалён) перед любыми другими операциями записи в файловую систему.
В случае операций с многопоточным связанным списком используется один бит «sync», чтобы указать, что изменение выполняется. Если этот флаг синхронизации установлен, многопоточный связанный список необходимо проверить на наличие ошибок, прежде чем его можно будет надёжно использовать. Точные случаи для проверки описаны выше в хвостовом теге.
**Расположение состояния перемещения:**
```
tag data
[-- 32 --][-- 32 --|-- 32 --|-- 32 --]
[1|- 11 -| 10 | 10 ][1|- 11 -| 10 | 10 |--- 64 ---]
^ ^ ^ ^ ^ ^ ^ ^- заполнение (0) ^- пара метаданных
| | | | | | '------ идентификатор перемещения
| | | | | '------------ тип перемещения
| | | | '----------------- бит синхронизации
| | | |
| | | '- размер (12)
| | '------ id (0x3ff)
| '------------ type (0x7ff)
'----------------- действительный бит
```
Поля состояния перемещения:
1. **Бит синхронизации (1 бит)** — указывает, находится ли многопоточный связанный список в синхронизированном состоянии. Если установлено, многопоточный связанный список следует проверить на наличие ошибок.
2. **Тип перемещения (11 бит)** — тип выполняемого перемещения. Должен быть либо `0x000`, указывающий на отсутствие перемещения, либо `0x4ff`, указывающий, что исходный файл должен быть удалён.
3. **Идентификатор перемещения (10 бит)** — идентификатор файла, который перемещается.
4. **Пара метаданных (8 байт)** — указатель на пару метаданных, содержащую перемещение.
---
#### `0x5xx` LFS_TYPE_CRC
Наконец, тег CRC отмечает конец фиксации и предоставляет контрольную сумму для любых фиксаций в блоке метаданных.
Первые 32 бита данных содержат CRC-32 с полиномом `0x04c11db7`, инициализированным значением `0xffffffff`. Этот CRC обеспечивает контрольную сумму всех метаданных с момента предыдущего тега CRC, включая сам тег CRC. Для первой фиксации это включает количество ревизий для блока метаданных.
Однако размер данных не ограничен 32-битами. Поле данных может быть больше, чтобы зафиксировать фиксацию до следующей границы выравнивания программы.
Кроме того, поле фрагмента тега CRC содержит набор флагов, которые могут изменить поведение фиксаций. В настоящее время используется только младший бит, который определяет ожидаемое состояние действительного бита для любых следующих тегов. Это используется для гарантии того, что незаписанное хранилище в блоке метаданных будет обнаружено как недопустимое.
**Расположение тега CRC:**
```
tag data
[-- 32 --][-- 32 --|--- переменная длина ---]
[1| 3| 8 | 10 | 10 ][-- 32 --|--- (размер * 8 - 32) ---]
^ ^ ^ ^ ^ ^- crc ^- заполнение
| | | | '- размер
| | | '------ id (0x3ff)
| | '----------- действительное состояние
| '-------------- type1 (0x5)
'----------------- действительный бит
```
Поля CRC:
1. **Действительное состояние (1 бит)** — указывает ожидаемое значение действительного бита для любых тегов в следующей фиксации.
2. **CRC (32 бита)** — CRC-32 с полиномом `0x04c11db7`, инициализированный значением `0xffffffff`.
3. **Заполнение** — заполнение до следующей границы выравнивания по программе. Гарантии относительно содержимого не предоставляются.
---
#### `0x5ff` LFS_TYPE_FCRC
Добавленный в lfs2.1, необязательный тег FCRC содержит контрольную сумму некоторого количества байтов в следующей фиксации на момент её стирания. Это позволяет нам гарантировать, что мы программируем только стёртые байты, даже если предыдущая фиксация не удалась из-за потери питания.