List serialization/deserialization can overflow the stack

[scabug]

Compiling and running this program will result in the issue that it overflows the stack at runtime in 2.10 but not in 2.9. Please fix this - it's a critical bug.

object ListSer extends App {

  val largeList = (1 to 1000000).toList

  val oos = new ObjectOutputStream(new FileOutputStream("C:/tmp/largeList.ser"))
  oos.writeObject(largeList)
  oos.flush()
  oos.close()

  val ois = new ObjectInputStream(new FileInputStream("C:/tmp/largeList.ser"))
  val read = ois.readObject().asInstanceOf[List[Int]]
  println(read.size)


}

Here is the stack trace:

        at scala.collection.immutable.$colon$colon.readObject(List.scala:362)
        at sun.reflect.GeneratedMethodAccessor16.invoke(Unknown Source)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.lang.reflect.Method.invoke(Method.java:601)
        at java.io.ObjectStreamClass.invokeReadObject(ObjectStreamClass.java:1004)
        at java.io.ObjectInputStream.readSerialData(ObjectInputStream.java:1866)
        at java.io.ObjectInputStream.readOrdinaryObject(ObjectInputStream.java:1771)
        at java.io.ObjectInputStream.readObject0(ObjectInputStream.java:1347)
        at java.io.ObjectInputStream.readObject(ObjectInputStream.java:369)
        at scala.collection.immutable.$colon$colon.readObject(List.scala:362)
        at sun.reflect.GeneratedMethodAccessor16.invoke(Unknown Source)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.lang.reflect.Method.invoke(Method.java:601)
        at java.io.ObjectStreamClass.invokeReadObject(ObjectStreamClass.java:1004)
        at java.io.ObjectInputStream.readSerialData(ObjectInputStream.java:1866)
        at java.io.ObjectInputStream.readOrdinaryObject(ObjectInputStream.java:1771)
        at java.io.ObjectInputStream.readObject0(ObjectInputStream.java:1347)
        at java.io.ObjectInputStream.readObject(ObjectInputStream.java:369)
        at scala.collection.immutable.$colon$colon.readObject(List.scala:362)
        at sun.reflect.GeneratedMethodAccessor16.invoke(Unknown Source)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.lang.reflect.Method.invoke(Method.java:601)
        at java.io.ObjectStreamClass.invokeReadObject(ObjectStreamClass.java:1004)
        at java.io.ObjectInputStream.readSerialData(ObjectInputStream.java:1866)
        at java.io.ObjectInputStream.readOrdinaryObject(ObjectInputStream.java:1771)
        at java.io.ObjectInputStream.readObject0(ObjectInputStream.java:1347)
        at java.io.ObjectInputStream.readObject(ObjectInputStream.java:369)
        at scala.collection.immutable.$colon$colon.readObject(List.scala:362)
        at sun.reflect.GeneratedMethodAccessor16.invoke(Unknown Source)
        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
        at java.lang.reflect.Method.invoke(Method.java:601)
        at java.io.ObjectStreamClass.invokeReadObject(ObjectStreamClass.java:1004)
        at java.io.ObjectInputStream.readSerialData(ObjectInputStream.java:1866)
        at java.io.ObjectInputStream.readOrdinaryObject(ObjectInputStream.java:1771)
        at java.io.ObjectInputStream.readObject0(ObjectInputStream.java:1347)
        at java.io.ObjectInputStream.readObject(ObjectInputStream.java:369)

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-6961?orig=1
Reporter: @oxbowlakes
Affected Versions: 2.10.0
See #5374

[scabug]

@xeno-by said:
http://groups.google.com/group/scala-internals/browse_thread/thread/ae1f6a1a78f0cb85

[scabug]

@retronym said:
Jan Vanek j3vanek@gmail.com
6:16 PM (3 minutes ago)

to scala-internals
Here is a gist, please have a look. It requires 2 Booleans in thread-local storage. Supports long lists including sub-structure sharing. The oldReadObject() is not incorporated.

https://gist.github.com/4512368

Regards,
Jan

[scabug]

Jan Vanek (j3vanek) said:
Hi, I've forked/updated the gist:

https://gist.github.com/4517945

There was couple of bugs in the first version, as you might have noticed.

