[libc++] Increase readability of typeinfo comparison of ARM64

[ldionne]

Summary

We wasted a good deal of time trying to figure out whether our implementation was correct. In the end, it was, but it wasn't so easy to determine. This patch dumbs down the implementation and improves the documentation to make it easier to validate.

See https://lists.llvm.org/pipermail/libcxx-dev/2020-December/001060.html.

[ldionne]

This is a WIP:

1. I'm not sure whether this change is actually correct, or whether we are mis-interpreting the ABI and the previous implementation was actually correct.
2. I don't know how to test this yet.

I created a patch because I wanted to avoid forgetting about this message on the mailing list forever. I'll need to do some investigation before I can make progress on this.

[rjmccall]

You're misinterpreting the condition. The "is non-unique" bit says that the RTTI is non-unique and thus its identity is string-based; otherwise it is pointer-based. A uniquely-emitted type is never the same as a non-uniquely-emitted type.

Usually people who are having problems with this are messing up type visibility so that it's inconsistent between libraries.

[ldionne]

Updating according to a discussion with John McCall

[smeenai]

libcxx/include/typeinfo

158–162

This reads a little confusingly, because the "Otherwise, if at least one of the RTTIs can't be assumed to be unique bit" makes you think that the case where on RTTI is unique and one isn't will do the deep string comparison, but then the next sentence changes the interpretation of that case. Maybe say "if both RTTIs can't be assumed to be unique", since the last sentence already handles the non-unique + unique case?

163–169

Thanks for explaining the motivation of the design and when it kicks in. I'd been casually curious about this before, and it's a neat design :)

257–258

I don't understand this. My reading of the two parameter __is_type_name_unique function was that it would return true if either typeinfo was unique, and that's also what you're doing in line 266 below. Over here, if both typeinfos are unique, this condition won't kick in, so wouldn't we incorrectly fall through to the strcmp below?

Also a nit: LLVM code style recommends not using an else after a return: https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return. I don't know if libc++ normally does this differently.

[rjmccall]

libcxx/include/typeinfo

151

"compiler"

162

This is not correct. We should only perform a string comparison if *both* RTTIs are non-unique. I still don't think this is a runtime bug.

[ldionne]

Address comments.

libcxx/include/typeinfo

158–162

Actually, that isn't what I meant to write. I meant:

When comparing type_infos, if both RTTIs can be assumed to be unique, it suffices to compare their addresses. If both the RTTIs can't be assumed to be unique, we must perform a deep string comparison of the type names. However, if one of the RTTIs is guaranteed unique and the other one isn't, then both RTTIs are necessarily not to be considered equal.

Thanks for catching that!

[curdeius]

libcxx/include/typeinfo

258–262

To be consistent with __lt and so that it reads easier, I propose negating the condition.
Unless you think that the codegen can be worse.

[ldionne]

Address Marek's comment. Turns out this patch is basically a NFC, just making
the code dumber and hence easier to follow.

[curdeius]

LGTM. You might want add "NFC" to the commit message.

[rjmccall]

LGTM

[rsmith]

libcxx/include/typeinfo

265–269

This is not an ordering relation. For example, we could have non-unique C < unique B < non-unique A < non-unique C, where the first and second comparisons are address comparisons, and the third comparison is a string comparison.

I think perhaps something like this would work:

bool __lhs_unique = __is_type_name_unique(__lhs);
if (__lhs_unique != __is_type_name_unique(__rhs))
  return __lhs_unique;
if (__lhs_unique)
  return __lhs < __rhs;
return __builtin_strcmp(__type_name_to_string(__lhs), __type_name_to_string(__rhs)) < 0;

(That is: order all unique typeinfos before all non-unique ones, then order unique typeinfos by pointer and non-unique ones by string.)

[rjmccall]

Wow, yes, you're absolutely right. I think we can probably get away with fixing that without worrying about ODR problems because type_info ordered comparison is so uncommon.

libcxx/include/typeinfo

 // ========================================================================== //
 //                           Implementations
 // ========================================================================== //
 // ------------------------------------------------------------------------- //
 //                               Unique
 //               (_LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION = 1)
 // ------------------------------------------------------------------------- //
 // This implementation of type_info assumes a unique copy of the RTTI for a
-// given type inside a program. This is a valid assumption when abiding to
+// given type inside a program. This is a valid assumption when abiding to the
 // Itanium ABI (http://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-components).
 // Under this assumption, we can always compare the addresses of the type names
 // to implement equality-comparison of type_infos instead of having to perform
 // a deep string comparison.
 // -------------------------------------------------------------------------- //
 //                             NonUnique
 //               (_LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION = 2)
 // -------------------------------------------------------------------------- //
 // This implementation of type_info does not assume there is always a unique
 // copy of the RTTI for a given type inside a program. For various reasons
 // the linker may have failed to merge every copy of a types RTTI
 // (For example: -Bsymbolic or llvm.org/PR37398). Under this assumption, two
 // type_infos are equal if their addresses are equal or if a deep string
 // comparison is equal.
 // -------------------------------------------------------------------------- //
 //                          NonUniqueARMRTTIBit
 //               (_LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION = 3)
 // -------------------------------------------------------------------------- //
