[翻译]单线程共享可变性的问题

发表于 阅读次数： Disqus：

原文链接: https://manishearth.github.io/blog/2015/05/17/the-problem-with-shared-mutability/
作者: Manish Goregaokar
翻译 by abaabaqua

注: 这篇文章写的比较早,早期的Rust编译器有很多不友善的地方,代码示例中部分当时无法编译的现在已经可以了,译者会增改一些代码导致和原文不同.

Edit(2017年1月):我重新发现了Niko的文章,文章也提到了这一点并达到了同样的认识.我怀疑我下意识地从这篇文章中得到了这个想法,至少是部分的想法.

这是我一直想写的一篇文章;Rust 1.0的发布给了我继续接下去的完美动力.

虽然这篇文章是讨论Rust设计中的一个选择,并且例子都是用Rust写的,但这里讨论的原则在很大程度上适用于其它语言.我还将尝试让那些没有Rust背景的人更容易理解这篇文章;如果需要解释一些代码或术语,请告诉我.

我将在这里讨论的是Rust做的一个选择,不允许同一数据有多个可变别名(或者当有active的不可变别名时只能有一个可变别名) ，即使是在同一个线程.本质上讲,它不允许做这样的事情:

let mut x = Vec::new();
{
    let ptr = &mut x; // 获取队`x`的可变引用
    ptr.push(1); // 允许
    let y = x[0]; // 不允许 (无法编译): 只要`ptr`是active的,
                  // x不能读取 ...
    x.push(1);    // .. 也不能写入
    println!("{:?}", ptr); // 这段是译者新加 现在的编译器限制判断是否active更加智能 不是看整个作用域了
}

// 另外一种,

let mut x = Vec::new();
x.push(1); // 允许
{
    let ptr = &x; // 创建一个不可变引用
    let y = ptr[0]; // 允许, 不改变值
    let y = x[0]; // 同样允许
    x.push(1); // 不允许 (无法编译): 只要`ptr`是active,
               // `x`被冻结了可变性
    println!("{:?}", ptr); // 译者新加 原因一样
}

这相当于是”读写锁”(Read-Write lock,RWLock)模式,只不过它不在一个多线程的环境中使用,而且”锁”是通过静态分析完成的(编译时的”borrow checking”).

语言的初学者会有一个反复出现的问题,为什么会有这种设计.所有权语义和不可变借用是容易理解的,因为其他一些语言比如像C++也有一些具体的例子来解决这些概念所防止的问题.对于只有一个所有者和多个借用者(静态保证存活时间不会超过所有者)是有意义的,可以防止比如释放之后使用(use-after-free)这类的问题.

但是使用多个句柄来改变一个对象会带来什么问题呢?我们为什么需要 RWLock模式?

它会导致内存不安全

这个问题是针对Rust的,我保证这将是唯一针对Rust的答案.

Rust的enums提供了代数数据类型的一种形式.Rust的enum允许”包含”数据,例如你可以有一个enum:

enum StringOrInt {
    Str(String),
    Int(i64)
}

该类型可以是具有关联字符串的Str,也可以是具有关联整数的Int.

对于这样的一个enum,我们可以造成一个segfault:

let mut x = Str("Hi!".to_string()); // 创建一个具有关联字符串"Hi!"的`Str`实例
let y = &mut x; // 创建一个x的可变引用

if let Str(ref insides) = x { // 如果x是`Str`, 将其内部数据借用给`insides`
    *y = Int(1); // 设置`*y`为`Int(1), 因此也是将`x`设置为`Int(1)`
    println!("x says: {}", insides); // Uh oh!
}

这个例子,我们使insides引用失效,因为将x设置为Int(1)意味着内部不再有字符串.但是,insides仍然是对String的引用,并且生成的程序集将尝试解引用指向曾经分配的字符串的指针所在的内存位置,并且可能最终尝试解引用1或附近的一些数据,从而导致Segfault.

目前为止还不错.我们知道,为了让Rust风格的enums在Rust中安全工作,我们需要RWLock模式.但是还有其他的我们需要RWLock模式的原因吗?没有多少语言有这样的enums,所以这对它们来说应该不是什么问题.

迭代器无效化

