EEPROM wear levelling

Using Arduino Programming Questions
#1

For the prototype I'm working on, I need to save an int16_t several times a day (i.e. at least once, less than 20). I just need to keep track of one integer at a time: I don't care if I lose the previous ones. My integer will be about a few hundreds around zero, say between -400 and +400, including 0. That makes many possible int16_t values out of range, so I thought I could use some of them as landmarks to find the next 2 cells in memory to be written to.

For example, to save -20, I'll fill the first 2 cells with 0xFFEC and the following 2 with 0xDFDF (don't fill, don't fill), which translates to an out-of-range integer. To save the next value, I scan for the last 0xDFDF I can find and fill the next 2 cells. If I reach the end of the EEPROM, I wipe the whole memory and start over. To retrieve the last value, I scan for the last 0xDFDF and read the previous 2 cells. This linear search is going to be slow, but I only need to do it once on each reboot, so it doesn't worry me too much.

Before I go out and start working on an implementation, however, I'd like to hear some opinions. Is my algorithm sound? Is there a simpler way that I haven't thought of?

Further info: My chip of choice is an 8-bit Nano (I think it comes with a 512-byte EEPROM). If the board were to lose power in the middle of a writing operation, thus corrupting the memory, that would be annoying, but not safety critical or financially expensive in any way. I'd like to be warned if this happens, however.

#2

If any value outside (-400, 400) is unused, you can use it as an "available" value. Make it a circular buffer, no need to erase the entire thing. Look for the first valid value (all others should be available). Write that one as available, increment and write the new value to the next location.

1 Like
#3

Seems unlikely.

#4

To me too, now that you mention it. I took off that extra 'k'.

#5

Still a little on the low side, no?

#6

Oh, come on! It may be twice or 4 times that, who cares?

#7

Not you, clearly.

#8

So, if I follow your logic, I should write in a trailing "available" value that I shall overwrite and push forward as I go. Then, at boot time, I scan the EEPROM for that value and remember where I saw it, so I can increment from here. If I can't see it anywhere, I filled up the memory, so I start over from cell #0. Is that it?

However, when you say

since 0x0000 and 0xFFFF are both within range, do you suggest that I should first initialise the whole memory? At this point, doesn't it make more sense to just stop as soon as I see the first "available"? This would tell me that the last 2 cells I wrote to were the ones just before.

#9

Clearly, because in this particular case it does not matter. 512 bytes, 1k, 2k all pose the same problem and lead to the same possible solutions. I may care in other cases, though.

#10

Hi @330R

you did not inform which method you will use to write to the EEPROM.
As they are "int" type variables, I recommend using the EEPROM.put() method to write and the EEPROM.get() method to read.
This method (put) has the advantage of using the EEPROM.update method to record, that is, it only records if the value of each cell is different from what is there.
Then I would record like this:
position X int(2bytes), EEPROM,put(x, myvar);, marker 0xDFDF(2 bytes) EEPROM,put(x, varMarker);, int varEnd = 0xFFFF), EEPROM.put(x+6, varEnd); .
Then you on the next recording look for 0xFFFF and start recording at x - 2, if it is the end of the EEPROM (1024 in the case of the Atmega328), go to the beginning.
This way it would save some recordings and it would not be necessary to reset the entire EEPROM when it was full.
Which would represent one more recording each (1024/4), 256 recordings.

EX:
x = 240
myVar = -250 = 0xFF06
EEPROM 240 = 0XFF, 241 = 0x06, 242 = 0xDE, 243 = 0xDE,
244 = 0x?? , 245 = 0x??, 246 = 0xFF, 247 = 0xFF

Lokking for 0XFFFF ----> 246
x = 246 -2;
next recording:
X = 244
mayVar = 28 = 0x001C
EEPROM 244 = 0x00, 245 = 0x1C, 246 = 0xDE, 247 = 0xDE,
248 = 0x??, 24A = 0x??, 24B = 0xFF, 24C = 0xFF

RV mineirin

#11

No, you can do this anytime you want to write a value. To initialize the system, fill the array with "available", for example 0xFF's. But, see the "gotcha" at the end here...

To store a new value:

  1. Begin anywhere you like (because only one valid value is ever stored), seek until you find a non-available (valid data). Remember this position, but no need to store it, you only need it right now!
  2. Overwrite the old valid data with an "available", e.g. 0x7FFF
  3. Advance the address by one (and check for wrap around), and store the new value
  4. Profit.

