Bug 1304449: Part 1 - Modify MSAA IDs to be partitioned based on content id; r=tbsaunde, a=gchang
authorAaron Klotz <aklotz@mozilla.com>
Wed, 05 Oct 2016 17:52:23 -0600
changeset 358401 c91317b095bd760c0e50ec1b14249e3306974315
parent 358400 49dfb63c28b9c093f13391b999de40b01f125613
child 358402 1b3dcd9245a3fc2f2d081d4a20a712675a63a257
push id1324
push usermtabara@mozilla.com
push dateMon, 16 Jan 2017 13:07:44 +0000
treeherdermozilla-release@a01c49833940 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerstbsaunde, gchang
bugs1304449
milestone51.0a2
Bug 1304449: Part 1 - Modify MSAA IDs to be partitioned based on content id; r=tbsaunde, a=gchang MozReview-Commit-ID: AGXtMaLDFGz
accessible/windows/msaa/IDSet.h
accessible/windows/msaa/MsaaIdGenerator.cpp
accessible/windows/msaa/MsaaIdGenerator.h
accessible/windows/msaa/moz.build
--- a/accessible/windows/msaa/IDSet.h
+++ b/accessible/windows/msaa/IDSet.h
@@ -14,72 +14,81 @@
 #include "mozilla/Attributes.h"
 #include "mozilla/MathAlgorithms.h"
 #include "mozilla/SplayTree.h"
 
 namespace mozilla {
 namespace a11y {
 
 /**
- * On windows an accessible's id must be a negative 32 bit integer.  It is
+ * On windows an accessible's id must be a negative 32 bit integer. It is
  * important to support recycling arbitrary IDs because accessibles can be
  * created and destroyed at any time in the life of a page.  IDSet provides 2
- * operations: generate an ID in the range [ - 2^31, 0 ), and release an ID so
+ * operations: generate an ID in the range (0, mMaxId], and release an ID so
  * it can be allocated again.  Allocated ID are tracked by a sparse bitmap
  * implemented with a splay tree.  Nodes in the tree are keyed by the upper N
- * bits of the bitwise negation of the ID, and the node contains a bitmap
- * tracking the allocation of 2^(32 - N) IDs.
+ * bits of the ID, and the node contains a bitmap tracking the allocation of
+ * 2^(ceil(log2(mMaxId)) - N) IDs.
+ *
+ * Note that negation is handled by MsaaIdGenerator as it performs additional
+ * decoration on the ID generated by IDSet.
+ * @see mozilla::a11y::MsaaIdGenerator
  */
 class IDSet
 {
 public:
-  constexpr IDSet() : mBitSet(), mIdx(0) {}
+  constexpr explicit IDSet(const uint32_t aMaxIdBits)
+    : mBitSet()
+    , mIdx(0)
+    , mMaxId((1UL << aMaxIdBits) - 1UL)
+    , mMaxIdx(mMaxId / bitsPerElt)
+  {
+  }
 
   /**
    * Return a new unique id.
    */
   uint32_t GetID()
   {
     uint32_t idx = mIdx;
     while (true) {
       BitSetElt* elt = mBitSet.findOrInsert(BitSetElt(idx));
       if (elt->mBitvec[0] != UINT64_MAX) {
         uint32_t i = CountTrailingZeroes64(~elt->mBitvec[0]);
 
         elt->mBitvec[0] |= (1ull << i);
         mIdx = idx;
-        return ~(elt->mIdx * bitsPerElt + i);
+        return (elt->mIdx * bitsPerElt + i);
       }
 
       if (elt->mBitvec[1] != UINT64_MAX) {
         uint32_t i = CountTrailingZeroes64(~elt->mBitvec[1]);
 
         elt->mBitvec[1] |= (1ull << i);
         mIdx = idx;
-        return ~(elt->mIdx * bitsPerElt + bitsPerWord + i);
+        return (elt->mIdx * bitsPerElt + bitsPerWord + i);
       }
 
       idx++;
-      if (idx > sMaxIdx) {
+      if (idx > mMaxIdx) {
         idx = 0;
       }
 
       if (idx == mIdx) {
         MOZ_CRASH("used up all the available ids");
       }
     }
   }
 
   /**
    * Free a no longer required id so it may be allocated again.
    */
   void ReleaseID(uint32_t aID)
   {
-    aID = ~aID;
-    MOZ_ASSERT(aID < static_cast<uint32_t>(INT32_MAX));
+    MOZ_ASSERT(aID < mMaxId);
 
     uint32_t idx = aID / bitsPerElt;
     mIdx = idx;
     BitSetElt* elt = mBitSet.find(BitSetElt(idx));
     MOZ_ASSERT(elt);
 
     uint32_t vecIdx = (aID % bitsPerElt) / bitsPerWord;
     elt->mBitvec[vecIdx] &= ~(1ull << (aID % bitsPerWord));
@@ -87,17 +96,16 @@ public:
       delete mBitSet.remove(*elt);
     }
   }
 
 private:
   static const unsigned int wordsPerElt = 2;
   static const unsigned int bitsPerWord = 64;
   static const unsigned int bitsPerElt = wordsPerElt * bitsPerWord;
-  static const uint32_t sMaxIdx = INT32_MAX / bitsPerElt;
 
   struct BitSetElt : mozilla::SplayTreeNode<BitSetElt>
   {
     explicit BitSetElt(uint32_t aIdx) :
       mIdx(aIdx)
     { mBitvec[0] = mBitvec[1] = 0; }
 
     uint64_t mBitvec[wordsPerElt];
@@ -113,14 +121,16 @@ private:
         return -1;
       }
       return 1;
     }
   };
 
   SplayTree<BitSetElt, BitSetElt> mBitSet;
   uint32_t mIdx;
+  const uint32_t mMaxId;
+  const uint32_t mMaxIdx;
 };
 
 }
 }
 
 #endif
