首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 二进制漏洞
    3. 发新帖
[原创]简单理解 V8 TurboFan
发表于: 2022-7-23 19:05 15948

[原创]简单理解 V8 TurboFan

Tokameine 活跃值
3
2022-7-23 19:05
15948

闲言碎语：之前一直不知道雪币能用来做什么，全拿去赌狗了，最近学弟跑来问我能不能送个邀请码，可我根本拿不出那么多雪币......我忏悔，不应该赌狗的

简单理解 TurboFan

“JavaScript 代码本身就是一个二进制程序。”
不知道读者是否在什么地方听说过这样的解释，但笔者认为这个形容相当生动。因为 JavaScript 的代码是懒惰解释的，只有在特定函数被执行时候，解释器才会对这部分代码进行解释，生成对应的字节码。但这些字节码会随着代码的运行而产生变动，同一份代码有可能在同一次执行中，由于动态优化的缘故而被解释为两段相差甚大的字节码。不知道您现在是否对这句话有了一点体会。在某些文章中我们甚至能看见这样的解释：“解释器即编译器”。

V8 的工作原理

或许您已经在某些地方见过这张图了，它很简洁的概况了整个流程。

 

  • 首先会将 JavaScript 代码传递给 V8 引擎，并将其递给 Parse
  • 然后它会根据代码生成对应的抽象语法树(AST)
  • 接下来，Ignition 解释器就会直接根据 AST 生成对应的字节码，并开始执行它们
  • 会有另外一个线程监测代码的执行过程，收集合适的数据进行回调
  • TurboFan 会根据这些数据优化字节码，让它们能够更快的执行
 

一个最简单的例子是，如果在运行过程中，TurboFan 发现某个函数的参数无论如何都只会是 32bit 整数，而不会是其他任何类型，那么它就可以省略掉很多类型检查上的操作了，完全有可能让一些加法被优化为单纯的 add 指令，而不是其他更加复杂的函数；但如果运行中发现，在某一时刻，传入的参数类型发生了变化，那么就会去除这次的优化，令代码回到本来的状态。

 

从安全的角度来说，如果一段被优化后的代码在遇到某些非法输入时没能正确的执行“去优化(deoptimizations)”步骤或是甚至没有做 deoptimizations，就有可能导致这段代码被错误的使用。

V8 字节码

字节码是根据语法树转换而来的，那不如我们先从语法树开始 。通过添加参数 --print-ast 可以令其打印出 AST。来看下面的示例：

1
2
3
4
5
function add(val1, val2) {
    return val1 + val2;
}
var res1=add(1,2);
var res2=add("a","b");
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
$ ./d8 ./bytecode.js --print-ast
[generating bytecode for function: ]
--- AST ---
FUNC at 0
. KIND 0
. LITERAL ID 0
. SUSPEND COUNT 0
. NAME ""
. INFERRED NAME ""
. DECLS
. . FUNCTION "add" = function add
. . VARIABLE (0x56295442b6b0) (mode = VAR, assigned = true) "res1"
. . VARIABLE (0x56295442b7c8) (mode = VAR, assigned = true) "res2"
. BLOCK NOCOMPLETIONS at -1
. . EXPRESSION STATEMENT at 62
. . . INIT at 62
. . . . VAR PROXY unallocated (0x56295442b6b0) (mode = VAR, assigned = true) "res1"
. . . . CALL
. . . . . VAR PROXY unallocated (0x56295442b650) (mode = VAR, assigned = true) "add"
. . . . . LITERAL 1
. . . . . LITERAL 2
. BLOCK NOCOMPLETIONS at -1
. . EXPRESSION STATEMENT at 81
. . . INIT at 81
. . . . VAR PROXY unallocated (0x56295442b7c8) (mode = VAR, assigned = true) "res2"
. . . . CALL
. . . . . VAR PROXY unallocated (0x56295442b650) (mode = VAR, assigned = true) "add"
. . . . . LITERAL "a"
. . . . . LITERAL "b"
 
