Hi Michael,

On 06/20/2018 08:38 PM, Michael S. Tsirkin wrote:

On Mon, Jun 04, 2018 at 05:55:17PM +0800, guangrong.xiao@gmail.com wrote:

quoted

From: Xiao Guangrong <redacted>

quoted

(1) https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/kfifo.h
(2) http://dpdk.org/doc/api/rte__ring_8h.html

Signed-off-by: Xiao Guangrong <redacted>

So instead of all this super-optimized trickiness, how about
a simple port of ptr_ring from linux?

That one isn't lockless but it's known to outperform
most others for a single producer/single consumer case.
And with a ton of networking going on,
who said it's such a hot spot? OTOH this implementation
has more barriers which slows down each individual thread.
It's also a source of bugs.

Thank you for pointing it out.

I just quickly went through the code of ptr_ring that is very nice and
really impressive. I will consider to port it to QEMU.

Further, atomic tricks this one uses are not fair so some threads can get
completely starved while others make progress. There's also no
chance to mix aggressive polling and sleeping with this
kind of scheme, so the starved thread will consume lots of
CPU.

So I'd like to see a simple ring used, and then a patch on top
switching to this tricky one with performance comparison
along with that.

I agree with you, i will make a version that uses a lock for multiple
producers and doing incremental optimizations based on it.

quoted

---
  migration/ring.h | 265 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 265 insertions(+)
  create mode 100644 migration/ring.h

diff --git a/migration/ring.h b/migration/ring.h
new file mode 100644
index 0000000000..da9b8bdcbb
--- /dev/null
+++ b/migration/ring.h

@@ -0,0 +1,265 @@
+/*
+ * Ring Buffer
+ *
+ * Multiple producers and single consumer are supported with lock free.
+ *
+ * Copyright (c) 2018 Tencent Inc
+ *
+ * Authors:
+ *  Xiao Guangrong <xiaoguangrong@tencent.com>
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2 or later.
+ * See the COPYING file in the top-level directory.
+ */
+
+#ifndef _RING__
+#define _RING__

Prefix Ring is too short.

Okay, will improve it.

quoted

+    atomic_set(&ring->data[index], NULL);
+
+    /*
+     * (B) smp_mb() is needed as we should read the entry out before
+     * updating ring->out as we did in __ring_get().
+     *
+     * (A) smp_wmb() is needed as we should make the entry be NULL before
+     * updating ring->out (which will make the entry be visible and usable).
+     */

I can't say I understand this all.
And the interaction of acquire/release semantics with smp_*
barriers is even scarier.

Hmm... the parallel accesses for these two indexes and the data stored
in the ring are subtle indeed. :(

quoted

+    atomic_store_release(&ring->out, ring->out + 1);
+
+    return data;
+}
+
+static inline int ring_put(Ring *ring, void *data)
+{
+    if (ring->flags & RING_MULTI_PRODUCER) {
+        return ring_mp_put(ring, data);
+    }
+    return __ring_put(ring, data);
+}
+
+static inline void *ring_get(Ring *ring)
+{
+    if (ring->flags & RING_MULTI_PRODUCER) {
+        return ring_mp_get(ring);
+    }
+    return __ring_get(ring);
+}
+#endif

A bunch of tricky barriers retries etc all over the place.  This sorely
needs *a lot of* unit tests. Where are they?

I used the code attached in this mail to test & benchmark the patches during
my development which does not dedicate for Ring, instead it is based
on the framework of compression.

Yes, test cases are useful and really needed, i will do it... :)