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.
--- 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;