I am writing a JVM and cannot seem to avoid undefined behavior in this situation

help
1

I know this post is longer but please, read all the way through. I want to hear your thoughts. The last few paragraphs summarize well if you really just can't :).

I am writing a JVM implementation as a personal challenge and I seem to have run into a situation where undefined behavior appears to be unavoidable. I am looking for help/advice on how I can work around this or different approaches that I am overlooking.

To give a quick background, the JVM has a Method Area, where once a class is loaded, the implementation specific definition stores the object in memory. This is used to store static data such as class definitions and static fields. When a method is invoked, the class file is either loaded from the file system or if it has been loaded already, the implementation specific representation is located in the Method Area. The method in question is located, a stack frame is pushed and the method is ran.

Here is my problem, the Java language obviously allows multiple frames on the stack to use this Method Area, that is its purpose after all. So if a class is loaded from the method area, and thus borrowed, and a method that was pushed to the stack has an instruction to update a static field of that same class, (a mutable borrow) that represents a problem. In fact, it doesn't have to be the same class, it could be any class. How can I load the class mutably for update, and know that there is no other stack frame lower in the stack that has also loaded that class and is simultaneously borrowing it? I found that when this happens, MIRI blows up!

Consider the example:

A class ClassA is loaded from memory, and method foo is called, that method calls bar on ClassB. ClassB.bar() updates a static field on ClassA. That mutation of ClassA's static field requires the class to be loaded from the Method Area and mutated. How can you do this without running into undefined behavior?

So that's basically the problem. If my JVM wants to initialize this java class (init static fields essentially):

public class Simple {

    public static String field = "JumboTrout";
    public static double pi = 3.14159;
}

A class is loaded:

    fn load_class(&mut self, name: &str) -> Result<&'static mut StaticAlloc> {
        match self.class_manager.request(name, &mut self.method_area) {
            Ok(Response::InitReq(class, alloc_index)) => {
                self.init_class(class)?;
                self.method_area.get_mut(alloc_index)
            }
            Ok(Response::Ready(alloc_index)) => self.method_area.get_mut(alloc_index),
            Err(e) => bail!(e),
            _ => panic!("Manager returned a not found!"),
        }
    }

A reference to the class is given back to the caller to call the initialization method and, self.init_class(class) is called. That looks like this:

    fn init_class(&mut self, class: &'static Class) -> Result<()> {
        println!("Initializing class: {:?}", class.get_name());
        let clinit = class.methods.get(CLINIT).unwrap();
        let frame = CallFrame::new(clinit, &class.cp);
        self.frames.push(frame);
        self.execute_frame()
    }

The initializations method is found (thats what CLINIT is), the method is pushed to that stack of stack frames, and self.execute_frame() is called to execute that frame. You'll notice that the a shared reference to the Class is used to facilitate this. That come's back to by me in a moment.

Eventually a putstatic instruction is executed to assign a value one of the static fields of the class above.

In my JVM that is implemented like this:

    fn put_static(&mut self, field_index: usize) -> Result<()> {
        let top = self.frames.len() - 1;
        if let Constant::FieldRef {
            class_index,
            name_and_type_index,
        } = self.frames[top].cp.get(field_index).unwrap()
        {
            let (f_name, alloc) = self.unpack_f_name(class_index, name_and_type_index)?;
            let field = alloc.get_field_mut(&f_name);
            *field = self.frames[top].stack.pop().unwrap();
        } else {
            bail!("Expected Constant::FieldRef for a put_static instruction.");
        };
        Ok(())
    }
}

I know that is a lot detail, but the code of interest is this one:

 let (f_name, alloc) = self.unpack_f_name(class_index, name_and_type_index)?;

That takes class_index, looks up its name, attempts to load it from the Method Area for mutation and BOOM! Undefined Behavior! That allocation of memory is already being borrowed! And that was back here:

fn init_class(&mut self, class: &'static Class)

Here is what miri has to say specifically:

error: Undefined Behavior: not granting access to tag <155013> because that would remove [SharedReadOnly for <120655512>] which is strongly protected because it is an argument of call 50092667
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/method_area.rs:71:21
    |
71  |         unsafe { Ok(&mut *(self.data.add(index))) }
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not granting access to tag <155013> because that would remove [SharedReadOnly for <120655512>] which is strongly protected because it is an argument of call 50092667
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <155013> was created here, as the base tag for alloc53111
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/method_area.rs:35:24
    |
35  |             let data = alloc::alloc(layout) as *mut StaticAlloc;
    |                        ^^^^^^^^^^^^^^^^^^^^
help: <120655512> is this argument
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:422:30
    |
422 |     fn init_class(&mut self, class: &'static Class) -> Result<()> {
    |                              ^^^^^
    = note: BACKTRACE (of the first span):
    = note: inside `sumatra_vm::method_area::MethodArea::get_mut` at /home/dylan/Documents/RustProjects/sumatra/vm/src/method_area.rs:71:21: 71:49
note: inside `sumatra_vm::vm::VM::<'_>::load_class`
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:414:49
    |
414 |             Ok(Response::Ready(alloc_index)) => self.method_area.get_mut(alloc_index),
    |                                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `sumatra_vm::vm::VM::<'_>::unpack`
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:444:32
    |
444 |             let static_alloc = self.load_class(name)?;
    |                                ^^^^^^^^^^^^^^^^^^^^^
note: inside `sumatra_vm::vm::VM::<'_>::unpack_f_name`
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:477:38
    |
477 |         let (name_index, _, alloc) = self.unpack(class_index, name_and_type)?;
    |                                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `sumatra_vm::vm::VM::<'_>::put_static`
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:395:35
    |
395 |             let (f_name, alloc) = self.unpack_f_name(class_index, name_and_type_index)?;
    |                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `sumatra_vm::vm::VM::<'_>::execute_frame`
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:281:56
    |
281 |                 Instruction::PutStatic(field_index) => self.put_static(*field_index as usize)?,
    |                                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `sumatra_vm::vm::VM::<'_>::init_class`
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:427:9
    |
427 |         self.execute_frame()
    |         ^^^^^^^^^^^^^^^^^^^^
note: inside `sumatra_vm::vm::VM::<'_>::load_class`
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:411:17
    |
411 |                 self.init_class(class)?;
    |                 ^^^^^^^^^^^^^^^^^^^^^^
note: inside `sumatra_vm::vm::VM::<'_>::run`
   --> /home/dylan/Documents/RustProjects/sumatra/vm/src/vm.rs:51:13
    |
51  |             self.load_class(c_entry)?
    |             ^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `main`
   --> cli/src/main.rs:19:5
    |
19  |     vm.run("Simple.class").unwrap()
    |     ^^^^^^^^^^^^^^^^^^^^^^

As I mulled over how to fix this, I realized I really don't know how? I mean, as I pointed out before, how can I make sure that when running code that can arbitrarily do anything, how can I allow multiple stack frames to mutate the same region in memory (as Java allows) without running afoul of Rust's borrowing rules? Or even consider race condition (some thing that java absolutely allows): If two threads are running and accessing a object, Java allows the mutation of objects without synchronization. Its undefined what will happen and the outcome is unpredictable but it isn't considered malformed java code to allow it. How can a compliant JVM specification be written in Rust without running into UB? Since Java allows this, does that mean a Rust implementation must transitively as well? But then you have to think of the implications of that. Is rustc going to optimize away a field write that absolutely cannot be optimized away?

I am getting carried away a little perhaps, but perhaps it is important question to answer before even deciding how to fix this problem, because perhaps this is just what comes with the territory of writing for a language that allows data races. In Rust world, a program that allows a data race is considered not well formed, but in Java land it is well-formed but perhaps just not a very useful program.

Anyway, please help me. Please guide me through this and if possible, how I can fix my code.

BTW I made a gist that condenses the problem to a more digestible size.

2

The short answer is "don't return references".

UB occurs when you violate the invariant that &mut T can never coexist with &T to the same instance of type T. You will notice that the safe Cell and RefCell types have a public API that is careful to avoid exactly this situation. Your API surface needs the same design constraints. Saying that is much easier said than done, but that's the gist.

I don't know if anyone has written anything clear and concise on the topic, but you should definitely start with the unsafe code guidelines and the nomicon. (I'm sure you are aware of all of this, but it bears repeating.)

4 Likes
3

As you noted, a data race is UB in Rust and must be avoided. So you would have synchronization in your Rust code, even if there was no corresponding synchronization in the Java code. When the result is unspecified in Java, you could switch up your implementation in ways that change behavior. So it may still "look like" a data race at the JVM layer. For example you could split writes to 64-bit integers/floats and still be within the spec (but not to Java references).

(I'm not familiar with Java's memory model and thus can't give very specific advice, but the atomic requirement noted in that link implies to me that JVM implementations do indeed need some sort of synchronization, in at least some cases, in order to meet the spec.)

1 Like
4

You may find the LLVM Atomic Instructions and Concurrency Guide useful. It has the following possible orderings for memory accesses:

  • NotAtomic - corresponds to normal reads and writes in Rust
  • Unordered - corresponds to normal reads and writes in Java
  • Monotonic - this is Rust's relaxed atomic memory ordering
  • Acquire - this is Rust's acquire atomic memory ordering
  • Release - this is Rust's release atomic memory ordering
  • AcquireRelease - this is Rust's acqrel atomic memory ordering
  • SequentiallyConsistent - this is Rust's seqcst atomic memory ordering

So the ordering you need for a Java access lies somewhere between Rust's relaxed atomic and an ordinary memory access. Since Rust provides no way to perform an operation with the LLVM unordered ordering, the best you can do is to use relaxed atomics.

Note that unordered operations are guaranteed to not have tearing, so 64-bit operations in Java are actually two 32-bit unordered operations on some platforms.

Note also that in Java, volatile operations are not the same as what volatile means in Rust. Instead, a Java volatile operation is either an Acquire or Release operation depending on whether it is a read or write.

You may also find the Memory Model for Concurrent Operations section interesting.

2 Likes
5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.