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