RFR: 8302670: use-after-free related to PhaseIterGVN interaction with Unique_Node_List and Node_Stack [v10]
Emanuel Peter
epeter at openjdk.org
Fri May 19 06:08:55 UTC 2023
On Thu, 11 May 2023 07:38:45 GMT, Emanuel Peter <epeter at openjdk.org> wrote:
>> **Motivation**
>>
>> - Generally: we copy containers by value: the consequence is that we copy all internals by value, including size, capacity and pointers. From there on, the containers can diverge, and make each other inconsistent. One may be destructed and free the memory of the other one. In theory this could cause a bug on the main-branch. In practice, we probably (maybe?) use the correct one of the many copies that is currently supposed to be alive. If one pushes to the wrong copy, then one will most likely eventually hit a SIGSEGV - which has happened to me and @TobiHartmann a few times - it is very annoying. Plus: copy by value of containers is very bad design, and makes it difficult to understand which one is the "live" copy.
>> - We also overwrite igvn phases. One case is particularly hairy: `igvn = ccp` (truncate ccp, and store it into igvn variable. Aka `object slicing in c++`)
>>
>> @jcking 's first version https://github.com/openjdk/jdk/pull/12703. He dropped it as a "discussion or starting point for somebody else". I took a lot of ideas from him, but went a bit more aggressive with refactoring instead of the `replace_with` move-like approach.
>>
>> **Changes**
>>
>> - Make many containers `NONCOPYABLE`:
>> - `Dict`
>> - `VectorSet`
>> - `Node_Array`, `Node_List`, `Unique_Node_List`
>> - `Node_Stack`
>> - `NodeHash`
>> - `Type_Array`
>> - `Phase`
>> - Note: for many classes I still allow the `A(A&&) = default;` constructor. This allows implicit moves (rvalues) so that we can return containers from functions and capture them.
>> - Create "global" containers for `Compile`:
>> - `C->igvn_worklist()` (renamed from `for_igvn`, referenced to by `PhaseIterGVN._worklist`)
>> - `C->type_array()` (referenced to by `PhaseValues._types`)
>> - `C->node_hash_table()` (referenced to by `PhaseValues._table`)
>> - They are created in the `Compile` constructor. The phases can then hold a reference (`&`) to them.
>> - Note: before, these were located in the phases, and passed back and forth by value. They were passed downward via the phase constructor, where the corresponding fields were taken over from the previous phase. Then they were passed upward by `PhaseGVN.replace_with` (for `_table` and `_types`), or by simply overwriting the old `igvn` variable with a newly constructed igvn that has the containers passed into its constructor from the previous phase. I imagine it as "weaving" the containers from phase to phase, where the ownership travels. Th...
>
> Emanuel Peter has updated the pull request incrementally with one additional commit since the last revision:
>
> Second batch of suggestions from @chhagedorn
This is the patch, there was only a hand full of cases. Should I apply this patch?
diff --git a/src/hotspot/share/libadt/dict.hpp b/src/hotspot/share/libadt/dict.hpp
index c021536c402..02c634ff1d1 100644
--- a/src/hotspot/share/libadt/dict.hpp
+++ b/src/hotspot/share/libadt/dict.hpp
@@ -61,9 +61,6 @@ class Dict : public AnyObj { // Dictionary structure
Dict(const Dict &base, Arena* arena); // Deep-copy
~Dict();
- // Allow move constructor for && (eg. capture return of function)
- Dict(Dict&&) = default;
-
// Return # of key-value pairs in dict
uint32_t Size(void) const { return _cnt; }
diff --git a/src/hotspot/share/libadt/vectset.hpp b/src/hotspot/share/libadt/vectset.hpp
index a82046f2ba9..5a58afc276b 100644
--- a/src/hotspot/share/libadt/vectset.hpp
+++ b/src/hotspot/share/libadt/vectset.hpp
@@ -55,9 +55,6 @@ public:
VectorSet(Arena* arena);
~VectorSet() {}
- // Allow move constructor for && (eg. capture return of function)
- VectorSet(VectorSet&&) = default;
-
void insert(uint elem);
bool is_empty() const;
void reset() {
diff --git a/src/hotspot/share/opto/loopPredicate.cpp b/src/hotspot/share/opto/loopPredicate.cpp
index 8511b3da897..04577ef35e4 100644
--- a/src/hotspot/share/opto/loopPredicate.cpp
+++ b/src/hotspot/share/opto/loopPredicate.cpp
@@ -229,7 +229,8 @@ ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj, Node*
// Update ctrl and control inputs of all data nodes starting from 'node' to 'new_ctrl' which have 'old_ctrl' as
// current ctrl.
void PhaseIdealLoop::set_ctrl_of_nodes_with_same_ctrl(Node* node, ProjNode* old_ctrl, Node* new_ctrl) {
- Unique_Node_List nodes_with_same_ctrl = find_nodes_with_same_ctrl(node, old_ctrl);
+ Unique_Node_List nodes_with_same_ctrl;
+ find_nodes_with_same_ctrl(node, old_ctrl, nodes_with_same_ctrl);
for (uint j = 0; j < nodes_with_same_ctrl.size(); j++) {
Node* next = nodes_with_same_ctrl[j];
if (next->in(0) == old_ctrl) {
@@ -240,8 +241,8 @@ void PhaseIdealLoop::set_ctrl_of_nodes_with_same_ctrl(Node* node, ProjNode* old_
}
// Recursively find all input nodes with the same ctrl.
-Unique_Node_List PhaseIdealLoop::find_nodes_with_same_ctrl(Node* node, const ProjNode* ctrl) {
- Unique_Node_List nodes_with_same_ctrl;
+void PhaseIdealLoop::find_nodes_with_same_ctrl(Node* node, const ProjNode* ctrl, Unique_Node_List& nodes_with_same_ctrl) {
+ nodes_with_same_ctrl.ensure_empty();
nodes_with_same_ctrl.push(node);
for (uint j = 0; j < nodes_with_same_ctrl.size(); j++) {
Node* next = nodes_with_same_ctrl[j];
@@ -252,15 +253,16 @@ Unique_Node_List PhaseIdealLoop::find_nodes_with_same_ctrl(Node* node, const Pro
}
}
}
- return nodes_with_same_ctrl;
}
// Clone all nodes with the same ctrl as 'old_ctrl' starting from 'node' by following its inputs. Rewire the cloned nodes
// to 'new_ctrl'. Returns the clone of 'node'.
Node* PhaseIdealLoop::clone_nodes_with_same_ctrl(Node* node, ProjNode* old_ctrl, Node* new_ctrl) {
DEBUG_ONLY(uint last_idx = C->unique();)
- Unique_Node_List nodes_with_same_ctrl = find_nodes_with_same_ctrl(node, old_ctrl);
- Dict old_new_mapping = clone_nodes(nodes_with_same_ctrl); // Cloned but not rewired, yet
+ Unique_Node_List nodes_with_same_ctrl;
+ find_nodes_with_same_ctrl(node, old_ctrl, nodes_with_same_ctrl);
+ Dict old_new_mapping(cmpkey, hashkey);
+ clone_nodes(nodes_with_same_ctrl, old_new_mapping); // Cloned but not rewired, yet
rewire_cloned_nodes_to_ctrl(old_ctrl, new_ctrl, nodes_with_same_ctrl, old_new_mapping);
Node* clone_phi_input = static_cast<Node*>(old_new_mapping[node]);
assert(clone_phi_input != nullptr && clone_phi_input->_idx >= last_idx, "must exist and be a proper clone");
@@ -268,15 +270,14 @@ Node* PhaseIdealLoop::clone_nodes_with_same_ctrl(Node* node, ProjNode* old_ctrl,
}
// Clone all the nodes on 'list_to_clone' and return an old->new mapping.
-Dict PhaseIdealLoop::clone_nodes(const Node_List& list_to_clone) {
- Dict old_new_mapping(cmpkey, hashkey);
+void PhaseIdealLoop::clone_nodes(const Node_List& list_to_clone, Dict& old_new_mapping) {
+ assert(old_new_mapping.Size() == 0, "must be empty");
for (uint i = 0; i < list_to_clone.size(); i++) {
Node* next = list_to_clone[i];
Node* clone = next->clone();
_igvn.register_new_node_with_optimizer(clone);
old_new_mapping.Insert(next, clone);
}
- return old_new_mapping;
}
// Rewire inputs of the unprocessed cloned nodes (inputs are not updated, yet, and still point to the old nodes) by
diff --git a/src/hotspot/share/opto/loopnode.hpp b/src/hotspot/share/opto/loopnode.hpp
index 0f876042eda..ae61fb87a6c 100644
--- a/src/hotspot/share/opto/loopnode.hpp
+++ b/src/hotspot/share/opto/loopnode.hpp
@@ -1345,9 +1345,9 @@ public:
private:
// Helper functions for create_new_if_for_predicate()
void set_ctrl_of_nodes_with_same_ctrl(Node* node, ProjNode* old_ctrl, Node* new_ctrl);
- Unique_Node_List find_nodes_with_same_ctrl(Node* node, const ProjNode* ctrl);
+ void find_nodes_with_same_ctrl(Node* node, const ProjNode* ctrl, Unique_Node_List& nodes_with_same_ctrl);
Node* clone_nodes_with_same_ctrl(Node* node, ProjNode* old_ctrl, Node* new_ctrl);
- Dict clone_nodes(const Node_List& list_to_clone);
+ void clone_nodes(const Node_List& list_to_clone, Dict& old_new_mapping);
void rewire_cloned_nodes_to_ctrl(const ProjNode* old_ctrl, Node* new_ctrl, const Node_List& nodes_with_same_ctrl,
const Dict& old_new_mapping);
void rewire_inputs_of_clones_to_clones(Node* new_ctrl, Node* clone, const Dict& old_new_mapping, const Node* next);
diff --git a/src/hotspot/share/opto/node.hpp b/src/hotspot/share/opto/node.hpp
index 43375187abc..b85459130d5 100644
--- a/src/hotspot/share/opto/node.hpp
+++ b/src/hotspot/share/opto/node.hpp
@@ -1539,9 +1539,6 @@ public:
}
Node_Array() : Node_Array(Thread::current()->resource_area()) {}
- // Allow move constructor for && (eg. capture return of function)
- Node_Array(Node_Array&&) = default;
-
Node *operator[] ( uint i ) const // Lookup, or null for not mapped
{ return (i<_max) ? _nodes[i] : (Node*)nullptr; }
Node* at(uint i) const { assert(i<_max,"oob"); return _nodes[i]; }
@@ -1568,9 +1565,6 @@ public:
Node_List(uint max = OptoNodeListSize) : Node_Array(Thread::current()->resource_area(), max), _cnt(0) {}
Node_List(Arena *a, uint max = OptoNodeListSize) : Node_Array(a, max), _cnt(0) {}
- // Allow move constructor for && (eg. capture return of function)
- Node_List(Node_List&&) = default;
-
bool contains(const Node* n) const {
for (uint e = 0; e < size(); e++) {
if (at(e) == n) return true;
@@ -1607,9 +1601,6 @@ public:
Unique_Node_List() : Node_List(), _clock_index(0) {}
Unique_Node_List(Arena *a) : Node_List(a), _in_worklist(a), _clock_index(0) {}
- // Allow move constructor for && (eg. capture return of function)
- Unique_Node_List(Unique_Node_List&&) = default;
-
void remove( Node *n );
bool member( Node *n ) { return _in_worklist.test(n->_idx) != 0; }
VectorSet& member_set(){ return _in_worklist; }
diff --git a/src/hotspot/share/opto/stringopts.cpp b/src/hotspot/share/opto/stringopts.cpp
index 399f18ce9aa..a2589d0f6fb 100644
--- a/src/hotspot/share/opto/stringopts.cpp
+++ b/src/hotspot/share/opto/stringopts.cpp
@@ -369,8 +369,8 @@ void StringConcat::eliminate_initialize(InitializeNode* init) {
init->disconnect_inputs(C);
}
-Node_List PhaseStringOpts::collect_toString_calls() {
- Node_List string_calls;
+void PhaseStringOpts::collect_toString_calls(Node_List& string_calls) {
+ assert(string_calls.size() == 0, "output list must be empty");
Node_List worklist;
_visited.clear();
@@ -405,7 +405,6 @@ Node_List PhaseStringOpts::collect_toString_calls() {
#ifndef PRODUCT
Atomic::add(&_stropts_total, encountered);
#endif
- return string_calls;
}
// Recognize a fluent-chain of StringBuilder/Buffer. They are either explicit usages
@@ -647,7 +646,8 @@ PhaseStringOpts::PhaseStringOpts(PhaseGVN* gvn):
// if it's possible to fuse the usage of the SB into a single String
// construction.
GrowableArray<StringConcat*> concats;
- Node_List toStrings = collect_toString_calls();
+ Node_List toStrings;
+ collect_toString_calls(toStrings);
while (toStrings.size() > 0) {
StringConcat* sc = build_candidate(toStrings.pop()->as_CallStaticJava());
if (sc != nullptr) {
diff --git a/src/hotspot/share/opto/stringopts.hpp b/src/hotspot/share/opto/stringopts.hpp
index 21be4109c7d..0ad349c32d1 100644
--- a/src/hotspot/share/opto/stringopts.hpp
+++ b/src/hotspot/share/opto/stringopts.hpp
@@ -47,7 +47,7 @@ class PhaseStringOpts : public Phase {
VectorSet _visited;
// Collect a list of all SB.toString calls
- Node_List collect_toString_calls();
+ void collect_toString_calls(Node_List& string_calls);
// Examine the use of the SB alloc to see if it can be replace with
// a single string construction.
diff --git a/src/hotspot/share/opto/superword.cpp b/src/hotspot/share/opto/superword.cpp
index b1e4677a7cb..823bd05b67b 100644
--- a/src/hotspot/share/opto/superword.cpp
+++ b/src/hotspot/share/opto/superword.cpp
@@ -2502,8 +2502,6 @@ private:
GrowableArray<int> _incnt; // number of (implicit) in-edges
int _max_pid = 0;
- bool _schedule_success;
-
SuperWord* _slp;
public:
PacksetGraph(SuperWord* slp)
@@ -2547,7 +2545,6 @@ public:
int incnt(int pid) { return _incnt.at(pid - 1); }
void incnt_set(int pid, int cnt) { return _incnt.at_put(pid - 1, cnt); }
GrowableArray<int>& out(int pid) { return _out.at(pid - 1); }
- bool schedule_success() const { return _schedule_success; }
// Create nodes (from packs and scalar-nodes), and add edges, based on DepPreds.
void build() {
@@ -2626,10 +2623,10 @@ public:
// Schedule nodes of PacksetGraph to worklist, using topsort: schedule a node
// that has zero incnt. If a PacksetGraph node corresponds to memops, then add
- // those to the memops_schedule. At the end, we return the memops_schedule, and
- // note if topsort was successful.
- Node_List schedule() {
- Node_List memops_schedule;
+ // those to the memops_schedule. We return true if topsort was successful, and
+ // false if there was a cycle.
+ bool schedule(Node_List& memops_schedule) {
+ assert(memops_schedule.size() == 0, "output list must be empty");
GrowableArray<int> worklist;
// Directly schedule all nodes without precedence
for (int pid = 1; pid <= _max_pid; pid++) {
@@ -2668,8 +2665,8 @@ public:
}
// Was every pid scheduled? If not, we found some cycles in the PacksetGraph.
- _schedule_success = (worklist.length() == _max_pid);
- return memops_schedule;
+ bool schedule_success = (worklist.length() == _max_pid);
+ return schedule_success;
}
// Print the PacksetGraph.
@@ -2722,7 +2719,8 @@ void SuperWord::schedule() {
graph.build();
// (2) Schedule the PacksetGraph.
- Node_List memops_schedule = graph.schedule();
+ Node_List memops_schedule;
+ bool schedule_success = graph.schedule(memops_schedule);
// (3) Check if the PacksetGraph schedule succeeded (had no cycles).
// We now know that we only have independent packs, see verify_packs.
@@ -2730,7 +2728,7 @@ void SuperWord::schedule() {
// graph (DAG) after scheduling. Thus, we must check if the packs have
// introduced a cycle. The SuperWord paper mentions the need for this
// in "3.7 Scheduling".
- if (!graph.schedule_success()) {
+ if (schedule_success) {
if (TraceSuperWord) {
tty->print_cr("SuperWord::schedule found cycle in PacksetGraph:");
graph.print(true, false);
-------------
PR Comment: https://git.openjdk.org/jdk/pull/13833#issuecomment-1554056240
More information about the hotspot-dev
mailing list