ArrayIndexOutOfBoundsException in IdentityMap.clear()

GoogleCodeExporter commented 9 years ago

What steps will reproduce the problem?
1. Instantiate Kryo instance.
2. Instantiate fairly complex composite Java class (my project uses one that I 
can't share)
3. Create 100+ copies of the complex instance in a loop

What is the expected output? What do you see instead?
Expect all 100+ copies to be made, but instead, I'm getting an 
ArrayIndexOutOfBoundsException at some point.

What version of the Kryo are you using?
2.19, 2.20, 2.21

Please provide any additional information below.
This problem does NOT exhibit itself in 2.17 or lower. It pops up only in 2.19 
and above. I recognize the problem is probably very specific to the nature of 
my complex, composite Java object that I'm cloning (copying) and therefore may 
be difficult for you guys to replicate. If time permits, I may try to 
troubleshoot this for you, however, I can clearly see something must have 
changed between 2.17 & 2.19 that affects IdentityMap.clear() to cause this. 
Perhaps you guys will be able to see the difference and arrive at a conclusion 
fairly easily. If not, let me know and I'll try to have a deeper look myself 
when I get an opportunity. In the meantime, I'll go just use 2.17.

Thanks

Original issue reported on code.google.com by terrymis...@gmail.com on 24 Jun 2013 at 8:27

GoogleCodeExporter commented 9 years ago

Incidentally, I believe the exception is thrown around line 362 in version 2.19:

valueTable[i] = null;

Original comment by terrymis...@gmail.com on 24 Jun 2013 at 8:30

GoogleCodeExporter commented 9 years ago

Hi, 

Could you provide a bit more details about this issue? Kryo is used to 
serialize thousands or even millions of rather complex objects  and usually it 
works. So, there should be something specific to your test-case that makes it 
fail.  To find out what it is we need more information. 

For starters, a stack-trace would be nice to have. At least the Kryo related 
part of it. Which class throws the exception, where it is called from, etc?

A test-case that helps to reproduce a problem would be even better. But it 
looks like you have problems disclosing it, right?

-Leo

Original comment by romixlev on 23 Jul 2013 at 1:30

GoogleCodeExporter commented 9 years ago

I have the same issue, here is the stack trace maybe it can help : 
java.lang.ArrayIndexOutOfBoundsException
    at com.esotericsoftware.kryo.util.IdentityMap.clear(IdentityMap.java:361)
    at com.esotericsoftware.kryo.Kryo.reset(Kryo.java:809)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:835)

I don't know if this is linked to the problem but it seems that when I have 14 
objects in one of my maps everything is ok, when it reaches 15 this exception 
is thrown (HashMap<Integer, Object>, jvm 1.5).

Original comment by ice...@gmail.com on 29 Jul 2013 at 12:18

GoogleCodeExporter commented 9 years ago

@icewil: Thanks a lot for your report. Could you provide a small test-case to 
reproduce the problem?  Or at least how the structure of your classes looks 
like and how you configure your kryo instance (e.g. refrences, registration of 
classes, etc)? It would help a lot.

BTW you used 2.21? Or current snapshot, i.e. 2.22-SNAPSHOT?
You use Kryo instance by a single thread only? Or is it a multithreaded app 
which tries to share a kryo instance between threads?

Thanks,
  -Leo

Original comment by romixlev on 29 Jul 2013 at 12:28

GoogleCodeExporter commented 9 years ago

