diff options
| -rw-r--r-- | components/layout/layout_task.rs | 3 | ||||
| -rw-r--r-- | components/layout/parallel.rs | 132 | ||||
| -rw-r--r-- | components/style/lib.rs | 1 | ||||
| -rw-r--r-- | components/style/parallel.rs | 142 |
4 files changed, 148 insertions, 130 deletions
diff --git a/components/layout/layout_task.rs b/components/layout/layout_task.rs index 0015cd3fc33..1eac2e78fc1 100644 --- a/components/layout/layout_task.rs +++ b/components/layout/layout_task.rs @@ -38,7 +38,7 @@ use msg::ParseErrorReporter; use msg::compositor_msg::Epoch; use msg::constellation_msg::{ConstellationChan, Failure, PipelineId}; use net_traits::image_cache_task::{ImageCacheChan, ImageCacheResult, ImageCacheTask}; -use parallel::{self, WorkQueueData}; +use parallel; use profile_traits::mem::{self, Report, ReportKind, ReportsChan}; use profile_traits::time::{TimerMetadataFrameType, TimerMetadataReflowType}; use profile_traits::time::{self, TimerMetadata, profile}; @@ -67,6 +67,7 @@ use style::computed_values::{filter, mix_blend_mode}; use style::context::{SharedStyleContext, StylistWrapper}; use style::dom::{TDocument, TElement, TNode}; use style::media_queries::{Device, MediaType}; +use style::parallel::WorkQueueData; use style::selector_matching::{Stylist, USER_OR_USER_AGENT_STYLESHEETS}; use style::stylesheets::{CSSRuleIteratorExt, Stylesheet}; use traversal::RecalcStyleAndConstructFlows; diff --git a/components/layout/parallel.rs b/components/layout/parallel.rs index 3e63f4ae8bf..f5f2eb30856 100644 --- a/components/layout/parallel.rs +++ b/components/layout/parallel.rs @@ -11,26 +11,23 @@ use context::{LayoutContext, SharedLayoutContext}; use flow::{self, Flow, MutableFlowUtils, PostorderFlowTraversal, PreorderFlowTraversal}; use flow_ref::{self, FlowRef}; -use gfx::display_list::OpaqueNode; use profile_traits::time::{self, TimerMetadata, profile}; use std::mem; use std::sync::atomic::{AtomicIsize, Ordering}; use style::dom::{TNode, UnsafeNode}; -use style::traversal::DomTraversalContext; +use style::parallel::{CHUNK_SIZE, WorkQueueData}; +use style::parallel::{run_queue_with_custom_work_data_type}; use traversal::{AssignBSizesAndStoreOverflow, AssignISizes, BubbleISizes}; use traversal::{BuildDisplayList, ComputeAbsolutePositions, PostorderNodeMutTraversal}; use util::opts; use util::workqueue::{WorkQueue, WorkUnit, WorkerProxy}; -const CHUNK_SIZE: usize = 64; - -pub struct WorkQueueData(usize, usize); +pub use style::parallel::traverse_dom_preorder; #[allow(dead_code)] fn static_assertion(node: UnsafeNode) { unsafe { let _: UnsafeFlow = ::std::intrinsics::transmute(node); - let _: UnsafeNodeList = ::std::intrinsics::transmute(node); } } @@ -53,18 +50,8 @@ pub fn borrowed_flow_to_unsafe_flow(flow: &Flow) -> UnsafeFlow { } } -pub type UnsafeNodeList = (Box<Vec<UnsafeNode>>, OpaqueNode); - pub type UnsafeFlowList = (Box<Vec<UnsafeNode>>, usize); -pub type ChunkedDomTraversalFunction = - extern "Rust" fn(UnsafeNodeList, - &mut WorkerProxy<SharedLayoutContext, UnsafeNodeList>); - -pub type DomTraversalFunction = - extern "Rust" fn(OpaqueNode, UnsafeNode, - &mut WorkerProxy<SharedLayoutContext, UnsafeNodeList>); - pub type ChunkedFlowTraversalFunction = extern "Rust" fn(UnsafeFlowList, &mut WorkerProxy<SharedLayoutContext, UnsafeFlowList>); @@ -230,94 +217,6 @@ impl<'a> ParallelPreorderFlowTraversal for ComputeAbsolutePositions<'a> { impl<'a> ParallelPostorderFlowTraversal for BuildDisplayList<'a> {} -/// A parallel top-down DOM traversal. -#[inline(always)] -fn top_down_dom<'ln, N, C>(unsafe_nodes: UnsafeNodeList, - proxy: &mut WorkerProxy<C::SharedContext, UnsafeNodeList>) - where N: TNode<'ln>, C: DomTraversalContext<'ln, N> { - let context = C::new(proxy.user_data(), unsafe_nodes.1); - - let mut discovered_child_nodes = Vec::new(); - for unsafe_node in *unsafe_nodes.0 { - // Get a real layout node. - let node = unsafe { N::from_unsafe(&unsafe_node) }; - - // Perform the appropriate traversal. - context.process_preorder(node); - - let child_count = node.children_count(); - - // Reset the count of children. - { - let data = node.mutate_data().unwrap(); - data.parallel.children_count.store(child_count as isize, - Ordering::Relaxed); - } - - // Possibly enqueue the children. - if child_count != 0 { - for kid in node.children() { - discovered_child_nodes.push(kid.to_unsafe()) - } - } else { - // If there were no more children, start walking back up. - bottom_up_dom::<N, C>(unsafe_nodes.1, unsafe_node, proxy) - } - } - - for chunk in discovered_child_nodes.chunks(CHUNK_SIZE) { - proxy.push(WorkUnit { - fun: top_down_dom::<N, C>, - data: (box chunk.iter().cloned().collect(), unsafe_nodes.1), - }); - } -} - -/// Process current node 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 bottom_up_dom<'ln, N, C>(root: OpaqueNode, - unsafe_node: UnsafeNode, - proxy: &mut WorkerProxy<C::SharedContext, UnsafeNodeList>) - where N: TNode<'ln>, C: DomTraversalContext<'ln, N> { - let context = C::new(proxy.user_data(), root); - - // Get a real layout node. - let mut node = unsafe { N::from_unsafe(&unsafe_node) }; - loop { - // Perform the appropriate operation. - context.process_postorder(node); - - let parent = match node.layout_parent_node(root) { - None => break, - Some(parent) => parent, - }; - - let parent_data = unsafe { - &*parent.borrow_data_unchecked().unwrap() - }; - - if parent_data - .parallel - .children_count - .fetch_sub(1, Ordering::Relaxed) != 1 { - // Get out of here and find another node to work on. - break - } - - // We were the last child of our parent. Construct flows for our parent. - node = parent; - } -} - fn assign_inline_sizes(unsafe_flows: UnsafeFlowList, proxy: &mut WorkerProxy<SharedLayoutContext, UnsafeFlowList>) { let shared_layout_context = proxy.user_data(); @@ -360,31 +259,6 @@ fn build_display_list(unsafe_flow: UnsafeFlow, build_display_list_traversal.run_parallel(unsafe_flow); } -fn run_queue_with_custom_work_data_type<To, F, SharedContext: Sync>( - queue: &mut WorkQueue<SharedContext, WorkQueueData>, - callback: F, - shared: &SharedContext) - where To: 'static + Send, F: FnOnce(&mut WorkQueue<SharedContext, To>) { - let queue: &mut WorkQueue<SharedContext, To> = unsafe { - mem::transmute(queue) - }; - callback(queue); - queue.run(shared); -} - -pub fn traverse_dom_preorder<'ln, N, C>( - root: N, - queue_data: &C::SharedContext, - queue: &mut WorkQueue<C::SharedContext, WorkQueueData>) - where N: TNode<'ln>, C: DomTraversalContext<'ln, N> { - run_queue_with_custom_work_data_type(queue, |queue| { - queue.push(WorkUnit { - fun: top_down_dom::<N, C>, - data: (box vec![root.to_unsafe()], root.opaque()), - }); - }, queue_data); -} - pub fn traverse_flow_tree_preorder( root: &mut FlowRef, profiler_metadata: Option<TimerMetadata>, diff --git a/components/style/lib.rs b/components/style/lib.rs index 18c43638cfb..5623c5bd8ed 100644 --- a/components/style/lib.rs +++ b/components/style/lib.rs @@ -53,6 +53,7 @@ pub mod dom; pub mod font_face; pub mod matching; pub mod media_queries; +pub mod parallel; pub mod parser; pub mod restyle_hints; pub mod selector_matching; diff --git a/components/style/parallel.rs b/components/style/parallel.rs new file mode 100644 index 00000000000..de0ae680e3a --- /dev/null +++ b/components/style/parallel.rs @@ -0,0 +1,142 @@ +/* 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 traversal over the DOM tree. +//! +//! This code is highly unsafe. Keep this file small and easy to audit. + +#![allow(unsafe_code)] + +use dom::{OpaqueNode, TNode, UnsafeNode}; +use std::mem; +use std::sync::atomic::Ordering; +use traversal::DomTraversalContext; +use util::workqueue::{WorkQueue, WorkUnit, WorkerProxy}; + +#[allow(dead_code)] +fn static_assertion(node: UnsafeNode) { + unsafe { + let _: UnsafeNodeList = ::std::intrinsics::transmute(node); + } +} + +pub type UnsafeNodeList = (Box<Vec<UnsafeNode>>, OpaqueNode); + +pub const CHUNK_SIZE: usize = 64; + +pub struct WorkQueueData(usize, usize); + +pub fn run_queue_with_custom_work_data_type<To, F, SharedContext: Sync>( + queue: &mut WorkQueue<SharedContext, WorkQueueData>, + callback: F, + shared: &SharedContext) + where To: 'static + Send, F: FnOnce(&mut WorkQueue<SharedContext, To>) { + let queue: &mut WorkQueue<SharedContext, To> = unsafe { + mem::transmute(queue) + }; + callback(queue); + queue.run(shared); +} + +pub fn traverse_dom_preorder<'ln, N, C>( + root: N, + queue_data: &C::SharedContext, + queue: &mut WorkQueue<C::SharedContext, WorkQueueData>) + where N: TNode<'ln>, C: DomTraversalContext<'ln, N> { + run_queue_with_custom_work_data_type(queue, |queue| { + queue.push(WorkUnit { + fun: top_down_dom::<N, C>, + data: (box vec![root.to_unsafe()], root.opaque()), + }); + }, queue_data); +} + +/// A parallel top-down DOM traversal. +#[inline(always)] +fn top_down_dom<'ln, N, C>(unsafe_nodes: UnsafeNodeList, + proxy: &mut WorkerProxy<C::SharedContext, UnsafeNodeList>) + where N: TNode<'ln>, C: DomTraversalContext<'ln, N> { + let context = C::new(proxy.user_data(), unsafe_nodes.1); + + let mut discovered_child_nodes = Vec::new(); + for unsafe_node in *unsafe_nodes.0 { + // Get a real layout node. + let node = unsafe { N::from_unsafe(&unsafe_node) }; + + // Perform the appropriate traversal. + context.process_preorder(node); + + let child_count = node.children_count(); + + // Reset the count of children. + { + let data = node.mutate_data().unwrap(); + data.parallel.children_count.store(child_count as isize, + Ordering::Relaxed); + } + + // Possibly enqueue the children. + if child_count != 0 { + for kid in node.children() { + discovered_child_nodes.push(kid.to_unsafe()) + } + } else { + // If there were no more children, start walking back up. + bottom_up_dom::<N, C>(unsafe_nodes.1, unsafe_node, proxy) + } + } + + for chunk in discovered_child_nodes.chunks(CHUNK_SIZE) { + proxy.push(WorkUnit { + fun: top_down_dom::<N, C>, + data: (box chunk.iter().cloned().collect(), unsafe_nodes.1), + }); + } +} + +/// Process current node 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 bottom_up_dom<'ln, N, C>(root: OpaqueNode, + unsafe_node: UnsafeNode, + proxy: &mut WorkerProxy<C::SharedContext, UnsafeNodeList>) + where N: TNode<'ln>, C: DomTraversalContext<'ln, N> { + let context = C::new(proxy.user_data(), root); + + // Get a real layout node. + let mut node = unsafe { N::from_unsafe(&unsafe_node) }; + loop { + // Perform the appropriate operation. + context.process_postorder(node); + + let parent = match node.layout_parent_node(root) { + None => break, + Some(parent) => parent, + }; + + let parent_data = unsafe { + &*parent.borrow_data_unchecked().unwrap() + }; + + if parent_data + .parallel + .children_count + .fetch_sub(1, Ordering::Relaxed) != 1 { + // Get out of here and find another node to work on. + break + } + + // We were the last child of our parent. Construct flows for our parent. + node = parent; + } +} + |