Thread-safe string in blink?

[Hiroshige Hayashizaki]

TL;DR: We (hiroshige@, yhirano@ and kinuko@) are considering introducing a thread-safe string class in blink as cross-thread string handling with WTF::String is inherently broken no matter whether we use deep-copy or not, and we want feedback/comments.

Background:

We've been using non-thread-safe ref-counted String implementation in blink (a.k.a. WTF::String, you can find some contexts in [1]), which is supposed to be highly tuned for small string operations on single-threaded environment, but also is known not to work well in multi-threaded environment.

For cross-thread string handling we had been using CrossThreadCopier and WTF::String::isolatedCopy() to deep-copy the string data, but hiroshige@ found that this still has race issues in WTF::bind() [2] and base::Bind() [3].  In general, objects that contain non-thread-safe reference counters (e.g. WTF::String, KURL) cannot be bound to a copyable Closure.

A race issue of WTF::bind() has been fixed by making WTF::bind() to return a move-only Closure (so that it can be cleanly passed to another thread).  But this solution is harder to apply to base::Bind(), because many existing code assumes base::Callback (the return type of base::Bind()) is copyable.

We started worrying that we’ll probably need to consider having thread-safe string in blink more seriously, as we could have more and more similar situations as we're integrating/merging blink into chromium's multi-threaded architecture.  (Note: other non-thread-safe ref-counted objects have similar problems and we’ll have to fix them similarly; but WTF::String is the most used, most problematic one ;) afaik)

Possible solutions:

1. Use thread-safe string only when we use base::Bind() (or WTF::bind()). When we need to pass string data across threads, convert WTF::String into a thread-safe string, pass the thread-safe string across threads, and then convert back to WTF::String before using it in the target thread. The thread-safe string is to be used in base::Bind(), WTF::bind() and CrossThreadCopier (we always call CrossThreadCopier in Bind/bind, no matter whether it is used for cross-thread or within a single thread), and other code continues to use WTF::String.
   
   We can possibly use std::string16 for this purpose once chromium/blink merge is done, but until then we're considering adding a small thread-safe string class (i.e. sort of non-ref-counted CString).
   
   

2. Use thread-safe strings in the entire Blink. This could be more controversial and could have performance penalty, but will make things easier for us to make more blink code multi-threaded.  For performance-sensitive single-threaded code we may still want to continue to use WTF::String.  (Some data: as a quick experiment, hiroshige@ tried changing StringImpl to use thread-safe atomic ref-counting [4], which resulted 20+% slower performance in some micro-benches [5]. So apparently naively changing RefCounted to ThreadSafeRefCounted isn’t a solution we want)

Currently we’re considering applying solution 1.

Any thoughts / comments?

[1] https://groups.google.com/a/chromium.org/d/msg/chromium-dev/EUqoIz2iFU4/k0t9JT-wRRkJ

[2] http://crbug.com/390851

[3] https://code.google.com/p/chromium/issues/detail?id=390851#c19

[4] https://codereview.chromium.org/751553004/

[5] Linux blink_perf.dom

