Closed Bug 1350262 Opened 3 years ago Closed 3 years ago

unordered_map causes check_stdcxx failures becauses @GLIBCXX_3.4.18 symbols

Categories

(Firefox Build System :: General, enhancement)

Unspecified
Linux
enhancement
Not set

Tracking

(firefox55 fixed)

RESOLVED FIXED
mozilla55
Tracking Status
firefox55 --- fixed

People

(Reporter: brsun, Assigned: lsalzman)

References

Details

Attachments

(1 file, 2 obsolete files)

check_stdcxx failures[1] when using some unordered_map operations on the try server for Linux platforms:
 - unordered_map::unordered_map(initializer_list<value_type>)
 - unordered_map::operator[]

[1] https://treeherder.mozilla.org/#/jobs?repo=try&revision=d88777dd85a64c81f79b9874b443105192c42552
:glandium suggests that we need to add two corresponding std::__detail::_Prime_rehash_policy functions under build/unix/stdc++compat.
And be careful with the license issue if we are going to directly copy codes from libstdc++.
Assignee: nobody → ywu
So here is my understanding of the problem: 

We intentionally added check_stdcxx test to detect using unwanted versions of symbols. In our case (on bug 1345330) we probably hit std::__detail::_Prime_rehash_policy class[1] per Bruce's investigation. 

We could (1) avoid its usage by eliminating unordered_map usage from imported chromium code, or (2) implement our version of std::__detail::_Prime_rehash_policy class in stdc++compat if possible. 

I'm not sure which one is easier. We could firstly understand how many places in Chromium code use unordered_map and summarize their usages, and then examine if we have something equal in Gecko to replace. If the replacement isn't feasible or causes maintenance effort, we don't have other option but go for (2) - implement std::__detail::_Prime_rehash_policy by ourselves.

@Bruce, besides std::__detail::_Prime_rehash_policy, what else? (as you mentioned in comment 1 saying there are *two*)

