diff options
| -rw-r--r-- | components/layout/traversal.rs | 38 | ||||
| -rw-r--r-- | components/script/layout_wrapper.rs | 8 | ||||
| -rw-r--r-- | components/style/bloom.rs | 235 | ||||
| -rw-r--r-- | components/style/dom.rs | 8 | ||||
| -rw-r--r-- | components/style/lib.rs | 1 | ||||
| -rw-r--r-- | components/style/parallel.rs | 8 | ||||
| -rw-r--r-- | components/style/traversal.rs | 198 |
7 files changed, 321 insertions, 175 deletions
diff --git a/components/layout/traversal.rs b/components/layout/traversal.rs index 478299a62d6..d1701448988 100644 --- a/components/layout/traversal.rs +++ b/components/layout/traversal.rs @@ -18,9 +18,7 @@ use style::data::ElementData; use style::dom::{StylingMode, TElement, TNode}; use style::selector_parser::RestyleDamage; use style::servo::restyle_damage::{BUBBLE_ISIZES, REFLOW, REFLOW_OUT_OF_FLOW, REPAINT}; -use style::traversal::{DomTraversalContext, put_thread_local_bloom_filter}; -use style::traversal::{recalc_style_at, remove_from_bloom_filter}; -use style::traversal::take_thread_local_bloom_filter; +use style::traversal::{DomTraversalContext, recalc_style_at, remove_from_bloom_filter}; use util::opts; use wrapper::{GetRawData, LayoutNodeHelpers, LayoutNodeLayoutData}; @@ -79,32 +77,12 @@ impl<'lc, N> DomTraversalContext<N> for RecalcStyleAndConstructFlows<'lc> // done by the HTML parser. node.initialize_data(); - if node.is_text_node() { - // FIXME(bholley): Stop doing this silly work to maintain broken bloom filter - // invariants. - // - // Longer version: The bloom filter is entirely busted for parallel traversal. Because - // parallel traversal is breadth-first, each sibling rejects the bloom filter set up - // by the previous sibling (which is valid for children, not siblings) and recreates - // it. Similarly, the fixup performed in the bottom-up traversal is useless, because - // threads perform flow construction up the parent chain until they find a parent with - // other unprocessed children, at which point they bail to the work queue and find a - // different node. - // - // Nevertheless, the remove_from_bloom_filter call at the end of flow construction - // asserts that the bloom filter is valid for the current node. This breaks when we - // stop calling recalc_style_at for text nodes, because the recursive chain of - // construct_flows_at calls is no longer necessarily rooted in a call that sets up the - // thread-local bloom filter for the leaf node. - // - // The bloom filter stuff is all going to be rewritten, so we just hackily duplicate - // the bloom filter manipulation from recalc_style_at to maintain invariants. - let parent = node.parent_node().unwrap().as_element(); - let bf = take_thread_local_bloom_filter(parent, self.root, self.context.shared_context()); - put_thread_local_bloom_filter(bf, &node.to_unsafe(), self.context.shared_context()); - } else { + // FIXME(emilio): Get it! + let traversal_depth = None; + + if !node.is_text_node() { let el = node.as_element().unwrap(); - recalc_style_at::<_, _, Self>(&self.context, self.root, el); + recalc_style_at::<_, _, Self>(&self.context, traversal_depth, el); } } @@ -174,9 +152,9 @@ fn construct_flows_at<'a, N: LayoutNode>(context: &'a LayoutContext<'a>, root: O if let Some(el) = node.as_element() { el.mutate_data().unwrap().persist(); unsafe { el.unset_dirty_descendants(); } - } - remove_from_bloom_filter(context, root, node); + remove_from_bloom_filter(context, root, el); + } } /// The bubble-inline-sizes traversal, the first part of layout computation. This computes diff --git a/components/script/layout_wrapper.rs b/components/script/layout_wrapper.rs index a386d5c8563..8838787defc 100644 --- a/components/script/layout_wrapper.rs +++ b/components/script/layout_wrapper.rs @@ -175,14 +175,6 @@ impl<'ln> TNode for ServoLayoutNode<'ln> { unsafe { self.get_jsmanaged().opaque() } } - fn layout_parent_element(self, reflow_root: OpaqueNode) -> Option<ServoLayoutElement<'ln>> { - if self.opaque() == reflow_root { - None - } else { - self.parent_node().and_then(|x| x.as_element()) - } - } - fn debug_id(self) -> usize { self.opaque().0 } diff --git a/components/style/bloom.rs b/components/style/bloom.rs new file mode 100644 index 00000000000..937c8788728 --- /dev/null +++ b/components/style/bloom.rs @@ -0,0 +1,235 @@ +/* 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/. */ + +//! The style bloom filter is used as an optimization when matching deep +//! descendant selectors. + +use dom::{TNode, TElement, UnsafeNode}; +use matching::MatchMethods; +use selectors::bloom::BloomFilter; + +pub struct StyleBloom { + /// The bloom filter per se. + filter: Box<BloomFilter>, + + /// The stack of elements that this bloom filter contains. These unsafe + /// nodes are guaranteed to be elements. + /// + /// Note that the use we do for them is safe, since the data we access from + /// them is completely read-only during restyling. + elements: Vec<UnsafeNode>, + + /// A monotonic counter incremented which each reflow in order to invalidate + /// the bloom filter if appropriate. + generation: u32, +} + +impl StyleBloom { + pub fn new(generation: u32) -> Self { + StyleBloom { + filter: Box::new(BloomFilter::new()), + elements: vec![], + generation: generation, + } + } + + pub fn filter(&self) -> &BloomFilter { + &*self.filter + } + + pub fn generation(&self) -> u32 { + self.generation + } + + pub fn maybe_pop<E>(&mut self, element: E) + where E: TElement + MatchMethods + { + if self.elements.last() == Some(&element.as_node().to_unsafe()) { + self.pop::<E>().unwrap(); + } + } + + /// Push an element to the bloom filter, knowing that it's a child of the + /// last element parent. + pub fn push<E>(&mut self, element: E) + where E: TElement + MatchMethods, + { + if cfg!(debug_assertions) { + if self.elements.is_empty() { + assert!(element.parent_element().is_none()); + } + } + element.insert_into_bloom_filter(&mut *self.filter); + self.elements.push(element.as_node().to_unsafe()); + } + + /// Pop the last element in the bloom filter and return it. + fn pop<E>(&mut self) -> Option<E> + where E: TElement + MatchMethods, + { + let popped = + self.elements.pop().map(|unsafe_node| { + let parent = unsafe { + E::ConcreteNode::from_unsafe(&unsafe_node) + }; + parent.as_element().unwrap() + }); + if let Some(popped) = popped { + popped.remove_from_bloom_filter(&mut self.filter); + } + + popped + } + + fn clear(&mut self) { + self.filter.clear(); + self.elements.clear(); + } + + fn rebuild<E>(&mut self, mut element: E) -> usize + where E: TElement + MatchMethods, + { + self.clear(); + + while let Some(parent) = element.parent_element() { + parent.insert_into_bloom_filter(&mut *self.filter); + self.elements.push(parent.as_node().to_unsafe()); + element = parent; + } + + // Put them in the order we expect, from root to `element`'s parent. + self.elements.reverse(); + return self.elements.len(); + } + + /// In debug builds, asserts that all the parents of `element` are in the + /// bloom filter. + pub fn assert_complete<E>(&self, mut element: E) + where E: TElement, + { + if cfg!(debug_assertions) { + let mut checked = 0; + while let Some(parent) = element.parent_element() { + assert_eq!(parent.as_node().to_unsafe(), + self.elements[self.elements.len() - 1 - checked]); + element = parent; + checked += 1; + } + assert_eq!(checked, self.elements.len()); + } + } + + /// Insert the parents of an element in the bloom filter, trying to recover + /// the filter if the last element inserted doesn't match. + /// + /// Gets the element depth in the dom, to make it efficient, or if not + /// provided always rebuilds the filter from scratch. + /// + /// Returns the new bloom filter depth. + pub fn insert_parents_recovering<E>(&mut self, + element: E, + element_depth: Option<usize>, + generation: u32) + -> usize + where E: TElement, + { + // Easy case, we're in a different restyle, or we're empty. + if self.generation != generation || self.elements.is_empty() { + self.generation = generation; + return self.rebuild(element); + } + + let parent_element = match element.parent_element() { + Some(parent) => parent, + None => { + // Yay, another easy case. + self.clear(); + return 0; + } + }; + + let unsafe_parent = parent_element.as_node().to_unsafe(); + if self.elements.last() == Some(&unsafe_parent) { + // Ta da, cache hit, we're all done. + return self.elements.len(); + } + + let element_depth = match element_depth { + Some(depth) => depth, + // If we don't know the depth of `element`, we'd rather don't try + // fixing up the bloom filter, since it's quadratic. + None => { + return self.rebuild(element); + } + }; + + // We should've early exited above. + debug_assert!(element_depth != 0, + "We should have already cleared the bloom filter"); + debug_assert!(!self.elements.is_empty(), + "How! We should've just rebuilt!"); + + // Now the fun begins: We have the depth of the dom and the depth of the + // last element inserted in the filter, let's try to find a common + // parent. + // + // The current depth, that is, the depth of the last element inserted in + // the bloom filter, is the number of elements _minus one_, that is: if + // there's one element, it must be the root -> depth zero. + let mut current_depth = self.elements.len() - 1; + + // If the filter represents an element too deep in the dom, we need to + // pop ancestors. + while current_depth >= element_depth - 1 { + self.pop::<E>().expect("Emilio is bad at math"); + current_depth -= 1; + } + + // Now let's try to find a common parent in the bloom filter chain, + // starting with parent_element. + let mut common_parent = parent_element; + let mut common_parent_depth = element_depth - 1; + + // Let's collect the parents we are going to need to insert once we've + // found the common one. + let mut parents_to_insert = vec![]; + + // If the bloom filter still doesn't have enough elements, the common + // parent is up in the dom. + while common_parent_depth > current_depth { + // TODO(emilio): Seems like we could insert parents here, then + // reverse the slice. + parents_to_insert.push(common_parent); + common_parent = + common_parent.parent_element().expect("We were lied"); + common_parent_depth -= 1; + } + + // Now the two depths are the same. + debug_assert_eq!(common_parent_depth, current_depth); + + // Happy case: The parents match, we only need to push the ancestors + // we've collected and we'll never enter in this loop. + // + // Not-so-happy case: Parent's don't match, so we need to keep going up + // until we find a common ancestor. + while *self.elements.last().unwrap() != common_parent.as_node().to_unsafe() { + parents_to_insert.push(common_parent); + common_parent = + common_parent.parent_element().expect("We were lied again?"); + self.pop::<E>().unwrap(); + } + + // Now the parents match, so insert the stack of elements we have been + // collecting so far. + for parent in parents_to_insert.into_iter().rev() { + self.push(parent); + } + + debug_assert_eq!(self.elements.len(), element_depth); + + // We're done! Easy. + return self.elements.len(); + } +} diff --git a/components/style/dom.rs b/components/style/dom.rs index c2874dee172..da476cedbaf 100644 --- a/components/style/dom.rs +++ b/components/style/dom.rs @@ -122,12 +122,8 @@ pub trait TNode : Sized + Copy + Clone + NodeInfo { /// Converts self into an `OpaqueNode`. fn opaque(&self) -> OpaqueNode; - fn layout_parent_element(self, reflow_root: OpaqueNode) -> Option<Self::ConcreteElement> { - if self.opaque() == reflow_root { - None - } else { - self.parent_node().and_then(|n| n.as_element()) - } + fn parent_element(&self) -> Option<Self::ConcreteElement> { + self.parent_node().and_then(|n| n.as_element()) } fn debug_id(self) -> usize; diff --git a/components/style/lib.rs b/components/style/lib.rs index 68a8ef46d40..0955a651105 100644 --- a/components/style/lib.rs +++ b/components/style/lib.rs @@ -92,6 +92,7 @@ pub mod animation; pub mod atomic_refcell; pub mod attr; pub mod bezier; +pub mod bloom; pub mod cache; pub mod cascade_info; pub mod context; diff --git a/components/style/parallel.rs b/components/style/parallel.rs index 1017e5fd900..8ef1b42a17d 100644 --- a/components/style/parallel.rs +++ b/components/style/parallel.rs @@ -125,8 +125,12 @@ fn bottom_up_dom<N, C>(root: OpaqueNode, // Perform the appropriate operation. context.process_postorder(node); - let parent = match node.layout_parent_element(root) { - None => break, + if node.opaque() == root { + break; + } + + let parent = match node.parent_element() { + None => unreachable!("How can this happen after the break above?"), Some(parent) => parent, }; diff --git a/components/style/traversal.rs b/components/style/traversal.rs index ca76f167541..9d3f15a5895 100644 --- a/components/style/traversal.rs +++ b/components/style/traversal.rs @@ -5,17 +5,16 @@ //! Traversing the DOM tree; the bloom filter. use atomic_refcell::{AtomicRefCell, AtomicRefMut}; +use bloom::StyleBloom; use context::{LocalStyleContext, SharedStyleContext, StyleContext}; use data::{ElementData, RestyleData, StoredRestyleHint}; -use dom::{OpaqueNode, StylingMode, TElement, TNode, UnsafeNode}; +use dom::{OpaqueNode, StylingMode, TElement, TNode}; use matching::{MatchMethods, StyleSharingResult}; use restyle_hints::{RESTYLE_DESCENDANTS, RESTYLE_LATER_SIBLINGS, RESTYLE_SELF}; -use selectors::bloom::BloomFilter; use selectors::matching::StyleRelations; use std::cell::RefCell; use std::marker::PhantomData; use std::sync::atomic::{AtomicUsize, ATOMIC_USIZE_INIT, Ordering}; -use tid::tid; use util::opts; /// Every time we do another layout, the old bloom filters are invalid. This is @@ -27,125 +26,68 @@ pub type Generation = u32; pub static STYLE_SHARING_CACHE_HITS: AtomicUsize = ATOMIC_USIZE_INIT; pub static STYLE_SHARING_CACHE_MISSES: AtomicUsize = ATOMIC_USIZE_INIT; -/// A pair of the bloom filter used for css selector matching, and the node to -/// which it applies. This is used to efficiently do `Descendant` selector -/// matches. Thanks to the bloom filter, we can avoid walking up the tree -/// looking for ancestors that aren't there in the majority of cases. -/// -/// As we walk down the DOM tree a thread-local bloom filter is built of all the -/// CSS `SimpleSelector`s which are part of a `Descendant` compound selector -/// (i.e. paired with a `Descendant` combinator, in the `next` field of a -/// `CompoundSelector`. -/// -/// Before a `Descendant` selector match is tried, it's compared against the -/// bloom filter. If the bloom filter can exclude it, the selector is quickly -/// rejected. -/// -/// When done styling a node, all selectors previously inserted into the filter -/// are removed. -/// -/// Since a work-stealing queue is used for styling, sometimes, the bloom filter -/// will no longer be the for the parent of the node we're currently on. When -/// this happens, the thread local bloom filter will be thrown away and rebuilt. thread_local!( - static STYLE_BLOOM: RefCell<Option<(Box<BloomFilter>, UnsafeNode, Generation)>> = RefCell::new(None)); + static STYLE_BLOOM: RefCell<Option<StyleBloom>> = RefCell::new(None)); /// Returns the thread local bloom filter. /// /// If one does not exist, a new one will be made for you. If it is out of date, /// it will be cleared and reused. -pub fn take_thread_local_bloom_filter<E>(parent_element: Option<E>, - root: OpaqueNode, - context: &SharedStyleContext) - -> Box<BloomFilter> - where E: TElement { +pub fn take_thread_local_bloom_filter(context: &SharedStyleContext) + -> StyleBloom +{ + debug!("{} taking bf", ::tid::tid()); + STYLE_BLOOM.with(|style_bloom| { - match (parent_element, style_bloom.borrow_mut().take()) { - // Root node. Needs new bloom filter. - (None, _ ) => { - debug!("[{}] No parent, but new bloom filter!", tid()); - Box::new(BloomFilter::new()) - } - // No bloom filter for this thread yet. - (Some(parent), None) => { - let mut bloom_filter = Box::new(BloomFilter::new()); - insert_ancestors_into_bloom_filter(&mut bloom_filter, parent, root); - bloom_filter - } - // Found cached bloom filter. - (Some(parent), Some((mut bloom_filter, old_node, old_generation))) => { - if old_node == parent.as_node().to_unsafe() && - old_generation == context.generation { - // Hey, the cached parent is our parent! We can reuse the bloom filter. - debug!("[{}] Parent matches (={}). Reusing bloom filter.", tid(), old_node.0); - } else { - // Oh no. the cached parent is stale. I guess we need a new one. Reuse the existing - // allocation to avoid malloc churn. - bloom_filter.clear(); - insert_ancestors_into_bloom_filter(&mut bloom_filter, parent, root); - } - bloom_filter - }, - } + style_bloom.borrow_mut().take() + .unwrap_or_else(|| StyleBloom::new(context.generation)) }) } -pub fn put_thread_local_bloom_filter(bf: Box<BloomFilter>, unsafe_node: &UnsafeNode, - context: &SharedStyleContext) { +pub fn put_thread_local_bloom_filter(bf: StyleBloom) { + debug!("[{}] putting bloom filter back", ::tid::tid()); + STYLE_BLOOM.with(move |style_bloom| { - assert!(style_bloom.borrow().is_none(), - "Putting into a never-taken thread-local bloom filter"); - *style_bloom.borrow_mut() = Some((bf, *unsafe_node, context.generation)); + debug_assert!(style_bloom.borrow().is_none(), + "Putting into a never-taken thread-local bloom filter"); + *style_bloom.borrow_mut() = Some(bf); }) } -/// "Ancestors" in this context is inclusive of ourselves. -fn insert_ancestors_into_bloom_filter<E>(bf: &mut Box<BloomFilter>, - mut el: E, - root: OpaqueNode) - where E: TElement { - debug!("[{}] Inserting ancestors.", tid()); - let mut ancestors = 0; - loop { - ancestors += 1; - - el.insert_into_bloom_filter(&mut **bf); - el = match el.layout_parent_element(root) { - None => break, - Some(p) => p, - }; - } - debug!("[{}] Inserted {} ancestors.", tid(), ancestors); -} - -pub fn remove_from_bloom_filter<'a, N, C>(context: &C, root: OpaqueNode, node: N) - where N: TNode, +/// Remove `element` from the bloom filter if it's the last element we inserted. +/// +/// Restores the bloom filter if this is not the root of the reflow. +/// +/// This is mostly useful for sequential traversal, where the element will +/// always be the last one. +pub fn remove_from_bloom_filter<'a, E, C>(context: &C, root: OpaqueNode, element: E) + where E: TElement, C: StyleContext<'a> { - let unsafe_layout_node = node.to_unsafe(); - - let (mut bf, old_node, old_generation) = - STYLE_BLOOM.with(|style_bloom| { - style_bloom.borrow_mut() - .take() - .expect("The bloom filter should have been set by style recalc.") - }); - - assert_eq!(old_node, unsafe_layout_node); - assert_eq!(old_generation, context.shared_context().generation); - - match node.layout_parent_element(root) { - None => { - debug!("[{}] - {:X}, and deleting BF.", tid(), unsafe_layout_node.0); - // If this is the reflow root, eat the thread-local bloom filter. + debug!("[{}] remove_from_bloom_filter", ::tid::tid()); + + // We may have arrived to `reconstruct_flows` without entering in style + // recalc at all due to our optimizations, nor that it's up to date, so we + // can't ensure there's a bloom filter at all. + let bf = STYLE_BLOOM.with(|style_bloom| { + style_bloom.borrow_mut().take() + }); + + if let Some(mut bf) = bf { + if context.shared_context().generation == bf.generation() { + bf.maybe_pop(element); + + // If we're the root of the reflow, just get rid of the bloom + // filter. + // + // FIXME: We might want to just leave it in TLS? You don't do 4k + // allocations every day. Also, this just clears one thread's bloom + // filter, which is... not great? + if element.as_node().opaque() != root { + put_thread_local_bloom_filter(bf); + } } - Some(parent) => { - // Otherwise, put it back, but remove this node. - node.as_element().map(|x| x.remove_from_bloom_filter(&mut *bf)); - let unsafe_parent = parent.as_node().to_unsafe(); - put_thread_local_bloom_filter(bf, &unsafe_parent, &context.shared_context()); - }, - }; + } } pub trait DomTraversalContext<N: TNode> { @@ -258,27 +200,19 @@ pub fn style_element_in_display_none_subtree<'a, E, C, F>(element: E, #[inline] #[allow(unsafe_code)] pub fn recalc_style_at<'a, E, C, D>(context: &'a C, - root: OpaqueNode, + dom_depth: Option<usize>, element: E) where E: TElement, C: StyleContext<'a>, D: DomTraversalContext<E::ConcreteNode> { - // Get the style bloom filter. - // - // FIXME(bholley): We need to do these even in the StylingMode::Stop case - // to handshake with the unconditional pop during servo's bottom-up - // traversal. We should avoid doing work here in the Stop case when we - // redesign the bloom filter. - let mut bf = take_thread_local_bloom_filter(element.parent_element(), root, context.shared_context()); - let mode = element.styling_mode(); let should_compute = element.borrow_data().map_or(true, |d| d.get_current_styles().is_none()); debug!("recalc_style_at: {:?} (should_compute={:?} mode={:?}, data={:?})", element, should_compute, mode, element.borrow_data()); let (computed_display_none, propagated_hint) = if should_compute { - compute_style::<_, _, D>(context, element, &*bf) + compute_style::<_, _, D>(context, dom_depth, element) } else { (false, StoredRestyleHint::empty()) }; @@ -294,25 +228,24 @@ pub fn recalc_style_at<'a, E, C, D>(context: &'a C, preprocess_children::<_, _, D>(context, element, propagated_hint, mode == StylingMode::Restyle); } - - let unsafe_layout_node = element.as_node().to_unsafe(); - - // Before running the children, we need to insert our nodes into the bloom - // filter. - debug!("[{}] + {:X}", tid(), unsafe_layout_node.0); - element.insert_into_bloom_filter(&mut *bf); - - // NB: flow construction updates the bloom filter on the way up. - put_thread_local_bloom_filter(bf, &unsafe_layout_node, context.shared_context()); } fn compute_style<'a, E, C, D>(context: &'a C, - element: E, - bloom_filter: &BloomFilter) -> (bool, StoredRestyleHint) + dom_depth: Option<usize>, + element: E) -> (bool, StoredRestyleHint) where E: TElement, C: StyleContext<'a>, D: DomTraversalContext<E::ConcreteNode> { + let shared_context = context.shared_context(); + let mut bf = take_thread_local_bloom_filter(shared_context); + + // Ensure the bloom filter is up to date. + bf.insert_parents_recovering(element, + dom_depth, + shared_context.generation); + bf.assert_complete(element); + let mut data = unsafe { D::ensure_element_data(&element).borrow_mut() }; debug_assert!(!data.is_persistent()); @@ -324,7 +257,7 @@ fn compute_style<'a, E, C, D>(context: &'a C, StyleSharingResult::CannotShare } else { unsafe { element.share_style_if_possible(style_sharing_candidate_cache, - context.shared_context(), &mut data) } + shared_context, &mut data) } }; // Otherwise, match and cascade selectors. @@ -337,7 +270,7 @@ fn compute_style<'a, E, C, D>(context: &'a C, } // Perform the CSS selector matching. - match_results = element.match_element(context, Some(bloom_filter)); + match_results = element.match_element(context, Some(bf.filter())); if match_results.primary_is_shareable() { Some(element) } else { @@ -379,6 +312,13 @@ fn compute_style<'a, E, C, D>(context: &'a C, clear_descendant_data(element, &|e| unsafe { D::clear_element_data(&e) }); } + // TODO(emilio): It's pointless to insert the element in the parallel + // traversal, but it may be worth todo it for sequential restyling. What we + // do now is trying to recover it which in that case is really cheap, so + // we'd save a few instructions, but probably not worth given the added + // complexity. + put_thread_local_bloom_filter(bf); + (display_none, data.as_restyle().map_or(StoredRestyleHint::empty(), |r| r.hint.propagate())) } |