chaokunyang commented on issue #2367:
URL: https://github.com/apache/fory/issues/2367#issuecomment-3000534056
The behavior of `HashMap` changed significantly in Java 8, which fixed the
classic infinite-loop-on-get issue. It's natural to assume `WeakHashMap` might
have received the same fix. However, that is not the case.
Even in JDK 11, `WeakHashMap` can hang when a `get` is performed
concurrently with unsynchronized `put` operations. Here's the updated analysis
for JDK 11.
### 1. `HashMap` vs. `WeakHashMap` Implementation in JDK 8+
In Java 8, `HashMap` was significantly overhauled:
* **Tree-based Buckets:** Buckets with many collisions are converted from
linked lists to balanced red-black trees, improving performance from O(n) to
O(log n).
* **New Resizing Logic:** The resizing algorithm was rewritten. It no
longer re-hashes and re-inserts each entry one by one. Instead, it cleverly
splits the entries in a bucket into two groups, preserving their relative
order. This new logic is not susceptible to the race condition that created
circular linked lists.
However, **`WeakHashMap` did not receive these updates.** It is a separate
implementation, and in JDK 11 it still uses the older, simpler design of an
array of buckets with simple linked lists for collision resolution.
### 2. The Resizing Logic in JDK 11's `WeakHashMap`
The core of the problem lies in the `transfer` method, which is called when
the map is resized during a `put` operation. The logic in JDK 11's
`WeakHashMap` is functionally identical to the logic in pre-Java-8 `HashMap`
that was known to cause this issue.
A simplified view of the `transfer` method in JDK 11's `WeakHashMap`:
```java
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
for (int j = 0; j < src.length; ++j) {
Entry<K,V> e = src[j];
src[j] = null;
while (e != null) {
Entry<K,V> next = e.next; // (1)
// ... (code to handle cleared weak references)
int i = indexFor(e.hash, dest.length);
e.next = dest[i]; // (2)
dest[i] = e; // (3)
e = next; // (4)
}
}
}
```
This code snippet is the recipe for the race condition.
### 3. Step-by-Step Hang Scenario in JDK 11
The scenario for creating an infinite loop remains the same as in older
`HashMap` versions:
1. **Initial State:** A bucket in the map has a simple linked list of
entries, for example, `Entry A -> Entry B -> null`.
2. **Thread 1 starts resizing:** It calls `put`, which triggers `resize`
and then `transfer`. It begins processing this bucket. It executes line `(1)`,
so its local `next` variable points to `Entry B`. Then, the thread scheduler
pauses Thread 1.
3. **Thread 2 starts and finishes resizing:** Thread 2 also calls `put`,
triggers a resize, and runs the `transfer` method on the *same original table*.
It completes the entire loop for this bucket. Because of how lines `(2)` and
`(3)` work, this operation reverses the list. The new table's bucket now points
to `Entry B -> Entry A -> null`.
4. **Thread 1 resumes:** Thread 1 is completely unaware of what Thread 2
did. It continues from where it was paused.
* It executes line `(2)`: `A.next` is set to what's in the new table's
bucket (which is `null` at this point, as Thread 1's `dest` is its own local
copy). So `A.next` becomes `null`.
* It executes line `(3)`: The new bucket now points to `A`. `dest[i]`
is now `A -> null`.
* It executes line `(4)`: `e` becomes `B` (from its `next` variable
saved in step 2).
* **The loop continues for `B`:**
* `(1)`: Its `next` variable is now `A` (because Thread 2 changed
`B.next` to point to `A`).
* `(2)`: `B.next` is set to the current head of the new bucket, which
is `A`. So now `B.next` points to `A`. **A circular list `B -> A` has been
created.**
* `(3)`: The head of the new bucket becomes `B`. The bucket is now `B
-> A -> B -> A...`.
* `(4)`: `e` becomes `A`.
5. **The `get()` Hang:** The resize is now complete, but the map is in a
corrupted state with a circular list in one of its buckets. When any thread
calls `get()` for a key that maps to this bucket, the `while (e != null)` loop
in the `get` method (as shown in your snippet) will never terminate, causing
the thread to hang.
### Conclusion for JDK 11
The risk is absolutely still present in JDK 11. **`WeakHashMap` is not
thread-safe.** The internal implementation details that prevent `HashMap` from
hanging under concurrent modification were not applied to `WeakHashMap`.
Any concurrent use of `WeakHashMap` where at least one thread is performing
a structural modification (`put`, `remove`, `clear`) without external
synchronization can lead to:
* **Hangs (infinite loops)** on `get` operations.
* Loss of data.
* `ConcurrentModificationException` on iterating views.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
