Journalling flash storage algorithm

I mentioned in another post the possibility of storing all variables in flash and using the RAM as a cache. Potentially it could be used on the Original Espruino with an SD card, but actually the biggest use right now is on the ESP8266, where there isn't much free RAM but there's bags of flash.

I had a quick go at this and I have something that more or less works now - there's a bug with details and a branch here.

So that leaves how to store everything in flash memory. We need some way to efficiently save and retrieve data that:

• Works when you can only erase pages of data (let's say 4096 bytes) at once
  
• Works when writing converts 1 to 0
  
• Doesn't need much RAM
  
• Is relatively quick for reading and writing
  
• Doesn't wear out the flash
  
• Stores fixed-size blocks of data (16 bytes)
  
  

We basically need:

typedef char[16] Block;

Block load(int blockNumber);
void save(int blockNumber, Block block);

Any thoughts on this? I'm thinking we could just write a block at a time (along with its number) but could leave a few bytes next to it that would point to the next block with that number (if a new block replaced it).

Then I guess when all the flash pages but one got full up, it could move all the unreplaced contents of the first page into the final free one, then erase the first page.

It'd still be a bit slow for reading sometimes (as you'd have to follow the linked list to find the latest block), but might not be too bad.

... or has this already been done? I know there's SPIFFS, but I don't think that's really suitable (text file names, variable sized files).

