Query reg a Cache causing OOM in 0.90.3 version

[LogeswaranRamasamy]

#264

This query is regarding this specific OOM which arised due to some Cache issue. We are currently using the 0.90.3 version & facing this issue.

Upon checking it appears the ThreadLocalCache created per iteration was uncleared causing memory retention & eventually OOM. To solve this I tried adapting the latest 0.91.X version jars but it has some issues in LRU Cache Size limit & element removal from Cache(reg which I will share a another issue shortly once I pentest it).

So meanwhile as a immediate workaround, I am planning to solve this issue in 0.90.3 by:

1. Keeping a single instance of XMLConfig through the entire Application lifetime with the defaultSharedFormatCache() itself.//OOM Cause Think it will only cause OOM when we multiple XMLConfig instance each with it's own ThreadLocal filling up memory. If we use just single instance/few instance of XMLConfig throughout application lifetime, OOM will not occur right? Is this fix concrete?

2. Obviously I suspect we cannot use formatCache = DefaultFormatCache() on a shared XML Config as it's not ThreadSafe & will lead to race conditions.

3. We can use formatCache = FormatCache.Dummy but problem is that while processing large/multiple xml of .docx processing, I suspect FormatCache.Dummy might cause slowness in serialisation as it's requires re-computing the XmlDescriptor for every node causing slowness.

So, the viable fix appears to be using a Singleton/few instance of XMLConfig() throughout the entire application lifetime or keep XMLConfig instance based itself for each thread & instead use formatCache = DefaultFormatCache() to Cache only at individual thread level not at application level?

Which is the best solution to address this OOM issue in the 0.90.3 itself as immediate resolution as versions 0.91.X has some LRU Cache Size limit issues.

[pdvrieze]

@LogeswaranRamasamy
The ThreadLocal cache was somewhat ill-conceived and others have also reported issues with it. This is why 0.91.0-RC (and later) have introduced a different cache (LayeredCache) that has a sort of copy, update, merge behaviour that maintains a single cache but doesn't have thread issues. There was no LRU/eviction mechanism either (otherwise there could still be large memory usage).

There have been quite some improvements to the caching mechanism in later versions, including the introduction of a LRU Cache (to avoid infinite cache growth), better cache keys (to avoid duplication), and the layered cache. As such you should consider updating the version. Also because there have been numerous other (significant) speed and memory usage improvements.

As this is the latest release that supports Kotlin 1.8 I've backported the changes to the caching mechanism to a new 0.90.x branch (hopefully for a 0.90.4 release).

[pdvrieze]

Btw. could you explain the size limit issues with LRUCache. I've checked, there is indeed no support to specify the size of the underlying cache (added to dev), I'll put it into 0.90.x as well.

[pdvrieze]

I've tagged 0.90.4 which is a backport (including some ability to specify cache size, and a cache that is per-invocation - rather than not at all as Dummy does). This would be similar to creating multiple formats (the biggest cost for creating a format is the cache). This code is mostly backported from 1.0.0 (although the size specification and per-invocation cache are new).

[LogeswaranRamasamy]

Btw. could you explain the size limit issues with LRUCache. I've checked, there is indeed no support to specify the size of the underlying cache (added to dev), I'll put it into 0.90.x as well.

I have encountered two issues when testing the versions 0.91.x & greater. Inorder to not pollute this thread with multiple issue, have filed them in a separate thread.

#372

[LogeswaranRamasamy]

I've tagged 0.90.4 which is a backport (including some ability to specify cache size, and a cache that is per-invocation - rather than not at all as Dummy does). This would be similar to creating multiple formats (the biggest cost for creating a format is the cache). This code is mostly backported from 1.0.0 (although the size specification and per-invocation cache are new).

@pdvrieze I have tested 0.90.4 & found it's solves the OOM issue hence proceeding with it for immediate resolution.

I have some queries in LRU Cache type alone whether is there any possibility for Layering Cache used in 0.90.4 to overflow/exceed if there are several unique XML Descriptors in the order of 1000's?

[pdvrieze]

The layering cache is ultimately backed by the lru cache, so the cache is be bounded (and I made specifying the size accessible too). While there can be different cache entries for different use sites of the same type this should be much less than before (better keys).

[LogeswaranRamasamy]

Thanks for the clarification closing this issue.

[pdvrieze]

@LogeswaranRamasamy Don't hesitate to open a bug if it does not work correctly or has excessive resource usage.

[LogeswaranRamasamy]

okk sure 👍

[LogeswaranRamasamy]

@pdvrieze I had recently faced an new issue in this actually. In the LRU Caching mechanism used I had faced java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 2048 actually. This issue is reproducible in 1.0.1 as well.

xmlutil LRUCache corruption on re-entrant getOrPut (descriptor-tree caching)

Symptom (for xmlutil 0.90.4)

java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 2048
    at nl.adaptivity.xmlutil.serialization.impl.LRUCache.removeOldestEntry(LRUCache.kt:555)
    at nl.adaptivity.xmlutil.serialization.impl.LRUCache.getOrPut(LRUCache.kt:174)
    at nl.adaptivity.xmlutil.serialization.DefaultFormatCache.lookupDescriptorOrStore$serialization(DefaultFormatCache.kt:165)
    at nl.adaptivity.xmlutil.serialization.LayeredCache$DefaultLayer.lookupDescriptorOrStore$serialization(LayeredCache.kt:184)
    at nl.adaptivity.xmlutil.serialization.structure.XmlDescriptor$Companion.from$serialization(XmlDescriptor.kt:333)
    ... (deserializing a large DOCX word/document.xml)

Affected versions (verified by running the reproducer below)

Version	Result
0.90.3	Not affected — this LRUCache did not exist yet (unbounded map cache)
0.90.4	ArrayIndexOutOfBoundsException: Index -1 in removeOldestEntry (deterministic)
1.0.0	IllegalStateException: Cache size exceeded expected bounds! (same corruption, caught earlier by the enabled check(size <= cacheSize) assertion)
1.0.1	ArrayIndexOutOfBoundsException: Index -1 in removeOldestEntry (deterministic, same as 0.90.4)

LRUCache.removeOldestEntry is byte-for-byte identical between 0.90.4 and 1.0.1, so upgrading 0.90.4 → 1.0.1 does not fix it.

Root cause

DefaultFormatCache.lookupDescriptorOrStore stores descriptors with:

return elemDescCache.getOrPut(key) { defaultValue() }   // defaultValue() builds an XmlDescriptor

Building that XmlDescriptor recursively looks up its child descriptors, i.e. defaultValue()
re-enters getOrPut on the same elemDescCache. But LRUCache.getOrPut captures the target slot
and reads size before invoking defaultValue():

} else if (currentKey == null) {
    if (size >= cacheSize) { removeOldestEntry(); break }
    else {
        val value = defaultValue()               // <-- re-enters getOrPut: inserts/evicts on THIS cache
        setKeyValue(currentPosition, key, value) // <-- currentPosition & size are now STALE
        addEntryToOrderListAsNewest(currentPosition)
        ++size                                   // <-- size can now exceed cacheSize
        return value
    }
}

The re-entrant child inserts mutate the cache (including possibly occupying currentPosition and
advancing size to/over cacheSize) while the parent call is suspended. When the parent resumes it
writes to the stale slot, re-links it as newest, and does ++size on a desynced counter — corrupting
the doubly-linked LRU list and the size counter. A subsequent eviction then executes, in
removeOldestEntry:

val nextOldestPos = getNewer(oldOldest)     // returns DoubledPos(-1) because the list is inconsistent
nextOldestPos.setOlder(DoubledPos(-1))      // -> orderLinks[-1 + OLDER_OFFSET] -> ArrayIndexOutOfBounds: Index -1

A flat (non-re-entrant) getOrPut workload — even 20,000 distinct keys with heavy hash collisions
into a 512-entry cache — never crashes and stays correctly bounded at 512. Only the re-entrant pattern
(which real descriptor-tree building always uses) triggers it.

Reproducer A — Kotlin, in-module (recommended; run as a unit test in the serialization module)

