NSOperationQueue bug with dependencies

Question

I am using NSOperation and NSOperationQueue for performing a sequence of operations, all dependent on each other (2 on 1, 3 on 2, etc...). I set the dependency after I create the operations. I am encountering problems when the queue completes: the program crashes in the _release part of the code, apparently when the NSOperations are getting released. Note that they all get released at the end by the queue, because it is only after the very last one which depends on the second last one, which depends on etc... that they can be released. If I remove any dependency, the code runs fine. If I change waitUntilFinished: to NO, it crashes, if it is YES, it does not.

I have isolated the problem to the following code which does not use any of my custom classes. NSOperation by default is a class that does absolutely nothing. Yet, this still crashes when all operations have completed. Therefore, it appears I am not using NSOperationQueue properly but can't see what is wrong. I am running on 10.9 and I have noticed that in general Maverick 10.9 is much more sensitive to these issues than 10.8.

I call this method from the main Thread with a Menu item:

- (void) testOperations:(id)object  
{

        NSOperationQueue* queue = [ [ NSOperationQueue alloc ] init ];

        NSMutableArray* array = [ NSMutableArray array ];
        for ( int i = 0; i < 10000; i++)
            [ array addObject: [[[ NSOperation alloc ] init ] autorelease ] ];

        for ( int i = 1; i < [ array count ]; i++)
            [[ array objectAtIndex:i ] addDependency:[array objectAtIndex:i-1]]; // remove this and no crash

        [ queue addOperations: array waitUntilFinished:NO ]; // Change to YES, no crash
        [ queue autorelease ]; // or release, it does not make a difference, in fact leaking the memory makes no difference: the code crashes when the queue is removing the NSOperations
}

This will crash every single time with: bool objc::DenseMapBase >, objc_object*, unsigned long, objc::DenseMapInfo, true>: (EXC_BAD_ACCESS)

The full stack is:

