Adding upstream version 110.0.1.upstream/110.0.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 293 insertions, 0 deletions

diff --git a/servo/components/style/parallel.rs b/servo/components/style/parallel.rs
new file mode 100644
index 0000000000..fea031115a
--- /dev/null
+++ b/servo/components/style/parallel.rs
@@ -0,0 +1,293 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+//! Implements parallel traversal over the DOM tree.
+//!
+//! This traversal is based on Rayon, and therefore its safety is largely
+//! verified by the type system.
+//!
+//! The primary trickiness and fine print for the above relates to the
+//! thread safety of the DOM nodes themselves. Accessing a DOM element
+//! concurrently on multiple threads is actually mostly "safe", since all
+//! the mutable state is protected by an AtomicRefCell, and so we'll
+//! generally panic if something goes wrong. Still, we try to to enforce our
+//! thread invariants at compile time whenever possible. As such, TNode and
+//! TElement are not Send, so ordinary style system code cannot accidentally
+//! share them with other threads. In the parallel traversal, we explicitly
+//! invoke |unsafe { SendNode::new(n) }| to put nodes in containers that may
+//! be sent to other threads. This occurs in only a handful of places and is
+//! easy to grep for. At the time of this writing, there is no other unsafe
+//! code in the parallel traversal.
+
+#![deny(missing_docs)]
+
+use crate::context::{StyleContext, ThreadLocalStyleContext};
+use crate::dom::{OpaqueNode, SendNode, TElement};
+use crate::scoped_tls::ScopedTLS;
+use crate::traversal::{DomTraversal, PerLevelTraversalData};
+use arrayvec::ArrayVec;
+use itertools::Itertools;
+use rayon;
+use smallvec::SmallVec;
+
+/// The minimum stack size for a thread in the styling pool, in kilobytes.
+pub const STYLE_THREAD_STACK_SIZE_KB: usize = 256;
+
+/// The stack margin. If we get this deep in the stack, we will skip recursive
+/// optimizations to ensure that there is sufficient room for non-recursive work.
+///
+/// We allocate large safety margins because certain OS calls can use very large
+/// amounts of stack space [1]. Reserving a larger-than-necessary stack costs us
+/// address space, but if we keep our safety margin big, we will generally avoid
+/// committing those extra pages, and only use them in edge cases that would
+/// otherwise cause crashes.
+///
+/// When measured with 128KB stacks and 40KB margin, we could support 53
+/// levels of recursion before the limiter kicks in, on x86_64-Linux [2]. When
+/// we doubled the stack size, we added it all to the safety margin, so we should
+/// be able to get the same amount of recursion.
+///
+/// [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1395708#c15
+/// [2] See Gecko bug 1376883 for more discussion on the measurements.
+///
+pub const STACK_SAFETY_MARGIN_KB: usize = 168;
+
+/// The maximum number of child nodes that we will process as a single unit.
+///
+/// Larger values will increase style sharing cache hits and general DOM
+/// locality at the expense of decreased opportunities for parallelism.  There
+/// are some measurements in
+/// https://bugzilla.mozilla.org/show_bug.cgi?id=1385982#c11 and comments 12
+/// and 13 that investigate some slightly different values for the work unit
+/// size.  If the size is significantly increased, make sure to adjust the
+/// condition for kicking off a new work unit in top_down_dom, because
+/// otherwise we're likely to end up doing too much work serially.  For
+/// example, the condition there could become some fraction of WORK_UNIT_MAX
+/// instead of WORK_UNIT_MAX.
+pub const WORK_UNIT_MAX: usize = 16;
+
+/// A set of nodes, sized to the work unit. This gets copied when sent to other
+/// threads, so we keep it compact.
+type WorkUnit<N> = ArrayVec<SendNode<N>, WORK_UNIT_MAX>;
+
+/// A callback to create our thread local context.  This needs to be
+/// out of line so we don't allocate stack space for the entire struct
+/// in the caller.
+#[inline(never)]
+fn create_thread_local_context<'scope, E>(slot: &mut Option<ThreadLocalStyleContext<E>>)
+where
+    E: TElement + 'scope,
+{
+    *slot = Some(ThreadLocalStyleContext::new());
+}
+
+/// A parallel top-down DOM traversal.
+///
+/// This algorithm traverses the DOM in a breadth-first, top-down manner. The
+/// goals are:
+/// * Never process a child before its parent (since child style depends on
+///   parent style). If this were to happen, the styling algorithm would panic.
+/// * Prioritize discovering nodes as quickly as possible to maximize
+///   opportunities for parallelism.  But this needs to be weighed against
+///   styling cousins on a single thread to improve sharing.
+/// * Style all the children of a given node (i.e. all sibling nodes) on
+///   a single thread (with an upper bound to handle nodes with an
+///   abnormally large number of children). This is important because we use
+///   a thread-local cache to share styles between siblings.
+#[inline(always)]
+#[allow(unsafe_code)]
+fn top_down_dom<'a, 'scope, E, D>(
+    nodes: &'a [SendNode<E::ConcreteNode>],
+    root: OpaqueNode,
+    mut traversal_data: PerLevelTraversalData,
+    scope: &'a rayon::ScopeFifo<'scope>,
+    pool: &'scope rayon::ThreadPool,
+    traversal: &'scope D,
+    tls: &'scope ScopedTLS<'scope, ThreadLocalStyleContext<E>>,
+) where
+    E: TElement + 'scope,
+    D: DomTraversal<E>,
+{
+    debug_assert!(nodes.len() <= WORK_UNIT_MAX);
+
+    // We set this below, when we have a borrow of the thread-local-context
+    // available.
+    let recursion_ok;
+
+    // Collect all the children of the elements in our work unit. This will
+    // contain the combined children of up to WORK_UNIT_MAX nodes, which may
+    // be numerous. As such, we store it in a large SmallVec to minimize heap-
+    // spilling, and never move it.
+    let mut discovered_child_nodes = SmallVec::<[SendNode<E::ConcreteNode>; 128]>::new();
+    {
+        // Scope the borrow of the TLS so that the borrow is dropped before
+        // a potential recursive call when we pass TailCall.
+        let mut tlc = tls.ensure(|slot: &mut Option<ThreadLocalStyleContext<E>>| {
+            create_thread_local_context(slot)
+        });
+
+        // Check that we're not in danger of running out of stack.
+        recursion_ok = !tlc.stack_limit_checker.limit_exceeded();
+
+        let mut context = StyleContext {
+            shared: traversal.shared_context(),
+            thread_local: &mut *tlc,
+        };
+
+        for n in nodes {
+            // If the last node we processed produced children, we may want to
+            // spawn them off into a work item. We do this at the beginning of
+            // the loop (rather than at the end) so that we can traverse our
+            // last bits of work directly on this thread without a spawn call.
+            //
+            // This has the important effect of removing the allocation and
+            // context-switching overhead of the parallel traversal for perfectly
+            // linear regions of the DOM, i.e.:
+            //
+            // <russian><doll><tag><nesting></nesting></tag></doll></russian>
+            //
+            // which are not at all uncommon.
+            //
+            // There's a tension here between spawning off a work item as soon
+            // as discovered_child_nodes is nonempty and waiting until we have a
+            // full work item to do so.  The former optimizes for speed of
+            // discovery (we'll start discovering the kids of the things in
+            // "nodes" ASAP).  The latter gives us better sharing (e.g. we can
+            // share between cousins much better, because we don't hand them off
+            // as separate work items, which are likely to end up on separate
+            // threads) and gives us a chance to just handle everything on this
+            // thread for small DOM subtrees, as in the linear example above.
+            //
+            // There are performance and "number of ComputedValues"
+            // measurements for various testcases in
+            // https://bugzilla.mozilla.org/show_bug.cgi?id=1385982#c10 and
+            // following.
+            //
+            // The worst case behavior for waiting until we have a full work
+            // item is a deep tree which has WORK_UNIT_MAX "linear" branches,
+            // hence WORK_UNIT_MAX elements at each level.  Such a tree would
+            // end up getting processed entirely sequentially, because we would
+            // process each level one at a time as a single work unit, whether
+            // via our end-of-loop tail call or not.  If we kicked off a
+            // traversal as soon as we discovered kids, we would instead
+            // process such a tree more or less with a thread-per-branch,
+            // multiplexed across our actual threadpool.
+            if discovered_child_nodes.len() >= WORK_UNIT_MAX {
+                let mut traversal_data_copy = traversal_data.clone();
+                traversal_data_copy.current_dom_depth += 1;
+                traverse_nodes(
+                    discovered_child_nodes.drain(..),
+                    DispatchMode::NotTailCall,
+                    recursion_ok,
+                    root,
+                    traversal_data_copy,
+                    scope,
+                    pool,
+                    traversal,
+                    tls,
+                );
+            }
+
+            let node = **n;
+            let mut children_to_process = 0isize;
+            traversal.process_preorder(&traversal_data, &mut context, node, |n| {
+                children_to_process += 1;
+                let send_n = unsafe { SendNode::new(n) };
+                discovered_child_nodes.push(send_n);
+            });
+
+            traversal.handle_postorder_traversal(&mut context, root, node, children_to_process);
+        }
+    }
+
+    // Handle whatever elements we have queued up but not kicked off traversals
+    // for yet.  If any exist, we can process them (or at least one work unit's
+    // worth of them) directly on this thread by passing TailCall.
+    if !discovered_child_nodes.is_empty() {
+        traversal_data.current_dom_depth += 1;
+        traverse_nodes(
+            discovered_child_nodes.drain(..),
+            DispatchMode::TailCall,
+            recursion_ok,
+            root,
+            traversal_data,
+            scope,
+            pool,
+            traversal,
+            tls,
+        );
+    }
+}
+
+/// Controls whether traverse_nodes may make a recursive call to continue
+/// doing work, or whether it should always dispatch work asynchronously.
+#[derive(Clone, Copy, PartialEq)]
+pub enum DispatchMode {
+    /// This is the last operation by the caller.
+    TailCall,
+    /// This is not the last operation by the caller.
+    NotTailCall,
+}
+
+impl DispatchMode {
+    fn is_tail_call(&self) -> bool {
+        matches!(*self, DispatchMode::TailCall)
+    }
+}
+
+/// Enqueues |nodes| for processing, possibly on this thread if the tail call
+/// conditions are met.
+#[inline]
+pub fn traverse_nodes<'a, 'scope, E, D, I>(
+    nodes: I,
+    mode: DispatchMode,
+    recursion_ok: bool,
+    root: OpaqueNode,
+    traversal_data: PerLevelTraversalData,
+    scope: &'a rayon::ScopeFifo<'scope>,
+    pool: &'scope rayon::ThreadPool,
+    traversal: &'scope D,
+    tls: &'scope ScopedTLS<'scope, ThreadLocalStyleContext<E>>,
+) where
+    E: TElement + 'scope,
+    D: DomTraversal<E>,
+    I: ExactSizeIterator<Item = SendNode<E::ConcreteNode>>,
+{
+    debug_assert_ne!(nodes.len(), 0);
+
+    // This is a tail call from the perspective of the caller. However, we only
+    // want to actually dispatch the job as a tail call if there's nothing left
+    // in our local queue. Otherwise we need to return to it to maintain proper
+    // breadth-first ordering. We also need to take care to avoid stack
+    // overflow due to excessive tail recursion. The stack overflow avoidance
+    // isn't observable to content -- we're still completely correct, just not
+    // using tail recursion any more. See Gecko bugs 1368302 and 1376883.
+    let may_dispatch_tail =
+        mode.is_tail_call() && recursion_ok && !pool.current_thread_has_pending_tasks().unwrap();
+
+    // In the common case, our children fit within a single work unit, in which
+    // case we can pass the SmallVec directly and avoid extra allocation.
+    if nodes.len() <= WORK_UNIT_MAX {
+        let work: WorkUnit<E::ConcreteNode> = nodes.collect();
+        if may_dispatch_tail {
+            top_down_dom(&work, root, traversal_data, scope, pool, traversal, tls);
+        } else {
+            scope.spawn_fifo(move |scope| {
+                gecko_profiler_label!(Layout, StyleComputation);
+                let work = work;
+                top_down_dom(&work, root, traversal_data, scope, pool, traversal, tls);
+            });
+        }
+    } else {
+        for chunk in nodes.chunks(WORK_UNIT_MAX).into_iter() {
+            let nodes: WorkUnit<E::ConcreteNode> = chunk.collect();
+            let traversal_data_copy = traversal_data.clone();
+            scope.spawn_fifo(move |scope| {
+                gecko_profiler_label!(Layout, StyleComputation);
+                let n = nodes;
+                top_down_dom(&*n, root, traversal_data_copy, scope, pool, traversal, tls)
+            });
+        }
+    }
+}