Bug 229168 - Make ThreadSafeRefCounted::deref race condition safe
Summary: Make ThreadSafeRefCounted::deref race condition safe
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Ryosuke Niwa
URL:
Keywords: InRadar
Depends on: 229018
Blocks: 229171
  Show dependency treegraph
 
Reported: 2021-08-16 15:39 PDT by Ryosuke Niwa
Modified: 2021-08-24 00:58 PDT (History)
10 users (show)

See Also:


Attachments
Patch (7.10 KB, patch)
2021-08-16 16:59 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Patch (7.28 KB, patch)
2021-08-17 13:45 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Patch (7.28 KB, patch)
2021-08-18 00:50 PDT, Ryosuke Niwa
no flags Details | Formatted Diff | Diff
Patch (7.60 KB, patch)
2021-08-18 17:39 PDT, Ryosuke Niwa
ews-feeder: commit-queue-
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ryosuke Niwa 2021-08-16 15:39:47 PDT
Address a subtle race condition in ThreadSafeRefCountedBase::derefBase.
Comment 1 Ryosuke Niwa 2021-08-16 16:59:44 PDT
Created attachment 435645 [details]
Patch
Comment 2 Radar WebKit Bug Importer 2021-08-16 17:00:16 PDT
<rdar://problem/82004905>
Comment 3 Geoffrey Garen 2021-08-17 10:08:13 PDT
Comment on attachment 435645 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=435645&action=review

> Source/WTF/ChangeLog:16
> +        This patch also makes use of appropraite std::memory_order in ThreadSafeRefCountedBase's

appropriate

> Source/WTF/wtf/CheckedRef.h:233
> +    void incrementPtrCount() { m_count.fetch_add(std::memory_order_release); }

std::shared_ptr does not use a memory order on increment. Are you sure we need one?

If we need one, I believe acquire is the appropriate memory order, not release -- because we are acquiring access to this object.

> Source/WTF/wtf/ThreadSafeRefCounted.h:51
> +        ASSERT_WITH_SECURITY_IMPLICATION(!deletionHasBegun());

What should we do about code that puts an object into a RefPtr during its destructor, simply because our programming idiom demands it, and not to extend the lifetime of the object?

> Source/WTF/wtf/ThreadSafeRefCounted.h:74
> +        // Setting m_refCount to 1 here prevents double delete within the destructor. See webkit.org/b/201576.
> +        unsigned refCountToBeginDeletingThis = 1;
> +        if (m_refCount.compare_exchange_strong(refCountToBeginDeletingThis, s_deletionHasBegunRefCount, std::memory_order_acq_rel))