LRUCache is internal, so this runs inside nl.adaptivity.xmlutil.serialization (same as the #372 repro).

import nl.adaptivity.xmlutil.serialization.impl.LRUCache

fun main() {
    val cache = LRUCache<Int, String>(512) // = DefaultFormatCache() default (LayeredCache per-decode layer)
    var next = 0
    fun insert(depth: Int, breadth: Int): String {
        val key = next++
        // Mirrors DefaultFormatCache.lookupDescriptorOrStore: the value-factory passed to getOrPut
        // RE-ENTERS getOrPut on the SAME cache to look up child descriptors.
        return cache.getOrPut(key) {
            if (depth > 0) repeat(breadth) { insert(depth - 1, breadth) }
            "v$key"
        }
    }
    insert(depth = 4, breadth = 8) // ~4681 nested lookups >> 512 -> eviction fires mid-re-entrancy
    // -> ArrayIndexOutOfBoundsException: Index -1 in removeOldestEntry (0.90.4 / 1.0.1)
    //    or IllegalStateException "Cache size exceeded expected bounds!" (1.0.0)
}

Also crashes at tiny sizes — e.g. LRUCache<Int,String>(2) with insert(depth = 3, breadth = 3)
(16 nested lookups) → Index -1 out of bounds for length 8.

Reproducer B — Java, against the published jar (no xmlutil source needed)

Uses reflection because LRUCache is internal; getOrPut's second parameter is
kotlin.jvm.functions.Function0, which a Java lambda satisfies directly.
Classpath: serialization-jvm-<ver>.jar + its core-jvm(common)-<ver>.jar + kotlin-stdlib.jar.

import java.lang.reflect.*;
import kotlin.jvm.functions.Function0;

public class ReproGetOrPut {
    static Method getOrPut; static Object cache; static int nextId = 0;

    static Object insert(final int depth, final int breadth) {
        final int myKey = nextId++;
        Function0<Object> dv = () -> {
            if (depth > 0) for (int i = 0; i < breadth; i++) insert(depth - 1, breadth);
            return "v" + myKey;
        };
        try { return getOrPut.invoke(cache, Integer.valueOf(myKey), dv); }
        catch (InvocationTargetException e) {
            Throwable c = e.getCause() != null ? e.getCause() : e;
            if (c instanceof RuntimeException) throw (RuntimeException) c;
            if (c instanceof Error) throw (Error) c;
            throw new RuntimeException(c);
        } catch (Exception e) { throw new RuntimeException(e); }
    }

    public static void main(String[] args) throws Exception {
        Class<?> lru = Class.forName("nl.adaptivity.xmlutil.serialization.impl.LRUCache");
        Constructor<?> ctor = lru.getConstructor(int.class, float.class);
        getOrPut = lru.getMethod("getOrPut", Object.class, Function0.class);
        cache = ctor.newInstance(512, 0.5f);
        insert(4, 8); // -> ArrayIndexOutOfBoundsException: Index -1 in removeOldestEntry
    }
}

Possible Workaround I thought of:

I thought that the Layered Cache(ThreadSafe) will have the option to set Cache Size but unfortunately could not find any. There is option to set Cache Size using DefaultFormatCache with LRUCache.cacheSize but doing so will create a Cache per thread & not shared Cache across all the threads right?

There is PerSerializationFormatCache but it reconstructs Cache on every serialisation which eventually defeats the purpose of Cache reuse across Threads. So, is there any option to config the Cache size for Layered Cache(ThreadSafe) option actually instead of caching per thread?

[pdvrieze]

I've updated getOrPut in the dev branch. It now allows for re-entry and will no longer assume that there are no changes caused by calculating the value.

[LogeswaranRamasamy]

Nice. Will the fix be pushed to 0.90.4 version also ?

Also, is there any possible workaround for the same?

Possible Workaround I thought of:
I thought that the Layered Cache(ThreadSafe) will have the option to set Cache Size but unfortunately could not find any. There is option to set Cache Size using DefaultFormatCache with LRUCache.cacheSize but doing so will create a Cache per thread & not shared Cache across all the threads right?

There is PerSerializationFormatCache but it reconstructs Cache on every serialisation which eventually defeats the purpose of Cache reuse across Threads. So, is there any option to config the Cache size for Layered Cache(ThreadSafe) option actually instead of caching per thread?