Simple EEPROM Wear Leveling

In order to deal with the limited write cycles on EEPROM, wear leveling algorithms are commonly used. Generally speaking, the most common use case is storing fixed size data like user settings. After some searching, I came across a really clever algorithm that uses only one extra bit on top of the stored data. It’s a solid read I’d recommend checking it out.

Algorithm

Conceptually, we start by splitting the memory into evenly sized chunks that’s the size of the data we’d like to store plus one bit. Our goal is to write to a different chunk each time to spread out the writes. The extra bit, which we call a sentinel bit, is used to mark where the last written data is. We’ll write the sentinel bits in such a way that it’s a sequence of 1s followed by 0s or 0s followed by 1s.

Every time we want to read our data, we search for the location just before our bit changes which gives us the last written data. If the bit doesn’t change, it means the last index in our array of chunks is the last written data. Rather than searching linearly and comparing adjacent indices, we can use binary search and compare against the first index for that sweet O(log n) runtime.

Every time we want to write data, we simply write to the location after the last written data, keeping the same sentinel bit as the last written data. If we rollover, we flip the sentinel bit. This is how we maintain that the sentinel bit change marks our most recent data.

Implementation

To test out the algorithm, I wrote it in C++ on Mbed. It interacts with a separate EEPROM library that provides a simple random byte-level read/write interface. My implementation when writing doesn’t read in the last written data to set the correct sentinel bit but rather assumes the passed in data has the correct sentinel bit. This has a slight performance improvement at the cost of needing to be careful not to modify the sentinel bit and having to read it in the first time before writing.

// Wear-leveling algorithm based on https://sites.google.com/site/dannychouinard/Home/atmel-avr-stuff/eeprom-longevity
#include "mbed.h"
#include "WLPROM.h"
#include "EEPROM.h"
DigitalOut led(PC_13, 1);
BufferedSerial pc(PA_9, PA_10, 115200);
I2C i2c(PB_7, PB_6);
FileHandle *mbed::mbed_override_console(int fd) {
return &pc;
}
// Test Variables
AnalogIn rand_seed(ADC_TEMP);
#define NUM_WRITE 100
#define NUM_READ 100
#define NUM_ENDURANCE 1000000
WLPROM::WLData orig, cop;
int main() {
i2c.frequency(1000000); // 1MHz max clock rate
printf("Starting Tests!\n");
EEPROM::resetEEPROM();
// Start Tests
srand(rand_seed.read_u16());
printf("First block at %04X\n", WLPROM::findData());
WLPROM::read(&orig); // read first to make sure sentinel good
WLPROM::read(&cop);
// Write Speed Test
Timer t;
printf("Starting Write Speed Test...\n");
t.start();
for (uint32_t i = 0; i < NUM_WRITE; i++) {
WLPROM::write(&orig);
}
t.stop();
printf("Done! %u writes took %.3f secs, %.3f KB/s\n\n", NUM_WRITE, t.read(),
NUM_WRITE * sizeof(WLPROM::WLData) / 1024.0 / t.read());
// Read Speed Test
t.reset();
printf("Starting Read Speed Test...\n");
t.start();
for (uint32_t i = 0; i < NUM_WRITE; i++) {
WLPROM::read(&cop);
}
t.stop();
printf("Done! %u reads took %.3f secs, %.3f KB/s\n\n", NUM_WRITE, t.read(),
NUM_WRITE * sizeof(WLPROM::WLData) / 1024.0 / t.read());
// Endurance Test
printf("Starting Endurance Test...\n");
for (uint64_t i = 0; i < NUM_ENDURANCE; i++) {
printf("Test %llu - ", i);
for (int i = 0; i < sizeof(WLPROM::WLData::dat) / sizeof(WLPROM::WLData::dat[0]); i++) {
orig.dat[i] = rand() * rand();
}
WLPROM::write(&orig);
printf("written at %04X - ", WLPROM::findData());
WLPROM::read(&cop);
for (int i = 0; i < sizeof(WLPROM::WLData::dat) / sizeof(WLPROM::WLData::dat[0]); i++) {
if (orig.dat[i] != cop.dat[i]) {
EEPROM::dumpEEPROM();
printf("Fail! Expected: %08X, Actual: %08X\n", orig.dat[i], cop.dat[i]);
return -1;
}
}
printf("Pass!\n");
}
printf("Done! \n\n");
while (true) {
led = !led;
ThisThread::sleep_for(500ms);
}
}
view raw main.cpp hosted with ❤ by GitHub
#include "WLPROM.h"
namespace WLPROM {
void read(WLData* dat) {
EEPROM::readBites(findData(), (char*) dat, sizeof(WLData));
}
void write(WLData* dat) {
uint16_t next_addr = findData() + sizeof(WLData);
if (next_addr + sizeof(WLData) > EEPROM::EEPROM_SIZE) {
next_addr = 0;
dat->sentinel ^= SENTINEL_MASK;
}
EEPROM::writeBites(next_addr, (char*) dat, sizeof(WLData));
}
uint16_t findData() {
WLData dat;
EEPROM::readBites(0, (char*) &dat, sizeof(WLData));
sentinel_t sentinel = dat.sentinel & SENTINEL_MASK;
// binary search!
uint16_t left = 0, right = MAX_WL_BLOCKS;
while (left + 1 != right) {
uint16_t mid = (left + right) / 2;
EEPROM::readBites(mid * sizeof(WLData), (char*) &dat, sizeof(WLData));
sentinel != (dat.sentinel & SENTINEL_MASK) ? right = mid : left = mid;
}
return left * sizeof(WLData);
}
}
view raw WLPROM.cpp hosted with ❤ by GitHub
#ifndef WLPROM_H
#define WLPROM_H
#include "EEPROM.h"
namespace WLPROM {
typedef uint8_t sentinel_t;
typedef struct {
sentinel_t sentinel; // careful not to touch leftmost bit
uint32_t dat[4];
} WLData;
const sentinel_t SENTINEL_MASK = 1 << (sizeof(sentinel_t) * 8 - 1);
const uint16_t MAX_WL_BLOCKS = EEPROM::EEPROM_SIZE / sizeof(WLData);
void write(WLData* dat);
void read(WLData* dat);
uint16_t findData();
}
#endif
view raw WLPROM.h hosted with ❤ by GitHub

