Use size_t, instead of unsigned, to represnt StringMapEntry length and alignment.

[mattd]

Summary

The original code was accessing bad data in the pathological case of
int foo[1024*1024*1024] which just happens to represent 2^32 bytes.
This was generating a bad unsigned size variable in StringMap that
was then used for memory allocation.

It turns out that StringMap's allocator was using unsigned values
when the size() operator in the class returns size_t. It seems safest,
just to use size_t when dealing with strings and their lengths.

[davide]

Matt, you should consider writing an unittest for this change.

[mattd]

• Added a unittest to StringMapTests.
• Changed a use of unsigned to be size_t, when constructing a StringMapEntry.

[mattd]

ping

[mattd]

Ping.

[mattd]

Ping :)

[aaron.ballman]

FWIW, this LGTM, but you should wait for independent confirmation. Adding @dblaikie in case he has opinions.

[dblaikie]

Sure, seems plausible

[mattd]

Thanks @aaron.ballman @dblaikie. Is there anything else needed for commit approval?

[aaron.ballman]

In D40684#973373, @mattd wrote:

Thanks @aaron.ballman @dblaikie. Is there anything else needed for commit approval?

Nope, you're good to commit now. Do you need someone to commit on your behalf?

[mattd]

I do need someone to commit this on my behalf. Thanks!

[aaron.ballman]

I've committed in r322305.

[mattd]

Great! Thanks!

[aaron.ballman]

In D40684#973559, @mattd wrote:

Great! Thanks!

You're welcome! If there are any issues with the commit, I'll let you know. Otherwise, you should be fine to manually close this review.

[mattd]

Changes have been committed at r322305.

