Changeset 187347 in webkit

Timestamp:

Jul 24, 2015, 11:23:13 AM (11 years ago)

Author:

fpizlo@apple.com

Message:

DFG::safeToExecute() is wrong for MultiGetByOffset, doesn't consider the structures of the prototypes that get loaded from
​https://bugs.webkit.org/show_bug.cgi?id=147250

Reviewed by Geoffrey Garen.

This fixes a nasty - but currently benign - bug in DFG::safeToExecute(). That function
will tell you if hoisting a node to some point is safe in the sense that the node will
not crash the VM if it executes at that point. A node may be unsafe to execute if we
cannot prove that at that point, the memory it is loading is not garbage. This is a
necessarily loose notion - for example it's OK to hoist a load if we haven't proved
that the load makes semantic sense at that point, since anyway the place where the node
did get used will still be guarded by any such semantic checks. But because we may also
hoist uses of the load, we need to make sure that it doesn't produce a garbage value.
Also, we need to ensure that the load won't trap. Hence safeToExecute() returns true
anytime we can be sure that a node will not produce a garbage result (i.e. a malformed
JSValue or object pointer) and will not trap when executed at the point in question.

The bug is that this verification isn't performed for the loads from prototypes inside
MultiGetByOffset. DFG::ByteCodeParser will guard MultiGetByOffset with CheckStructure's
on the prototypes. So, hypothetically, you might end up hoisting a MultiGetByOffset
above those structure checks, which would mean that we might load a value from a memory
location without knowing that the location is valid. It might then return the value
loaded.

This never happens in practice. Those structure checks are more hoistable that the
MultiGetByOffset, since they read a strict subset of the MultiGetByOffset's abstract
heap reads. Also, we hoist in program order. So, those CheckStructure's will always be
hoisted before the MultiGetByOffset gets hoisted.

But we should fix this anyway. DFG::safeToExecute() has a clear definition of what a
"true" return means for IR transformations, and it fails in satisfying that definition
for MultiGetByOffset.

There are various approaches we can use for making this safe. I considered two:

1) Have MultiGetByOffset refer to the prototypes it is loading from in IR, so that we

can check if it's safe to load from them.

2) Turn off MultiGetByOffset hoisting when it will emit loads from prototypes, and the

prototype structure isn't being watched.

I ended up using (2), because it will be the most natural solution once I finish
​https://bugs.webkit.org/show_bug.cgi?id=146929. Already now, it's somewhat more natural
than (1) since that requires more extensive IR changes. Also, (2) will give us what we
want in *most* cases: we will usually watch the prototype structure, and we will
usually constant-fold loads from prototypes. Both of these usually-true things would
have to become false for MultiGetByOffset hoisting to be disabled by this change.

This change also adds my attempt at a test, though it's not really a test of this bug.
This bug is currently benign. But, the test does at least trigger the logic to run,
which is better than nothing.

• dfg/DFGSafeToExecute.h:

(JSC::DFG::safeToExecute):

• tests/stress/multi-get-by-offset-hoist-around-structure-check.js: Added.

(foo):

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• dfg/DFGSafeToExecute.h (modified) (3 diffs)
• tests/stress/multi-get-by-offset-hoist-around-structure-check.js (added)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2015-07-23  Filip Pizlo  <fpizlo@apple.com>
+
+        DFG::safeToExecute() is wrong for MultiGetByOffset, doesn't consider the structures of the prototypes that get loaded from
+        https://bugs.webkit.org/show_bug.cgi?id=147250
+
+        Reviewed by Geoffrey Garen.
+        
+        This fixes a nasty - but currently benign - bug in DFG::safeToExecute(). That function
+        will tell you if hoisting a node to some point is safe in the sense that the node will
+        not crash the VM if it executes at that point. A node may be unsafe to execute if we
+        cannot prove that at that point, the memory it is loading is not garbage. This is a
+        necessarily loose notion - for example it's OK to hoist a load if we haven't proved
+        that the load makes semantic sense at that point, since anyway the place where the node
+        did get used will still be guarded by any such semantic checks. But because we may also
+        hoist uses of the load, we need to make sure that it doesn't produce a garbage value.
+        Also, we need to ensure that the load won't trap. Hence safeToExecute() returns true
+        anytime we can be sure that a node will not produce a garbage result (i.e. a malformed
+        JSValue or object pointer) and will not trap when executed at the point in question.
+        
+        The bug is that this verification isn't performed for the loads from prototypes inside
+        MultiGetByOffset. DFG::ByteCodeParser will guard MultiGetByOffset with CheckStructure's
+        on the prototypes. So, hypothetically, you might end up hoisting a MultiGetByOffset
+        above those structure checks, which would mean that we might load a value from a memory
+        location without knowing that the location is valid. It might then return the value
+        loaded.
+        
+        This never happens in practice. Those structure checks are more hoistable that the
+        MultiGetByOffset, since they read a strict subset of the MultiGetByOffset's abstract
+        heap reads. Also, we hoist in program order. So, those CheckStructure's will always be
+        hoisted before the MultiGetByOffset gets hoisted.
+        
+        But we should fix this anyway. DFG::safeToExecute() has a clear definition of what a
+        "true" return means for IR transformations, and it fails in satisfying that definition
+        for MultiGetByOffset.
+        
+        There are various approaches we can use for making this safe. I considered two:
+        
+        1) Have MultiGetByOffset refer to the prototypes it is loading from in IR, so that we
+           can check if it's safe to load from them.
+        
+        2) Turn off MultiGetByOffset hoisting when it will emit loads from prototypes, and the
+           prototype structure isn't being watched.
+        
+        I ended up using (2), because it will be the most natural solution once I finish
+        https://bugs.webkit.org/show_bug.cgi?id=146929. Already now, it's somewhat more natural
+        than (1) since that requires more extensive IR changes. Also, (2) will give us what we
+        want in *most* cases: we will usually watch the prototype structure, and we will
+        usually constant-fold loads from prototypes. Both of these usually-true things would
+        have to become false for MultiGetByOffset hoisting to be disabled by this change.
+        
+        This change also adds my attempt at a test, though it's not really a test of this bug.
+        This bug is currently benign. But, the test does at least trigger the logic to run,
+        which is better than nothing.
+
+        * dfg/DFGSafeToExecute.h:
+        (JSC::DFG::safeToExecute):
+        * tests/stress/multi-get-by-offset-hoist-around-structure-check.js: Added.
+        (foo):
+
 2015-07-23  Sukolsak Sakshuwong  <sukolsak@gmail.com>
 