The EEPROM I tested on is the BRCF016GWZ. I pretty much just wanted to try soldering a CSP package. It can only write a certain number of bytes at a time, so I had to convert that interface to one that can write any number of bytes.

#include "EEPROM.h"
extern I2C i2c;
namespace EEPROM {
void resetEEPROM() {
char buff[MAX_BLOCK_WRITE];
for (uint16_t i = 0; i < MAX_BLOCK_WRITE; i++) {
buff[i] = 0xFF;
}
for (uint16_t i = 0; i < EEPROM_SIZE; i += MAX_BLOCK_WRITE) {
writeBlock(i, buff, MAX_BLOCK_WRITE);
}
}
void dumpEEPROM() {
char buff[32]; // size determines cells per line
printf("Dumping EEPROM...\n");
for (uint16_t i = 0; i < EEPROM_SIZE; i += sizeof(buff)) {
printf("%04X : ", i);
readBites(i, buff, sizeof(buff));
for (int j = 0; j < sizeof(buff); j++) {
printf("%X ", buff[j]);
}
printf("\n");
}
}
void readBites(uint16_t addr, char* dest, uint16_t length) {
if (addr + length > EEPROM_SIZE) {
return; // not enough memory!
}
while (i2c.write(ID, NULL, 0) != 0); // wait until chip is ready
char c = addr & 0xFF;
i2c.write(ID | (PAGE_MASK & (addr >> 7)), &c, 1);
i2c.read(ID, dest, length);
}
void writeBites(uint16_t addr, char* data, uint16_t length) {
if (addr + length > EEPROM_SIZE) {
return; // not enough memory!
}
// write until page aligned
uint16_t to_page_length = ((addr + MAX_BLOCK_WRITE - 1) / MAX_BLOCK_WRITE) * MAX_BLOCK_WRITE - addr;
if (length <= to_page_length) {
writeBlock(addr, data, length);
return; // no more bytes to write
}
writeBlock(addr, data, to_page_length);
addr += to_page_length;
data += to_page_length;
length -= to_page_length;
// now we can write MAX_BLOCK_WRITE at a time
while (length >= MAX_BLOCK_WRITE) {
writeBlock(addr, data, MAX_BLOCK_WRITE);
addr += MAX_BLOCK_WRITE;
data += MAX_BLOCK_WRITE;
length -= MAX_BLOCK_WRITE;
}
writeBlock(addr, data, length);
}
void writeBlock(uint16_t addr, char* data, uint16_t length) {
while (i2c.write(ID, NULL, 0) != 0);
char buff[length + 1];
buff[0] = addr & 0xFF;
memcpy(buff + 1, data, length);
i2c.write(ID | (PAGE_MASK & (addr >> 7)), buff, length + 1);
}
}
view raw EEPROM.cpp hosted with ❤ by GitHub
#ifndef EEPROM_H
#define EEPROM_H
#include "mbed.h"
namespace EEPROM {
// For BRCF016GWZ
const uint8_t ID = 0b10100000; // left 4 bits is ID
const uint8_t PAGE_MASK = 0b00001110; // 3 bits determines page
const uint16_t EEPROM_SIZE = 2048; // bytes
const uint8_t MAX_BLOCK_WRITE = 16; // bytes, size of pages
void resetEEPROM(); // call this if changing size of data structure stored
void dumpEEPROM();
void readBites(uint16_t addr, char* dest, uint16_t length);
void writeBites(uint16_t addr, char* data, uint16_t length);
void writeBlock(uint16_t addr, char* data, uint16_t length);
}
#endif
view raw EEPROM.h hosted with ❤ by GitHub

Extras

As a simple demonstration of this algorithm, the code works really well, but there’s definitely some features that could be added. We could add a CRC or checksum to detect errors and potentially fix them or revert to the last good write. Due to the nature of the algorithm, we also keep track of the past couple writes. Support for multiple instances or being able to split the memory up to write more than one kind of data could also be added. Even accounting for the memory itself and using a more optimized write pattern could be looked into.

Matt Written by:

Be First to Comment

Leave a Reply