Bug 37722 - Allow to construct HashTraits<WebCore::QualifiedName>::constructDeletedValue
Summary: Allow to construct HashTraits<WebCore::QualifiedName>::constructDeletedValue
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: WebCore Misc. (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-04-16 12:06 PDT by anton muhin
Modified: 2010-04-24 10:53 PDT (History)
3 users (show)

See Also:


Attachments
Patch (2.89 KB, patch)
2010-04-16 12:15 PDT, anton muhin
no flags Details | Formatted Diff | Diff
Patch (4.70 KB, patch)
2010-04-19 07:29 PDT, anton muhin
no flags Details | Formatted Diff | Diff
Proper is deleted check (4.81 KB, patch)
2010-04-19 12:12 PDT, anton muhin
no flags Details | Formatted Diff | Diff
Proper check (4.83 KB, patch)
2010-04-23 08:18 PDT, anton muhin
no flags Details | Formatted Diff | Diff
Remove comment (4.78 KB, patch)
2010-04-23 09:26 PDT, anton muhin
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description anton muhin 2010-04-16 12:06:11 PDT
Allow to construct HashTraits<WebCore::QualifiedName>::constructDeletedValue
Comment 1 anton muhin 2010-04-16 12:15:01 PDT
Created attachment 53549 [details]
Patch
Comment 2 anton muhin 2010-04-16 12:16:15 PDT
If a patch is fine, is there a way to add a unit test for that?
Comment 3 Maciej Stachowiak 2010-04-16 15:58:47 PDT
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.
Comment 4 Maciej Stachowiak 2010-04-16 16:03:46 PDT
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.
Comment 5 anton muhin 2010-04-19 07:29:46 PDT
Created attachment 53677 [details]
Patch
Comment 6 anton muhin 2010-04-19 07:39:21 PDT
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.
Comment 7 anton muhin 2010-04-19 12:12:39 PDT
Created attachment 53702 [details]
Proper is deleted check
Comment 8 anton muhin 2010-04-20 12:17:18 PDT
(In reply to comment #7)
> Created an attachment (id=53702) [details]
> Proper is deleted check

Friendly ping
Comment 9 Darin Adler 2010-04-22 17:41:45 PDT
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?
Comment 10 anton muhin 2010-04-23 08:18:41 PDT
Created attachment 54161 [details]
Proper check
Comment 11 anton muhin 2010-04-23 08:20:56 PDT
(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.
Comment 12 Darin Adler 2010-04-23 09:09:55 PDT
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.
Comment 13 anton muhin 2010-04-23 09:26:22 PDT
Created attachment 54167 [details]
Remove comment
Comment 14 anton muhin 2010-04-23 09:29:38 PDT
(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.
Comment 15 anton muhin 2010-04-24 10:26:06 PDT
Comment on attachment 54167 [details]
Remove comment

Thanks, Darin.
Comment 16 WebKit Commit Bot 2010-04-24 10:53:34 PDT
Comment on attachment 54167 [details]
Remove comment

Clearing flags on attachment: 54167

Committed r58220: <http://trac.webkit.org/changeset/58220>
Comment 17 WebKit Commit Bot 2010-04-24 10:53:40 PDT
All reviewed patches have been landed.  Closing bug.