[NEWS] Introducing MFS

This forum is dedicated to feedback, discussions about ongoing or future developments, ideas and suggestions regarding the ChibiOS projects are welcome. This forum is NOT for support.
steved
Posts: 823
Joined: Fri Nov 09, 2012 2:22 pm
Has thanked: 12 times
Been thanked: 135 times

Re: [NEWS] Introducing MFS

Postby steved » Mon Nov 20, 2017 2:55 pm

Some filesystems allocate space in large blocks, then sub-allocate within the block. The code for those may give some inspiration - what's used on PCs with SSDs, for instance? FatFS supports NTFS, which I think is that type of filesystem. (The problem may also be similar on randomly updateable CD-RW).
I can see a danger of ending up with, effectively, a file system on top of a file system.
Using YAFFS may be an alternative, albeit one with a GPL+commercial licence rather than a more liberal one

Tabulous
Posts: 509
Joined: Fri May 03, 2013 12:02 pm
Has thanked: 7 times
Been thanked: 17 times

Re: [NEWS] Introducing MFS

Postby Tabulous » Mon Nov 20, 2017 5:55 pm

Giovanni wrote:Question!

How valuable would it be to be able to use FatFS (or others) on top of a MFS partition? a thin block-device emulation layer would be needed between the twos. It would enable creating a full FS on top of any flash, even internal ones (performance would not be necessarily great).

This emulation layer could also include a RAM buffers cache at 512 bytes block level for cached access and, optionally, delayed writes.

The interesting thing is that even a FAT-based file system would have ensured wear leveling by the underlying MFS.

Giovanni


This would be very good, its what i did earlier this year. FatFS on top of SPI flash.

User avatar
Giovanni
Site Admin
Posts: 14444
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 1074 times
Been thanked: 921 times
Contact:

Re: [NEWS] Introducing MFS

Postby Giovanni » Mon Nov 20, 2017 6:56 pm

Tabulous wrote:
Giovanni wrote:Question!

How valuable would it be to be able to use FatFS (or others) on top of a MFS partition? a thin block-device emulation layer would be needed between the twos. It would enable creating a full FS on top of any flash, even internal ones (performance would not be necessarily great).

This emulation layer could also include a RAM buffers cache at 512 bytes block level for cached access and, optionally, delayed writes.

The interesting thing is that even a FAT-based file system would have ensured wear leveling by the underlying MFS.

Giovanni


This would be very good, its what i did earlier this year. FatFS on top of SPI flash.


Which strategy did you use? there are several and right now I cannot decide.

Giovanni

steved
Posts: 823
Joined: Fri Nov 09, 2012 2:22 pm
Has thanked: 12 times
Been thanked: 135 times

Re: [NEWS] Introducing MFS

Postby steved » Tue Nov 21, 2017 2:58 pm

I've been spending more time than I should thinking about this, and come up with my own set of random thoughts, mostly based on solution 3:

I'm assuming 512-byte data chunks, for compatibility with FatFS, although the principles can be applied to chunks of any size.

The flash I'm intending to use (Microchip SST26VF064) supports page writes of any size, and with any start address; its only the erase which operates on large (4K, typically) blocks.
And I'm sure other devices are much the same.
So an algorithm which appends data within blocks could be quite efficient, as well as being economical with RAM.

At the lowest level, work with the device's minimum page erase size as a basic block. Divide it into 514-byte buckets, where the first two bytes are a bucket number, and the rest is a chunk of data.
[Could use 516-byte buckets, with a 16-bit CRC on the data]
For an empty bucket, the bucket number is 0xffff.
For a used bucket, the bucket number is some other non-zero value which uniquely identifies the bucket within the block.
For a 'cast off' bucket, the pointer is zero.
When allocating buckets within a block, allow a percentage of free space to allow for writes (system configuration constant?)

At a higher level, assign some blocks to be a "directory"; these will follow the structure just described, although probably with a much smaller data size. These entries identify the
location of each block within the memory. Again, allow a percentage of free space (separately configurable from the previous value?) within the overall device.

Within each block, similar processes apply for both directory and data:

To read:
1. Calculate the initial bucket address as an offset within the block.
2. If the first two bytes of the bucket are 0xffff, return "uninitialised data"
3. If the first two bytes of the bucket match the expected bucket number, return the following data
4. Step through the "reallocation space" looking for the required bucket number; return data

To write:
1. Calculate the initial bucket address as an offset within the block.
2. If the first two bytes of the bucket are 0xffff, write the data and return
3. Find the bucket currently assigned; update the bucket address
3a. Possibly check to see if the write data has actually changed; if not, return
4. Find an unused bucket in the "reallocation space" of the current block
5. If reallocation space available (in current block)
Write new data into bucket
Write zero into the first two bytes of the previously assigned bucket
return
6. Find an unused block
7. Copy data from the currently assigned block, garbage collecting on the way, and merging new data
8. Update the directory entry to point to the new block
9. Erase the previously assigned block


At the highest level, the required location is determined initially from the directory block.

