use store_io_core::evidence::Evidence;
use store_io_format::meta::{TableEntry, VOLUME_META_LEN};
pub(crate) const MIN_LOG2_BLOCK: u8 = 12;
pub(crate) const MAX_LOG2_BLOCK: u8 = 16;
pub(crate) const DATA_ALIGN: u64 = 1 << 20;
pub(crate) const VOLUME_OBJECT: u64 = 0;
pub(crate) const TABLE_OBJECT: u64 = 1;
pub(crate) fn choose_log2_block(ev: &Evidence, requested: Option<u32>) -> u8 {
let d = &ev.device;
let f = &ev.fs;
let need = [
4096,
d.logical_block,
d.physical_block,
d.optimal_write,
f.dio_mem_align,
f.dio_offset_align,
]
.into_iter()
.max()
.unwrap_or(4096)
.max(requested.unwrap_or(0));
let log2 = need.next_power_of_two().trailing_zeros() as u8;
log2.clamp(MIN_LOG2_BLOCK, MAX_LOG2_BLOCK)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct Layout {
pub(crate) log2_block: u8,
pub(crate) log2_table: u8,
pub(crate) format: u16,
pub(crate) pages: u32,
}
impl Layout {
pub(crate) fn region_object(&self, id: u64) -> u64 {
if self.format == store_io_format::slot::FORMAT_2 {
(1u64 << 62) | id
} else {
debug_assert!(id < 1 << 32, "a format 1 region id");
(1u64 << 32) | id
}
}
pub(crate) fn block(&self) -> u64 {
1u64 << self.log2_block
}
pub(crate) fn table(&self) -> u64 {
1u64 << self.log2_table
}
pub(crate) fn volume_slots(&self) -> (u64, u64) {
(0, self.block())
}
pub(crate) fn table_slots(&self) -> (u64, u64) {
let a = 2 * self.block();
(a, a + self.table())
}
pub(crate) fn page_slots(&self, p: u32) -> (u64, u64) {
let a = 2 * self.block() + 2 * u64::from(p) * self.table();
(a, a + self.table())
}
pub(crate) fn data_start(&self) -> u64 {
2 * self.block() + 2 * u64::from(self.pages) * self.table()
}
pub(crate) const fn v1(log2_block: u8, log2_table: u8) -> Self {
Self {
log2_block,
log2_table,
format: store_io_format::slot::FORMAT_1,
pages: 1,
}
}
pub(crate) fn extent(&self, data: u64) -> Option<u64> {
data.checked_add(2 * self.block())
}
pub(crate) fn table_capacity(&self) -> usize {
let room = self.table() as usize
- store_io_format::slot::HEADER_LEN
- store_io_format::meta::TABLE_HEADER_LEN;
room / store_io_format::meta::ENTRY_LEN
}
pub(crate) fn place(
&self,
entries: &[TableEntry],
container_len: u64,
len: u64,
align: bool,
) -> Option<(u64, Option<usize>, bool)> {
let block = self.block();
for (i, e) in entries.iter().enumerate() {
if e.state == store_io_format::meta::RegionState::Released
&& e.extent_len(block)? == len
&& !overlaps_ready(entries, e.offset, len, block)
{
return Some((e.offset, Some(i), false));
}
}
let tail = self.tail(entries);
let header = 2 * block;
let start = if align && len.saturating_sub(header) >= DATA_ALIGN {
store_io_core::align::align_up(tail.checked_add(header)?, DATA_ALIGN)? - header
} else {
tail
};
let grow = start.checked_add(len)? > container_len;
Some((start, None, grow))
}
pub(crate) fn tail(&self, entries: &[TableEntry]) -> u64 {
let block = self.block();
entries
.iter()
.filter_map(|e| e.offset.checked_add(e.extent_len(block)?))
.fold(self.data_start(), u64::max)
}
}
fn overlaps_ready(entries: &[TableEntry], start: u64, len: u64, block: u64) -> bool {
let end = start.saturating_add(len);
entries
.iter()
.filter(|e| e.state == store_io_format::meta::RegionState::Ready)
.any(|e| {
let e_end = e
.offset
.saturating_add(e.extent_len(block).unwrap_or(u64::MAX));
start < e_end && e.offset < end
})
}
const _: () = assert!(VOLUME_META_LEN + store_io_format::slot::HEADER_LEN <= 1 << MIN_LOG2_BLOCK);
#[cfg(test)]
mod tests {
use super::*;
use store_io_core::evidence::PlatformKind;
use store_io_format::meta::{FillPattern, RegionKind, RegionName, RegionState};
#[test]
fn test_block_choice_follows_the_largest_constraint() {
let mut ev = Evidence::unknown(PlatformKind::Sim);
assert_eq!(choose_log2_block(&ev, None), 12);
ev.device.physical_block = 16384;
assert_eq!(choose_log2_block(&ev, None), 14);
ev.fs.dio_offset_align = 1 << 20;
assert_eq!(choose_log2_block(&ev, None), 16, "capped at 64 KiB");
let ev = Evidence::unknown(PlatformKind::Sim);
assert_eq!(choose_log2_block(&ev, Some(8192)), 13);
}
#[test]
fn test_region_header_objects_follow_the_format() {
let mut l = Layout::v1(12, 16);
assert_eq!(l.region_object(7), (1 << 32) | 7);
l.format = store_io_format::slot::FORMAT_2;
let id = (3u64 << 32) | 9;
assert_eq!(l.region_object(id), (1 << 62) | id);
}
#[test]
fn test_layout_offsets_and_capacity() {
let l = Layout::v1(12, 14);
assert_eq!(l.volume_slots(), (0, 4096));
assert_eq!(l.table_slots(), (8192, 8192 + 16384));
assert_eq!(l.data_start(), 8192 + 32768);
assert_eq!(l.table_capacity(), 253);
}
#[test]
fn test_placement_appends_or_reuses_released_space() {
let l = Layout::v1(12, 14);
let entry = |id, offset, data, state| TableEntry {
region_id: id,
kind: RegionKind::Append,
state,
name: RegionName::new("r").unwrap_or_else(|_| panic!("name")),
offset,
data_size: data,
fill: FillPattern::Zeros,
tag: 0,
};
let start = l.data_start();
assert_eq!(
l.place(&[], start, 3 * 4096, true),
Some((start, None, true))
);
let used = vec![entry(0, start, 4096, RegionState::Ready)];
assert_eq!(
l.place(&used, start + 3 * 4096, 4096 * 3, true),
Some((start + 3 * 4096, None, true))
);
let released = vec![entry(0, start, 4096, RegionState::Released)];
assert_eq!(
l.place(&released, start + 3 * 4096, 3 * 4096, true),
Some((start, Some(0), false))
);
assert_eq!(
l.place(&released, start + 3 * 4096, 4 * 4096, true),
Some((start + 3 * 4096, None, true))
);
}
#[test]
fn test_large_regions_start_their_data_on_a_mebibyte_boundary() {
let l = Layout::v1(12, 14);
let start = l.data_start();
let len = 2 * 4096 + DATA_ALIGN;
let (at, reuse, _) = l.place(&[], start, len, true).unwrap_or((0, None, false));
assert_eq!(reuse, None);
assert_eq!((at + 2 * 4096) % DATA_ALIGN, 0, "data area aligned");
assert!(at >= start);
assert_eq!(l.place(&[], start, len, false).map(|p| p.0), Some(start));
assert_eq!(
l.place(&[], start, 3 * 4096, true).map(|p| p.0),
Some(start)
);
}
}