Circular buffer in flash

Question

I have been facing following problem. I have implemented a datalogger i.e. software running on a MCU which creates periodic snapshots of a system state (values of some quantities of the system). These snapshots are stored in a circular buffer in external flash memory. This circular buffer causes that the oldest snapshots are overwritten by the newest ones which is desired behavior. Another requirement is that the datalogger has to work correctly also in case the MCU is restarted. Due to this fact there needs to be a mechanism how to recognize where in the external flash memory the last snapshot has been stored.

I have decided to fullfill this requirement in following way. The external flash memory is divided into sectors which consist of 512 bytes. So I collect several snapshots into one block and I append so called header at the beginning of this block. At beginning I have decided to use only 8 sectors of the external flash so the header contains block number which goes through values \$1,2,\ldots 9\$. This algoritm works pretty well but only for small sizes of circular buffer. In case I have extended size of the circular buffer into several thousands of blocks (the external flash memory contains \$2^{23}\$ sectors) I have found that the time needed for founding sector for continuing in storing of the snapshots after MCU reset is unacceptably long. So I have been looking for another solution how to find sector for continuing in snapshot storage after MCU reset in quicker manner.

Does anybody have any idea? Thanks for any suggestions.

Answer 1

Simply have a counter in your snapshots (you probably already do), and make them fixed-size (either individually, or by making your 512 B sectors).

Your search for the point that the pointer becomes non-consecutive shouldn't take long at all!

What you're looking for is a binary search (wikipedia and literature certainly have information on this standard search algorithm):

1. Take the counter of the first and the last sector. Compare!
2. if #last > #first, then you're in the special case that your flash has been written exactly full, for an integer amount of times. I.e., your write point is at the very beginning.
3. if #last < #first: Your write pointer is somewhere in the middle between the first and the last. Set oldlast = last, compare #first > (middle of old interval); if that's true, the write pointer is in the lower half of your flash, i.e. [first, middle], else in the upper half, i.e. [middle, oldlast]
4. repeat this search algorithm in the half that you just found out contains the write pointer

The worst case for this search algorithm takes 23 steps to find the right sector. I doubt that's a problem.

Answer 2

I had the exact same issue.

The way I solved it was to reserve the 20 or so first sector to store the position of the last written sector.

To avoid flash wear, it would always write the last written sector on the first 20 on a circular manner, and only do it every 1h or so. In case of hard power down, you would loose 1h of data basically.

With 100'000 flash writing cycle life, it give approx 200 years before the flash wears out.

Another method, is to store the position on the first sector, and then use an EEPROM to buffer this first sector which means you only write it once a day or have a button that you press before removing the flash so that the EEPROM updates it.

Answer 3

There exists lots of questionable solutions to this. What I do:

• Ensure that the first word in each segment is not allowed to contain data 0xFF...FF.
• Pick a MCU where erased flash has the value 0xFF...FF, which means the vast majority of them.
• Divide your flash page into x segments that align evenly with the size of the flash page. Ideally this size should fit in data cache if available, to dodge wait states and access time.
• Write to the log from ls address to ms address. Wrap-around when full, by erasing the whole page, during everything to 0xFF...
• When searching for the last active segment, use a specialized binary search from x/2 over the whole page, in a manner where you look for the occurrence of the first 0xFF...FF.
• If segment x/2 is 0xFF..FF then binary search downwards until finding the first valid data.
• If segment x/2 is valid data, then binary search upwards until finding the first 0xFF...FF.
• The segment before the first 0xFF...FF is the last valid data.
• If there is no 0xFF...FF segment then the page is full and the last segment in the page is the valid one.

This is O(log n) and you don't need to store mysterious counters/headers/overhead to bloat flash usage.