CompletableFuture#postComplete() can be invoked concurrently?

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

CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
In CompletableFuture, when I invoke the thenApply() on a CompletableFuture Object, 
There is a subtle point in time, and it will make CompletableFuture#postComplete()
invoked concurrently.

    private <V> CompletableFuture<V> uniApplyStage(
        Executor e, Function<? super T,? extends V> f) {
        if (f == null) throw new NullPointerException();
        CompletableFuture<V> d =  new CompletableFuture<V>();
        if (e != null || !d.uniApply(this, f, null)) {
            UniApply<T,V> c = new UniApply<T,V>(e, d, this, f);
            push(c);
            // at this point, this CompletableFuture Object just invoke the completeThrowable(),
            // because the process to execute Supplier throw a exception.
            c.tryFire(SYNC);
        }
        return d;
    }

The thread that invoke c.tryFire(SYNC) and the thread that iovoke completeThrowable() will invoke 
c.tryFire(NESTED) soonly in postComplete() . The important thing is the two "c"  is same Object.

So the two threads can invoke c.tryFire() concurrently, and in some special
timing, the (d = dep) == null check can't work out.

1. The thread that invoke c.tryFire(SYNC) will invoke a.postComplete() in postFire() directly.
2. The thread that iovoke completeThrowable() will not invoke a.postComplete() in postFire(),
    but it will return to the postComplete().

Above two sentence, the two threads will invoke postComplete() on same CompletableFuture object.

I'm afraid I didn't express it clearly. If you don't understand my opinion, just tell me if 
CompletableFuture#postComplete() is designed to invoked concurrently or not?

PS: above code from JDK8, and I think this problem will happen too in newest JDK, if I am right about my opinion.

--------------------------------------------------------------------------------
Regards
Liu

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

Re: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
This code is very tricky and hard to understand.
When studying this, I would only look at latest version of the code.

If you think you've found a bug, you should try to create a repro,
preferably in jsr166 CVS.
You can see some stress tests in the tests e.g look at expensiveTests in
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/test/tck/CompletableFutureTest.java?view=markup

On Sat, Aug 22, 2020 at 8:19 AM Liu via Concurrency-interest
<[hidden email]> wrote:

>
> In CompletableFuture, when I invoke the thenApply() on a CompletableFuture Object,
> There is a subtle point in time, and it will make CompletableFuture#postComplete()
> invoked concurrently.
>
>     private <V> CompletableFuture<V> uniApplyStage(
>         Executor e, Function<? super T,? extends V> f) {
>         if (f == null) throw new NullPointerException();
>         CompletableFuture<V> d =  new CompletableFuture<V>();
>         if (e != null || !d.uniApply(this, f, null)) {
>             UniApply<T,V> c = new UniApply<T,V>(e, d, this, f);
>             push(c);
>             // at this point, this CompletableFuture Object just invoke the completeThrowable(),
>             // because the process to execute Supplier throw a exception.
>             c.tryFire(SYNC);
>         }
>         return d;
>     }
>
> The thread that invoke c.tryFire(SYNC) and the thread that iovoke completeThrowable() will invoke
> c.tryFire(NESTED) soonly in postComplete() . The important thing is the two "c"  is same Object.
>
> So the two threads can invoke c.tryFire() concurrently, and in some special
> timing, the (d = dep) == null check can't work out.
>
> 1. The thread that invoke c.tryFire(SYNC) will invoke a.postComplete() in postFire() directly.
> 2. The thread that iovoke completeThrowable() will not invoke a.postComplete() in postFire(),
>     but it will return to the postComplete().
>
> Above two sentence, the two threads will invoke postComplete() on same CompletableFuture object.
>
> I'm afraid I didn't express it clearly. If you don't understand my opinion, just tell me if
> CompletableFuture#postComplete() is designed to invoked concurrently or not?
>
> PS: above code from JDK8, and I think this problem will happen too in newest JDK, if I am right about my opinion.
>
> --------------------------------------------------------------------------------
> Regards
> Liu
> _______________________________________________
> 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: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
It is kind of difficult to test it, because it all depend on special Thread execution order.
I can't think of the test case temporarily.

Let my opinion simpler.


