[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-frameworks-devel
Subject: Re: Review Request 128893: Fix sorted insert (aka flat_map like insert).
From: Dominik Haumann <dhaumann () kde ! org>
Date: 2016-09-11 20:36:34
Message-ID: 20160911203634.10006.77027 () mimi ! kde ! org
[Download RAW message or body]
--===============0092460434188178834==
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 7bit
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://git.reviewboard.kde.org/r/128893/#review99113
-----------------------------------------------------------
Ship it!
Looks good to me.
- Dominik Haumann
On Sept. 11, 2016, 8:35 p.m., Christoph Cullmann wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://git.reviewboard.kde.org/r/128893/
> -----------------------------------------------------------
>
> (Updated Sept. 11, 2016, 8:35 p.m.)
>
>
> Review request for KDE Frameworks and Boudhayan Gupta.
>
>
> Repository: baloo
>
>
> Description
> -------
>
> Old code was plain wrong:
>
> - auto it = std::upper_bound(subDocs.begin(), subDocs.end(), id);
> -
> - // Merge the id if it does not
> - auto prev = it - 1;
> - if (*prev != id) {
> - subDocs.insert(it, id);
> - }
>
>
> => you deref begin()-1 in my test case
>
> => BAM ;)
>
> valgrind backtrace for old code (moved it to template method)
>
> 0
> PASS : DocumentUrlDBTest::testGetId()
> it == begin 1
> ==22283== Invalid read of size 8
> ==22283== at 0x406F20: void Baloo::sortedIdInsert<std::vector<unsigned long \
> long, std::allocator<unsigned long long> >, unsigned long \
> long>(std::vector<unsigned long long, std::allocator<unsigned long long> >&, \
> unsigned long long const&) (idutils.h:101) ==22283== by 0x406965: \
> DocumentUrlDBTest::testSortedIdInsert() (documenturldbtest.cpp:158) ==22283== by \
> 0x404DD9: DocumentUrlDBTest::qt_static_metacall(QObject*, QMetaObject::Call, int, \
> void**) (documenturldbtest.moc:99) ==22283== by 0x57F90BD: \
> QMetaMethod::invoke(QObject*, Qt::ConnectionType, QGenericReturnArgument, \
> QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, \
> QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, \
> QGenericArgument, QGenericArgument) const (in /usr/lib/libQt5Core.so.5.7.0) \
> ==22283== by 0x4E489D6: ??? (in /usr/lib/libQt5Test.so.5.7.0) ==22283== by \
> 0x4E49405: ??? (in /usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x4E49A51: ??? (in \
> /usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x4E49F60: QTest::qExec(QObject*, \
> int, char**) (in /usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x404CF1: main \
> (documenturldbtest.cpp:167) ==22283== Address 0xbf25418 is 8 bytes before a block \
> of size 8 alloc'd ==22283== at 0x4C2A0FC: operator new(unsigned long) (in \
> /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==22283== by 0x40AF63: \
> __gnu_cxx::new_allocator<unsigned long long>::allocate(unsigned long, void const*) \
> (new_allocator.h:104) ==22283== by 0x40AD46: \
> std::allocator_traits<std::allocator<unsigned long long> \
> >::allocate(std::allocator<unsigned long long>&, unsigned long) \
> > (alloc_traits.h:416)
> ==22283== by 0x40A171: std::_Vector_base<unsigned long long, \
> std::allocator<unsigned long long> >::_M_allocate(unsigned long) (stl_vector.h:170) \
> ==22283== by 0x409151: void std::vector<unsigned long long, \
> std::allocator<unsigned long long> >::_M_emplace_back_aux<unsigned long \
> long>(unsigned long long&&) (vector.tcc:412) ==22283== by 0x40886C: void \
> std::vector<unsigned long long, std::allocator<unsigned long long> \
> >::emplace_back<unsigned long long>(unsigned long long&&) (vector.tcc:101) \
> > ==22283== by 0x406E55: std::vector<unsigned long long, std::allocator<unsigned \
> > long long> >::push_back(unsigned long long&&) (stl_vector.h:933)
> ==22283== by 0x40694A: DocumentUrlDBTest::testSortedIdInsert() \
> (documenturldbtest.cpp:155) ==22283== by 0x404DD9: \
> DocumentUrlDBTest::qt_static_metacall(QObject*, QMetaObject::Call, int, void**) \
> (documenturldbtest.moc:99) ==22283== by 0x57F90BD: QMetaMethod::invoke(QObject*, \
> Qt::ConnectionType, QGenericReturnArgument, QGenericArgument, QGenericArgument, \
> QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, \
> QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument) const (in \
> /usr/lib/libQt5Core.so.5.7.0) ==22283== by 0x4E489D6: ??? (in \
> /usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x4E49405: ??? (in \
> /usr/lib/libQt5Test.so.5.7.0) ==22283==
>
>
> Bug report:
>
> https://bugs.kde.org/show_bug.cgi?id=367991
>
>
> Diffs
> -----
>
> autotests/unit/engine/documenturldbtest.cpp 448821b
> src/engine/documenturldb.cpp 5083e7a
> src/engine/idutils.h cc7da9c
> src/engine/writetransaction.cpp 3808970
>
> Diff: https://git.reviewboard.kde.org/r/128893/diff/
>
>
> Testing
> -------
>
> Wrote test, valgrind shows error (or you get segfault, depending on luck) with old \
> code, new one works.
>
> Thanks,
>
> Christoph Cullmann
>
>
--===============0092460434188178834==
MIME-Version: 1.0
Content-Type: text/html; charset="utf-8"
Content-Transfer-Encoding: 7bit
<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="12" style="border: 1px #c9c399 \
solid; border-radius: 6px; -moz-border-radius: 6px; -webkit-border-radius: 6px;"> \
<tr> <td>
This is an automatically generated e-mail. To reply, visit:
<a href="https://git.reviewboard.kde.org/r/128893/">https://git.reviewboard.kde.org/r/128893/</a>
</td>
</tr>
</table>
<br />
<p>
Ship it!
</p>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;"><p style="padding: \
0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: inherit;">Looks \
good to me.</p></pre> <br />
<p>- Dominik Haumann</p>
<br />
<p>On September 11th, 2016, 8:35 p.m. UTC, Christoph Cullmann wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="12" style="border: \
1px #888a85 solid; border-radius: 6px; -moz-border-radius: 6px; \
-webkit-border-radius: 6px;"> <tr>
<td>
<div>Review request for KDE Frameworks and Boudhayan Gupta.</div>
<div>By Christoph Cullmann.</div>
<p style="color: grey;"><i>Updated Sept. 11, 2016, 8:35 p.m.</i></p>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt;">Repository: </b>
baloo
</div>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Description </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" \
style="border: 1px solid #b8b5a0"> <tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: \
-moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: \
break-word;"><p style="padding: 0;text-rendering: inherit;margin: 0;line-height: \
inherit;white-space: inherit;">Old code was plain wrong:</p> <h2 style="font-size: \
100%;text-rendering: inherit;padding: 0;white-space: normal;margin: 0;line-height: \
inherit;">- auto it = std::upper_bound(subDocs.begin(), subDocs.end(), \
id);</h2> <ul style="padding: 0;text-rendering: inherit;margin: 0 0 0 \
1em;line-height: inherit;white-space: normal;"> <li style="padding: 0;text-rendering: \
inherit;margin: 0;line-height: inherit;white-space: normal;">// Merge the id if it \
does not</li> <li style="padding: 0;text-rendering: inherit;margin: 0;line-height: \
inherit;white-space: normal;">auto prev = it - 1;</li> <li style="padding: \
0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">if \
(*prev != id) {</li> <li style="padding: 0;text-rendering: inherit;margin: \
0;line-height: inherit;white-space: normal;">subDocs.insert(it, id);</li> <li \
style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: \
normal;">}</li> </ul>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: \
inherit;white-space: inherit;">=> you deref begin()-1 in my test case</p> <p \
style="padding: 0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: \
inherit;">=> BAM ;)</p> <p style="padding: 0;text-rendering: inherit;margin: \
0;line-height: inherit;white-space: inherit;">valgrind backtrace for old code (moved \
it to template method)</p> <p style="padding: 0;text-rendering: inherit;margin: \
0;line-height: inherit;white-space: inherit;">0 PASS : \
DocumentUrlDBTest::testGetId() it == begin 1
==22283== Invalid read of size 8
==22283== at 0x406F20: void Baloo::sortedIdInsert<std::vector<unsigned long \
long, std::allocator<unsigned long long> >, unsigned long \
long>(std::vector<unsigned long long, std::allocator<unsigned long long> \
>&, unsigned long long const&) (idutils.h:101) ==22283== by 0x406965: \
DocumentUrlDBTest::testSortedIdInsert() (documenturldbtest.cpp:158) ==22283== by \
0x404DD9: DocumentUrlDBTest::qt_static_metacall(QObject<em style="padding: \
0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">, \
QMetaObject::Call, int, void<strong style="padding: 0;text-rendering: inherit;margin: \
0;line-height: inherit;white-space: normal;">) (documenturldbtest.moc:99) ==22283== \
by 0x57F90BD: QMetaMethod::invoke(QObject<em style="padding: 0;text-rendering: \
inherit;margin: 0;line-height: inherit;white-space: normal;">, Qt::ConnectionType, \
QGenericReturnArgument, QGenericArgument, QGenericArgument, QGenericArgument, \
QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, \
QGenericArgument, QGenericArgument, QGenericArgument) const (in \
/usr/lib/libQt5Core.so.5.7.0) ==22283== by 0x4E489D6: ??? (in \
/usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x4E49405: ??? (in \
/usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x4E49A51: ??? (in \
/usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x4E49F60: QTest::qExec(QObject</em>, \
int, char</strong>) (in /usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x404CF1: main \
(documenturldbtest.cpp:167) ==22283== Address 0xbf25418 is 8 bytes before a block of \
size 8 alloc'd ==22283== at 0x4C2A0FC: operator new(unsigned long) (in \
/usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==22283== by 0x40AF63: \
__gnu_cxx::new_allocator<unsigned long long>::allocate(unsigned long, void \
const</em>) (new_allocator.h:104) ==22283== by 0x40AD46: \
std::allocator_traits<std::allocator<unsigned long long> \
>::allocate(std::allocator<unsigned long long>&, unsigned long) \
(alloc_traits.h:416) ==22283== by 0x40A171: std::_Vector_base<unsigned long \
long, std::allocator<unsigned long long> >::_M_allocate(unsigned long) \
(stl_vector.h:170) ==22283== by 0x409151: void std::vector<unsigned long long, \
std::allocator<unsigned long long> >::_M_emplace_back_aux<unsigned long \
long>(unsigned long long&&) (vector.tcc:412) ==22283== by 0x40886C: \
void std::vector<unsigned long long, std::allocator<unsigned long long> \
>::emplace_back<unsigned long long>(unsigned long long&&) \
(vector.tcc:101) ==22283== by 0x406E55: std::vector<unsigned long long, \
std::allocator<unsigned long long> >::push_back(unsigned long \
long&&) (stl_vector.h:933) ==22283== by 0x40694A: \
DocumentUrlDBTest::testSortedIdInsert() (documenturldbtest.cpp:155) ==22283== by \
0x404DD9: DocumentUrlDBTest::qt_static_metacall(QObject<em style="padding: \
0;text-rendering: inherit;margin: 0;line-height: inherit;white-space: normal;">, \
QMetaObject::Call, int, void</em><em style="padding: 0;text-rendering: \
inherit;margin: 0;line-height: inherit;white-space: normal;">) \
(documenturldbtest.moc:99) ==22283== by 0x57F90BD: \
QMetaMethod::invoke(QObject</em>, Qt::ConnectionType, QGenericReturnArgument, \
QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, \
QGenericArgument, QGenericArgument, QGenericArgument, QGenericArgument, \
QGenericArgument, QGenericArgument) const (in /usr/lib/libQt5Core.so.5.7.0) ==22283== \
by 0x4E489D6: ??? (in /usr/lib/libQt5Test.so.5.7.0) ==22283== by 0x4E49405: ??? \
(in /usr/lib/libQt5Test.so.5.7.0) ==22283==</p>
<p style="padding: 0;text-rendering: inherit;margin: 0;line-height: \
inherit;white-space: inherit;">Bug report:</p> <p style="padding: 0;text-rendering: \
inherit;margin: 0;line-height: inherit;white-space: \
inherit;">https://bugs.kde.org/show_bug.cgi?id=367991</p></pre> </td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Testing </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: \
1px solid #b8b5a0"> <tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: \
-moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: \
break-word;"><p style="padding: 0;text-rendering: inherit;margin: 0;line-height: \
inherit;white-space: inherit;">Wrote test, valgrind shows error (or you get segfault, \
depending on luck) with old code, new one works.</p></pre> </td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>autotests/unit/engine/documenturldbtest.cpp <span style="color: \
grey">(448821b)</span></li>
<li>src/engine/documenturldb.cpp <span style="color: grey">(5083e7a)</span></li>
<li>src/engine/idutils.h <span style="color: grey">(cc7da9c)</span></li>
<li>src/engine/writetransaction.cpp <span style="color: grey">(3808970)</span></li>
</ul>
<p><a href="https://git.reviewboard.kde.org/r/128893/diff/" style="margin-left: \
3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>
--===============0092460434188178834==--
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic