Bug 37722 – Allow to construct HashTraits<WebCore::QualifiedName>::constructDeletedValue

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[anton muhin]

Allow to construct HashTraits<WebCore::QualifiedName>::constructDeletedValue

[anton muhin]

Created attachment 53549 [details]
Patch

[anton muhin]

If a patch is fine, is there a way to add a unit test for that?

[Maciej Stachowiak]

What's this patch trying to accomplish? Is there a problem with the previous behavior? If so, please describe it in the ChangeLog, and in this bug.

[Maciej Stachowiak]

Comment on attachment 53549 [details]
Patch

The ChangeLog needs to explain the purpose of this change. I can't tell if this is fixing a bug, changing performance, or just a refactoring change.

> Index: WebCore/dom/QualifiedName.cpp
> ===================================================================
> --- WebCore/dom/QualifiedName.cpp	(revision 57720)
> +++ WebCore/dom/QualifiedName.cpp	(working copy)
> @@ -78,6 +78,7 @@ void QualifiedName::deref()
>      if (!m_impl)
>          return;
>  #endif
> +    ASSERT(m_impl); // HashTableDeletedValue values must be never destructed.

Hash table deleted values are generally are generally -1 cast to a pointer rather than 0 cast to a pointer by convention.

>  
>      if (m_impl->hasOneRef())
>          gNameCache->remove(m_impl);
> Index: WebCore/dom/QualifiedName.h
> ===================================================================
> --- WebCore/dom/QualifiedName.h	(revision 57720)
> +++ WebCore/dom/QualifiedName.h	(working copy)
> @@ -58,6 +58,8 @@ public:
>  
>      QualifiedName(const AtomicString& prefix, const AtomicString& localName, const AtomicString& namespaceURI);
>      QualifiedName(const AtomicString& prefix, const char* localName, const AtomicString& namespaceURI);
> +    QualifiedName(WTF::HashTableDeletedValueType) : m_impl(0) { }
> +    bool isHashTableDeletedValue() const { return !m_impl; }
>      ~QualifiedName() { deref(); }
>  #ifdef QNAME_DEFAULT_CONSTRUCTOR
>      QualifiedName() : m_impl(0) { }
> @@ -167,7 +169,7 @@ namespace WTF {
>      template<> struct HashTraits<WebCore::QualifiedName> : GenericHashTraits<WebCore::QualifiedName> {
>          static const bool emptyValueIsZero = false;
>          static WebCore::QualifiedName emptyValue() { return WebCore::QualifiedName(WebCore::nullAtom, WebCore::nullAtom, WebCore::nullAtom); }
> -        static void constructDeletedValue(WebCore::QualifiedName& slot) { new (&slot) WebCore::QualifiedName(WebCore::nullAtom, WebCore::AtomicString(HashTableDeletedValue), WebCore::nullAtom); }
> +        static void constructDeletedValue(WebCore::QualifiedName& slot) { new (&slot) WebCore::QualifiedName(WTF::HashTableDeletedValue); }
>          static bool isDeletedValue(const WebCore::QualifiedName& slot) { return slot.localName().isHashTableDeletedValue(); }
>      };
>  }

r- for not explaining the purpose of the patch. Please resubmit with an explanation of what bug is being fixed (if any) and a test case of there is a behavior change.

[anton muhin]

Created attachment 53677 [details]
Patch

[anton muhin]

Sorry, Maciej, I put explanations into ChangeLog, but that was probably not enough and wrong place.

It's not related to performance, it appears to me a bug which we were lucky not to hit.  I noticed that while trying to understand what's wrong with node list caching.  Sample stack trace: 