http://storage.googleapis.com/chromium-telemetry/html-results/results-2014-12-08_00-35-55
(CL: https://codereview.chromium.org/751553004/)

[Daniel Bratell]

On Mon, 08 Dec 2014 12:12:09 +0100, Hiroshige Hayashizaki <hiro...@chromium.org> wrote:

For cross-thread string handling we had been using CrossThreadCopier and WTF::String::isolatedCopy() to deep-copy the string data, but hiroshige@ found that this still has race issues in WTF::bind() [2] and base::Bind() [3].  In general, objects that contain non-thread-safe reference counters (e.g. WTF::String, KURL) cannot be bound to a copyable Closure.

The references (both to  http://crbug.com/390851 ) are not readable by me (internal bug?) so I cannot comment on them specifically , but do I understand it correctly if I say that the problem is that strings are shared between threads and both threads look at/touch/modify the strings at the same time?

Threads are complicated, but I don't think making low level classes (strings in this case) thread safe is the solution. As you point out, it has performance issues, but also, if we have threads that manipulate the same data at the same time then those code blocks should probably be protected at a higher level than at raw data level. With such higher locks, then low level locks also become unnecessary.

So of your two suggestions (1. special string class for multi thread communication, or 2. make WTF:String thread safe) I think the first suggestion is the most suitable.

/Daniel

[Yoav Weiss]

On Mon, Dec 8, 2014 at 12:12 PM, Hiroshige Hayashizaki <hiro...@chromium.org> wrote:

For cross-thread string handling we had been using CrossThreadCopier and WTF::String::isolatedCopy() to deep-copy the string data, but hiroshige@ found that this still has race issues in WTF::bind() [2] and base::Bind() [3].  In general, objects that contain non-thread-safe reference counters (e.g. WTF::String, KURL) cannot be bound to a copyable Closure.

Hmm, so copies created by isolatedCopy() are not safe to pass to other threads and cannot made to be safe? I'd be very interested in details.

The related bugs seems to be protected (I'm assuming that this is because they are security bugs).

[Adam Barth]

It is safe to send to another thread, but you need to be slightly careful about the lifetimes of any temporary WTF::String objects you create.  Specifically, you need to be sure that any temporary WTF::String objects that exist on the origin thread have ended their lifetimes before the destination thread gets the WTF::String you are transporting.

For example, the following isn't safe:

callOnMainThread(bind(&Foo::bar, str.isolatedCopy()));

The temporary returned by isolatedCopy lives until the statement that it was created in terminates.  In this case, Foo::bar can start running on the main thread before callOnMainThread returns, which means it can start referencing the new copy of the string on the main thread before the temporary WTF::String on the original thread's lifetime is over, resulting in a data race.

The following is safe:

auto closure = bind(&Foo::bar, str.isolatedCopy());

callOnMainThread(closure);

In this case the temporary created by isolatedCopy's lifetime is over before we invoke callOnMainThread, which means we never reference the string on the main thread before its lifetime is over on the origin thread.

Adam

[Adam Barth]

One design you might consider is using a thread-safe container for a StringImpl.

Consider the class WTF::StringBuffer.  By design, StringBuffer holds a RefPtr<StringImpl> such that no one else has a reference to the same StringImpl (i.e., either m_data is null or points to a StringImpl with a refcount of exactly one).  Using this approach, we would need to make the following changes:

1) Add a new constructor to WTF::StringBuffer that took a String and made a copy of the buffer inside the string.

2) Changed String::isolatedCopy to return a StringBuffer.

3) Added a move constructor to StringBuffer.

Then StringBuffer would be safe to send across threads and could replace String as the transport type for strings across thread boundaries.

Adam

[Hiroshige Hayashizaki]

Thanks for comments!

One problem due to temporary objects is described by abarth@ above.

Another problem caused by copyable base::Closure is as follows.

When we execute code like:

1. base::Closure a = base::Bind(func, str.isolatedCopy()); // on Thread 1

2. base::Closure b = a;

3. Move Closure b to another Thread 2

4. Call b.Run()         // on Thread 2

5. Destruct Closure b   // on Thread 2

6. Destruct Closure a   // on Thread 1

After Step 2, the structure of the objects at this time is like:

[base::Closure a]-scoped_refptr->[base::   ]-has->[WTF::String]-RefPtr->[WTF::StringImpl]

[base::Closure b]-scoped_refptr->[BindState]

where the refcount of the StringImpl is one.

At Step 4, more references to the StringImpl are added in func() from Thread 2:

[base::Closure a (Thread 1)]-scoped_refptr->[base::   ]-has->[WTF::String]-RefPtr->[WTF::StringImpl]<-RefPtrs from Thread 2

[base::Closure b (Thread 2)]-scoped_refptr->[BindState]

At Step 6, Closure a is destructed, then BindState is destructed, then StringImpl's deref() is called from Thread 1.

However, StringImpl's ref()/deref() can be called from Thread 2 (via references created at Step 4), which causes race conditions.

