jdk

1
/*
2
 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3
 * Copyright (c) 2024, Red Hat Inc.
4
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5
 *
6
 * This code is free software; you can redistribute it and/or modify it
7
 * under the terms of the GNU General Public License version 2 only, as
8
 * published by the Free Software Foundation.
9
 *
10
 * This code is distributed in the hope that it will be useful, but WITHOUT
11
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
13
 * version 2 for more details (a copy is included in the LICENSE file that
14
 * accompanied this code).
15
 *
16
 * You should have received a copy of the GNU General Public License version
17
 * 2 along with this work; if not, write to the Free Software Foundation,
18
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19
 *
20
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21
 * or visit www.oracle.com if you need additional information or have any
22
 * questions.
23
 *
24
 */
25

26
#include "precompiled.hpp"
27
#include "nmt/vmatree.hpp"
28
#include "utilities/growableArray.hpp"
29

30
const VMATree::RegionData VMATree::empty_regiondata{NativeCallStackStorage::StackIndex{}, mtNone};
31

32
const char* VMATree::statetype_strings[3] = {
33
  "reserved", "committed", "released",
34
};
35

36
VMATree::SummaryDiff VMATree::register_mapping(position A, position B, StateType state,
37
                                               const RegionData& metadata) {
38
  if (A == B) {
39
    // A 0-sized mapping isn't worth recording.
40
    return SummaryDiff();
41
  }
42

43
  IntervalChange stA{
44
      IntervalState{StateType::Released, empty_regiondata},
45
      IntervalState{              state,   metadata}
46
  };
47
  IntervalChange stB{
48
      IntervalState{              state,   metadata},
49
      IntervalState{StateType::Released, empty_regiondata}
50
  };
51

52
  // First handle A.
53
  // Find closest node that is LEQ A
54
  bool LEQ_A_found = false;
55
  AddressState LEQ_A;
56
  TreapNode* leqA_n = _tree.closest_leq(A);
57
  if (leqA_n == nullptr) {
58
    // No match. We add the A node directly, unless it would have no effect.
59
    if (!stA.is_noop()) {
60
      _tree.upsert(A, stA);
61
    }
62
  } else {
63
    LEQ_A_found = true;
64
    LEQ_A = AddressState{leqA_n->key(), leqA_n->val()};
65
    // Unless we know better, let B's outgoing state be the outgoing state of the node at or preceding A.
66
    // Consider the case where the found node is the start of a region enclosing [A,B)
67
    stB.out = leqA_n->val().out;
68

69
    // Direct address match.
70
    if (leqA_n->key() == A) {
71
      // Take over in state from old address.
72
      stA.in = leqA_n->val().in;
73

74
      // We may now be able to merge two regions:
75
      // If the node's old state matches the new, it becomes a noop. That happens, for example,
76
      // when expanding a committed area: commit [x1, A); ... commit [A, x3)
77
      // and the result should be a larger area, [x1, x3). In that case, the middle node (A and le_n)
78
      // is not needed anymore. So we just remove the old node.
79
      stB.in = stA.out;
80
      if (stA.is_noop()) {
81
        // invalidates leqA_n
82
        _tree.remove(leqA_n->key());
83
      } else {
84
        // If the state is not matching then we have different operations, such as:
85
        // reserve [x1, A); ... commit [A, x2); or
86
        // reserve [x1, A), flag1; ... reserve [A, x2), flag2; or
87
        // reserve [A, x1), flag1; ... reserve [A, x2), flag2;
88
        // then we re-use the existing out node, overwriting its old metadata.
89
        leqA_n->val() = stA;
90
      }
91
    } else {
92
      // The address must be smaller.
93
      assert(A > leqA_n->key(), "must be");
94

95
      // We add a new node, but only if there would be a state change. If there would not be a
96
      // state change, we just omit the node.
97
      // That happens, for example, when reserving within an already reserved region with identical metadata.
98
      stA.in = leqA_n->val().out; // .. and the region's prior state is the incoming state
99
      if (stA.is_noop()) {
100
        // Nothing to do.
101
      } else {
102
        // Add new node.
103
        _tree.upsert(A, stA);
104
      }
105
    }
106
  }
107

108
  // Now we handle B.
109
  // We first search all nodes that are (A, B]. All of these nodes
110
  // need to be deleted and summary accounted for. The last node before B determines B's outgoing state.
111
  // If there is no node between A and B, its A's incoming state.
112
  GrowableArrayCHeap<AddressState, mtNMT> to_be_deleted_inbetween_a_b;
113
  bool B_needs_insert = true;
114

115
  // Find all nodes between (A, B] and record their addresses and values. Also update B's
116
  // outgoing state.
117
  _tree.visit_range_in_order(A + 1, B + 1, [&](TreapNode* head) {
118
    int cmp_B = PositionComparator::cmp(head->key(), B);
119
    stB.out = head->val().out;
120
    if (cmp_B < 0) {
121
      // Record all nodes preceding B.
122
      to_be_deleted_inbetween_a_b.push({head->key(), head->val()});
123
    } else if (cmp_B == 0) {
124
      // Re-purpose B node, unless it would result in a noop node, in
125
      // which case record old node at B for deletion and summary accounting.
126
      if (stB.is_noop()) {
127
        to_be_deleted_inbetween_a_b.push(AddressState{B, head->val()});
128
      } else {
129
        head->val() = stB;
130
      }
131
      B_needs_insert = false;
132
    }
133
  });
134

135
  // Insert B node if needed
136
  if (B_needs_insert && // Was not already inserted
137
      !stB.is_noop())   // The operation is differing
138
    {
139
    _tree.upsert(B, stB);
140
  }
141

142
  // We now need to:
143
  // a) Delete all nodes between (A, B]. Including B in the case of a noop.
144
  // b) Perform summary accounting
145
  SummaryDiff diff;
146

147
  if (to_be_deleted_inbetween_a_b.length() == 0 && LEQ_A_found) {
148
    // We must have smashed a hole in an existing region (or replaced it entirely).
149
    // LEQ_A < A < B <= C
150
    SingleDiff& rescom = diff.flag[NMTUtil::flag_to_index(LEQ_A.out().flag())];
151
    if (LEQ_A.out().type() == StateType::Reserved) {
152
      rescom.reserve -= B - A;
153
    } else if (LEQ_A.out().type() == StateType::Committed) {
154
      rescom.commit -= B - A;
155
      rescom.reserve -= B - A;
156
    }
157
  }
158

159
  // Track the previous node.
160
  AddressState prev{A, stA};
161
  for (int i = 0; i < to_be_deleted_inbetween_a_b.length(); i++) {
162
    const AddressState delete_me = to_be_deleted_inbetween_a_b.at(i);
163
    _tree.remove(delete_me.address);
164

165
    // Perform summary accounting
166
    SingleDiff& rescom = diff.flag[NMTUtil::flag_to_index(delete_me.in().flag())];
167
    if (delete_me.in().type() == StateType::Reserved) {
168
      rescom.reserve -= delete_me.address - prev.address;
169
    } else if (delete_me.in().type() == StateType::Committed) {
170
      rescom.commit -= delete_me.address - prev.address;
171
      rescom.reserve -= delete_me.address - prev.address;
172
    }
173
    prev = delete_me;
174
  }
175

176
  if (prev.address != A && prev.out().type() != StateType::Released) {
177
    // The last node wasn't released, so it must be connected to a node outside of (A, B)
178
    // A - prev - B - (some node >= B)
179
    // It might be that prev.address == B == (some node >= B), this is fine.
180
    if (prev.out().type() == StateType::Reserved) {
181
      SingleDiff& rescom = diff.flag[NMTUtil::flag_to_index(prev.out().flag())];
182
      rescom.reserve -= B - prev.address;
183
    } else if (prev.out().type() == StateType::Committed) {
184
      SingleDiff& rescom = diff.flag[NMTUtil::flag_to_index(prev.out().flag())];
185
      rescom.commit -= B - prev.address;
186
      rescom.reserve -= B - prev.address;
187
    }
188
  }
189

190
  // Finally, we can register the new region [A, B)'s summary data.
191
  SingleDiff& rescom = diff.flag[NMTUtil::flag_to_index(metadata.flag)];
192
  if (state == StateType::Reserved) {
193
    rescom.reserve += B - A;
194
  } else if (state == StateType::Committed) {
195
    rescom.commit += B - A;
196
    rescom.reserve += B - A;
197
  }
198
  return diff;
199
}
200