style/
parallel.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5//! Implements parallel traversal over the DOM tree.
6//!
7//! This traversal is based on Rayon, and therefore its safety is largely
8//! verified by the type system.
9//!
10//! The primary trickiness and fine print for the above relates to the
11//! thread safety of the DOM nodes themselves. Accessing a DOM element
12//! concurrently on multiple threads is actually mostly "safe", since all
13//! the mutable state is protected by an AtomicRefCell, and so we'll
14//! generally panic if something goes wrong. Still, we try to to enforce our
15//! thread invariants at compile time whenever possible. As such, TNode and
16//! TElement are not Send, so ordinary style system code cannot accidentally
17//! share them with other threads. In the parallel traversal, we explicitly
18//! invoke |unsafe { SendNode::new(n) }| to put nodes in containers that may
19//! be sent to other threads. This occurs in only a handful of places and is
20//! easy to grep for. At the time of this writing, there is no other unsafe
21//! code in the parallel traversal.
22
23#![deny(missing_docs)]
24
25use crate::context::{StyleContext, ThreadLocalStyleContext};
26use crate::dom::{OpaqueNode, SendNode, TElement};
27use crate::scoped_tls::ScopedTLS;
28use crate::traversal::{DomTraversal, PerLevelTraversalData};
29use std::collections::VecDeque;
30
31/// The minimum stack size for a thread in the styling pool, in kilobytes.
32#[cfg(feature = "gecko")]
33pub const STYLE_THREAD_STACK_SIZE_KB: usize = 256;
34
35/// The minimum stack size for a thread in the styling pool, in kilobytes.
36/// Servo requires a bigger stack in debug builds.
37/// We allow configuring the size, since running with ASAN requires an even larger
38/// stack size.
39#[cfg(feature = "servo")]
40pub const STYLE_THREAD_STACK_SIZE_KB: usize = const {
41    let default_stack_size = 512;
42    if let Some(user_def_size) = option_env!("SERVO_STYLE_THREAD_STACK_SIZE_KB") {
43        if let Ok(user_def_size) = usize::from_str_radix(user_def_size, 10) {
44            user_def_size
45        } else {
46            panic!("SERVO_STYLE_THREAD_STACK_SIZE_KB must be a valid integer")
47        }
48    } else {
49        default_stack_size
50    }
51};
52
53/// The stack margin. If we get this deep in the stack, we will skip recursive
54/// optimizations to ensure that there is sufficient room for non-recursive work.
55///
56/// We allocate large safety margins because certain OS calls can use very large
57/// amounts of stack space [1]. Reserving a larger-than-necessary stack costs us
58/// address space, but if we keep our safety margin big, we will generally avoid
59/// committing those extra pages, and only use them in edge cases that would
60/// otherwise cause crashes.
61///
62/// When measured with 128KB stacks and 40KB margin, we could support 53
63/// levels of recursion before the limiter kicks in, on x86_64-Linux [2]. When
64/// we doubled the stack size, we added it all to the safety margin, so we should
65/// be able to get the same amount of recursion.
66///
67/// [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1395708#c15
68/// [2] See Gecko bug 1376883 for more discussion on the measurements.
69pub const STACK_SAFETY_MARGIN_KB: usize = 168;
70
71/// A callback to create our thread local context.  This needs to be
72/// out of line so we don't allocate stack space for the entire struct
73/// in the caller.
74#[inline(never)]
75pub(crate) fn create_thread_local_context<'scope, E>(slot: &mut Option<ThreadLocalStyleContext<E>>)
76where
77    E: TElement + 'scope,
78{
79    *slot = Some(ThreadLocalStyleContext::new());
80}
81
82// Sends one chunk of work to the thread-pool.
83fn distribute_one_chunk<'a, 'scope, E, D>(
84    items: VecDeque<SendNode<E::ConcreteNode>>,
85    traversal_root: OpaqueNode,
86    work_unit_max: usize,
87    traversal_data: PerLevelTraversalData,
88    scope: &'a rayon::ScopeFifo<'scope>,
89    traversal: &'scope D,
90    tls: &'scope ScopedTLS<'scope, ThreadLocalStyleContext<E>>,
91) where
92    E: TElement + 'scope,
93    D: DomTraversal<E>,
94{
95    scope.spawn_fifo(move |scope| {
96        #[cfg(feature = "gecko")]
97        gecko_profiler_label!(Layout, StyleComputation);
98        let mut tlc = tls.ensure(create_thread_local_context);
99        let mut context = StyleContext {
100            shared: traversal.shared_context(),
101            thread_local: &mut *tlc,
102        };
103        style_trees(
104            &mut context,
105            items,
106            traversal_root,
107            work_unit_max,
108            traversal_data,
109            Some(scope),
110            traversal,
111            tls,
112        );
113    })
114}
115
116/// Distributes all items into the thread pool, in `work_unit_max` chunks.
117fn distribute_work<'a, 'scope, E, D>(
118    mut items: impl Iterator<Item = SendNode<E::ConcreteNode>>,
119    traversal_root: OpaqueNode,
120    work_unit_max: usize,
121    traversal_data: PerLevelTraversalData,
122    scope: &'a rayon::ScopeFifo<'scope>,
123    traversal: &'scope D,
124    tls: &'scope ScopedTLS<'scope, ThreadLocalStyleContext<E>>,
125) where
126    E: TElement + 'scope,
127    D: DomTraversal<E>,
128{
129    use std::iter::FromIterator;
130    loop {
131        let chunk = VecDeque::from_iter(items.by_ref().take(work_unit_max));
132        if chunk.is_empty() {
133            return;
134        }
135        distribute_one_chunk(
136            chunk,
137            traversal_root,
138            work_unit_max,
139            traversal_data,
140            scope,
141            traversal,
142            tls,
143        );
144    }
145}
146
147/// Processes `discovered` items, possibly spawning work in other threads as needed.
148#[inline]
149pub fn style_trees<'a, 'scope, E, D>(
150    context: &mut StyleContext<E>,
151    mut discovered: VecDeque<SendNode<E::ConcreteNode>>,
152    traversal_root: OpaqueNode,
153    work_unit_max: usize,
154    mut traversal_data: PerLevelTraversalData,
155    scope: Option<&'a rayon::ScopeFifo<'scope>>,
156    traversal: &'scope D,
157    tls: &'scope ScopedTLS<'scope, ThreadLocalStyleContext<E>>,
158) where
159    E: TElement + 'scope,
160    D: DomTraversal<E>,
161{
162    let local_queue_size = if tls.current_thread_index() == 0 {
163        static_prefs::pref!("layout.css.stylo-local-work-queue.in-main-thread")
164    } else {
165        static_prefs::pref!("layout.css.stylo-local-work-queue.in-worker")
166    } as usize;
167
168    let mut nodes_remaining_at_current_depth = discovered.len();
169    while let Some(node) = discovered.pop_front() {
170        let mut children_to_process = 0isize;
171        traversal.process_preorder(&traversal_data, context, *node, |n| {
172            children_to_process += 1;
173            discovered.push_back(unsafe { SendNode::new(n) });
174        });
175
176        traversal.handle_postorder_traversal(context, traversal_root, *node, children_to_process);
177
178        nodes_remaining_at_current_depth -= 1;
179
180        // If we have enough children at the next depth in the DOM, spawn them to a different job
181        // relatively soon, while keeping always at least `local_queue_size` worth of work for
182        // ourselves.
183        let discovered_children = discovered.len() - nodes_remaining_at_current_depth;
184        if discovered_children >= work_unit_max
185            && discovered.len() >= local_queue_size + work_unit_max
186            && scope.is_some()
187        {
188            let kept_work = std::cmp::max(nodes_remaining_at_current_depth, local_queue_size);
189            let mut traversal_data_copy = traversal_data.clone();
190            traversal_data_copy.current_dom_depth += 1;
191            distribute_work(
192                discovered.range(kept_work..).cloned(),
193                traversal_root,
194                work_unit_max,
195                traversal_data_copy,
196                scope.unwrap(),
197                traversal,
198                tls,
199            );
200            discovered.truncate(kept_work);
201        }
202
203        if nodes_remaining_at_current_depth == 0 {
204            traversal_data.current_dom_depth += 1;
205            nodes_remaining_at_current_depth = discovered.len();
206        }
207    }
208}
style/parallel.rs

style/
parallel.rs
