在循环缓冲区中查找最旧的条目，考虑整数溢出(Finding oldest entry in a circular buffer, taking integer overflow into accoun

在循环缓冲区中查找最旧的条目，考虑整数溢出(Finding oldest entry in a circular buffer, taking integer overflow into account)

我想将一系列日志条目存储在闪存设备的循环缓冲区中。

闪存设备没有板载磨损均衡，所以我需要在我的日志代码中处理它。 循环缓冲区将作为实现的一部分执行此操作，但我遇到整数溢出问题。

我打算做的是将flash区域划分为以下区域：

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

Index = 0xFF表示“已擦除”。 因此ID的范围可以从0x00到0xFE（零到254）。 这意味着增量规则是：

id = (last_id + 1) % 255

当闪存开始时，它看起来像这样（仅显示ID）：

FF FF FF FF FF

我们选择第一个空块（索引零）并在第一个日志条目中写入：

00 FF FF FF FF

这将继续，直到没有条目被删除：

00 01 02 03 04

当我们选择编号最小的块时，擦除它并用新数据覆盖：

05 01 02 03 04

但是当8位ID溢出时，会发生不好的事情：

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)

这意味着第一个块现在用于每一次写入，我们回到了我想避免的“不均匀写入”场景中。 我想要做的是找到最旧的块，在这种情况下是“FB”。

这是我目前的代码（在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

如何正确处理整数溢出情况？

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?

最满意答案

我看到了两种可能的方法。

第一个保留队列的相同容量，但要求容量必须小于255。

我们的想法是按照你现在的方式编写，但是，不是寻找最低的数字，而是先查找序列中的不连续性 ，即从一个单元格到下一个单元格的差异不是一个。 初步了解情况：

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)

它需要小于255的原因是，一旦它变大，就没有不连续性，因为数字将在每个循环中恰好缠绕一次。

另一种方法是简单地使用特殊标记ff来指示下一个空闲时隙，无论如何。

这种方式的工作方式是，无论何时向条目写入记录，您还可以使用ff标记写下一个条目。

然后，要查找要填充的下一个条目，您只需查找第一个ff 。 在启动阶段，会有多个ff标记，你只需选择第一个，但一旦它们耗尽，每次写入都会给你另一个：

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

这会将循环缓冲区容量减少一个，导致读取次数是原始方案的两倍，因此我更倾向于使用上面的第一个方案进行最小写入。

但是，如果您需要更大的缓冲区（大于254个元素），这是实现它的一种方法。

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.