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 }