[XRay][compiler-rt] - Dedupe xray event type strings from different addresses.

[kpw]

Summary

An immutable, statically allocated Vector class keeps track of the strings.
Sanitizer dependencies are used to avoid linkage problems for users.

[dberris]

lib/xray/xray_interface.cc

71

Couple of things:

• I don't think you need to use the fully qualified name for the type here, we're already in the __xray namespace.

• I would have thought we can initialise this lazily, on the first call to the type registration function.

lib/xray/xray_unique_string_table.cc

21–24

I suspect you may not actually need these, if you're already in the __xray namespace.

38

Do we not have this yet in the sanitizer_common/... library? And do we actually need this?

99

Consider using __sanitizer::InternalAlloc(...) then placement-new. That's a bit more friendly than calling new directly and relying on the implementation's allocator, which may not be the same as the allocator being used by the sanitizer libraries.

lib/xray/xray_unique_string_table.h

29

Probably use the sanitizer-local typedefs for some of these values -- say u16 instead of uint16_t, etc.

36

Do you really need to use the pimpl idiom?

[kpw]

Haven't made any changes yet. Thanks for the comments Dean.

lib/xray/xray_interface.cc

71

1. Good catch.
2. We can do it either way.

lib/xray/xray_unique_string_table.cc

38

1. I saw a murmur 2 implementation, but it was part of an implementation file.
2. I started out wanting to build a hashmap without resizing. Essentially it would grow up until a load factor with something layers like BlockLink. Collision would cause array-wrapped lookahead, and it grows by adding more layers. You can find a value in lookups ~= to the number of Block layers, and it would never have to resize. I decided this patch was "good enough" though.

99

Cool. Didn't know about that method until recently.

lib/xray/xray_unique_string_table.h

29

What's the difference between these? When and why should I prefer sanitizer types?

36

No, but the class must have a known size, which will uglify the header.

[dberris]

lib/xray/xray_unique_string_table.cc

38

We should be able to hoist out the existing implementation into a header in sanitizer_common/ if it's already in the sanitizer implementation(s). We can either do that in this change, or in a separate one which this will depend on.

I agree that for the purposes of implementing an efficient string intern table which only really gets looked up very infrequently (i.e. using registration of types) then we shouldn't be over-thinking this data structure/implementation for now.

