use std::collections::BTreeMap;
use std::collections::BTreeSet;
use quickcheck::Gen;
use quickcheck::QuickCheck;
use crate::checksum::crc32c;
use crate::hashing::FixedPrehashedMap;
use crate::region::index::ReclaimIndexAction;
use crate::region::index::RegionIndex;
use crate::region::index::packed::IndexEntry;
use crate::region::index::packed::PackedLocation;
use crate::region::index::packed::record_size_class_upper_bound;
use crate::region::index::storage::IndexSlot;
use crate::region::index::storage::PartitionedIndexStorage;
use crate::region::index::storage::page_format::INDEX_IMAGE_SLOT_SIZE;
use crate::region::manager::RegionAppendReservation;
use crate::region::record::MAX_KEY_SIZE;
use crate::region::record::RECORD_ALIGNMENT;
use crate::region::record::RECORD_HEADER_SIZE;
use crate::region::record::RecordHeader;
use crate::region::record::codec::RecordPayload;
use crate::region::record::codec::encode_reinsert_into_hashed;
use crate::region::record::codec::encode_value_into_hashed;
use crate::region::record::codec::required_record_bytes;
use crate::region::recovery::DataSuperblock;
use crate::region::recovery::RECOVERY_PAGE_SIZE;
use crate::region::recovery::RecoveryImageHeader;
use crate::region::recovery::StateRecord;
use crate::region::recovery::metadata::RegionMetadata;
const MAX_PROPERTY_INPUT_BYTES: usize = 16 * 1024;
const MAX_PROPERTY_MAP_ENTRIES: usize = 64;
const MAX_PROPERTY_OPERATIONS: usize = 256;
const PROPERTY_CASES: u64 = 10_000;
fn exercise_persistent_decoders(input: &[u8]) {
probe_persistent_bytes(input);
let page = padded::<RECOVERY_PAGE_SIZE>(input);
probe_persistent_bytes(&page);
}
fn probe_persistent_bytes(input: &[u8]) {
let _ = DataSuperblock::probe(input);
let _ = RecoveryImageHeader::probe(input);
let _ = StateRecord::decode(input);
let _ = RecordHeader::decode(input);
let _ = RegionMetadata::decode(input);
if let Some(encoded) = input
.get(..INDEX_IMAGE_SLOT_SIZE)
.and_then(|bytes| <&[u8; INDEX_IMAGE_SLOT_SIZE]>::try_from(bytes).ok())
{
let _ = IndexSlot::decode(encoded).runtime_state();
}
}
fn exercise_record_roundtrip(input: &[u8]) {
let control = padded::<32>(input);
let payload_len = usize::from(u16::from_le_bytes(control[0..2].try_into().unwrap()))
.min(MAX_PROPERTY_INPUT_BYTES);
let payload_seed = input.get(control.len()..).unwrap_or_default();
let pattern = if payload_seed.is_empty() {
control.as_slice()
} else {
payload_seed
};
let payload = (0..payload_len)
.map(|index| pattern[index % pattern.len()])
.collect::<Vec<_>>();
let key_limit = payload.len().min(MAX_KEY_SIZE);
let key_len =
usize::from(u16::from_le_bytes(control[2..4].try_into().unwrap())) % (key_limit + 1);
let (key, value) = payload.split_at(key_len);
let record_bytes = required_record_bytes(key.len(), value.len()).unwrap();
let hash = u64::from_le_bytes(control[4..12].try_into().unwrap());
let region_created_seqno =
u64::from(u16::from_le_bytes(control[12..14].try_into().unwrap())) + 1;
let seqno =
region_created_seqno + u64::from(u16::from_le_bytes(control[14..16].try_into().unwrap()));
let region_id = u32::from_le_bytes(control[16..20].try_into().unwrap()) & 0x3ff;
let offset_units = u32::from_le_bytes(control[20..24].try_into().unwrap()) & 0xffff;
let reservation = RegionAppendReservation {
shard_id: usize::from(control[30] & 3),
region_id,
region_created_seqno,
offset: offset_units * RECORD_ALIGNMENT,
record_bytes,
seqno,
};
let logical_seqno = u64::from_le_bytes(control[24..32].try_into().unwrap()).max(1);
let reinsert = control[31] & 1 != 0;
let expected_seqno = if reinsert { logical_seqno } else { seqno };
let mut destination = vec![0xa5; record_bytes as usize];
let record_payload = RecordPayload::new(key, value);
let entry = if reinsert {
encode_reinsert_into_hashed(
&mut destination,
reservation,
hash,
record_bytes,
&record_payload,
logical_seqno,
)
} else {
encode_value_into_hashed(
&mut destination,
reservation,
hash,
record_bytes,
&record_payload,
)
}
.unwrap();
assert_eq!(entry.location.region_id(), region_id);
assert_eq!(entry.location.offset(), reservation.offset);
assert_eq!(entry.location.record_len(), record_bytes);
let header = RecordHeader::decode(&destination[..RECORD_HEADER_SIZE]).unwrap();
assert_eq!(usize::from(header.key_len), key.len());
assert_eq!(header.value_len as usize, value.len());
assert_eq!(header.seqno, expected_seqno);
assert_eq!(header.key_hash, hash);
assert_eq!(header.payload_crc, crc32c(&[&payload]));
assert_eq!(header.region_generation, region_created_seqno);
assert_eq!(header.record_len, record_bytes);
let mut chunks = Vec::new();
let mut remaining = payload.as_slice();
for control_byte in control {
if remaining.is_empty() {
break;
}
let chunk_len = usize::from(control_byte) % remaining.len() + 1;
let (chunk, tail) = remaining.split_at(chunk_len);
chunks.push(chunk);
remaining = tail;
}
chunks.push(remaining);
assert_eq!(crc32c(&chunks), header.payload_crc);
let payload_end = RECORD_HEADER_SIZE + payload.len();
assert_eq!(&destination[RECORD_HEADER_SIZE..payload_end], payload);
assert!(destination[payload_end..].iter().all(|byte| *byte == 0));
}
fn exercise_fixed_map_operations(input: &[u8]) {
let operation_bytes = input.get(1..).unwrap_or_default();
let maximum_entries = operation_bytes
.len()
.div_ceil(3)
.clamp(1, MAX_PROPERTY_MAP_ENTRIES);
let capacity = usize::from(input.first().copied().unwrap_or(0)) % maximum_entries + 1;
let mut actual = FixedPrehashedMap::try_new(capacity).unwrap();
let mut expected = BTreeMap::<u64, u32>::new();
let mut seen = BTreeSet::new();
for chunk in operation_bytes.chunks(3).take(MAX_PROPERTY_OPERATIONS) {
let operation = padded::<3>(chunk);
let hash = u64::from(operation[1]);
let value = u32::from(operation[2]);
seen.insert(hash);
match operation[0] % 3 {
0 => {
let previous = expected.get(&hash).copied();
if previous.is_none() && expected.len() == capacity {
assert_eq!(actual.get(hash), None);
continue;
}
let can_insert = actual.can_upsert(hash);
let inserted = actual.insert(hash, value);
assert_eq!(inserted.is_some(), can_insert);
if let Some(actual_previous) = inserted {
assert_eq!(actual_previous, previous);
expected.insert(hash, value);
} else {
assert!(previous.is_none());
}
}
1 => assert_eq!(actual.get(hash), expected.get(&hash).copied()),
_ => {
let expected_removed = expected.remove(&hash);
assert_eq!(actual.remove(hash), expected_removed);
}
}
assert_eq!(actual.get(hash), expected.get(&hash).copied());
}
for hash in seen {
assert_eq!(actual.get(hash), expected.get(&hash).copied());
}
}
fn exercise_region_index_operations(input: &[u8]) {
let slot_count = 8_usize << usize::from(input.first().copied().unwrap_or(0) & 3);
let storage = PartitionedIndexStorage::anonymous(slot_count).unwrap();
let index = RegionIndex::from_storage(storage).unwrap();
index.set_activity_counters_enabled(true);
for chunk in input
.get(1..)
.unwrap_or_default()
.chunks(4)
.take(MAX_PROPERTY_OPERATIONS)
{
let operation = padded::<4>(chunk);
let hash = splitmix64(u64::from(operation[1]));
let location = property_location(splitmix64(u64::from(operation[2])));
let replacement = IndexEntry {
location: property_location(splitmix64(u64::from(operation[3]) ^ u64::MAX)),
};
let before = index.lookup_raw(hash).unwrap();
match operation[0] % 7 {
0 => {
assert!(index.upsert(hash, IndexEntry { location }).unwrap());
assert_eq!(
index.lookup_raw(hash).unwrap(),
Some(indexed_entry(location))
);
}
1 => {}
2 => {
assert_eq!(index.try_delete(hash).unwrap(), before.is_some());
assert_eq!(index.lookup_raw(hash).unwrap(), None);
}
3 => {
let expected_match =
before.is_some_and(|entry| entry.location.index_equivalent(location));
assert_eq!(
index.remove_if_match(hash, location).unwrap(),
expected_match
);
assert_eq!(
index.lookup_raw(hash).unwrap(),
if expected_match { None } else { before }
);
}
4 => {
let expected_match =
before.is_some_and(|entry| entry.location.index_equivalent(location));
assert_eq!(
index.replace_if_match(hash, location, replacement).unwrap(),
expected_match
);
assert_eq!(
index.lookup_raw(hash).unwrap(),
if expected_match {
Some(indexed_entry(replacement.location))
} else {
before
}
);
}
5 => {
let expected_match =
before.is_some_and(|entry| entry.location.index_equivalent(location));
match index.prepare_reclaim(hash, location).unwrap() {
ReclaimIndexAction::Missing => {
assert!(!expected_match);
assert_eq!(index.lookup_raw(hash).unwrap(), before);
}
ReclaimIndexAction::Removed => {
assert!(expected_match);
assert_eq!(index.lookup_raw(hash).unwrap(), None);
}
ReclaimIndexAction::Reinsert => {
assert!(expected_match);
assert_eq!(index.lookup_raw(hash).unwrap(), before);
}
}
}
_ => {
assert!(index.upsert(hash, IndexEntry { location }).unwrap());
assert_eq!(
index.prepare_reclaim(hash, location).unwrap(),
ReclaimIndexAction::Removed
);
assert_eq!(index.lookup_raw(hash).unwrap(), None);
}
}
let snapshot = index.snapshot().unwrap();
assert_eq!(
snapshot.physical_value_slots + snapshot.empty_slots,
snapshot.slot_capacity
);
}
}
fn property_location(raw: u64) -> PackedLocation {
let region_id = raw as u32 & 0x3ff;
let offset = ((raw >> 10) as u32 & 0xffff) * RECORD_ALIGNMENT;
let record_len = (((raw >> 26) as u32 & 0x3ff) + 1) * RECORD_ALIGNMENT;
PackedLocation::new(region_id, offset, record_len)
.expect("bounded aligned property-test location is representable")
}
fn indexed_entry(location: PackedLocation) -> IndexEntry {
let record_len = record_size_class_upper_bound(location.index_size_class()).unwrap();
IndexEntry {
location: PackedLocation::new(location.region_id(), location.offset(), record_len)
.expect("a valid property-test location has a representable size-class upper bound"),
}
}
fn splitmix64(mut value: u64) -> u64 {
value = value.wrapping_add(0x9e37_79b9_7f4a_7c15);
value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
value ^ (value >> 31)
}
fn padded<const N: usize>(input: &[u8]) -> [u8; N] {
let mut output = [0; N];
let len = input.len().min(N);
output[..len].copy_from_slice(&input[..len]);
output
}
fn check_arbitrary_bytes(property: fn(Vec<u8>) -> bool) {
QuickCheck::new()
.tests(PROPERTY_CASES)
.max_tests(PROPERTY_CASES)
.min_tests_passed(PROPERTY_CASES)
.rng(Gen::new(MAX_PROPERTY_INPUT_BYTES + 1))
.quickcheck(property);
}
#[test]
fn arbitrary_persistent_bytes_never_escape_bounds() {
fn property(input: Vec<u8>) -> bool {
exercise_persistent_decoders(&input);
true
}
exercise_persistent_decoders(&vec![u8::MAX; MAX_PROPERTY_INPUT_BYTES]);
check_arbitrary_bytes(property);
}
#[test]
fn arbitrary_record_roundtrips_preserve_encoding_contract() {
fn property(input: Vec<u8>) -> bool {
exercise_record_roundtrip(&input);
true
}
exercise_record_roundtrip(&vec![u8::MAX; MAX_PROPERTY_INPUT_BYTES]);
check_arbitrary_bytes(property);
}
#[test]
fn arbitrary_fixed_map_operations_match_the_reference_model() {
fn property(input: Vec<u8>) -> bool {
exercise_fixed_map_operations(&input);
true
}
exercise_fixed_map_operations(&vec![u8::MAX; MAX_PROPERTY_INPUT_BYTES]);
check_arbitrary_bytes(property);
}
#[test]
fn arbitrary_region_index_operations_preserve_invariants() {
fn property(input: Vec<u8>) -> bool {
exercise_region_index_operations(&input);
true
}
exercise_region_index_operations(&vec![u8::MAX; MAX_PROPERTY_INPUT_BYTES]);
check_arbitrary_bytes(property);
}