Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8054446

Repeated offer and remove on ConcurrentLinkedQueue lead to an OutOfMemoryError

    Details

    • Type: Bug
    • Status: Closed
    • Priority: P3
    • Resolution: Duplicate
    • Affects Version/s: 8u5, 9
    • Fix Version/s: 9
    • Component/s: core-libs
    • Labels:

      Backports

        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.

          Issue Links

            Activity

            webbuggrp Webbug Group created issue -
            mduigou Michael Duigou made changes -
            Field Original Value New Value
            Component/s core-libs [ 10701 ]
            Project Java Incidents [ 10301 ] JDK [ 10100 ]
            Key JI-9013898 JDK-8054446
            Workflow JBS Incident Workflow [ 4743647 ] JBS Workflow [ 4744249 ]
            Affects Version/s 8u5 [ 15804 ]
            Affects Version/s 9 [ 14949 ]
            Affects Version/s 8u5 [ 16305 ]
            Component/s core-libs [ 10300 ]
            mduigou Michael Duigou made changes -
            Subcomponent java.util [ 505 ] java.util [ 216 ]
            mduigou Michael Duigou made changes -
            CPU x86_64 [ 19000 ] generic [ 17008 ]
            mduigou Michael Duigou made changes -
            OS linux_ubuntu [ 17048 ] generic [ 17010 ]
            mduigou Michael Duigou made changes -
            Subcomponent java.util [ 216 ] java.util.concurrent [ 215 ]
            mduigou Michael Duigou made changes -
            Status New [ 10000 ] Open [ 1 ]
            mduigou Michael Duigou made changes -
            Priority P4 [ 4 ] P3 [ 3 ]
            chegar Chris Hegarty made changes -
            Fix Version/s tbd_minor [ 11999 ]
            martin Martin Buchholz made changes -
            Assignee Martin Buchholz [ martin ]
            martin Martin Buchholz made changes -
            Status Open [ 1 ] In Progress [ 3 ]
            Hide
            martin Martin Buchholz added a comment -
            Surprising to me, because significant work has been done over the years to avoid garbage retention.
            Show
            martin Martin Buchholz added a comment - Surprising to me, because significant work has been done over the years to avoid garbage retention.
            Hide
            martin Martin Buchholz added a comment -
            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)
            Show
            martin Martin Buchholz added a comment - 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)
            Hide
            martin Martin Buchholz added a comment -
            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;
                }
            Show
            martin Martin Buchholz added a comment - 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;     }
            martin Martin Buchholz made changes -
            Status In Progress [ 3 ] Open [ 1 ]
            Understanding Fix Understood [ 10001 ]
            Hide
            martin Martin Buchholz added a comment -
            A fix was committed to jsr166 CVS. Feel free to pull into openjdk.
            Show
            martin Martin Buchholz added a comment - A fix was committed to jsr166 CVS. Feel free to pull into openjdk.
            martin Martin Buchholz made changes -
            Status Open [ 1 ] Resolved [ 5 ]
            Understanding Fix Understood [ 10001 ]
            Resolution Duplicate [ 3 ]
            martin Martin Buchholz made changes -
            Link This issue duplicates JDK-8134853 [ JDK-8134853 ]
            Hide
            martin Martin Buchholz added a comment -
            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;
            Show
            martin Martin Buchholz added a comment - 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;
            martin Martin Buchholz made changes -
            Link This issue duplicates JDK-8137184 [ JDK-8137184 ]
            martin Martin Buchholz made changes -
            Link This issue duplicates JDK-8137185 [ JDK-8137185 ]
            Hide
            hgupdate HG Updates added a comment -
            URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/6dd59c01f011
            User: martin
            Date: 2015-10-14 01:19:13 +0000
            Show
            hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/dev/jdk/rev/6dd59c01f011 User: martin Date: 2015-10-14 01:19:13 +0000
            hgupdate HG Updates made changes -
            Resolved In Build team [ 17324 ]
            Fix Version/s 9 [ 14949 ]
            Fix Version/s tbd_minor [ 11999 ]
            Hide
            hgupdate HG Updates added a comment -
            URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/6dd59c01f011
            User: lana
            Date: 2015-10-21 22:17:00 +0000
            Show
            hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/jdk9/jdk/rev/6dd59c01f011 User: lana Date: 2015-10-21 22:17:00 +0000
            hgupdate HG Updates made changes -
            Resolved In Build team [ 17324 ] master [ 18256 ]
            hgupdate HG Updates made changes -
            Resolved In Build master [ 18256 ] b88 [ 17536 ]
            hgupdate HG Updates made changes -
            Link This issue backported by JDK-8142171 [ JDK-8142171 ]
            martin Martin Buchholz made changes -
            Link This issue backported by JDK-8150780 [ JDK-8150780 ]
            jibiche Jibing Chen (Inactive) made changes -
            Status Resolved [ 5 ] Closed [ 6 ]

              People

              • Assignee:
                martin Martin Buchholz
                Reporter:
                webbuggrp Webbug Group
              • Votes:
                0 Vote for this issue
                Watchers:
                5 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: