Use a semaphore instead of NSCondition for -waitUntilFinished.

[toddreed]

NSCondition suffers from the possibility of spurious wakeups and requires a predicate to guard against this; -waitUntilFinished did not do this. Changed implementation to used a semaphore (from libdispatch).

This fixes #134.

[facebook-github-bot]

Thank you for your pull request and welcome to our community. We require contributors to sign our Contributor License Agreement, and we don't seem to have you on file. In order for us to review and merge your code, please sign up at https://code.facebook.com/cla - and if you have received this in error or have any questions, please drop us a line at cla@fb.com. Thanks!

[facebook-github-bot]

Thank you for signing our Contributor License Agreement. We can now accept your code for this (and any) Facebook open source project. Thanks!

[toddreed]

Hmmm, there's probably an issue with this. Whether or not dispatch_release is needed depends on the deployment target. From the documentation of dispatch_release:

If your app is built with a deployment target of OS X v10.8 and later or iOS v6.0 and later, dispatch queues are typically managed by ARC, so you do not need to retain or release the dispatch queues.

Maybe this is needed to conditionally include dealloc:

#if __IPHONE_OS_VERSION_MIN_REQUIRED < __IPHONE_6_0 || __MAC_OS_X_VERSION_MIN_REQUIRED < __MAC_10_8
- (void)dealloc {
    dispatch_release(_completedSemaphore);
}
#endif

[nlutsenko]

There is an issue with this one.
waitUntilFinished should be a no-op if the task is already completed, dependless of how many times it is called.
The previous flow had a check for that around if (self.completed) return, this one doesn't.

I think simply adding lines 433-436 back would solve the problem.

[toddreed]

Ah, good point. Will fix that.

[nlutsenko]

Single piece to fix, but otherwise - looks great.
It might be a good idea also to add a test for the flow I am describing.

[toddreed]

Not entirely sure if the unit test is admissible: couldn't figure out a way to have the unit test fail without hanging without using a timeout. So it's possible that the unit test could fail occasionally in the event the timeout is legitimately exceeded for some reason. Would love to see a better of doing this.

[nlutsenko]

You can use say - diatch_async onto a background thread. Wait for the task there twice and then fulfill a test expectation. In this case - you won't timeout the whole test run, but rather it would fail the single test with timeout.

[nlutsenko]

Haha. Just noticed this. Yup this is great.
Maybe split into a separate test and use XCTestExpectation instead of a semaphore here.

[nlutsenko]

Last piece about the strong vs assign on iOS 5 vs 6, and ready to merge in.
Thanks for adding test!

[nlutsenko]

Perfect! Last piece - squash all the commits into a single one and I'll merge it in!

[nlutsenko]

@toddreed, would love to merge this one in before we do a release, any chance you can squash commits into a single one?

[nlutsenko]

I just realized - this approach isn't going to work if you have multiple threads accessing the same waitUntilFinished before the task is completed, since dispatch_semaphore describes a finite amount of resources.

So something like this would fail:

    BFTaskCompletionSource *taskCompletionSource = [BFTaskCompletionSource taskCompletionSource];
    dispatch_apply(100500, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^(size_t i) {
        [taskCompletionSource.task waitUntilFinished];
        NSLog(@"%d", i);
    });
    [taskCompletionSource trySetResult:nil];

While we could get the dispatch_semaphore_signal to signal all the threads - it still doesn't solve the problem of potential race conditions in the amount of time between if (self.completed) and dispatch_semaphore_wait...

I am currently thinking about potential ways of solving this, but as far as I can understand - it's definetly not dispatch_semaphores.

Another thing to note - I already looked into implementation of this using dispatch_groups, but that solution still doesn't work because of a single comment on the method:

...
 * The result of calling this function from multiple threads simultaneously
 * with the same dispatch group is undefined.
...
long dispatch_group_wait(dispatch_group_t group, dispatch_time_t timeout);

[nlutsenko]

Crazy late nite ideas:

• Add a dispatch_semaphore_signal() straight after wait call. Since we don't really care about thread sleeps after the task is completed - this will make every single thread that is waiting on this wakeup, signal another thread and continue. Sounds like a crazy idea, but I guess it works. The downside is that threads won't going to wakeup all at once, but rather one by one in a series.
• Instead of doing dispatch_semaphore_signal once - do it inside the loop until the value of the dispatch_semaphore_signal call becomes 0, which means that we didn't wake up any thread.

Open to other ideas, something @richardjrossiii mentioned offline with using NSConditionLock (which hopefully doesn't have thread wakeup problem, but can't confirm that).

[toddreed]

The original issue was that -[NSCondition wait] was used without testing that the task was completed, which is necessary as a defence for spurious wakeups. Perhaps using NSCondition is the best solution after all—it just needs the added check. When I reported bug (#134) I had proposed a fix that did this.

Compared to the original NSCondition implementation (before going downing the semaphore path), I'd move the -broadcast call to -setCompleted::

- (BOOL)isCompleted {
    [self.condition lock];
    BOOL completed = _completed;
    [self.condition unlock];
    return completed;
}

- (void)setCompleted:(BOOL)completed {
    [self.condition lock];
    _completed = completed;
    if (_completed) {
        [self.condition broadcast];
    }
    [self.condition unlock];
}

And then:

- (void)waitUntilFinished {
    [self.condition lock];
    while (!_completed) {
        [self.condition wait];
    }
    [self.condition unlock];
}

[richardjrossiii]

I don't think the while loop there works, as there's still a race condition upon spurious wakeup between the condition being checked and waiting again.

I'm going to look into the implementation of NSConditionLock and see if it prevents this problem at all.

[toddreed]

@richardjrossiii I don't think there's a race a condition here. The condition is always checked when the lock is acquired and the _completed instance variable is only set when the lock is acquired. When -wait returns—whether by -signal, -broadcast, or spurious wakeup—the lock is acquired. The implementation follows almost exactly the pattern documented here.

[richardjrossiii]

@toddreed You're right. I had forgotten that NSCondition has both a condition and a mutex internally. The while loop solution should work, for all situations I can think of.

[facebook-github-bot]

@toddreed updated the pull request.

[nlutsenko]

Continuing conversation and implementation in #247