abarth@, does your WTF::StringBuffer solution take a deep copy at |base::Bind| (String -> StringBuffer) and

a deep copy at |base::Callback::Run| (StringBuffer -> String)?

If so, I think it will work.

In the example above, RefPtrs from Thread 2 are not added at Step 4 to StringBuffer's StringImpl, but to a copy of it.

The reference count of StringBuffer's StringImpl remains one, and is safely destructed at Step 6.

> 3) Added a move constructor to StringBuffer.

How this move constructor used?

[Daniel Cheng]

I don't think we would be able to make base::Closure move-only, but is there a reason we can't make it moveable? I imagine that we'd want to eventually combine base::Bind/base::Closure and wtf::bind/wtf::Closure.

Daniel

[Adam Barth]

On Tue Dec 09 2014 at 12:43:00 AM Hiroshige Hayashizaki <hiro...@chromium.org> wrote:

Thanks for comments!

One problem due to temporary objects is described by abarth@ above.

Another problem caused by copyable base::Closure is as follows.

When we execute code like:

1. base::Closure a = base::Bind(func, str.isolatedCopy()); // on Thread 1

2. base::Closure b = a;

3. Move Closure b to another Thread 2

4. Call b.Run()         // on Thread 2

5. Destruct Closure b   // on Thread 2

6. Destruct Closure a   // on Thread 1

After Step 2, the structure of the objects at this time is like:

[base::Closure a]-scoped_refptr->[base::   ]-has->[WTF::String]-RefPtr->[WTF::StringImpl]

[base::Closure b]-scoped_refptr->[BindState]

where the refcount of the StringImpl is one.

At Step 4, more references to the StringImpl are added in func() from Thread 2:

[base::Closure a (Thread 1)]-scoped_refptr->[base::   ]-has->[WTF::String]-RefPtr->[WTF::StringImpl]<-RefPtrs from Thread 2

[base::Closure b (Thread 2)]-scoped_refptr->[BindState]

At Step 6, Closure a is destructed, then BindState is destructed, then StringImpl's deref() is called from Thread 1.

However, StringImpl's ref()/deref() can be called from Thread 2 (via references created at Step 4), which causes race conditions.

abarth@, does your WTF::StringBuffer solution take a deep copy at |base::Bind| (String -> StringBuffer) and

a deep copy at |base::Callback::Run| (StringBuffer -> String)?

The StringBuffer approach just makes one copy, during the calling to isolatedCopy.  The resulting StringImpl is stored inside the StringBuffer object.  Instead of making another copy of the string during base::Callback::Run, code that wishes to take a reference to the string will need to call StringBuffer::release() to take the StringImpl out of the StringBuffer.  In your example, at step 6, when the BindState is destructed, there's no longer a StringImpl to deref and therefore no data race.

If so, I think it will work.

In the example above, RefPtrs from Thread 2 are not added at Step 4 to StringBuffer's StringImpl, but to a copy of it.

The reference count of StringBuffer's StringImpl remains one, and is safely destructed at Step 6.

The StringBuffer approach doesn't introduce any more copies than necessary.  If we make another copy during base::Callback::Run, then we'll be creating more copies than necessary.

> 3) Added a move constructor to StringBuffer.

How this move constructor used?

The move constructor lets us return a StringBuffer object from String::isolatedCopy and move the resulting value into the BindState without touching the refcount of the underlying StringImpl.

On Tue Dec 09 2014 at 1:16:18 AM Daniel Cheng <dch...@chromium.org> wrote:

I don't think we would be able to make base::Closure move-only, but is there a reason we can't make it moveable?

It might be valuable to make base::Closure movable, but it's not necessary to solve the problems described in this thread.

 

I imagine that we'd want to eventually combine base::Bind/base::Closure and wtf::bind/wtf::Closure.

Yes, I'd recommend deleting WTF::Bind.  The only reason we started using it in the first place was that we weren't able to use base::Bind due to being in a separate repository from Chromium.

Adam

[Kinuko Yasuda]

