Journalling flash storage algorithm

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?