Closed Bug 1395064 Opened 7 years ago Closed 7 years ago

stylo: Add uses of fallible Vec, SmallVec and HashMap facilities

Categories

(Core :: CSS Parsing and Computation, defect, P1)

defect

Tracking

()

RESOLVED FIXED
Tracking Status
firefox57 --- fixed

People

(Reporter: jseward, Assigned: jseward)

References

Details

Attachments

(7 files, 3 obsolete files)

Bug 1389009 and bug 1393656 add fallible versions of Vec::push,
SmalLVec::push and HashMap::insert.  Now we need to to identify big
infallible memory allocations in Stylo (potential OOM points) and change
them to use the fallible versions instead.

There's also the tricky question of how to test this stuff without actually
running machines out of memory.
Depends on: 1389009, 1393656
Stylesheet::parse_rules: add parsed rules fallibly to their containing vector.
Assignee: nobody → jseward
A simple valgrind tool (recycled version of dhat) for selectively causing
allocations to fail.  Intercepts, symbolises and filters all large
allocation stacks and can cause any specific stack to fail.
Handles allocation failures in the path

Servo_StyleSet_FlushStyleSheets
-> style::gecko::data::PerDocumentStyleDataImpl::flush_stylesheets
   -> insert<style::stylist::Rule>
      -> <hashglobe::hash_map::HashMap<K, V, S>>::entry
         -> <hashglobe::hash_map::HashMap<K, V, S>>::resize
            -> malloc

as that seems to happen frequently in bug 1390838.

With the patch in place, and testing with the tool in comment 3, the system
stays alive when loading the Obama test case and also
https://www.w3.org/TR/html5/single-page.html, when all allocations >= 16384
bytes along the abovementioned path are forced to fail.  That is in total
5128 allocation attempts.  The pages don't look right but the system stays
alive and responsive.
Attachment #8904611 - Flags: feedback?(bobbyholley)
Blocks: 1396594
Comment on attachment 8904611 [details] [diff] [review]
bug1395064-use-fallible-collections-2.diff

Review of attachment 8904611 [details] [diff] [review]:
-----------------------------------------------------------------

ISTR some discussion on the Vec of Rules within the stylesheet needing fallible allocation as well. You can probably test this on 100x myspace [1], since that has an abnormally-large stylesheet.

[1] https://www.dropbox.com/s/h51fspacftf1lcq/myspace.tar.bz2?dl=0

