Bug 1406303 - Only store 2 levels of bit sizes for the radix tree. r?njn draft
authorMike Hommey <mh+mozilla@glandium.org>
Fri, 06 Oct 2017 15:24:07 +0900
changeset 677070 34d180d496601d830ca54a9735671a08cd21ff4a
parent 677069 d37d48915b9d4e8feca3c925c54f2f013f27f0e8
child 677071 153dabc7d854716d7439c2f466ba7059b70f0aec
push id83679
push userbmo:mh+mozilla@glandium.org
push dateMon, 09 Oct 2017 23:14:34 +0000
reviewersnjn
bugs1406303
milestone58.0a1
Bug 1406303 - Only store 2 levels of bit sizes for the radix tree. r?njn All levels except the first are using the same size, and in some cases, even the first uses the same size. Only storing those two different sizes allows to fix the class size, while not making the code significantly more complex.
memory/build/mozjemalloc.cpp
--- a/memory/build/mozjemalloc.cpp
+++ b/memory/build/mozjemalloc.cpp
@@ -653,17 +653,17 @@ class AddressRadixTree {
   static const size_t kNodeSize2Pow = 14;
 #else
   static const size_t kNodeSize2Pow = CACHELINE_2POW;
 #endif
 
   malloc_spinlock_t mLock;
   void** mRoot;
   unsigned mHeight;
-  unsigned mLevel2Bits[1]; // Dynamically sized.
+  unsigned mLevel2Bits[2];
 
 public:
   static AddressRadixTree* Create(unsigned aBits);
 
   inline void* Get(void* aAddr);
 
   // Returns whether the value was properly set
   inline bool Set(void* aAddr, void* aValue);
@@ -1732,37 +1732,34 @@ pages_copy(void *dest, const void *src, 
 	    (vm_address_t)dest);
 }
 #endif
 
 AddressRadixTree*
 AddressRadixTree::Create(unsigned aBits)
 {
   AddressRadixTree* ret;
-  unsigned bits_per_level, height, i;
+  unsigned bits_per_level, height;
 
   bits_per_level = AddressRadixTree::kNodeSize2Pow - SIZEOF_PTR_2POW;
   height = (aBits + bits_per_level - 1) / bits_per_level;
 
-  ret = (AddressRadixTree*)base_calloc(1, sizeof(AddressRadixTree) +
-      (sizeof(unsigned) * (height - 1)));
+  ret = (AddressRadixTree*)base_calloc(1, sizeof(AddressRadixTree));
   if (!ret) {
     return nullptr;
   }
 
   malloc_spin_init(&ret->mLock);
   ret->mHeight = height;
   if (bits_per_level * height > aBits) {
     ret->mLevel2Bits[0] = aBits % bits_per_level;
   } else {
     ret->mLevel2Bits[0] = bits_per_level;
   }
-  for (i = 1; i < height; i++) {
-    ret->mLevel2Bits[i] = bits_per_level;
-  }
+  ret->mLevel2Bits[1] = bits_per_level;
 
   ret->mRoot = (void**)base_calloc(1 << ret->mLevel2Bits[0], sizeof(void*));
   if (!ret->mRoot) {
     // We leak the rtree here, since there's no generic base deallocation.
     return nullptr;
   }
 
   return ret;
@@ -1775,35 +1772,35 @@ AddressRadixTree::GetSlot(void* aKey, bo
   uintptr_t subkey;
   unsigned i, lshift, height, bits;
   void** node;
   void** child;
 
   for (i = lshift = 0, height = mHeight, node = mRoot;
        i < height - 1;
        i++, lshift += bits, node = child) {
-    bits = mLevel2Bits[i];
+    bits = mLevel2Bits[i ? 1 : 0];
     subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits);
     child = (void**) node[subkey];
     if (!child && aCreate) {
-      child = (void**) base_calloc(1 << mLevel2Bits[i + 1], sizeof(void*));
+      child = (void**) base_calloc(1 << mLevel2Bits[1], sizeof(void*));
       if (child) {
         node[subkey] = child;
       }
     }
     if (!child) {
       return nullptr;
     }
   }
 
   /*
    * node is a leaf, so it contains values rather than node
    * pointers.
    */
-  bits = mLevel2Bits[i];
+  bits = mLevel2Bits[i ? 1 : 0];
   subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits);
   return &node[subkey];
 }
 
 void*
 AddressRadixTree::Get(void* aKey)
 {
   void* ret = nullptr;