Wear leveling on a microcontroller's EEPROM

The technique I normally use is to prefix the data with a 4-byte rolling sequence number where the largest number represents the lastest / current value. In the case of storing 2 bytes of actual data that would give 6 bytes total and then I form into a circular queue arrangement so for 128 bytes of EEPROM it would contain 21 entries and increase endurance 21 times.

Then when booting the largest sequence number can be used to determine both the next sequence number to be used and the current tail of the queue. The following C pseudo-code demonstrates, this assumes that upon initial programming the EEPROM area has been erased to values of 0xFF so I ignore a sequence number of 0xFFFF:

struct
{
  uint32_t sequence_no;
  uint16_t my_data;
} QUEUE_ENTRY;

#define EEPROM_SIZE 128
#define QUEUE_ENTRIES (EEPROM_SIZE / sizeof(QUEUE_ENTRY))

uint32_t last_sequence_no;
uint8_t queue_tail;
uint16_t current_value;

// Called at startup
void load_queue()
{
  int i;

  last_sequence_no = 0;
  queue_tail = 0;
  current_value = 0;
  for (i=0; i < QUEUE_ENTRIES; i++)
  {
    // Following assumes you've written a function where the parameters
    // are address, pointer to data, bytes to read
    read_EEPROM(i * sizeof(QUEUE_ENTRY), &QUEUE_ENTRY, sizeof(QUEUE_ENTRY));
    if ((QUEUE_ENTRY.sequence_no > last_sequence_no) && (QUEUE_ENTRY.sequence_no != 0xFFFF))
    {
      queue_tail = i;
      last_sequence_no = QUEUE_ENTRY.sequence_no;
      current_value = QUEUE_ENTRY.my_data;
    }
  }
}

void write_value(uint16_t v)
{
  queue_tail++;
  if (queue_tail >= QUEUE_ENTRIES)
    queue_tail = 0;
  last_sequence_no++;
  QUEUE_ENTRY.sequence_no = last_sequence_no;
  QUEUE_ENTRY.my_data = v;
  // Following assumes you've written a function where the parameters
  // are address, pointer to data, bytes to write
  write_EEPROM(queue_tail * sizeof(QUEUE_ENTRY), &QUEUE_ENTRY, sizeof(QUEUE_ENTRY));
  current_value = v;
}

For a smaller EEPROM a 3-byte sequence would be more efficient, although would require a bit of bit slicing instead of using standard data types.

Following is a method that uses buckets and about one overhead byte per bucket. The bucket bytes and overhead bytes get about the same amount of wear. In the example at hand, given 128 EEPROM bytes this method allocates 42 2-byte buckets and 44 status bytes, increasing wear capability about 42-fold.

Method:

Divide the EEPROM address space into k buckets, where k =⌊E/(n+1)⌋, with n = setup-data-array size = bucket size, and E = EEPROM size (or, more generally, the number of EEPROM cells to be devoted to this data structure).

Initialize a directory, an array of m bytes all set to k, with m = E-n·k. When your device starts up, it reads through the directory until it finds the current entry, which is a byte not equal to k. [If all directory entries equal k, initialize the first directory entry to 0, and go on from there.]

When the current directory entry contains j, bucket j contains current data. When you need to write a new setup-data entry, you store j+1 into the current directory entry; if that makes it equal to k, initialize the next directory entry to 0, and go on from there.

Note that directory bytes get about the same amount of wear as bucket bytes because 2·k > m ≥ k.

(I adapted the above from my answer to Arduino SE question 34189, How to increase life of EEPROM?.)

I have used a rolling sequence number for this (similar to Peter's answer). The sequence number can actually be as little as 1 bit, providing the number of elements in the cue is odd. The head and tail are then marked by the 2 consecutive 1's or 0's

For example if want to roll through 5 elements the sequence numbers would be:

{01010} (write to 0) {11010} (write to 1) {10010} (write to 2) {10110} (write to 3) {10100} (write to 4) {10101} (write to 5)