6 ms·
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
by asveikau 11y 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/ 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.]
- dilap 11y agoHmm? No I don't think you have to stop them. Basically you have: cache = <newval> if ok() { free(<oldval>) } The problem you have is if anyone is still using <oldval> at the point you free it. So: // maybe someone here gets a reference to <oldval> (1) cache = <newval> // from this point onward no one can reference <oldval> if ok() { free(<oldval>) } So ok() only has to check if threads have a reference to <oldval> that they are still using. Imagine ok() pauses all threads. It sees if any threads threads are in BAD=[PC_BAD_START, PC_BAD_END]. If yes, return false, if no, return true. Now imagine PC doesn't pause the threads. What can happen? A thread that was in BAD leaves BAD. That's fine. A thread that wasn't in BAD enters BAD. But that will use <newval>, so that's fine too. That thread that was in BAD leaves BAD, and then reenters. That's also fine. So there's no problem. (re your question, I believe objc_msgSend is hand optimized assembly that doesn't make any function calls; if it did, you'd just have to make sure to include those functions in the range of bad PC addresses.)
- asveikau 11y ago> So ok() only has to check if threads have a reference to <oldval> that they are still using. Right. The problem with doing this while other threads are running is that ok() can return true, correctly so for its point in time, then immediately after ok() returns another thread could enter objc_msgSend() while you are inside free(). Maybe ok() ran on thread A while thread B was right at unrelated function foo()'s "call objc_msgSend" instruction. The check is OK at a point in time, but perhaps by the time you enter free() thread B did an unsafe read. > A thread that wasn't in BAD enters BAD. But that will use <newval>, so that's fine too. You can't make guarantees that it will see newval. Whether or not it does depends on timing. For example, maybe the guy who calls ok() gets a page fault or is on a very busy CPU with lots of preemption happening. That will alter timing in the direction of this being unsafe. Cache coherence may also be an issue here.
- dilap 11y agoYou have to be atomically reading and writing cache (which you can do). So then after cache = <newval> ...any future reads of cache will use <newval> (or <newer-val>, but not <oldval>). That's what makes the trick work w/o having to pause threads.
- asveikau 11y ago> cache = <newval> As written, that is not a guarantee that all cores will see <newval> immediately. It's very CPU-specific but you may need memory fences to achieve this. Further, in my opinion it's kind of playing with fire. Edit: Also, it is my impression reading the article that <oldval> is actually a shared list of old caches to be freed (gOldCachesList). That makes it a lot more complicated than your example snippet and leaves more potential for nasty synchronization problems.
- dilap 11y agoAs written, it's psuedo-code. ;) Yup it's tricky and platform specific, but the point is it can be done (or at least that's my understanding -- I do not have first hand knowledge).
- ridiculous_fish 11y agoStrictly speaking you're right. However it's not necessary that other cores see the new store immediately: it's only necessary that they see it before the memory is freed, which occurs after a substantial delay sufficient to prevent these out-of-order issues on other CPUs. This is the technique by which memory barriers are elided on the read side (but not the write side).
- vitalyd 11y agoThis is both clever and terrifying :). How do they prevent compiler from scheduling the load early, observing, and using the stale cache pointer? Do they have at least a compiler fence on the read side?