Flash中的循环缓冲区
我需要将不同长度的项目存储在闪存芯片的循环队列中。每个项目都有其封装，这样我就可以弄清楚它有多大以及下一个项目从哪里开始。当缓冲区中有足够的项目时，它将换行到开头。
在闪存芯片中存储循环队列的好方法是什么？
我可能想存储数以万计的项目。因此，从开头开始读取到缓冲区末尾并不理想，因为搜索到末尾需要时间。
另外，因为它是循环的，所以我需要能够区分第一项和最后一项。
最后一个问题是，它存储在闪存中，因此擦除每个块既耗时又只能对每个块执行一定的次数。
I need to store items of varying length in a circular queue in a flash chip. Each item will have its encapsulation so I can figure out how big it is and where the next item begins. When there are enough items in the buffer, it will wrap to the beginning.
What is a good way to store a circular queue in a flash chip?
There is a possibility of tens of thousands of items I would like to store. So starting at the beginning and reading to the end of the buffer is not ideal because it will take time to search to the end.
Also, because it is circular, I need to be able to distinguish the first item from the last.
The last problem is that this is stored in flash, so erasing each block is both time consuming and can only be done a set number of times for each block.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
首先，块管理：
在每个块的开头放置一个较小的标头。您需要跟踪“最旧”和“最新”的主要内容是块号，它只是以 k 为模递增。 k 必须大于您的区块总数。理想情况下，使k小于您的最大值（例如0xFFFF），以便您可以轻松判断什么是已擦除块。
启动时，您的代码依次读取每个块的标头，并按 ni+1 = (ni + 1) 模 k。请注意不要被已擦除的块（例如，块号为 0xFFFF）或以某种方式损坏的数据（例如，不完全擦除）所迷惑。
在每个块内
每个块最初都是空的（每个字节都是 0xFF）。每条记录只是一个接一个地写入。如果您有固定大小的记录，那么您可以使用简单的索引来访问它。如果您有可变大小的记录，那么要读取它，您必须从块的开头开始扫描，采用链表样式。
如果您想要可变大小的记录，但避免线性扫描，那么您可以在每个记录上有一个明确定义的标题。例如使用 0 作为记录分隔符，并且 COBS-编码（或COBS/R-编码）每个记录。或者使用您选择的字节作为分隔符，如果该字节出现在每个记录中，则“转义”该字节（类似于 PPP 协议）。
在启动时，一旦知道最新的块，就可以对最新的记录进行线性扫描。或者，如果您有固定大小的记录或记录分隔符，则可以进行二分搜索。
擦除调度
对于某些闪存芯片，擦除一个块可能需要很长的时间，例如 5 秒。考虑将擦除安排为稍微“提前”的后台任务。例如，当当前块已满 x% 时，则开始擦除下一个块。
记录编号
您可能想要对记录进行编号。我过去的做法是将第一条记录的记录号放入每个块的标头中。然后软件必须计算块内每条记录的数量。
校验和或CRC
如果您想检测损坏的数据（例如，由于意外电源故障而导致的不完整写入或擦除），那么您可以向每个记录（也许还包括块头）添加校验和或CRC。请注意，块头 CRC 仅覆盖头本身，而不覆盖记录，因为写入每个新记录时无法重写它。
First, block management:
Put a smaller header at the start of each block. The main thing you need to keep track of the "oldest" and "newest" is a block number, which simply increments modulo k. k must be greater than your total number of blocks. Ideally, make k less than your MAX value (e.g. 0xFFFF) so you can easily tell what is an erased block.
At start-up, your code reads the headers of each block in turn, and locates the first and last blocks in the sequence that is ni+1 = (ni + 1) MODULO k. Take care not to get confused by erased blocks (block number is e.g. 0xFFFF) or data that is somehow corrupted (e.g. incomplete erase).
Within each block
Each block initially starts empty (each byte is 0xFF). Each record is simply written one after the other. If you have fixed-size records, then you can access it with a simple index. If you have variable-size records, then to read it you have to scan from the start of the block, linked-list style.
If you want to have variable-size records, but avoid linear scan, then you could have a well defined header on each record. E.g. use 0 as a record delimiter, and COBS-encode (or COBS/R-encode) each record. Or use a byte of your choice as a delimiter, and 'escape' that byte if it occurs in each record (similar to the PPP protocol).
At start-up, once you know your latest block, you can do a linear scan for the latest record. Or if you have fixed-size records or record delimiters, you could do a binary search.
Erase scheduling
For some Flash memory chips, erasing a block can take significant time--e.g. 5 seconds. Consider scheduling an erase as a background task a bit "ahead of time". E.g. when the current block is x% full, then start erasing the next block.
Record numbering
You may want to number records. The way I've done it in the past is to put, in the header of each block, the record number of the first record. Then the software has to keep count of the numbers of each record within the block.
Checksum or CRC
If you want to detect corrupted data (e.g. incomplete writes or erases due to unexpected power failure), then you can add a checksum or CRC to each record, and perhaps to the block header. Note the block header CRC would only cover the header itself, not the records, since it could not be re-written when each new record is written.
保留一个单独的块，其中包含指向第一个记录的开头和最后一个记录的结尾的指针。您还可以保留更多信息，例如记录总数等。
在最初用完空间之前，添加记录就像将它们写入缓冲区末尾并更新尾指针一样简单。
当您需要回收空间时，请删除足够的记录，以便适合当前的记录。删除记录时更新头指针。
您需要跟踪已释放了多少额外空间。如果保留指向最后一条记录末尾的指针，则下次需要添加记录时，可以将其与指向第一条记录的指针进行比较，以确定是否需要删除更多记录。
另外，如果这是 NAND，您或闪存控制器将需要进行解块和磨损均衡，但这都应该位于比为循环缓冲区分配空间更低的层。
Keep a separate block that contains a pointer to the start of the first record and the end of the last record. You can also keep more information like the total number of records, etc.
Until you initially run out of space, adding records is as simple as writing them to the end of the buffer and updating the tail pointer.
As you need to reclaim space, delete enough records so that you can fit your current record. Update the head pointer as you delete records.
You'll need to keep track of how much extra space has been freed. If you keep a pointer to end of the last record, the next time you need to add a record, you can compare that with the pointer to the first record to determine if you need to delete any more records.
Also, if this is NAND, you or the flash controller will need to do deblocking and wear-leveling, but that should all be at a lower layer than allocating space for the circular buffer.
我想我现在明白了。看来您最大的问题是，填满可用的录音空间后，接下来会发生什么？新数据应该覆盖最旧的数据，我相信这就是循环缓冲区的意思。但由于数据的长度不固定，您可能会覆盖多个记录。
我假设长度的可变性足够高，以至于无法将所有内容填充到固定长度。
您的写入段需要跟踪代表下一个要写入的记录的开头的地址。如果您提前知道要写入的块的大小，则可以判断是否会到达逻辑缓冲区的末尾并从“0”开始。我不会将一张唱片分成一些在结尾，一些在开头。
一个单独的寄存器可以跟踪开始；这是尚未被覆盖的最旧的数据。如果您要读出数据，这就是您要开始的地方。
然后，数据写入器将检查，给定写入起始地址和即将提交的数据长度，是否应该碰撞读取寄存器，读取寄存器将检查第一个块并查看长度，然后前进到下一个记录，直到有足够的空间来写入任何数据。写入数据的末尾和最旧数据的开头之间可能存在垃圾数据的间隙。但这样，您可以只写入一两个地址作为开销，而不需要重新排列块。
至少，我可能会这么做。华泰
I think I get it now. It seems like your largest issue will be, having filled the available space for recording, what happens next? The new data should overwrite the oldest data, which is I believe what you mean by a circular buffer. But since the data is not fixed length you may overwrite more than one record.
I'm assuming that the amount of variability in length is high enough that padding everything out to a fixed length isn't an option.
Your write segment needs to keep track of the address that represents the start of the next record to write. If you know the size of a block to write ahead of time, you can tell if you are going to end up at the end of the logical buffer and start over at '0'. I wouldn't split a record up with some at the end and some at the beginning.
A separate register can track the beginning; this is the oldest data that hasn't been overwritten yet. If you went to read out the data this is where you would start.
The data writer then would check, given the write-start address and the length of data its about to commit, if it should bump the read register, which would examine the first block and see the length, and advance to the next record, until there is enough room to write whatever the data is. There will be a gap of junk data that lives between the end of the written data and the start of the oldest data, probably. But this way, you can just be writing an address or two as overhead, and not rearranging blocks.
At least, that's probably what I would do. HTH
闪存中的“循环”可以根据块大小来完成，这意味着您必须声明为此缓冲区分配多少闪存块。
每个特定时间缓冲区的实际大小将在 n-1（n 是块数）和 n 之间。
每个块应以包含序列号或时间戳的标头开头，可用于确定哪个块比另一个块旧。
每个项目都封装有页眉和页脚。默认标头包含您想要的任何内容，但根据此标头，您必须知道项目的大小。默认页脚为 0xFFFFFFFF。该值表示空终止。
在 RAM 中，您必须保存指向最旧块和最新块的指针以及指向最旧项目和最新项目的指针。通电后，您将遍历所有块，找到相关块并加载该成员。
当您想要存储新项目时，请检查最新的块是否包含足够的空间来容纳该项目。如果确实如此，则将该项目保存在前一个项目的末尾，并将前一个页脚更改为指向该项目。如果它没有足够的空间，您需要擦除最旧的块。在擦除此块之前，将最旧的块成员 (RAM) 更改为指向下一个块，并将最旧的项目更改为指向该块中的第一个项目。
然后您可以将新项目保存在该块中，并将最新项目的页脚更改为指向该项目。
我知道这个解释可能听起来很复杂，但过程非常简单，如果你写得正确，你甚至可以使它即使断电也安全（始终记住写入的顺序）。
请注意，缓冲区的循环性并不保存在闪存中，而是闪存中仅包含带有项目的块，您可以根据块头和项目头决定这些项目的顺序
The "circular" in a flash can be done on basis of block size, which means that you must declare how much blocks of the flash you allocate for this buffer.
The actual size of the buffer will be at each particular time between n-1 (n is the number of blocks) and n.
Each block should start with an header that contains sequential number or timestamp that could be used to determine which block is older than the other.
Each Item encapsulated with an header and a footer. the default header contains whatever you want but according to this header you must know the size of the item. The default footer is 0xFFFFFFFF. This value indicates a null termination.
In your RAM you must save a pointer to the oldest block and the latest block and pointer to the oldest item and latest item. On power up you go over all blocks find the relevant blocks and load this members.
When you want to store a new item, you check if the latest block contain enough space for this item. If it does you save the item at the end of the previous item and the change the previous footer to point to this item. If it does not contain enough space you need to erase the oldest block. Before you erase this block change the oldest block members (RAM) to point on the next block and the oldest item to point on the first item in this block.
Then you can save the new item in this block and change the footer of the latest item to point this item.
I know that the explanation may sounds complicated but the process is very simple and if you write it correct you can make it even power fail safe (always keep in you mind the order of the writes).
Pay attention that the circularity of the buffer is not saved in the flash but the flash only contains a blocks with items that you can decide according to the blocks headers and items headers what is the order of these items
我看到三个选项：
选项1：是将所有内容填充到相同的大小，这很简单，存储指向缓冲区头部和尾部的指针，这样你就知道从哪里写入以及从哪里开始读取，使用每个缓冲区的大小对象以获得到下一个的偏移量，这意味着您需要像链接列表一样横穿缓冲区，也就是说，如果您需要第 5000 项，则速度很慢。
选项2：仅存储指向循环缓冲区中实际数据的指针，即这样，当您循环时，您就不必处理尺寸不匹配的问题。如果您将真实数据存储在循环缓冲区中并且不将其填充，您可能会遇到这样的情况：您用 1 个新数据对象过度了解多个项目，我认为这是不行的。
将实际数据存储在闪存中的其他位置，大多数闪存都会内置某种磨损均衡，如果是这样，您无需担心多次覆盖同一位置，IC会找出实际将其存储在芯片上的位置，只需写入下一个可用的空闲空间即可。
这意味着您需要选择循环缓冲区的最大大小，具体操作方式取决于数据的可变性。如果数据的大小变化很大，比如只变化几个字节，那么您应该将其填充并使用选项 1。如果大小变化剧烈且不可预测，请选择可能的最大大小并计算出有多少个对象该大小适合您的闪存，请使用它作为缓冲区中的最大条目数。这意味着你浪费了很多空间。
选项 3：如果对象确实可以是任何大小，那么您应该使用文件系统，按顺序命名文件，并在您完全记住如果您的新条目很大时，您可能需要删除它多个旧条目来适应它。这实际上只是选项 2 的扩展，因为选项 2 在很多方面都是一个简单的文件系统。
I see three options:
option1: is to pad everything out to the same size, this is simple, store a pointer to the head and tail of the buffer so you know where to write and where to start reading from, use the size of each object to get an offset to the next, this means you need to transverse the buffer as you would a linked list, aka its slow if you need item 5000.
option2: is to store only pointers to the real data in the circular buffer, that way when you loop around you don't have to deal with size mis-matchs. if you store the real data in a circular buffer and don't pad it out you could run into a situations where your over witting multiple items with 1 new data object, i assume this is not ok.
store the actual data elsewhere in flash, most flash will have some sort of wear leveling built in, if so you don't need to worry about overwriting the same location multiple times, the IC will figure out where to actually store it on chip, just write to to the next available free space.
this means you need to pick a maximum size for the circular buffer how you do this depends on the data variability. If the size of the data just change much, say by only a few bytes, then you should just pad it out and use option 1. If the size changes wildly and unpredictably, choose the largest size it could be and figure out how many objects of that size would fit in your flash, use that as the max number of entries in the buffer. This means you waste a bunch of space.
option 3: if the object can really be any size, your at the point where you should just use a file system, name the files in order and loop back when your full keeping in mind if your new entry is large you may have to delete multiple old entries to fit it in. This is really just an extension of option 2 as option2 is in many ways a simple file system.