Bug 1470365: Part 1 - Add a compact, read-only, shared-memory string map class. r=erahm
authorKris Maglione <maglione.k@gmail.com>
Fri, 29 Jun 2018 22:50:41 -0700
changeset 482312 b982fcdb2ded44272f2c08be9579b59fd2406364
parent 482311 e5bf63c13445d926553f85ed9381ca38d15a0781
child 482313 86fad941c4d4950935568607e66809bbed364b3d
push id1815
push userffxbld-merge
push dateMon, 15 Oct 2018 10:40:45 +0000
treeherdermozilla-release@18d4c09e9378 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerserahm
bugs1470365
milestone63.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1470365: Part 1 - Add a compact, read-only, shared-memory string map class. r=erahm This class implements a shared memory key-value store that fits into a single memory mapped segment. All of the runtime data for its instances are stored in the shared memory region, which means that memory overhead for each instance in each process is only a few bytes. Importantly, the key and value strings returned by this class are also pointers into the shared memory region, which means that once an instance is created, its memory cannot be unmapped until process shutdown. For the uses I intend to put it to, this is a reasonable constraint. If we need to use it for shorter-lived maps in the future, we can add an option to return non-literal dependent strings that will be copied if they need to be kept alive long term. MozReview-Commit-ID: 5BwAaDsb7HS
dom/ipc/SharedStringMap.cpp
dom/ipc/SharedStringMap.h
dom/ipc/StructuredCloneData.cpp
dom/ipc/moz.build
js/xpconnect/loader/AutoMemMap.cpp
js/xpconnect/loader/AutoMemMap.h
js/xpconnect/loader/moz.build
mfbt/RangedPtr.h
new file mode 100644
--- /dev/null
+++ b/dom/ipc/SharedStringMap.cpp
@@ -0,0 +1,158 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/* vim: set ts=8 sts=4 et sw=4 tw=99: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "SharedStringMap.h"
+
+#include "MemMapSnapshot.h"
+#include "ScriptPreloader-inl.h"
+
+#include "mozilla/BinarySearch.h"
+#include "mozilla/ipc/FileDescriptor.h"
+
+using namespace mozilla::loader;
+
+namespace mozilla {
+
+using namespace ipc;
+
+namespace dom {
+namespace ipc {
+
+static inline size_t
+GetAlignmentOffset(size_t aOffset, size_t aAlign)
+{
+  auto mod = aOffset % aAlign;
+  return mod ? aAlign - mod : 0;
+}
+
+
+SharedStringMap::SharedStringMap(const FileDescriptor& aMapFile, size_t aMapSize)
+{
+  auto result = mMap.initWithHandle(aMapFile, aMapSize);
+  MOZ_RELEASE_ASSERT(result.isOk());
+  // We return literal nsStrings and nsCStrings pointing to the mapped data,
+  // which means that we may still have references to the mapped data even
+  // after this instance is destroyed. That means that we need to keep the
+  // mapping alive until process shutdown, in order to be safe.
+  mMap.setPersistent();
+}
+
+SharedStringMap::SharedStringMap(SharedStringMapBuilder&& aBuilder)
+{
+  auto result = aBuilder.Finalize(mMap);
+  MOZ_RELEASE_ASSERT(result.isOk());
+  mMap.setPersistent();
+}
+
+mozilla::ipc::FileDescriptor
+SharedStringMap::CloneFileDescriptor() const
+{
+  return mMap.cloneHandle();
+}
+
+bool
+SharedStringMap::Has(const nsCString& aKey)
+{
+  size_t index;
+  return Find(aKey, &index);
+}
+
+bool
+SharedStringMap::Get(const nsCString& aKey, nsAString& aValue)
+{
+  const auto& entries = Entries();
+
+  size_t index;
+  if (!Find(aKey, &index)) {
+    return false;
+  }
+
+  aValue.Assign(ValueTable().Get(entries[index].mValue));
+  return true;
+}
+
+bool
+SharedStringMap::Find(const nsCString& aKey, size_t* aIndex)
+{
+  const auto& keys = KeyTable();
+
+  return BinarySearchIf(Entries(), 0, EntryCount(),
+                        [&] (const Entry& aEntry) {
+                          return aKey.Compare(keys.GetBare(aEntry.mKey));
+                        },
+                        aIndex);
+}
+
+
+void
+SharedStringMapBuilder::Add(const nsCString& aKey, const nsString& aValue)
+{
+  mEntries.Put(aKey, {{mKeyTable.Add(aKey), aKey.Length()},
+                      {mValueTable.Add(aValue), aValue.Length()}});
+}
+
+Result<Ok, nsresult>
+SharedStringMapBuilder::Finalize(loader::AutoMemMap& aMap)
+{
+  using Header = SharedStringMap::Header;
+
+  MOZ_ASSERT(mEntries.Count() == mKeyTable.Count());
+
+  nsTArray<nsCString> keys(mEntries.Count());
+  for (auto iter = mEntries.Iter(); !iter.Done(); iter.Next()) {
+    keys.AppendElement(iter.Key());
+  }
+  keys.Sort();
+
+
+  Header header = {uint32_t(keys.Length())};
+
+  size_t offset = sizeof(header);
+  offset += GetAlignmentOffset(offset, alignof(Header));
+
+  offset += keys.Length() * sizeof(SharedStringMap::Entry);
+
+  header.mKeyStringsOffset = offset;
+  header.mKeyStringsSize = mKeyTable.Size();
+
+  offset += header.mKeyStringsSize;
+  offset += GetAlignmentOffset(offset, alignof(decltype(mValueTable)::ElemType));
+
+  header.mValueStringsOffset = offset;
+  header.mValueStringsSize = mValueTable.Size();
+
+  offset += header.mValueStringsSize;
+
+
+  MemMapSnapshot mem;
+  MOZ_TRY(mem.Init(offset));
+
+  auto headerPtr = mem.Get<Header>();
+  headerPtr[0] = header;
+
+  auto* entry = reinterpret_cast<Entry*>(&headerPtr[1]);
+  for (auto& key : keys) {
+    *entry++ = mEntries.Get(key);
+  }
+
+  auto ptr = mem.Get<uint8_t>();
+
+  mKeyTable.Write({ &ptr[header.mKeyStringsOffset],
+                    header.mKeyStringsSize });
+
+  mValueTable.Write({ &ptr[header.mValueStringsOffset],
+                      header.mValueStringsSize });
+
+  mKeyTable.Clear();
+  mValueTable.Clear();
+  mEntries.Clear();
+
+  return mem.Finalize(aMap);
+}
+
+} // ipc
+} // dom
+} // mozilla
new file mode 100644
--- /dev/null
+++ b/dom/ipc/SharedStringMap.h
@@ -0,0 +1,324 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/* vim: set ts=8 sts=4 et sw=4 tw=99: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef dom_ipc_SharedStringMap_h
+#define dom_ipc_SharedStringMap_h
+
+#include "mozilla/AutoMemMap.h"
+#include "mozilla/Result.h"
+#include "mozilla/TypeTraits.h"
+#include "nsDataHashtable.h"
+
+namespace mozilla {
+namespace dom {
+namespace ipc {
+
+class SharedStringMapBuilder;
+
+/**
+ * This class provides a simple, read-only key-value string store, with all
+ * data packed into a single segment of memory, which can be shared between
+ * processes.
+ *
+ * Look-ups are performed by binary search of a static table in the mapped
+ * memory region, and all returned strings are literals which reference the
+ * mapped data. No copies are performed on instantiation or look-up.
+ *
+ * Important: The mapped memory created by this class is persistent. Once an
+ * instance has been initialized, the memory that it allocates can never be
+ * freed before process shutdown. Do not use it for short-lived mappings.
+ */
+class SharedStringMap
+{
+  using FileDescriptor = mozilla::ipc::FileDescriptor;
+
+public:
+  /**
+   * The header at the beginning of the shared memory region describing its
+   * layout. The layout of the shared memory is as follows:
+   *
+   * - Header:
+   *   A Header struct describing the contents of the rest of the memory region.
+   *
+   * - Optional alignment padding for Header[].
+   *
+   * - Entry[header.mEntryCount]:
+   *   An array of Entry structs, one for each entry in the map. Entries are
+   *   lexocographically sorted by key.
+   *
+   * - StringTable<nsCString>:
+   *   A region of flat, null-terminated C strings. Entry key strings are
+   *   encoded as character offsets into this region.
+   *
+   * - Optional alignment padding for char16_t[]
+   *
+   * - StringTable<nsString>:
+   *   A region of flat, null-terminated UTF-16 strings. Entry value strings are
+   *   encoded as character (*not* byte) offsets into this region.
+   */
+  struct Header {
+    // The number of entries in this map.
+    uint32_t mEntryCount;
+
+    // The raw byte offset of the beginning of the key string table, from the
+    // start of the shared memory region, and its size in bytes.
+    size_t mKeyStringsOffset;
+    size_t mKeyStringsSize;
+
+    // The raw byte offset of the beginning of the value string table, from the
+    // start of the shared memory region, and its size in bytes (*not*
+    // characters).
+    size_t mValueStringsOffset;
+    size_t mValueStringsSize;
+  };
+
+  /**
+   * Contains the character offset and character length of an entry in a string
+   * table. This may be used for either 8-bit or 16-bit strings, and is required
+   * to retrieve an entry from a string table.
+   */
+  struct StringEntry {
+    uint32_t mOffset;
+    uint32_t mLength;
+  };
+
+  /**
+   * Describes a value in the string map, as offsets into the key and value
+   * string tables.
+   */
+  struct Entry {
+    // The offset and size of the entry's UTF-8 key in the key string table.
+    StringEntry mKey;
+    // The offset and size of the entry's UTF-16 value in the value string table.
+    StringEntry mValue;
+  };
+
+  NS_INLINE_DECL_REFCOUNTING(SharedStringMap)
+
+  // Note: These constructors are infallible on the premise that this class
+  // is used primarily in cases where it is critical to platform
+  // functionality.
+  explicit SharedStringMap(const FileDescriptor&, size_t);
+  explicit SharedStringMap(SharedStringMapBuilder&&);
+
+  /**
+   * Searches for the given value in the map, and returns true if it exists.
+   */
+  bool Has(const nsCString& aKey);
+
+  /**
+   * Searches for the given value in the map, and, if it exists, returns true
+   * and places its value in aValue.
+   *
+   * The returned value is a literal string which references the mapped memory
+   * region.
+   */
+  bool Get(const nsCString& aKey, nsAString& aValue);
+
+private:
+  /**
+   * Searches for an entry for the given key. If found, returns true, and
+   * places its index in the entry array in aIndex.
+   */
+  bool Find(const nsCString& aKey, size_t* aIndex);
+
+public:
+  /**
+   * Returns the number of entries in the map.
+   */
+  uint32_t Count() const { return EntryCount(); }
+
+  /**
+   * Returns the string entry at the given index. Keys are guaranteed to be
+   * sorted lexographically.
+   *
+   * The given index *must* be less than the value returned by Count().
+   *
+   * The returned value is a literal string which references the mapped memory
+   * region.
+   */
+  nsCString GetKeyAt(uint32_t aIndex) const
+  {
+    MOZ_ASSERT(aIndex < Count());
+    return KeyTable().Get(Entries()[aIndex].mKey);
+  }
+
+  /**
+   * Returns the string value for the entry at the given index.
+   *
+   * The given index *must* be less than the value returned by Count().
+   *
+   * The returned value is a literal string which references the mapped memory
+   * region.
+   */
+  nsString GetValueAt(uint32_t aIndex) const
+  {
+    MOZ_ASSERT(aIndex < Count());
+    return ValueTable().Get(Entries()[aIndex].mValue);
+  }
+
+  /**
+   * Returns a copy of the read-only file descriptor which backs the shared
+   * memory region for this map. The file descriptor may be passed between
+   * processes, and used to construct new instances of SharedStringMap with
+   * the same data as this instance.
+   */
+  FileDescriptor CloneFileDescriptor() const;
+
+  size_t MapSize() const { return mMap.size(); }
+
+protected:
+  ~SharedStringMap() = default;
+
+private:
+  template <typename StringType>
+  class StringTable
+  {
+    using ElemType = decltype(DeclVal<StringType>()[0]);
+
+  public:
+    MOZ_IMPLICIT StringTable(const RangedPtr<uint8_t>& aBuffer)
+      : mBuffer(aBuffer.ReinterpretCast<ElemType>())
+    {
+      MOZ_ASSERT(uintptr_t(aBuffer.get()) % alignof(ElemType) == 0,
+                 "Got misalinged buffer");
+    }
+
+    StringType Get(const StringEntry& aEntry) const
+    {
+      StringType res;
+      res.AssignLiteral(GetBare(aEntry), aEntry.mLength);
+      return res;
+    }
+
+    const ElemType* GetBare(const StringEntry& aEntry) const
+    {
+      return &mBuffer[aEntry.mOffset];
+    }
+
+  private:
+    RangedPtr<ElemType> mBuffer;
+  };
+
+
+  // Type-safe getters for values in the shared memory region:
+  const Header& GetHeader() const
+  {
+    return mMap.get<Header>()[0];
+  }
+
+  RangedPtr<const Entry> Entries() const
+  {
+    return { reinterpret_cast<const Entry*>(&GetHeader() + 1),
+             EntryCount() };
+  }
+
+  uint32_t EntryCount() const
+  {
+    return GetHeader().mEntryCount;
+  }
+
+  StringTable<nsCString> KeyTable() const
+  {
+    auto& header = GetHeader();
+    return { { &mMap.get<uint8_t>()[header.mKeyStringsOffset],
+               header.mKeyStringsSize } };
+  }
+
+  StringTable<nsString> ValueTable() const
+  {
+    auto& header = GetHeader();
+    return { { &mMap.get<uint8_t>()[header.mValueStringsOffset],
+               header.mValueStringsSize } };
+  }
+
+
+  loader::AutoMemMap mMap;
+};
+
+/**
+ * A helper class which builds the contiguous look-up table used by
+ * SharedStringMap. Each key-value pair in the final map is added to the
+ * builder, before it is finalized and transformed into a snapshot.
+ */
+class MOZ_RAII SharedStringMapBuilder
+{
+public:
+  SharedStringMapBuilder() = default;
+
+  /**
+   * Adds a key-value pair to the map.
+   */
+  void Add(const nsCString& aKey, const nsString& aValue);
+
+  /**
+   * Finalizes the binary representation of the map, writes it to a shared
+   * memory region, and then initializes the given AutoMemMap with a reference
+   * to the read-only copy of it.
+   */
+  Result<Ok, nsresult> Finalize(loader::AutoMemMap& aMap);
+
+private:
+  template <typename KeyType, typename StringType>
+  class StringTableBuilder
+  {
+  public:
+    using ElemType = typename StringType::char_type;
+
+    uint32_t Add(const StringType& aKey)
+    {
+      auto entry = mEntries.LookupForAdd(aKey).OrInsert([&] () {
+        Entry newEntry { mSize, aKey };
+        mSize += aKey.Length() + 1;
+
+        return newEntry;
+      });
+
+      return entry.mOffset;
+    }
+
+    void Write(const RangedPtr<uint8_t>& aBuffer)
+    {
+      auto buffer = aBuffer.ReinterpretCast<ElemType>();
+
+      for (auto iter = mEntries.Iter(); !iter.Done(); iter.Next()) {
+        auto& entry = iter.Data();
+        memcpy(&buffer[entry.mOffset], entry.mValue.BeginReading(),
+               sizeof(ElemType) * (entry.mValue.Length() + 1));
+      }
+    }
+
+    uint32_t Count() const { return mEntries.Count(); }
+
+    uint32_t Size() const { return mSize * sizeof(ElemType); }
+
+    void Clear() { mEntries.Clear(); }
+
+  private:
+    struct Entry
+    {
+      uint32_t mOffset;
+      StringType mValue;
+    };
+
+    nsDataHashtable<KeyType, Entry> mEntries;
+    uint32_t mSize = 0;
+  };
+
+  using Entry = SharedStringMap::Entry;
+
+  StringTableBuilder<nsCStringHashKey, nsCString> mKeyTable;
+  StringTableBuilder<nsStringHashKey, nsString> mValueTable;
+
+  nsDataHashtable<nsCStringHashKey, Entry> mEntries;
+};
+
+} // ipc
+} // dom
+} // mozilla
+
+#endif // dom_ipc_SharedStringMap_h
+
--- a/dom/ipc/StructuredCloneData.cpp
+++ b/dom/ipc/StructuredCloneData.cpp
@@ -7,25 +7,29 @@
 #include "StructuredCloneData.h"
 
 #include "nsIMutable.h"
 #include "nsIXPConnect.h"
 
 #include "ipc/IPCMessageUtils.h"
 #include "mozilla/dom/BindingUtils.h"
 #include "mozilla/dom/BlobBinding.h"
