RFR: 8251158: Implementation of JEP 387: Elastic Metaspace

[Leo Korinth]

Hi, review of: freeBlocks.?pp, blockTree.?pp and binList.hpp below

I have some comments in addition to those from Coleen:

### freeBlocks.hpp:

75
76   static const size_t splinter_threshold = 0;// 0x100;
77

splinter_threshold with the strange comment // 0X100, what is it
supposed to be used for?  (always 0, but with a comment 0x100;). Maybe
related to this, is that I have problems to understand how allocation
guards are handled when memory is put back to the freelist, I can not
see the pointer being decremented (the inverse operation of
payload_from_prefix, prefix_from_payload seems never to be used, and I
fail to find the operation done manually either.

68   typedef BinList32 SmallBlocksType;
69
70   // _small_blocks takes care of small to very small blocks.
71   SmallBlocksType _small_blocks;
   
   
I think all of BinListXX typedefs can be removed and also the
SmallBlocksType typedef. The SmallBlocksType is only used once if we
rewrite

const static size_t minimal_word_size = SmallBlocksType::minimal_word_size;
to
const static size_t minimal_word_size = _small_blocks.minimal_word_size;

(and also change the name of minimal_word_size so that we can see it
is a constant)

84
85   // Retrieve a block of at least requested_word_size.
86   MetaWord* get_block(size_t requested_word_size);
87

The function named get_block, this is not a getter, this mutates the
object. I would prefer remove_block (goes well with add_block), and I
would like that rename to propagate to both blockTree and binList.

###  binList.hpp:

Maybe another name for binList, binLookup for example?  When I hear
list I am thinking /linked/ list and that might just be my problem,
sorry if that is that case, and then ignore this point.

76
77 template <size_t smallest_size, int num_lists>
78 class BinListImpl {
79

Template argument smallest_size would be nice if the unit of the size
(words) is mentioned in the name. It is so easy to mix sizes up.

82   // a mask to speed up searching for populated lists.
83   // 0 marks an empty list, 1 for a non-empty one.
84   typedef uint32_t mask_t;

Is a mask really speeding up anything? Seems the code would be a bit
simpler removing the mask.

158   // Given a word_size, searches and returns a block of at least that size.
159   // Block may be larger. Real block size is returned in *p_real_word_size.
160   MetaWord* get_block(size_t word_size, size_t* p_real_word_size) {
get_block -> remove_block

217 typedef BinListImpl<2, 8>  BinList8;
218 typedef BinListImpl<2, 16> BinList16;
219 typedef BinListImpl<2, 32> BinList32;
220 typedef BinListImpl<2, 64> BinList64;
  
BinListXX typedefs could be removed I think. (see comment above)


### blocktree.hpp

79   struct node_t {
80
81     // Normal tree node stuff...
82     node_t* parent;
83     node_t* left;
84     node_t* right;
85


I think in the future we could make the node_t without a parent
pointer, that would make the node size somewhat smaller and we could
then be able to fit smaller memory areas into the tree. The code
should be somewhat simpler as well I think. Maybe file a future
improvement for this?

98   // Largest node size, (bit arbitrarily) capped at 4M since we know this to
99   // be the max possible metaspace allocation size. TODO. Do this better.
100   const static size_t maximal_word_size = 4 * M;

maximal_word_size should take its value from MAX_CHUNK_BYTE_SIZE in
some way if it is not too hard.

102   // We need nodes to be at least large enough to hold a node_t
103   const static size_t minimal_word_size =
104       (sizeof(node_t) + sizeof(MetaWord) - 1) / sizeof(MetaWord);

maybe add a division-ceil comment?

172   // Given a node n, return its predecessor in the tree
173   // (node with the next-smaller size).
174   static node_t* successor(node_t* n) {

The comment is wrong on successor (I guess it is copied from predecessor).

199     if (parent != NULL) {
200       if (parent->left == child) { // I am a left child

I think  "// child is a left child" is better

215   // Given a node n and a node forebear, insert n under forebear
216   void insert(node_t* forebear, node_t* n) {

The name forebear confused me, it is just a root for
insertion, and has no existing ancestor relation to "n".

230           if (_largest_size_added < n->size) {
231             _largest_size_added = n->size;
232           }

This is unnecessary as it is already done by add_block(MetaWord* p,
size_t word_size). I also think that add_block is the better place to
have the update. The method maybe could be static after this change? I
also think the opposite decrease update should be done in remove_block
to keep the symmetry.

There are at least two recursive calls of insert that could be
tail-called instead (it would be somewhat harder to read, so I am not
proposing it). However, with an unbalanced tree I guess we
could get deep call stacks if we are unlucky. I guess it is best to
leave this as is, just wanted to comment on it.

278   // Given a node n, remove it from the tree and repair tree.
279   void remove_node_from_tree(node_t* n) {
280
281     assert(n->next == NULL, "do not delete a node which has a non-empty list");

Is there any reason for not calling the remove_from_list logic
here instead of in get_block? We would get rid of this assert, and I
think it would be better placed logically.

283     // Maintain largest size node to speed up lookup
284     if (n->size == _largest_size_added) {
285       node_t* pred = predecessor(n);
286       if (pred != NULL) {
287         _largest_size_added = pred->size;
288       } else {
289         _largest_size_added = 0;
290       }
291     }

As I said above, the _largest_size_added logic seems (to me) to fit
better in remove_block(). It is not really a tree operation but a cached
result.

I also wonder if the caching is really needed.

If we have a huge tree, /and/ we fail to find a free area
/repeatedly/, the caching will perform better.

But If the tree is empty, it will be as fast to check anyway, and I
guess that is the common case).

Every time we remove an element from the tree, the predecessor()
function needs to be called at the end (just) to update the cached
value, so each remove (that successfully fetch free memory) is a bit
more expensive with caching.

Just a thought.

379     node_t* n = (node_t*)p;
380     n->size = word_size;
381     n->next = n->left = n->right = n->parent = NULL;

Placement new would look better in my opinion.

Thanks,
Leo