#0  0x0000000100f0bf60 in WebCore::StringImpl::inTable (this=0xffffffffffffffff) at StringImpl.h:168
#1  0x0000000100f0b971 in WebCore::AtomicString::add (r=0xffffffffffffffff) at /Users/chrome-user/WebKit/WebCore/platform/text/AtomicString.cpp:217
#2  0x0000000100f0fc14 in WebCore::AtomicString::AtomicString (this=0x7fff5fbfcad0, imp=0xffffffffffffffff) at AtomicString.h:51
#3  0x00000001016c41ad in WebCore::QNameComponentsTranslator::translate (location=@0x106827728, components=@0x7fff5fbfcd60) at /Users/chrome-user/WebKit/WebCore/dom/QualifiedName.cpp:48
#4  0x00000001016c4232 in WTF::HashSetTranslatorAdapter<WebCore::QualifiedName::QualifiedNameImpl*, WTF::HashTraits<WebCore::QualifiedName::QualifiedNameImpl*>, WebCore::QualifiedNameComponents, WebCore::QNameComponentsTranslator>::translate (location=@0x106827728, key=@0x7fff5fbfcd60, hashCode=234777509) at HashSet.h:111
#5  0x00000001016c434e in WTF::HashTable<WebCore::QualifiedName::QualifiedNameImpl*, WebCore::QualifiedName::QualifiedNameImpl*, WTF::IdentityExtractor<WebCore::QualifiedName::QualifiedNameImpl*>, WebCore::QualifiedNameHash, WTF::HashTraits<WebCore::QualifiedName::QualifiedNameImpl*>, WTF::HashTraits<WebCore::QualifiedName::QualifiedNameImpl*> >::addPassingHashCode<WebCore::QualifiedNameComponents, WebCore::QualifiedNameComponents, WTF::HashSetTranslatorAdapter<WebCore::QualifiedName::QualifiedNameImpl*, WTF::HashTraits<WebCore::QualifiedName::QualifiedNameImpl*>, WebCore::QualifiedNameComponents, WebCore::QNameComponentsTranslator> > (this=0x107016370, key=@0x7fff5fbfcd60, extra=@0x7fff5fbfcd60) at HashTable.h:737
#6  0x00000001016c44e0 in WTF::HashSet<WebCore::QualifiedName::QualifiedNameImpl*, WebCore::QualifiedNameHash, WTF::HashTraits<WebCore::QualifiedName::QualifiedNameImpl*> >::add<WebCore::QualifiedNameComponents, WebCore::QNameComponentsTranslator> (this=0x107016370, value=@0x7fff5fbfcd60) at HashSet.h:219
#7  0x00000001016c2671 in WebCore::QualifiedName::init (this=0x1068238f0, p=@0x102afeb20, l=@0x7fff5fbfcde0, n=@0x102afeb20) at /Users/chrome-user/WebKit/WebCore/dom/QualifiedName.cpp:59
#8  0x00000001016c2784 in WebCore::QualifiedName::QualifiedName (this=0x1068238f0, p=@0x102afeb20, l=@0x7fff5fbfcde0, n=@0x102afeb20) at /Users/chrome-user/WebKit/WebCore/dom/QualifiedName.cpp:67
#9  0x000000010197926d in WTF::HashTraits<WebCore::QualifiedName>::constructDeletedValue (slot=@0x1068238f0) at QualifiedName.h:170
#10 0x0000000101979292 in WTF::PairHashTraits<WTF::HashTraits<WebCore::QualifiedName>, WTF::HashTraits<WebCore::TagNodeList*> >::constructDeletedValue (slot=@0x1068238f0) at HashTraits.h:103

So any attempt to delete a key from hash table keyed by QualifiedName should crash if I understand what goes on correctly---QualifiedName::init would lookup in internal table and this lookup would attempt to search if AtomicString(HashTableDeletedValue) is present in internal tables.  Even if we would make that check pass, idea to construct temporary AtomicString(HashTableDeletedValue) appears dubious to me---eventually destructor should run (unless I forgot some other C++ quirk) which is bad idea for any HashTableDeletedValue and would probably crash when derefing underlying StringImpl.

I'd be glad to provide a unit test to prove that, but I am lacking knowledge of WebKit testing infrastructure---LayoutTests don't seem to be a tool for me.

I've uploaded new patch to address your comment about NULL vs. -1 as a sentinel value.