[generating bytecode for function: add]
--- AST ---
FUNC at 12
. KIND 0
. LITERAL ID 1
. SUSPEND COUNT 0
. NAME "add"
. PARAMS
. . VAR (0x56295442b6e0) (mode = VAR, assigned = false) "val1"
. . VAR (0x56295442b760) (mode = VAR, assigned = false) "val2"
. DECLS
. . VARIABLE (0x56295442b6e0) (mode = VAR, assigned = false) "val1"
. . VARIABLE (0x56295442b760) (mode = VAR, assigned = false) "val2"
. RETURN at 31
. . ADD at 43
. . . VAR PROXY parameter[0] (0x56295442b6e0) (mode = VAR, assigned = false) "val1"
. . . VAR PROXY parameter[1] (0x56295442b760) (mode = VAR, assigned = false) "val2"

第一个 AST 是整个程序执行流的，而第二个则是函数 add 的 AST，我们的重点放在第二个上并将其转为流程图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                       +---------+
             +---------+ Function+----------+
             |         +---------+          |
          +--v---+                     +----v---+
          |params|                     | return |
     +---------------+                 +----+---+
     |               |                      |
     |               |                      |
+----v-----+   +----------+            +----v----+
| var val1 |   | var val2 |            |   add   |
+----------+   +----------+     +------+---------+-------+
                                |                        |
                                |                        |
                        +-------v--------+     +---------v------+
                        | var proxy val1 |     | var proxy val2 |
                        +----------------+     +----------------+

这里我们省略掉了 DECLS 分支，因为我们并不是很关心这些。

 

出于一些特殊的规则，语法树会为函数创建两个分支，一个用于参数，另外一个则用于执行流。并且，执行流中使用 var proxy 结点代替参数，当使用到参数时，这两个结点会从左子树中的参数结点中获取变量。

 

而如果附带 --print-bytecode 参数，就能够得到其对应的字节码：

1
2
3
4
5
6
7
8
9
10
11
12
[generated bytecode for function: add (0x314000253b61 )]
Bytecode length: 6
Parameter count 3
Register count 0
Frame size 0
Bytecode age: 0
         0x314000253d3e @    0 : 0b 04             Ldar a1
         0x314000253d40 @    2 : 39 03 00          Add a0, [0]
         0x314000253d43 @    5 : a9                Return
Constant pool (size = 0)
Handler Table (size = 0)
Source Position Table (size = 0)
  • Parameter count：参数个数。除了我们提供的参数以外，还包括了一个 this 指针。

Ignition 使用一种名为 “register machine” 的机制来模拟寄存器，其中有一个与 x86 下的 rax 相似的 accumulator register(累加寄存器)，它用于常规的计算以及返回值。

 

具体的字节码就不再做翻译了，因为下文中其实不怎么需要它，此处多有一些抛砖引玉的意思。

优化过程

通过添加参数 --trace-opt 和 --trace-deopt 可以跟踪程序的优化和去优化过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Player{}
class Wall{}
 
function move(obj) {
  var tmp = obj.x + 42;
  var x = Math.random();
  x += 1;
  return tmp + x;
}
 
for (var i = 0; i < 0x10000; ++i) {
  move(new Player());
}
move(new Wall());
for (var i = 0; i < 0x10000; ++i) {
  move(new Wall());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
$ ./d8 ./bytecode.js --trace-opt --trace-deopt
[marking 0x3fe4081d3629 = 0x3fe4081d3211)> for optimized recompilation, reason: small function]
[compiling method 0x3fe4081d3629 = 0x3fe4081d3211)> (target TURBOFAN) using TurboFan]
[optimizing 0x3fe4081d3629 = 0x3fe4081d3211)> (target TURBOFAN) - took 0.139, 0.330, 0.015 ms]
[completed optimizing 0x3fe4081d3629 = 0x3fe4081d3211)> (target TURBOFAN)]
[marking 0x3fe4081d35ad = 0x3fe4081d317d)> for optimized recompilation, reason: hot and stable]
[compiling method 0x3fe4081d35ad = 0x3fe4081d317d)> (target TURBOFAN) using TurboFan OSR]
[optimizing 0x3fe4081d35ad = 0x3fe4081d317d)> (target TURBOFAN) - took 0.137, 0.687, 0.019 ms]
 
[bailout (kind: deopt-soft, reason: Insufficient type feedback for construct): begin. deoptimizing 0x3fe4081d35ad = 0x3fe4081d317d)>, opt id 1, bytecode offset 123, deopt exit 6, FP to SP delta 96, caller SP 0x7ffdd0530428, pc 0x3fe4001c4b51]
[bailout (kind: deopt-eager, reason: wrong map): begin. deoptimizing 0x3fe4081d3629 = 0x3fe4081d3211)>, opt id 0, bytecode offset 0, deopt exit 1, FP to SP delta 32, caller SP 0x7ffdd05303b8, pc 0x3fe4001c485f]
[marking 0x3fe4081d3629 = 0x3fe4081d3211)> for optimized recompilation, reason: small function]
[compiling method 0x3fe4081d3629 = 0x3fe4081d3211)> (target TURBOFAN) using TurboFan]
[marking 0x3fe4081d35ad = 0x3fe4081d317d)> for optimized recompilation, reason: hot and stable]
[optimizing 0x3fe4081d3629 = 0x3fe4081d3211)> (target TURBOFAN) - took 0.138, 0.612, 0.098 ms]
[completed optimizing 0x3fe4081d3629 = 0x3fe4081d3211)> (target TURBOFAN)]
[compiling method 0x3fe4081d35ad = 0x3fe4081d317d)> (target TURBOFAN) using TurboFan OSR]
[optimizing 0x3fe4081d35ad = 0x3fe4081d317d)> (target TURBOFAN) - took 0.253, 0.901, 0.044 ms]

可以注意到，当程序多次执行 move(new Player()) 时，TurboFan 认为可以对此做更进一步的优化以加快程序执行；而让其遇到 move(new Wall()) 时，则因为二者的不同类型而出现 wrong map ，于是其去除以前的优化并重新执行，再之后又因为多次执行而再次优化。

也可以通过 %PrepareFunctionForOptimization() 与 %OptimizeFunctionOnNextCall() 来进行主动优化，不过这需要您在执行时添加参数 --allow-natives-syntax 来允许这种语法。

另外，具体的过程我们会在接下来的内容说明。目前我们需要知道的事实仅有如上这部分内容。

图形化分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function add(x)
{
    var va1=1;
    if(x)
        va1=0;
    return 1+va1;
}
 
for (let i = 0; i < 0x10000; ++i) {
 add(true);
}
for (let i = 0; i < 0x10000; ++i) {
 add(false);
}

通过添加 --trace-turbo 可以在目录下生成 *.json 和 *.cfg* ，我们可以将 add 函数导出的 json 导入到 turbolizer 中以获取到对应的值传递图：(隐藏了一部分，优化以前的状态)

 

 

在值传递的过程中可以注意到，Turbofan 总是传递 Range(n,n) 类型，它表示传出的值的上下限，对于常数来说，它的上下界是相同的；而对于 SpeculativeSafeIntergerAdd 这类运算函数，它的类型则根据执行流分别计算下界和上界。

是的，只需要知道值的上下限就能够确定最终能够使用什么样的类型了。它只是在尝试简化 AST 树，因此并不涉及到实际的执行过程，只需要确定在执行的过程中，需要用什么类型的值表示变量即可。

 

另外，因为一些编译原理上的设计，每个变量只会经过一次赋值，因此需要使用 Phi 结点去对值进行选择。尽管它只可能返回 0 或 1，但仍然给出了 Range(0,1) 。

 

在完成基本的构建以后，是通过 TyperPhase::Run 对整个结构图进行遍历并确定所有结点的属性，其调用链大致如下：

 

TyperPhase::Run --> Typer::Run --> GraphReducer::ReduceGraph --> Typer::Visitor::Reduce --> Typer::Visitor::***Typer (此处 * 用以指代某个名称，例如 JSCall)

 