Notice that you can subdivide the EEPROM and still have this, you just need to define the buffer start and end points - of course the math is easier if you use a power of 2 size and offset.

You're correct about the first time exception, then nothing is stored and it has to stop somewhere rather than repeatedly searching and not finding. The easiest solution for that, is to initialize it with all "available", but also one dummy value.

Subsequently, at any given time, the buffer will contain all "available" markers, except for one valid data value.

For safety, in case corruption happens between overwriting the old value and writing the new one, it might be better to:

  1. Begin anywhere you like (because only one valid value is ever stored), seek until you find a non-available (valid data). Remember this position, for the overwrite.
  2. Advance the address by one (and check for wrap around), and store the new value
  3. Overwrite the old valid data with an "available", e.g. 0x7FFF
  4. Profit.

If it were interrupted, it would leave behind two data values. But on the next go round, the "extra" advance data would be overwritten. This would preserve the previous data but not the most current one. But it would restore the desired condition of having only one value in the buffer.

As long as you are saving only one data item per buffer, there is never any need to store an EEPROM address in the EEPROM itself.

Also, you are only "blind" at boot time. After that, you can keep a "candidate" address for the data where you can start searching when you want to write. It's foolproof because if it misses, it will just keep looking until it finds data anyway... but in this case, usually you would not have to search the entire EEPROM buffer each time. On boot, the search might succeed at the first location, or the last, depending on where the data was last stored.

#12

The EEPROM is rated for 100,000 cycles so is it really a problem?

#13

Thing is, often the EEPROM is mostly empty. So why not use it efficiently if it's not too much work?

#14

Not a big one, but it bothers me to just write and rewrite in place. In fact, my first idea was to hard-code an offset and update it from time to time, but an efficient use of memory is more elegant, needs no further intervention and leads to a reusable solution if I'm happy with how it turns out this time.

#15

This part is unclear. 0xFFFF is decimal -1 when interpreted as an int16_t, and -1 is within the range of my values. How would I know that 0xFFFF is anything special as opposed to a legit value?

I use EEPROM.read and EEPROM.write and do all the conversions manually. Of course, I only update the EEPROM when necessary, that is, when I must update the value.

#16

Since 0xFF is the "erased" value of EEPROM, and since 0xFFFF (aka -1) is also a valid value in your code, I would simply flip the high bit when reading a value from and writing a value to EEPROM. So then when you read 0xFFFF from EEPROM it becomes the value 0x7FFF, which is not in the valid range for your data.

#17

In cells index 2, this is 2, 6, A, E, 12, 16, 1A ...... there in no data but the marker code .
RV mineirin

#18

As @christop implies and provides a means to do, you can always shift your legal values into any range, like add 500 before you store them and subtract when you retrieve.

Then all you valid stored numbers are between 100 and 900 (say) and anything greater or negative can have special meaning.

For example.

a7

#19

You can store the value distributed (as the XOR of all the values in the EEPROM).

Then you don't need any available flags or whatever and thus no need to write anything but a single entry. You simply step linearly round the EEPROM while the code is running to write each value (as the XOR of new and prev and existing location). At bootup you have to pick a random starting point (for wear to be level on average if the runs are short), as well as compute the total XOR of the EEPROM so you know the previous value written as each new write has to have the XOR of the new and previous values.

You can partition the EEPROM into multiple sections if you have multiple variables (those written more often would want more addresses to share the wear evenly).

The previous methods write twice as often as this scheme so it should double the life of the EEPROM.

#20

As code (using an array rather than EEPROM for clarity):

#define N ... whatever ....
int prev_value;  // whatever was written last
int eeprom[N] ;  // simulated EEPROM, N is size in units (here int)
int addr ;       // write pointer, advances round-robin fashion

void setup()
{
  prev_value = read_value() ;
  addr = random (0..N-1) ;   // tricky part is seeding this random number
}

int read_value ()
{
  int value = 0 ;
  for (int i = 0 ; i < N ; i++)
    value ^= eeprom[i] ;
  return value;
}

void write_new_value(int new_value)
{
  eeprom[addr] = eeprom[addr] ^ prev_value ^ new_value ;  // single write only.
  prev_value = new_value ;
  addr += 1 ;
  if (addr >= N)
    addr = 0 ;
}

Some details I glossed over, like addressing for multibyte entries in the EEPROM, randomizing well at startup.

You could lose the global prev_value and rescan the whole eeprom each time to calculate it when writing if you wanted.