April 6, 2020

WebKit の JSObject の Butterfly アドレスについて調べた

WebKit の JSObject について調べていたのでメモ。

準備

まずはリポジトリを clone する。

$ ghq get git://git.webkit.org/WebKit.git

debug 付きで JavaScriptCore のみをビルドして実行する。

$ ./Tools/Scripts/build-webkit --jsc-only --debug
$ ./WebKitBuild/Debug/bin/jsc

今回は lldb でデバッグしながら見ていく。
jsc 内で describe() を実行するとその JSObject の情報を取得できるので、この情報を参考に lldb でメモリの中身を見ていくことになる。

$ lldb ./WebKitBuild/Debug/bin/jsc
(lldb) target create "./WebKitBuild/Debug/bin/jsc"
Current executable set to './WebKitBuild/Debug/bin/jsc' (x86_64).
(lldb) run
Process 45074 launched: 'WebKit/webkit/WebKitBuild/Debug/bin/jsc' (x86_64)
>>> a = [1,2,3,4]
1,2,3,4
>>> describe(a)
Object: 0x108ab4340 with butterfly 0x10000e4008 (Structure 0x108af2a00:[Array, {}, ArrayWithInt32, Proto:0x108ac80a0, Leaf]), StructureID: 97
# Ctrl+c
>>> Process 45074 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP
    frame #0: 0x00007fff726b6eee libsystem_kernel.dylib`read + 10
libsystem_kernel.dylib`read:
->  0x7fff726b6eee <+10>: jae    0x7fff726b6ef8            ; <+20>
    0x7fff726b6ef0 <+12>: movq   %rax, %rdi
    0x7fff726b6ef3 <+15>: jmp    0x7fff726b541d            ; cerror
    0x7fff726b6ef8 <+20>: retq

これで準備OK。

JSC Object と Butterfly Pointer

先程作った Array adescribe() した結果は次のようになる。

>>> describe(a)
Object: 0x108ab4340 with butterfly 0x10000e4008 (Structure 0x108af2a00:[Array, {}, ArrayWithInt32, Proto:0x108ac80a0, Leaf]), StructureID: 97

JSC ではプロパティと要素を同じメモリ領域に格納し、その領域へのポインタをオブジェクト自体に保存する。
そのポインタは with butterfly ... で出力されているアドレスであり、このポインタを Butterfly と呼ぶ。

JSC Object

では、なぜ Butterfly と呼ばれるのか、について探る前に JSC Object の表現を見ていく。

先程作った Array a の Object のメモリを見てみる。

(lldb) x/8gx 0x108ab4340
0x108ab4340: 0x0108210500000061 0x00000010000e4008
0x108ab4350: 0x00000000badbeef0 0x00000000badbeef0
0x108ab4360: 0x00000000badbeef0 0x00000000badbeef0
0x108ab4370: 0x00000000badbeef0 0x00000000badbeef0

0x108ab43408 には Butterfly Pointer がある。
Butterfly Pointer を見ると Array a の要素の値が含まれていることがわかる。

(lldb) x/8gx 0x00000010000e4008
0x10000e4008: 0xffff000000000001 0xffff000000000002
0x10000e4018: 0xffff000000000003 0xffff000000000004
0x10000e4028: 0x0000000000000000 0x00000000badbeef0
0x10000e4038: 0x00000000badbeef0 0x00000000badbeef0

値の先頭に ffff がついているが、これはSource/JavaScriptCore/runtime/JSCJSValue.h を見ればわかる。

     * This range of NaN space is represented by 64-bit numbers begining with the 16-bit
     * hex patterns 0xFFFE and 0xFFFF - we rely on the fact that no valid double-precision
     * numbers will fall in these ranges.
     *
     * The top 16-bits denote the type of the encoded JSValue:
     *
     *     Pointer {  0000:PPPP:PPPP:PPPP
     *              / 0001:****:****:****
     *     Double  {         ...
     *              \ FFFE:****:****:****
     *     Integer {  FFFF:0000:IIII:IIII
     * The scheme we have implemented encodes double precision values by performing a
     * 64-bit integer addition of the value 2^48 to the number. After this manipulation
     * no encoded double-precision value will begin with the pattern 0x0000 or 0xFFFF.
     * Values must be decoded by reversing this operation before subsequent floating point
     * operations may be peformed.
     *
     * 32-bit signed integers are marked with the 16-bit tag 0xFFFF.
     *
     * The tag 0x0000 denotes a pointer, or another form of tagged immediate. Boolean,
     * null and undefined values are represented by specific, invalid pointer values:
     *
     *     False:     0x06
     *     True:      0x07
     *     Undefined: 0x0a
     *     Null:      0x02
     *

どうも Integer は 0xffff がつくらしい。
他にも Pointer は 0000:PPPP:PPPP:PPPP のフォーマットであること、False や True はそれぞれ 0x06 , 0x07 で表現されていることがわかる。

実際に確認してみる。

>>> a = [5, false, true, {}, undefined, 123456, -5]
5,false,true,[object Object],,123456,-5
>>> describe(a)
Object: 0x108ab4350 with butterfly 0x10000f8488 (Structure 0x108af2ae0:[Array, {}, ArrayWithContiguous, Proto:0x108ac80a0]), StructureID: 99

>>> Process 24360 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP
    frame #0: 0x00007fff726b6eee libsystem_kernel.dylib`read + 10