I was thinking that we'd be uniformly using std::string16 for multi-threaded code after repository merge, but StringBuffer approach seems like a good reasonable solution for the problem we have right now (and we might be going to do the opposite-- using these fancy Blink string classes in Chromium).   I imagine we're going to have a separate discussion thread for this after repo merge though.

On Tue Dec 09 2014 at 1:16:18 AM Daniel Cheng <dch...@chromium.org> wrote:

I don't think we would be able to make base::Closure move-only, but is there a reason we can't make it moveable?

It might be valuable to make base::Closure movable, but it's not necessary to solve the problems described in this thread.

 

I imagine that we'd want to eventually combine base::Bind/base::Closure and wtf::bind/wtf::Closure.

Yes, I'd recommend deleting WTF::Bind.  The only reason we started using it in the first place was that we weren't able to use base::Bind due to being in a separate repository from Chromium.

Yes, we assume we're subsuming wtf::bind into base::Bind after we merge repositories.

[Kentaro Hara]

Just DBC: If we want to move Strings to Oilpan, we need to keep WTF Strings even after repository merge (just like we need to keep WTF Vectors, WTF HashTables etc because they are already on Oilpan's heap). At the moment, I have no data to indicate whether moving Strings to Oilpan is a performance win or not, so this is just FYI.

--

Kentaro Hara, Tokyo, Japan

[Adam Barth]

Using string16 would also work, but it's much less efficient if you want to use these strings with V8 (e.g., in service workers).  One of the primary benefits of WTF::String is that we can share the underlying character data with V8 efficiently (i.e., zero copy and zero bloat).

but StringBuffer approach seems like a good reasonable solution for the problem we have right now (and we might be going to do the opposite-- using these fancy Blink string classes in Chromium).   I imagine we're going to have a separate discussion thread for this after repo merge though.

On Tue Dec 09 2014 at 1:16:18 AM Daniel Cheng <dch...@chromium.org> wrote:

I don't think we would be able to make base::Closure move-only, but is there a reason we can't make it moveable?

It might be valuable to make base::Closure movable, but it's not necessary to solve the problems described in this thread.

 

I imagine that we'd want to eventually combine base::Bind/base::Closure and wtf::bind/wtf::Closure.

Yes, I'd recommend deleting WTF::Bind.  The only reason we started using it in the first place was that we weren't able to use base::Bind due to being in a separate repository from Chromium.

Yes, we assume we're subsuming wtf::bind into base::Bind after we merge repositories.

We'll also need to remove WTF::WeakPtr in favor of base::WeakPtr, but that should be relatively straightforward.

[Hiroshige Hayashizaki]

The StringBuffer approach just makes one copy, during the calling to isolatedCopy.  The resulting StringImpl is stored inside the StringBuffer object.  Instead of making another copy of the string during base::Callback::Run, code that wishes to take a reference to the string will need to call StringBuffer::release() to take the StringImpl out of the StringBuffer.  In your example, at step 6, when the BindState is destructed, there's no longer a StringImpl to deref and therefore no data race.

This makes Closure (and its copies) callable only once.

[Example 2]

1. base::Closure a = base::Bind(func, str.isolatedCopy());

2. base::Closure b = a;

3. Call b.Run() // Good. Here StringBuffer.release() is called, and Closure a and b are no longer callable

4. Call a.Run() // Invalid. func receives null StringImpl.

    // This is the first time Closure a is called, but StringBuffer's reference is already released at a call to its copy, Closure b, at Step 3.

5. Call b.Run() again // Invalid. func receives null StringImpl.

Also, the current implementation of StringBuffer::release() is not thread-safe, and there will be another race condition when a.Run() and b.Run() is executed simultaneously (in Steps 3 and 4 in Example 2 above) from different threads.

(I assume base::Closure can (or should be able to) be passed across threads, copied, and have Run() called without limitation.)

[Kinuko Yasuda]

On Wed, Dec 10, 2014 at 3:12 PM, Hiroshige Hayashizaki <hiro...@chromium.org> wrote:

The StringBuffer approach just makes one copy, during the calling to isolatedCopy.  The resulting StringImpl is stored inside the StringBuffer object.  Instead of making another copy of the string during base::Callback::Run, code that wishes to take a reference to the string will need to call StringBuffer::release() to take the StringImpl out of the StringBuffer.  In your example, at step 6, when the BindState is destructed, there's no longer a StringImpl to deref and therefore no data race.

This makes Closure (and its copies) callable only once.

[Example 2]

1. base::Closure a = base::Bind(func, str.isolatedCopy());

2. base::Closure b = a;

3. Call b.Run() // Good. Here StringBuffer.release() is called, and Closure a and b are no longer callable

4. Call a.Run() // Invalid. func receives null StringImpl.

    // This is the first time Closure a is called, but StringBuffer's reference is already released at a call to its copy, Closure b, at Step 3.

5. Call b.Run() again // Invalid. func receives null StringImpl.

Also, the current implementation of StringBuffer::release() is not thread-safe, and there will be another race condition when a.Run() and b.Run() is executed simultaneously (in Steps 3 and 4 in Example 2 above) from different threads.

(I assume base::Closure can (or should be able to) be passed across threads, copied, and have Run() called without limitation.)

We can have a type of callbacks that can be called only once with base::Callback (e.g. it can take scoped_ptr with base::Passed helper [1]).  I think making callbacks which take StringImpl callable-only-once is probably ok.

[1] https://code.google.com/p/chromium/codesearch#chromium/src/base/bind_helpers.h&l=24

[Kinuko Yasuda]

On Wed, Dec 10, 2014 at 3:23 PM, Kinuko Yasuda <kin...@chromium.org> wrote:

On Wed, Dec 10, 2014 at 3:12 PM, Hiroshige Hayashizaki <hiro...@chromium.org> wrote:

The StringBuffer approach just makes one copy, during the calling to isolatedCopy.  The resulting StringImpl is stored inside the StringBuffer object.  Instead of making another copy of the string during base::Callback::Run, code that wishes to take a reference to the string will need to call StringBuffer::release() to take the StringImpl out of the StringBuffer.  In your example, at step 6, when the BindState is destructed, there's no longer a StringImpl to deref and therefore no data race.

This makes Closure (and its copies) callable only once.

[Example 2]

1. base::Closure a = base::Bind(func, str.isolatedCopy());

2. base::Closure b = a;

3. Call b.Run() // Good. Here StringBuffer.release() is called, and Closure a and b are no longer callable

4. Call a.Run() // Invalid. func receives null StringImpl.

    // This is the first time Closure a is called, but StringBuffer's reference is already released at a call to its copy, Closure b, at Step 3.

5. Call b.Run() again // Invalid. func receives null StringImpl.

Also, the current implementation of StringBuffer::release() is not thread-safe, and there will be another race condition when a.Run() and b.Run() is executed simultaneously (in Steps 3 and 4 in Example 2 above) from different threads.

(I assume base::Closure can (or should be able to) be passed across threads, copied, and have Run() called without limitation.)

We can have a type of callbacks that can be called only once with base::Callback (e.g. it can take scoped_ptr with base::Passed helper [1]).  I think making callbacks which take StringImpl callable-only-once is probably ok.

[1] https://code.google.com/p/chromium/codesearch#chromium/src/base/bind_helpers.h&l=24

(.release() implementation needs to take care of thread safety if we take this option for sure)

[James Robinson]

base::Callbacks often capture move-only types which makes them callable only once. Whether a given callback can be called multiple times depends on the particular usage and is not a feature of the type itself.

(In contrast C++11's std::bind+std::function requires that all parameters be copyable which makes it completely useless in many situations).

- James

[Adam Barth]

On Tue Dec 09 2014 at 10:24:47 PM Kinuko Yasuda <kin...@chromium.org> wrote:

On Wed, Dec 10, 2014 at 3:23 PM, Kinuko Yasuda <kin...@chromium.org> wrote:

On Wed, Dec 10, 2014 at 3:12 PM, Hiroshige Hayashizaki <hiro...@chromium.org> wrote:

The StringBuffer approach just makes one copy, during the calling to isolatedCopy.  The resulting StringImpl is stored inside the StringBuffer object.  Instead of making another copy of the string during base::Callback::Run, code that wishes to take a reference to the string will need to call StringBuffer::release() to take the StringImpl out of the StringBuffer.  In your example, at step 6, when the BindState is destructed, there's no longer a StringImpl to deref and therefore no data race.

This makes Closure (and its copies) callable only once.

[Example 2]

1. base::Closure a = base::Bind(func, str.isolatedCopy());

2. base::Closure b = a;

3. Call b.Run() // Good. Here StringBuffer.release() is called, and Closure a and b are no longer callable

4. Call a.Run() // Invalid. func receives null StringImpl.

    // This is the first time Closure a is called, but StringBuffer's reference is already released at a call to its copy, Closure b, at Step 3.

5. Call b.Run() again // Invalid. func receives null StringImpl.

Also, the current implementation of StringBuffer::release() is not thread-safe, and there will be another race condition when a.Run() and b.Run() is executed simultaneously (in Steps 3 and 4 in Example 2 above) from different threads.

(I assume base::Closure can (or should be able to) be passed across threads, copied, and have Run() called without limitation.)

We can have a type of callbacks that can be called only once with base::Callback (e.g. it can take scoped_ptr with base::Passed helper [1]).  I think making callbacks which take StringImpl callable-only-once is probably ok.

[1] https://code.google.com/p/chromium/codesearch#chromium/src/base/bind_helpers.h&l=24

(.release() implementation needs to take care of thread safety if we take this option for sure)

Can you explain the thread safety issue you're worried about with StringBuffer::release() ?

Adam

[Kinuko Yasuda]

On Thu, Dec 11, 2014 at 2:27 AM, Adam Barth <aba...@chromium.org> wrote:

On Tue Dec 09 2014 at 10:24:47 PM Kinuko Yasuda <kin...@chromium.org> wrote:

On Wed, Dec 10, 2014 at 3:23 PM, Kinuko Yasuda <kin...@chromium.org> wrote:

On Wed, Dec 10, 2014 at 3:12 PM, Hiroshige Hayashizaki <hiro...@chromium.org> wrote:

The StringBuffer approach just makes one copy, during the calling to isolatedCopy.  The resulting StringImpl is stored inside the StringBuffer object.  Instead of making another copy of the string during base::Callback::Run, code that wishes to take a reference to the string will need to call StringBuffer::release() to take the StringImpl out of the StringBuffer.  In your example, at step 6, when the BindState is destructed, there's no longer a StringImpl to deref and therefore no data race.

This makes Closure (and its copies) callable only once.

[Example 2]

1. base::Closure a = base::Bind(func, str.isolatedCopy());

2. base::Closure b = a;

3. Call b.Run() // Good. Here StringBuffer.release() is called, and Closure a and b are no longer callable

4. Call a.Run() // Invalid. func receives null StringImpl.

    // This is the first time Closure a is called, but StringBuffer's reference is already released at a call to its copy, Closure b, at Step 3.

5. Call b.Run() again // Invalid. func receives null StringImpl.

Also, the current implementation of StringBuffer::release() is not thread-safe, and there will be another race condition when a.Run() and b.Run() is executed simultaneously (in Steps 3 and 4 in Example 2 above) from different threads.

(I assume base::Closure can (or should be able to) be passed across threads, copied, and have Run() called without limitation.)

We can have a type of callbacks that can be called only once with base::Callback (e.g. it can take scoped_ptr with base::Passed helper [1]).  I think making callbacks which take StringImpl callable-only-once is probably ok.

[1] https://code.google.com/p/chromium/codesearch#chromium/src/base/bind_helpers.h&l=24

(.release() implementation needs to take care of thread safety if we take this option for sure)

Can you explain the thread safety issue you're worried about with StringBuffer::release() ?

Um, no, if we don't allow the callback that is bound to StringImpl to be called more than once it is not a problem of course. It looks I wrote two replies with contradicting assumptions, sorry for my confusion.