`MapSerializer._orderEntries()` throws NPE when operating on `ConcurrentHashMap`

[Sovietaced]

It seems that the fix introduced for #1411 in 2.8 can be problematic for ConcurrentSkipListMap (and possibly other map data structures).

com.fasterxml.jackson.databind.JsonMappingException: (was java.lang.NullPointerException) (through reference chain: <redacted>->java.util.Collections$UnmodifiableCollection[0]-><redacted>
	at com.fasterxml.jackson.databind.JsonMappingException.wrapWithPath(JsonMappingException.java:388)
	at com.fasterxml.jackson.databind.JsonMappingException.wrapWithPath(JsonMappingException.java:348)
	at com.fasterxml.jackson.databind.ser.std.StdSerializer.wrapAndThrow(StdSerializer.java:343)
	at com.fasterxml.jackson.databind.ser.std.BeanSerializerBase.serializeFields(BeanSerializerBase.java:698)
	at com.fasterxml.jackson.databind.ser.BeanSerializer.serialize(BeanSerializer.java:155)
	at com.fasterxml.jackson.databind.ser.std.CollectionSerializer.serializeContents(CollectionSerializer.java:149)
	at com.fasterxml.jackson.databind.ser.std.CollectionSerializer.serialize(CollectionSerializer.java:112)
	at com.fasterxml.jackson.databind.ser.std.CollectionSerializer.serialize(CollectionSerializer.java:25)
	at com.fasterxml.jackson.databind.ser.BeanPropertyWriter.serializeAsField(BeanPropertyWriter.java:704)
	at com.fasterxml.jackson.databind.ser.std.BeanSerializerBase.serializeFields(BeanSerializerBase.java:690)
	at com.fasterxml.jackson.databind.ser.BeanSerializer.serialize(BeanSerializer.java:155)
	at com.fasterxml.jackson.databind.ser.DefaultSerializerProvider.serializeValue(DefaultSerializerProvider.java:292)
	at com.fasterxml.jackson.databind.ObjectMapper._configAndWriteValue(ObjectMapper.java:3681)
	at com.fasterxml.jackson.databind.ObjectMapper.writeValueAsString(ObjectMapper.java:3057)
	at <redacted>
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
	at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
	at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:26)
	at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
	at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
	at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
	at org.eclipse.jdt.internal.junit4.runner.JUnit4TestReference.run(JUnit4TestReference.java:86)
	at org.eclipse.jdt.internal.junit.runner.TestExecution.run(TestExecution.java:38)
	at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:459)
	at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.runTests(RemoteTestRunner.java:675)
	at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.run(RemoteTestRunner.java:382)
	at org.eclipse.jdt.internal.junit.runner.RemoteTestRunner.main(RemoteTestRunner.java:192)
Caused by: java.lang.NullPointerException
	at java.util.concurrent.ConcurrentSkipListMap.doGet(ConcurrentSkipListMap.java:778)
	at java.util.concurrent.ConcurrentSkipListMap.containsKey(ConcurrentSkipListMap.java:1528)
	at java.util.Collections$UnmodifiableMap.containsKey(Collections.java:1452)
	at com.fasterxml.jackson.databind.ser.std.MapSerializer._orderEntries(MapSerializer.java:954)
	at com.fasterxml.jackson.databind.ser.std.MapSerializer.serialize(MapSerializer.java:526)
	at com.fasterxml.jackson.databind.ser.std.MapSerializer.serialize(MapSerializer.java:30)
	at com.fasterxml.jackson.databind.ser.BeanPropertyWriter.serializeAsField(BeanPropertyWriter.java:704)
	at com.fasterxml.jackson.databind.ser.std.BeanSerializerBase.serializeFields(BeanSerializerBase.java:690)
	... 35 more

doc for ConcurrentSkipListMap.doGet()

Throws:
java.lang.ClassCastException if the specified key cannot be compared with the keys currently in the map
java.lang.NullPointerException if the specified key is null

[cowtowncoder]

Ok, thank you for reporting this. From exception it sounds like one should verify that keys implement Comparable? This should be possibly to verify when constructing deserializer, giving up-front failure with enough information.

[Sovietaced]

@cowtowncoder hmm. Not sure if I follow.

The key being queried on the ConcurrentSkipListMap does not necessarily exist in the map, it looks to be a test query made by Jackson.

776     private V More ...doGet(Object key) {
777         if (key == null)
778             throw new NullPointerException();
779         Comparator<? super K> cmp = comparator;
780         outer: for (;;) {
781             for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
782                 Object v; int c;
783                 if (n == null)
784                     break outer;
785                 Node<K,V> f = n.next;
786                 if (n != b.next)                // inconsistent read
787                     break;
788                 if ((v = n.value) == null) {    // n is deleted
789                     n.helpDelete(b, f);
790                     break;
791                 }
792                 if (b.value == null || v == n)  // b is deleted
793                     break;
794                 if ((c = cpr(cmp, key, n.key)) == 0) {
795                     @SuppressWarnings("unchecked") V vv = (V)v;
796                     return vv;
797                 }
798                 if (c < 0)
799                     break outer;
800                 b = n;
801                 n = f;
802             }
803         }
804         return null;
805     }

The issue is triggered when orderEntries attempts to see if a null key exists in the map at all.

// [databind#1411]: TreeMap does not like null key...
        if (input.containsKey(null)) {
            TreeMap<Object,Object> result = new TreeMap<Object,Object>();
            for (Map.Entry<?,?> entry : input.entrySet()) {
                Object key = entry.getKey();
                if (key == null) {
                    _writeNullKeyedEntry(gen, provider, entry.getValue());
                    continue;
                } 
                result.put(key, entry.getValue());
            }
            return result;
        }