这会遍历每一个结点，并根据它们的输入来确定最后的类型，并且在这个过程中，它会尝试减少一部分节点来加快运行效率。

 

姑且用一段简单的源代码来说明一下这个过程，哪怕我并不希望在入门阶段就立刻进入源代码层面，但又似乎逃不开它：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Typer::Run(const NodeVector& roots,
                LoopVariableOptimizer* induction_vars) {
  if (induction_vars != nullptr) {
    induction_vars->ChangeToInductionVariablePhis();
  }
  Visitor visitor(this, induction_vars);
  GraphReducer graph_reducer(zone(), graph(), tick_counter_, broker());
  graph_reducer.AddReducer(&visitor);
  for (Node* const root : roots) graph_reducer.ReduceNode(root);
  graph_reducer.ReduceGraph();
    ···
    induction_vars->ChangeToPhisAndInsertGuards();
  }
}

在 Typer::Run 中会调用 ReduceGraph 尝试对结点进行缩减，它最终会根据结点的类型来确定运行的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Type Typer::Visitor::JSCallTyper(Type fun, Typer* t) {
if (!fun.IsHeapConstant() || !fun.AsHeapConstant()->Ref().IsJSFunction()) {
return Type::NonInternal();
}
JSFunctionRef function = fun.AsHeapConstant()->Ref().AsJSFunction();
if (!function.shared().HasBuiltinId()) {
return Type::NonInternal();
}
switch (function.shared().builtin_id()) {
case Builtin::kMathRandom:
return Type::PlainNumber();
case Builtin::kMathFloor:
case Builtin::kMathCeil:
case Builtin::kMathRound:
case Builtin::kMathTrunc:
return t->cache_->kIntegerOrMinusZeroOrNaN;
···

这是一个庞大的 switch ，对于那些内置函数(buildin)，它能够很快找出对应的类型；而对于一些其他类型的函数，则返回 NonInternal 。这么做的目的是能够简化一些检查操作，既然判明了这个结点必然会是某个确定的属性，就不再需要对它的输入做其他类型的检查了。

 

对于常数，也有类似却又小得多的结果：

1
2
3
4
Type Typer::Visitor::TypeNumberConstant(Node* node) {
double number = OpParameter(node->op());
return Type::Constant(number, zone());
}

不过这里用到的是 double 类型，所以 v8 中的常数最大值肯定小于普通的八字节可表示的常数最大值。

 

然后再进入 Type::Constant ：

1
2
3
4
5
6
7
8
9
10
11
Type Type::Constant(double value, Zone* zone) {
if (RangeType::IsInteger(value)) {
return Range(value, value, zone);
} else if (IsMinusZero(value)) {
return Type::MinusZero();
} else if (std::isnan(value)) {
return Type::NaN();
}
DCHECK(OtherNumberConstantType::IsOtherNumberConstant(value));
return OtherNumberConstant(value, zone);
}

对于普通整数的返回值自然就是一个 Range 了，另外还有两种值被使用 -0 和 NaN 。

 

而 Speculative 前缀含有推测的意思，这往往意味着这个函数能够根据情况进一步优化，例如SpeculativeSafeIntegerAdd 就是如此。在优化以前，它会以这个结点表示所有的加法，而在它通过代码运行时分析，发现其执行数据符合一定的预期时，就能够用更加具体且更加快速的函数来替代了。

1
2
3
Type OperationTyper::SpeculativeToNumber(Type type) {
  return ToNumber(Type::Intersect(type, Type::NumberOrOddball(), zone()));
}

ToNumber 会继续向下化简，最终根据我们给出的 Range 选择一个合适的函数替代，我们以如下的例子说明：

 

假如我们使用一个稍大一些的数：

1
2
3
4
5
6
7
8
let opt_me = (x) => {
  return x + 1000000000000;
}
opt_me(42);
for(var i=0;i<0x10000;i++)
{
opt_me(4242);
}

就会使用 SpeculativeNumberAdd 替代它：

 


[注意]看雪招聘，专注安全领域的专业人才平台！

收藏
免费 ・5
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回