RFR: 8351661: NMT: VMATree should support separate call-stacks for reserve and commit operations [v13]

[Afshin Zafari]

On Wed, 23 Apr 2025 07:57:13 GMT, Afshin Zafari <azafari at openjdk.org> wrote:

>> In NMT detail mode, we need to have separate call-stacks for Reserve and Commit operations.
>> This PR adds a second stack to every node that will be used when committing (and uncommitting) the start node of a reserved region.
>
> Afshin Zafari has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains 14 additional commits since the last revision:
> 
>  - Merge remote-tracking branch 'origin/master' into _8351661_separate_call_stack_reserve_commit
>  - one more test case for overlapping multiple regions
>  - 10 cases added for overlapping with multiple regions
>  - 24 test-cases added for full coverage of cases.
>  - fixed format of the missed Pre
>  - Pre conditions are also visualized.
>  - fixes. New check_tree impl and visualization.
>  - fix the GHA failures.
>  - improvements
>  - more fixes.
>  - ... and 4 more: https://git.openjdk.org/jdk/compare/3056820f...b8b40862

Whatever approach we take, all the semantics, impl and test-cases should be easily understandable and maintainable.
In future we may receive RFEs like these:
- test-case TTT fails if PPPP is true
- regions with different call-stacks should not merge
- it is preferred to store call-stacks for uncommit operations
- re-committing a region should/not change the MemTag

then we need to dig into the semantics, impl and test-cases to find the reason and also the appropriate fix.
I'd rather to have a straightforward approach for all the semantics. I think for handlining a request `(op, A, B, tag, call-stack)` we can do something like this:
1- how [A,B) overlaps with existing nodes. decompose overlaps into sub-regions.
2- what is the new state of overlapped regions 
3- what is the new tag of overlapped regions
4- what is the new reserve-call-stack of overlapped regions
5- what is the new commit-call-stack of overlapped regions
6- what is the summary diff of the result
7- any new node to be inserted?
8- if any existing node to be deleted? or to be updated?

Or equivalently:

overlaps_info = func_1(op, A, B, tag, call-stack, tree)
for each ov_rgns in overlap_info : 
  new_state = func_2(op, A, B, tag, call-stack, tree, ov_rgns)
  new_tag = func_3(op, A, B, tag,  call-stack, tree, ov_rgns)
  new_reserve_call_stack = func_4( ...)
  new_commit_call_stack = func_5(...)
  summary_diff = func_6(...)
  node_insert = func_7(..)
  node_update_delete = func_8(...)      
  apply_changes(tree)


which basically separates "What To Do" from "When To Do". Each `func_n()` can have a map from inputs to its output such as:

 StateType func_2(op,  A, B) {
  // new state depends on state of existing region and the requested operation
  //         existing state
  //           Rl  Rs  C
  //         --------------
  //     Rl    Rl  Rl  Rl
  // op  Rs    Rs  Rs  Rs
  //     C     C   C   C
  //     U     Rl  Rs  Rs

  result_map = {{Rl, Rl, Rl}, 
                {Rs, Rs, Rs},
                { C,  C,  C},
                {Rl, Rs, Rs} };
  return result_map[op][existing_state];
}

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

PR Comment: https://git.openjdk.org/jdk/pull/24028#issuecomment-2826712000