use std::fmt;
use xxhash_rust::xxh3::xxh3_64_with_seed;
use crate::checksum::Crc32c;
use crate::format::{MAX_KEY_SIZE, RECORD_ALIGNMENT, RECORD_HEADER_SIZE, RecordHeader};
use crate::index::{IndexEntry, MAX_RECORD_LEN, PackedLocation, PackedLocationError};
use crate::region_manager::RegionAppendReservation;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) 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 std::error::Error for RecordEncodeError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::InvalidLocation(error) => Some(error),
_ => None,
}
}
}
pub(crate) 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)]
pub(crate) 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 entry = encode_value_into_hashed(destination, reservation, hash, required, key, value)?;
Ok((hash, entry))
}
pub(crate) fn encode_value_into_hashed(
destination: &mut [u8],
reservation: RegionAppendReservation,
hash: u64,
required: u32,
key: &[u8],
value: &[u8],
) -> Result<IndexEntry, RecordEncodeError> {
encode_value_into_hashed_with_seqno(
destination,
reservation,
hash,
required,
key,
value,
reservation.seqno,
)
}
pub(crate) fn encode_reinsert_into_hashed(
destination: &mut [u8],
reservation: RegionAppendReservation,
hash: u64,
required: u32,
key: &[u8],
value: &[u8],
logical_seqno: u64,
) -> Result<IndexEntry, RecordEncodeError> {
if logical_seqno == 0 {
return Err(RecordEncodeError::InvalidReservation);
}
encode_value_into_hashed_with_seqno(
destination,
reservation,
hash,
required,
key,
value,
logical_seqno,
)
}
fn encode_value_into_hashed_with_seqno(
destination: &mut [u8],
reservation: RegionAppendReservation,
hash: u64,
required: u32,
key: &[u8],
value: &[u8],
logical_seqno: u64,
) -> Result<IndexEntry, RecordEncodeError> {
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 payload_end = RECORD_HEADER_SIZE
.checked_add(key.len())
.and_then(|end| end.checked_add(value.len()))
.ok_or(RecordEncodeError::LengthOverflow)?;
if payload_end > destination_len {
return Err(RecordEncodeError::ReservationTooSmall {
required,
reserved: reservation.record_bytes,
});
}
let mut payload_crc = Crc32c::new();
payload_crc.update(key);
payload_crc.update(value);
destination[payload_end..].fill(0);
let key_start = RECORD_HEADER_SIZE;
let value_start = key_start
.checked_add(key.len())
.ok_or(RecordEncodeError::LengthOverflow)?;
destination[key_start..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.finish(),
region_generation: reservation.region_created_seqno,
record_len: reservation.record_bytes,
};
destination[..RECORD_HEADER_SIZE].copy_from_slice(&header.encode());
Ok(IndexEntry { location })
}
pub(crate) fn hash_key(seed: u64, key: &[u8]) -> u64 {
xxh3_64_with_seed(key, seed)
}
#[cfg(test)]
mod tests {
use crate::checksum::crc32c;
use super::*;
#[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,]);
}
#[test]
fn sixteen_kib_value_uses_the_minimum_format_envelope() {
let key = b"file/chunk/0007";
let value = (0..16 * 1024)
.map(|index| ((index * 17 + index / 13) & 0xff) as u8)
.collect::<Vec<_>>();
let required = required_record_bytes(key.len(), value.len()).unwrap();
assert_ne!(
required as usize % crate::io_backend::DIRECT_IO_ALIGNMENT,
0
);
let reservation = RegionAppendReservation {
shard_id: 0,
region_id: 7,
region_created_seqno: 11,
offset: 0,
record_bytes: required,
seqno: 17,
};
let mut destination = vec![0xa5; required as usize];
let (hash, entry) = encode_value_into(
&mut destination,
reservation,
0x0123_4567_89ab_cdef,
key,
&value,
)
.unwrap();
assert_eq!(hash, hash_key(0x0123_4567_89ab_cdef, key));
assert_eq!(entry.location.region_id(), 7);
assert_eq!(entry.location.offset(), 0);
assert_eq!(entry.location.record_len(), required);
let header = RecordHeader::decode(&destination[..RECORD_HEADER_SIZE]).unwrap();
assert_eq!(usize::from(header.key_len), key.len());
assert_eq!(header.value_len, value.len() as u32);
assert_eq!(header.seqno, 17);
assert_eq!(header.key_hash, hash);
let key_start = RECORD_HEADER_SIZE;
let value_start = key_start + key.len();
let payload_end = value_start + value.len();
assert_eq!(&destination[key_start..value_start], key);
assert_eq!(&destination[value_start..payload_end], value);
assert_eq!(
header.payload_crc,
crc32c(&destination[key_start..payload_end])
);
assert!(destination[payload_end..].iter().all(|byte| *byte == 0));
}
#[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];
encode_reinsert_into_hashed(&mut destination, reservation, 7, required, key, value, 11)
.unwrap();
let header = RecordHeader::decode(&destination[..RECORD_HEADER_SIZE]).unwrap();
assert_eq!(header.seqno, 11);
assert_eq!(header.region_generation, 100);
}
#[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));
}
}