# Circular buffer in flash

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.

• Which flash chip is it? If this flash allows multiple writes (switching bits from 1 to 0) of the same sector without having to erase between writes, you might be able to come up with a clever scheme and store a kind of fixed-location index, updated each time, but without wearing the flash too much. But on some flash (typically MLC flash) it isn't possible. – dim lost faith in SE Feb 27 '19 at 11:50
• How do you solve wrap-around? Do you allocate massive amounts of RAM or do you use 2 flash pages? – Lundin Feb 27 '19 at 12:29
• @Lundin Thank you for your reaction. The wrap-around detection is based on discontinuity in block headers. In case I have 8 blocks the headers go through values 1,2, ... 9. Whenever I find unexpected header value I know that wrap-around occured. – Steve Feb 27 '19 at 12:37

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.

• There are 2^23 sectors (8mio+), don't get how that would take 23 steps. – Damien Feb 27 '19 at 13:03
• by the algorithm I described! You find the half in which the "wraparound" happens, and only look into that half. You repeat that. It takes $\lceil \log_2 N \rceil$ halvings to find a single element in N=2²³ elements, i.e. 23 steps. Binary search is really a standard algorithm, and I couldn't explain it better than the millions of websites out there; it's not that hard! – Marcus Müller Feb 27 '19 at 13:07
• – dim lost faith in SE Feb 27 '19 at 13:07
• @Marcus Muller Thank you for your reaction. Sorry, maybe I have missed something important in your answer but in case I use any search algorithm I need to specify what value I am looking for. But in my opinion I don't know this value. – Steve Feb 27 '19 at 13:10
• You don't search for a value, you search for the point where counter of the sections stops increasing monotonously, but suddenly jumps to a smaller value! – Marcus Müller Feb 27 '19 at 13:12

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.

• Thank you for your reaction. As far as I understand your first suggestion correctly I should define an auxiliary circular buffer of small size and I should store information about last written sector into it. For storing the last written sector I should use a mechanism with header to be able to recognize roll over in the main circular buffer. In the main circular buffer I don't need the mechanism with block headers no longer because I know correct sector based on information from auxiliary buffer. – Steve Feb 27 '19 at 12:30
• Yes, to take care of the rollover you can use simply an incremental value and you will always know the most recent write event.You read the first 20 sector and take the data from the highest increment and you keep incrementing from there. – Damien Feb 27 '19 at 12:45
• If you are going to do this, don't store a number but rather a mapped flag. Ie, each word in the directory maps to one page in the data store. When you write the page, write the corresponding word. If the flash does not have ECC meaning you can overwrite unwrritten bits in a word then it can be a bitmap rather than a word map. But with the binary searches described you probably don't need this. Even a linear search could be fast if you only read a few worda per page. – Chris Stratton Feb 27 '19 at 15:04

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.