wear levelling

Some storage strategies are based on using media that are known to get degrade over time. The example that springs to my mind, since I have been wrestling with it in one way or another for the past few weeks, is solid-state Flash memory.

Flash memory can only be written to about 100,000 times before it wears out. Sometimes, no one cares about this high number, but if your application is doing some data logging every second, and you have not taken this number into account, then you might get an ugly surprise after running your gadget for a couple of days straight.

A strategy of wear levelling counteracts this data corruption by keeping track of what portions of what sectors have been written to, and trying to space out the actual memory areas written to in order to maximize the service life of the Flash.

Usually, you (the product developer) don't have to care about wear levelling. Any off-the-shelf file system for a Flash media will handle wear-levelling quite well. It is when you are writing your own file system, or working in a system that does not use a file system that you have to start being careful.

A Very Simple Example

Just to give you an idea of where you might want to use it:

I am working on a very basic application that uses only about 20 binary files stored in flash memory. In order to cut royalty costs, our client is not paying for a file system to be included in our code, so we are referencing files by sticking them directly into various sectors and using our own custom-made sector headers.

In one of the smaller sectors, we are storing a small structure that contains parameter information about the device's settings and state. The structure is about 200 bytes long, and the sector is 8k in length.

Now, if we were not to take into account wear levelling, I would just store this structure directly after the sector header, and write directly to it every time. The two main problems with this are:

1. Wear levelling, as said before. If I do this, in a few months of normal use, I will have hosed an entire 8k sector because I was always rewriting to the first 208 bytes (remember...we erase the entire sector, so we have to rewrite the header, too). Also, there this method is really horrible,
2. Efficiency-wise. Only the very bottom of this sector is being used for data storage. Surely there is a better way. I will describe, in abstract pseudocode, the way that we used:

The structure:

typedef struct {
     unsigned short writeflags;
     MyBunchOfData data;
} StoredData;

The storage code:

writeMyData( MyBunchOfData *stuffToWrite ) {
     StoredData whatIWillStore;
     FlashHeader header;
     unsigned short i=0, flagArea, flashOffset;

     /* Since Flash erase writes 1s in the sector, we need
     to write zeros instead to show that we have written to
     this area */
     whatIWillStore.writeflags = 0;

     do {
      /*look for the offset from base that we haven't written to yet*/
          flashOffset = i * sizeof( StoredData) + sizeof(FlashHeader);
          readDataFromFlash( &flagArea, 
               Sector_Address + flashOffset, sizeof(flagArea) );
          if( flagArea == 0xFF) break;  //found a good spot to write
          i++;
     } while( flashOffset + sizeof( StoredData) < SECTOR_SIZE );

     if( flagArea != 0xFF ) {
          /*we scanned the whole sector and didn't find 
          space to write, so we must erase the sector and 
          start over from the beginning*/

          eraseSector(Sector_Address);
          header = GoodFlashHeader;
          writeDataToFlash(Sector_Address, &header, sizeof(header));
          writeDataToFlash(Sector_Address + sizeof(header),
               &whatIWillStore, sizeof(whatIWillStore) );
     } else {
          /*There was still unwritten space left in our 
          sector, so write the data to that area*/
          writeDataToFlash( Sector_Address + flashOffset,
               &whatIWillStore, sizeof(whatIWillStore) );
     }
}

Writing a read function is left as an exercise to the reader. You may have noted that you are taking a bit of a speed hit when you use this method, since it's not a simple read/write anymore, but a linear search through the flash, plus the bonus delay of a flash erase every so often. This is one of the reasons it's nice to leave the wear-levelling to a prepackaged filesystem that uses better algorithms.