Daniel Beer

17 Apr 2014

This package implements a simple and effective shadow-paging scheme for use with NOR flash or EEPROM. It has the following features:

• Small footprint: it uses only a single byte of memory to hold state between active read and write transactions. During an active transaction, a few extra bytes of state are held on the stack. This memory use is constant-size, and not proportional to the size of flash blocks.

• Writes are atomic. If the power fails while updating the stored state, the previous state is left intact for the next power cycle.

• Writes are verified. If a write completes, but corrupts the memory due to a low programming voltage, then the result is as if the write was never attempted.

• The API is easily adaptable to both memory-addressable flash and serial flash.

• There is some resistance to offline corruption. If the most recent version is corrupted, the system will revert to the previous version, if it is intact.

Type make test to build and run a simple test program, using a simulated EEPROM device.

## Algorithm

The algorithm used to implement this is developed in stages. First, start with the most naive write scheme possible: update data on a single flash block simply by erasing and re-programming it.

### Checksums

The most obvious problem is that if power fails while rewriting the block, you're left with a block containing garbage. So, alter the format of the block slightly, by dedicating a few bytes to a checksum:

[USER PAYLOAD] [4-BYTE CRC32]

Now we can tell if a write completed successfully: if the power fails during a write, the resulting block is unlikely to contain a valid checksum. This also gives us a method of testing for offline corruption.

If the power fails using the above scheme, we can be reasonably confident that we won't read back garbage. But we still have a problem: we won't read back anything at all in the case of a failure.

This is where we introduce a simple shadow-paging scheme: instead of reprogramming a single block, use a pair of independently reprogrammable blocks and alternate between them. No matter what happens, we'll always have at least one version which is intact, and we can detect which blocks are intact by testing the checksum.

### Versions

Now we can deal with power failures without losing data. One final problem remains: if we didn't have a power failure during the previous write, we'll have two perfectly good versions of the data on the next power cycle. How do we know which is the most recent version?

Simple: by adding a toggling magic marker to the block format:

[USER PAYLOAD] [2-BYTE MAGIC] [4-BYTE CRC32]

The magic marker field has two possible valid values: MAGIC (an arbitrary constant) and magic (the inverse of MAGIC). The rules for picking the value to be used on each write is:

• Designate one of the blocks 0 and the other 1.

• When writing to block 1, use the same magic value that we used on the last time.

• When writing to block 0, use the opposite magic value to that which was used last time.

Observe the data held in a pair of blocks after each update in a sequence of rewrites. In each row, the most recent version is indicated with square brackets:

Version    Block 0    Block 1
--------------------------------
-----      -----
0          [MAGIC]     -----
1           MAGIC     [MAGIC]
2          [magic]     MAGIC
3           magic     [magic]
4          [MAGIC]     magic
5           MAGIC     [MAGIC]
6          [magic]     MAGIC
7           magic     [magic]

This sequence is periodic: the state is identical after every four writes.

Following a power-on, we scan each of the pair of blocks and determine for each, the following two bits of state:

• Vi: Block i contains a valid checksum and magic value.

• Mi: Block i contains magic (as opposed to MAGIC).

Note that if Vi = 0, Mi is irrelevant. We therefore have only three states of interest to consider for each block in the pair.

Using the combined four bits of state, we can determine three bits of state which describe the block-pair:

• V: Whether we have any valid data at all.

• A: The block that contains the most recent data.

• M: Whether the most recent block contains magic (as opposed to MAGIC).

We construct the following truth table (3 * 3 = 9 input states of interest):

V0    M0    V1    M1    | V    A    M
------------------------+---------------
0     x     0     x     | 0    x    x
1     0     0     x     | 1    0    0
1     1     0     x     | 1    0    1
0     x     1     0     | 1    1    0
0     x     1     1     | 1    1    1
1     0     1     0     | 1    1    0
1     0     1     1     | 1    0    0
1     1     1     0     | 1    0    1
1     1     1     1     | 1    1    1

...and from it, derive formulas:

• V = V0 | V1
• A = ~V0 | (V1 & (M0 == M1))
• M = A ? M1 : M0

The state (V, A, M) is all we need to know about the state of the current block. We can derive the state after the next write as:

• V' = 1
• A' = ~A
• M' = M ^ A

The next state (V', A', M') tells us where to write the next version, and what magic value to use.

## Flash interface

This section describes the contents of nor.h, which you must provide. A trivial example is provided in the source package.

To use the shadow-paging system, you need to define a low-level interface to the memory device. The first thing you need to define is a handle to describe blocks:

typedef ... nor_block_t;

This can be whatever type you like. It is passed by value, and never manipulated or managed by the shadow-pager. You then need to define the pairing relationship that exists between blocks. Each block-pair has a designated representative, which is what you will pass to the shadow-pager. The shadow-pager in turn uses the following function to get the other block of the pair:

nor_block_t nor_shadow(nor_block_t representative);

You must specify the smallest unit of data access and programming (word size), and the number of such units comprising a block. The example file specifies a 16-bit word size and a 512-byte block size:

typedef uint16_t nor_word_t;

#define NOR_WORD_BITS   16
#define NOR_WORDS       256

All transactions consist of a sequence of words, transferred one at a time, and explicitly delimited by begin and end operations. For example, the write interface requires you to define:

typedef ... nor_write_pointer_t;

void nor_write_begin(nor_block_t blk, nor_write_pointer_t *ptr);
nor_word_t nor_write_word(nor_block_t blk, nor_write_pointer_t *ptr);
void nor_write_end(nor_block_t blk, nor_write_pointer_t *ptr);

The function nor_write_begin should erase the block. A similar interface exists for read transfers:

typedef ... nor_read_pointer_t;

void nor_read_end(nor_block_t blk, nor_read_pointer_t *ptr);

The begin and end functions are always used for all block transfers. You can therefore use them to control, for example, the chip-select line for a serial flash memory.

## User interface

Suppose you want to store configuration data in a shadow-paged block pair. First, declare the representative block that you want to use for the purpose (and by implication, a shadow block), and a state variable:

static const nor_block_t config_block = ...;

shadow_state_t config_state;

During power-on initialization, scan the block pair:

config_state = shadow_scan(config_block);

This state variable contains the (V, A, M) state bits described above. At this point, you should either read the valid data (if it exists), or load default values:

if (shadow_has_data(config_state)) {

} else {
/* load default values ... */
}

At any point, you can write a new version to the appropriate shadow-block:

struct shadow_writer writer;

config_state = shadow_write_end(&writer, config_state);

Note the final update of config_state when the transaction completes. This is essential for correct operation.

If you want to be able to react to programming failures immediately, you can alter the final update slightly:

const shadow_state_t next_state = shadow_write_end(&writer, config_state);

if (next_state != config_state) {
/* The write completed successfully */
config_state = next_state;
} else {
/* Something went wrong -- the write was corrupted */
/* ... */
}

This extra check isn't required for safe operation. Even if you don't perform this check, the state will be silently rolled back -- further write attempts will never overwrite the sole good version.