1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
/* 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 traversal over the DOM tree. The traversal starts in sequential
//! mode, and optionally parallelizes as it discovers work.
#![deny(missing_docs)]
use crate::context::{PerThreadTraversalStatistics, StyleContext};
use crate::context::{ThreadLocalStyleContext, TraversalStatistics};
use crate::dom::{SendNode, TElement, TNode};
use crate::parallel;
use crate::parallel::{work_unit_max, DispatchMode};
use crate::scoped_tls::ScopedTLS;
use crate::traversal::{DomTraversal, PerLevelTraversalData, PreTraverseToken};
use rayon;
use std::collections::VecDeque;
use std::mem;
use time;
#[cfg(feature = "servo")]
fn should_report_statistics() -> bool {
false
}
#[cfg(feature = "gecko")]
fn should_report_statistics() -> bool {
unsafe { crate::gecko_bindings::structs::ServoTraversalStatistics_sActive }
}
#[cfg(feature = "servo")]
fn report_statistics(_stats: &PerThreadTraversalStatistics) {
unreachable!("Servo never report stats");
}
#[cfg(feature = "gecko")]
fn report_statistics(stats: &PerThreadTraversalStatistics) {
// This should only be called in the main thread, or it may be racy
// to update the statistics in a global variable.
debug_assert!(unsafe { crate::gecko_bindings::bindings::Gecko_IsMainThread() });
let gecko_stats =
unsafe { &mut crate::gecko_bindings::structs::ServoTraversalStatistics_sSingleton };
gecko_stats.mElementsTraversed += stats.elements_traversed;
gecko_stats.mElementsStyled += stats.elements_styled;
gecko_stats.mElementsMatched += stats.elements_matched;
gecko_stats.mStylesShared += stats.styles_shared;
gecko_stats.mStylesReused += stats.styles_reused;
}
fn parallelism_threshold() -> usize {
static_prefs::pref!("layout.css.stylo-parallelism-threshold") as usize
}
/// Do a DOM traversal for top-down and (optionally) bottom-up processing, generic over `D`.
///
/// We use an adaptive traversal strategy. We start out with simple sequential processing, until we
/// arrive at a wide enough level in the DOM that the parallel traversal would parallelize it.
/// If a thread pool is provided, we then transfer control over to the parallel traversal.
///
/// Returns true if the traversal was parallel, and also returns the statistics object containing
/// information on nodes traversed (on nightly only). Not all of its fields will be initialized
/// since we don't call finish().
pub fn traverse_dom<E, D>(
traversal: &D,
token: PreTraverseToken<E>,
pool: Option<&rayon::ThreadPool>,
) -> E
where
E: TElement,
D: DomTraversal<E>,
{
let root = token
.traversal_root()
.expect("Should've ensured we needed to traverse");
let report_stats = should_report_statistics();
let dump_stats = traversal.shared_context().options.dump_style_statistics;
let start_time = if dump_stats {
Some(time::precise_time_s())
} else {
None
};
// Declare the main-thread context, as well as the worker-thread contexts,
// which we may or may not instantiate. It's important to declare the worker-
// thread contexts first, so that they get dropped second. This matters because:
// * ThreadLocalContexts borrow AtomicRefCells in TLS.
// * Dropping a ThreadLocalContext can run SequentialTasks.
// * Sequential tasks may call into functions like
// Servo_StyleSet_GetBaseComputedValuesForElement, which instantiate a
// ThreadLocalStyleContext on the main thread. If the main thread
// ThreadLocalStyleContext has not released its TLS borrow by that point,
// we'll panic on double-borrow.
let mut tls_slots = None;
let mut tlc = ThreadLocalStyleContext::new();
let mut context = StyleContext {
shared: traversal.shared_context(),
thread_local: &mut tlc,
};
// Process the nodes breadth-first, just like the parallel traversal does.
// This helps keep similar traversal characteristics for the style sharing
// cache.
let work_unit_max = work_unit_max();
let parallelism_threshold = parallelism_threshold();
let mut discovered = VecDeque::<SendNode<E::ConcreteNode>>::with_capacity(work_unit_max * 2);
let mut depth = root.depth();
let mut nodes_remaining_at_current_depth = 1;
discovered.push_back(unsafe { SendNode::new(root.as_node()) });
while let Some(node) = discovered.pop_front() {
let mut children_to_process = 0isize;
let traversal_data = PerLevelTraversalData {
current_dom_depth: depth,
};
traversal.process_preorder(&traversal_data, &mut context, *node, |n| {
children_to_process += 1;
discovered.push_back(unsafe { SendNode::new(n) });
});
traversal.handle_postorder_traversal(
&mut context,
root.as_node().opaque(),
*node,
children_to_process,
);
nodes_remaining_at_current_depth -= 1;
// If there is enough work to parallelize over, and the caller allows parallelism, switch
// to the parallel driver. We do this only when moving to the next level in the dom so that
// we can pass the same depth for all the children.
if nodes_remaining_at_current_depth != 0 {
continue;
}
depth += 1;
if pool.is_some() && discovered.len() > parallelism_threshold && parallelism_threshold > 0 {
let pool = pool.unwrap();
let tls = ScopedTLS::<ThreadLocalStyleContext<E>>::new(pool);
let root_opaque = root.as_node().opaque();
pool.scope_fifo(|scope| {
// Enable a breadth-first rayon traversal. This causes the work
// queue to be always FIFO, rather than FIFO for stealers and
// FILO for the owner (which is what rayon does by default). This
// ensures that we process all the elements at a given depth before
// proceeding to the next depth, which is important for style sharing.
gecko_profiler_label!(Layout, StyleComputation);
parallel::traverse_nodes(
discovered.make_contiguous(),
DispatchMode::TailCall,
/* recursion_ok = */ true,
root_opaque,
PerLevelTraversalData {
current_dom_depth: depth,
},
scope,
pool,
traversal,
&tls,
);
});
tls_slots = Some(tls.into_slots());
break;
}
nodes_remaining_at_current_depth = discovered.len();
}
// Collect statistics from thread-locals if requested.
if dump_stats || report_stats {
let mut aggregate = mem::replace(&mut context.thread_local.statistics, Default::default());
let parallel = tls_slots.is_some();
if let Some(ref mut tls) = tls_slots {
for slot in tls.iter_mut() {
if let Some(cx) = slot.get_mut() {
aggregate += cx.statistics.clone();
}
}
}
if report_stats {
report_statistics(&aggregate);
}
// dump statistics to stdout if requested
if dump_stats {
let stats =
TraversalStatistics::new(aggregate, traversal, parallel, start_time.unwrap());
if stats.is_large {
println!("{}", stats);
}
}
}
root
}
|
