ConcurrentSkipListMap visibility guarantees

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

ConcurrentSkipListMap visibility guarantees

JSR166 Concurrency mailing list

Hello concurrency interest,

 

I just came across some old code that concurrently does the following:

  1. Remove Object o from ConcurrentSkipListMap
  2. Mutate Object o
  3. Add Object o back

Sometimes, the remove will fail.

 

I was wondering how badly this is abusing the guarantees of ConcurrentSkipListMap, and what makes the remove fail?

 

Here is some code that reproduces (tried with Java 8u241 and 13.0.2):

 

 

public class ConcurrentSkipListMapMissingRemove {

    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();

    private final static Comparator<DummyTimer> myTimerComparator = Comparator.comparing(DummyTimer::getSequence);

    private final static ConcurrentSkipListMap<DummyTimer, Long> theTimers = new ConcurrentSkipListMap<>(myTimerComparator);

 

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 10; ++i) {

            CompletableFuture.runAsync(() -> {

                DummyTimer myDummyTimer = new DummyTimer();

                myDummyTimer.start();

 

                while (true) {

                    myDummyTimer.restart();

                }

            });

        }

 

        Thread.sleep(100_000_000);

    }

 

    private static class DummyTimer {

        private volatile long theSequence;

 

        void start() {

            add();

        }

 

        void restart() {

            remove();

            theSequence = SEQUENCE_CREATOR.getAndIncrement();

            add();

        }

 

        private void add() {

            theTimers.put(this, theSequence);

        }

 

        private void remove() {

            if (theTimers.remove(this) == null) {

                System.out.println("Ooops, failed to remove...");

            }

        }

 

        public long getSequence() {

            return theSequence;

        }

    }

}

 

Thanks,

 

Alex

IMC Logo

F

t

I

in

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.

It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentSkipListMap visibility guarantees

JSR166 Concurrency mailing list
DummyTimer has no constructor, so they are all created with a sequence of zero, so initially they compare equal, so the map considers them equivalent, and so the initial add may fail.

On Wed, Jun 3, 2020 at 6:00 PM Alexandre De Champeaux via Concurrency-interest <[hidden email]> wrote:

Hello concurrency interest,

 

I just came across some old code that concurrently does the following:

  1. Remove Object o from ConcurrentSkipListMap
  2. Mutate Object o
  3. Add Object o back

Sometimes, the remove will fail.

 

I was wondering how badly this is abusing the guarantees of ConcurrentSkipListMap, and what makes the remove fail?

 

Here is some code that reproduces (tried with Java 8u241 and 13.0.2):

 

 

public class ConcurrentSkipListMapMissingRemove {

    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();

    private final static Comparator<DummyTimer> myTimerComparator = Comparator.comparing(DummyTimer::getSequence);

    private final static ConcurrentSkipListMap<DummyTimer, Long> theTimers = new ConcurrentSkipListMap<>(myTimerComparator);

 

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 10; ++i) {

            CompletableFuture.runAsync(() -> {

                DummyTimer myDummyTimer = new DummyTimer();

                myDummyTimer.start();

 

                while (true) {

                    myDummyTimer.restart();

                }

            });

        }

 

        Thread.sleep(100_000_000);

    }

 

    private static class DummyTimer {

        private volatile long theSequence;

 

        void start() {

            add();

        }

 

        void restart() {

            remove();

            theSequence = SEQUENCE_CREATOR.getAndIncrement();

            add();

        }

 

        private void add() {

            theTimers.put(this, theSequence);

        }

 

        private void remove() {

            if (theTimers.remove(this) == null) {

                System.out.println("Ooops, failed to remove...");

            }

        }

 

        public long getSequence() {

            return theSequence;

        }

    }

}

 

Thanks,

 

Alex

IMC Logo

F

t

I

in

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.

It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentSkipListMap visibility guarantees

JSR166 Concurrency mailing list

Ah yes, I dumbed down the example too much…

 

Here it is again (But now with theSequence being updated inside add):

 

public class ConcurrentSkipListMapMissingRemove {

    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();

    private final static Comparator<DummyTimer> COMPARATOR = Comparator.comparing(DummyTimer::getSequence);

