890968 - PJS: String representation operations aren't thread safe

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Shu-yu Guo [:shu]]

bhackett points out that the string operations are in-place and change representation, and so are certainly not threadsafe.

In blindly converting the string APIs to take a ThreadSafeContext, this makes it seem like they are. This should be reverted.

Comment 1

[Shu-yu Guo [:shu]]

After talking with bhackett, billm, terrence, and nmatsakis, my conclusion is that having string operations work in parallel without excessive locking and bailing out is important. Given that, my plan of action is the following:

 1. Add asserts to |flatten|, |undepend|, and |uninline| that check:
     If a ThreadSafeContext is given, the thread associated with that context owns |this|, i.e. the thread-local allocator, if in PJS execution, owns the arena that |this| belongs to.
     Otherwise, that we are either in sequential execution or we have stopped the world.

    I do understand that this assert is error prone, but this type of 'write guard' is already employed in PJS. Maybe there can be an effect system written as a clang analysis or something for C++ usage of these operations.

 2. When the receiver object of |flatten|, |undepend|, and |uninline| is *not* thread-local, stop the world and carry out the operation.

    The hope here is that the number of non-thread local strings is limited and we will eventually reach fixed point; it's better than bailing out. Since 1. is already error-prone, by opting for a stop-the-world lock over peppering read locks everywhere should limit the sites prone to errors somewhat.

Comment 2

[Shu-yu Guo [:shu]]

Attachment: Part 1: Thread ownership asserts in string functions

Comment 3

[Shu-yu Guo [:shu]]

Attachment: Part 2: Non-destructive getChars

The STW lock approach seems more prone to degenerate cases that we *want* to perform well, such as parallel algorithms with phases, which compute strings in one phase and consume them in the next. Such an algorithm might cause the second phase to be constantly stopping the world to update string representations.

So this patch takes the usual approach of code duplication, by creating a non-destructive version of getChars for JSRope and JSDependentString. There's also a ConcatStringsPure which uses them.

Comment 4

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Comment on attachment 772766 [details] [diff] [review]
Part 1: Thread ownership asserts in string functions

