Bug 107535 – Change the Supplementable class to not use AtomicString

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Mark Lam]

The Supplementable class is used to associate auxiliary data structures with a ScriptExecutionContext or Page.  In the current implementation, Supplementable uses an AtomicString as the key for a map.  For example, an AtomicString based on a literal C string "DatabaseContext" is used as the key for a DatabaseContext object associated with a given ScriptExecutionContext.

However, in the web database refactoring work, we find that a WorkerContext (which inherits from ScriptExecutionContext) can be referenced by the main thread (as opposed to the owner worker thread) in DatabaseTracker::interruptAllDatabasesForContext() for shutdown / clean up purposes.  Technically, the DatabaseTracker deals with back-end database activity as opposed to the front-end script activity.  Hence, it should not be referencing the ScriptExecutionContext.  Instead, it should be using a DatabaseBackendContext which is associated with the DatabaseContext supplement to the ScriptExecutionContext.  This is not currently the case, but will be so one the database code gets refactored for webkit 2.

Because the Supplementable code uses AtomicStrings (which is thread specific), it is not thread-safe (nor correct) for DatabaseTracker::interruptAllDatabasesForContext() to look up the relevant DatabaseContext in the ScriptExecutionsContext's supplements.  Doing so can result in a crash and potential corrupted data.

The fix is to introduce a LiteralCString type that we'll use to replace the use of AtomicString in Supplementable.  LiteralCString is basically a wrapper around the const char* C string which is used to specify the supplement key and is not thread specific.

In addition, a mutex is added to Supplementable methods to synchronize access to the SupplementMap.

[Mark Lam]

Created attachment 183965 [details]
Preliminary patch to test the bots.

[Mark Lam]

Created attachment 183966 [details]
svn up'ed prelim patch for bot testing.

[Early Warning System Bot]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

Attachment 183966 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/16041576

[Early Warning System Bot]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

Attachment 183966 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/16031574

[WebKit Review Bot]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

Attachment 183966 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/16044519

[EFL EWS Bot]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

Attachment 183966 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/16037557

[Peter Beverloo (cr-android ews)]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

Attachment 183966 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/16011843

[Build Bot]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

Attachment 183966 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/16011858

[Zan Dobersek]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

Attachment 183966 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/16042566

[Adam Barth]

I don't think we should make Supplemental thread-safe.  Instead, multithreaded code needs to use a different mechanism.

Please do not add a mutex to Supplemental.

[Geoffrey Garen]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

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

> Source/WTF/wtf/text/LiteralCString.h:78
> +LiteralCString::LiteralCString(WTF::HashTableDeletedValueType)
> +    : m_string(0), m_length(0), m_hash(0)
> +{
> +}

Your empty value and deleted value are identical. That's not valid. After some deletes, it will cause lookup to fail even if the item is in the table.

[Geoffrey Garen]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

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

> Source/WTF/wtf/text/LiteralCString.h:94
> +    if (m_hash && m_hash == other.m_hash)
> +        return true;

Hashes are not guaranteed unique. It's OK to say that, if hashes don't match, strings don't match, but it's not OK to say that, if hashes do match, string do match.

[Mark Lam]

