Concurrent Memory Deallocation in the Objective-C Runtime

http://www.mikeash.com/pyblog/friday-qa-2015-05-29-concurrent-memory-deallocation-in-the-objective-c-runtime.html

by chmaynard • 11 years ago

58 38 11 years ago

pron8• 11 years ago

That's a cool GC algorithm, but it has two big drawbacks:

1. It works well only if the number of GCed data structures -- i.e. the number of entry/exit points -- is relatively small (in this case, just the method cache).

2. It prevents inlining of the data structure's access functions, which adds quite a bit of overhead to each access (though not as much as two fenced CASes).

It can, however, be very useful for hot code swapping (provided there's no inlining or you have a JIT that can un-inline).

pcwalton3• 11 years ago

I think the way to look at this is more of as a synchronization technique as opposed to a general-purpose GC algorithm.

I don't understand the objection about inlining--could you explain? You could in principle not use function boundaries to delimit the critical section: a range of PC addresses within a function would do just as well.

pron8• 11 years ago

a range of PC addresses within a function would do just as well

Yes, but you'll need to know where those ranges are (i.e. you'll need some feedback from the compiler), and then be very careful that no tool injects any instructions into, or moves code around your executable/library.

pcwalton3• 11 years ago

Fascinating. I had never considered sending signals to stop all threads and check their PCs as a synchronization technique. But it works, and it brings down the uncontended lock acquisition and release time down to zero in the case where no synchronization needs to be performed.

Now I'm trying to think of other places to use this trick. :)

rayiner• 11 years ago

Clozure CL and I believe SBCL do this in their GCs to allow threads to be stopped for GC preemptively while dealing with sequences that must be atomic (like allocation). Clozure calls it PC lusering: http://ccl.clozure.com/manual/chapter17.1.html

pron8• 11 years ago

It's a take on kernel-mode RCU.

1amzave2• 11 years ago

Yes, this essentially just a form of RCU. Note however that RCU isn't just for the kernel anymore though: http://urcu.so/

lgg4• 11 years ago

It isn't actually stopping the threads. The thing to understand is that you don't need to ensure that all threads are outside of a critical section at the time you free the cache, what you need is the weaker guarantee that all threads have to have exited any critical sections they were in at the time of the pointer swap before you can call free.

You don't have to do anything heavy weight like stop all the threads, instead you can just pull their PCs out and check them. Sure, they may have moved on (and even back into the critical section) by the time you call free, but it doesn't matter because they'll be using the new cache buffer. The downside is that you might get false positives for the critical section, but you can either run the dealloc in a loop or defer it and try again later.

asveikau4• 11 years ago

No, you pretty much have to stop them. If you observe the PC of other threads at a point in time while they are running, that is no guarantee that they aren't about to enter the unsafe region immediately after you make the check.

Your suggestion sounds akin to replacing a mutex acquire with an "is the lock held?" [like trylock with 0 timeout, then immediate release]. Observing that it's unheld at time t makes no guarantee it won't be held by the time of your next instruction. It therefore becomes a meaningless check, not useful at all for real synchronization.

[PS: mentioned this on HN before, but my favorite "observe the PC as part of a synchronization primitive" hack was this one from Linux on armv5: http://lwn.net/Articles/314561/]

[PPS: How much does objc_msgSend() do inline and how much is external calls? This PC hack seems like it could have huge holes if some of its critical work is done in a non-inlined function.]

pcwalton3• 11 years ago

How do you get the PC of a thread in a POSIX userland without sending it a signal? ptrace(PTRACE_GETREGS), I guess?

Concurrent Memory Deallocation in the Objective-C Runtime

Related Stories