啊,每次问到上面这个问题的时候几乎都会提到这个例子.虽然我自己经常使用这个例子(并且觉得这是一个非常合适的例子,可以很快地解释),我也发现它有点逃避,原因我将在下面解释.这也是我写这篇文章的部分原因;对于那些想要深入研究的人来说,应该有一个更好的答案。

迭代器失效涉及使用类似迭代器的工具时,同时以某种方式修改底层数据集.

比如

let buf = vec![1,2,3,4];

for i in &buf {
    buf.push(i);
}

首先,这将导致无限循环(如果它能编译通过,但其实很不行,Rust会阻止这个行为).等价的C++例子是这个,我每次都会使用它。

无限循环甚至不是真正的问题.真正的问题是过不了多久我们就会得到一个segfault.在内部,vectors有一块确定的分配空间来使用.如果vector增长超过了这个空间,需要进行一个新的,更大的空间分配(同时释放旧的分配空间),因为vectors必须使用连续的内存.

这意味着当vector超出其容量时,它将重新分配,使得存储在迭代器中的引用失效,并导致use-after-free.

当然,这种case有一个简单的解决方案,在迭代器中存储Vec/Vector对象的引用,而不是直接指向堆中的vector的指针.这会导致迭代器额外的间接指向(注:要解引用两次)或更大的堆栈大小(取决于如何实现它),但总体上可以防止内存不安全.

但这仍然会在涉及多维vectors的更复杂的情况下引发问题.

“这实际上就是多线程”

在足够复杂的单线程程序中,能够改变状态的别名实际上等同于不加锁访问多线程间共享的数据

(以上是我对其他人的引用的解释,但我找不到原文,也不记得是谁写的) 我找到了原文,来自于kmc的评论:

我的直觉是,离我自己的代码比较远的其他代码就像在另一个线程中,尽管我可以推断它将对共享的可变状态做什么.

让我们退一步来看看为什么我们需要在多线程程序中使用锁.这取决于缓存和内存的工作方式;我们永远不用担心两个进程同时写入同一个内存位置导致产生一个混合的值,或者在写入过程中发生读取.

我们真正需要担心的是我们脚下的地毯会被拉出来.在编写一组相关的读/写操作时,应该考虑到一些不变量,而在这些不变量中间可能发生的任意读/写操作将使这些不变量失效.例如,一段代码可能首先读取一个vector的length,然后用for循环以length为界遍历这个vector.这里假设的不变量是vector的length.如果在其他线程中对vector调用pop(),那么在读取到length之后但在其他地方读取之前,这个不变量可能会失效,这可能会导致在最后一次遍历中出现Segfault或use-after-free。

但是,在单线程代码中,我们可能会遇到(在精神上)类似的情况:

let x = some_big_thing();
let len = x.some_vec.len();
for i in 0..len {
    x.do_something_complicated(x.some_vec[i]);
}

我们有相同的不变量(len);但是我们能确定x.do_something_complicated()不会修改x.some_vec吗?在一个复杂的代码库中,do_something_complicated()自身会调用许多其他函数,这些函数也可能修改x,因此很难对其进行检查.

当然,上面的例子是一个简化和人为设计的例子;但是这样的错误也可能发生在大型代码库中的 - 在大型代码库中,许多被调用的方法都有副作用,而这些副作用可能并不总是明显的.

这意味着在大型代码库中,我们会遇到和多线程代码一样的问题.当一个人不完全确定每行代码在做什么时,维护不变量是非常困难的.可以通过阅读代码(这需要一段时间)可以确定这一点,但是未来代码的修改可能会导致要再次阅读.一直这样做是不切实际的,最后bug会突然出现.

另一方面,有一个对于这种情况不会发生的静态保证是很好的.如果静态保证会让代码变得过于复杂(或者只是想避免借用检查器),Rust中可以使用单线程RWlock风格的RefCell类型。它是一种提供内部可变性的类型，其行为类似于借用检查器的运行时版本.可以用其他语言编写类似的包装.

修改:对于许多基础类型比如简单的整型,共享可变性并不是一个主要问题.对于这些类型,我们有一个类型称为Cell,让这些可变性和共享同时进行.这适用于所有的Copy类型,即只需要在栈上进行复制的类型.(而不涉及指针或其他间接方式的类型)

这种类型的bug也是可重入性问题的一个很好的来源.

安全抽象