This version removes the thread-local data (set's to null) after top-level call, so no trace is left. I think it's better so. But if you think it is better to keep the data there to avoid per-top-list-allocation, then it should not be an instance of a scala class (ListSerializationCtrl), but an Array[Boolean] instance, so the hypothetical class-loader leak is prevented.

The version sets inLoop = false directly after write/read in finally block, so that when an exception is thrown the data is in correct state. I first thought it is enough to just remove (set to null) the TLS data in the top-level try/finally, but this way is safer; it's possible to imagine serialization-data which could leave the TLS data in wrong state (if one does e.g serialization within serialization). This is paranoid, but I measured the cost of try/finally there (against setting inLoop = false not within finally) and it was not recognizeable, so no reason to not have that.

It also supports the 2.9 serialization format data, at least according my testing. I wrote the object using oldWriteObject() and read correctly using the new readObject().

I've moved the ListSerializationCtrl class and thread-local variable out of List object. This is mainly to have it private and not private[scala] because the List.tlSerCtrl would be visible from Java in IDEs. So now ListSerializationStart/End/Ctrl are all private classes close to each other.

Finally I did some performance testing. List of size S, serialized/deserialized N times into/from a byte-array:

List size | repeated | 2.9.(ms) | this code(ms) | current 2.10.(ms)
10 | 2000x | 33 | 46 | 50
20 | 2000x | 40 | 62 | 70
500 | 200x | 44 | 86 | 105

So this code is actually faster then the current 2.10. code. That was a pleasant surprise. I don't have definitive explanation on that. I think the code is ready, but I didn't yet have time to learn how to do pull request, or what is the next step.

[scabug]

@retronym said:
Alex: could you please review Jan's suggested fix?

[scabug]

@axel22 said:
Yes, I'll review this today.

[scabug]

@axel22 said (edited on Jan 15, 2013 4:27:09 PM UTC):
Jan, thank you for your patch!
It seems to me that you have correctly addressed the issues from #5374, in particular
that the structural sharing is maintained when serializing objects which point to the same lists multiple times.
Also, it seems to me that the loop-logic works correctly now.

A couple of comments:

1. I did not completely understand why the fields seen0 and inLoop0 private, why not have just public vars.

2. It seems to me that the idea is that when the seen field becomes false, serializing a :: has to bring it
   back to true. Otherwise, the tail must have been Nil, meaning that the loop in writeObjectImpl can end.

3. It seems to me that serializing nested lists should work as well.
   Calling writeAsSeen in line 34 may serialize a nested list, in which case the nested list should leave the ctrl
   object in the seen == false state, but in that case the writeAsSeen of the outer list brings it back to true.

Am I right?

Nevertheless, could you add a few more tests with nested lists, and lists of objects having nested lists and shared lists to ensure that this works?

4. I suppose a similar inverse logic applies to readObject, from what I can see.

Overall, looks good.

On a side note, I wonder if there is some existing serialization infrastructure, i.e. a method call, we could use instead
of the thread local with state patch to output the objects into the object output stream and maintain structural sharing.
Something like out.writeObjectId(...) could greatly simplify the code we have in the patch now.

[scabug]

Jan Vanek (j3vanek) said:
Hi Aleksandar,

ad 1) It was so in the first (or maybe also second) version in the fork. I refactored those code pieces from write/readObjectImpl into those ListSerializationCtrl.write/read/InLoop/AsSeen methods to make the code in write/readObjectImpl shorter and more readable and I hoped giving those pieces names would also make it more understandable (than mutate the vars in the write/readObjectImpl directly). When that happened, having the vars private makes clear that only the methods of LSCtrl can mutate them. Doing that I hoped that the analogy of read vs. write is apparent because both write/readObjectImpl and those write/readInLoop, write/readAsSeen are simple enough to see the mirroring. The goal is readability. If you find the "inlined" version more readable, I've absolutely nothing against it.

ad 2,3) Yes. The idea is that the list is serialized in the loop, and each sub-list contributes just its head and itself, so to say. So technically the serialization stream consists of multiple of single-head unconnected lists (well they don't have tail in the stream so they are not lists). The loop makes sure all of them are in, and during the deserialization the loop connects them again.

This is controlled by the inLoop variable. When the writeObjectImpl sees inLoop = true, it knows someone else manages the loop and that it must serialize its head only, and that it has to set the seen to true, to tell that someone it did so. So the seen is like a response, that the list (not the head) was there and contributed itself and it's head. I don't like the name "seen". I don't know a better name now, but we should find one. The "inLoop" is more critical, it's like a request, and thus the inLoop = true can't escape, that's why I set it to false in finally. For the same reason the "inLoop" is set to false before the head is serialized. Head can be or can contain a list, that one must not enter writeObject with inLoop = true, obviously.

So if after calling writeInLoop the ctrl.seen is false, then it was either Nil or already serialized shared sub-list. There is no need to distinguish the two, in either case the loop must stop.

ad 4) Yes, I tried to make read a clear inverse of write.

I've added 1 :-) test into the gist. It is a "shared" thing, and it deserializes properly.

ad side note) You mean like oos.beginWriteObject(obj): Boolean (false if already there and ID written, true if not and ID generated and definition starts) and oos.endWriteObject()?

Regards...

[scabug]

@axel22 said:
Yes, something like beginWriteObject and endWriteObject like you described would be ideal.
I have not seen such a facility on the ObjectOutputStream.

Otherwise, looks good to me!
You can fork the Scala repo and open a new branch issue/6961, apply the patch, build the repo and run all the tests (ant test), and then submit a pull request to the Scala repo on GitHub.
Or I can do this for you, as you like.

[scabug]

Jan Vanek (j3vanek) said:
When it's there, we can rewrite it, well, I actually doubt it will come. Also when the closures don't cost anything, we can simplify the code which tests/creates/resets the thread-local - I believe this will happen much sooner than the first thing.

Thanks! I'll try to do that during the weekend. Of course if there is pressure, please do that now.

[scabug]

Jan Vanek (j3vanek) said:
Alex, I tried the closure version, please have a look. The code is simpler, the performance is like 124ms:125ms for the non-closure version and there is some memory cost, 1 closure instance per writeObject call (each non-shared list). I'd do that, but I'm not sure.

[scabug]

@axel22 said:
I'd vote for the version without the extra object allocations. The difference in complexity does not seem to be huge.
I didn't understand, what was the performance difference you have observed?

[scabug]

Jan Vanek (j3vanek) said:
The non-closure version was minimally faster. Like 752.5ms vs 760.7ms (list size 500, serialized 2000x). OK, lets wait for the closure version when it is free.

[scabug]

@axel22 said:
Ok, thanks for doing this!
I think there is no rush currently, Jason please correct me if I'm wrong.
If there is, I can submit a pull request, otherwise feel free to submit one and set me as a reviewer (review by @axel22).

[scabug]

@retronym said:
Current plan would be for 2.10.1. We'll have to see if the fix meets with our binary compatibility constraints. For that reason, might be best for you to do this Alex.