Bug 167344 – InferredTypeTable entry manipulation is not TOCTOU race safe

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Michael Saboff]

InferredTypeTable.cpp has Time of Check, Time of Use (TOCTOU) races in code that accesses and modifies the values stored in the table.  Consider:

void InferredTypeTable::visitChildren(JSCell* cell, SlotVisitor& visitor)
{
    InferredTypeTable* inferredTypeTable = jsCast<InferredTypeTable*>(cell);

    ConcurrentJSLocker locker(inferredTypeTable->m_lock);
    
    for (auto& entry : inferredTypeTable->m_table) {
        if (!entry.value)
            continue;
        if (entry.value->isRelevant())
            visitor.append(entry.value);
        else
            entry.value.clear();
    }
}

Between the null check at the top of the loop and call to isRelevant(), the entry can be cleared by another thread.

<rdar://problem/30156092>

[Michael Saboff]

Created attachment 299568 [details]
Patch

[Filip Pizlo]

Comment on attachment 299568 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=299568&action=review

> Source/JavaScriptCore/runtime/InferredTypeTable.cpp:67
> +            entryValue.clear();

This clears the value you loaded as opposed to clearing the value in the table. Not the same thing. You should leave this line of code unchanged.

> Source/JavaScriptCore/runtime/InferredTypeTable.cpp:83
> +        entryValue.clear();

Ditto.

> Source/JavaScriptCore/runtime/InferredTypeTable.cpp:118
> +        entryValue.clear();

Ditto.

> Source/JavaScriptCore/runtime/InferredTypeTable.cpp:139
> +    entryValue.clear();

Ditto.

> Source/JavaScriptCore/runtime/InferredTypeTable.cpp:157
> +        entryValue.clear();

Ditto.

[Michael Saboff]

Created attachment 299573 [details]
Updated Patch

(In reply to comment #2)
> Comment on attachment 299568 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=299568&action=review
> 
> > Source/JavaScriptCore/runtime/InferredTypeTable.cpp:67
> > +            entryValue.clear();
> 
> This clears the value you loaded as opposed to clearing the value in the
> table. Not the same thing. You should leave this line of code unchanged.
> 
> > Source/JavaScriptCore/runtime/InferredTypeTable.cpp:83
> > +        entryValue.clear();
> 
> Ditto.
> 
> > Source/JavaScriptCore/runtime/InferredTypeTable.cpp:118
> > +        entryValue.clear();
> 
> Ditto.
> 
> > Source/JavaScriptCore/runtime/InferredTypeTable.cpp:139
> > +    entryValue.clear();
> 
> Ditto.
> 
> > Source/JavaScriptCore/runtime/InferredTypeTable.cpp:157
> > +        entryValue.clear();
> 
> Ditto.

Fixed all instances.

[Michael Saboff]

Committed r211091: <http://trac.webkit.org/changeset/211091>

[Filip Pizlo]

This looks like it's a huge Octane regression.  Almost all of that regression is in deltablue.  Somehow, this broke the logic of InferredTypeTable so that we are no longer inferring types.

[Filip Pizlo]

Comment on attachment 299573 [details]
Updated Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=299573&action=review

> Source/JavaScriptCore/runtime/InferredTypeTable.cpp:133
> -        result.iterator->value.set(vm, this, inferredType);
> -    } else if (!result.iterator->value)
> +        entryValue.set(vm, this, inferredType);
> +    } else if (!entryValue)

Oh man, you're never setting the new value because you're setting entryValue.  You need to result.iterator->value.set here.

[WebKit Commit Bot]

Re-opened since this is blocked by bug 167384

[Michael Saboff]

Created attachment 299649 [details]
Patch addressing Octane perf regression

Performance test results:

Benchmark report for SunSpider, LongSpider, Octane, and Kraken on il0204e-dhcp90 (MacPro6,1).

VMs tested:
"Baseline" at /Volumes/Data/src/wk.work/OpenSource/WebKitBuild/Release/jsc (r211112)
"InferredTypesFix" at /Volumes/Data/src/wk/OpenSource/WebKitBuild/Release/jsc (r211112)

Collected 6 samples per benchmark/VM, with 6 VM invocations per benchmark. Emitted a call to gc() between sample
measurements. Used 1 benchmark iteration per VM invocation for warm-up. Used the jsc-specific preciseTime() function to
get microsecond-level timing. Reporting benchmark execution times with 95% confidence intervals in milliseconds.

                                                 Baseline              InferredTypesFix                                 
