Daniel Beer Atom | RSS | About

NOR-flash shadow paging

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:

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

Download the source code here:

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.

Shadow-paging

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:

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:

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:

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:

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:

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

Read/write interface

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_begin(nor_block_t blk, nor_read_pointer_t *ptr);
nor_word_t nor_read_word(nor_block_t blk, nor_read_pointer_t *ptr);
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)) {
        struct shadow_reader reader;

        shadow_read_begin(&reader, config_state, config_block);
        shadow_read(&reader, data1, sizeof(data1));
        shadow_read(&reader, data2, sizeof(data2));
        shadow_read(&reader, data3, sizeof(data3));
        shadow_read_end(&reader);
} else {
        /* load default values ... */
}

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

struct shadow_writer writer;

shadow_write_begin(&writer, config_state, config_block);
shadow_write(&writer, data1, sizeof(data1));
shadow_write(&writer, data2, sizeof(data2));
shadow_write(&writer, data3, sizeof(data3));
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.

License

Copyright (C) Daniel Beer <>

Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.

THE SOFTWARE IS PROVIDED “AS IS” AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.