Bug 1406303 - Simplify the calculation of AddressRadixTree's bits_per_level. r?njn
bits_per_level was defined as:
ffs(pow2_ceil((kNodeSize / sizeof(void*)))) - 1
kNodeSize is (1U << 14) when SIZEOF_PTR is 4 (sizeof(void*) being the
same). Otherwise, it's CACHELINE, which is (1U << 6).
The most important part, though, is that it's always a power of 2.
And it's divided by sizeof(void*) which is always a power or 2.
The result of that division is thus always a power of 2, as long as
kNodeSize is larger than the size of a pointer, which it is.
The argument to pow2_ceil being a power of 2, pow2_ceil is a noop,
so it can go away. And the argument to ffs being a power of 2, it
returns one more than n that matches 1 << n == value. So overall
the expression returns the number of shifts for
kNodeSize / SIZEOF_PTR.
Transforming kNodeSize to a number of shifts/power of 2, the expression
can then be simplified as kNodeSize2Pow - SIZEOF_PTR_2POW.
--- a/memory/build/mozjemalloc.cpp
+++ b/memory/build/mozjemalloc.cpp
@@ -642,22 +642,22 @@ struct ExtentTreeBoundsTrait : public Ex
};
/******************************************************************************/
/*
* Radix tree data structures.
*/
class AddressRadixTree {
- // Size of each radix tree node (must be a power of 2).
+ // Size of each radix tree node (as a power of 2).
// This impacts tree depth.
#if (SIZEOF_PTR == 4)
- static const size_t kNodeSize = 1U << 14;
+ static const size_t kNodeSize2Pow = 14;
#else
- static const size_t kNodeSize = CACHELINE;
+ static const size_t kNodeSize2Pow = CACHELINE_2POW;
#endif
malloc_spinlock_t mLock;
void** mRoot;
unsigned mHeight;
unsigned mLevel2Bits[1]; // Dynamically sized.
public:
@@ -1734,18 +1734,17 @@ pages_copy(void *dest, const void *src,
#endif
AddressRadixTree*
AddressRadixTree::Create(unsigned aBits)
{
AddressRadixTree* ret;
unsigned bits_per_level, height, i;
- bits_per_level = ffs(pow2_ceil((AddressRadixTree::kNodeSize /
- sizeof(void*)))) - 1;
+ bits_per_level = AddressRadixTree::kNodeSize2Pow - SIZEOF_PTR_2POW;
height = aBits / bits_per_level;
if (height * bits_per_level != aBits) {
height++;
}
MOZ_DIAGNOSTIC_ASSERT(height * bits_per_level >= aBits);
ret = (AddressRadixTree*)base_calloc(1, sizeof(AddressRadixTree) +
(sizeof(unsigned) * (height - 1)));