libsystem_kernel.dylib`read:
->  0x7fff726b6eee <+10>: jae    0x7fff726b6ef8            ; <+20>
    0x7fff726b6ef0 <+12>: movq   %rax, %rdi
    0x7fff726b6ef3 <+15>: jmp    0x7fff726b541d            ; cerror
    0x7fff726b6ef8 <+20>: retq
(lldb) x/8gx 0x10000f8488
0x10000f8488: 0xffff000000000005 0x0000000000000006
0x10000f8498: 0x0000000000000007 0x0000000108ab00c0
0x10000f84a8: 0x000000000000000a 0xffff00000001e240
0x10000f84b8: 0xffff0000fffffffb 0x00000000badbeef0

0x0000000108ab00c0{} なのだが、これはポインタで 0000:PPPP:PPPP:PPPP のフォーマットになっている。
確かにドキュメントどおりのフォーマット、値になっている。

Butterfly Pointer

話を Array に戻す。 Array a に値を push してみる。

>>> describe(a)
Object: 0x108ab4340 with butterfly 0x8000e4008 (Structure 0x108af2a00:[Array, {}, ArrayWithInt32, Proto:0x108ac80a0, Leaf]), StructureID: 97
>>> a.push(5)
5
>>> a.push(6)
6
>>> describe(a)
Object: 0x108ab4340 with butterfly 0x8000e0008 (Structure 0x108af2a00:[Array, {}, ArrayWithInt32, Proto:0x108ac80a0, Leaf]), StructureID: 97
>>> Process 9896 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGSTOP
    frame #0: 0x00007fff726b6eee libsystem_kernel.dylib`read + 10
