Strange bug ever in V8

Recently, I find out about a strange bug in V8. Everyone is discussing it in Twitter, Facebook, Gitter and other social networks. So, I will try to explain it.

To my knowledge, it happens in the latest stable version of Google Chrome (my version is 51.0.2704.103).

You can check it with the following snippet of code:

function test() {
  return null === 'undefined';
}

for (var i = 0; i < 1000; i++) {
  console.log(test());
}

This leads to the following result:

What happened?

Well, I’ve found a commit that fixes this issue. Here is the link, so you can look yourself into it.

https://github.com/v8/v8/commit/7dfb5beeec8821521beeb2b8eac36707a663064c

According to a commit description, the issue was in canonicalizations. What is that?

In computer science, canonicalizations (sometimes standardization or normalization) is a process for converting data that has more than one possible representation into a “standard”, “normal”, or canonical form. This can be done to compare different representations for equivalence, to count the number of distinct data structures, to improve the efficiency of various algorithms by eliminating repeated calculations, or to make it possible to impose a meaningful sorting order.

In our case, the issue was in strings canonicalizations.

Let me give you a brief example of what canonicalizations is via boolean. Let’s say, in JavaScript, we can write boolean as true, false, 1, 0, empty string, etc… But, in canonical form it can be only true or false. That is a canonical form of boolean. The only one form of representing the data, the correct one.

That’s where this bug was. Crankshaft compiler in V8 does it a little wrong when optimizing your code. That’s why first iterations were right in our loop until Crankshaft optimized it.

Share your thoughts, will be glad to discuss.

UPD: Thanks to Vyacheslav Egorov, we have a nice explanation of what happened:

Regarding the bug itself. There is a code in Crankshaft that looks at typeof x == “…” and typeof x === “…” and tries to figure out if they always evaluate to true or false (see HTypeofIsAndBranch::KnownSuccessorBlock). For example if x is a constant it just computes typeof x and compares it with right hand side in compile time. However Crankshaft does not actually call to the same typeof implementation that normal JavaScript uses. For unknown reasons (probably because Crankshaft optimization passes can run in a background compiler thread) it has a its own implementation of typeof (see TypeOfString function). This implementation got out of sync when V8 folks were refactoring stuff related to an obscure thing called “undetectable objects” — null got marked as undetectable object for Crankshaft in this change but TypeOfString implementation was not aligned with this change.

Note: that TypeOfString was only ever used to fold constant HTypeOfIsAndBranch instructions and was never used to constant fold standalone typeof Const which did not participate in typeof x == “…” like pattern. That’s why things like (0, typeof null) == ‘undefined’ work around this bug — because they break recognition of this pattern.

Regarding let vs var. If you bump iteration limit for the `var` case to 20000 you will see it hit the bug. The reason for this is that for loop with `let`-binding gets desugared in a very baroque way in V8 — which causes it to be optimized earlier than for loop with `var`-binding.

(reference)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.