Ensure consistent value count in ConcurrentReferenceHashMap#Segment

[nihongye]

Affects: <Spring Framework version>

---

affected versions：all

Background

We have a application where the jvm meta space periodically fluctuates significantly, as shown in the following screenshot.

After analyzing the heap space, we found a large number(200000+) of sun.reflect.DelegatingClassLoader and sun.reflect.GeneratedSerializationConstructorAccessor, which are mainly generated for org.springframework.data.redis.connection.jedis.JedisConnection$$EnhancerBySpringCGLIB$$xxxxx, because the application dynamically uses the ProxyFactory to generate proxy objects.
Further analysis revealed that the segment of the ConcurrentReferenceMap associated with org.springframework.data.redis.connection.jedis.JedisConnection$$EnhancerBySpringCGLIB$$xxxxx has a count of 0, but actually contains 1 Entry, as shown below screenshot.

In the org.springframework.util.ConcurrentReferenceHashMap.Segment#getReference method, if the count is 0, it returns null.

Therefore, the org.springframework.objenesis.SpringObjenesis#cache method for the key "org.springframework.data.redis.connection.jedis.JedisConnection$$EnhancerBySpringCGLIB$$xxxxx" is ineffective, leading to the creation of a large number of sun.reflect.GeneratedSerializationConstructorAccessor repeatedly.

Why does the ConcurrentReferenceHashMap.Segment has this problem?

We have tried to reproduce the problem, as shown in the demo code
conrefmap-demo.tgz,
and it seems that the remove operation caused the problem, but there is no remove operation in the phenomenon described earlier，the org.springframework.objenesis.SpringObjenesis just invoke get and putIfAbsent.
We cannot confirm the reason for the count being less than the actual number of entries, but we speculate on the following possibilities:

• First: in the restructure method, copy the reference, generate multiple references for same key, and some old references also have the opportunity to enter the ReferenceQueue（for example getReference has the old Reference，so may cause old Reference have the opportunity to enter the ReferenceQueue）.
• Second: when resizing, both arrays reference new and old reference, and the old references array are replaced only after the restructuring is completed. The old reference may be added to the ReferenceQueue by the garbage collector, and later, new reference are also added to the ReferenceQueue.
• Third: mysterious multi-threading issues.

Regardless of the reason, we only need to ensure that the count is equal to the actual number of entries containing references to fix the problem.

[bclozel]

Thanks @nihongye for the detailed report. I think I understand what's going on here, although writing a test for this would be really challenging.

I think the issue is in the org.springframework.util.ConcurrentReferenceHashMap.Segment#restructure method. When conditions are met, this method will be called to purge elements from the segment that have been added to the queue by the garbage collector. Indeed, we need to remove References from the segments that no longer hold a valid entry.

Example

Let's use an example where a given Segment holds 10 Reference instances "element01"..."element10".
Now consider that 3 elements have been queued for removal by the GC. The restructure() method collects them first:

spring-framework/spring-core/src/main/java/org/springframework/util/ConcurrentReferenceHashMap.java

Lines 585 to 592 in 1e7e532

	Set<Reference<K, V>> toPurge = Collections.emptySet();
	if (ref != null) {
	toPurge = new HashSet<>();
	while (ref != null) {
	toPurge.add(ref);
	ref = this.referenceManager.pollForPurge();
	}
	}

Then it predicts the element count in the segment once the restructure operation is done:

spring-framework/spring-core/src/main/java/org/springframework/util/ConcurrentReferenceHashMap.java

Line 593 in 1e7e532

countAfterRestructure -= toPurge.size();

Later, we effectively restructure entries and only add them if they're not in the toPurge set and the referenced entry is not null. At this point we can effectively remove more than 3 elements from the Segment, but the counter will decrease by 3.

spring-framework/spring-core/src/main/java/org/springframework/util/ConcurrentReferenceHashMap.java

Lines 610 to 626 in 1e7e532

	for (int i = 0; i < this.references.length; i++) {
	ref = this.references[i];
	if (!resizing) {
	restructured[i] = null;
	}
	while (ref != null) {
	if (!toPurge.contains(ref)) {
	Entry<K, V> entry = ref.get();
	if (entry != null) {
	int index = getIndex(ref.getHash(), restructured);
	restructured[index] = this.referenceManager.createReference(
	entry, ref.getHash(), restructured[index]);
	}
	}
	ref = ref.getNext();
	}
	}

