Revision control
Copy as Markdown
Other Tools
use {
crate::prelude::*,
rand::random,
serde::{Deserialize, Deserializer, Serialize, Serializer},
std::{error, fmt},
};
// TODO: Intend to convert this module to a standalone `no_std` crate
pub type TestResult<O> = Result<Outcome, Error<<O as TestObserver>::Error>>;
#[derive(Debug, Serialize, Deserialize)]
#[must_use]
pub enum Outcome {
Pass,
Fail(Failure),
}
#[derive(Serialize, Deserialize)]
pub enum Failure {
/// Failure due to the actual value read being different from the expected value
UnexpectedValue {
address: usize,
expected: usize,
actual: usize,
},
/// Failure due to the two memory locations being compared returning two different values
/// This is used by tests where memory is split in two and values are written in pairs
MismatchedValues {
address1: usize,
value1: usize,
address2: usize,
value2: usize,
},
}
pub trait TestObserver {
type Error: error::Error;
fn init(&mut self, expected_iter: u64);
fn check(&mut self) -> Result<(), Self::Error>;
}
#[derive(Debug, Serialize, Deserialize)]
pub enum Error<E> {
Observer(E),
#[serde(
serialize_with = "serialize_error_other",
deserialize_with = "deserialize_error_other"
)]
Other(anyhow::Error),
}
macro_rules! test_kinds {{
$($variant: ident),* $(,)?
} => {
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum TestKind {
$($variant,)*
}
impl TestKind {
pub const ALL: &'static [Self] = &[
$(Self::$variant),*
];
}
impl std::str::FromStr for TestKind {
type Err = ParseTestKindError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
$(
stringify!($variant) => Ok(Self::$variant),
)*
_ => Err(ParseTestKindError),
}
}
}
}}
test_kinds! {
OwnAddressBasic,
OwnAddressRepeat,
RandomVal,
Xor,
Sub,
Mul,
Div,
Or,
And,
SeqInc,
SolidBits,
Checkerboard,
BlockSeq,
MovInvFixedBlock,
MovInvFixedBit,
MovInvFixedRandom,
MovInvWalk,
BlockMove,
MovInvRandom,
Modulo20,
}
#[derive(Debug, PartialEq, Eq)]
pub struct ParseTestKindError;
impl TestKind {
pub fn run<O: TestObserver>(&self, memory: &mut [usize], observer: O) -> TestResult<O> {
use two_region::{
run_two_region_test_algorithm, And, BlockSeq, Checkerboard, Div, Mul, Or, RandomVal,
SeqInc, SolidBits, Sub, Xor,
};
match self {
Self::OwnAddressBasic => {
run_test_algorithm(OwnAddressBasic::default(), memory, observer)
}
Self::OwnAddressRepeat => {
run_test_algorithm(OwnAddressRepeat::default(), memory, observer)
}
Self::RandomVal => {
run_two_region_test_algorithm(RandomVal::default(), memory, observer)
}
Self::Xor => run_two_region_test_algorithm(Xor::default(), memory, observer),
Self::Sub => run_two_region_test_algorithm(Sub::default(), memory, observer),
Self::Mul => run_two_region_test_algorithm(Mul::default(), memory, observer),
Self::Div => run_two_region_test_algorithm(Div::default(), memory, observer),
Self::Or => run_two_region_test_algorithm(Or::default(), memory, observer),
Self::And => run_two_region_test_algorithm(And::default(), memory, observer),
Self::SeqInc => run_two_region_test_algorithm(SeqInc::default(), memory, observer),
Self::SolidBits => {
run_two_region_test_algorithm(SolidBits::default(), memory, observer)
}
Self::Checkerboard => {
run_two_region_test_algorithm(Checkerboard::default(), memory, observer)
}
Self::BlockSeq => run_two_region_test_algorithm(BlockSeq::default(), memory, observer),
Self::MovInvFixedBlock => {
run_test_algorithm(mov_inv::FixedBlock::default(), memory, observer)
}
Self::MovInvFixedBit => {
run_test_algorithm(mov_inv::FixedBit::default(), memory, observer)
}
Self::MovInvFixedRandom => {
run_test_algorithm(mov_inv::FixedRandom::default(), memory, observer)
}
Self::MovInvWalk => run_test_algorithm(mov_inv::Walk::default(), memory, observer),
Self::BlockMove => run_block_move(memory, observer),
Self::MovInvRandom => run_test_algorithm(mov_inv::Random::default(), memory, observer),
Self::Modulo20 => run_modulo_20(memory, observer),
}
}
}
/// A pass can be done forward (default) or reversed
#[derive(Debug, Default)]
enum PassDirection {
#[default]
Forward,
Reverse,
}
type PassFn<T> = fn(&mut T, direction: &mut PassDirection) -> IterFn<T>;
type IterFn<T> = fn(&mut T, &mut usize) -> Result<(), Failure>;
trait TestAlgorithm: fmt::Debug {
/// The number of runs the algorithm needs. Most tests can just accept the default of '1'
fn num_runs(&self) -> u64 {
1
}
/// Initialize the state for the run given by `run_idx`. Most tests don't need to do anything.
fn start_run(&mut self, _run_idx: u64) {}
/// Return a list of functions defining the behavior of the passes
///
/// Each function receives a mutable reference to `direction`, which will always be set to
/// the default of `Forward`. If a pass wants the direction reversed, it can set it to
/// `Reverse`.
///
/// Each function must return the iteration function for the pass. This is the function that
/// will be run for each memory address.
///
/// The iteration function itself takes a mutable reference to each memory address and
/// returns either `Ok(())` or `Err(Failure)`.
fn passes(&self) -> Vec<PassFn<Self>>;
}
#[tracing::instrument(skip(memory, observer))]
fn run_test_algorithm<T: TestAlgorithm, O: TestObserver>(
mut test: T,
memory: &mut [usize],
mut observer: O,
) -> TestResult<O> {
let expected_iter = u64::try_from(memory.len())
.ok()
.and_then(|count| count.checked_mul(test.num_runs()))
.and_then(|count| count.checked_mul(u64::try_from(test.passes().len()).ok()?))
.context("Total number of iterations overflowed")?;
observer.init(expected_iter);
for i in 0..test.num_runs() {
test.start_run(i);
for pass_fn in test.passes() {
let mut direction = PassDirection::default();
let iter_fn = pass_fn(&mut test, &mut direction);
let mem_iter: Box<dyn Iterator<Item = &mut usize>> = match direction {
PassDirection::Forward => Box::new(memory.iter_mut()),
PassDirection::Reverse => Box::new(memory.iter_mut().rev()),
};
for mem_ref in mem_iter {
observer.check().map_err(Error::Observer)?;
if let Err(f) = iter_fn(&mut test, mem_ref) {
return Ok(Outcome::Fail(f));
}
}
}
}
Ok(Outcome::Pass)
}
fn check_expected_value(address: usize, expected: usize, actual: usize) -> Result<(), Failure> {
if actual != expected {
info!("Test failed at 0x{address:x}");
Err(Failure::UnexpectedValue {
address,
expected,
actual,
})
} else {
Ok(())
}
}
/// Write the address of each memory location to itself, then read back the value and check that it
/// matches the expected address.
#[derive(Debug, Default)]
struct OwnAddressBasic {}
impl TestAlgorithm for OwnAddressBasic {
fn passes(&self) -> Vec<PassFn<Self>> {
vec![Self::pass_0, Self::pass_1]
}
}
impl OwnAddressBasic {
fn pass_0(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
|_state, mem_ref| {
write_volatile_safe(mem_ref, address_from_ref(mem_ref));
Ok(())
}
}
fn pass_1(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
|_state, mem_ref| {
check_expected_value(
address_from_ref(mem_ref),
address_from_ref(mem_ref),
read_volatile_safe(mem_ref),
)
}
}
}
/// Write the address of each memory location (or its complement) to itself, then read back the
/// value and check that it matches the expected address.
/// This procedure is repeated 16 times.
#[derive(Debug, Default)]
struct OwnAddressRepeat {
complement: bool,
run_idx: u64,
}
impl TestAlgorithm for OwnAddressRepeat {
fn num_runs(&self) -> u64 {
16
}
fn start_run(&mut self, run_idx: u64) {
self.run_idx = run_idx;
}
fn passes(&self) -> Vec<PassFn<Self>> {
vec![Self::pass_0, Self::pass_1]
}
}
impl OwnAddressRepeat {
fn pass_0(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
self.init_complement();
|state, mem_ref| {
write_volatile_safe(mem_ref, state.val_to_write(mem_ref));
state.complement = !state.complement;
Ok(())
}
}
fn pass_1(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
self.init_complement();
|state, mem_ref| {
check_expected_value(
address_from_ref(mem_ref),
state.val_to_write(mem_ref),
read_volatile_safe(mem_ref),
)?;
state.complement = !state.complement;
Ok(())
}
}
fn init_complement(&mut self) {
self.complement = self.run_idx % 2 != 0;
}
fn val_to_write(&self, mem_ref: &usize) -> usize {
if self.complement {
!address_from_ref(mem_ref)
} else {
address_from_ref(mem_ref)
}
}
}
mod two_region {
use {
super::{
address_from_ref, mem_reset, read_volatile_safe, split_slice_in_half,
usize_filled_from_byte, write_volatile_safe, Error, Failure, Outcome, TestObserver,
TestResult,
},
crate::prelude::*,
rand::random,
std::fmt,
};
type TwoRegionWriteFn<T> = fn(&mut T, &mut usize, &mut usize);
/// A two region test has to passes of memory for every run. The test splits memory into
/// two halves. The first pass iterates through memory and writes some memory pattern to each
/// pair of locations. The second pass reads through and compare the two halves.
trait TwoRegionTestAlgorithm: fmt::Debug + Default {
/// The number of runs the algorithm needs. Most tests can just accept the default of '1'
fn num_runs(&self) -> u64 {
1
}
/// Initialize the state for the run given by `run_idx`. Most tests don't need to do anything.
fn start_run(&mut self, _run_idx: u64) {}
/// Returns whether a memory reset is needed at the start of each run
/// If true, the algorithm will reset all bits to 1.
fn reset_before_run(&self) -> bool;
/// Returns the function that is called for every iteration of the first pass to write to
/// memory.
fn write_fn(&self) -> TwoRegionWriteFn<Self>;
}
#[tracing::instrument(skip(memory, observer))]
pub(super) fn run_two_region_test_algorithm<T: TwoRegionTestAlgorithm, O: TestObserver>(
mut test: T,
memory: &mut [usize],
mut observer: O,
) -> TestResult<O> {
if test.reset_before_run() {
mem_reset(memory);
}
let (first_half, second_half) = split_slice_in_half(memory)?;
let expected_iter = u64::try_from(first_half.len())
.ok()
.and_then(|count| count.checked_mul(2))
.and_then(|count| count.checked_mul(test.num_runs()))
.context("Total number of iterations overflowed")?;
observer.init(expected_iter);
for i in 0..test.num_runs() {
test.start_run(i);
let write_fn = test.write_fn();
for (first_ref, second_ref) in first_half.iter_mut().zip(second_half.iter_mut()) {
observer.check().map_err(Error::Observer)?;
write_fn(&mut test, first_ref, second_ref);
}
for (first_ref, second_ref) in first_half.iter().zip(second_half.iter()) {
observer.check().map_err(Error::Observer)?;
if let Err(f) = check_matching_values(
address_from_ref(first_ref),
read_volatile_safe(first_ref),
address_from_ref(second_ref),
read_volatile_safe(second_ref),
) {
return Ok(Outcome::Fail(f));
}
}
}
Ok(Outcome::Pass)
}
fn check_matching_values(
address1: usize,
value1: usize,
address2: usize,
value2: usize,
) -> Result<(), Failure> {
if value1 != value2 {
info!("Test failed at 0x{address1:x} compared to 0x{address2:x}");
Err(Failure::MismatchedValues {
address1,
value1,
address2,
value2,
})
} else {
Ok(())
}
}
/// Split given memory into two halves and iterate through memory locations in pairs. For each
/// pair, write a random value. After all locations are written, read and compare the two halves.
#[derive(Debug, Default)]
pub(super) struct RandomVal {}
impl TwoRegionTestAlgorithm for RandomVal {
fn reset_before_run(&self) -> bool {
false
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
|_state, first_ref, second_ref| {
let val = random();
write_volatile_safe(first_ref, val);
write_volatile_safe(second_ref, val);
}
}
}
macro_rules! two_region_write_fn_with_transform_fn {
($transform_fn:expr) => {
|_state, first_ref, second_ref| {
let mixing_val: usize = random();
let val = read_volatile_safe(first_ref);
let new_val = $transform_fn(val, mixing_val);
write_volatile_safe(first_ref, new_val);
let val = read_volatile_safe(second_ref);
let new_val = $transform_fn(val, mixing_val);
write_volatile_safe(second_ref, new_val);
}
};
}
/// Reset all bits in given memory to 1s. Split given memory into two halves and iterate through
/// memory locations in pairs. For each pair, write the XOR result of a random value and the value
/// read from the location. After all locations are written, read and compare the two halves.
#[derive(Debug, Default)]
pub(super) struct Xor {}
impl TwoRegionTestAlgorithm for Xor {
fn reset_before_run(&self) -> bool {
true
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
two_region_write_fn_with_transform_fn!(std::ops::BitXor::bitxor)
}
}
/// Reset all bits in given memory to 1s. Split given memory into two halves and iterate through
/// memory locations in pairs. For each pair, write the result of subtracting a random value from
/// the value read from the location. After all locations are written, read and compare the two
/// halves.
#[derive(Debug, Default)]
pub(super) struct Sub {}
impl TwoRegionTestAlgorithm for Sub {
fn reset_before_run(&self) -> bool {
true
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
two_region_write_fn_with_transform_fn!(usize::wrapping_sub)
}
}
/// Reset all bits in given memory to 1s. Split given memory into two halves and iterate through
/// memory locations in pairs. For each pair, write the result of multiplying a random value with
/// the value read from the location. After all locations are written, read and compare the two
/// halves.
#[derive(Debug, Default)]
pub(super) struct Mul {}
impl TwoRegionTestAlgorithm for Mul {
fn reset_before_run(&self) -> bool {
true
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
two_region_write_fn_with_transform_fn!(usize::wrapping_mul)
}
}
/// Reset all bits in given memory to 1s. Split given memory into two halves and iterate through
/// memory locations in pairs. For each pair, write the result of dividing the value read from the
/// location with a random value. After all locations are written, read and compare the two halves.
#[derive(Debug, Default)]
pub(super) struct Div {}
impl TwoRegionTestAlgorithm for Div {
fn reset_before_run(&self) -> bool {
true
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
two_region_write_fn_with_transform_fn!(
|n: usize, d: usize| n.wrapping_div(usize::max(d, 1))
)
}
}
/// Reset all bits in given memory to 1s. Split given memory into two halves and iterate through
/// memory locations in pairs. For each pair, write the OR result of a random value and the value
/// read from the location. After all locations are written, read and compare the two halves.
#[derive(Debug, Default)]
pub(super) struct Or {}
impl TwoRegionTestAlgorithm for Or {
fn reset_before_run(&self) -> bool {
true
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
two_region_write_fn_with_transform_fn!(std::ops::BitOr::bitor)
}
}
/// Reset all bits in given memory to 1s. Split given memory into two halves and iterate through
/// memory locations in pairs. For each pair, write the AND result of a random value and the value
/// read from the location. After all locations are written, read and compare the two halves.
#[derive(Debug, Default)]
pub(super) struct And {}
impl TwoRegionTestAlgorithm for And {
fn reset_before_run(&self) -> bool {
true
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
two_region_write_fn_with_transform_fn!(std::ops::BitAnd::bitand)
}
}
/// Split given memory into two halves and iterate through memory locations in pairs. Generate a
/// random value at the start. For each pair, write the result of adding the random value and the
/// index of iteration. After all locations are written, read and compare the two halves.
#[derive(Debug, Default)]
pub(super) struct SeqInc {
val: usize,
}
impl TwoRegionTestAlgorithm for SeqInc {
fn reset_before_run(&self) -> bool {
false
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
|state, first_ref, second_ref| {
state.val = state.val.wrapping_add(1);
write_volatile_safe(first_ref, state.val);
write_volatile_safe(second_ref, state.val);
}
}
}
/// Split given memory into two halves and iterate through memory locations in pairs. For each
/// pair, write to all bits as either 1s or 0s, alternating after each memory location pair.
/// After all locations are written, read and compare the two halves.
/// This procedure is repeated 64 times.
#[derive(Debug)]
pub(super) struct SolidBits {
solid_bits: usize,
val: usize,
}
impl Default for SolidBits {
fn default() -> Self {
SolidBits {
solid_bits: !0,
val: usize::default(),
}
}
}
impl TwoRegionTestAlgorithm for SolidBits {
fn num_runs(&self) -> u64 {
64
}
fn start_run(&mut self, _run_idx: u64) {
self.solid_bits = !self.solid_bits;
self.val = self.solid_bits;
}
fn reset_before_run(&self) -> bool {
false
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
|state, first_ref, second_ref| {
state.val = !state.val;
write_volatile_safe(first_ref, state.val);
write_volatile_safe(second_ref, state.val);
}
}
}
/// Split given memory into two halves and iterate through memory locations in pairs. For each pair,
/// write to a pattern of alternating 1s and 0s (in bytes it is either 0x55 or 0xaa, and alternating
/// after each memory location pair). After all locations are written, read and compare the two
/// halves.
/// This procedure is repeated 64 times.
#[derive(Debug)]
pub(super) struct Checkerboard {
checker_board: usize,
val: usize,
}
impl Default for Checkerboard {
fn default() -> Self {
Checkerboard {
checker_board: usize_filled_from_byte(0xaa),
val: usize::default(),
}
}
}
impl TwoRegionTestAlgorithm for Checkerboard {
fn num_runs(&self) -> u64 {
64
}
fn start_run(&mut self, _run_idx: u64) {
self.checker_board = !self.checker_board;
self.val = self.checker_board;
}
fn reset_before_run(&self) -> bool {
false
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
|state, first_ref, second_ref| {
state.val = !state.val;
write_volatile_safe(first_ref, state.val);
write_volatile_safe(second_ref, state.val);
}
}
}
/// Split given memory into two halves and iterate through memory locations in pairs. For each pair,
/// write to all bytes with the value i. After all locations are written, read and compare the two
/// halves.
/// This procedure is repeated 256 times, with i corresponding to the iteration number 0-255.
#[derive(Debug, Default)]
pub(super) struct BlockSeq {
val: usize,
}
impl TwoRegionTestAlgorithm for BlockSeq {
fn num_runs(&self) -> u64 {
256
}
fn start_run(&mut self, run_idx: u64) {
self.val = usize_filled_from_byte(run_idx.try_into().unwrap());
}
fn reset_before_run(&self) -> bool {
false
}
fn write_fn(&self) -> TwoRegionWriteFn<Self> {
|state, first_ref, second_ref| {
write_volatile_safe(first_ref, state.val);
write_volatile_safe(second_ref, state.val);
}
}
}
}
mod mov_inv {
use {
super::{
address_from_ref, check_expected_value, read_volatile_safe, usize_filled_from_byte,
write_volatile_safe, IterFn, PassDirection, PassFn, TestAlgorithm,
},
rand::{random, rngs::SmallRng, Rng, SeedableRng},
std::{
fmt,
time::{SystemTime, UNIX_EPOCH},
},
};
/// These tests adapt the moving inversion algorithm implemented by [memtest86+](https://github.com/
/// memtest86plus/memtest86plus). As described in the the [Memtest86+ Test Algorithm Section](https://github.com/
/// memtest86plus/memtest86plus?tab=readme-ov-file#memtest86-test-algorithms),
///
/// "The moving inversion tests work as follows:
/// 1. Fill memory with a pattern
/// 2. Starting at the lowest address
/// i. check that the pattern has not changed
/// ii. write the pattern's complement
/// iii. increment the address
/// iv. repeat 2.1 to 2.3
/// 3. Starting at the highest address
/// i. check that the pattern has not changed
/// ii. write the pattern's complement
/// iii. decrement the address
/// iv. repeat 3.1 to 3.3 "
pub(super) trait MovInvAlgorithm: fmt::Debug + Default {
fn num_runs(&self) -> u64;
fn start_run(&mut self, _run_idx: u64);
fn start_pass(&mut self, _pass_idx: u64) {}
fn generate_pattern(&mut self) -> usize;
fn backtrack_pattern(&mut self) -> usize;
fn passes(&self) -> Vec<PassFn<Self>> {
vec![Self::pass_0, Self::pass_1, Self::pass_2]
}
fn pass_0(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
self.start_pass(0);
|state, mem_ref| {
let pattern = state.generate_pattern();
write_volatile_safe(mem_ref, pattern);
Ok(())
}
}
fn pass_1(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
self.start_pass(1);
|state, mem_ref| {
let pattern = state.generate_pattern();
check_expected_value(
address_from_ref(mem_ref),
pattern,
read_volatile_safe(mem_ref),
)?;
write_volatile_safe(mem_ref, !pattern);
Ok(())
}
}
fn pass_2(&mut self, direction: &mut PassDirection) -> IterFn<Self> {
*direction = PassDirection::Reverse;
self.start_pass(2);
|state, mem_ref| {
let pattern = !state.backtrack_pattern();
check_expected_value(
address_from_ref(mem_ref),
pattern,
read_volatile_safe(mem_ref),
)?;
write_volatile_safe(mem_ref, !pattern);
Ok(())
}
}
}
impl<T: MovInvAlgorithm> TestAlgorithm for T {
fn num_runs(&self) -> u64 {
T::num_runs(self)
}
fn start_run(&mut self, run_idx: u64) {
T::start_run(self, run_idx)
}
fn passes(&self) -> Vec<PassFn<Self>> {
T::passes(self)
}
}
#[derive(Debug, Default)]
pub(super) struct FixedBlock {
run_idx: u64,
}
/// This test runs the moving inversion algorithm with fixed patterns of all bits as 1s or 0s.
impl MovInvAlgorithm for FixedBlock {
fn num_runs(&self) -> u64 {
2
}
fn start_run(&mut self, run_idx: u64) {
self.run_idx = run_idx;
}
fn generate_pattern(&mut self) -> usize {
self.pattern()
}
fn backtrack_pattern(&mut self) -> usize {
self.pattern()
}
}
impl FixedBlock {
fn pattern(&mut self) -> usize {
if self.run_idx == 0 {
0
} else {
!0
}
}
}
/// This test runs the moving inversion algorithm with fixed 8-bit patterns where 1 bit is 1/0 and the
/// other 7 bits are 0/1s. The procedure is repeated 8 times with the pattern rotated by 1 bit each
/// time to test all bits in a byte.
#[derive(Debug)]
pub(super) struct FixedBit {
run_idx: u64,
pattern: usize,
}
impl Default for FixedBit {
fn default() -> Self {
FixedBit {
run_idx: u64::default(),
pattern: usize_filled_from_byte(0x01),
}
}
}
impl MovInvAlgorithm for FixedBit {
fn num_runs(&self) -> u64 {
16
}
fn start_run(&mut self, run_idx: u64) {
self.run_idx = run_idx;
if run_idx % 2 == 0 {
self.pattern = self.pattern.rotate_right(1);
}
}
fn generate_pattern(&mut self) -> usize {
self.pattern()
}
fn backtrack_pattern(&mut self) -> usize {
self.pattern()
}
}
impl FixedBit {
fn pattern(&mut self) -> usize {
if self.run_idx % 2 == 0 {
self.pattern
} else {
!self.pattern
}
}
}
/// This test runs the moving inversion algorithm with a random fixed pattern.
#[derive(Debug)]
pub(super) struct FixedRandom {
run_idx: u64,
pattern: usize,
}
impl Default for FixedRandom {
fn default() -> Self {
FixedRandom {
run_idx: u64::default(),
pattern: random(),
}
}
}
impl MovInvAlgorithm for FixedRandom {
fn num_runs(&self) -> u64 {
2
}
fn start_run(&mut self, run_idx: u64) {
self.run_idx = run_idx;
}
fn generate_pattern(&mut self) -> usize {
self.pattern()
}
fn backtrack_pattern(&mut self) -> usize {
self.pattern()
}
}
impl FixedRandom {
fn pattern(&mut self) -> usize {
if self.run_idx % 2 == 0 {
self.pattern
} else {
!self.pattern
}
}
}
#[derive(Debug, Default)]
pub(super) struct Walk {
run_idx: u64,
starting_pattern: usize,
pattern: usize,
}
/// This test runs the moving inversion algorithm with a "walking" bit pattern. The algorithm starts
/// with 0x1 (or the compliment of 0x1) and "walks" the bit by shifting left for every new memory
/// location.
/// The procedure is repeated with offsets 0-31 or 0-63 depending on the size of `usize` to test all
/// bits in a memory location.
impl MovInvAlgorithm for Walk {
fn num_runs(&self) -> u64 {
u64::from(usize::BITS) * 2
}
fn start_run(&mut self, run_idx: u64) {
self.run_idx = run_idx;
self.starting_pattern = 1 << (run_idx / 2);
}
fn start_pass(&mut self, pass_idx: u64) {
// For pass_idx == 2, pattern is not reset
if pass_idx == 0 || pass_idx == 1 {
self.pattern = self.starting_pattern;
}
}
fn generate_pattern(&mut self) -> usize {
let pattern = if self.run_idx % 2 == 0 {
self.pattern
} else {
!self.pattern
};
self.pattern = self.pattern.rotate_left(1);
pattern
}
fn backtrack_pattern(&mut self) -> usize {
self.pattern = self.pattern.rotate_right(1);
if self.run_idx % 2 == 0 {
self.pattern
} else {
!self.pattern
}
}
}
// Despite its name MovInvRandom, this implementation (which follows the Memtest86+
// implementation) is not similar to other moving inversion tests. Due to its nature of using
// random numbers for each address, pass 2 does not traverse the memory in reverse.
// TODO: Consider using a reversible RNG to match other moving inversion tests
// for XORshift, which is the RNG used in Memtest86+
#[derive(Debug)]
pub(super) struct Random {
seed: u64,
rng: SmallRng,
}
impl Default for Random {
fn default() -> Self {
let seed = SystemTime::now()
.duration_since(UNIX_EPOCH)
.unwrap()
.as_millis() as u64;
Random {
seed,
rng: SmallRng::seed_from_u64(seed),
}
}
}
impl TestAlgorithm for Random {
fn passes(&self) -> Vec<PassFn<Self>> {
vec![Self::pass_0, Self::pass_1, Self::pass_2]
}
}
impl Random {
fn pass_0(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
self.reset_rng();
|state, mem_ref| {
let pattern = state.rng.gen();
write_volatile_safe(mem_ref, pattern);
Ok(())
}
}
fn pass_1(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
self.reset_rng();
|state, mem_ref| {
let pattern = state.rng.gen();
check_expected_value(
address_from_ref(mem_ref),
pattern,
read_volatile_safe(mem_ref),
)?;
write_volatile_safe(mem_ref, !pattern);
Ok(())
}
}
fn pass_2(&mut self, _direction: &mut PassDirection) -> IterFn<Self> {
self.reset_rng();
|state, mem_ref| {
let pattern = !state.rng.gen::<usize>();
check_expected_value(
address_from_ref(mem_ref),
pattern,
read_volatile_safe(mem_ref),
)?;
write_volatile_safe(mem_ref, !pattern);
Ok(())
}
}
fn reset_rng(&mut self) {
self.rng = SmallRng::seed_from_u64(self.seed);
}
}
}
/// memtest86plus/memtest86plus). For a detailed explanation of the algorithm, please refer to
/// memtest86plus/memtest86plus?tab=readme-ov-file#memtest86-test-algorithms)
///
/// The test aims to stress test the memory by moving blocks of memory, such as with the `movs` instruction.
/// It first initializes the memory with an irregular shifting pattern. Then it performs 3 memory block moves.
/// 1. Copy the first half of the memory region to the second half
/// 2. Copy the second half of the memory region back to the first half, offset by 8 locations.
/// ie. Copy the second half - the last 8 locations, to the first half's original location + 8
/// 3. Copy the second half's last 8 locations to the first half's first 8 locations
/// Finally, the test verifies that the second half has the values of the original first half, and
/// the first half's values are right rotated by 8 locations
///
/// Note that the original implementation in Memtest86+ only verifies the values by comparing
/// neighbouring pairs of memory location. Instead of that, this implementation verifies by
/// recalculating the expected pattern in each location.
///
/// Also note that unlike the other memory tests, `Observer::check()` is only called in the initial
/// loop for initalizing memory and the final loop for verifying values. It is not called during the
/// memory block moves, as it intefere with the stress testing of memory. Unfortunately, this means
/// that `Observer::check()` will not be called for a siginficant duration of the test run time.
#[tracing::instrument(skip_all)]
pub fn run_block_move<O: TestObserver>(memory: &mut [usize], mut observer: O) -> TestResult<O> {
const CHUNK_SIZE: usize = 16;
const OFFSET: usize = 8;
if memory.len() < CHUNK_SIZE {
Err(anyhow!("Insufficient memory length for Block Move Test"))?;
}
let expected_iter = u64::try_from(memory.len())
.ok()
.and_then(|count| count.checked_mul(2))
.context("Total number of iterations overflowed")?;
observer.init(expected_iter);
let val_to_write = |pattern: usize, idx| match idx {
4 | 5 | 10 | 11 | 14 | 15 => !pattern,
_ => pattern,
};
// Set up initial pattern in memory
let mut pattern = 1;
for chunk in memory.chunks_exact_mut(CHUNK_SIZE) {
for (i, mem_ref) in chunk.iter_mut().enumerate() {
observer.check().map_err(Error::Observer)?;
let val = val_to_write(pattern, i);
write_volatile_safe(mem_ref, val);
}
pattern = pattern.rotate_left(1);
}
// Move blocks of memory around
let (first_half, second_half) = split_slice_in_half(memory)?;
let half_len = first_half.len();
volatile_copy_slice(second_half, first_half);
volatile_copy_slice(
&mut first_half[OFFSET..],
&second_half[..(half_len - OFFSET)],
);
volatile_copy_slice(
&mut first_half[..OFFSET],
&second_half[(half_len - OFFSET)..],
);
// Verify that values stored after block move are as expected, by traversing both halves at the
// same time (with first half rotated by OFFSET), as they have the same expected values
let mut pattern = 1;
for (chunk1, chunk2) in [&first_half[OFFSET..], &first_half[..OFFSET]]
.concat()
.chunks(CHUNK_SIZE)
.zip(second_half.chunks(CHUNK_SIZE))
{
for (i, (mem_ref1, mem_ref2)) in chunk1.iter().zip(chunk2.iter()).enumerate() {
let expected = val_to_write(pattern, i);
for mem_ref in [mem_ref1, mem_ref2] {
observer.check().map_err(Error::Observer)?;
if let Err(f) = check_expected_value(
address_from_ref(mem_ref),
expected,
read_volatile_safe(mem_ref),
) {
return Ok(Outcome::Fail(f));
}
}
}
pattern = pattern.rotate_left(1);
}
Ok(Outcome::Pass)
}
// TODO: In Memtest86+, block move is achieved with the `movs` assembly instruction
fn volatile_copy_slice<T: Copy>(dst: &mut [T], src: &[T]) {
assert_eq!(
dst.len(),
src.len(),
"length of dst and src should be equal"
);
for (dst_ref, src_ref) in dst.iter_mut().zip(src.iter()) {
let val = read_volatile_safe(src_ref);
write_volatile_safe(dst_ref, val);
}
}
/// memtest86plus/memtest86plus), which is designed to avoid effects of caching and buffering.
///
/// The test generates a random value, then write the value to every 20th memory location.
/// Afterwards write the complement of the value to all other locations one or more times (twice in
/// this case). Then verify that the values stored in every 20th location is unchanged.
///
/// The procedure is repeated with offsets 0-19 to test all memory locations.
#[tracing::instrument(skip_all)]
pub fn run_modulo_20<O: TestObserver>(memory: &mut [usize], mut observer: O) -> TestResult<O> {
const STEP: usize = 20;
(memory.len() > STEP)
.then_some(())
.context("Insufficient memory length for two-regions memtest")?;
let expected_iter = u64::try_from(memory.len())
.ok()
.and_then(|count| count.checked_mul((STEP * 2).try_into().unwrap()))
.context("Total number of iterations overflowed")?;
observer.init(expected_iter);
let pattern = random();
for offset in 0..STEP {
for mem_ref in memory.iter_mut().skip(offset).step_by(STEP) {
observer.check().map_err(Error::Observer)?;
write_volatile_safe(mem_ref, pattern);
}
for _ in 0..2 {
for (i, mem_ref) in memory.iter_mut().enumerate() {
if i % STEP == offset {
continue;
}
observer.check().map_err(Error::Observer)?;
write_volatile_safe(mem_ref, !pattern);
}
}
for mem_ref in memory.iter().skip(offset).step_by(STEP) {
observer.check().map_err(Error::Observer)?;
if let Err(f) = check_expected_value(
address_from_ref(mem_ref),
pattern,
read_volatile_safe(mem_ref),
) {
return Ok(Outcome::Fail(f));
}
}
}
Ok(Outcome::Pass)
}
fn read_volatile_safe<T: Copy>(src: &T) -> T {
unsafe { std::ptr::read_volatile(src) }
}
fn write_volatile_safe<T: Copy>(dst: &mut T, src: T) {
unsafe { std::ptr::write_volatile(dst, src) }
}
fn split_slice_in_half(slice: &mut [usize]) -> anyhow::Result<(&mut [usize], &mut [usize])> {
let mut it = slice.chunks_exact_mut(slice.len() / 2);
let (Some(first), Some(second)) = (it.next(), it.next()) else {
bail!("Insufficient memory length for two-regions memtest");
};
Ok((first, second))
}
fn mem_reset(memory: &mut [usize]) {
for mem_ref in memory.iter_mut() {
write_volatile_safe(mem_ref, !0);
}
}
fn address_from_ref(r: &usize) -> usize {
std::ptr::from_ref(r) as usize
}
/// Return a usize where all bytes are set to to value of `byte`
fn usize_filled_from_byte(byte: u8) -> usize {
let mut val = 0;
unsafe { std::ptr::write_bytes(&mut val, byte, 1) }
val
}
impl fmt::Debug for Failure {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
Self::UnexpectedValue {
address,
expected,
actual,
} => f
.debug_struct("UnexpectedValue")
.field("address", &format_args!("0x{address:x}"))
.field("expected", &format_args!("0x{expected:x}"))
.field("actual", &format_args!("0x{actual:x}"))
.finish(),
Self::MismatchedValues {
address1,
value1,
address2,
value2,
} => f
.debug_struct("MismatchedValues")
.field("address1", &format_args!("0x{address1:x}"))
.field("value1", &format_args!("0x{value1:x}"))
.field("address2", &format_args!("0x{address2:x}"))
.field("value2", &format_args!("0x{value2:x}"))
.finish(),
}
}
}
impl fmt::Display for ParseTestKindError {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{:?}", self)
}
}
impl error::Error for ParseTestKindError {}
impl fmt::Display for Outcome {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "Outcome: {:?}", self)
}
}
impl<E: fmt::Debug> fmt::Display for Error<E> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "Error: {:?}", self)
}
}
impl<E: error::Error + 'static> error::Error for Error<E> {
fn source(&self) -> Option<&(dyn error::Error + 'static)> {
match self {
Error::Observer(err) => Some(err),
Error::Other(err) => Some(err.as_ref()),
}
}
}
impl<E> From<anyhow::Error> for Error<E> {
fn from(err: anyhow::Error) -> Error<E> {
Error::Other(err)
}
}
fn serialize_error_other<S>(error: &anyhow::Error, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
serializer.serialize_str(&format!("{:?}", error))
}
fn deserialize_error_other<'de, D>(deserializer: D) -> Result<anyhow::Error, D::Error>
where
D: Deserializer<'de>,
{
let str = String::deserialize(deserializer)?;
Ok(anyhow!(str))
}
#[cfg(test)]
mod test {
use {
super::{Outcome, TestKind, TestObserver},
std::convert::Infallible,
};
#[derive(Debug)]
struct IterationCounter {
expected_iter: Option<u64>,
completed_iter: u64,
}
impl TestObserver for &mut IterationCounter {
type Error = Infallible;
fn init(&mut self, expected_iter: u64) {
assert!(
self.expected_iter.is_none(),
"init() should only be called once per test"
);
self.expected_iter = Some(expected_iter);
}
#[inline(always)]
fn check(&mut self) -> Result<(), Self::Error> {
self.completed_iter += 1;
Ok(())
}
}
impl IterationCounter {
fn new() -> IterationCounter {
IterationCounter {
expected_iter: None,
completed_iter: 0,
}
}
fn assert_count(self) {
let expected_iter = self.expected_iter.expect("init() should be called");
assert_eq!(expected_iter, self.completed_iter);
}
}
#[test]
fn test_memtest_expected_iter() {
let mut memory = vec![0; 512];
for test_kind in TestKind::ALL {
let mut counter = IterationCounter::new();
assert!(
matches!(test_kind.run(&mut memory, &mut counter), Ok(Outcome::Pass),),
"{:?} should pass",
test_kind
);
counter.assert_count();
}
}
}