(In reply to comment #12)
> (From update of attachment 183966 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=183966&action=review
> 
> > Source/WTF/wtf/text/LiteralCString.h:94
> > +    if (m_hash && m_hash == other.m_hash)
> > +        return true;
> 
> Hashes are not guaranteed unique. It's OK to say that, if hashes don't match, strings don't match, but it's not OK to say that, if hashes do match, string do match.

Thanks for catching that.  Will fix.  Will also fix the empty vs deleted values.

[Mark Lam]

(In reply to comment #10)
> I don't think we should make Supplemental thread-safe.  Instead, multithreaded code needs to use a different mechanism.
> 
> Please do not add a mutex to Supplemental.

Adam, while I'm inclined to agree, but just to make sure I understand the whole picture, would you mind articulating your rationale as to why Supplementable should not be synchronized?  Thanks.

[Adam Barth]

> Adam, while I'm inclined to agree, but just to make sure I understand the whole picture, would you mind articulating your rationale as to why Supplementable should not be synchronized?

WebCore is largely single-threaded.  The threading model used in the database code is fragile and is not a good model for future threaded code.  We shouldn't complicate core mechanisms like Supplementable to support database's poor threading model.  Instead, we should improve database's threading model.

[Darin Adler]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

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

> Source/WTF/wtf/text/LiteralCString.h:2
> + * Copyright (C) 2012 Apple Inc. All rights reserved.

2013

> Source/WTF/wtf/text/LiteralCString.h:36
> +class LiteralCString {

Why do we have both this class and the ASCIILiteral class? The names of the classes do not make it clear how they differ. Please talk to Ben Poulain about this work.

> Source/WTF/wtf/text/LiteralCString.h:51
> +    inline LiteralCString();
> +    explicit inline LiteralCString(const char*);
> +    inline LiteralCString(const LiteralCString& other);
> +    inline LiteralCString(WTF::HashTableDeletedValueType);
> +
> +    bool isHashTableDeletedValue() const { return !m_string; }
> +
> +    unsigned length() const { return m_length; }
> +    unsigned hash() const { return m_hash; }
> +
> +    inline bool operator==(const LiteralCString& other) const;
> +
> +private:
> +    inline void computeHash();

I believe that all these uses of “inline” are ineffective. The inline keyword needs to be below, on the function definitions, not up here in the function declarations.

> Source/WTF/wtf/text/LiteralCString.h:73
> +LiteralCString::LiteralCString(const LiteralCString& other)
> +    : m_string(other.m_string), m_length(other.m_length), m_hash(other.m_hash)
> +{
> +}

This is unneeded. The compiler will correctly generate this if you simply don’t declare it explicitly.

> Source/WTF/wtf/text/LiteralCString.h:83
> +    m_hash = StringHasher::computeHashAndMaskTop8Bits(reinterpret_cast<const LChar*>(m_string), m_length);

Why mask top 8 bits?

> Source/WTF/wtf/text/LiteralCStringHash.h:2
> + * Copyright (C) 2012 Apple Inc. All rights reserved.

2013

> Source/WTF/wtf/text/LiteralCStringHash.h:45
> +    static const bool safeToCompareToEmptyOrDeleted = false;

If the current implementation, it is safe to compare with empty or deleted. I think this should be true, depending on what you change to resolve the issue with operator== and the empty vs. deleted values.

[Darin Adler]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

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

I couldn’t find a change log.

> Source/WebCore/platform/Supplementable.h:64
> +        MutexLocker locker(m_supplementsLock);

Where is the comment that explains why we need to add locking? What does this have to do with AtomicString vs. LiteralCString?

[Mark Lam]

(In reply to comment #17)
> (From update of attachment 183966 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=183966&action=review
> 
> I couldn’t find a change log.

That's because this patch wasn't ready for review yet.  I merely uploaded it as a work in progress to test on the EWS bots and make sure that I'm not breaking all the other builds.
 
> > Source/WebCore/platform/Supplementable.h:64
> > +        MutexLocker locker(m_supplementsLock);
> 
> Where is the comment that explains why we need to add locking? What does this have to do with AtomicString vs. LiteralCString?

I haven't added the comment regarding the locking yet, and the locking does not have anything to do with AtomicString vs LiteralCString.  It does have to do with Supplementable, and was motivated by the database code's use of the DatabaseContext supplement in forthcoming database refactoring.

Regardless, I plan to remove the locking changes from this patch, and will address the locking needs in a different bug later.  I'll comment on it then.

[Mark Lam]

(In reply to comment #16)
> (From update of attachment 183966 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=183966&action=review
> 
> > Source/WTF/wtf/text/LiteralCString.h:2
> > + * Copyright (C) 2012 Apple Inc. All rights reserved.
> 
> 2013

Thanks.

> > Source/WTF/wtf/text/LiteralCString.h:36
> > +class LiteralCString {
> 
> Why do we have both this class and the ASCIILiteral class? The names of the classes do not make it clear how they differ. Please talk to Ben Poulain about this work.

I've talk with Ben briefly and will need to talk some more.  It looks like ASCIILiteral (in a near future form) may have everything I need.

> > Source/WTF/wtf/text/LiteralCString.h:51
> > +    inline LiteralCString();
> > +    explicit inline LiteralCString(const char*);
> > +    inline LiteralCString(const LiteralCString& other);
> > +    inline LiteralCString(WTF::HashTableDeletedValueType);
> > +
> > +    bool isHashTableDeletedValue() const { return !m_string; }
> > +
> > +    unsigned length() const { return m_length; }
> > +    unsigned hash() const { return m_hash; }
> > +
> > +    inline bool operator==(const LiteralCString& other) const;
> > +
> > +private:
> > +    inline void computeHash();
> 
> I believe that all these uses of “inline” are ineffective. The inline keyword needs to be below, on the function definitions, not up here in the function declarations.

It's effective.  The C++ spec (C++ Standard - ANSI ISO IEC 14882 2003) Section 9.3.3 states "An inline member function (whether static or nonstatic) may also be defined outside of its class definition provided either its declaration in the class definition or its definition outside of the class definition declares the function as inline."


> > Source/WTF/wtf/text/LiteralCString.h:73
> > +LiteralCString::LiteralCString(const LiteralCString& other)
> > +    : m_string(other.m_string), m_length(other.m_length), m_hash(other.m_hash)
> > +{
> > +}
> 
> This is unneeded. The compiler will correctly generate this if you simply don’t declare it explicitly.

OK.
 
> > Source/WTF/wtf/text/LiteralCString.h:83
> > +    m_hash = StringHasher::computeHashAndMaskTop8Bits(reinterpret_cast<const LChar*>(m_string), m_length);
> 
> Why mask top 8 bits?

No reason.  I learned about StringHasher::computeHashAndMaskTop8Bits() by studying StringImpl.h, but should have found and used StringHasher::computeHash() instead.  I apologize for being sloppy.

> > Source/WTF/wtf/text/LiteralCStringHash.h:45
> > +    static const bool safeToCompareToEmptyOrDeleted = false;
> 
> If the current implementation, it is safe to compare with empty or deleted. I think this should be true, depending on what you change to resolve the issue with operator== and the empty vs. deleted values.

Fixed, but may be moot pending ASCIILiteral discussion.

[Geoffrey Garen]

> WebCore is largely single-threaded.  The threading model used in the database code is fragile and is not a good model for future threaded code.  We shouldn't complicate core mechanisms like Supplementable to support database's poor threading model.  Instead, we should improve database's threading model.

To be clear, the reason Supplementable needs multi-threaded support is workers, which are multi-threaded. Workers access ScriptExecutable from multiple threads, and access to a supplemental property of a Worker causes data races. This data race was introduced by the change that made ScriptExecutionContext inherit from Supplementable (<http://trac.webkit.org/changeset/109319>). Now, any access to a ScriptExecutionContext's supplemental properties, and any new access that anyone adds in the future, risks data races.

(Side note: It looks like none of the WebKit threading experts were CC'd on that change, which is a shame.)

If we want to limit the threading idiom in WebKit, let's create a specific ThreadSafeSupplementable subclass, specifically for ScriptExecutionContext to use.

[Benjamin Poulain]

Comment on attachment 183966 [details]
svn up'ed prelim patch for bot testing.

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

Maybe we can take the opportunity to rethink Supplement to be more efficient?

Since all the supplement names are literals: you can just enforce that rule (by using a template specialization to get the supplement name of a class for example), then make the hash out of the char* pointer instead of the string.

> Source/WTF/WTF.xcodeproj/project.pbxproj:1266
>  				A8A47487151A825B004123FF /* WTFThreadData.h in Headers */,
> +				FEA0878616AE448100BDD4EA /* LiteralCString.h in Headers */,
> +				FEA0878716AE448100BDD4EA /* LiteralCStringHash.h in Headers */,

The build section should be sorted alphabetically.

> Source/WTF/wtf/text/LiteralCString.h:96
> +    return !strcmp(m_string, other.m_string);

StringImpl has optimized version of equal() when you know the size of a string.

[Adam Barth]

> Workers access ScriptExecutable from multiple threads

^^^ Perhaps we should rethink that design.

[Mark Lam]

Created attachment 184116 [details]
The patch with fixes.

In the final implementation, here's what we ended up doing:
1. For Supplementable, replaced the use of AtomicString keys with const char* keys.
2. Made sure all Supplement implementations implements a supplementName() static method that returns a const char* string for its name.
- This is needed because the SupplementMap will do pointer comparisons on the keys.  Hence, we need to use the same const char* string when identifying the same Supplement, not just any 2 strings with the same characters.

The locking changes have been removed.  The LiteralCString class has been removed as well since we decided to go with using a const char* directly.

[Adam Barth]

Comment on attachment 184116 [details]
The patch with fixes.

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

This looks great!  If it was marked for review, I would have given it an r=me.  (I might have put more information in the ChangeLog, but that's just a nit.)

> Source/WebCore/Modules/quota/DOMWindowQuota.cpp:51
>  // static

I think the consensus was to skip these "static" comments because they aren't enforced by the compiler.

> Source/WebCore/Modules/webdatabase/DatabaseContext.cpp:52
> +DatabaseContext* DatabaseContext::existingDatabaseContextFrom(ScriptExecutionContext* context)

Ah, if this works for you, that's much better than locking.  Do you want to ASSERT that this function returns non-zero?

[WebKit Review Bot]

Comment on attachment 184116 [details]
The patch with fixes.

Attachment 184116 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/16043910

[Mark Lam]

(In reply to comment #25)
> (From update of attachment 184116 [details])
> Attachment 184116 [details] did not pass chromium-ews (chromium-xvfb):
> Output: http://queues.webkit.org/results/16043910

And this is why I didn't r? and waited for the bots to show some love first.  New patch coming up soon.

[Mark Lam]

Created attachment 184127 [details]
The patch + one more fix.

[Mark Lam]

(In reply to comment #24)
> (From update of attachment 184116 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=184116&action=review
> 
> This looks great!  If it was marked for review, I would have given it an r=me.  (I might have put more information in the ChangeLog, but that's just a nit.)

I said a little more in the ChangeLog comments, but didn't mention anything about synchronization issues because this patch only improves the situation i.e. avoids one cross thread issue from the use of AtomicStrings, but does not fix another issue.

I'll wait for the bots to go green first before I r? the patch, because there's a chance that I may miss one or more AtomicString to const char* conversions (or they may be added after I made my changes) in code that is only built in ports that I don't build.  I might have to upload another patch if that occurs again and will need another r+ thereafter.  Thanks.

> > Source/WebCore/Modules/quota/DOMWindowQuota.cpp:51
> >  // static
> 
> I think the consensus was to skip these "static" comments because they aren't enforced by the compiler.

Removed.

> > Source/WebCore/Modules/webdatabase/DatabaseContext.cpp:52
> > +DatabaseContext* DatabaseContext::existingDatabaseContextFrom(ScriptExecutionContext* context)
> 
> Ah, if this works for you, that's much better than locking.  Do you want to ASSERT that this function returns non-zero?

This does not resolve the potential cross-thread SupplementMap corruption issue.  I have another idea for solving that which I will apply in a separate patch.

[Ryosuke Niwa]

FYI, you can run
update-webkit --chromium
build-webkit --chromium
to build Chromium Mac port on your machine.

Also see http://trac.webkit.org/wiki/Chromium

[Mark Lam]

Comment on attachment 184127 [details]
The patch + one more fix.

Bots are green.  Ready for a review, please.  Thanks.

[Mark Lam]

Landed in r140509: <http://trac.webkit.org/changeset/140509>