[Calligra] 0a253ac Fixed a really weird race condition in KisNode
Dmitry Kazakov
dimula73 at gmail.com
Mon Dec 13 22:24:13 CET 2010
A krita/image/kis_safe_read_list.h [License: UNKNOWN]
commit 0a253ac8d265ac4bf5fdb805bf6ff7fba8d00170
Author: Dmitry Kazakov <dimula73 at gmail.com>
Date: Mon Dec 13 22:24:56 2010 +0300
Fixed a really weird race condition in KisNode
I was fighting with this bug about two weeks (in total). The bug was
really nasty. And the most weird thing, it could be reproduced in case
your cpu has three or more cores! I've managed to catch it only thanks
to the 6+6 cores server I was given access to.
Ok, now about a bug. It happened due to Qt's cool feature called
"implicit-sharing" coupled with the const methods having the same name
as non-const names. Ok. Imagine a single KisNode object having some
childs in a QList m_d->nodes. Now imagine three threads fighting for
the read access to this node:
1Th, 2Th, 3Th -- threads
LA - initial list contents before implicit-sharing copying done
LB - final list contents after implicit-sharing copying has been done
1Th: reads KisNodeSP &var1 = m_d->nodes.first(); // Notice the
reference
// var1 will be equal to LA.first();
1Th: gets suspended
2Th: starts foreach cycle in childNodes() method
foreach creates an implicit, *shared*, const copy of the initial
list (i'm not sure, why qt's decided to do so, anyway, they do
not support thread-safety officially).
2Th: gets suspended
/* the funniest part */
3Th: calls KisNodeSP &var3 = m_d->nodes.first();
Do you really think var3 will be equal to LA.first()? He-he.. ;)
After the call is done, m_d->nodes reincarnates into LB(!). So
var3 will be equal to LB.first(). The reference to the LA is
holded by foreach loop from now on.
3Th: gets suspended
/* the show is going on */
2Th: wakes up...
The foreach loop finishes. Now it is (officially) the only owner
of LA... So the best choice is to delete LA completely.
2Th: is done
1Th: is waking up... crash...
I've made up a solution for this by creating a KisSafeReadList. This
is a simple QList but the access to it is hightly limited: only
constant methods are allowed and no copy-constructor at all. So
effectively, it desables implicit-sharing.
Now it works, but now i should search for similar bugs in KisBaseNode
and in KoProperties.
BUG:254545
CCMAIL:kimageshop at kde.org
diff --git a/krita/image/kis_node.cpp b/krita/image/kis_node.cpp
index 58996f1..5f27951 100644
--- a/krita/image/kis_node.cpp
+++ b/krita/image/kis_node.cpp
@@ -33,6 +33,9 @@
#include "kis_node_visitor.h"
#include "kis_node_progress_proxy.h"
+#include "kis_safe_read_list.h"
+typedef KisSafeReadList<KisNodeSP> KisSafeReadNodeList;
+
/**
* The link between KisProjection ans KisImageUpdater
@@ -57,7 +60,7 @@ public:
KisNodeWSP parent;
KisNodeGraphListener * graphListener;
- QList<KisNodeSP> nodes;
+ KisSafeReadNodeList nodes;
KisNodeProgressProxy* nodeProgressProxy;
};
@@ -75,8 +78,10 @@ KisNode::KisNode(const KisNode & rhs)
{
m_d->parent = 0;
m_d->graphListener = rhs.m_d->graphListener;
- foreach(const KisNodeSP & node, rhs.m_d->nodes) {
- KisNodeSP children = node.data()->clone();
+
+ KisSafeReadNodeList::const_iterator iter;
+ FOREACH_SAFE(iter, rhs.m_d->nodes) {
+ KisNodeSP children = (*iter)->clone();
children->createNodeProgressProxy();
m_d->nodes.append(children);
children->setParent(this);
@@ -174,7 +179,7 @@ KisNodeSP KisNode::nextSibling() const
quint32 KisNode::childCount() const
{
- return m_d->nodes.count();
+ return m_d->nodes.size();
}
@@ -200,16 +205,24 @@ QList<KisNodeSP> KisNode::childNodes(const QStringList & nodeTypes, const KoProp
{
QList<KisNodeSP> nodes;
- foreach(const KisNodeSP & node, m_d->nodes) {
- if (!nodeTypes.isEmpty()) {
- foreach(const QString & nodeType, nodeTypes) {
- if (node->inherits(nodeType.toAscii())) {
- if (properties.isEmpty() || node->check(properties))
- nodes.append(node);
+ KisSafeReadNodeList::const_iterator iter;
+ FOREACH_SAFE(iter, m_d->nodes) {
+ if (properties.isEmpty() || (*iter)->check(properties)) {
+ bool rightType = true;
+
+ if(!nodeTypes.isEmpty()) {
+ rightType = false;
+ foreach(const QString &nodeType, nodeTypes) {
+ if ((*iter)->inherits(nodeType.toAscii())) {
+ rightType = true;
+ break;
+ }
}
}
- } else if (properties.isEmpty() || node->check(properties))
- nodes.append(node);
+ if(rightType) {
+ nodes.append(*iter);
+ }
+ }
}
return nodes;
}
@@ -278,12 +291,7 @@ bool KisNode::remove(quint32 index)
bool KisNode::remove(KisNodeSP node)
{
- if (node->parent().data() != this) {
- return false;
- }
-
- return remove(index(node));
-
+ return node->parent().data() == this ? remove(index(node)) : false;
}
KisNodeProgressProxy* KisNode::nodeProgressProxy() const
diff --git a/krita/image/kis_node.h b/krita/image/kis_node.h
index 16e9017..c76b650 100644
--- a/krita/image/kis_node.h
+++ b/krita/image/kis_node.h
@@ -33,6 +33,11 @@ class KisNodeProgressProxy;
* A KisNode is a KisBaseNode that knows about its direct peers, parent
* and children and whether it can have children.
*
+ * THREAD-SAFETY: All const methods of this class and setDirty calls
+ * are considered to be thread-safe(!). All the others
+ * especially add(), remove() and setParent() must be
+ * protected externally.
+ *
* NOTE: your subclasses must have the Q_OBJECT declaration, even if
* you do not define new signals or slots.
*/
diff --git a/krita/image/kis_safe_read_list.h b/krita/image/kis_safe_read_list.h
new file mode 100644
index 0000000..c4af651
--- /dev/null
+++ b/krita/image/kis_safe_read_list.h
@@ -0,0 +1,98 @@
+/*
+ * Copyright (c) 2010 Dmitry Kazakov <dimula73 at gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef KIS_SAFE_READ_LIST_H_
+#define KIS_SAFE_READ_LIST_H_
+
+
+#include <QList>
+
+/**
+ * \class KisSafeReadList
+ *
+ * This is a special wrapper around QList class
+ * Q: Why is it needed?
+ * A: It guarantees thread-safety of all the read requests to the list.
+ * There is absolutely *no* guarantees for write requests though.
+ * Q: Why pure QList cannot guarantee it?
+ * A: First, Qt does not guarantee thread-safety for QList at all.
+ * Second, QList is implicitly shared structure, therefore even
+ * with read, but non-const requests (e.g. non-const QList::first()),
+ * QList will perform internal write operations. That will lead to
+ * a race condition in an environment with 3 and more threads.
+ */
+template<class T> class KisSafeReadList : private QList<T> {
+public:
+ KisSafeReadList() {}
+
+ using QList<T>::const_iterator;
+
+ /**
+ * All the methods of this class are splitted into two groups:
+ * treadsafe and non-threadsafe. The methods from the first group
+ * can be called concurrently with each other. The ones form
+ * the other group can't be called concurrently (even with the
+ * firends from the first group) and must have an exclusive
+ * access to the list.
+ */
+
+ /**
+ * The thread-safe group
+ */
+
+ inline const T& first() const {
+ return QList<T>::first();
+ }
+
+ inline const T& last() const {
+ return QList<T>::last();
+ }
+
+ inline const T& at(int i) const {
+ return QList<T>::at(i);
+ }
+
+ using QList<T>::constBegin;
+ using QList<T>::constEnd;
+ using QList<T>::isEmpty;
+ using QList<T>::size;
+ using QList<T>::indexOf;
+ using QList<T>::contains;
+
+ /**
+ * The non-thread-safe group
+ */
+
+ using QList<T>::append;
+ using QList<T>::prepend;
+ using QList<T>::insert;
+ using QList<T>::removeAt;
+ using QList<T>::clear;
+
+private:
+ Q_DISABLE_COPY(KisSafeReadList);
+};
+
+
+#define FOREACH_SAFE(_iter, _container) \
+ for(_iter = _container.constBegin(); \
+ _iter != _container.constEnd(); \
+ _iter++)
+
+
+#endif /* KIS_SAFE_READ_LIST_H_ */
diff --git a/krita/image/tests/kis_node_test.cpp b/krita/image/tests/kis_node_test.cpp
index a0606f4..0a13057 100644
--- a/krita/image/tests/kis_node_test.cpp
+++ b/krita/image/tests/kis_node_test.cpp
@@ -370,6 +370,81 @@ void KisNodeTest::testDirtyRegion()
#endif
}
+#define NUM_CYCLES 100000
+#define NUM_THREADS 30
+
+class VisibilityKiller : public QRunnable {
+public:
+ VisibilityKiller(KisNodeSP victimNode, KisNodeSP nastyChild)
+ : m_victimNode(victimNode),
+ m_nastyChild(nastyChild)
+ {}
+
+ void run() {
+
+ int visibility = 0;
+
+ for(int i = 0; i < NUM_CYCLES; i++) {
+ if(i % 3 == 0) {
+ m_nastyChild->setVisible(visibility++ & 0x1);
+ // qDebug() << "visibility" << i << m_nastyChild->visible();
+ }
+ else if (i%3 == 1){
+ KoProperties props;
+ props.setProperty("visible", true);
+
+ QList<KisNodeSP> visibleNodes =
+ m_victimNode->childNodes(QStringList("TestNodeB"), props);
+
+ foreach(KisNodeSP node, visibleNodes) {
+ m_nastyChild->setVisible(visibility++ & 0x1);
+ }
+ // qDebug() << visibleNodes;
+ }
+ else {
+ Q_ASSERT(m_victimNode->firstChild());
+ Q_ASSERT(m_victimNode->lastChild());
+
+ m_victimNode->firstChild()->setVisible(visibility++ & 0x1);
+ m_victimNode->lastChild()->setVisible(visibility++ & 0x1);
+ }
+ }
+ }
+
+private:
+ KisNodeSP m_victimNode;
+ KisNodeSP m_nastyChild;
+};
+
+
+void KisNodeTest::propertiesStressTest() {
+ KisNodeSP root = new TestNodeA();
+
+ KisNodeSP a = new TestNodeA();
+ KisNodeSP b = new TestNodeB();
+ KisNodeSP c = new TestNodeC();
+ root->add(a, 0);
+ root->add(b, 0);
+ root->add(c, 0);
+ a->setVisible(true);
+ b->setVisible(true);
+ c->setVisible(true);
+ a->setUserLocked(true);
+ b->setUserLocked(true);
+ c->setUserLocked(true);
+
+ QThreadPool threadPool;
+ threadPool.setMaxThreadCount(NUM_THREADS);
+
+ for(int i = 0; i< NUM_THREADS; i++) {
+ VisibilityKiller *killer = new VisibilityKiller(root, b);
+
+ threadPool.start(killer);
+ }
+
+ threadPool.waitForDone();
+}
+
QTEST_KDEMAIN(KisNodeTest, NoGUI)
#include "kis_node_test.moc"
diff --git a/krita/image/tests/kis_node_test.h b/krita/image/tests/kis_node_test.h
index c59b3be..b74cb7f 100644
--- a/krita/image/tests/kis_node_test.h
+++ b/krita/image/tests/kis_node_test.h
@@ -119,6 +119,8 @@ private slots:
void testSetDirty();
void testChildNodes();
void testDirtyRegion();
+
+ void propertiesStressTest();
};
#endif
More information about the kimageshop
mailing list