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
|
/* 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 http://mozilla.org/MPL/2.0/. */
//! Implements parallel traversals over the DOM and flow trees.
//!
//! This code is highly unsafe. Keep this file small and easy to audit.
#![allow(unsafe_code)]
use context::LayoutContext;
use flow::{self, Flow, MutableFlowUtils, PostorderFlowTraversal, PreorderFlowTraversal};
use flow_ref::FlowRef;
use profile_traits::time::{self, TimerMetadata, profile};
use rayon;
use servo_config::opts;
use std::mem;
use std::sync::atomic::{AtomicIsize, Ordering};
use style::dom::UnsafeNode;
use style::parallel::CHUNK_SIZE;
use traversal::{AssignISizes, BubbleISizes};
use traversal::AssignBSizes;
pub use style::parallel::traverse_dom;
#[allow(dead_code)]
fn static_assertion(node: UnsafeNode) {
unsafe {
let _: UnsafeFlow = ::std::intrinsics::transmute(node);
}
}
/// Vtable + pointer representation of a Flow trait object.
pub type UnsafeFlow = (usize, usize);
fn null_unsafe_flow() -> UnsafeFlow {
(0, 0)
}
pub fn mut_owned_flow_to_unsafe_flow(flow: *mut FlowRef) -> UnsafeFlow {
unsafe {
mem::transmute::<&Flow, UnsafeFlow>(&**flow)
}
}
pub fn borrowed_flow_to_unsafe_flow(flow: &Flow) -> UnsafeFlow {
unsafe {
mem::transmute::<&Flow, UnsafeFlow>(flow)
}
}
/// Information that we need stored in each flow.
pub struct FlowParallelInfo {
/// The number of children that still need work done.
pub children_count: AtomicIsize,
/// The address of the parent flow.
pub parent: UnsafeFlow,
}
impl FlowParallelInfo {
pub fn new() -> FlowParallelInfo {
FlowParallelInfo {
children_count: AtomicIsize::new(0),
parent: null_unsafe_flow(),
}
}
}
/// Process current flow and potentially traverse its ancestors.
///
/// If we are the last child that finished processing, recursively process
/// our parent. Else, stop. Also, stop at the root.
///
/// Thus, if we start with all the leaves of a tree, we end up traversing
/// the whole tree bottom-up because each parent will be processed exactly
/// once (by the last child that finishes processing).
///
/// The only communication between siblings is that they both
/// fetch-and-subtract the parent's children count.
fn buttom_up_flow(mut unsafe_flow: UnsafeFlow,
assign_bsize_traversal: &AssignBSizes) {
loop {
// Get a real flow.
let flow: &mut Flow = unsafe {
mem::transmute(unsafe_flow)
};
// Perform the appropriate traversal.
if assign_bsize_traversal.should_process(flow) {
assign_bsize_traversal.process(flow);
}
let base = flow::mut_base(flow);
// Reset the count of children for the next layout traversal.
base.parallel.children_count.store(base.children.len() as isize,
Ordering::Relaxed);
// Possibly enqueue the parent.
let unsafe_parent = base.parallel.parent;
if unsafe_parent == null_unsafe_flow() {
// We're done!
break
}
// No, we're not at the root yet. Then are we the last child
// of our parent to finish processing? If so, we can continue
// on with our parent; otherwise, we've gotta wait.
let parent: &mut Flow = unsafe {
mem::transmute(unsafe_parent)
};
let parent_base = flow::mut_base(parent);
if parent_base.parallel.children_count.fetch_sub(1, Ordering::Relaxed) == 1 {
// We were the last child of our parent. Reflow our parent.
unsafe_flow = unsafe_parent
} else {
// Stop.
break
}
}
}
fn top_down_flow<'scope>(unsafe_flows: &[UnsafeFlow],
scope: &rayon::Scope<'scope>,
assign_isize_traversal: &'scope AssignISizes,
assign_bsize_traversal: &'scope AssignBSizes)
{
let mut discovered_child_flows = vec![];
for unsafe_flow in unsafe_flows {
let mut had_children = false;
unsafe {
// Get a real flow.
let flow: &mut Flow = mem::transmute(*unsafe_flow);
// FIXME(emilio): With the switch to rayon we can no longer
// access a thread id from here easily. Either instrument
// rayon (the unstable feature) to get a worker thread
// identifier, or remove all the layout tinting mode.
//
// flow::mut_base(flow).thread_id = proxy.worker_index();
if assign_isize_traversal.should_process(flow) {
// Perform the appropriate traversal.
assign_isize_traversal.process(flow);
}
// Possibly enqueue the children.
for kid in flow::child_iter_mut(flow) {
had_children = true;
discovered_child_flows.push(borrowed_flow_to_unsafe_flow(kid));
}
}
// If there were no more children, start assigning block-sizes.
if !had_children {
buttom_up_flow(*unsafe_flow, &assign_bsize_traversal)
}
}
for chunk in discovered_child_flows.chunks(CHUNK_SIZE) {
let nodes = chunk.iter().cloned().collect::<Vec<_>>().into_boxed_slice();
scope.spawn(move |scope| {
top_down_flow(&nodes, scope, &assign_isize_traversal, &assign_bsize_traversal);
});
}
}
pub fn traverse_flow_tree_preorder(
root: &mut Flow,
profiler_metadata: Option<TimerMetadata>,
time_profiler_chan: time::ProfilerChan,
context: &LayoutContext,
queue: &rayon::ThreadPool) {
if opts::get().bubble_inline_sizes_separately {
let bubble_inline_sizes = BubbleISizes { layout_context: &context };
root.traverse_postorder(&bubble_inline_sizes);
}
let assign_isize_traversal = &AssignISizes { layout_context: &context };
let assign_bsize_traversal = &AssignBSizes { layout_context: &context };
let nodes = vec![borrowed_flow_to_unsafe_flow(root)].into_boxed_slice();
queue.install(move || {
rayon::scope(move |scope| {
profile(time::ProfilerCategory::LayoutParallelWarmup,
profiler_metadata, time_profiler_chan, move || {
top_down_flow(&nodes, scope, assign_isize_traversal, assign_bsize_traversal);
});
});
});
}
|