A 4K block size is going to hold 7.9 buckets total, so lots wasted space. Probably better to work with larger blocks (32K?) to give realistic numbers.

The directory of blocks is going to need around 4K entries for a 8Mbyte flash memory - a trivial overhead

This approach mostly does garbage collection on the fly, with a maximum of two page erases and two complete page writes. Some form of background garbage collection is also a
possibility, scanning and seeking blocks with less than a certain percentage of buckets free.

Treat directory blocks the same as data blocks? That way should help with wear levelling, since directory blocks probably reallocated more often.

If go for 32K block size, will often only need one 'active' directory block.

Keeping track of the directory location(s) could be interesting; these may have to be specifically identified, and the device scanned to find them at startup. This information
could then be cached in non-volatile storage elsewhere - FRAM/EEPROM/battery backed RAM.

The F767 supports a 'memory-mapped' mode for QSPI. Could this simplify things at all?

A level of RAM caching could sometimes be beneficial

This has also made me wonder whether the original MFS implementation is appropriate to a file system; with the right design, a single copy of everything may well suffice.

As an aside, there are some interesting comments on the UBIFs web site, especially in relation to NAND flash.

Tabulous
Posts: 509
Joined: Fri May 03, 2013 12:02 pm
Has thanked: 7 times
Been thanked: 17 times

Re: [NEWS] Introducing MFS

Postby Tabulous » Tue Nov 21, 2017 5:41 pm

Giovanni wrote:
Tabulous wrote:
Giovanni wrote:Question!

How valuable would it be to be able to use FatFS (or others) on top of a MFS partition? a thin block-device emulation layer would be needed between the twos. It would enable creating a full FS on top of any flash, even internal ones (performance would not be necessarily great).

This emulation layer could also include a RAM buffers cache at 512 bytes block level for cached access and, optionally, delayed writes.

The interesting thing is that even a FAT-based file system would have ensured wear leveling by the underlying MFS.

Giovanni


This would be very good, its what i did earlier this year. FatFS on top of SPI flash.


Which strategy did you use? there are several and right now I cannot decide.

Giovanni


It uses the s25f SPI flash library, but i wrapped that in my own flash wrapper. So the fatfs_diskio.c calls, call read and write block functions in my flash wrapper. Did this as i also wanted one block in the flash for eeprom emulation.

All works very well, also the Fat disk is available as a MSD when only the USB is connected to the board. Makes for easy firmware/config updates.

See here i shared the files

viewtopic.php?f=3&t=3320&start=20

User avatar
Giovanni
Site Admin
Posts: 14444
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 1074 times
Been thanked: 921 times
Contact:

Re: [NEWS] Introducing MFS

Postby Giovanni » Tue Nov 21, 2017 6:47 pm

This reminds me that I still need to merge that new driver...

I am moving that topic under "change requests".

Giovanni

User avatar
alex31
Posts: 374
Joined: Fri May 25, 2012 10:23 am
Location: toulouse, france
Has thanked: 38 times
Been thanked: 61 times
Contact:

Re: [NEWS] Introducing MFS

Postby alex31 » Fri Nov 02, 2018 11:31 am

Hello,

I need to store few key->value records, so I have a question about MFS :
The example (testhal/STM32/multi/QSPI-MFS/main.c) use an external chip as store, is there a portable way (at least F4/F7, later L4) to use MFS over internal flash (without having to provide hardware dependant low level flash function for each families) ?

Thanks
Alexandre

User avatar
Giovanni
Site Admin
Posts: 14444
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 1074 times
Been thanked: 921 times
Contact:

Re: [NEWS] Introducing MFS

Postby Giovanni » Fri Nov 02, 2018 11:37 am

Hi,

MFS is not HW-dependent but you need to give it a valid flash interface (a flash driver), it does not matter if internal or external or emulated.

Giovanni

User avatar
alex31
Posts: 374
Joined: Fri May 25, 2012 10:23 am
Location: toulouse, france
Has thanked: 38 times
Been thanked: 61 times
Contact:

Re: [NEWS] Introducing MFS

Postby alex31 » Fri Nov 02, 2018 12:09 pm

Thanks Giovanni for your answer, so probably the flash interfaces for internal flash of stm32[f4,f7,l4] do not exist yet and they need to be written.

I think using embedded flash to provide key->values permanent storage is a common need, and it would be nice to have demos using it on the demo directory for stm32 family.

Alexandre

User avatar
Giovanni
Site Admin
Posts: 14444
Joined: Wed May 27, 2009 8:48 am
Location: Salerno, Italy
Has thanked: 1074 times
Been thanked: 921 times
Contact:

Re: [NEWS] Introducing MFS

Postby Giovanni » Fri Nov 02, 2018 1:03 pm

Hi,

A flash driver for STM32 has been contributed if I remember well, search the forum, probably it needs to be updated but it would be a base.

Giovanni


Return to “Development and Feedback”

Who is online

Users browsing this forum: No registered users and 18 guests