UUID: Add support for arbitrary-sized module IDs

[labath]

Summary

The data structure is optimized for the case where the UUID size is <=
20 bytes (standard length emitted by the GNU linkers), but larger sizes
are also possible.

I've modified the string conversion function to support the new sizes as
well. For standard UUIDs it maintains the traditional formatting
(4-2-2-2-6). If a UUID is shorter, we just cut this sequence short, and
for longer UUIDs it will just repeat the last 6-byte block as long as
necessary.

I've also modified ObjectFileELF to take advantage of the new UUIDs and
avoid manually padding the UUID to 16 bytes. While there, I also made
sure the computed UUID does not depend on host endianness.

[clayborg]

source/Interpreter/OptionValueUUID.cpp

82 ↗

(On Diff #153048)

Probably should have a return value that indicates success or not. What if the user enters "aab". The string must have an event number of hex digits.

[labath]

source/Interpreter/OptionValueUUID.cpp

82 ↗

(On Diff #153048)

The function returns the unparsed portion of the string (so empty string means success), but this code wasn't checking it for some reason.

I've added a check for that.

[labath]

Add a check to the tab-completion function.

lldb/trunk/include/lldb/Utility/UUID.h

 }
 
 namespace lldb_private {
 
   class Stream;
 
 class UUID {
 public:
-  // Most UUIDs are 16 bytes, but some Linux build-ids (SHA1) are 20.
-  typedef uint8_t ValueType[20];
-
-  //------------------------------------------------------------------
-  // Constructors and Destructors
-  //------------------------------------------------------------------
   UUID() = default;
 
   /// Creates a UUID from the data pointed to by the bytes argument. No special
   /// significance is attached to any of the values.
   static UUID fromData(const void *bytes, uint32_t num_bytes) {
     if (bytes)
       return fromData({reinterpret_cast<const uint8_t *>(bytes), num_bytes});
     return UUID();
public:
   /// Creates a UUID from the data pointed to by the bytes argument. Data
   /// consisting purely of zero bytes is treated as an invalid UUID.
   static UUID fromOptionalData(llvm::ArrayRef<uint8_t> bytes) {
     if (llvm::all_of(bytes, [](uint8_t b) { return b == 0; }))
       return UUID();
     return UUID(bytes);
   }
 
-  void Clear() { m_num_uuid_bytes = 0; }
+  void Clear() { m_bytes.clear(); }
 
   void Dump(Stream *s) const;
 
-  llvm::ArrayRef<uint8_t> GetBytes() const {
-    return {m_uuid, m_num_uuid_bytes};
-  }
+  llvm::ArrayRef<uint8_t> GetBytes() const { return m_bytes; }
 
   explicit operator bool() const { return IsValid(); }
-  bool IsValid() const { return m_num_uuid_bytes > 0; }
+  bool IsValid() const { return !m_bytes.empty(); }
 
-  std::string GetAsString(const char *separator = nullptr) const;
+  std::string GetAsString(llvm::StringRef separator = "-") const;
 
   size_t SetFromStringRef(llvm::StringRef str, uint32_t num_uuid_bytes = 16);
 
   // Decode as many UUID bytes (up to 16) as possible from the C string "cstr"
   // This is used for auto completion where a partial UUID might have been
   // typed in. It
   //------------------------------------------------------------------
   /// Decode as many UUID bytes (up to 16) as possible from the C
   /// string \a cstr.
   ///
   /// @param[in] cstr
   ///     A NULL terminate C string that points at a UUID string value
   ///     (no leading spaces). The string must contain only hex
   ///     characters and optionally can contain the '-' sepearators.
   ///
   /// @param[in] uuid_bytes
   ///     A buffer of bytes that will contain a full or patially
   ///     decoded UUID.
   ///
   /// @return
   ///     The original string, with all decoded bytes removed.
   //------------------------------------------------------------------
   static llvm::StringRef
-  DecodeUUIDBytesFromString(llvm::StringRef str, ValueType &uuid_bytes,
-                            uint32_t &bytes_decoded,
+  DecodeUUIDBytesFromString(llvm::StringRef str,
+                            llvm::SmallVectorImpl<uint8_t> &uuid_bytes,
                             uint32_t num_uuid_bytes = 16);
 
 private:
-  UUID(llvm::ArrayRef<uint8_t> bytes);
-
-  uint32_t m_num_uuid_bytes = 0; // Should be 0, 16 or 20
-  ValueType m_uuid;
-};
+  UUID(llvm::ArrayRef<uint8_t> bytes) : m_bytes(bytes.begin(), bytes.end()) {}
 
-bool operator==(const UUID &lhs, const UUID &rhs);
-bool operator!=(const UUID &lhs, const UUID &rhs);
-bool operator<(const UUID &lhs, const UUID &rhs);
-bool operator<=(const UUID &lhs, const UUID &rhs);
-bool operator>(const UUID &lhs, const UUID &rhs);
-bool operator>=(const UUID &lhs, const UUID &rhs);
+  // GNU ld generates 20-byte build-ids. Size chosen to avoid heap allocations
+  // for this case.
+  llvm::SmallVector<uint8_t, 20> m_bytes;
 
+  friend bool operator==(const UUID &LHS, const UUID &RHS) {
+    return LHS.m_bytes == RHS.m_bytes;
+  }
+  friend bool operator!=(const UUID &LHS, const UUID &RHS) {
+    return !(LHS == RHS);
+  }
+  friend bool operator<(const UUID &LHS, const UUID &RHS) {
+    return LHS.m_bytes < RHS.m_bytes;
+  }
+  friend bool operator<=(const UUID &LHS, const UUID &RHS) {
+    return !(RHS < LHS);
+  }
+  friend bool operator>(const UUID &LHS, const UUID &RHS) { return RHS < LHS; }
+  friend bool operator>=(const UUID &LHS, const UUID &RHS) {
+    return !(LHS < RHS);
+  }
+};
 } // namespace lldb_private
 
 #endif // LLDB_UTILITY_UUID_H

lldb/trunk/source/Interpreter/OptionValueUUID.cpp

size_t OptionValueUUID::AutoComplete(CommandInterpreter &interpreter,
                                      llvm::StringRef s, int match_start_point,
                                      int max_return_elements,
                                      bool &word_complete, StringList &matches) {
   word_complete = false;
   matches.Clear();
   ExecutionContext exe_ctx(interpreter.GetExecutionContext());
   Target *target = exe_ctx.GetTargetPtr();
   if (target) {
+    llvm::SmallVector<uint8_t, 20> uuid_bytes;
+    if (UUID::DecodeUUIDBytesFromString(s, uuid_bytes).empty()) {
       const size_t num_modules = target->GetImages().GetSize();
-    if (num_modules > 0) {
-      UUID::ValueType uuid_bytes;
-      uint32_t num_bytes_decoded = 0;
-      UUID::DecodeUUIDBytesFromString(s, uuid_bytes, num_bytes_decoded);
       for (size_t i = 0; i < num_modules; ++i) {
         ModuleSP module_sp(target->GetImages().GetModuleAtIndex(i));
         if (module_sp) {
           const UUID &module_uuid = module_sp->GetUUID();
           if (module_uuid.IsValid()) {
-            llvm::ArrayRef<uint8_t> decoded_bytes(uuid_bytes,
-                                                  num_bytes_decoded);
             llvm::ArrayRef<uint8_t> module_bytes = module_uuid.GetBytes();
-            if (module_bytes.size() >= num_bytes_decoded &&
-                module_bytes.take_front(num_bytes_decoded) == decoded_bytes) {
+            if (module_bytes.size() >= uuid_bytes.size() &&
+                module_bytes.take_front(uuid_bytes.size()).equals(uuid_bytes)) {
               matches.AppendString(module_uuid.GetAsString());
             }
           }
         }
       }
     }
   }
   return matches.GetSize();
 }

lldb/trunk/source/Plugins/ObjectFile/ELF/ObjectFileELF.cpp

if (header.Parse(data, &header_offset)) {
 
                 core_notes_crc =
                     CalculateELFNotesSegmentsCRC32(program_headers, data);
               } else {
                 gnu_debuglink_crc = calc_gnu_debuglink_crc32(
                     data.GetDataStart(), data.GetByteSize());
               }
             }
+            using u32le = llvm::support::ulittle32_t;
             if (gnu_debuglink_crc) {
               // Use 4 bytes of crc from the .gnu_debuglink section.
-              uint32_t uuidt[4] = {gnu_debuglink_crc, 0, 0, 0};
-              uuid = UUID::fromData(uuidt, sizeof(uuidt));
+              u32le data(gnu_debuglink_crc);
+              uuid = UUID::fromData(&data, sizeof(data));
             } else if (core_notes_crc) {
               // Use 8 bytes - first 4 bytes for *magic* prefix, mainly to make
               // it look different form .gnu_debuglink crc followed by 4 bytes
               // of note segments crc.
-              uint32_t uuidt[4] = {g_core_uuid_magic, core_notes_crc, 0, 0};
-              uuid = UUID::fromData(uuidt, sizeof(uuidt));
+              u32le data[] = {u32le(g_core_uuid_magic), u32le(core_notes_crc)};
+              uuid = UUID::fromData(data, sizeof(data));
             }
           }
 
           specs.Append(spec);
         }
       }
     }
   }

 }
 
 bool ObjectFileELF::GetUUID(lldb_private::UUID *uuid) {
   // Need to parse the section list to get the UUIDs, so make sure that's been
   // done.
   if (!ParseSectionHeaders() && GetType() != ObjectFile::eTypeCoreFile)
     return false;
 
+  using u32le = llvm::support::ulittle32_t;
   if (m_uuid.IsValid()) {
     // We have the full build id uuid.
     *uuid = m_uuid;
     return true;
   } else if (GetType() == ObjectFile::eTypeCoreFile) {
     uint32_t core_notes_crc = 0;
 
     if (!ParseProgramHeaders())
       return false;
 
     core_notes_crc = CalculateELFNotesSegmentsCRC32(m_program_headers, m_data);
 
     if (core_notes_crc) {
       // Use 8 bytes - first 4 bytes for *magic* prefix, mainly to make it look
       // different form .gnu_debuglink crc - followed by 4 bytes of note
       // segments crc.
-      uint32_t uuidt[4] = {g_core_uuid_magic, core_notes_crc, 0, 0};
-      m_uuid = UUID::fromData(uuidt, sizeof(uuidt));
+      u32le data[] = {u32le(g_core_uuid_magic), u32le(core_notes_crc)};
+      m_uuid = UUID::fromData(data, sizeof(data));
     }
   } else {
     if (!m_gnu_debuglink_crc)
       m_gnu_debuglink_crc =
           calc_gnu_debuglink_crc32(m_data.GetDataStart(), m_data.GetByteSize());
     if (m_gnu_debuglink_crc) {
       // Use 4 bytes of crc from the .gnu_debuglink section.
-      uint32_t uuidt[4] = {m_gnu_debuglink_crc, 0, 0, 0};
-      m_uuid = UUID::fromData(uuidt, sizeof(uuidt));
+      u32le data(m_gnu_debuglink_crc);
+      m_uuid = UUID::fromData(&data, sizeof(data));
     }
   }
 
   if (m_uuid.IsValid()) {
     *uuid = m_uuid;
     return true;
   }
 
else if (note.n_name == LLDB_NT_OWNER_GNU) {
           }
         }
         break;
 
       case LLDB_NT_GNU_BUILD_ID_TAG:
         // Only bother processing this if we don't already have the uuid set.
         if (!uuid.IsValid()) {
           // 16 bytes is UUID|MD5, 20 bytes is SHA1. Other linkers may produce a
-          // build-id of a different
-          // length. Accept it as long as it's at least 4 bytes as it will be
-          // better than our own crc32.
-          if (note.n_descsz >= 4 && note.n_descsz <= 20) {
-            uint8_t uuidbuf[20];
-            if (data.GetU8(&offset, &uuidbuf, note.n_descsz) == nullptr) {
+          // build-id of a different length. Accept it as long as it's at least
+          // 4 bytes as it will be better than our own crc32.
+          if (note.n_descsz >= 4) {
+            if (const uint8_t *buf = data.PeekData(offset, note.n_descsz)) {
+              // Save the build id as the UUID for the module.
+              uuid = UUID::fromData(buf, note.n_descsz);
+            } else {
               error.SetErrorString("failed to read GNU_BUILD_ID note payload");
               return error;
             }
-
-            // Save the build id as the UUID for the module.
-            uuid = UUID::fromData(uuidbuf, note.n_descsz);
           }
         }
         break;
       }
       if (arch_spec.IsMIPS() &&
           arch_spec.GetTriple().getOS() == llvm::Triple::OSType::UnknownOS)
         // The note.n_name == LLDB_NT_OWNER_GNU is valid for Linux platform
         arch_spec.GetTriple().setOS(llvm::Triple::OSType::Linux);

lldb/trunk/source/Utility/UUID.cpp

 //===-- UUID.cpp ------------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lldb/Utility/UUID.h"
 
 // Other libraries and framework includes
 // Project includes
 #include "lldb/Utility/Stream.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Format.h"
 
 // C Includes
 #include <ctype.h>
 #include <stdio.h>
 #include <string.h>
 
 using namespace lldb_private;
 
-UUID::UUID(llvm::ArrayRef<uint8_t> bytes) {
-  if (bytes.size() != 20 && bytes.size() != 16)
-    bytes = {};
-
-  m_num_uuid_bytes = bytes.size();
-  std::memcpy(m_uuid, bytes.data(), bytes.size());
+// Whether to put a separator after count uuid bytes.
+// For the first 16 bytes we follow the traditional UUID format. After that, we
+// simply put a dash after every 6 bytes.
+static inline bool separate(size_t count) {
+  if (count >= 10)
+    return (count - 10) % 6 == 0;
+
+  switch (count) {
+  case 4:
+  case 6:
+  case 8:
+    return true;
+  default:
+    return false;
+  }
 }
 
-std::string UUID::GetAsString(const char *separator) const {
+std::string UUID::GetAsString(llvm::StringRef separator) const {
   std::string result;
-  char buf[256];
-  if (!separator)
-    separator = "-";
-  const uint8_t *u = GetBytes().data();
-  if (sizeof(buf) >
-      (size_t)snprintf(buf, sizeof(buf), "%2.2X%2.2X%2.2X%2.2X%s%2.2X%2.2X%s%2."
-                                         "2X%2.2X%s%2.2X%2.2X%s%2.2X%2.2X%2.2X%"
-                                         "2.2X%2.2X%2.2X",
-                       u[0], u[1], u[2], u[3], separator, u[4], u[5], separator,
-                       u[6], u[7], separator, u[8], u[9], separator, u[10],
-                       u[11], u[12], u[13], u[14], u[15])) {
-    result.append(buf);
-    if (m_num_uuid_bytes == 20) {
-      if (sizeof(buf) > (size_t)snprintf(buf, sizeof(buf),
-                                         "%s%2.2X%2.2X%2.2X%2.2X", separator,
-                                         u[16], u[17], u[18], u[19]))
-        result.append(buf);
-    }
+  llvm::raw_string_ostream os(result);
+
+  for (auto B : llvm::enumerate(GetBytes())) {
+    if (separate(B.index()))
+      os << separator;
+
+    os << llvm::format_hex_no_prefix(B.value(), 2, true);
   }
+  os.flush();
+
   return result;
 }
 
 void UUID::Dump(Stream *s) const {
   s->PutCString(GetAsString().c_str());
 }
 
 static inline int xdigit_to_int(char ch) {
   ch = tolower(ch);
   if (ch >= 'a' && ch <= 'f')
     return 10 + ch - 'a';
   return ch - '0';
 }
 
-llvm::StringRef UUID::DecodeUUIDBytesFromString(llvm::StringRef p,
-                                                ValueType &uuid_bytes,
-                                                uint32_t &bytes_decoded,
-                                                uint32_t num_uuid_bytes) {
-  ::memset(uuid_bytes, 0, sizeof(uuid_bytes));
-  size_t uuid_byte_idx = 0;
+llvm::StringRef
+UUID::DecodeUUIDBytesFromString(llvm::StringRef p,
+                                llvm::SmallVectorImpl<uint8_t> &uuid_bytes,
+  uuid_bytes.clear();
   while (!p.empty()) {
     if (isxdigit(p[0]) && isxdigit(p[1])) {
       int hi_nibble = xdigit_to_int(p[0]);
       int lo_nibble = xdigit_to_int(p[1]);
       // Translate the two hex nibble characters into a byte
-      uuid_bytes[uuid_byte_idx] = (hi_nibble << 4) + lo_nibble;
+      uuid_bytes.push_back((hi_nibble << 4) + lo_nibble);
 
       // Skip both hex digits
       p = p.drop_front(2);
 
       // Increment the byte that we are decoding within the UUID value and
       // break out if we are done
-      if (++uuid_byte_idx == num_uuid_bytes)
+      if (uuid_bytes.size() == num_uuid_bytes)
         break;
     } else if (p.front() == '-') {
       // Skip dashes
       p = p.drop_front();
     } else {
       // UUID values can only consist of hex characters and '-' chars
       break;
     }
   }
-
-  // Clear trailing bytes to 0.
-  for (uint32_t i = uuid_byte_idx; i < sizeof(ValueType); i++)
-    uuid_bytes[i] = 0;
-  bytes_decoded = uuid_byte_idx;
   return p;
 }
 
 size_t UUID::SetFromStringRef(llvm::StringRef str, uint32_t num_uuid_bytes) {
   llvm::StringRef p = str;
 
   // Skip leading whitespace characters
   p = p.ltrim();
 
-  ValueType bytes;
-  uint32_t bytes_decoded = 0;
+  llvm::SmallVector<uint8_t, 20> bytes;
   llvm::StringRef rest =
-      UUID::DecodeUUIDBytesFromString(p, bytes, bytes_decoded, num_uuid_bytes);
+      UUID::DecodeUUIDBytesFromString(p, bytes, num_uuid_bytes);
 
   // If we successfully decoded a UUID, return the amount of characters that
   // were consumed
-  if (bytes_decoded == num_uuid_bytes) {
-    *this = fromData(bytes, bytes_decoded);
+  if (bytes.size() == num_uuid_bytes) {
+    *this = fromData(bytes);
     return str.size() - rest.size();
   }
 
   // Else return zero to indicate we were not able to parse a UUID value
   return 0;
 }
-
-bool lldb_private::operator==(const lldb_private::UUID &lhs,
-                              const lldb_private::UUID &rhs) {
-  return lhs.GetBytes() == rhs.GetBytes();
-}
-
-bool lldb_private::operator!=(const lldb_private::UUID &lhs,
-                              const lldb_private::UUID &rhs) {
-  return !(lhs == rhs);
-}
-
-bool lldb_private::operator<(const lldb_private::UUID &lhs,
-                             const lldb_private::UUID &rhs) {
-  if (lhs.GetBytes().size() != rhs.GetBytes().size())
-    return lhs.GetBytes().size() < rhs.GetBytes().size();
-
-  return std::memcmp(lhs.GetBytes().data(), rhs.GetBytes().data(),
-                     lhs.GetBytes().size());
-}
-
-bool lldb_private::operator<=(const lldb_private::UUID &lhs,
-                              const lldb_private::UUID &rhs) {
-  return !(lhs > rhs);
-}
-
-bool lldb_private::operator>(const lldb_private::UUID &lhs,
-                             const lldb_private::UUID &rhs) {
-  return rhs < lhs;
-}
-
-bool lldb_private::operator>=(const lldb_private::UUID &lhs,
-                              const lldb_private::UUID &rhs) {
-  return !(lhs < rhs);
-}

lldb/trunk/unittests/Utility/UUIDTest.cpp

TEST(UUIDTest, SetFromStringRef) {
   EXPECT_EQ(0u, u.SetFromStringRef(""));
   EXPECT_EQ(UUID::fromData("@ABCDEFGHIJKLMNOPQRS", 20), u)
       << "uuid was changed by failed parse calls";
 
   EXPECT_EQ(
       32u, u.SetFromStringRef("404142434445464748494a4b4c4d4e4f-50515253", 16));
   EXPECT_EQ(UUID::fromData("@ABCDEFGHIJKLMNO", 16), u);
 }
+
+TEST(UUIDTest, StringConverion) {
+  EXPECT_EQ("40414243", UUID::fromData("@ABC", 4).GetAsString());
+  EXPECT_EQ("40414243-4445-4647", UUID::fromData("@ABCDEFG", 8).GetAsString());
+  EXPECT_EQ("40414243-4445-4647-4849-4A4B",
+            UUID::fromData("@ABCDEFGHIJK", 12).GetAsString());
+  EXPECT_EQ("40414243-4445-4647-4849-4A4B4C4D4E4F",
+            UUID::fromData("@ABCDEFGHIJKLMNO", 16).GetAsString());
+  EXPECT_EQ("40414243-4445-4647-4849-4A4B4C4D4E4F-50515253",
+            UUID::fromData("@ABCDEFGHIJKLMNOPQRS", 20).GetAsString());
+}