    private final static ConcurrentSkipListMap<DummyTimer, Long> TIMERS = new ConcurrentSkipListMap<>(COMPARATOR);

 

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 10; ++i) {

            CompletableFuture.runAsync(() -> {

                DummyTimer myDummyTimer = new DummyTimer();

                myDummyTimer.start();

 

                while (true) {

                    myDummyTimer.restart();

                }

            });

        }

 

        Thread.sleep(100_000_000);

    }

 

    private static class DummyTimer {

        private volatile long theSequence;

 

        void start() {

            add();

        }

 

        void restart() {

            remove();

            add();

        }

 

        private void add() {

            theSequence = SEQUENCE_CREATOR.getAndIncrement();

            TIMERS.put(this, theSequence);

        }

 

        private void remove() {

            if (TIMERS.remove(this) == null) {

                System.out.println("Ooops, failed to remove...");

            }

        }

 

        public long getSequence() {

            return theSequence;

        }

    }

}

 

From: Martin Buchholz <[hidden email]>
Date: Thursday, 4 June 2020 at 12:11 pm
To: Alexandre De Champeaux <[hidden email]>
Cc: "[hidden email]" <[hidden email]>
Subject: Re: [concurrency-interest] ConcurrentSkipListMap visibility guarantees

 

DummyTimer has no constructor, so they are all created with a sequence of zero, so initially they compare equal, so the map considers them equivalent, and so the initial add may fail.

 

On Wed, Jun 3, 2020 at 6:00 PM Alexandre De Champeaux via Concurrency-interest <[hidden email]> wrote:

Hello concurrency interest,

 

I just came across some old code that concurrently does the following:

  1. Remove Object o from ConcurrentSkipListMap
  2. Mutate Object o
  3. Add Object o back

Sometimes, the remove will fail.

 

I was wondering how badly this is abusing the guarantees of ConcurrentSkipListMap, and what makes the remove fail?

 

Here is some code that reproduces (tried with Java 8u241 and 13.0.2):

 

 

public class ConcurrentSkipListMapMissingRemove {

    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();

    private final static Comparator<DummyTimer> myTimerComparator = Comparator.comparing(DummyTimer::getSequence);

    private final static ConcurrentSkipListMap<DummyTimer, Long> theTimers = new ConcurrentSkipListMap<>(myTimerComparator);

 

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 10; ++i) {

            CompletableFuture.runAsync(() -> {

                DummyTimer myDummyTimer = new DummyTimer();

                myDummyTimer.start();

 

                while (true) {

                    myDummyTimer.restart();

                }

            });

        }

 

        Thread.sleep(100_000_000);

    }

 

    private static class DummyTimer {

        private volatile long theSequence;

 

        void start() {

            add();

        }

 

        void restart() {

            remove();

            theSequence = SEQUENCE_CREATOR.getAndIncrement();

            add();

        }

 

        private void add() {

            theTimers.put(this, theSequence);

        }

 

        private void remove() {

            if (theTimers.remove(this) == null) {

                System.out.println("Ooops, failed to remove...");

            }

        }

 

        public long getSequence() {

            return theSequence;

        }

    }

}

 

Thanks,

 

Alex

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.


It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

IMC Logo

F

t

I

in

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.

It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentSkipListMap visibility guarantees

JSR166 Concurrency mailing list
The comparator is called with two keys in the map.  Even normally, the map has to deal with the possibility of a key being asynchronously removed while the comparator is running.  But it's really too much to expect that the map will be able to sanely handle the value of the key changing and being reinserted elsewhere in the map while the comparator is running.

Another way to look at it is that a key might be in use by a comparator for an arbitrarily long time after it has been removed, so the key object can never be mutated and reused.

On Wed, Jun 3, 2020 at 8:23 PM Alexandre De Champeaux <[hidden email]> wrote:

Ah yes, I dumbed down the example too much…

 

Here it is again (But now with theSequence being updated inside add):

 

public class ConcurrentSkipListMapMissingRemove {

    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();

    private final static Comparator<DummyTimer> COMPARATOR = Comparator.comparing(DummyTimer::getSequence);

