354982 - Cleaning up iterator implementation

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

[This is a spin-off of the bug 354750, which is security-related. As such I mark this also as security-restricted even if it is an enhancement. Let me know, if this is overkill. ]

Recent evolution of iterator protocol, see bug 354750, made JSContext.cachedIterObj redundant. It should be removed.

In addition it was discovered that the interpreter does not need 2 slots to keep the state of the iterator, as the enumerating iterator knows its original object via parent slot. This should be addressed as well.

Comment 1

[Igor Bukanov]

Recording the coming patch dependencies.

Comment 2

[Igor Bukanov]

Attachment: Implementatib v0

Work in progress with the following changes:

1. cachedIterObj is removed.

2. The enumerating iterator knows how to change the prototype chain on its own without creating an extra iteration objects. To record the original object that started the enumeration it uses JSSLOT_PROTO as the enumerator never escapes to scripts. Thus the interpreter does not need to worry about enumerations simplifying the code there significantly.

3. The code takes advantage of the fact that iterator's methods are read-only and permanent. So for instances of non-enumerating native iterators it calls iter_next directly.

4. For enumerators over XML object the code never enumerates over their prototype chain.

Now with this patch the interpreter does not need to store origobj and obj, but the patch does not change stack allocation in the interpreter as it is not clear what would be the best way to do it. Ideally it would be nice to save both stack slots for obj and origobj but that requires an extra instruction that would call js_ValueToIterator. Right?

Comment 3

[Igor Bukanov]

Attachment: Implementation v1

Work in progress (untested).

Besides the cleanups from the above this also contains the following:

1. Only 2, not 3 slots are used for iterator and its original object. This can be reduced to just one slot if one renames toobject by toiter and call js_ValueToIter there directly. But that requires to change the emitter to prefix toiter with for_each and similar prefixes and I am not sure that it would be allowed on 1.8.1 branch.

2. For the common case of enumerator/native iterator StopIteration is not thrown and the interpreter notified directly by a boolean flag about stopped iteration. That flag can be replaces by passing JSVAL_HOLE as rval from js_CallIteratorNext but it would expose JSVAL_HOLE to GC-reachable location.

3. JS_RVAL2_ITERKEY is removed. As far as I can see that was used to avoid constructing [key, pair] for for-each enumerator but the new code avoids the whole issue throw explicit enumeration code path.

Now I need to test this.

Comment 4

[Igor Bukanov]

Attachment: Implementation v2

This the previous patch with stupid bugs/mistypes removed, which passes some trivial tests and which uses JSVAL_HOLE to indicate to the interpreter that the iterator stopped.

Comment 5

[Igor Bukanov]

Attachment: Implementation v3

Compared with the previous version this patch removes the need for JSOP_TOOBJECT as js_valueToIterator now knows how to deal with null and undefined when enumerating. For compatibility JSOP_TOOBJECT is preserved but it became an empty case in the interpreter switch.

The patch shrinks an optimized build of jsshell compiled with GCC 4.1 -Os for i386 by 1600 bytes.

Comment 6

[Brendan Eich [:brendan]]

Comment on attachment 241164 [details] [diff] [review]
Implementation v3

Couple of quick comments:

* Just rename JSOP_TOOBJECT to JSOP_UNUSED103.

* "Increment" JSXDR_BYTECODE_VERSION in jsxdrapi.h.

* With the above, you can remove the JSOP_TOOBJECT* case from js_Interpret altogether.

/be

Comment 7

[Igor Bukanov]

Attachment: Implementation v4

In this version I removed TO_OBJECT and changed JSOP_FORIN, JSOP_FOREACH JSOP_FOREACHKEYVAL to mean to convert the stack top into iterator. In this way only single stack slot is necessary the code is reduced even more. But it required to update the emitter, which was a simple change to move JSOP_FORIN etc. before the loop jump, and the decompiler, which I do not know how to deal with. So with the patch applied decompilation of any for-in loop asserts.

Comment 8

[Brendan Eich [:brendan]]

Attachment: Implementation v5

I'm plussing Igor's patch, with changes made here.  I'll solicit Igor's second r+ in a second.

/be

Comment 9

[Brendan Eich [:brendan]]

Comment on attachment 241227 [details] [diff] [review]
Implementation v5

I hope bugzilla's interdiff works. Let me know if any of the comment changes are misworded.

/be

Comment 10

[Brendan Eich [:brendan]]

This is a lesson to me and probably others tending Mozilla code: don't be too conservative when modifying.  I left the ancient ediface of the for-in loop code alone, after it had been ECMA-ized with things like JSOP_TOOBJECT seven or so years ago.  Thanks to Igor for cleaning up.

/be

Comment 11

[Igor Bukanov]

Comment on attachment 241227 [details] [diff] [review]
Implementation v5

Even less code! Nice :)

But I should remember to check for *all* instances of the jsop when changing its meaning.

Comment 12

[Brendan Eich [:brendan]]

Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.283; previous revision: 3.282
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.122; previous revision: 3.121
done
Checking in jsemit.c;
/cvsroot/mozilla/js/src/jsemit.c,v  <--  jsemit.c
new revision: 3.221; previous revision: 3.220
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.178; previous revision: 3.177
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.296; previous revision: 3.295
done
Checking in jsiter.c;
/cvsroot/mozilla/js/src/jsiter.c,v  <--  jsiter.c
new revision: 3.47; previous revision: 3.46
done
Checking in jsiter.h;
/cvsroot/mozilla/js/src/jsiter.h,v  <--  jsiter.h
new revision: 3.16; previous revision: 3.15
done
Checking in jsopcode.c;
/cvsroot/mozilla/js/src/jsopcode.c,v  <--  jsopcode.c
new revision: 3.188; previous revision: 3.187
done
Checking in jsopcode.tbl;
/cvsroot/mozilla/js/src/jsopcode.tbl,v  <--  jsopcode.tbl
new revision: 3.80; previous revision: 3.79
done
Checking in jsxdrapi.h;
/cvsroot/mozilla/js/src/jsxdrapi.h,v  <--  jsxdrapi.h
new revision: 1.24; previous revision: 1.23
done