SunSpider:
   3d-cube                                    6.4209+-0.3679     ?      6.5473+-0.4023        ? might be 1.0197x slower
   3d-morph                                   6.4951+-0.2281     ?      6.5304+-0.1367        ?
   3d-raytrace                                6.8444+-0.4943     ?      7.1405+-0.3123        ? might be 1.0433x slower
   access-binary-trees                        2.7230+-0.0694     ?      2.7451+-0.1568        ?
   access-fannkuch                            7.1478+-0.3453     ?      7.2475+-0.1555        ? might be 1.0139x slower
   access-nbody                               3.5854+-0.1374     ?      3.6036+-0.1255        ?
   access-nsieve                              3.9108+-0.1406     ?      3.9179+-0.0680        ?
   bitops-3bit-bits-in-byte                   1.5856+-0.0974            1.5332+-0.0726          might be 1.0342x faster
   bitops-bits-in-byte                        3.2681+-0.1637     ?      3.3331+-0.1548        ? might be 1.0199x slower
   bitops-bitwise-and                         2.5864+-0.0676            2.5625+-0.0736        
   bitops-nsieve-bits                         4.1708+-0.2883            4.0641+-0.1070          might be 1.0263x faster
   controlflow-recursive                      3.1398+-0.0515     ?      3.1532+-0.1406        ?
   crypto-aes                                 5.7424+-0.1814            5.6379+-0.1150          might be 1.0185x faster
   crypto-md5                                 3.1805+-0.0568     ?      3.2399+-0.0988        ? might be 1.0187x slower
   crypto-sha1                                3.6145+-0.0635     ?      3.7335+-0.0959        ? might be 1.0329x slower
   date-format-tofte                         11.8614+-0.5058           11.6270+-0.3326          might be 1.0202x faster
   date-format-xparb                          6.8865+-0.2567            6.6904+-0.2633          might be 1.0293x faster
   math-cordic                                3.7902+-0.0637            3.7128+-0.1476          might be 1.0208x faster
   math-partial-sums                          5.6377+-0.1549     ?      5.7065+-0.2119        ? might be 1.0122x slower
   math-spectral-norm                         2.6617+-0.0744            2.6497+-0.0573        
   regexp-dna                                 8.4866+-0.2157     ?      8.6143+-0.1351        ? might be 1.0151x slower
   string-base64                              6.4612+-0.5030            6.0780+-0.2290          might be 1.0631x faster
   string-fasta                               6.9689+-0.0527     ?      7.0331+-0.1079        ?
   string-tagcloud                           11.1892+-0.2837     ?     11.2621+-0.2968        ?
   string-unpack-code                        22.7508+-0.3979     ?     23.1963+-0.7508        ? might be 1.0196x slower
   string-validate-input                      5.4245+-0.1385     ?      5.5733+-0.2508        ? might be 1.0274x slower

   <arithmetic>                               6.0205+-0.0603     ?      6.0436+-0.0414        ? might be 1.0038x slower

                                                 Baseline              InferredTypesFix                                 
LongSpider:
   3d-cube                                  991.6088+-4.3694     ^    978.5234+-8.3152        ^ definitely 1.0134x faster
   3d-morph                                 750.0930+-2.5157     ?    751.8838+-4.0748        ?
   3d-raytrace                              616.2951+-4.4204     ?    623.4863+-8.3589        ? might be 1.0117x slower
   access-binary-trees                     1058.4160+-18.4894        1051.8694+-8.6104        
   access-fannkuch                          323.9742+-8.4540          320.9875+-12.5369       
   access-nbody                             706.4329+-4.0762          694.8193+-20.0971         might be 1.0167x faster
   access-nsieve                            408.3072+-4.6034          401.2708+-5.7336          might be 1.0175x faster
   bitops-3bit-bits-in-byte                  37.9218+-0.8019     ?     37.9934+-0.5970        ?
   bitops-bits-in-byte                      125.3421+-6.9399          125.3361+-6.0166        
   bitops-nsieve-bits                       456.8028+-2.4240          453.7797+-2.3159        
   controlflow-recursive                    507.5275+-6.0453     ?    517.8056+-5.7289        ? might be 1.0203x slower
   crypto-aes                               753.1373+-11.5402         741.2782+-5.4138          might be 1.0160x faster
   crypto-md5                               631.9283+-22.9290         623.7808+-2.8468          might be 1.0131x faster
   crypto-sha1                              793.1381+-4.9837          791.7640+-5.5127        
   date-format-tofte                        567.3540+-20.2099    ?    569.3134+-12.9838       ?
   date-format-xparb                        763.4613+-25.0997    ?    781.0818+-10.9772       ? might be 1.0231x slower
   hash-map                                 183.4460+-3.1517          178.1792+-5.1301          might be 1.0296x faster
   math-cordic                              550.3267+-3.5766     ?    551.2601+-3.1013        ?
   math-partial-sums                        427.7788+-5.0810     ?    428.8451+-5.8373        ?
   math-spectral-norm                       624.9413+-6.0367          620.0635+-1.3772        
   string-base64                            439.6993+-45.4779    ?    462.4300+-22.6587       ? might be 1.0517x slower
   string-fasta                             443.5594+-13.7696         442.9814+-13.3058       
   string-tagcloud                          216.9223+-4.1820     ^    210.0163+-1.8127        ^ definitely 1.0329x faster

   <geometric>                              447.4081+-1.8973          446.4484+-2.7897          might be 1.0021x faster

                                                 Baseline              InferredTypesFix                                 