I think the key issue is this: while the segment itself is locked, the GC can still collect references and make entries as null. It could be that new elements were marked as nulls and will be removed during the restructure operation. This means that the count can be higher than the actual number of elements.

From there, other inconsistencies can happen, as the GC'd elements are guaranteed to be queued and will be considered in a later restructure() call. The count should be eventually consistent, but as you have seen several operations are skipped if the current count is 0 (including removals). I think the combination of the two can make the count invalid, at least temporarily. I haven't figured out an exact scenario but I think this could explain it.

Possible fix

To fix this inconsistency, we can:

1. not use the toPurge size to recalculate the count, but the actual count of removed entries. This is still a bit inconsistent, as we're removing more entries that we initially polled from the queue and the size calculations are somewhat wrong.
2. only remove the entries that are listed in the toPurge Set and possibly leave null entries in the Segment. They will be later removed during a later restructure() call. I have benchmarked this solution and results are similar.

I am tempted to apply the second solution to the 6.0.x and 6.1.x branches, given we receive enough feedback about this change. At this point, a 5.3.x backport is unlikely as this is the first report for such an issue.

@nihongye would you consider testing a 6.0.14-SNAPSHOT version with your production scenario (so, not using the repro project) and report back with the results? The release is scheduled on November 15th at the moment.

[nihongye]

@bclozel
Regarding "the count can be higher than the actual number of elements, The count should be eventually consistent", I think we should be consistent. This is the inevitable result of ConcurrentReferenceHashMap relying on Reference, and it is acceptable.

As for the reason why count is smaller than the actual number of elements, I would like to do another logical reasoning, which will help us understand this problem:

Only the new key causes count+1, and only the restructure process gets the Reference from the ReferenceQueue, causing the number to decrease; so we can infer that these Purged References contain at least one pair pointing to the same key.

Regarding the fix

"we only need to ensure that the count is greater than the actual number,The count should be eventually consistent". In my original PullRequest, this can be guaranteed.

For test

This problem occurred in one of our customer's production applications. It happened very accidentally. Already suggested to remove the dynamic use of ProxyFactory, so new fixes cannot be retested on previous scenarios application.

[bclozel]

Thanks for the update @nihongye

Only the new key causes count+1, and only the restructure process gets the Reference from the ReferenceQueue, causing the number to decrease; so we can infer that these Purged References contain at least one pair pointing to the same key.

I'm not sure I understand . How would that relate to the use case for your customer? This would only reproduce this if the use code is calling remove (which is not the case apparently?). Also, this would mean that we can get duplicate values for the same key in the reference list, but I don't see how this can happen given that we lock the entire segment:

spring-framework/spring-core/src/main/java/org/springframework/util/ConcurrentReferenceHashMap.java

Lines 524 to 540 in 1e7e532

	lock();
	try {
	final int index = getIndex(hash, this.references);
	final Reference<K, V> head = this.references[index];
	Reference<K, V> ref = findInChain(head, key, hash);
	Entry<K, V> entry = (ref != null ? ref.get() : null);
	Entries<V> entries = value -> {
	@SuppressWarnings("unchecked")
	Entry<K, V> newEntry = new Entry<>((K) key, value);
	Reference<K, V> newReference = Segment.this.referenceManager.createReference(newEntry, hash, head);
	Segment.this.references[index] = newReference;
	Segment.this.count.incrementAndGet();
	};
	return task.execute(ref, entry, entries);
	}
	finally {
	unlock();

"we only need to ensure that the count is greater than the actual number,The count should be eventually consistent". In my original PullRequest, this can be guaranteed.

I have looked at your PR and unfortunately it suffers from two issues:

• this adds another complete iteration over all values, which decreases performance
• because it happens before the actual restructure operations, there are still chances that the GC collects entries and we remove more than expected. The window of opportunity for this is reduced but it's still possible

This problem occurred in one of our customer's production applications. It happened very accidentally. Already suggested to remove the dynamic use of ProxyFactory, so new fixes cannot be retested on previous scenarios application.

Since there is no way for us to experiment with the fix, I'll schedule this for 6.1 and we might consider backports in the future if we get new reports for this.