Fixed on trunk.  I made one comment change, in jsiter.c -- I'll attach the patch I landed for posterity and to nominate for 1.8.1.1 (but it may be obsoleted in the near term due to other changes).

/be

Comment 13

[Brendan Eich [:brendan]]

Attachment: what I just landed

Comment 14

[Brendan Eich [:brendan]]

Comment on attachment 241260 [details] [diff] [review]
what I just landed

Sigh.  Consolidated 1.8 branch patch in a bit.

/be

Comment 15

[Brendan Eich [:brendan]]

Attachment: 1.8 branch version of fixes

Asking for igor to r+, since I had to merge and bring over the changes for bug 352846 and bug 355029, as well as bug 347065.

Asking for 1.8.1 approval too, since Igor and I are concerned about fixing this sooner rather than later, given the independent discovery of at least one of the exploitable holes.

/be

Comment 16

[Brendan Eich [:brendan]]

Attachment: 1.8 branch version of fixes

Fixed argo bustage (ISO C leaves #if in macro actual arg undefined, so of course GCC says it's illegal).

/be

Comment 17

[Mike Beltzner [:beltzner, not reading bugmail]]

Comment on attachment 241279 [details] [diff] [review]
1.8 branch version of fixes

We're only doing an RC3 for showstoppers, and since this wasn't nominated for blocking1.8.1, I'm guessing it's not one of those :)

I'd suggest that we take this in 1.8.1.1

Comment 18

[Brendan Eich [:brendan]]

Comment on attachment 241279 [details] [diff] [review]
1.8 branch version of fixes

Then we need a + on 1.8.1.1 and drivers should plus the minimal fix patches in the related bugs.

/be

Comment 19

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Are you saying that there are related bugs that are blocking1.8.1?  If so, please nominate.

Comment 20

[Brendan Eich [:brendan]]

dbaron: already nominated.

/be

Comment 21

[Igor Bukanov]

Recording bug source dependency

Comment 22

[Igor Bukanov]

Attachment: 1.8 branch version + fix from bug 355658

Due to security fixes that was made for 1.8.1 without the clean-up implementation applied (especially due to bug 355474) the patch required heavy update. So to simplify life I also added to the merged patch the fixes from bug  355658 which is approved for 1.8.1.1. 

In this way I knew how to verify the merged work: after the patch applied the only difference between the trunk and 1.8.1 version of jsiter.c should come from bug 359062. And viola, it was indeed so. Due to this property I am very sure about the patch.




  

355474, 355658

Comment 23

[Igor Bukanov]

Attachment: 1.8 branch version + fix from bug 355658 for real

The previous attachment contained the wrong patch.

Comment 24

[Jay Patel [:jay]]

Comment on attachment 245036 [details] [diff] [review]
1.8 branch version + fix from bug 355658 for real

Approved for 1.8.1 branch, a=jay for drivers.  Please land asap and confirm that we have all related patches from dependency bugs.  Thanks!

Comment 25

[Igor Bukanov]

Attachment: Updated 1.8 branch version + fix from bug 355658 for real

Part of changes from the patch was already committed so here is an updated version.

Comment 26

[Mike Connor [:mconnor]]

Comment on attachment 246361 [details] [diff] [review]
Updated 1.8 branch version + fix from bug 355658 for real

carrying over a=jay from yesterday

Comment 27

[Igor Bukanov]

I committed the patch from comment 25 to MOZILLA_1_8_BRANCH:

Checking in jsapi.c;
/cvsroot/mozilla/js/src/jsapi.c,v  <--  jsapi.c
new revision: 3.214.2.29; previous revision: 3.214.2.28
done
Checking in jscntxt.h;
/cvsroot/mozilla/js/src/jscntxt.h,v  <--  jscntxt.h
new revision: 3.80.4.17; previous revision: 3.80.4.16
done
Checking in jsemit.c;
/cvsroot/mozilla/js/src/jsemit.c,v  <--  jsemit.c
new revision: 3.128.2.61; previous revision: 3.128.2.60
done
Checking in jsgc.c;
/cvsroot/mozilla/js/src/jsgc.c,v  <--  jsgc.c
new revision: 3.104.2.26; previous revision: 3.104.2.25
done
Checking in jsinterp.c;
/cvsroot/mozilla/js/src/jsinterp.c,v  <--  jsinterp.c
new revision: 3.181.2.75; previous revision: 3.181.2.74
done
Checking in jsiter.c;
/cvsroot/mozilla/js/src/jsiter.c,v  <--  jsiter.c
new revision: 3.17.2.27; previous revision: 3.17.2.26
done
Checking in jsiter.h;
/cvsroot/mozilla/js/src/jsiter.h,v  <--  jsiter.h
new revision: 3.6.2.10; previous revision: 3.6.2.9
done
Checking in jsopcode.c;
/cvsroot/mozilla/js/src/jsopcode.c,v  <--  jsopcode.c
new revision: 3.89.2.67; previous revision: 3.89.2.66
done
Checking in jsopcode.tbl;
/cvsroot/mozilla/js/src/jsopcode.tbl,v  <--  jsopcode.tbl
new revision: 3.43.2.20; previous revision: 3.43.2.19
done
Checking in jsxdrapi.h;
/cvsroot/mozilla/js/src/jsxdrapi.h,v  <--  jsxdrapi.h
new revision: 1.14.58.10; previous revision: 1.14.58.9
done