4 ms·

Hmm? 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 a

by dilap 11y ago

Hmm? 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 ago
  You 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 ago
      As 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 ago
      Strictly 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 ago
        This 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?
        ridiculous_fish 11y ago
        Nothing prevents using a stale cache pointer. The stale cache still contains correct data, so using it is benign, up until it gets deallocated. A stale cache pointer may become wrong if a method implementation is replaced, e.g. by a category, but replacing a method while calling it in another thread is inherently racey.

by dilap 11y ago

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 ago
You 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 ago
    As 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 ago
    Strictly 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 ago
      This 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?
      - ridiculous_fish 11y ago
        Nothing prevents using a stale cache pointer. The stale cache still contains correct data, so using it is benign, up until it gets deallocated. A stale cache pointer may become wrong if a method implementation is replaced, e.g. by a category, but replacing a method while calling it in another thread is inherently racey.