This line of code tests for 1; it does not set to 1.
Comment 4 Ryosuke Niwa 2021-08-17 13:01:27 PDT
(In reply to Geoffrey Garen from comment #3)
> Comment on attachment 435645 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=435645&action=review
> 
> > Source/WTF/ChangeLog:16
> > +        This patch also makes use of appropraite std::memory_order in ThreadSafeRefCountedBase's
> 
> appropriate

Fixed.

> > Source/WTF/wtf/CheckedRef.h:233
> > +    void incrementPtrCount() { m_count.fetch_add(std::memory_order_release); }
> 
> std::shared_ptr does not use a memory order on increment. Are you sure we
> need one?

Yes, because in the case of std::shared_ptr or RefPtr, there is no effect from ref() call. That is, as long as another Ref/RefPtr's deref doesn't happen after this ref() call, we don't end up deleting the object.

CheckedPtr/CheckedRef is different. incrementPtrCount() has an effect in that the destructor may release assert that the counter is 0.

Consider the following code:
1. bar->incrementPtrCount()
2. bar->f()
3. bar->decrementPtrCount()

The compiler may re-order (2) to be either before (1) or after (3) if it can determine that there is no single thread memory dependency:

2. bar->f()
1. bar->incrementPtrCount()
3. bar->decrementPtrCount()

1. bar->incrementPtrCount()
3. bar->decrementPtrCount()
2. bar->f()

Either codegen is problematic because we rely on f() call to happen while ptrCount is positive for the destructor's release assertion to catch UAF.

> If we need one, I believe acquire is the appropriate memory order, not
> release -- because we are acquiring access to this object.

No, acquire/release really refers to load/store memory operations. Here, we don't really care when ptrCount is loaded. If it happens many instructions / statements earlier, we don't care. What we care is *store* of new ptrCount because we want to ensure ptrCount is positive, not zero; not that it was zero or non-zero immediately before calling incrementPtrCount.

> > Source/WTF/wtf/ThreadSafeRefCounted.h:51
> > +        ASSERT_WITH_SECURITY_IMPLICATION(!deletionHasBegun());
> 
> What should we do about code that puts an object into a RefPtr during its
> destructor, simply because our programming idiom demands it, and not to
> extend the lifetime of the object?

Right, we discussed getting rid of these assertions. But we have the same assertion in RefCounted so I decided to keep it for now. It's probably a good idea to get rid of altogether in a separate patch.

> 
> > Source/WTF/wtf/ThreadSafeRefCounted.h:74
> > +        // Setting m_refCount to 1 here prevents double delete within the destructor. See webkit.org/b/201576.
> > +        unsigned refCountToBeginDeletingThis = 1;
> > +        if (m_refCount.compare_exchange_strong(refCountToBeginDeletingThis, s_deletionHasBegunRefCount, std::memory_order_acq_rel))
> 
> This line of code tests for 1; it does not set to 1.

Yeah, I'd update.
Comment 5 Ryosuke Niwa 2021-08-17 13:45:10 PDT
Created attachment 435711 [details]
Patch
Comment 6 Geoffrey Garen 2021-08-17 15:34:32 PDT
> Consider the following code:
> 1. bar->incrementPtrCount()
> 2. bar->f()
> 3. bar->decrementPtrCount()
> 
> The compiler may re-order (2) to be either before (1) or after (3) if it can
> determine that there is no single thread memory dependency:
> 
> 2. bar->f()
> 1. bar->incrementPtrCount()
> 3. bar->decrementPtrCount()

My understanding is that loads and stores cannot be moved *below* a release, but can be moved *above* a release. Therefore, a release in incrementPtrCount() does not prohibit this reordering.
Comment 7 Ryosuke Niwa 2021-08-17 16:39:51 PDT
(In reply to Geoffrey Garen from comment #6)
> > Consider the following code:
> > 1. bar->incrementPtrCount()
> > 2. bar->f()
> > 3. bar->decrementPtrCount()
> > 
> > The compiler may re-order (2) to be either before (1) or after (3) if it can
> > determine that there is no single thread memory dependency:
> > 
> > 2. bar->f()
> > 1. bar->incrementPtrCount()
> > 3. bar->decrementPtrCount()
> 
> My understanding is that loads and stores cannot be moved *below* a release,
> but can be moved *above* a release. Therefore, a release in
> incrementPtrCount() does not prohibit this reordering.

Oh, I see. Yeah, I guess we need memory_order_acq_rel then because we need to prohibit both reordering possibilities.
Comment 8 Ryosuke Niwa 2021-08-17 16:42:01 PDT
(In reply to Ryosuke Niwa from comment #7)
> (In reply to Geoffrey Garen from comment #6)
> > > Consider the following code:
> > > 1. bar->incrementPtrCount()
> > > 2. bar->f()
> > > 3. bar->decrementPtrCount()
> > > 
> > > The compiler may re-order (2) to be either before (1) or after (3) if it can
> > > determine that there is no single thread memory dependency:
> > > 
> > > 2. bar->f()
> > > 1. bar->incrementPtrCount()
> > > 3. bar->decrementPtrCount()
> > 
> > My understanding is that loads and stores cannot be moved *below* a release,
> > but can be moved *above* a release. Therefore, a release in
> > incrementPtrCount() does not prohibit this reordering.
> 
> Oh, I see. Yeah, I guess we need memory_order_acq_rel then because we need
> to prohibit both reordering possibilities.

Never mind. Reordering things to be after incrementPtrCount() is safe, just not decrementPtrCount() so memory_order_acquire will suffice.
Comment 9 Ryosuke Niwa 2021-08-18 00:50:00 PDT
Created attachment 435753 [details]
Patch
Comment 10 Geoffrey Garen 2021-08-18 10:59:14 PDT
Comment on attachment 435753 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=435753&action=review

r=me

> Source/WTF/wtf/ThreadSafeRefCounted.h:78
> +        // Using s_deletionHasBegunRefCount instead of 0 prevents double delete. See webkit.org/b/201576.
> +        unsigned refCountToBeginDeletingThis = 1;
> +        if (m_refCount.compare_exchange_strong(refCountToBeginDeletingThis, s_deletionHasBegunRefCount, std::memory_order_acq_rel))
>              return true;
> -        }
>  
> +        m_refCount.fetch_sub(1, std::memory_order_release);
>          return false;

I think we might be able to make this more efficient by doing a naked load, then branching to decide whether to take the delete or decrement path, then doing a compare_exchange to commit our decision, then looping if the compare_exchange fails. That way, in the normal non-deleting case, there's only one atomic refcount change instead of two.
Comment 11 Ryosuke Niwa 2021-08-18 14:42:32 PDT
Comment on attachment 435753 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=435753&action=review

>> Source/WTF/wtf/ThreadSafeRefCounted.h:78
>>          return false;
> 
> I think we might be able to make this more efficient by doing a naked load, then branching to decide whether to take the delete or decrement path, then doing a compare_exchange to commit our decision, then looping if the compare_exchange fails. That way, in the normal non-deleting case, there's only one atomic refcount change instead of two.

You mean something like this?

while (1) {
    auto currentRefCount = m_refCount.load(std::memory_order_relaxed);
    bool shouldDelete = currentRefCount == 1;
    auto newRefCount = shouldDelete ? s_deletionHasBegunRefCount : currentRefCount - 1;
    if (m_refCount.compare_exchange_weak(currentRefCount, newRefCount, std::memory_order_release))
        return shouldDelete;
}
Comment 12 Geoffrey Garen 2021-08-18 15:32:47 PDT
> You mean something like this?
> 
> while (1) {
>     auto currentRefCount = m_refCount.load(std::memory_order_relaxed);
>     bool shouldDelete = currentRefCount == 1;
>     auto newRefCount = shouldDelete ? s_deletionHasBegunRefCount :
> currentRefCount - 1;
>     if (m_refCount.compare_exchange_weak(currentRefCount, newRefCount,
> std::memory_order_release))
>         return shouldDelete;
> }

Yeah.

Or:

while (1) {
    auto refCount = m_refCount.load(std::memory_order_relaxed);
    if (refCount == 1) {
        if (m_refCount.compare_exchange_weak(refCount, s_deletionHasBegunRefCount, memory_order_release)
            break;
    } else {
        if (m_refCount.compare_exchange_weak(refCount, refCount - 1,
std::memory_order_release))
            break;
    }
}
Comment 13 Ryosuke Niwa 2021-08-18 17:37:32 PDT
(In reply to Geoffrey Garen from comment #12)
> > You mean something like this?
> > 
> > while (1) {
> >     auto currentRefCount = m_refCount.load(std::memory_order_relaxed);
> >     bool shouldDelete = currentRefCount == 1;
> >     auto newRefCount = shouldDelete ? s_deletionHasBegunRefCount :
> > currentRefCount - 1;
> >     if (m_refCount.compare_exchange_weak(currentRefCount, newRefCount,
> > std::memory_order_release))
> >         return shouldDelete;
> > }
> 
> Yeah.
> 
> Or:
> 
> while (1) {
>     auto refCount = m_refCount.load(std::memory_order_relaxed);
>     if (refCount == 1) {
>         if (m_refCount.compare_exchange_weak(refCount,
> s_deletionHasBegunRefCount, memory_order_release)
>             break;
>     } else {
>         if (m_refCount.compare_exchange_weak(refCount, refCount - 1,
> std::memory_order_release))
>             break;
>     }
> }

Ok. I'd do this:
while (1) {
    auto currentRefCount = m_refCount.load(std::memory_order_relaxed);
    auto newRefCount = currentRefCount - 1;
    if (!newRefCount) {
        // Using s_deletionHasBegunRefCount instead of 0 prevents double delete. See webkit.org/b/201576.
        if (m_refCount.compare_exchange_weak(currentRefCount, s_deletionHasBegunRefCount, std::memory_order_release))
            return true;
    } else {
        if (m_refCount.compare_exchange_weak(currentRefCount, newRefCount, std::memory_order_release))
            return false;
    }
}
Comment 14 Ryosuke Niwa 2021-08-18 17:39:48 PDT
Created attachment 435822 [details]
Patch
Comment 15 Ryosuke Niwa 2021-08-18 23:54:44 PDT
Comment on attachment 435822 [details]
Patch

Actually, this patch has already been reviewed by Geoff. Just making it go through EWS.
Comment 16 Ryosuke Niwa 2021-08-24 00:58:50 PDT
Hm... looks like this will result in 0.2~0.4% Speedometer 2 regression on iPad Pro 2. That sucks.