zstd block codec (CRC32C, varint tagged records), segment files with sealed footers and block index, crash-atomic MANIFEST, LogStore (lock, recovery, rolls, orphaning, heal with backoff), the evidence view, and the legacy unqlite store kept for import. Property tests under injected faults and crashes, a differential test against the old store, and fuzz targets for every decoder. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
301 lines
12 KiB
C++
301 lines
12 KiB
C++
// Event-store codec: unit checks plus seeded properties. A failure prints the
|
|
// seed; re-run with STRAWBERRY_PROPERTY_SEED=<seed> to reproduce.
|
|
//
|
|
// Properties:
|
|
// C1 varint/zigzag round-trip for every u64/i64; decoders reject truncation
|
|
// C2 crc32c(hardware) == crc32c(portable) for every input and split point
|
|
// C3 fields/records round-trip; unknown tags and types are skippable
|
|
// C4 blocks round-trip (raw, zstd, zstd+dictionary)
|
|
// C5 any single-bit flip in a block is detected (never silently decoded)
|
|
// C6 any truncation of a block is reported as truncated
|
|
// C7 decoders never throw or crash on random bytes
|
|
|
|
#include "strawberry/store/codec.hpp"
|
|
|
|
#include <cstdint>
|
|
#include <cstdlib>
|
|
#include <iostream>
|
|
#include <random>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
using namespace strawberry::store;
|
|
|
|
namespace {
|
|
|
|
uint64_t seed_from_env() {
|
|
if (const char* text = std::getenv("STRAWBERRY_PROPERTY_SEED")) {
|
|
return std::strtoull(text, nullptr, 10);
|
|
}
|
|
return std::random_device{}();
|
|
}
|
|
|
|
const uint64_t kSeed = seed_from_env();
|
|
|
|
#define PROPERTY(cond) \
|
|
do { \
|
|
if (!(cond)) { \
|
|
std::cerr << "PROPERTY FAILED: " #cond " (seed " << kSeed << ", " << __FILE__ << ":" \
|
|
<< __LINE__ << ")" << std::endl; \
|
|
std::abort(); \
|
|
} \
|
|
} while (0)
|
|
|
|
uint64_t random_u64(std::mt19937_64& rng) {
|
|
// Bias toward small values and boundaries, where varint bugs live.
|
|
switch (rng() % 4) {
|
|
case 0: return rng() % 256;
|
|
case 1: return (uint64_t{1} << (rng() % 64)) - (rng() % 2);
|
|
default: return rng();
|
|
}
|
|
}
|
|
|
|
std::string random_bytes(std::mt19937_64& rng, std::size_t max_len) {
|
|
std::string s(rng() % (max_len + 1), '\0');
|
|
for (auto& c : s) c = static_cast<char>(rng());
|
|
return s;
|
|
}
|
|
|
|
/// Text that looks like telemetry (paths, argv), so zstd actually compresses.
|
|
std::string telemetry_like(std::mt19937_64& rng, std::size_t records) {
|
|
static const std::vector<std::string> words = {"/usr/bin/", "/home/user/", "python3", "bash", "-c",
|
|
"curl", "https://example.org/", "sha256=", "ssh", "--flag"};
|
|
std::string raw;
|
|
FieldWriter w;
|
|
for (std::size_t i = 0; i < records; ++i) {
|
|
w.clear();
|
|
w.u64(1, 1700000000000ull + rng() % 100000);
|
|
w.u64(2, rng() % 65536);
|
|
std::string path;
|
|
for (int k = 0; k < 4; ++k) path += words[rng() % words.size()];
|
|
w.bytes(3, path);
|
|
append_record(raw, RecordType::process_exec, w.data());
|
|
}
|
|
return raw;
|
|
}
|
|
|
|
struct Fixture {
|
|
uint32_t tag;
|
|
WireType type;
|
|
uint64_t value;
|
|
std::string bytes;
|
|
};
|
|
|
|
void test_known_vectors() {
|
|
// RFC 3720 / iSCSI check value.
|
|
PROPERTY(crc32c_portable("123456789", 9) == 0xE3069283u);
|
|
PROPERTY(crc32c("123456789", 9) == 0xE3069283u);
|
|
PROPERTY(crc32c("", 0) == 0);
|
|
std::string v;
|
|
put_varint(v, 300);
|
|
PROPERTY(v == std::string("\xAC\x02", 2));
|
|
PROPERTY(zigzag_encode(-1) == 1 && zigzag_encode(1) == 2 && zigzag_encode(INT64_MIN) == UINT64_MAX);
|
|
std::cout << "crc32c implementation: " << crc32c_impl() << std::endl;
|
|
}
|
|
|
|
void property_varint(std::mt19937_64& rng) { // C1
|
|
for (int i = 0; i < 20000; ++i) {
|
|
const uint64_t x = random_u64(rng);
|
|
std::string enc;
|
|
put_varint(enc, x);
|
|
PROPERTY(enc.size() <= kMaxVarintBytes);
|
|
std::string_view in = enc;
|
|
uint64_t got = 0;
|
|
PROPERTY(get_varint(in, got) && got == x && in.empty());
|
|
for (std::size_t cut = 0; cut < enc.size(); ++cut) {
|
|
std::string_view t(enc.data(), cut);
|
|
const std::string_view before = t;
|
|
PROPERTY(!get_varint(t, got) && t == before);
|
|
}
|
|
const auto s = static_cast<int64_t>(x);
|
|
PROPERTY(zigzag_decode(zigzag_encode(s)) == s);
|
|
}
|
|
// 11 continuation bytes, and a 10th byte carrying bits past 64.
|
|
std::string_view overlong("\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x01", 11);
|
|
uint64_t got = 0;
|
|
PROPERTY(!get_varint(overlong, got));
|
|
std::string_view overflow("\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x02", 10);
|
|
PROPERTY(!get_varint(overflow, got));
|
|
std::string_view max("\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x01", 10);
|
|
PROPERTY(get_varint(max, got) && got == UINT64_MAX);
|
|
}
|
|
|
|
void property_crc(std::mt19937_64& rng) { // C2
|
|
for (int i = 0; i < 3000; ++i) {
|
|
const std::string s = random_bytes(rng, 4096);
|
|
const uint32_t whole = crc32c(s.data(), s.size());
|
|
PROPERTY(whole == crc32c_portable(s.data(), s.size()));
|
|
const std::size_t split = s.empty() ? 0 : rng() % s.size();
|
|
PROPERTY(crc32c(s.data() + split, s.size() - split, crc32c(s.data(), split)) == whole);
|
|
// unaligned start
|
|
if (s.size() > 3) {
|
|
PROPERTY(crc32c(s.data() + 3, s.size() - 3) == crc32c_portable(s.data() + 3, s.size() - 3));
|
|
}
|
|
}
|
|
}
|
|
|
|
void property_fields_records(std::mt19937_64& rng) { // C3
|
|
for (int i = 0; i < 3000; ++i) {
|
|
std::vector<Fixture> fields(rng() % 12);
|
|
FieldWriter w;
|
|
for (auto& f : fields) {
|
|
f.tag = 1 + static_cast<uint32_t>(rng() % 3 == 0 ? rng() % kMaxFieldTag : rng() % 32);
|
|
switch (rng() % 4) {
|
|
case 0: f.type = WireType::varint; f.value = random_u64(rng); w.u64(f.tag, f.value); break;
|
|
case 1: f.type = WireType::fixed32; f.value = static_cast<uint32_t>(rng()); w.fixed32(f.tag, static_cast<uint32_t>(f.value)); break;
|
|
case 2: f.type = WireType::fixed64; f.value = rng(); w.fixed64(f.tag, f.value); break;
|
|
default: f.type = WireType::bytes; f.bytes = random_bytes(rng, 300); w.bytes(f.tag, f.bytes); break;
|
|
}
|
|
}
|
|
FieldReader r(w.data());
|
|
Field got;
|
|
std::size_t n = 0;
|
|
while (r.next(got)) {
|
|
PROPERTY(n < fields.size());
|
|
const auto& want = fields[n++];
|
|
PROPERTY(got.tag == want.tag && got.type == want.type);
|
|
if (want.type == WireType::bytes) {
|
|
PROPERTY(got.bytes == want.bytes);
|
|
} else {
|
|
PROPERTY(got.value == want.value);
|
|
}
|
|
}
|
|
PROPERTY(!r.error() && n == fields.size());
|
|
|
|
// Records: a reader that only knows some types still walks them all.
|
|
std::string block;
|
|
const uint32_t unknown_type = 1000 + static_cast<uint32_t>(rng() % 1000);
|
|
append_record(block, RecordType::process_exec, w.data());
|
|
append_record(block, static_cast<RecordType>(unknown_type), "future");
|
|
append_record(block, RecordType::label, "");
|
|
RecordReader rr(block);
|
|
RecordView rec;
|
|
PROPERTY(rr.next(rec) && rec.type == 16 && rec.payload == w.data());
|
|
PROPERTY(rr.next(rec) && rec.type == unknown_type && rec.payload == "future");
|
|
PROPERTY(rr.next(rec) && rec.type == 36 && rec.payload.empty());
|
|
PROPERTY(!rr.next(rec) && !rr.error());
|
|
|
|
// A truncated record stream stops with an error after the intact prefix.
|
|
const std::size_t cut = 1 + rng() % (block.size() - 1);
|
|
RecordReader torn(std::string_view(block).substr(0, block.size() - cut));
|
|
std::size_t ok = 0;
|
|
while (torn.next(rec)) ++ok;
|
|
// (a cut on a record boundary is indistinguishable from a shorter
|
|
// stream; the block CRC, not the record framing, catches that)
|
|
PROPERTY(ok < 3);
|
|
}
|
|
}
|
|
|
|
const ZstdDictionary* g_dict = nullptr;
|
|
const ZstdDictionary* lookup(uint32_t id, const void*) noexcept {
|
|
return g_dict != nullptr && g_dict->id() == id ? g_dict : nullptr;
|
|
}
|
|
|
|
void property_blocks(std::mt19937_64& rng) { // C4, C5, C6
|
|
std::vector<std::string> samples;
|
|
for (int i = 0; i < 200; ++i) samples.push_back(telemetry_like(rng, 4));
|
|
const auto dict = ZstdDictionary::train(samples, 4096, 3);
|
|
PROPERTY(dict != nullptr && dict->id() != 0);
|
|
g_dict = dict.get();
|
|
const auto reloaded = ZstdDictionary::load(dict->bytes(), 3);
|
|
PROPERTY(reloaded != nullptr && reloaded->id() == dict->id());
|
|
PROPERTY(ZstdDictionary::load("not a dictionary", 3) == nullptr);
|
|
|
|
for (int i = 0; i < 400; ++i) {
|
|
const int mode = i % 3; // 0 random bytes (raw), 1 zstd, 2 zstd+dict
|
|
const std::string raw = mode == 0 ? random_bytes(rng, 2000) : telemetry_like(rng, 1 + rng() % 200);
|
|
std::string enc;
|
|
const BlockInfo info = encode_block(enc, raw, 3, mode == 2 ? dict.get() : nullptr);
|
|
if (mode != 0 && raw.size() > 256) {
|
|
PROPERTY(info.codec == BlockCodec::zstd);
|
|
}
|
|
if (info.codec == BlockCodec::raw) {
|
|
PROPERTY(info.stored_bytes == raw.size());
|
|
}
|
|
// trailing bytes after the block must be left alone
|
|
enc += "TRAILER";
|
|
std::string out;
|
|
std::size_t consumed = 0;
|
|
BlockInfo got;
|
|
PROPERTY(decode_block(enc, out, consumed, lookup, nullptr, &got) == BlockError::ok);
|
|
PROPERTY(out == raw && consumed == enc.size() - 7);
|
|
PROPERTY(got.codec == info.codec && got.dictionary_id == info.dictionary_id);
|
|
if (info.dictionary_id != 0) {
|
|
PROPERTY(decode_block(enc, out, consumed) == BlockError::unknown_dictionary);
|
|
}
|
|
const std::size_t block_size = consumed;
|
|
|
|
// C5: every single-bit flip is caught (sampled positions for big blocks).
|
|
for (int k = 0; k < 24; ++k) {
|
|
std::string bad = enc.substr(0, block_size);
|
|
const std::size_t pos = rng() % bad.size();
|
|
bad[pos] = static_cast<char>(bad[pos] ^ (1 << (rng() % 8)));
|
|
std::string o;
|
|
std::size_t c = 0;
|
|
PROPERTY(decode_block(bad, o, c, lookup, nullptr) != BlockError::ok);
|
|
}
|
|
// C6: every truncation point is reported (never ok).
|
|
for (int k = 0; k < 16; ++k) {
|
|
const std::size_t len = rng() % block_size;
|
|
std::string o;
|
|
std::size_t c = 0;
|
|
const BlockError e = decode_block(std::string_view(enc).substr(0, len), o, c, lookup, nullptr);
|
|
PROPERTY(e == BlockError::truncated);
|
|
}
|
|
}
|
|
|
|
// Size limits.
|
|
bool threw = false;
|
|
try {
|
|
std::string enc;
|
|
encode_block(enc, std::string(kMaxBlockRaw + 1, 'x'), 3);
|
|
} catch (const std::length_error&) {
|
|
threw = true;
|
|
}
|
|
PROPERTY(threw);
|
|
std::string enc;
|
|
encode_block(enc, std::string(kMaxBlockRaw, 'x'), 3);
|
|
std::string out;
|
|
std::size_t consumed = 0;
|
|
PROPERTY(decode_block(enc, out, consumed) == BlockError::ok && out.size() == kMaxBlockRaw);
|
|
g_dict = nullptr;
|
|
}
|
|
|
|
void property_garbage(std::mt19937_64& rng) { // C7
|
|
for (int i = 0; i < 20000; ++i) {
|
|
std::string bytes = random_bytes(rng, 600);
|
|
if (rng() % 2 && bytes.size() >= 4) {
|
|
bytes[0] = 'S'; bytes[1] = 'B'; bytes[2] = 'B'; bytes[3] = 'K';
|
|
}
|
|
std::string out;
|
|
std::size_t consumed = 0;
|
|
(void) decode_block(bytes, out, consumed);
|
|
RecordReader rr(bytes);
|
|
RecordView rec;
|
|
while (rr.next(rec)) {
|
|
FieldReader fr(rec.payload);
|
|
Field f;
|
|
while (fr.next(f)) {
|
|
}
|
|
}
|
|
FieldReader fr(bytes);
|
|
Field f;
|
|
while (fr.next(f)) {
|
|
}
|
|
}
|
|
}
|
|
|
|
} // namespace
|
|
|
|
int main() {
|
|
std::cout << "store codec properties, seed " << kSeed << std::endl;
|
|
std::mt19937_64 rng(kSeed);
|
|
test_known_vectors();
|
|
property_varint(rng);
|
|
property_crc(rng);
|
|
property_fields_records(rng);
|
|
property_blocks(rng);
|
|
property_garbage(rng);
|
|
std::cout << "store codec: all properties hold" << std::endl;
|
|
return 0;
|
|
}
|