#1488 StackOverflowError in Value Pool mechanism

[Jean Schuetz]

StackOverflowError in Value Pool mechanism

Since HSQLDB version 2.3.4 there is a bug in the area of the ValuePoolHashMap which will eventually cause HSQLDB to crash with a StackOverflowError. In our test environment the crash will reproducibly occur after 5 days of continuous operation. In real operational scenarios the occurrence may be more or less frequent depending of the frequency of updates performed on existing table records.

Characteristics:

The occurrence is characterized by a StackOverflowError, with a stack trace of the following constitution:

java.lang.StackOverflowError
at org.hsqldb.map.BaseHashMap.getAccessCountCeiling(Unknown Source)
at org.hsqldb.map.BaseHashMap.clear(Unknown Source)
at org.hsqldb.map.BaseHashMap.reset(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddString(Unknown Source)
...

Several variants of the stack trace are possible, like:

java.lang.StackOverflowError
at org.hsqldb.map.BaseHashMap.getAccessCountCeiling(Unknown Source)
at org.hsqldb.map.BaseHashMap.clear(Unknown Source)
at org.hsqldb.map.BaseHashMap.reset(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddObject(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddObject(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddObject(Unknown Source)
at org.hsqldb.map.ValuePoolHashMap.getOrAddObject(Unknown Source)
...

Further, in theory, the bug may occur in the methods: org.hsqldb.map.ValuePoolHashMap.getOrAddDate, org.hsqldb.map.ValuePoolHashMap.getOrAddDouble.

After the occurrence, HSQLDB will fail to execute any further query through JDBC with the following error:
connection exception: connection failure: java.io.EOFException Code: 08006
A restart of the HSQLDB is required to get it working again. No database corruption was observed after restart.

Analysis:

The ValuePoolHashmap serves as a mechanism of de-duplication to reduce memory usage when the database contains several entries with equal value. For this purpose it provides a number of type specific methods like getOrAddString() or getOrAddInteger() with accept a primitive type value or object value, respectively and returns a unique, singleton object instance with equal value. It’s implementation relies on the bespoke hash map implementation class BaseHashMap, which behavior is modified in ValuePoolHashmap to achieve a cache-like behavior in order to not endlessly keep value objects that are no longer part of the database entries. At the same time the implementation attempts to keep a balance between holding enough value objects for repeated equal values in the database but not waste memory by keeping value objects in the internal hash map that only occur once of few times in the database. This is realized by access counting.

The typical logic of the de-duplication methods consist of computing a hash index based on the value and attempt to find a matching singleton instance, possibly after several re-hashes. If a matching object is found, the method returns that object right away. Otherwise, if no matching value object can be found in the hash map, a size check of the internal index data is performed:

if (hashIndex.elementCount >= threshold)

When this condition holds, an internal re-organization of the hash map is performed, after which the method invokes itself recursively in a repeated attempt to find a matching value object. When the bug occurs, the recursive invocation of the method does still not find a matching value object and the condition hashIndex.elementCount >= threshold still holds, which leads to an endless recursion.

Related:

On 2015-05-29 a similar bug was discovered and reported by Jesse Barnum in the SF forum, which affected the method getOrAddInteger of HSQLDB in the development trunk for version 2.3.4. That similar bug was then reported to be fixed on 2015-05-30 with commit r5476, which made it to the release of version 2.3.4. The commit however only affected the methods getOrAddInteger() and getOrAddLong(). The other methods like getOrAddString(), the culprit of this bug, was not changed.

[Taku]

Does this problem occur only in multithreading?

[Jean Schuetz]

Hi,

from what I see in the HSQLDB code, I believe that the problem can also occur in single-threaded applications. The ValuePoolHashMap methods are proteced and exclusively accessed through the ValuePool class, which uses synchronized access for all calls. Therefore the ValuePoolHashMap will never have concurrent thread aceess and would behave equally in single or multi-threaded applications.

[Fred Toussi]

Fixed and committed to SVN /base/trunk. No recursion should now occur.

Please compile and check.

[geon12]

Hi,
When will it be released?

[Fred Toussi]

The fix for the ValuePool issue is in the snapshot dated July 2017
http://hsqldb.org/repos/org/hsqldb/hsqldb/SNAPSHOT/