There is a lot of redundancy between malloc_rtree_get and malloc_rtree_set. Essentially, they both look up a slot, and either get a value or set a value in that slot. malloc_rtree_get doesn't create a tree path for the slot when it doesn't exist. And the MALLOC_RTREE_GET_GENERATE macro machinery makes malloc_rtree_get retry with a lock and validate both results agree in debug builds. By introducing a malloc_rtree_get_slot function that returns a slot, optionally creating a tree path to it, we remove the redundancy between _get and _set, and we can avoid the macro machinery as well. Review commit: https://reviewboard.mozilla.org/r/187128/diff/#index_header See other reviews: https://reviewboard.mozilla.org/r/187128/

The only semantic change is in the value returned by Set, which now returns whether the value could be set or not. Review commit: https://reviewboard.mozilla.org/r/187130/diff/#index_header See other reviews: https://reviewboard.mozilla.org/r/187130/

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. Review commit: https://reviewboard.mozilla.org/r/187132/diff/#index_header See other reviews: https://reviewboard.mozilla.org/r/187132/

The tree height was defined as: height = aBits / bits_per_level; if (height * bits_per_level != aBits) { height++; } What's wanted here is a height that covers all the bits, where the first level might cover less than bits_per_level. So aBits / bits_per_level gets us the height covered by levels with exactly bits_per_level bits. The tree height is one more when there are remaining bits. Put differently, we can write aBits as: aBits = bits_per_level * x + y with y < bits_per_level. We have: aBits / bits_per_level = x. height = x when y = 0, and x + 1 when y > 0. We're looking for a number z such that height = (aBits + z) / bits_per_level. Or: height = (bits_per_level * x + y + z) / bits_per_level. = x + (y + z) / bits_per_level. So we're looking for a z such that (y + z) / bits_per_level = 0 when y = 0 = 1 when y > 0 The properties of the integer division are such that the above means: 0 <= y + z < bits_per_level when y = 0 bits_per_level <= y + z < 2 * bits_per_level when y > 0 Which gives us: 0 <= z < bits_per_level bits_per_level - y <= z < 2 * bits_per_level - y when y > 0 y being < bit_per_level per the constraint further above, 2 * bits_per_level - y > bits_per_level. So all in all, we want a z such that bits_per_level - y <= z < bits_per_level with 0 < y < bits_per_level The largest value where this is true is z = bits_per_level - 1. In summary, height = (aBits + bits_per_level - 1) / bits_per_level is the same as the height as originally defined. With that formula, it's self evident that height * bits_per_level is always >= aBits, so we remove the assertion. Review commit: https://reviewboard.mozilla.org/r/187134/diff/#index_header See other reviews: https://reviewboard.mozilla.org/r/187134/

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. Review commit: https://reviewboard.mozilla.org/r/187136/diff/#index_header See other reviews: https://reviewboard.mozilla.org/r/187136/

All the parameters of the radix tree (bits per level, height) are derived from the aBits argument to ::Create in a straightforward way. aBits itself is a constant at the call point, making them all constants, so we can turn all of them as constants at compile time instead of storing as data. Review commit: https://reviewboard.mozilla.org/r/187138/diff/#index_header See other reviews: https://reviewboard.mozilla.org/r/187138/

Now that the radix tree structure has a fixed size, we can just allocate the chunk radix tree object statically. Review commit: https://reviewboard.mozilla.org/r/187140/diff/#index_header See other reviews: https://reviewboard.mozilla.org/r/187140/

Comment on attachment 8915873 [details] Bug 1406303 - Refactor malloc_rtree_get/set. Review request updated; see interdiff: https://reviewboard.mozilla.org/r/187128/diff/1-2/

Comment on attachment 8915874 [details] Bug 1406303 - Turn malloc_rtree_t into a C++ class. Review request updated; see interdiff: https://reviewboard.mozilla.org/r/187130/diff/1-2/

Comment on attachment 8915875 [details] Bug 1406303 - Simplify the calculation of AddressRadixTree's bits_per_level. Review request updated; see interdiff: https://reviewboard.mozilla.org/r/187132/diff/1-2/

Comment on attachment 8915876 [details] Bug 1406303 - Simplify the calculation of AddressRadixTree's height. Review request updated; see interdiff: https://reviewboard.mozilla.org/r/187134/diff/1-2/

Comment on attachment 8915877 [details] Bug 1406303 - Only store 2 levels of bit sizes for the radix tree. Review request updated; see interdiff: https://reviewboard.mozilla.org/r/187136/diff/1-2/

Comment on attachment 8915878 [details] Bug 1406303 - Make the number of significant bits used by the radix tree a template parameter. Review request updated; see interdiff: https://reviewboard.mozilla.org/r/187138/diff/1-2/

Comment on attachment 8915879 [details] Bug 1406303 - Don't heap-allocate the global chunk radix tree. Review request updated; see interdiff: https://reviewboard.mozilla.org/r/187140/diff/1-2/