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).