[libc++] Fix wrong implementation of CityHash

[oToToT]

Summary

As PR56606 stated, the current implementation of CityHash in libc++
would drop some bits unintentionally. Cast the 32bit int to the 64bit
int to avoid this happened.

[oToToT]

As mentioned in PR56606, CityHash seems not being actively maintained anymore.
Do we want to change our hash implementation to FarmHash or other hash functions?

Not sure whether this is a good place for discussion, though.

[Mordante]

I'm not familiar with this code, but I find it concerning that the change causes no tests to fail.
I leave the review to somebody more familiar with this code.

In D134124#3798046, @oToToT wrote:

As mentioned in PR56606, CityHash seems not being actively maintained anymore.
Do we want to change our hash implementation to FarmHash or other hash functions?

I had a short look at FarmHash. Judging by the bugtracker it doesn't seem to be maintained either.

Not sure whether this is a good place for discussion, though.

#libcxx on Discord is the best place.

[oToToT]

I'm not familiar with this code, but I find it concerning that the change causes no tests to fail.

For the tests, it's also possible to add some hash quality tests.
To my knowledge, most of the hash algorithms would provide some kind of hash quality test to convince the user of its quality.
For example, CityHash and FarmHash both use SMHasher to ensure quality. (though it's also not actively maintained now)
Therefore, we can add the referenced test once we decided the algorithm.

[ldionne]

In D134124#3798046, @oToToT wrote:

As mentioned in PR56606, CityHash seems not being actively maintained anymore.
Do we want to change our hash implementation to FarmHash or other hash functions?

Not sure whether this is a good place for discussion, though.

I think this is really tricky to change, since we need to remain ABI compatible with code previously compiled. In other words, let's say an already compiled library creates an unordered_map with the old hash function and passes that to a program compiled with a new libc++ (with the new hashing function): the newly compiled program would have to be able to manipulate the old unordered_map. It being slower is probably reasonable, but it would have to function correctly.

We could introduce a new hashing algorithm in our unstable ABI, but I think we should still fix this issue with our existing CityHash algorithm.

@oToToT are you able to add a test that would fail with our current (buggy) implementation? https://github.com/llvm/llvm-project/issues/56606 seems to have a reproducer.

[oToToT]

Add basic test cases.

[oToToT]

Besides using a new hash algorithm, would we want to upgrade our CityHash version to v1.1 [1]?
The v1.1 version claims to have a better hash quality. (I haven't test it though)
And, IIUC, upgrading to v1.1 wouldn't change the ABI.

[1] https://github.com/google/cityhash/commit/0469694b4609253742bcd3008c0b3f3ba9fcd9ba

[ldionne]

In D134124#3801752, @oToToT wrote:

Besides using a new hash algorithm, would we want to upgrade our CityHash version to v1.1 [1]?
The v1.1 version claims to have a better hash quality. (I haven't test it though)
And, IIUC, upgrading to v1.1 wouldn't change the ABI.

[1] https://github.com/google/cityhash/commit/0469694b4609253742bcd3008c0b3f3ba9fcd9ba

Yes, that might be interesting, however we'd need to analyze whether we still find elements in an unordered_map when we change the hash in that way. Technically, changing the hash means that we'd violate http://eel.is/c++draft/hash.requirements#2: if one part of the program has the old CityHash implementation inlined and another part of the program has the new CityHash implementation, then all evaluations of h(k) might not yield the same result. We'd have to analyze whether that is benign UB or actual UB that's going to cause crashes and whatnot.

In all cases, we could find the best hash implementation out there and use that for ABI v2.

libcxx/test/libcxx/utilities/utility/__murmur2_or_cityhash.pass.cpp

10

I assume this test fails without your change?

Edit: I checked locally and it does, great.

[ldionne]

Oh, also, please make sure to fix the CI on AIX before committing this.

Thanks for the patch!

[oToToT]

Technically, changing the hash means that we'd violate http://eel.is/c++draft/hash.requirements#2

Yes, but actually we're also now changing the hash value in this patch. Thus, I think upgrading CityHash might not be that harmful if we can do it in the same release (i.e. libc++ 16.0.0).

On the other side, if we have some concerns about changing the hash value, maybe I also need to add some notice for this patch somewhere?

Oh, also, please make sure to fix the CI on AIX before committing this.

Hmm, I'm still thinking why this break the AIX CI. I'll fix it before I commit this.
Upd: Oh, I know the problem.

[oToToT]

Fix the endianess issue of the test.

[ldionne]

We ran into an issue while deploying this. This is technically an ABI break as we had noted. I realize I had underestimated the potential for this biting users -- we had users where a std::unordered_map was obtained from a different dylib compiled against old libc++ and they were unable to find a key in code built against new libc++ headers.

I think we'll need to guard this under ABI v2, unfortunately.

[oToToT]

@ldionne Am I right that I should revert this commit now?

I could guard this under ABI v2, too.
However, I think I could also do a little survey on hash functions and send a patch to discuss which one we should choose.
WDYT?

[ldionne]

In D134124#4116198, @oToToT wrote:

@ldionne Am I right that I should revert this commit now?

No, you're good. I'll handle everything, but thanks a lot for the suggestion.

I could guard this under ABI v2, too.
However, I think I could also do a little survey on hash functions and send a patch to discuss which one we should choose.
WDYT?

I agree, under ABI v2 we can select an arbitrary hash function, so let's select the best one. For the time being that will be the fixed CityHash, but we can use anything else. I suggest you do that on top of my patch that introduces the ABI v2 switch.

[oToToT]

Got it. Thanks for your work!

[ldionne]

I just opened https://reviews.llvm.org/D143688.

libcxx/include/__functional/hash.h

static _Size __hash_len_0_to_16(const char* __s, _Size __len)
     if (__len > 8) {
       const _Size __a = __loadword<_Size>(__s);
       const _Size __b = __loadword<_Size>(__s + __len - 8);
       return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b;
     }
     if (__len >= 4) {
       const uint32_t __a = __loadword<uint32_t>(__s);
       const uint32_t __b = __loadword<uint32_t>(__s + __len - 4);
-      return __hash_len_16(__len + (__a << 3), __b);
+      return __hash_len_16(__len + (static_cast<_Size>(__a) << 3), __b);
     }
     if (__len > 0) {
       const unsigned char __a = static_cast<unsigned char>(__s[0]);
       const unsigned char __b = static_cast<unsigned char>(__s[__len >> 1]);
       const unsigned char __c = static_cast<unsigned char>(__s[__len - 1]);
       const uint32_t __y = static_cast<uint32_t>(__a) +
                            (static_cast<uint32_t>(__b) << 8);
       const uint32_t __z = __len + (static_cast<uint32_t>(__c) << 2);

libcxx/test/libcxx/utilities/utility/__murmur2_or_cityhash.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// Test the CityHash implementation is correct.
+
+// UNSUPPORTED: c++03
+
+#include <cassert>
+#include <string>
+#include <utility>
+
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+#  define CHOOSE_BY_ENDIANESS(little, big) (little)
+#else
+#  define CHOOSE_BY_ENDIANESS(little, big) (big)
+#endif
+
+int main(int, char**) {
+  const std::pair<std::string, uint64_t> TestCases[] = {
+      {"abcdefgh", CHOOSE_BY_ENDIANESS(0x4382a8d0fe8edb17ULL, 0xca84e809bef16fbcULL)},
+      {"abcDefgh", CHOOSE_BY_ENDIANESS(0xecefb080a6854061ULL, 0xd7feb824250272dcULL)},
+      {"CityHash", CHOOSE_BY_ENDIANESS(0x169ea3aebf908d6dULL, 0xea8cef3ca6f6e368ULL)},
+      {"CitYHash", CHOOSE_BY_ENDIANESS(0xe18298a2760f09faULL, 0xf33a7700bb7a94a8ULL)},
+  };
+
+  std::__murmur2_or_cityhash<uint64_t> h64;
+  for (const auto& test_case : TestCases) {
+    assert(h64(test_case.first.data(), test_case.first.size()) == test_case.second);
+  }
+  return 0;
+}