354145 - Wrong assumptions about immutable XML

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

Consider the following example:

var xml = <></>
var N = 10;
for (var i = 0; i != N; ++i) {
  xml[i] = <{"a"+i}/>;
}

function prepare()
{
  for (var i = N - 1; i >= 0; --i)
    delete xml[i];
  gc();
  return "test";
}

xml[N - 1] = { toString: prepare };

Currently it crashes the shell since PutProperty in jsxml.c assumes that after ensuring that the insert index is less then the list length, the list length would not change. This is wrong since the code later  convert the passed value to string which can execute arbitrary scrip code that modifies the list.

In the above example the crash happens when accessing NULL pointer, but its modification can be used to reinterpret as XML object arbitrary script-controlled memory.

Comment 1

[Igor Bukanov]

Here is a similar problem with xml_child code:

~/m/trunk/mozilla/js/src> cat ~/m/files/y.js
var list = <></>
var N = 10;
for (var i = 0; i != N; ++i)
  list[i] = <{"a"+i}/>;

function prepare()
{
  for (var i = N - 1; i >= 0; --i)
    delete list[i];
  gc();
  return "test";
}

list.child({ toString: prepare });
~/m/trunk/mozilla/js/src> ./Linux_All_DBG.OBJ/js ~/m/files/y.js
before 9232, after 9232, break 08181000
Segmentation fault

Comment 2

[Igor Bukanov]

xml_contains has the bug:

~/m/trunk/mozilla/js/src> cat ~/m/files/y.js
var list = <></>
var N = 10;
for (var i = 0; i != N; ++i)
  list[i] = <{"a"+i}/>;

function prepare()
{
  for (var i = N - 1; i >= 0; --i)
    delete list[i];
  gc();
  return "test";
}

list.contains({ toString: prepare });
~/m/trunk/mozilla/js/src> ./Linux_All_DBG.OBJ/js ~/m/files/y.js
before 9232, after 9232, break 08141000
Segmentation fault

Comment 3

[Brendan Eich [:brendan]]

Is this a bug in the spec?  I implemented the spec in as brain-off a way as I could stand.  I should have seen this.

Immutability is lovely, even if used only under the hood.  Is there a simple fix, or is the assumption about immutability deeply enough wired that we should try to satisfy it, instead of work around the lack of it?

/be

Comment 4

[Igor Bukanov]

