JDK-8054446 : Repeated offer and remove on ConcurrentLinkedQueue lead to an OutOfMemoryError
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util.concurrent
  • Affected Version: 8u5,9
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2014-08-01
  • Updated: 2020-07-28
  • Resolved: 2019-05-20
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 7 JDK 8 JDK 9 Other
7u221Fixed 8u102Fixed 9 b88Fixed openjdk7uFixed
Related Reports
Duplicate :  
Duplicate :  
Duplicate :  
Description
FULL PRODUCT VERSION :
tested on 

java version "1.8.0_05"
Java(TM) SE Runtime Environment (build 1.8.0_05-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.5-b02, mixed mode)

and 

java version "1.6.0_37"
Java(TM) SE Runtime Environment (build 1.6.0_37-b06)
Java HotSpot(TM) 64-Bit Server VM (build 20.12-b01, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
independent of OS

tested on ubuntu :
Linux pc-cap90 3.11.0-24-generic #41-Ubuntu SMP Mon Jun 9 20:36:00 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux

EXTRA RELEVANT SYSTEM CONFIGURATION :
to reproduce easily, small heap is helping (-Xmx4m)

A DESCRIPTION OF THE PROBLEM :
This test case with repeated offer and remove operations on ConcurrentLinkedQueue lead to an OutOfMemory Error.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :

Run the following test :

    // Quick OutOfMemory with -Xmx4m
    public void testOutOfMemory(){
        ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<String>();
        String a="a";
        String b="b";
        queue.offer(a);
        for(int i=0;;i++){
            if(i % 1024 == 0) {
                System.out.println("i = "+i);
            }
            queue.offer(b);
            queue.remove(b);

        }
    }


EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
No OutOfMemoryError.
ACTUAL -
    i = 307200
    i = 308224
    i = 309248
    i = 310272

    java.lang.OutOfMemoryError: Java heap space
                   at java.util.concurrent.ConcurrentLinkedQueue.offer(ConcurrentLinkedQueue.java:274)
                   at TestConcurrentLinkedQueue16.testOutOfMemory



REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
   public void testOutOfMemory(){
        ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<String>();
        String a="a";
        String b="b";
        queue.offer(a);
        for(int i=0;;i++){
            if(i % 1024 == 0) {
                System.out.println("i = "+i);
            }
            queue.offer(b);
            queue.remove(b);

        }
    }
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
When called on the last element of a ConcurrentLinkedQueue with more than 1 element, the remove method nullify the item but the Node object is not unlinked from the list.
After many add/remove the queue structure is : a -> null -> ... -> null -> b
To be garbage collected the Node objects with null item must be unlinked from the list.
They are unlinked only when the queue is iterated or when the head is polled.

The advance() method of the Iterator contains code that skip and unlink nodes with null item :

        private E advance() {
            lastRet = nextNode;
            E x = nextItem;

            Node<E> pred, p;
            if (nextNode == null) {
                p = first();
                pred = null;
            } else {
                pred = nextNode;
                p = succ(nextNode);
            }

            for (;;) {
                if (p == null) {
                    nextNode = null;
                    nextItem = null;
                    return x;
                }
                E item = p.item;
                if (item != null) {
                    nextNode = p;
                    nextItem = item;
                    return x;
                } else {
                    // skip over nulls
                    Node<E> next = succ(p);
                    if (pred != null && next != null)
                        pred.casNext(p, next);
                    p = next;
                }
            }
        }

A fix could be to unlink the Node objects with null items while iterating on the elements in the remove method.


Comments
Regression test for this: http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/jtreg/util/concurrent/ConcurrentLinkedQueue/RemoveLeak.java?view=markup Fix for this appears to be JSR166 CVS commit: revision 1.110 date: 2015/01/16 22:38:54; author: jsr166; state: Exp; lines: +15 -10 fix for 8054446: Repeated offer and remove on ConcurrentLinkedQueue lead to an OutOfMemoryError $ cvs diff -r 1.109 -r 1.110 ./main/java/util/concurrent/ConcurrentLinkedQueue.java Index: ./main/java/util/concurrent/ConcurrentLinkedQueue.java =================================================================== RCS file: /export/home/jsr166/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentLinkedQueue.java,v retrieving revision 1.109 retrieving revision 1.110 diff -u -r1.109 -r1.110 --- ./main/java/util/concurrent/ConcurrentLinkedQueue.java 4 Jan 2015 09:15:11 -0000 1.109 +++ ./main/java/util/concurrent/ConcurrentLinkedQueue.java 16 Jan 2015 22:38:54 -0000 1.110 @@ -447,18 +447,23 @@ */ public boolean remove(Object o) { if (o != null) { - Node<E> pred = null; - for (Node<E> p = first(); p != null; p = succ(p)) { + Node<E> next, pred = null; + for (Node<E> p = first(); p != null; pred = p, p = next) { + boolean removed = false; E item = p.item; - if (item != null && - o.equals(item) && - casItem(p, item, null)) { - Node<E> next = succ(p); - if (pred != null && next != null) - casNext(pred, p, next); - return true; + if (item != null) { + if (!o.equals(item)) { + next = succ(p); + continue; + } + removed = casItem(p, item, null); } - pred = p; + + next = succ(p); + if (pred != null && next != null) // unlink + casNext(pred, p, next); + if (removed) + return true; } } return false;
26-09-2015

A fix was committed to jsr166 CVS. Feel free to pull into openjdk.
16-01-2015

Reporter is correct - remove(Object) will never unlink dead Nodes if only ever the element at the tail is removed. This minor rewrite of remove should fix it: public boolean remove(Object o) { if (o != null) { Node<E> next, pred = null; for (Node<E> p = first(); p != null; pred = p, p = next) { boolean removed = false; next = succ(p); E item = p.item; if (item != null) { if (!o.equals(item)) continue; removed = casItem(p, item, null); } // unlink if (pred != null && next != null) casNext(pred, p, next); if (removed) return true; } } return false; }
16-01-2015

Here's my SSCCE version of the test case: import java.util.concurrent.ConcurrentLinkedQueue; public class CLQOOME { public static void main(String[] args) { ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<String>(); String a="a"; String b="b"; queue.offer(a); for (int i = 0;; i++){ if ((i & ((1 << 15) - 1)) == 0) { System.out.println("i = "+i); } queue.offer(b); queue.remove(b); } } java -Xmx4m -esa -ea CLQOOME i = 0 i = 32768 i = 65536 i = 98304 Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at java.util.concurrent.ConcurrentLinkedQueue.offer(ConcurrentLinkedQueue.java:328)
16-01-2015

Surprising to me, because significant work has been done over the years to avoid garbage retention.
16-01-2015