feat: memory backend api

Signed-off-by: Henry <mail@henrygressmann.de>

31 files changed, 2155 insertions, 545 deletions

diff --git a/crates/tinywasm/Cargo.toml b/crates/tinywasm/Cargo.toml
index c0fb85d..adbcbde 100644
--- a/crates/tinywasm/Cargo.toml
+++ b/crates/tinywasm/Cargo.toml
@@ -55,7 +55,7 @@ canonicalize_nans=[]
 # derive Debug for runtime/types structs
 debug=["tinywasm-types/debug"]
 
-# expose module-internal by-index inspection APIs
+# expose module-internal by-index inspection APIs for non-exported entities (for testing and debugging)
 guest_debug=[]
 
 # enable x86-specific SIMD intrinsics in Value128 (uses unsafe code)
@@ -139,6 +139,10 @@ harness=false
 name="tinywasm_modes"
 harness=false
 
+[[bench]]
+name="memory_backends"
+harness=false
+
 [[test]]
 name="test-wasm-3"
 harness=false
diff --git a/crates/tinywasm/benches/memory_backends.rs b/crates/tinywasm/benches/memory_backends.rs
new file mode 100644
index 0000000..bbc1b31
--- /dev/null
+++ b/crates/tinywasm/benches/memory_backends.rs
@@ -0,0 +1,122 @@
+use criterion::measurement::WallTime;
+use criterion::{BatchSize, BenchmarkGroup, BenchmarkId, Criterion, criterion_group, criterion_main};
+use std::hint::black_box;
+use tinywasm::{LinearMemory, PagedMemory, VecMemory};
+
+const PAGE_SIZE: usize = 64 * 1024;
+const CHUNK_SIZE: usize = 4 * 1024;
+const GROW_STEPS: usize = 32;
+const BENCH_MEASUREMENT_TIME: std::time::Duration = std::time::Duration::from_secs(10);
+
+const MEMORY_LEN: usize = PAGE_SIZE * 4;
+const CONTIGUOUS_OFFSET: usize = 1024;
+const CONTIGUOUS_LEN: usize = 2048;
+const CROSS_CHUNK_OFFSET: usize = CHUNK_SIZE - 512;
+const CROSS_CHUNK_LEN: usize = CHUNK_SIZE * 2;
+
+fn bench_grow<M, F>(group: &mut BenchmarkGroup<'_, WallTime>, backend: &str, make_memory: F)
+where
+    M: LinearMemory,
+    F: Fn() -> M + Copy,
+{
+    group.bench_function(BenchmarkId::new("grow", backend), |b| {
+        b.iter_batched(
+            make_memory,
+            |mut memory| {
+                for page_count in 2..=GROW_STEPS + 1 {
+                    memory.grow_to(page_count * PAGE_SIZE).unwrap();
+                }
+                black_box(memory.len())
+            },
+            BatchSize::SmallInput,
+        )
+    });
+}
+
+fn bench_write_all<M: LinearMemory>(
+    group: &mut BenchmarkGroup<'_, WallTime>,
+    backend: &str,
+    workload: &str,
+    mut memory: M,
+    offset: usize,
+    len: usize,
+) {
+    let src = vec![0xA5; len];
+    group.bench_function(BenchmarkId::new(format!("write_all/{workload}"), backend), |b| {
+        b.iter(|| {
+            memory.write_all(offset, black_box(&src)).unwrap();
+            black_box(memory.len())
+        })
+    });
+}
+
+fn bench_read_exact<M: LinearMemory>(
+    group: &mut BenchmarkGroup<'_, WallTime>,
+    backend: &str,
+    workload: &str,
+    mut memory: M,
+    offset: usize,
+    len: usize,
+) {
+    let src = vec![0x5A; len];
+    memory.write_all(offset, &src).unwrap();
+
+    let mut dst = vec![0; len];
+    group.bench_function(BenchmarkId::new(format!("read_exact/{workload}"), backend), |b| {
+        b.iter(|| {
+            memory.read_exact(offset, black_box(&mut dst)).unwrap();
+            black_box(&dst);
+        })
+    });
+}
+
+fn criterion_benchmark(c: &mut Criterion) {
+    let mut group = c.benchmark_group("memory_backends");
+    group.measurement_time(BENCH_MEASUREMENT_TIME);
+
+    bench_grow(&mut group, "vec", || VecMemory::new(PAGE_SIZE));
+    bench_grow(&mut group, "paged", || PagedMemory::new(PAGE_SIZE, CHUNK_SIZE));
+
+    bench_write_all(&mut group, "vec", "contiguous", VecMemory::new(MEMORY_LEN), CONTIGUOUS_OFFSET, CONTIGUOUS_LEN);
+    bench_write_all(
+        &mut group,
+        "paged",
+        "contiguous",
+        PagedMemory::new(MEMORY_LEN, CHUNK_SIZE),
+        CONTIGUOUS_OFFSET,
+        CONTIGUOUS_LEN,
+    );
+    bench_read_exact(&mut group, "vec", "contiguous", VecMemory::new(MEMORY_LEN), CONTIGUOUS_OFFSET, CONTIGUOUS_LEN);
+    bench_read_exact(
+        &mut group,
+        "paged",
+        "contiguous",
+        PagedMemory::new(MEMORY_LEN, CHUNK_SIZE),
+        CONTIGUOUS_OFFSET,
+        CONTIGUOUS_LEN,
+    );
+
+    bench_write_all(&mut group, "vec", "cross_chunk", VecMemory::new(MEMORY_LEN), CROSS_CHUNK_OFFSET, CROSS_CHUNK_LEN);
+    bench_write_all(
+        &mut group,
+        "paged",
+        "cross_chunk",
+        PagedMemory::new(MEMORY_LEN, CHUNK_SIZE),
+        CROSS_CHUNK_OFFSET,
+        CROSS_CHUNK_LEN,
+    );
+    bench_read_exact(&mut group, "vec", "cross_chunk", VecMemory::new(MEMORY_LEN), CROSS_CHUNK_OFFSET, CROSS_CHUNK_LEN);
+    bench_read_exact(
+        &mut group,
+        "paged",
+        "cross_chunk",
+        PagedMemory::new(MEMORY_LEN, CHUNK_SIZE),
+        CROSS_CHUNK_OFFSET,
+        CROSS_CHUNK_LEN,
+    );
+
+    group.finish();
+}
+
+criterion_group!(benches, criterion_benchmark);
+criterion_main!(benches);
diff --git a/crates/tinywasm/benches/tinywasm.rs b/crates/tinywasm/benches/tinywasm.rs
index 8de1838..48458d7 100644
--- a/crates/tinywasm/benches/tinywasm.rs
+++ b/crates/tinywasm/benches/tinywasm.rs
@@ -1,6 +1,8 @@
 use criterion::{Criterion, criterion_group, criterion_main};
 use eyre::Result;
-use tinywasm::{FuncContext, HostFunction, Imports, ModuleInstance, Store, types};
+use tinywasm::{
+    Engine, FuncContext, HostFunction, Imports, MemoryBackend, ModuleInstance, Store, engine::Config, types,
+};
 use types::TinyWasmModule;
 
 const WASM: &[u8] = include_bytes!("../../../examples/rust/out/tinywasm.wasm");
@@ -22,7 +24,8 @@ fn tinywasm_from_twasm(twasm: &[u8]) -> Result<TinyWasmModule> {
 }
 
 fn tinywasm_run(module: TinyWasmModule) -> Result<()> {
-    let mut store = Store::default();
+    let engine = Engine::new(Config::default().with_memory_backend(MemoryBackend::paged(64 * 1024)));
+    let mut store = Store::new(engine);
     let mut imports = Imports::default();
     imports.define("env", "printi32", HostFunction::from(&mut store, |_: FuncContext<'_>, _: i32| Ok(())));
     let instance = ModuleInstance::instantiate(&mut store, module.into(), Some(imports)).expect("instantiate");
diff --git a/crates/tinywasm/benches/tinywasm_modes.rs b/crates/tinywasm/benches/tinywasm_modes.rs
index f5f70d0..d7636f8 100644
--- a/crates/tinywasm/benches/tinywasm_modes.rs
+++ b/crates/tinywasm/benches/tinywasm_modes.rs
@@ -58,7 +58,7 @@ fn criterion_benchmark(c: &mut Criterion) {
     let mut group = c.benchmark_group("tinywasm_modes");
     group.measurement_time(BENCH_MEASUREMENT_TIME);
 
-    let per_instruction_engine = Engine::new(Config::new().fuel_policy(FuelPolicy::PerInstruction));
+    let per_instruction_engine = Engine::new(Config::new().with_fuel_policy(FuelPolicy::PerInstruction));
     group.bench_function("resume_fuel_per_instruction", |b| {
         b.iter_batched_ref(
             || {
@@ -70,7 +70,7 @@ fn criterion_benchmark(c: &mut Criterion) {
         )
     });
 
-    let weighted_engine = Engine::new(Config::new().fuel_policy(FuelPolicy::Weighted));
+    let weighted_engine = Engine::new(Config::new().with_fuel_policy(FuelPolicy::Weighted));
     group.bench_function("resume_fuel_weighted", |b| {
         b.iter_batched_ref(
             || setup_typed_func(module.clone(), Some(weighted_engine.clone())).expect("setup fuel weighted"),
diff --git a/crates/tinywasm/src/engine.rs b/crates/tinywasm/src/engine.rs
index c8f05e9..916e493 100644
--- a/crates/tinywasm/src/engine.rs
+++ b/crates/tinywasm/src/engine.rs
@@ -1,5 +1,8 @@
 use alloc::sync::Arc;
 
+/// Memory backend types and traits.
+pub use crate::store::{LinearMemory, MemoryBackend, PagedMemory, VecMemory};
+
 /// Global configuration for the WebAssembly interpreter
 ///
 /// Can be cheaply cloned and shared across multiple executions and threads.
@@ -66,6 +69,8 @@ pub struct Config {
     pub max_call_stack_size: usize,
     /// Fuel accounting policy used by budgeted execution.
     pub fuel_policy: FuelPolicy,
+    /// Backend used for runtime memories.
+    pub memory_backend: MemoryBackend,
 }
 
 impl Config {
@@ -75,10 +80,26 @@ impl Config {
     }
 
     /// Set the fuel accounting policy for budgeted execution.
-    pub fn fuel_policy(mut self, fuel_policy: FuelPolicy) -> Self {
+    pub fn with_fuel_policy(mut self, fuel_policy: FuelPolicy) -> Self {
         self.fuel_policy = fuel_policy;
         self
     }
+
+    /// Set the backend used for runtime memories.
+    pub fn with_memory_backend(mut self, memory_backend: MemoryBackend) -> Self {
+        self.memory_backend = memory_backend;
+        self
+    }
+
+    /// Get the current fuel policy
+    pub fn fuel_policy(&self) -> FuelPolicy {
+        self.fuel_policy
+    }
+
+    /// Get the current memory backend
+    pub fn memory_backend(&self) -> &MemoryBackend {
+        &self.memory_backend
+    }
 }
 
 impl Default for Config {
@@ -89,6 +110,7 @@ impl Default for Config {
             stack_128_size: DEFAULT_VALUE_STACK_128_SIZE,
             max_call_stack_size: DEFAULT_MAX_CALL_STACK_SIZE,
             fuel_policy: FuelPolicy::default(),
+            memory_backend: MemoryBackend::default(),
         }
     }
 }
diff --git a/crates/tinywasm/src/error.rs b/crates/tinywasm/src/error.rs
index 591ba99..6a0ae26 100644
--- a/crates/tinywasm/src/error.rs
+++ b/crates/tinywasm/src/error.rs
@@ -1,3 +1,4 @@
+use alloc::boxed::Box;
 use alloc::string::{String, ToString};
 use alloc::vec::Vec;
 use core::fmt::Debug;
@@ -18,7 +19,7 @@ pub enum Error {
     Linker(LinkingError),
 
     /// A WebAssembly feature is not supported
-    UnsupportedFeature(String),
+    UnsupportedFeature(&'static str),
 
     /// An unknown error occurred
     Other(String),
@@ -89,6 +90,9 @@ pub enum Trap {
     /// An unreachable instruction was executed
     Unreachable,
 
+    /// A host function returned an error
+    HostFunction(Box<dyn core::error::Error + Send + Sync>),
+
     /// An out-of-bounds memory access occurred
     MemoryOutOfBounds {
         /// The offset of the access
@@ -143,6 +147,9 @@ pub enum Trap {
         /// The actual type
         actual: FuncType,
     },
+
+    /// Catch-all for other messages
+    Other(&'static str),
 }
 
 impl Trap {
@@ -160,6 +167,8 @@ impl Trap {
             Self::UndefinedElement { .. } => "undefined element",
             Self::UninitializedElement { .. } => "uninitialized element",
             Self::IndirectCallTypeMismatch { .. } => "indirect call type mismatch",
+            Self::HostFunction(_) => "host function trap",
+            Self::Other(message) => message,
         }
     }
 }
@@ -231,6 +240,8 @@ impl Display for LinkingError {
 impl Display for Trap {
     fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
         match self {
+            Self::Other(message) => write!(f, "{message}"),
+            Self::HostFunction(message) => write!(f, "host function trap: {message}"),
             Self::Unreachable => write!(f, "unreachable"),
             Self::MemoryOutOfBounds { offset, len, max } => {
                 write!(f, "out of bounds memory access: offset={offset}, len={len}, max={max}")
@@ -265,6 +276,16 @@ impl Debug for Error {
 
 impl core::error::Error for Error {}
 
+#[cfg(feature = "std")]
+impl From<Error> for crate::std::io::Error {
+    fn from(value: Error) -> Self {
+        match value {
+            Error::Io(err) => err,
+            other => Self::other(other.to_string()),
+        }
+    }
+}
+
 #[cfg(feature = "parser")]
 impl From<tinywasm_parser::ParseError> for Error {
     fn from(value: tinywasm_parser::ParseError) -> Self {
diff --git a/crates/tinywasm/src/imports.rs b/crates/tinywasm/src/imports.rs
index 89578b8..d82b8a4 100644
--- a/crates/tinywasm/src/imports.rs
+++ b/crates/tinywasm/src/imports.rs
@@ -276,8 +276,7 @@ impl Imports {
                             return Err(LinkingError::incompatible_import_type(import).into());
                         };
                         let mem = store.state.get_mem(memory.0.addr);
-                        let (size, kind) = { (mem.page_count, mem.kind) };
-                        Self::compare_memory_types(import, &kind, import_ty, size)?;
+                        Self::compare_memory_types(import, &mem.kind, import_ty, mem.page_count)?;
                         imports.memories.push(memory.0.addr);
                     }
                     Extern::Function(func_handle) => {
@@ -327,8 +326,7 @@ impl Imports {
                     }
                     (ExternVal::Memory(memory_addr), ImportKind::Memory(ty)) => {
                         let mem = store.state.get_mem(memory_addr);
-                        let (size, kind) = { (mem.page_count, mem.kind) };
-                        Self::compare_memory_types(import, &kind, ty, size)?;
+                        Self::compare_memory_types(import, &mem.kind, ty, mem.page_count)?;
                         imports.memories.push(memory_addr);
                     }
                     (ExternVal::Func(func_addr), ImportKind::Function(ty)) => {
diff --git a/crates/tinywasm/src/instance.rs b/crates/tinywasm/src/instance.rs
index d2c3b2c..11c4191 100644
--- a/crates/tinywasm/src/instance.rs
+++ b/crates/tinywasm/src/instance.rs
@@ -133,7 +133,7 @@ impl ModuleInstance {
 
         addrs.funcs.extend(store.init_funcs(&module.0.funcs, idx));
         addrs.tables.extend(store.init_tables(&module.0.table_types, idx));
-        addrs.memories.extend(store.init_memories(&module.0.memory_types, idx));
+        addrs.memories.extend(store.init_memories(&module.0.memory_types, idx)?);
         let global_addrs = store.init_globals(addrs.globals, &module.0.globals, &addrs.funcs, idx)?;
         let (elem_addrs, elem_trapped) =
             store.init_elements(&addrs.tables, &addrs.funcs, &global_addrs, &module.0.elements, idx)?;
diff --git a/crates/tinywasm/src/interpreter/executor.rs b/crates/tinywasm/src/interpreter/executor.rs
index ca100b9..0c85d02 100644
--- a/crates/tinywasm/src/interpreter/executor.rs
+++ b/crates/tinywasm/src/interpreter/executor.rs
@@ -5,7 +5,7 @@ use core::hint::cold_path;
 use super::no_std_floats::NoStdFloatExt;
 
 use alloc::boxed::Box;
-use alloc::{rc::Rc, string::ToString};
+use alloc::rc::Rc;
 
 use interpreter::stack::CallFrame;
 use tinywasm_types::*;
@@ -29,10 +29,10 @@ pub(crate) struct Executor<'store, const BUDGETED: bool> {
 }
 
 impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
-    pub(crate) fn new(store: &'store mut Store, cf: CallFrame) -> Result<Self> {
+    pub(crate) fn new(store: &'store mut Store, cf: CallFrame) -> Self {
         let module = store.get_module_instance_raw(cf.module_addr).clone();
         let func = store.state.get_wasm_func(cf.func_addr).clone();
-        Ok(Self { module, store, cf, func })
+        Self { module, store, cf, func }
     }
 
     #[inline(always)]
@@ -48,7 +48,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
     }
 
     #[inline(always)]
-    fn exec(&mut self) -> Result<Option<()>> {
+    fn exec(&mut self) -> Result<Option<()>, Trap> {
         macro_rules! stack_op {
             (unary $ty:ty, |$v:ident| $expr:expr) => {{
                 let $v = self.store.value_stack.pop::<$ty>();
@@ -129,7 +129,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         #[rustfmt::skip]
         match next {
             Nop => {}
-            Unreachable => return Err(Trap::Unreachable.into()),
+            Unreachable => return Err(Trap::Unreachable),
             Drop32 => self.store.value_stack.drop::<Value32>(),
             Drop64 => self.store.value_stack.drop::<Value64>(),
             Drop128 => self.store.value_stack.drop::<Value128>(),
@@ -454,7 +454,16 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             V128Store64Lane(arg, lane) => self.exec_mem_store_lane::<i64, 8>(arg.mem_addr(), arg.offset(), *lane)?,
             V128Load32Zero(arg) => self.exec_mem_load::<i32, 4, Value128>(arg.mem_addr(), arg.offset(), |v| Value128::from_i32x4([v, 0, 0, 0]))?,
             V128Load64Zero(arg) => self.exec_mem_load::<i64, 8, Value128>(arg.mem_addr(), arg.offset(), |v| Value128::from_i64x2([v, 0]))?,
-            V128Const(arg) => self.exec_const(Value128::from(self.func.data.v128_constants.get(*arg as usize).copied().unwrap_or_else(|| {cold_path(); unreachable!("invalid v128 constant index") })))?,
+            V128Const(arg) => {
+                let val = match self.func.data.v128_constants.get(*arg as usize) {
+                    Some(val) => *val,
+                    None => {
+                        cold_path();
+                        unreachable!("invalid v128 constant index");
+                    }
+                };
+                self.exec_const(Value128(val))?
+            },
             I8x16ExtractLaneS(lane) => stack_op!(unary Value128 => i32, |v| v.extract_lane_i8(*lane) as i32),
             I8x16ExtractLaneU(lane) => stack_op!(unary Value128 => i32, |v| v.extract_lane_u8(*lane) as i32),
             I16x8ExtractLaneS(lane) => stack_op!(unary Value128 => i32, |v| v.extract_lane_i16(*lane) as i32),
@@ -622,8 +631,11 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             I64x2ExtendHighI32x4U => stack_op!(unary Value128, |a| a.i64x2_extend_high_i32x4_u()),
             I8x16Popcnt => stack_op!(unary Value128, |v| v.i8x16_popcnt()),
             I8x16Shuffle(idx) => {
-                let mask = self.func.data.v128_constants.get(*idx as usize).unwrap_or_else(|| {cold_path(); unreachable!("invalid i128 constant index")});
-                stack_op!(binary Value128, |a, b| Value128::i8x16_shuffle(a, b, Value128::from(*mask)))
+                let Some(mask) = self.func.data.v128_constants.get(*idx as usize) else {
+                    cold_path();
+                    unreachable!("invalid i128 constant index")
+                };
+                stack_op!(binary Value128, |a, b| Value128::i8x16_shuffle(a, b, Value128(*mask)))
             },
             I16x8Q15MulrSatS => stack_op!(binary Value128, |a, b| a.i16x8_q15mulr_sat_s(b)),
             I32x4DotI16x8S => stack_op!(binary Value128, |a, b| a.i32x4_dot_i16x8_s(b)),
@@ -770,7 +782,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         &mut self,
         wasm_func: WasmFunctionInstance,
         func_addr: FuncAddr,
-    ) -> Result<()> {
+    ) -> Result<(), Trap> {
         if !Rc::ptr_eq(&self.func, &wasm_func.func) {
             self.func = wasm_func.func.clone();
         }
@@ -779,11 +791,17 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             self.store.value_stack.truncate_keep_counts(self.cf.locals_base, wasm_func.func.params);
         }
 
-        let res = self.store.value_stack.enter_locals(&wasm_func.func.params, &wasm_func.func.locals);
-        let locals_base = res.map_err(|err| {
-            cold_path();
-            if IS_RETURN_CALL { err } else { Error::Trap(Trap::CallStackOverflow) }
-        })?;
+        let locals_base = match self.store.value_stack.enter_locals(&wasm_func.func.params, &wasm_func.func.locals) {
+            Ok(base) => base,
+            Err(err) => {
+                cold_path();
+                if IS_RETURN_CALL {
+                    return Err(err);
+                } else {
+                    return Err(Trap::CallStackOverflow);
+                }
+            }
+        };
 
         let new_call_frame = CallFrame::new(func_addr, wasm_func.owner, locals_base, wasm_func.func.locals);
 
@@ -799,14 +817,20 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
 
         Ok(())
     }
-    fn exec_call_host(&mut self, host_func: Rc<HostFunction>) -> Result<()> {
+    fn exec_call_host(&mut self, host_func: Rc<HostFunction>) -> Result<(), Trap> {
         let params = self.store.value_stack.pop_types(host_func.ty.params()).collect::<Box<_>>();
-        let res = host_func.call(FuncContext { store: self.store, module_addr: self.module.idx }, &params)?;
+        let res = match host_func.call(FuncContext { store: self.store, module_addr: self.module.idx }, &params) {
+            Ok(res) => res,
+            Err(err) => {
+                cold_path();
+                return Err(Trap::HostFunction(Box::new(err)));
+            }
+        };
         self.store.value_stack.extend_from_wasmvalues(&res)?;
         self.cf.incr_instr_ptr();
         Ok(())
     }
-    fn exec_call_direct<const IS_RETURN_CALL: bool>(&mut self, v: u32) -> Result<()> {
+    fn exec_call_direct<const IS_RETURN_CALL: bool>(&mut self, v: u32) -> Result<(), Trap> {
         self.charge_call_fuel(FUEL_COST_CALL_TOTAL);
         let addr = self.module.resolve_func_addr(v);
         match self.store.state.get_func(addr) {
@@ -815,7 +839,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         }
     }
 
-    fn exec_call_self<const IS_RETURN_CALL: bool>(&mut self) -> Result<()> {
+    fn exec_call_self<const IS_RETURN_CALL: bool>(&mut self) -> Result<(), Trap> {
         self.charge_call_fuel(FUEL_COST_CALL_TOTAL);
         let params = self.func.params;
         let locals = self.func.locals;
@@ -824,13 +848,19 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             self.store.value_stack.truncate_keep_counts(self.cf.locals_base, params);
         }
 
-        let res = self.store.value_stack.enter_locals(&params, &locals);
-        let locals_base = res.map_err(|err| {
-            cold_path();
-            if IS_RETURN_CALL { err } else { Error::Trap(Trap::CallStackOverflow) }
-        })?;
-        let new_call_frame = CallFrame::new(self.cf.func_addr, self.cf.module_addr, locals_base, locals);
+        let locals_base = match self.store.value_stack.enter_locals(&params, &locals) {
+            Ok(base) => base,
+            Err(err) => {
+                cold_path();
+                if IS_RETURN_CALL {
+                    return Err(err);
+                } else {
+                    return Err(Trap::CallStackOverflow);
+                }
+            }
+        };
 
+        let new_call_frame = CallFrame::new(self.cf.func_addr, self.cf.module_addr, locals_base, locals);
         if !IS_RETURN_CALL {
             self.cf.incr_instr_ptr();
             self.store.call_stack.push(self.cf)?;
@@ -839,7 +869,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         Ok(())
     }
 
-    fn exec_call_indirect<const IS_RETURN_CALL: bool>(&mut self, type_addr: u32, table_addr: u32) -> Result<()> {
+    fn exec_call_indirect<const IS_RETURN_CALL: bool>(&mut self, type_addr: u32, table_addr: u32) -> Result<(), Trap> {
         self.charge_call_fuel(FUEL_COST_CALL_TOTAL);
         // verify that the table is of the right type, this should be validated by the parser already
         let func_ref = {
@@ -847,15 +877,18 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             let table = self.store.state.get_table(self.module.resolve_table_addr(table_addr));
             assert!(table.kind.element_type == WasmType::RefFunc, "table is not of type funcref");
 
-            let table = table.get(table_idx).map_err(|_| {
+            let Ok(table) = table.get(table_idx) else {
                 cold_path();
-                Error::from(Trap::UndefinedElement { index: table_idx as usize })
-            })?;
+                return Err(Trap::UndefinedElement { index: table_idx as usize });
+            };
 
-            table.addr().ok_or_else(|| {
-                cold_path();
-                Error::from(Trap::UninitializedElement { index: table_idx as usize })
-            })?
+            match table.addr() {
+                Some(addr) => addr,
+                None => {
+                    cold_path();
+                    return Err(Trap::UninitializedElement { index: table_idx as usize });
+                }
+            }
         };
 
         let call_ty = self.module.func_ty(type_addr);
@@ -866,8 +899,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
                     return Err(Trap::IndirectCallTypeMismatch {
                         actual: wasm_func.ty().clone(),
                         expected: call_ty.clone(),
-                    }
-                    .into());
+                    });
                 }
 
                 self.exec_call::<IS_RETURN_CALL>(wasm_func.clone(), func_ref)
@@ -878,8 +910,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
                     return Err(Trap::IndirectCallTypeMismatch {
                         actual: host_func.ty.clone(),
                         expected: call_ty.clone(),
-                    }
-                    .into());
+                    });
                 }
 
                 self.exec_call_host(host_func.clone())
@@ -903,49 +934,28 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         false
     }
 
-    #[cfg(target_pointer_width = "64")]
-    fn effective_addr<const N: usize>(addr: u64, offset: u64) -> Result<usize> {
-        let Some(addr) = offset.checked_add(addr) else {
-            cold_path();
-            return Err(Error::Trap(Trap::MemoryOutOfBounds { offset: addr as usize, len: N, max: 0 }));
-        };
-        Ok(addr as usize)
-    }
-
-    #[cfg(not(target_pointer_width = "64"))]
-    fn effective_addr<const N: usize>(addr: u64, offset: u64) -> Result<usize> {
-        let Some(Ok(addr)) = offset.checked_add(addr).map(|a| a.try_into()) else {
-            cold_path();
-            return Err(Error::Trap(Trap::MemoryOutOfBounds { offset: addr as usize, len: N, max: 0 }));
-        };
-        Ok(addr)
-    }
-
     fn exec_store_local_local<T: InternalValue + MemValue<N>, const N: usize>(
         &mut self,
         memarg: MemoryArg,
         addr_local: u8,
         value_local: u8,
-    ) -> Result<()> {
+    ) -> Result<(), Trap> {
         let addr = u64::from(self.store.value_stack.local_get::<u32>(&self.cf, u16::from(addr_local)));
         let value = self.store.value_stack.local_get::<T>(&self.cf, u16::from(value_local)).to_mem_bytes();
         let mem = self.store.state.get_mem_mut(self.module.resolve_mem_addr(memarg.mem_addr()));
-        mem.store(Self::effective_addr::<N>(addr, memarg.offset())?, &value)?;
+        mem.store(addr, memarg.offset(), value)?;
         Ok(())
     }
 
-    fn exec_load_local_value<T: MemValue<N>, const N: usize>(&self, memarg: MemoryArg, addr_local: u8) -> Result<T> {
+    fn exec_load_local_value<T: MemValue<N>, const N: usize>(
+        &self,
+        memarg: MemoryArg,
+        addr_local: u8,
+    ) -> Result<T, Trap> {
         let mem = self.store.state.get_mem(self.module.resolve_mem_addr(memarg.mem_addr()));
         let addr = u64::from(self.store.value_stack.local_get::<u32>(&self.cf, u16::from(addr_local)));
-        mem.load_as::<N, T>(Self::effective_addr::<N>(addr, memarg.offset())?)
-    }
-
-    fn exec_load_local<T: InternalValue + MemValue<N>, const N: usize>(
-        &mut self,
-        mem: MemoryArg,
-        addr: u8,
-    ) -> Result<()> {
-        self.store.value_stack.push(self.exec_load_local_value::<T, N>(mem, addr)?)
+        let bytes = mem.load(addr, memarg.offset())?;
+        Ok(T::from_mem_bytes(bytes))
     }
 
     fn exec_load_local_tee<T: InternalValue + MemValue<N>, const N: usize>(
@@ -953,7 +963,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         memarg: MemoryArg,
         addr_local: u8,
         dst_local: u8,
-    ) -> Result<()> {
+    ) -> Result<(), Trap> {
         let value = self.exec_load_local_value::<T, N>(memarg, addr_local)?;
         self.store.value_stack.local_set(&self.cf, u16::from(dst_local), value);
         self.store.value_stack.push(value)?;
@@ -965,13 +975,13 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         memarg: MemoryArg,
         addr_local: u8,
         dst_local: u8,
-    ) -> Result<()> {
+    ) -> Result<(), Trap> {
         let value = self.exec_load_local_value::<T, N>(memarg, addr_local)?;
         self.store.value_stack.local_set(&self.cf, u16::from(dst_local), value);
         Ok(())
     }
 
-    fn exec_global_get(&mut self, global_index: u32) -> Result<()> {
+    fn exec_global_get(&mut self, global_index: u32) -> Result<(), Trap> {
         self.store.value_stack.push_dyn(self.store.state.get_global_val(self.module.resolve_global_addr(global_index)))
     }
 
@@ -992,22 +1002,22 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         self.store.state.set_global_val(global_addr, value);
     }
 
-    fn exec_const<T: InternalValue>(&mut self, val: T) -> Result<()> {
+    fn exec_const<T: InternalValue>(&mut self, val: T) -> Result<(), Trap> {
         self.store.value_stack.push(val)
     }
-    fn exec_ref_is_null(&mut self) -> Result<()> {
+    fn exec_ref_is_null(&mut self) -> Result<(), Trap> {
         let is_null = i32::from(self.store.value_stack.pop::<ValueRef>().is_null());
         self.store.value_stack.push::<i32>(is_null)
     }
 
-    fn exec_memory_size(&mut self, addr: u32) -> Result<()> {
+    fn exec_memory_size(&mut self, addr: u32) -> Result<(), Trap> {
         let mem = self.store.state.get_mem(self.module.resolve_mem_addr(addr));
         match mem.is_64bit() {
             true => self.store.value_stack.push::<i64>(mem.page_count as i64),
             false => self.store.value_stack.push::<i32>(mem.page_count as i32),
         }
     }
-    fn exec_memory_grow(&mut self, addr: u32) -> Result<()> {
+    fn exec_memory_grow(&mut self, addr: u32) -> Result<(), Trap> {
         let mem = self.store.state.get_mem_mut(self.module.resolve_mem_addr(addr));
         let is_64bit = mem.is_64bit();
         let pages_delta = match is_64bit {
@@ -1024,7 +1034,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         Ok(())
     }
 
-    fn exec_memory_copy(&mut self, dst_mem: u32, src_mem: u32) -> Result<()> {
+    fn exec_memory_copy(&mut self, dst_mem: u32, src_mem: u32) -> Result<(), Trap> {
         let size: i32 = self.store.value_stack.pop();
         let src: i32 = self.store.value_stack.pop();
         let dst: i32 = self.store.value_stack.pop();
@@ -1038,47 +1048,54 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             // copy between two memories
             let src_mem_addr = self.module.resolve_mem_addr(src_mem);
             let (dst_memory, src_memory) = self.store.state.get_mems_mut(dst_mem_addr, src_mem_addr);
-            dst_memory.copy_from_slice(dst as usize, src_memory.load(src as usize, size as usize)?)?;
+            dst_memory.copy_from_memory(dst as usize, src_memory, src as usize, size as usize)?;
         }
         Ok(())
     }
-    fn exec_memory_fill(&mut self, addr: u32) -> Result<()> {
+    fn exec_memory_fill(&mut self, addr: u32) -> Result<(), Trap> {
         let size: i32 = self.store.value_stack.pop();
         let val: i32 = self.store.value_stack.pop();
         let dst: i32 = self.store.value_stack.pop();
         self.exec_memory_fill_impl(addr, dst, val as u8, size)
     }
 
-    fn exec_memory_fill_imm(&mut self, addr: u32, val: u8, size: i32) -> Result<()> {
+    fn exec_memory_fill_imm(&mut self, addr: u32, val: u8, size: i32) -> Result<(), Trap> {
         let dst: i32 = self.store.value_stack.pop();
         self.exec_memory_fill_impl(addr, dst, val, size)
     }
 
-    fn exec_memory_fill_impl(&mut self, addr: u32, dst: i32, val: u8, size: i32) -> Result<()> {
-        self.store.state.get_mem_mut(self.module.resolve_mem_addr(addr)).fill(dst as usize, size as usize, val)
+    fn exec_memory_fill_impl(&mut self, addr: u32, dst: i32, val: u8, size: i32) -> Result<(), Trap> {
+        let mem = self.store.state.get_mem_mut(self.module.resolve_mem_addr(addr));
+        if mem.inner.fill(dst as usize, size as usize, val).is_none() {
+            cold_path();
+            return Err(Trap::MemoryOutOfBounds {
+                offset: dst as usize,
+                len: size as usize,
+                max: self.store.state.get_mem(self.module.resolve_mem_addr(addr)).inner.len(),
+            });
+        }
+        Ok(())
     }
 
-    fn exec_memory_init(&mut self, data_index: u32, mem_index: u32) -> Result<()> {
+    fn exec_memory_init(&mut self, data_index: u32, mem_index: u32) -> Result<(), Trap> {
         let size: i32 = self.store.value_stack.pop();
         let offset: i32 = self.store.value_stack.pop();
         let dst: i32 = self.store.value_stack.pop();
 
         let data_addr = self.module.resolve_data_addr(data_index) as usize;
         let Some(data) = self.store.state.data.get(data_addr) else {
-            cold_path();
             unreachable!("data segment not found, should have been validated by the parser")
         };
 
         let mem_addr = self.module.resolve_mem_addr(mem_index) as usize;
         let Some(mem) = self.store.state.memories.get_mut(mem_addr) else {
-            cold_path();
             unreachable!("memory not found, should have been validated by the parser")
         };
 
         let data_len = data.data.as_ref().map_or(0, |d| d.len());
-        if ((size + offset) as usize > data_len) || ((dst + size) as usize > mem.len()) {
+        if ((size + offset) as usize > data_len) || ((dst + size) as usize > mem.inner.len()) {
             cold_path();
-            return Err(Trap::MemoryOutOfBounds { offset: offset as usize, len: size as usize, max: data_len }.into());
+            return Err(Trap::MemoryOutOfBounds { offset: offset as usize, len: size as usize, max: data_len });
         }
 
         if size == 0 {
@@ -1087,12 +1104,16 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
 
         let Some(data) = &data.data else {
             cold_path();
-            return Err(Trap::MemoryOutOfBounds { offset: 0, len: 0, max: 0 }.into());
+            return Err(Trap::MemoryOutOfBounds { offset: 0, len: 0, max: 0 });
         };
 
-        mem.store(dst as usize, &data[offset as usize..((offset + size) as usize)])
+        if mem.inner.write_all(dst as usize, &data[offset as usize..((offset + size) as usize)]).is_none() {
+            cold_path();
+            return Err(Trap::MemoryOutOfBounds { offset: dst as usize, len: size as usize, max: mem.inner.len() });
+        }
+        Ok(())
     }
-    fn exec_table_copy(&mut self, dst_table: u32, src_table: u32) -> Result<()> {
+    fn exec_table_copy(&mut self, dst_table: u32, src_table: u32) -> Result<(), Trap> {
         let size: i32 = self.store.value_stack.pop();
         let src: i32 = self.store.value_stack.pop();
         let dst: i32 = self.store.value_stack.pop();
@@ -1114,15 +1135,23 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         mem_addr: tinywasm_types::MemAddr,
         offset: u64,
         lane: u8,
-    ) -> Result<()> {
-        let mut imm = self.store.value_stack.pop::<Value128>().to_mem_bytes();
-        let val = self.store.value_stack.pop::<i32>() as u64;
+    ) -> Result<(), Trap> {
         let mem = self.store.state.get_mem(self.module.resolve_mem_addr(mem_addr));
-        let addr = Self::effective_addr::<LOAD_SIZE>(val, offset)?;
-        let val = mem.load_as::<LOAD_SIZE, LOAD>(addr)?.to_mem_bytes();
+        let base = match mem.is_64bit() {
+            true => self.store.value_stack.pop::<i64>() as u64,
+            false => self.store.value_stack.pop::<i32>() as u32 as u64,
+        };
+        let val = match mem.load::<LOAD_SIZE>(base, offset) {
+            Ok(val) => val,
+            Err(e) => {
+                cold_path();
+                return Err(e);
+            }
+        };
         let offset = lane as usize * LOAD_SIZE;
+        let mut imm = self.store.value_stack.pop::<Value128>().to_mem_bytes();
         imm[offset..offset + LOAD_SIZE].copy_from_slice(&val);
-        self.store.value_stack.push(Value128::from_mem_bytes(imm))?;
+        self.store.value_stack.push(Value128(imm))?;
         Ok(())
     }
 
@@ -1132,15 +1161,24 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         mem_addr: tinywasm_types::MemAddr,
         offset: u64,
         cast: impl Fn(LOAD) -> TARGET,
-    ) -> Result<()> {
+    ) -> Result<(), Trap> {
         let mem = self.store.state.get_mem(self.module.resolve_mem_addr(mem_addr));
         let base = match mem.is_64bit() {
             true => self.store.value_stack.pop::<i64>() as u64,
             false => self.store.value_stack.pop::<i32>() as u32 as u64,
         };
-        let addr = Self::effective_addr::<LOAD_SIZE>(base, offset)?;
-        let val = mem.load_as::<LOAD_SIZE, LOAD>(addr)?;
-        self.store.value_stack.push(cast(val))
+
+        match mem.load::<LOAD_SIZE>(base, offset) {
+            Ok(val) => {
+                let val = cast(LOAD::from_mem_bytes(val));
+                self.store.value_stack.push(val)?;
+                Ok(())
+            }
+            Err(e) => {
+                cold_path();
+                Err(e)
+            }
+        }
     }
 
     fn exec_mem_store_lane<U: MemValue<N> + Copy, const N: usize>(
@@ -1148,7 +1186,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         mem_addr: tinywasm_types::MemAddr,
         offset: u64,
         lane: u8,
-    ) -> Result<()> {
+    ) -> Result<(), Trap> {
         let bytes = self.store.value_stack.pop::<Value128>().to_mem_bytes();
         let lane_offset = lane as usize * N;
         let mut val = [0u8; N];
@@ -1159,8 +1197,13 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             true => self.store.value_stack.pop::<i64>() as u64,
             false => self.store.value_stack.pop::<i32>() as u32 as u64,
         };
-        let effective_addr = Self::effective_addr::<N>(addr, offset)?;
-        mem.store(effective_addr, &val)
+        match mem.store(addr, offset, val) {
+            Ok(()) => Ok(()),
+            Err(e) => {
+                cold_path();
+                Err(e)
+            }
+        }
     }
 
     fn exec_mem_store<T: InternalValue, U: MemValue<N>, const N: usize>(
@@ -1168,7 +1211,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
         mem_addr: tinywasm_types::MemAddr,
         offset: u64,
         cast: impl Fn(T) -> U,
-    ) -> Result<()> {
+    ) -> Result<(), Trap> {
         let val = self.store.value_stack.pop::<T>();
         let val = cast(val).to_mem_bytes();
 
@@ -1178,44 +1221,47 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             true => self.store.value_stack.pop::<i64>() as u64,
             false => self.store.value_stack.pop::<i32>() as u32 as u64,
         };
-        let effective_addr = Self::effective_addr::<N>(addr, offset)?;
-        mem.store(effective_addr, &val)
+        match mem.store(addr, offset, val) {
+            Ok(()) => Ok(()),
+            Err(e) => {
+                cold_path();
+                Err(e)
+            }
+        }
     }
 
-    fn exec_table_get(&mut self, table_index: u32) -> Result<()> {
+    fn exec_table_get(&mut self, table_index: u32) -> Result<(), Trap> {
         let idx: i32 = self.store.value_stack.pop::<i32>();
         let table = self.store.state.get_table(self.module.resolve_table_addr(table_index));
         let v = table.get_wasm_val(idx as u32)?;
         self.store.value_stack.push_dyn(v.into())
     }
-    fn exec_table_set(&mut self, table_index: u32) -> Result<()> {
+    fn exec_table_set(&mut self, table_index: u32) -> Result<(), Trap> {
         let val = self.store.value_stack.pop::<ValueRef>();
         let idx = self.store.value_stack.pop::<i32>() as u32;
         let table = self.store.state.get_table_mut(self.module.resolve_table_addr(table_index));
         table.set(idx, val.addr().into())
     }
-    fn exec_table_size(&mut self, table_index: u32) -> Result<()> {
+    fn exec_table_size(&mut self, table_index: u32) -> Result<(), Trap> {
         let table = self.store.state.get_table(self.module.resolve_table_addr(table_index));
         self.store.value_stack.push(table.size())
     }
-    fn exec_table_init(&mut self, elem_index: u32, table_index: u32) -> Result<()> {
+    fn exec_table_init(&mut self, elem_index: u32, table_index: u32) -> Result<(), Trap> {
         let size: i32 = self.store.value_stack.pop(); // n
         let offset: i32 = self.store.value_stack.pop(); // s
         let dst: i32 = self.store.value_stack.pop(); // d
         let elem_addr = self.module.resolve_elem_addr(elem_index) as usize;
-        let elem =
-            self.store.state.elements.get(elem_addr).ok_or_else(|| Error::Other("element not found".to_string()))?;
+        let elem = self.store.state.elements.get(elem_addr).ok_or_else(|| Trap::Other("element not found"))?;
 
         let table_addr = self.module.resolve_table_addr(table_index) as usize;
-        let table =
-            self.store.state.tables.get_mut(table_addr).ok_or_else(|| Error::Other("table not found".to_string()))?;
+        let table = self.store.state.tables.get_mut(table_addr).ok_or_else(|| Trap::Other("table not found"))?;
 
         let elem_len = elem.items.as_ref().map_or(0, alloc::vec::Vec::len);
         let table_len = table.size();
 
         if size < 0 || ((size + offset) as usize > elem_len) || ((dst + size) > table_len) {
             cold_path();
-            return Err(Trap::TableOutOfBounds { offset: offset as usize, len: size as usize, max: elem_len }.into());
+            return Err(Trap::TableOutOfBounds { offset: offset as usize, len: size as usize, max: elem_len });
         }
 
         if size == 0 {
@@ -1224,17 +1270,17 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
 
         if let ElementKind::Active { .. } = elem.kind {
             cold_path();
-            return Err(Error::Other("table.init with active element".to_string()));
+            return Err(Trap::Other("table.init with active element"));
         }
 
         let Some(items) = elem.items.as_ref() else {
             cold_path();
-            return Err(Trap::TableOutOfBounds { offset: 0, len: 0, max: 0 }.into());
+            return Err(Trap::TableOutOfBounds { offset: 0, len: 0, max: 0 });
         };
 
         table.init(i64::from(dst), &items[offset as usize..(offset + size) as usize])
     }
-    fn exec_table_grow(&mut self, table_index: u32) -> Result<()> {
+    fn exec_table_grow(&mut self, table_index: u32) -> Result<(), Trap> {
         let table = self.store.state.get_table_mut(self.module.resolve_table_addr(table_index));
         let sz = table.size();
         let n = self.store.value_stack.pop::<i32>();
@@ -1244,7 +1290,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
             Err(_) => self.store.value_stack.push(-1_i32),
         }
     }
-    fn exec_table_fill(&mut self, table_index: u32) -> Result<()> {
+    fn exec_table_fill(&mut self, table_index: u32) -> Result<(), Trap> {
         let table = self.store.state.get_table_mut(self.module.resolve_table_addr(table_index));
 
         let n = self.store.value_stack.pop::<i32>();
@@ -1253,11 +1299,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
 
         if i + n > table.size() {
             cold_path();
-            return Err(Error::Trap(Trap::TableOutOfBounds {
-                offset: i as usize,
-                len: n as usize,
-                max: table.size() as usize,
-            }));
+            return Err(Trap::TableOutOfBounds { offset: i as usize, len: n as usize, max: table.size() as usize });
         }
 
         if n == 0 {
@@ -1270,7 +1312,7 @@ impl<'store, const BUDGETED: bool> Executor<'store, BUDGETED> {
 
 impl<'store> Executor<'store, false> {
     #[inline(always)]
-    pub(crate) fn run_to_completion(&mut self) -> Result<()> {
+    pub(crate) fn run_to_completion(&mut self) -> Result<(), Trap> {
         // ideally we use `loop_match` / `become` once thats stabilized
         loop {
             if self.exec()?.is_some() {
@@ -1281,7 +1323,7 @@ impl<'store> Executor<'store, false> {
 
     #[cfg(feature = "std")]
     #[inline(always)]
-    pub(crate) fn run_with_time_budget(&mut self, time_budget: core::time::Duration) -> Result<ExecState> {
+    pub(crate) fn run_with_time_budget(&mut self, time_budget: core::time::Duration) -> Result<ExecState, Trap> {
         use crate::std::time::Instant;
         let start = Instant::now();
         if time_budget.is_zero() {
@@ -1304,7 +1346,7 @@ impl<'store> Executor<'store, false> {
 
 impl<'store> Executor<'store, true> {
     #[inline(always)]
-    pub(crate) fn run_with_fuel(&mut self, fuel: u32) -> Result<ExecState> {
+    pub(crate) fn run_with_fuel(&mut self, fuel: u32) -> Result<ExecState, Trap> {
         self.store.execution_fuel = fuel;
         if self.store.execution_fuel == 0 {
             return Ok(ExecState::Suspended(self.cf));
diff --git a/crates/tinywasm/src/interpreter/mod.rs b/crates/tinywasm/src/interpreter/mod.rs
index ab94d47..db094e0 100644
--- a/crates/tinywasm/src/interpreter/mod.rs
+++ b/crates/tinywasm/src/interpreter/mod.rs
@@ -7,7 +7,7 @@ pub(crate) mod values;
 #[cfg(not(feature = "std"))]
 mod no_std_floats;
 
-use crate::{Result, Store, interpreter::stack::CallFrame};
+use crate::{Result, Store, Trap, interpreter::stack::CallFrame};
 pub(crate) use simd::*;
 pub(crate) use values::*;
 
@@ -26,12 +26,12 @@ pub(crate) enum ExecState {
 pub(crate) struct InterpreterRuntime;
 
 impl InterpreterRuntime {
-    pub(crate) fn exec(store: &mut Store, cf: CallFrame) -> Result<()> {
-        executor::Executor::<false>::new(store, cf)?.run_to_completion()
+    pub(crate) fn exec(store: &mut Store, cf: CallFrame) -> Result<(), Trap> {
+        executor::Executor::<false>::new(store, cf).run_to_completion()
     }
 
-    pub(crate) fn exec_with_fuel(store: &mut Store, cf: CallFrame, fuel: u32) -> Result<ExecState> {
-        executor::Executor::<true>::new(store, cf)?.run_with_fuel(fuel)
+    pub(crate) fn exec_with_fuel(store: &mut Store, cf: CallFrame, fuel: u32) -> Result<ExecState, Trap> {
+        executor::Executor::<true>::new(store, cf).run_with_fuel(fuel)
     }
 
     #[cfg(feature = "std")]
@@ -39,7 +39,7 @@ impl InterpreterRuntime {
         store: &mut Store,
         cf: CallFrame,
         time_budget: core::time::Duration,
-    ) -> Result<ExecState> {
-        executor::Executor::<false>::new(store, cf)?.run_with_time_budget(time_budget)
+    ) -> Result<ExecState, Trap> {
+        executor::Executor::<false>::new(store, cf).run_with_time_budget(time_budget)
     }
 }
diff --git a/crates/tinywasm/src/interpreter/num_helpers.rs b/crates/tinywasm/src/interpreter/num_helpers.rs
index 6fa4df0..88fa691 100644
--- a/crates/tinywasm/src/interpreter/num_helpers.rs
+++ b/crates/tinywasm/src/interpreter/num_helpers.rs
@@ -2,8 +2,8 @@ pub(crate) trait TinywasmIntExt
 where
     Self: Sized,
 {
-    fn checked_wrapping_rem(self, rhs: Self) -> Result<Self>;
-    fn wasm_checked_div(self, rhs: Self) -> Result<Self>;
+    fn checked_wrapping_rem(self, rhs: Self) -> Result<Self, Trap>;
+    fn wasm_checked_div(self, rhs: Self) -> Result<Self, Trap>;
 }
 
 /// Doing the actual conversion from float to int is a bit tricky, because
@@ -34,10 +34,10 @@ macro_rules! checked_conv_float {
         let v = $self.store.value_stack.pop::<$from>();
         let (min, max) = float_min_max!($from, $intermediate);
         if unlikely(v.is_nan()) {
-            return Err(Error::Trap(crate::Trap::InvalidConversionToInt));
+            return Err(crate::Trap::InvalidConversionToInt);
         }
         if unlikely(v <= min || v >= max) {
-            return Err(Error::Trap(crate::Trap::IntegerOverflow));
+            return Err(crate::Trap::IntegerOverflow);
         }
         $self.store.value_stack.push::<$to>((v as $intermediate as $to).into())?;
     }};
@@ -46,8 +46,8 @@ macro_rules! checked_conv_float {
 pub(crate) use checked_conv_float;
 pub(crate) use float_min_max;
 
-pub(super) fn trap_0() -> Error {
-    Error::Trap(crate::Trap::DivisionByZero)
+pub(super) fn trap_0() -> Trap {
+    crate::Trap::DivisionByZero
 }
 pub(crate) trait TinywasmFloatExt {
     fn tw_minimum(self, other: Self) -> Self;
@@ -55,7 +55,7 @@ pub(crate) trait TinywasmFloatExt {
     fn tw_nearest(self) -> Self;
 }
 
-use crate::{Error, Result};
+use crate::{Result, Trap};
 
 #[cfg(not(feature = "std"))]
 use super::no_std_floats::NoStdFloatExt;
@@ -160,19 +160,19 @@ impl_wrapping_self_sh! { i32 i64 u32 u64 }
 macro_rules! impl_checked_wrapping_rem {
     ($($t:ty)*) => ($(
         impl TinywasmIntExt for $t {
-            fn checked_wrapping_rem(self, rhs: Self) -> Result<Self> {
+            fn checked_wrapping_rem(self, rhs: Self) -> Result<Self, crate::Trap> {
                 if rhs == 0 {
-                    Err(Error::Trap(crate::Trap::DivisionByZero))
+                    Err(crate::Trap::DivisionByZero)
                 } else {
                     Ok(self.wrapping_rem(rhs))
                 }
             }
 
-            fn wasm_checked_div(self, rhs: Self) -> Result<Self> {
+            fn wasm_checked_div(self, rhs: Self) -> Result<Self, crate::Trap> {
                 if rhs == 0 {
-                    Err(Error::Trap(crate::Trap::DivisionByZero))
+                    Err(crate::Trap::DivisionByZero)
                 } else {
-                    self.checked_div(rhs).ok_or_else(|| Error::Trap(crate::Trap::IntegerOverflow))
+                    self.checked_div(rhs).ok_or_else(|| crate::Trap::IntegerOverflow)
                 }
             }
         }
diff --git a/crates/tinywasm/src/interpreter/simd/mod.rs b/crates/tinywasm/src/interpreter/simd/mod.rs
index 9d926f7..d3cdd98 100644
--- a/crates/tinywasm/src/interpreter/simd/mod.rs
+++ b/crates/tinywasm/src/interpreter/simd/mod.rs
@@ -16,7 +16,7 @@ use crate::MemValue;
 
 #[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
 /// A 128-bit SIMD value
-pub struct Value128([u8; 16]);
+pub struct Value128(pub(super) [u8; 16]);
 
 impl From<[u8; 16]> for Value128 {
     fn from(bytes: [u8; 16]) -> Self {
diff --git a/crates/tinywasm/src/interpreter/simd/tests.rs b/crates/tinywasm/src/interpreter/simd/tests.rs
index ca69942..7400f6b 100644
--- a/crates/tinywasm/src/interpreter/simd/tests.rs
+++ b/crates/tinywasm/src/interpreter/simd/tests.rs
@@ -32,7 +32,7 @@ fn swizzle_matches_reference() {
             *byte = (x & 0xff) as u8;
         }
 
-        let got = Value128::from(a).i8x16_swizzle(Value128::from(s));
+        let got = Value128(a).i8x16_swizzle(Value128(s));
         let expected = ref_swizzle(a, s).into();
         assert_eq!(got, expected, "seed={seed}");
     }
@@ -53,7 +53,7 @@ fn shuffle_matches_reference() {
             *byte = (x & 0xff) as u8;
         }
 
-        let got = Value128::i8x16_shuffle(Value128::from(a), Value128::from(b), Value128::from(idx));
+        let got = Value128::i8x16_shuffle(Value128(a), Value128(b), Value128(idx));
         let expected = ref_shuffle(a, b, idx).into();
         assert_eq!(got, expected, "seed={seed}");
     }
diff --git a/crates/tinywasm/src/interpreter/stack/call_stack.rs b/crates/tinywasm/src/interpreter/stack/call_stack.rs
index 40f162e..c080929 100644
--- a/crates/tinywasm/src/interpreter/stack/call_stack.rs
+++ b/crates/tinywasm/src/interpreter/stack/call_stack.rs
@@ -24,10 +24,10 @@ impl CallStack {
     }
 
     #[inline(always)]
-    pub(crate) fn push(&mut self, call_frame: CallFrame) -> Result<()> {
+    pub(crate) fn push(&mut self, call_frame: CallFrame) -> Result<(), Trap> {
         if self.stack.len() == self.stack.capacity() {
             cold_path();
-            return Err(Trap::CallStackOverflow.into());
+            return Err(Trap::CallStackOverflow);
         }
 
         self.stack.push(call_frame);
diff --git a/crates/tinywasm/src/interpreter/stack/value_stack.rs b/crates/tinywasm/src/interpreter/stack/value_stack.rs
index 335bef6..fdf5f83 100644
--- a/crates/tinywasm/src/interpreter/stack/value_stack.rs
+++ b/crates/tinywasm/src/interpreter/stack/value_stack.rs
@@ -32,10 +32,10 @@ impl<T: Copy + Default> Stack<T> {
     }
 
     #[inline(always)]
-    pub(crate) fn push(&mut self, value: T) -> Result<()> {
+    pub(crate) fn push(&mut self, value: T) -> Result<(), Trap> {
         if self.data.len() == self.data.capacity() {
             cold_path();
-            return Err(Trap::ValueStackOverflow.into());
+            return Err(Trap::ValueStackOverflow);
         }
 
         self.data.push(value);
@@ -98,14 +98,14 @@ impl<T: Copy + Default> Stack<T> {
     }
 
     #[inline(always)]
-    pub(crate) fn enter_locals(&mut self, param_count: usize, local_count: usize) -> Result<u32> {
+    pub(crate) fn enter_locals(&mut self, param_count: usize, local_count: usize) -> Result<u32, Trap> {
         debug_assert!(param_count <= local_count && param_count <= self.data.len());
 
         let start = self.data.len() - param_count;
         let end = start + local_count;
         if end > self.data.capacity() {
             cold_path();
-            return Err(Trap::ValueStackOverflow.into());
+            return Err(Trap::ValueStackOverflow);
         }
 
         self.data.resize(end, T::default());
@@ -169,7 +169,7 @@ impl ValueStack {
     }
 
     #[inline(always)]
-    pub(crate) fn push<T: InternalValue>(&mut self, value: T) -> Result<()> {
+    pub(crate) fn push<T: InternalValue>(&mut self, value: T) -> Result<(), Trap> {
         T::stack_push(self, value)
     }
 
@@ -179,7 +179,7 @@ impl ValueStack {
     }
 
     #[inline(always)]
-    pub(crate) fn select<T: InternalValue>(&mut self) -> Result<()> {
+    pub(crate) fn select<T: InternalValue>(&mut self) -> Result<(), Trap> {
         let cond: i32 = self.pop();
         let val2: T = self.pop();
         if cond == 0 {
@@ -204,7 +204,7 @@ impl ValueStack {
         val_types.into_iter().map(|val_type| self.pop_wasmvalue(*val_type))
     }
 
-    pub(crate) fn enter_locals(&mut self, params: &ValueCounts, locals: &ValueCounts) -> Result<StackBase> {
+    pub(crate) fn enter_locals(&mut self, params: &ValueCounts, locals: &ValueCounts) -> Result<StackBase, Trap> {
         let locals_base32 = self.stack_32.enter_locals(params.c32 as usize, locals.c32 as usize)?;
         let locals_base64 = self.stack_64.enter_locals(params.c64 as usize, locals.c64 as usize)?;
         let locals_base128 = self.stack_128.enter_locals(params.c128 as usize, locals.c128 as usize)?;
@@ -237,7 +237,7 @@ impl ValueStack {
         T::local_set(self, frame, index, value);
     }
 
-    pub(crate) fn push_dyn(&mut self, value: TinyWasmValue) -> Result<()> {
+    pub(crate) fn push_dyn(&mut self, value: TinyWasmValue) -> Result<(), Trap> {
         match value {
             TinyWasmValue::Value32(v) => self.stack_32.push(v)?,
             TinyWasmValue::Value64(v) => self.stack_64.push(v)?,
@@ -259,7 +259,7 @@ impl ValueStack {
         }
     }
 
-    pub(crate) fn extend_from_wasmvalues(&mut self, values: &[WasmValue]) -> Result<()> {
+    pub(crate) fn extend_from_wasmvalues(&mut self, values: &[WasmValue]) -> Result<(), Trap> {
         for value in values {
             match value {
                 WasmValue::I32(v) => self.stack_32.push(*v as u32)?,
diff --git a/crates/tinywasm/src/interpreter/values.rs b/crates/tinywasm/src/interpreter/values.rs
index 3d58879..1971279 100644
--- a/crates/tinywasm/src/interpreter/values.rs
+++ b/crates/tinywasm/src/interpreter/values.rs
@@ -146,7 +146,7 @@ mod sealed {
 }
 
 pub(crate) trait InternalValue: sealed::Sealed + Into<TinyWasmValue> + Copy + Default {
-    fn stack_push(stack: &mut ValueStack, value: Self) -> Result<()>;
+    fn stack_push(stack: &mut ValueStack, value: Self) -> Result<(), crate::Trap>;
     fn local_get(stack: &ValueStack, frame: &CallFrame, index: LocalAddr) -> Self;
     fn local_update(stack: &mut ValueStack, frame: &CallFrame, index: LocalAddr, func: impl FnOnce(Self) -> Self);
     fn local_set(stack: &mut ValueStack, frame: &CallFrame, index: LocalAddr, value: Self);
@@ -167,7 +167,7 @@ macro_rules! impl_internalvalue {
 
             impl InternalValue for $outer {
                 #[inline(always)]
-                fn stack_push(stack: &mut ValueStack, value: Self) -> Result<()> {
+                fn stack_push(stack: &mut ValueStack, value: Self) -> Result<(), crate::Trap> {
                     stack.$stack.push($to_stack(value))
                 }
 
diff --git a/crates/tinywasm/src/lib.rs b/crates/tinywasm/src/lib.rs
index 6180de3..7806016 100644
--- a/crates/tinywasm/src/lib.rs
+++ b/crates/tinywasm/src/lib.rs
@@ -115,7 +115,7 @@ use interpreter::InterpreterRuntime;
 
 /// Global configuration for the WebAssembly interpreter
 pub mod engine;
-pub use engine::Engine;
+pub use engine::{Engine, LinearMemory, MemoryBackend, PagedMemory, VecMemory};
 
 #[cfg(feature = "parser")]
 /// Re-export of [`tinywasm_parser`]. Requires `parser` feature.
diff --git a/crates/tinywasm/src/reference.rs b/crates/tinywasm/src/reference.rs
index e1d3d48..125fa22 100644
--- a/crates/tinywasm/src/reference.rs
+++ b/crates/tinywasm/src/reference.rs
@@ -1,11 +1,11 @@
-use core::ffi::CStr;
 use core::hint::cold_path;
 
 use alloc::string::{String, ToString};
+use alloc::vec::Vec;
 use alloc::{ffi::CString, format};
 
 use crate::store::{GlobalInstance, TableElement, TableInstance};
-use crate::{Error, MemoryInstance, Result, Store};
+use crate::{Error, MemoryInstance, Result, Store, Trap};
 use tinywasm_types::{
     Addr, ExternRef, FuncRef, GlobalAddr, GlobalType, MemAddr, MemoryArch, MemoryType, TableAddr, TableType, WasmType,
     WasmValue,
@@ -25,9 +25,9 @@ impl StoreItem {
     }
 
     #[inline]
-    pub(crate) fn validate_store(&self, store: &Store) -> Result<()> {
+    pub(crate) fn validate_store(&self, store: &Store) -> Result<(), Trap> {
         if self.store_id != store.id() {
-            return Err(Error::InvalidStore);
+            return Err(Trap::Other("invalid store"));
         }
         Ok(())
     }
@@ -48,6 +48,96 @@ pub struct Table(pub(crate) StoreItem);
 #[cfg_attr(feature = "debug", derive(Debug))]
 pub struct Global(pub(crate) StoreItem);
 
+/// A cursor over a [`Memory`] instance.
+///
+/// Available with the `std` feature enabled.
+#[cfg(feature = "std")]
+pub struct MemoryCursor<'a> {
+    memory: &'a mut MemoryInstance,
+    position: u64,
+}
+
+#[cfg(feature = "std")]
+impl<'a> MemoryCursor<'a> {
+    fn new(memory: &'a mut MemoryInstance, position: u64) -> Self {
+        Self { memory, position }
+    }
+
+    fn offset(&self) -> crate::std::io::Result<usize> {
+        usize::try_from(self.position).map_err(|_| {
+            crate::std::io::Error::new(crate::std::io::ErrorKind::InvalidInput, "cursor position exceeds usize")
+        })
+    }
+
+    fn advance(&mut self, amount: usize) -> crate::std::io::Result<()> {
+        self.position = self.position.checked_add(amount as u64).ok_or_else(|| {
+            crate::std::io::Error::new(crate::std::io::ErrorKind::InvalidInput, "cursor position overflow")
+        })?;
+        Ok(())
+    }
+
+    /// Returns the current cursor position.
+    pub const fn position(&self) -> u64 {
+        self.position
+    }
+
+    /// Sets the current cursor position.
+    pub fn set_position(&mut self, position: u64) {
+        self.position = position;
+    }
+}
+
+#[cfg(feature = "std")]
+impl crate::std::io::Read for MemoryCursor<'_> {
+    fn read(&mut self, buf: &mut [u8]) -> crate::std::io::Result<usize> {
+        let offset = self.offset()?;
+        let read = self.memory.inner.read(offset, buf);
+        self.advance(read)?;
+        Ok(read)
+    }
+}
+
+#[cfg(feature = "std")]
+impl crate::std::io::Write for MemoryCursor<'_> {
+    fn write(&mut self, buf: &[u8]) -> crate::std::io::Result<usize> {
+        let offset = self.offset()?;
+        let written = self.memory.inner.write(offset, buf);
+        self.advance(written)?;
+        Ok(written)
+    }
+
+    fn flush(&mut self) -> crate::std::io::Result<()> {
+        Ok(())
+    }
+}
+
+#[cfg(feature = "std")]
+impl crate::std::io::Seek for MemoryCursor<'_> {
+    fn seek(&mut self, pos: crate::std::io::SeekFrom) -> crate::std::io::Result<u64> {
+        let len = self.memory.inner.len() as i128;
+        let current = i128::from(self.position);
+
+        let next = match pos {
+            crate::std::io::SeekFrom::Start(offset) => i128::from(offset),
+            crate::std::io::SeekFrom::End(offset) => len + i128::from(offset),
+            crate::std::io::SeekFrom::Current(offset) => current + i128::from(offset),
+        };
+
+        if next < 0 {
+            return Err(crate::std::io::Error::new(
+                crate::std::io::ErrorKind::InvalidInput,
+                "invalid seek before start",
+            ));
+        }
+
+        let next = u64::try_from(next).map_err(|_| {
+            crate::std::io::Error::new(crate::std::io::ErrorKind::InvalidInput, "invalid seek position")
+        })?;
+        self.position = next;
+        Ok(next)
+    }
+}
+
 impl Memory {
     #[inline]
     pub(crate) const fn from_store_addr(store_id: usize, addr: MemAddr) -> Self {
@@ -57,13 +147,29 @@ impl Memory {
     /// Create a new memory in the given store.
     pub fn new(store: &mut Store, ty: MemoryType) -> Result<Self> {
         if let MemoryArch::I64 = ty.arch() {
-            return Err(Error::UnsupportedFeature("64-bit memories".to_string()));
+            return Err(Error::UnsupportedFeature("64-bit memories"));
         }
         let addr = store.state.memories.len() as MemAddr;
-        store.state.memories.push(MemoryInstance::new(ty));
+        store.state.memories.push(MemoryInstance::new(ty, &store.engine.config().memory_backend)?);
         Ok(Self::from_store_addr(store.id(), addr))
     }
 
+    /// Creates a cursor positioned at the start of this memory.
+    ///
+    /// Available with the `std` feature enabled.
+    #[cfg(feature = "std")]
+    pub fn cursor<'a>(&self, store: &'a mut Store) -> Result<MemoryCursor<'a>> {
+        self.cursor_at(store, 0)
+    }
+
+    /// Creates a cursor positioned at `position` bytes from the start of this memory.
+    ///
+    /// Available with the `std` feature enabled.
+    #[cfg(feature = "std")]
+    pub fn cursor_at<'a>(&self, store: &'a mut Store, position: u64) -> Result<MemoryCursor<'a>> {
+        Ok(MemoryCursor::new(self.instance_mut(store)?, position))
+    }
+
     #[inline]
     fn instance<'a>(&self, store: &'a Store) -> Result<&'a MemoryInstance> {
         self.0.validate_store(store)?;
@@ -76,24 +182,49 @@ impl Memory {
         Ok(store.state.get_mem_mut(self.0.addr))
     }
 
-    /// Returns the full raw memory data.
-    pub fn data<'a>(&self, store: &'a Store) -> Result<&'a [u8]> {
-        Ok(&self.instance(store)?.data)
+    /// Returns the raw memory byte length.
+    pub fn len(&self, store: &Store) -> Result<usize> {
+        Ok(self.instance(store)?.inner.len())
     }
 
-    /// Returns the full raw mutable memory data.
-    pub fn data_mut<'a>(&self, store: &'a mut Store) -> Result<&'a mut [u8]> {
-        Ok(&mut self.instance_mut(store)?.data)
+    /// Returns the memory type, including page size and limits.
+    pub fn ty(&self, store: &Store) -> Result<MemoryType> {
+        Ok(self.instance(store)?.kind)
     }
 
-    /// Returns the raw memory byte length.
-    pub fn data_size(&self, store: &Store) -> Result<usize> {
-        Ok(self.instance(store)?.data.len())
+    /// Reads up to `dst.len()` bytes from memory and returns the number of bytes read.
+    ///
+    /// Depending on the configured backend, this may return fewer bytes than requested even when
+    /// more data is available. Use [`Self::read_exact`] or [`Self::read_vec`] when you need a full
+    /// range.
+    pub fn read(&self, store: &Store, offset: usize, dst: &mut [u8]) -> Result<usize> {
+        Ok(self.instance(store)?.inner.read(offset, dst))
     }
 
-    /// Load a slice of memory.
-    pub fn load<'a>(&self, store: &'a Store, offset: usize, len: usize) -> Result<&'a [u8]> {
-        self.instance(store)?.load(offset, len)
+    /// Writes up to `src.len()` bytes into memory and returns the number of bytes written.
+    ///
+    /// Depending on the configured backend, this may return fewer bytes than requested even when
+    /// more space is available. Use [`Self::copy_from_slice`] when you need the full slice written.
+    pub fn write(&self, store: &mut Store, offset: usize, src: &[u8]) -> Result<usize> {
+        Ok(self.instance_mut(store)?.inner.write(offset, src))
+    }
+
+    /// Reads exactly `dst.len()` bytes from memory.
+    pub fn read_exact(&self, store: &Store, offset: usize, dst: &mut [u8]) -> Result<()> {
+        self.instance(store)?.inner.read_exact(offset, dst).ok_or_else(|| {
+            Error::Trap(crate::Trap::MemoryOutOfBounds {
+                offset,
+                len: dst.len(),
+                max: self.instance(store).unwrap().inner.len(),
+            })
+        })
+    }
+
+    /// Reads `len` bytes from memory into a newly allocated buffer.
+    pub fn read_vec(&self, store: &Store, offset: usize, len: usize) -> Result<Vec<u8>> {
+        self.instance(store)?.inner.read_vec(offset, len).ok_or_else(|| {
+            Error::Trap(crate::Trap::MemoryOutOfBounds { offset, len, max: self.instance(store).unwrap().inner.len() })
+        })
     }
 
     /// Grow the memory by the given number of pages.
@@ -108,50 +239,54 @@ impl Memory {
 
     /// Copy a slice of memory to another place in memory.
     pub fn copy_within(&self, store: &mut Store, src: usize, dst: usize, len: usize) -> Result<()> {
-        self.instance_mut(store)?.copy_within(dst, src, len)
+        self.instance_mut(store)?.copy_within(dst, src, len)?;
+        Ok(())
     }
 
     /// Fill a slice of memory with a value.
     pub fn fill(&self, store: &mut Store, offset: usize, len: usize, val: u8) -> Result<()> {
-        self.instance_mut(store)?.fill(offset, len, val)
+        self.instance_mut(store)?.inner.fill(offset, len, val).ok_or_else(|| {
+            Error::Trap(crate::Trap::MemoryOutOfBounds { offset, len, max: self.instance(store).unwrap().inner.len() })
+        })
     }
 
-    /// Store a slice of memory.
-    pub fn store(&self, store: &mut Store, offset: usize, data: &[u8]) -> Result<()> {
-        self.instance_mut(store)?.store(offset, data)
+    /// Copies a full slice into memory.
+    pub fn copy_from_slice(&self, store: &mut Store, offset: usize, data: &[u8]) -> Result<()> {
+        self.instance_mut(store)?.inner.write_all(offset, data).ok_or_else(|| {
+            Error::Trap(crate::Trap::MemoryOutOfBounds {
+                offset,
+                len: data.len(),
+                max: self.instance(store).unwrap().inner.len(),
+            })
+        })
     }
 
-    /// Load a C-style string from memory.
-    pub fn load_cstr<'a>(&self, store: &'a Store, offset: usize, len: usize) -> Result<&'a CStr> {
-        CStr::from_bytes_with_nul(self.load(store, offset, len)?)
+    /// Reads a C-style string from memory.
+    pub fn read_cstring(&self, store: &Store, offset: usize, len: usize) -> Result<CString> {
+        CString::from_vec_with_nul(self.read_vec(store, offset, len)?)
             .map_err(|e| crate::Error::Other(format!("Invalid C-style string: {e}")))
     }
 
-    /// Load a C-style string from memory, stopping at the first nul byte.
-    pub fn load_cstr_until_nul<'a>(&self, store: &'a Store, offset: usize, max_len: usize) -> Result<&'a CStr> {
-        CStr::from_bytes_until_nul(self.load(store, offset, max_len)?)
+    /// Reads a C-style string from memory, stopping at the first null byte.
+    pub fn read_cstring_until_null(&self, store: &Store, offset: usize, max_len: usize) -> Result<CString> {
+        let bytes = self.read_vec(store, offset, max_len)?;
+        let Some(null) = bytes.iter().position(|byte| *byte == 0) else {
+            return Err(crate::Error::Other("Invalid C-style string: missing null terminator".to_string()));
+        };
+
+        CString::from_vec_with_nul(bytes[..=null].to_vec())
             .map_err(|e| crate::Error::Other(format!("Invalid C-style string: {e}")))
     }
 
-    /// Load a UTF-8 string from memory.
-    pub fn load_string(&self, store: &Store, offset: usize, len: usize) -> Result<String> {
-        String::from_utf8(self.load(store, offset, len)?.to_vec())
+    /// Reads a UTF-8 string from memory.
+    pub fn read_string(&self, store: &Store, offset: usize, len: usize) -> Result<String> {
+        String::from_utf8(self.read_vec(store, offset, len)?)
             .map_err(|e| crate::Error::Other(format!("Invalid UTF-8 string: {e}")))
     }
 
-    /// Load a C-style string from memory.
-    pub fn load_cstring(&self, store: &Store, offset: usize, len: usize) -> Result<CString> {
-        Ok(CString::from(self.load_cstr(store, offset, len)?))
-    }
-
-    /// Load a C-style string from memory, stopping at the first nul byte.
-    pub fn load_cstring_until_nul(&self, store: &Store, offset: usize, max_len: usize) -> Result<CString> {
-        Ok(CString::from(self.load_cstr_until_nul(store, offset, max_len)?))
-    }
-
-    /// Load a JavaScript-style utf-16 string from memory.
-    pub fn load_js_string(&self, store: &Store, offset: usize, len: usize) -> Result<String> {
-        let bytes = self.load(store, offset, len)?;
+    /// Reads a JavaScript-style utf-16 string from memory.
+    pub fn read_js_string(&self, store: &Store, offset: usize, len: usize) -> Result<String> {
+        let bytes = self.read_vec(store, offset, len)?;
         let mut string = String::new();
         for i in 0..(len / 2) {
             let c = u16::from_le_bytes([bytes[i * 2], bytes[i * 2 + 1]]);
@@ -171,11 +306,11 @@ fn table_element_to_value(element_type: WasmType, element: TableElement) -> Wasm
     }
 }
 
-fn table_value_to_element(element_type: WasmType, value: WasmValue) -> Result<TableElement> {
+fn table_value_to_element(element_type: WasmType, value: WasmValue) -> Result<TableElement, Trap> {
     match (element_type, value) {
         (WasmType::RefFunc, WasmValue::RefFunc(func_ref)) => Ok(TableElement::from(func_ref.addr())),
         (WasmType::RefExtern, WasmValue::RefExtern(extern_ref)) => Ok(TableElement::from(extern_ref.addr())),
-        _ => Err(Error::Other("invalid table value type".to_string())),
+        _ => Err(Trap::Other("invalid table value type")),
     }
 }
 
@@ -204,7 +339,7 @@ impl Table {
     }
 
     #[inline]
-    fn instance_mut<'a>(&self, store: &'a mut Store) -> Result<&'a mut TableInstance> {
+    fn instance_mut<'a>(&self, store: &'a mut Store) -> Result<&'a mut TableInstance, Trap> {
         self.0.validate_store(store)?;
         Ok(store.state.get_table_mut(self.0.addr))
     }
@@ -221,7 +356,7 @@ impl Table {
 
     /// Get a table element as a wasm reference value.
     pub fn get(&self, store: &Store, index: TableAddr) -> Result<WasmValue> {
-        self.instance(store)?.get_wasm_val(index)
+        Ok(self.instance(store)?.get_wasm_val(index)?)
     }
 
     /// Load a range of table elements and iterate over wasm reference values.
@@ -238,14 +373,14 @@ impl Table {
     }
 
     /// Set a table element.
-    pub fn set(&self, store: &mut Store, index: TableAddr, value: WasmValue) -> Result<()> {
+    pub fn set(&self, store: &mut Store, index: TableAddr, value: WasmValue) -> Result<(), Trap> {
         let table = self.instance_mut(store)?;
         let value = table_value_to_element(table.kind.element_type, value)?;
         table.set(index, value)
     }
 
     /// Copy elements within the same table.
-    pub fn copy_within(&self, store: &mut Store, src: usize, dst: usize, len: usize) -> Result<()> {
+    pub fn copy_within(&self, store: &mut Store, src: usize, dst: usize, len: usize) -> Result<(), Trap> {
         self.instance_mut(store)?.copy_within(dst, src, len)
     }
 
diff --git a/crates/tinywasm/src/store/memory.rs b/crates/tinywasm/src/store/memory.rs
deleted file mode 100644
index 64754e6..0000000
--- a/crates/tinywasm/src/store/memory.rs
+++ /dev/null
@@ -1,284 +0,0 @@
-use core::hint::cold_path;
-
-use crate::{Error, Result, log};
-use alloc::vec;
-use alloc::vec::Vec;
-use tinywasm_types::{MemoryArch, MemoryType};
-
-/// A WebAssembly Memory Instance
-///
-/// See <https://webassembly.github.io/spec/core/exec/runtime.html#memory-instances>
-#[cfg_attr(feature = "debug", derive(Debug))]
-pub(crate) struct MemoryInstance {
-    pub(crate) kind: MemoryType,
-    pub(crate) data: Vec<u8>,
-    pub(crate) page_count: usize,
-}
-
-impl MemoryInstance {
-    pub(crate) fn new(kind: MemoryType) -> Self {
-        assert!(kind.page_count_initial() <= kind.page_count_max());
-        log::debug!("initializing memory with {} pages of {} bytes", kind.page_count_initial(), kind.page_size());
-        Self { kind, data: vec![0; kind.initial_size() as usize], page_count: kind.page_count_initial() as usize }
-    }
-
-    pub(crate) const fn is_64bit(&self) -> bool {
-        matches!(self.kind.arch(), MemoryArch::I64)
-    }
-
-    pub(crate) const fn len(&self) -> usize {
-        self.data.len()
-    }
-
-    const fn trap_oob(&self, addr: usize, len: usize) -> Error {
-        cold_path();
-        Error::Trap(crate::Trap::MemoryOutOfBounds { offset: addr, len, max: self.data.len() })
-    }
-
-    pub(crate) fn store(&mut self, addr: usize, data: &[u8]) -> Result<()> {
-        let Some(end) = addr.checked_add(data.len()) else {
-            return Err(self.trap_oob(addr, data.len()));
-        };
-
-        if end > self.data.len() || end < addr {
-            return Err(self.trap_oob(addr, data.len()));
-        }
-        self.data[addr..end].copy_from_slice(data);
-        Ok(())
-    }
-
-    pub(crate) fn load(&self, addr: usize, len: usize) -> Result<&[u8]> {
-        let Some(end) = addr.checked_add(len) else {
-            return Err(self.trap_oob(addr, len));
-        };
-
-        if end > self.data.len() || end < addr {
-            return Err(self.trap_oob(addr, len));
-        }
-
-        Ok(&self.data[addr..end])
-    }
-
-    pub(crate) fn load_as<const SIZE: usize, T: MemValue<SIZE>>(&self, addr: usize) -> Result<T> {
-        let Some(end) = addr.checked_add(SIZE) else {
-            return Err(self.trap_oob(addr, SIZE));
-        };
-
-        if end > self.data.len() {
-            return Err(self.trap_oob(addr, SIZE));
-        }
-
-        Ok(T::from_mem_bytes(match self.data[addr..end].try_into() {
-            Ok(bytes) => bytes,
-            Err(_) => return Err(self.trap_oob(addr, SIZE)),
-        }))
-    }
-
-    pub(crate) fn fill(&mut self, addr: usize, len: usize, val: u8) -> Result<()> {
-        let end = addr.checked_add(len).ok_or_else(|| self.trap_oob(addr, len))?;
-        if end > self.data.len() {
-            return Err(self.trap_oob(addr, len));
-        }
-        self.data[addr..end].fill(val);
-        Ok(())
-    }
-
-    pub(crate) fn copy_from_slice(&mut self, dst: usize, src: &[u8]) -> Result<()> {
-        let end = dst.checked_add(src.len()).ok_or_else(|| self.trap_oob(dst, src.len()))?;
-        if end > self.data.len() {
-            return Err(self.trap_oob(dst, src.len()));
-        }
-
-        self.data[dst..end].copy_from_slice(src);
-        Ok(())
-    }
-
-    pub(crate) fn copy_within(&mut self, dst: usize, src: usize, len: usize) -> Result<()> {
-        // Calculate the end of the source slice
-        let src_end = src.checked_add(len).ok_or_else(|| self.trap_oob(src, len))?;
-        if src_end > self.data.len() {
-            return Err(self.trap_oob(src, len));
-        }
-
-        // Calculate the end of the destination slice
-        let dst_end = dst.checked_add(len).ok_or_else(|| self.trap_oob(dst, len))?;
-        if dst_end > self.data.len() {
-            return Err(self.trap_oob(dst, len));
-        }
-
-        // Perform the copy
-        self.data.copy_within(src..src_end, dst);
-        Ok(())
-    }
-
-    pub(crate) fn grow(&mut self, pages_delta: i64) -> Option<i64> {
-        if pages_delta < 0 {
-            cold_path();
-            log::debug!("memory.grow failed: negative delta {}", pages_delta);
-            return None;
-        }
-
-        let current_pages = self.page_count;
-        let pages_delta = usize::try_from(pages_delta).ok()?;
-        let new_pages = current_pages.checked_add(pages_delta)?;
-        let max_pages = self.kind.page_count_max().try_into().unwrap_or(usize::MAX);
-
-        if new_pages > max_pages {
-            cold_path();
-            log::debug!("memory.grow failed: new_pages={}, max_pages={}", new_pages, max_pages);
-            return None;
-        }
-
-        let new_size = (new_pages as u64).checked_mul(self.kind.page_size())?;
-        if new_size > self.kind.max_size() {
-            cold_path();
-            log::debug!("memory.grow failed: new_size={}, max_size={}", new_size, self.kind.max_size());
-            return None;
-        }
-
-        let new_size = usize::try_from(new_size).ok()?;
-        if new_size == self.data.len() {
-            return i64::try_from(current_pages).ok();
-        }
-
-        self.page_count = new_pages;
-        self.data.resize(new_size, 0);
-        i64::try_from(current_pages).ok()
-    }
-}
-
-/// A trait for types that can be converted to and from static byte arrays
-pub(crate) trait MemValue<const N: usize>: Copy + Default {
-    /// Store a value in memory
-    fn to_mem_bytes(self) -> [u8; N];
-
-    /// Load a value from memory
-    fn from_mem_bytes(bytes: [u8; N]) -> Self;
-}
-
-macro_rules! impl_mem_traits {
-    ($($ty:ty, $size:expr),*) => {
-        $(
-            impl MemValue<$size> for $ty {
-                #[inline(always)]
-                fn from_mem_bytes(bytes: [u8; $size]) -> Self {
-                    <$ty>::from_le_bytes(bytes)
-                }
-
-                #[inline(always)]
-                fn to_mem_bytes(self) -> [u8; $size] {
-                    self.to_le_bytes()
-                }
-            }
-        )*
-    }
-}
-
-impl_mem_traits!(u8, 1, i8, 1, u16, 2, i16, 2, u32, 4, i32, 4, f32, 4, u64, 8, i64, 8, f64, 8);
-
-#[cfg(test)]
-mod memory_instance_tests {
-    use super::*;
-    use tinywasm_types::MemoryArch;
-
-    fn create_test_memory() -> MemoryInstance {
-        let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
-        MemoryInstance::new(kind)
-    }
-
-    #[test]
-    fn test_memory_store_and_load() {
-        let mut memory = create_test_memory();
-        let data_to_store = [1, 2, 3, 4];
-        assert!(memory.store(0, &data_to_store).is_ok());
-        let loaded_data = memory.load(0, data_to_store.len()).unwrap();
-        assert_eq!(loaded_data, &data_to_store);
-    }
-
-    #[test]
-    fn test_memory_store_out_of_bounds() {
-        let mut memory = create_test_memory();
-        let data_to_store = [1, 2, 3, 4];
-        assert!(memory.store(memory.data.len(), &data_to_store).is_err());
-    }
-
-    #[test]
-    fn test_memory_fill() {
-        let mut memory = create_test_memory();
-        assert!(memory.fill(0, 10, 42).is_ok());
-        assert_eq!(&memory.data[0..10], &[42; 10]);
-    }
-
-    #[test]
-    fn test_memory_fill_out_of_bounds() {
-        let mut memory = create_test_memory();
-        assert!(memory.fill(memory.data.len(), 10, 42).is_err());
-    }
-
-    #[test]
-    fn test_memory_copy_within() {
-        let mut memory = create_test_memory();
-        memory.fill(0, 10, 1).unwrap();
-        assert!(memory.copy_within(10, 0, 10).is_ok());
-        assert_eq!(&memory.data[10..20], &[1; 10]);
-    }
-
-    #[test]
-    fn test_memory_copy_within_out_of_bounds() {
-        let mut memory = create_test_memory();
-        assert!(memory.copy_within(memory.data.len(), 0, 10).is_err());
-    }
-
-    #[test]
-    fn test_memory_grow() {
-        let mut memory = create_test_memory();
-        let original_pages = memory.page_count;
-        assert_eq!(memory.grow(1), Some(original_pages as i64));
-        assert_eq!(memory.page_count, original_pages + 1);
-    }
-
-    #[test]
-    fn test_memory_grow_out_of_bounds() {
-        let mut memory = create_test_memory();
-        assert!(memory.grow(memory.kind.max_size() as i64 + 1).is_none());
-    }
-
-    #[test]
-    fn test_memory_grow_max_pages() {
-        let mut memory = create_test_memory();
-        assert_eq!(memory.grow(1), Some(1));
-        assert_eq!(memory.grow(1), None);
-    }
-
-    #[test]
-    fn test_memory_grow_negative_delta() {
-        let mut memory = create_test_memory();
-        let original_pages = memory.page_count;
-
-        assert_eq!(memory.grow(-1), None);
-        assert_eq!(memory.page_count, original_pages);
-    }
-
-    #[test]
-    fn test_memory_custom_page_size_out_of_bounds() {
-        let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), Some(1));
-        let mut memory = MemoryInstance::new(kind);
-
-        let data_to_store = [1, 2];
-        assert!(memory.store(0, &data_to_store).is_err());
-    }
-
-    #[test]
-    fn test_memory_custom_page_size_grow() {
-        let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), Some(1));
-        let mut memory = MemoryInstance::new(kind);
-
-        assert_eq!(memory.grow(1), Some(1));
-
-        let data_to_store = [1, 2];
-        assert!(memory.store(0, &data_to_store).is_ok());
-
-        let loaded_data = memory.load(0, data_to_store.len()).unwrap();
-        assert_eq!(loaded_data, &data_to_store);
-    }
-}
diff --git a/crates/tinywasm/src/store/memory/instance.rs b/crates/tinywasm/src/store/memory/instance.rs
new file mode 100644
index 0000000..7761f3f
--- /dev/null
+++ b/crates/tinywasm/src/store/memory/instance.rs
@@ -0,0 +1,262 @@
+use alloc::format;
+use tinywasm_types::MemoryArch;
+use tinywasm_types::MemoryType;
+
+use crate::Error;
+use crate::MemoryBackend;
+use crate::Result;
+use crate::Trap;
+
+use super::MemoryStorage;
+use super::memory_oob;
+use core::hint::cold_path;
+
+/// A WebAssembly Memory Instance
+///
+/// See <https://webassembly.github.io/spec/core/exec/runtime.html#memory-instances>
+#[cfg_attr(feature = "debug", derive(Debug))]
+pub(crate) struct MemoryInstance {
+    pub(crate) kind: MemoryType,
+    pub(crate) inner: MemoryStorage,
+    pub(crate) page_count: usize,
+}
+
+impl MemoryInstance {
+    const COPY_CHUNK_SIZE: usize = 4 * 1024;
+
+    pub(crate) fn new(kind: MemoryType, backend: &MemoryBackend) -> Result<Self> {
+        assert!(kind.page_count_initial() <= kind.page_count_max());
+
+        let initial_len = usize::try_from(kind.initial_size())
+            .map_err(|_| Error::UnsupportedFeature("memory size exceeds the host address space"))?;
+
+        log::debug!("initializing memory with {} pages of {} bytes", kind.page_count_initial(), kind.page_size());
+
+        let storage = backend.create(kind, initial_len)?;
+        if storage.len() != initial_len {
+            return Err(Error::Other(format!(
+                "memory backend returned {} bytes for a memory that requires {initial_len}",
+                storage.len()
+            )));
+        }
+
+        Ok(Self { kind, inner: storage, page_count: kind.page_count_initial() as usize })
+    }
+
+    pub(crate) const fn is_64bit(&self) -> bool {
+        matches!(self.kind.arch(), MemoryArch::I64)
+    }
+
+    #[inline(always)]
+    pub(crate) fn load<const SIZE: usize>(&self, base: u64, offset: u64) -> Result<[u8; SIZE], Trap> {
+        // the compiler doesn't optimize .as_slice().try_into() for some reason, so we have to manually copy the bytes into an array
+        // heavy usage of cold_path() seems to help a lot from looking at profile data
+        match SIZE {
+            1 => {
+                let res = match self.inner.read_8(base, offset) {
+                    Ok(bytes) => bytes,
+                    Err(e) => {
+                        cold_path();
+                        return Err(e);
+                    }
+                };
+                let mut bytes = [0; SIZE];
+                bytes[0] = res;
+                Ok(bytes)
+            }
+            2 => {
+                let res = match self.inner.read_16(base, offset) {
+                    Ok(bytes) => bytes,
+                    Err(e) => {
+                        cold_path();
+                        return Err(e);
+                    }
+                };
+                let mut bytes = [0; SIZE];
+                bytes[0] = res[0];
+                bytes[1] = res[1];
+                Ok(bytes)
+            }
+            4 => {
+                let mut bytes = [0; SIZE];
+                let res = match self.inner.read_32(base, offset) {
+                    Ok(bytes) => bytes,
+                    Err(e) => {
+                        cold_path();
+                        return Err(e);
+                    }
+                };
+                bytes[0] = res[0];
+                bytes[1] = res[1];
+                bytes[2] = res[2];
+                bytes[3] = res[3];
+                Ok(bytes)
+            }
+            8 => {
+                let mut bytes = [0; SIZE];
+                let res = match self.inner.read_64(base, offset) {
+                    Ok(bytes) => bytes,
+                    Err(e) => {
+                        cold_path();
+                        return Err(e);
+                    }
+                };
+                bytes[0] = res[0];
+                bytes[1] = res[1];
+                bytes[2] = res[2];
+                bytes[3] = res[3];
+                bytes[4] = res[4];
+                bytes[5] = res[5];
+                bytes[6] = res[6];
+                bytes[7] = res[7];
+                Ok(bytes)
+            }
+            16 => {
+                let mut bytes = [0; SIZE];
+                let res = match self.inner.read_128(base, offset) {
+                    Ok(bytes) => bytes,
+                    Err(e) => {
+                        cold_path();
+                        return Err(e);
+                    }
+                };
+                bytes[0] = res[0];
+                bytes[1] = res[1];
+                bytes[2] = res[2];
+                bytes[3] = res[3];
+                bytes[4] = res[4];
+                bytes[5] = res[5];
+                bytes[6] = res[6];
+                bytes[7] = res[7];
+                bytes[8] = res[8];
+                bytes[9] = res[9];
+                bytes[10] = res[10];
+                bytes[11] = res[11];
+                bytes[12] = res[12];
+                bytes[13] = res[13];
+                bytes[14] = res[14];
+                bytes[15] = res[15];
+                Ok(bytes)
+            }
+            _ => unreachable!("unsupported fixed-size read width {SIZE}"),
+        }
+    }
+
+    #[inline(always)]
+    pub(crate) fn store<const SIZE: usize>(&mut self, base: u64, offset: u64, bytes: [u8; SIZE]) -> Result<(), Trap> {
+        // the compiler doesn't optimize .as_slice().try_into() for some reason, so we have to manually copy the bytes into an array
+        // heavy usage of cold_path() seems to help a lot from looking at profile data
+        let res = match SIZE {
+            1 => self.inner.write_8(base, offset, bytes[0]),
+            2 => self.inner.write_16(base, offset, [bytes[0], bytes[1]]),
+            4 => self.inner.write_32(base, offset, [bytes[0], bytes[1], bytes[2], bytes[3]]),
+            8 => self.inner.write_64(
+                base,
+                offset,
+                [bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7]],
+            ),
+            16 => self.inner.write_128(
+                base,
+                offset,
+                [
+                    bytes[0], bytes[1], bytes[2], bytes[3], bytes[4], bytes[5], bytes[6], bytes[7], bytes[8], bytes[9],
+                    bytes[10], bytes[11], bytes[12], bytes[13], bytes[14], bytes[15],
+                ],
+            ),
+            _ => unreachable!("unsupported fixed-size write width {SIZE}"),
+        };
+
+        if let Err(e) = res {
+            cold_path();
+            return Err(e);
+        }
+        Ok(())
+    }
+
+    pub(crate) fn copy_from_memory(
+        &mut self,
+        dst: usize,
+        src_memory: &MemoryInstance,
+        src: usize,
+        len: usize,
+    ) -> Result<(), Trap> {
+        fn check_range(mem: &MemoryStorage, addr: usize, len: usize) -> Result<(), crate::Trap> {
+            let Some(end) = addr.checked_add(len) else {
+                cold_path();
+                return Err(memory_oob(addr, len, mem.len()));
+            };
+
+            if end > mem.len() || end < addr {
+                cold_path();
+                return Err(memory_oob(addr, len, mem.len()));
+            }
+            Ok(())
+        }
+
+        check_range(&src_memory.inner, src, len)?;
+        check_range(&self.inner, dst, len)?;
+
+        if len == 0 {
+            return Ok(());
+        }
+
+        let mut buf = [0u8; Self::COPY_CHUNK_SIZE];
+        let mut copied = 0;
+        while copied < len {
+            let chunk_len = buf.len().min(len - copied);
+            src_memory.inner.read_exact(src + copied, &mut buf[..chunk_len]).ok_or_else(|| {
+                cold_path();
+                memory_oob(src + copied, chunk_len, src_memory.inner.len())
+            })?;
+            self.inner.write_all(dst + copied, &buf[..chunk_len]).ok_or_else(|| {
+                cold_path();
+                memory_oob(dst + copied, chunk_len, self.inner.len())
+            })?;
+            copied += chunk_len;
+        }
+
+        Ok(())
+    }
+
+    pub(crate) fn copy_within(&mut self, dst: usize, src: usize, len: usize) -> Result<(), Trap> {
+        self.inner.copy_within(dst, src, len).ok_or_else(|| {
+            cold_path();
+            memory_oob(dst, len, self.inner.len())
+        })
+    }
+
+    pub(crate) fn grow(&mut self, pages_delta: i64) -> Option<i64> {
+        if pages_delta < 0 {
+            cold_path();
+            log::debug!("memory.grow failed: negative delta {}", pages_delta);
+            return None;
+        }
+
+        let current_pages = self.page_count;
+        let pages_delta = usize::try_from(pages_delta).ok()?;
+        let new_pages = current_pages.checked_add(pages_delta)?;
+        let max_pages = self.kind.page_count_max().try_into().unwrap_or(usize::MAX);
+
+        if new_pages > max_pages {
+            cold_path();
+            log::debug!("memory.grow failed: new_pages={}, max_pages={}", new_pages, max_pages);
+            return None;
+        }
+
+        let new_size = (new_pages as u64).checked_mul(self.kind.page_size())?;
+        if new_size > self.kind.max_size() {
+            cold_path();
+            log::debug!("memory.grow failed: new_size={}, max_size={}", new_size, self.kind.max_size());
+            return None;
+        }
+
+        let new_size = usize::try_from(new_size).ok()?;
+        if new_size == self.inner.len() {
+            return i64::try_from(current_pages).ok();
+        }
+
+        self.inner.grow_to(new_size)?;
+        self.page_count = new_pages;
+        i64::try_from(current_pages).ok()
+    }
+}
diff --git a/crates/tinywasm/src/store/memory/mod.rs b/crates/tinywasm/src/store/memory/mod.rs
new file mode 100644
index 0000000..d62b80e
--- /dev/null
+++ b/crates/tinywasm/src/store/memory/mod.rs
@@ -0,0 +1,566 @@
+use alloc::boxed::Box;
+use alloc::format;
+use alloc::sync::Arc;
+use alloc::vec;
+use alloc::vec::Vec;
+use core::hint::cold_path;
+use core::ops::DerefMut;
+use core::{cmp::min, ops::Deref};
+
+use tinywasm_types::MemoryType;
+
+use crate::{Error, Result};
+
+mod instance;
+
+mod paged;
+#[path = "vec.rs"]
+mod vec_memory;
+
+pub(crate) use instance::MemoryInstance;
+pub use {paged::PagedMemory, vec_memory::VecMemory};
+
+/// Backend storage for a linear memory.
+pub trait LinearMemory {
+    /// Returns the current memory length in bytes.
+    fn len(&self) -> usize;
+
+    /// Returns true if the memory is empty.
+    fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    /// Grows the memory to `new_len` bytes.
+    ///
+    /// The runtime only calls this with lengths that are exact multiples of the Wasm page size for
+    /// the owning memory.
+    fn grow_to(&mut self, new_len: usize) -> Option<()>;
+
+    /// Reads up to `dst.len()` bytes starting at `addr` and returns the number of bytes read.
+    ///
+    /// Backends may return fewer bytes than requested even when more data is available. This lets
+    /// non-contiguous backends stop at a natural boundary such as the end of a chunk.
+    fn read(&self, addr: usize, dst: &mut [u8]) -> usize;
+
+    /// Writes up to `src.len()` bytes starting at `addr` and returns the number of bytes written.
+    ///
+    /// Backends may return fewer bytes than requested even when more space is available. This lets
+    /// non-contiguous backends stop at a natural boundary such as the end of a chunk.
+    fn write(&mut self, addr: usize, src: &[u8]) -> usize;
+
+    /// Writes all bytes in `src` starting at `addr`, or returns `None` if any byte could not be written.
+    fn write_all(&mut self, addr: usize, src: &[u8]) -> Option<()> {
+        let end = addr.checked_add(src.len())?;
+        if end > self.len() {
+            return None;
+        }
+
+        let mut offset = 0;
+        while offset < src.len() {
+            let written = self.write(addr + offset, &src[offset..]);
+            if written == 0 {
+                return None;
+            }
+            offset += written;
+        }
+
+        Some(())
+    }
+
+    /// Fills the range `[addr, addr + len)` with `val`.
+    fn fill(&mut self, addr: usize, len: usize, val: u8) -> Option<()> {
+        let end = addr.checked_add(len)?;
+        if end > self.len() {
+            return None;
+        }
+
+        let mut offset = 0;
+        while offset < len {
+            let chunk_len = min(len - offset, 1024);
+            let chunk = vec![val; chunk_len];
+            self.write_all(addr + offset, &chunk)?;
+            offset += chunk_len;
+        }
+
+        Some(())
+    }
+
+    /// Copies `len` bytes from `src` to `dst` within the same memory.
+    fn copy_within(&mut self, dst: usize, src: usize, len: usize) -> Option<()> {
+        let src_end = src.checked_add(len)?;
+        let dst_end = dst.checked_add(len)?;
+        if src_end > self.len() || dst_end > self.len() {
+            return None;
+        }
+
+        if len == 0 || dst == src {
+            return Some(());
+        }
+
+        // If the source and destination ranges are disjoint, we can copy forward without a temporary buffer.
+        if dst < src || dst >= src_end {
+            let mut offset = 0;
+            while offset < len {
+                let chunk_len = min(len - offset, 1024);
+                let chunk = vec![0; chunk_len];
+                self.read_exact(src + offset, &mut chunk.clone())?;
+                self.write_all(dst + offset, &chunk)?;
+                offset += chunk_len;
+            }
+        } else {
+            // Otherwise, we need to copy backward to avoid overwriting the source data before it's read.
+            let mut offset = len;
+            while offset > 0 {
+                let chunk_len = min(offset, 1024);
+                offset -= chunk_len;
+                let chunk = vec![0; chunk_len];
+                self.read_exact(src + offset, &mut chunk.clone())?;
+                self.write_all(dst + offset, &chunk)?;
+            }
+        }
+
+        Some(())
+    }
+
+    /// Reads exactly `dst.len()` bytes starting at `addr`.
+    fn read_exact(&self, addr: usize, dst: &mut [u8]) -> Option<()> {
+        let end = addr.checked_add(dst.len())?;
+        if end > self.len() {
+            return None;
+        }
+
+        let mut offset = 0;
+        while offset < dst.len() {
+            let read = self.read(addr + offset, &mut dst[offset..]);
+            if read == 0 {
+                return None;
+            }
+            offset += read;
+        }
+
+        Some(())
+    }
+
+    /// Reads `len` bytes starting at `addr` into a newly allocated buffer.
+    fn read_vec(&self, addr: usize, len: usize) -> Option<Vec<u8>> {
+        let end = addr.checked_add(len)?;
+        if end > self.len() {
+            return None;
+        }
+
+        let mut data = vec![0; len];
+        self.read_exact(addr, &mut data)?;
+        Some(data)
+    }
+
+    /// Reads exactly 1 byte at the effective address `base + offset`.
+    fn read_8(&self, base: u64, offset: u64) -> core::result::Result<u8, crate::Trap> {
+        let addr = checked_effective_addr::<1>(self.len(), base, offset)?;
+        let mut bytes = [0; 1];
+        self.read_exact(addr, &mut bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 1, self.len())
+        })?;
+        Ok(bytes[0])
+    }
+
+    /// Reads exactly 2 bytes at the effective address `base + offset`.
+    fn read_16(&self, base: u64, offset: u64) -> core::result::Result<[u8; 2], crate::Trap> {
+        let addr = checked_effective_addr::<2>(self.len(), base, offset)?;
+        let mut bytes = [0; 2];
+        self.read_exact(addr, &mut bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 2, self.len())
+        })?;
+        Ok(bytes)
+    }
+
+    /// Reads exactly 4 bytes at the effective address `base + offset`.
+    fn read_32(&self, base: u64, offset: u64) -> core::result::Result<[u8; 4], crate::Trap> {
+        let addr = checked_effective_addr::<4>(self.len(), base, offset)?;
+        let mut bytes = [0; 4];
+        self.read_exact(addr, &mut bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 4, self.len())
+        })?;
+        Ok(bytes)
+    }
+
+    /// Reads exactly 8 bytes at the effective address `base + offset`.
+    fn read_64(&self, base: u64, offset: u64) -> core::result::Result<[u8; 8], crate::Trap> {
+        let addr = checked_effective_addr::<8>(self.len(), base, offset)?;
+        let mut bytes = [0; 8];
+        self.read_exact(addr, &mut bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 8, self.len())
+        })?;
+        Ok(bytes)
+    }
+
+    /// Reads exactly 16 bytes at the effective address `base + offset`.
+    fn read_128(&self, base: u64, offset: u64) -> core::result::Result<[u8; 16], crate::Trap> {
+        let addr = checked_effective_addr::<16>(self.len(), base, offset)?;
+        let mut bytes = [0; 16];
+        self.read_exact(addr, &mut bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 16, self.len())
+        })?;
+        Ok(bytes)
+    }
+
+    /// Writes exactly 1 byte at the effective address `base + offset`.
+    fn write_8(&mut self, base: u64, offset: u64, byte: u8) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<1>(self.len(), base, offset)?;
+        self.write(addr, &[byte]);
+        Ok(())
+    }
+
+    /// Writes exactly 2 bytes at the effective address `base + offset`.
+    fn write_16(&mut self, base: u64, offset: u64, bytes: [u8; 2]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<2>(self.len(), base, offset)?;
+        self.write_all(addr, &bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 2, self.len())
+        })
+    }
+
+    /// Writes exactly 4 bytes at the effective address `base + offset`.
+    fn write_32(&mut self, base: u64, offset: u64, bytes: [u8; 4]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<4>(self.len(), base, offset)?;
+        self.write_all(addr, &bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 4, self.len())
+        })
+    }
+
+    /// Writes exactly 8 bytes at the effective address `base + offset`.
+    fn write_64(&mut self, base: u64, offset: u64, bytes: [u8; 8]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<8>(self.len(), base, offset)?;
+        self.write_all(addr, &bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 8, self.len())
+        })
+    }
+
+    /// Writes exactly 16 bytes at the effective address `base + offset`.
+    fn write_128(&mut self, base: u64, offset: u64, bytes: [u8; 16]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<16>(self.len(), base, offset)?;
+        self.write_all(addr, &bytes).ok_or_else(|| {
+            cold_path();
+            memory_oob(addr, 16, self.len())
+        })
+    }
+}
+
+type MemoryFactory = dyn Fn(MemoryType) -> Result<Box<dyn LinearMemory>> + Send + Sync;
+
+/// Configures how runtime memory instances are created.
+#[derive(Clone, Default)]
+pub struct MemoryBackend {
+    kind: MemoryBackendKind,
+}
+
+#[derive(Clone, Default)]
+enum MemoryBackendKind {
+    #[default]
+    Vec,
+    Paged {
+        chunk_size: usize,
+    },
+    Custom(Arc<MemoryFactory>),
+}
+
+impl MemoryBackend {
+    /// Uses a contiguous [`VecMemory`] for each memory instance.
+    ///
+    /// This is usually the fastest option for reads and writes, but large grows can be expensive
+    /// because they may reallocate and copy the entire buffer.
+    pub const fn vec() -> Self {
+        Self { kind: MemoryBackendKind::Vec }
+    }
+
+    /// Uses sparse chunked storage for each memory instance.
+    ///
+    /// `chunk_size` is the backend chunk size in bytes. It is independent from the Wasm page size.
+    ///
+    /// This generally makes growth cheaper than [`Self::vec`], but read and write operations do a
+    /// little more work and may be slightly slower.
+    pub fn paged(chunk_size: usize) -> Self {
+        assert!(chunk_size != 0, "chunk_size must be greater than zero");
+        Self { kind: MemoryBackendKind::Paged { chunk_size } }
+    }
+
+    /// Uses a custom factory to create memory instances.
+    pub fn custom<F, M>(factory: F) -> Self
+    where
+        F: Fn(MemoryType) -> Result<M> + Send + Sync + 'static,
+        M: LinearMemory + 'static,
+    {
+        Self {
+            kind: MemoryBackendKind::Custom(Arc::new(move |ty| {
+                let memory = factory(ty)?;
+                Ok(Box::new(memory) as Box<dyn LinearMemory>)
+            })),
+        }
+    }
+
+    pub(crate) fn create(&self, ty: MemoryType, initial_len: usize) -> Result<MemoryStorage> {
+        let storage = match &self.kind {
+            MemoryBackendKind::Vec => Box::new(VecMemory::new(initial_len)) as Box<dyn LinearMemory>,
+            MemoryBackendKind::Paged { chunk_size } => {
+                Box::new(PagedMemory::new(initial_len, *chunk_size)) as Box<dyn LinearMemory>
+            }
+            MemoryBackendKind::Custom(factory) => factory(ty)?,
+        };
+
+        if storage.len() < initial_len {
+            return Err(Error::Other(format!(
+                "memory backend returned {} bytes for a memory that requires at least {initial_len}",
+                storage.len()
+            )));
+        }
+
+        Ok(MemoryStorage(storage))
+    }
+}
+
+#[cfg(feature = "debug")]
+impl core::fmt::Debug for MemoryBackend {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        match &self.kind {
+            MemoryBackendKind::Vec => f.debug_tuple("MemoryBackend::Vec").finish(),
+            MemoryBackendKind::Paged { chunk_size } => {
+                f.debug_struct("MemoryBackend::Paged").field("chunk_size", chunk_size).finish()
+            }
+            MemoryBackendKind::Custom(_) => f.debug_tuple("MemoryBackend::Custom").finish(),
+        }
+    }
+}
+
+pub(crate) struct MemoryStorage(Box<dyn LinearMemory>);
+
+impl Deref for MemoryStorage {
+    type Target = dyn LinearMemory;
+
+    #[inline(always)]
+    fn deref(&self) -> &Self::Target {
+        &*self.0
+    }
+}
+
+impl DerefMut for MemoryStorage {
+    #[inline(always)]
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut *self.0
+    }
+}
+
+#[cfg(feature = "debug")]
+impl core::fmt::Debug for MemoryStorage {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        f.debug_tuple("MemoryStorage").field(&format!("{} bytes", self.len())).finish()
+    }
+}
+
+/// A trait for types that can be converted to and from static byte arrays
+pub(crate) trait MemValue<const N: usize>: Copy + Default {
+    /// Store a value in memory
+    fn to_mem_bytes(self) -> [u8; N];
+
+    /// Load a value from memory
+    fn from_mem_bytes(bytes: [u8; N]) -> Self;
+}
+
+macro_rules! impl_mem_traits {
+    ($($ty:ty, $size:expr),*) => {
+        $(
+            impl MemValue<$size> for $ty {
+                #[inline(always)]
+                fn from_mem_bytes(bytes: [u8; $size]) -> Self {
+                    <$ty>::from_le_bytes(bytes)
+                }
+
+                #[inline(always)]
+                fn to_mem_bytes(self) -> [u8; $size] {
+                    self.to_le_bytes()
+                }
+            }
+        )*
+    }
+}
+
+impl_mem_traits!(u8, 1, i8, 1, u16, 2, i16, 2, u32, 4, i32, 4, f32, 4, u64, 8, i64, 8, f64, 8);
+
+fn memory_oob(offset: usize, len: usize, max: usize) -> crate::Trap {
+    crate::Trap::MemoryOutOfBounds { offset, len, max }
+}
+
+fn checked_effective_addr<const LEN: usize>(
+    max: usize,
+    base: u64,
+    offset: u64,
+) -> core::result::Result<usize, crate::Trap> {
+    let Some(max_addr) = max.checked_sub(LEN).map(|max_addr| max_addr as u64) else {
+        cold_path();
+        return Err(memory_oob(usize::try_from(base).unwrap_or(usize::MAX), LEN, max));
+    };
+
+    let addr = base.wrapping_add(offset);
+    if addr < base || addr > max_addr {
+        cold_path();
+        return Err(memory_oob(usize::try_from(addr).unwrap_or(usize::MAX), LEN, max));
+    }
+
+    Ok(addr as usize)
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use tinywasm_types::MemoryArch;
+
+    fn create_test_memory(kind: MemoryType, backend: MemoryBackend) -> MemoryInstance {
+        MemoryInstance::new(kind, &backend).unwrap()
+    }
+
+    fn test_backends() -> [MemoryBackend; 2] {
+        [MemoryBackend::vec(), MemoryBackend::paged(4)]
+    }
+
+    #[test]
+    fn memory_copy_from_slice_and_read_vec_work() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            let data = [1, 2, 3, 4];
+            assert!(memory.inner.write_all(0, &data).is_some());
+            assert_eq!(memory.inner.read_vec(0, data.len()).unwrap(), data);
+        }
+    }
+
+    #[test]
+    fn memory_read_returns_partial_count() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(1), Some(4));
+            let memory = create_test_memory(kind, backend);
+            let mut dst = [9; 8];
+            assert_eq!(memory.inner.read(2, &mut dst), 2);
+            assert_eq!(&dst[..2], &[0, 0]);
+            assert_eq!(&dst[2..], &[9; 6]);
+        }
+    }
+
+    #[test]
+    fn memory_copy_from_slice_out_of_bounds_fails() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            let data = [1, 2, 3, 4];
+            let len = memory.inner.len();
+            assert!(memory.inner.write_all(len, &data).is_none());
+        }
+    }
+
+    #[test]
+    fn memory_fill_works() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            assert!(memory.inner.fill(0, 10, 42).is_some());
+            assert_eq!(memory.inner.read_vec(0, 10).unwrap(), vec![42; 10]);
+        }
+    }
+
+    #[test]
+    fn memory_fill_out_of_bounds_fails() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            let len = memory.inner.len();
+            assert!(memory.inner.fill(len, 10, 42).is_none());
+        }
+    }
+
+    #[test]
+    fn memory_copy_within_works() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            memory.inner.fill(0, 10, 1).unwrap();
+            assert!(memory.copy_within(10, 0, 10).is_ok());
+            assert_eq!(memory.inner.read_vec(10, 10).unwrap(), vec![1; 10]);
+        }
+    }
+
+    #[test]
+    fn memory_copy_within_out_of_bounds_fails() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            assert!(memory.copy_within(memory.inner.len(), 0, 10).is_err());
+        }
+    }
+
+    #[test]
+    fn memory_grow_works() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            let original_pages = memory.page_count;
+            assert_eq!(memory.grow(1), Some(original_pages as i64));
+            assert_eq!(memory.page_count, original_pages + 1);
+        }
+    }
+
+    #[test]
+    fn memory_grow_out_of_bounds_fails() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            assert!(memory.grow(memory.kind.max_size() as i64 + 1).is_none());
+        }
+    }
+
+    #[test]
+    fn memory_grow_respects_max_pages() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            assert_eq!(memory.grow(1), Some(1));
+            assert_eq!(memory.grow(1), None);
+        }
+    }
+
+    #[test]
+    fn memory_grow_negative_delta_fails() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), None);
+            let mut memory = create_test_memory(kind, backend);
+            let original_pages = memory.page_count;
+            assert_eq!(memory.grow(-1), None);
+            assert_eq!(memory.page_count, original_pages);
+        }
+    }
+
+    #[test]
+    fn memory_custom_page_size_out_of_bounds_fails() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), Some(1));
+            let mut memory = create_test_memory(kind, backend);
+            let data = [1, 2];
+            assert!(memory.inner.write_all(0, &data).is_none());
+        }
+    }
+
+    #[test]
+    fn memory_custom_page_size_grow_works() {
+        for backend in test_backends() {
+            let kind = MemoryType::new(MemoryArch::I32, 1, Some(2), Some(1));
+            let mut memory = create_test_memory(kind, backend);
+            assert_eq!(memory.grow(1), Some(1));
+            let data = [1, 2];
+            assert!(memory.inner.write_all(0, &data).is_some());
+            assert_eq!(memory.inner.read_vec(0, data.len()).unwrap(), data);
+        }
+    }
+}
diff --git a/crates/tinywasm/src/store/memory/paged.rs b/crates/tinywasm/src/store/memory/paged.rs
new file mode 100644
index 0000000..555261b
--- /dev/null
+++ b/crates/tinywasm/src/store/memory/paged.rs
@@ -0,0 +1,424 @@
+use alloc::boxed::Box;
+use alloc::vec;
+use alloc::vec::Vec;
+use core::cmp::min;
+
+use super::{LinearMemory, checked_effective_addr};
+
+/// A sparse chunked linear memory.
+///
+/// This backend stores memory in fixed-size chunks, which makes growth cheaper because it avoids
+/// resizing and copying one large contiguous buffer.
+///
+/// The tradeoff is that reads and writes do a bit more bookkeeping and may need to cross chunk
+/// boundaries, so they are usually slightly slower than [`super::VecMemory`].
+///
+/// In particular, [`LinearMemory::read`] and [`LinearMemory::write`] return at most the bytes up to
+/// the end of the current chunk. Higher-level exact helpers loop over these short operations when
+/// they need a full range.
+pub struct PagedMemory {
+    len: usize,
+    chunk_size: usize,
+    chunk_shift: u32,
+    chunk_mask: usize,
+    chunks: Vec<Option<Box<[u8]>>>,
+}
+
+impl PagedMemory {
+    /// Creates a new sparse memory with `len` addressable bytes and the given `chunk_size`.
+    ///
+    /// Prefer this backend when grow behavior matters more than absolute read and write speed.
+    pub fn new(len: usize, chunk_size: usize) -> Self {
+        assert!(chunk_size.is_power_of_two(), "chunk_size must be a power of two");
+
+        let mut memory = Self {
+            len: 0,
+            chunk_size,
+            chunk_shift: chunk_size.trailing_zeros(),
+            chunk_mask: chunk_size - 1,
+            chunks: Vec::new(),
+        };
+        memory.grow_to(len).expect("initial length must be growable");
+        memory
+    }
+
+    #[inline(always)]
+    fn chunk_mut(&mut self, chunk_idx: usize) -> &mut [u8] {
+        self.chunks[chunk_idx].get_or_insert_with(|| vec![0; self.chunk_size].into_boxed_slice()).as_mut()
+    }
+
+    #[inline(always)]
+    fn chunk_slice(&self, chunk_idx: usize) -> Option<&[u8]> {
+        self.chunks[chunk_idx].as_deref()
+    }
+
+    #[inline(always)]
+    fn checked_end(&self, addr: usize, len: usize) -> Option<usize> {
+        let end = addr.checked_add(len)?;
+        if end > self.len {
+            return None;
+        }
+        Some(end)
+    }
+
+    #[inline(always)]
+    fn copy_within_single_chunk(&mut self, dst: usize, src: usize, len: usize) -> bool {
+        if len == 0 {
+            return true;
+        }
+
+        if self.checked_end(src, len).is_none() || self.checked_end(dst, len).is_none() {
+            return false;
+        }
+
+        let src_chunk_idx = src >> self.chunk_shift;
+        let dst_chunk_idx = dst >> self.chunk_shift;
+        if src_chunk_idx != dst_chunk_idx {
+            return false;
+        }
+
+        let src_offset = src & self.chunk_mask;
+        let dst_offset = dst & self.chunk_mask;
+        if src_offset + len > self.chunk_size || dst_offset + len > self.chunk_size {
+            return false;
+        }
+
+        if let Some(Some(chunk)) = self.chunks.get_mut(src_chunk_idx) {
+            chunk.copy_within(src_offset..src_offset + len, dst_offset);
+        }
+
+        true
+    }
+}
+
+#[cfg(feature = "debug")]
+impl core::fmt::Debug for PagedMemory {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        let allocated_chunks = self.chunks.iter().filter(|chunk| chunk.is_some()).count();
+        f.debug_struct("PagedMemory")
+            .field("len", &self.len)
+            .field("chunk_size", &self.chunk_size)
+            .field("allocated_chunks", &allocated_chunks)
+            .finish()
+    }
+}
+
+impl LinearMemory for PagedMemory {
+    #[inline(always)]
+    fn len(&self) -> usize {
+        self.len
+    }
+
+    #[inline(always)]
+    fn grow_to(&mut self, new_len: usize) -> Option<()> {
+        if new_len < self.len {
+            return None;
+        }
+        self.chunks.resize_with(if new_len == 0 { 0 } else { new_len.div_ceil(self.chunk_size) }, || None);
+        self.len = new_len;
+        Some(())
+    }
+
+    #[inline(always)]
+    fn read(&self, addr: usize, dst: &mut [u8]) -> usize {
+        if addr >= self.len || dst.is_empty() {
+            return 0;
+        }
+
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        let chunk_end = min((chunk_idx + 1) << self.chunk_shift, self.len);
+        let read_len = min(chunk_end - addr, dst.len());
+        if let Some(chunk) = self.chunk_slice(chunk_idx) {
+            dst[..read_len].copy_from_slice(&chunk[chunk_offset..chunk_offset + read_len]);
+        } else {
+            dst[..read_len].fill(0);
+        }
+
+        read_len
+    }
+
+    #[inline(always)]
+    fn write(&mut self, addr: usize, src: &[u8]) -> usize {
+        if addr >= self.len || src.is_empty() {
+            return 0;
+        }
+
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        let write_len = min(min(self.chunk_size - chunk_offset, self.len - addr), src.len());
+
+        let chunk = self.chunk_mut(chunk_idx);
+        chunk[chunk_offset..chunk_offset + write_len].copy_from_slice(&src[..write_len]);
+        write_len
+    }
+
+    #[inline(always)]
+    fn write_all(&mut self, addr: usize, src: &[u8]) -> Option<()> {
+        let end = self.checked_end(addr, src.len())?;
+        let mut pos = addr;
+        let mut src_offset = 0;
+
+        while pos < end {
+            let chunk_idx = pos >> self.chunk_shift;
+            let chunk_offset = pos & self.chunk_mask;
+            let copy_len = min(self.chunk_size - chunk_offset, end - pos);
+
+            let chunk = self.chunk_mut(chunk_idx);
+            chunk[chunk_offset..chunk_offset + copy_len].copy_from_slice(&src[src_offset..src_offset + copy_len]);
+
+            pos += copy_len;
+            src_offset += copy_len;
+        }
+
+        Some(())
+    }
+
+    #[inline(always)]
+    fn fill(&mut self, addr: usize, len: usize, val: u8) -> Option<()> {
+        let end = self.checked_end(addr, len)?;
+        let mut pos = addr;
+
+        while pos < end {
+            let chunk_idx = pos >> self.chunk_shift;
+            let chunk_offset = pos & self.chunk_mask;
+            let chunk_start = chunk_idx << self.chunk_shift;
+            let chunk_full_len = min(self.chunk_size, self.len - chunk_start);
+            let chunk_end = min(chunk_start + self.chunk_size, end);
+            let fill_len = chunk_end - pos;
+
+            if val == 0 {
+                if chunk_offset == 0 && fill_len == chunk_full_len {
+                    self.chunks[chunk_idx] = None;
+                } else if let Some(Some(chunk)) = self.chunks.get_mut(chunk_idx) {
+                    chunk[chunk_offset..chunk_offset + fill_len].fill(0);
+                }
+            } else {
+                self.chunk_mut(chunk_idx)[chunk_offset..chunk_offset + fill_len].fill(val);
+            }
+
+            pos = chunk_end;
+        }
+
+        Some(())
+    }
+
+    #[inline(always)]
+    fn copy_within(&mut self, dst: usize, src: usize, len: usize) -> Option<()> {
+        self.checked_end(src, len)?;
+        self.checked_end(dst, len)?;
+
+        if len == 0 || dst == src {
+            return Some(());
+        }
+
+        if self.copy_within_single_chunk(dst, src, len) {
+            return Some(());
+        }
+
+        let mut buf = [0u8; 256];
+
+        if dst < src || dst >= src + len {
+            let mut copied = 0;
+            while copied < len {
+                let chunk_len = min(buf.len(), len - copied);
+                self.read_exact(src + copied, &mut buf[..chunk_len])?;
+                self.write_all(dst + copied, &buf[..chunk_len])?;
+                copied += chunk_len;
+            }
+        } else {
+            let mut remaining = len;
+            while remaining > 0 {
+                let chunk_len = min(buf.len(), remaining);
+                let chunk_start = remaining - chunk_len;
+                self.read_exact(src + chunk_start, &mut buf[..chunk_len])?;
+                self.write_all(dst + chunk_start, &buf[..chunk_len])?;
+                remaining = chunk_start;
+            }
+        }
+
+        Some(())
+    }
+
+    #[inline(always)]
+    fn read_8(&self, base: u64, offset: u64) -> core::result::Result<u8, crate::Trap> {
+        let addr = checked_effective_addr::<1>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        Ok(self.chunk_slice(chunk_idx).map_or(0, |chunk| chunk[chunk_offset]))
+    }
+
+    #[inline(always)]
+    fn read_16(&self, base: u64, offset: u64) -> core::result::Result<[u8; 2], crate::Trap> {
+        let addr = checked_effective_addr::<2>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        if chunk_offset + 2 <= self.chunk_size {
+            return Ok(match self.chunk_slice(chunk_idx) {
+                Some(chunk) => chunk[chunk_offset..chunk_offset + 2].try_into().unwrap_or_else(|_| unreachable!()),
+                None => [0; 2],
+            });
+        }
+
+        let mut bytes = [0; 2];
+        self.read_exact(addr, &mut bytes).unwrap();
+        Ok(bytes)
+    }
+
+    #[inline(always)]
+    fn read_32(&self, base: u64, offset: u64) -> core::result::Result<[u8; 4], crate::Trap> {
+        let addr = checked_effective_addr::<4>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        if chunk_offset + 4 <= self.chunk_size {
+            return Ok(match self.chunk_slice(chunk_idx) {
+                Some(chunk) => chunk[chunk_offset..chunk_offset + 4].try_into().unwrap_or_else(|_| unreachable!()),
+                None => [0; 4],
+            });
+        }
+
+        let mut bytes = [0; 4];
+        self.read_exact(addr, &mut bytes).unwrap();
+        Ok(bytes)
+    }
+
+    #[inline(always)]
+    fn read_64(&self, base: u64, offset: u64) -> core::result::Result<[u8; 8], crate::Trap> {
+        let addr = checked_effective_addr::<8>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        if chunk_offset + 8 <= self.chunk_size {
+            return Ok(match self.chunk_slice(chunk_idx) {
+                Some(chunk) => chunk[chunk_offset..chunk_offset + 8].try_into().unwrap_or_else(|_| unreachable!()),
+                None => [0; 8],
+            });
+        }
+
+        let mut bytes = [0; 8];
+        self.read_exact(addr, &mut bytes).unwrap();
+        Ok(bytes)
+    }
+
+    #[inline(always)]
+    fn read_128(&self, base: u64, offset: u64) -> core::result::Result<[u8; 16], crate::Trap> {
+        let addr = checked_effective_addr::<16>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        if chunk_offset + 16 <= self.chunk_size {
+            return Ok(match self.chunk_slice(chunk_idx) {
+                Some(chunk) => chunk[chunk_offset..chunk_offset + 16].try_into().unwrap_or_else(|_| unreachable!()),
+                None => [0; 16],
+            });
+        }
+
+        let mut bytes = [0; 16];
+        self.read_exact(addr, &mut bytes).unwrap();
+        Ok(bytes)
+    }
+
+    #[inline(always)]
+    fn write_8(&mut self, base: u64, offset: u64, byte: u8) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<1>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        self.chunk_mut(chunk_idx)[chunk_offset] = byte;
+        Ok(())
+    }
+
+    #[inline(always)]
+    fn write_16(&mut self, base: u64, offset: u64, bytes: [u8; 2]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<2>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        if chunk_offset + 2 <= self.chunk_size {
+            self.chunk_mut(chunk_idx)[chunk_offset..chunk_offset + 2].copy_from_slice(&bytes);
+        } else {
+            self.write_all(addr, &bytes).unwrap();
+        }
+        Ok(())
+    }
+
+    #[inline(always)]
+    fn write_32(&mut self, base: u64, offset: u64, bytes: [u8; 4]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<4>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        if chunk_offset + 4 <= self.chunk_size {
+            self.chunk_mut(chunk_idx)[chunk_offset..chunk_offset + 4].copy_from_slice(&bytes);
+        } else {
+            self.write_all(addr, &bytes).unwrap();
+        }
+        Ok(())
+    }
+
+    #[inline(always)]
+    fn write_64(&mut self, base: u64, offset: u64, bytes: [u8; 8]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<8>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        if chunk_offset + 8 <= self.chunk_size {
+            self.chunk_mut(chunk_idx)[chunk_offset..chunk_offset + 8].copy_from_slice(&bytes);
+        } else {
+            self.write_all(addr, &bytes).unwrap();
+        }
+        Ok(())
+    }
+
+    #[inline(always)]
+    fn write_128(&mut self, base: u64, offset: u64, bytes: [u8; 16]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<16>(self.len, base, offset)?;
+        let chunk_idx = addr >> self.chunk_shift;
+        let chunk_offset = addr & self.chunk_mask;
+        if chunk_offset + 16 <= self.chunk_size {
+            self.chunk_mut(chunk_idx)[chunk_offset..chunk_offset + 16].copy_from_slice(&bytes);
+        } else {
+            self.write_all(addr, &bytes).unwrap();
+        }
+        Ok(())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::{LinearMemory, PagedMemory};
+
+    #[test]
+    fn paged_memory_reads_zeroes_from_sparse_chunks() {
+        let memory = PagedMemory::new(16, 4);
+        let mut dst = [1; 6];
+        assert_eq!(memory.read(5, &mut dst), 3);
+        assert_eq!(&dst[..3], &[0; 3]);
+        assert_eq!(&dst[3..], &[1; 3]);
+    }
+
+    #[test]
+    fn paged_memory_store_and_load_crosses_chunk_boundaries() {
+        let mut memory = PagedMemory::new(16, 4);
+        memory.write_all(3, &[1, 2, 3, 4, 5, 6]).unwrap();
+
+        let mut dst = [0; 6];
+        memory.read_exact(3, &mut dst).unwrap();
+        assert_eq!(dst, [1, 2, 3, 4, 5, 6]);
+    }
+
+    #[test]
+    fn paged_memory_copy_within_handles_overlap() {
+        let mut memory = PagedMemory::new(16, 4);
+        memory.write_all(0, &[1, 2, 3, 4, 5, 6]).unwrap();
+        memory.copy_within(2, 0, 6).unwrap();
+
+        let mut dst = [0; 8];
+        memory.read_exact(0, &mut dst).unwrap();
+        assert_eq!(dst, [1, 2, 1, 2, 3, 4, 5, 6]);
+    }
+
+    #[test]
+    fn paged_memory_write_stops_at_chunk_boundary() {
+        let mut memory = PagedMemory::new(16, 4);
+        assert_eq!(memory.write(3, &[1, 2, 3, 4]), 1);
+
+        let mut dst = [0; 4];
+        memory.read_exact(3, &mut dst).unwrap();
+        assert_eq!(dst, [1, 0, 0, 0]);
+    }
+}
diff --git a/crates/tinywasm/src/store/memory/vec.rs b/crates/tinywasm/src/store/memory/vec.rs
new file mode 100644
index 0000000..6f802f7
--- /dev/null
+++ b/crates/tinywasm/src/store/memory/vec.rs
@@ -0,0 +1,162 @@
+use alloc::vec;
+use alloc::vec::Vec;
+
+use super::{LinearMemory, checked_effective_addr};
+
+/// A contiguous `Vec<u8>`-backed linear memory.
+///
+/// This is the simplest backend and typically gives the best read and write throughput because
+/// the whole memory lives in one contiguous allocation.
+///
+/// The tradeoff is growth cost: large grows may need to reallocate and copy the full buffer,
+/// which can get expensive for large memories.
+#[cfg_attr(feature = "debug", derive(Debug))]
+pub struct VecMemory {
+    data: Vec<u8>,
+}
+
+impl VecMemory {
+    /// Creates a new memory with `len` zero-initialized bytes.
+    ///
+    /// Prefer this backend when contiguous access is more important than grow performance.
+    pub fn new(len: usize) -> Self {
+        Self { data: vec![0; len] }
+    }
+}
+
+impl LinearMemory for VecMemory {
+    #[inline(always)]
+    fn len(&self) -> usize {
+        self.data.len()
+    }
+
+    #[inline(always)]
+    fn grow_to(&mut self, new_len: usize) -> Option<()> {
+        if new_len < self.data.len() {
+            return None;
+        }
+        self.data.resize(new_len, 0);
+        Some(())
+    }
+
+    #[inline(always)]
+    fn read(&self, addr: usize, dst: &mut [u8]) -> usize {
+        if addr >= self.data.len() {
+            return 0;
+        }
+        let read_len = dst.len().min(self.data.len() - addr);
+        dst[..read_len].copy_from_slice(&self.data[addr..addr + read_len]);
+        read_len
+    }
+
+    #[inline(always)]
+    fn read_exact(&self, addr: usize, dst: &mut [u8]) -> Option<()> {
+        dst.copy_from_slice(self.data.get(addr..addr.checked_add(dst.len())?)?);
+        Some(())
+    }
+
+    #[inline(always)]
+    fn read_vec(&self, addr: usize, len: usize) -> Option<Vec<u8>> {
+        Some(self.data.get(addr..addr.checked_add(len)?)?.to_vec())
+    }
+
+    #[inline(always)]
+    fn write(&mut self, addr: usize, src: &[u8]) -> usize {
+        if addr >= self.data.len() {
+            return 0;
+        }
+
+        let write_len = src.len().min(self.data.len() - addr);
+        self.data[addr..addr + write_len].copy_from_slice(&src[..write_len]);
+        write_len
+    }
+
+    #[inline(always)]
+    fn write_all(&mut self, addr: usize, src: &[u8]) -> Option<()> {
+        let dst = self.data.get_mut(addr..addr.checked_add(src.len())?)?;
+        dst.copy_from_slice(src);
+        Some(())
+    }
+
+    #[inline(always)]
+    fn fill(&mut self, addr: usize, len: usize, val: u8) -> Option<()> {
+        self.data.get_mut(addr..addr.checked_add(len)?)?.fill(val);
+        Some(())
+    }
+
+    #[inline(always)]
+    fn copy_within(&mut self, dst: usize, src: usize, len: usize) -> Option<()> {
+        let src_end = src.checked_add(len)?;
+        let dst_end = dst.checked_add(len)?;
+        if src_end > self.data.len() || dst_end > self.data.len() {
+            return None;
+        }
+
+        self.data.copy_within(src..src_end, dst);
+        Some(())
+    }
+
+    #[inline(always)]
+    fn read_8(&self, base: u64, offset: u64) -> core::result::Result<u8, crate::Trap> {
+        Ok(self.data[checked_effective_addr::<1>(self.data.len(), base, offset)?])
+    }
+
+    #[inline(always)]
+    fn read_16(&self, base: u64, offset: u64) -> core::result::Result<[u8; 2], crate::Trap> {
+        let addr = checked_effective_addr::<2>(self.data.len(), base, offset)?;
+        Ok(self.data[addr..addr + 2].try_into().unwrap_or_else(|_| unreachable!()))
+    }
+
+    #[inline(always)]
+    fn read_32(&self, base: u64, offset: u64) -> core::result::Result<[u8; 4], crate::Trap> {
+        let addr = checked_effective_addr::<4>(self.data.len(), base, offset)?;
+        Ok(self.data[addr..addr + 4].try_into().unwrap_or_else(|_| unreachable!()))
+    }
+
+    #[inline(always)]
+    fn read_64(&self, base: u64, offset: u64) -> core::result::Result<[u8; 8], crate::Trap> {
+        let addr = checked_effective_addr::<8>(self.data.len(), base, offset)?;
+        Ok(self.data[addr..addr + 8].try_into().unwrap_or_else(|_| unreachable!()))
+    }
+
+    #[inline(always)]
+    fn read_128(&self, base: u64, offset: u64) -> core::result::Result<[u8; 16], crate::Trap> {
+        let addr = checked_effective_addr::<16>(self.data.len(), base, offset)?;
+        Ok(self.data[addr..addr + 16].try_into().unwrap_or_else(|_| unreachable!()))
+    }
+
+    #[inline(always)]
+    fn write_8(&mut self, base: u64, offset: u64, byte: u8) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<1>(self.data.len(), base, offset)?;
+        self.data[addr] = byte;
+        Ok(())
+    }
+
+    #[inline(always)]
+    fn write_16(&mut self, base: u64, offset: u64, bytes: [u8; 2]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<2>(self.data.len(), base, offset)?;
+        self.data[addr..addr + 2].copy_from_slice(&bytes);
+        Ok(())
+    }
+
+    #[inline(always)]
+    fn write_32(&mut self, base: u64, offset: u64, bytes: [u8; 4]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<4>(self.data.len(), base, offset)?;
+        self.data[addr..addr + 4].copy_from_slice(&bytes);
+        Ok(())
+    }
+
+    #[inline(always)]
+    fn write_64(&mut self, base: u64, offset: u64, bytes: [u8; 8]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<8>(self.data.len(), base, offset)?;
+        self.data[addr..addr + 8].copy_from_slice(&bytes);
+        Ok(())
+    }
+
+    #[inline(always)]
+    fn write_128(&mut self, base: u64, offset: u64, bytes: [u8; 16]) -> core::result::Result<(), crate::Trap> {
+        let addr = checked_effective_addr::<16>(self.data.len(), base, offset)?;
+        self.data[addr..addr + 16].copy_from_slice(&bytes);
+        Ok(())
+    }
+}
diff --git a/crates/tinywasm/src/store/mod.rs b/crates/tinywasm/src/store/mod.rs
index e76673f..9c3d0ad 100644
--- a/crates/tinywasm/src/store/mod.rs
+++ b/crates/tinywasm/src/store/mod.rs
@@ -15,7 +15,9 @@ mod global;
 mod memory;
 mod table;
 
-pub(crate) use {data::*, element::*, function::*, global::*, memory::*, table::*};
+pub use memory::{LinearMemory, MemoryBackend, PagedMemory, VecMemory};
+pub(crate) use memory::{MemValue, MemoryInstance};
+pub(crate) use {data::*, element::*, function::*, global::*, table::*};
 
 // global store id counter
 static STORE_ID: AtomicUsize = AtomicUsize::new(0);
@@ -282,14 +284,14 @@ impl Store {
     }
 
     /// Add memories to the store, returning their addresses in the store
-    pub(crate) fn init_memories(&mut self, memories: &[MemoryType], _idx: ModuleInstanceAddr) -> Vec<MemAddr> {
+    pub(crate) fn init_memories(&mut self, memories: &[MemoryType], _idx: ModuleInstanceAddr) -> Result<Vec<MemAddr>> {
         let mem_count = self.state.memories.len();
         let mut mem_addrs = Vec::with_capacity(mem_count);
         for (i, mem) in memories.iter().enumerate() {
-            self.state.memories.push(MemoryInstance::new(*mem));
+            self.state.memories.push(MemoryInstance::new(*mem, &self.engine.config().memory_backend)?);
             mem_addrs.push((i + mem_count) as MemAddr);
         }
-        mem_addrs
+        Ok(mem_addrs)
     }
 
     /// Add globals to the store, returning their addresses in the store
@@ -367,7 +369,7 @@ impl Store {
                     // This isn't mentioned in the spec, but the "unofficial" testsuite has a test for it:
                     // https://github.com/WebAssembly/testsuite/blob/5a1a590603d81f40ef471abba70a90a9ae5f4627/linking.wast#L264-L276
                     // I have NO IDEA why this is allowed, but it is.
-                    if let Err(Error::Trap(trap)) = table.init(offset, &init) {
+                    if let Err(trap) = table.init(offset, &init) {
                         return Ok((elem_addrs.into_boxed_slice(), Some(trap)));
                     }
 
@@ -407,10 +409,18 @@ impl Store {
                         return Err(Error::Other(format!("memory {mem_addr} not found for data segment {i}")));
                     };
 
-                    match mem.store(offset as usize, &data.data) {
-                        Ok(()) => None,
-                        Err(Error::Trap(trap)) => return Ok((data_addrs.into_boxed_slice(), Some(trap))),
-                        Err(e) => return Err(e),
+                    match mem.inner.write_all(offset as usize, &data.data) {
+                        Some(()) => None,
+                        None => {
+                            return Ok((
+                                data_addrs.into_boxed_slice(),
+                                Some(crate::Trap::MemoryOutOfBounds {
+                                    offset: offset as usize,
+                                    len: data.data.len(),
+                                    max: mem.inner.len(),
+                                }),
+                            ));
+                        }
                     }
                 }
                 tinywasm_types::DataKind::Passive => Some(data.data.to_vec()),
diff --git a/crates/tinywasm/src/store/table.rs b/crates/tinywasm/src/store/table.rs
index df98508..50b0d88 100644
--- a/crates/tinywasm/src/store/table.rs
+++ b/crates/tinywasm/src/store/table.rs
@@ -1,4 +1,4 @@
-use crate::{Error, Result, Trap};
+use crate::{Result, Trap};
 use alloc::{vec, vec::Vec};
 use tinywasm_types::*;
 
@@ -24,21 +24,21 @@ impl TableInstance {
 
     #[inline(never)]
     #[cold]
-    fn trap_oob(&self, addr: usize, len: usize) -> Error {
-        Error::Trap(crate::Trap::TableOutOfBounds { offset: addr, len, max: self.elements.len() })
+    fn trap_oob(&self, addr: usize, len: usize) -> Trap {
+        crate::Trap::TableOutOfBounds { offset: addr, len, max: self.elements.len() }
     }
 
-    pub(crate) fn get_wasm_val(&self, addr: TableAddr) -> Result<WasmValue> {
+    pub(crate) fn get_wasm_val(&self, addr: TableAddr) -> Result<WasmValue, Trap> {
         let val = self.get(addr)?.addr();
 
         Ok(match self.kind.element_type {
             WasmType::RefFunc => WasmValue::RefFunc(FuncRef::new(val)),
             WasmType::RefExtern => WasmValue::RefExtern(ExternRef::new(val)),
-            _ => Err(Error::UnsupportedFeature("non-ref table".into()))?,
+            _ => Err(Trap::Other("non-ref table"))?,
         })
     }
 
-    pub(crate) fn fill(&mut self, func_addrs: &[u32], addr: usize, len: usize, val: TableElement) -> Result<()> {
+    pub(crate) fn fill(&mut self, func_addrs: &[u32], addr: usize, len: usize, val: TableElement) -> Result<(), Trap> {
         let val = val.map(|addr| self.resolve_func_ref(func_addrs, addr));
         let end = addr.checked_add(len).ok_or_else(|| self.trap_oob(addr, len))?;
         if end > self.elements.len() {
@@ -49,15 +49,15 @@ impl TableInstance {
         Ok(())
     }
 
-    pub(crate) fn get(&self, addr: TableAddr) -> Result<&TableElement> {
-        self.elements.get(addr as usize).ok_or(Error::Trap(Trap::TableOutOfBounds {
+    pub(crate) fn get(&self, addr: TableAddr) -> Result<&TableElement, Trap> {
+        self.elements.get(addr as usize).ok_or(Trap::TableOutOfBounds {
             offset: addr as usize,
             len: 1,
             max: self.elements.len(),
-        }))
+        })
     }
 
-    pub(crate) fn copy_from_slice(&mut self, dst: usize, src: &[TableElement]) -> Result<()> {
+    pub(crate) fn copy_from_slice(&mut self, dst: usize, src: &[TableElement]) -> Result<(), Trap> {
         let end = dst.checked_add(src.len()).ok_or_else(|| self.trap_oob(dst, src.len()))?;
 
         if end > self.elements.len() {
@@ -68,7 +68,7 @@ impl TableInstance {
         Ok(())
     }
 
-    pub(crate) fn load(&self, addr: usize, len: usize) -> Result<&[TableElement]> {
+    pub(crate) fn load(&self, addr: usize, len: usize) -> Result<&[TableElement], Trap> {
         let Some(end) = addr.checked_add(len) else {
             return Err(self.trap_oob(addr, len));
         };
@@ -80,7 +80,7 @@ impl TableInstance {
         Ok(&self.elements[addr..end])
     }
 
-    pub(crate) fn copy_within(&mut self, dst: usize, src: usize, len: usize) -> Result<()> {
+    pub(crate) fn copy_within(&mut self, dst: usize, src: usize, len: usize) -> Result<(), Trap> {
         // Calculate the end of the source slice
         let src_end = src.checked_add(len).ok_or_else(|| self.trap_oob(src, len))?;
         if src_end > self.elements.len() {
@@ -98,7 +98,7 @@ impl TableInstance {
         Ok(())
     }
 
-    pub(crate) fn set(&mut self, table_idx: TableAddr, value: TableElement) -> Result<()> {
+    pub(crate) fn set(&mut self, table_idx: TableAddr, value: TableElement) -> Result<(), Trap> {
         if table_idx as usize >= self.elements.len() {
             return Err(self.trap_oob(table_idx as usize, 1));
         }
@@ -107,15 +107,15 @@ impl TableInstance {
         Ok(())
     }
 
-    pub(crate) fn grow(&mut self, n: i32, init: TableElement) -> Result<()> {
+    pub(crate) fn grow(&mut self, n: i32, init: TableElement) -> Result<(), Trap> {
         if n < 0 {
-            return Err(Error::Trap(crate::Trap::TableOutOfBounds { offset: 0, len: 1, max: self.elements.len() }));
+            return Err(crate::Trap::TableOutOfBounds { offset: 0, len: 1, max: self.elements.len() });
         }
 
         let len = n as usize + self.elements.len();
         let max = self.kind.size_max.unwrap_or(MAX_TABLE_SIZE) as usize;
         if len > max {
-            return Err(Error::Trap(crate::Trap::TableOutOfBounds { offset: len, len: 1, max: self.elements.len() }));
+            return Err(crate::Trap::TableOutOfBounds { offset: len, len: 1, max: self.elements.len() });
         }
 
         self.elements.resize(len, init);
@@ -136,14 +136,16 @@ impl TableInstance {
             .expect("error initializing table: function not found. This should have been caught by the validator")
     }
 
-    pub(crate) fn init(&mut self, offset: i64, init: &[TableElement]) -> Result<()> {
+    pub(crate) fn init(&mut self, offset: i64, init: &[TableElement]) -> Result<(), Trap> {
         let offset = offset as usize;
-        let end = offset.checked_add(init.len()).ok_or({
-            Error::Trap(crate::Trap::TableOutOfBounds { offset, len: init.len(), max: self.elements.len() })
+        let end = offset.checked_add(init.len()).ok_or(crate::Trap::TableOutOfBounds {
+            offset,
+            len: init.len(),
+            max: self.elements.len(),
         })?;
 
         if end > self.elements.len() || end < offset {
-            return Err(crate::Trap::TableOutOfBounds { offset, len: init.len(), max: self.elements.len() }.into());
+            return Err(crate::Trap::TableOutOfBounds { offset, len: init.len(), max: self.elements.len() });
         }
         self.elements[offset..end].copy_from_slice(init);
         Ok(())
@@ -217,7 +219,7 @@ mod tests {
         }
 
         match table_instance.get_wasm_val(999) {
-            Err(Error::Trap(Trap::TableOutOfBounds { .. })) => {}
+            Err(Trap::TableOutOfBounds { .. }) => {}
             _ => panic!("get_wasm_val failed to handle undefined element correctly"),
         }
     }
diff --git a/crates/tinywasm/tests/internal_refs.rs b/crates/tinywasm/tests/internal_refs.rs
index dd4179a..9bd091e 100644
--- a/crates/tinywasm/tests/internal_refs.rs
+++ b/crates/tinywasm/tests/internal_refs.rs
@@ -25,8 +25,8 @@ fn private_items_are_accessible_by_index() -> Result<()> {
     let func = instance.func_by_index(&store, 0)?;
     assert_eq!(func.call(&mut store, &[])?, vec![WasmValue::I32(7)]);
 
-    instance.memory_by_index(0)?.store(&mut store, 0, &[1, 2, 3, 4])?;
-    assert_eq!(instance.memory_by_index(0)?.load(&store, 0, 4)?, &[1, 2, 3, 4]);
+    instance.memory_by_index(0)?.copy_from_slice(&mut store, 0, &[1, 2, 3, 4])?;
+    assert_eq!(instance.memory_by_index(0)?.read_vec(&store, 0, 4)?, &[1, 2, 3, 4]);
 
     assert_eq!(instance.table_by_index(0)?.size(&store)?, 2);
     assert_eq!(instance.table_by_index(0)?.get(&store, 0)?, WasmValue::RefFunc(FuncRef::new(Some(0))));
diff --git a/crates/tinywasm/tests/memory_backends.rs b/crates/tinywasm/tests/memory_backends.rs
new file mode 100644
index 0000000..0efbee0
--- /dev/null
+++ b/crates/tinywasm/tests/memory_backends.rs
@@ -0,0 +1,121 @@
+use core::sync::atomic::{AtomicUsize, Ordering};
+use std::sync::Arc;
+
+#[cfg(feature = "std")]
+use std::io::{Read, Seek, SeekFrom, Write};
+
+use eyre::Result;
+use tinywasm::engine::Config;
+use tinywasm::types::{MemoryArch, MemoryType};
+use tinywasm::{Engine, Memory, MemoryBackend, Module, PagedMemory, Store};
+
+#[test]
+fn paged_backend_works_for_module_memories() -> Result<()> {
+    let wasm = wat::parse_str(
+        r#"
+        (module
+          (memory (export "memory") 1)
+        )
+        "#,
+    )?;
+
+    let module = Module::parse_bytes(&wasm)?;
+    let config = Config::new().with_memory_backend(MemoryBackend::paged(8));
+    let mut store = Store::new(Engine::new(config));
+    let instance = module.instantiate(&mut store, None)?;
+    let memory = instance.memory("memory")?;
+
+    memory.copy_from_slice(&mut store, 6, &[1, 2, 3, 4, 5, 6, 7, 8])?;
+    assert_eq!(memory.read_vec(&store, 6, 8)?, &[1, 2, 3, 4, 5, 6, 7, 8]);
+
+    Ok(())
+}
+
+#[test]
+fn custom_backend_factory_is_used_for_host_memories() -> Result<()> {
+    let created = Arc::new(AtomicUsize::new(0));
+    let seen_page_size = Arc::new(AtomicUsize::new(0));
+    let factory_calls = created.clone();
+    let page_size_seen = seen_page_size.clone();
+
+    let backend = MemoryBackend::custom(move |ty| {
+        factory_calls.fetch_add(1, Ordering::Relaxed);
+        page_size_seen.store(ty.page_size() as usize, Ordering::Relaxed);
+        Ok(PagedMemory::new(ty.initial_size() as usize, 16))
+    });
+
+    let engine = Engine::new(Config::new().with_memory_backend(backend));
+    let mut store = Store::new(engine);
+
+    let memory = Memory::new(&mut store, MemoryType::new(MemoryArch::I32, 1, Some(2), Some(32)))?;
+    assert_eq!(memory.ty(&store)?.page_size(), 32);
+    memory.copy_from_slice(&mut store, 12, &[9, 8, 7, 6, 5])?;
+
+    assert_eq!(memory.read_vec(&store, 12, 5)?, &[9, 8, 7, 6, 5]);
+    assert_eq!(created.load(Ordering::Relaxed), 1);
+    assert_eq!(seen_page_size.load(Ordering::Relaxed), 32);
+
+    Ok(())
+}
+
+#[test]
+fn read_returns_short_count_at_end_of_memory() -> Result<()> {
+    let mut store = Store::default();
+    let memory = Memory::new(&mut store, MemoryType::new(MemoryArch::I32, 1, Some(1), Some(4)))?;
+    memory.copy_from_slice(&mut store, 0, &[1, 2, 3, 4])?;
+
+    let mut dst = [9; 8];
+    assert_eq!(memory.read(&store, 2, &mut dst)?, 2);
+    assert_eq!(&dst[..2], &[3, 4]);
+    assert_eq!(&dst[2..], &[9; 6]);
+
+    Ok(())
+}
+
+#[test]
+fn paged_read_and_write_stop_at_chunk_boundaries() -> Result<()> {
+    let engine = Engine::new(Config::new().with_memory_backend(MemoryBackend::paged(4)));
+    let mut store = Store::new(engine);
+    let memory = Memory::new(&mut store, MemoryType::new(MemoryArch::I32, 1, Some(1), Some(16)))?;
+
+    memory.copy_from_slice(&mut store, 0, &[1, 2, 3, 4, 5, 6, 7, 8])?;
+
+    let mut read_buf = [9; 6];
+    assert_eq!(memory.read(&store, 2, &mut read_buf)?, 2);
+    assert_eq!(&read_buf[..2], &[3, 4]);
+    assert_eq!(&read_buf[2..], &[9; 4]);
+
+    let mut exact_buf = [0; 6];
+    memory.read_exact(&store, 2, &mut exact_buf)?;
+    assert_eq!(exact_buf, [3, 4, 5, 6, 7, 8]);
+
+    assert_eq!(memory.write(&mut store, 6, &[10, 11, 12, 13])?, 2);
+    assert_eq!(memory.read_vec(&store, 6, 4)?, &[10, 11, 0, 0]);
+
+    memory.copy_from_slice(&mut store, 6, &[20, 21, 22, 23])?;
+    assert_eq!(memory.read_vec(&store, 6, 4)?, &[20, 21, 22, 23]);
+
+    Ok(())
+}
+
+#[cfg(feature = "std")]
+#[test]
+fn memory_cursor_supports_read_write_and_seek() -> Result<()> {
+    let mut store = Store::default();
+    let memory = Memory::new(&mut store, MemoryType::new(MemoryArch::I32, 1, Some(1), Some(8)))?;
+
+    let mut cursor = memory.cursor(&mut store)?;
+    cursor.seek(SeekFrom::Start(2))?;
+    cursor.write_all(b"abc")?;
+    cursor.seek(SeekFrom::Start(0))?;
+
+    let mut buf = [0; 5];
+    cursor.read_exact(&mut buf)?;
+    assert_eq!(buf, [0, 0, b'a', b'b', b'c']);
+
+    cursor.seek(SeekFrom::End(-1))?;
+    cursor.write_all(b"z")?;
+
+    assert_eq!(memory.read_vec(&store, 0, 8)?, &[0, 0, b'a', b'b', b'c', 0, 0, b'z']);
+    Ok(())
+}
diff --git a/crates/tinywasm/tests/memory_ref_api.rs b/crates/tinywasm/tests/memory_ref_api.rs
index 21c8c90..97252f4 100644
--- a/crates/tinywasm/tests/memory_ref_api.rs
+++ b/crates/tinywasm/tests/memory_ref_api.rs
@@ -16,10 +16,10 @@ fn memory_ref_mut_copy_within_uses_src_then_dst_order() -> Result<()> {
     let instance = module.instantiate(&mut store, None)?;
 
     let memory = instance.memory("memory")?;
-    memory.store(&mut store, 0, &[1, 2, 3, 4])?;
+    memory.copy_from_slice(&mut store, 0, &[1, 2, 3, 4])?;
     memory.copy_within(&mut store, 0, 4, 4)?;
 
-    assert_eq!(memory.load(&store, 0, 8)?, &[1, 2, 3, 4, 1, 2, 3, 4]);
+    assert_eq!(memory.read_vec(&store, 0, 8)?, &[1, 2, 3, 4, 1, 2, 3, 4]);
 
     Ok(())
 }
diff --git a/crates/tinywasm/tests/resume_execution.rs b/crates/tinywasm/tests/resume_execution.rs
index a1e2bc6..06b666f 100644
--- a/crates/tinywasm/tests/resume_execution.rs
+++ b/crates/tinywasm/tests/resume_execution.rs
@@ -65,7 +65,7 @@ fn weighted_call_fuel_requires_more_rounds() -> Result<()> {
     let func_per_instr = instance_per_instr.func::<i32, i32>(&per_instr_store, "fibonacci_recursive")?;
 
     let mut weighted_store =
-        tinywasm::Store::new(tinywasm::Engine::new(Config::new().fuel_policy(FuelPolicy::Weighted)));
+        tinywasm::Store::new(tinywasm::Engine::new(Config::new().with_fuel_policy(FuelPolicy::Weighted)));
     let instance_weighted = module.instantiate(&mut weighted_store, None)?;
     let func_weighted = instance_weighted.func::<i32, i32>(&weighted_store, "fibonacci_recursive")?;
 
diff --git a/crates/tinywasm/tests/store_ownership.rs b/crates/tinywasm/tests/store_ownership.rs
index b8c3729..f1bd117 100644
--- a/crates/tinywasm/tests/store_ownership.rs
+++ b/crates/tinywasm/tests/store_ownership.rs
@@ -37,7 +37,7 @@ fn memory_access_rejects_wrong_store() -> Result<()> {
 
     let memory = instance.memory("memory")?;
     let other_store = Store::default();
-    let err = memory.data(&other_store).unwrap_err();
+    let err = memory.len(&other_store).unwrap_err();
     assert!(matches!(err, Error::InvalidStore));
 
     Ok(())
diff --git a/examples/wasm-rust.rs b/examples/wasm-rust.rs
index 2d2b91a..928b9e1 100644
--- a/examples/wasm-rust.rs
+++ b/examples/wasm-rust.rs
@@ -107,7 +107,7 @@ fn hello() -> Result<()> {
 
     let print_utf8 = HostFunction::from(&mut store, |ctx: FuncContext<'_>, (ptr, len): (i64, i32)| {
         let mem = ctx.memory("memory")?;
-        let string = mem.load_string(ctx.store(), ptr as usize, len as usize)?;
+        let string = mem.read_string(ctx.store(), ptr as usize, len as usize)?;
         println!("{string}");
         Ok(())
     });
@@ -119,7 +119,7 @@ fn hello() -> Result<()> {
     let arg_ptr = instance.func::<(), i32>(&store, "arg_ptr")?.call(&mut store, ())?;
     let arg = b"world";
 
-    instance.memory("memory")?.store(&mut store, arg_ptr as usize, arg)?;
+    instance.memory("memory")?.copy_from_slice(&mut store, arg_ptr as usize, arg)?;
     let hello = instance.func::<i32, ()>(&store, "hello")?;
     hello.call(&mut store, arg.len() as i32)?;