Octane:
   encrypt                                   0.21097+-0.00735          0.20948+-0.00167       
   decrypt                                   3.61547+-0.02368    ?     3.62406+-0.10379       ?
   deltablue                        x2       0.17321+-0.01541          0.16993+-0.00396         might be 1.0193x faster
   earley                                    0.34667+-0.00408    ?     0.34687+-0.00207       ?
   boyer                                     5.64998+-0.03264    ?     5.67878+-0.10221       ?
   navier-stokes                    x2       5.68744+-0.03055    ?     5.73907+-0.13634       ?
   raytrace                         x2       0.99721+-0.01066    ?     1.00053+-0.01190       ?
   richards                         x2       0.11394+-0.00259    ?     0.11405+-0.00213       ?
   splay                            x2       0.33324+-0.00352          0.33192+-0.00326       
   regexp                           x2      21.08939+-0.14539    ?    21.21617+-0.26932       ?
   pdfjs                            x2      51.58568+-0.22684    ?    51.88562+-0.59929       ?
   mandreel                         x2      57.42961+-1.08898         57.01296+-0.23170       
   gbemu                            x2      46.94567+-3.44121         45.42880+-0.71315         might be 1.0334x faster
   closure                                   0.71822+-0.00509          0.71468+-0.00437       
   jquery                                    9.42738+-0.05983    ?     9.47057+-0.09977       ?
   box2d                            x2      13.38796+-0.08151    ?    13.46752+-0.15528       ?
   zlib                             x2     428.49689+-19.58085   ?   433.01335+-15.17694      ? might be 1.0105x slower
   typescript                       x2     967.34713+-11.31398   ?   968.79667+-9.55830       ?

   <geometric>                               6.58992+-0.05488          6.58309+-0.02484         might be 1.0010x faster

                                                 Baseline              InferredTypesFix                                 
Kraken:
   ai-astar                                  123.823+-0.396      ?     126.659+-4.606         ? might be 1.0229x slower
   audio-beat-detection                       53.417+-0.623             53.166+-1.326         
   audio-dft                                 119.139+-1.082            118.281+-0.740         
   audio-fft                                  42.025+-6.392             38.619+-1.040           might be 1.0882x faster
   audio-oscillator                           57.238+-0.232      ?      57.753+-1.093         ?
   imaging-darkroom                           78.677+-2.037             78.562+-1.390         
   imaging-desaturate                         66.703+-1.296      ?      66.772+-1.912         ?
   imaging-gaussian-blur                      94.712+-6.311             86.502+-7.795           might be 1.0949x faster
   json-parse-financial                       44.782+-0.326      ?      45.773+-1.418         ? might be 1.0221x slower
   json-stringify-tinderbox                   29.509+-0.153      !      31.604+-0.287         ! definitely 1.0710x slower
   stanford-crypto-aes                        45.537+-0.323      ?      46.454+-0.883         ? might be 1.0201x slower
   stanford-crypto-ccm                        45.446+-4.544             42.731+-1.697           might be 1.0635x faster
   stanford-crypto-pbkdf2                    118.408+-1.515      ?     118.834+-2.139         ?
   stanford-crypto-sha256-iterative           37.577+-0.645      ?      37.619+-0.372         ?

   <arithmetic>                               68.357+-0.741             67.809+-0.721           might be 1.0081x faster

                                                 Baseline              InferredTypesFix                                 
Geomean of preferred means:
   <scaled-result>                           33.1890+-0.1992           33.1275+-0.0831          might be 1.0019x faster

[Michael Saboff]

Committed r211124: <http://trac.webkit.org/changeset/211124>