[swift-dev] Thread safety of weak properties

[Greg Parker]

> On Dec 14, 2015, at 7:51 PM, Mike Ash <mike at mikeash.com> wrote:
> 
>> On Dec 14, 2015, at 3:19 PM, Greg Parker via swift-dev <swift-dev at swift.org> wrote:
>> 
>>> On Dec 14, 2015, at 9:47 AM, John McCall via swift-dev <swift-dev at swift.org> wrote:
>>> 
>>>> On Dec 12, 2015, at 7:04 PM, Chris Lattner <clattner at apple.com> wrote:
>>>> #3 sounds like a great approach to me.  I agree with Kevin that if we keep the object husk approach that any use of a weak pointer that returns nil should drop any reference to a husk.
>>> 
>>> Spin locks are, unfortunately, illegal on iOS, which does not guarantee progress in the face of priority inversion.
>> 
>> There is a spinlock algorithm that does work (in practice if not in theory), but it requires a full word of storage instead of a single bit.
> 
> Do you have a pointer (unintentional pun, oops) to this algorithm?
> 
> In this case, if we're going to dedicate a whole word to it, then we might as well go with the activity count implementation, but I'd be curious to read more just the same.

The iOS scheduler maintains several different priority levels / QoS classes: background, utility, default, user-initiated, user-interactive. If any thread in a higher class is runnable then it will always run before every thread in lower classes. A thread's priority will never decay down into a lower class. (I am told that I/O throttling has similar effects, but I don't know the details there.)

This breaks naïve spinlocks like OSSpinLock. If a lower priority thread acquires the lock and is scheduled out, and then enough high-priority threads spin on the lock, then the low-priority thread will be starved and will never run again.

This is not a theoretical problem. libobjc saw dozens of livelocks against its internal spinlocks until we stopped using OSSpinLock.

One solution is to use truly unbounded backoff. This prevents permanent livelock (assuming the rest of the system ever goes quiescent), but can still block a high-priority thread for tens of seconds depending on system load.

Another solution is to use a handoff lock algorithm. This is what libobjc does now. The lock owner stores its thread ID in the lock. Each lock waiter yields to the owner thread specifically, donating its priority and resolving the inversion. This scheme has theoretical holes when multiple locks are involved, but in practice we haven't seen any problems.

As far as I know the spinlock that libobjc now uses is not API. We can't change OSSpinLock for binary compatibility reasons (the locked state is no longer 1 but some existing code assumes that).


-- 
Greg Parker     gparker at apple.com     Runtime Wrangler