In JDK15, CompletableFuture.UniApply#tryFire(), I think 
it should be like this:

    @SuppressWarnings("serial")
    static final class UniApply<T,V> extends UniCompletion<T,V> {
        Function<? super T,? extends V> fn;
        UniApply(Executor executor, CompletableFuture<V> dep,
                 CompletableFuture<T> src,
                 Function<? super T,? extends V> fn) {
            super(executor, dep, src); this.fn = fn;
        }
        final CompletableFuture<V> tryFire(int mode) {
            CompletableFuture<V> d; CompletableFuture<T> a;
            Object r; Throwable x; Function<? super T,? extends V> f;
            if ((a = src) == null || (r = a.result) == null
                || (d = dep) == null || (f = fn) == null)
                return null;
            tryComplete: if (d.result == null) {
                if (r instanceof AltResult) {
                    if ((x = ((AltResult)r).ex) != null) {
                        if (!claim())         //before completeThrowable, it should be claimed (this two lines is added by me)
                            return null;
                        d.completeThrowable(x, r);
                        break tryComplete;
                    }
                    r = null;
                }
                try {
                    if (mode <= 0 && !claim())
                        return null;
                    else {
                        @SuppressWarnings("unchecked") T t = (T) r;
                        d.completeValue(f.apply(t));
                    }
                } catch (Throwable ex) {
                    d.completeThrowable(ex);
                }
            }
            src = null; dep = null; fn = null;
            return d.postFire(a, mode);
        }
    }

before completeThrowable, it should be claimed just like following code.
This is mean to avoid two diffrent threads can invoke tryFire on same Object,
and to avoid it will both do the d.completeThrowable(x, r) successfully and do
d.postFire(a, mode) both.

Or you can tell me, Why not need to claim() before d.completeThrowable(x, r).
I suppose it is necessary.


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

Re: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
You may be right, but ... I recall when working on this code myself I
ended up asking the same sorts of questions, and later realizing the
code was correct, but as usual I forget the details.

Current CompletableFuture has no known correctness bugs, so we'd be
reluctant to fix anything here without a repro.
You only need the repro to fail once in a million tries.

You might try changing the code in jsr166 CVS and running the tests,
perhaps repeatedly, perhaps with expensiveTests turned on.

     *   forms.)  The claim() callback suppresses function invocation
     *   if already claimed by another thread.

Looks like claim() is only intended to suppress duplicate runs of a
completion function, which normally only happens on successful
completion of a source future.

On Sat, Aug 22, 2020 at 8:42 PM Liu <[hidden email]> wrote:

>
> It is kind of difficult to test it, because it all depend on special Thread execution order.
> I can't think of the test case temporarily.
>
> Let my opinion simpler.
>
> http://hg.openjdk.java.net/jdk/jdk15/file/d2c6eb3b2c8d/src/java.base/share/classes/java/util/concurrent/CompletableFuture.java#l615
>
> In JDK15, CompletableFuture.UniApply#tryFire(), I think
> it should be like this:
>
>     @SuppressWarnings("serial")
>     static final class UniApply<T,V> extends UniCompletion<T,V> {
>         Function<? super T,? extends V> fn;
>         UniApply(Executor executor, CompletableFuture<V> dep,
>                  CompletableFuture<T> src,
>                  Function<? super T,? extends V> fn) {
>             super(executor, dep, src); this.fn = fn;
>         }
>         final CompletableFuture<V> tryFire(int mode) {
>             CompletableFuture<V> d; CompletableFuture<T> a;
>             Object r; Throwable x; Function<? super T,? extends V> f;
>             if ((a = src) == null || (r = a.result) == null
>                 || (d = dep) == null || (f = fn) == null)
>                 return null;
>             tryComplete: if (d.result == null) {
>                 if (r instanceof AltResult) {
>                     if ((x = ((AltResult)r).ex) != null) {
>                         if (!claim())         //before completeThrowable, it should be claimed (this two lines is added by me)
>                             return null;
>                         d.completeThrowable(x, r);
>                         break tryComplete;
>                     }
>                     r = null;
>                 }
>                 try {
>                     if (mode <= 0 && !claim())
>                         return null;
>                     else {
>                         @SuppressWarnings("unchecked") T t = (T) r;
>                         d.completeValue(f.apply(t));
>                     }
>                 } catch (Throwable ex) {
>                     d.completeThrowable(ex);
>                 }
>             }
>             src = null; dep = null; fn = null;
>             return d.postFire(a, mode);
>         }
>     }
>
> before completeThrowable, it should be claimed just like following code.
> This is mean to avoid two diffrent threads can invoke tryFire on same Object,
> and to avoid it will both do the d.completeThrowable(x, r) successfully and do
> d.postFire(a, mode) both.
>
> Or you can tell me, Why not need to claim() before d.completeThrowable(x, r).
> I suppose it is necessary.
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
In reply to this post by JSR166 Concurrency mailing list
Can you outline a high level outcome of the race vs expected outcome?

