[Reland][ADT][ConcurrentHashTable] adapt ConcurrentHashTable and its users to LLVM_ENABLE_THREADS=0 mode.

[avl]

Summary

This patch hides thread specific handling under LLVM_ENABLE_THREADS guard.
It also removes usages of thread_local variables, since it has a weak
support on some platforms. Instead, the patch uses single mutex for locking
allocator. That may be replaced with more effective allocator later.
f.e. D142318

[SeanP]

Thanks for the update. I tried this on z/OS and it is working.

[avl]

Thank you for the review.

[vitalybuka]

This is memory leak now https://lab.llvm.org/buildbot/#/builders/5/builds/32731

[avl]

cure buildbot failure. refactor.

[avl]

Original patch broke buildbots with memory leak. This new version removes usages of thread_local variables and adds checks for LLVM_ENABLE_THREADS

[JDevlieghere]

It's a bit unfortunate that we have to sprinkle LLVM_ENABLE_THREADS throughout the code, but not enough that I think it's worth doing anything fancy like subclassing (I think it would just make things worse). LGTM.

llvm/include/llvm/DWARFLinkerParallel/StringPool.h

25

Why not just StringAllocator. Do we expect to have a more "complex" allocator down the line?

[avl]

llvm/include/llvm/DWARFLinkerParallel/StringPool.h

25

I am planning to use allocator from D142318 later.

Will rename SimpleStringAllocator to StringAllocator as suggested.

[SeanP]

LGTM

I tested this patch on z/os. Everything is working. Thanks

[avl]

Thanks!

llvm/include/llvm/ADT/ConcurrentHashtable.h

