Share allows for unsafe mutations in safe code

[michaelwoerister]

Since the Freeze kind has been replaced with Share it's possible to break things in safe code, such as mutating keys in a collection and thus invalidating the collection. With Freeze one was able to prevent this.

Here is an example of how one can break the standard hashmap:

#![feature(default_type_params)]

extern crate collections;
extern crate sync;

use collections::hashmap::HashMap;
use std::hash::Hash;
use std::sync::atomics::{AtomicUint, SeqCst};

// A perfectly valid `Share` type
struct Shareable {
    val: AtomicUint
}

impl Shareable {
    fn new(val: uint) -> Shareable {
        Shareable { val: AtomicUint::new(val) }
    }

    fn mutate_threadsafe(&self, val: uint) {
        self.val.store(val, SeqCst);
    }
}

impl Eq for Shareable {
    fn eq(&self, other: &Shareable) -> bool {
        self.val.load(SeqCst) == other.val.load(SeqCst)
    }
}

impl TotalEq for Shareable {}

impl<S: Writer> Hash<S> for Shareable {
    fn hash(&self, state: &mut S) {
        let _ = state.write_le_uint(self.val.load(SeqCst));
    }
}

#[test]
fn test() {
    let mut map = HashMap::new();

    for i in range(0u, 1000u) {
        map.insert(Shareable::new(i), i);
    }

    // With `Share` you can mutate through immutable references ...
    for k in map.keys() {
        k.mutate_threadsafe(999999u);
    }

    // ... leads to problems that Rust promises to prevent :(
    for i in range(0u, 1000u) {
        assert_eq!(map.find_copy(&Shareable::new(i)), Some(i));
    }
}

I think it might be a good idea to re-introduce Freeze (which could then imply Share). Being able to specify that a type can be made deeply immutable is a very strong and a very useful guarantee. It's one of the reasons why Rust's &T is much more useful than C++'s const T&. And as the above example shows, Share cannot provide a replacement for this as it basically just means that access to the object is synchronized. (I'm not even sure that Share as it is defined now---allowing for mutation through & references---is a good idea; but that's just a gut feeling)

[huonw]

I don't believe the HashMap breakage was affected by the Share -> Freeze change. The same effect could previously be achieved using Cell or RefCell, couldn't it? I.e. HashMap<Cell<uint>, uint>. (Well some wrapper around Cell that implements Hash.)

[michaelwoerister]

That's true but before could specify that keys have to be Freeze, now you can't.

[alexcrichton]

Nominating.

[brson]

It's not clear that this is a 'memory safety' issue, but may be just a logic error. I'll also note that before removing Freeze we didn't solve this. Admittedly though, this could be useful.

[pnkfelix]

There are a mix of problems/questions that should be addressed here:

