Now that the basic requirements and API for the EEPROM emulation are known, we can move on to the design and implementation of it all. Here’s the basic idea:

• there are two pages of flash memory in use for EEPROM emulation
• at any point in time, one is actively being used, the other is empty
• the first half of the page is used to store variable values, by index
• the second half contains slots for changes, as «index, value» tuples
• normal changes add to the end, and can be re-written to flash in-situ
• when we run out of slots, we compact the page and store it in the other flash page
• once that write is done, we erase the original page
• the next time around, both flash pages then change place
• the first value (variable #0) is reserved and stores the page number

This is the layout of a single page (using a 32-byte page size here, for brevity):

The key is to never overwrite any value with another one, unless:

• the original value is all ones, i.e. 0xFFFF (meaning it was still unset), or …
• … we are compacting the data structure and writing it to a new empty flash page

Furthermore, new pages are written to flash memory as follows:

• the underlying flash page is erased
• values[0] is set to 0xFFFF, i.e. not filled in yet
• the data is saved to flash
• values[0] is now set to the page number
• the modified data is saved again to flash

This ensures that there is never an incomplete page in flash which could be mistaken as valid, since the page number is always written last, after the rest is known to be in place.

Note that we do assume that 16- and 32-bit writes to flash are atomic: they either succeed in full, or don’t take place at all – even in case of sudden power loss. If this turns out to be an issue, our algorithm will have to be refined so that a single bit change marks completion.

We also need to keep three pieces of information in RAM:

• the master copy of the currently active flash page
• a map from variable index to change slot (or 0 if not changed yet)
• the index of the next unused tuple

This RAM info is reconstructed from what’s in flash memory at initialisation time.

Here is an extract of the class definition (full code on GitHub):

class RomVars {
  typedef struct { uint16_t key, val; } Tuple;

public:
  void init ();
  Ref operator[] (int index);

private:
  uint16_t& at (int index);
  uint16_t set (int index, uint16_t newVal);
  bool reusePage (int page);
  void combineChanges ();
  void flipAndSave ();

  union {
    uint16_t values [NumVars];
    Tuple tuples [NumVars];
  };

  uint8_t map [NumVars];
  uint16_t fill;
};

Only two public methods: init() and the array operator for getting/setting an item.

In the case of a 64-byte flash page, NumVars will be 16. Since a Tuple is 4 bytes, the union will be 64 bytes long, with the 16 values entries overlapping the first 8 tuples entries.

The map array entries will be either zero, meaning the values[] array has the actual latest values, or some value from 8 to 15, meaning the tuples[] array has the latest value, at the index indicated in the map. Note that the first time a rom variable is set, this will end up in the values array, and that each change after that creates a new entry in the tuples array, starting at entry 8. The fill variable tracks the next unused entry in tuples.

There are quite a few design trade-offs to be made in this code. The important part is that these choices match the properties of flash memory (erase rarely, atomic single-word writes) and the expected usage patterns (fast access, occasional changes).

The actual implementation uses a number of fairly advanced C++ tricks – stay tuned!

[Back to article index]