【选修】Rust 生态蜜蜂｜学习 MiniRust Part 1 ：基本内存模型
引言
本系列内容是对 MiniRust 的学习笔记。学习 MiniRust 主要是尝试站在 Rust 语言缔造者之一 RalfJung 的思维视角来学习 Rust 语言的语义规范。对于初学 Rust 的朋友，这部分内容可以暂时不看。如果你也对 MiniRust 感兴趣，那么可以一起学习交流。
什么是 MiniRust ？
简单来说，MiniRust 是 Rust 官方成员 RalfJung 对 Rust 语义规范的愿景。换句话说，MiniRust 定义了 RalfJung 看待 Rust 的心智模型。或许这个名字也可以称为 CoreRust。它是一种理想化的类似 MIR 的语言，目的是作为Rust的 "核心语言"。
其目标是精确地规定 Rust 的操作行为，即 Rust 程序在执行时可能有的行为。Rust程序的行为是通过首先将其翻译成 MiniRust（目前还未定义） ，然后考虑本 MiniRust 项目中规定的程序的可能行为而定义的。MiniRust关注很多细节，比如精确的计算顺序，数据表示，以及精确到什么是和不是未定义行为。
这是一个长期计划，RalfJung 打算用 伪 Rust 代码代替英文来解释 Rust 的语义。后期可能会将该项目中的伪代码翻译为真正的 Rust 和 Coq 代码，并且对其进行证明，当然这是长期目标，短期内需要完善 MiniRust 这个模型。
MiniRust 语义
为了将内存的复杂性从MiniRust语句和表达式的语义中分离出来，我们引入了MiniRust内存接口：将内存看作是实现了某种特质（trait），MiniRust语义是对该特质的实际实现。MiniRust语言（在 lang/ 中指定）和它的内存模型（在mem/中指定）之间的接口是无类型和面向字节的（但 "字节 "比你想象的要复杂一些）。
在MiniRust语言层面，需要理解的最重要的概念是值（value）以及它与类型的关系。值形成了一个宏观的、结构性的数据视图（例如数学整数）；类型的作用是将值与它们的底层的面向字节的表示联系起来。类型本质上只是附加在某些操作上的参数，用来定义（反）序列化格式。MiniRust 程序的良好形式确保表达式和语句满足一些基本的类型规范，但 MiniRust 在设计上不是类型安全的。
MiniRust 与伪 Rust
MiniRust 项目中包含两种“语言”：
MiniRust 是“Rust 核心语言”，是本项目的主要主题。它具有 unsafe Rust 的所有令人讨厌的特性，并带有一个解释器，可以描述程序执行时究竟发生了什么，但是由于缺乏任何便利，因此编写起来会很糟糕。它甚至没有具体的语法； 伪 Rust是编写 MiniRust 解释器本身的编程语言。它是一种完全安全的 Rust 风格语言，其目的是伪 Rust 程序的含义对任何 Rust 程序员来说都是“显而易见的”。将来，我们希望有可以执行 Pseudo Rust 的工具，这样我们就可以运行 MiniRust 解释器，但现在这是一种没有实现的语言。
MiniRust 基本内存模型
在 `MiniRust/mem/basic.md`[1] 中定义了 MiniRust 的基本内存模型，它没有对任何类型的别名限制进行建模，但除此之外应该足以解释我们在 Rust 中看到的所有行为和未定义行为，特别是关于内存访问和指针算术的边界检查。
内存接口
指针
指针并不是简单的整数（参见前面的文章《复杂的指针》系列）。内存模型认为指针由地址（address，实际上只是一个适当大小的整数）和出处（provenance）组成。
抽象字节
抽象字节不同于u8，它支持表示未初始化的内存和支持在指针存储在内存中时维护指针来源。
#[derive(PartialEq, Eq)]
enum AbstractByte<Provenance> {
/// 未初始化字节
Uninit,
/// 一个初始化的字节，出处是可选（当指针时）。
Init(u8, Option<Provenance>),
}
impl AbstractByte<Provenance> {
fn data(self) -> Option<u8> {
match self {
Uninit => None,
Init(data, _) => Some(data),
}
}
fn provenance(self) -> Option<Provenance> {
match self {
Uninit => None,
Init(_, provenance) => provenance,
}
}
}
内存接口
/// "address" 是内存中的位置。它对应真实程序中的实际位置
/// 我们让它成为一个数学上的整数，当然，它是由地址空间的大小来约束的
type Address = BigInt;
/// "pointer" 是一个地址，连同它的Provenance
/// Provenance可以不存在。
/// 这些指针对于所有非零大小的访问都是无效的
#[derive(PartialEq, Eq)]
struct Pointer<Provenance> {
addr: Address,
provenance: Option<Provenance>,
}
/// *注意*。所有的内存操作都可以是非确定性的，
/// 这意味着在相同的内存上执行相同的操作会有不同的结果。
/// 我们还让读操作有可能修改内存（它们实际上在并发内存模型和 Stack Borrow中改变当前状态）。
trait MemoryInterface {
type Provenance : Eq;
/// 用 `Self::Pointer` 标记 `Pointer<Self::Provenance>`,
/// 用 `Self::AbstractByte` 标记 `AbstractByte<Self::Provenance>`.
type Pointer = Pointer<Self::Provenance>;
type AbstractByte = AbstractByte<Self::Provenance>;
/// 创建新的内存分配
/// 使用 `AbstractByte::Uninit`初始化
fn allocate(&mut self, size: Size, align: Align) -> NdResult<Self::Pointer>;
/// 移除分配
fn deallocate(&mut self, ptr: Self::Pointer, size: Size, align: Align) -> Result;
/// 向内存写入字节
fn store(&mut self, ptr: Self::Pointer, bytes: List<Self::AbstractByte>, align: Align) -> Result;
/// 从内存读取字节
fn load(&mut self, ptr: Self::Pointer, len: Size, align: Align) -> Result<List<Self::AbstractByte>>;
/// 测试给定的指针是否可以按给定的尺寸和对齐方式解引用
/// 如果不是这种情况，提升为 UB
/// 请注意，成功的 read/write/deallocate 意味着在该操作之前
/// 指针是可被解除引用的（但反之则不然）
fn dereferenceable(&self, ptr: Self::Pointer, size: Size, align: Align) -> Result;
}
该内存接口目前还不完整。
数据结构
此内存模型跟踪的出处（Provenance）只是一个标识指针指向的分配的 ID。
#[derive(PartialEq, Eq)]
struct AllocId(BigInt);
impl MemoryInterface for BasicMemory {
type Provenance = AllocId;
}
struct Allocation {
/// 数据存储在分配的内存中
contents: List<AbstractByte<AllocId>>,
/// 分配的内存的起始地址
/// 永远不会是 0, 并且 `addr + contents.len()` 是 `usize`.
addr: BigInt,
/// 分配的内存要求对齐
/// `addr` 是该字段的倍数.
align: Align,
/// 这块分配的内存是否还活跃
live: bool,
}
struct BasicMemory {
allocations: List<Allocation>,
}
内存跟踪的数据相当简单：对于每个分配，我们跟踪它的内容、它在内存中的绝对整数地址、创建它的对齐方式（大小隐含在内容的长度中），以及它是否还活跃（或已经被释放）。
然后，内存（BasicMemory）由一个跟踪每个 ID 分配的映射组成，存储为一个列表（因为我们连续分配 ID）。
操作
先看一些基本操作：
impl Allocation {
fn size(self) -> BigInt { self.contents.len() }
fn overlaps(self, other_addr: BigInt, other_size: Size) -> bool {
let end_addr = self.addr + self.size();
let other_end_addr = other_addr + other_size;
if end_addr <= other_addr || other_end_addr <= self.addr {
// 结尾是在它们起始之前，反之亦然 - 不会重叠。
false
} else {
true
}
}
}
然后看看创建和删除内存分配
impl MemoryInterface for BasicMemory {
fn allocate(&mut self, size: Size, align: Align) -> NdResult<Pointer<AllocId>> {
// 拒绝太大的分配，大小必须适合 “isize”。
if !size.in_bounds(Signed, PTR_SIZE) {
throw_ub!("asking for a too large allocation");
}
// 选择一个基本地址。我们使用daemonic非决定性的选择，
// 意味着程序必须应付每一种可能的选择。
// FIXME: 这使得OOM（当没有可能的选择时）变成 "没有行为"，
// 这不是我们想要的。
let addr = pick(|addr: BigInt| {
// 选择严格的正整数...
if addr <= 0 { return false; }
// ... 适当对齐...
if addr % align != 0 { return false; }
// ... 使得 addr+size 在 `usize` 范围内...
if !(addr+size).in_bounds(Unsigned, PTR_SIZE) { return false; }
// ... 并且不会和已经存在的活跃分配内存重叠
if self.allocations.values().any(|a| a.live && a.overlaps(addr, size)) { return false; }
// 如果所有测试通过就很好
true
})?;
// 计算分配
let allocation = Allocation {
addr,
align,
live: true,
contents: list![AbstractByte::Uninit; size],
}
// 插入到 list，并且记录它的位置
let id = AllocId(self.allocations.len());
self.allocations.push(allocation);
// And we are done!
Pointer { addr, provenance: Some(id) }
}
fn deallocate(&mut self, ptr: Pointer<AllocId>, size: Size, align: Align) -> Result {
let Some(id) = ptr.provenance else {
throw_ub!("deallocating invalid pointer")
};
// 这种查找肯定会起作用，因为分配不能伪造。
let allocation = &mut self.allocations[id.0];
// 进行一系列检查.
if !allocation.live {
throw_ub!("double-free");
}
if ptr.addr != allocation.addr {
throw_ub!("deallocating with pointer not to the beginning of its allocation");
}
if size != allocation.size() {
throw_ub!("deallocating with incorrect size information");
}
if align != allocation.align {
throw_ub!("deallocating with incorrect alignment information");
}
// Mark it as dead. That's it.
allocation.live = false.
}
}
内存模型的关键操作当然是处理 load和store。我们为它们定义的辅助函数check_ptr也用于实现内存 API 的最后一部分，dereferenceable.
impl BasicMemory {
/// 检查给定指针对于给定长度和对齐的访问是否可取消引用
/// 对于可解引用，返回分配 ID 和偏移量
/// 对于大小为 0 的无效指针和访问可能会丢失
fn check_ptr(&self, ptr: Self::Pointer, len: Size, align: Align) -> Result<Option<(AllocId, Size)>> {
// Basic address sanity checks.
if ptr.addr == 0 {
throw_ub!("dereferencing null pointer");
}
if ptr.addr % align != 0 {
throw_ub!("pointer is insufficiently aligned");
}
// Now try to access the allocation information.
let Some(id) = ptr.provenance else {
// An invalid pointer.
if size != 0 {
throw_ub!("non-zero-sized access with invalid pointer");
}
// Zero-sized accesses are fine.
return None;
}
let allocation = &self.allocations[id.0];
// 计算相对偏移量，并确保我们在界内
let offset_in_alloc = ptr.addr - allocation.addr;
if offset_in_alloc < 0 || offset_in_alloc+len > allocation.size() {
// 越界内存访问
throw_ub!("out-of-bounds memory access");
}
// All is good!
Some((id, Size::from_bytes(offset_in_alloc).unwrap()))
}
}
impl MemoryInterface for BasicMemory {
fn load(&mut self, ptr: Pointer<AllocId>, len: Size, align: Align) -> Result<List<AbstractByte<AllocId>>> {
let Some((id, offset)) = self.check_ptr(ptr, len, align)? else {
return list![];
}
let allocation = &self.allocations[id.0];
// Slice into the contents, and copy them to a new list.
allocation.contents[offset..][..len].iter().collect()
}
fn store(&mut self, ptr: Self::Pointer, bytes: List<Self::AbstractByte>, align: Align) -> Result {
let Some((id, offset)) = self.check_ptr(ptr, bytes.len(), align)? else {
return;
}
let allocation = &mut self.allocations[id.0];
// Slice into the contents, and put the new bytes there.
allocation.contents[offset..][..len].copy_from_slice(bytes);
}
fn dereferenceable(&self, ptr: Self::Pointer, size: Size, align: Align) -> Result {
self.check_ptr(ptr, size, align)?;
}
}
延伸阅读
宣布：MiniRust[2] https://github.com/RalfJung/minirust [3]
参考资料
MiniRust/mem/basic.md: https://github.com/RalfJung/minirust/blob/master/mem/basic.md
宣布：MiniRust: https://www.ralfj.de/blog/2022/08/08/minirust.html
[3]https://github.com/RalfJung/minirust : https://github.com/RalfJung/minirust
- 1. Rust 生态蜜蜂｜2022-7-24
- 2. Rust 生态蜜蜂｜2022-7-31
- 3. Rust 生态蜜蜂｜2022-08-01
#Rust生态蜜蜂