    private final static ConcurrentSkipListMap<DummyTimer, Long> TIMERS = new ConcurrentSkipListMap<>(COMPARATOR);

 

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 10; ++i) {

            CompletableFuture.runAsync(() -> {

                DummyTimer myDummyTimer = new DummyTimer();

                myDummyTimer.start();

 

                while (true) {

                    myDummyTimer.restart();

                }

            });

        }

 

        Thread.sleep(100_000_000);

    }

 

    private static class DummyTimer {

        private volatile long theSequence;

 

        void start() {

            add();

        }

 

        void restart() {

            remove();

            add();

        }

 

        private void add() {

            theSequence = SEQUENCE_CREATOR.getAndIncrement();

            TIMERS.put(this, theSequence);

        }

 

        private void remove() {

            if (TIMERS.remove(this) == null) {

                System.out.println("Ooops, failed to remove...");

            }

        }

 

        public long getSequence() {

            return theSequence;

        }

    }

}

 

From: Martin Buchholz <[hidden email]>
Date: Thursday, 4 June 2020 at 12:11 pm
To: Alexandre De Champeaux <[hidden email]>
Cc: "[hidden email]" <[hidden email]>
Subject: Re: [concurrency-interest] ConcurrentSkipListMap visibility guarantees

 

DummyTimer has no constructor, so they are all created with a sequence of zero, so initially they compare equal, so the map considers them equivalent, and so the initial add may fail.

 

On Wed, Jun 3, 2020 at 6:00 PM Alexandre De Champeaux via Concurrency-interest <[hidden email]> wrote:

Hello concurrency interest,

 

I just came across some old code that concurrently does the following:

  1. Remove Object o from ConcurrentSkipListMap
  2. Mutate Object o
  3. Add Object o back

Sometimes, the remove will fail.

 

I was wondering how badly this is abusing the guarantees of ConcurrentSkipListMap, and what makes the remove fail?

 

Here is some code that reproduces (tried with Java 8u241 and 13.0.2):

 

 

public class ConcurrentSkipListMapMissingRemove {

    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();

    private final static Comparator<DummyTimer> myTimerComparator = Comparator.comparing(DummyTimer::getSequence);

    private final static ConcurrentSkipListMap<DummyTimer, Long> theTimers = new ConcurrentSkipListMap<>(myTimerComparator);

 

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 10; ++i) {

            CompletableFuture.runAsync(() -> {

                DummyTimer myDummyTimer = new DummyTimer();

                myDummyTimer.start();

 

                while (true) {

                    myDummyTimer.restart();

                }

            });

        }

 

        Thread.sleep(100_000_000);

    }

 

    private static class DummyTimer {

        private volatile long theSequence;

 

        void start() {

            add();

        }

 

        void restart() {

            remove();

            theSequence = SEQUENCE_CREATOR.getAndIncrement();

            add();

        }

 

        private void add() {

            theTimers.put(this, theSequence);

        }

 

        private void remove() {

            if (theTimers.remove(this) == null) {

                System.out.println("Ooops, failed to remove...");

            }

        }

 

        public long getSequence() {

            return theSequence;

        }

    }

}

 

Thanks,

 

Alex

Image removed by sender. IMC Logo

Image removed by sender. F

Image removed by sender. t

Image removed by sender. I

Image removed by sender. in

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.


It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

IMC Logo

F

t

I

in

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.

It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentSkipListMap visibility guarantees

JSR166 Concurrency mailing list

Thanks for the quick reply Martin.

 

That does sound pretty fair.

 

From: Martin Buchholz <[hidden email]>
Date: Thursday, 4 June 2020 at 2:09 pm
To: Alexandre De Champeaux <[hidden email]>
Cc: "[hidden email]" <[hidden email]>
Subject: Re: [concurrency-interest] ConcurrentSkipListMap visibility guarantees

 

The comparator is called with two keys in the map.  Even normally, the map has to deal with the possibility of a key being asynchronously removed while the comparator is running.  But it's really too much to expect that the map will be able to sanely handle the value of the key changing and being reinserted elsewhere in the map while the comparator is running.

 

Another way to look at it is that a key might be in use by a comparator for an arbitrarily long time after it has been removed, so the key object can never be mutated and reused.

 