libsystem_kernel.dylib`read:
->  0x7fff726b6eee <+10>: jae    0x7fff726b6ef8            ; <+20>
    0x7fff726b6ef0 <+12>: movq   %rax, %rdi
    0x7fff726b6ef3 <+15>: jmp    0x7fff726b541d            ; cerror
    0x7fff726b6ef8 <+20>: retq
(lldb) x/8gx 0x108ab4340
0x108ab4340: 0x0108210500000061 0x00000008000e0008
0x108ab4350: 0x00000000badbeef0 0x00000000badbeef0
0x108ab4360: 0x00000000badbeef0 0x00000000badbeef0
0x108ab4370: 0x00000000badbeef0 0x00000000badbeef0
(lldb) x/8gx 0x8000e0008
0x8000e0008: 0xffff000000000001 0xffff000000000002
0x8000e0018: 0xffff000000000003 0xffff000000000004
0x8000e0028: 0xffff000000000005 0xffff000000000006
0x8000e0038: 0x0000000000000000 0x0000000000000000

値が増えていることが確認できる。そして、butterfly pointer のアドレスも変わっていることもわかる。
つまり、値を push することで reallocate されたと推測できる。
一方で StructureID は変化していない。

続いて Property を設定してみる。

>>> a.a = 7
7
>>> a.b = 8
8
>>> describe(a)
Object: 0x108ab4340 with butterfly 0x8000f4668 (Structure 0x108a70380:[Array, {a:100, b:101}, ArrayWithInt32, Proto:0x108ac80a0, Leaf]), StructureID: 295

こちらもまた butterfly pointer が変化している他、StructureID も変化した。
そして Structure に a, b という Property が作られている。

しかし butterfly pointer のアドレスのメモリを見ると値は変わっていないことがわかる。

(lldb) x/8gx 0x8000f4668
0x8000f4668: 0xffff000000000001 0xffff000000000002
0x8000f4678: 0xffff000000000003 0xffff000000000004
0x8000f4688: 0xffff000000000005 0xffff000000000006
0x8000f4698: 0x0000000000000000 0x0000000000000000

では Property の中身はどこに配置されたのかというと、要素より前(下位アドレス)に積まれている。

(lldb) x/8gx 0x8000f4648
0x8000f4648: 0x0000000000000000 0xffff000000000008
0x8000f4658: 0xffff000000000007 0x0000000d00000006
0x8000f4668: 0xffff000000000001 0xffff000000000002
0x8000f4678: 0xffff000000000003 0xffff000000000004

つまり図にするとこのようになる。

...
0x8000f4678   3
0x8000f4670   2
0x8000f4668   1
0x8000f4660   6
0x8000f4658   7
0x8000f4650   8
...

この 6 というのは配列用の要素数になる。 つまりこのようなメモリレイアウトになっている。

 (上位アドレス)
|     ...     |
|    Elem[N]  |
|    Elem[2]  |
|    Elem[1]  |
|    Elem[0]  |
|    Length   |
|  Property 1 |
|  Property 2 |
|  Property N |
|     ...     |
 (下位アドレス)

一般的なメモリレイアウトとして縦で示したが、横にすると、ちょうど要素の先頭を指すところに Butterfly Pointer があり、そこから右(上位アドレス)に要素値が並び、逆に左(下位アドレス)には Property が並んでいる。この様子を “蝶の羽” のよう例えて、ベースとなるこのポインタを Butterfly Pointer と呼ぶらしい。

メモリレイアウトの全体を示すとこのようになり、 JSCell を継承している。

ref : http://www.phrack.org/papers/attacking_javascript_engines.html

            +------------------------------------------+
            |                Butterfly                 |
            | baz | bar | foo | length: 2 | 42 | 13.37 |
            +------------------------------------------+
                                          ^
                                +---------+
               +----------+     |
               |          |     |
            +--+  JSCell  |     |      +-----------------+
            |  |          |     |      |                 |
            |  +----------+     |      |  MethodTable    |
            |       /\          |      |                 |
 References |       || inherits |      |  Put            |
   by ID in |  +----++----+     |      |  Get            |
  structure |  |          +-----+      |  Delete         |
      table |  | JSObject |            |  VisitChildren  |
            |  |          |<-----      |  ...            |
            |  +----------+     |      |                 |
            |       /\          |      +-----------------+
            |       || inherits |                  ^
            |  +----++----+     |                  |
            |  |          |     | associated       |
            |  | JSArray  |     | prototype        |
            |  |          |     | object           |
            |  +----------+     |                  |
            |                   |                  |
            v                   |          +-------+--------+
        +-------------------+   |          |   ClassInfo    |
        |    Structure      +---+      +-->|                |
        |                   |          |   |  Name: "Array" |
        | property: slot    |          |   |                |
        |     foo : 0       +----------+   +----------------+
        |     bar : 1       |
        |     baz : 2       |
        |                   |
        +-------------------+

この様子は lldb を使って可視化できる。

(lldb) p *(JSC::JSArray*)(0x108ab4340)
(JSC::JSArray) $9 = {
  JSC::JSNonFinalObject = {
    JSC::JSObject = {
      JSC::JSCell = {
        m_structureID = 295
        m_indexingTypeAndMisc = '\x05'
        m_type = ArrayType
        m_flags = '\b'
        m_cellState = DefinitelyWhite
      }
      m_butterfly = (m_value = 0x00000010000f4668)
    }
  }
}

では object はどうなっているのだろうか。Array のように要素がない場合、どのように表現されるのか確認する。

>>> a = {}
[object Object]
>>> describe(a)
Object: 0x1092b0080 with butterfly 0x0 (Structure 0x1092f20d0:[Object, {}, NonArray, Proto:0x1092b4000]), StructureID: 76
>>> a.b = 1
1
>>> a.c = 2
2
>>> describe(a)
Object: 0x1092b0080 with butterfly 0x0 (Structure 0x109270380:[Object, {b:0, c:1}, NonArray, Proto:0x1092b4000, Leaf]), StructureID: 295

Butterfly Pointer のアドレスがないことがわかる。
Array のときと違って Object のメモリを見るとプロパティが見える。

(lldb) x/8gx 0x1092b0080
0x1092b0080: 0x0100160000000127 0x0000000000000000
0x1092b0090: 0xffff000000000001 0xffff000000000002
0x1092b00a0: 0x0000000000000000 0x0000000000000000
0x1092b00b0: 0x0000000000000000 0x0000000000000000

プロパティを作り続けると butterfly が出てくる。

>>> a.d = 3
3
>>> a.e = 4
4
>>> a.f = 5
5
>>> describe(a)
Object: 0x1092b0080 with butterfly 0x0 (Structure 0x1092704d0:[Object, {b:0, c:1, d:2, e:3, f:4}, NonArray, Proto:0x1092b4000, Leaf]), StructureID: 298
>>> a.g = 6
6
>>> describe(a)
Object: 0x1092b0080 with butterfly 0x0 (Structure 0x109270540:[Object, {b:0, c:1, d:2, e:3, f:4, g:5}, NonArray, Proto:0x1092b4000, Leaf]), StructureID: 299
>>> a.h = 7
7
>>> describe(a)
Object: 0x1092b0080 with butterfly 0x8000fe6c8 (Structure 0x1092705b0:[Object, {b:0, c:1, d:2, e:3, f:4, g:5, h:100}, NonArray, Proto:0x1092b4000, Leaf]), StructureID: 300

Butterfly Pointer のアドレスを確認すると要素の部分が空になっている。

(lldb) x/8gx 0x8000fe6c8
0x8000fe6c8: 0x00000000badbeef0 0x00000000badbeef0
0x8000fe6d8: 0x00000000badbeef0 0x00000000badbeef0
0x8000fe6e8: 0x00000000badbeef0 0x00000000badbeef0
0x8000fe6f8: 0x00000000badbeef0 0x00000000badbeef0

Object を見ると6つまでのプロパティは見えるが、それ以降は連続していない。

(lldb) x/10gx 0x1092b0080
0x1092b0080: 0x010016000000012c 0x00000008000fe6c8
0x1092b0090: 0xffff000000000001 0xffff000000000002
0x1092b00a0: 0xffff000000000003 0xffff000000000004
0x1092b00b0: 0xffff000000000005 0xffff000000000006
0x1092b00c0: 0x00000000badbeef0 0x00000000badbeef0

7つめは… butterfly のプロパティのところに配置されていた。

(lldb) x/8gx 0x8000fe6b0
0x8000fe6b0: 0x0000000000000000 0xffff000000000007
0x8000fe6c0: 0x00000000badbeef0 0x00000000badbeef0
0x8000fe6d0: 0x00000000badbeef0 0x00000000badbeef0
0x8000fe6e0: 0x00000000badbeef0 0x00000000badbeef0

fm… もういちど describe() の結果を見てみる。

Object: 0x1092b0080 with butterfly 0x8000fe6c8 (Structure 0x1092705b0:[Object, {b:0, c:1, d:2, e:3, f:4, g:5, h:100}, NonArray, Proto:0x1092b4000, Leaf]), StructureID: 300

Structure の部分に注目すると Property h のオフセットが 100 になっている。
100というオフセットは、つまり Butterfly の Property のところになるようだ。
Object に6つまでしか Property が含まれないのは謎だが、そういう仕様っぽい気配。

References


このエントリーをはてなブックマークに追加

© Kohei Morita 2020