#0  0x9104d81b in objc::DenseMapBase<objc::DenseMap<objc_object*, unsigned long, true, objc::DenseMapInfo<objc_object*> >, objc_object*, unsigned long, objc::DenseMapInfo<objc_object*>, true>::find(objc_object* const&) ()
#1  0x910384e3 in _objc_rootReleaseWasZero ()
#2  0x9104d5d9 in -[NSObject release] ()
#3  0x99e41224 in CFRelease ()
#4  0x99e56277 in -[__NSArrayM dealloc] ()
#5  0x9104d5ef in -[NSObject release] ()
#6  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#7  0x9104d5ef in -[NSObject release] ()
#8  0x97f62ac8 in -[NSOperation dealloc] ()
#9  0x9104d5ef in -[NSObject release] ()
#10 0x99e41224 in CFRelease ()
#11 0x99e56277 in -[__NSArrayM dealloc] ()
#12 0x9104d5ef in -[NSObject release] ()
#13 0x97f62b22 in -[__NSOperationInternal dealloc] ()
#14 0x9104d5ef in -[NSObject release] ()
#15 0x97f62ac8 in -[NSOperation dealloc] ()
#16 0x9104d5ef in -[NSObject release] ()
#17 0x99e41224 in CFRelease ()
#18 0x99e56277 in -[__NSArrayM dealloc] ()
#19 0x9104d5ef in -[NSObject release] ()
#20 0x97f62b22 in -[__NSOperationInternal dealloc] ()
#21 0x9104d5ef in -[NSObject release] ()
#22 0x97f62ac8 in -[NSOperation dealloc] ()
#23 0x9104d5ef in -[NSObject release] ()
#24 0x99e41224 in CFRelease ()
#25 0x99e56277 in -[__NSArrayM dealloc] ()
#26 0x9104d5ef in -[NSObject release] ()
#27 0x97f62b22 in -[__NSOperationInternal dealloc] ()
#28 0x9104d5ef in -[NSObject release] ()
#29 0x97f62ac8 in -[NSOperation dealloc] ()
#30 0x9104d5ef in -[NSObject release] ()
#31 0x99e41224 in CFRelease ()
#32 0x99e56277 in -[__NSArrayM dealloc] ()
#33 0x9104d5ef in -[NSObject release] ()
#34 0x97f62b22 in -[__NSOperationInternal dealloc] ()
#35 0x9104d5ef in -[NSObject release] ()
#36 0x97f62ac8 in -[NSOperation dealloc] ()
#37 0x9104d5ef in -[NSObject release] ()
#38 0x99e41224 in CFRelease ()
#39 0x99e56277 in -[__NSArrayM dealloc] ()
#40 0x9104d5ef in -[NSObject release] ()
#41 0x97f62b22 in -[__NSOperationInternal dealloc] ()
#42 0x9104d5ef in -[NSObject release] ()
#43 0x97f62ac8 in -[NSOperation dealloc] ()
#44 0x9104d5ef in -[NSObject release] ()
#45 0x99e41224 in CFRelease ()
#46 0x99e56277 in -[__NSArrayM dealloc] ()
#47 0x9104d5ef in -[NSObject release] ()
#48 0x97f62b22 in -[__NSOperationInternal dealloc] ()
#49 0x9104d5ef in -[NSObject release] ()
#50 0x97f62ac8 in -[NSOperation dealloc] ()
#10722  0x9104d5ef in -[NSObject release] ()
#10723  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10724  0x9104d5ef in -[NSObject release] ()
#10725  0x97f62ac8 in -[NSOperation dealloc] ()
#10726  0x9104d5ef in -[NSObject release] ()
#10727  0x99e41224 in CFRelease ()
#10728  0x99e56277 in -[__NSArrayM dealloc] ()
#10729  0x9104d5ef in -[NSObject release] ()
#10730  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10731  0x9104d5ef in -[NSObject release] ()
#10732  0x97f62ac8 in -[NSOperation dealloc] ()
#10733  0x9104d5ef in -[NSObject release] ()
#10734  0x99e41224 in CFRelease ()
#10735  0x99e56277 in -[__NSArrayM dealloc] ()
#10736  0x9104d5ef in -[NSObject release] ()
#10737  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10738  0x9104d5ef in -[NSObject release] ()
#10739  0x97f62ac8 in -[NSOperation dealloc] ()
#10740  0x9104d5ef in -[NSObject release] ()
#10741  0x99e41224 in CFRelease ()
#10742  0x99e56277 in -[__NSArrayM dealloc] ()
#10743  0x9104d5ef in -[NSObject release] ()
#10744  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10745  0x9104d5ef in -[NSObject release] ()
#10746  0x97f62ac8 in -[NSOperation dealloc] ()
#10747  0x9104d5ef in -[NSObject release] ()
#10748  0x99e41224 in CFRelease ()
#10749  0x99e56277 in -[__NSArrayM dealloc] ()
#10750  0x9104d5ef in -[NSObject release] ()
#10751  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10752  0x9104d5ef in -[NSObject release] ()
#10753  0x97f62ac8 in -[NSOperation dealloc] ()
#10754  0x9104d5ef in -[NSObject release] ()
#10755  0x99e41224 in CFRelease ()
#10756  0x99e56277 in -[__NSArrayM dealloc] ()
#10757  0x9104d5ef in -[NSObject release] ()
#10758  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10759  0x9104d5ef in -[NSObject release] ()
#10760  0x97f62ac8 in -[NSOperation dealloc] ()
#10761  0x9104d5ef in -[NSObject release] ()
#10762  0x99e41224 in CFRelease ()
#10763  0x99e56277 in -[__NSArrayM dealloc] ()
#10764  0x9104d5ef in -[NSObject release] ()
#10765  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10766  0x9104d5ef in -[NSObject release] ()
#10767  0x97f62ac8 in -[NSOperation dealloc] ()
#10768  0x9104d5ef in -[NSObject release] ()
#10769  0x99e41224 in CFRelease ()
#10770  0x99e56277 in -[__NSArrayM dealloc] ()
#10771  0x9104d5ef in -[NSObject release] ()
#10772  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10773  0x9104d5ef in -[NSObject release] ()
#10774  0x97f62ac8 in -[NSOperation dealloc] ()
#10775  0x9104d5ef in -[NSObject release] ()
#10776  0x99e41224 in CFRelease ()
#10777  0x99e56277 in -[__NSArrayM dealloc] ()
#10778  0x9104d5ef in -[NSObject release] ()
#10779  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10780  0x9104d5ef in -[NSObject release] ()
#10781  0x97f62ac8 in -[NSOperation dealloc] ()
#10782  0x9104d5ef in -[NSObject release] ()
#10783  0x99e41224 in CFRelease ()
#10784  0x99e56277 in -[__NSArrayM dealloc] ()
#10785  0x9104d5ef in -[NSObject release] ()
#10786  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10787  0x9104d5ef in -[NSObject release] ()
#10788  0x97f62ac8 in -[NSOperation dealloc] ()
#10789  0x9104d5ef in -[NSObject release] ()
#10790  0x99e41224 in CFRelease ()
#10791  0x99e56277 in -[__NSArrayM dealloc] ()
#10792  0x9104d5ef in -[NSObject release] ()
#10793  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10794  0x9104d5ef in -[NSObject release] ()
#10795  0x97f62ac8 in -[NSOperation dealloc] ()
#10796  0x9104d5ef in -[NSObject release] ()
#10797  0x99e41224 in CFRelease ()
#10798  0x99e56277 in -[__NSArrayM dealloc] ()
#10799  0x9104d5ef in -[NSObject release] ()
#10800  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10801  0x9104d5ef in -[NSObject release] ()
#10802  0x97f62ac8 in -[NSOperation dealloc] ()
#10803  0x9104d5ef in -[NSObject release] ()
#10804  0x99e41224 in CFRelease ()
#10805  0x99e56277 in -[__NSArrayM dealloc] ()
#10806  0x9104d5ef in -[NSObject release] ()
#10807  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10808  0x9104d5ef in -[NSObject release] ()
#10809  0x97f62ac8 in -[NSOperation dealloc] ()
#10810  0x9104d5ef in -[NSObject release] ()
#10811  0x99e41224 in CFRelease ()
#10812  0x99e56277 in -[__NSArrayM dealloc] ()
#10813  0x9104d5ef in -[NSObject release] ()
#10814  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10815  0x9104d5ef in -[NSObject release] ()
#10816  0x97f62ac8 in -[NSOperation dealloc] ()
#10817  0x9104d5ef in -[NSObject release] ()
#10818  0x99e41224 in CFRelease ()
#10819  0x99e56277 in -[__NSArrayM dealloc] ()
#10820  0x9104d5ef in -[NSObject release] ()
#10821  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10822  0x9104d5ef in -[NSObject release] ()
#10823  0x97f62ac8 in -[NSOperation dealloc] ()
#10824  0x9104d5ef in -[NSObject release] ()
#10825  0x99e41224 in CFRelease ()
#10826  0x99e56277 in -[__NSArrayM dealloc] ()
#10827  0x9104d5ef in -[NSObject release] ()
#10828  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10829  0x9104d5ef in -[NSObject release] ()
#10830  0x97f62ac8 in -[NSOperation dealloc] ()
#10831  0x9104d5ef in -[NSObject release] ()
#10832  0x99e41224 in CFRelease ()
#10833  0x99e56277 in -[__NSArrayM dealloc] ()
#10834  0x9104d5ef in -[NSObject release] ()
#10835  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10836  0x9104d5ef in -[NSObject release] ()
#10837  0x97f62ac8 in -[NSOperation dealloc] ()
#10838  0x9104d5ef in -[NSObject release] ()
#10839  0x99e41224 in CFRelease ()
#10840  0x99e56277 in -[__NSArrayM dealloc] ()
#10841  0x9104d5ef in -[NSObject release] ()
#10842  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10843  0x9104d5ef in -[NSObject release] ()
#10844  0x97f62ac8 in -[NSOperation dealloc] ()
#10845  0x9104d5ef in -[NSObject release] ()
#10846  0x99e41224 in CFRelease ()
#10847  0x99e56277 in -[__NSArrayM dealloc] ()
#10848  0x9104d5ef in -[NSObject release] ()
#10849  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10850  0x9104d5ef in -[NSObject release] ()
#10851  0x97f62ac8 in -[NSOperation dealloc] ()
#10852  0x9104d5ef in -[NSObject release] ()
#10853  0x99e41224 in CFRelease ()
#10854  0x99e56277 in -[__NSArrayM dealloc] ()
#10855  0x9104d5ef in -[NSObject release] ()
#10856  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10857  0x9104d5ef in -[NSObject release] ()
#10858  0x97f62ac8 in -[NSOperation dealloc] ()
#10859  0x9104d5ef in -[NSObject release] ()
#10860  0x99e41224 in CFRelease ()
#10861  0x99e56277 in -[__NSArrayM dealloc] ()
#10862  0x9104d5ef in -[NSObject release] ()
#10863  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10864  0x9104d5ef in -[NSObject release] ()
#10865  0x97f62ac8 in -[NSOperation dealloc] ()
#10866  0x9104d5ef in -[NSObject release] ()
#10867  0x99e41224 in CFRelease ()
#10868  0x99e56277 in -[__NSArrayM dealloc] ()
#10869  0x9104d5ef in -[NSObject release] ()
#10870  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10871  0x9104d5ef in -[NSObject release] ()
#10872  0x97f62ac8 in -[NSOperation dealloc] ()
#10873  0x9104d5ef in -[NSObject release] ()
#10874  0x99e41224 in CFRelease ()
#10875  0x99e56277 in -[__NSArrayM dealloc] ()
#10876  0x9104d5ef in -[NSObject release] ()
#10877  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10878  0x9104d5ef in -[NSObject release] ()
#10879  0x97f62ac8 in -[NSOperation dealloc] ()
#10880  0x9104d5ef in -[NSObject release] ()
#10881  0x99e41224 in CFRelease ()
#10882  0x99e56277 in -[__NSArrayM dealloc] ()
#10883  0x9104d5ef in -[NSObject release] ()
#10884  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10885  0x9104d5ef in -[NSObject release] ()
#10886  0x97f62ac8 in -[NSOperation dealloc] ()
#10887  0x9104d5ef in -[NSObject release] ()
#10888  0x99e41224 in CFRelease ()
#10889  0x99e56277 in -[__NSArrayM dealloc] ()
#10890  0x9104d5ef in -[NSObject release] ()
#10891  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10892  0x9104d5ef in -[NSObject release] ()
#10893  0x97f62ac8 in -[NSOperation dealloc] ()
#10894  0x9104d5ef in -[NSObject release] ()
#10895  0x99e41224 in CFRelease ()
#10896  0x99e56277 in -[__NSArrayM dealloc] ()
#10897  0x9104d5ef in -[NSObject release] ()
#10898  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10899  0x9104d5ef in -[NSObject release] ()
#10900  0x97f62ac8 in -[NSOperation dealloc] ()
#10901  0x9104d5ef in -[NSObject release] ()
#10902  0x99e41224 in CFRelease ()
#10903  0x99e56277 in -[__NSArrayM dealloc] ()
#10904  0x9104d5ef in -[NSObject release] ()
#10905  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10906  0x9104d5ef in -[NSObject release] ()
#10907  0x97f62ac8 in -[NSOperation dealloc] ()
#10908  0x9104d5ef in -[NSObject release] ()
#10909  0x99e41224 in CFRelease ()
#10910  0x99e56277 in -[__NSArrayM dealloc] ()
#10911  0x9104d5ef in -[NSObject release] ()
#10912  0x97f62b22 in -[__NSOperationInternal dealloc] ()
#10913  0x9104d5ef in -[NSObject release] ()
#10914  0x97f62ac8 in -[NSOperation dealloc] ()
#10915  0x9104d5ef in -[NSObject release] ()
#10916  0x97f49cca in __NSOQSchedule_f ()
#10917  0x9c1c9e21 in _dispatch_async_redirect_invoke ()
#10918  0x9c1c53a6 in _dispatch_client_callout ()
#10919  0x9c1c7467 in _dispatch_root_queue_drain ()
#10920  0x9c1c8732 in _dispatch_worker_thread2 ()
#10921  0x960c2dab in _pthread_wqthread ()

