1393656 - stylo: Support fallible allocations for HashMaps

Status: RESOLVED FIXED

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

Description

[Bobby Holley (:bholley)]

Moving this out of bug 1389009 for clarity.

Comment 1

[Bobby Holley (:bholley)]

(Responding to bug 1389009 comment 54 and onward)

(In reply to Simon Sapin (:SimonSapin) from comment #54)
> I’m extremely worried about any plan that involves making assumptions about
> private implementation details of standard library types, such as the memory
> layout or which allocator is used. Yes, static assertions can help turn some
> cases of UB into compilation errors. Yes, we can ask the Rust team to tell
> us when these details change. But things would still break when they do
> change. With such a plan, in addition to a minimum Rust version requirement,
> any given Firefox version would effectively also have a maximum Rust version.
> 
> Do we really want to say “only Rust 1.20.x is supported for compiling
> Firefox 57”? That would defeat the point of using the stable channel.

It's only a maximum version in the event that the HashMap layout actually changes in the near term, which seems unlikely, especially if the libs team is aware of this situation. As long as we push them team to hurry up and give us the API we need, it seems unlikely that we will develop a maximum version in the timeframe that 57 is supported and people are building it. And after that we don't really care. And if somebody did care, it would be trivial to backport a patch to just disable fallible allocation, which would likely be unimportant for whatever use case is involved.

Maximum versions are annoying, but they happen all the time in Firefox, especially given our complicated matrix of compilers. And this already happened for stylo IIUC when a recent rust version broke our FFI lifetime safety stuff. The only way to reliably get a working build of Firefox is to use the same tooling that ran on CI when the code was current.

> I strongly feel that this is a deal-breaker, and that the only viable way to
> get fallible allocations before they’re supported

I remain unconvinced that the small possibility of a maximum version is a deal-breaker. We are selecting the least of bad options.

> in the standard library is
> to build separate collections types on top of libc::malloc/free (or jemalloc
> equivalents), fully independent from the standard library collections or
> allocators. (They can be a copy/fork of the same code, as long as we control
> what exact version of it is used.)

We could fork HashMap, but the cost seems high. There's a lot of complicated code, and we can't copy it verbatim because it uses various unstable features. It's certainly doable, I just think it's marginally worse than the buffer exchange hackery.


(In reply to Manish Goregaokar [:manishearth] from comment #55)
> Agreed.
> 
> I consider "guessing" HashMap layout to be the worst of the options here.
> Especially since we don't pin rust versions at all.

As noted above, the maximum version thing is not particularly unusual for Firefox.

> 
> I really think the ordermap solution is the way to go; fallible APIs can be
> easily added to OrderMap, even without a fork (but if we fork it it's easy
> to maintain since it's 100% safe)

Except that OrderMap is less vetted and slower, and making/proving it fast for our purposes is potentially time-consuming, and we don't have much time. Again, not undoable, I just think the tradeoffs are worse.

(In reply to Simon Sapin (:SimonSapin) from comment #56)
> Specifically, I’m proposing:
> 
> * Copying into a new crate the entire implementation of std::vec::Vec

I don't see why we need to duplicate Vec at all, given my non-invasive approach in bug 1389009. We just use into_boxed_slice and from_raw_parts to manipulate the buffer in a typesafe way.

> and
> std::collections::HashMap, including anything else they need that is private
> or unstable. (This includes the std::heap::Alloc trait, except that our
> equivalent of its std::heap::Heap impl could use libc or jemalloc directly
> and skip std’s mechanism for changing the default allocator.)

This is potentially a lot of code. HashMap alone is spread across several files that aren't small. And we couldn't leave the code pristine anyway, given the reliance on intrinsics like needs_drop.

> * Add fallible methods to that copy.
> * Change SmallVec to be based on this instead of std::vec::Vec

Changing SmallVec to be based on a non-standard type has costs and isn't necessary. With my proposal from bug 1389009 we can have our cake and eat it too.

Comment 2

[Nathan Froyd [:froydnj]]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #1)
> (In reply to Simon Sapin (:SimonSapin) from comment #54)
> > I strongly feel that this is a deal-breaker, and that the only viable way to
> > get fallible allocations before they’re supported
> 
> I remain unconvinced that the small possibility of a maximum version is a
> deal-breaker. We are selecting the least of bad options.

Insofar as avoiding delving into Rust std:: internals, I agree with Simon.

I would also note here that we have a Rust upgrade policy in place, and it's going to be a little odd if, shortly after we implemented this policy, we decided to not follow it.  And why?  Because we had written code that depended on the exact layout of std:: internals?  That behavior sets a bad precedent in my mind.  People had a hard enough time understanding why we didn't upgrade to the latest and greatest Rust compiler when we talked about "pain for downstream", "no truly needed features", and "packages we depend on can just not use newer features"; if our reason now (and potentially in the future) becomes "well, we're dependent on std:: internals", that gets...kind of laughable.

Comment 3

[Manish Goregaokar [:manishearth]]

>  As long as we push them team to hurry up and give us the API we need


This could basically be more than half a year. The impl period (sept 18) is coming up so if the allocations RFC misses that we'll have to wait for January for the RFC to be even *accepted*. Then it will need to get implemented and bake for the relevant amount of time, and then stabilize.

>  We are selecting the least of bad options.


I fail to see how -- the concerns of forking hashmap are much less.

The concerns of forking hashmap are that maintaining a large chunk of unsafe code is a major burden, especially when std changes things. This applies even more to layout punning hashmap.

In fact, with the layout punned hashmap we'll have algorithm problems as well -- since we're only wrapping it we'll have to reimplement the reallocation routine which can very easily go quadratic if not done right (the internal hashmap impl has more knowledge of the buckets and does it a smarter way IIRC)


I'm still very against forking hashmap, but layout punning seems strictly worse to me.

> Except that OrderMap is less vetted and slower

It's also 100% safe, so it doesn't need as much vetting. But yes, perf issues are there :(

> This is potentially a lot of code. HashMap alone is spread across several files that aren't small. And we couldn't leave the code pristine anyway, given the reliance on intrinsics like needs_drop.

We can clean up reliance on multiple things. needs_drop is an optimization IIRC.

I should perhaps try this out and report back.

Comment 4

[Bobby Holley (:bholley)]

(In reply to Nathan Froyd [:froydnj] from comment #2)
> (In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #1)
> > (In reply to Simon Sapin (:SimonSapin) from comment #54)
> > > I strongly feel that this is a deal-breaker, and that the only viable way to
> > > get fallible allocations before they’re supported
> > 
> > I remain unconvinced that the small possibility of a maximum version is a
> > deal-breaker. We are selecting the least of bad options.
> 
> Insofar as avoiding delving into Rust std:: internals, I agree with Simon.
> 
> I would also note here that we have a Rust upgrade policy in place, and it's
> going to be a little odd if, shortly after we implemented this policy, we
> decided to not follow it.

I'm not aware of anything in our update policy related to maximum versions for unsupported branches. Did I miss it somewhere?

> And why?  Because we had written code that
> depended on the exact layout of std:: internals?  That behavior sets a bad
> precedent in my mind.  People had a hard enough time understanding why we
> didn't upgrade to the latest and greatest Rust compiler when we talked about
> "pain for downstream", "no truly needed features", and "packages we depend
> on can just not use newer features"; if our reason now (and potentially in
> the future) becomes "well, we're dependent on std:: internals", that
> gets...kind of laughable.

Only in the scenario where this actually becomes a problem for people downstream, which I've noted several times is pretty unlikely. It seems like this would only be an issue for ESR, and we can always uplift a patch to fix ESR (or just disable fallible allocations) if it becomes necessary.

Honestly it seems pretty straightforward to just ask the libs team to ship us the right API, and not shuffle the HashMap fields (if they were inclined to, which they probably aren't) until they do so.

Comment 5

[Bobby Holley (:bholley)]

(In reply to Manish Goregaokar [:manishearth] from comment #3)
> >  As long as we push them team to hurry up and give us the API we need
> 
> 
> This could basically be more than half a year. The impl period (sept 18) is
> coming up so if the allocations RFC misses that we'll have to wait for
> January for the RFC to be even *accepted*. Then it will need to get
> implemented and bake for the relevant amount of time, and then stabilize.

That seems like a good reason to get our staff to push on the RFC.

> 
> >  We are selecting the least of bad options.
> 
> 
> I fail to see how -- the concerns of forking hashmap are much less.
> 
> The concerns of forking hashmap are that maintaining a large chunk of unsafe
> code is a major burden, especially when std changes things. This applies
> even more to layout punning hashmap.

Hm, I don't follow this. The "maintaining a large chunk of unsafe code" is the downside of forking hashmap, and the "when stdlib changes things" is the downside of layout punning. The absence of each downside is the upside of the opposite approach.

> 
> In fact, with the layout punned hashmap we'll have algorithm problems as
> well -- since we're only wrapping it we'll have to reimplement the
> reallocation routine which can very easily go quadratic if not done right
> (the internal hashmap impl has more knowledge of the buckets and does it a
> smarter way IIRC)

I thought we could fix this by reseeding hashes? In any case, we'd only invoke this routine for large reallocs, which would be rare.

> 
> 
> I'm still very against forking hashmap, but layout punning seems strictly
> worse to me.
> 
> > Except that OrderMap is less vetted and slower
> 
> It's also 100% safe, so it doesn't need as much vetting. But yes, perf
> issues are there :(
> 
> > This is potentially a lot of code. HashMap alone is spread across several files that aren't small. And we couldn't leave the code pristine anyway, given the reliance on intrinsics like needs_drop.
> 
> We can clean up reliance on multiple things. needs_drop is an optimization
> IIRC.
> 
> I should perhaps try this out and report back.

Feel free, and I wouldn't object if the result turned out to be manageable and the Servo team preferred this outcome. The only outcomes I object to are (a) switching impls or (b) doing nothing.

Comment 6

[Manish Goregaokar [:manishearth]]

> Hm, I don't follow this. The "maintaining a large chunk of unsafe code" is the downside of forking hashmap,

The large chunk of unsafe code only needs to be "maintained" *when* the stdlib or language changes things. Otherwise it can just stay unchanged. The fork at least will be resilient to changes to the impl itself and only have to deal with changes to how unsafe code works, which is easier to track and much more rare. (The only reason breaking unsafe is a concern is because of the amount of pre-1.0 unsafe code in hashmap, which may not actually be invoking stable behavior but is maintained within the stdlib so that doesn't matter. But breaking unsafe is still pretty rare.)

It's not a situation I'm overly happy with, but it would be way better than layout punning, which has the same set of problems but is much more brittle.

> In any case, we'd only invoke this routine for large reallocs, which would be rare.

This sounds reasonable.

> That seems like a good reason to get our staff to push on the RFC.

I'll spend some time helping out to see if it can be sped up. There are a lot of things one can do to keep an RFC going smoothly.

Comment 7

[Julian Seward [:jseward]]

On the whole my instinct inclines me towards Simon's proposal, because it
makes us more independent of std:: internal changes and of std:: RFC
adoption timescales.

> > Except that OrderMap is less vetted and slower
>
> It's also 100% safe, so it doesn't need as much vetting. But yes, perf
> issues are there :(

The vanilla OrderMap produces a Stylo which is only 1.5% slower than using
HashMap, and OrderMap is often faster than HashMap on its own micro
benchmarks, especially for iteration.  All that from 1500 lines of 100% safe
code.  Given that, I'm kinda sceptical how much benefit HashMap's extensive
unsafe hackery really brings.

If we stick with un-forked HashMap we pretty much preclude the possibility
-- at some point in the future -- of making a *Map which is tuned for
Stylo's specific workload.  OrderMap's memory layout [cache friendlyness]
seems to me something that could be improved on, for example.

All of the above said ..  I see the urgency of the current situation.

Comment 8

[Nathan Froyd [:froydnj]]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #4)
> (In reply to Nathan Froyd [:froydnj] from comment #2)
> > I would also note here that we have a Rust upgrade policy in place, and it's
> > going to be a little odd if, shortly after we implemented this policy, we
> > decided to not follow it.
> 
> I'm not aware of anything in our update policy related to maximum versions
> for unsupported branches. Did I miss it somewhere?

No--and I agree that we shouldn't be in the business of supporting newer Rust releases on release branches and so forth.  I was thinking of:

* We start depending on std:: internals on central;
* New Rust version comes out;
* We don't upgrade central according to policy because the new release "broke" the internals from our perspective.

Comment 9

[Jack Moffitt [:jack]]

I spoke with Aaron Turon and Niko Matsakis yesterday and asked about the probability of a layout change to HashMap. They said it was very, very low and that they probably be willing to block changes to it until landing fallible APIs. I think that's strictly more than is needed here. It also sounded pretty hopeful to get the fallible APIs moving quickly, and while they won't land before we need them in 57, at least this means whatever solution we put in place here is temporary.

I agree with Bobby that the practical downsides seem low for depending on the internals of HashMap temporarily, but I also understand the concern that it's a bad habit to get into. I think I can live with any of the three proposals because they are temporary, but we need to keep on top of the fallible RFC and make sure that progresses on schedule.

Comment 10

[Manish Goregaokar [:manishearth]]

I've got a fork up at https://github.com/Manishearth/hashglobe

It's not complete, but I've removed dependence on all unstable features except the allocation APIs (which we need to change anyway). I'll be fixing that up shortly. It doesn't diverge too much, but I hope we never have to touch this once it's finished.

Comment 11

[Manish Goregaokar [:manishearth]]

Fork done. There's a RawTable::new_uninitialized_fallible API, which y'all can propagage up to create the desired fallible APIs.

Some notes:

 - I've tried to keep the commit history as clean as possible wrt the changes being made so the divergence is obvious. However src/set.rs managed to miss getting VCSd and got checked in later. It's no big deal since that file was not changed much aside from some removals
 - There are FORK NOTEs wherever something has diverged nontrivially
 - There's actually not much that diverged, it was mostly shimming Unique/Shared/alloc and removing extraneous impls
 - This library contains a cleaned up fork of liballoc_system, which handles all the platform-specific allocation stuff. This forces the allocation strategy of this library to be liballoc_system.
 - We should *only* use this library in geckolib mode, since in servo mode using the system allocator might not work well.
 - I have not reviewed my own changes. This may explode in the most trivial manner possible. We should review and test this.
 - We probably should move this into tree instead of publishing to crates.io (unless git deps work), since I don't really want this out there on Crates.

Comment 12

[Julian Seward [:jseward]]

What's the plan of record here?  Is it to use Manishearth's HashMap fork?
Or go with Bobby's layering of fallible insert on top of the existing
HashMap code, as described at
https://bugzilla.mozilla.org/show_bug.cgi?id=1389009#c48 ?

Comment 14

[Manish Goregaokar [:manishearth]]

The above comment said that we're going through with the fork (I'm working on adding fallibility to the API, and making it robust so that it can be used in infallible mode when used with a non-system allocator)

The above comment contained an emoji and bugzilla ate it.

Comment 15

[Bobby Holley (:bholley)]

Yep, we're going to land Manish's HashMap fork.

Comment 16

[Manish Goregaokar [:manishearth]]

Alright, it's done. I'll make a PR swapping it in soon.

I need unsafe code / fork review.


https://github.com/Manishearth/hashglobe

I tried to keep the history clean, but set.rs got checked in a bit later than it should have. However, it has a very clean diff with the stdlib set.rs so it's no big deal.

Comment 17

[Manish Goregaokar [:manishearth]]

cc gankro for unsafe review

Comment 18

[Manish Goregaokar [:manishearth]]

Attachment: Bug 1393656 - Part 1: stylo: Add dependency on hashglobe;

Review commit: https://reviewboard.mozilla.org/r/174726/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/174726/

Comment 19

[Manish Goregaokar [:manishearth]]

Attachment: Bug 1393656 - Part 2: stylo: Add hash module for reexporting HashMap;

Review commit: https://reviewboard.mozilla.org/r/174728/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/174728/

Comment 20

[Manish Goregaokar [:manishearth]]

Attachment: Bug 1393656 - Part 3: stylo: Replace all hashtable collections with ones from style::hash;

Review commit: https://reviewboard.mozilla.org/r/174730/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/174730/

Comment 21

[Manish Goregaokar [:manishearth]]

The commits don't properly vendor hashglobe yet, I'm debating whether to just copy into tree or crates.io release it as terrible-horrible-no-good-very-bad-hashglobe (I'm reluctant to release since I don't want folks using this)

Comment 22

[Bobby Holley (:bholley)]

(In reply to Manish Goregaokar [:manishearth] from comment #21)
> The commits don't properly vendor hashglobe yet, I'm debating whether to
> just copy into tree or crates.io release it as
> terrible-horrible-no-good-very-bad-hashglobe (I'm reluctant to release since
> I don't want folks using this)

Why would we develop it in a separate github repo or put it on crates.io? It seems like this is exactly the kind of thing we should just stick in components/.

Comment 23

[Manish Goregaokar [:manishearth]]

I wanted to preserve the fork history.


I can instead do a merge of the repo directly into servo/ however.

Comment 24

[Emilio Cobos Álvarez (:emilio)]

I think preserving history is nice.

My only comment is in https://github.com/Manishearth/hashglobe/commit/f0231f7c1bcc32d448fa1122beeb4f57a369c19d, rest looks good. I guess if we happen to have lifetime issues on custom properties we could just use std::HashMap instead, though it seems unlikely.

Comment 25

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8902966 [details]
Bug 1393656 - Part 1: stylo: Add dependency on hashglobe;

https://reviewboard.mozilla.org/r/174726/#review179930

::: servo/components/style/Cargo.toml:75
(Diff revision 1)
>  servo_url = {path = "../url", optional = true}
>  time = "0.1"
>  unicode-bidi = "0.3"
>  unicode-segmentation = "1.0"
>  
> +hashglobe = { git = "https://github.com/Manishearth/hashglobe.git"}

Move it up, sorted with the rest of dependencies.

Comment 26

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8902967 [details]
Bug 1393656 - Part 2: stylo: Add hash module for reexporting HashMap;

https://reviewboard.mozilla.org/r/174728/#review179932

Comment 27

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8902967 [details]
Bug 1393656 - Part 2: stylo: Add hash module for reexporting HashMap;

https://reviewboard.mozilla.org/r/174728/#review179934

::: servo/components/style/hash.rs:6
(Diff revision 1)
> +/* 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/. */
> +
> +use fnv;
> +

Oh, please add a comment here re. this going away eventually.

Comment 28

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8902968 [details]
Bug 1393656 - Part 3: stylo: Replace all hashtable collections with ones from style::hash;

https://reviewboard.mozilla.org/r/174730/#review179936

This is missing a bunch of FnvHashMaps:

 * context.rs
 * servo/selector_parser.rs (though I guess it doesn't really matter in this case since they're servo-specific).
 * stylesheets/stylesheet.rs
 * invalidation/stylesheets.rs
 * invalidation/media_queries.rs
 * There's also a `FnvHashMap` re-export from stylist.rs, but I think it's unused, so you can just kill it.

With that, r=me

::: servo/components/style/hash.rs:17
(Diff revision 1)
>  #[cfg(feature = "gecko")]
>  pub use hashglobe::hash_set::HashSet;
>  
>  
> +
> +

nit: This belongs to the previous commit, and this whitespace is unnecessary.

::: servo/components/style/selector_map.rs:114
(Diff revision 1)
>  #[inline]
>  fn sort_by_key<T, F: Fn(&T) -> K, K: Ord>(v: &mut [T], f: F) {
>      sort_by(v, |a, b| f(a).cmp(&f(b)))
>  }
>  
> -impl<T> SelectorMap<T> {
> +// XXXManishearth the 'static bound can be removed when

Trailing `.` is missing. Also, I think we mostly use `FIXME(Foo)` instead of `XXXFoo`, but no big deal.

::: servo/components/style/selector_map.rs:471
(Diff revision 1)
>  #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
> -pub struct MaybeCaseInsensitiveHashMap<K: PrecomputedHash + Hash + Eq, V>(PrecomputedHashMap<K, V>);
> +pub struct MaybeCaseInsensitiveHashMap<K: PrecomputedHash + Hash + Eq, V: 'static>(PrecomputedHashMap<K, V>);
>  
> -impl<V> MaybeCaseInsensitiveHashMap<Atom, V> {
> +// XXXManishearth the 'static bound can be removed when
> +// our HashMap fork (hashglobe) is able to use NonZero,
> +// or when stdlib gets fallible collections

Ditto.

Comment 29

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8902968 [details]
Bug 1393656 - Part 3: stylo: Replace all hashtable collections with ones from style::hash;

https://reviewboard.mozilla.org/r/174730/#review179938

Oh, and there's of course the custom properties map I mentioned earlier. I guess it can't be changed due to the lifetime issues? If so, maybe leave a comment there?

Comment 30

[Aria Beingessner [:Gankra]]

I commented on the issues I saw; this seems basically fine from an unsafe code perspective. I didn't strongly review from the eye of miscellaneous correctness issues.

Comment 31

[Manish Goregaokar [:manishearth]]

Since I want to preserve history and that's going to be tricky across repos, I moved this to a Servo PR:

https://github.com/servo/servo/pull/18334

Only the last commit needs review

Comment 32

[Bobby Holley (:bholley)]

This landed. Adding usage is tracked in bug 1395064.