+#include "mozilla/dom/DOMTypes.h"
+#include "mozilla/dom/File.h"
 #include "mozilla/dom/IPCBlobUtils.h"
-#include "mozilla/dom/File.h"
+#include "mozilla/ipc/BackgroundParent.h"
 #include "mozilla/ipc/IPCStreamUtils.h"
 #include "nsContentUtils.h"
 #include "nsJSEnvironment.h"
 #include "MainThreadUtils.h"
 #include "StructuredCloneTags.h"
 #include "jsapi.h"
 
+using namespace mozilla::ipc;
+
 namespace mozilla {
 namespace dom {
 namespace ipc {
 
 StructuredCloneData::StructuredCloneData()
   : StructuredCloneData(StructuredCloneHolder::TransferringSupported)
 {}
 
--- a/dom/ipc/moz.build
+++ b/dom/ipc/moz.build
@@ -10,16 +10,17 @@ with Files("**"):
 XPIDL_SOURCES += [
     'nsIHangReport.idl',
 ]
 
 XPIDL_MODULE = 'dom'
 
 EXPORTS.mozilla.dom.ipc += [
     'IdType.h',
+    'SharedStringMap.h',
     'StructuredCloneData.h',
 ]
 
 EXPORTS.mozilla.dom += [
     'CoalescedInputData.h',
     'CoalescedMouseData.h',
     'CoalescedWheelData.h',
     'ContentBridgeChild.h',
@@ -63,16 +64,17 @@ UNIFIED_SOURCES += [
     'FilePickerParent.cpp',
     'MemMapSnapshot.cpp',
     'MemoryReportRequest.cpp',
     'nsIContentChild.cpp',
     'nsIContentParent.cpp',
     'PermissionMessageUtils.cpp',
     'PreallocatedProcessManager.cpp',
     'ProcessPriorityManager.cpp',
+    'SharedStringMap.cpp',
     'StructuredCloneData.cpp',
     'TabChild.cpp',
     'TabContext.cpp',
     'TabMessageUtils.cpp',
     'TabParent.cpp',
     'URLClassifierParent.cpp',
 ]
 
--- a/js/xpconnect/loader/AutoMemMap.cpp
+++ b/js/xpconnect/loader/AutoMemMap.cpp
@@ -138,17 +138,17 @@ AutoMemMap::cloneHandle() const
 }
 
 #endif
 
 void
 AutoMemMap::reset()
 {
     if (fileMap) {
-        if (addr) {
+        if (addr && !persistent_) {
             Unused << NS_WARN_IF(PR_MemUnmap(addr, size()) != PR_SUCCESS);
             addr = nullptr;
         }
 
         Unused << NS_WARN_IF(PR_CloseFileMap(fileMap) != PR_SUCCESS);
         fileMap = nullptr;
     }
 #ifdef XP_WIN
--- a/js/xpconnect/loader/AutoMemMap.h
+++ b/js/xpconnect/loader/AutoMemMap.h
@@ -66,16 +66,20 @@ class AutoMemMap
             return { static_cast<T*>(addr), size_ };
         }
 
         size_t nonHeapSizeOfExcludingThis() { return size_; }
 
         FileDescriptor cloneFileDescriptor() const;
         FileDescriptor cloneHandle() const;
 
+        // Makes this mapping persistent. After calling this, the mapped memory
+        // will remained mapped, even after this instance is destroyed.
+        void setPersistent() { persistent_ = true; }
+
     private:
         Result<Ok, nsresult> initInternal(PRFileMapProtect prot = PR_PROT_READONLY,
                                           size_t expectedSize = 0);
 
         AutoFDClose fd;
         PRFileMap* fileMap = nullptr;
 
 #ifdef XP_WIN
@@ -83,16 +87,18 @@ class AutoMemMap
         // by some binding headers (which are explicitly incompatible with
         // windows.h). So we can't use the HANDLE type here.
         void* handle_ = nullptr;
 #endif
 
         uint32_t size_ = 0;
         void* addr = nullptr;
 
+        bool persistent_ = 0;
+
         AutoMemMap(const AutoMemMap&) = delete;
         void operator=(const AutoMemMap&) = delete;
 };
 
 } // namespace loader
 } // namespace mozilla
 
 #endif // loader_AutoMemMap_h
--- a/js/xpconnect/loader/moz.build
+++ b/js/xpconnect/loader/moz.build
@@ -20,16 +20,17 @@ SOURCES += [
     'mozJSComponentLoader.cpp'
 ]
 
 IPDL_SOURCES += [
     'PScriptCache.ipdl',
 ]
 
 EXPORTS.mozilla += [
+    'AutoMemMap.h',
     'ScriptPreloader.h',
     'URLPreloader.h',
 ]
 
 EXPORTS.mozilla.dom += [
     'PrecompiledScript.h',
 ]
 
--- a/mfbt/RangedPtr.h
+++ b/mfbt/RangedPtr.h
@@ -118,16 +118,29 @@ public:
   explicit operator bool() const { return mPtr != nullptr; }
 
   void checkIdenticalRange(const RangedPtr<T>& aOther) const
   {
     MOZ_ASSERT(mRangeStart == aOther.mRangeStart);
     MOZ_ASSERT(mRangeEnd == aOther.mRangeEnd);
   }
 
+  template <typename U>
+  RangedPtr<U>
+  ReinterpretCast() const
+  {
+#ifdef DEBUG
+    return { reinterpret_cast<U*>(mPtr),
+             reinterpret_cast<U*>(mRangeStart),
+             reinterpret_cast<U*>(mRangeEnd) };
+#else
+    return { reinterpret_cast<U*>(mPtr), nullptr, nullptr };
+#endif
+  }
+
   /*
    * You can only assign one RangedPtr into another if the two pointers have
    * the same valid range:
    *
    *   char arr1[] = "hi";
    *   char arr2[] = "bye";
    *   RangedPtr<char> p1(arr1, 2);
    *   p1 = RangedPtr<char>(arr1 + 1, arr1, arr1 + 2); // works