1 /*
2  * Copyright (c) 2013, 2018, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
23 
24 
25 
26 package org.graalvm.compiler.hotspot.phases;
27 
28 import java.util.Iterator;
29 
30 import org.graalvm.compiler.debug.GraalError;
31 import org.graalvm.compiler.graph.Node;
32 import org.graalvm.compiler.graph.NodeFlood;
33 import org.graalvm.compiler.hotspot.GraalHotSpotVMConfig;
34 import org.graalvm.compiler.hotspot.gc.g1.G1PostWriteBarrier;
35 import org.graalvm.compiler.hotspot.gc.shared.ArrayRangeWriteBarrier;
36 import org.graalvm.compiler.hotspot.gc.shared.ObjectWriteBarrier;
37 import org.graalvm.compiler.hotspot.gc.shared.SerialWriteBarrier;
38 import org.graalvm.compiler.nodeinfo.Verbosity;
39 import org.graalvm.compiler.nodes.DeoptimizingNode;
40 import org.graalvm.compiler.nodes.FixedWithNextNode;
41 import org.graalvm.compiler.nodes.LoopBeginNode;
42 import org.graalvm.compiler.nodes.StructuredGraph;
43 import org.graalvm.compiler.nodes.ValueNode;
44 import org.graalvm.compiler.nodes.extended.ArrayRangeWrite;
45 import org.graalvm.compiler.nodes.java.LoweredAtomicReadAndWriteNode;
46 import org.graalvm.compiler.nodes.java.LogicCompareAndSwapNode;
47 import org.graalvm.compiler.nodes.java.ValueCompareAndSwapNode;
48 import org.graalvm.compiler.nodes.memory.FixedAccessNode;
49 import org.graalvm.compiler.nodes.memory.HeapAccess;
50 import org.graalvm.compiler.nodes.memory.HeapAccess.BarrierType;
51 import org.graalvm.compiler.nodes.memory.ReadNode;
52 import org.graalvm.compiler.nodes.memory.WriteNode;
53 import org.graalvm.compiler.nodes.memory.address.OffsetAddressNode;
54 import org.graalvm.compiler.nodes.type.StampTool;
55 import org.graalvm.compiler.nodes.util.GraphUtil;
56 import org.graalvm.compiler.phases.Phase;
57 
58 /**
59  * Verification phase that checks if, for every write, at least one write barrier is present at all
60  * paths leading to the previous safepoint. For every write, necessitating a write barrier, a
61  * bottom-up traversal of the graph is performed up to the previous safepoints via all possible
62  * paths. If, for a certain path, no write barrier satisfying the processed write is found, an
63  * assertion is generated.
64  */
65 public class WriteBarrierVerificationPhase extends Phase {
66 
67     private final GraalHotSpotVMConfig config;
68 
WriteBarrierVerificationPhase(GraalHotSpotVMConfig config)69     public WriteBarrierVerificationPhase(GraalHotSpotVMConfig config) {
70         this.config = config;
71     }
72 
73     @Override
run(StructuredGraph graph)74     protected void run(StructuredGraph graph) {
75         processWrites(graph);
76     }
77 
processWrites(StructuredGraph graph)78     private void processWrites(StructuredGraph graph) {
79         for (Node node : graph.getNodes()) {
80             if (isObjectWrite(node) || isObjectArrayRangeWrite(node)) {
81                 if (node instanceof WriteNode) {
82                     WriteNode writeNode = (WriteNode) node;
83                     if (StampTool.isPointerAlwaysNull(writeNode.value())) {
84                         continue;
85                     }
86                 }
87                 validateWrite(node);
88             }
89         }
90     }
91 
validateWrite(Node write)92     private void validateWrite(Node write) {
93         /*
94          * The currently validated write is checked in order to discover if it has an appropriate
95          * attached write barrier.
96          */
97         if (hasAttachedBarrier((FixedWithNextNode) write)) {
98             return;
99         }
100         NodeFlood frontier = write.graph().createNodeFlood();
101         expandFrontier(frontier, write);
102         Iterator<Node> iterator = frontier.iterator();
103         while (iterator.hasNext()) {
104             Node currentNode = iterator.next();
105             if (isSafepoint(currentNode)) {
106                 throw new AssertionError("Write barrier must be present " + write.toString(Verbosity.All) + " / " + write.inputs());
107             }
108             if (useG1GC()) {
109                 if (!(currentNode instanceof G1PostWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
110                     expandFrontier(frontier, currentNode);
111                 }
112             } else {
113                 if (!(currentNode instanceof SerialWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode)) ||
114                                 ((currentNode instanceof SerialWriteBarrier) && !validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
115                     expandFrontier(frontier, currentNode);
116                 }
117             }
118         }
119     }
120 
useG1GC()121     private boolean useG1GC() {
122         return config.useG1GC;
123     }
124 
hasAttachedBarrier(FixedWithNextNode node)125     private boolean hasAttachedBarrier(FixedWithNextNode node) {
126         final Node next = node.next();
127         final Node previous = node.predecessor();
128         boolean validatePreBarrier = useG1GC() && (isObjectWrite(node) || !((ArrayRangeWrite) node).isInitialization());
129         if (node instanceof WriteNode) {
130             WriteNode writeNode = (WriteNode) node;
131             if (config.useDeferredInitBarriers && writeNode.getLocationIdentity().isInit()) {
132                 return true;
133             }
134             if (writeNode.getLocationIdentity().isInit()) {
135                 validatePreBarrier = false;
136             }
137         }
138         if (isObjectWrite(node)) {
139             return (isObjectBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isObjectBarrier(node, previous));
140         } else if (isObjectArrayRangeWrite(node)) {
141             return (isArrayBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isArrayBarrier(node, previous));
142         } else {
143             return true;
144         }
145     }
146 
isObjectBarrier(FixedWithNextNode node, final Node next)147     private static boolean isObjectBarrier(FixedWithNextNode node, final Node next) {
148         return next instanceof ObjectWriteBarrier && validateBarrier((FixedAccessNode) node, (ObjectWriteBarrier) next);
149     }
150 
isArrayBarrier(FixedWithNextNode node, final Node next)151     private static boolean isArrayBarrier(FixedWithNextNode node, final Node next) {
152         return (next instanceof ArrayRangeWriteBarrier) && ((ArrayRangeWrite) node).getAddress() == ((ArrayRangeWriteBarrier) next).getAddress();
153     }
154 
isObjectWrite(Node node)155     private static boolean isObjectWrite(Node node) {
156         // Read nodes with barrier attached (G1 Ref field) are not validated yet.
157         return node instanceof FixedAccessNode && ((HeapAccess) node).getBarrierType() != BarrierType.NONE && !(node instanceof ReadNode);
158     }
159 
isObjectArrayRangeWrite(Node node)160     private static boolean isObjectArrayRangeWrite(Node node) {
161         return node instanceof ArrayRangeWrite && ((ArrayRangeWrite) node).writesObjectArray();
162     }
163 
expandFrontier(NodeFlood frontier, Node node)164     private static void expandFrontier(NodeFlood frontier, Node node) {
165         for (Node previousNode : node.cfgPredecessors()) {
166             if (previousNode != null) {
167                 frontier.add(previousNode);
168             }
169         }
170     }
171 
isSafepoint(Node node)172     private static boolean isSafepoint(Node node) {
173         if (node instanceof FixedAccessNode) {
174             // Implicit null checks on reads or writes do not count.
175             return false;
176         }
177         /*
178          * LoopBegin nodes are also treated as safepoints since a bottom-up analysis is performed
179          * and loop safepoints are placed before LoopEnd nodes. Possible elimination of write
180          * barriers inside loops, derived from writes outside loops, can not be permitted.
181          */
182         return ((node instanceof DeoptimizingNode) && ((DeoptimizingNode) node).canDeoptimize()) || (node instanceof LoopBeginNode);
183     }
184 
getValueWritten(FixedWithNextNode write)185     private static ValueNode getValueWritten(FixedWithNextNode write) {
186         if (write instanceof WriteNode) {
187             return ((WriteNode) write).value();
188         } else if (write instanceof LogicCompareAndSwapNode) {
189             return ((LogicCompareAndSwapNode) write).getNewValue();
190         } else if (write instanceof LoweredAtomicReadAndWriteNode) {
191             return ((LoweredAtomicReadAndWriteNode) write).getNewValue();
192         } else {
193             throw GraalError.shouldNotReachHere(String.format("unexpected write node %s", write));
194         }
195     }
196 
validateBarrier(FixedAccessNode write, ObjectWriteBarrier barrier)197     private static boolean validateBarrier(FixedAccessNode write, ObjectWriteBarrier barrier) {
198         assert write instanceof WriteNode || write instanceof LogicCompareAndSwapNode || write instanceof ValueCompareAndSwapNode ||
199                         write instanceof LoweredAtomicReadAndWriteNode : "Node must be of type requiring a write barrier " + write;
200         if (!barrier.usePrecise()) {
201             if (barrier.getAddress() instanceof OffsetAddressNode && write.getAddress() instanceof OffsetAddressNode) {
202                 return GraphUtil.unproxify(((OffsetAddressNode) barrier.getAddress()).getBase()) == GraphUtil.unproxify(((OffsetAddressNode) write.getAddress()).getBase());
203             }
204         }
205         return barrier.getAddress() == write.getAddress();
206     }
207 }
208