littlefs storage utilization

[dorsadeh]

I'm using littlefs on a 128MB external NAND flash
the flash erase resolution is only in blocks sized 128KB
My application writes files ranging from 2KB - 60KB
I noticed littlefs writes every new file to a new flash block. in case of a 2KB file it is only 1.5625% utilization of block space!
Is this issue solvable?

[geky]

Hi @dorsadeh thanks for opening an issue.

So littlefs can store multiple files in a block but it has a caveat that these files, called "inlined files", need to fit in the device's RAM, controlled by the cache_size configuration. So if you set cache_size >= 2KB, you should no longer see one block per file.

This is a tradeoff necessary to allow multiple open files, since a sync of any file might need to rewrite that block, possibly invalidating other open-but-unsynced files.

[rabbitsaviola]

Hi @geky , it seems inline file size is limited by 0x3fe byte besides cache size. Even if cache size is increased to 32768, 2KB file would still use a new block. Is my understanding right?

static lfs_ssize_t lfs_file_flushedwrite(lfs_t *lfs, lfs_file_t *file,
        const void *buffer, lfs_size_t size) {
    const uint8_t *data = buffer;
    lfs_size_t nsize = size;

    if ((file->flags & LFS_F_INLINE) &&
            lfs_max(file->pos+nsize, file->ctz.size) >
            lfs_min(0x3fe, lfs_min(
                lfs->cfg->cache_size,
                (lfs->cfg->metadata_max ?
                    lfs->cfg->metadata_max : lfs->cfg->block_size) / 8))) {
        // inline file doesn't fit anymore
        int err = lfs_file_outline(lfs, file);
        if (err) {
            file->flags |= LFS_F_ERRED;
            return err;
        }
    }

[geky]

Ah, @rabbitsaviola, you are right, I had forgotten about the field limit. On disk inline files are stored with a 10-bit length field, with 0x3ff representing a deleted file, so there is a hard limit at ~1 KiB.

There are 2 extra reversed bits in the tag (it wasn't clear if these 2 bits would be more useful for ids (files per metadata block) or for the attribute length). This could raise the limit to 12-bits (~4KiB) at the cost of some complexity since these bits aren't contiguous in the tag.

[rabbitsaviola]

Hi @geky , thanks for your explanation. As it's limited by tag structure, it seems difficult to raise the limit to bigger value, such as 32KB? In my application there're many read-only files and most of them are smaller than 32KB. Sufficient RAM space could be provided as cache if it can help improve the disk utilization. Do you have any suggestion?

[geky]

Yes, this is a significant shortsight in littlefs. One of a number of issues (mostly performance) related to NAND. NAND support was an afterthought vs NOR and it shows in places like this.

It's still possible to improve this, for example using the extra bits to indicate an "extended tag" that is multiple words long. I'm looking into making significant changes to how metadata is stored so this should improve in the long-term, but that will take time since these are more involved changes.

---

A short-term option, which to be fair may be a "cheat", would be to use an FTL such as the Dhara FTL to convert NAND into more littlefs friendly block sizes. littlefs's wear leveling could be disabled in this case. In theory this would be a full-featured solution at a code/complexity cost, though I realize it's not ideal.

[rabbitsaviola]

Thanks for your suggestion, @geky. I do tried Dhara as FTL for fatfs before. But its performance is much worse than littlefs. Metadata cache might be needed to improve the performance. I'll try it with littlefs to double check it.

[kyrreaa]

I'm looking forward to progress on this as well. Not from actual storage utilization standpoint but more for efficiency and data recoverability.
I notice the structure put on disk aligning oddly and even with inline turned off it adds empty inline tags.
Here's some output from my own analyser (Is there one in littlefs, I could not find one?) where a new filesystem has a 64byte file created with inline turned off:

Examining block 64 with revcount = 00000002:
Offset 00040004: Superblock name: 'littlefs' Tag length=12
Offset 00040010: Inline struct. Ver:00020001 bsize:00040000 bcount:00001000 name_max:000000FF file_max:7FFFFFFF attr_max:000003FE Tag length=28
Offset 0004002C: CRC block with padding. Tag length=1026
Offset 0004042E: CRC block with padding. Tag length=1026
Offset 00040830: CRC block with padding. Tag length=1026
Offset 00040C32: CRC block with padding. Tag length=12
Offset 00040C3E: CRC block with padding. Tag length=962
Examining sector 65:
Offset 00041000: id=001 Creating file. Tag length=4
Offset 00041004: Regular file: id=001 name='test1.txt' Tag length=13
Offset 00041011: Inline data. id=001 length=000 (0) Tag length=4
Offset 00041015: CRC block with padding. Tag length=1026
Offset 00041417: CRC block with padding. Tag length=1026
Offset 00041819: CRC block with padding. Tag length=1026
Offset 00041C1B: CRC block with padding. Tag length=12
Offset 00041C27: CRC block with padding. Tag length=985
Examining sector 66:
Offset 00042000: CTZ struct: id=001 head=00000D05 (3333) size=00000040 (64) Tag length=12
Offset 0004200C: CRC block with padding. Tag length=1026
Offset 0004240E: CRC block with padding. Tag length=1026
Offset 00042810: CRC block with padding. Tag length=1026
Offset 00042C12: CRC block with padding. Tag length=12
Offset 00042C1E: CRC block with padding. Tag length=994
Edit: Updated printouts with the missing crc blocks and changed length listing to represent length including tag.

The 1022(+4) chunks stand out hehe.
I was expecting the chunks to align with 512 byte blocks though in case of smaller sector memory etc. It however does not...
After the CTZ block I was expecting a CRC padding out to 512 or 4096 (write size) somehow, but with 4 byte tag and 1022 length I get 1026 byte chunks at a time which seems odd.

[kyrreaa]

With inline enabled it seems to be no way to actually utilize the first inline tag written as it is written during creation of the file upon open, and no writes to the file has happened yet. It would be very useful to be able to write both the name and the first inline data bit in that first record as it would be able to contain the initial header of my files.

Examining block 64 with revcount = 00000002:
Offset 00040004: Superblock name: 'littlefs' Tag length=12
Offset 00040010: Inline struct. Ver:00020001 bsize:00040000 bcount:00001000 name_max:000000FF file_max:7FFFFFFF attr_max:000003FE Tag length=28
Offset 0004002C: CRC block with padding. Tag length=1026
Offset 0004042E: CRC block with padding. Tag length=1026
Offset 00040830: CRC block with padding. Tag length=1026
Offset 00040C32: CRC block with padding. Tag length=12
Offset 00040C3E: CRC block with padding. Tag length=962
Examining sector 65:
Offset 00041000: id=001 Creating file. Tag length=4
Offset 00041004: Regular file: id=001 name='test1.txt' Tag length=13
Offset 00041011: Inline data. id=001 length=000 (0) Tag length=4
Offset 00041015: CRC block with padding. Tag length=1026
Offset 00041417: CRC block with padding. Tag length=1026
Offset 00041819: CRC block with padding. Tag length=1026
Offset 00041C1B: CRC block with padding. Tag length=12
Offset 00041C27: CRC block with padding. Tag length=985
Examining sector 66:
Offset 00042000: Inline data. id=001 length=040 (64) Tag length=68
Offset 00042044: CRC block with padding. Tag length=1026
Offset 00042446: CRC block with padding. Tag length=1026
Offset 00042848: CRC block with padding. Tag length=1026
Offset 00042C4A: CRC block with padding. Tag length=12
Offset 00042C56: CRC block with padding. Tag length=938
Edit: Updated printouts with the missing crc blocks and changed length listing to represent length including tag.

[kyrreaa]

I'm using littlefs on a 128MB external NAND flash the flash erase resolution is only in blocks sized 128KB My application writes files ranging from 2KB - 60KB I noticed littlefs writes every new file to a new flash block. in case of a 2KB file it is only 1.5625% utilization of block space! Is this issue solvable?

There is also the config prog_size that is normally used for the sector size your flash can write, but as long as block_size is correctly defined erases will happen aligned correctly. I limited my metadata_max to reduce the time it takes for compaction (and to make it happen often) and ran a test on my nand flash with reduced prog_size after checking with my device datasheet.
My flash (mt29f8g) has 4096 byte "sectors" and 64*4096 byte eraseable block size, but it also mentions a maximum of 4 partial writes per "sector" allowed when using it's built in parity system. (Writing only the 4096 byte data area, and leaving it to automatically fill in the 256 byte metadata area.) I thus set up a test with cache_size and read_size equal to the sector size of 4096 and setting prog_size to read_size/4 for 1024 byte chunks. I first checked that my nand flash implementation would allow this and added code to check against any writes crossing the actual sector boundaries; splitting these into two or more operations. (Using larger cache would allow littlefs to write multiple sectors at once and I didn't want it to end up trying to write 2 sectors at once, offset by 1/4 sector...)
Running my file-creation and deletion test I could see a quite significant change in behaviour allowing littlefs to pack the initial metadata 4x tighter.

A quick examine of the filesystem after creating 5 files show how some of them are now packed better into each sector:
Examining sector 65:
Offset 00041000: id=002 Creating file. Tag length=4
Offset 00041004: Regular file: id=002 name='test_001.txt' Tag length=16
Offset 00041014: Inline data. id=002 length=000 (0) Tag length=4
Offset 00041018: CRC block with padding. Tag length=12
Offset 00041024: CRC block with padding. Tag length=988
Offset 00041400: Inline data. id=002 length=010 (16) Tag length=20
Offset 00041414: CRC block with padding. Tag length=12
Offset 00041420: CRC block with padding. Tag length=992
Offset 00041800: CTZ struct: id=002 head=00000A8C (2700) size=00000FA0 (4000) Tag length=12
Offset 0004180C: CRC block with padding. Tag length=12
Offset 00041818: CRC block with padding. Tag length=1000
Offset 00041C00: id=003 Creating file. Tag length=4
Offset 00041C04: Regular file: id=003 name='test_002.txt' Tag length=16
Offset 00041C14: Inline data. id=003 length=000 (0) Tag length=4
Offset 00041C18: CRC block with padding. Tag length=12
Offset 00041C24: CRC block with padding. Tag length=988
Examining sector 66:
Offset 00042000: Inline data. id=003 length=010 (16) Tag length=20
Offset 00042014: CRC block with padding. Tag length=12
Offset 00042020: CRC block with padding. Tag length=992
Offset 00042400: CTZ struct: id=003 head=00000A8D (2701) size=00000FA0 (4000) Tag length=12
Offset 0004240C: CRC block with padding. Tag length=12
Offset 00042418: CRC block with padding. Tag length=1000
Offset 00042800: id=004 Creating file. Tag length=4
Offset 00042804: Regular file: id=004 name='test_003.txt' Tag length=16
Offset 00042814: Inline data. id=004 length=000 (0) Tag length=4
Offset 00042818: CRC block with padding. Tag length=12
Offset 00042824: CRC block with padding. Tag length=988
Offset 00042C00: Inline data. id=004 length=010 (16) Tag length=20
Offset 00042C14: CRC block with padding. Tag length=12
Offset 00042C20: CRC block with padding. Tag length=992
(I still notice the extra empty inline data tag after opening every file though?
Is this due to the file being committed to storage to remember name and it's the only way to store file length of 0?)

Data integrity is still ok, but I do not know how much more wear this causes or other issues.
This should help OP as I think his nand may have similar capability although on 2048 byte sectors allowing 4x512 byte writes instead. For live file creation though I see the metadata_max does wonders to keep delays down so suggest creating few files in a directory is possible during time critical events.

[kyrreaa]

I forgot to say @dorsadeh that any file that does not fit inline will be allocated a full eraseable block sized chunk (block_size) in the CTZ structure for the file. The ability to write 4 smaller bits to a sector will not help with the current way littlefs allocates data space.

[geky]

Here's some output from my own analyser (Is there one in littlefs, I could not find one?)

There are a couple scripts used during development:

• https://github.com/littlefs-project/littlefs/blob/master/scripts/readtree.py
• https://github.com/littlefs-project/littlefs/blob/master/scripts/readmdir.py
• https://github.com/littlefs-project/littlefs/blob/master/scripts/readblock.py

$ ./scripts/readtree.py --help
$ ./scripts/readtree.py disk 4096

Though no promises they work all the time. It would be nice to make these stable and move to a typed language, but it's low-priority.

After the CTZ block I was expecting a CRC padding out to 512 or 4096 (write size) somehow, but with 4 byte tag and 1022 length I get 1026 byte chunks at a time which seems odd.

This also caused by the above mentioned tag encoding limit. CRC padding uses the same 10-bit field in the tag, so the largest amount of padding is 1022 bytes (1023 being reserved for for deleted tags).

littlefs then writes multiple CRC tags to fill out the necessary padding, which is a hack, but at least keeps littlefs functional.

With inline enabled it seems to be no way to actually utilize the first inline tag written as it is written during creation of the file upon open, and no writes to the file has happened yet. It would be very useful to be able to write both the name and the first inline data bit in that first record as it would be able to contain the initial header of my files.

I can address this in #942 (comment), thanks for creating an issue.

(I still notice the extra empty inline data tag after opening every file though?
Is this due to the file being committed to storage to remember name and it's the only way to store file length of 0?)

Yes, basically. In theory you could omit the empty inline tag, but since littlefs then writes ~1000 bytes of padding you wouldn't really be gaining anything

[geky]

I'm looking into making significant changes to how metadata is stored so this should improve in the long-term, but that will take time since these are more involved changes.

I just thought I'd add a quick update on this. I've been making progress on this in the background, and have a prototype working that should, in theory, be able to remove both the RAM requirement for inline files and tag encoding limitations.

Though it will be a bit longer before this is usable.