Re: NSObject.m threading bug(s).

[David Chisnall]

On 10 Sep 2010, at 22:22, Chris Ball wrote:

> 
> I noticed some odd behaviour when I tried to upgrade from gnustep 1.18 to
> either of the new versions 1.20/1.21.  After a bit of fiddling around I
> found the problem.  It appears that if GSATOMICREAD is defined, some
> non-thread safe code gets used.
> 
> 
> Potential bug #0:
> 
> The implementation of GSAtomicIncrement/Decrement for PowerPC and MIPS appears
> to be of the form:
> 
> Load a register
> Increment/Decrement the register
> store the register
> Some branchey returny stuff.
> 
> Now it has been a long time since I have done any assembly programming and I
> have never done any for mips/power but I don't really see anything at all
> atomic about this.  If one thread gets through the load and then switches to
> another thread which then goes through all the steps of load 
> increment/decrement
> store, when we get back to the first thread, we are essentially b0rked.

The load and store are interlocked.  This is how all atomic ops are implemented 
on RISC platforms (including ARM).  The load puts the address in a reservation 
buffer.  Every store to that address (by any CPU, in a cache-cohernect system) 
sets a flag.  The interlinked store then writes to the address in the 
reservation buffer if and only if the flag is not set.  The branch happens if 
the store failed - the load-modify-retry cycle happens again until nothing else 
touches the memory in the middle.

> Bug #1 ('round about line 425):
> 
> #if     defined(GSATOMICREAD)
>      int       result;
> 
>      result = GSAtomicDecrement((gsatomic_t)&(((obj)anObject)[-1].retained));
>      if (result < 0)
>        {
>          if (result != -1)
>            {
>              [NSException raise: NSInternalInconsistencyException
>                format: @"NSDecrementExtraRefCount() decremented too far"];
>            }
>          /* The counter has become negative so it must have been zero.
>           * We reset it and return YES ... in a correctly operating
>           * process we know we can safely reset back to zero without
>           * worrying about atomicity, since there can be no other
>           * thread accessing the object (or its reference count would
>           * have been greater than zero)
>           */
>          (((obj)anObject)[-1].retained) = 0;
>          return YES;
>        }
> #else   /* GSATOMICREAD */
> 
> 
> For architectures like Intel where bug #0 isn't relevant we definitely have a
> problem here.  GSAtomicDecrement can be atomic but the two if's following it
> make this whole bit a critical section which requires some locks which pretty
> much defeats the purpose of the GSATOMICLOCK stuff.  
> 
> Specifically one thread can get the result to -2 before the thread that 
> noticed
> that the result was -1 reset the result to zero.  

This will only ever happen in the case of an object being released after its 
retain count hits 0.  This has undefined behaviour (in a single threaded 
system, it will probably segfault), so we are free to do whatever we want here, 
including some complete nonsense or crashing.

> Thank goodness for the NSInteralInconsistencyException because this would have
> been a bear to find otherwise.  Although very random/crashy behaviour seemed
> about as likely as getting the exception.

The exception is there for debugging.  We don't guarantee catching double-free 
bugs using this mechanism, because if it happened in a non-concurrent system 
we'd already have free'd the memory that the retain count is stored in, giving 
a segfault.

> At some level I suppose this can be half interesting because if there is a
> properly atomic increment available you only really need locks for the
> decrement half of the operation, but then again if we don't have real atomic
> increment/decrement for a couple supported architectures it maybe isn't worth
> the effort.

On any modern compiler (clang or gcc 4.2 or later), we are using the GCC 
built-in functions for atomic ops, so that asm is not used.  It's only needed 
for a couple of platforms that don't have a recent compiler on a few archs.

David

-- Send from my Jacquard Loom