search

tweedegolf / sequential-storage

A crate for storing data in flash memory with minimal need for erasing pages
Apache License 2.0
87 stars 8 forks source link

feat: add some initial cargo-fuzz test for queues #13

Closed lulf closed 7 months ago

lulf commented 7 months ago

I played with using cargo-fuzz for testing the queue behavior. I wanted to reuse the mock flash for that, but that would require gating it behind some hidden feature, not sure if you have a preferred way.

diondokter commented 7 months ago

Hmmm, cool! Dario's suggestions are good.

Also, seems like the fuzz target folder, corpus and artifact folder are not gitignored

lulf commented 7 months ago

@diondokter I'm trying to have the fuzzer determine whether or not a push() operation should fail due to out of capacity, and for that I need to calculate the expected overhead of the metadata.

From what I can infer, the per-item overhead is 6 bytes, but aligned to word boundary, and at the start(?) of each page there is a byte controlling which state the page is in?

diondokter commented 7 months ago

From what I can infer, the per-item overhead is 6 bytes, but aligned to word boundary, and at the start(?) of each page there is a byte controlling which state the page is in?

  1. There's two words that control the page state. The first and the last word. So the total space in a page is the page - 2 words
  2. An item must fully fit on one page, they cannot be split over two pages. When an item doesn't fit in the remaining space of a page, the page is closed and the next page is used to write the item into.
  3. The layout of an item is documented here: https://github.com/tweedegolf/sequential-storage/blob/9ffb7b6453cf7d6b19b7baba92e79009c2cacf9f/src/item.rs#L1-L20 There's this helper function too: https://github.com/tweedegolf/sequential-storage/blob/9ffb7b6453cf7d6b19b7baba92e79009c2cacf9f/src/item.rs#L150-L152 Just give it the space left in the page and it'll tell you how much data can still be stored in the page. It's None if no data can be stored anymore.
lulf commented 7 months ago

@diondokter believe it has found one off-by-one bug in next_free_item (but please check it, see https://github.com/tweedegolf/sequential-storage/pull/13/commits/a5217501bf654f06e7303b1ea806e509f703a7b4).

Another fuzz test to add (which I'd like to add in a follow-up PR) is to take an existing 'image' that may be corrupted in random ways and see what happens.

Regarding the distribution, we can do that by using a custom type and implementing the Arbitrary trait. However, I think what's there is pretty good already.

Finally, there is a question of semantics and another potential bug. At the moment a push of an empty item will fail with StorageFull in some cases, and some cases not (depending on what happened before). I'd like to get your view on what the behavior should be if there is space for the aligned header but not the empty item. My thinking is that it should be allowed (could be useful as some kind of external marker?)

diondokter commented 7 months ago

Nice! I'll review later.

As for the 0 length, that is allowed. It didn't use to, so the weird behavior might be from that still. So yeah, I do consider that a bug

lulf commented 7 months ago

@diondokter Just a quick update, fixed a bug in the new find_max_fit() handling 0 length correctly.

diondokter commented 7 months ago

Btw, I just added a simple CI script on master. We could add a small fuzz step that fuzzes for only like 10 seconds.

Not sure how much that would bring us, but at least the fuzzer would run every change, even if it's brief.

For statime we do that (though that still uses the old actions-rs): https://github.com/pendulum-project/statime/blob/main/.github/workflows/rust.yml#L101-L124