上一节中的问题使得编写安全的抽象变得非常困难,尤其在使用泛型时.这个问题在Rust下更加明显(在Rust中,抽象被期望是安全的,最好是低开销的),这也并不是任何语言所独有的.

你公开的每个方法都有一个预期要遵循的约定.很多时候,约定是由类型安全本身处理的,或者你可能有一些基于错误的模型来抛出非约定的数据(比如,除以零).

但是,随着API(可以是内部的,也可以是公开的)变得越来越复杂,约定也变得越来越复杂.在运行时也不总是可能验证约定是否被违反,比如即便使用断言,很多情况下在复杂的代码中也很难防止迭代器失效.

创建一个方法并添加文档”前两个参数不应指向同一内存”是容易的.但是如果这个方法被其他方法使用,约定就会变得更加复杂,更加难以表达或检查.当涉及到泛型时,情况只会变得更糟;你有时无法强制不出现共享的可变别名,或者无法在文档中描述不允许的内容.API使用者也不一定遵从文档.

这使得编写安全,通用的抽象变得越来越困难.这样的抽象依赖于不变量,而这些不变量通常会被前一节中描述的问题所打破.强制这些不变量并不总是容易的.而且这样的抽象要么被误用,要么一开始就没有,选择了一个更重的选项.一般来说,这样的抽象或模式会被完全避开,即使它们可能会提高性能,因为它们是有风险并且难以维护.即使当前版本的代码是正确的,将来可能会有人再次改变某些东西来打破不变量.

我之前的文章描述了一种情况,Rust能够选择较轻的道路而C++在获得同样的保证下会更难.

请注意,这是一个比可变别名更广泛的问题.Rust也有这个问题,但是当涉及到可变的别名时就没有了.修复可变别名非常重要,因为当没有可变别名时,我们可以对程序做出很多假设.通过查看一行代码，我们可以知道局部变量发生了什么.如果存在可变别名,那么其他局部变量也有可能被修改.一个非常简单的例子是:

fn look_ma_no_temp_var_l33t_interview_swap(&mut x, &mut y) {
    *x = *x + *y;
    *y = *x - *y;
    *x = *x - *y;
}
// or
fn look_ma_no_temp_var_rockstar_interview_swap(&mut x, &mut y) {
    *x = *x ^ *y;
    *y = *x ^ *y;
    *x = *x ^ *y;
}

在上面两种情况下,当两个引用是相同时(Rust中不会发生),代码不是交换两个变量的值,而是将两个变量设置为零.用户(库的内部用户或API使用者)可能希望swap()在提供相同的引用时不会改变任何内容,但上面的代码做的是完全不同的事.这个假设可以在程序中使用;比如,在进行数组排序时,因为slot正在与它自己进行比较,所以swap()应该跳过,不应该改变任何东西;但上述的代码会改变,然后排序函数会用零填充所有内容.这个问题可以通过在文档中写参数的前置条件和使用断言来解决,但是随着swap()在其他方法中被使用,写文档变得越来越困难.

当然,上面的例子是为了说明问题人为的.现实中swap()实现具有一些先决条件,不能在这种条件下使用.此外,在大多数交换算法中,会有当比较元素与其自身时忽略的边界检查.

但是这个例子只是对手头问题的一个简单描述.

在Rust中,由于静态检查因此不需要太担心这些问题,并且可以设计健壮的API,因为知道什么时候某些东西不可变可以帮助简化不变量.

总结

不符合RWLock模式的别名使用是危险的.如果使用的是Rust这样的语言,那就不需要担心.如果正在使用C++这样的语言,它可能会导致内存不安全,所以要非常小心.如果使用Java或Go这样的语言,虽然它不会导致内存不安全,但是它会导致复杂的代码出现问题.

这也不意味着这个问题迫使你切换到Rust.如果你觉得可以避免写出这种问题的API,那这也是一种有效的解决方法.在使用GC的语言中,这个问题要罕见得多,因此你可以不费吹灰之力地完全避免它.使用运行时检查和断言来维护不变量也是可以的;毕竟性能并不是一切.

但这是编程中的一个问题;请确保在设计代码时考虑到这一点.

讨论:HN,Reddit

原文链接: https://manishearth.github.io/blog/2015/05/17/the-problem-with-shared-mutability/
作者: Manish Goregaokar
翻译 by abaabaqua

相关文章