return_address intrinsic problematic with MIR and hard/impossible to use safely.

[eddyb]

Servo currently can't compile with -Zorbit (see servo/servo#11706) and my suspect is return_address.

Even if that wasn't the reason, Servo's usage of return_address to create a rooting cycle only ever worked because it happened to get the final destination of the call, but with MIR, the call destination might be a temporary, so it's not the final destination anymore.
Servo has a lint for disallowing moves on the types that are being returned, but that analysis is wrong unless performed on exactly the MIR we translate.

We also could change the ABI at any time, so the indirect returns becomes direct (we can do this for any pair of pointer-sized values) which would also break Servo.
I'm not even sure how LLVM doesn't miscompile what Servo is doing, capturing an sret argument seems quite dubious to me, and some architectures also have an intermediary copy.

AFAIK, the eventual solution is to have proper stack map support, however that might be a long ways off and I don't want to block removing old trans on it.

cc @jdm @pcwalton @Manishearth @rust-lang/compiler

[arielb1]

@eddyb

The problematic function is CallSetup::new, right?

The problematic code is

    pub fn new<T: CallbackContainer>(callback: &T, handling: ExceptionHandling) -> CallSetup {
        let global = unsafe { global_root_from_object(callback.callback()) };
        let cx = global.r().get_cx();

        let exception_compartment = unsafe {
            GetGlobalForObjectCrossCompartment(callback.callback())
        };
        CallSetup {
            exception_compartment: RootedObject::new_with_addr(cx,
                                                               exception_compartment,
                                                               unsafe { return_address() }),
            cx: cx,
            old_compartment: unsafe { JS_EnterCompartment(cx, callback.callback()) },
            handling: handling,
        }
    }