I use 2.21 (it's working normally with 2.16, I don't tried other versions 
between these two) and I use a new instance each time but the application is 
multithreaded (I also tried to put a synchronized(myObject) before creating the 
kryo instance but it doesn't change anything). I tried to reproduce the problem 
on a smaller scale but my objects are very complicated sadly...

(Note that once serialized/unserialized with the java standard way, the error 
is never thrown.)

Original comment by ice...@gmail.com on 29 Jul 2013 at 4:03

GoogleCodeExporter commented 9 years ago

OK. The important thing is that your Kryo instances are not simultaneously by 
multiple threads.

Could you test with 2.22-SNAPSHOT to see if this error is still present? Just 
replace the version in your POM by 2.22-SNAPSHOT.

Original comment by romixlev on 29 Jul 2013 at 4:13

GoogleCodeExporter commented 9 years ago

> I tried to reproduce the problem on a smaller scale but my objects are very 
complicated sadly...
That's a pity. Because we  need a hint how to reproduce a problem. Currently 
all Kryo unit tests pass, i.e. they do not trigger a problem. But we need to 
find a way to reproduce it. 

Would it be possible for you to provide a test that only shows a structure of 
your classes and how you construct objects, so that we can reproduce a problem? 
Only the structure is important for Kryo. You can remove all the business logic 
and rename the classes and fields, if you don't want to disclose any secrets 
due to corporate policies. 

-Leo

Original comment by romixlev on 29 Jul 2013 at 4:48

GoogleCodeExporter commented 9 years ago

I tried with 2.22-SNAPSHOT, the error is still present. I don't have enough 
time to do what you propose actually. I will use 2.16 for the moment and retry 
later when I will have more time.

Original comment by ice...@gmail.com on 30 Jul 2013 at 8:39

GoogleCodeExporter commented 9 years ago

If you can give us the keys when you have 14 objects and also the key for the 
15th object you try to add, likely we can reproduce the crash.

Original comment by nathan.s...@gmail.com on 5 Aug 2013 at 12:23

GoogleCodeExporter commented 9 years ago

I finally got time for debugging the issue. I found out that the real error is 
not in IdentityMap.clear() but in IdentityMap.resize(), because of "finally" 
statement the original error is replaced. I had a try/catch in Kryo.reference() 
method, I got this error in addition to the other :

 java.lang.OutOfMemoryError
    at com.esotericsoftware.kryo.util.IdentityMap.resize(IdentityMap.java:448)

So the OutOfMemoryError corrupted the IdentityMap object, the new array is not 
created but the capacity has been increased and this causes an error when 
clearing the map in "finally" statement in Kryo.copy().

Now, I do not understand why Kryo needs so much memory (the IdentityMap.size is 
around 500-800 objects and the IdentityMap.keyTable size is always 33554468 
before trying to change is size to 67108902).

Original comment by ice...@gmail.com on 9 Aug 2013 at 9:18

GoogleCodeExporter commented 9 years ago

@icewil: This is a very good hint! Thanks for looking into this.

But if you are at it anyway, could you really try to record just the keys which 
are in the map when you try to add the last one which leads to the crash, as 
Nate suggested? Then we likely can reproduce the crash. 

I guess it would be even better if you could record the order in which keys 
were added/removed to/from identity map.

Original comment by romixlev on 9 Aug 2013 at 9:43

GoogleCodeExporter commented 9 years ago

@icewil, @tcmartin24: Nate committed some fixes which may improve the 
situation. It would be nice, if you could try with the trunk version. 

Btw, the kryo-2.22-SNAPSHOT is available in the sonatype snapshots repo: 
https://oss.sonatype.org/content/repositories/snapshots/ 
(https://oss.sonatype.org/content/repositories/snapshots/com/esotericsoftware/kr
yo/kryo/) 

-Leo

Original comment by romixlev on 14 Aug 2013 at 3:15

GoogleCodeExporter commented 9 years ago

I am on vacation until September, I had no time for working on this since my 
last comment. You will have to wait, sorry.

Original comment by ice...@gmail.com on 16 Aug 2013 at 4:57

GoogleCodeExporter commented 9 years ago

I tried with the latest 2.22 snapshot, the memory error seems random depending 
on memory status. An example : 

java.lang.OutOfMemoryError
    at com.esotericsoftware.kryo.util.IdentityMap.resize(IdentityMap.java:469)
    at com.esotericsoftware.kryo.util.IdentityMap.putStash(IdentityMap.java:255)
    at com.esotericsoftware.kryo.util.IdentityMap.push(IdentityMap.java:249)
    at com.esotericsoftware.kryo.util.IdentityMap.put(IdentityMap.java:144)
    at com.esotericsoftware.kryo.Kryo.reference(Kryo.java:833)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:878)
    at com.esotericsoftware.kryo.serializers.UnsafeCacheFields$UnsafeObjectField.copy(UnsafeCacheFields.java:297)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:153)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:17)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.UnsafeCacheFields$UnsafeObjectField.copy(UnsafeCacheFields.java:297)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:153)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:17)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.UnsafeCacheFields$UnsafeObjectField.copy(UnsafeCacheFields.java:297)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.UnsafeCacheFields$UnsafeObjectField.copy(UnsafeCacheFields.java:297)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.UnsafeCacheFields$UnsafeObjectField.copy(UnsafeCacheFields.java:297)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:153)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:17)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.UnsafeCacheFields$UnsafeObjectField.copy(UnsafeCacheFields.java:297)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)

I noticed a few weeks ago that immutable objects are stored in the identity map 
with the key equals to the value. I have many immutable objects (String, 
Double, BigDecimal, Integer, ...) so I wonder if this might be causing the 
memory issue. Is it useful to store immutable objects in the identity map ?

Original comment by ice...@gmail.com on 3 Sep 2013 at 9:17

GoogleCodeExporter commented 9 years ago

@icewil: Nice to hear from you again!

Thanks for checking the latest snapshot. I'd like to ask a few questions:

1) Your stack trace shows that you use Unsafe-based FieldSerializer. Could you 
also try with the ASM-based one? Simply call kryo.setAsmEnabled(true); 
immediately after this kryo instance is created, but before any other 
operations on it.

2) It seems you use Kryo's support for circular references and shared objects 
in the object graph. Is it the case? Do you really need it in your application? 
If not, you could try to disable it by using kryo.setReferences(false);

In any case, Kryo should work properly even without these proposed changes. 
Most likely you hit a very subtle bug in Kryo and we would really like to fix 
it. But we need a way to reproduce it somehow. May be you could try to provide 
a test-case? Or may be at least you could provide a set of keys and order of 
operations on the identity map that leads to the crash? 

-Leo

Original comment by romixlev on 3 Sep 2013 at 9:28

GoogleCodeExporter commented 9 years ago

1) Only the stack changed with this setting : 

java.lang.OutOfMemoryError
    at com.esotericsoftware.kryo.util.IdentityMap.resize(IdentityMap.java:469)
    at com.esotericsoftware.kryo.util.IdentityMap.putStash(IdentityMap.java:255)
    at com.esotericsoftware.kryo.util.IdentityMap.push(IdentityMap.java:249)
    at com.esotericsoftware.kryo.util.IdentityMap.put(IdentityMap.java:144)
    at com.esotericsoftware.kryo.Kryo.reference(Kryo.java:833)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:557)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:153)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:17)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.ObjectField.copy(ObjectField.java:140)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:153)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:17)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.ObjectField.copy(ObjectField.java:140)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.ObjectField.copy(ObjectField.java:140)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.ObjectField.copy(ObjectField.java:140)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:153)
    at com.esotericsoftware.kryo.serializers.MapSerializer.copy(MapSerializer.java:17)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)
    at com.esotericsoftware.kryo.serializers.ObjectField.copy(ObjectField.java:140)
    at com.esotericsoftware.kryo.serializers.FieldSerializer.copy(FieldSerializer.java:562)
    at com.esotericsoftware.kryo.Kryo.copy(Kryo.java:877)

What is the purpose of this setting ?

2) I already tried this setting before, it does not change anything but I do 
not really need circular references or shared objects (I only need my objects 
to be different from the original ones). 

I tried to produce manually a test case multiple times without success. My 
original object is initialized with many database accesses, use a hundred 
conditions to be initialized the same way and have many maps/intern 
classes/lists/properties to fill. I tried to serialize my objet in a file 
before the crash with the java default serialization but the object doesn't 
seems to produce the crash once unserialized in a separate test class. The 
identity map contains around 600 objets when the crash occurs and the last keys 
inserted are different each time, I am just unable (and not allowed) to provide 
a relevant set of keys. 
I have at least 200MB free memory available before the clone method call. I 
will do further testing the next week.

Original comment by ice...@gmail.com on 3 Sep 2013 at 1:20

GoogleCodeExporter commented 9 years ago

Regarding kryo.setAsmEnabled(true):
The purpose of this setting is to use the ASM-based backend. This backend uses 
run-time bytecode generation. It is faster than Java-reflection based approach, 
but slower than Unsafe-based approach. But on some platforms like Android or 
securiry-constrained environments the Unsafe-based approach cannot be used due 
to platform limitations. In such situations, ASM-based backend is used.
BTW, ASM was the only backend until Kryo's changes earlier this year introduced 
 a new Unsafe-based implementation.

Overall, it is good that you get a consistent failure in all modes, because it 
really indicates that this is a generic bug in Kryo and it is not specific for 
a given backend or mode of operation.

Of course, it is very pity that you cannot provide us with a reproducible 
test-case yet. But let's see if we can find the problem anyways.

Let me continue with questions:
3) According to your traces, you try to copy/clone an object graph and hit the 
exception. If you serialize into a file and then deserialize instead, do you 
get the same problem?

4) Can you try to provide us with the info about how this identityMap resizes 
and stats about it? E.g. how many elements were in the map, what was the amount 
of reserved elements, etc when it performs a resize operation. I.e. it would be 
interesting to know the dynamics of growth for this map. 

It would be also useful to know the rough amount of unique objects you insert 
into this map. In theory, the upper bound should be the amount of objects in 
your object graph that you try to serialize/clone.

5) In your comment #3 on this issue, you were hitting the problem already with 
15 objects in the IdentityMap. Has it gone now for that test-case and you see 
another problem now? Or is that test-case still failing?

Original comment by romixlev on 3 Sep 2013 at 1:40

GoogleCodeExporter commented 9 years ago

@icewill:

> I am just unable (and not allowed) to provide a relevant set of keys