+// This implementation is specific to ARM64 on Apple platforms.
+//
 // This implementation of type_info does not assume always a unique copy of
-// the RTTI for a given type inside a program. It packs the pointer to the
-// type name into a uintptr_t and reserves the high bit of that pointer (which
-// is assumed to be free for use under the ABI in use) to represent whether
-// that specific copy of the RTTI can be assumed unique inside the program.
-// To implement equality-comparison of type_infos, we check whether BOTH
-// type_infos are guaranteed unique, and if so, we simply compare the addresses
-// of their type names instead of doing a deep string comparison, which is
-// faster. If at least one of the type_infos can't guarantee uniqueness, we
-// have no choice but to fall back to a deep string comparison.
+// the RTTI for a given type inside a program. When constructing the type_info,
+// the compiler packs the pointer to the type name into a uintptr_t and reserves
+// the high bit of that pointer, which is assumed to be free for use under that
+// ABI. If that high bit is set, that specific copy of the RTTI can't be assumed
+// to be unique within the program. If the high bit is unset, then the RTTI can
+// be assumed to be unique within the program.
 //
-// This implementation is specific to ARM64 on Apple platforms.
+// When comparing type_infos, if both RTTIs can be assumed to be unique, it
+// suffices to compare their addresses. If both the RTTIs can't be assumed to
+// be unique, we must perform a deep string comparison of the type names.
+// However, if one of the RTTIs is guaranteed unique and the other one isn't,
+// then both RTTIs are necessarily not to be considered equal.
 //
-// Note that the compiler is the one setting (or unsetting) the high bit of
-// the pointer when it constructs the type_info, depending on whether it can
-// guarantee uniqueness for that specific type_info.
+// The intent of this design is to remove the need for weak symbols. Specifically,
+// if a type would normally have a default-visibility RTTI emitted as a weak
+// symbol, it is given hidden visibility instead and the non-unique bit is set.
+// Otherwise, types declared with hidden visibility are always considered to have
+// a unique RTTI: the RTTI is emitted with linkonce_odr linkage and is assumed
+// to be deduplicated by the linker within the linked image. Across linked image
+// boundaries, such types are thus considered different types.
 
 // This value can be overriden in the __config_site. When it's not overriden,
 // we pick a default implementation based on the platform here.
 #ifndef _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION
 
   // Windows binaries can't merge typeinfos, so use the NonUnique implementation.
 # ifdef _LIBCPP_OBJECT_FORMAT_COFF
 #   define _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION 2
struct __non_unique_arm_rtti_bit_impl {
     static size_t __hash(__type_name_t __v) _NOEXCEPT {
       if (__is_type_name_unique(__v))
         return reinterpret_cast<size_t>(__v);
       return __non_unique_impl::__hash(__type_name_to_string(__v));
     }
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
     static bool __eq(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
       if (__lhs == __rhs)
         return true;
-      if (__is_type_name_unique(__lhs, __rhs))
-        return false;
+      if (!__is_type_name_unique(__lhs) && !__is_type_name_unique(__rhs))
         return __builtin_strcmp(__type_name_to_string(__lhs), __type_name_to_string(__rhs)) == 0;
+      // Either both are unique and have a different address, or one of them
+      // is unique and the other one isn't. In both cases they are unequal.
+      return false;
     }
     _LIBCPP_INLINE_VISIBILITY _LIBCPP_ALWAYS_INLINE
     static bool __lt(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
-      if (__is_type_name_unique(__lhs, __rhs))
+      if (__is_type_name_unique(__lhs) || __is_type_name_unique(__rhs))
         return __lhs < __rhs;
       return __builtin_strcmp(__type_name_to_string(__lhs), __type_name_to_string(__rhs)) < 0;
     }
 
    private:
     // The unique bit is the top bit. It is expected that __type_name_t is 64 bits when
     // this implementation is actually used.
     typedef integral_constant<__type_name_t,
       (1ULL << ((__CHAR_BIT__ * sizeof(__type_name_t)) - 1))> __non_unique_rtti_bit;
 
     _LIBCPP_INLINE_VISIBILITY
     static bool __is_type_name_unique(__type_name_t __lhs) _NOEXCEPT {
       return !(__lhs & __non_unique_rtti_bit::value);
     }
-    _LIBCPP_INLINE_VISIBILITY
-    static bool __is_type_name_unique(__type_name_t __lhs, __type_name_t __rhs) _NOEXCEPT {
-      return !((__lhs & __rhs) & __non_unique_rtti_bit::value);
-    }
   };
 
   typedef
 #if _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION == 1
     __unique_impl
 #elif _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION == 2
     __non_unique_impl
 #elif _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION == 3