Alex

On Sun, 23 Aug 2020, 04:44 Liu via Concurrency-interest, <[hidden email]> wrote:
It is kind of difficult to test it, because it all depend on special Thread execution order.
I can't think of the test case temporarily.

Let my opinion simpler.


In JDK15, CompletableFuture.UniApply#tryFire(), I think 
it should be like this:

    @SuppressWarnings("serial")
    static final class UniApply<T,V> extends UniCompletion<T,V> {
        Function<? super T,? extends V> fn;
        UniApply(Executor executor, CompletableFuture<V> dep,
                 CompletableFuture<T> src,
                 Function<? super T,? extends V> fn) {
            super(executor, dep, src); this.fn = fn;
        }
        final CompletableFuture<V> tryFire(int mode) {
            CompletableFuture<V> d; CompletableFuture<T> a;
            Object r; Throwable x; Function<? super T,? extends V> f;
            if ((a = src) == null || (r = a.result) == null
                || (d = dep) == null || (f = fn) == null)
                return null;
            tryComplete: if (d.result == null) {
                if (r instanceof AltResult) {
                    if ((x = ((AltResult)r).ex) != null) {
                        if (!claim())         //before completeThrowable, it should be claimed (this two lines is added by me)
                            return null;
                        d.completeThrowable(x, r);
                        break tryComplete;
                    }
                    r = null;
                }
                try {
                    if (mode <= 0 && !claim())
                        return null;
                    else {
                        @SuppressWarnings("unchecked") T t = (T) r;
                        d.completeValue(f.apply(t));
                    }
                } catch (Throwable ex) {
                    d.completeThrowable(ex);
                }
            }
            src = null; dep = null; fn = null;
            return d.postFire(a, mode);
        }
    }

before completeThrowable, it should be claimed just like following code.
This is mean to avoid two diffrent threads can invoke tryFire on same Object,
and to avoid it will both do the d.completeThrowable(x, r) successfully and do
d.postFire(a, mode) both.

Or you can tell me, Why not need to claim() before d.completeThrowable(x, r).
I suppose it is necessary.

_______________________________________________
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: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
In my first post, There is the special thread execution order.

high level outcome is:
two thread will invoke CompletableFuture#postComplete() 
on same object concurrently.

expected outcome:
only one thread can invoke CompletableFuture#postComplete()
on a object.

like I said, in CompletableFuture.UniApply#tryFire(),
d.completeThrowable(x, r); and dep = null;
are not a atomic operation. The gap between two codes
may cause high level outcome.

PS:when dep == null, it means current Completion Object
has been done.

PPS: CompletableFuture#postComplete() seems not design to be
invoked on same object.



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

Re: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
     * Method postComplete is called upon completion unless the target
     * is guaranteed not to be observable (i.e., not yet returned or
     * linked). Multiple threads can call postComplete, which

On Sat, Aug 22, 2020 at 11:53 PM Liu <[hidden email]> wrote:

>
> In my first post, There is the special thread execution order.
>
> high level outcome is:
> two thread will invoke CompletableFuture#postComplete()
> on same object concurrently.
>
> expected outcome:
> only one thread can invoke CompletableFuture#postComplete()
> on a object.
>
> like I said, in CompletableFuture.UniApply#tryFire(),
> d.completeThrowable(x, r); and dep = null;
> are not a atomic operation. The gap between two codes
> may cause high level outcome.
>
> PS:when dep == null, it means current Completion Object
> has been done.
>
> PPS: CompletableFuture#postComplete() seems not design to be
> invoked on same object.
>
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
Besides, first need to show reachability of that state.

So you have src.result set. Concurrent invocations of d.completeThrowable vs d.completeValue are possible only if two threads can see different src.result or different src.result.ex.

I don't see a path to reach this necessary condition.

Alex

On Sun, 23 Aug 2020, 08:03 Martin Buchholz, <[hidden email]> wrote:
     * Method postComplete is called upon completion unless the target
     * is guaranteed not to be observable (i.e., not yet returned or
     * linked). Multiple threads can call postComplete, which