::: servo/components/style/selector_map.rs
@@ +250,5 @@
>                      .or_insert_with(SmallVec::new)
>              }
>              Bucket::Class(class) => {
> +                match self.class_hash.try_entry(class.clone(), quirks_mode) {
> +                    Err(_err) => return (), // We OOMd.  Give up.

Nit: You don't need the (), and can just do |return|. I'd also shorten the comment to just say // OOM

::: servo/components/style/stylist.rs
@@ +336,5 @@
>                          debug!("Found valid keyframe animation: {:?}", animation);
> +                        match origin_cascade_data.animations.try_insert(keyframes_rule.name.as_atom().clone(), animation) {
> +                            Err(_err) => return (), // We OOMd.  Give up.
> +                            Ok(_rule) => ()
> +                        }

Instead, just do:

if origin_cascade_data.animations.try_insert(keyframes_rule.name.as_atom().clone(), animation).is_err() {
  return;
}
Attachment #8904611 - Flags: feedback?(bobbyholley) → feedback+
Comment on attachment 8904611 [details] [diff] [review]
bug1395064-use-fallible-collections-2.diff

Review of attachment 8904611 [details] [diff] [review]:
-----------------------------------------------------------------

::: servo/components/style/stylist.rs
@@ +336,5 @@
>                          debug!("Found valid keyframe animation: {:?}", animation);
> +                        match origin_cascade_data.animations.try_insert(keyframes_rule.name.as_atom().clone(), animation) {
> +                            Err(_err) => return (), // We OOMd.  Give up.
> +                            Ok(_rule) => ()
> +                        }

(Or, better yet, propagate the error up so we don't try to keep inserting stuff? If we've reached OOM conditions once it seems not a big deal to just bail out from the pending rules).

Also, that'd allow to write this as:

  animations.try_insert(...)?;

Which is shorter and nicer IMO.
Comment on attachment 8904611 [details] [diff] [review]
bug1395064-use-fallible-collections-2.diff

Review of attachment 8904611 [details] [diff] [review]:
-----------------------------------------------------------------

::: servo/components/style/selector_map.rs
@@ +490,5 @@
>          self.0.entry(key)
>      }
>  
> +    /// HashMap::try_entry
> +    pub fn try_entry(&mut self, mut key: Atom, quirks_mode: QuirksMode) -> Result<hash_map::Entry<Atom, V>, FailedAllocationError> {

Is this function used anywhere?

nit: probably should wrap this before the ->
Attachment #8904611 - Flags: feedback+
* uses shorter forms where possible, per comment 6
* adds handling for Vec of Rules OOM, per comment 6
* adds handling for an OOM with a large SmallVec allocation
* impl DocumentCascadeData, add_stylesheet(): propagates failure into
  rebuild, per Emilio's suggestion in comment 7, and if rebuild
  catches it, it just returns immediately

Tested on Obama testcase, 100x myspace,
https://www.w3.org/TR/html5/single-page.html.
Attachment #8904611 - Attachment is obsolete: true
Attachment #8905484 - Flags: review?(bobbyholley)
Comment on attachment 8905484 [details] [diff] [review]
bug1395064-use-fallible-collections-3.diff

Review of attachment 8905484 [details] [diff] [review]:
-----------------------------------------------------------------

In general, I think we should bubble OOMs up more from the selector_map stuff, and handle them higher up the stack, so that we don't keep trying to allocate in low-memory situations. This will also make the APIs cleaner, since we can use the |?| operator, which means that we only need a single extra character (plus the function signature modifications) to handle allocation failure.
Attachment #8905484 - Flags: review?(bobbyholley) → review-
Ok, I can try for that.  I had assumed, perhaps unwisely, that the goal was
merely not to crash at a few specific large allocation points.  Is there a
particular function or functions that would be good places to end the
propagation chain(s) ?  I can try to find candidate(s), but if you already
have some in mind, that would be good to know.
Flags: needinfo?(bobbyholley)
For stylist flushing, let's propagate up to add_stylesheet (and have that function continue to return void). For parsing, parse_rules is probably the right place.
Flags: needinfo?(bobbyholley)
(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #12)
> For stylist flushing, let's propagate up to add_stylesheet (and have that
> function continue to return void). For parsing, parse_rules is probably the
> right place.

I think propagating it up to rebuild() is nicer. Or at the very minimum to add_stylesheet.

Otherwise, you basically keep calling add_stylesheet() with the following stylesheets, trying to allocate more and more, which is pretty bad if you're already in OOM conditions. WDYT, Bobby?
Flags: needinfo?(bobbyholley)
(In reply to Emilio Cobos Álvarez [:emilio] from comment #13)
> (In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #12)
> > For stylist flushing, let's propagate up to add_stylesheet (and have that
> > function continue to return void). For parsing, parse_rules is probably the
> > right place.
> 
> I think propagating it up to rebuild() is nicer. Or at the very minimum to
> add_stylesheet.
> 
> Otherwise, you basically keep calling add_stylesheet() with the following
> stylesheets, trying to allocate more and more, which is pretty bad if you're
> already in OOM conditions. WDYT, Bobby?

That is fine.

This bug and bug 1389009 need to move faster. We're less than 2 weeks from the merge, and since we're expecting them to fix OOM crashes, we need time for them to percolate into the Nightly population, and possibly adjust.

If time zones are an issue, please work directly with emilio for reviews. Ideally this would land within the next 24hrs. If you're not around, let me know and I will just do it.
Flags: needinfo?(bobbyholley) → needinfo?(jseward)
Respin.  Passes (cd servo && ./mach test-unit -p style) but otherwise
untested.
Attachment #8905484 - Attachment is obsolete: true
Flags: needinfo?(jseward)
Status: NEW → ASSIGNED
Attachment #8906147 - Flags: feedback?(emilio)
Comment on attachment 8906147 [details] [diff] [review]
bug1395064-use-fallible-collections-5.diff

Review of attachment 8906147 [details] [diff] [review]:
-----------------------------------------------------------------

Looks pretty reasonable over all. I think I got a place where you were not using fallible push, and I'd propagate up at least note_selector(..), and probably add_stylesheet(..) too.

The rest of comments are mostly formatting nits.

::: servo/components/fallible/lib.rs
@@ +47,4 @@
>      let old_ptr = vec.as_mut_ptr();
>      let old_len = vec.len();
>  
> +    let err_str = "capacity overflow when allocating Vec";

We can make this a `static const` or something like that, I think.

@@ +100,3 @@
>  #[inline(never)]
>  #[cold]
> +fn try_double_small_vec<T>(svec: &mut SmallVec<T>)

nit: I'd run this through rustfmt.

@@ +112,3 @@
>      let old_cap: usize = svec.capacity();
> +    let new_cap: usize = if old_cap == 0 { 4 } else {
> +        old_cap.checked_mul(2).ok_or(FailedAllocationError::new(err_str)) ?

nit: spacing.

::: servo/components/style/invalidation/element/invalidation_map.rs
@@ +192,5 @@
>          selector: &Selector<SelectorImpl>,
>          quirks_mode: QuirksMode)
>      {
>          self.collect_invalidations_for(selector, quirks_mode)
> +            .unwrap_or_else(|_| warn!("out of memory in InvalidationMap::note_selector"))

I'd propagate this up, I think. Should only be called from rebuild(), right?

@@ +209,5 @@
>      fn collect_invalidations_for(
>          &mut self,
>          selector: &Selector<SelectorImpl>,
>          quirks_mode: QuirksMode)
> +        -> Result<(), FailedAllocationError>

Let's format this as:
fn collect_invalidations_for(
    // ...
    quirks_mode: QuirksMode,
) -> Result<(), FailedAllocationError> {

::: servo/components/style/selector_map.rs
@@ +273,5 @@
>  }
>  
>  impl<T: SelectorMapEntry> SelectorMap<T> {
>      /// Inserts into the correct hash, trying id, class, and localname.
> +    pub fn insert(&mut self, entry: T, quirks_mode: QuirksMode)

Let's format it as:

pub fn insert(
    &mut self,
    entry: T,
    quirks_mode: QuirksMode,
) -> Result< ... > {

@@ +489,5 @@
>  #[inline]
>  fn find_push<Str: Eq + Hash, V, VL>(map: &mut PrecomputedHashMap<Str, VL>,
>                                      key: Str,
>                                      value: V)
> +                                    -> Result<(), FailedAllocationError>

Ditto about formatting, though it's pre-existing.

@@ +494,3 @@
>      where VL: VecLike<V> + Default
>  {
> +    map.try_entry(key) ? .or_insert_with(VL::default).push(value);

nit: spacing seems weird here. Also, don't you need to use try_push here? If so, why not?

@@ +519,5 @@
>          self.0.entry(key)
>      }
>  
> +    /// HashMap::try_entry
> +    pub fn try_entry(&mut self, mut key: Atom, quirks_mode: QuirksMode)

nit: ditto about formatting.

::: servo/components/style/stylist.rs
@@ +149,5 @@
>                  }
>  
> +                if self.add_stylesheet(device, quirks_mode, stylesheet,
> +                                       guards.ua_or_user, extra_data,
> +                                       SheetRebuildKind::Full).is_err() {

I'd really propagate this one, seems not great to keep trying to add stuff to the data structures after an OOM.

@@ +186,5 @@
>  
>          for (stylesheet, rebuild_kind) in flusher {
> +            if self.add_stylesheet(device, quirks_mode, stylesheet,
> +                                   guards.author, extra_data,
> +                                   rebuild_kind).is_err() {

Ditto for these.
Attachment #8906147 - Flags: feedback?(emilio) → feedback+
Comment on attachment 8906147 [details] [diff] [review]
bug1395064-use-fallible-collections-5.diff

Review of attachment 8906147 [details] [diff] [review]:
-----------------------------------------------------------------

::: servo/components/fallible/lib.rs
@@ +47,4 @@
>      let old_ptr = vec.as_mut_ptr();
>      let old_len = vec.len();
>  
> +    let err_str = "capacity overflow when allocating Vec";

Or just inline it, given that you only use it twice. Shortening to "Vec capacity overflow" is fine.

@@ +67,5 @@
>      };
>  
>      if new_ptr.is_null() {
> +        return Err(FailedAllocationError::new(
> +            "out of memory when allocating Vec"));

This probably doesn't need to wrap.

::: servo/components/style/invalidation/element/invalidation_map.rs
@@ +192,5 @@
>          selector: &Selector<SelectorImpl>,
>          quirks_mode: QuirksMode)
>      {
>          self.collect_invalidations_for(selector, quirks_mode)
> +            .unwrap_or_else(|_| warn!("out of memory in InvalidationMap::note_selector"))

I don't think detailed error messages for these warnings are worth the visual cost, given that they're very unlikely to be observed. Please just make all these warn!("OOM")

::: servo/tests/unit/style/stylist.rs
@@ +169,5 @@
>  fn test_insert() {
>      let (rules_list, _) = get_mock_rules(&[".intro.foo", "#top"]);
>      let mut selector_map = SelectorMap::new();
> +    selector_map.insert(rules_list[1][0].clone(), QuirksMode::NoQuirks)
> +                .expect("test_insert #1: OOM");

Either just .unwrap() or .expect("OOM");
Attachment #8906147 - Flags: feedback+
Addresses all review comments (comment 16, comment 17).
Attachment #8906147 - Attachment is obsolete: true
Attachment #8906253 - Flags: review?(emilio)
Comment on attachment 8906253 [details] [diff] [review]
bug1395064-use-fallible-collections-6.diff

Review of attachment 8906253 [details] [diff] [review]:
-----------------------------------------------------------------

Modulo formatting nits, this lgtm.

::: servo/components/style/invalidation/element/invalidation_map.rs
@@ +191,4 @@
>      pub fn note_selector(
>          &mut self,
>          selector: &Selector<SelectorImpl>,
>          quirks_mode: QuirksMode)

nit: Paren and brace to the same line as the return type, here and everywhere else:

    ) -> Result<(), FailedAllocationError> {

::: servo/components/style/selector_map.rs
@@ +274,5 @@
>  
>  impl<T: SelectorMapEntry> SelectorMap<T> {
>      /// Inserts into the correct hash, trying id, class, and localname.
> +    pub fn insert(&mut self,
> +                  entry: T,

nit: Arguments four-space indented:

pub fn insert(
    &mut self,
    entry: T,
    quirks_mode: QuirksMode,
) -> Result<(), FailedAllocationError> {

@@ +519,5 @@
>          self.0.entry(key)
>      }
>  
> +    /// HashMap::try_entry
> +    pub fn try_entry(&mut self, mut key: Atom, quirks_mode: QuirksMode)

ditto here.

::: servo/components/style/stylist.rs
@@ +150,5 @@
>                  }
>  
> +                self.add_stylesheet(device, quirks_mode, stylesheet,
> +                                    guards.ua_or_user, extra_data,
> +                                    SheetRebuildKind::Full)?;

nit: Keep the indentation as it was, and just add the question mark, here and below.
Attachment #8906253 - Flags: review?(emilio) → review+
The Talos link in comment 19 shows a 30.15% perf regression on bloom_basic
opt e10s linux64.  I can't reproduce anything like that.  On a quiet machine
w/ cpu locked at 2.4GHz, and doing 30 runs, for
style-perf-tests/perf-reftest/bloom-basic.html, I have the following
traversal_time_ms numbers:

  base        MIN 42.80  AVG 46.76
  infallible  MIN 42.88  AVG 47.01

This is with the default number of threads (6, I assume) and e10s disabled.
(In reply to Julian Seward [:jseward] from comment #18)
> Addresses all review comments (comment 16, comment 17).

On testing this against forced fails, it handles {Vec,SmallVec}::try_push
failures OK.  But for HashMap forced fails, Gecko segfaults outside and
presumably downstream from Stylo.  This didn't happen with earlier versions
of the patch.  I assume that's because this version propagates failures
more agressively than earlier ones.

Bobby:
(1) [see failure log in next comment] any insights into this?

(2) Shall I land it anyway and deal with this in a followup?
    Or try to fix it before landing?
Flags: needinfo?(bobbyholley)
Per IRC discussion, the crash is not something to worry about, since XUL is known to crash if anonymous box style are wrong, and that's what happens when we force OOM when rebuilding the UA stylist.

The main concern is performance of stylesheet parsing and stylist building. Once those are measured to be OK (per discussion) we should be good to land.
Flags: needinfo?(bobbyholley)
Further measurements, per IRC discussion.  Same methodology as in comment 21.
All times are milliseconds.  Summary:


./mach gtest Stylo.Servo_StyleSheet_FromUTF8Bytes_Bench

10 runs: BASE     min 358           avg 362.3
         PATCHED  min 358 (+0.00%)  avg 364.0 (+0.47%)


tp6 facebook, time for impl DocumentCascadeData :: rebuild, biggest number
only

20 runs:  BASE     min 5.32           avg 5.43
          PATCHED  min 5.49 (+3.20%)  avg 5.61 (+3.31%)


100x myspace, time for impl DocumentCascadeData :: rebuild, biggest number
only

20 runs: BASE     min 108.8           avg 109.9
         PATCHED  min 111.3 (+2.30%)  avg 112.3 (+2.18%)
In short a 2% to 3% perf loss in stylist rebuild.

Possible causes (surmised, not measured):

* increased number of conditional branches due to null checks

* increased icache cost

* poorer optimization of affected functions due to increased number of
  control flow paths to exit nodes

* needing to return a Result<(), FallibleAllocationError> in the affected
  functions

* possibly non-optimal initial vec size of 4 following resize from zero

* missing inline directive(s) in some crucial place?

Possible mitigations

* change return type to Result<(), ()> if that reduces the number of
  returned machine words from 2 to 1

* tune initial vec size of 4 following resize from zero

* more inlining

Proceeding to land regardless, since we need this functionality anyway,
measurements/mitigations will delay further, and proposed mitigations are
low risk.
Blocks: 1398593
(In reply to Julian Seward [:jseward] from comment #28)
> Proceeding to land regardless, since we need this functionality anyway,
> measurements/mitigations will delay further, and proposed mitigations are
> low risk.

Yeah, makes sense. I filed bug 1398593 to track the mitigations.
https://hg.mozilla.org/integration/autoland/rev/903b743e407e
Status: ASSIGNED → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
Depends on: 1400754
You need to log in before you can comment on or make changes to this bug.