Finding oldest entry in a circular buffer, taking integer overflow into account

Question

I'd like to store a series of log entries in a circular buffer in a Flash memory device.

The flash device has no onboard wear levelling, so I need to handle it in my logging code. A circular buffer would do this as part of the implementation, but I'm having trouble with an integer overflow issue.

What I intend to do is partition the flash area into areas like this:

char index;
char checksum;
char logdata[512-(sizeof(char)*2))];

Index = 0xFF means "erased". So the ID can range from 0x00 to 0xFE (zero to 254). That means the increment rule is:

id = (last_id + 1) % 255

When the flash starts out, it looks like this (showing IDs only):

FF FF FF FF FF

We pick the first empty block (index zero) and write in our first log entry:

00 FF FF FF FF

This continues until none of the entries are erased:

00 01 02 03 04

When we pick the lowest numbered block, erase it and overwrite with new data:

05 01 02 03 04

But when the 8-bit ID overflows, bad things happen:

FA FB FC FD FE
00 FB FC FD FE  (OK)
01 FB FC FD FE  (Not OK - should have overwritten "FB"!)
02 FB FC FD FE  (Stuck writing the first block over and over)

Which means the first block is now being used for every single write, and we're back in the "uneven writes" scenario I want to avoid. What I want to do is find the oldest block, which in this case is "FB".

Here's the code I have at the moment (in Python):

buf = [0xFF]*5

for i in range(260):
    note = ""

    slot = None

    # Find first erased slot
    for x in range(len(buf)):
        if buf[x] == 0xFF:
            slot = x
            break

    if slot is None:
        # No erased slots, find lowest numbered slot
        n = 0xFF
        for x in range(len(buf)):
            if buf[x] < n:
                n = buf[x]
                slot = x

    # Debug output
    print ''.join(["%02X " % x for x in buf])

    # Write new block
    buf[slot] = i % 255

How can I handle the integer overflow case correctly?

Answer 1

I see two possible ways around this.

The first keeps the same capacity for your queue but requires that the capacity must be less than 255.

The idea is to write exactly as you are now but, rather than looking for the lowest number, you first look for the discontinuity in the sequence, the point where the difference from one cell to the next is not one. Taking your initial situation:

FA FB FC FD FE
00 FB FC FD FE  (discontinuous at fe->fa, use fa)
00 01 FC FD FE  (discontinuous at 00->fb, use fb)
00 01 02 FD FE  (discontinuous at 01->fc, use fc)

The reason why it needs to be less that 255 is that, once it's that big, there is no discontinuity, because the numbers will wrap around exactly once each cycle.

Another way is to simply use the special marker ff to indicate the next free slot no matter what.

The way this works is that, whenever you write a record to an entry, you also write the next entry but with an ff marker.

Then, to find the next entry to populate, you simply look for the first ff. In the startup phase, there will be multiple ff markers and you just choose the first but once they're exhausted, each write will give you another one:

ff ff ff ff ff ff
00 ff ff ff ff ff
00 01 ff ff ff ff
00 01 02 ff ff ff
00 01 02 03 ff ff
00 01 02 03 04 ff
ff 01 02 03 04 05
06 ff 02 03 04 05

This reduces your circular buffer capacity by one and results in twice as many reads as the original scheme so I'd prefer the first scheme above for minimal writes.

However, if you want larger buffers (greater than 254 elements), this is one way to achieve it.

Answer 2

That loop is finding the lowest numbered slot. Well 00, 01, and 02 are all less than FB. So that is why the first slot is getting re-used all the time after the first roll over.

You need a better design. Maybe keep a circular buffer index that always refers to the next available slot.