Cleaning up iterator implementation

RESOLVED FIXED

Status

()

Core
JavaScript Engine
--
enhancement
RESOLVED FIXED
11 years ago
11 years ago

People

(Reporter: Igor Bukanov, Assigned: Igor Bukanov)

Tracking

({fixed1.8.1.1})

Trunk
fixed1.8.1.1
Points:
---
Dependency tree / graph
Bug Flags:
blocking1.8.1.1 +
in-testsuite -

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: js1.7)

Attachments

(2 attachments, 10 obsolete attachments)

(Assignee)

Description

11 years ago
[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.
(Assignee)

Updated

11 years ago
Assignee: general → igor.bukanov
(Assignee)

Comment 1

11 years ago
Recording the coming patch dependencies.
Depends on: 355025, 355029
(Assignee)

Comment 2

11 years ago
Created attachment 240822 [details] [diff] [review]
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?
(Assignee)

Comment 3

11 years ago
Created attachment 241125 [details] [diff] [review]
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.
Attachment #240822 - Attachment is obsolete: true
(Assignee)

Comment 4

11 years ago
Created attachment 241136 [details] [diff] [review]
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.
Attachment #241125 - Attachment is obsolete: true
Attachment #241136 - Flags: review?(brendan)
(Assignee)

Comment 5

11 years ago
Created attachment 241164 [details] [diff] [review]
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.
Attachment #241136 - Attachment is obsolete: true
Attachment #241164 - Flags: review?(brendan)
Attachment #241136 - Flags: review?(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
(Assignee)

Comment 7

11 years ago
Created attachment 241189 [details] [diff] [review]
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.
Attachment #241164 - Attachment is obsolete: true
Attachment #241189 - Flags: review?(brendan)
Attachment #241164 - Flags: review?(brendan)
Created attachment 241227 [details] [diff] [review]
Implementation v5

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

/be
Attachment #241189 - Attachment is obsolete: true
Attachment #241227 - Flags: review+
Attachment #241189 - Flags: review?(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
Attachment #241227 - Flags: review?(igor.bukanov)
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
Blocks: 355044
Flags: blocking1.8.1.1?
(Assignee)

Comment 11

11 years ago
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.
Attachment #241227 - Flags: review?(igor.bukanov) → review+
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
Status: NEW → RESOLVED
Last Resolved: 11 years ago
Resolution: --- → FIXED
Created attachment 241260 [details] [diff] [review]
what I just landed
Attachment #241260 - Flags: review+
Attachment #241260 - Flags: approval1.8.1.1?
Comment on attachment 241260 [details] [diff] [review]
what I just landed

Sigh.  Consolidated 1.8 branch patch in a bit.

/be
Attachment #241260 - Attachment is obsolete: true
Attachment #241260 - Flags: review+
Attachment #241260 - Flags: approval1.8.1.1?
Created attachment 241269 [details] [diff] [review]
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
Attachment #241269 - Flags: review?(igor.bukanov)
Attachment #241269 - Flags: approval1.8.1?
Attachment #241269 - Flags: approval1.8.1.1?
(Assignee)

Updated

11 years ago
Attachment #241269 - Flags: review?(igor.bukanov) → review+
Created attachment 241279 [details] [diff] [review]
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
Attachment #241269 - Attachment is obsolete: true
Attachment #241279 - Flags: review+
Attachment #241279 - Flags: approval1.8.1?
Attachment #241279 - Flags: approval1.8.1.1?
Attachment #241269 - Flags: approval1.8.1?
Attachment #241269 - Flags: approval1.8.1.1?

Updated

11 years ago
Flags: in-testsuite-
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
Attachment #241279 - Flags: approval1.8.1? → approval1.8.1-
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
Attachment #241279 - Flags: approval1.8.1.1? → approval1.8.1.1+
Are you saying that there are related bugs that are blocking1.8.1?  If so, please nominate.
dbaron: already nominated.

/be

Updated

11 years ago
Blocks: 355658
Flags: blocking1.8.1.1? → blocking1.8.1.1+
Whiteboard: js1.7
(Assignee)

Comment 21

11 years ago
Recording bug source dependency
Blocks: 355474
(Assignee)

Comment 22

11 years ago
Created attachment 245035 [details] [diff] [review]
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
Attachment #241279 - Attachment is obsolete: true
Attachment #245035 - Flags: approval1.8.1.1?
(Assignee)

Comment 23

11 years ago
Created attachment 245036 [details] [diff] [review]
1.8 branch version + fix from bug 355658 for real

The previous attachment contained the wrong patch.
Attachment #245035 - Attachment is obsolete: true
Attachment #245036 - Flags: approval1.8.1.1?
Attachment #245035 - Flags: approval1.8.1.1?
(Assignee)

Updated

11 years ago
Attachment #241279 - Flags: approval1.8.1.1+

Comment 24

11 years ago
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!
Attachment #245036 - Flags: approval1.8.1.1? → approval1.8.1.1+
(Assignee)

Comment 25

11 years ago
Created attachment 246361 [details] [diff] [review]
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.
Attachment #245036 - Attachment is obsolete: true
Attachment #246361 - Flags: approval1.8.1.1?
(Assignee)

Updated

11 years ago
Attachment #245036 - Flags: approval1.8.1.1+
Comment on attachment 246361 [details] [diff] [review]
Updated 1.8 branch version + fix from bug 355658 for real

carrying over a=jay from yesterday
Attachment #246361 - Flags: approval1.8.1.1? → approval1.8.1.1+
(Assignee)

Comment 27

11 years ago
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

Keywords: fixed1.8.1.1
You need to log in before you can comment on or make changes to this bug.