Queue feedback

[JcBernack]

I reviewed the queue implementation and I think it's great. Thanks for sharing this.

A few things I noticed and some suggestions, if I misread anything please correct me:

• A method to "initialize" the queue would be nice. Currently you expect the user to erase the pages before using the queue.
  • This could also be used to add a tiny bit of metadata like a version tag and something like number of pages in the queue. This could help whenever there is a breaking change that we don't accidentally use a newer version of the queue on data belonging to an older version. Or if the pages used for the queue are ever changed (start page or number of pages) that the queue can detect that and automatically re-initialize.
• I think you could get rid of the end marker by using different values for the start marker:
  • erase value FF: page unused/empty/open
  • some magic value 42: page partially written
  • zero 00: page closed
• Adding a CRC to every element would be nice to detect data corruption (or a failing flash).
• When removing an element you could keep the length and only remove the data. That way finding the next element would be faster. Currently, this would make it impossible to know if the data was removed or was all zeros to begin with, but the CRC field could be used for that. If CRC field is zero: Skip over removed element.

Especially the initialization and preventing issues when upgrading a system with existing data in the flash storage are important features to me. What do you think?

Edit: I missed that only the queue is working on a MultiwriteNorFlash while the rest is working with NorFlash. My suggestion regarding the marker would not work with NorFlash.

[diondokter]

Hi, thanks for the feedback!

Currently the initialization is just erasing the parts of the flash that the queue will use. Probably good to document somewhere.

add a tiny bit of metadata like a version tag

This is not a bad idea. The page marker doesn't have to be 0, it could be a version number as well.

I think you could get rid of the end marker by using different values for the start marker:

• erase value FF: page unused/empty/open
• some magic value 42: page partially written
• zero 00: page closed

If I hadn't made the map before, then I probably would've gone with something like that. But now I'd rather use the existing proven code. And it'd only save one write word, which to me is negligible. Or do you have a weird flash chip where it's significant?

Adding a CRC to every element would be nice to detect data corruption (or a failing flash).

That'd be kinda nice to have, but adds complexity. Ideally you'd want to let the users provide an implementation for the CRC so they can optionally use e.g. a hardware CRC. But maybe a simpler fletcher16 would suffice. IDK

The leaving the lengths behind would be a nice optimization, but indeed only when a checksum is present. Of course you can currently include a CRC in your own data which would allow you to detect some corruption, but only if it happens to be in the data itself.

So:

1. I think initialization isn't an issue. Just erase the flash, you already need all data to use the queue that you also need for erasing.
2. Version tags would be nice to have. I personally don't need it because my queue is used as a cache that gets wiped at every boot (including after a firmware update). But I'm open for a PR for that.
3. The CRC I'm less sure about. If we pick a 16-bit one, we could combine it with the length tag and make it a 4-byte tag including both. On many flash chips this wouldn't even cost any more space. I'm open for a PR that adds it.
4. I'd like to keep the pages working as they are now with a start and an end marker.

I currently don't have the time nor the need for these features, so I'm leaving them for you or anyone to pick up :)

[JcBernack]

If I hadn't made the map before, then I probably would've gone with something like that. But now I'd rather use the existing proven code. And it'd only save one write word, which to me is negligible. Or do you have a weird flash chip where it's significant?

No, not at all. It was less about saving space, but more about reducing complexity. When I wrote that I had not seen that the Map and common code is working on NorFlash which cannot be overwritten to zeros.

1. I think initialization isn't an issue. Just erase the flash, you already need all data to use the queue that you also need for erasing.

I agree, this was mainly in case including metadata (version, etc.) would require some special handling in addition to erasing all pages. I like the idea of reusing the marker value as a version tag.

2. Version tags would be nice to have. I personally don't need it because my queue is used as a cache that gets wiped at every boot (including after a firmware update). But I'm open for a PR for that.

Our current C implementation uses something like your queue as a buffer for sensor data. It should be empty whenever an OTA update is installed, but if it is not I would like it to not explode in case the sensor-data struct changed. On init our store just erases everything if it detects a version mismatch.

3. The CRC I'm less sure about. If we pick a 16-bit one, we could combine it with the length tag and make it a 4-byte tag including both. On many flash chips this wouldn't even cost any more space. I'm open for a PR that adds it.

Good point! We use STM32 chips, their write-word size is 64 bit, so it would not have any additional size overhead. CRC algorithms are so simple and fast, I would just go the easy route and use a software implementation.

4. I'd like to keep the pages working as they are now with a start and an end marker.

Agree.

I currently don't have the time nor the need for these features, so I'm leaving them for you or anyone to pick up :)

If we decide to "rewrite it in Rust" I will :wink: