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?

Page

Are you working directly on flash or are you using a file system on flash? – Lichter

No file system. Writing to flash directly. – Page

Answer 1

See a related question Circular buffer in Flash.

Dispirit

Answer 2

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.

Despond

Answer 3

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.

Osculate

It's not exactly wear levelling. He needs to focus on writing as few times as possible. – Pytlik

I'm pretty sure the flash memory controller does not provide wear leveling. I'm using AT45DB642D. – Page

@mjh2007: You're right, that controller doesn't seem to have any special management in its specification manual. – Osculate

Answer 4

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

Pytlik

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.

Lichter

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.

Sophistication