Wear leveling on a microcontroller's EEPROM

For example: The datasheet for ATtiny2313 (as do most Atmel AVR datasheets) states:

128 Bytes In-System Programmable EEPROM Endurance: 100,000 Write/Erase Cycles

Imagine a program only requires two bytes to store some configuration, the other 126 bytes are effectively wasted. What concerns me is that regular updates of the two configuration bytes may wear out the device's EEPROM and render it useless. The whole device would become unreliable, because at a certain moment you just can't keep track of which bytes in EEPROM are unreliable.

Is there a smart way to do wear leveling on a microcontroller's EEPROM when you effectively use only one or two bytes out of available 128?

Answer

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.