new file mode 100644
--- /dev/null
+++ b/accessible/windows/msaa/MsaaIdGenerator.cpp
@@ -0,0 +1,246 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=2 et sw=2 tw=80: */
+/* 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 "MsaaIdGenerator.h"
+
+#include "mozilla/a11y/AccessibleWrap.h"
+#include "mozilla/ClearOnShutdown.h"
+#include "mozilla/dom/ContentChild.h"
+#include "mozilla/StaticPtr.h"
+#include "mozilla/Unused.h"
+#include "nsDataHashtable.h"
+#include "nsIXULRuntime.h"
+
+// These constants may be adjusted to modify the proportion of the Child ID
+// allocated to the content ID vs proportion allocated to the unique ID. They
+// must always sum to 31, ie. the width of a 32-bit integer less the sign bit.
+
+// NB: kNumContentProcessIDBits must be large enough to successfully hold the
+// maximum permitted number of e10s content processes. If the e10s maximum
+// number of content processes changes, then kNumContentProcessIDBits must also
+// be updated if necessary to accommodate that new value!
+static const uint32_t kNumContentProcessIDBits = 7UL;
+static const uint32_t kNumUniqueIDBits = (31UL - kNumContentProcessIDBits);
+
+static_assert(kNumContentProcessIDBits + kNumUniqueIDBits == 31,
+              "Allocation of Content ID bits and Unique ID bits must sum to 31");
+
+namespace mozilla {
+namespace a11y {
+namespace detail {
+
+typedef nsDataHashtable<nsUint64HashKey, uint32_t> ContentParentIdMap;
+
+#pragma pack(push, 1)
+union MsaaID
+{
+  int32_t mInt32;
+  uint32_t mUInt32;
+  struct
+  {
+    uint32_t mUniqueID:kNumUniqueIDBits;
+    uint32_t mContentProcessID:kNumContentProcessIDBits;
+    uint32_t mSignBit:1;
+  }
+  mCracked;
+};
+#pragma pack(pop)
+
+static uint32_t
+BuildMsaaID(const uint32_t aID, const uint32_t aContentProcessID)
+{
+  MsaaID id;
+  id.mCracked.mSignBit = 0;
+  id.mCracked.mUniqueID = aID;
+  id.mCracked.mContentProcessID = aContentProcessID;
+  return ~id.mUInt32;
+}
+
+class MsaaIDCracker
+{
+public:
+  explicit MsaaIDCracker(const uint32_t aMsaaID)
+  {
+    mID.mUInt32 = ~aMsaaID;
+  }
+
+  uint32_t GetContentProcessId()
+  {
+    return mID.mCracked.mContentProcessID;
+  }
+
+  uint32_t GetUniqueId()
+  {
+    return mID.mCracked.mUniqueID;
+  }
+
+private:
+  MsaaID  mID;
+};
+
+} // namespace detail
+
+constexpr MsaaIdGenerator::MsaaIdGenerator()
+  : mIDSet(kNumUniqueIDBits)
+  , mContentProcessID(0)
+{}
+
+uint32_t
+MsaaIdGenerator::GetID()
+{
+  static const uint32_t kContentProcessId = ResolveContentProcessID();
+  uint32_t id = mIDSet.GetID();
+  MOZ_ASSERT(id <= ((1UL << kNumUniqueIDBits) - 1UL));
+  return detail::BuildMsaaID(id, kContentProcessId);
+}
+
+void
+MsaaIdGenerator::ReleaseID(AccessibleWrap* aAccWrap)
+{
+  MOZ_ASSERT(aAccWrap);
+  uint32_t id = aAccWrap->GetExistingID();
+  MOZ_ASSERT(id != AccessibleWrap::kNoID);
+  detail::MsaaIDCracker cracked(id);
+  if (cracked.GetContentProcessId() != mContentProcessID) {
+    // This may happen if chrome holds a proxy whose ID was originally generated
+    // by a content process. Since ReleaseID only has meaning in the process
+    // that originally generated that ID, we ignore ReleaseID calls for any ID
+    // that did not come from the current process.
+    MOZ_ASSERT(aAccWrap->IsProxy());
+    return;
+  }
+  mIDSet.ReleaseID(cracked.GetUniqueId());
+}
+
+bool
+MsaaIdGenerator::IsChromeID(uint32_t aID)
+{
+  detail::MsaaIDCracker cracked(aID);
+  return cracked.GetContentProcessId() == 0;
+}
+
+bool
+MsaaIdGenerator::IsIDForThisContentProcess(uint32_t aID)
+{
+  MOZ_ASSERT(XRE_IsContentProcess());
+  static const uint32_t kContentProcessId = ResolveContentProcessID();
+  detail::MsaaIDCracker cracked(aID);
+  return cracked.GetContentProcessId() == kContentProcessId;
+}
+
+bool
+MsaaIdGenerator::IsIDForContentProcess(uint32_t aID,
+                                       dom::ContentParentId aIPCContentProcessId)
+{
+  MOZ_ASSERT(XRE_IsParentProcess());
+  detail::MsaaIDCracker cracked(aID);
+  return cracked.GetContentProcessId() ==
+           GetContentProcessIDFor(aIPCContentProcessId);
+}
+
+bool
+MsaaIdGenerator::IsSameContentProcessFor(uint32_t aFirstID, uint32_t aSecondID)
+{
+  detail::MsaaIDCracker firstCracked(aFirstID);
+  detail::MsaaIDCracker secondCracked(aSecondID);
+  return firstCracked.GetContentProcessId() ==
+           secondCracked.GetContentProcessId();
+}
+
+uint32_t
+MsaaIdGenerator::ResolveContentProcessID()
+{
+  if (XRE_IsParentProcess()) {
+    return 0;
+  }
+
+  dom::ContentChild* contentChild = dom::ContentChild::GetSingleton();
+  Unused << contentChild->SendGetA11yContentId(&mContentProcessID);
+
+  MOZ_ASSERT(mContentProcessID);
+  return mContentProcessID;
+}
+
+/**
+ * Each dom::ContentParent has a 64-bit ID. This ID is monotonically increasing
+ * with each new content process, so those IDs are effectively single-use. OTOH,
+ * MSAA requires 32-bit IDs. Since we only allocate kNumContentProcessIDBits for
+ * the content process ID component, the MSAA content process ID value must be
+ * reusable. sContentParentIdMap holds the current associations between
+ * dom::ContentParent IDs and the MSAA content parent IDs that have been
+ * allocated to them.
+ */
+static StaticAutoPtr<detail::ContentParentIdMap> sContentParentIdMap;
+
+static const uint32_t kBitsPerByte = 8UL;
+// Set sContentProcessIdBitmap[0] to 1 to reserve the Chrome process's id
+static uint64_t sContentProcessIdBitmap[(1UL << kNumContentProcessIDBits) /
+                                        (sizeof(uint64_t) * kBitsPerByte)] = {1ULL};
+static const uint32_t kBitsPerElement = sizeof(sContentProcessIdBitmap[0]) *
+                                        kBitsPerByte;
+
+uint32_t
+MsaaIdGenerator::GetContentProcessIDFor(dom::ContentParentId aIPCContentProcessID)
+{
+  MOZ_ASSERT(XRE_IsParentProcess() && NS_IsMainThread());
+  if (!sContentParentIdMap) {
+    sContentParentIdMap = new detail::ContentParentIdMap();
+    ClearOnShutdown(&sContentParentIdMap);
+  }
+
+  uint32_t value = 0;
+  if (sContentParentIdMap->Get(aIPCContentProcessID, &value)) {
+    return value;
+  }
+
+  uint32_t index = 0;
+  for (; index < ArrayLength(sContentProcessIdBitmap); ++index) {
+    if (sContentProcessIdBitmap[index] == UINT64_MAX) {
+      continue;
+    }
+    uint32_t bitIndex = CountTrailingZeroes64(~sContentProcessIdBitmap[index]);
+    MOZ_ASSERT(!(sContentProcessIdBitmap[index] & (1ULL << bitIndex)));
+    MOZ_ASSERT(bitIndex != 0 || index != 0);
+    sContentProcessIdBitmap[index] |= (1ULL << bitIndex);
+    value = index * kBitsPerElement + bitIndex;
+    break;
+  }
+
+  // If we run out of content process IDs, we're in trouble
+  MOZ_RELEASE_ASSERT(index < ArrayLength(sContentProcessIdBitmap));
+
+  sContentParentIdMap->Put(aIPCContentProcessID, value);
+  return value;
+}
+
+void
+MsaaIdGenerator::ReleaseContentProcessIDFor(dom::ContentParentId aIPCContentProcessID)
+{
+  MOZ_ASSERT(XRE_IsParentProcess() && NS_IsMainThread());
+  if (!sContentParentIdMap) {
+    // Since Content IDs are generated lazily, ContentParent might attempt
+    // to release an ID that was never allocated to begin with.
+    return;
+  }
+
+  Maybe<uint32_t> mapping = sContentParentIdMap->GetAndRemove(aIPCContentProcessID);
+  if (!mapping) {
+    // Since Content IDs are generated lazily, ContentParent might attempt
+    // to release an ID that was never allocated to begin with.
+    return;
+  }
+
+  uint32_t index = mapping.ref() / kBitsPerElement;
+  MOZ_ASSERT(index < ArrayLength(sContentProcessIdBitmap));
+
+  uint64_t mask = 1ULL << (mapping.ref() % kBitsPerElement);
+  MOZ_ASSERT(sContentProcessIdBitmap[index] & mask);
+
+  sContentProcessIdBitmap[index] &= ~mask;
+}
+
+} // namespace a11y
+} // namespace mozilla
new file mode 100644
--- /dev/null
+++ b/accessible/windows/msaa/MsaaIdGenerator.h
@@ -0,0 +1,57 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=2 et sw=2 tw=80: */
+/* 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 mozilla_a11y_MsaaIdGenerator_h
+#define mozilla_a11y_MsaaIdGenerator_h
+
+#include "mozilla/a11y/IDSet.h"
+
+#include "mozilla/dom/ipc/IdType.h"
+
+namespace mozilla {
+namespace a11y {
+
+class AccessibleWrap;
+
+/**
+ * This class is responsible for generating child IDs used by our MSAA
+ * implementation. Since e10s requires us to differentiate IDs based on the
+ * originating process of the accessible, a portion of the ID's bits are
+ * allocated to storing that information. The remaining bits represent the
+ * unique ID of the accessible, within that content process.
+ *
+ * The constants kNumContentProcessIDBits and kNumUniqueIDBits in the
+ * implementation are responsible for determining the proportion of bits that
+ * are allocated for each purpose.
+ */
+class MsaaIdGenerator
+{
+public:
+  constexpr MsaaIdGenerator();
+
+  uint32_t GetID();
+  void ReleaseID(AccessibleWrap* aAccWrap);
+  bool IsChromeID(uint32_t aID);
+  bool IsIDForThisContentProcess(uint32_t aID);
+  bool IsIDForContentProcess(uint32_t aID,
+                             dom::ContentParentId aIPCContentProcessId);
+  bool IsSameContentProcessFor(uint32_t aFirstID, uint32_t aSecondID);
+
+  uint32_t GetContentProcessIDFor(dom::ContentParentId aIPCContentProcessID);
+  void ReleaseContentProcessIDFor(dom::ContentParentId aIPCContentProcessID);
+
+private:
+  uint32_t ResolveContentProcessID();
+
+private:
+  IDSet     mIDSet;
+  uint32_t  mContentProcessID;
+};
+
+} // namespace a11y
+} // namespace mozilla
+
+#endif // mozilla_a11y_MsaaIdGenerator_h
--- a/accessible/windows/msaa/moz.build
+++ b/accessible/windows/msaa/moz.build
@@ -8,31 +8,33 @@ EXPORTS += [
     'IUnknownImpl.h',
 ]
 
 EXPORTS.mozilla.a11y += [
     'AccessibleWrap.h',
     'Compatibility.h',
     'HyperTextAccessibleWrap.h',
     'IDSet.h',
+    'MsaaIdGenerator.h',
 ]
 
 UNIFIED_SOURCES += [
     'AccessibleWrap.cpp',
     'ApplicationAccessibleWrap.cpp',
     'ARIAGridAccessibleWrap.cpp',
     'ChildIDThunk.cpp',
     'Compatibility.cpp',
     'DocAccessibleWrap.cpp',
     'EnumVariant.cpp',
     'HTMLTableAccessibleWrap.cpp',
     'HTMLWin32ObjectAccessible.cpp',
     'HyperTextAccessibleWrap.cpp',
     'ImageAccessibleWrap.cpp',
     'IUnknownImpl.cpp',
+    'MsaaIdGenerator.cpp',
     'nsWinUtils.cpp',
     'Platform.cpp',
     'RootAccessibleWrap.cpp',
     'TextLeafAccessibleWrap.cpp',
 ]
 
 # This file cannot be built in unified mode because it includes ISimpleDOMNode_i.c.
 SOURCES += [