(In reply to comment #4)
> (From update of attachment 53549 [details])
> The ChangeLog needs to explain the purpose of this change. I can't tell if this
> is fixing a bug, changing performance, or just a refactoring change.
> 
> > Index: WebCore/dom/QualifiedName.cpp
> > ===================================================================
> > --- WebCore/dom/QualifiedName.cpp	(revision 57720)
> > +++ WebCore/dom/QualifiedName.cpp	(working copy)
> > @@ -78,6 +78,7 @@ void QualifiedName::deref()
> >      if (!m_impl)
> >          return;
> >  #endif
> > +    ASSERT(m_impl); // HashTableDeletedValue values must be never destructed.
> 
> Hash table deleted values are generally are generally -1 cast to a pointer
> rather than 0 cast to a pointer by convention.
> 
> >  
> >      if (m_impl->hasOneRef())
> >          gNameCache->remove(m_impl);
> > Index: WebCore/dom/QualifiedName.h
> > ===================================================================
> > --- WebCore/dom/QualifiedName.h	(revision 57720)
> > +++ WebCore/dom/QualifiedName.h	(working copy)
> > @@ -58,6 +58,8 @@ public:
> >  
> >      QualifiedName(const AtomicString& prefix, const AtomicString& localName, const AtomicString& namespaceURI);
> >      QualifiedName(const AtomicString& prefix, const char* localName, const AtomicString& namespaceURI);
> > +    QualifiedName(WTF::HashTableDeletedValueType) : m_impl(0) { }
> > +    bool isHashTableDeletedValue() const { return !m_impl; }
> >      ~QualifiedName() { deref(); }
> >  #ifdef QNAME_DEFAULT_CONSTRUCTOR
> >      QualifiedName() : m_impl(0) { }
> > @@ -167,7 +169,7 @@ namespace WTF {
> >      template<> struct HashTraits<WebCore::QualifiedName> : GenericHashTraits<WebCore::QualifiedName> {
> >          static const bool emptyValueIsZero = false;
> >          static WebCore::QualifiedName emptyValue() { return WebCore::QualifiedName(WebCore::nullAtom, WebCore::nullAtom, WebCore::nullAtom); }
> > -        static void constructDeletedValue(WebCore::QualifiedName& slot) { new (&slot) WebCore::QualifiedName(WebCore::nullAtom, WebCore::AtomicString(HashTableDeletedValue), WebCore::nullAtom); }
> > +        static void constructDeletedValue(WebCore::QualifiedName& slot) { new (&slot) WebCore::QualifiedName(WTF::HashTableDeletedValue); }
> >          static bool isDeletedValue(const WebCore::QualifiedName& slot) { return slot.localName().isHashTableDeletedValue(); }
> >      };
> >  }
> 
> r- for not explaining the purpose of the patch. Please resubmit with an
> explanation of what bug is being fixed (if any) and a test case of there is a
> behavior change.

[anton muhin]

Created attachment 53702 [details]
Proper is deleted check

[anton muhin]

(In reply to comment #7)
> Created an attachment (id=53702) [details]
> Proper is deleted check

Friendly ping

[Darin Adler]

Comment on attachment 53702 [details]
Proper is deleted check

WebCore/dom/QualifiedName.h:62
 +      bool isHashTableDeletedValue() const { return !m_impl; }

This can't be right. It should be:

    bool isHashTableDeletedValue() { return m_impl == hashTableDeletedValue(); }

Right?

[anton muhin]

Created attachment 54161 [details]
Proper check

[anton muhin]

(In reply to comment #9)
> (From update of attachment 53702 [details])
> WebCore/dom/QualifiedName.h:62
>  +      bool isHashTableDeletedValue() const { return !m_impl; }
> 
> This can't be right. It should be:
> 
>     bool isHashTableDeletedValue() { return m_impl == hashTableDeletedValue();
> }
> 
> Right?

Oh yes, thanks a lot for spotting this,Darin.  New patch uploaded.

[Darin Adler]

Comment on attachment 54161 [details]
Proper check

> +    ASSERT(!isHashTableDeletedValue()); // HashTableDeletedValue values must be never derefed..

There's an extra period here. Also, the comment says the same thing as the assertion, so I suggest just leaving the comment out.

I'm going to say r=me, but I am wondering how you tested this change, given the old wrong version you had here before.

[anton muhin]

Created attachment 54167 [details]
Remove comment

[anton muhin]

(In reply to comment #12)
> (From update of attachment 54161 [details])
> > +    ASSERT(!isHashTableDeletedValue()); // HashTableDeletedValue values must be never derefed..
> 
> There's an extra period here. Also, the comment says the same thing as the
> assertion, so I suggest just leaving the comment out.
> 
> I'm going to say r=me, but I am wondering how you tested this change, given the
> old wrong version you had here before.

Comment removed.

I too dissatisfied with the testing I can currently do, that's why I asked if
there are any unit tests in WebKit.

Current patch is tested by running run-webkit-tests on MBP in both debug and
release versions.

Previous version of patch (one that used NULL as a marker for deleted object)
got better testing as it was embedded into NodeList caching benchmark which
indeed exercises removal of elements from maps keyed by QualifiedName.

If you could suggest any testing method I should use, I'd be happy to run it
too.

[anton muhin]

Comment on attachment 54167 [details]
Remove comment

Thanks, Darin.

[WebKit Commit Bot]

Comment on attachment 54167 [details]
Remove comment

Clearing flags on attachment: 54167

Committed r58220: <http://trac.webkit.org/changeset/58220>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.