• Does hash/hashmap actually document that the keys must not be mutated, or at least not mutated in any way that is propagated into their computed hash values? This property was almost built-in to our old setup when hashing was pretty much forced to always be IterBytes (excepting corner cases where one did things like make IterBytes return random results), but now the ability to plug in other hash functions (admittedly a feature-gated property) changes this. And of course the ability to mutate the keys as illustrated here also breaks this property.
• Is this actually exposing a safety violation? Depending on how hashmap is implemented, it could be, but if the hashmap were not using unsafe code, then you wouldn't have any safety violation -- it would just be that the internal variants of the hashmap are violated, and you get answers that you didn't expect, but things remain safe.
• Do we want to bring back the Freeze bound since it sounds like it may be useful in some cases (though may also be a stronger constraint than what you actually want/need for the keys in a hashmap, I'm not sure).

We should resolve the questions above; they may need to be split off into subbugs.

Accepted for 1.0, P-backcompat-lang

[huonw]

It appears that Python is simliarly affected. The following creates a dictionary with keys from 0-9, and then "reverses" the keys in-place.

class Foo:
    def __init__(self, i):
        self.i = i

    def __eq__(self, other):
        return self.i == other.i
    def __hash__(self):
        return self.i
    def __repr__(self):
        return 'Foo(%d)' % self.i

d = { Foo(i): i for i in range(0, 10)}
print('** Before **')
print(d)
print('d[1]: %s' % d[Foo(1)])

for k in d:
    k.i = 9 - k.i

print('** After **')
print(d)
print('d[1]: %s' % d[Foo(1)])

** Before **
{Foo(0): 0, Foo(1): 1, Foo(2): 2, Foo(3): 3, Foo(4): 4, Foo(5): 5, Foo(6): 6, Foo(7): 7, Foo(8): 8, Foo(9): 9}
d[1]: 1
** After **
{Foo(9): 0, Foo(8): 1, Foo(7): 2, Foo(6): 3, Foo(5): 4, Foo(4): 5, Foo(3): 6, Foo(2): 7, Foo(1): 8, Foo(0): 9}
Traceback (most recent call last):
  File "modify_key.py", line 22, in <module>
    print('d[1]: %s' % d[Foo(1)])
KeyError: Foo(1)

(I don't know if this is memory-unsafe.)

[michaelwoerister]

No, it may not necessarily always be a memory safety issue. But I remember several presentations where it was prominently stated that Rust's rules around references, mutability and aliasing prevented your typical iterator-invalidation bugs and ConcurrentModificationException scenarios. And I always found this to be very good argument for having the things the way they are.

I feel that with Share replacing Freeze, the meaning of 'immutable' references has changed in a subtle but significant way. Before, when I had a &T reference I knew a very important thing: I don't have to care about aliasing issues. &T would only allow aliasing in a way where it effectively would not matter. That's a huge deal for a programmer's mental workload when reading code. Granted, with Cell and @mut this already was not entirely true but Freeze would allow me to really safely guard against this problem.

Now, when I have a &T, what do I know? That access to the underlying object is synchronized. That's not nothing, admittedly, but aliasing has become an issue again. If I mutate something through some 'immutable' reference, what else will change? What's the role of &mut if & also allows for mutation. Maybe it would make more sense to have a &share reference kind instead of the Share trait. Then one could allow for synchronized access to an object without giving up on having the concept of deep immutability at the language level.

Well, this has become kind of a rant now :) Maybe it's just a problem I've glossed over so far because I try avoid Cell as much as possible. But I look at trans in its current form and I'm wondering if Share doesn't invite this unfortunate style of & being more of a suggestion than a hard guarantee.

[arielb1]

The assumption you made was never true - you could, and still can, write the following code

extern crate collections;
extern crate sync;

use collections::hashmap::HashMap;
use std::hash::Hash;
use std::io::File;

struct Evil {
  ix: uint
}


impl Evil {
    fn new(ix: uint, val: &[u8]) -> Evil {
        let result = Evil { ix: ix };
        result.mutate(val);
        result
    }

    fn mutate(&self, val: &[u8]) {
        let f = File::open(&Path::new(self.ix.to_str()));
        f.write(val);
    }
}

impl Eq for Evil {
    fn eq(&self, other: &Evil) -> bool {
        self.ix == other.ix
    }
}

impl TotalEq for Evil {}

impl<S: Writer> Hash<S> for Evil {
    fn hash(&self, state: &mut S) {
        let _ = state.write_le_uint(File::open(&Path::new(self.ix.to_str()))
            .read_to_end());
    }
}

#[test]
fn test() {
    let mut map = HashMap::new();

    for i in range(0u, 1000u) {
        map.insert(Evil::new(i, bytes!("good")), i);
    }

    // With `Share` you can mutate through immutable references ...
    for k in map.keys() {
        k.mutate(bytes!("evil"));
    }

    // ... leads to problems that Rust promises to prevent :(
    for i in range(0u, 1000u) {
        assert_eq!(map.find_copy(&Evil::new(i,  bytes!("good"))), Some(i));
    }
}

Which breaks the invariant, with IO substituting for direct mutation. What you really want is pure functions - which Rust probably isn't going to get - which would (of course) prevent IO and dereference of Cells etc.

[pcwalton]

I nominate this for removal; I don't see any way that addressing this could result in a backwards incompatible language change. Probably the biggest thing we could do is to reintroduce Freeze, which would be backwards compatible.

[michaelwoerister]

FWIW, I'm more relaxed about this issue now for a few reasons:

• @arielb1 is right, as soon as IO is involved, all bets are off and one has to rely on informal promises anyway.
• If Share, as has been proposed somewhere, is renamed to Threadsafe or something to that effect, the situation will be less ambiguous.

It would be nice if something like Freeze was expressible even when methods are involved but short of an effect system tracking IO, I don't see a way of doing this. Definitely not something I would expect in Rust 1.0.

[brson]

Closing for previously-stated reasons.