1406303 - Refactor malloc_rtree_t

Status: RESOLVED FIXED

(Core :: Memory Allocator, enhancement)

Comment 1

[Mike Hommey [:glandium]]

Attachment: Bug 1406303 - Refactor malloc_rtree_get/set.

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/

Comment 2

[Mike Hommey [:glandium]]

Attachment: Bug 1406303 - Turn malloc_rtree_t into a C++ class.

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/

Comment 3

[Mike Hommey [:glandium]]

Attachment: Bug 1406303 - Simplify the calculation of AddressRadixTree's bits_per_level.

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/

Comment 4

[Mike Hommey [:glandium]]

Attachment: Bug 1406303 - Simplify the calculation of AddressRadixTree's height.

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/

Comment 5

[Mike Hommey [:glandium]]

Attachment: Bug 1406303 - Only store 2 levels of bit sizes for the radix tree.

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/

Comment 6

[Mike Hommey [:glandium]]

Attachment: Bug 1406303 - Make the number of significant bits used by the radix tree a template parameter.

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/

Comment 7

[Mike Hommey [:glandium]]

Attachment: Bug 1406303 - Don't heap-allocate the global chunk radix tree.

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 8

[Nicholas Nethercote [inactive]]

Comment on attachment 8915873 [details]
Bug 1406303 - Refactor malloc_rtree_get/set.

https://reviewboard.mozilla.org/r/187128/#review192574

::: memory/build/mozjemalloc.cpp:1762
(Diff revision 1)
>  
>  	return (ret);
>  }
>  
> -#define	MALLOC_RTREE_GET_GENERATE(f)					\
> -/* The least significant bits of the key are ignored. */		\
> +static inline void**
> +malloc_rtree_get_slot(malloc_rtree_t* aTree, uintptr_t aKey, bool aCreate=false)

Spaces around '='.

Is it worth commenting here that the tree must be locked before this function can be called?