btw, the log in comment 0 on treherder is expired.
Flags: needinfo?(brsun)
INFO -  TEST-UNEXPECTED-FAIL | check_stdcxx | We do not want these libstdc++ symbol versions to be used:
INFO -    _ZNKSt8__detail20_Prime_rehash_policy14_M_need_rehashEjjj@GLIBCXX_3.4.18
INFO -    _ZNKSt8__detail20_Prime_rehash_policy11_M_next_bktEj@GLIBCXX_3.4.18
Flags: needinfo?(brsun)
(In reply to Bruce Sun [:brsun] from comment #4)
> INFO -  TEST-UNEXPECTED-FAIL | check_stdcxx | We do not want these libstdc++
> symbol versions to be used:
> INFO -   
> _ZNKSt8__detail20_Prime_rehash_policy14_M_need_rehashEjjj@GLIBCXX_3.4.18
> INFO -    _ZNKSt8__detail20_Prime_rehash_policy11_M_next_bktEj@GLIBCXX_3.4.18

Running into this as well while trying to update our tree version of Skia to the next milestone - and as such, this is currently blocking our ability to do that update. It is not feasible to just replace uses of unordered_map/unordered_set with something else, so I would recommend we fix this in such a way as to allow these to be used, as anything else will cause massive headaches.
(In reply to Lee Salzman [:lsalzman] from comment #5)
> (In reply to Bruce Sun [:brsun] from comment #4)
> > INFO -  TEST-UNEXPECTED-FAIL | check_stdcxx | We do not want these libstdc++
> > symbol versions to be used:
> > INFO -   
> > _ZNKSt8__detail20_Prime_rehash_policy14_M_need_rehashEjjj@GLIBCXX_3.4.18
> > INFO -    _ZNKSt8__detail20_Prime_rehash_policy11_M_next_bktEj@GLIBCXX_3.4.18
> 
> Running into this as well while trying to update our tree version of Skia to
> the next milestone - and as such, this is currently blocking our ability to
> do that update. It is not feasible to just replace uses of
> unordered_map/unordered_set with something else, so I would recommend we fix
> this in such a way as to allow these to be used, as anything else will cause
> massive headaches.

Mike, what would be the viability of your suggestion of just adding these two compat functions as noted above in comment 1? It would be nice if we could get a timely solution to this, and if just stubbing those gets us that, it seems worthwhile to me.
Flags: needinfo?(mh+mozilla)
You can certainly add them, but they require copying things from libstdc++ headers, which I think is OK (?).  But in copying things from the libstdc++ headers, you will discover that they reference actual symbols in libstdc++.so itself, and you'll need to decide what to do about that.  I don't think you can just blindly copy the code/data out of libstdc++.

You may want to ask Gerv about what the libstdc++ license requires here.
Flags: needinfo?(mh+mozilla)
I got our first baby step with the empty implementation of them here.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=d0f85d9d82308be3f6c04052880f09ddb1df3359
See also: https://pdfium.googlesource.com/pdfium/+/e47e0c96009b8633294eebbb9eb0e84caf525c57%5E%21/

It might be an alternative to avoid implementing this.
Status: NEW → ASSIGNED
Thanks comment 9's input. PDF team noticed this changes yesterday so we are looking into it now and might go for the choice of replacing unordered_map in pdfium. We at first tried to implement these two compat functions because we wanted to make as less changes as possible in pdfium in order to save the efforts on update the tree version of pdfium. But now it looks like we have the reasons to replace it.

Hey lsalzman, you probably can check on my comment 8 to see if that's what you need. We haven't had sure answer that we are going to choose the replacing unordered_map way as I said we noticed this yesterday and we still need to process it first. I will keep it posted when there is a decision made. you probably can go first if there is a timeline limit :)
(In reply to Nathan Froyd [:froydnj] from comment #7)
> You can certainly add them, but they require copying things from libstdc++
> headers, which I think is OK (?).  But in copying things from the libstdc++
> headers, you will discover that they reference actual symbols in
> libstdc++.so itself, and you'll need to decide what to do about that.  I
> don't think you can just blindly copy the code/data out of libstdc++.
> 
> You may want to ask Gerv about what the libstdc++ license requires here.

It looks like the details of interacting with the libstdc++ implementation here are so specific that we basically have to copy these functions out of libstdc++ for compat. And those functions are thus licensed under the GPL. Gerv, what are the bugbears thereof?
Flags: needinfo?(gerv)
Copying GPL-only code into something which ships with Firefox isn't possible, I'm afraid. That would place all of Firefox under the GPL (alone), which is not something we want to do.

Gerv
Flags: needinfo?(gerv)
Does the answer change any if we're copying LGPL code?  Probably not...
Slightly. If you structure it so the LGPLed code is in its own separate library (presumably a very small one), that would be OK.

Gerv
Mike, would it be reasonable to change the libstdc++ symbol version requirement from 3.4.16 to 3.4.18, that way we sidestep this entire issue? Otherwise, this becomes annoying. :(
Flags: needinfo?(mh+mozilla)
Blocks: 1340627
This independently implements the prime rehash policy based on the public header documentation without being dependent on internal mechanisms/details in the linked library that would pose licensing problems. The prime progression should more or less mimic the way our in-tree hashtable works by just growing with powers-of-2, though this tries to do that within the extra constraint of making sure those sizes are also prime and play nicely with the memory allocator.
Assignee: ywu → lsalzman
Attachment #8864372 - Flags: review?(nfroyd)
Comment on attachment 8864372 [details] [diff] [review]
implement prime rehash policy compat for unordered_map and unordered_set in libstdc++

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

I guess I can review this, but I'm not excited about duplicating this functionality.  I'd like a second opinion, so run this by glandium, too, and get Gerv's opinion on it with regard to the licensing minutiae as well?

::: build/unix/stdc++compat/stdc++compat.cpp
@@ +45,5 @@
> +    // tightly within power-of-2 spans of memory, rather than unnecessarily
> +    // wasting memory for overflow buckets. The first row of small primes does
> +    // not follow this pattern so as to give a more reasonable progression
> +    // for small bucket counts.
> +    static const size_t primes[] = {

We may want to make sure this is the same size as the symbol on 32-bit and 64-bit libstdc++, just in case, which means adding more primes as necessary (either padding out the list with the maximum prime we use, or using bigger primes on 64-bit as necessary).
Attachment #8864372 - Flags: review?(nfroyd)
Attachment #8864372 - Flags: review?(mh+mozilla)
Attachment #8864372 - Flags: review?(gerv)
Attachment #8864372 - Flags: review+
Comment on attachment 8864372 [details] [diff] [review]
implement prime rehash policy compat for unordered_map and unordered_set in libstdc++

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

::: build/unix/stdc++compat/stdc++compat.cpp
@@ +45,5 @@
> +    // tightly within power-of-2 spans of memory, rather than unnecessarily
> +    // wasting memory for overflow buckets. The first row of small primes does
> +    // not follow this pattern so as to give a more reasonable progression
> +    // for small bucket counts.
> +    static const size_t primes[] = {

If you don't really care about the specific list of primes, you could use std::tr1::__detail::__prime_list ; its size is std::tr1::__detail::_Prime_rehash_policy::_S_n_primes.

@@ +54,5 @@
> +      16777213, 33554393, 67108859, 134217689, 268435399, 536870909,
> +      1073741789, 2147483647, 4294967291
> +    };
> +    size_t i = 0;
> +    while (i < sizeof(primes) / sizeof(primes[0]) - 1) {

This loop could be replaced with std::lower_bound.

@@ +60,5 @@
> +        break;
> +      }
> +      i++;
> +    }
> +    return primes[i];

libstdc++ sets _M_next_resize to __builtin_ceil(primes[i] * (long double)_M_max_load_factor);

(or size_t(-1) when using the last prime)

and some functions use _M_next_resize through _M_state() to further give to _M_reset, so it is necessary to set that member variable.

@@ +70,5 @@
> +                                                 size_t __n_ins) const
> +  {
> +    // Check if the number of used elements is still within the load factor.
> +    size_t used = __n_elt + __n_ins;
> +    if (used >= __n_bkt * _M_max_load_factor) {

The arithmetic operations in this function can overflow.

Note that libstdc++ implementation is slightly different and uses _M_next_resize:
https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8e8270c597270a1a7967/libstdc%2B%2B-v3/src/c%2B%2B11/hashtable_c%2B%2B0x.cc#L98

But that's GPLv3 code... although the GCC Runtime Library Exception version 3.1 applies (https://www.gnu.org/licenses/gcc-exception-3.1.en.html) but it's not entirely clear what that means for the hacks in this file.

Now, with all that being said, there's a possible hacky way out by entirely reusing std::tr1::__detail::_Prime_rehash_policy.

Something like (untested):

namespace std {
size_t __detail::_Prime_rehash_policy::_M_next_bkt(size_t __n) const {
  std::tr1::__detail::_Prime_rehash_policy policy(_M_max_load_factor);
  size_t ret = policy._M_next_bkt(__n);
  _M_next_resize = policy._M_next_resize;
  return ret;
}

And something similar for _M_need_rehash.
Attachment #8864372 - Flags: review?(mh+mozilla) → review-
So why can't we sidestep this entire issue by bumping the libstdc++ version requirement to 3.4.18?
This version routes the calls to the tr1 versions, which seems to pass the symbol checks and otherwise work.
Attachment #8865894 - Flags: review?(mh+mozilla)
Small performance fix to initialize _M_next_resize in the tr1 policy before calling _M_need_rehash.
Attachment #8865894 - Attachment is obsolete: true
Attachment #8865894 - Flags: review?(mh+mozilla)
Attachment #8866064 - Flags: review?(mh+mozilla)
(In reply to Lee Salzman [:lsalzman] from comment #19)
> So why can't we sidestep this entire issue by bumping the libstdc++ version
> requirement to 3.4.18?

Because it means dropping support for Fedora < 19, OpenSUSE < 13.1, Debian wheezy and Ubuntu 12.04. (and we're running tests on the latter)
Flags: needinfo?(mh+mozilla)
Attachment #8866064 - Flags: review?(mh+mozilla) → review+
Attachment #8864372 - Attachment is obsolete: true
Attachment #8864372 - Flags: review?(gerv)
Pushed by lsalzman@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3d157ccbc5a7
implement prime rehash policy compat for unordered_map and unordered_set in libstdc++. r=glandium
https://hg.mozilla.org/mozilla-central/rev/3d157ccbc5a7
Status: ASSIGNED → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Product: Core → Firefox Build System
You need to log in before you can comment on or make changes to this bug.