On Sat, Aug 22, 2020 at 11:53 PM Liu <[hidden email]> wrote:
>
> In my first post, There is the special thread execution order.
>
> high level outcome is:
> two thread will invoke CompletableFuture#postComplete()
> on same object concurrently.
>
> expected outcome:
> only one thread can invoke CompletableFuture#postComplete()
> on a object.
>
> like I said, in CompletableFuture.UniApply#tryFire(),
> d.completeThrowable(x, r); and dep = null;
> are not a atomic operation. The gap between two codes
> may cause high level outcome.
>
> PS:when dep == null, it means current Completion Object
> has been done.
>
> PPS: CompletableFuture#postComplete() seems not design to be
> invoked on same object.
>
>

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

Re: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list

Thanks to Alex and Martin for pointing out that this case cannot arise. It would be great if we could have full mechanical proofs of such things. People out there occasionally work on these for j.u.c components, but they always lag development by a long time. In the mean time, we should improve internal algorithm documentation.

On 8/23/20 3:09 AM, Alex Otenko via Concurrency-interest wrote:
Besides, first need to show reachability of that state.

So you have src.result set. Concurrent invocations of d.completeThrowable vs d.completeValue are possible only if two threads can see different src.result or different src.result.ex.

I don't see a path to reach this necessary condition.

Alex

On Sun, 23 Aug 2020, 08:03 Martin Buchholz, <[hidden email]> wrote:
     * Method postComplete is called upon completion unless the target
     * is guaranteed not to be observable (i.e., not yet returned or
     * linked). Multiple threads can call postComplete, which

On Sat, Aug 22, 2020 at 11:53 PM Liu <[hidden email]> wrote:
>
> In my first post, There is the special thread execution order.
>
> high level outcome is:
> two thread will invoke CompletableFuture#postComplete()
> on same object concurrently.
>
> expected outcome:
> only one thread can invoke CompletableFuture#postComplete()
> on a object.
>
> like I said, in CompletableFuture.UniApply#tryFire(),
> d.completeThrowable(x, r); and dep = null;
> are not a atomic operation. The gap between two codes
> may cause high level outcome.
>
> PS:when dep == null, it means current Completion Object
> has been done.
>
> PPS: CompletableFuture#postComplete() seems not design to be
> invoked on same object.
>
>

_______________________________________________
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: CompletableFuture#postComplete() can be invoked concurrently?

JSR166 Concurrency mailing list
I think target audience is important. This decides which things need to be said explicitly, and which can be left to be inferred, supposing the target audience can formulate the right questions. 

Say, in this case knowing what a sufficient condition is for this to be impossible, makes the proof very mechanical. But knowing what questions to ask seems to be a prerequisite. (And actually the safety guarantees that I checked the code for, turned out to be documented) 

Alex

On Sun, 23 Aug 2020, 13:41 Doug Lea via Concurrency-interest, <[hidden email]> wrote:

Thanks to Alex and Martin for pointing out that this case cannot arise. It would be great if we could have full mechanical proofs of such things. People out there occasionally work on these for j.u.c components, but they always lag development by a long time. In the mean time, we should improve internal algorithm documentation.

On 8/23/20 3:09 AM, Alex Otenko via Concurrency-interest wrote:
Besides, first need to show reachability of that state.

So you have src.result set. Concurrent invocations of d.completeThrowable vs d.completeValue are possible only if two threads can see different src.result or different src.result.ex.

I don't see a path to reach this necessary condition.

Alex

On Sun, 23 Aug 2020, 08:03 Martin Buchholz, <[hidden email]> wrote:
     * Method postComplete is called upon completion unless the target
     * is guaranteed not to be observable (i.e., not yet returned or
     * linked). Multiple threads can call postComplete, which

On Sat, Aug 22, 2020 at 11:53 PM Liu <[hidden email]> wrote:
>
> In my first post, There is the special thread execution order.
>
> high level outcome is:
> two thread will invoke CompletableFuture#postComplete()
> on same object concurrently.
>
> expected outcome:
> only one thread can invoke CompletableFuture#postComplete()
> on a object.
>
> like I said, in CompletableFuture.UniApply#tryFire(),
> d.completeThrowable(x, r); and dep = null;
> are not a atomic operation. The gap between two codes
> may cause high level outcome.
>
> PS:when dep == null, it means current Completion Object
> has been done.
>
> PPS: CompletableFuture#postComplete() seems not design to be
> invoked on same object.
>
>

_______________________________________________
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

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