4 ms·

I recently coded a linear-probing hash map in C and I highly recommend you to use fuzz tests. These evolve naturally from unit tests: next step table unit tests

I recently coded a linear-probing hash map in C and I highly recommend you to use fuzz tests. These evolve naturally from unit tests: next step table unit tests, next step property test, next step fuzzing, all steps are incremental, hence easy. Having a fuzz test was in-va-lu-ab-le. I caught several bugs right there. The delete function was particularly tricky. I ended up with two fuzz tests as my hash table has a key feature: convergence. Having same contents, it would have exactly same bits in the buffer. In other words, it is independent of the insertion/deletion order. For this, I added another fuzz test. I would add a third one if I realize there is an important invariant I did not fuzz test. That is not much work, but so much useful! https://github.com/gritzko/librdx/blob/master/abc/fuzz/HASH.cpp https://github.com/gritzko/librdx/blob/master/abc/fuzz/HASH.... https://github.com/gritzko/librdx/blob/master/abc/fuzz/HASHd.c https://github.com/gritzko/librdx/blob/master/abc/fuzz/HASHd... P.S. In your case, I recommend clang's libfuzzer with ASAN. https://llvm.org/docs/LibFuzzer.html#fuzzer-usage https://llvm.org/docs/LibFuzzer.html#fuzzer-usage

dwattttt 2y ago
fuzz testing vs HN-popular-post testing, go!
eqvinox 2y ago
Here's another example of unit tests for hash tables (and RB-trees and skiplists and…) https://github.com/FRRouting/frr/blob/master/tests/lib/test_typelist.h https://github.com/FRRouting/frr/blob/master/tests/lib/test_... (this file is #include'd from another, with some #define set up:) https://github.com/FRRouting/frr/blob/master/tests/lib/test_typelist.c https://github.com/FRRouting/frr/blob/master/tests/lib/test_... The "tribe" of C developers with distaste for the preprocessor will absolutely hate how this is written. But it works and caught real issues. It doesn't use an external fuzzing tool but rather a deterministic PRNG (see prng_* calls) to get a good mix of call combinations. Coverage analysis was done to make sure it reaches everywhere. (disclaimer: I wrote this. And it did catch bugs. Also it really should have a lot of comments.)
- cb321 2y ago
  If you are in a tribe not hating on pp-macros, you might find this approach for testing/debugging data structures (or even the surrounding pp-based "CTL"-like C templating idea or abstract ways of dealing with the BST zoo) interesting: https://github.com/c-blake/bst/blob/main/test/bst-interact.c Essentially, you just write a very simple (some might say trivial) interactive command-shell that can include an auto-checking upon edit of (in that case tree) invariants keyed-off an environment variable. The only missing piece is some little tool to generate random inserts/deletes/etc. If the micro-shell has a pretty printer then it is easy to "replay" any failed series of edits with some "p" commands before & after invariant failures.
  - eqvinox 2y ago
    This is incredibly funny to me, because that's (almost) exactly how some of our other tests work :D (Almost: we have a full-featured command shell and just use that for testing) Shell bindings: https://github.com/FRRouting/frr/blob/master/tests/ospf6d/test_lsdb.c https://github.com/FRRouting/frr/blob/master/tests/ospf6d/te... Input: https://github.com/FRRouting/frr/blob/master/tests/ospf6d/test_lsdb.in https://github.com/FRRouting/frr/blob/master/tests/ospf6d/te... Expected output: https://github.com/FRRouting/frr/blob/master/tests/ospf6d/test_lsdb.refout https://github.com/FRRouting/frr/blob/master/tests/ospf6d/te... Absolutely agree this is a great option to have for some kinds of tests.
    - cb321 2y ago
      One reason to have a razor thin custom command shell (perhaps obeying similar conventions across data structures..) is that the parsing for such can be so fast/consistent that you can also use it for benchmarking/perf regression testing with a workload generator. You might also find & record "anomalous" workloads that way or write a little "translator" (some might say "compiler") from a log to such a workload or etc. I have done this for data structures even as fast as integer-keyed hash tables (though in that hyper-fast case you might need to try to measure & subtract off parser-loop/IO dispatch overhead and/or need statistical testing for "actually even different at all", perhaps along the lines of https://github.com/c-blake/bu/blob/main/doc/tim.md https://github.com/c-blake/bu/blob/main/doc/tim.md).

dwattttt 2y ago

fuzz testing vs HN-popular-post testing, go!

eqvinox 2y ago

Here's another example of unit tests for hash tables (and RB-trees and skiplists and…) https://github.com/FRRouting/frr/blob/master/tests/lib/test_typelist.h https://github.com/FRRouting/frr/blob/master/tests/lib/test_... (this file is #include'd from another, with some #define set up:) https://github.com/FRRouting/frr/blob/master/tests/lib/test_typelist.c https://github.com/FRRouting/frr/blob/master/tests/lib/test_... The "tribe" of C developers with distaste for the preprocessor will absolutely hate how this is written. But it works and caught real issues. It doesn't use an external fuzzing tool but rather a deterministic PRNG (see prng_* calls) to get a good mix of call combinations. Coverage analysis was done to make sure it reaches everywhere. (disclaimer: I wrote this. And it did catch bugs. Also it really should have a lot of comments.)

cb321 2y ago
If you are in a tribe not hating on pp-macros, you might find this approach for testing/debugging data structures (or even the surrounding pp-based "CTL"-like C templating idea or abstract ways of dealing with the BST zoo) interesting: https://github.com/c-blake/bst/blob/main/test/bst-interact.c Essentially, you just write a very simple (some might say trivial) interactive command-shell that can include an auto-checking upon edit of (in that case tree) invariants keyed-off an environment variable. The only missing piece is some little tool to generate random inserts/deletes/etc. If the micro-shell has a pretty printer then it is easy to "replay" any failed series of edits with some "p" commands before & after invariant failures.
- eqvinox 2y ago
  This is incredibly funny to me, because that's (almost) exactly how some of our other tests work :D (Almost: we have a full-featured command shell and just use that for testing) Shell bindings: https://github.com/FRRouting/frr/blob/master/tests/ospf6d/test_lsdb.c https://github.com/FRRouting/frr/blob/master/tests/ospf6d/te... Input: https://github.com/FRRouting/frr/blob/master/tests/ospf6d/test_lsdb.in https://github.com/FRRouting/frr/blob/master/tests/ospf6d/te... Expected output: https://github.com/FRRouting/frr/blob/master/tests/ospf6d/test_lsdb.refout https://github.com/FRRouting/frr/blob/master/tests/ospf6d/te... Absolutely agree this is a great option to have for some kinds of tests.
  - cb321 2y ago
    One reason to have a razor thin custom command shell (perhaps obeying similar conventions across data structures..) is that the parsing for such can be so fast/consistent that you can also use it for benchmarking/perf regression testing with a workload generator. You might also find & record "anomalous" workloads that way or write a little "translator" (some might say "compiler") from a log to such a workload or etc. I have done this for data structures even as fast as integer-keyed hash tables (though in that hyper-fast case you might need to try to measure & subtract off parser-loop/IO dispatch overhead and/or need statistical testing for "actually even different at all", perhaps along the lines of https://github.com/c-blake/bu/blob/main/doc/tim.md https://github.com/c-blake/bu/blob/main/doc/tim.md).