1350262 - unordered_map causes check_stdcxx failures becauses @GLIBCXX_3.4.18 symbols

Status: RESOLVED FIXED

(Firefox Build System :: General, enhancement)

Description

[Bruce Sun [:brsun]]

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

Comment 1

[Bruce Sun [:brsun]]

:glandium suggests that we need to add two corresponding std::__detail::_Prime_rehash_policy functions under build/unix/stdc++compat.

Comment 2

[Bruce Sun [:brsun]]

And be careful with the license issue if we are going to directly copy codes from libstdc++.

Comment 3

[Evelyn Hung]

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.

Comment 4

[Bruce Sun [: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

Comment 5

[Lee Salzman [:lsalzman]]

(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.

Comment 6

[Lee Salzman [:lsalzman]]

(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.

Comment 7

[Nathan Froyd [:froydnj]]

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.

Comment 8

[Ya-Chieh Wu (inactive)]

I got our first baby step with the empty implementation of them here.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=d0f85d9d82308be3f6c04052880f09ddb1df3359

Comment 9

[Astley Chen (inactive)]

See also: https://pdfium.googlesource.com/pdfium/+/e47e0c96009b8633294eebbb9eb0e84caf525c57%5E%21/

It might be an alternative to avoid implementing this.

Comment 10

[Ya-Chieh Wu (inactive)]

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 :)

Comment 11

[Lee Salzman [:lsalzman]]

(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?

Comment 12

[Gervase Markham [: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

Comment 13

[Nathan Froyd [:froydnj]]

Does the answer change any if we're copying LGPL code?  Probably not...

Comment 14

[Gervase Markham [:gerv]]

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

Comment 15

[Lee Salzman [:lsalzman]]

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. :(

Comment 16

[Lee Salzman [:lsalzman]]

Attachment: implement prime rehash policy compat for unordered_map and unordered_set in libstdc++

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.

Comment 17

[Nathan Froyd [:froydnj]]

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).

Comment 18

[Mike Hommey [:glandium]]

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.

Comment 19

[Lee Salzman [:lsalzman]]

So why can't we sidestep this entire issue by bumping the libstdc++ version requirement to 3.4.18?

Comment 20

[Lee Salzman [:lsalzman]]

Attachment: implement prime rehash policy compat for unordered_map and unordered_set in libstdc++

This version routes the calls to the tr1 versions, which seems to pass the symbol checks and otherwise work.

Comment 21

[Lee Salzman [:lsalzman]]

Attachment: implement prime rehash policy compat for unordered_map and unordered_set in libstdc++

Small performance fix to initialize _M_next_resize in the tr1 policy before calling _M_need_rehash.

Comment 22

[Mike Hommey [:glandium]]

(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)

Comment 23

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3d157ccbc5a7
implement prime rehash policy compat for unordered_map and unordered_set in libstdc++. r=glandium

Comment 24

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/3d157ccbc5a7