Review of attachment 772766 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsgcinlines.h
@@ +52,2 @@
>  {
> +    JS_ASSERT_IF(isJSContext(), &((JSContext *)(this))->zone()->allocator == allocator_);

What's wrong with asJSContext()?

Comment 5

[Brian Hackett [Laid off!]]

Comment on attachment 772774 [details] [diff] [review]
Part 2: Non-destructive getChars

Review of attachment 772774 [details] [diff] [review]:
-----------------------------------------------------------------

Sorry for the delay.  I think this still races when ropes are composed of nodes both owned by and not owned by the current slice.

::: js/src/ion/ParallelFunctions.cpp
@@ +198,5 @@
>  ion::ParConcatStrings(ForkJoinSlice *slice, HandleString left, HandleString right,
>                        MutableHandleString out)
>  {
> +    JSString *str;
> +    if ((left->isAtom() || slice->ownsCell(left)) && (right->isAtom() || slice->ownsCell(right))) {

I think these isAtom() tests can instead be isFlat().  From my reading of JSRope::flattenInternal it will only modify rope nodes that it finds under the initial rope.

@@ +200,5 @@
>  {
> +    JSString *str;
> +    if ((left->isAtom() || slice->ownsCell(left)) && (right->isAtom() || slice->ownsCell(right))) {
> +        // Fast path: both operands are thread-local or atoms; we can use the
> +        // destructive, in-place algorithm which may flatten the operands.

I don't think this is correct.  If slice->ownsCell(left) and left is a rope, it might be composed of other rope nodes which predated the fork/join and are not owned by the slice.  I think you need to remove the ownsCell() tests.

::: js/src/vm/String.h
@@ +264,5 @@
>       * All strings have a fallible operation to get an array of chars.
>       * getCharsZ additionally ensures the array is null terminated.
> +     *
> +     * These operations are thread safe iff the receiver object is owned by
> +     * the thread associated with the context. See |ContextOwnsCell|.

I do not think this comment is correct, for the same reason as in ParConcatStrings.

@@ +269,5 @@
>       */
>  
>      inline const jschar *getChars(js::ThreadSafeContext *tcx);
>      inline const jschar *getCharsZ(js::ThreadSafeContext *tcx);
>      inline bool getChar(js::ThreadSafeContext *tcx, size_t index, jschar *code);

I think these methods should take a JSContext.

@@ +280,5 @@
> +    inline const jschar *maybeCharsZ();
> +
> +    /*
> +     * In addition they have a fallible operation to get an array of chars
> +     * non-destructively. These operations are thread safe.

The phrasing in this comment is weird, rm the 'In addition they have' bit.

@@ +292,5 @@
> +    /*
> +     * Fallible conversions to more-derived string types.
> +     *
> +     * These operations are thread safe iff the receiver object is owned by
> +     * the thread associated with the context. See |ContextOwnsCell|.

Same issue as the getChars comment.

@@ +298,4 @@
>  
>      inline JSLinearString *ensureLinear(js::ThreadSafeContext *tcx);
>      inline JSFlatString *ensureFlat(js::ThreadSafeContext *tcx);
>      inline JSStableString *ensureStable(js::ThreadSafeContext *tcx);

I think these methods should take a JSContext.

Comment 6

[Shu-yu Guo [:shu]]

(In reply to Brian Hackett (:bhackett) from comment #5)

> 
> @@ +200,5 @@
> >  {
> > +    JSString *str;
> > +    if ((left->isAtom() || slice->ownsCell(left)) && (right->isAtom() || slice->ownsCell(right))) {
> > +        // Fast path: both operands are thread-local or atoms; we can use the
> > +        // destructive, in-place algorithm which may flatten the operands.
> 
> I don't think this is correct.  If slice->ownsCell(left) and left is a rope,
> it might be composed of other rope nodes which predated the fork/join and
> are not owned by the slice.  I think you need to remove the ownsCell() tests.

Yeah, you're right. Flatten needs to either recursively check that all sub-ropes are also thread-local or just not bother. Good catch.

I guess it is indeed too much trouble to make flatten, and transitively, the ensure* functions, thread-safe. I'll follow your advice on having them take a JSContext.

Comment 7

[Shu-yu Guo [:shu]]

Attachment: Part 1: Revert thread unsafe String methods to take JSContext

Comment 8

[Shu-yu Guo [:shu]]

Attachment: Part 2: Non-destructive getChars

Comment 9

[Brian Hackett [Laid off!]]

Comment on attachment 773242 [details] [diff] [review]
Part 2: Non-destructive getChars

Review of attachment 773242 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/vm/String.h
@@ +264,5 @@
>       * All strings have a fallible operation to get an array of chars.
>       * getCharsZ additionally ensures the array is null terminated.
> +     *
> +     * These operations are thread safe iff the receiver object is owned by
> +     * the thread associated with the context. See |ContextOwnsCell|.

rm

@@ +272,5 @@
>      inline const jschar *getCharsZ(JSContext *cx);
>      inline bool getChar(JSContext *cx, size_t index, jschar *code);
>  
> +    /*
> +     * If the string is already linear, return chars. Otherwise returns NULL

I think, 'already linear/flat'

@@ +280,5 @@
> +    inline const jschar *maybeCharsZ();
> +
> +    /*
> +     * In addition they have a fallible operation to get an array of chars
> +     * non-destructively. These operations are thread safe.

Same tense issue as the earlier patch.

@@ +292,5 @@
> +    /*
> +     * Fallible conversions to more-derived string types.
> +     *
> +     * These operations are thread safe iff the receiver object is owned by
> +     * the thread associated with the context. See |ContextOwnsCell|.

rm

Comment 10

[Shu-yu Guo [:shu]]

Yes, oops, forgot to address comments.

Comment 11

[Shu-yu Guo [:shu]]

Attachment: Part 3: RAII helper for threadsafe inspection of strings.

Comment 12

[Justin Lebar (not reading bugmail)]

> JSString::maybeChars()

Can we make these const?

Comment 13

[Shu-yu Guo [:shu]]

(In reply to Justin Lebar [:jlebar] from comment #12)
> > JSString::maybeChars()
> 
> Can we make these const?

Good suggestion, done.

Comment 14

[Justin Lebar (not reading bugmail)]

Also the non-destructive getChars methods, if you didn't change those.

Comment 15

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/34b415634255
https://hg.mozilla.org/mozilla-central/rev/9ebf7bea5f6a
https://hg.mozilla.org/mozilla-central/rev/0d9cc1586740

Comment 16

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/3c7925520f33