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 

    69     public WriteBarrierVerificationPhase(GraalHotSpotVMConfig config) {

    70         this.config = config;

    71     }

    72 

    73     @Override

    74     protected void run(StructuredGraph graph) {

    75         processWrites(graph);

    76     }

    77 

    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 

    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 

   121     private boolean useG1GC() {

   122         return config.useG1GC;

   123     }

   124 

   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 

   147     private static boolean isObjectBarrier(FixedWithNextNode node, final Node next) {

   148         return next instanceof ObjectWriteBarrier && validateBarrier((FixedAccessNode) node, (ObjectWriteBarrier) next);

   149     }

   150 

   151     private static boolean isArrayBarrier(FixedWithNextNode node, final Node next) {

   152         return (next instanceof ArrayRangeWriteBarrier) && ((ArrayRangeWrite) node).getAddress() == ((ArrayRangeWriteBarrier) next).getAddress();

   153     }

   154 

   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 

   160     private static boolean isObjectArrayRangeWrite(Node node) {

   161         return node instanceof ArrayRangeWrite && ((ArrayRangeWrite) node).writesObjectArray();

   162     }

   163 

   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 

   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 

   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 

   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 }