Actually, we do not need the values of keys, most likely. We need just their 
hash-values as computed by hash functions inside the IdentityMap (because 
decisions inside this map are based on those hash-values mostly) and some 
virtual names for each key, e.g. key1,...,keyX, so that we can e.g. understand 
that same key is inserted twice, or a given key is deleted, etc, even though we 
don't know the value of this key.

And I'd say that hash values of keys won't disclose anything about the keys 
themselves or their semantics. 

I guess stats like this could be produced if you'd build Kryo from sources and 
add some simple debug print statements into put, putResize, resize and may be 
some other methods that change the state of the map. At least it could be worth 
a try.

-Leo

Original comment by romixlev on 3 Sep 2013 at 2:03

GoogleCodeExporter commented 9 years ago

I think I finally found out what really happens. It seems to be linked to my 
IBM JVM. The keys in identity map can be differents but can have the same 
System.identityHashCode() value sometimes with this JVM (it seems managed 
differently with Oracle JVM). Here is an example :

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.esotericsoftware.kryo.Kryo;

public class Test {

    public static void main(String[] args) throws Exception {

        Map<Integer, List<String>> map2 = new HashMap<Integer, List<String>>();

        List<String> biggerList = null;

        for (int i = 0; biggerList == null; i++) {
            String obj = new String("test"+i);

            List<String> samehashlist = map2.get(System.identityHashCode(obj));
            if (samehashlist != null) {
                samehashlist.add(obj);
                if(samehashlist.size() >= 100) {

                    biggerList = samehashlist;

                }
            } else {
                samehashlist = new ArrayList<String>();
                samehashlist.add(obj);
                map2.put(System.identityHashCode(obj), samehashlist);
            }
        }
        map2.clear();
        map2 = null;

        System.gc();

        Runtime runtime = Runtime.getRuntime();
        double mb = 1024.*1024.;
        System.out.println("Memory used : " + ((runtime.totalMemory() - runtime.freeMemory())/mb) + "/" + (runtime.totalMemory()/mb) + " max:"+ (runtime.maxMemory()/mb)); 

        Kryo k = new Kryo();
        k.copy(biggerList);

    }

}

With with kryo > 2.16 releases (I have not tested again with the snapshot 
release) :

This code will cause a java heap space exception on Oracle JVM (because all 
string identity hash codes seems differents) :
java.lang.OutOfMemoryError: Java heap space
    at java.lang.StringBuilder.toString(Unknown Source)

But it will cause my ArrayIndexOutOfBoundsException with my IBM JVM on 
kryo.copy trying to copy a list of 100 different String with the same hash code.

I tried with latest IBM JVM, it seems to work as the Oracle one but I can not 
use it. My IBM JVM comes from IBM WebSphere 7 and I can not change it. I think 
that an option for using a different (but slower) indentity map implementation 
using "obj1 == obj2" equality could be enough for me to fix the issue (or an 
option to disable the map).

For the questions :
3) In practice, it seems to be random.
4) I noticed the map resized often when putting a String or Integer or an other 
object with a identity hash code already in the map index but with a different 
object (I guess it should not be the case anyway).
5) My map only impacted the amount of data (especially strings), I think the 
risk of collision between identity hash codes was more important when my map 
growed.

Original comment by ice...@gmail.com on 16 Sep 2013 at 4:52

GoogleCodeExporter commented 9 years ago

@icewill: Thanks a lot for your feedback. I think now we are getting closer to 
the solution. As for the System.identityHashCode(), I've found this:
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6321873

So, basically, we cannot rely on the fact that two different objects which are 
not equal always have different identityHashCode values.

I guess we need to rewrite Kryo's identity maps accordingly by removing this 
assumption.

@Nate: Can you look into this?

Original comment by romixlev on 16 Sep 2013 at 5:52

Changed state: Accepted

GoogleCodeExporter commented 9 years ago

Any news on this issue?

Original comment by ice...@gmail.com on 20 Nov 2013 at 12:44

GoogleCodeExporter commented 9 years ago

Have you tried with the latest snapshot (2.23-SNAPSHOT) or release (2.22)? 
There were some related changes there.

BTW, we have moved to github. All the issues are migrated there as well.

Original comment by romixlev on 20 Nov 2013 at 1:00

GoogleCodeExporter commented 9 years ago

I commented on github : https://github.com/EsotericSoftware/kryo/issues/115

Original comment by ice...@gmail.com on 21 Nov 2013 at 9:44

GoogleCodeExporter commented 9 years ago

Hi,

Could you please suggest how to check the kryo version ?

Please help

Original comment by ak3...@gmail.com on 23 Apr 2015 at 5:29

Avi-Levi / kryo

ArrayIndexOutOfBoundsException in IdentityMap.clear() #115