Alarm history stack or queue?

Question

I'm trying to develop an alarm history structure to be stored in non-volatile flash memory. Flash memory has a limited number of write cycles so I need a way to add records to the structure without rewriting all of the flash pages in the structure each time or writing out updated pointers to the head/tail of the queue.

Additionally once the available flash memory space has been used I want to begin overwriting records previously stored in flash starting with the first record added first-in-first-out. This makes me think a circular buffer would work best for adding items. However when viewing records I want the structure to work like a stack. E.g. The records would be displayed in reverse chronological order last-in-first-out.

Structure size, head, tail, indexes can not be stored unless they are stored in the record itself since if they were written out each time to a fixed location it would exceed the maximum write cycles on the page where they were stored.

So should I use a stack, a queue, or some hybrid structure? How should I store the head, tail, size information in flash so that it can be re-initialized after power-up?

Answer 1

Lookup ring-buffer

Assuming you can work out which is the last entry (from a time stamp etc so don't need to write a marker) this also has the best wear leveling performance.

Answer 2

Edit: Doesn't apply to the OP's flash controller: You shouldn't have to worry about wear leveling in your code. The flash memory controller should handle this behind the scenes.

However, if you still want to go ahead an do this, just use a regular circular buffer, and keep pointers to the head and tail of the stack.

You could also consider using a Least Recently Used cache to manage where on flash to store data.

Answer 3

See a related question Circular buffer in Flash.

Answer 4

You definitely want a ring buffer. But you're right, the meta information is a bit...interesting.

Answer 5

Map your entries on several sections. When the sections are full, overwrite starting with the first section. Add a sequence-number (nbr sequence numbers > 2 * entries), so on reboot you know what the first entry is.

Answer 6

You could do a version of the ring-buffer, where the first element stored in the page is number of times that page has been written. This allows you to determine where you should write next by finding the first page where the number is lower than the previous page. If they're all the same, you start from the beginning with the next number.