ArrayIndexOutOfBoundsException in com.fasterxml.jackson.core.sym.ByteQuadsCanonicalizer

[fschopp]

The following code demonstrates a bug in jackson-core, version 2.6.0, in the hash table implementation of com.fasterxml.jackson.core.sym.ByteQuadsCanonicalizer. From a quick glance, it looks to me as if the "primary hash information area" _hashArea has a spillover area that is not accounted for properly in the String array _names.

import com.fasterxml.jackson.core.JsonFactory;
import com.fasterxml.jackson.core.sym.ByteQuadsCanonicalizer;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.testng.annotations.Test;

import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.nio.charset.StandardCharsets;
import java.util.Map;

/**
 * Simple test case for demonstrating bug in class {@link ByteQuadsCanonicalizer}.
 *
 * <p>In some cases, it is possible to work around this bug by disabling the
 * {@link JsonFactory.Feature#CANONICALIZE_FIELD_NAMES} feature. In that case
 * {@link com.fasterxml.jackson.core.json.ByteSourceJsonBootstrapper#constructParser(int, com.fasterxml.jackson.core.ObjectCodec, ByteQuadsCanonicalizer, com.fasterxml.jackson.core.sym.CharsToNameCanonicalizer, int)}
 * creates a {@link com.fasterxml.jackson.core.json.ReaderBasedJsonParser} instead of a
 * {@link com.fasterxml.jackson.core.json.UTF8StreamJsonParser}.
 */
public class UTF8ByteStreamTest {
    private static final int SEED = -523743345;

    private static void injectReproducibleSeed(ObjectMapper objectMapper) throws Exception {
        JsonFactory jsonFactory = objectMapper.getFactory();
        // As a workaround, uncomment the following line.
        // jsonFactory.disable(JsonFactory.Feature.CANONICALIZE_FIELD_NAMES);
        Field byteSymbolCanonicalizerField = JsonFactory.class.getDeclaredField("_byteSymbolCanonicalizer");
        byteSymbolCanonicalizerField.setAccessible(true);

        Method factoryMethod = ByteQuadsCanonicalizer.class.getDeclaredMethod("createRoot", int.class);
        factoryMethod.setAccessible(true);
        byteSymbolCanonicalizerField.set(jsonFactory, factoryMethod.invoke(null, SEED));
    }

    @Test
    public void testRead() throws Exception {
        ObjectMapper objectMapper = new ObjectMapper();
        injectReproducibleSeed(objectMapper);
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("{\n");
        stringBuilder.append("    \"expectedGCperPosition\": null");
        for (int i = 0; i < 60; ++i) {
            stringBuilder.append(",\n    \"").append(i + 1).append("\": null");
        }
        stringBuilder.append("\n}");
        objectMapper.readValue(stringBuilder.toString().getBytes(StandardCharsets.UTF_8), Map.class);
    }
}

[cowtowncoder]

Thank you for reporting this. Surprising that the problem can be reproduced this easily.

[cowtowncoder]

Looks like this is a degenerate case with very unusual number of collisions; but that also seems strange given that it is a straight-sequence of number strings.

[cowtowncoder]

Ok. The real bug was in check to see where is the end of spillover area: was assuming hash array end is it, but this is not correct -- optional area exists for long names.

But I also changed short-name hash shuffling slightly to produce better distribution; test case had 50% spill rate which is way too high. With changes much more modest spillover rate, and also slightly improves hashing wrt existing tests.

[tlrx]

I also hit this exception with 2.6.1:

Caused by: java.lang.ArrayIndexOutOfBoundsException: 512
    at com.fasterxml.jackson.core.sym.ByteQuadsCanonicalizer.addName(ByteQuadsCanonicalizer.java:822)
    at com.fasterxml.jackson.core.json.UTF8StreamJsonParser.addName(UTF8StreamJsonParser.java:2340)
    at com.fasterxml.jackson.core.json.UTF8StreamJsonParser.findName(UTF8StreamJsonParser.java:2185)
    at com.fasterxml.jackson.core.json.UTF8StreamJsonParser._parseName(UTF8StreamJsonParser.java:1691)
    at com.fasterxml.jackson.core.json.UTF8StreamJsonParser.nextToken(UTF8StreamJsonParser.java:740)
    at org.elasticsearch.common.xcontent.json.JsonXContentParser.nextToken(JsonXContentParser.java:53)

I have a test that basically creates strings like this:

{ "1" : "test" }
{ "2" : "test" }
{ "3" : "test" }
...
{ "200" : "test" }

and the test just parses each string using jsonFactory.createParser(is). The test always fail, but if I set jsonFactory.disable(JsonFactory.Feature.CANONICALIZE_FIELD_NAMES); the test succeed.

[pwebbitrs]

We have the same issue. For us, this is quite a critical problem.

I’ve done a bit of analysis on this ( it may not be complete but here it is anyway).

The ByteQuadCanonicalizer has a flag called _needsRehash which determines when they need to size up the internal _names array.

• Prior to adding the offending string via addName, _needsRehash = false. Size of the names is 128 (full) (clearly it does require a rehash)
• In addName() at this point the 2.6.1 ‘fix’ kicks in and sets needRehash = true
• However at the end of this method we have:

this._names[offset >> 2] = name;
++this._count;
this._verifyNeedForRehash();
return name;

_verifyNeedForRehash only serves to flip the rehash flag. And even if it did, it is too late because the array accesor here blows up (first line of code above). This all occurs before an actual rehash can be performed (hence the blow up), so nothing prevents the exception from occuring (certainly not on this code path anyway).

I hope this helps. :)

[tlrx]

@pwebbitrs I came to a similar conclusion: I also tested with 2.7.0-SNAPSHOT with forcing rehash() call in the ̀_verifySharing()` and it also works.

[cowtowncoder]

(apologies for slow response -- I was on vacation for past 2 weeks, just came back now)

@tlrx Thank you for reporting this. Would it be possible to share your test code? Seems like my fix was incomplete and I would like to verify the (new) fix.