1 /*
   2  * Copyright (c) 2013, 2015, 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 package org.graalvm.compiler.hotspot.phases;
  25 
  26 import java.util.Iterator;
  27 
  28 import org.graalvm.compiler.debug.GraalError;
  29 import org.graalvm.compiler.graph.Node;
  30 import org.graalvm.compiler.graph.NodeFlood;
  31 import org.graalvm.compiler.hotspot.GraalHotSpotVMConfig;
  32 import org.graalvm.compiler.hotspot.nodes.ArrayRangeWriteBarrier;
  33 import org.graalvm.compiler.hotspot.nodes.G1PostWriteBarrier;
  34 import org.graalvm.compiler.hotspot.nodes.ObjectWriteBarrier;
  35 import org.graalvm.compiler.hotspot.nodes.SerialWriteBarrier;
  36 import org.graalvm.compiler.nodeinfo.Verbosity;
  37 import org.graalvm.compiler.nodes.DeoptimizingNode;
  38 import org.graalvm.compiler.nodes.FixedWithNextNode;
  39 import org.graalvm.compiler.nodes.LoopBeginNode;
  40 import org.graalvm.compiler.nodes.StructuredGraph;
  41 import org.graalvm.compiler.nodes.ValueNode;
  42 import org.graalvm.compiler.nodes.extended.ArrayRangeWriteNode;
  43 import org.graalvm.compiler.nodes.java.LoweredAtomicReadAndWriteNode;
  44 import org.graalvm.compiler.nodes.java.LogicCompareAndSwapNode;
  45 import org.graalvm.compiler.nodes.memory.FixedAccessNode;
  46 import org.graalvm.compiler.nodes.memory.HeapAccess;
  47 import org.graalvm.compiler.nodes.memory.HeapAccess.BarrierType;
  48 import org.graalvm.compiler.nodes.memory.ReadNode;
  49 import org.graalvm.compiler.nodes.memory.WriteNode;
  50 import org.graalvm.compiler.nodes.memory.address.OffsetAddressNode;
  51 import org.graalvm.compiler.nodes.type.StampTool;
  52 import org.graalvm.compiler.nodes.util.GraphUtil;
  53 import org.graalvm.compiler.phases.Phase;
  54 
  55 /**
  56  * Verification phase that checks if, for every write, at least one write barrier is present at all
  57  * paths leading to the previous safepoint. For every write, necessitating a write barrier, a
  58  * bottom-up traversal of the graph is performed up to the previous safepoints via all possible
  59  * paths. If, for a certain path, no write barrier satisfying the processed write is found, an
  60  * assertion is generated.
  61  */
  62 public class WriteBarrierVerificationPhase extends Phase {
  63 
  64     private final GraalHotSpotVMConfig config;
  65 
  66     public WriteBarrierVerificationPhase(GraalHotSpotVMConfig config) {
  67         this.config = config;
  68     }
  69 
  70     @Override
  71     protected void run(StructuredGraph graph) {
  72         processWrites(graph);
  73     }
  74 
  75     private void processWrites(StructuredGraph graph) {
  76         for (Node node : graph.getNodes()) {
  77             if (isObjectWrite(node) || isObjectArrayRangeWrite(node)) {
  78                 if (node instanceof WriteNode) {
  79                     WriteNode writeNode = (WriteNode) node;
  80                     if (StampTool.isPointerAlwaysNull(writeNode.value())) {
  81                         continue;
  82                     }
  83                 }
  84                 validateWrite(node);
  85             }
  86         }
  87     }
  88 
  89     private void validateWrite(Node write) {
  90         /*
  91          * The currently validated write is checked in order to discover if it has an appropriate
  92          * attached write barrier.
  93          */
  94         if (hasAttachedBarrier((FixedWithNextNode) write)) {
  95             return;
  96         }
  97         NodeFlood frontier = write.graph().createNodeFlood();
  98         expandFrontier(frontier, write);
  99         Iterator<Node> iterator = frontier.iterator();
 100         while (iterator.hasNext()) {
 101             Node currentNode = iterator.next();
 102             if (isSafepoint(currentNode)) {
 103                 throw new AssertionError("Write barrier must be present " + write.toString(Verbosity.All) + " / " + write.inputs());
 104             }
 105             if (useG1GC()) {
 106                 if (!(currentNode instanceof G1PostWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
 107                     expandFrontier(frontier, currentNode);
 108                 }
 109             } else {
 110                 if (!(currentNode instanceof SerialWriteBarrier) || (!validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode)) ||
 111                                 ((currentNode instanceof SerialWriteBarrier) && !validateBarrier((FixedAccessNode) write, (ObjectWriteBarrier) currentNode))) {
 112                     expandFrontier(frontier, currentNode);
 113                 }
 114             }
 115         }
 116     }
 117 
 118     private boolean useG1GC() {
 119         return config.useG1GC;
 120     }
 121 
 122     private boolean hasAttachedBarrier(FixedWithNextNode node) {
 123         final Node next = node.next();
 124         final Node previous = node.predecessor();
 125         boolean validatePreBarrier = useG1GC() && (isObjectWrite(node) || !((ArrayRangeWriteNode) node).isInitialization());
 126         if (node instanceof WriteNode) {
 127             WriteNode writeNode = (WriteNode) node;
 128             if (writeNode.getLocationIdentity().isInit()) {
 129                 validatePreBarrier = false;
 130             }
 131         }
 132         if (isObjectWrite(node)) {
 133             return (isObjectBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isObjectBarrier(node, previous));
 134         } else if (isObjectArrayRangeWrite(node)) {
 135             return (isArrayBarrier(node, next) || StampTool.isPointerAlwaysNull(getValueWritten(node))) && (!validatePreBarrier || isArrayBarrier(node, previous));
 136         } else {
 137             return true;
 138         }
 139     }
 140 
 141     private static boolean isObjectBarrier(FixedWithNextNode node, final Node next) {
 142         return next instanceof ObjectWriteBarrier && validateBarrier((FixedAccessNode) node, (ObjectWriteBarrier) next);
 143     }
 144 
 145     private static boolean isArrayBarrier(FixedWithNextNode node, final Node next) {
 146         return (next instanceof ArrayRangeWriteBarrier) && ((ArrayRangeWriteNode) node).getArray() == ((ArrayRangeWriteBarrier) next).getObject();
 147     }
 148 
 149     private static boolean isObjectWrite(Node node) {
 150         // Read nodes with barrier attached (G1 Ref field) are not validated yet.
 151         return node instanceof FixedAccessNode && ((HeapAccess) node).getBarrierType() != BarrierType.NONE && !(node instanceof ReadNode);
 152     }
 153 
 154     private static boolean isObjectArrayRangeWrite(Node node) {
 155         return node instanceof ArrayRangeWriteNode && ((ArrayRangeWriteNode) node).isObjectArray();
 156     }
 157 
 158     private static void expandFrontier(NodeFlood frontier, Node node) {
 159         for (Node previousNode : node.cfgPredecessors()) {
 160             if (previousNode != null) {
 161                 frontier.add(previousNode);
 162             }
 163         }
 164     }
 165 
 166     private static boolean isSafepoint(Node node) {
 167         if (node instanceof FixedAccessNode) {
 168             // Implicit null checks on reads or writes do not count.
 169             return false;
 170         }
 171         /*
 172          * LoopBegin nodes are also treated as safepoints since a bottom-up analysis is performed
 173          * and loop safepoints are placed before LoopEnd nodes. Possible elimination of write
 174          * barriers inside loops, derived from writes outside loops, can not be permitted.
 175          */
 176         return ((node instanceof DeoptimizingNode) && ((DeoptimizingNode) node).canDeoptimize()) || (node instanceof LoopBeginNode);
 177     }
 178 
 179     private static ValueNode getValueWritten(FixedWithNextNode write) {
 180         if (write instanceof WriteNode) {
 181             return ((WriteNode) write).value();
 182         } else if (write instanceof LogicCompareAndSwapNode) {
 183             return ((LogicCompareAndSwapNode) write).getNewValue();
 184         } else if (write instanceof LoweredAtomicReadAndWriteNode) {
 185             return ((LoweredAtomicReadAndWriteNode) write).getNewValue();
 186         } else {
 187             throw GraalError.shouldNotReachHere(String.format("unexpected write node %s", write));
 188         }
 189     }
 190 
 191     private static boolean validateBarrier(FixedAccessNode write, ObjectWriteBarrier barrier) {
 192         assert write instanceof WriteNode || write instanceof LogicCompareAndSwapNode || write instanceof LoweredAtomicReadAndWriteNode : "Node must be of type requiring a write barrier " + write;
 193         if (!barrier.usePrecise()) {
 194             if (barrier.getAddress() instanceof OffsetAddressNode && write.getAddress() instanceof OffsetAddressNode) {
 195                 return GraphUtil.unproxify(((OffsetAddressNode) barrier.getAddress()).getBase()) == GraphUtil.unproxify(((OffsetAddressNode) write.getAddress()).getBase());
 196             }
 197         }
 198         return barrier.getAddress() == write.getAddress();
 199     }
 200 }