use std::collections::BTreeSet;
use std::fs::File;
use std::io::{Read, Seek, SeekFrom};
use std::path::{Path, PathBuf};
use crate::error::{Neo4jStoreError, Result};
const META_SIZE: usize = 40;
const STATE_SIZE: usize = 114;
const STATE_FIELDS_SIZE: usize = STATE_SIZE / 2;
const HEADER_LENGTH_SIZE: usize = 4;
const ID_HEADER_SIZE: usize = 36;
const EXPECTED_IDS_PER_ENTRY: u32 = 128;
const PAGE_SIZE: usize = 8192;
const BASE_HEADER_SIZE: usize = 82;
const KEY_SIZE: usize = 8;
const LONGS_PER_ENTRY: usize = EXPECTED_IDS_PER_ENTRY as usize / u64::BITS as usize;
const BITSET_COUNT: usize = 3;
const VALUE_SIZE: usize = 8 + LONGS_PER_ENTRY * 8 * BITSET_COUNT;
const MAX_KEY_COUNT: usize = (PAGE_SIZE - BASE_HEADER_SIZE) / (KEY_SIZE + VALUE_SIZE);
const VALUE_AREA_OFFSET: usize = BASE_HEADER_SIZE + MAX_KEY_COUNT * KEY_SIZE;
const ID_RANGE_LAYOUT_IDENTIFIER: u64 = 3_735_929_054 + EXPECTED_IDS_PER_ENTRY as u64;
const TREE_NODE: u8 = 1;
const LEAF_NODE: u8 = 1;
const INTERNAL_NODE: u8 = 0;
const DATA_LAYER: u8 = 0;
const PAGE_REFERENCE_SIZE: usize = 24;
const GENERATION_SAFE_POINTER_SIZE: usize = 12;
const INTERNAL_MAX_KEY_COUNT: usize =
(PAGE_SIZE - BASE_HEADER_SIZE - PAGE_REFERENCE_SIZE) / (KEY_SIZE + PAGE_REFERENCE_SIZE);
const INTERNAL_CHILDREN_OFFSET: usize = BASE_HEADER_SIZE + INTERNAL_MAX_KEY_COUNT * KEY_SIZE;
const BITSET_COMMIT: usize = 0;
const BITSET_REUSE: usize = 1;
const BITSET_RESERVED: usize = 2;
pub(super) fn empty_file(high_id: u64) -> Vec<u8> {
let highest_written_id = high_id.checked_sub(1).unwrap_or(u64::MAX);
let mut bytes = vec![0_u8; PAGE_SIZE * 4];
bytes[4..8].copy_from_slice(&(PAGE_SIZE as u32).to_be_bytes());
bytes[8..16].copy_from_slice(&ID_RANGE_LAYOUT_IDENTIFIER.to_be_bytes());
write_empty_state(&mut bytes, 1, 5, high_id, highest_written_id);
write_empty_state(&mut bytes, 2, 4, high_id, highest_written_id);
let root = &mut bytes[3 * PAGE_SIZE..4 * PAGE_SIZE];
root[0] = TREE_NODE;
root[1] = LEAF_NODE;
root[2..6].copy_from_slice(&3_u32.to_be_bytes());
bytes
}
fn write_empty_state(
bytes: &mut [u8],
page_id: usize,
unstable: u32,
high_id: u64,
highest_written_id: u64,
) {
let offset = PAGE_SIZE * page_id;
let mut fields = [0_u8; STATE_FIELDS_SIZE];
fields[0..4].copy_from_slice(&4_u32.to_be_bytes());
fields[4..8].copy_from_slice(&unstable.to_be_bytes());
fields[8..16].copy_from_slice(&3_u64.to_be_bytes());
fields[16..24].copy_from_slice(&3_u64.to_be_bytes());
fields[24..32].copy_from_slice(&3_u64.to_be_bytes());
fields[56] = 1;
bytes[offset..offset + STATE_FIELDS_SIZE].copy_from_slice(&fields);
bytes[offset + STATE_FIELDS_SIZE..offset + STATE_SIZE].copy_from_slice(&fields);
let header_offset = offset + STATE_SIZE;
bytes[header_offset..header_offset + HEADER_LENGTH_SIZE]
.copy_from_slice(&(ID_HEADER_SIZE as u32).to_be_bytes());
let header = &mut bytes
[header_offset + HEADER_LENGTH_SIZE..header_offset + HEADER_LENGTH_SIZE + ID_HEADER_SIZE];
header[0..8].copy_from_slice(&high_id.to_be_bytes());
header[8..16].copy_from_slice(&highest_written_id.to_be_bytes());
header[16..24].copy_from_slice(&2_u64.to_be_bytes());
header[24..28].copy_from_slice(&EXPECTED_IDS_PER_ENTRY.to_be_bytes());
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct IdGeneratorHeader {
pub(super) high_id: u64,
pub(super) highest_written_id: u64,
pub(super) generation: u64,
pub(super) ids_per_entry: u32,
pub(super) num_unused_ids: u64,
pub(super) state_header_offsets: [u64; 2],
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct TreeState {
page_id: u64,
stable_generation: u32,
unstable_generation: u32,
root_id: u64,
root_generation: u64,
last_id: u64,
clean: bool,
valid: bool,
}
#[allow(dead_code)]
pub(super) struct IdAllocation {
pub(super) first_id: u64,
pub(super) header_patches: [(u64, Vec<u8>); 2],
}
#[derive(Debug, PartialEq, Eq)]
#[allow(dead_code)]
pub(super) struct IdFreeUpdate {
pub(super) root_page_offset: u64,
pub(super) root_page: Vec<u8>,
pub(super) header_patches: [(u64, Vec<u8>); 2],
}
#[derive(Debug, PartialEq, Eq)]
pub(super) struct IdReuseUpdate {
pub(super) ids: Vec<u64>,
pub(super) root_page_offset: u64,
pub(super) root_page: Vec<u8>,
pub(super) header_patches: [(u64, Vec<u8>); 2],
}
#[derive(Debug, PartialEq, Eq)]
pub(super) struct IdTransactionUpdate {
pub(super) reused_ids: Vec<u64>,
pub(super) root_page_offset: u64,
pub(super) root_page: Vec<u8>,
pub(super) header_patches: [(u64, Vec<u8>); 2],
}
#[cfg(test)]
fn read(path: &Path) -> Result<IdGeneratorHeader> {
let (_, payload_size, _, header) = read_tree_header(path, false)?;
let offsets = [
state_header_offset(payload_size, 1) as u64,
state_header_offset(payload_size, 2) as u64,
];
Ok(IdGeneratorHeader {
state_header_offsets: offsets,
..header
})
}
pub(super) fn validate_writable(
database_directory: &Path,
store_name: &str,
physical_record_count: u64,
) -> Result<IdGeneratorHeader> {
let path = database_directory.join(format!("{store_name}.id"));
let (mut file, payload_size, selected, mut header) = read_tree_header(&path, true)?;
header.state_header_offsets = [
state_header_offset(payload_size, 1) as u64,
state_header_offset(payload_size, 2) as u64,
];
if header.generation <= 1 || header.ids_per_entry != EXPECTED_IDS_PER_ENTRY {
return Err(unsupported(
database_directory,
format!(
"ID generator {} requires rebuild or uses an unsupported range size",
path.display()
),
));
}
if header.high_id > physical_record_count {
return Err(unsupported(
database_directory,
format!(
"ID generator {} has high ID {}, beyond physical record capacity {physical_record_count}",
path.display(),
header.high_id
),
));
}
if header.high_id == 0 {
if header.highest_written_id != u64::MAX {
return Err(invalid(
&path,
0,
"zero high ID has a non-empty highest-written ID",
));
}
} else if header.highest_written_id >= header.high_id {
return Err(invalid(&path, 0, "highest-written ID is not below high ID"));
}
let persisted_unused_ids = validate_range_tree(&mut file, &path, selected, header.high_id)?;
validate_unused_id_count(&path, selected.page_id, header, persisted_unused_ids)?;
Ok(header)
}
#[allow(dead_code)]
pub(super) fn allocate_high_ids(
header: IdGeneratorHeader,
count: u64,
) -> std::result::Result<IdAllocation, String> {
if count == 0 {
return Err("ID allocation count must be greater than zero".to_owned());
}
let first_id = header.high_id;
let next_high_id = first_id
.checked_add(count)
.ok_or_else(|| "ID generator high ID overflow".to_owned())?;
let highest_written_id = next_high_id - 1;
let mut values = Vec::with_capacity(16);
values.extend_from_slice(&next_high_id.to_be_bytes());
values.extend_from_slice(&highest_written_id.to_be_bytes());
Ok(IdAllocation {
first_id,
header_patches: header
.state_header_offsets
.map(|offset| (offset, values.clone())),
})
}
#[allow(dead_code)]
pub(super) fn prepare_mark_deleted_and_free(path: &Path, ids: &[u64]) -> Result<IdFreeUpdate> {
if ids.is_empty() {
return Err(invalid(path, 0, "ID free list cannot be empty"));
}
let mut ids = ids.to_vec();
ids.sort_unstable();
if ids.windows(2).any(|pair| pair[0] == pair[1]) {
return Err(invalid(path, 0, "ID free list contains a duplicate ID"));
}
let (mut file, _, selected, header) = read_tree_header(path, true)?;
if header.ids_per_entry != EXPECTED_IDS_PER_ENTRY {
return Err(invalid(path, 0, "unsupported ID range size"));
}
if ids.iter().any(|id| *id >= header.high_id) {
return Err(invalid(
path,
0,
"cannot free an ID at or above the high ID",
));
}
let root_offset = usize::try_from(selected.root_id)
.ok()
.and_then(|id| id.checked_mul(PAGE_SIZE))
.ok_or_else(|| invalid(path, 0, "ID range root page offset overflow"))?;
let mut root = read_region(
&mut file,
path,
root_offset as u64,
PAGE_SIZE,
root_offset,
"ID range root page is truncated",
)?;
let persisted_unused_ids = validate_range_root(
path,
root_offset,
&root,
selected.root_generation,
header.high_id,
)?;
validate_unused_id_count(path, selected.page_id, header, persisted_unused_ids)?;
let key_count = read_u32_from(&root, 6) as usize;
let mut entries = (0..key_count)
.map(|position| {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let value_offset = VALUE_AREA_OFFSET + position * VALUE_SIZE;
let key = read_u64_from(&root, key_offset);
let value: [u8; VALUE_SIZE] = root[value_offset..value_offset + VALUE_SIZE]
.try_into()
.expect("validated fixed-size ID range value");
(key, value)
})
.collect::<Vec<_>>();
for id in &ids {
let range_index = *id / EXPECTED_IDS_PER_ENTRY as u64;
let offset_in_range = (*id % EXPECTED_IDS_PER_ENTRY as u64) as usize;
let position = entries.iter().position(|(key, _)| *key == range_index);
let position = if let Some(position) = position {
position
} else {
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&header.generation.to_be_bytes());
entries.push((range_index, value));
entries.len() - 1
};
let value = &mut entries[position].1;
let existing_generation = read_u64_from(value, 0);
if existing_generation != header.generation {
for long_index in 0..LONGS_PER_ENTRY {
let commit = read_bitset_long(value, BITSET_COMMIT, long_index);
write_bitset_long(value, BITSET_REUSE, long_index, commit);
write_bitset_long(value, BITSET_RESERVED, long_index, 0);
}
value[..8].copy_from_slice(&header.generation.to_be_bytes());
}
let long_index = offset_in_range / u64::BITS as usize;
let bit_index = offset_in_range % u64::BITS as usize;
let mask = 1_u64 << bit_index;
let commit = read_bitset_long(value, BITSET_COMMIT, long_index);
if commit & mask != 0 {
return Err(invalid(
path,
root_offset,
format!("ID {id} is already unused"),
));
}
write_bitset_long(value, BITSET_COMMIT, long_index, commit | mask);
let reuse = read_bitset_long(value, BITSET_REUSE, long_index);
write_bitset_long(value, BITSET_REUSE, long_index, reuse | mask);
let reserved = read_bitset_long(value, BITSET_RESERVED, long_index);
write_bitset_long(value, BITSET_RESERVED, long_index, reserved & !mask);
}
entries.sort_unstable_by_key(|(key, _)| *key as i64);
if entries.len() > MAX_KEY_COUNT {
return Err(invalid(
path,
root_offset,
"ID range leaf has no capacity for a new key",
));
}
root[6..10].copy_from_slice(&(entries.len() as u32).to_be_bytes());
root[BASE_HEADER_SIZE..VALUE_AREA_OFFSET].fill(0);
root[VALUE_AREA_OFFSET..VALUE_AREA_OFFSET + MAX_KEY_COUNT * VALUE_SIZE].fill(0);
for (position, (key, value)) in entries.into_iter().enumerate() {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
root[key_offset..key_offset + KEY_SIZE].copy_from_slice(&key.to_be_bytes());
let value_offset = VALUE_AREA_OFFSET + position * VALUE_SIZE;
root[value_offset..value_offset + VALUE_SIZE].copy_from_slice(&value);
}
let num_unused_ids = header
.num_unused_ids
.checked_add(ids.len() as u64)
.ok_or_else(|| invalid(path, 0, "unused ID count overflow"))?;
Ok(IdFreeUpdate {
root_page_offset: root_offset as u64,
root_page: root,
header_patches: [1_u64, 2_u64].map(|page_id| {
(
(state_header_offset(PAGE_SIZE, page_id) + 28) as u64,
num_unused_ids.to_be_bytes().to_vec(),
)
}),
})
}
pub(super) fn prepare_take_free_ids(path: &Path, count: usize) -> Result<Option<IdReuseUpdate>> {
if count == 0 {
return Err(invalid(path, 0, "ID reuse count must be greater than zero"));
}
let (mut file, _, selected, header) = read_tree_header(path, true)?;
if header.ids_per_entry != EXPECTED_IDS_PER_ENTRY {
return Err(invalid(path, 0, "unsupported ID range size"));
}
let root_offset = usize::try_from(selected.root_id)
.ok()
.and_then(|id| id.checked_mul(PAGE_SIZE))
.ok_or_else(|| invalid(path, 0, "ID range root page offset overflow"))?;
let mut root = read_region(
&mut file,
path,
root_offset as u64,
PAGE_SIZE,
root_offset,
"ID range root page is truncated",
)?;
let persisted_unused_ids = validate_range_root(
path,
root_offset,
&root,
selected.root_generation,
header.high_id,
)?;
validate_unused_id_count(path, selected.page_id, header, persisted_unused_ids)?;
if header.num_unused_ids == 0 {
return Ok(None);
}
let key_count = read_u32_from(&root, 6) as usize;
let mut ids = Vec::with_capacity(count);
for position in 0..key_count {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let range_index = read_u64_from(&root, key_offset);
let value_offset = VALUE_AREA_OFFSET + position * VALUE_SIZE;
let value = &mut root[value_offset..value_offset + VALUE_SIZE];
if read_u64_from(value, 0) != header.generation {
for long_index in 0..LONGS_PER_ENTRY {
let commit = read_bitset_long(value, BITSET_COMMIT, long_index);
write_bitset_long(value, BITSET_REUSE, long_index, commit);
write_bitset_long(value, BITSET_RESERVED, long_index, 0);
}
value[..8].copy_from_slice(&header.generation.to_be_bytes());
}
for long_index in 0..LONGS_PER_ENTRY {
let mut commit = read_bitset_long(value, BITSET_COMMIT, long_index);
let mut reuse = read_bitset_long(value, BITSET_REUSE, long_index);
let mut reserved = read_bitset_long(value, BITSET_RESERVED, long_index);
let mut available = commit & reuse & !reserved;
while available != 0 && ids.len() < count {
let bit_index = available.trailing_zeros() as usize;
let offset_in_range = long_index * u64::BITS as usize + bit_index;
let id = range_index
.checked_mul(EXPECTED_IDS_PER_ENTRY as u64)
.and_then(|base| base.checked_add(offset_in_range as u64))
.ok_or_else(|| invalid(path, root_offset, "reused ID overflow"))?;
let mask = 1_u64 << bit_index;
available &= !mask;
if id >= header.high_id {
continue;
}
ids.push(id);
commit &= !mask;
reuse &= !mask;
reserved &= !mask;
}
write_bitset_long(value, BITSET_COMMIT, long_index, commit);
write_bitset_long(value, BITSET_REUSE, long_index, reuse);
write_bitset_long(value, BITSET_RESERVED, long_index, reserved);
if ids.len() == count {
break;
}
}
if ids.len() == count {
break;
}
}
if ids.is_empty() {
return Ok(None);
}
let num_unused_ids = header
.num_unused_ids
.checked_sub(ids.len() as u64)
.ok_or_else(|| invalid(path, 0, "unused ID count underflow"))?;
Ok(Some(IdReuseUpdate {
ids,
root_page_offset: root_offset as u64,
root_page: root,
header_patches: [1_u64, 2_u64].map(|page_id| {
(
(state_header_offset(PAGE_SIZE, page_id) + 28) as u64,
num_unused_ids.to_be_bytes().to_vec(),
)
}),
}))
}
pub(super) fn prepare_reuse_and_free_ids(
path: &Path,
reuse_count: usize,
freed_ids: &[u64],
high_id_limit: u64,
) -> Result<IdTransactionUpdate> {
if reuse_count == 0 && freed_ids.is_empty() {
return Err(invalid(path, 0, "ID transaction update cannot be empty"));
}
let mut freed_ids = freed_ids.to_vec();
freed_ids.sort_unstable();
if freed_ids.windows(2).any(|pair| pair[0] == pair[1]) {
return Err(invalid(path, 0, "ID free list contains a duplicate ID"));
}
let (mut file, _, selected, header) = read_tree_header(path, true)?;
if header.ids_per_entry != EXPECTED_IDS_PER_ENTRY {
return Err(invalid(path, 0, "unsupported ID range size"));
}
let high_id_limit = high_id_limit.max(header.high_id);
if freed_ids.iter().any(|id| *id >= high_id_limit) {
return Err(invalid(
path,
0,
"cannot free an ID at or above the transaction high ID",
));
}
let root_offset = usize::try_from(selected.root_id)
.ok()
.and_then(|id| id.checked_mul(PAGE_SIZE))
.ok_or_else(|| invalid(path, 0, "ID range root page offset overflow"))?;
let mut root = read_region(
&mut file,
path,
root_offset as u64,
PAGE_SIZE,
root_offset,
"ID range root page is truncated",
)?;
let persisted_unused_ids = validate_range_root(
path,
root_offset,
&root,
selected.root_generation,
header.high_id,
)?;
validate_unused_id_count(path, selected.page_id, header, persisted_unused_ids)?;
let key_count = read_u32_from(&root, 6) as usize;
let mut entries = (0..key_count)
.map(|position| {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let value_offset = VALUE_AREA_OFFSET + position * VALUE_SIZE;
let key = read_u64_from(&root, key_offset);
let value: [u8; VALUE_SIZE] = root[value_offset..value_offset + VALUE_SIZE]
.try_into()
.expect("validated fixed-size ID range value");
(key, value)
})
.collect::<Vec<_>>();
let mut reused_ids = Vec::with_capacity(reuse_count);
for (range_index, value) in &mut entries {
if read_u64_from(value, 0) != header.generation {
for long_index in 0..LONGS_PER_ENTRY {
let commit = read_bitset_long(value, BITSET_COMMIT, long_index);
write_bitset_long(value, BITSET_REUSE, long_index, commit);
write_bitset_long(value, BITSET_RESERVED, long_index, 0);
}
value[..8].copy_from_slice(&header.generation.to_be_bytes());
}
for long_index in 0..LONGS_PER_ENTRY {
let mut commit = read_bitset_long(value, BITSET_COMMIT, long_index);
let mut reuse = read_bitset_long(value, BITSET_REUSE, long_index);
let mut reserved = read_bitset_long(value, BITSET_RESERVED, long_index);
let mut available = commit & reuse & !reserved;
while available != 0 && reused_ids.len() < reuse_count {
let bit_index = available.trailing_zeros() as usize;
let offset_in_range = long_index * u64::BITS as usize + bit_index;
let id = range_index
.checked_mul(EXPECTED_IDS_PER_ENTRY as u64)
.and_then(|base| base.checked_add(offset_in_range as u64))
.ok_or_else(|| invalid(path, root_offset, "reused ID overflow"))?;
let mask = 1_u64 << bit_index;
available &= !mask;
if id >= header.high_id {
continue;
}
reused_ids.push(id);
commit &= !mask;
reuse &= !mask;
reserved &= !mask;
}
write_bitset_long(value, BITSET_COMMIT, long_index, commit);
write_bitset_long(value, BITSET_REUSE, long_index, reuse);
write_bitset_long(value, BITSET_RESERVED, long_index, reserved);
if reused_ids.len() == reuse_count {
break;
}
}
if reused_ids.len() == reuse_count {
break;
}
}
if reused_ids.len() != reuse_count {
return Err(invalid(
path,
root_offset,
"selected reusable ID count changed before commit",
));
}
for id in &freed_ids {
let range_index = *id / EXPECTED_IDS_PER_ENTRY as u64;
let offset_in_range = (*id % EXPECTED_IDS_PER_ENTRY as u64) as usize;
let position = entries.iter().position(|(key, _)| *key == range_index);
let position = if let Some(position) = position {
position
} else {
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&header.generation.to_be_bytes());
entries.push((range_index, value));
entries.len() - 1
};
let value = &mut entries[position].1;
if read_u64_from(value, 0) != header.generation {
for long_index in 0..LONGS_PER_ENTRY {
let commit = read_bitset_long(value, BITSET_COMMIT, long_index);
write_bitset_long(value, BITSET_REUSE, long_index, commit);
write_bitset_long(value, BITSET_RESERVED, long_index, 0);
}
value[..8].copy_from_slice(&header.generation.to_be_bytes());
}
let long_index = offset_in_range / u64::BITS as usize;
let bit_index = offset_in_range % u64::BITS as usize;
let mask = 1_u64 << bit_index;
let commit = read_bitset_long(value, BITSET_COMMIT, long_index);
if commit & mask != 0 {
return Err(invalid(
path,
root_offset,
format!("ID {id} is already unused"),
));
}
write_bitset_long(value, BITSET_COMMIT, long_index, commit | mask);
let reuse = read_bitset_long(value, BITSET_REUSE, long_index);
write_bitset_long(value, BITSET_REUSE, long_index, reuse | mask);
let reserved = read_bitset_long(value, BITSET_RESERVED, long_index);
write_bitset_long(value, BITSET_RESERVED, long_index, reserved & !mask);
}
entries.sort_unstable_by_key(|(key, _)| *key as i64);
if entries.len() > MAX_KEY_COUNT {
return Err(invalid(
path,
root_offset,
"ID range leaf has no capacity for a new key",
));
}
root[6..10].copy_from_slice(&(entries.len() as u32).to_be_bytes());
root[BASE_HEADER_SIZE..VALUE_AREA_OFFSET].fill(0);
root[VALUE_AREA_OFFSET..VALUE_AREA_OFFSET + MAX_KEY_COUNT * VALUE_SIZE].fill(0);
for (position, (key, value)) in entries.into_iter().enumerate() {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
root[key_offset..key_offset + KEY_SIZE].copy_from_slice(&key.to_be_bytes());
let value_offset = VALUE_AREA_OFFSET + position * VALUE_SIZE;
root[value_offset..value_offset + VALUE_SIZE].copy_from_slice(&value);
}
let num_unused_ids = header
.num_unused_ids
.checked_sub(reused_ids.len() as u64)
.and_then(|count| count.checked_add(freed_ids.len() as u64))
.ok_or_else(|| invalid(path, 0, "unused ID count overflow"))?;
Ok(IdTransactionUpdate {
reused_ids,
root_page_offset: root_offset as u64,
root_page: root,
header_patches: [1_u64, 2_u64].map(|page_id| {
(
(state_header_offset(PAGE_SIZE, page_id) + 28) as u64,
num_unused_ids.to_be_bytes().to_vec(),
)
}),
})
}
fn read_tree_header(
path: &Path,
require_range_layout: bool,
) -> Result<(File, usize, TreeState, IdGeneratorHeader)> {
let mut file = File::open(path).map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?;
let file_len = file
.metadata()
.map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?
.len();
if file_len < META_SIZE as u64 {
return Err(invalid(path, 0, "truncated GB+Tree metadata"));
}
let metadata = read_region(
&mut file,
path,
0,
META_SIZE,
0,
"truncated GB+Tree metadata",
)?;
let payload_size = read_u32(path, &metadata, 4)? as usize;
if payload_size < STATE_SIZE + HEADER_LENGTH_SIZE + ID_HEADER_SIZE {
return Err(invalid(path, 4, "invalid GB+Tree payload size"));
}
if require_range_layout {
validate_range_metadata(path, &metadata)?;
}
let required_len = (payload_size as u64)
.checked_mul(3)
.ok_or_else(|| invalid(path, 4, "GB+Tree file length overflow"))?;
if file_len < required_len {
return Err(invalid(
path,
usize::try_from(file_len).unwrap_or(usize::MAX),
"truncated GB+Tree state pages",
));
}
let page_prefix_len = STATE_SIZE + HEADER_LENGTH_SIZE + ID_HEADER_SIZE;
let mut pages = Vec::with_capacity(2);
for page_id in [1_u64, 2_u64] {
let page_offset = (payload_size as u64)
.checked_mul(page_id)
.ok_or_else(|| invalid(path, 0, "state page offset overflow"))?;
pages.push(read_region(
&mut file,
path,
page_offset,
page_prefix_len,
usize::try_from(page_offset).unwrap_or(usize::MAX),
"truncated tree state",
)?);
}
let state_a = read_state(&pages[0], 1);
let state_b = read_state(&pages[1], 2);
let selected = select_newest(path, state_a, state_b)?;
if selected.root_id > selected.last_id {
return Err(invalid(
path,
payload_size * selected.page_id as usize + 8,
"ID range tree root page ID is beyond the last allocated page",
));
}
let selected_index = usize::try_from(selected.page_id - 1).expect("state page is 1 or 2");
let page_offset = (payload_size as u64)
.checked_mul(selected.page_id)
.ok_or_else(|| invalid(path, 0, "state page offset overflow"))?;
let header = read_embedded_header(path, &pages[selected_index], page_offset, file_len)?;
Ok((file, payload_size, selected, header))
}
fn read_region(
file: &mut File,
path: &Path,
offset: u64,
len: usize,
invalid_offset: usize,
truncated_message: &str,
) -> Result<Vec<u8>> {
file.seek(SeekFrom::Start(offset))
.map_err(|source| Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
})?;
let mut bytes = vec![0_u8; len];
let mut actual = 0;
while actual < len {
match file.read(&mut bytes[actual..]) {
Ok(0) => return Err(invalid(path, invalid_offset, truncated_message)),
Ok(count) => actual += count,
Err(source) if source.kind() == std::io::ErrorKind::Interrupted => {}
Err(source) => {
return Err(Neo4jStoreError::Read {
path: path.to_path_buf(),
source,
}
.into());
}
}
}
Ok(bytes)
}
fn read_state(page: &[u8], page_id: u64) -> TreeState {
let state = &page[..STATE_SIZE];
let first = &state[..STATE_FIELDS_SIZE];
let second = &state[STATE_FIELDS_SIZE..];
let stable_generation = u32::from_be_bytes(first[0..4].try_into().expect("fixed field"));
let unstable_generation = u32::from_be_bytes(first[4..8].try_into().expect("fixed field"));
let empty = first[..56].iter().all(|byte| *byte == 0);
TreeState {
page_id,
stable_generation,
unstable_generation,
root_id: u64::from_be_bytes(first[8..16].try_into().expect("fixed field")),
root_generation: u64::from_be_bytes(first[16..24].try_into().expect("fixed field")),
last_id: u64::from_be_bytes(first[24..32].try_into().expect("fixed field")),
clean: first[56] == 1,
valid: first == second && !empty,
}
}
fn validate_range_metadata(path: &Path, bytes: &[u8]) -> Result<()> {
if read_u32(path, bytes, 4)? as usize != PAGE_SIZE {
return Err(invalid(
path,
4,
"ID range tree does not use 8192-byte pages",
));
}
let identifier = bytes
.get(8..16)
.ok_or_else(|| invalid(path, 8, "truncated ID range layout identifier"))?;
if identifier != ID_RANGE_LAYOUT_IDENTIFIER.to_be_bytes() {
return Err(invalid(
path,
8,
"unexpected ID range tree layout identifier",
));
}
Ok(())
}
fn validate_range_tree(
file: &mut File,
path: &Path,
selected: TreeState,
high_id: u64,
) -> Result<u64> {
let mut visited = BTreeSet::new();
let mut previous_leaf_key = None;
validate_range_subtree(
file,
path,
selected.root_id,
selected.root_generation,
selected,
high_id,
&mut visited,
&mut previous_leaf_key,
)
}
#[allow(clippy::too_many_arguments)]
fn validate_range_subtree(
file: &mut File,
path: &Path,
page_id: u64,
expected_generation: u64,
selected: TreeState,
high_id: u64,
visited: &mut BTreeSet<u64>,
previous_leaf_key: &mut Option<u64>,
) -> Result<u64> {
if page_id < 3 || page_id > selected.last_id {
return Err(invalid(
path,
0,
format!("ID range child page ID {page_id} is outside the allocated tree pages"),
));
}
if !visited.insert(page_id) {
return Err(invalid(
path,
0,
format!("ID range tree contains a cycle or duplicate child page {page_id}"),
));
}
let page_offset = usize::try_from(page_id)
.ok()
.and_then(|id| id.checked_mul(PAGE_SIZE))
.ok_or_else(|| invalid(path, 0, "ID range page offset overflow"))?;
let page = read_region(
file,
path,
page_offset as u64,
PAGE_SIZE,
page_offset,
"ID range tree page is truncated",
)?;
if page[0] != TREE_NODE || (page[1] >> 4) & 0x0f != DATA_LAYER {
return Err(invalid(
path,
page_offset,
"ID range tree page is not a data-layer tree node",
));
}
if read_u32_from(&page, 2) as u64 != expected_generation {
return Err(invalid(
path,
page_offset + 2,
"ID range page generation does not match its parent pointer",
));
}
match page[1] & 0x0f {
LEAF_NODE => validate_range_leaf(path, page_offset, &page, high_id, previous_leaf_key),
INTERNAL_NODE => {
let key_count = read_u32_from(&page, 6) as usize;
if key_count > INTERNAL_MAX_KEY_COUNT {
return Err(invalid(
path,
page_offset + 6,
"ID range internal key count exceeds capacity",
));
}
let mut previous_key = None;
for position in 0..key_count {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let key = read_u64_from(&page, key_offset);
i64::try_from(key).map_err(|_| {
invalid(
path,
page_offset + key_offset,
"ID range internal contains a negative key",
)
})?;
if previous_key.is_some_and(|previous| previous >= key) {
return Err(invalid(
path,
page_offset + key_offset,
"ID range internal keys are not strictly increasing",
));
}
previous_key = Some(key);
}
let mut unused_ids = 0_u64;
for position in 0..=key_count {
let pointer_offset = INTERNAL_CHILDREN_OFFSET + position * PAGE_REFERENCE_SIZE;
let (child_id, child_generation) = read_generation_safe_pointer_pair(
path,
page_offset + pointer_offset,
&page[pointer_offset..pointer_offset + PAGE_REFERENCE_SIZE],
selected.stable_generation as u64,
selected.unstable_generation as u64,
)?;
unused_ids = unused_ids
.checked_add(validate_range_subtree(
file,
path,
child_id,
child_generation,
selected,
high_id,
visited,
previous_leaf_key,
)?)
.ok_or_else(|| invalid(path, page_offset, "unused ID count overflow"))?;
}
Ok(unused_ids)
}
_ => Err(invalid(
path,
page_offset + 1,
"ID range page has an unsupported tree-node type",
)),
}
}
fn read_generation_safe_pointer_pair(
path: &Path,
offset: usize,
bytes: &[u8],
stable_generation: u64,
unstable_generation: u64,
) -> Result<(u64, u64)> {
let candidates = [0, GENERATION_SAFE_POINTER_SIZE].map(|slot| {
let generation = read_u32_from(bytes, slot) as u64;
let pointer = read_six_byte_u64(&bytes[slot + 4..slot + 10]);
let stored_checksum = u16::from_be_bytes(bytes[slot + 10..slot + 12].try_into().unwrap());
let checksum_valid = stored_checksum == generation_pointer_checksum(generation, pointer);
let state = if generation == 0 && pointer == 0 {
PointerState::Empty
} else if !checksum_valid || generation == 0 {
PointerState::Broken
} else if generation <= stable_generation {
PointerState::Stable
} else if generation == unstable_generation {
PointerState::Unstable
} else {
PointerState::Crash
};
(generation, pointer, state)
});
let [a, b] = candidates;
let selected = match (a.2, b.2) {
(PointerState::Unstable, PointerState::Stable | PointerState::Empty) => Some(a),
(PointerState::Stable | PointerState::Empty, PointerState::Unstable) => Some(b),
(PointerState::Stable, PointerState::Stable) if a.0 > b.0 => Some(a),
(PointerState::Stable, PointerState::Stable) if b.0 > a.0 => Some(b),
(PointerState::Stable, _) => Some(a),
(_, PointerState::Stable) => Some(b),
_ => None,
};
selected
.map(|(generation, pointer, _)| (pointer, generation))
.ok_or_else(|| {
invalid(
path,
offset,
"ID range child pointer pair has no readable slot",
)
})
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum PointerState {
Stable,
Unstable,
Crash,
Broken,
Empty,
}
fn read_six_byte_u64(bytes: &[u8]) -> u64 {
let mut value = [0_u8; 8];
value[2..].copy_from_slice(bytes);
u64::from_be_bytes(value)
}
fn generation_pointer_checksum(generation: u64, pointer: u64) -> u16 {
generation as u16
^ (generation >> 16) as u16
^ pointer as u16
^ (pointer >> 16) as u16
^ (pointer >> 32) as u16
}
fn validate_range_root(
path: &Path,
root_offset: usize,
root: &[u8],
root_generation: u64,
high_id: u64,
) -> Result<u64> {
if root[0] != TREE_NODE || root[1] & 0x0f != LEAF_NODE || (root[1] >> 4) & 0x0f != DATA_LAYER {
return Err(invalid(
path,
root_offset,
"ID range tree root is not a single data leaf",
));
}
if read_u32_from(root, 2) as u64 != root_generation {
return Err(invalid(
path,
root_offset + 2,
"ID range root generation does not match state",
));
}
let key_count = read_u32_from(root, 6) as usize;
if key_count > MAX_KEY_COUNT {
return Err(invalid(
path,
root_offset + 6,
"ID range leaf key count exceeds capacity",
));
}
let mut previous_key = None;
validate_range_leaf(path, root_offset, root, high_id, &mut previous_key)
}
fn validate_range_leaf(
path: &Path,
page_offset: usize,
page: &[u8],
high_id: u64,
previous_key: &mut Option<u64>,
) -> Result<u64> {
let key_count = read_u32_from(page, 6) as usize;
if key_count > MAX_KEY_COUNT {
return Err(invalid(
path,
page_offset + 6,
"ID range leaf key count exceeds capacity",
));
}
let mut persisted_unused_ids = 0_u64;
for position in 0..key_count {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
let key = read_u64_from(page, key_offset);
i64::try_from(key).map_err(|_| {
invalid(
path,
page_offset + key_offset,
"ID range leaf contains a negative range key",
)
})?;
if previous_key.is_some_and(|previous| previous >= key) {
return Err(invalid(
path,
page_offset + key_offset,
"ID range leaf keys are not strictly increasing globally",
));
}
let range_start = key
.checked_mul(EXPECTED_IDS_PER_ENTRY as u64)
.ok_or_else(|| {
invalid(
path,
page_offset + key_offset,
"ID range leaf key overflows the ID space",
)
})?;
if range_start >= high_id {
return Err(invalid(
path,
page_offset + key_offset,
"ID range leaf key starts at or above the high ID",
));
}
let valid_ids = (high_id - range_start).min(EXPECTED_IDS_PER_ENTRY as u64) as usize;
let value_offset = VALUE_AREA_OFFSET + position * VALUE_SIZE;
let value = &page[value_offset..value_offset + VALUE_SIZE];
for long_index in 0..LONGS_PER_ENTRY {
let valid_bits = valid_ids
.saturating_sub(long_index * u64::BITS as usize)
.min(u64::BITS as usize);
let valid_mask = match valid_bits {
0 => 0,
bits if bits == u64::BITS as usize => u64::MAX,
bits => (1_u64 << bits) - 1,
};
for bitset in 0..BITSET_COUNT {
if read_bitset_long(value, bitset, long_index) & !valid_mask != 0 {
return Err(invalid(
path,
page_offset + value_offset + bitset_offset(bitset, long_index),
"ID range leaf contains bits at or above the high ID",
));
}
}
persisted_unused_ids +=
read_bitset_long(value, BITSET_COMMIT, long_index).count_ones() as u64;
}
*previous_key = Some(key);
}
Ok(persisted_unused_ids)
}
fn validate_unused_id_count(
path: &Path,
state_page_id: u64,
header: IdGeneratorHeader,
persisted_unused_ids: u64,
) -> Result<()> {
if header.num_unused_ids != persisted_unused_ids {
return Err(invalid(
path,
state_header_offset(PAGE_SIZE, state_page_id) + 28,
format!(
"ID header unused count {} does not match {persisted_unused_ids} persisted COMMIT bits",
header.num_unused_ids
),
));
}
Ok(())
}
fn bitset_offset(bitset: usize, long_index: usize) -> usize {
8 + (bitset * LONGS_PER_ENTRY + long_index) * 8
}
fn read_bitset_long(value: &[u8], bitset: usize, long_index: usize) -> u64 {
read_u64_from(value, bitset_offset(bitset, long_index))
}
fn write_bitset_long(value: &mut [u8], bitset: usize, long_index: usize, bits: u64) {
let offset = bitset_offset(bitset, long_index);
value[offset..offset + 8].copy_from_slice(&bits.to_be_bytes());
}
fn read_u32_from(bytes: &[u8], offset: usize) -> u32 {
u32::from_be_bytes(
bytes[offset..offset + 4]
.try_into()
.expect("validated field"),
)
}
fn read_u64_from(bytes: &[u8], offset: usize) -> u64 {
u64::from_be_bytes(
bytes[offset..offset + 8]
.try_into()
.expect("validated field"),
)
}
fn select_newest(path: &Path, a: TreeState, b: TreeState) -> Result<TreeState> {
match (a.valid, b.valid) {
(true, false) => Ok(a),
(false, true) => Ok(b),
(false, false) => Err(invalid(path, 0, "both GB+Tree state pages are invalid")),
(true, true)
if a.stable_generation == b.stable_generation
&& a.unstable_generation == b.unstable_generation
&& a.clean != b.clean =>
{
Ok(if a.clean { a } else { b })
}
(true, true)
if a.stable_generation >= b.stable_generation
&& a.unstable_generation > b.unstable_generation =>
{
Ok(a)
}
(true, true)
if b.stable_generation >= a.stable_generation
&& b.unstable_generation > a.unstable_generation =>
{
Ok(b)
}
_ => Err(invalid(
path,
0,
"GB+Tree state generations do not identify a newest page",
)),
}
}
fn read_embedded_header(
path: &Path,
page: &[u8],
page_offset: u64,
file_len: u64,
) -> Result<IdGeneratorHeader> {
let relative_offset = STATE_SIZE + HEADER_LENGTH_SIZE;
let absolute_offset = page_offset
.checked_add(relative_offset as u64)
.ok_or_else(|| invalid(path, 0, "ID header offset overflow"))?;
let header_len = read_u32(path, page, STATE_SIZE)? as usize;
if header_len < ID_HEADER_SIZE {
return Err(invalid(
path,
usize::try_from(page_offset + STATE_SIZE as u64).unwrap_or(usize::MAX),
"truncated ID header",
));
}
let header_end = absolute_offset
.checked_add(header_len as u64)
.ok_or_else(|| invalid(path, 0, "ID header end offset overflow"))?;
if header_end > file_len {
return Err(invalid(
path,
usize::try_from(absolute_offset).unwrap_or(usize::MAX),
"ID header extends beyond file",
));
}
let header = &page[relative_offset..relative_offset + ID_HEADER_SIZE];
Ok(IdGeneratorHeader {
high_id: u64::from_be_bytes(header[0..8].try_into().expect("fixed field")),
highest_written_id: u64::from_be_bytes(header[8..16].try_into().expect("fixed field")),
generation: u64::from_be_bytes(header[16..24].try_into().expect("fixed field")),
ids_per_entry: u32::from_be_bytes(header[24..28].try_into().expect("fixed field")),
num_unused_ids: u64::from_be_bytes(header[28..36].try_into().expect("fixed field")),
state_header_offsets: [0; 2],
})
}
fn state_header_offset(page_size: usize, page_id: u64) -> usize {
page_size * page_id as usize + STATE_SIZE + HEADER_LENGTH_SIZE
}
fn read_u32(path: &Path, bytes: &[u8], offset: usize) -> Result<u32> {
let value = bytes
.get(offset..offset + 4)
.ok_or_else(|| invalid(path, offset, "truncated 32-bit field"))?;
Ok(u32::from_be_bytes(value.try_into().expect("fixed field")))
}
fn invalid(path: &Path, offset: usize, message: impl Into<String>) -> crate::Error {
Neo4jStoreError::InvalidMetadata {
path: path.to_path_buf(),
offset: offset as u64,
message: message.into(),
}
.into()
}
fn unsupported(path: &Path, message: impl Into<String>) -> crate::Error {
Neo4jStoreError::UnsupportedWritableStore {
path: PathBuf::from(path),
message: message.into(),
}
.into()
}
#[cfg(test)]
mod tests {
use std::fs;
use super::*;
fn write_state(bytes: &mut [u8], page_size: usize, page_id: usize, unstable: u32) {
let offset = page_size * page_id;
let mut fields = [0_u8; STATE_FIELDS_SIZE];
fields[0..4].copy_from_slice(&4_u32.to_be_bytes());
fields[4..8].copy_from_slice(&unstable.to_be_bytes());
fields[8..16].copy_from_slice(&3_u64.to_be_bytes());
fields[24..32].copy_from_slice(&3_u64.to_be_bytes());
fields[56] = 1;
bytes[offset..offset + STATE_FIELDS_SIZE].copy_from_slice(&fields);
bytes[offset + STATE_FIELDS_SIZE..offset + STATE_SIZE].copy_from_slice(&fields);
let header_offset = offset + STATE_SIZE;
bytes[header_offset..header_offset + 4].copy_from_slice(&36_u32.to_be_bytes());
let header = &mut bytes[header_offset + 4..header_offset + 40];
header[0..8].copy_from_slice(&133_u64.to_be_bytes());
header[8..16].copy_from_slice(&132_u64.to_be_bytes());
header[16..24].copy_from_slice(&2_u64.to_be_bytes());
header[24..28].copy_from_slice(&128_u32.to_be_bytes());
header[28..36].copy_from_slice(&0_u64.to_be_bytes());
}
fn id_range_file(entries: &[(u64, [u8; VALUE_SIZE])]) -> Vec<u8> {
let mut bytes = vec![0_u8; PAGE_SIZE * 4];
bytes[4..8].copy_from_slice(&(PAGE_SIZE as u32).to_be_bytes());
bytes[8..16].copy_from_slice(&ID_RANGE_LAYOUT_IDENTIFIER.to_be_bytes());
write_state(&mut bytes, PAGE_SIZE, 1, 5);
write_state(&mut bytes, PAGE_SIZE, 2, 4);
for page_id in [1, 2] {
let offset = PAGE_SIZE * page_id;
for copy in [0, STATE_FIELDS_SIZE] {
bytes[offset + copy + 16..offset + copy + 24].copy_from_slice(&3_u64.to_be_bytes());
}
}
let root = &mut bytes[3 * PAGE_SIZE..4 * PAGE_SIZE];
root[0] = TREE_NODE;
root[1] = LEAF_NODE;
root[2..6].copy_from_slice(&3_u32.to_be_bytes());
root[6..10].copy_from_slice(&(entries.len() as u32).to_be_bytes());
for (position, (key, value)) in entries.iter().enumerate() {
let key_offset = BASE_HEADER_SIZE + position * KEY_SIZE;
root[key_offset..key_offset + KEY_SIZE].copy_from_slice(&key.to_be_bytes());
let value_offset = VALUE_AREA_OFFSET + position * VALUE_SIZE;
root[value_offset..value_offset + VALUE_SIZE].copy_from_slice(value);
}
bytes
}
fn write_generation_safe_pointer(bytes: &mut [u8], generation: u32, pointer: u64) {
bytes[..4].copy_from_slice(&generation.to_be_bytes());
bytes[4..10].copy_from_slice(&pointer.to_be_bytes()[2..]);
bytes[10..12].copy_from_slice(
&generation_pointer_checksum(generation as u64, pointer).to_be_bytes(),
);
}
fn two_leaf_id_range_file() -> Vec<u8> {
let mut bytes = id_range_file(&[]);
bytes.resize(PAGE_SIZE * 6, 0);
for page_id in [1, 2] {
let state_offset = PAGE_SIZE * page_id;
for copy in [0, STATE_FIELDS_SIZE] {
bytes[state_offset + copy + 8..state_offset + copy + 16]
.copy_from_slice(&5_u64.to_be_bytes());
bytes[state_offset + copy + 16..state_offset + copy + 24]
.copy_from_slice(&3_u64.to_be_bytes());
bytes[state_offset + copy + 24..state_offset + copy + 32]
.copy_from_slice(&5_u64.to_be_bytes());
}
}
for (page_id, key) in [(3, 0_u64), (4, 1_u64)] {
let leaf = &mut bytes[page_id * PAGE_SIZE..(page_id + 1) * PAGE_SIZE];
leaf[0] = TREE_NODE;
leaf[1] = LEAF_NODE;
leaf[2..6].copy_from_slice(&3_u32.to_be_bytes());
leaf[6..10].copy_from_slice(&1_u32.to_be_bytes());
leaf[BASE_HEADER_SIZE..BASE_HEADER_SIZE + KEY_SIZE].copy_from_slice(&key.to_be_bytes());
leaf[VALUE_AREA_OFFSET..VALUE_AREA_OFFSET + 8].copy_from_slice(&2_u64.to_be_bytes());
}
let root = &mut bytes[5 * PAGE_SIZE..6 * PAGE_SIZE];
root[0] = TREE_NODE;
root[1] = INTERNAL_NODE;
root[2..6].copy_from_slice(&3_u32.to_be_bytes());
root[6..10].copy_from_slice(&1_u32.to_be_bytes());
root[BASE_HEADER_SIZE..BASE_HEADER_SIZE + KEY_SIZE].copy_from_slice(&1_u64.to_be_bytes());
for (position, child_id) in [3_u64, 4].into_iter().enumerate() {
let pointer_offset = INTERNAL_CHILDREN_OFFSET + position * PAGE_REFERENCE_SIZE;
write_generation_safe_pointer(
&mut root[pointer_offset..pointer_offset + GENERATION_SAFE_POINTER_SIZE],
3,
child_id,
);
}
bytes
}
fn set_num_unused_ids(bytes: &mut [u8], count: u64) {
for page_id in [1, 2] {
let offset = state_header_offset(PAGE_SIZE, page_id) + 28;
bytes[offset..offset + 8].copy_from_slice(&count.to_be_bytes());
}
}
#[test]
fn reads_the_newest_valid_id_generator_header() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let page_size = 512;
let mut bytes = vec![0_u8; page_size * 3];
bytes[4..8].copy_from_slice(&(page_size as u32).to_be_bytes());
write_state(&mut bytes, page_size, 1, 5);
write_state(&mut bytes, page_size, 2, 4);
fs::write(&path, bytes).unwrap();
let header = read(&path).unwrap();
assert_eq!(header.high_id, 133);
assert_eq!(header.highest_written_id, 132);
assert_eq!(header.generation, 2);
assert_eq!(header.ids_per_entry, 128);
assert_eq!(header.state_header_offsets, [630, 1142]);
}
#[test]
fn reads_headers_and_range_pages_without_loading_a_sparse_file() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
fs::write(&path, id_range_file(&[])).unwrap();
let file = fs::OpenOptions::new().write(true).open(&path).unwrap();
file.set_len(1_u64 << 40).unwrap();
let header = read(&path).unwrap();
assert_eq!(header.high_id, 133);
let update = prepare_mark_deleted_and_free(&path, &[4]).unwrap();
assert_eq!(update.root_page.len(), PAGE_SIZE);
}
#[test]
fn writable_validation_rejects_invalid_range_metadata_and_root_keys() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut bytes = id_range_file(&[]);
bytes[8] ^= 1;
fs::write(&path, bytes).unwrap();
let error = validate_writable(directory.path(), "records.db", 133).unwrap_err();
assert!(error.to_string().contains("layout identifier"));
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&2_u64.to_be_bytes());
fs::write(&path, id_range_file(&[(0, value), (0, value)])).unwrap();
let error = validate_writable(directory.path(), "records.db", 133).unwrap_err();
assert!(
error.to_string().contains("not strictly increasing"),
"{error}"
);
}
#[test]
fn validates_a_two_leaf_range_tree_but_keeps_mutation_leaf_only() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let bytes = two_leaf_id_range_file();
fs::write(&path, &bytes).unwrap();
let header = validate_writable(directory.path(), "records.db", 133).unwrap();
assert_eq!(header.high_id, 133);
let error = prepare_take_free_ids(&path, 1).unwrap_err();
assert!(error
.to_string()
.contains("ID range tree root is not a single data leaf"));
let mut duplicate_child = bytes.clone();
let second_pointer = 5 * PAGE_SIZE + INTERNAL_CHILDREN_OFFSET + PAGE_REFERENCE_SIZE;
write_generation_safe_pointer(
&mut duplicate_child[second_pointer..second_pointer + GENERATION_SAFE_POINTER_SIZE],
3,
3,
);
fs::write(&path, duplicate_child).unwrap();
let error = validate_writable(directory.path(), "records.db", 133).unwrap_err();
assert!(error.to_string().contains("cycle or duplicate"), "{error}");
let mut unordered = bytes.clone();
let second_leaf_key = 4 * PAGE_SIZE + BASE_HEADER_SIZE;
unordered[second_leaf_key..second_leaf_key + KEY_SIZE]
.copy_from_slice(&0_u64.to_be_bytes());
fs::write(&path, unordered).unwrap();
let error = validate_writable(directory.path(), "records.db", 133).unwrap_err();
assert!(
error
.to_string()
.contains("not strictly increasing globally"),
"{error}"
);
let mut corrupt = bytes;
corrupt[5 * PAGE_SIZE + INTERNAL_CHILDREN_OFFSET + 10] ^= 1;
fs::write(&path, corrupt).unwrap();
let error = validate_writable(directory.path(), "records.db", 133).unwrap_err();
assert!(error.to_string().contains("no readable slot"), "{error}");
}
#[test]
fn rejects_a_root_beyond_the_last_allocated_range_page() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut bytes = id_range_file(&[]);
let selected_state_offset = PAGE_SIZE;
for copy in [0, STATE_FIELDS_SIZE] {
bytes[selected_state_offset + copy + 8..selected_state_offset + copy + 16]
.copy_from_slice(&4_u64.to_be_bytes());
}
fs::write(&path, bytes).unwrap();
let error = validate_writable(directory.path(), "records.db", 133).unwrap_err();
assert!(error.to_string().contains("last allocated page"));
}
#[test]
fn rejects_unused_count_that_disagrees_with_commit_bits() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&2_u64.to_be_bytes());
write_bitset_long(&mut value, BITSET_COMMIT, 0, 1 << 5);
let mut bytes = id_range_file(&[(0, value)]);
fs::write(&path, &bytes).unwrap();
let error = validate_writable(directory.path(), "records.db", 133).unwrap_err();
assert!(error
.to_string()
.contains("unused count 0 does not match 1 persisted COMMIT bits"));
set_num_unused_ids(&mut bytes, 2);
fs::write(&path, bytes).unwrap();
let error = prepare_take_free_ids(&path, 1).unwrap_err();
assert!(error
.to_string()
.contains("unused count 2 does not match 1 persisted COMMIT bits"));
}
#[test]
fn unused_count_includes_current_generation_ids_that_are_not_reusable() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&2_u64.to_be_bytes());
write_bitset_long(&mut value, BITSET_COMMIT, 0, 1 << 5);
write_bitset_long(&mut value, BITSET_RESERVED, 0, 1 << 5);
let mut bytes = id_range_file(&[(0, value)]);
set_num_unused_ids(&mut bytes, 1);
fs::write(&path, bytes).unwrap();
assert!(prepare_take_free_ids(&path, 1).unwrap().is_none());
}
#[test]
fn rejects_invalid_state_copies() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let page_size = 512;
let mut bytes = vec![0_u8; page_size * 3];
bytes[4..8].copy_from_slice(&(page_size as u32).to_be_bytes());
write_state(&mut bytes, page_size, 1, 5);
write_state(&mut bytes, page_size, 2, 4);
bytes[page_size + STATE_FIELDS_SIZE] ^= 1;
bytes[page_size * 2 + STATE_FIELDS_SIZE] ^= 1;
fs::write(&path, bytes).unwrap();
assert!(read(&path)
.unwrap_err()
.to_string()
.contains("both GB+Tree state pages are invalid"));
}
#[test]
fn encodes_append_only_high_id_updates_for_both_state_pages() {
let header = IdGeneratorHeader {
high_id: 133,
highest_written_id: 132,
generation: 2,
ids_per_entry: 128,
num_unused_ids: 0,
state_header_offsets: [8310, 16502],
};
let allocation = allocate_high_ids(header, 2).unwrap();
let patches = allocation.header_patches;
assert_eq!(allocation.first_id, 133);
assert_eq!(patches[0].0, 8310);
assert_eq!(patches[1].0, 16502);
assert_eq!(
u64::from_be_bytes(patches[0].1[0..8].try_into().unwrap()),
135
);
assert_eq!(
u64::from_be_bytes(patches[0].1[8..16].try_into().unwrap()),
134
);
assert_eq!(patches[0].1, patches[1].1);
}
#[test]
fn inserts_deleted_and_free_bits_in_the_correct_range_slot() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
fs::write(&path, id_range_file(&[])).unwrap();
let update = prepare_mark_deleted_and_free(&path, &[70]).unwrap();
assert_eq!(update.root_page_offset, (3 * PAGE_SIZE) as u64);
assert_eq!(read_u32_from(&update.root_page, 6), 1);
assert_eq!(read_u64_from(&update.root_page, BASE_HEADER_SIZE), 0);
let value = &update.root_page[VALUE_AREA_OFFSET..VALUE_AREA_OFFSET + VALUE_SIZE];
assert_eq!(read_u64_from(value, 0), 2);
assert_eq!(read_bitset_long(value, BITSET_COMMIT, 0), 0);
assert_eq!(read_bitset_long(value, BITSET_COMMIT, 1), 1 << 6);
assert_eq!(read_bitset_long(value, BITSET_REUSE, 1), 1 << 6);
assert_eq!(read_bitset_long(value, BITSET_RESERVED, 1), 0);
assert_eq!(update.header_patches[0].1, 1_u64.to_be_bytes());
assert_eq!(update.header_patches[1].1, 1_u64.to_be_bytes());
}
#[test]
fn normalizes_an_old_range_and_rejects_freeing_an_unused_id() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&1_u64.to_be_bytes());
write_bitset_long(&mut value, BITSET_COMMIT, 0, 1 << 5);
write_bitset_long(&mut value, BITSET_RESERVED, 0, 1 << 5);
let mut bytes = id_range_file(&[(0, value)]);
set_num_unused_ids(&mut bytes, 1);
fs::write(&path, bytes).unwrap();
let update = prepare_mark_deleted_and_free(&path, &[6]).unwrap();
let value = &update.root_page[VALUE_AREA_OFFSET..VALUE_AREA_OFFSET + VALUE_SIZE];
assert_eq!(read_u64_from(value, 0), 2);
assert_eq!(
read_bitset_long(value, BITSET_COMMIT, 0),
(1 << 5) | (1 << 6)
);
assert_eq!(
read_bitset_long(value, BITSET_REUSE, 0),
(1 << 5) | (1 << 6)
);
assert_eq!(read_bitset_long(value, BITSET_RESERVED, 0), 0);
let mut bytes = id_range_file(&[(0, value.try_into().unwrap())]);
set_num_unused_ids(&mut bytes, 2);
fs::write(&path, bytes).unwrap();
assert!(prepare_mark_deleted_and_free(&path, &[6])
.unwrap_err()
.to_string()
.contains("already unused"));
}
#[test]
fn rejects_duplicate_and_out_of_range_ids() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
fs::write(&path, id_range_file(&[])).unwrap();
assert!(prepare_mark_deleted_and_free(&path, &[4, 4])
.unwrap_err()
.to_string()
.contains("duplicate"));
assert!(prepare_mark_deleted_and_free(&path, &[133])
.unwrap_err()
.to_string()
.contains("high ID"));
}
#[test]
fn rejects_duplicate_descending_and_negative_range_keys() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&2_u64.to_be_bytes());
for entries in [
vec![(0, value), (0, value)],
vec![(1, value), (0, value)],
vec![(u64::MAX, value)],
] {
fs::write(&path, id_range_file(&entries)).unwrap();
let error = prepare_mark_deleted_and_free(&path, &[4]).unwrap_err();
assert!(error.to_string().contains("ID range leaf"));
}
}
#[test]
fn rejects_range_keys_and_bits_at_or_above_the_high_id() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&2_u64.to_be_bytes());
fs::write(&path, id_range_file(&[(2, value)])).unwrap();
let error = prepare_mark_deleted_and_free(&path, &[4]).unwrap_err();
assert!(error.to_string().contains("at or above the high ID"));
write_bitset_long(&mut value, BITSET_COMMIT, 0, 1 << 5);
fs::write(&path, id_range_file(&[(1, value)])).unwrap();
let error = prepare_mark_deleted_and_free(&path, &[4]).unwrap_err();
assert!(error.to_string().contains("bits at or above the high ID"));
}
#[test]
fn takes_reusable_ids_and_clears_their_range_bits() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&2_u64.to_be_bytes());
write_bitset_long(&mut value, BITSET_COMMIT, 0, (1 << 5) | (1 << 6));
write_bitset_long(&mut value, BITSET_REUSE, 0, (1 << 5) | (1 << 6));
write_bitset_long(&mut value, BITSET_RESERVED, 0, 1 << 6);
write_bitset_long(&mut value, BITSET_COMMIT, 1, 1 << 6);
write_bitset_long(&mut value, BITSET_REUSE, 1, 1 << 6);
let mut bytes = id_range_file(&[(0, value)]);
set_num_unused_ids(&mut bytes, 3);
fs::write(&path, bytes).unwrap();
let update = prepare_take_free_ids(&path, 2).unwrap().unwrap();
assert_eq!(update.ids, [5, 70]);
let value = &update.root_page[VALUE_AREA_OFFSET..VALUE_AREA_OFFSET + VALUE_SIZE];
assert_eq!(read_bitset_long(value, BITSET_COMMIT, 0), 1 << 6);
assert_eq!(read_bitset_long(value, BITSET_REUSE, 0), 1 << 6);
assert_eq!(read_bitset_long(value, BITSET_RESERVED, 0), 1 << 6);
assert_eq!(read_bitset_long(value, BITSET_COMMIT, 1), 0);
assert_eq!(read_bitset_long(value, BITSET_REUSE, 1), 0);
assert_eq!(update.header_patches[0].1, 1_u64.to_be_bytes());
assert_eq!(update.header_patches[1].1, 1_u64.to_be_bytes());
}
#[test]
fn combines_reuse_free_and_new_high_id_free_in_one_update() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&2_u64.to_be_bytes());
write_bitset_long(&mut value, BITSET_COMMIT, 0, (1 << 5) | (1 << 6));
write_bitset_long(&mut value, BITSET_REUSE, 0, (1 << 5) | (1 << 6));
let mut bytes = id_range_file(&[(0, value)]);
set_num_unused_ids(&mut bytes, 2);
fs::write(&path, bytes).unwrap();
let update = prepare_reuse_and_free_ids(&path, 1, &[5, 70, 133], 134).unwrap();
assert_eq!(update.reused_ids, [5]);
assert_eq!(update.header_patches[0].1, 4_u64.to_be_bytes());
let first = &update.root_page[VALUE_AREA_OFFSET..VALUE_AREA_OFFSET + VALUE_SIZE];
assert_eq!(
read_bitset_long(first, BITSET_COMMIT, 0),
(1 << 5) | (1 << 6)
);
assert_eq!(read_bitset_long(first, BITSET_COMMIT, 1), 1 << 6);
let second =
&update.root_page[VALUE_AREA_OFFSET + VALUE_SIZE..VALUE_AREA_OFFSET + 2 * VALUE_SIZE];
assert_eq!(read_u64_from(second, 0), 2);
assert_eq!(read_bitset_long(second, BITSET_COMMIT, 0), 1 << 5);
}
#[test]
fn normalizes_an_old_range_before_reusing_an_id() {
let directory = tempfile::tempdir().unwrap();
let path = directory.path().join("records.db.id");
let mut value = [0_u8; VALUE_SIZE];
value[..8].copy_from_slice(&1_u64.to_be_bytes());
write_bitset_long(&mut value, BITSET_COMMIT, 0, 1 << 9);
write_bitset_long(&mut value, BITSET_RESERVED, 0, 1 << 9);
let mut bytes = id_range_file(&[(0, value)]);
set_num_unused_ids(&mut bytes, 1);
fs::write(&path, bytes).unwrap();
let update = prepare_take_free_ids(&path, 1).unwrap().unwrap();
assert_eq!(update.ids, [9]);
let value = &update.root_page[VALUE_AREA_OFFSET..VALUE_AREA_OFFSET + VALUE_SIZE];
assert_eq!(read_u64_from(value, 0), 2);
assert_eq!(read_bitset_long(value, BITSET_COMMIT, 0), 0);
assert_eq!(read_bitset_long(value, BITSET_REUSE, 0), 0);
assert_eq!(read_bitset_long(value, BITSET_RESERVED, 0), 0);
}
#[test]
#[ignore = "requires NEO4J_REAL_FIXTURE generated by tools/neo4j-fixture-generator"]
fn reads_a_real_property_id_generator() {
let database = std::env::var("NEO4J_REAL_FIXTURE").unwrap();
let path = Path::new(&database).join("neostore.propertystore.db.id");
let header = read(&path).unwrap();
assert_eq!(header.ids_per_entry, 128);
assert_eq!(header.highest_written_id + 1, header.high_id);
assert_eq!(header.high_id, 133);
let string_path = Path::new(&database).join("neostore.propertystore.db.strings.id");
let string_header = read(&string_path).unwrap();
assert_eq!(string_header.ids_per_entry, 128);
assert!(string_header.high_id > 0);
assert!(string_header.highest_written_id < string_header.high_id);
let array_path = Path::new(&database).join("neostore.propertystore.db.arrays.id");
let array_header = read(&array_path).unwrap();
assert_eq!(array_header.ids_per_entry, 128);
assert!(array_header.high_id > 0);
assert!(array_header.highest_written_id < array_header.high_id);
for store in [
"neostore.propertystore.db.index",
"neostore.propertystore.db.index.keys",
] {
let token_path = Path::new(&database).join(format!("{store}.id"));
let token_header = read(&token_path).unwrap();
assert_eq!(token_header.ids_per_entry, 128);
assert!(token_header.high_id > 0);
assert!(token_header.highest_written_id < token_header.high_id);
}
}
}