RVO is actually pretty reliable with MIR (in initializations, that's it, not in assignments) - the only problem is that there is an aggregate here, and that we don't have aggregate RVO optimization.

[eddyb]

Well, it looks like RootedTraceable doesn't use return_address, only RootedVec and CallSetup do, which suggests it's not as essential.
Why can't those use the same mechanism RootedTraceable does?

[eefriedman]

The return_address trick is a performance optimization to avoid heap allocations. Strictly speaking, RootedVec isn't necessary at all: a RootedVec<JS<T>> is basically equivalent to a Vec<Root<T>>. But Vec<Root<T>> involves keeping each element of the vector on the global root list, which is bad, so instead we want to root the Vec as a whole. Rooting something requires a stable address... which means either pointing at a heap allocation, or using return_address with the no_move lint.

It would be easy to change RootedVec so it contains a Box<Vec<T>> instead of a Vec<T>, but that requires extra heap allocations. If we wanted to be fancy, RootedVec could use manual memory management and keep the root pointed at the underlying heap allocation... but that requires writing a bunch of extra code.

[eddyb]

@eefriedman I think the last option is the best one, and it can still use Vec and/or liballoc's RawVec.
Although it's hard to tell what kind of mutation of the underlying Vec is being done with RootedVec before removing the DerefMut<Target = Vec<T>> for RootedVec<T> implementation.

[eefriedman]

FYI, there's a couple more uses of return_address in rust-mozjs: https://github.com/servo/rust-mozjs/blob/c6f6817a7beb7f310050e1dde88654a95de6df26/src/rust.rs . In particular, I think there's a bunch of code in Servo using the Rooted type.

[eddyb]

@eefriedman Ah, there it is! Rooted is what I remembered and was surprised to not find in Servo itself.

[Manishearth]

. If we wanted to be fancy, RootedVec could use manual memory management and keep the root pointed at the underlying heap allocation..

Well, the root set needs to know the length too so just keeping a ptr to the heap alloc isn't enough. What we can do is have:

struct RootedVecBox<T> {
 len: usize,
 cap: usize,
 rootsetptr: *const RootSetEntry,
 data: [T]
}

and use Box<RootedVecBox<T>> everywhere. Each time the vec reallocates, we update the root set with the new location. Requires reimplementing half of Vec though.

[eddyb]

@Manishearth However, Rooted is a bigger problem - what's the difference between it and RootedTraceable?

[jdm]

Rooted is a port of the C++ Rooted type which uses a separate linked list-based rooting mechanism.

[eddyb]

@jdm Are both in active use? I'm envisioning something like this would be optimal before stack maps:

#[thread_local]
static ROOT_STACK: RootStack = RootStack {
    roots: [Cell::new(ptr::null()); 32 * 1024],
    top: Cell::new(0)
};

When pushing, check for overflow, increment the top, store your pointer and keep the index.
When popping, write a NULL over your index's slot, then if your index is at the top (which is only always true when roots are destroyed in the exact reverse order in which they were taken) find the first non-NULL to move the top back down to.

I believe RootedTraceable would be similar, but with an extra function pointer for each entry.

For RootedVec, I just realized that there's a good compromise, in between Box<Vec<T>> and manually reimplementing all of Vec: have a RootVecStack, like RootStack but instead of just a pointer, keep an UnsafeCell<Option<(unsafe fn(*const Vec<()>), Vec<()>)>> for each root.

RootedVec<T> then holds a *mut Vec<T> pointing into the RootVecStack.
I'm not sure about allowing someone to obtain a &mut Vec<T>, but worst-case you'd shim the methods of Vec to go through the raw pointer, without actually keeping a &mut Vec<T>. The current implementation has the same problem though, the Vec is aliased in a way.

Note that Vec<()> is used so that in case the root doesn't take it out and destroy it, it gets leaked, i.e. mem::forget on RootedVec<T> has the same effect as on Vec<T>.

[jdm]

They are both in active use, yes. We use Rooted for stack roots of JS engine types; the things that live outside of rust-mozjs are for stack roots of Servo types that could contain JS engine types.

[eddyb]

On IRC @nox brought up that Rooted actually handles a moving GC, i.e. SM can update the pointer:

/*
 * Moving GC Stack Rooting
 *
 * A moving GC may change the physical location of GC allocated things, even
 * when they are rooted, updating all pointers to the thing to refer to its new
 * location. The GC must therefore know about all live pointers to a thing,
 * not just one of them, in order to behave correctly.
 *
 * The |Rooted| and |Handle| classes below are used to root stack locations
 * whose value may be held live across a call that can trigger GC. For a
 * code fragment such as:
 *
 * JSObject* obj = NewObject(cx);
 * DoSomething(cx);
 * ... = obj->lastProperty();
 *
 * If |DoSomething()| can trigger a GC, the stack location of |obj| must be
 * rooted to ensure that the GC does not move the JSObject referred to by
 * |obj| without updating |obj|'s location itself. This rooting must happen
 * regardless of whether there are other roots which ensure that the object
 * itself will not be collected.
 *
 * If |DoSomething()| cannot trigger a GC, and the same holds for all other
 * calls made between |obj|'s definitions and its last uses, then no rooting
 * is required.

This does not invalidate my shadow stack suggestion, but it does require holding a reference to an element of the thread-local array (i.e. &'static Cell<*mut JSObject>).
OTOH, you need a way to clear that slot (by writing NULL to it) anyway, so this is not worse.

EDIT: There's, however, the problem of hooking SM for the moving GC, not just tracing.
EDIT2: It seems possible to create a Handle<*mut JSObject> which is pointing into a TLS stack slot or any other place.

[eefriedman]

If you wanted to go the slightly awkward route, it's possible to write a macro that constructs a Rooted on the stack correctly:

rooted!(let data = RootedValue::new(global.get_cx(), init.data));

// Expands to:
let data = RootedValueContainer::new(global.get_cx(), init.data);
let data = RootedValue::new(&mut data);

[eddyb]

@eefriedman I've been told that was tried and didn't scale. I think the shadow stack can be more efficient than the linked list shenanigans and might eventually end up being mutated into the optimal stack map integration.

[pnkfelix]

compiler team would like more detail from servo if possible about exactly what guarantees they expect from the compiler (in terms of extra moves generated by mir-based trans vs old-trans)...

[pnkfelix]

(also: not sure if best fix possible is on the compiler side)

Anyway: assigning P-high because the breakage here breaks Servo.

[eddyb]

I can experiment with an approach like the TLS shadow stack made out of Rooted<*const ()> nodes instead of just the *const (), that shouldn't require anything from SM that isn't used already by Servo.

@jdm @Manishearth @pcwalton What's a reliable way to measure performance of SM <-> Rust interactions, i.e. can I tell whether I've made rooting slower?

[jdm]

Probably running the dromaeo tests; ./mach test-dromaeo --release dom >output will spit out a file, and ./mach compare_dromaeo before after will compare two files named before and after generated from running test-dromaeo and show the difference between them.

[eddyb]

The bad news: TLS gets ugly and has some overhead on platforms without cfg(target_thread_local).

The good news: I have originally misjudged the scale that Rooted and RootedVec were used on: only about 50 of the former and a dozen of the latter, with some more in the auto-generated bindings.

I was able to replace most uses with a macro which defines two variables, one being the stable object which has to be referenced from some list of roots and the other one the guard that does the insertion/removal from the list of roots, and provides access to the rooted value.

That macro doesn't work in 1.9 or earlier due to a hygiene bug which got fixed for 1.10, so my guess right now is that what I did has been tried in the past, unsuccessfully, due to the hygiene bug.

I will post the Servo PR with the performance numbers when I get compare_dromaeo working.
EDIT: Ahh, dromaeo has so much variance it's useless for a comparison 😞.

[nagisa]

Since servo was moved away from return_address and we removed the intrinsic in question this can be closed?

[eddyb]

@nagisa It's not yet fully merged.