All the keys in the map being serialized implement Comparable. They are Strings.

[mathieucarbou]

we have the same issue. we had to rollback to jackson databind 2.8.3

[cowtowncoder]

I can not reproduce the problem with simple ConcurrentSkipListMap, so there must be something different in either configuration or input data that triggers the problem.

@Sovietaced @mathieucarbou Has this been reproduced with version 2.8.6? Check:

        if (input instanceof SortedMap<?,?>) {
            return input;
        }

would seem to cover for this specific case.

[mathieucarbou]

Oh sorry! No our issue is still a NPE but when dealing with TreeMap, in version 2.8.6.

Actually, in 2.8.6, there is this code (see #1411):

        // prevent NPE in TreeMap
        if (input.containsKey(null)) {
            return input;
        }

The comment is wrong: if input is a TreeMap, TreeMap.containsKey(null) will throw a NPE. A TreeMap just cannot contain null keys and cannot check against null keys.

java.lang.NullPointerException
        at java_util_Map$containsKey.call(Unknown Source)

2.8.3 does not have this bug.

Yes, checking for SortedMap will fix the issue in our case, though, I think the code should be instead:

if (!(input instanceof SortedMap)) {
   return input;
}

Because if I understand correctly, what you wanted (I think) is to return the map if it "could" contain null keys, and consequently you are not able to order the keys.
So if it is a SortedMap, it cannot contain null keys, so you must not return and you must continue to order the keys, right ?

[cowtowncoder]

@mathieucarbou I can not reproduce the issue; I am looking for for actual way to replicate the problem you have. Without this explanations of problem will not help.

As to check: no. If we get SortedMap, it is already good as is and further processing would be waste of time (as well as hit null related issues).

[mathieucarbou]

OK, fine :-) I'll be able to provide a junit test to reproduce on Monday.

…

-- Mathieu On Feb 18, 2017 19:01, "Tatu Saloranta" <notifications@github.com> wrote: @mathieucarbou <https://github.com/mathieucarbou> I can not reproduce the issue; I am looking for for actual way to replicate the problem you have. Without this explanations of problem will not help. As to check: no. If we get SortedMap, it is already good as is and further processing would be waste of time (as well as hit null related issues). — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1513 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AADvomr-ZWPvCW2ps2YntuTm7g2dryFOks5rd4ZMgaJpZM4L0Wjq> .

[andi-bigswitch]

@cowtowncoder the problem that we experienced (that @Sovietaced reported) arose because we wrapped the ConcurrentSkipListMap in Collections.unmodifiableMap to prevent accidental modification.

The map wrapper returned by Collections.unmodifiableMap does not implement SortedMap, so the code would not return as a result of the if (input instanceof SortedMap<?,?> conditional.
Instead it would try calling if (input.containsKey(null)) on the wrapped CSLM, which yields a NPE.

I think the code in #1411 needs to be rethought. The contract of java.util.Map says that:

Attempting to query the presence of an ineligible key or value may throw an exception, or it may simply return false.

I.e., it is not a safe operation to call map.conttainsKey(null) on any Map. And it is not a safe assumption that only Sorted Maps would disallow null keys. In fact, if you just use a ConcurrentHashMap, which is a way more common data structure than a wrapped ConcurrentSkipListMap, you would also get an NPE, because the Map is not sorted, but containsKey(null) throws an NPE (I am testing on Java 8).

IMHO the right way to fix the problem in #1411 is, instead of using a TreeMap directly, to implement a SortedMap (e.g., NullSafeTreeMap) that can handle null keys and values by replacing them with a marker object, should the underlaying map contain them. But one cannot check the underlying map with containsKey(null) because that might yield an NPE; it can only be detected while iterating over the entrySet of the underlying map.

[ogmios-voice]

No surprise the NPE is present for ConcurrentHashMap too. ConcurrentHashMap.containsKey docs:

Throws:
NullPointerException - if the specified key is null

I agree with @andi-bigswitch`s solution regarding #1411. (thanks)

[cowtowncoder]

At this point I slightly disagree with the root causes analysis: in my opinion, the fundamental root cause is that SOME MAPS do not allow storage of null keys; and some do not allow attempts to use null as key to retrieve values (possibly overlapping but not guaranteed as identical) -- yet there is no way to introspect this aspect. java.util.Map javadocs state:

Some map implementations have restrictions on the keys and values they may contain. For example, some implementations prohibit null keys and values, and some have restrictions on the types of their keys. Attempting to insert an ineligible key or value throws an unchecked exception, typically NullPointerException or ClassCastException. Attempting to query the presence of an ineligible key or value may throw an exception, or it may simply return false; some implementations will exhibit the former behavior and some will exhibit the latter.

It is also worth noting that the check for SortedMap is not primarily to check against null issue: it is because no sorting is required if contents are already sorted. Its side effect is to prevent problems for a subset of types.

I am also bit uneasy about building yet more complex work-arounds for likely open-ended sets of Map types: especially as it is not at all guaranteed that one can construct marker objects that do not fail (considering key value checks may or may not use full type, so could fail with ClassCastException).

But I am open to PRs for fixes for specific set of types. Since the method in question is part of internal MapSerializer implementation API compatibility should not be highly problematic, although it is possible that change could cause problems for developers who sub-class MapSerializer (not recommended but possible).

[cowtowncoder]

I can reproduce the issue with ConcurrentHashMap as suggested.