(In reply to comment #3)
> Is this a bug in the spec?  I implemented the spec in as brain-off a way as I
> could stand.  I should have seen this.
> 
> Immutability is lovely, even if used only under the hood.  Is there a simple
> fix, or is the assumption about immutability deeply enough wired that we should
> try to satisfy it, instead of work around the lack of it?
 
A simple fix would be to always throw an exception when converting non-xml-object into string unless it is an instance of String. AFAICS this deviates from E4X but I am in favour of it, as otherwise the amount of code to fix is huge.  

Comment 5

[Igor Bukanov]

The same story with insertChildAfter/Before:

var xml = <tag/>;
var N = 10;
for (var i = 0; i != N; ++i)
  xml.appendChild(<{'a'+i}/>);

function prepare()
{
  delete xml.*;
  gc();
  return "test";
}

var last = xml.*[N - 1];
xml.insertChildAfter(last, { toString: prepare });
~/m/trunk/mozilla/js/src> ./Linux_All_DBG.OBJ/js ~/m/files/y.js
Segmentation fault
var xml = <tag/>;
var N = 10;
for (var i = 0; i != N; ++i)
  xml.appendChild(<{'a'+i}/>);

function prepare()
{
  delete xml.*;
  gc();
  return "test";
}

var last = xml.*[N - 1];
xml.insertChildBefore(last, { toString: prepare });
~/m/trunk/mozilla/js/src> ./Linux_All_DBG.OBJ/js ~/m/files/y.js
Segmentation fault

Comment 6

[Brendan Eich [:brendan]]

(In reply to comment #4)
> (In reply to comment #3)
> > Is this a bug in the spec?  I implemented the spec in as brain-off a way as I
> > could stand.  I should have seen this.

It is a spec bug too: the spec seems to assume that ToString cannot mutate the XML list or object being operated upon.

> > Immutability is lovely, even if used only under the hood.  Is there a simple
> > fix, or is the assumption about immutability deeply enough wired that we should
> > try to satisfy it, instead of work around the lack of it?
> 
> A simple fix would be to always throw an exception when converting
> non-xml-object into string unless it is an instance of String. AFAICS this
> deviates from E4X but I am in favour of it, as otherwise the amount of code to
> fix is huge.  

Another idea is to detect mutation cheaply and restart the operation with the converted parameter or right-hand side.

/be

Comment 7

[Igor Bukanov]

Attachment: Food for thoughts

All but PutProperty bugs happens because the code caches the length value to speedup the loop. So if this optimization is removed, the bug would be mostly fixed. The question is how useful the optimization? 

In most cases where the length caching occurs is used it to optimized loops like in:

        for (i = 0, n = xml->xml_kids.length; i < n; i++) {

Since the loop body is complex code in such cases, the optimization can not speedup things in any visible matter. So what about code size? To check this, I created this patch which replaces in all the places accessing cached value by direct member queries. The result was rather interesting. 

An optimized build of the shell with the default -O flag did not change the size of jsxml.o compiled with GCC 4.1 for i386 Linux from its 56604 bytes. When I compiled with -Os with the patch applied jsxml.o dropped from 49180 to 48796 bytes, a saving of 0.8%. When I compiled with -O2 size also dropped from 59964 to 59900, a saving about 0.1%.

Thus AFAICS the optimization in fact harmful. What happens is that the compiler  , besides generating the code to access length, also has to generate an extra code to save/restore the cached value in the register across function calls.  

So in fact this patch can be commited under a separated bug like shrinking jsxml.o size and nobody would notice that it also fixes xml_child problem.

Comment 8

[Brendan Eich [:brendan]]

Comment on attachment 241326 [details] [diff] [review]
Food for thoughts

>@@ -3253,25 +3252,24 @@ DeepCopy(JSContext *cx, JSXML *xml, JSOb
>  * (ii) parent must have a rooted object.
>  * (iii) from's owning object must be locked if not thread-local.
>  */
> static JSBool
> DeepCopySetInLRS(JSContext *cx, JSXMLArray *from, JSXMLArray *to, JSXML *parent,
>                  uintN flags)
> {
>-    uint32 i, j, n;
>+    uint32 i, j;
>     JSXML *kid, *kid2;
>     JSString *str;
> 
>     JS_ASSERT(cx->localRootStack);
> 
>-    n = from->length;
>-    if (!XMLArraySetCapacity(cx, to, n))
>+    if (!XMLArraySetCapacity(cx, to, from->length))
>         return JS_FALSE;
> 
>-    for (i = j = 0; i < n; i++) {
>+    for (i = j = 0; i < from->length; i++) {

This is ok if it saves code size on x86, but just for this particular case there should never be a mutation to the from array when copying -- right?

>@@ -4301,15 +4297,15 @@ PutProperty(JSContext *cx, JSObject *obj
>                      * y.[[Parent]] is here called kid->parent, which we know
>                      * from 2(c)(ii) is _r_, here called rxml.  So let's just
>                      * test that!  Erratum, the spec should be simpler here.
>                      */
>                     if (rxml) {
>                         JS_ASSERT(JSXML_HAS_KIDS(rxml));
>                         n = rxml->xml_kids.length;
>-                        j = n - 1;
>+                        j = rxml->xml_kids.length - 1;

This seems like a gratuitous change -- there's no mutation hazard, and n is a common subexpression above and just below:

>                         if (n != 0 && i != 0) {
>                             for (n = j, j = 0; j < n; j++) {
>                                 if (rxml->xml_kids.vector[j] ==
>                                     xml->xml_kids.vector[i-1]) {
>                                     break;
>                                 }
>                             }

>@@ -5233,15 +5228,15 @@ again:
>             kid = XMLARRAY_MEMBER(&xml->xml_kids, 0, JSXML);
>             xml = kid;
>             goto again;
>         }
>         /* FALL THROUGH */
>       default:
>         simple = JS_TRUE;
>-        for (i = 0, n = JSXML_LENGTH(xml); i < n; i++) {
>+        for (i = 0; i < JSXML_LENGTH(xml); i++) {
>             kid = XMLARRAY_MEMBER(&xml->xml_kids, i, JSXML);
>             if (kid->xml_class == JSXML_CLASS_ELEMENT) {
>                 simple = JS_FALSE;
>                 break;
>             }
>         }
>         return simple;

This is also a safe commoning; not sure it hurts code size but there's no mutation hazard.

> static JSBool
> xml_childIndex(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
>                jsval *rval)
> {
>     JSXML *xml, *parent;
>-    uint32 i, n;
>+    uint32 i;
> 
>     XML_METHOD_PROLOG;
>     parent = xml->parent;
>     if (!parent || xml->xml_class == JSXML_CLASS_ATTRIBUTE) {
>         *rval = DOUBLE_TO_JSVAL(cx->runtime->jsNaN);
>         return JS_TRUE;
>     }
>-    for (i = 0, n = JSXML_LENGTH(parent); i < n; i++) {
>+    for (i = 0; i < JSXML_LENGTH(parent); i++) {
>         if (XMLARRAY_MEMBER(&parent->xml_kids, i, JSXML) == xml)
>             break;
>     }
>-    JS_ASSERT(i < n);
>+    JS_ASSERT(i < JSXML_LENGTH(parent));

Again the existing code is safe and perhaps even yields better code.  It's not even clearly a source code with to undo the commoning to n, given the brevity of n vs. JSXML_LENGTH(parent).

I'm obviously a RISC fan who expects lots of registers, and I common too much with explicit locals, but the old code seemed better here.

>@@ -6010,15 +6005,15 @@ again:
>             obj = kidobj;
>             xml = (JSXML *) JS_GetPrivate(cx, obj);
>             goto again;
>         }
>         /* FALL THROUGH */
>       default:
>         *rval = JSVAL_FALSE;
>-        for (i = 0, n = xml->xml_kids.length; i < n; i++) {
>+        for (i = 0; i < xml->xml_kids.length; i++) {
>             kid = XMLARRAY_MEMBER(&xml->xml_kids, i, JSXML);
>             if (kid->xml_class == JSXML_CLASS_ELEMENT) {
>                 *rval = JSVAL_TRUE;
>                 break;
>             }
>         }
>         break;

Another simple case with no calls out of the loop body and no direct mutation.

> /* XML and XMLList */
> static JSBool
> xml_parent(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
> {
>     JSXML *xml, *parent, *kid;
>-    uint32 i, n;
>+    uint32 i;
>     JSObject *parentobj;
> 
>     XML_METHOD_PROLOG;
>     parent = xml->parent;
>     if (xml->xml_class == JSXML_CLASS_LIST) {
>         *rval = JSVAL_VOID;
>-        n = xml->xml_kids.length;
>-        if (n == 0)
>+        if (xml->xml_kids.length == 0)
>             return JS_TRUE;
> 
>         kid = XMLARRAY_MEMBER(&xml->xml_kids, 0, JSXML);
>         parent = kid->parent;
>-        for (i = 1; i < n; i++) {
>+        for (i = 1; i < xml->xml_kids.length; i++) {
>             kid = XMLARRAY_MEMBER(&xml->xml_kids, i, JSXML);
>             if (kid->parent != parent)
>                 return JS_TRUE;
>         }
>     }
> 
>     if (!parent) {

Another simple case.

I'm curious if reverting the changes for simple cases worsens code size.  Also curious about what MSVC++ does with and without the patch.

Filing a separate "cover" cleanup bug sounds like a good idea.

/be

Comment 9

[Igor Bukanov]

Attachment: Fix via explicit abort

The patch just calls abort for out-of-bounds access. Yes, this would crash a browser, but it would be a controllable crash until a better remedy would be found. 

An alternative is to do nothing in XMLArraySetMember and return other array element in XMLArrayMember, but then to return something for the empty array cx has to be passed to the macro.

Comment 10

[Brendan Eich [:brendan]]

(In reply to comment #9)
> An alternative is to do nothing in XMLArraySetMember and return other array
> element in XMLArrayMember, but then to return something for the empty array cx
> has to be passed to the macro.

I'm totally ok with using cx from the macro call's lexical environment.  That seems better than naked abort calls, and easy enough.

/be

Comment 11

[Igor Bukanov]

Attachment: Fix v2

This a version of the patch that does nothing on set and return null on get. The good side of this patch is that after having it in CVS it would be safe to explicit null checks in broken places, exposing them would do no harm with the explicit protection.

Comment 12

[Igor Bukanov]

Another observation. If the simple loops with cached length would be turned into non-cached version a good compiler should be able to figure out that the bounds checks are not reachable.

Comment 13

[Igor Bukanov]

I filed a cover bug 355611 for optimizing jsxml.c for size.

Comment 14

[Brendan Eich [:brendan]]

Comment on attachment 241378 [details] [diff] [review]
Fix v2


>+static void
>+XMLArraySetMember(JSXMLArray *array, uint32 index, void *elt)
>+{
>+    if (index >= array->length) {
>+        if (JS_UNLIKELY(index >= JSXML_CAPACITY(array)))
>+            return;
>+        array->length = index + 1;
>+    }
>+    array->vector = elt;

Typo for sure: array->vector[index] = elt;

r+ with that fixed.

/be

Comment 15

[Igor Bukanov]

Attachment: Fix v3

Patch to commit with stupid typo fixed

Comment 16

[Igor Bukanov]

Comment on attachment 241386 [details] [diff] [review]
Fix v3

I am stupid! I should not touch orphaned child!

Comment 17

[Igor Bukanov]

Attachment: Fix v4

The proper patch. Asking for r one more time just to be sure.

Comment 18

[Igor Bukanov]

I think I spend too much time on this. The patch only forces the cases from comment 5 and 2, the cases from comment 0 and comment 1 are still exploitable through GC. There the problem is that temporary XML is stored on the stack and is killed from the script. 

At this point I really suggest to define something like SafeToString that would throw an exception when the target is an object and not String/XML. 

Comment 19

[Igor Bukanov]

Attachment: Fix v5 via SafeToString

[This is untested but sufficient to address all the examples]

The patch adds SafeToString which never execute any scripted code and should work for most useful cases with throwing exception when necessary.

The patch also uses explicit local roots in many places where they are not strictly necessary.

Now after playing for sometime with this I think there is a better solution based on the following observation. XML code eventually converts the majority of passed jsval to string if they are not primitive values or XML, QName, Namespace  objects. Thus the idea to convert such jsval ASAP and then replace various js_valueToString by a helper method that does string conversation assuming that the value is sanitized.

I will try to see how much work that would require.

Comment 20

[Igor Bukanov]

Attachment: Fix v6 via value sanitation

Work in progress that allows to resolve all the reported problems.

This adds SanitizeValue/ConvertToString pair that allows to convert objects to string earlier. The critical part is to call ConvertToString in places that navigates XML structures. The function asserts in the debug builds if the value a generic object but in optimized build it returns empty string. 

Then to support a generic value SanitizeValue should be called ASAP in the places that receives an arbitrary jsval. I will test/review the patch few more times.

Comment 21

[Brendan Eich [:brendan]]

Comment on attachment 241514 [details] [diff] [review]
Fix v6 via value sanitation

>Index: jsxml.c
>===================================================================
>RCS file: /cvsroot/mozilla/js/src/jsxml.c,v
>retrieving revision 3.130
>diff -U7 -p -r3.130 jsxml.c
>--- jsxml.c	5 Oct 2006 20:35:29 -0000	3.130
>+++ jsxml.c	7 Oct 2006 01:26:24 -0000
>@@ -129,17 +129,128 @@ const char js_gt_entity_str[]     = "&gt
> const char js_lt_entity_str[]     = "<";
> const char js_quot_entity_str[]   = """;
> 
> #define IS_EMPTY(str) (JSSTRING_LENGTH(str) == 0)
> #define IS_STAR(str)  (JSSTRING_LENGTH(str) == 1 && *JSSTRING_CHARS(str) == '*')
> 
> static JSBool
>+js_IsXMLName(JSContext *cx, jsval v);

Any reason to make this static in this patch?  Minimize, also leave it in case the DOM<=>E4X hookup needs it (why I exposed it).

>+    if (!JSVAL_IS_PRIMITIVE(*vp)) {
>+        obj = JSVAL_TO_OBJECT(*vp);
>+        if (OBJECT_IS_XML(cx, obj)) {
>+            JSXML *xml;
>+
>+            xml = (JSXML *) JS_GetPrivate(cx, obj);
>+            str = xml_toString_helper(cx, xml);
>+            goto string_result;
>+        }

else {...} here to avoid goto string_result?

>+
>+        clasp = OBJ_GET_CLASS(cx, obj);
>+        if (clasp == &js_NamespaceClass.base) {
>+            JSXMLNamespace *ns;
>+
>+            ns = (JSXMLNamespace *) JS_GetPrivate(cx, obj);
>+            *vp = STRING_TO_JSVAL(ns->uri);
>+            return JS_TRUE;
>+        } else

else after return non-sequitur.

>+        if (clasp == &js_QNameClass.base ||
>+                   clasp == &js_AttributeNameClass ||
>+                   clasp == &js_AnyNameClass) {
>+            JSXMLQName *qn;
>+
>+            qn = (JSXMLQName *) JS_GetPrivate(cx, obj);
>+            JS_PUSH_TEMP_ROOT_OBJECT(cx, obj, &tvr);
>+            ok = QNameToString(cx, clasp, qn, vp);
>+            JS_POP_TEMP_ROOT(cx, &tvr);
>+            return ok;
>+        } else

Ditto.

>+            JS_NOT_REACHED("Not a result of SanitizeValue");
>+            str = cx->runtime->emptyString;
>+            goto string_result;
>+        }

This end brace goes away, leaving the goto string_result easily replaced by else around this:

>+    }
>+    JS_ASSERT(JSVAL_IS_PRIMITIVE(*vp));
>+    str = js_ValueToString(cx, *vp);
>+
>+  string_result:
>+    if (!str)
>+        return JS_FALSE;
>+    *vp = STRING_TO_JSVAL(str);
>+    return JS_TRUE;
>+}

[. . .]

>+  eq_list:

Use a tail call to a helper to avoid this goto?  Wonder if that would even save code size.

/be

Comment 22

[Igor Bukanov]

Attachment: Fix v7

I think I covered all suspicious paths and added over-paranoid JSTempValueRoot litter in the places where apparently reliance on newborn is enough. But I want to play it save especially after ToXML that does not wrap ParseXMLSource into Enter/LeaveLocalRootScope while ToXMLList does that.

Comment 23

[Igor Bukanov]

Note that v7 does not address the comment 21.

Comment 24

[Igor Bukanov]

(In reply to comment #21)
> > static JSBool
> >+js_IsXMLName(JSContext *cx, jsval v);
> 
> Any reason to make this static in this patch?  Minimize, also leave it in case
> the DOM<=>E4X hookup needs it (why I exposed it).

It uses ConvertToString which requires the caller to call SanitizeValue. If exposure is important, then js_IsXMLName(JSContext *cx, jsval v) can be split in 2 functions with the nested one calling SanitizeValue. 

Comment 25

[Igor Bukanov]

One more thing about the previous attachment. It changes ToXMLName to use
ConvertToString to ensure that String instances with overwritten
String.prototype.toString still uses the default ToString conversion. But that
required that SanitizeValue skips string converssion for Number, Boolean and
String object instances.

Comment 26

[Igor Bukanov]

Here is another source of worries. If some object creation hook can trigger a full GC, then a close hook from a generator can do exactly the damage that the examples demonstrates. I really thinking of delegating running close hooks to the embedding. 

Comment 27

[Igor Bukanov]

Attachment: Fix v8

This version mostly simplifies Equals implementation and changes xml_toString_helper to use passed root instead of EnterLocalRoots.

I still do not ask for a review as I have to do it myself first.

Comment 28

[Igor Bukanov]

Attachment: Fix v8 for real

I attached the older file

Comment 29

[Igor Bukanov]

Attachment: Fix v9

Fixing bug in ToXMLList and using ok in ToXML and ToXMLList for consistency.

Comment 30

[Igor Bukanov]

Attachment: Fix v10

Here xml_replace calls SanitizeValue for both arguments ASAP not to worry about effects of executing arbitrary script on CHECK_COPY_ON_WRITE. This is AFAICS groundless, but I want to be 100% sure.

Comment 31

[Igor Bukanov]

The patch causes a single regression among e4x tests in e4x/GC/regress-313952-02.js for bug 313952 which is in fact expected since the test contains:

var str = String(1);
var expected = String(1);

var x = new XML("text");
x.function::toString = function() {
        var tmp = str; str = null; return tmp;
}

...
var likeString = { toString: function() { bug-related-stuff; return expected }};

var test = (x == likeString);

After the patch x.function::toString is no longer called for XML objects so the test fails.

I think this is an acceptable price to pay for GC-safty.

Comment 32

[Igor Bukanov]

Here is another problem not covered by the patch in js_FilterXMLList. It contains:

    for (i = 0, n = list->xml_kids.length; i < n; i++) {
        kid = XMLARRAY_MEMBER(&list->xml_kids, i, JSXML);
        kidobj = js_GetXMLObject(cx, kid);
        if (!kidobj)
            goto bad;
        OBJ_SET_PROTO(cx, withobj, kidobj);
        ok = js_Interpret(cx, pc, vp) && js_ValueToBoolean(cx, *vp, &match);

Since here list is the original passed object when it is itself a list, so this just asks for troubles.

Comment 33

[Brendan Eich [:brendan]]

I'm wondering whether we can't take a different approach based on cursors, either snapshotting the array in a copy-on-write fashion, or locking it against mutation. If we make the XMLArray layer handle this problem, the higher layers may not need so much changing -- just the loops.

/be

Comment 34

[Igor Bukanov]

Here is a test case that exposes the hazard with the filter via segfault:

var list = <><a/><b/></>

function a() {
   delete list[1];
   delete list[0];
   gc();
   for (var i = 0; i != 50000; ++i) 
     var tmp = ""+i;     
  return true;
}

var list2 = list.(a());

print(uneval(list2))

Note that gc() here is used to shrink spare list capacity that becomes available after the removal of elements. It is also interesting to note that since js_ValueToBoolean does not do any valueOf calls, the bug can not be exposed using a specially crafted like_boolean object. 

But on 1.8.0 branch the situation id different AFAICS. There if a script can set a version to 1.2, then js_ValueToBoolean calls valueOf on the result. Now that can not only change the list, but also unroot kidobj via changing the prototype of with. So to make this as safe as possible I will explicitly root kidobj in the patch.  

Comment 35

[Igor Bukanov]

(In reply to comment #33)
> I'm wondering whether we can't take a different approach based on cursors,
> either snapshotting the array in a copy-on-write fashion, or locking it against
> mutation. If we make the XMLArray layer handle this problem, the higher layers
> may not need so much changing -- just the loops.

But how would you deal with Insert/PutProperty? It requires changing the arrays! 

Comment 36

[Igor Bukanov]

Attachment: Fix v11

This is just an extension of v9 to cover XML filtering.

Comment 37

[Igor Bukanov]

Note about GC hazard with js_FilterXMLList. It does not require any specially crafted like_boolean objects and JS 1.2 as long as a script can reach via __parent__ property the scope containing kidobj. If this is possible, then the script can replace the value of __proto__ and unroot kidobj.

On the other hand  I was not able to get hold on that with using __parent__, it seems with(xml) behaves differently then with({}).

In case, the patch v11 does contain explicit GC rooting for kidobj. 

Comment 38

[Brendan Eich [:brendan]]

Attachment: alternative approach based on cursors

This does not include any of the specific GC safety fixes you've made in your good work on the patches before it, but it does mark cursor's current items, so e.g. it protects js_FilterXMLList without extra code beyond the switch from for (i = 0...) to a cursor while loop.

XMLARRAY_MEMBER is nullable and so all callers must check and do something sane to avoid a null dereference crash.  I hope I changed all the callers correctly.

/be

Comment 39

[Brendan Eich [:brendan]]

(In reply to comment #35)
> (In reply to comment #33)
> > I'm wondering whether we can't take a different approach based on cursors,
> > either snapshotting the array in a copy-on-write fashion, or locking it against
> > mutation. If we make the XMLArray layer handle this problem, the higher layers
> > may not need so much changing -- just the loops.
> 
> But how would you deal with Insert/PutProperty? It requires changing the
> arrays! 

Yes, that's the problem with immutability in an implementation of a spec with mutation.  Instead of trying to solve that conundrum, the patch I just attached uses the existing cursor mechanism to avoid indexing deleted items in arrays, and it also roots the last cursor'ed item.  Sorry I didn't suggest this sooner.  Is it enough for memory safety in the face of mutation?

/be

Comment 40

[Brendan Eich [:brendan]]

Attachment: alternative approach, minimized

ParseNodeTo* functions do not need to worry about null from XMLARRAY_MEMBER, and xml_enumerateValues should skip any null kids, not terminate the enumeration on the first null kid.

/be

Comment 41

[Brendan Eich [:brendan]]

Attachment: alternative approach, minimized correctly

Argh, --n in XMLARRAY_MEMBER actual parameter came back from the dead via patch -R blind usage.  Interdiff shows all.

/be

Comment 42

[Brendan Eich [:brendan]]

Attachment: alternative approach, with GC safety in PutProperty

Thanks to Igor for pointing out a few problems that this patch fixes.  What is left to fix here?  I'll have to take a fresh look on Monday.  Comments welcome.

/be

Comment 43

[Brendan Eich [:brendan]]

Attachment: alternative approach, fix late night glitch

Comment 44

[Igor Bukanov]

With the patch I was not able to find any more GC bugs. In principle I would prefer a patch that uses a version of cursor that roots the current element via tvr rooter without the assumption that the parent is rooted , as it decreses the number of of cases to consider, but even in the current form its reflect the spirit of E4X through cursor loops, not explicit element loops.  

AFAICS the only problematic behavior left is that Insert sets the element to NULL before inserting it. Thus if replace fails (perhaps due to exception throws during ValueToString ;) , null kid would remain in the array leading to null-pointer derefs later or infinite for-each loop in enumerate as the following example demonstrates:

var a = <a><b/></a>
try {
  a.insertChildAfter(a.b[0], {toString: function() { throw 1; }});
} catch (e) { }

for each (var i in a) { }

But my patch has not fixed it either and it can go to a separated bug.

Still before giving r=+ I check few more times.

Comment 45

[Brendan Eich [:brendan]]

Attachment: alternative approach, with iloop fix

That xml_enumerateValues iloop was just a late-night glitch -- easy to fix.

There should not be null dereferences now that all the XMLARRAY_MEMBER uses except those under ParseNodeTo{QName,XML} do null checks.

/be

Comment 46

[Brendan Eich [:brendan]]

Attachment: alternative approach, minimal iloop fix

Comment 47

[Brendan Eich [:brendan]]

The null defense needed in most calls to XMLARRAY_MEMBER to cope with both failed Insert (due to exception under toString) and any mutations that leave the length shorter than the index is usually written so as to continue for (i=0...) loops -- but XMLArrayCursorNext loops will break on the first null embedded in an array due to throw from toString.

If the nulls can only be embedded at the end, this is ok.  But it's inconsistent and perhaps incorrect.  Igor, what do you think?  XMLArrayCursorNext could skip null items (and then xml_enumerate* should use XMLArrayCursorNext instead of the pre-existing inline equivalents).

/be

Comment 48

[Brendan Eich [:brendan]]

(In reply to comment #47)
> If the nulls can only be embedded at the end, this is ok.

But if so, then for(i=0...) loops should break on the first null item.

/be

Comment 49

[Igor Bukanov]

Attachment: alternative approach + insert fix

The solution for Insert problem is simple: just inline Replace code and move value-to-string-to-text conversion before the insertion begins which allows not to worry about insert injecting nulls at all.

The patch also changes Insert to accept insert index as uint32 directly as it is always used with integer ids. 

I hope the interdiff would tell the story in details.

Comment 50

[Igor Bukanov]

Attachment: alternative approach + always insert fix

The previous patch ignores insert if value-to-string-to-xml removes elements so the index is out of bounds. I think it is better to always insert so the new version resets i when necessary.

Comment 51

[Brendan Eich [:brendan]]

Comment on attachment 241647 [details] [diff] [review]
alternative approach + always insert fix

Great, land it on the trunk and we can get it into the 1.8 branch for rc3 tomorrow (Bob, Jeff, anyone else who can, please pound on E4X).

/be

Comment 52

[Igor Bukanov]

Comment on attachment 241626 [details] [diff] [review]
alternative approach, minimal iloop fix

I give r=+ based on the observation that the patch solves all the discovered problems with jsxml.c and looking through the changes I do not see anything suspicious. On the other hand after starring at jsxml.c for few days chances that I would notes the problem with the way patch is coded is 0. So it would be nice if somebody fresh just look at it.   





After starring into jsxml.c  for few days I ca

Comment 53

[Brendan Eich [:brendan]]

(In reply to comment #52)
> (From update of attachment 241626 [details] [diff] [review] [edit])
> On the other hand after starring at jsxml.c for few days chances
> that I would notes the problem with the way patch is coded is 0. So it would
> be nice if somebody fresh just look at it.

Jeff Walden, you are that man! :-P

I'm happier with the code now, finally.  Onward to thread safety!

/be

Comment 54

[Brendan Eich [:brendan]]

Comment on attachment 241626 [details] [diff] [review]
alternative approach, minimal iloop fix

Leaving r+ for posterity but marking obsolete by Igor's patch based on this one, with Insert fixed not to leave null item on exception from ToString.

/be

Comment 55

[Igor Bukanov]

I committed the patch from comment 50 (: nice number :) to the trunk:

Checking in jsxml.c;
/cvsroot/mozilla/js/src/jsxml.c,v  <--  jsxml.c
new revision: 3.131; previous revision: 3.130
done
Checking in jsxml.h;
/cvsroot/mozilla/js/src/jsxml.h,v  <--  jsxml.h
new revision: 3.15; previous revision: 3.14
done

Comment 56

[Igor Bukanov]

The patch does not applies to 1.8.1 branch as the branch lacks patches from bug  354151 and bug 355474.

Comment 57

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

Blocking for Fx2 RC3

Comment 58

[Igor Bukanov]

I record strong dependency of the committed patch to the trunk on the patch from bug 354151 that show the same scale of threat as this bug but the patch there is not yet approved for 1.8.1.

Comment 59

[Igor Bukanov]

If I apply the patches from bug 353165 and bug 354151 and remove junk trailing whitespace in xml_namespace(), then the patch applies cleanly to 1.8.1 branch.

Comment 60

[Bob Clary [:bc] (inactive)]

Attachment: e4x/Regress/regress-354145-01.js

Comment 61

[Bob Clary [:bc] (inactive)]

Attachment: e4x/Regress/regress-354145-02.js

Comment 62

[Bob Clary [:bc] (inactive)]

Attachment: e4x/Regress/regress-354145-03.js

Comment 63

[Bob Clary [:bc] (inactive)]

Attachment: e4x/Regress/regress-354145-04.js

Comment 64

[Bob Clary [:bc] (inactive)]

Attachment: e4x/Regress/regress-354145-05.js

Comment 65

[Bob Clary [:bc] (inactive)]

Attachment: e4x/Regress/regress-354145-06.js

Comment 66

[Bob Clary [:bc] (inactive)]

Attachment: e4x/Regress/regress-354145-07.js

Comment 67

[Bob Clary [:bc] (inactive)]

verified fixed 1.9 20061009 windows/linux

Comment 68

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

Comment on attachment 241647 [details] [diff] [review]
alternative approach + always insert fix

a=beltzner on behalf of drivers for 1.8.1 branch RC 3

Comment 69

[Igor Bukanov]

I committed the patch from comment 50 to MOZILLA_1_8_BRANCH:

Checking in jsxml.c;
/cvsroot/mozilla/js/src/jsxml.c,v  <--  jsxml.c
new revision: 3.50.2.52; previous revision: 3.50.2.51
done
Checking in jsxml.h;
/cvsroot/mozilla/js/src/jsxml.h,v  <--  jsxml.h
new revision: 3.10.4.4; previous revision: 3.10.4.3
done

Note that before applying the patch I have to remove junk whitespace at line 6323. After that the patch applied as is and jsxml.c became the same as it is on the trunk, which is expected.

Comment 70

[Igor Bukanov]

The branch 1.8.0 requires own patch as does not have js_EqualStrings.

Comment 71

[Igor Bukanov]

For the record: after the patch xml_child_helper may set rval to JSVAL_NULL, but xml_child does not check for this. This could be non-bug since the current code may never set a member to null AFAICS. Still for the future this has to be dealt somehow. 

Comment 72

[Igor Bukanov]

Attachment: alternative approach + always insert fix for 1.8.0 branch

This is a backport to 1.8.0 branch. I will do some quick checks before asking for approval etc.

Comment 73

[Igor Bukanov]

Attachment: alternative approach + always insert fix for 1.8.0 branch

The prev patch missed POP_TEMP_ROOT in PutProperty.

Comment 74

[Igor Bukanov]

Attachment: diff between trunk and 1.8.0 patches

Few comments: the biggest deviations between trunk and 1.8.0 comes from XMLToXMLString and js_MarkXML. In the former case the oder of applying steps 17(c) and 17(b) are different and in the latter case xml_mark_tail is inlined on the trunk. So this has to be checked in the patch itself.

In the rest of cases this diff is pretty effective for patch checking.

Comment 75

[Brendan Eich [:brendan]]

Comment on attachment 241900 [details] [diff] [review]
alternative approach + always insert fix for 1.8.0 branch

Looks correct -- thanks.

/be

Comment 76

[Brendan Eich [:brendan]]

(In reply to comment #71)
> For the record: after the patch xml_child_helper may set rval to JSVAL_NULL,
> but xml_child does not check for this. This could be non-bug since the current
> code may never set a member to null AFAICS. Still for the future this has to be
> dealt somehow. 

File a new bug?

/be

Comment 77

[Bob Clary [:bc] (inactive)]

verified fixed 1.8 20061010 windows/mac*/linux

Comment 78

[Igor Bukanov]

Attachment: alternative approach + always insert fix for 1.8.0 branch v3

In the previous patch I forgot to remove in XMLToXMLString the assignment to kid at line 2683. With this patch e4x tests show the same list of regressions with the same output as was before the patch.

Comment 79

[Brendan Eich [:brendan]]

Comment on attachment 241934 [details] [diff] [review]
alternative approach + always insert fix for 1.8.0 branch v3

I should have seen that in the plain diff of patches:

433c433
< -            kid = XMLARRAY_MEMBER(&xml->xml_kids, i, JSXML);
---
>              kid = XMLARRAY_MEMBER(&xml->xml_kids, i, JSXML);

/be

Comment 80

[Daniel Veditz [:dveditz]]

Comment on attachment 241934 [details] [diff] [review]
alternative approach + always insert fix for 1.8.0 branch v3

approved for 1.8.0 branch, a=dveditz for drivers

Comment 81

[Igor Bukanov]

I committed the patch from comment 78 to MOZILLA_1_8_0_BRANCH:

Checking in jsxml.c;
/cvsroot/mozilla/js/src/jsxml.c,v  <--  jsxml.c
new revision: 3.50.2.15.2.22; previous revision: 3.50.2.15.2.21
done
Checking in jsxml.h;
/cvsroot/mozilla/js/src/jsxml.h,v  <--  jsxml.h
new revision: 3.10.4.1.2.1; previous revision: 3.10.4.1
done

Comment 82

[Jeff Walden [:Waldo]]

Comment on attachment 241647 [details] [diff] [review]
alternative approach + always insert fix

Sorry for the delay, but I've been pretty busy lately, and looking through this took a while.

As a general note, I'm slightly confused about the null-checking strategy here.  Most places null-check, a very few don't, and it's not really obvious to me how the distinction was made.  In some cases proving that the null-check is unnecessary requires reading up a few screens and thus is reasonable from a maintenance standpoint, but in other cases it seems more obvious but is still done.


>@@ -1384,15 +1417,16 @@ ParseNodeToQName(JSContext *cx, JSParseN
>             while (n != 0) {
>-                ns = XMLARRAY_MEMBER(inScopeNSes, --n, JSXMLNamespace);
>+                --n;
>+                ns = XMLARRAY_MEMBER(inScopeNSes, n, JSXMLNamespace);
>                 if (ns->prefix && js_EqualStrings(ns->prefix, prefix)) {

Irrelevant aside: this is because macro arguments can be evaluated multiple times, correct?


>@@ -1418,15 +1452,16 @@ ParseNodeToQName(JSContext *cx, JSParseN
>             n = inScopeNSes->length;
>             while (n != 0) {
>-                ns = XMLARRAY_MEMBER(inScopeNSes, --n, JSXMLNamespace);
>+                --n;
>+                ns = XMLARRAY_MEMBER(inScopeNSes, n, JSXMLNamespace);
>                 if (!ns->prefix || IS_EMPTY(ns->prefix)) {
>                     uri = ns->uri;
>                     break;
>                 }

No null-check of ns here, and at least from my readthrough it doesn't look easy (if it's even possible) to prove that inScopeNSes won't contain a null.


>     for (i = 0, n = decls.length; i < n; i++) {
>         ns2 = XMLARRAY_MEMBER(&decls, i, JSXMLNamespace);
>+        if (!ns2)
>+            continue;
>         JS_ASSERT(!XMLARRAY_HAS_MEMBER(&ancdecls, ns2, namespace_identity));
>         if (!XMLARRAY_APPEND(cx, &ancdecls, ns2))
>             goto out;
>     }

This null-check isn't necessary, as can easily be proven from the preceding code, although it requires a few screens of reading to verify and thus is probably reasonable.


>@@ -3227,26 +3290,30 @@ DeepCopy(JSContext *cx, JSXML *xml, JSOb

>-    for (i = j = 0; i < n; i++) {
>-        kid = XMLARRAY_MEMBER(from, i, JSXML);
>+    XMLArrayCursorInit(&cursor, from);
>+    j = 0;
>+    ok = JS_TRUE;
>+    while ((kid = (JSXML *) XMLArrayCursorNext(&cursor)) != NULL) {
>         if ((flags & XSF_IGNORE_COMMENTS) &&
>             kid->xml_class == JSXML_CLASS_COMMENT) {
>             continue;
>         }
...

What's the reason for the |ok| temp variable here?  Why not use break/if (kid) since that's what's used everywhere else?


>    } else {
>        xvec = (JSXML **) xml->xml_kids.vector;
>        vvec = (JSXML **) vxml->xml_kids.vector;
>        for (i = 0; i < n; i++) {
>            xobj = js_GetXMLObject(cx, xvec[i]);
>            vobj = js_GetXMLObject(cx, vvec[i]);
>            if (!xobj || !vobj)
>                return JS_FALSE;
>            if (!js_XMLObjectOps.equality(cx, xobj, OBJECT_TO_JSVAL(vobj), bp))
>                return JS_FALSE;
>            if (!*bp)
>                break;
>        }

This clearly isn't going to handle holes in xml->xml_kids very well -- looks like js_GetXMLObject would crash trying to dereference (x|v)vec[i].  (Note: this was inside XMLEquals but not in the patch's context.)


>     * [[Replace]] handles _i >= x.[[Length]]_ by incrementing _x.[[Length]_.

This isn't part of patch, but this line's missing a "]" at the end.  Could someone with the time to do so fix this?


The namespace_identity function doesn't null-check either of its arguments, but it's used as a comparator with XMLARRAY_HAS_MEMBER multiple times (and in places where I'm not sure it's completely safe to do so -- SyncInScopeNamespaces in particular looks suspicious).  The same holds for the attr_identity and namespace_full_match functions.


Anyway, that's all I saw in the patch that looks possibly-relevant.  Hope that helps...

Comment 83

[Igor Bukanov]

(In reply to comment #82)
> 
> >    } else {
> >        xvec = (JSXML **) xml->xml_kids.vector;
> >        vvec = (JSXML **) vxml->xml_kids.vector;
> >        for (i = 0; i < n; i++) {
> >            xobj = js_GetXMLObject(cx, xvec[i]);
> >            vobj = js_GetXMLObject(cx, vvec[i]);
> >            if (!xobj || !vobj)
> >                return JS_FALSE;
> >            if (!js_XMLObjectOps.equality(cx, xobj, OBJECT_TO_JSVAL(vobj), bp))
> >                return JS_FALSE;
> >            if (!*bp)
> >                break;
> >        }
> 
> This clearly isn't going to handle holes in xml->xml_kids very well -- looks
> like js_GetXMLObject would crash trying to dereference (x|v)vec[i].  (Note:
> this was inside XMLEquals but not in the patch's context.)

It is worse than that since in fact this is a GC hazard, see bug 354145.

Comment 84

[Igor Bukanov]

(In reply to comment #83)
> It is worse than that since in fact this is a GC hazard, see bug 354145.
                                                           ^^^^^^^^^^^^^^

That should be bug 357063.

Comment 85

[Jeff Walden [:Waldo]]

Comment on attachment 241647 [details] [diff] [review]
alternative approach + always insert fix

>@@ -6464,22 +6619,24 @@ xml_normalize(JSContext *cx, JSObject *o

>         } else if (kid->xml_class == JSXML_CLASS_TEXT) {
>             while (i + 1 < n &&
>-                   (kid2 = XMLARRAY_MEMBER(&xml->xml_kids, i + 1, JSXML))
>-                   ->xml_class == JSXML_CLASS_TEXT) {
>+                   (kid2 = XMLARRAY_MEMBER(&xml->xml_kids, i + 1, JSXML)) &&
>+                   kid2->xml_class == JSXML_CLASS_TEXT) {
>                 str = js_ConcatStrings(cx, kid->xml_value, kid2->xml_value);
>                 if (!str)
>                     return JS_FALSE;

Another missing null-check here.

Comment 86

[Bob Clary [:bc] (inactive)]

Igor: e4x/Regress/regress-354145-03.js fails to execute the TEST function call after the list.contains() call. Is this a bug?

Comment 87

[Igor Bukanov]

(In reply to comment #86)
> Igor: e4x/Regress/regress-354145-03.js fails to execute the TEST function call
> after the list.contains() call. Is this a bug?

The file attached to the bug contains the TEST call. Do you mean some file?

Comment 88

[Bob Clary [:bc] (inactive)]

(In reply to comment #87)

add some print statements around the list.contains(...) like:

print("Before list.contains");
list.contains({ toString: prepare });
print("After list.contains");

After list.contains is not printed.

Comment 89

[Igor Bukanov]

(In reply to comment #88)
> (In reply to comment #87)
> 
> add some print statements around the list.contains(...) like:
> 
> print("Before list.contains");
> list.contains({ toString: prepare });
> print("After list.contains");
> 
> After list.contains is not printed.

That is a regression. I will file a bug for it.

Comment 90

[Daniel Veditz [:dveditz]]

Bug not relevant to aviary/moz1.7 branches

Comment 91

[Bob Clary [:bc] (inactive)]

verified fixed 1.8.0.8 20061015. Note 'FAILED HARNESS' on -03 was fixed in bug 358965.

Comment 92

[Bob Clary [:bc] (inactive)]

RCS file: /cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-01.js,v
done
Checking in regress-354145-01.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-01.js,v  <--  regress-354145-01.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-02.js,v
done
Checking in regress-354145-02.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-02.js,v  <--  regress-354145-02.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-03.js,v
done
Checking in regress-354145-03.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-03.js,v  <--  regress-354145-03.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-04.js,v
done
Checking in regress-354145-04.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-04.js,v  <--  regress-354145-04.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-05.js,v
done
Checking in regress-354145-05.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-05.js,v  <--  regress-354145-05.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-06.js,v
done
Checking in regress-354145-06.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-06.js,v  <--  regress-354145-06.js
initial revision: 1.1
done
RCS file: /cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-07.js,v
done
Checking in regress-354145-07.js;
/cvsroot/mozilla/js/tests/e4x/Regress/regress-354145-07.js,v  <--  regress-354145-07.js
initial revision: 1.1
done