Add a 'unique' method to SkRefCnt, document the usage, and add support.

Add a 'unique' method to SkRefCnt, document the usage, and add support.

std::shared_ptr has a method called 'unique' which captures the concept that
a reference count of 1 is special, and can be used to optimize copy on write.
It also has some undocumented need for memory barriers in certain situations
and those needs are documented here.

The motivation for looking into this is crbug.com/258499 . The use of the
reference count in this manner is a benign race with both ref() and unref().
By introducing sk_atomic_unprotected_read, it is possible for Chromium to
annotate this read to tell ThreadSanitizer that this is known.

R=bsalomon@google.com

Committed: https://code.google.com/p/skia/source/detail?r=10221

[bsalomon, 2013-07-15 13:04:08]

mostly lgtm. Two questions inlined.

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h
File include/core/SkRefCnt.h (right):

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h#ne...
include/core/SkRefCnt.h:44: /** Return the reference count. Use only for
debugging. */
It seems a little weird that these obviously call the same function but one is
only for debugging purposes. Maybe we should put this function in a SK_DEBUG
block or not inline it? Do we call it anywhere after this change?

https://codereview.chromium.org/18770007/diff/5003/include/core/SkThread_plat...
File include/core/SkThread_platform.h (right):

https://codereview.chromium.org/18770007/diff/5003/include/core/SkThread_plat...
include/core/SkThread_platform.h:91: int32_t sk_atomic_unprotected_read(const
volatile int32_t & x) {
We've got several implementations of this that are all the same. Would it be
different on any platform?

[Alexander Potapenko, 2013-07-15 15:05:34]

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h
File include/core/SkRefCnt.h (right):

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h#ne...
include/core/SkRefCnt.h:62: bool unique() const {
I suggest to add an sk_atomic_acquire_load() function and use it here instead.
That reflects the semantics of unique() (see
https://code.google.com/p/chromium/codesearch#chromium/src/base/atomic_ref_co...
for how this is done in base/) and will be properly understood by TSan if
annotated as such.

In regular x86 sk_atomic_acquire_load() will be a plain load and a compiler
barrier, whereas under #if defined(THREAD_SANITIZER) it'll be a call to
__tsan_atomic32_load(ptr, __tsan_memory_order_acquire) (see
https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/atomicops_i...)

Missing acquire/release semantics for the accesses to the refcounters may result
in more false positives.

[bungeman-skia, 2013-07-15 16:02:40]

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h
File include/core/SkRefCnt.h (right):

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h#ne...
include/core/SkRefCnt.h:44: /** Return the reference count. Use only for
debugging. */
On 2013/07/15 13:04:08, bsalomon wrote:
> It seems a little weird that these obviously call the same function but one is
> only for debugging purposes. Maybe we should put this function in a SK_DEBUG
> block or not inline it? Do we call it anywhere after this change?

I believe that with this change this is only used in debug blocks. It's actually
somewhat shaky to use it there anyway, but I haven't done anything about it yet
because I haven't reviewed all of them. This is a somewhat odd method to have
around, so reasoning about it is a bit iffy anyway. The return value (other than
1) doesn't really mean anything, and the idea is to have unique handle that,
since that's the only good use for it. Maybe we should make this very heavy
weight, putting full barriers on both sides.

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h#ne...
include/core/SkRefCnt.h:62: bool unique() const {
On 2013/07/15 15:05:34, Alexander Potapenko wrote:
> I suggest to add an sk_atomic_acquire_load() function and use it here instead.

Yes, this is addressed in the comment above. Adding such a barrier should be
essentially cheap or free, except that Android is using full barriers for all
memory barrier requests. As a result, using a memory barrier here is rather
heavy on Android (this is called on every path modification, and ARM
traditionally has slow full memory barriers). The reason for this is that, as
stated in the comment, there is no need for any barrier in the case of
implementing copy on write only (as there are no modifications on other threads
to be out of order with). Copy on write is the only thing we ever use this for.

> That reflects the semantics of unique() (see
>
https://code.google.com/p/chromium/codesearch#chromium/src/base/atomic_ref_co...
> for how this is done in base/) and will be properly understood by TSan if
> annotated as such.
> 

Yes, that is the way Chromium does it, though annoyingly the C++ specification
doesn't seem to require any memory barriers from shared_ptr::unique. Unless I've
missed something, someone really needs to clarify this in the C++ spec.

> In regular x86 sk_atomic_acquire_load() will be a plain load and a compiler
> barrier, whereas under #if defined(THREAD_SANITIZER) it'll be a call to
> __tsan_atomic32_load(ptr, __tsan_memory_order_acquire) (see
>
https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/atomicops_i...)
> 

And, as mentioned above, on Android will be a full memory barrier. Which will
happen on every path modification at least. And we don't need it. Also, an
acquire barrier here is enough for exclusivity (when returning true), but isn't
enough to prevent races. This read would still be a race with previous ref()s,
and in fact still in a race with previous unref()s. In practice this will happen
much less often, but it's still possible. In fact, a previous version of this
was written something like

    bool isUnique = (1 == fRefCnt);
    if (unique) {
        sk_membar__aquire_after_load(); //rmb()
    }
    return unique;

because the memory barrier is totally wasted if we're not returning true,
because returning false provides no information about the state of the reference
count. However, this optimization doesn't help much, since the condition will,
in practice, be true 99.9% of the time. Then I realized that in pure copy on
write situations the barrier isn't needed at all, hence the verbose comment.

> Missing acquire/release semantics for the accesses to the refcounters may
result
> in more false positives.

False positives of what? A false positive from unique? I don't believe that is
possible. A false positive from tsan? Of course, that's why I'm trying to mark
it.

https://codereview.chromium.org/18770007/diff/5003/include/core/SkThread_plat...
File include/core/SkThread_platform.h (right):

https://codereview.chromium.org/18770007/diff/5003/include/core/SkThread_plat...
include/core/SkThread_platform.h:91: int32_t sk_atomic_unprotected_read(const
volatile int32_t & x) {
On 2013/07/15 13:04:08, bsalomon wrote:
> We've got several implementations of this that are all the same. Would it be
> different on any platform?

Yes, we need to clean this up in general. Note that the one which would be in
Chromium is different.

[Dmitry Vyukov, 2013-07-16 13:17:51]

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h
File include/core/SkRefCnt.h (right):

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h#ne...
include/core/SkRefCnt.h:65: return (1 == sk_atomic_unprotected_read(fRefCnt));
sk_atomic_unprotected_read() needs to use Acquire_Load() to support this use
case -- it needs to to synchronize with concurrent dec() operations.

[Alexander Potapenko, 2013-07-16 14:03:30]

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h
File include/core/SkRefCnt.h (right):

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h#ne...
include/core/SkRefCnt.h:62: bool unique() const {
Yes, I was talking about false positives from TSan.
Let thread 1 read a memory location and thread 2 write to it without any
additional synchronization.

Consider these possible cases:
1. Both threads are using regular, nonatomic writes. In this case TSan will
report a data race on the memory location despite of the fact these accesses are
atomic on x86 - it is just too aggressive for the tool to treat every word-sized
memory access as an atomic one.
2. Both threads are using relaxed atomics to access memory. In this case TSan
won't report a race on that particular address, but it may report other races on
nearby memory locations if they're being accessed in a non-atomic fashion.
Annotating every memory access as an atomic one will effectively hide all the
races, both benign and harmful ones.
3. Threads are using Acquire_Load() and Release_Store() operations to express
the synchronization. In this case TSan understands there's a happens-before arc
between the store and the load and takes that into account when looking for
races.

[Dmitry Vyukov, 2013-07-16 15:26:23]

https://codereview.chromium.org/18770007/diff/5003/src/core/SkPathRef.h
File src/core/SkPathRef.h (right):

https://codereview.chromium.org/18770007/diff/5003/src/core/SkPathRef.h#newco...
src/core/SkPathRef.h:43: (*pathRef)->incReserve(incReserveVerbs,
incReservePoints);
Won't it be modified after this unique() check?

[bungeman-skia, 2013-07-16 15:50:57]

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h
File include/core/SkRefCnt.h (right):

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h#ne...
include/core/SkRefCnt.h:62: bool unique() const {
On 2013/07/16 14:03:30, Alexander Potapenko wrote:
> Yes, I was talking about false positives from TSan.
> Let thread 1 read a memory location and thread 2 write to it without any
> additional synchronization.
> 
> Consider these possible cases:
> 1. Both threads are using regular, nonatomic writes. In this case TSan will
> report a data race on the memory location despite of the fact these accesses
are
> atomic on x86 - it is just too aggressive for the tool to treat every
word-sized
> memory access as an atomic one.

All writes here are atomic. The entire point of this exercise is to get the load
in unique into NoBarrier_Load to address this issue (and ensure that the load
is, itself, atomic).

> 2. Both threads are using relaxed atomics to access memory. In this case TSan
> won't report a race on that particular address, but it may report other races
on
> nearby memory locations if they're being accessed in a non-atomic fashion.
> Annotating every memory access as an atomic one will effectively hide all the
> races, both benign and harmful ones.

Yes, that's what the comment above is about. If you're only doing copy on write
(only writing to the owned object when unique returns/would return true) then
tsan won't be reporting races on nearby locations, because there aren't any
races there to begin with. If you are potentially writing to the owned object at
times when unique might not return true, then you must provide an acquire
barrier in the case where unique returns true before using the owned object in
order to ensure that previous writes to the owned object are observed to have
happened. We actually want this behavior from tsan, to detect cases where we are
doing something other than copy on write and not using the appropriate barriers.

Personally I believe that shared_ptrs in general should stick to the pointer
guarantee and shy away from trying to protect the owned object.
 
> 3. Threads are using Acquire_Load() and Release_Store() operations to express
> the synchronization. In this case TSan understands there's a happens-before
arc
> between the store and the load and takes that into account when looking for
> races.

https://codereview.chromium.org/18770007/diff/5003/include/core/SkRefCnt.h#ne...
include/core/SkRefCnt.h:65: return (1 == sk_atomic_unprotected_read(fRefCnt));
On 2013/07/16 13:17:51, Dmitry Vyukov wrote:
> sk_atomic_unprotected_read() needs to use Acquire_Load() to support this use
> case -- it needs to to synchronize with concurrent dec() operations.

I've tried to clarify via email, but nothing inter-thread synchronizes with
unref except itself. Adding an acquire here also will not do anything about the
current race in question, which is the race with ref. This load racing with both
ref and unref is benign, as we will not provide any information to the caller
unless the reference count is 1. The acquire would only be useful to ensure
modifications to the owned object on other threads happen before looking at the
owned object without whatever locks would normally be used in the case where
unique returns true.

Note that the acquire in unref is actually unneeded (for the same reasons) if
dispose is empty or the owned object is never modified when unique could return
false. This is somewhat unpractical as an optimization, however, since dispose
probably must modify something (even if implicitly) and the general case cannot
be assumed to be copy on write. With unique, however, the primary use is copy on
write, and the use of unique is external and easy to see (as opposed to
dispose).

https://codereview.chromium.org/18770007/diff/5003/src/core/SkPathRef.h
File src/core/SkPathRef.h (right):

https://codereview.chromium.org/18770007/diff/5003/src/core/SkPathRef.h#newco...
src/core/SkPathRef.h:43: (*pathRef)->incReserve(incReserveVerbs,
incReservePoints);
On 2013/07/16 15:26:23, Dmitry Vyukov wrote:
> Won't it be modified after this unique() check?

Yes, but it will only be modified when unique returns or would return true. The
entire reason for this check is copy on write (and no copy is needed ~99% of the
time) to avoid the heavy overhead of 'new' below. Because this is copy on write
(only modify when you're the only owner) there are no modifications on other
threads to the owned object which need to happen before using the owned object.

[bungeman-skia, 2013-07-19 19:24:15]

So I have been convinced that even copy-on-write needs a L/S barrier after the
read of fRefCnt is 1 (unless you can get it for free with the load or with the
control dependency). The L/L almost always comes free anyway, so we should just
drop an acquire barrier in here.

This change (at Patch Set 5) no longer adds support. It turns out we're going to
need a different set of changes to get SkThread straightened out first (build
issues). This change now just brings together existing non-debug tests of the
reference count under 'unique' so that we can fix things in one place after
SkThread is fixed.

[bungeman-skia, 2013-07-19 23:18:56]

Committed patchset #5 manually as r10221.