lib/xray/CMakeLists.txt

 # Build for all components of the XRay runtime support library.
 
 # XRay runtime library implementation files.
 set(XRAY_SOURCES
   xray_init.cc
   xray_flags.cc
   xray_interface.cc
   xray_log_interface.cc
+  xray_unique_string_table.cc
   xray_utils.cc)
 
 # Implementation files for all XRay modes.
 set(XRAY_FDR_MODE_SOURCES
   xray_buffer_queue.cc
   xray_fdr_logging.cc)
 
 set(XRAY_BASIC_MODE_SOURCES

lib/xray/tests/unit/CMakeLists.txt

 add_xray_unittest(XRayBufferQueueTest SOURCES
   buffer_queue_test.cc xray_unit_test_main.cc)
 add_xray_unittest(XRayFDRLoggingTest SOURCES
   fdr_logging_test.cc xray_unit_test_main.cc)
+add_xray_unittest(XRayUniqueStringTableTest SOURCES
+  unique_string_table_test.cc xray_unit_test_main.cc)

lib/xray/tests/unit/unique_string_table_test.cc

+//===-- unique_string_table_test.cc ---------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a function call tracing system.
+//
+//===----------------------------------------------------------------------===//
+
+#include "xray/xray_interface.h"
+#include "xray_unique_string_table.h"
+#include "gtest/gtest.h"
+
+static __xray::UniqueStringTable *Strings = new __xray::UniqueStringTable();
+
+static constexpr char HelloHello[] = "Hello Hello";
+
+TEST(UniqueStringTableTest, Register) {
+  uint16_t Hello = Strings->AddOrLookupValue("Hello", 5);
+  uint16_t Different = Strings->AddOrLookupValue("Goodbye", 7);
+  EXPECT_NE(Hello, Different) << "Different strings should be different";
+  uint16_t HelloAgain = Strings->AddOrLookupValue("Hello", 5);
+  EXPECT_EQ(HelloAgain, Hello) << "Should be same";
+  uint16_t FromCharArray = Strings->AddOrLookupValue(HelloHello, 5);
+  EXPECT_EQ(FromCharArray, Hello) << "Should be same";
+  uint16_t FromCharArraySubstring = Strings->AddOrLookupValue(HelloHello, 6);
+  EXPECT_NE(FromCharArraySubstring, Hello) << "Should be different";
+  uint16_t FromCharArrayOffset = Strings->AddOrLookupValue(HelloHello + 6, 5);
+  EXPECT_EQ(FromCharArrayOffset, Hello) << "Should be same";
+  uint16_t Aloha = Strings->AddOrLookupValue("Aloha", 5);
+  EXPECT_NE(Hello, Aloha) << "Should be different";
+  EXPECT_NE(Different, Aloha) << "Should be different";
+}
+
+TEST(UniqueStringTableTest, ThroughPublicInterface) {
+  uint16_t One = __xray_register_event_type("One");
+  uint16_t Two = __xray_register_event_type("2");
+  uint16_t Million = __xray_register_event_type("One Million");
+  uint16_t OneAgain = __xray_register_event_type("One");
+  uint16_t MillionAgain = __xray_register_event_type("One Million");
+  EXPECT_EQ(One, OneAgain) << "Equal types give different tags";
+  EXPECT_EQ(Million, MillionAgain) << "Bad Accounting";
+  EXPECT_NE(One, Two) << "1 != 2";
+  EXPECT_NE(One, Million) << "1 != 1000000";
+  EXPECT_NE(Two, Million) << "2 != 1000000";
+}

lib/xray/xray_interface.cc

 
 #include <cstdint>
 #include <cstdio>
 #include <errno.h>
 #include <limits>
 #include <string.h>
 #include <sys/mman.h>
 
-#include "sanitizer_common/sanitizer_addrhashmap.h"
 #include "sanitizer_common/sanitizer_common.h"
+#include "sanitizer_common/sanitizer_libc.h"
 
 #include "xray_defs.h"
 #include "xray_flags.h"
+#include "xray_unique_string_table.h"
 
 extern __sanitizer::SpinMutex XRayInstrMapMutex;
 extern __sanitizer::atomic_uint8_t XRayInitialized;
 extern __xray::XRaySledMap XRayInstrMap;
 
 namespace __xray {
 
 #if defined(__x86_64__)

 
 // This is the function to call when we encounter a typed event log call.
 __sanitizer::atomic_uintptr_t XRayPatchedTypedEvent{0};
 
 // This is the global status to determine whether we are currently
 // patching/unpatching.
 __sanitizer::atomic_uint8_t XRayPatching{0};
 
-struct TypeDescription {
-  uint32_t type_id;
-  std::size_t description_string_length;
-};
-
-using TypeDescriptorMapType = __sanitizer::AddrHashMap<TypeDescription, 11>;
-// An address map from immutable descriptors to type ids.
-TypeDescriptorMapType TypeDescriptorAddressMap{};
-
-__sanitizer::atomic_uint32_t TypeEventDescriptorCounter{0};
+// Keep track of unique strings registered as type ids.
+::__xray::UniqueStringTable *const TypeEventTable = new UniqueStringTable();
 
 // MProtectHelper is an RAII wrapper for calls to mprotect(...) that will
 // undo any successful mprotect(...) changes. This is used to make a page
 // writeable and executable, and upon destruction if it was successful in
 // doing so returns the page into a read-only and executable page.
 //
 // This is only used specifically for runtime-patching of the XRay
 // instrumentation points. This assumes that the executable pages are

 }
 
 int __xray_remove_typedevent_handler() noexcept XRAY_NEVER_INSTRUMENT {
   return __xray_set_typedevent_handler(nullptr);
 }
 
 uint16_t __xray_register_event_type(
     const char *const event_type) noexcept XRAY_NEVER_INSTRUMENT {
-  TypeDescriptorMapType::Handle h(&TypeDescriptorAddressMap, (uptr)event_type);
-  if (h.created()) {
-    h->type_id = __sanitizer::atomic_fetch_add(
-        &TypeEventDescriptorCounter, 1, __sanitizer::memory_order_acq_rel);
-    h->description_string_length = strnlen(event_type, 1024);
-  }
-  return h->type_id;
+  auto length = __sanitizer::internal_strnlen(event_type, 1024);
+  // TODO: The current API contract is that the pointer registered must be
+  // valid for the length of the program. This may change with DSO support.
+  // We can copy the string to a buffer if we decide to pay that cost.
+  return TypeEventTable->AddOrLookupValue(event_type, length);
 }
 
 XRayPatchingStatus __xray_patch() XRAY_NEVER_INSTRUMENT {
   return controlPatching(true);
 }
 
 XRayPatchingStatus __xray_unpatch() XRAY_NEVER_INSTRUMENT {
   return controlPatching(false);

lib/xray/xray_unique_string_table.h

+//===-- xray_unique_string_table.h ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// Defines a table of deduped strings and their unique identifiers.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef XRAY_UNIQUE_STRING_TABLE_H
+#define XRAY_UNIQUE_STRING_TABLE_H
+
+#include <cstddef>
+#include <cstdint>
+namespace __xray {
+
+// Forward declare storage
+struct UniqueStringTableImpl;
+
+class UniqueStringTable {
+public:
+  UniqueStringTable();
+  uint16_t AddOrLookupValue(const char *const content, std::size_t length);
+  // Meant to be constructed once as a static storage duration.
+  ~UniqueStringTable() = delete;
+  UniqueStringTable(const UniqueStringTable &) = delete;
+  UniqueStringTable &operator=(const UniqueStringTable &) = delete;
+
+private:
+  UniqueStringTableImpl *impl_;
+};
+
+} // namespace __xray
+
+#endif // XRAY_UNIQUE_STRING_TABLE_H

lib/xray/xray_unique_string_table.cc

+//===-- xray_unique_string_table.cc -----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of XRay, a dynamic runtime instrumentation system.
+//
+// Defines a table of deduped strings and their unique identifiers.
+//
+//===----------------------------------------------------------------------===//
+
+#include "xray_unique_string_table.h"
+#include "sanitizer_common/sanitizer_libc.h"
+#include "sanitizer_common/sanitizer_mutex.h"
+#include "sanitizer_common/sanitizer_vector.h"
+
+using __sanitizer::internal_strncmp;
+using __sanitizer::SpinMutex;
+using __sanitizer::SpinMutexLock;
+using __sanitizer::Vector;
+
+namespace __xray {
+
+namespace {
+
+struct HashNode {
+  const char *const content;
+  const std::size_t length;
+  const uint32_t hash;
+};
+
+// Murmur3's 32 bit variant. strncmp for each node in linear search felt wrong,
+// even though the intended use cases are not high cardinality.
+uint32_t Murmur3_32(const char *key, std::size_t length) {
+  static constexpr uint32_t seed = 0x31415926;
+  static constexpr uint32_t c1 = 0xcc9e2d51;
+  static constexpr uint32_t c2 = 0x1b873593;
+  static constexpr uint32_t m = 5;
+  static constexpr uint32_t n = 0xe6546b64;
+
+  uint32_t hash = seed;
+  const uint8_t *key_width_8 = reinterpret_cast<const uint8_t *>(key);
+  if (length > 3) {
+    const uint32_t *key_width_32 = reinterpret_cast<const uint32_t *>(key);
+    std::size_t len_width_32 = length >> 2;
+    do {
+      uint32_t k = *key_width_32++;
+      k *= c1;
+      k = (k << 15) | (k >> 17);
+      k *= c2;
+      hash ^= k;
+      hash = (hash << 13) | (hash >> 19);
+      hash = (hash * m) + n;
+    } while (--len_width_32);
+    key_width_8 = reinterpret_cast<const uint8_t *>(key_width_32);
+  }
+  if (length & 3) {
+    std::size_t i = length & 3;
+    uint32_t remaining_bytes = 0;
+    // shift values into a uint32
+    switch (i) {
+    case 3:
+      remaining_bytes |= key_width_8[2];
+      remaining_bytes <<= 8;
+    case 2:
+      remaining_bytes |= key_width_8[1];
+      remaining_bytes <<= 8;
+    case 1:
+      remaining_bytes |= key_width_8[0];
+    }
+    // multiply, rotate, multiply the final block.
+    remaining_bytes *= c1;
+    remaining_bytes = (remaining_bytes << 15) | (remaining_bytes >> 17);
+    remaining_bytes *= c2;
+    hash ^= remaining_bytes;
+  }
+
+  // Final avalanche stage.
+  hash ^= length;
+  hash ^= (hash >> 16);
+  hash *= 0x85ebca6b;
+  hash ^= (hash >> 13);
+  hash *= 0xc2b2ae35;
+  hash ^= (hash >> 16);
+  return hash;
+}
+
+} // namespace
+
+struct UniqueStringTableImpl {
+  Vector<HashNode> Storage{};
+  SpinMutex insertion_mutex{};
+};
+
+UniqueStringTable::UniqueStringTable() : impl_(new UniqueStringTableImpl()) {}
+
+uint16_t UniqueStringTable::AddOrLookupValue(const char *const content,
+                                             std::size_t length) {
+  uint32_t HashValue = Murmur3_32(content, length);
+  // Linear search storage.
+  std::size_t PreInsertSize = 0;
+  for (; PreInsertSize < impl_->Storage.Size(); ++PreInsertSize) {
+    const HashNode &val = impl_->Storage[PreInsertSize];
+    if (val.hash == HashValue && val.length == length &&
+        internal_strncmp(content, val.content, length) == 0)
+      return PreInsertSize;
+  }
+  SpinMutexLock Lock(&impl_->insertion_mutex);
+  std::size_t SizeAfterLock = impl_->Storage.Size();
+  // Search anything that may have been added after we acquire the lock.
+  for (std::size_t i = PreInsertSize; i < SizeAfterLock; ++i) {
+    const HashNode &Val = impl_->Storage[i];
+    if (Val.hash == HashValue && Val.length == length &&
+        internal_strncmp(content, Val.content, length) == 0)
+      return i;
+  }
+  HashNode Node{content, length, HashValue};
+  impl_->Storage.PushBack(Node);
+  return impl_->Storage.Size() - 1;
+}
+
+} // namespace __xray