On Mon, 9 Jun 2025 16:53:07 GMT, kabutz <d...@openjdk.org> wrote:
>> We logged several bugs on the LinkedBlockingDeque. This aggregates them into
>> a single bug report and PR.
>>
>> 1. LinkedBlockingDeque does not immediately throw InterruptedException in
>> put/take
>>
>> The LinkedBlockingDeque does not behave consistently with other concurrency
>> components. If we call putFirst(), putLast(), takeFirst(), or takeLast()
>> with a thread that is interrupted, it does not immediately throw an
>> InterruptedException, the way that ArrayBlockingQueue and
>> LInkedBlockingQueue does, because instead of lockInterruptibly(), we call
>> lock(). It will only throw an InterruptedException if the queue is full (on
>> put) or empty (on take). Since interruptions are frequently used as a
>> shutdown mechanism, this might prevent code from ever shutting down.
>>
>> 2. LinkedBlockingDeque.clear() should preserve weakly-consistent iterators
>>
>> LinkedBlockingDeque.clear() should preserve weakly-consistent iterators by
>> linking f.prev and f.next back to f, allowing the iterators to continue from
>> the first or last respectively. This would be consistent with how the other
>> node-based weakly consistent queues LinkedBlockingQueue LinkedTransferQueue,
>> ConcurrentLinkedQueue/Deque work.
>>
>> The LBD already supports self-linking, since that is done by the
>> unlinkFirst() and unlinkLast() methods, and the iterators and spliterator
>> thus all support self-linking.
>>
>> This can be fixed very easily by linking both f.prev and f.next back to f.
>>
>> 3. LinkedBlockingDeque offer() creates nodes even if capacity has been
>> reached
>>
>> In the JavaDoc of LinkedBlockingDeque, it states: "Linked nodes are
>> dynamically created upon each insertion unless this would bring the deque
>> above capacity." However, in the current implementation, nodes are always
>> created, even if the deque is full. This is because count is non-volatile,
>> and we only check inside the linkFirst/Last() methods whether the queue is
>> full. At this point we have already locked and have created the Node.
>> Instead, the count could be volatile, and we could check before locking.
>>
>> In the current version, calling offer() on a full LinkedBlockingDeque
>> creates unnecessary objects and contention. Similarly for poll() and peek(),
>> we could exit prior to locking by checking the count field.
>>
>> 4. LinkedBlockingDeque allows us to overflow size with addAll()
>>
>> In LinkedBlockingDeque.addAll() we first build up the chain of nodes and
>> then add that chain in bulk to the existing nodes. We count the nodes in
>> "int n" and then whilst hol...
>
> kabutz has updated the pull request incrementally with one additional commit
> since the last revision:
>
> Whitespace
@kabutz Thanks for the updates, this is really looking good now. I added some
suggestions for edits to avoid a couple of volatile reads, which I think makes
sense for Aarch64-based systems (as we're already updating the code).
src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java line
215:
> 213: // assert lock.isHeldByCurrentThread();
> 214: if (count >= capacity)
> 215: return false;
Suggestion:
int c;
if ((c = count) >= capacity)
return false;
src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java line
225:
> 223: ++count;
> 224: notEmpty.signal();
> 225: return true;
Suggestion:
count = c + 1;
notEmpty.signal();
return true;
src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java line
236:
> 234: // assert lock.isHeldByCurrentThread();
> 235: if (count >= capacity)
> 236: return false;
Suggestion:
int c;
if ((c = count) >= capacity)
return false;
src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java line
246:
> 244: ++count;
> 245: notEmpty.signal();
> 246: return true;
Suggestion:
count = c + 1;
notEmpty.signal();
return true;
test/jdk/java/util/concurrent/tck/LinkedBlockingDequeTest.java line 1967:
> 1965:
> 1966: public void testWeaklyConsistentIterationWithIteratorRemove() {
> 1967: final LinkedBlockingDeque<Item> q = new
> LinkedBlockingDeque<>(15);
@kabutz Would 5 suffice?
-------------
PR Review: https://git.openjdk.org/jdk/pull/24925#pullrequestreview-2912857958
PR Review Comment: https://git.openjdk.org/jdk/pull/24925#discussion_r2137473157
PR Review Comment: https://git.openjdk.org/jdk/pull/24925#discussion_r2137473540
PR Review Comment: https://git.openjdk.org/jdk/pull/24925#discussion_r2137471349
PR Review Comment: https://git.openjdk.org/jdk/pull/24925#discussion_r2137472031
PR Review Comment: https://git.openjdk.org/jdk/pull/24925#discussion_r2137478626
