Wear Leveling

The simple reset counter sketch works pretty well and is completely unaffected by the boot loader. Also it gives some quite interesting insights on how often the Arduino gets reset during boot of the main computer and due to other causes. The simple approach has some minor issue though. The EEPROM cells will not last forever. According to the data sheet they are only guaranteed to be good for 100 000 write cycles.

You can find experiments on the internet where these cells are tested and seem to survive way more cycles. But these experiments ignore the fact that failure of the cells does not mean that they do not retain the values anymore. Failure means that they will not retain data for sustained periods of time anymore. If the cells could be guaranteed to last much longer then Atmel would surely advertise this. So we have to believe the data sheet and this means 100 000 cycles are the limit. Anything beyond is just luck.

This is not really an important issue because it is very unlikely that any Arduino will be reseted >100 000 times. Anyway I use this as an excuse to look into „wear leveling“. The idea is to use multiple EEPROM cells to store the data. By writing a different cell each time the wear gets leveled and therfore the to time to failure will be extended. The standard approach for wear leveling are „ring counters“. That is the cells are considered as a „ring“. After a position in the ring is updated the next write will go to the next position. Usually these ring counters are used to store a pointer to the actual data. But since I only need some counter I will be satisfied with implementing the ring counter only.

The next sketch shows how such a counter can be implemented.

//
//	www.blinkenlight.net
//
//	Copyright 2011 Udo Klein
//
//	This program is free software: you can redistribute it and/or modify
//	it under the terms of the GNU General Public License as published by
//	the Free Software Foundation, either version 3 of the License, or
//	(at your option) any later version.
//
//	This program is distributed in the hope that it will be useful,
//	but WITHOUT ANY WARRANTY; without even the implied warranty of
//	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
//	GNU General Public License for more details.
//
//	You should have received a copy of the GNU General Public License
//	along with this program. If not, see http://www.gnu.org/licenses/


#include <EEPROM.h>

uint8_t get_next_count(const uint8_t count_limit) {
	// n cells to use --> 1/n wear per cll --> n times the life time
	const uint16_t cells_to_use = 128;

	// default cell to change
	uint8_t change_this_cell  = 0;
	// value of the default cell
	uint8_t change_value = EEPROM.read(change_this_cell);

	// will be used to aggregate the count_limit
	// must be able to hold values up to cells_to_use*255 + 1
	uint32_t count = change_value;

	for (uint16_t cell = 1; cell < cells_to_use; ++cell) {
		uint8_t value = EEPROM.read(cell);

		// determine current count by cummulating all cells
		count += value;

		if (value != change_value) {
			// at the same time find at least one cell that differs
			change_this_cell = cell;
		}
	}

	// Either a cell differs from cell 0 --> change it
	// Otherwise no cell differs from cell 0 --> change cell 0

	// Since a cell might initially hold a value of -1 the % operator must be applied twice
	EEPROM.write(change_this_cell, (EEPROM.read(change_this_cell) % count_limit + 1) % count_limit);

	// return the new count
	return (count + 1) % count_limit;
}


void setup() {
	uint8_t count = get_next_count(20);

	for (uint8_t pin = 0; pin < 20; ++pin) {
		pinMode(pin, OUTPUT);
		digitalWrite(pin, pin == count);
	}
}

void loop() { }

It is no surprise that this sketch exhibits the same visual behavior as the simple implementation. In fact the behavior is so much indistinguishable that I did not bother to create a different video of it. Instead I created only one video for both sketches ;)

With the next experiment we will use this approach to switch between multiple light effect modes.

5 Responses to Wear Leveling

  1. ikue says:

    I have a question regarding this interesting piece of source code: It seems to give the option of storing counts of up to 255 (one byte) only. What about storing a much larger number such as the “long” type? Which part of the structure would need to be changed?

    Thank you!

    • The easiest way would be to use this as an index to a larger structure. The idea would be to increment the index each time the larger records are written. Thus this could be used to distribute the load for the larger records. Since the Arduino has so little memory it would be reasonable to decrease n accordingly, e.g. suppose record size would be 4 bytes. The Arduino could store 256 * 4 bytes. The easisest way would be to go for 128 records and keep the number of cells as it is. Then just increment and use the result mod 128 as an index.

      • pimpdeeerste says:

        Thank you for your quick reply. I have found a way to simply address the available memory by multiples of 4 whenever reading / writing the EEPROM. This way, enough space is available for the “long” type which is 4 bytes in size.

        A remark on the source code listed above: Are you sure the “change_this_cell” variable is really changing to anything higher than 0 (its initial value)? In my tests it did not and by this there was no wear leveling function as only one EEPROM cell (no. 0) got rewritten all the time. Am I misunderstanding the purpose of the code above?

        Another thing important for people using this code: It assumes that only EEPROM space from cell no. 0 to “cells_to_use” is addressed. In case one wants to keep the first few cells for something else, e.g. starting at cell no. 50, one cannot simply write “change_this_cell=50;” because it would mess up the following code. Instead, a starting index needs to be added to any EEPROM read / write in the method, such as:
        uint8_t change_value = EEPROM.read(50 + change_this_cell);
        Maybe this hint is helpful to some beginners.

      • pimpdeeerste says:

        Thank you for your quick reply. I have found a way to simply address the available memory by multiples of 4 whenever reading / writing the EEPROM. This way, enough space is available for the “long” type which is 4 bytes in size.

        A remark on the source code listed above: Are you sure the “change_this_cell” variable is really changing to anything higher than 0 (its initial value)? In my tests it did not and by this there was no wear leveling function as only one EEPROM cell (no. 0) got rewritten all the time.

        Another thing important for people using this code: It assumes that only EEPROM space from cell no. 0 to “cells_to_use” is addressed. In case one wants to keep the first few cells for something else, e.g. starting at cell no. 50, one cannot simply write “change_this_cell=50;” because it would mess up the following code. Instead, a starting index needs to be added to any EEPROM read / write in the method, such as:
        uint8_t change_value = EEPROM.read(50 + change_this_cell);
        Maybe this hint is helpful to some beginners.

      • Yes, I am sure. I actually copied the published code to Arduino Ide, added a print statement and verified that it does so. Why do you assume that it does not work as it should?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s