public:
   /// \returns entry and "true" if an entry is just inserted or
   /// "false" if an entry already exists.
   std::pair<KeyDataTy *, bool> insert(const KeyTy &NewValue) {
     // Calculate bucket index.
     uint64_t Hash = Info::getHashValue(NewValue);
     Bucket &CurBucket = BucketsArray[getBucketIdx(Hash)];
     uint32_t ExtHashBits = getExtHashBits(Hash);
 
+#if LLVM_ENABLE_THREADS
     // Lock bucket.
     CurBucket.Guard.lock();
+#endif
 
     HashesPtr BucketHashes = CurBucket.Hashes;
     DataPtr BucketEntries = CurBucket.Entries;
     uint32_t CurEntryIdx = getStartIdx(ExtHashBits, CurBucket.Size);
 
     while (true) {
       uint32_t CurEntryHashBits = BucketHashes[CurEntryIdx];
 
       if (CurEntryHashBits == 0 && BucketEntries[CurEntryIdx] == nullptr) {
         // Found empty slot. Insert data.
         KeyDataTy *NewData = Info::create(NewValue, MultiThreadAllocator);
         BucketEntries[CurEntryIdx] = NewData;
         BucketHashes[CurEntryIdx] = ExtHashBits;
 
         CurBucket.NumberOfEntries++;
         RehashBucket(CurBucket);
 
+#if LLVM_ENABLE_THREADS
         CurBucket.Guard.unlock();
+#endif
 
         return {NewData, true};
       }
 
       if (CurEntryHashBits == ExtHashBits) {
         // Hash matched. Check value for equality.
         KeyDataTy *EntryData = BucketEntries[CurEntryIdx];
         if (Info::isEqual(Info::getKey(*EntryData), NewValue)) {
           // Already existed entry matched with inserted data is found.
+#if LLVM_ENABLE_THREADS
           CurBucket.Guard.unlock();
+#endif
 
           return {EntryData, false};
         }
       }
 
       CurEntryIdx++;
       CurEntryIdx &= (CurBucket.Size - 1);
     }
struct Bucket {
     uint32_t NumberOfEntries = 0;
 
     // Hashes for [Size] entries.
     HashesPtr Hashes = nullptr;
 
     // [Size] entries.
     DataPtr Entries = nullptr;
 
+#if LLVM_ENABLE_THREADS
     // Mutex for this bucket.
     std::mutex Guard;
+#endif
   };
 
   // Reallocate and rehash bucket if this is full enough.
   void RehashBucket(Bucket &CurBucket) {
     assert((CurBucket.Size > 0) && "Uninitialised bucket");
     if (CurBucket.NumberOfEntries < CurBucket.Size * 0.9)
       return;
 

llvm/include/llvm/DWARFLinkerParallel/StringPool.h

 
 namespace llvm {
 namespace dwarflinker_parallel {
 
 /// StringEntry keeps data of the string: the length, external offset
 /// and a string body which is placed right after StringEntry.
 using StringEntry = StringMapEntry<DwarfStringPoolEntry *>;
 
-class PerThreadStringAllocator
-    : public AllocatorBase<PerThreadStringAllocator> {
+class StringAllocator : public AllocatorBase<StringAllocator> {
 public:
   inline LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t Size,
                                                        size_t Alignment) {
-    return ThreadLocalAllocator.Allocate(Size, Align(Alignment));
+#if LLVM_ENABLE_THREADS
+    std::lock_guard<std::mutex> Guard(AllocatorMutex);
+#endif
+
+    return Allocator.Allocate(Size, Align(Alignment));
   }
 
   // Pull in base class overloads.
-  using AllocatorBase<PerThreadStringAllocator>::Allocate;
+  using AllocatorBase<StringAllocator>::Allocate;
 
 private:
-  static thread_local BumpPtrAllocator ThreadLocalAllocator;
+#if LLVM_ENABLE_THREADS
+  std::mutex AllocatorMutex;
+#endif
+
+  BumpPtrAllocator Allocator;
 };
 
 class StringPoolEntryInfo {
 public:
   /// \returns Hash value for the specified \p Key.
   static inline uint64_t getHashValue(const StringRef &Key) {
     return xxHash64(Key);
   }
 
   /// \returns true if both \p LHS and \p RHS are equal.
   static inline bool isEqual(const StringRef &LHS, const StringRef &RHS) {
     return LHS == RHS;
   }
 
   /// \returns key for the specified \p KeyData.
   static inline StringRef getKey(const StringEntry &KeyData) {
     return KeyData.getKey();
   }
 
   /// \returns newly created object of KeyDataTy type.
   static inline StringEntry *create(const StringRef &Key,
-                                    PerThreadStringAllocator &Allocator) {
+                                    StringAllocator &Allocator) {
     return StringEntry::create(Key, Allocator);
   }
 };
 
-class StringPool : public ConcurrentHashTableByPtr<StringRef, StringEntry,
-                                                   PerThreadStringAllocator,
-                                                   StringPoolEntryInfo> {
+class StringPool
+    : public ConcurrentHashTableByPtr<StringRef, StringEntry, StringAllocator,
 public:
   StringPool()
-      : ConcurrentHashTableByPtr<StringRef, StringEntry,
-                                 PerThreadStringAllocator, StringPoolEntryInfo>(
-            Allocator) {}
+      : ConcurrentHashTableByPtr<StringRef, StringEntry, StringAllocator,
+                                 StringPoolEntryInfo>(Allocator) {}
 
   StringPool(size_t InitialSize)
-      : ConcurrentHashTableByPtr<StringRef, StringEntry,
-                                 PerThreadStringAllocator, StringPoolEntryInfo>(
-            Allocator, InitialSize) {}
+      : ConcurrentHashTableByPtr<StringRef, StringEntry, StringAllocator,
+                                 StringPoolEntryInfo>(Allocator, InitialSize) {}
 
-  PerThreadStringAllocator &getAllocatorRef() { return Allocator; }
+  StringAllocator &getAllocatorRef() { return Allocator; }
 
 private:
-  PerThreadStringAllocator Allocator;
+  StringAllocator Allocator;
 };
 
 } // end of namespace dwarflinker_parallel
 } // end namespace llvm
 
 #endif // LLVM_DWARFLINKERPARALLEL_STRINGPOOL_H

llvm/lib/DWARFLinkerParallel/StringPool.cpp

 //=== StringPool.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
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DWARFLinkerParallel/StringPool.h"
-
-thread_local llvm::BumpPtrAllocator
-    llvm::dwarflinker_parallel::PerThreadStringAllocator::ThreadLocalAllocator;

llvm/unittests/ADT/ConcurrentHashtableTest.cpp

 
 protected:
   String(const std::string &Num) { Data += Num; }
 
   std::string Data;
   std::array<char, 0x20> ExtraData;
 };
 
-static thread_local BumpPtrAllocator ThreadLocalAllocator;
-class PerThreadAllocator : public AllocatorBase<PerThreadAllocator> {
+class SimpleAllocator : public AllocatorBase<SimpleAllocator> {
 public:
   inline LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t Size,
                                                        size_t Alignment) {
-    return ThreadLocalAllocator.Allocate(Size, Align(Alignment));
-  }
-  inline size_t getBytesAllocated() const {
-    return ThreadLocalAllocator.getBytesAllocated();
+#if LLVM_ENABLE_THREADS
+    std::lock_guard<std::mutex> Guard(AllocatorMutex);
+#endif
+
+    return Allocator.Allocate(Size, Align(Alignment));
+  }
+  inline size_t getBytesAllocated() {
+#if LLVM_ENABLE_THREADS
+    std::lock_guard<std::mutex> Guard(AllocatorMutex);
+#endif
+
+    return Allocator.getBytesAllocated();
   }
 
   // Pull in base class overloads.
-  using AllocatorBase<PerThreadAllocator>::Allocate;
+  using AllocatorBase<SimpleAllocator>::Allocate;
+
+protected:
+#if LLVM_ENABLE_THREADS
+  std::mutex AllocatorMutex;
+#endif
+  BumpPtrAllocator Allocator;
 } Allocator;
 
 TEST(ConcurrentHashTableTest, AddStringEntries) {
   ConcurrentHashTableByPtr<
-      std::string, String, PerThreadAllocator,
-      ConcurrentHashTableInfoByPtr<std::string, String, PerThreadAllocator>>
+      std::string, String, SimpleAllocator,
+      ConcurrentHashTableInfoByPtr<std::string, String, SimpleAllocator>>
       HashTable(Allocator, 10);
 
   size_t AllocatedBytesAtStart = Allocator.getBytesAllocated();
   std::pair<String *, bool> res1 = HashTable.insert("1");
   // Check entry is inserted.
   EXPECT_TRUE(res1.first->getKey() == "1");
   EXPECT_TRUE(res1.second);
 
TEST(ConcurrentHashTableTest, AddStringEntries) {
 
   EXPECT_TRUE(StatisticString.find("Overall number of entries = 3\n") !=
               std::string::npos);
 }
 
 TEST(ConcurrentHashTableTest, AddStringMultiplueEntries) {
   const size_t NumElements = 10000;
   ConcurrentHashTableByPtr<
-      std::string, String, PerThreadAllocator,
-      ConcurrentHashTableInfoByPtr<std::string, String, PerThreadAllocator>>
+      std::string, String, SimpleAllocator,
+      ConcurrentHashTableInfoByPtr<std::string, String, SimpleAllocator>>
       HashTable(Allocator);
 
   // Check insertion.
   for (size_t I = 0; I < NumElements; I++) {
     size_t AllocatedBytesAtStart = Allocator.getBytesAllocated();
     std::string StringForElement = formatv("{0}", I);
     std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
     EXPECT_TRUE(Entry.second);
TEST(ConcurrentHashTableTest, AddStringMultiplueEntries) {
   EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000\n") !=
               std::string::npos);
 }
 
 TEST(ConcurrentHashTableTest, AddStringMultiplueEntriesWithResize) {
   // Number of elements exceeds original size, thus hashtable should be resized.
   const size_t NumElements = 20000;
   ConcurrentHashTableByPtr<
-      std::string, String, PerThreadAllocator,
-      ConcurrentHashTableInfoByPtr<std::string, String, PerThreadAllocator>>
+      std::string, String, SimpleAllocator,
+      ConcurrentHashTableInfoByPtr<std::string, String, SimpleAllocator>>
       HashTable(Allocator, 100);
 
   // Check insertion.
   for (size_t I = 0; I < NumElements; I++) {
     size_t AllocatedBytesAtStart = Allocator.getBytesAllocated();
     std::string StringForElement = formatv("{0} {1}", I, I + 100);
     std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
     EXPECT_TRUE(Entry.second);
TEST(ConcurrentHashTableTest, AddStringMultiplueEntriesWithResize) {
   // inserted.
   EXPECT_TRUE(StatisticString.find("Overall number of entries = 20000\n") !=
               std::string::npos);
 }
 
 TEST(ConcurrentHashTableTest, AddStringEntriesParallel) {
   const size_t NumElements = 10000;
   ConcurrentHashTableByPtr<
-      std::string, String, PerThreadAllocator,
-      ConcurrentHashTableInfoByPtr<std::string, String, PerThreadAllocator>>
+      std::string, String, SimpleAllocator,
+      ConcurrentHashTableInfoByPtr<std::string, String, SimpleAllocator>>
       HashTable(Allocator);
 
   // Check parallel insertion.
   parallelFor(0, NumElements, [&](size_t I) {
     size_t AllocatedBytesAtStart = Allocator.getBytesAllocated();
     std::string StringForElement = formatv("{0}", I);
     std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
     EXPECT_TRUE(Entry.second);
TEST(ConcurrentHashTableTest, AddStringEntriesParallel) {
   // inserted.
   EXPECT_TRUE(StatisticString.find("Overall number of entries = 10000\n") !=
               std::string::npos);
 }
 
 TEST(ConcurrentHashTableTest, AddStringEntriesParallelWithResize) {
   const size_t NumElements = 20000;
   ConcurrentHashTableByPtr<
-      std::string, String, PerThreadAllocator,
-      ConcurrentHashTableInfoByPtr<std::string, String, PerThreadAllocator>>
+      std::string, String, SimpleAllocator,
+      ConcurrentHashTableInfoByPtr<std::string, String, SimpleAllocator>>
       HashTable(Allocator, 100);
 
   // Check parallel insertion.
   parallelFor(0, NumElements, [&](size_t I) {
     size_t AllocatedBytesAtStart = Allocator.getBytesAllocated();
     std::string StringForElement = formatv("{0}", I);
     std::pair<String *, bool> Entry = HashTable.insert(StringForElement);
     EXPECT_TRUE(Entry.second);