Prototype property lookup incorrectly assumes that hashtable fetch suffices.

RESOLVED FIXED in Q1 12 - Brannan

Status

Tamarin
Library
P2
normal
RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: pnkfelix, Assigned: pnkfelix)

Tracking

(Blocks: 3 bugs)

unspecified
Q1 12 - Brannan
Dependency tree / graph
Bug Flags:
flashplayer-injection +
flashplayer-qrb +
flashplayer-bug +

Details

Attachments

(3 attachments, 6 obsolete attachments)

% cat /tmp/foo.as 
  var a = [];
  print(a[10]);
  Array.prototype[10] = "hello";
  print(a[10]);

64-bit DebugDebugger shell.  First at rev 5711, second at rev 5713.

% ./shell/avmshell.r5711 /tmp/foo.abc 
undefined
hello

% ./shell/avmshell.r5713 /tmp/foo.abc 
undefined
undefined

% hg log -r 5711:5713
changeset:   5711:93a6f1d1128f
user:        Edwin Smith <edwsmith@adobe.com>
date:        Tue Jan 04 14:56:48 2011 -0500
summary:     Bug 622903 - Valgrind/memcheck false positive on thisPage in TraceConservatePointer() (r=fklockii+)

changeset:   5712:9c0aeb405ad3
user:        Steven Johnson <stejohns@adobe.com>
date:        Tue Jan 04 12:55:41 2011 -0800
summary:     Bug 610063 - Port 'dense array' work from TT (r=lhansen)

changeset:   5713:96816b60cf0f
user:        Steven Johnson <stejohns@adobe.com>
date:        Tue Jan 04 13:19:17 2011 -0800
summary:     Fix unused-arg warnings in previous checkin (r=stejohns)


So this is another injection from dense array work.
(Assignee)

Updated

6 years ago
Flags: flashplayer-qrb?
Sigh; our Array implementation inconsistencies from the past continue to surprise.

Code:
  var a = [];
  Array.prototype[1] = "hello";
  Array.prototype[10] = "world";
  print("  a[   1]: " + a[   1]);
  print("  a[  10]: " + a[  10]);

  print("                  (now setting near element)")
  Array.prototype[0] = "introducing";
  print("  a[   0]: " + a[   0]);
  print("  a[   1]: " + a[   1]);
  print("  a[  10]: " + a[  10]);

  print("                  (now setting far element)")
  Array.prototype[1000] = "from far away";
  print("  a[   0]: " + a[   0]);
  print("  a[   1]: " + a[   1]);
  print("  a[  10]: " + a[  10]);
  print("  a[1000]: " + a[1000]);

rev5711:
  a[   1]: hello
  a[  10]: world
                  (now setting near element)
  a[   0]: undefined
  a[   1]: undefined
  a[  10]: world
                  (now setting far element)
  a[   0]: undefined
  a[   1]: undefined
  a[  10]: world
  a[1000]: from far away


rev5713:
  a[   1]: undefined
  a[  10]: undefined
                  (now setting near element)
  a[   0]: undefined
  a[   1]: undefined
  a[  10]: undefined
                  (now setting far element)
  a[   0]: introducing
  a[   1]: hello
  a[  10]: world
  a[1000]: from far away


