use std::error;
use std::fmt;
use hashcrew::xxhash::xxh3_64_with_seed;
use crate::checksum::crc32c;
use crate::region::index::packed::IndexEntry;
use crate::region::index::packed::MAX_RECORD_LEN;
use crate::region::index::packed::PackedLocation;
use crate::region::index::packed::PackedLocationError;
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;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum RecordEncodeError {
LengthOverflow,
KeyTooLarge,
RecordTooLarge,
DestinationLengthMismatch { reserved: u32, destination: usize },
ReservationTooSmall { required: u32, reserved: u32 },
InvalidReservation,
InvalidLocation(PackedLocationError),
}
impl fmt::Display for RecordEncodeError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::LengthOverflow => formatter.write_str("record length overflow"),
Self::KeyTooLarge => formatter.write_str("record key exceeds the format limit"),
Self::RecordTooLarge => {
formatter.write_str("record length exceeds the packed-location limit")
}
Self::DestinationLengthMismatch {
reserved,
destination,
} => write!(
formatter,
"record destination length {destination} does not match reservation {reserved}"
),
Self::ReservationTooSmall { required, reserved } => write!(
formatter,
"record reservation {reserved} is smaller than required length {required}"
),
Self::InvalidReservation => {
formatter.write_str("record reservation identity is invalid")
}
Self::InvalidLocation(error) => {
write!(formatter, "invalid record location: {error}")
}
}
}
}
impl error::Error for RecordEncodeError {
fn source(&self) -> Option<&(dyn error::Error + 'static)> {
match self {
Self::InvalidLocation(error) => Some(error),
_ => None,
}
}
}
pub struct RecordPayload<'a> {
key: &'a [u8],
value: &'a [u8],
crc: u32,
}
impl<'a> RecordPayload<'a> {
pub fn new(key: &'a [u8], value: &'a [u8]) -> Self {
Self {
key,
value,
crc: crc32c(&[key, value]),
}
}
pub fn validate(key: &'a [u8], value: &'a [u8], expected_crc: u32) -> Option<Self> {
let payload = Self::new(key, value);
(payload.crc == expected_crc).then_some(payload)
}
}
pub fn required_record_bytes(key_len: usize, value_len: usize) -> Result<u32, RecordEncodeError> {
if key_len > MAX_KEY_SIZE {
return Err(RecordEncodeError::KeyTooLarge);
}
let record_bytes =
RecordHeader::aligned_len(key_len, value_len).ok_or(RecordEncodeError::LengthOverflow)?;
if record_bytes > MAX_RECORD_LEN {
return Err(RecordEncodeError::RecordTooLarge);
}
Ok(record_bytes)
}
#[cfg(test)]
fn encode_value_into(
destination: &mut [u8],
reservation: RegionAppendReservation,
hash_seed: u64,
key: &[u8],
value: &[u8],
) -> Result<(u64, IndexEntry), RecordEncodeError> {
let required = required_record_bytes(key.len(), value.len())?;
let hash = hash_key(hash_seed, key);
let payload = RecordPayload::new(key, value);
let entry = encode_value_into_hashed(destination, reservation, hash, required, &payload)?;
Ok((hash, entry))
}
pub fn encode_value_into_hashed(
destination: &mut [u8],
reservation: RegionAppendReservation,
hash: u64,
required: u32,
payload: &RecordPayload<'_>,
) -> Result<IndexEntry, RecordEncodeError> {
encode_value_into_hashed_with_seqno(
destination,
reservation,
hash,
required,
payload,
reservation.seqno,
)
}
pub fn encode_reinsert_into_hashed(
destination: &mut [u8],
reservation: RegionAppendReservation,
hash: u64,
required: u32,
payload: &RecordPayload<'_>,
logical_seqno: u64,
) -> Result<IndexEntry, RecordEncodeError> {
if logical_seqno == 0 {
return Err(RecordEncodeError::InvalidReservation);
}
encode_value_into_hashed_with_seqno(
destination,
reservation,
hash,
required,
payload,
logical_seqno,
)
}
fn encode_value_into_hashed_with_seqno(
destination: &mut [u8],
reservation: RegionAppendReservation,
hash: u64,
required: u32,
payload: &RecordPayload<'_>,
logical_seqno: u64,
) -> Result<IndexEntry, RecordEncodeError> {
let key = payload.key;
let value = payload.value;
let destination_len = destination.len();
let reserved_len =
usize::try_from(reservation.record_bytes).map_err(|_| RecordEncodeError::LengthOverflow)?;
if destination_len != reserved_len {
return Err(RecordEncodeError::DestinationLengthMismatch {
reserved: reservation.record_bytes,
destination: destination_len,
});
}
if reservation.record_bytes < required {
return Err(RecordEncodeError::ReservationTooSmall {
required,
reserved: reservation.record_bytes,
});
}
if reservation.region_created_seqno == 0
|| reservation.seqno < reservation.region_created_seqno
|| !reservation.offset.is_multiple_of(RECORD_ALIGNMENT)
{
return Err(RecordEncodeError::InvalidReservation);
}
let location = PackedLocation::new(
reservation.region_id,
reservation.offset,
reservation.record_bytes,
)
.map_err(RecordEncodeError::InvalidLocation)?;
let value_len = u32::try_from(value.len()).map_err(|_| RecordEncodeError::LengthOverflow)?;
let key_len = u16::try_from(key.len()).map_err(|_| RecordEncodeError::KeyTooLarge)?;
let value_start = RECORD_HEADER_SIZE
.checked_add(key.len())
.ok_or(RecordEncodeError::LengthOverflow)?;
let payload_end = value_start
.checked_add(value.len())
.ok_or(RecordEncodeError::LengthOverflow)?;
if payload_end > destination_len {
return Err(RecordEncodeError::ReservationTooSmall {
required,
reserved: reservation.record_bytes,
});
}
destination[payload_end..].fill(0);
destination[RECORD_HEADER_SIZE..value_start].copy_from_slice(key);
destination[value_start..payload_end].copy_from_slice(value);
let header = RecordHeader {
key_len,
value_len,
seqno: logical_seqno,
key_hash: hash,
payload_crc: payload.crc,
region_generation: reservation.region_created_seqno,
record_len: reservation.record_bytes,
};
destination[..RECORD_HEADER_SIZE].copy_from_slice(&header.encode());
Ok(IndexEntry { location })
}
pub fn hash_key(seed: u64, key: &[u8]) -> u64 {
xxh3_64_with_seed(key, seed)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::io::file::DIRECT_IO_ALIGNMENT;
#[test]
fn seeded_xxh3_vectors_define_key_hashing() {
let seed = 0x6a09_e667_f3bc_c909;
let actual = [hash_key(seed, b""), hash_key(seed, b"cache2\0key")];
assert_eq!(actual, [0x4e79_f242_1392_7a65, 0xd168_c107_36e1_695c,]);
let key = (0..4096)
.map(|index| ((index * 17 + index / 13) & 0xff) as u8)
.collect::<Vec<_>>();
for (length, expected) in [
(17, [0xc941_bd3a_fcc1_dde6, 0x7c4f_f470_c665_724d]),
(128, [0xf2e0_bda2_8217_733d, 0x3cb7_ae15_895a_24ad]),
(129, [0x1317_3987_cd70_3b99, 0xd88a_7ac4_c75e_9413]),
(240, [0x172a_b708_d5be_4619, 0x46c0_b308_8509_604e]),
(241, [0x32fe_e601_d243_0747, 0xc98a_c273_fd5f_d41a]),
(1024, [0x8c8f_31e5_7d4a_a58c, 0x2e24_86ac_39f8_9d6a]),
(1025, [0x769a_d4b4_4613_261a, 0xe965_733c_5fb9_ca62]),
(4096, [0x6d68_4012_8c18_9b6b, 0x6a15_bc71_0ad2_9e01]),
] {
let actual = [0, seed].map(|seed| hash_key(seed, &key[..length]));
assert_eq!(actual, expected, "key length {length}");
}
}
#[test]
fn default_sized_value_uses_only_record_alignment() {
let key_len = b"file/chunk/0007".len();
let value_len = 16 * 1024;
let payload_end = RECORD_HEADER_SIZE + key_len + value_len;
let expected = payload_end.next_multiple_of(RECORD_ALIGNMENT as usize);
assert_eq!(
required_record_bytes(key_len, value_len).unwrap() as usize,
expected
);
assert!(!expected.is_multiple_of(DIRECT_IO_ALIGNMENT));
}
#[test]
fn payload_validation_checks_all_bytes_before_rewrite() {
for (key, value) in [
(&b""[..], &b""[..]),
(&b"key"[..], &b""[..]),
(&b""[..], &b"value"[..]),
(&b"key"[..], &b"value"[..]),
] {
let expected_crc = crc_fast::crc32_iscsi(&[key, value].concat());
let payload = RecordPayload::validate(key, value, expected_crc).unwrap();
assert_eq!(payload.key, key);
assert_eq!(payload.value, value);
assert_eq!(payload.crc, expected_crc);
assert!(RecordPayload::validate(key, value, expected_crc ^ 1).is_none());
}
}
#[test]
fn reinsertion_preserves_logical_seqno_across_a_new_region_generation() {
let key = b"key";
let value = b"value";
let required = required_record_bytes(key.len(), value.len()).unwrap();
let reservation = RegionAppendReservation {
shard_id: 0,
region_id: 3,
region_created_seqno: 100,
offset: 0,
record_bytes: required,
seqno: 101,
};
let mut destination = vec![0_u8; required as usize];
let expected_crc = crc_fast::crc32_iscsi(&[&key[..], &value[..]].concat());
let payload = RecordPayload::validate(key, value, expected_crc).unwrap();
encode_reinsert_into_hashed(&mut destination, reservation, 7, required, &payload, 11)
.unwrap();
let header = RecordHeader::decode(&destination[..RECORD_HEADER_SIZE]).unwrap();
assert_eq!(header.seqno, 11);
assert_eq!(header.region_generation, 100);
assert_eq!(header.payload_crc, expected_crc);
}
#[test]
fn invalid_lengths_and_reservations_return_typed_errors_without_writes() {
assert_eq!(
required_record_bytes(MAX_KEY_SIZE + 1, 0),
Err(RecordEncodeError::KeyTooLarge)
);
assert_eq!(
required_record_bytes(0, MAX_RECORD_LEN as usize - RECORD_HEADER_SIZE + 1),
Err(RecordEncodeError::RecordTooLarge)
);
let required = required_record_bytes(3, 16).unwrap();
let reservation = RegionAppendReservation {
shard_id: 0,
region_id: 0,
region_created_seqno: 1,
offset: 0,
record_bytes: required,
seqno: 1,
};
let mut wrong_destination = vec![0xa5; required as usize + 32];
assert!(matches!(
encode_value_into(&mut wrong_destination, reservation, 0, b"key", &[7; 16],),
Err(RecordEncodeError::DestinationLengthMismatch { .. })
));
assert!(wrong_destination.iter().all(|byte| *byte == 0xa5));
let invalid_generation = RegionAppendReservation {
region_created_seqno: 0,
..reservation
};
let mut exact_destination = vec![0xa5; required as usize];
assert_eq!(
encode_value_into(
&mut exact_destination,
invalid_generation,
0,
b"key",
&[7; 16],
),
Err(RecordEncodeError::InvalidReservation)
);
assert!(exact_destination.iter().all(|byte| *byte == 0xa5));
}
}