contrib/llvm/tools/lldb/include/lldb/Core/MappedHash.h

   1 //===-- MappedHash.h --------------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef liblldb_MappedHash_h_
  11 #define liblldb_MappedHash_h_
  12
  13 // C Includes
  14 #include <assert.h>
  15 #include <stdint.h>
  16
  17 // C++ Includes
  18 #include <algorithm>
  19 #include <functional>
  20 #include <map>
  21 #include <vector>
  22
  23 // Other libraries and framework includes
  24 // Project includes
  25 #include "lldb/Utility/DataExtractor.h"
  26 #include "lldb/Utility/Stream.h"
  27 #include "llvm/Support/DJB.h"
  28
  29 class MappedHash {
  30 public:
  31   enum HashFunctionType {
  32     eHashFunctionDJB = 0u // Daniel J Bernstein hash function that is also used
  33                           // by the ELF GNU_HASH sections
  34   };
  35
  36   static uint32_t HashString(uint32_t hash_function, llvm::StringRef s) {
  37     switch (hash_function) {
  38     case MappedHash::eHashFunctionDJB:
  39       return llvm::djbHash(s);
  40
  41     default:
  42       break;
  43     }
  44     llvm_unreachable("Invalid hash function index");
  45   }
  46
  47   static const uint32_t HASH_MAGIC = 0x48415348u;
  48   static const uint32_t HASH_CIGAM = 0x48534148u;
  49
  50   template <typename T> struct Header {
  51     typedef T HeaderData;
  52
  53     uint32_t
  54         magic; // HASH_MAGIC or HASH_CIGAM magic value to allow endian detection
  55     uint16_t version;         // Version number
  56     uint16_t hash_function;   // The hash function enumeration that was used
  57     uint32_t bucket_count;    // The number of buckets in this hash table
  58     uint32_t hashes_count;    // The total number of unique hash values and hash
  59                               // data offsets in this table
  60     uint32_t header_data_len; // The size in bytes of the "header_data" template
  61                               // member below
  62     HeaderData header_data;   //
  63
  64     Header()
  65         : magic(HASH_MAGIC), version(1), hash_function(eHashFunctionDJB),
  66           bucket_count(0), hashes_count(0), header_data_len(sizeof(T)),
  67           header_data() {}
  68
  69     virtual ~Header() = default;
  70
  71     size_t GetByteSize() const {
  72       return sizeof(magic) + sizeof(version) + sizeof(hash_function) +
  73              sizeof(bucket_count) + sizeof(hashes_count) +
  74              sizeof(header_data_len) + header_data_len;
  75     }
  76
  77     virtual size_t GetByteSize(const HeaderData &header_data) = 0;
  78
  79     void SetHeaderDataByteSize(uint32_t header_data_byte_size) {
  80       header_data_len = header_data_byte_size;
  81     }
  82
  83     void Dump(lldb_private::Stream &s) {
  84       s.Printf("header.magic              = 0x%8.8x\n", magic);
  85       s.Printf("header.version            = 0x%4.4x\n", version);
  86       s.Printf("header.hash_function      = 0x%4.4x\n", hash_function);
  87       s.Printf("header.bucket_count       = 0x%8.8x %u\n", bucket_count,
  88                bucket_count);
  89       s.Printf("header.hashes_count       = 0x%8.8x %u\n", hashes_count,
  90                hashes_count);
  91       s.Printf("header.header_data_len    = 0x%8.8x %u\n", header_data_len,
  92                header_data_len);
  93     }
  94
  95     virtual lldb::offset_t Read(lldb_private::DataExtractor &data,
  96                                 lldb::offset_t offset) {
  97       if (data.ValidOffsetForDataOfSize(
  98               offset, sizeof(magic) + sizeof(version) + sizeof(hash_function) +
  99                           sizeof(bucket_count) + sizeof(hashes_count) +
 100                           sizeof(header_data_len))) {
 101         magic = data.GetU32(&offset);
 102         if (magic != HASH_MAGIC) {
 103           if (magic == HASH_CIGAM) {
 104             switch (data.GetByteOrder()) {
 105             case lldb::eByteOrderBig:
 106               data.SetByteOrder(lldb::eByteOrderLittle);
 107               break;
 108             case lldb::eByteOrderLittle:
 109               data.SetByteOrder(lldb::eByteOrderBig);
 110               break;
 111             default:
 112               return LLDB_INVALID_OFFSET;
 113             }
 114           } else {
 115             // Magic bytes didn't match
 116             version = 0;
 117             return LLDB_INVALID_OFFSET;
 118           }
 119         }
 120
 121         version = data.GetU16(&offset);
 122         if (version != 1) {
 123           // Unsupported version
 124           return LLDB_INVALID_OFFSET;
 125         }
 126         hash_function = data.GetU16(&offset);
 127         if (hash_function == 4)
 128           hash_function = 0; // Deal with pre-release version of this table...
 129         bucket_count = data.GetU32(&offset);
 130         hashes_count = data.GetU32(&offset);
 131         header_data_len = data.GetU32(&offset);
 132         return offset;
 133       }
 134       return LLDB_INVALID_OFFSET;
 135     }
 136     //
 137     //        // Returns a buffer that contains a serialized version of this
 138     //        table
 139     //        // that must be freed with free().
 140     //        virtual void *
 141     //        Write (int fd);
 142   };
 143
 144   // A class for reading and using a saved hash table from a block of data
 145   // in memory
 146   template <typename __KeyType, class __HeaderType, class __HashData>
 147   class MemoryTable {
 148   public:
 149     typedef __HeaderType HeaderType;
 150     typedef __KeyType KeyType;
 151     typedef __HashData HashData;
 152
 153     enum Result {
 154       eResultKeyMatch = 0u, // The entry was found, key matched and "pair" was
 155                             // filled in successfully
 156       eResultKeyMismatch =
 157           1u, // Bucket hash data collision, but key didn't match
 158       eResultEndOfHashData = 2u, // The chain of items for this hash data in
 159                                  // this bucket is terminated, search no more
 160       eResultError = 3u          // Status parsing the hash data, abort
 161     };
 162
 163     struct Pair {
 164       KeyType key;
 165       HashData value;
 166     };
 167
 168     MemoryTable(lldb_private::DataExtractor &data)
 169         : m_header(), m_hash_indexes(nullptr), m_hash_values(nullptr),
 170           m_hash_offsets(nullptr) {
 171       lldb::offset_t offset = m_header.Read(data, 0);
 172       if (offset != LLDB_INVALID_OFFSET && IsValid()) {
 173         m_hash_indexes = (const uint32_t *)data.GetData(
 174             &offset, m_header.bucket_count * sizeof(uint32_t));
 175         m_hash_values = (const uint32_t *)data.GetData(
 176             &offset, m_header.hashes_count * sizeof(uint32_t));
 177         m_hash_offsets = (const uint32_t *)data.GetData(
 178             &offset, m_header.hashes_count * sizeof(uint32_t));
 179       }
 180     }
 181
 182     virtual ~MemoryTable() = default;
 183
 184     bool IsValid() const {
 185       return m_header.version == 1 &&
 186              m_header.hash_function == eHashFunctionDJB &&
 187              m_header.bucket_count > 0;
 188     }
 189
 190     uint32_t GetHashIndex(uint32_t bucket_idx) const {
 191       uint32_t result = UINT32_MAX;
 192       if (m_hash_indexes && bucket_idx < m_header.bucket_count)
 193         memcpy(&result, m_hash_indexes + bucket_idx, sizeof(uint32_t));
 194       return result;
 195     }
 196
 197     uint32_t GetHashValue(uint32_t hash_idx) const {
 198       uint32_t result = UINT32_MAX;
 199       if (m_hash_values && hash_idx < m_header.hashes_count)
 200         memcpy(&result, m_hash_values + hash_idx, sizeof(uint32_t));
 201       return result;
 202     }
 203
 204     uint32_t GetHashDataOffset(uint32_t hash_idx) const {
 205       uint32_t result = UINT32_MAX;
 206       if (m_hash_offsets && hash_idx < m_header.hashes_count)
 207         memcpy(&result, m_hash_offsets + hash_idx, sizeof(uint32_t));
 208       return result;
 209     }
 210
 211     bool Find(llvm::StringRef name, Pair &pair) const {
 212       if (name.empty())
 213         return false;
 214
 215       if (IsValid()) {
 216         const uint32_t bucket_count = m_header.bucket_count;
 217         const uint32_t hash_count = m_header.hashes_count;
 218         const uint32_t hash_value =
 219             MappedHash::HashString(m_header.hash_function, name);
 220         const uint32_t bucket_idx = hash_value % bucket_count;
 221         uint32_t hash_idx = GetHashIndex(bucket_idx);
 222         if (hash_idx < hash_count) {
 223           for (; hash_idx < hash_count; ++hash_idx) {
 224             const uint32_t curr_hash_value = GetHashValue(hash_idx);
 225             if (curr_hash_value == hash_value) {
 226               lldb::offset_t hash_data_offset = GetHashDataOffset(hash_idx);
 227               while (hash_data_offset != UINT32_MAX) {
 228                 const lldb::offset_t prev_hash_data_offset = hash_data_offset;
 229                 Result hash_result =
 230                     GetHashDataForName(name, &hash_data_offset, pair);
 231                 // Check the result of getting our hash data
 232                 switch (hash_result) {
 233                 case eResultKeyMatch:
 234                   return true;
 235
 236                 case eResultKeyMismatch:
 237                   if (prev_hash_data_offset == hash_data_offset)
 238                     return false;
 239                   break;
 240
 241                 case eResultEndOfHashData:
 242                   // The last HashData for this key has been reached, stop
 243                   // searching
 244                   return false;
 245                 case eResultError:
 246                   // Status parsing the hash data, abort
 247                   return false;
 248                 }
 249               }
 250             }
 251             if ((curr_hash_value % bucket_count) != bucket_idx)
 252               break;
 253           }
 254         }
 255       }
 256       return false;
 257     }
 258
 259     // This method must be implemented in any subclasses. The KeyType is user
 260     // specified and must somehow result in a string value. For example, the
 261     // KeyType might be a string offset in a string table and subclasses can
 262     // store their string table as a member of the subclass and return a valie
 263     // "const char *" given a "key". The value could also be a C string
 264     // pointer, in which case just returning "key" will suffice.
 265     virtual const char *GetStringForKeyType(KeyType key) const = 0;
 266
 267     virtual bool ReadHashData(uint32_t hash_data_offset,
 268                               HashData &hash_data) const = 0;
 269
 270     // This method must be implemented in any subclasses and it must try to
 271     // read one "Pair" at the offset pointed to by the "hash_data_offset_ptr"
 272     // parameter. This offset should be updated as bytes are consumed and a
 273     // value "Result" enum should be returned. If the "name" matches the full
 274     // name for the "pair.key" (which must be filled in by this call), then the
 275     // HashData in the pair ("pair.value") should be extracted and filled in
 276     // and "eResultKeyMatch" should be returned. If "name" doesn't match this
 277     // string for the key, then "eResultKeyMismatch" should be returned and all
 278     // data for the current HashData must be consumed or skipped and the
 279     // "hash_data_offset_ptr" offset needs to be updated to point to the next
 280     // HashData. If the end of the HashData objects for a given hash value have
 281     // been reached, then "eResultEndOfHashData" should be returned. If
 282     // anything else goes wrong during parsing, return "eResultError" and the
 283     // corresponding "Find()" function will be canceled and return false.
 284     virtual Result GetHashDataForName(llvm::StringRef name,
 285                                       lldb::offset_t *hash_data_offset_ptr,
 286                                       Pair &pair) const = 0;
 287
 288     const HeaderType &GetHeader() { return m_header; }
 289
 290     void ForEach(
 291         std::function<bool(const HashData &hash_data)> const &callback) const {
 292       const size_t num_hash_offsets = m_header.hashes_count;
 293       for (size_t i = 0; i < num_hash_offsets; ++i) {
 294         uint32_t hash_data_offset = GetHashDataOffset(i);
 295         if (hash_data_offset != UINT32_MAX) {
 296           HashData hash_data;
 297           if (ReadHashData(hash_data_offset, hash_data)) {
 298             // If the callback returns false, then we are done and should stop
 299             if (callback(hash_data) == false)
 300               return;
 301           }
 302         }
 303       }
 304     }
 305
 306   protected:
 307     // Implementation agnostic information
 308     HeaderType m_header;
 309     const uint32_t *m_hash_indexes;
 310     const uint32_t *m_hash_values;
 311     const uint32_t *m_hash_offsets;
 312   };
 313 };
 314
 315 #endif // liblldb_MappedHash_h_