This seems to be a case where the shift between dense and sparse is being exposed to user code.  The ScriptObject::getUintProperty code always uses the object hashtables for lookup while ascending the prototype-chain.  The Array in turn uses the object hashtable as the basis for its sparse storage.  And finally, in both cases, an instance of an Array is used as the prototype for instances of Array.  With the old code circa rev 5711, the array storage was split between a dense prefix and sparse suffix, and so the prototype lookup skips looking in the dense prefix (that's reflected in the change in how a[1] is printed above after setting Array.prototype[0]).  With the new code circa rev 5713, the array storage is always 100% dense or 100% sparse, but we try harder to keep it dense.  That's why one has to write a property at an index that is far far away before seeing any of the lookups succeed, but once it does become sparse, all of the properties become visible.

What's the right solution here?  Perhaps not to assume that the sparse hashtable lookup is the right one to use while traversing the prototype chain?

(That leads me to wonder: couldn't one observe this more generally for any object that has had its constructor's prototype set to an array instance?  Will investigate.)
(In reply to Felix S Klock II from comment #1)
> (That leads me to wonder: couldn't one observe this more generally for any
> object that has had its constructor's prototype set to an array instance? 
> Will investigate.)

The answer is: Yes, this is a general problem with lookups that traverse the prototype chain.

Assuming the right thing is to fix the prototype-lookup loop to handle arrays, this behavior may need to be versioned-checked.
Created attachment 561272 [details]
test B v1: test lookup when prototype is an Array

(this is a simple port of the code from comment 1 with a non-array constructor that has an array as its prototype.)
(Assignee)

Updated

6 years ago
Summary: array a[i] skips prototype for i > length → Prototype property lookup incorrectly assumes that hashtable fetch suffices.
(In reply to Felix S Klock II from comment #2)
> Assuming the right thing is to fix the prototype-lookup loop to handle
> arrays, this behavior may need to be versioned-checked.

(but then again, a *good* version check may be impossible.  Its not like we can bring back the prior oh-so-strange behavior where the presence/absence depended on the dense/sparse policy.)
Also, this comment above ScriptObject::getAtomProperty probably needs to be refined in light of this ticket:

     * traverse the delegate chain looking for a value.
     * [ed] it's okay to look only at the HT's in the delegate chain because
     * delegate values may only be instances of Object.  They cannot be objects
     * with slots.  We don't need to look at traits at each step.
Created attachment 561320 [details] [diff] [review]
patch P v1: no version checks.  no performance tuning.

Sketch of one way to skin this cat.

No version checks, because I'm not convinced they'd be meaningful here.

No performance tuning, because I haven't run any comparative benchmarks yet.

But it does bring the behavior of my reference test back in line with my expectations:

  a[   1]: hello
  a[  10]: world
                  (now setting near element)
  a[   0]: introducing
  a[   1]: hello
  a[  10]: world
                  (now setting far element)
  a[   0]: introducing
  a[   1]: hello
  a[  10]: world
  a[1000]: from far away
Attachment #561320 - Flags: feedback?(lhansen)

Comment 7

6 years ago
Comment on attachment 561320 [details] [diff] [review]
patch P v1: no version checks.  no performance tuning.

I've not checked this carefully in all its details but the approach seems reasonable.
Attachment #561320 - Flags: feedback?(lhansen) → feedback+

Comment 8

6 years ago
BTW:

- This strikes me as a shoo-in for Anza and it really should have been in Serrano,
  since technically it regresses relative to Argo, no?
- I agree versioning of a fix is probably meaningless and not desirable.

Updated

6 years ago
Assignee: nobody → fklockii
Flags: flashplayer-qrb?
Flags: flashplayer-qrb+
Flags: flashplayer-injection+
Flags: flashplayer-bug+
Priority: -- → P2
Target Milestone: --- → Q4 11 - Anza
(Assignee)

Updated

6 years ago
Blocks: 690498
(Assignee)

Updated

6 years ago
Blocks: 472863
Created attachment 564592 [details]
csv data for patch P v1

(will post .txt version shortly.)
Created attachment 564593 [details]
text formatted performance data for patch P v1

There are some troubling regressions.

It is possible that the regressions will go away when Bug 688486 is wrapped up.

I'd like to confirm that hypothesis before landing this.  (And even then, if this is targeted for Anza but Bug 688486 is targeted for a later release, then it might be worthwhile to figure out where the time is going in this patch alone...)
Oh, the data from the two posted attachments were taken from a 32-bit release shell atop Mac OS X on a 2x3.2 Ghz Quad-Core Intel Xeon MacPro.
this is targeted to Anza.  I suggest deferral; the regressions trouble me enough that I would not want to land patch P v1 as is, but I do not think I have time to revise it.

Comment 13

6 years ago
Agree with delaying patch until regressions are resolved.  Moving to Brannan.
Target Milestone: Q4 11 - Anza → Q1 12 - Brannan
(Assignee)

Updated

6 years ago
Blocks: 700686
Created attachment 577655 [details] [diff] [review]
test B v2: more thorough testing of all kinds of corners

On TR rev 5711 (i.e. before dense array work landed):

Array .proto start0 array          ref  1 a = undefined FAILED! expected: one A
Class .proto start0 array trans    ref  1 b = undefined FAILED! expected: one A
Function .proto start0 array trans ref  1 d_post = undefined FAILED! expected: one A
Function .proto start0 array immed ref  1 e_post = undefined FAILED! expected: one Epost
Array .proto sparse array          ref  1 a = undefined FAILED! expected: one A
Class .proto sparse array trans    ref  1 b = undefined FAILED! expected: one A
Function .proto sparse array trans ref  1 d_post = undefined FAILED! expected: one A
Function .proto sparse array immed ref  1 e_post = undefined FAILED! expected: one Epost
Function .proto sparse array trans ref 1k d_pre = undefined FAILED! expected: thousand D
Function .proto sparse array immed ref 1k e_pre = undefined FAILED! expected: thousand Epre
Function .proto sparse array immed ref 1k e_post = thousand E FAILED! expected: thousand Epost
Array .proto+self sparse           ref  1 a_s = undefined FAILED! expected: one A
Class .proto+self sparse trans     ref  1 b_s = undefined FAILED! expected: one A


On TR rev 6749 (i.e. current repo tip):

Array .proto start1 array          ref  1 a = undefined FAILED! expected: one A
Class .proto start1 array trans    ref  1 b = undefined FAILED! expected: one A
Function .proto start1 array trans ref  1 d = undefined FAILED! expected: one A
Function .proto start1 array immed ref  1 e = undefined FAILED! expected: one Epost
Array .proto start1 array          ref 10 a = undefined FAILED! expected: ten A
Class .proto start1 array trans    ref 10 b = undefined FAILED! expected: ten A
Function .proto start1 array trans ref 10 d = undefined FAILED! expected: ten A
Function .proto start1 array immed ref 10 e = undefined FAILED! expected: ten Epost
Array .proto start0 array          ref  1 a = undefined FAILED! expected: one A
Class .proto start0 array trans    ref  1 b = undefined FAILED! expected: one A
Function .proto start0 array trans ref  1 d_post = undefined FAILED! expected: one A
Function .proto start0 array immed ref  1 e_post = undefined FAILED! expected: one Epost
Array .proto start0 array          ref 10 a = undefined FAILED! expected: ten A
Class .proto start0 array trans    ref 10 b = undefined FAILED! expected: ten A
Function .proto start0 array trans ref 10 d_post = undefined FAILED! expected: ten A
Function .proto start0 array immed ref 10 e_post = undefined FAILED! expected: ten Epost
Function .proto sparse array trans ref 1k d_pre = undefined FAILED! expected: thousand D
Function .proto sparse array immed ref 1k e_pre = undefined FAILED! expected: thousand Epre
Function .proto sparse array immed ref 1k e_post = thousand E FAILED! expected: thousand Epost




(The thing to note about the above is how crazy different the sets of errors look.  At least to my eye.  I'll try with my patch for the bug later tonight to see how many it helps with, I need to take a break at the moment.)
Attachment #561272 - Attachment is obsolete: true
Created attachment 577674 [details] [diff] [review]
patch P v2: no version checks. no performance tuning.

(rebased patch; no substantial difference from v1)
Attachment #561320 - Attachment is obsolete: true
On TR rev 6749 with patch P v2 applied, test B yields:

Function .proto sparse array trans ref 1k d_pre = undefined FAILED! expected: thousand D
Function .proto sparse array immed ref 1k e_pre = undefined FAILED! expected: thousand Epre
Function .proto sparse array immed ref 1k e_post = thousand E FAILED! expected: thousand Epost

So that's significantly better than where we were in comment 14.

And in fact, reviewing the code for attachment B v2 now, the test for Function .proto sparse array trans ref 1k d_pre is obviously broken, and it seems likely that the same is true for Function .proto sparse array immed ref 1k e_{pre,post}.

So I suspect that after fixing attachment test B, patch P v2 will fix all of the correctly encoded test cases in attachment B v2.
Created attachment 577923 [details] [diff] [review]
test B v3: more thorough testing of all kinds of corners

fixed test
Attachment #577655 - Attachment is obsolete: true
Created attachment 577932 [details] [diff] [review]
test B v4: thorough testing of all kinds of corners

(fixed test, revised presentation/encoding slightly to make grouping clearer via block alignment in source text.)

Executive summary: I'm happy with this set of tests.  They show that Patch P v2 is an improvement on our past.

Still don't want to land until I do one round of performance tests, but at this point the simple array jit work has landed and so I am hoping that performance is not an issue (because real world code should almost never get into this control path in the VM).

More details: With this version, the breakdown is:

TR rev 5711 (i.e. before dense array work landed):

   Arr .proto start0 array       ref  1 a = undefined FAILED! expected: one A
   Cls .proto start0 array trans ref  1 b = undefined FAILED! expected: one A
   Fcn .proto start0 array trans ref  1 d = undefined FAILED! expected: one A
   Fcn .proto start0 array immed ref  1 e = undefined FAILED! expected: one Epost
   Arr .proto sparse array       ref  1 a = undefined FAILED! expected: one A
   Arr .proto+self sparse        ref  1 a = undefined FAILED! expected: one A
   Cls .proto sparse array trans ref  1 b = undefined FAILED! expected: one A
   Cls .proto+self sparse trans  ref  1 b = undefined FAILED! expected: one A
   Fcn .proto sparse array trans ref  1 d = undefined FAILED! expected: one A
   Fcn .proto sparse array immed ref  1 e = undefined FAILED! expected: one Epost
   FAILED passes:101 fails:10 unexpected passes: 0 expected failures: 0

TR rev 6749 (i.e. the repo tip as of yesterday):
   Arr .proto start1 array       ref  1 a = undefined FAILED! expected: one A
   Arr .proto start1 self sparse ref  1 a = undefined FAILED! expected: one A
   Cls .proto start1 array trans ref  1 b = undefined FAILED! expected: one A
   Cls .proto sparse array trans ref  1 b = undefined FAILED! expected: one A
   Fcn .proto start1 array trans ref  1 d = undefined FAILED! expected: one A
   Fcn .proto start1 array immed ref  1 e = undefined FAILED! expected: one Epost
   Arr .proto start1 array       ref 10 a = undefined FAILED! expected: ten A
   Cls .proto start1 array trans ref 10 b = undefined FAILED! expected: ten A
   Cls .proto sparse array trans ref 10 b = undefined FAILED! expected: ten A
   Fcn .proto start1 array trans ref 10 d = undefined FAILED! expected: ten A
   Fcn .proto start1 array immed ref 10 e = undefined FAILED! expected: ten Epost
   Arr .proto start0 array       ref  1 a = undefined FAILED! expected: one A
   Cls .proto start0 array trans ref  1 b = undefined FAILED! expected: one A
   Fcn .proto start0 array trans ref  1 d = undefined FAILED! expected: one A
   Fcn .proto start0 array immed ref  1 e = undefined FAILED! expected: one Epost
   Arr .proto start0 array       ref 10 a = undefined FAILED! expected: ten A
   Cls .proto start0 array trans ref 10 b = undefined FAILED! expected: ten A
   Fcn .proto start0 array trans ref 10 d = undefined FAILED! expected: ten A
   Fcn .proto start0 array immed ref 10 e = undefined FAILED! expected: ten Epost
   FAILED passes:92 fails:19 unexpected passes: 0 expected failures: 0

TR rev 6749 with patch P v2 applied:
   test run PASSED!
Attachment #577923 - Attachment is obsolete: true
Created attachment 578008 [details]
text formatted performance data for patch P v2

Another round of performance data.

I suspect most of the regressions can be disregarded because they are either:
1. In sparse array lookup (where one would expect a performance hit, especially when the key is not present), or

2. In benchmark suites that are known to be noisy junk (e.g. sunspider), or,

3. In untyped variants of code and the regressions are not reflected in the typed variants.
Attachment #564592 - Attachment is obsolete: true
Attachment #564593 - Attachment is obsolete: true
(In reply to Felix S Klock II from comment #19)
> Created attachment 578008 [details]
> text formatted performance data for patch P v2

(p.s. these results were gathered on my iMac (a 2.66 Ghz Intel Core i5) using a 64-bit release avmshell build.)
(Assignee)

Updated

6 years ago
Attachment #577674 - Flags: review?(lhansen)
Comment on attachment 577932 [details] [diff] [review]
test B v4: thorough testing of all kinds of corners

This test case is intended to land after the patch P v2 lands.  (It wouldn't make sense for it to land first since it exposes current buggy behavior.)

brbaker: feel free to hand off to dschaffe, or suggest that I demote the R? to a pending SR? and push.
Attachment #577932 - Flags: review?(brbaker)
Attachment #577932 - Flags: feedback?(lhansen)

Updated

6 years ago
Attachment #577932 - Flags: feedback?(lhansen) → feedback+

Comment 22

6 years ago
Comment on attachment 577674 [details] [diff] [review]
patch P v2: no version checks. no performance tuning.

A nit: the "ignoring proto" part is conventionally abbreviated as "own", eg, "hasOwnAtomProperty", "findOwnProperty".  What you have is perfectly clear so may actually be preferable.
Attachment #577674 - Flags: review?(lhansen) → review+

Comment 23

6 years ago
changeset: 6770:af3e1d66b791
user:      Felix S Klock II <fklockii@adobe.com>
summary:   Bug 687838: include sparse and dense parts during array prototype-chain lookups (r=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/af3e1d66b791
Comment on attachment 577932 [details] [diff] [review]
test B v4: thorough testing of all kinds of corners

(switching to SR for QE and then pushing with a "SR pending" note)
Attachment #577932 - Flags: review?(brbaker) → superreview?(brbaker)
(Assignee)

Updated

6 years ago
Status: NEW → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → FIXED

Comment 25

6 years ago
changeset: 6771:240207231e23
user:      Felix S Klock II <fklockii@adobe.com>
summary:   Bug 687838: test corner cases of array prototype chain lookup (sr pending=brbaker, f=lhansen).

http://hg.mozilla.org/tamarin-redux/rev/240207231e23

Updated

6 years ago
Attachment #577932 - Flags: superreview?(brbaker)
You need to log in before you can comment on or make changes to this bug.