On Wed, Jun 3, 2020 at 8:23 PM Alexandre De Champeaux <[hidden email]> wrote:

Ah yes, I dumbed down the example too much…

 

Here it is again (But now with theSequence being updated inside add):

 

public class ConcurrentSkipListMapMissingRemove {

    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();

    private final static Comparator<DummyTimer> COMPARATOR = Comparator.comparing(DummyTimer::getSequence);

    private final static ConcurrentSkipListMap<DummyTimer, Long> TIMERS = new ConcurrentSkipListMap<>(COMPARATOR);

 

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 10; ++i) {

            CompletableFuture.runAsync(() -> {

                DummyTimer myDummyTimer = new DummyTimer();

                myDummyTimer.start();

 

                while (true) {

                    myDummyTimer.restart();

                }

            });

        }

 

        Thread.sleep(100_000_000);

    }

 

    private static class DummyTimer {

        private volatile long theSequence;

 

        void start() {

            add();

        }

 

        void restart() {

            remove();

            add();

        }

 

        private void add() {

            theSequence = SEQUENCE_CREATOR.getAndIncrement();

            TIMERS.put(this, theSequence);

        }

 

        private void remove() {

            if (TIMERS.remove(this) == null) {

                System.out.println("Ooops, failed to remove...");

            }

        }

 

        public long getSequence() {

            return theSequence;

        }

    }

}

 

From: Martin Buchholz <[hidden email]>
Date: Thursday, 4 June 2020 at 12:11 pm
To: Alexandre De Champeaux <[hidden email]>
Cc: "[hidden email]" <[hidden email]>
Subject: Re: [concurrency-interest] ConcurrentSkipListMap visibility guarantees

 

DummyTimer has no constructor, so they are all created with a sequence of zero, so initially they compare equal, so the map considers them equivalent, and so the initial add may fail.

 

On Wed, Jun 3, 2020 at 6:00 PM Alexandre De Champeaux via Concurrency-interest <[hidden email]> wrote:

Hello concurrency interest,

 

I just came across some old code that concurrently does the following:

  1. Remove Object o from ConcurrentSkipListMap
  2. Mutate Object o
  3. Add Object o back

Sometimes, the remove will fail.

 

I was wondering how badly this is abusing the guarantees of ConcurrentSkipListMap, and what makes the remove fail?

 

Here is some code that reproduces (tried with Java 8u241 and 13.0.2):

 

 

public class ConcurrentSkipListMapMissingRemove {

    private final static AtomicLong SEQUENCE_CREATOR = new AtomicLong();

    private final static Comparator<DummyTimer> myTimerComparator = Comparator.comparing(DummyTimer::getSequence);

    private final static ConcurrentSkipListMap<DummyTimer, Long> theTimers = new ConcurrentSkipListMap<>(myTimerComparator);

 

    public static void main(String[] args) throws InterruptedException {

        for (int i = 0; i < 10; ++i) {

            CompletableFuture.runAsync(() -> {

                DummyTimer myDummyTimer = new DummyTimer();

                myDummyTimer.start();

 

                while (true) {

                    myDummyTimer.restart();

                }

            });

        }

 

        Thread.sleep(100_000_000);

    }

 

    private static class DummyTimer {

        private volatile long theSequence;

 

        void start() {

            add();

        }

 

        void restart() {

            remove();

            theSequence = SEQUENCE_CREATOR.getAndIncrement();

            add();

        }

 

        private void add() {

            theTimers.put(this, theSequence);

        }

 

        private void remove() {

            if (theTimers.remove(this) == null) {

                System.out.println("Ooops, failed to remove...");

            }

        }

 

        public long getSequence() {

            return theSequence;

        }

    }

}

 

Thanks,

 

Alex

Error! Filename not specified.

Error! Filename not specified.

Error! Filename not specified.

Error! Filename not specified.

Error! Filename not specified.

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.


It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.


It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.

IMC Logo

F

t

I

in

imc.com


The information in this e-mail is intended only for the person or entity to which it is addressed.

It may contain confidential and /or privileged material. If you are not the intended recipient, please notify us immediately and delete it from your system. Any other use or disclosure by you, including through automated tools operating on your systems is prohibited.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest