v2: How does LittleFS calculate the physical address of a block?

[insiberias]

Hello LittleFS team,

We are studying this file system for a project and when I was reading the DESIGN.md file I was left with a question.

In the chapter about CTZ skip-lists, you say it is only needed to store a pointer to the head of the list, and size.

My question is, in the configuration structure, we do not specify any page size, and blocks are made of pages. I confess I am learning about reading and programming flash memory as I learn about LittleFS, but the program granularity in, for example, NAND flash memory is page and not block, so how does LittleFS handle the offset in this situation, since page sizes can vary? In NOR flash memory I think the program granularity is word and since LittleFS uses 32 bit words that makes things easy, but I am curious for NAND flash also.

Also, some memories to get the address of a block also need information of the plane the block is in, if you can comment on this it would help my curiosity a bit, or even point us toward the functions that handle this internally would also be helpful. 😃

Regardless, thank you. 😅

[BenBE]

I think this question somehow boils down to how storage space is organized when going from the logical place that LittleFS thinks data is to how it is physically organized. And the answer here is kinda mundane: LittleFS doesn't really care.

Let's explain with a somewhat different perspective, that might illuminate this a bit better. When you want to store data on a floppy or a hard drive, you have two ways do address a certain location: Either you can go by cylinder (or track), head and sector or you can assign each sector some contiguous number called an LBA (large block address). While the LBA still can be broken down into a physical location given the CHS address of that sector on the actual medium, it's usually used as an abstraction to not care about this physical detail. In particular because this abstraction allows things like remapping bad sectors or removing the physical storage media from the equation entirely.

The same abstraction is done for LittleFS too. When you create a volume containing a LittleFS filesystem, all that is needed to handle the data are information about the overall size of that volume (which does not necessarily need to take up all of the flash) and some constraints inherent with the underlying media: The program and erase block sizes. This is necessary as LittleFS needs to know, how much data needs to be moved to another place, whenever it attempts to remove data from a given location (i.e. to free a sector previously used for other data). While this size can be taken as 512 or 4096 bytes on modern hard drives, the situation is a bit more nuanced with typical flash memory ICs. But the principle behind it stays the same: If any byte on the storage needs to be modified, a certain number of adjacent bytes also needs to change, and thus the filesystem needs to know, how much data it needs to preserver somewhere else. These sizes usually differ between programming (writing zero bits to the flash) and erasing (restoring the flash to all one bits). Some chips even differ in behaviour when a given sector of the chip has previously been programmed, but this can be dealt with from the filesystem side, if you know which data a low-level operation on the storage media is going to affect.

I hope this clarifies some ideas in how LittleFS (and actually many other filesystems too) think of their underlying media; or if not, at least provided a few hints for further questions to elaborate on.

[geky]

Hi @insiberias, it's a good question.

And the answer here is kinda mundane: LittleFS doesn't really care.

This is more-or-less the gist.

To go into more of the low-level details:

LittleFS is a bit unique as a NAND flash filesystem in that it doesn't really have a concept of pages. LittleFS organizes storage into blocks, but the data in each block is viewed as a stream of bytes. When LittleFS talks to the block device, it uses block number + byte offset and expects the block device to map this to the correct block+page+plane+etc.

To support different read/prog granularity, we have cfg.read_size and cfg.prog_size, which let you set the minimum read/prog size+alignment. On NAND you would set these to at least the page size, on NOR they can usually be set to 1 byte. But the alignment is resolved at a pretty low-level in the stack, LittleFS is mostly designed around bytes. It's interesting to note read/prog size isn't even written to disk and can change between mounts, though in practice that's probably rare.

---

The reason for this is LittleFS's history originally targeting NOR flash, which usually (but not always) reads/progs at the byte level. But it has the advantage that it makes LittleFS quite flexible and able to support many different types of storage: NOR flash, NAND flash, but also NVRAM, SDs, etc.

The main downside is that blocks on NAND flash can be BIG (>=~128KiB), and this creates a lot of performance problems. Metadata compaction running in $O(n^2)$, for example, becomes unreasonable for most use cases.

LittleFS3 is attempting to improve things in the same blocks+bytes model (#1111, unstable), but it's a work in progress and the new DESIGN.md is still a TODO item.

---

Also, some memories to get the address of a block also need information of the plane the block is in

Planes are a funny one where designing around them can improve performance (I think reading/progging separate planes can be done in parallel?), but for LittleFS we just don't care. That sort of performance improvement would require a more complicated filesystem, maybe a future LittleFS.

Usually which plane a block is on just ends up encoded in the block number.

[bmcdonnell-fb]

Aside:

LittleFS [is] quite flexible and able to support many different types of storage: NOR flash, NAND flash, but also NVRAM, SDs, etc.

Has this bit made it into the documentation yet?

Bump #992.

[insiberias]

Thank you @BenBE and @geky both for the quick and very insightful replies.

This is important information for our case study in particular, since we are looking to see how compatible LittleFS can be with different types of memory, and for that I needed to understand what LittleFS expects of the memory device and how it dealt with addressing blocks and offsets in the blocks. Thanks again for the clarification. :)