The full crash context is (bold for crash line):

libobjc.A.dylib`objc::DenseMapBase<objc::DenseMap<objc_object*, unsigned long, true, objc::DenseMapInfo<objc_object*> >, objc_object*, unsigned long, objc::DenseMapInfo<objc_object*>, true>::find(objc_object* const&):
0x9104d800:  pushl  %ebp
0x9104d801:  movl   %esp, %ebp
0x9104d803:  pushl  %esi
0x9104d804:  subl   $20, %esp
0x9104d807:  leal   -8(%ebp), %eax
0x9104d80a:  movl   %eax, 8(%esp)
0x9104d80e:  movl   16(%ebp), %eax
0x9104d811:  movl   %eax, 4(%esp)
0x9104d815:  movl   12(%ebp), %esi
0x9104d818:  movl   %esi, (%esp)
**0x9104d81b:  calll  0x9104d9b6                ; bool objc::DenseMapBase<objc::DenseMap<objc_object*, unsigned long, true, objc::DenseMapInfo<objc_object*> >, objc_object*, unsigned long, objc::DenseMapInfo<objc_object*>, true>::LookupBucketFor<objc_object*>(objc_object* const&, std::__1::pair<objc_object*, unsigned long> const*&) const**
0x9104d820:  movl   12(%esi), %ecx
0x9104d823:  shll   $3, %ecx
0x9104d826:  addl   (%esi), %ecx
0x9104d828:  movl   8(%ebp), %edx
0x9104d82b:  testb  %al, %al
0x9104d82d:  je     0x9104d836                ; objc::DenseMapBase<objc::DenseMap<objc_object*, unsigned long, true, objc::DenseMapInfo<objc_object*> >, objc_object*, unsigned long, objc::DenseMapInfo<objc_object*>, true>::find(objc_object* const&) + 54
0x9104d82f:  movl   -8(%ebp), %eax
0x9104d832:  movl   %eax, (%edx)
0x9104d834:  jmp    0x9104d838                ; objc::DenseMapBase<objc::DenseMap<objc_object*, unsigned long, true, objc::DenseMapInfo<objc_object*> >, objc_object*, unsigned long, objc::DenseMapInfo<objc_object*>, true>::find(objc_object* const&) + 56
0x9104d836:  movl   %ecx, (%edx)
0x9104d838:  movl   %ecx, 4(%edx)
0x9104d83b:  addl   $20, %esp
0x9104d83e:  popl   %esi
0x9104d83f:  popl   %ebp
0x9104d840:  ret    $4
0x9104d843:  nop    

I tried using a pre-created queue, this makes no difference. Apparently, with dependencies, this code is a problem with XCode 5.0, 32-bit.

Edit: In fact, I can isolate the problem much further. An empty Cocoa Application project in XCOde 5.0 on 10.9 with ARC on and a single method will crash. If it does not on your computer, increase 4269 to anything bigger:

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification
{
    NSOperationQueue* aQueue = [[ NSOperationQueue alloc ] init ];
    NSMutableArray* array = [ NSMutableArray array ];
    for ( int i = 0; i < 4269; i++)
        [ array addObject: [ [NSOperation alloc ] init  ]];

    for ( int i = 1; i < [ array count ]; i++)
        [[ array objectAtIndex:i ] addDependency:[array objectAtIndex:i-1]];

    [ aQueue addOperations: array waitUntilFinished:NO ];
}

Edit 2:

Please note that the following code will crash in a clean new project (with ARC ON, but I think this is irrelevant). I expect the queue to keep a strong reference (retain) the NSOperation.

1. the NSOperationQueue is kept forever, is never released.
2. there is no temporary NSMutableArray.
3. The operations start running as soon as they are added

Here is the code:

static NSOperationQueue* aQueue = nil;

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification
{
    aQueue = [[ NSOperationQueue alloc ] init ];
    NSOperation* lastOp = nil;
    for ( int i = 0; i < 5000 ; i++) {
        NSOperation* newOp = [ NSBlockOperation blockOperationWithBlock:^{ ;} ];
        if ( lastOp != nil )
            [ newOp addDependency: lastOp ];

        [ aQueue addOperation:newOp ];

        lastOp = newOp;
    }

}

Answer 1

New Theory

Okay, here's another theory as to what's going on:

1) Each NSOperation object keeps a strong pointer to all dependencies, probably using an array.

2) NSOperation releases the reference in dealloc, not when the dependent operation is complete.

3) As a result, you get a chain of references that prevents anything from being deallocated until the last operation completes, which does not have anything referencing it.

4) Since the queue and array are auto released, their references to the NSOperation objects go away.

5) When the last operation completes, it unleashes a string of release, dealloc, array iteration calls that, and I'm speculating here, cause a stack overflow.

I think the solution might be to keep references to the NSOperation objects manually and deliberately release them in reverse order (last to first) after they're all completed. Not really the most elegant solution, but if my theory is right, it should work.

Answer 2

Building on the analysis made by Daniel and Godel9, one may solve the issue by cleaning up the NSOperation dependencies while it executes:

@implementation MyOperation 

- (void) main 
{
  ...
  NSArray* dependencies = self.dependencies;
  for (NSOperation* op in dependencies)
    [self removeDependency:op];
}

@end

Indeed, when an operation executes, all operations in its dependencies array are finished. It is not required to retain a pointer on them anymore.