include/llvm/ADT/StringMap.h

 namespace llvm {
 
 template<typename ValueTy> class StringMapConstIterator;
 template<typename ValueTy> class StringMapIterator;
 template<typename ValueTy> class StringMapKeyIterator;
 
 /// StringMapEntryBase - Shared base class of StringMapEntry instances.
 class StringMapEntryBase {
-  unsigned StrLen;
+  size_t StrLen;
 
 public:
-  explicit StringMapEntryBase(unsigned Len) : StrLen(Len) {}
+  explicit StringMapEntryBase(size_t Len) : StrLen(Len) {}
 
-  unsigned getKeyLength() const { return StrLen; }
+  size_t getKeyLength() const { return StrLen; }
 };
 
 /// StringMapImpl - This is the base class of StringMap that is shared among
 /// all of its instantiations.
 class StringMapImpl {
 protected:
   // Array of NumBuckets pointers to entries, null pointers are holes.
   // TheTable[NumBuckets] contains a sentinel value for easy iteration. Followed

 /// StringMapEntry - This is used to represent one value that is inserted into
 /// a StringMap.  It contains the Value itself and the key: the string length
 /// and data.
 template<typename ValueTy>
 class StringMapEntry : public StringMapEntryBase {
 public:
   ValueTy second;
 
-  explicit StringMapEntry(unsigned strLen)
+  explicit StringMapEntry(size_t strLen)
     : StringMapEntryBase(strLen), second() {}
   template <typename... InitTy>
-  StringMapEntry(unsigned strLen, InitTy &&... InitVals)
+  StringMapEntry(size_t strLen, InitTy &&... InitVals)
       : StringMapEntryBase(strLen), second(std::forward<InitTy>(InitVals)...) {}
   StringMapEntry(StringMapEntry &E) = delete;
 
   StringRef getKey() const {
     return StringRef(getKeyData(), getKeyLength());
   }
 
   const ValueTy &getValue() const { return second; }
   ValueTy &getValue() { return second; }
 
   void setValue(const ValueTy &V) { second = V; }
 
   /// getKeyData - Return the start of the string data that is the key for this
   /// value.  The string data is always stored immediately after the
   /// StringMapEntry object.
   const char *getKeyData() const {return reinterpret_cast<const char*>(this+1);}
 
   StringRef first() const { return StringRef(getKeyData(), getKeyLength()); }
 
   /// Create a StringMapEntry for the specified key construct the value using
   /// \p InitiVals.
   template <typename AllocatorTy, typename... InitTy>
   static StringMapEntry *Create(StringRef Key, AllocatorTy &Allocator,
                                 InitTy &&... InitVals) {
-    unsigned KeyLength = Key.size();
+    size_t KeyLength = Key.size();
 
     // Allocate a new item with space for the string at the end and a null
     // terminator.
-    unsigned AllocSize = static_cast<unsigned>(sizeof(StringMapEntry))+
-      KeyLength+1;
-    unsigned Alignment = alignof(StringMapEntry);
+    size_t AllocSize = sizeof(StringMapEntry) + KeyLength + 1;
+    size_t Alignment = alignof(StringMapEntry);
 
     StringMapEntry *NewItem =
       static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
 
     if (NewItem == nullptr)
       report_bad_alloc_error("Allocation of StringMap entry failed.");
 
     // Construct the value.
static StringMapEntry &GetStringMapEntryFromKeyData(const char *KeyData) {
     return *reinterpret_cast<StringMapEntry*>(Ptr);
   }
 
   /// Destroy - Destroy this StringMapEntry, releasing memory back to the
   /// specified allocator.
   template<typename AllocatorTy>
   void Destroy(AllocatorTy &Allocator) {
     // Free memory referenced by the item.
-    unsigned AllocSize =
-        static_cast<unsigned>(sizeof(StringMapEntry)) + getKeyLength() + 1;
+    size_t AllocSize = sizeof(StringMapEntry) + getKeyLength() + 1;
     this->~StringMapEntry();
     Allocator.Deallocate(static_cast<void *>(this), AllocSize);
   }
 
   /// Destroy this object, releasing memory back to the malloc allocator.
   void Destroy() {
     MallocAllocator A;
     Destroy(A);

unittests/ADT/StringMapTest.cpp

 //===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/DataTypes.h"
 #include "gtest/gtest.h"
+#include <limits>
 #include <tuple>
 using namespace llvm;
 
 namespace {
 
 // Test fixture
 class StringMapTest : public testing::Test {
 protected:

 // Test that we can "emplace" an element in the map without involving map/move
 TEST(StringMapCustomTest, EmplaceTest) {
   StringMap<NonMoveableNonCopyableType> Map;
   Map.try_emplace("abcd", 42);
   EXPECT_EQ(1u, Map.count("abcd"));
   EXPECT_EQ(42, Map["abcd"].Data);
 }
 
+// Test that StringMapEntryBase can handle size_t wide sizes.
+TEST(StringMapCustomTest, StringMapEntryBaseSize) {
+  size_t LargeValue;
+
+  // Test that the entry can represent max-unsigned.
+  if (sizeof(size_t) <= sizeof(unsigned))
+    LargeValue = std::numeric_limits<unsigned>::max();
+  else
+    LargeValue = std::numeric_limits<unsigned>::max() + 1ULL;
+  StringMapEntryBase LargeBase(LargeValue);
+  EXPECT_EQ(LargeValue, LargeBase.getKeyLength());
+
+  // Test that the entry can hold at least max size_t.
+  LargeValue = std::numeric_limits<size_t>::max();
+  StringMapEntryBase LargerBase(LargeValue);
+  LargeValue = std::numeric_limits<size_t>::max();
+  EXPECT_EQ(LargeValue, LargerBase.getKeyLength());
+}
+
+// Test that StringMapEntry can handle size_t wide sizes.
+TEST(StringMapCustomTest, StringMapEntrySize) {
+  size_t LargeValue;
+
+  // Test that the entry can represent max-unsigned.
+  if (sizeof(size_t) <= sizeof(unsigned))
+    LargeValue = std::numeric_limits<unsigned>::max();
+  else
+    LargeValue = std::numeric_limits<unsigned>::max() + 1ULL;
+  StringMapEntry<int> LargeEntry(LargeValue);
+  StringRef Key = LargeEntry.getKey();
+  EXPECT_EQ(LargeValue, Key.size());
+
+  // Test that the entry can hold at least max size_t.
+  LargeValue = std::numeric_limits<size_t>::max();
+  StringMapEntry<int> LargerEntry(LargeValue);
+  Key = LargerEntry.getKey();
+  EXPECT_EQ(LargeValue, Key.size());
+}
+
 } // end anonymous namespace