RFR: 8312132: Add tracking of multiple address spaces in NMT [v5]

[Thomas Stuefe]

On Tue, 30 Apr 2024 09:40:40 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Huh? Should the indexes not be stable across resize? Unless you shrink, which we would not need to do?
>> 
>> The base address of the array may change, but the relative order of the items in it hopefully not.
>
>> Should the indexes not be stable across resize?
> 
> **No.** The hash is determined as: `int place_to_put_element = hash_of(the_thing) % size_of_array;`
> 
> The `size_of_array` will change, so when probing for/inserting the same NCS after a resize a new index may be used. Meaning, we will have duplicate entries. If we're OK with this, then that's fine. It means that equality checking will require dereferencing the index and doing the full NCS comparison.
> 
> ```c++
> GA<int> ht(2); // Size 2
> int oldidx = hash(4) % ht.size(); // oldidx == 0
> ht.put(oldidx, 4);
> // Out of room, resize
> ht.grow(4);
> // Now imagine you insert oldidx into some treap node's metadata
> // Now we're adding the same int, 4, again but get a different index
> int newidx = hash(4) % ht.size(); // newidx == 2
> // Now what?

Ah, I get the confusion. This is not what I meant.

What I mean was:

At the moment you malloc space for NativeCallStack, then keep NativeCallStack* in the hash map. NativeCallStack* now uniquely identifies your stack.

What I meant is to place NativeCallStack in a growable array. Now, you have a 32-bit or even a 16-bit index into that array. That index uniquely identifies the stack. You keep that index the hashmap. The hashmap does not change. Hashmap storage has nothing to do with that array. This is not the bucket array.

Basically, you replace the malloc for the NativeCallStack with a placement-new in a new growable array. The rest stays the same. 

But now, you have a 32-bit or even 16-bit index, and that is smaller than a native pointer, which makes it possible to encode the stack information in a tree node much more succinctively. This makes it possible to encode the whole tree node metainfo very comfortably in a single 64-bit value. You can even get both in- and out-state of the VMATree into a single 64-bit value like this:

bits 0-7 MEMFLAGS in
bits 8-16 State in
bits 16-31 callstack index in

bits 32-39 MEMFLAGS out
bits 40-47 State out
bits 48-63 callstack index out

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/18289#discussion_r1584629296