[I'm assuming this is an esp8266 focused discussion]

From a performance point of view, you have to decide whether by "flash" you mean memory-mapped flash, i.e. 1MB, or all flash, i.e. up to 4MB. I have not made any performance benchmarks. I believe that the routine that reads from any flash has to jump through a bunch of hoops to disable the cache and such in order to gain control of the SPI interface. Getting a good grasp on that might be one place to start looking.

Some numbers: the current build uses 445780 of 483328 bytes of flash reserved for the firmware (472KB). (See flash map in the esp8266 reference page). The remainder of the first 512KB on a 512KB system has the bootloader (4KB) , the SDK save area (16KB), the Espruino save area (16KB) and the EEPROM emulation area (4KB). If you want to put JSvars into flash on such a system you have to take away from one of these.

On a 4MB flash system, the first 1MB has a total of 56KB of unused flash in 2 blocks. If you eliminate the ability to flash an update over the air then you have a bit over 512KB of free flash.

If you're willing to use rboot (open source bootloader), I believe you can change the cache mapping so you could have an upgrade partition and ~512KB of free flash.

The loading of a block is trivial, either using memory mapped flash accesses or the read-flash function. I think writing is more fun. If the bytes you're writing are erased there's a straight-forward function. The fun part is the garbage collection, you probably want to always have at least one block you can allocate into and ensure that by compacting blocks at idle time?

How would GC work with all this? Would you modify the GC so it could access flash directly, or would it basically wipe out the cache?

Personally, I believe that with 1400-1500 JSvars things are going to be OK and the next step I would go is to be able to preload modules where the code is stored in flash using native strings.

Yes - on normal 512k parts it wouldn't be useful at all, but on the 1MB parts I imagine most people would be interested in using the extra 512k even if that meant they couldn't use the bootloader (and that 512 is memory mapped?).

Usage won't be 100%, but suddenly having ~200kB of program memory available would be hugely exciting to a lot of people I imagine.

With the modules, I'm still not sure it will save you much - I guess it might be possible to do some hack that allowed function code to stay in flash memory, but right now just parsing the module from a string in flash wouldn't make any difference to the final result at all (since the string is thrown away after parsing in Espruino).

As you say, 1400 vars is good though, and will probably mean this isn't that urgent.

Still, I think this could be pretty cool - and is something totally different that none of the other language interpreters for the ESP8266 can manage (as far as I know).

I think GC could possibly be split into two passes - one that worked quickly on just what was in the cache, and one that ran on what was in flash, but only when there was a real problem with memory.

Having had a play with the branch, it seems like there's actually very little thrashing involved in most things - generally code just stays in RAM and you don't see much performance drop-off.

Cool. How do you think this affects the flash longevity? Do these things do wear leveling? I assume not, right?

Having the algorithm above should effectively do wear levelling (it's just going to work its way round all the flash pages, without thrashing one in particular). The only bad point really is the time taken to find a JsVar, as you're basically just searching through the Journal.

I thing some kind of 'index' right at the start would help with that though.

It's kind of hard to describe the algorithm. I guess the best option would be to create a 'fake' flash memory for the Linux build and then to play around with different approaches.

Hi,
I've started a module that stores and recovers JavaScript fragments in esp8266 flash.
The first 4096 byte page is used to store a json string that holds a structure.
The first part of this contains the length, and the rest is an associate array holding keys, and the start page and number of pages for the object stored at this key.

The idea is to be able to store css, html, and js fragments in flash.

Using a .pipe method, requests to these resources can be streamed out to the browser using very little memory overhead.

I have also tested storing functions and eval'ing to load and run the function.

I'm also experimenting with a cache type function - where you specify the source uri, this is fetched from the web, and then stored in cache.
This means images, bootstrap.css and other resources can be stored on the device, meaning it can be run in ap mode, and still have a decent looking interface. This means that a page could be set up, which does a wifi scan, provides a select list of access points, and asks a password to join a network.

Let me know if you would like to see the code so far.

Have you seen: http://www.espruino.com/FlashEEPROM

While it doesn't have filenames, it will store numbered items in a journalled way, but actually within pages (rather than one page for each item) so it's a bit more efficient.

Yours is probably better for big blocks of data that don't change often though. I hacked something very simple up for the google sheets tutorial for the Pico but it would be way better to have something in a module.

By the look of it you've spotted E.memoryArea too - that could be really interesting if your code could make the data easily available - however actually implementing pipe like you've done is still the best bet for HTTP - as even if you had a massive string you wouldn't be able to just write it with Socket.write.

@wilberforce, some time ago a manual was created. It describes something similiar on a very low level.
http://jumspruino.jumware.com/docu/Add_JS_Commands.html
I would be very interested to see your code. There are some problems with reading bytes from flash, afaik sources in github already have a solution for this. Gordon added some lines some time ago.

I've been looking at the variable_cache branch for a bit. I like it :-) I've been a bit stuck on how to store variables in flash. Basically implementing

typedef char[16] Block;
Block load(int blockNumber);
void save(int blockNumber, Block block);

The main difficulty I've been struggling with is how to find where the most recent version of a specific JsVar is stored in flash so it can be loaded into RAM. Each time a JsVar is evicted dirty from RAM it has to be written to a new location. That means it later has to be found... Assuming 1MB of flash @16-32 bytes per JsVar one ends up with 32k-65k JsVars. That makes it impractical to keep a mapping table in memory. So finding a JsVar has to happen by traversing flash. (Unless I'm missing something.)

The idea I've come up with is the following:

• Divide the total flash into two regions: a base region and an update region.
  
• The base region is used to store the first version of a JsVar. It is managed as an indexed array, i.e., locating the first version of a specific var is a simple index operation into the array. This first version is not only the first value but also the start of that JsVar's linked update list.
  
• The update region is managed as a journal: one updated JsVar is written at a time into consecutive locations. When the journal is full the first page needs to have been erased so the journal can wrap around.
  
• When a JsVar is first written, it is written to the base region into its location there.
  
• When a JsVar is updated (written back from RAM to flash) it is appended to the update region and a pointer to the update location is added to its location in the base region. This means that each JsVar in the base region needs to have extra bytes to point to the first update location.
  
• When a JsVar is updated again its update linked list is continued, this means that to find a JsVar that is frequently evicted from RAM one has to follow several pointers (which becomes slow).
  
• As the update region starts to fill up flash-GC is invoked, it's job is to free pages for the journal.
  
• The way flash-gc works is by rewriting base region pages by collecting the latest values of all the variables in the page. This removes data from the journal and resets the update linked lists.
  
• For each journal page, flash-gc needs to maintain a count of occupied JsVar slots. When the count for a page turns to zero the page can be erased and added to the journal's free list. This means that the journal isn't strictly sequential (there's some room to play there).
  
  

The first thing I don't know what to do about is the free JsVar list. As a first cut, when a JsVar is freed (which often does not involve GC) that's just an in-memory operation which changes the JsVar's value. It may be reallocated and get a new value without any effect on flash. I.e. a free JsVar is really no different from a full one from the flash storage point of view. However, this means that initially the base region would be filled with this linked list and the first actual value written to any JsVar would already use the update region. Most likely free JsVars should be stored as 0xFFFF..FF in flash and the allocation of a JsVar changed...

The second thing is regular GC. Currently GC does a first pass through all JsVars and modifies them to clear the is-live flag, and then it does a pass through all live JsVars to set their is-live flags, and finally it adds all dead JsVars to put them into the free-list. This means that for every GC pass every JsVar is modified twice. If there truly is only one bit per JsVar needed for GC then maybe storing that as a bit array in RAM for the duration of GC is OK.

Just to get a feeling for the numbers involved, the following might be doable:

• 1MB total flash for JsVars
  
• 18 bytes per JsVar in flash
  
• 58K JsVar slots total
  
• 16 bits to address any JsVar slot in flash
  
• Base region of 256KB
  
  • 14K JsVars available to the application
    
• Update region of 756KB
  -43K update slots
  
• JsVar storage:
  
  • 16 bytes for actual JsVar value as represented in RAM
    
  • 2 bytes to link to next update value
    
• GC marking bit array: <2KB
  
  

One final major concern is real-time performance. I don't know how flash erase works on ARM chips, but on the esp8266 it's not asynchronous: the processor has to wait for the erase to complete. A typical erase takes 30ms, but can take up to 400ms (the time increases with the number of erase cycles). If the application has idle time and can trigger gc-flash at that point there may be no problem. But if it's running a continuous display or neopixel animation there are going to be hiccups.

Thoughts?

Some random thoughts:

There is a page size difference with arm/esp8266 - 256/4096 .

Can a closure compiler or similar be used to work out what is "constant" so that goes directly to flash?

You seem to be describing a write through cache. For rapidly changing vars, loops interators etc, these don't need to go flash at all.

Yes, it's a write through cache. That's what Gordon implemented. If it uses random replacement, which is what I would use, then evictions are independent if frequency of use.

@Wilberforce the idea is to avoid any pre-computation of what is constant and what isn't - it would 'just happen'.

@tve great - thanks for taking a look at it!

What you're suggesting sounds like what I had in mind - so you leave each JSVar's address in flash as 0xFFFF, and then overwrite it with the address of the new var if the var gets replaced?

For testing, what I had in mind was to make the Linux versions of jshFlashRead/Write/Erase/etc work on a file (or even just RAM) and behave like proper flash memory would. You can then develop + debug it on linux with a proper debugger :)

The free list is tricky - for simple stuff it could definitely just pick something from the variables in the cache, and then maybe just do a linear search for a free variable if it missed the cache (keeping unused entries at 0xFF) - but as you say, for starters it's best to leave what's there and see how it performs. As you say it probably wont be that bad because the free list will tend to use stuff that was in the cache anyway.

For GC - I guess the bit set/reset code could just call a function, and in the variable cache case that function could do something different. I think it might even be able to store the GC bit in flash, because basically the bit is just reset (flash erase) and then set when the var is referenced (but never cleared again). You could then use a huge amount of flash.

But RAM would be faster (and much easier for now :). The page erase is going to be slow - on most ARM you can do it non-blocking I think (but it's sometimes not exposed via the API). I think it's probably something that (at least for now) people will have to deal with. Another option is to do the erase on idle when the interpreter knows it's got some free time before the next setInterval - it's not perfect but it'd help in a lot of cases.

When I did some tests, I found that even with relatively few variables in RAM (256?) there was virtually no cache eviction during normal execution, so I think the interpreter will stop pretty rarely.

Sounds like we have a plan, Now need the time :-)