Parallel handling of dom nodes in style/layout is a ball of unsafe spaghetti

[Ms2ger]

In particular, borrow_data_unchecked and friends scare me.

[SimonSapin]

@pcwalton, what makes borrow_data_unchecked and our usage of it not unsound?

[metajack]

There are several cases:

1. servo/components/style/parallel.rs

   Line 126 in 0fb5d63

   &*parent.borrow_data_unchecked().unwrap()

In this case, we are decrementing the children left count in the parent during a bottom up traversal. Because we are working on a child, the children left is at least one, therefor a job mutating the parent could not have been enqueued. The child that decreases the count to 1 will cause the parent to be enqueued.

Note that because two children could mutate the count simultaneously, it is done with atomics. I assume this is also why we used unchecked borrows.

1. servo/components/style/matching.rs

   Line 222 in e3be718

   match element.as_node().borrow_data_unchecked() {

I'm not sure about this one.

1. servo/components/style/matching.rs

   Line 233 in e3be718

   match parent_element.as_node().borrow_data_unchecked() {

I'm not sure about this one either.

1. servo/components/style/matching.rs

   Line 503 in e3be718

   parent_node.borrow_data_unchecked().map(|d| &*d)

No idea.

1. servo/components/style/matching.rs

   Line 658 in e3be718

   let parent_style = (*parent_node.borrow_data_unchecked().unwrap()).style.as_ref().unwrap();

seems to only be called from here:

servo/components/layout/traversal.rs

Line 76 in 14dc119

node.initialize_data();

[samlh]

The remainder all occur when determining the style for some dom nodes after the parent style is determined. Because multiple threads will access a given parent style at once (readonly), the obvious answer is a RWLock. Alas, it is too slow, thus the current code.

[notriddle]

Could an alternate implementation of RWLock be fast enough?

Uncontended lock acquisition and release is done through fast inline paths which only require a single atomic operation.

[metajack]

@notriddle Is a single compare exchange faster than the check that refcell does currently (which we've apparently already determined is not fast enough)? Or is the theory that we disabled the check because it's not threadsafe rather than because it is slow?

If we are using unchecked solely for the threadsafety issue, then maybe an RWLock with a fast path is a great plan. If we are doing unchecked for speed, then I don't see how any checks will be tolerated.

[notriddle]

Is a single compare exchange faster than the check that refcell does currently

No.

[SimonSapin]

@metajack My current theory is that RWLock would be too slow, and RefCell is not Sync/thread-safe: multiple threads calling the borrow method would race on incrementing/decrementing the borrow counter. If we can be "confident enough" that no thread is calling borrow_mut or holding a RefMut during that time, having multiple threads reading the data at the same time without touching the borrow counter could be memory-safe. But "confident enough" is key. I don’t think the type system is helping us with this right now.

But I’m only guessing here. @pcwalton You first introduced borrow_layout_data_unchecked, can you confirm?

I remember a talk/presentation several years ago explaining how Servo used phantom types for this kind of thing: giving different threads a different view of the same data to statically protect against data races. Did we remove this?

[jdm]

The phantom types in question were something like Node<Script> vs. Node<Layout>, which allowed us to define only methods that were relevant to layout; it didn't provide any protection for multiple layout threads as far as I recall.

[metajack]

We still use something similar. See

servo/components/script_layout_interface/wrapper_traits.rs

Line 86 in 3de14d9

pub trait ThreadSafeLayoutNode: Clone + Copy + Sized + PartialEq {

It's not a true phantom type, but the idea is the same. The code that operates on these cannot access ancestors or siblings via the trait, and I assume it always deals with Box.

I thought there was a similar construction in the actual layout code for each of the two directions.

[pcwalton]

One potential way to consolidate the unchecked accesses might be to have some sort of borrow_layout_data_for_current_node() that borrows the layout data only for the single node that is being restyled right now, with only a single unsynchronized check to avoid double borrows. That would ensure that we never double-borrow, as long as the traversal is correct (and if the traversal is wrong, we have lots of other problems).