trunk/Source/JavaScriptCore/dfg/DFGSafeToExecute.h

@@ -100 +100 @@
 // Determines if it's safe to execute a node within the given abstract state. This may
 // return false conservatively. If it returns true, then you can hoist the given node
-// up to the given point and expect that it will not crash. This doesn't guarantee that
-// the node will produce the result you wanted other than not crashing.
+// up to the given point and expect that it will not crash. It also guarantees that the
+// node will not produce a malformed JSValue or object pointer when executed in the
+// given state. But this doesn't guarantee that the node will produce the result you
+// wanted. For example, you may have a GetByOffset from a prototype that only makes
+// semantic sense if you've also checked that some nearer prototype doesn't also have
+// a property of the same name. This could still return true even if that check hadn't
+// been performed in the given abstract state. That's fine though: the load can still
+// safely execute before that check, so long as that check continues to guard any
+// user-observable things done to the loaded value.
 template<typename AbstractStateType>
 bool safeToExecute(AbstractStateType& state, Graph& graph, Node* node)
@@ -256 +263 @@
     case ConstantStoragePointer:
     case Check:
-    case MultiGetByOffset:
     case MultiPutByOffset:
     case ValueRep:
@@ -334 +340 @@
     }
         
+    case MultiGetByOffset: {
+        // We can't always guarantee that the MultiGetByOffset is safe to execute if it
+        // contains loads from prototypes. We know that it won't load from those prototypes if
+        // we watch the mutability of the properties being loaded. So, here we try to
+        // constant-fold prototype loads, and if that fails, we claim that we cannot hoist. We
+        // also know that a load is safe to execute if we are watching the prototype's
+        // structure.
+        for (const GetByIdVariant& variant : node->multiGetByOffsetData().variants) {
+            if (!variant.alternateBase()) {
+                // It's not a prototype load.
+                continue;
+            }
+            
+            JSValue base = variant.alternateBase();
+            FrozenValue* frozen = graph.freeze(base);
+            if (state.structureClobberState() == StructuresAreWatched
+                && frozen->structure()->dfgShouldWatch()
+                && frozen->structure()->isValidOffset(variant.offset())) {
+                // We're already watching that it's safe to load from this.
+                continue;
+            }
+            
+            JSValue constantResult = graph.tryGetConstantProperty(
+                variant.alternateBase(), variant.baseStructure(), variant.offset());
+            if (!constantResult) {
+                // Couldn't constant-fold a prototype load. Therefore, we shouldn't hoist
+                // because the safety of the load depends on structure checks on the prototype,
+                // and we're too cheap to verify that here.
+                return false;
+            }
+            
+            // Otherwise, we will either:
+            // - Not load from the prototype because constant folding will succeed in the
+            //   backend, or
+            // - Emit invalid code that fails watchpoint checks. This could happen if the
+            //   property becomes mutable after this point, since we already set the watchpoint
+            //   above. This case is OK since the code will fail watchpoint checks and never
+            //   get installed.
+        }
+        return true;
+    }
+
     case LastNodeType:
         RELEASE_ASSERT_NOT_REACHED();