use std::{
cmp::min,
collections::{btree_map, BTreeMap, BTreeSet},
};
use devicemapper::Sectors;
use crate::{
engine::{
strat_engine::{backstore::transaction::RequestTransaction, metadata::BlockdevSize},
types::DevUuid,
},
stratis::{StratisError, StratisResult},
};
#[derive(Debug, Clone)]
pub struct PerDevSegments {
limit: Sectors,
used: BTreeMap<Sectors, Sectors>,
}
impl PerDevSegments {
pub fn new(limit: Sectors) -> PerDevSegments {
PerDevSegments {
limit,
used: BTreeMap::new(),
}
}
pub fn len(&self) -> usize {
self.used.len()
}
pub fn sum(&self) -> Sectors {
self.used.values().cloned().sum()
}
pub fn limit(&self) -> Sectors {
self.limit
}
pub fn iter(&self) -> Iter<'_> {
Iter {
items: self.used.iter(),
}
}
fn locate_prev_and_next(&self, value: Sectors) -> (Option<Sectors>, Option<Sectors>) {
let mut prev = None;
let mut next = None;
for &key in self.used.keys() {
if value >= key {
prev = Some(key);
}
if value <= key {
next = Some(key);
break;
}
}
(prev, next)
}
#[allow(clippy::type_complexity)]
fn insertion_result(
&self,
prev: Option<Sectors>,
next: Option<Sectors>,
range: &(Sectors, Sectors),
) -> StratisResult<(
Option<(Sectors, Sectors)>,
(Sectors, Sectors),
Option<(Sectors, Sectors)>,
)> {
let &(start, len) = range;
assert!(len != Sectors(0));
let end = if let Some(end) = start.checked_add(len) {
end
} else {
return Err(StratisError::Msg(format!(
"range ({}, {}) extends beyond maximum possible size",
start, len
)));
};
if end > self.limit {
return Err(StratisError::Msg(format!(
"range ({}, {}) extends beyond limit {}",
start, len, self.limit
)));
};
let res: (Sectors, Sectors) = (start, len);
let (lhs, (new_start, new_len)) = if let Some(prev) = prev {
let prev_len: Sectors = *self.used.get(&prev).expect("see precondition");
if prev + prev_len > start {
return Err(StratisError::Msg(format!(
"range to add ({}, {}) overlaps previous range ({}, {})",
start, len, prev, prev_len
)));
}
if prev + prev_len == start {
(None, (prev, prev_len + len))
} else {
(Some((prev, prev_len)), res)
}
} else {
(None, res)
};
let (res, rhs) = if let Some(next) = next {
if new_start + new_len > next {
return Err(StratisError::Msg(format!(
"range to add ({}, {}) overlaps subsequent range starting at {}",
new_start, new_len, next
)));
}
let next_len: Sectors = *self.used.get(&next).expect("see precondition");
if new_start + new_len == next {
((new_start, new_len + next_len), None)
} else {
((new_start, new_len), Some((next, next_len)))
}
} else {
((new_start, new_len), None)
};
Ok((lhs, res, rhs))
}
pub fn insert(&mut self, range: &(Sectors, Sectors)) -> StratisResult<()> {
let &(start, len) = range;
if start > self.limit {
return Err(StratisError::Msg(format!(
"value specified for start of range, {}, exceeds limit, {}",
start, self.limit
)));
}
if len == Sectors(0) {
return Ok(());
}
let (prev, next) = self.locate_prev_and_next(start);
let (prev_res, (new_start, new_len), next_res) =
self.insertion_result(prev, next, range)?;
if let Some(prev) = prev {
if prev_res.is_none() {
self.used.remove(&prev);
}
}
if let Some(next) = next {
if next_res.is_none() {
self.used.remove(&next);
}
}
assert!(
self.used.insert(new_start, new_len).is_none(),
"removed in previous steps if present"
);
Ok(())
}
pub fn insert_all(&mut self, ranges: &[(Sectors, Sectors)]) -> StratisResult<()> {
let mut temp = PerDevSegments::new(self.limit);
for range in ranges.iter() {
temp.insert(range)?;
}
let union = self.union(&temp)?;
self.used = union.used;
Ok(())
}
pub fn union(&self, other: &PerDevSegments) -> StratisResult<PerDevSegments> {
if self.limit != other.limit {
return Err(StratisError::Msg(
"limits differ between PerDevSegments structs, can not do a union".into(),
));
}
let keys = self
.used
.keys()
.chain(other.used.keys())
.cloned()
.collect::<BTreeSet<Sectors>>();
let mut union = PerDevSegments::new(self.limit);
for key in keys.iter().rev() {
if let Some(val) = self.used.get(key) {
union.insert(&(*key, *val))?;
}
if let Some(val) = other.used.get(key) {
union.insert(&(*key, *val))?;
}
}
Ok(union)
}
pub fn complement(&self) -> PerDevSegments {
let mut free = BTreeMap::new();
let mut prev_end = Sectors(0);
for (&start, &len) in self.used.iter() {
let range = start - prev_end;
if range != Sectors(0) {
free.insert(prev_end, range);
}
prev_end = start + len; }
if prev_end < self.limit {
free.insert(prev_end, self.limit - prev_end);
}
PerDevSegments {
limit: self.limit,
used: free,
}
}
#[cfg(test)]
fn invariant(&self) {
assert!(self.used.values().all(|&l| l != Sectors(0)));
assert!(self
.used
.iter()
.collect::<Vec<_>>()
.windows(2)
.all(|l| *l[0].0 + *l[0].1 < *l[1].0));
assert!(self
.used
.iter()
.rev()
.next()
.map(|(s, l)| *s + *l <= self.limit)
.unwrap_or(true));
let same = self.complement().complement();
assert_eq!(same.limit, self.limit);
assert_eq!(same.used, self.used);
}
}
pub struct Iter<'a> {
items: btree_map::Iter<'a, Sectors, Sectors>,
}
impl<'a> Iterator for Iter<'a> {
type Item = (&'a Sectors, &'a Sectors);
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.items.next()
}
}
#[derive(Debug)]
pub struct RangeAllocator {
segments: PerDevSegments,
}
impl RangeAllocator {
pub fn new(
limit: BlockdevSize,
initial_used: &[(Sectors, Sectors)],
) -> StratisResult<RangeAllocator> {
let mut segments = PerDevSegments::new(limit.sectors());
segments.insert_all(initial_used)?;
Ok(RangeAllocator { segments })
}
#[cfg(test)]
pub fn size(&self) -> BlockdevSize {
BlockdevSize::new(self.segments.limit())
}
pub fn available(&self) -> Sectors {
self.segments.limit() - self.used()
}
pub fn used(&self) -> Sectors {
self.segments.sum()
}
pub fn request(
&self,
uuid: DevUuid,
amount: Sectors,
transaction: &RequestTransaction,
) -> StratisResult<PerDevSegments> {
let trans_used = transaction
.get_blockdevmgr()
.into_iter()
.filter_map(|seg| {
if seg.uuid == uuid {
Some((seg.segment.start, seg.segment.length))
} else {
None
}
})
.try_fold(
PerDevSegments::new(self.segments.limit()),
|mut segs, seg| {
segs.insert(&seg)?;
StratisResult::Ok(segs)
},
)?;
let total_segments = self.segments.union(&trans_used)?;
let mut segs = PerDevSegments::new(self.segments.limit());
let mut needed = amount;
for (&start, &len) in total_segments.complement().iter() {
if needed == Sectors(0) {
break;
}
let to_use = min(needed, len);
let used_range = (start, to_use);
segs.insert(&used_range)
.expect("wholly disjoint from other elements in segs");
needed -= to_use;
}
Ok(segs)
}
pub fn commit(&mut self, segs: PerDevSegments) {
self.segments = self
.segments
.union(&segs)
.expect("all segments verified to be in available ranges");
}
pub fn increase_size(&mut self, new_size: Sectors) {
assert!(new_size > self.segments.limit);
self.segments.limit = new_size;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_allocator_allocations() {
let mut allocator = RangeAllocator::new(BlockdevSize::new(Sectors(128)), &[]).unwrap();
assert_eq!(allocator.used(), Sectors(0));
assert_eq!(allocator.available(), Sectors(128));
allocator
.segments
.insert_all(&[(Sectors(10), Sectors(100))])
.unwrap();
assert_eq!(allocator.used(), Sectors(100));
assert_eq!(allocator.available(), Sectors(28));
let seg = allocator
.request(
DevUuid::new_v4(),
Sectors(50),
&RequestTransaction::default(),
)
.unwrap();
allocator.commit(seg.clone());
assert_eq!(seg.len(), 2);
assert_eq!(seg.sum(), Sectors(28));
assert_eq!(allocator.used(), Sectors(128));
assert_eq!(allocator.available(), Sectors(0));
let available = allocator.available();
let seg = allocator
.request(DevUuid::new_v4(), available, &RequestTransaction::default())
.unwrap();
allocator.commit(seg);
assert_eq!(allocator.available(), Sectors(0));
}
#[test]
fn test_allocator_initialized_with_range() {
let mut allocator = PerDevSegments::new(Sectors(128));
let ranges = [
(Sectors(20), Sectors(10)),
(Sectors(10), Sectors(10)),
(Sectors(30), Sectors(10)),
];
allocator.insert_all(&ranges).unwrap();
assert_eq!(allocator.used.len(), 1);
assert_eq!(
allocator.used.iter().next().unwrap(),
(&Sectors(10), &Sectors(30))
);
}
#[test]
fn test_allocator_insert_ranges_contig() {
let mut allocator = PerDevSegments::new(Sectors(128));
allocator.insert(&(Sectors(20), Sectors(10))).unwrap();
allocator.insert(&(Sectors(10), Sectors(10))).unwrap();
allocator.insert(&(Sectors(30), Sectors(10))).unwrap();
assert_eq!(allocator.used.len(), 1);
assert_eq!(
allocator.used.iter().next().unwrap(),
(&Sectors(10), &Sectors(30))
);
allocator.invariant();
}
#[test]
fn test_max_allocator_range() {
use std::u64::MAX;
PerDevSegments::new(Sectors(MAX));
}
#[test]
fn test_allocator_insert_prev_overlap() {
let mut allocator = PerDevSegments::new(Sectors(128));
let bad_insert_ranges = [(Sectors(21), Sectors(20)), (Sectors(40), Sectors(40))];
assert_matches!(allocator.insert_all(&bad_insert_ranges), Err(_))
}
#[test]
fn test_allocator_insert_next_overlap() {
let mut allocator = PerDevSegments::new(Sectors(128));
let bad_insert_ranges = [(Sectors(40), Sectors(1)), (Sectors(39), Sectors(2))];
assert_matches!(allocator.insert_all(&bad_insert_ranges), Err(_))
}
#[test]
fn test_allocator_failures_range_overwrite() {
let mut allocator = RangeAllocator::new(BlockdevSize::new(Sectors(128)), &[]).unwrap();
let seg = allocator
.request(
DevUuid::new_v4(),
Sectors(128),
&RequestTransaction::default(),
)
.unwrap();
allocator.commit(seg.clone());
assert_eq!(allocator.used(), Sectors(128));
assert_eq!(
seg.iter().collect::<Vec<_>>(),
vec![(&Sectors(0), &Sectors(128))]
);
assert!(allocator.segments.complement().iter().next().is_none());
assert_matches!(
allocator.segments.insert_all(&[(Sectors(1), Sectors(1))]),
Err(_)
);
}
#[test]
fn test_allocator_failures_overflow_limit() {
let mut allocator = PerDevSegments::new(Sectors(128));
assert_matches!(allocator.insert(&(Sectors(1), Sectors(128))), Err(_));
allocator.invariant();
}
#[test]
fn test_allocator_failures_overflow_max() {
use std::u64::MAX;
let mut allocator = PerDevSegments::new(Sectors(MAX));
assert_matches!(allocator.insert(&(Sectors(MAX), Sectors(1))), Err(_));
allocator.invariant();
}
#[test]
fn test_allocator_indices_empty() {
let allocator = PerDevSegments::new(Sectors(400));
let result = allocator.locate_prev_and_next(Sectors(37));
assert_eq!(result, (None, None));
allocator.invariant();
}
#[test]
fn test_allocator_indices_full() {
let mut allocator = PerDevSegments::new(Sectors(400));
allocator.insert(&(Sectors(0), Sectors(400))).unwrap();
let result = allocator.locate_prev_and_next(Sectors(37));
assert_eq!(result, (Some(Sectors(0)), None));
let result = allocator.locate_prev_and_next(Sectors(0));
assert_eq!(result, (Some(Sectors(0)), Some(Sectors(0))));
allocator.invariant();
}
#[test]
fn test_search_over_limit() {
let mut allocator = PerDevSegments::new(Sectors(400));
assert_eq!(allocator.locate_prev_and_next(Sectors(500)), (None, None));
allocator.insert(&(Sectors(0), Sectors(400))).unwrap();
assert_eq!(
allocator.locate_prev_and_next(Sectors(500)),
(Some(Sectors(0)), None)
);
allocator.invariant();
}
#[test]
fn test_allocator_zero_length_insertion() {
let mut allocator = PerDevSegments::new(Sectors(400));
assert_matches!(allocator.insert(&(Sectors(12), Sectors(0))), Ok(_));
assert_eq!(allocator.len(), 0);
allocator.invariant();
}
#[test]
fn test_allocator_zero_length() {
let allocator = PerDevSegments::new(Sectors(0));
allocator.invariant();
}
#[test]
fn test_allocator_end_behavior() {
let mut allocator = PerDevSegments::new(Sectors(127));
allocator.insert(&(Sectors(127), Sectors(0))).unwrap();
assert_eq!(allocator.len(), 0);
assert_matches!(allocator.insert(&(Sectors(127), Sectors(1))), Err(_));
allocator.invariant();
}
}