in src/hotspot/share/nmt/vmatree.cpp [245:647]
void VMATree::register_mapping(position _A, position _B, StateType state,
const RegionData& metadata, VMATree::SummaryDiff& diff, bool use_tag_inplace) {
diff.clear();
if (_A == _B) {
return;
}
assert(_A < _B, "should be");
RequestInfo req{_A, _B, state, metadata.mem_tag, metadata.stack_idx, use_tag_inplace};
IntervalChange stA{
IntervalState{StateType::Released, empty_regiondata},
IntervalState{ state, metadata}
};
IntervalChange stB{
IntervalState{ state, metadata},
IntervalState{StateType::Released, empty_regiondata}
};
stA.out.set_commit_stack(NativeCallStackStorage::invalid);
stB.in.set_commit_stack(NativeCallStackStorage::invalid);
VMARBTree::Range rA = _tree.find_enclosing_range(_A);
VMARBTree::Range rB = _tree.find_enclosing_range(_B);
// nodes: .....X.......Y...Z......W........U
// request: A------------------B
// X,Y = enclosing_nodes(A)
// W,U = enclosing_nodes(B)
// The cases are whether or not X and Y exists and X == A. (A == Y doesn't happen since it is searched by 'lt' predicate)
// The cases are whether or not W and U exists and W == B. (B == U doesn't happen since it is searched by 'lt' predicate)
// We update regions in 3 sections: 1) X..A..Y, 2) Y....W, 3) W..B..U
// Y: is the closest node greater than A, but less than B
// W: is the closest node less than B, but greater than A
// The regions in [Y,W) are updated in a loop. We update X..A..Y before the loop and W..B..U after the loop.
// The table below summarizes the overlap cases. The overlapping case depends on whether X, Y, W and U exist or not,
// and if they exist whether they are the same or not.
// In the notations here, when there is not dot ('.') between two nodes it meaans that they are the same. For example,
// ...XA....Y.... means X == A.
// row 0: .........A..................B.....
// row 1: .........A...YW.............B..... // it is impossible, since it means only one node exists in the tree.
// row 2: .........A...Y..........W...B.....
// row 3: .........A...Y.............WB.....
// row 4: .....X...A..................B.....
// row 5: .....X...A...YW.............B.....
// row 6: .....X...A...Y..........W...B.....
// row 7: .....X...A...Y.............WB.....
// row 8: ........XA..................B.....
// row 9: ........XA...YW.............B.....
// row 10: ........XA...Y..........W...B.....
// row 11: ........XA...Y.............WB.....
// row 12: .........A..................B....U
// row 13: .........A...YW.............B....U
// row 14: .........A...Y..........W...B....U
// row 15: .........A...Y.............WB....U
// row 16: .....X...A..................B....U
// row 17: .....X...A...YW.............B....U
// row 18: .....X...A...Y..........W...B....U
// row 19: .....X...A...Y.............WB....U
// row 20: ........XA..................B....U
// row 21: ........XA...YW.............B....U
// row 22: ........XA...Y..........W...B....U
// row 23: ........XA...Y.............WB....U
// We intentionally did not summarize/compress the cases to keep them as separate.
// This expanded way of describing the cases helps us to understand/analyze/verify/debug/maintain
// the corresponding code more easily.
// Mapping of table to row, row to switch-case should be consistent. If one changes, the others have
// to be updated accordingly. The sequence of dependecies is: table -> row no -> switch(row)-case -> code.
// Meaning that whenever any of one item in this sequence is changed, the rest of the consequent items to
// be checked/changed.
TNode* X = rA.start;
TNode* Y = rA.end;
TNode* W = rB.start;
TNode* U = rB.end;
TNode nA{_A, stA}; // the node that represents A
TNode nB{_B, stB}; // the node that represents B
TNode* A = &nA;
TNode* B = &nB;
auto upsert_if= [&](TNode* node) {
if (!node->val().is_noop()) {
_tree.upsert(node->key(), node->val());
}
};
// update region between n1 and n2
auto update = [&](TNode* n1, TNode* n2) {
update_region(n1, n2, req, diff);
};
auto remove_if = [&](TNode* node) -> bool{
if (node->val().is_noop()) {
_tree.remove(node->key());
return true;
}
return false;
};
GrowableArrayCHeap<position, mtNMT> to_be_removed;
// update regions in range A to B
auto update_loop = [&]() {
TNode* prev = nullptr;
_tree.visit_range_in_order(_A + 1, _B + 1, [&](TNode* curr) {
if (prev != nullptr) {
update_region(prev, curr, req, diff);
// during visit, structure of the tree should not be changed
// keep the keys to be removed, and remove them later
if (prev->val().is_noop()) {
to_be_removed.push(prev->key());
}
}
prev = curr;
return true;
});
};
// update region of [A,T)
auto update_A = [&](TNode* T) {
A->val().out = A->val().in;
update(A, T);
};
bool X_exists = X != nullptr;
bool Y_exists = Y != nullptr && Y->key() <= _B;
bool W_exists = W != nullptr && W->key() > _A;
bool U_exists = U != nullptr;
bool X_eq_A = X_exists && X->key() == _A;
bool W_eq_B = W_exists && W->key() == _B;
bool Y_eq_W = Y_exists && W_exists && W->key() == Y->key();
int row = -1;
#ifdef ASSERT
auto print_case = [&]() {
log_trace(vmatree)(" req: %4d---%4d", (int)_A, (int)_B);
log_trace(vmatree)(" row: %2d", row);
log_trace(vmatree)(" X: %4ld", X_exists ? (long)X->key() : -1);
log_trace(vmatree)(" Y: %4ld", Y_exists ? (long)Y->key() : -1);
log_trace(vmatree)(" W: %4ld", W_exists ? (long)W->key() : -1);
log_trace(vmatree)(" U: %4ld", U_exists ? (long)U->key() : -1);
};
#endif
// Order of the nodes if they exist are as: X <= A < Y <= W <= B < U
// A---------------------------B
// X Y YW WB U
// XA Y YW WB U
if (!X_exists && !Y_exists && !U_exists) { row = 0; }
if (!X_exists && Y_exists && Y_eq_W && !W_eq_B && !U_exists) { row = 1; }
if (!X_exists && Y_exists && !Y_eq_W && !W_eq_B && !U_exists) { row = 2; }
if (!X_exists && Y_exists && W_eq_B && !U_exists) { row = 3; }
if ( X_exists && !Y_exists && !U_exists) { row = 4; }
if ( X_exists && Y_exists && Y_eq_W && !W_eq_B && !U_exists) { row = 5; }
if ( X_exists && Y_exists && !Y_eq_W && !W_eq_B && !U_exists) { row = 6; }
if ( X_exists && Y_exists && W_eq_B && !U_exists) { row = 7; }
if ( X_eq_A && !Y_exists && !U_exists) { row = 8; }
if ( X_eq_A && Y_exists && Y_eq_W && !W_eq_B && !U_exists) { row = 9; }
if ( X_eq_A && Y_exists && !Y_eq_W && !W_eq_B && !U_exists) { row = 10; }
if ( X_eq_A && Y_exists && W_eq_B && !U_exists) { row = 11; }
if (!X_exists && !Y_exists && U_exists) { row = 12; }
if (!X_exists && Y_exists && Y_eq_W && !W_eq_B && U_exists) { row = 13; }
if (!X_exists && Y_exists && !Y_eq_W && !W_eq_B && U_exists) { row = 14; }
if (!X_exists && Y_exists && W_eq_B && U_exists) { row = 15; }
if ( X_exists && !Y_exists && U_exists) { row = 16; }
if ( X_exists && Y_exists && Y_eq_W && !W_eq_B && U_exists) { row = 17; }
if ( X_exists && Y_exists && !Y_eq_W && !W_eq_B && U_exists) { row = 18; }
if ( X_exists && Y_exists && W_eq_B && U_exists) { row = 19; }
if ( X_eq_A && !Y_exists && U_exists) { row = 20; }
if ( X_eq_A && Y_exists && Y_eq_W && !W_eq_B && U_exists) { row = 21; }
if ( X_eq_A && Y_exists && !Y_eq_W && !W_eq_B && U_exists) { row = 22; }
if ( X_eq_A && Y_exists && W_eq_B && U_exists) { row = 23; }
switch(row) {
// row 0: .........A..................B.....
case 0: {
update_A(B);
upsert_if(A);
upsert_if(B);
break;
}
// row 1: .........A...YW.............B.....
case 1: {
ShouldNotReachHere();
break;
}
// row 2: .........A...Y..........W...B.....
case 2: {
update_A(Y);
upsert_if(A);
update_loop();
remove_if(Y);
update(W, B);
remove_if(W);
upsert_if(B);
break;
}
// row 3: .........A...Y.............WB.....
case 3: {
update_A(Y);
upsert_if(A);
update_loop();
remove_if(W);
break;
}
// row 4: .....X...A..................B.....
case 4: {
A->val().in = X->val().out;
update_A(B);
upsert_if(A);
upsert_if(B);
break;
}
// row 5: .....X...A...YW.............B.....
case 5: {
A->val().in = X->val().out;
update_A(Y);
upsert_if(A);
update(Y, B);
remove_if(Y);
upsert_if(B);
break;
}
// row 6: .....X...A...Y..........W...B.....
case 6: {
A->val().in = X->val().out;
update_A(Y);
upsert_if(A);
update_loop();
update(W, B);
remove_if(W);
upsert_if(B);
break;
}
// row 7: .....X...A...Y.............WB.....
case 7: {
A->val().in = X->val().out;
update_A(Y);
upsert_if(A);
update_loop();
remove_if(W);
break;
}
// row 8: ........XA..................B.....
case 8: {
update(X, B);
remove_if(X);
upsert_if(B);
break;
}
// row 9: ........XA...YW.............B.....
case 9: {
update(X, Y);
remove_if(X);
update(W, B);
remove_if(W);
upsert_if(B);
break;
}
// row 10: ........XA...Y..........W...B.....
case 10: {
update(X, Y);
remove_if(X);
update_loop();
update(W, B);
remove_if(W);
upsert_if(B);
break;
}
// row 11: ........XA...Y.............WB.....
case 11: {
update(X, Y);
remove_if(X);
update_loop();
remove_if(W);
break;
}
// row 12: .........A..................B....U
case 12: {
update_A(B);
upsert_if(A);
upsert_if(B);
break;
}
// row 13: .........A...YW.............B....U
case 13: {
update_A(Y);
upsert_if(A);
update(W, B);
remove_if(W);
B->val().out = U->val().in;
upsert_if(B);
break;
}
// row 14: .........A...Y..........W...B....U
case 14: {
update_A(Y);
upsert_if(A);
update_loop();
update(W, B);
remove_if(W);
B->val().out = U->val().in;
upsert_if(B);
break;
}
// row 15: .........A...Y.............WB....U
case 15: {
update_A(Y);
upsert_if(A);
update_loop();
remove_if(W);
break;
}
// row 16: .....X...A..................B....U
case 16: {
A->val().in = X->val().out;
update_A(B);
upsert_if(A);
B->val().out = U->val().in;
upsert_if(B);
break;
}
// row 17: .....X...A...YW.............B....U
case 17: {
A->val().in = X->val().out;
update_A(Y);
upsert_if(A);
update(W, B);
remove_if(W);
B->val().out = U->val().in;
upsert_if(B);
break;
}
// row 18: .....X...A...Y..........W...B....U
case 18: {
A->val().in = X->val().out;
update_A(Y);
upsert_if(A);
update_loop();
update(W, B);
remove_if(W);
B->val().out = U->val().in;
upsert_if(B);
break;
}
// row 19: .....X...A...Y.............WB....U
case 19: {
A->val().in = X->val().out;
update_A(Y);
upsert_if(A);
update_loop();
remove_if(W);
break;
}
// row 20: ........XA..................B....U
case 20: {
update(X, B);
remove_if(X);
B->val().out = U->val().in;
upsert_if(B);
break;
}
// row 21: ........XA...YW.............B....U
case 21: {
update(X, Y);
remove_if(X);
update(W, B);
remove_if(W);
B->val().out = U->val().in;
upsert_if(B);
break;
}
// row 22: ........XA...Y..........W...B....U
case 22: {
update(X, Y);
remove_if(X);
update_loop();
update(W, B);
remove_if(W);
B->val().out = U->val().in;
upsert_if(B);
break;
}
// row 23: ........XA...Y.............WB....U
case 23: {
update(X, Y);
remove_if(X);
update_loop();
remove_if(W);
break;
}
default:
ShouldNotReachHere();
}
// Remove the 'noop' nodes that found inside the loop
while(to_be_removed.length() != 0) {
_tree.remove(to_be_removed.pop());
}
}