::: memory/build/mozjemalloc.cpp:1776
(Diff revision 1)
> -	MALLOC_RTREE_LOCK(&rtree->lock);				\
> -	for (i = lshift = 0, height = rtree->height, node = rtree->root;\
> -	    i < height - 1;						\
> -	    i++, lshift += bits, node = child) {			\
> -		bits = rtree->level2bits[i];				\
> -		subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits);	\
> +       i++, lshift += bits, node = child) {
> +    bits = aTree->level2bits[i];
> +    subkey = (aKey << lshift) >> ((SIZEOF_PTR << 3) - bits);
> +    child = (void**) node[subkey];
> +    if (!child && aCreate) {
> +      child = (void**) base_calloc(1 << aTree->level2bits[i+1], sizeof(void*));

Spaces around '+'.

Comment 9

[Nicholas Nethercote [inactive]]

Comment on attachment 8915874 [details]
Bug 1406303 - Turn malloc_rtree_t into a C++ class.

https://reviewboard.mozilla.org/r/187130/#review192576

::: memory/build/mozjemalloc.cpp:1770
(Diff revision 1)
> +  }
>  
> -	ret->root = (void**)base_calloc(1, sizeof(void *) << ret->level2bits[0]);
> -	if (!ret->root) {
> +  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
> +     * We leak the rtree here, since there's no generic base

I think this comment would fit on a single line, esp. if it uses C++ style.

::: memory/build/mozjemalloc.cpp:1795
(Diff revision 1)
>         i++, lshift += bits, node = child) {
> -    bits = aTree->level2bits[i];
> -    subkey = (aKey << lshift) >> ((SIZEOF_PTR << 3) - bits);
> +    bits = mLevel2Bits[i];
> +    subkey = (key << lshift) >> ((SIZEOF_PTR << 3) - bits);
>      child = (void**) node[subkey];
>      if (!child && aCreate) {
> -      child = (void**) base_calloc(1 << aTree->level2bits[i+1], sizeof(void*));
> +      child = (void**) base_calloc(1 << mLevel2Bits[i+1], sizeof(void*));

Spaces around '+'.

Comment 10

[Nicholas Nethercote [inactive]]

Comment on attachment 8915875 [details]
Bug 1406303 - Simplify the calculation of AddressRadixTree's bits_per_level.

https://reviewboard.mozilla.org/r/187132/#review192578

Thanks for the good commit message. Have you confirmed empirically that the result matches theory? :)

Comment 11

[Nicholas Nethercote [inactive]]

Comment on attachment 8915877 [details]
Bug 1406303 - Only store 2 levels of bit sizes for the radix tree.

https://reviewboard.mozilla.org/r/187136/#review192582

::: memory/build/mozjemalloc.cpp:661
(Diff revision 1)
>  #endif
>  
>    malloc_spinlock_t mLock;
>    void** mRoot;
>    unsigned mHeight;
> -  unsigned mLevel2Bits[1]; // Dynamically sized.
> +  unsigned mLevel2Bits[2];

It would be useful to have a comment here about why there are two entries.

Actually, I think it would be better to have two separate fields instead of a 2-element array. Can you do that?

Comment 12

[Nicholas Nethercote [inactive]]

> Actually, I think it would be better to have two separate fields instead of
> a 2-element array. Can you do that?

Oh, I see the next patch gets rid of the array.

Comment 13

[Nicholas Nethercote [inactive]]

Comment on attachment 8915878 [details]
Bug 1406303 - Make the number of significant bits used by the radix tree a template parameter.

https://reviewboard.mozilla.org/r/187138/#review192584

::: memory/build/mozjemalloc.cpp:669
(Diff revision 1)
>  #if (SIZEOF_PTR == 4)
>    static const size_t kNodeSize2Pow = 14;
>  #else
>    static const size_t kNodeSize2Pow = CACHELINE_2POW;
>  #endif
> +  static const size_t kBitsPerLevel = kNodeSize2Pow - SIZEOF_PTR_2POW;

I don't like this name because it's not clear that it excludes level 1. What about kBitsAtLevel2Plus? (Or something else where the 1 vs. 2+ distinction is clear.)

Comment 14

[Nicholas Nethercote [inactive]]

Comment on attachment 8915879 [details]
Bug 1406303 - Don't heap-allocate the global chunk radix tree.

https://reviewboard.mozilla.org/r/187140/#review192586

Comment 15

[Nicholas Nethercote [inactive]]

Comment on attachment 8915876 [details]
Bug 1406303 - Simplify the calculation of AddressRadixTree's height.

https://reviewboard.mozilla.org/r/187134/#review192580

Again: have you checked this empirically?

Comment 16

[Mike Hommey [:glandium]]

(In reply to Nicholas Nethercote [:njn] from comment #8)
> Is it worth commenting here that the tree must be locked before this
> function can be called?

We're actually only locking on write.

Comment 17

[Mike Hommey [:glandium]]

(In reply to Nicholas Nethercote [:njn] from comment #10)
> Comment on attachment 8915875 [details]
> Bug 1406303 - Simplify the calculation of AddressRadixTree's bits_per_level.
> 
> https://reviewboard.mozilla.org/r/187132/#review192578
> 
> Thanks for the good commit message. Have you confirmed empirically that the
> result matches theory? :)

As a matter of fact, I did.

(In reply to Nicholas Nethercote [:njn] from comment #15)
> Comment on attachment 8915876 [details]
> Bug 1406303 - Simplify the calculation of AddressRadixTree's height.
> 
> https://reviewboard.mozilla.org/r/187134/#review192580
> 
> Again: have you checked this empirically?

For this one, I actually went in the opposite direction: I had a hunch that it would work this way, checked empirically, and then worked out the math.

Comment 18

[Mike Hommey [:glandium]]

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 19

[Mike Hommey [:glandium]]

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 20

[Mike Hommey [:glandium]]

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 21

[Mike Hommey [:glandium]]

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 22

[Mike Hommey [:glandium]]

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 23

[Mike Hommey [:glandium]]

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 24

[Mike Hommey [:glandium]]

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/

Comment 25

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/e42bb7139c71
Refactor malloc_rtree_get/set. r=njn
https://hg.mozilla.org/integration/autoland/rev/7b2056d32ff5
Turn malloc_rtree_t into a C++ class. r=njn
https://hg.mozilla.org/integration/autoland/rev/cd3472504445
Simplify the calculation of AddressRadixTree's bits_per_level. r=njn
https://hg.mozilla.org/integration/autoland/rev/387202ecf011
Simplify the calculation of AddressRadixTree's height. r=njn
https://hg.mozilla.org/integration/autoland/rev/94b89dd64fc7
Only store 2 levels of bit sizes for the radix tree. r=njn
https://hg.mozilla.org/integration/autoland/rev/6ee5dedf4f64
Make the number of significant bits used by the radix tree a template parameter. r=njn
https://hg.mozilla.org/integration/autoland/rev/d57bcfffe5ba
Don't heap-allocate the global chunk radix tree. r=njn

Comment 26

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/e42bb7139c71
https://hg.mozilla.org/mozilla-central/rev/7b2056d32ff5
https://hg.mozilla.org/mozilla-central/rev/cd3472504445
https://hg.mozilla.org/mozilla-central/rev/387202ecf011
https://hg.mozilla.org/mozilla-central/rev/94b89dd64fc7
https://hg.mozilla.org/mozilla-central/rev/6ee5dedf4f64
https://hg.mozilla.org/mozilla-central/rev/d57bcfffe5ba