[concurrency-interest] ConcurrentSkipListMap visibility guarantees

Martin Buchholz martinrb at google.com
Thu Jun 4 00:08:53 EDT 2020


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 <
alexandre.dechampeaux at imc.com> 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 <martinrb at google.com>
> *Date: *Thursday, 4 June 2020 at 12:11 pm
> *To: *Alexandre De Champeaux <alexandre.dechampeaux at imc.com>
> *Cc: *"concurrency-interest at cs.oswego.edu" <
> concurrency-interest at cs.oswego.edu>
> *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 <concurrency-interest at cs.oswego.edu> 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: Image removed by sender. IMC Logo] <https://www.imc.com/us/>
>
> [image: Image removed by sender. F] <https://www.facebook.com/IMCTrading>
>
> [image: Image removed by sender. t] <http://twitter.com/IMCTrading>
>
> [image: Image removed by sender. I]
> <https://www.instagram.com/imctrading/>
>
> [image: Image removed by sender. in]
> <https://www.linkedin.com/company/imc-financial-markets>
>
> *imc.com* <https://www.imc.com/us/>
> ------------------------------
>
> 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
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
> [image: IMC Logo] <https://www.imc.com/us/>
>
> [image: F] <https://www.facebook.com/IMCTrading>
>
> [image: t] <http://twitter.com/IMCTrading>
>
> [image: I] <https://www.instagram.com/imctrading/>
>
> [image: in] <https://www.linkedin.com/company/imc-financial-markets>
>
> *imc.com* <https://www.imc.com/us/>
> ------------------------------
> 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20200603/4eafc2c6/attachment-0001.htm>


More information about the Concurrency-interest mailing list