* virtio pull for 4.5 (was Re: [PULL] virtio: barrier rework+fixes)
From: Michael S. Tsirkin @ 2016-01-18 13:21 UTC (permalink / raw)
To: Linus Torvalds
Cc: aquini, kvm, peterz, benh, heiko.carstens, alexander.duyck,
virtualization, mingo, linux-arch, dave, linux, dbueso, richard,
bjorn.andersson, rmk+kernel, paulmck, james.hogan, arnd,
julian.calaby, boqun.feng, schwidefsky, stefanha, tglx, tony.luck,
netdev, linux-kernel, stable, minchan, david.vrabel, joe, akpm,
davem
In-Reply-To: <20160113182855-mutt-send-email-mst@redhat.com>
Hi Linus,
Just making sure nothing's wrong with this pull request.
If there's an issue, pls let me know!
Thanks!
On Wed, Jan 13, 2016 at 06:28:55PM +0200, Michael S. Tsirkin wrote:
> The following changes since commit afd2ff9b7e1b367172f18ba7f693dfb62bdcb2dc:
>
> Linux 4.4 (2016-01-10 15:01:32 -0800)
>
> are available in the git repository at:
>
> git://git.kernel.org/pub/scm/linux/kernel/git/mst/vhost.git tags/for_linus
>
> for you to fetch changes up to 43e361f23c49dbddf74f56ddf6cdd85c5dbff6da:
>
> checkpatch: add virt barriers (2016-01-12 20:47:08 +0200)
>
> ----------------------------------------------------------------
> virtio: barrier rework+fixes
>
> This adds a new kind of barrier, and reworks virtio and xen
> to use it.
> Plus some fixes here and there.
>
> Signed-off-by: Michael S. Tsirkin <mst@redhat.com>
>
> ----------------------------------------------------------------
>
> Yes I know that the patch by Davidlohr Bueso has a typo in the subject :(
>
> Davidlohr Bueso (1):
> lcoking/barriers, arch: Use smp barriers in smp_store_release()
>
> Michael S. Tsirkin (40):
> asm-generic: guard smp_store_release/load_acquire
> ia64: rename nop->iosapic_nop
> ia64: reuse asm-generic/barrier.h
> powerpc: reuse asm-generic/barrier.h
> s390: reuse asm-generic/barrier.h
> sparc: reuse asm-generic/barrier.h
> arm: reuse asm-generic/barrier.h
> arm64: reuse asm-generic/barrier.h
> metag: reuse asm-generic/barrier.h
> mips: reuse asm-generic/barrier.h
> x86/um: reuse asm-generic/barrier.h
> x86: reuse asm-generic/barrier.h
> asm-generic: add __smp_xxx wrappers
> powerpc: define __smp_xxx
> arm64: define __smp_xxx
> arm: define __smp_xxx
> blackfin: define __smp_xxx
> ia64: define __smp_xxx
> metag: define __smp_xxx
> mips: define __smp_xxx
> s390: define __smp_xxx
> sh: define __smp_xxx, fix smp_store_mb for !SMP
> sparc: define __smp_xxx
> tile: define __smp_xxx
> xtensa: define __smp_xxx
> x86: define __smp_xxx
> asm-generic: implement virt_xxx memory barriers
> Revert "virtio_ring: Update weak barriers to use dma_wmb/rmb"
> virtio_ring: update weak barriers to use virt_xxx
> sh: support 1 and 2 byte xchg
> sh: move xchg_cmpxchg to a header by itself
> virtio_ring: use virt_store_mb
> xenbus: use virt_xxx barriers
> xen/io: use virt_xxx barriers
> xen/events: use virt_xxx barriers
> s390: use generic memory barriers
> s390: more efficient smp barriers
> checkpatch.pl: add missing memory barriers
> checkpatch: check for __smp outside barrier.h
> checkpatch: add virt barriers
>
> Minchan Kim (2):
> virtio_balloon: fix race by fill and leak
> virtio_balloon: fix race between migration and ballooning
>
> Stefan Hajnoczi (1):
> virtio: make find_vqs() checkpatch.pl-friendly
>
> arch/arm/include/asm/barrier.h | 35 ++---------
> arch/arm64/include/asm/barrier.h | 19 ++----
> arch/blackfin/include/asm/barrier.h | 4 +-
> arch/ia64/include/asm/barrier.h | 24 +++-----
> arch/metag/include/asm/barrier.h | 55 +++++------------
> arch/mips/include/asm/barrier.h | 51 +++++-----------
> arch/powerpc/include/asm/barrier.h | 33 ++++------
> arch/s390/include/asm/barrier.h | 23 ++++---
> arch/sh/include/asm/barrier.h | 3 +-
> arch/sh/include/asm/cmpxchg-grb.h | 22 +++++++
> arch/sh/include/asm/cmpxchg-irq.h | 11 ++++
> arch/sh/include/asm/cmpxchg-llsc.h | 25 +-------
> arch/sh/include/asm/cmpxchg-xchg.h | 51 ++++++++++++++++
> arch/sh/include/asm/cmpxchg.h | 3 +
> arch/sparc/include/asm/barrier_32.h | 1 -
> arch/sparc/include/asm/barrier_64.h | 29 ++-------
> arch/sparc/include/asm/processor.h | 3 -
> arch/tile/include/asm/barrier.h | 9 +--
> arch/x86/include/asm/barrier.h | 36 +++++------
> arch/x86/um/asm/barrier.h | 9 +--
> arch/xtensa/include/asm/barrier.h | 4 +-
> drivers/virtio/virtio_pci_common.h | 2 +-
> include/asm-generic/barrier.h | 106 ++++++++++++++++++++++++++++++---
> include/linux/virtio_config.h | 2 +-
> include/linux/virtio_ring.h | 21 +++++--
> include/xen/interface/io/ring.h | 16 ++---
> arch/ia64/kernel/iosapic.c | 6 +-
> drivers/gpu/drm/virtio/virtgpu_kms.c | 2 +-
> drivers/misc/mic/card/mic_virtio.c | 2 +-
> drivers/remoteproc/remoteproc_virtio.c | 2 +-
> drivers/rpmsg/virtio_rpmsg_bus.c | 2 +-
> drivers/s390/virtio/kvm_virtio.c | 2 +-
> drivers/s390/virtio/virtio_ccw.c | 2 +-
> drivers/virtio/virtio_balloon.c | 4 +-
> drivers/virtio/virtio_input.c | 2 +-
> drivers/virtio/virtio_mmio.c | 2 +-
> drivers/virtio/virtio_pci_common.c | 4 +-
> drivers/virtio/virtio_pci_modern.c | 2 +-
> drivers/virtio/virtio_ring.c | 15 +++--
> drivers/xen/events/events_fifo.c | 3 +-
> drivers/xen/xenbus/xenbus_comms.c | 8 +--
> mm/balloon_compaction.c | 4 +-
> Documentation/memory-barriers.txt | 28 +++++++--
> scripts/checkpatch.pl | 33 +++++++++-
> 44 files changed, 401 insertions(+), 319 deletions(-)
> create mode 100644 arch/sh/include/asm/cmpxchg-xchg.h
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Herbert Xu @ 2016-01-18 8:19 UTC (permalink / raw)
To: paulmck
Cc: linux-mips, linux-ia64, mst, peterz, will.deacon, virtualization,
hpa, sparclinux, mingo, linux-arch, linux-s390, linux, arnd,
linux-sh, mpe, x86, Linus Torvalds, xen-devel, mingo,
linux-xtensa, james.hogan, user-mode-linux-devel,
stefano.stabellini, adi-buildroot-devel, Leonid.Yegoshin,
ddaney.cavm, tglx, linux-metag, linux-arm-kernel, andrew.cooper3,
linux-kernel, ralf, joe
In-Reply-To: <20160114204827.GE3818@linux.vnet.ibm.com>
Paul E. McKenney <paulmck@linux.vnet.ibm.com> wrote:
>
> You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
> smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
> The reason for this is that smp_read_barrier_depends() must order the
> pointer load against any subsequent read or write through a dereference
> of that pointer. For example:
>
> p = READ_ONCE(gp);
> smp_rmb();
> r1 = p->a; /* ordered by smp_rmb(). */
> p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
> r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
>
> In contrast:
>
> p = READ_ONCE(gp);
> smp_read_barrier_depends();
> r1 = p->a; /* ordered by smp_read_barrier_depends(). */
> p->b = 42; /* ordered by smp_read_barrier_depends(). */
> r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
>
> Again, if your hardware maintains local ordering for address
> and data dependencies, you can have read_barrier_depends() and
> smp_read_barrier_depends() be no-ops like they are for most
> architectures.
>
> Does that help?
This is crazy! smp_rmb started out being strictly stronger than
smp_read_barrier_depends, when did this stop being the case?
--
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
^ permalink raw reply
* [PATCH RFC] vhost: convert pre sorted vhost memory array to interval tree
From: Jason Wang @ 2016-01-18 2:42 UTC (permalink / raw)
To: mst, kvm, virtualization, netdev, linux-kernel
Current pre-sorted memory region array has some limitations for future
device IOTLB conversion:
1) need extra work for adding and removing a single region, and it's
expected to be slow because of sorting or memory re-allocation.
2) need extra work of removing a large range which may intersect
several regions with different size.
3) need trick for a replacement policy like LRU
To overcome the above shortcomings, this patch convert it to interval
tree which can easily address the above issue with almost no extra
work.
The patch could be used for:
- Extend the current API and only let the userspace to send diffs of
memory table.
- Simplify Device IOTLB implementation.
Signed-off-by: Jason Wang <jasowang@redhat.com>
---
drivers/vhost/net.c | 8 +--
drivers/vhost/vhost.c | 179 +++++++++++++++++++++++++++-----------------------
drivers/vhost/vhost.h | 27 ++++++--
3 files changed, 125 insertions(+), 89 deletions(-)
diff --git a/drivers/vhost/net.c b/drivers/vhost/net.c
index 9eda69e..481db96 100644
--- a/drivers/vhost/net.c
+++ b/drivers/vhost/net.c
@@ -968,20 +968,20 @@ static long vhost_net_reset_owner(struct vhost_net *n)
struct socket *tx_sock = NULL;
struct socket *rx_sock = NULL;
long err;
- struct vhost_memory *memory;
+ struct vhost_umem *umem;
mutex_lock(&n->dev.mutex);
err = vhost_dev_check_owner(&n->dev);
if (err)
goto done;
- memory = vhost_dev_reset_owner_prepare();
- if (!memory) {
+ umem = vhost_dev_reset_owner_prepare();
+ if (!umem) {
err = -ENOMEM;
goto done;
}
vhost_net_stop(n, &tx_sock, &rx_sock);
vhost_net_flush(n);
- vhost_dev_reset_owner(&n->dev, memory);
+ vhost_dev_reset_owner(&n->dev, umem);
vhost_net_vq_reset(n);
done:
mutex_unlock(&n->dev.mutex);
diff --git a/drivers/vhost/vhost.c b/drivers/vhost/vhost.c
index ad2146a..851dce8 100644
--- a/drivers/vhost/vhost.c
+++ b/drivers/vhost/vhost.c
@@ -27,6 +27,7 @@
#include <linux/cgroup.h>
#include <linux/module.h>
#include <linux/sort.h>
+#include <linux/interval_tree_generic.h>
#include "vhost.h"
@@ -42,6 +43,10 @@ enum {
#define vhost_used_event(vq) ((__virtio16 __user *)&vq->avail->ring[vq->num])
#define vhost_avail_event(vq) ((__virtio16 __user *)&vq->used->ring[vq->num])
+INTERVAL_TREE_DEFINE(struct vhost_umem_node,
+ rb, __u64, __subtree_last,
+ START, LAST, , vhost_umem_interval_tree);
+
#ifdef CONFIG_VHOST_CROSS_ENDIAN_LEGACY
static void vhost_vq_reset_user_be(struct vhost_virtqueue *vq)
{
@@ -275,7 +280,7 @@ static void vhost_vq_reset(struct vhost_dev *dev,
vq->call_ctx = NULL;
vq->call = NULL;
vq->log_ctx = NULL;
- vq->memory = NULL;
+ vq->umem = NULL;
vq->is_le = virtio_legacy_is_little_endian();
vhost_vq_reset_user_be(vq);
}
@@ -381,7 +386,7 @@ void vhost_dev_init(struct vhost_dev *dev,
mutex_init(&dev->mutex);
dev->log_ctx = NULL;
dev->log_file = NULL;
- dev->memory = NULL;
+ dev->umem = NULL;
dev->mm = NULL;
spin_lock_init(&dev->work_lock);
INIT_LIST_HEAD(&dev->work_list);
@@ -486,27 +491,36 @@ err_mm:
}
EXPORT_SYMBOL_GPL(vhost_dev_set_owner);
-struct vhost_memory *vhost_dev_reset_owner_prepare(void)
+static void *vhost_kvzalloc(unsigned long size)
+{
+ void *n = kzalloc(size, GFP_KERNEL | __GFP_NOWARN | __GFP_REPEAT);
+
+ if (!n)
+ n = vzalloc(size);
+ return n;
+}
+
+struct vhost_umem *vhost_dev_reset_owner_prepare(void)
{
- return kmalloc(offsetof(struct vhost_memory, regions), GFP_KERNEL);
+ return vhost_kvzalloc(sizeof(struct vhost_umem));
}
EXPORT_SYMBOL_GPL(vhost_dev_reset_owner_prepare);
/* Caller should have device mutex */
-void vhost_dev_reset_owner(struct vhost_dev *dev, struct vhost_memory *memory)
+void vhost_dev_reset_owner(struct vhost_dev *dev, struct vhost_umem *umem)
{
int i;
vhost_dev_cleanup(dev, true);
/* Restore memory to default empty mapping. */
- memory->nregions = 0;
- dev->memory = memory;
+ INIT_LIST_HEAD(&umem->umem_list);
+ dev->umem = umem;
/* We don't need VQ locks below since vhost_dev_cleanup makes sure
* VQs aren't running.
*/
for (i = 0; i < dev->nvqs; ++i)
- dev->vqs[i]->memory = memory;
+ dev->vqs[i]->umem = umem;
}
EXPORT_SYMBOL_GPL(vhost_dev_reset_owner);
@@ -523,6 +537,19 @@ void vhost_dev_stop(struct vhost_dev *dev)
}
EXPORT_SYMBOL_GPL(vhost_dev_stop);
+static void vhost_umem_clean(struct vhost_dev *dev)
+{
+ struct vhost_umem_node *node, *tmp;
+ struct vhost_umem *umem = dev->umem;
+
+ list_for_each_entry_safe(node, tmp, &umem->umem_list, link) {
+ vhost_umem_interval_tree_remove(node, &umem->umem_tree);
+ list_del(&node->link);
+ kvfree(node);
+ }
+ kvfree(umem);
+}
+
/* Caller should have device mutex if and only if locked is set */
void vhost_dev_cleanup(struct vhost_dev *dev, bool locked)
{
@@ -549,8 +576,8 @@ void vhost_dev_cleanup(struct vhost_dev *dev, bool locked)
fput(dev->log_file);
dev->log_file = NULL;
/* No one will access memory at this point */
- kvfree(dev->memory);
- dev->memory = NULL;
+ vhost_umem_clean(dev);
+ dev->umem = NULL;
WARN_ON(!list_empty(&dev->work_list));
if (dev->worker) {
kthread_stop(dev->worker);
@@ -576,25 +603,25 @@ static int log_access_ok(void __user *log_base, u64 addr, unsigned long sz)
}
/* Caller should have vq mutex and device mutex. */
-static int vq_memory_access_ok(void __user *log_base, struct vhost_memory *mem,
+static int vq_memory_access_ok(void __user *log_base, struct vhost_umem *umem,
int log_all)
{
- int i;
+ struct vhost_umem_node *node;
- if (!mem)
+ if (!umem)
return 0;
- for (i = 0; i < mem->nregions; ++i) {
- struct vhost_memory_region *m = mem->regions + i;
- unsigned long a = m->userspace_addr;
- if (m->memory_size > ULONG_MAX)
+ list_for_each_entry(node, &umem->umem_list, link) {
+ unsigned long a = node->userspace_addr;
+
+ if (node->size > ULONG_MAX)
return 0;
else if (!access_ok(VERIFY_WRITE, (void __user *)a,
- m->memory_size))
+ node->size))
return 0;
else if (log_all && !log_access_ok(log_base,
- m->guest_phys_addr,
- m->memory_size))
+ node->start,
+ node->size))
return 0;
}
return 1;
@@ -602,7 +629,7 @@ static int vq_memory_access_ok(void __user *log_base, struct vhost_memory *mem,
/* Can we switch to this memory table? */
/* Caller should have device mutex but not vq mutex */
-static int memory_access_ok(struct vhost_dev *d, struct vhost_memory *mem,
+static int memory_access_ok(struct vhost_dev *d, struct vhost_umem *umem,
int log_all)
{
int i;
@@ -615,7 +642,8 @@ static int memory_access_ok(struct vhost_dev *d, struct vhost_memory *mem,
log = log_all || vhost_has_feature(d->vqs[i], VHOST_F_LOG_ALL);
/* If ring is inactive, will check when it's enabled. */
if (d->vqs[i]->private_data)
- ok = vq_memory_access_ok(d->vqs[i]->log_base, mem, log);
+ ok = vq_memory_access_ok(d->vqs[i]->log_base,
+ umem, log);
else
ok = 1;
mutex_unlock(&d->vqs[i]->mutex);
@@ -642,7 +670,7 @@ static int vq_access_ok(struct vhost_virtqueue *vq, unsigned int num,
/* Caller should have device mutex but not vq mutex */
int vhost_log_access_ok(struct vhost_dev *dev)
{
- return memory_access_ok(dev, dev->memory, 1);
+ return memory_access_ok(dev, dev->umem, 1);
}
EXPORT_SYMBOL_GPL(vhost_log_access_ok);
@@ -653,7 +681,7 @@ static int vq_log_access_ok(struct vhost_virtqueue *vq,
{
size_t s = vhost_has_feature(vq, VIRTIO_RING_F_EVENT_IDX) ? 2 : 0;
- return vq_memory_access_ok(log_base, vq->memory,
+ return vq_memory_access_ok(log_base, vq->umem,
vhost_has_feature(vq, VHOST_F_LOG_ALL)) &&
(!vq->log_used || log_access_ok(log_base, vq->log_addr,
sizeof *vq->used +
@@ -669,28 +697,12 @@ int vhost_vq_access_ok(struct vhost_virtqueue *vq)
}
EXPORT_SYMBOL_GPL(vhost_vq_access_ok);
-static int vhost_memory_reg_sort_cmp(const void *p1, const void *p2)
-{
- const struct vhost_memory_region *r1 = p1, *r2 = p2;
- if (r1->guest_phys_addr < r2->guest_phys_addr)
- return 1;
- if (r1->guest_phys_addr > r2->guest_phys_addr)
- return -1;
- return 0;
-}
-
-static void *vhost_kvzalloc(unsigned long size)
-{
- void *n = kzalloc(size, GFP_KERNEL | __GFP_NOWARN | __GFP_REPEAT);
-
- if (!n)
- n = vzalloc(size);
- return n;
-}
-
static long vhost_set_memory(struct vhost_dev *d, struct vhost_memory __user *m)
{
- struct vhost_memory mem, *newmem, *oldmem;
+ struct vhost_memory mem, *newmem;
+ struct vhost_memory_region *region;
+ struct vhost_umem_node *node;
+ struct vhost_umem *newumem, *oldumem;
unsigned long size = offsetof(struct vhost_memory, regions);
int i;
@@ -710,24 +722,51 @@ static long vhost_set_memory(struct vhost_dev *d, struct vhost_memory __user *m)
kvfree(newmem);
return -EFAULT;
}
- sort(newmem->regions, newmem->nregions, sizeof(*newmem->regions),
- vhost_memory_reg_sort_cmp, NULL);
- if (!memory_access_ok(d, newmem, 0)) {
+ newumem = vhost_kvzalloc(sizeof(*newumem));
+ if (!newumem) {
kvfree(newmem);
- return -EFAULT;
+ return -ENOMEM;
+ }
+
+ newumem->umem_tree = RB_ROOT;
+ INIT_LIST_HEAD(&newumem->umem_list);
+
+ for (region = newmem->regions;
+ region < newmem->regions + mem.nregions;
+ region++) {
+ node = vhost_kvzalloc(sizeof(*node));
+ if (!node)
+ goto err;
+ node->start = region->guest_phys_addr;
+ node->size = region->memory_size;
+ node->last = node->start + node->size - 1;
+ node->userspace_addr = region->userspace_addr;
+ INIT_LIST_HEAD(&node->link);
+ list_add_tail(&node->link, &newumem->umem_list);
+ vhost_umem_interval_tree_insert(node, &newumem->umem_tree);
}
- oldmem = d->memory;
- d->memory = newmem;
+
+ if (!memory_access_ok(d, newumem, 0))
+ goto err;
+
+ oldumem = d->umem;
+ d->umem = newumem;
/* All memory accesses are done under some VQ mutex. */
for (i = 0; i < d->nvqs; ++i) {
mutex_lock(&d->vqs[i]->mutex);
- d->vqs[i]->memory = newmem;
+ d->vqs[i]->umem = newumem;
mutex_unlock(&d->vqs[i]->mutex);
}
- kvfree(oldmem);
+
+ kvfree(newmem);
return 0;
+
+err:
+ vhost_umem_clean(d);
+ kvfree(newmem);
+ return -EFAULT;
}
long vhost_vring_ioctl(struct vhost_dev *d, int ioctl, void __user *argp)
@@ -1017,28 +1056,6 @@ done:
}
EXPORT_SYMBOL_GPL(vhost_dev_ioctl);
-static const struct vhost_memory_region *find_region(struct vhost_memory *mem,
- __u64 addr, __u32 len)
-{
- const struct vhost_memory_region *reg;
- int start = 0, end = mem->nregions;
-
- while (start < end) {
- int slot = start + (end - start) / 2;
- reg = mem->regions + slot;
- if (addr >= reg->guest_phys_addr)
- end = slot;
- else
- start = slot + 1;
- }
-
- reg = mem->regions + start;
- if (addr >= reg->guest_phys_addr &&
- reg->guest_phys_addr + reg->memory_size > addr)
- return reg;
- return NULL;
-}
-
/* TODO: This is really inefficient. We need something like get_user()
* (instruction directly accesses the data, with an exception table entry
* returning -EFAULT). See Documentation/x86/exception-tables.txt.
@@ -1180,29 +1197,29 @@ EXPORT_SYMBOL_GPL(vhost_init_used);
static int translate_desc(struct vhost_virtqueue *vq, u64 addr, u32 len,
struct iovec iov[], int iov_size)
{
- const struct vhost_memory_region *reg;
- struct vhost_memory *mem;
+ const struct vhost_umem_node *node;
+ struct vhost_umem *umem = vq->umem;
struct iovec *_iov;
u64 s = 0;
int ret = 0;
- mem = vq->memory;
while ((u64)len > s) {
u64 size;
if (unlikely(ret >= iov_size)) {
ret = -ENOBUFS;
break;
}
- reg = find_region(mem, addr, len);
- if (unlikely(!reg)) {
+ node = vhost_umem_interval_tree_iter_first(&umem->umem_tree,
+ addr, addr + len - 1);
+ if (node == NULL || node->start > addr) {
ret = -EFAULT;
break;
}
_iov = iov + ret;
- size = reg->memory_size - addr + reg->guest_phys_addr;
+ size = node->size - addr + node->start;
_iov->iov_len = min((u64)len - s, size);
_iov->iov_base = (void __user *)(unsigned long)
- (reg->userspace_addr + addr - reg->guest_phys_addr);
+ (node->userspace_addr + addr - node->start);
s += size;
addr += size;
++ret;
diff --git a/drivers/vhost/vhost.h b/drivers/vhost/vhost.h
index d3f7674..5d64393 100644
--- a/drivers/vhost/vhost.h
+++ b/drivers/vhost/vhost.h
@@ -52,6 +52,25 @@ struct vhost_log {
u64 len;
};
+#define START(node) ((node)->start)
+#define LAST(node) ((node)->last)
+
+struct vhost_umem_node {
+ struct rb_node rb;
+ struct list_head link;
+ __u64 start;
+ __u64 last;
+ __u64 size;
+ __u64 userspace_addr;
+ __u64 flags_padding;
+ __u64 __subtree_last;
+};
+
+struct vhost_umem {
+ struct rb_root umem_tree;
+ struct list_head umem_list;
+};
+
/* The virtqueue structure describes a queue attached to a device. */
struct vhost_virtqueue {
struct vhost_dev *dev;
@@ -100,7 +119,7 @@ struct vhost_virtqueue {
struct iovec *indirect;
struct vring_used_elem *heads;
/* Protected by virtqueue mutex. */
- struct vhost_memory *memory;
+ struct vhost_umem *umem;
void *private_data;
u64 acked_features;
/* Log write descriptors */
@@ -117,7 +136,6 @@ struct vhost_virtqueue {
};
struct vhost_dev {
- struct vhost_memory *memory;
struct mm_struct *mm;
struct mutex mutex;
struct vhost_virtqueue **vqs;
@@ -127,14 +145,15 @@ struct vhost_dev {
spinlock_t work_lock;
struct list_head work_list;
struct task_struct *worker;
+ struct vhost_umem *umem;
};
void vhost_dev_init(struct vhost_dev *, struct vhost_virtqueue **vqs, int nvqs);
long vhost_dev_set_owner(struct vhost_dev *dev);
bool vhost_dev_has_owner(struct vhost_dev *dev);
long vhost_dev_check_owner(struct vhost_dev *);
-struct vhost_memory *vhost_dev_reset_owner_prepare(void);
-void vhost_dev_reset_owner(struct vhost_dev *, struct vhost_memory *);
+struct vhost_umem *vhost_dev_reset_owner_prepare(void);
+void vhost_dev_reset_owner(struct vhost_dev *, struct vhost_umem *);
void vhost_dev_cleanup(struct vhost_dev *, bool locked);
void vhost_dev_stop(struct vhost_dev *);
long vhost_dev_ioctl(struct vhost_dev *, unsigned int ioctl, void __user *argp);
--
2.5.0
^ permalink raw reply related
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-15 22:01 UTC (permalink / raw)
To: Peter Zijlstra
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115212912.GN3421@worktop>
On Fri, Jan 15, 2016 at 10:29:12PM +0100, Peter Zijlstra wrote:
> On Fri, Jan 15, 2016 at 09:39:12AM -0800, Paul E. McKenney wrote:
> > Should we start putting litmus tests for the various examples
> > somewhere, perhaps in a litmus-tests directory within each participating
> > architecture? I have a pile of powerpc-related litmus tests on my laptop,
> > but they probably aren't doing all that much good there.
>
> Yeah, or a version of them in C that we can 'compile'?
That would be good as well. I am guessing that architecture-specific
litmus tests will also be needed, but you are right that
architecture-independent versions are higher priority.
> > commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
> > Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > Date: Fri Jan 15 09:30:42 2016 -0800
> >
> > documentation: Distinguish between local and global transitivity
> >
> > The introduction of smp_load_acquire() and smp_store_release() had
> > the side effect of introducing a weaker notion of transitivity:
> > The transitivity of full smp_mb() barriers is global, but that
> > of smp_store_release()/smp_load_acquire() chains is local. This
> > commit therefore introduces the notion of local transitivity and
> > gives an example.
> >
> > Reported-by: Peter Zijlstra <peterz@infradead.org>
> > Reported-by: Will Deacon <will.deacon@arm.com>
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
>
> I think it fails to mention smp_mb__after_release_acquire(), although I
> suspect we didn't actually introduce the primitive yet, which raises the
> point, do we want to?
Well, it is not in v4.4. I believe that we need good use cases before
we add it.
Thanx, Paul
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-15 21:58 UTC (permalink / raw)
To: Peter Zijlstra
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115212714.GM3421@worktop>
On Fri, Jan 15, 2016 at 10:27:14PM +0100, Peter Zijlstra wrote:
> On Fri, Jan 15, 2016 at 09:46:12AM -0800, Paul E. McKenney wrote:
> > On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
>
> > > And the stuff we're confused about is how best to express the difference
> > > and guarantees of these two forms of transitivity and how exactly they
> > > interact.
> >
> > Hoping my memory-barrier.txt patch helps here...
>
> Yes, that seems a good start. But yesterday you raised the 'fun' point
> of two globally ordered sequences connected by a single local link.
The conclusion that I am slowly coming to is that litmus tests should
not be thought of as linear chains, but rather as cycles. If you think
of it as a cycle, then it doesn't matter where the local link is, just
how many of them and how they are connected.
But I will admit that there are some rather strange litmus tests that
challenge this cycle-centric view, for example, the one shown below.
It turns out that herd and ppcmem disagree on the outcome. (The Power
architects side with ppcmem.)
> And I think I'm still confused on LWSYNC (in the smp_wmb case) when one
> of the stores looses a conflict, and if that scenario matters. If it
> does, we should inspect the same case for other barriers.
Indeed. I am still working on how these should be described. My
current thought is to be quite conservative on what ordering is
actually respected, however, the current task is formalizing how
RCU plays with the rest of the memory model.
Thanx, Paul
------------------------------------------------------------------------
PPC Overlapping Group-B sets version 4
""
(* When the Group-B sets from two different barriers involve instructions in
the same thread, within that thread one set must contain the other.
P0 P1 P2
Rx=1 Wy=1 Wz=2
dep. lwsync lwsync
Ry=0 Wz=1 Wx=1
Rz=1
assert(!(z=2))
Forbidden by ppcmem, allowed by herd.
*)
{
0:r1=x; 0:r2=y; 0:r3=z;
1:r1=x; 1:r2=y; 1:r3=z; 1:r4=1;
2:r1=x; 2:r2=y; 2:r3=z; 2:r4=1; 2:r5=2;
}
P0 | P1 | P2 ;
lwz r6,0(r1) | stw r4,0(r2) | stw r5,0(r3) ;
xor r7,r6,r6 | lwsync | lwsync ;
lwzx r7,r7,r2 | stw r4,0(r3) | stw r4,0(r1) ;
lwz r8,0(r3) | | ;
exists
(z=2 /\ 0:r6=1 /\ 0:r7=0 /\ 0:r8=1)
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Peter Zijlstra @ 2016-01-15 21:29 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115173912.GU3818@linux.vnet.ibm.com>
On Fri, Jan 15, 2016 at 09:39:12AM -0800, Paul E. McKenney wrote:
> Should we start putting litmus tests for the various examples
> somewhere, perhaps in a litmus-tests directory within each participating
> architecture? I have a pile of powerpc-related litmus tests on my laptop,
> but they probably aren't doing all that much good there.
Yeah, or a version of them in C that we can 'compile'?
>
> commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
> Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Date: Fri Jan 15 09:30:42 2016 -0800
>
> documentation: Distinguish between local and global transitivity
>
> The introduction of smp_load_acquire() and smp_store_release() had
> the side effect of introducing a weaker notion of transitivity:
> The transitivity of full smp_mb() barriers is global, but that
> of smp_store_release()/smp_load_acquire() chains is local. This
> commit therefore introduces the notion of local transitivity and
> gives an example.
>
> Reported-by: Peter Zijlstra <peterz@infradead.org>
> Reported-by: Will Deacon <will.deacon@arm.com>
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
I think it fails to mention smp_mb__after_release_acquire(), although I
suspect we didn't actually introduce the primitive yet, which raises the
point, do we want to?
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Peter Zijlstra @ 2016-01-15 21:27 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115174612.GV3818@linux.vnet.ibm.com>
On Fri, Jan 15, 2016 at 09:46:12AM -0800, Paul E. McKenney wrote:
> On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
> > And the stuff we're confused about is how best to express the difference
> > and guarantees of these two forms of transitivity and how exactly they
> > interact.
>
> Hoping my memory-barrier.txt patch helps here...
Yes, that seems a good start. But yesterday you raised the 'fun' point
of two globally ordered sequences connected by a single local link.
And I think I'm still confused on LWSYNC (in the smp_wmb case) when one
of the stores looses a conflict, and if that scenario matters. If it
does, we should inspect the same case for other barriers.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-15 19:28 UTC (permalink / raw)
To: Will Deacon
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115175401.GW3818@linux.vnet.ibm.com>
On Fri, Jan 15, 2016 at 09:54:01AM -0800, Paul E. McKenney wrote:
> On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
> > On Thu, Jan 14, 2016 at 02:55:10PM -0800, Paul E. McKenney wrote:
> > > On Thu, Jan 14, 2016 at 01:36:50PM -0800, Leonid Yegoshin wrote:
> > > > On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
> > > > >
> > > > >>On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
> > > > >>>
> > > > >>>The WRC+addr+addr is OK because data dependencies are not required to be
> > > > >>>transitive, in other words, they are not required to flow from one CPU to
> > > > >>>another without the help of an explicit memory barrier.
> > > > >>I don't see any reliable way to fit WRC+addr+addr into "DATA
> > > > >>DEPENDENCY BARRIERS" section recommendation to have data dependency
> > > > >>barrier between read of a shared pointer/index and read the shared
> > > > >>data based on that pointer. If you have this two reads, it doesn't
> > > > >>matter the rest of scenario, you should put the dependency barrier
> > > > >>in code anyway. If you don't do it in WRC+addr+addr scenario then
> > > > >>after years it can be easily changed to different scenario which
> > > > >>fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
> > > > >>fails.
> > > > >The trick is that lockless_dereference() contains an
> > > > >smp_read_barrier_depends():
> > > > >
> > > > >#define lockless_dereference(p) \
> > > > >({ \
> > > > > typeof(p) _________p1 = READ_ONCE(p); \
> > > > > smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
> > > > > (_________p1); \
> > > > >})
> > > > >
> > > > >Or am I missing your point?
> > > >
> > > > WRC+addr+addr has no any barrier. lockless_dereference() has a
> > > > barrier. I don't see a common points between this and that in your
> > > > answer, sorry.
> > >
> > > Me, I am wondering what WRC+addr+addr has to do with anything at all.
> >
> > See my earlier reply [1] (but also, your WRC Linux example looks more
> > like a variant on WWC and I couldn't really follow it).
>
> I will revisit my WRC Linux example. And yes, creating litmus tests
> that use non-fake dependencies is still a bit of an undertaking. :-/
> I am sure that it will seem more natural with time and experience...
Hmmm... You are quite right, I did do WWC. I need to change cpu2()'s
last access from a store to a load to get WRC. Plus the levels of
indirection definitely didn't match up, did they?
struct foo {
struct foo *next;
};
struct foo a;
struct foo b;
struct foo c = { &a };
struct foo d = { &b };
struct foo x = { &c };
struct foo y = { &d };
struct foo *r1, *r2, *r3;
void cpu0(void)
{
WRITE_ONCE(x.next, &y);
}
void cpu1(void)
{
r1 = lockless_dereference(x.next);
WRITE_ONCE(r1->next, &x);
}
void cpu2(void)
{
r2 = lockless_dereference(y.next);
r3 = READ_ONCE(r2->next);
}
In this case, it is legal to end the run with:
r1 == &y && r2 == &x && r3 == &c
Please see below for a ppcmem litmus test.
So, did I get it right this time? ;-)
Thanx, Paul
PS. And yes, working through this does help me understand the
benefits of fake dependencies. Why do you ask? ;-)
------------------------------------------------------------------------
PPC WRCnf+addrs
""
{
0:r2=x; 0:r3=y;
1:r2=x; 1:r3=y;
2:r2=x; 2:r3=y;
c=a; d=b; x=c; y=d;
}
P0 | P1 | P2 ;
stw r3,0(r2) | lwz r8,0(r2) | lwz r8,0(r3) ;
| stw r2,0(r3) | lwz r9,0(r8) ;
exists
(1:r8=y /\ 2:r8=x /\ 2:r9=c)
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Leonid Yegoshin @ 2016-01-15 18:54 UTC (permalink / raw)
To: Will Deacon, Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag, linux-arm-kernel, And
In-Reply-To: <20160115095756.GA2131@arm.com>
On 01/15/2016 01:57 AM, Will Deacon wrote:
> Paul,
>
>
> I think you figured this out while I was sleeping, but just to confirm:
>
> 1. The MIPS64 ISA doc [1] talks about SYNC in a way that applies only
> to memory accesses appearing in *program-order* before the SYNC
>
> 2. We need WRC+sync+addr to work, which means that the SYNC in P1 must
> also capture the store in P0 as being "before" the barrier. Leonid
> reckons it works, but his explanation [2] focussed on the address
> dependency in P2 as to why this works. If that is the case (i.e.
> address dependency provides global transitivity), then WRC+addr+addr
> should also work (even though its not required).
No, it is not correct. There is one old design which provides access to
core (thread0 + thread1) write-buffers for threads load in advance of it
is visible to other cores. It means, that WRC+sync+addr passes because
of SYNC in write thread and register dependency inside other thread but
WRC+addr+addr may fail because other core may get a stale data.
>
> 3. It seems that WRC+addr+addr doesn't work, so I'm still suspicious
> about WRC+sync+addr, because neither the architecture document or
> Leonid's explanation tell me that it should be forbidden.
>
> Will
>
> [1] https://imgtec.com/?do-download=4302
> [2] http://lkml.kernel.org/r/569565DA.2010903@imgtec.com (scroll to the end)
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-15 17:54 UTC (permalink / raw)
To: Will Deacon
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115102431.GB2131@arm.com>
On Fri, Jan 15, 2016 at 10:24:32AM +0000, Will Deacon wrote:
> On Thu, Jan 14, 2016 at 02:55:10PM -0800, Paul E. McKenney wrote:
> > On Thu, Jan 14, 2016 at 01:36:50PM -0800, Leonid Yegoshin wrote:
> > > On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
> > > >
> > > >>On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
> > > >>>
> > > >>>The WRC+addr+addr is OK because data dependencies are not required to be
> > > >>>transitive, in other words, they are not required to flow from one CPU to
> > > >>>another without the help of an explicit memory barrier.
> > > >>I don't see any reliable way to fit WRC+addr+addr into "DATA
> > > >>DEPENDENCY BARRIERS" section recommendation to have data dependency
> > > >>barrier between read of a shared pointer/index and read the shared
> > > >>data based on that pointer. If you have this two reads, it doesn't
> > > >>matter the rest of scenario, you should put the dependency barrier
> > > >>in code anyway. If you don't do it in WRC+addr+addr scenario then
> > > >>after years it can be easily changed to different scenario which
> > > >>fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
> > > >>fails.
> > > >The trick is that lockless_dereference() contains an
> > > >smp_read_barrier_depends():
> > > >
> > > >#define lockless_dereference(p) \
> > > >({ \
> > > > typeof(p) _________p1 = READ_ONCE(p); \
> > > > smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
> > > > (_________p1); \
> > > >})
> > > >
> > > >Or am I missing your point?
> > >
> > > WRC+addr+addr has no any barrier. lockless_dereference() has a
> > > barrier. I don't see a common points between this and that in your
> > > answer, sorry.
> >
> > Me, I am wondering what WRC+addr+addr has to do with anything at all.
>
> See my earlier reply [1] (but also, your WRC Linux example looks more
> like a variant on WWC and I couldn't really follow it).
I will revisit my WRC Linux example. And yes, creating litmus tests
that use non-fake dependencies is still a bit of an undertaking. :-/
I am sure that it will seem more natural with time and experience...
> > <Going back through earlier email>
> >
> > OK, so it looks like Will was asking not about WRC+addr+addr, but instead
> > about WRC+sync+addr. This would drop an smp_mb() into cpu2() in my
> > earlier example, which needs to provide ordering.
> >
> > I am guessing that the manual's "Older instructions which must be globally
> > performed when the SYNC instruction completes" provides the equivalent
> > of ARM/Power A-cumulativity, which can be thought of as transitivity
> > backwards in time.
>
> I couldn't make that leap. In particular, the manual's "Detailed
> Description" sections explicitly refer to program-order:
>
> Every synchronizable specified memory instruction (loads or stores or
> both) that occurs in the instruction stream before the SYNC
> instruction must reach a stage in the load/store datapath after which
> no instruction re-ordering is possible before any synchronizable
> specified memory instruction which occurs after the SYNC instruction
> in the instruction stream reaches the same stage in the load/store
> datapath.
>
> Will
>
> [1] http://lists.infradead.org/pipermail/linux-arm-kernel/2016-January/399765.html
All good points. I think we all agree that the MIPS documentation could
use significant help. And given that I work for the company that produced
the analogous documentation for PowerPC, that is saying something. ;-)
We simply can't know if MIPS's memory ordering is sufficient for the
Linux kernel given its current implementation of the ordering primitives
and its current documentation.
I feel a bit better than I did earlier due to Leonid's response to my
earlier litmus-test examples. But I do recommend some serious stress
testing of MIPS on a good set of litmus tests. Much nicer finding issues
that way than as random irreproducible strange behavior!
Thanx, Paul
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-15 17:46 UTC (permalink / raw)
To: Peter Zijlstra
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115091348.GA27936@worktop>
On Fri, Jan 15, 2016 at 10:13:48AM +0100, Peter Zijlstra wrote:
> On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
> > On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
> > > So smp_mb() provides transitivity, as do pairs of smp_store_release()
> > > and smp_read_acquire(),
> >
> > But they provide different grades of transitivity, which is where all
> > the confusion lays.
> >
> > smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
> >
> > Whereas the RCpc release+acquire is weakly so, only the two cpus
> > involved in the handover will agree on the order.
>
> And the stuff we're confused about is how best to express the difference
> and guarantees of these two forms of transitivity and how exactly they
> interact.
Hoping my memory-barrier.txt patch helps here...
> And smp_load_acquire()/smp_store_release() are RCpc because TSO archs
> and PPC. the atomic*_{acquire,release}() are RCpc because PPC and
> LOCK,UNLOCK are similarly RCpc because of PPC.
>
> Now we'd like PPC to stick a SYNC in either LOCK or UNLOCK so at least
> the locks are RCsc again, but they resist for performance reasons but
> waver because they don't want to be the ones finding all the nasty bugs
> because they're the only one.
I believe that the relevant proverb said something about starving to
death between two bales of hay... ;-)
> Now the thing I worry about, and still have not had an answer to is if
> weakly ordered MIPS will end up being RCsc or RCpc for their locks if
> they get implemented with SYNC_ACQUIRE and SYNC_RELEASE instead of the
> current SYNC.
It would be good to have better clarity on this, no two ways about it.
Thanx, Paul
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-15 17:39 UTC (permalink / raw)
To: Peter Zijlstra
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115085554.GF3421@worktop>
On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
> On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
> > So smp_mb() provides transitivity, as do pairs of smp_store_release()
> > and smp_read_acquire(),
>
> But they provide different grades of transitivity, which is where all
> the confusion lays.
>
> smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
>
> Whereas the RCpc release+acquire is weakly so, only the two cpus
> involved in the handover will agree on the order.
Good point!
Using grace periods in place of smp_mb() also provides strong/global
transitivity, but also insanely high latencies. ;-)
The patch below updates Documentation/memory-barriers.txt to define
local vs. global transitivity. The corresponding ppcmem litmus test
is included below as well.
Should we start putting litmus tests for the various examples
somewhere, perhaps in a litmus-tests directory within each participating
architecture? I have a pile of powerpc-related litmus tests on my laptop,
but they probably aren't doing all that much good there.
Thanx, Paul
------------------------------------------------------------------------
PPC local-transitive
""
{
0:r1=1; 0:r2=u; 0:r3=v; 0:r4=x; 0:r5=y; 0:r6=z;
1:r1=1; 1:r2=u; 1:r3=v; 1:r4=x; 1:r5=y; 1:r6=z;
2:r1=1; 2:r2=u; 2:r3=v; 2:r4=x; 2:r5=y; 2:r6=z;
3:r1=1; 3:r2=u; 3:r3=v; 3:r4=x; 3:r5=y; 3:r6=z;
}
P0 | P1 | P2 | P3 ;
lwz r9,0(r4) | lwz r9,0(r5) | lwz r9,0(r6) | stw r1,0(r3) ;
lwsync | lwsync | lwsync | sync ;
stw r1,0(r2) | lwz r8,0(r3) | stw r1,0(r7) | lwz r9,0(r2) ;
lwsync | lwz r7,0(r2) | | ;
stw r1,0(r5) | lwsync | | ;
| stw r1,0(r6) | | ;
exists
(* (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r8=0 /\ 3:r9=0) *)
(* (0:r9=1 /\ 1:r9=1 /\ 2:r9=1) *)
(* (0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r7=0) *)
(0:r9=0 /\ 1:r9=1 /\ 2:r9=1 /\ 1:r7=0)
------------------------------------------------------------------------
commit 2cb4e83a1b5c89c8e39b8a64bd89269d05913e41
Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Date: Fri Jan 15 09:30:42 2016 -0800
documentation: Distinguish between local and global transitivity
The introduction of smp_load_acquire() and smp_store_release() had
the side effect of introducing a weaker notion of transitivity:
The transitivity of full smp_mb() barriers is global, but that
of smp_store_release()/smp_load_acquire() chains is local. This
commit therefore introduces the notion of local transitivity and
gives an example.
Reported-by: Peter Zijlstra <peterz@infradead.org>
Reported-by: Will Deacon <will.deacon@arm.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index c66ba46d8079..d8109ed99342 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -1318,8 +1318,82 @@ or a level of cache, CPU 2 might have early access to CPU 1's writes.
General barriers are therefore required to ensure that all CPUs agree
on the combined order of CPU 1's and CPU 2's accesses.
-To reiterate, if your code requires transitivity, use general barriers
-throughout.
+General barriers provide "global transitivity", so that all CPUs will
+agree on the order of operations. In contrast, a chain of release-acquire
+pairs provides only "local transitivity", so that only those CPUs on
+the chain are guaranteed to agree on the combined order of the accesses.
+For example, switching to C code in deference to Herman Hollerith:
+
+ int u, v, x, y, z;
+
+ void cpu0(void)
+ {
+ r0 = smp_load_acquire(&x);
+ WRITE_ONCE(u, 1);
+ smp_store_release(&y, 1);
+ }
+
+ void cpu1(void)
+ {
+ r1 = smp_load_acquire(&y);
+ r4 = READ_ONCE(v);
+ r5 = READ_ONCE(u);
+ smp_store_release(&z, 1);
+ }
+
+ void cpu2(void)
+ {
+ r2 = smp_load_acquire(&z);
+ smp_store_release(&x, 1);
+ }
+
+ void cpu3(void)
+ {
+ WRITE_ONCE(v, 1);
+ smp_mb();
+ r3 = READ_ONCE(u);
+ }
+
+Because cpu0(), cpu1(), and cpu2() participate in a local transitive
+chain of smp_store_release()/smp_load_acquire() pairs, the following
+outcome is prohibited:
+
+ r0 == 1 && r1 == 1 && r2 == 1
+
+Furthermore, because of the release-acquire relationship between cpu0()
+and cpu1(), cpu1() must see cpu0()'s writes, so that the following
+outcome is prohibited:
+
+ r1 == 1 && r5 == 0
+
+However, the transitivity of release-acquire is local to the participating
+CPUs and does not apply to cpu3(). Therefore, the following outcome
+is possible:
+
+ r0 == 0 && r1 == 1 && r2 == 1 && r3 == 0 && r4 == 0
+
+Although cpu0(), cpu1(), and cpu2() will see their respective reads and
+writes in order, CPUs not involved in the release-acquire chain might
+well disagree on the order. This disagreement stems from the fact that
+the weak memory-barrier instructions used to implement smp_load_acquire()
+and smp_store_release() are not required to order prior stores against
+subsequent loads in all cases. This means that cpu3() can see cpu0()'s
+store to u as happening -after- cpu1()'s load from v, even though
+both cpu0() and cpu1() agree that these two operations occurred in the
+intended order.
+
+However, please keep in mind that smp_load_acquire() is not magic.
+In particular, it simply reads from its argument with ordering. It does
+-not- ensure that any particular value will be read. Therefore, the
+following outcome is possible:
+
+ r0 == 0 && r1 == 0 && r2 == 0 && r5 == 0
+
+Note that this outcome can happen even on a mythical sequentially
+consistent system where nothing is ever reordered.
+
+To reiterate, if your code requires global transitivity, use general
+barriers throughout.
========================
^ permalink raw reply related
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Will Deacon @ 2016-01-15 10:24 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160114225510.GJ3818@linux.vnet.ibm.com>
On Thu, Jan 14, 2016 at 02:55:10PM -0800, Paul E. McKenney wrote:
> On Thu, Jan 14, 2016 at 01:36:50PM -0800, Leonid Yegoshin wrote:
> > On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
> > >
> > >>On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
> > >>>
> > >>>The WRC+addr+addr is OK because data dependencies are not required to be
> > >>>transitive, in other words, they are not required to flow from one CPU to
> > >>>another without the help of an explicit memory barrier.
> > >>I don't see any reliable way to fit WRC+addr+addr into "DATA
> > >>DEPENDENCY BARRIERS" section recommendation to have data dependency
> > >>barrier between read of a shared pointer/index and read the shared
> > >>data based on that pointer. If you have this two reads, it doesn't
> > >>matter the rest of scenario, you should put the dependency barrier
> > >>in code anyway. If you don't do it in WRC+addr+addr scenario then
> > >>after years it can be easily changed to different scenario which
> > >>fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
> > >>fails.
> > >The trick is that lockless_dereference() contains an
> > >smp_read_barrier_depends():
> > >
> > >#define lockless_dereference(p) \
> > >({ \
> > > typeof(p) _________p1 = READ_ONCE(p); \
> > > smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
> > > (_________p1); \
> > >})
> > >
> > >Or am I missing your point?
> >
> > WRC+addr+addr has no any barrier. lockless_dereference() has a
> > barrier. I don't see a common points between this and that in your
> > answer, sorry.
>
> Me, I am wondering what WRC+addr+addr has to do with anything at all.
See my earlier reply [1] (but also, your WRC Linux example looks more
like a variant on WWC and I couldn't really follow it).
> <Going back through earlier email>
>
> OK, so it looks like Will was asking not about WRC+addr+addr, but instead
> about WRC+sync+addr. This would drop an smp_mb() into cpu2() in my
> earlier example, which needs to provide ordering.
>
> I am guessing that the manual's "Older instructions which must be globally
> performed when the SYNC instruction completes" provides the equivalent
> of ARM/Power A-cumulativity, which can be thought of as transitivity
> backwards in time.
I couldn't make that leap. In particular, the manual's "Detailed
Description" sections explicitly refer to program-order:
Every synchronizable specified memory instruction (loads or stores or
both) that occurs in the instruction stream before the SYNC
instruction must reach a stage in the load/store datapath after which
no instruction re-ordering is possible before any synchronizable
specified memory instruction which occurs after the SYNC instruction
in the instruction stream reaches the same stage in the load/store
datapath.
Will
[1] http://lists.infradead.org/pipermail/linux-arm-kernel/2016-January/399765.html
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Will Deacon @ 2016-01-15 9:57 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160114222046.GH3818@linux.vnet.ibm.com>
Paul,
On Thu, Jan 14, 2016 at 02:20:46PM -0800, Paul E. McKenney wrote:
> On Thu, Jan 14, 2016 at 01:24:34PM -0800, Leonid Yegoshin wrote:
> > It is not so simple, I mean "local ordering for address and data
> > dependencies". Local ordering is NOT enough. It happens that current
> > MIPS R6 doesn't require in your example smp_read_barrier_depends()
> > but in discussion it comes out that it may not. Because without
> > smp_read_barrier_depends() your example can be a part of Will's
> > WRC+addr+addr and we found some design which easily can bump into
> > this test. And that design actually performs "local ordering for
> > address and data dependencies" too.
>
> As noted in another email in this thread, I do not believe that
> WRC+addr+addr needs to be prohibited. Sounds like Will and I need to
> get our story straight, though.
I think you figured this out while I was sleeping, but just to confirm:
1. The MIPS64 ISA doc [1] talks about SYNC in a way that applies only
to memory accesses appearing in *program-order* before the SYNC
2. We need WRC+sync+addr to work, which means that the SYNC in P1 must
also capture the store in P0 as being "before" the barrier. Leonid
reckons it works, but his explanation [2] focussed on the address
dependency in P2 as to why this works. If that is the case (i.e.
address dependency provides global transitivity), then WRC+addr+addr
should also work (even though its not required).
3. It seems that WRC+addr+addr doesn't work, so I'm still suspicious
about WRC+sync+addr, because neither the architecture document or
Leonid's explanation tell me that it should be forbidden.
Will
[1] https://imgtec.com/?do-download=4302
[2] http://lkml.kernel.org/r/569565DA.2010903@imgtec.com (scroll to the end)
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Peter Zijlstra @ 2016-01-15 9:13 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160115085554.GF3421@worktop>
On Fri, Jan 15, 2016 at 09:55:54AM +0100, Peter Zijlstra wrote:
> On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
> > So smp_mb() provides transitivity, as do pairs of smp_store_release()
> > and smp_read_acquire(),
>
> But they provide different grades of transitivity, which is where all
> the confusion lays.
>
> smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
>
> Whereas the RCpc release+acquire is weakly so, only the two cpus
> involved in the handover will agree on the order.
And the stuff we're confused about is how best to express the difference
and guarantees of these two forms of transitivity and how exactly they
interact.
And smp_load_acquire()/smp_store_release() are RCpc because TSO archs
and PPC. the atomic*_{acquire,release}() are RCpc because PPC and
LOCK,UNLOCK are similarly RCpc because of PPC.
Now we'd like PPC to stick a SYNC in either LOCK or UNLOCK so at least
the locks are RCsc again, but they resist for performance reasons but
waver because they don't want to be the ones finding all the nasty bugs
because they're the only one.
Now the thing I worry about, and still have not had an answer to is if
weakly ordered MIPS will end up being RCsc or RCpc for their locks if
they get implemented with SYNC_ACQUIRE and SYNC_RELEASE instead of the
current SYNC.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Peter Zijlstra @ 2016-01-15 8:55 UTC (permalink / raw)
To: Paul E. McKenney
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Will Deacon,
virtualization, H. Peter Anvin, sparclinux, Ingo Molnar,
linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, Leonid Yegoshin,
ddaney.cavm, Thomas Gleixner, linux-metag
In-Reply-To: <20160114212913.GF3818@linux.vnet.ibm.com>
On Thu, Jan 14, 2016 at 01:29:13PM -0800, Paul E. McKenney wrote:
> So smp_mb() provides transitivity, as do pairs of smp_store_release()
> and smp_read_acquire(),
But they provide different grades of transitivity, which is where all
the confusion lays.
smp_mb() is strongly/globally transitive, all CPUs will agree on the order.
Whereas the RCpc release+acquire is weakly so, only the two cpus
involved in the handover will agree on the order.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Leonid Yegoshin @ 2016-01-15 1:07 UTC (permalink / raw)
To: paulmck
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <20160115004753.GN3818@linux.vnet.ibm.com>
On 01/14/2016 04:47 PM, Paul E. McKenney wrote:
> On Thu, Jan 14, 2016 at 03:33:40PM -0800, Leonid Yegoshin wrote:
>> Don't be fooled here by words "ordered" and "completed" - it is HW
>> design items and actually written poorly.
>> Just assume that SYNC_MB is absolutely the same as SYNC for any CPU
>> and coherent device (besides performance). The difference can be in
>> non-coherent devices because SYNC actually tries to make a barrier
>> for them too. In some SoCs it is just the same because there is no
>> need to barrier a non-coherent device (device register access
>> usually strictly ordered... if there is no bridge in between).
> So smp_mb() can be SYNC_MB. However, mb() needs to be SYNC for MMIO
> purposes, correct?
Absolutely. For MIPS R2 which is not Octeon.
>> Note: I am not sure about ANY past MIPS R2 CPU because that stuff is
>> implemented some time but nobody made it in Linux kernel (it was
>> used by some vendor for non-Linux system). For that reason my patch
>> for lightweight SYNCs has an option - implement it or implement a
>> generic SYNC. It is possible that some vendor did it in different
>> way but nobody knows or test it. But as a minimum - SYNC must be
>> implemented in spinlocks/atomics/bitops, in recent P5600 it is
>> proven that read can pass write in atomics.
>>
>> MIPS R6 is a different story, I verified lightweight SYNCs from the
>> beginning and it also should use SYNCs.
> So you need to build a different kernel for some types of MIPS systems?
> Or do you do boot-time rewriting, like a number of other arches do?
I don't know. I would like to have responses. Ralf asked Maciej about
old systems and that came nowhere. Even rewrite - don't know what to do
with that: no lightweight SYNC or no SYNC at all - yes, it is still
possible that SYNC on some systems can be too heavy or even harmful,
nobody tested that.
- Leonid.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-15 0:47 UTC (permalink / raw)
To: Leonid Yegoshin
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <56983054.4070807@imgtec.com>
On Thu, Jan 14, 2016 at 03:33:40PM -0800, Leonid Yegoshin wrote:
> On 01/14/2016 02:55 PM, Paul E. McKenney wrote:
> >OK, so it looks like Will was asking not about WRC+addr+addr, but instead
> >about WRC+sync+addr.
> (He actually asked twice about this and that too but skip this)
Fair enough! ;-)
> >I am guessing that the manual's "Older instructions which must be globally
> >performed when the SYNC instruction completes" provides the equivalent
> >of ARM/Power A-cumulativity, which can be thought of as transitivity
> >backwards in time. This leads me to believe that your smp_mb() needs
> >to use SYNC rather than SYNC_MB, as was the subject of earlier spirited
> >discussion in this thread.
>
> Don't be fooled here by words "ordered" and "completed" - it is HW
> design items and actually written poorly.
> Just assume that SYNC_MB is absolutely the same as SYNC for any CPU
> and coherent device (besides performance). The difference can be in
> non-coherent devices because SYNC actually tries to make a barrier
> for them too. In some SoCs it is just the same because there is no
> need to barrier a non-coherent device (device register access
> usually strictly ordered... if there is no bridge in between).
So smp_mb() can be SYNC_MB. However, mb() needs to be SYNC for MMIO
purposes, correct?
> >Suppose you have something like this:
> >...
> >Does your hardware guarantee that it is not possible for all of r0,
> >r1, r2, and r3 to be equal to zero at the end of the test, assuming
> >that a, b, c, and d are all initially zero, and the four functions
> >above run concurrently?
>
> It is assumed to be so from Arch point of view. HW bugs are
> possible, of course.
Indeed!
> >Another (more academic) case is this one, with x and y initially zero:
> >
> >...
> >Does SYNC_MB() prohibit r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0?
>
> It is assumed to be so from Arch point of view. HW bugs are
> possible, of course.
Looks to me like smp_mb() can be SYNC_MB, then.
> Note: I am not sure about ANY past MIPS R2 CPU because that stuff is
> implemented some time but nobody made it in Linux kernel (it was
> used by some vendor for non-Linux system). For that reason my patch
> for lightweight SYNCs has an option - implement it or implement a
> generic SYNC. It is possible that some vendor did it in different
> way but nobody knows or test it. But as a minimum - SYNC must be
> implemented in spinlocks/atomics/bitops, in recent P5600 it is
> proven that read can pass write in atomics.
>
> MIPS R6 is a different story, I verified lightweight SYNCs from the
> beginning and it also should use SYNCs.
So you need to build a different kernel for some types of MIPS systems?
Or do you do boot-time rewriting, like a number of other arches do?
Thanx, Paul
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Leonid Yegoshin @ 2016-01-14 23:33 UTC (permalink / raw)
To: paulmck
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <20160114225510.GJ3818@linux.vnet.ibm.com>
On 01/14/2016 02:55 PM, Paul E. McKenney wrote:
> OK, so it looks like Will was asking not about WRC+addr+addr, but instead
> about WRC+sync+addr.
(He actually asked twice about this and that too but skip this)
> I am guessing that the manual's "Older instructions which must be globally
> performed when the SYNC instruction completes" provides the equivalent
> of ARM/Power A-cumulativity, which can be thought of as transitivity
> backwards in time. This leads me to believe that your smp_mb() needs
> to use SYNC rather than SYNC_MB, as was the subject of earlier spirited
> discussion in this thread.
Don't be fooled here by words "ordered" and "completed" - it is HW
design items and actually written poorly.
Just assume that SYNC_MB is absolutely the same as SYNC for any CPU and
coherent device (besides performance). The difference can be in
non-coherent devices because SYNC actually tries to make a barrier for
them too. In some SoCs it is just the same because there is no need to
barrier a non-coherent device (device register access usually strictly
ordered... if there is no bridge in between).
>
> Suppose you have something like this:
> ...
> Does your hardware guarantee that it is not possible for all of r0,
> r1, r2, and r3 to be equal to zero at the end of the test, assuming
> that a, b, c, and d are all initially zero, and the four functions
> above run concurrently?
It is assumed to be so from Arch point of view. HW bugs are possible, of
course.
> Another (more academic) case is this one, with x and y initially zero:
>
> ...
> Does SYNC_MB() prohibit r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0?
It is assumed to be so from Arch point of view. HW bugs are possible, of
course.
Note: I am not sure about ANY past MIPS R2 CPU because that stuff is
implemented some time but nobody made it in Linux kernel (it was used by
some vendor for non-Linux system). For that reason my patch for
lightweight SYNCs has an option - implement it or implement a generic
SYNC. It is possible that some vendor did it in different way but nobody
knows or test it. But as a minimum - SYNC must be implemented in
spinlocks/atomics/bitops, in recent P5600 it is proven that read can
pass write in atomics.
MIPS R6 is a different story, I verified lightweight SYNCs from the
beginning and it also should use SYNCs.
- Leonid.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Leonid Yegoshin @ 2016-01-14 23:04 UTC (permalink / raw)
To: paulmck
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <20160114222433.GI3818@linux.vnet.ibm.com>
On 01/14/2016 02:24 PM, Paul E. McKenney wrote:
> Actually, the Linux kernel doesn't have an acquire barrier, just an
> smp_load_acquire(). Or did someone sneak one in while I wasn't looking?
That was an exactly starting point for this discussion. This patch just
pulls out from MIPS files smp_load_acquire() and smp_store_release().
However, I put into LMO half year ago the patch
http://patchwork.linux-mips.org/patch/10506/ which replaces a generic
smp_mb with MIPS specific smp_release/acquire in that functions. This
patch also fixes use of SYNCs barriers in spin_locks/atomics/bitops for
Imagination MIPS CPUs too - it is just absent now for any Imagination
MIPS CPUs!
Michael later pointed me that it can be returned back with his series of
patches but discussion was already here.
- Leonid.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-14 22:55 UTC (permalink / raw)
To: Leonid Yegoshin
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <569814F2.50801@imgtec.com>
On Thu, Jan 14, 2016 at 01:36:50PM -0800, Leonid Yegoshin wrote:
> On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
> >
> >>On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
> >>>
> >>>The WRC+addr+addr is OK because data dependencies are not required to be
> >>>transitive, in other words, they are not required to flow from one CPU to
> >>>another without the help of an explicit memory barrier.
> >>I don't see any reliable way to fit WRC+addr+addr into "DATA
> >>DEPENDENCY BARRIERS" section recommendation to have data dependency
> >>barrier between read of a shared pointer/index and read the shared
> >>data based on that pointer. If you have this two reads, it doesn't
> >>matter the rest of scenario, you should put the dependency barrier
> >>in code anyway. If you don't do it in WRC+addr+addr scenario then
> >>after years it can be easily changed to different scenario which
> >>fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
> >>fails.
> >The trick is that lockless_dereference() contains an
> >smp_read_barrier_depends():
> >
> >#define lockless_dereference(p) \
> >({ \
> > typeof(p) _________p1 = READ_ONCE(p); \
> > smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
> > (_________p1); \
> >})
> >
> >Or am I missing your point?
>
> WRC+addr+addr has no any barrier. lockless_dereference() has a
> barrier. I don't see a common points between this and that in your
> answer, sorry.
Me, I am wondering what WRC+addr+addr has to do with anything at all.
<Going back through earlier email>
OK, so it looks like Will was asking not about WRC+addr+addr, but instead
about WRC+sync+addr. This would drop an smp_mb() into cpu2() in my
earlier example, which needs to provide ordering.
I am guessing that the manual's "Older instructions which must be globally
performed when the SYNC instruction completes" provides the equivalent
of ARM/Power A-cumulativity, which can be thought of as transitivity
backwards in time. This leads me to believe that your smp_mb() needs
to use SYNC rather than SYNC_MB, as was the subject of earlier spirited
discussion in this thread.
Suppose you have something like this:
void cpu0(void)
{
WRITE_ONCE(a, 1);
SYNC_MB();
r0 = READ_ONCE(b);
}
void cpu1(void)
{
WRITE_ONCE(b, 1);
SYNC_MB();
r1 = READ_ONCE(c);
}
void cpu2(void)
{
WRITE_ONCE(c, 1);
SYNC_MB();
r2 = READ_ONCE(d);
}
void cpu3(void)
{
WRITE_ONCE(d, 1);
SYNC_MB();
r3 = READ_ONCE(a);
}
Does your hardware guarantee that it is not possible for all of r0,
r1, r2, and r3 to be equal to zero at the end of the test, assuming
that a, b, c, and d are all initially zero, and the four functions
above run concurrently? There are many similar litmus tests for other
combinations of reads and writes, but this is perhaps the nastiest from
a hardware viewpoint. Does SYNC_MB() provide sufficient ordering for
this sort of situation?
Another (more academic) case is this one, with x and y initially zero:
void cpu0(void)
{
WRITE_ONCE(x, 1);
}
void cpu1(void)
{
WRITE_ONCE(y, 1);
}
void cpu2(void)
{
r1 = READ_ONCE(x, 1);
SYNC_MB();
r2 = READ_ONCE(y, 1);
}
void cpu3(void)
{
r3 = READ_ONCE(y, 1);
SYNC_MB();
r4 = READ_ONCE(x, 1);
}
Does SYNC_MB() prohibit r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0?
Now, I don't know of any specific use cases for this pattern, but it
is greatly beloved of some of the old-school concurrency community,
so it is likely to crop up at some point, despite my best efforts. :-/
Thanx, Paul
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-14 22:24 UTC (permalink / raw)
To: Leonid Yegoshin
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <56981708.4000007@imgtec.com>
On Thu, Jan 14, 2016 at 01:45:44PM -0800, Leonid Yegoshin wrote:
> On 01/14/2016 01:34 PM, Paul E. McKenney wrote:
> >On Thu, Jan 14, 2016 at 12:46:43PM -0800, Leonid Yegoshin wrote:
> >>On 01/14/2016 12:15 PM, Peter Zijlstra wrote:
> >>>On Thu, Jan 14, 2016 at 11:42:02AM -0800, Leonid Yegoshin wrote:
> >>>>An the only point - please use an appropriate SYNC_* barriers instead of
> >>>>heavy bold hammer. That stuff was design explicitly to support the
> >>>>requirements of Documentation/memory-barriers.txt
> >>>That's madness. That document changes from version to version as to what
> >>>we _think_ the actual hardware does. It is _NOT_ a specification.
> >>>
> >>>You cannot design hardware from that. Its incomplete and fails to
> >>>specify a bunch of things. It not a mathematically sound definition of a
> >>>memory model.
> >>>
> >>>Please stop referring to that document for what a particular barrier
> >>>_should_ do. Explain what MIPS does, so we can attempt to integrate
> >>>this knowledge with our knowledge of PPC/ARM/Alpha/x86/etc. and improve
> >>>upon our understanding of hardware and improve the Linux memory model.
> >>I am afraid I can't help you here. It is very complicated stuff and
> >>a model is actually doesn't fit your assumptions about CPUs well
> >>without some simplifications which are based on what you want to
> >>have.
> >>
> >>I say that SYNC_ACQUIRE/etc follows what you expect for smp_acquire
> >>etc (basing on that document). And at least two CPU models were
> >>tested with my patches (see it in LMO) for that last year and that
> >>instructions are implemented now in engineering kernel.
> >>
> >>If you have something else in mind, you can ask me. But I prefer to
> >>do not deviate too much from Documentation/memory-barriers.txt, for
> >>exam - if it asks to have memory barrier somewhere, then I assume
> >>the code should have it, and please - don't ask me a test which
> >>violates the current version of document recommendations.
> >>
> >>For a moment I don't see a significant changes in this document for
> >>MIPS Arch at least 1.5 year, and the only significant point is that
> >>MIPS CPU Arch doesn't have yet smp_read_barrier_depends() and
> >>smp_rmb() should be used instead.
>
> >Is SYNC_ACQUIRE a memory-barrier instruction that orders prior loads
> >against later loads and stores?
>
> Yes, it is in MD00087 (table 6.6 of document Ver 6.04) -
> https://imgtec.com/?do-download=4302
OK, it does look like it should work. Of course, if you can rely
on straight address/data dependencies, that would be even better.
> > If so, and if MIPS does not do
> >ordering based on address and data dependencies, I suggest making
> >read_barrier_depends() be a SYNC_ACQUIRE rather than SYNC_RMB.
>
> I understood that, after I see the example of using it.
> Please consider to add that into Documentation/memory-barriers.txt
> (it is not easy to find that this barrier is used for shared WRITE
> basing on shared pointer), it would be helpful.
Actually, the Linux kernel doesn't have an acquire barrier, just an
smp_load_acquire(). Or did someone sneak one in while I wasn't looking? ;-)
Thanx, Paul
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Paul E. McKenney @ 2016-01-14 22:20 UTC (permalink / raw)
To: Leonid Yegoshin
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <56981212.7050301@imgtec.com>
On Thu, Jan 14, 2016 at 01:24:34PM -0800, Leonid Yegoshin wrote:
> On 01/14/2016 12:48 PM, Paul E. McKenney wrote:
> >
> >So SYNC_RMB is intended to implement smp_rmb(), correct?
> Yes.
> >
> >You could use SYNC_ACQUIRE() to implement read_barrier_depends() and
> >smp_read_barrier_depends(), but SYNC_RMB probably does not suffice.
>
> If smp_read_barrier_depends() is used to separate not only two reads
> but read pointer and WRITE basing on that pointer (example below) -
> yes. I just doesn't see any example of this in famous
> Documentation/memory-barriers.txt and had no chance to know what you
> use it in this way too.
Well, Documentation/memory-barriers.txt was intended as a guide for Linux
kernel hackers, and not for hardware architects. The need for something
more precise has become clear over the past year or two, and I am working
on it with some heavy-duty memory-model folks. But all previous memory
models have been for a specific CPU architecture, so doing one for the
intersection of several is offering up some complications. I therefore
cannot yet provide a completion date.
That said, I still suggest use of SYNC_ACQUIRE for read_barrier_depends().
> >The reason for this is that smp_read_barrier_depends() must order the
> >pointer load against any subsequent read or write through a dereference
> >of that pointer.
>
> I can't see that requirement anywhere in Documents directory. I mean
> - the words "write through a dereference of that pointer" or similar
> for smp_read_barrier_depends.
No worries, I will add one. Please see the end of this message for an
initial patch.
Please understand that Documentation/memory-barriers.txt is a living
document:
v4.4: Two changes
v4.3: Three changes
v4.2: Six changes
v4.1: Three changes
v4.0: Two changes
It tends to change as we locate corner cases either in hardware or
in software use cases/APIs.
> > For example:
> >
> > p = READ_ONCE(gp);
> > smp_rmb();
> > r1 = p->a; /* ordered by smp_rmb(). */
> > p->b = 42; /* NOT ordered by smp_rmb(), BUG!!! */
> > r2 = x; /* ordered by smp_rmb(), but doesn't need to be. */
> >
> >In contrast:
> >
> > p = READ_ONCE(gp);
> > smp_read_barrier_depends();
> > r1 = p->a; /* ordered by smp_read_barrier_depends(). */
> > p->b = 42; /* ordered by smp_read_barrier_depends(). */
> > r2 = x; /* not ordered by smp_read_barrier_depends(), which is OK. */
> >
> >Again, if your hardware maintains local ordering for address
> >and data dependencies, you can have read_barrier_depends() and
> >smp_read_barrier_depends() be no-ops like they are for most
> >architectures.
>
> It is not so simple, I mean "local ordering for address and data
> dependencies". Local ordering is NOT enough. It happens that current
> MIPS R6 doesn't require in your example smp_read_barrier_depends()
> but in discussion it comes out that it may not. Because without
> smp_read_barrier_depends() your example can be a part of Will's
> WRC+addr+addr and we found some design which easily can bump into
> this test. And that design actually performs "local ordering for
> address and data dependencies" too.
As noted in another email in this thread, I do not believe that
WRC+addr+addr needs to be prohibited. Sounds like Will and I need to
get our story straight, though.
Will?
Thanx, Paul
------------------------------------------------------------------------
commit 955720966e216b00613fcf60188d507c103f0e80
Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Date: Thu Jan 14 14:17:04 2016 -0800
documentation: Subsequent writes ordered by rcu_dereference()
The current memory-barriers.txt does not address the possibility of
a write to a dereferenced pointer. This should be rare, but when it
happens, we need that write -not- to be clobbered by the initialization.
This commit therefore adds an example showing a data dependency ordering
a later data-dependent write.
Reported-by: Leonid Yegoshin <Leonid.Yegoshin@imgtec.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index f49c15f7864f..c66ba46d8079 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -555,6 +555,30 @@ between the address load and the data load:
This enforces the occurrence of one of the two implications, and prevents the
third possibility from arising.
+A data-dependency barrier must also order against dependent writes:
+
+ CPU 1 CPU 2
+ =============== ===============
+ { A == 1, B == 2, C = 3, P == &A, Q == &C }
+ B = 4;
+ <write barrier>
+ WRITE_ONCE(P, &B);
+ Q = READ_ONCE(P);
+ <data dependency barrier>
+ *Q = 5;
+
+The data-dependency barrier must order the read into Q with the store
+into *Q. This prohibits this outcome:
+
+ (Q == B) && (B == 4)
+
+Please note that this pattern should be rare. After all, the whole point
+of dependency ordering is to -prevent- writes to the data structure, along
+with the expensive cache misses associated with those writes. This pattern
+can be used to record rare error conditions and the like, and the ordering
+prevents such records from being lost.
+
+
[!] Note that this extremely counterintuitive situation arises most easily on
machines with split caches, so that, for example, one cache bank processes
even-numbered cache lines and the other bank processes odd-numbered cache
^ permalink raw reply related
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Leonid Yegoshin @ 2016-01-14 21:45 UTC (permalink / raw)
To: paulmck
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <20160114213440.GG3818@linux.vnet.ibm.com>
On 01/14/2016 01:34 PM, Paul E. McKenney wrote:
> On Thu, Jan 14, 2016 at 12:46:43PM -0800, Leonid Yegoshin wrote:
>> On 01/14/2016 12:15 PM, Peter Zijlstra wrote:
>>> On Thu, Jan 14, 2016 at 11:42:02AM -0800, Leonid Yegoshin wrote:
>>>> An the only point - please use an appropriate SYNC_* barriers instead of
>>>> heavy bold hammer. That stuff was design explicitly to support the
>>>> requirements of Documentation/memory-barriers.txt
>>> That's madness. That document changes from version to version as to what
>>> we _think_ the actual hardware does. It is _NOT_ a specification.
>>>
>>> You cannot design hardware from that. Its incomplete and fails to
>>> specify a bunch of things. It not a mathematically sound definition of a
>>> memory model.
>>>
>>> Please stop referring to that document for what a particular barrier
>>> _should_ do. Explain what MIPS does, so we can attempt to integrate
>>> this knowledge with our knowledge of PPC/ARM/Alpha/x86/etc. and improve
>>> upon our understanding of hardware and improve the Linux memory model.
>> I am afraid I can't help you here. It is very complicated stuff and
>> a model is actually doesn't fit your assumptions about CPUs well
>> without some simplifications which are based on what you want to
>> have.
>>
>> I say that SYNC_ACQUIRE/etc follows what you expect for smp_acquire
>> etc (basing on that document). And at least two CPU models were
>> tested with my patches (see it in LMO) for that last year and that
>> instructions are implemented now in engineering kernel.
>>
>> If you have something else in mind, you can ask me. But I prefer to
>> do not deviate too much from Documentation/memory-barriers.txt, for
>> exam - if it asks to have memory barrier somewhere, then I assume
>> the code should have it, and please - don't ask me a test which
>> violates the current version of document recommendations.
>>
>> For a moment I don't see a significant changes in this document for
>> MIPS Arch at least 1.5 year, and the only significant point is that
>> MIPS CPU Arch doesn't have yet smp_read_barrier_depends() and
>> smp_rmb() should be used instead.
> Is SYNC_ACQUIRE a memory-barrier instruction that orders prior loads
> against later loads and stores?
Yes, it is in MD00087 (table 6.6 of document Ver 6.04) -
https://imgtec.com/?do-download=4302
> If so, and if MIPS does not do
> ordering based on address and data dependencies, I suggest making
> read_barrier_depends() be a SYNC_ACQUIRE rather than SYNC_RMB.
I understood that, after I see the example of using it.
Please consider to add that into Documentation/memory-barriers.txt (it
is not easy to find that this barrier is used for shared WRITE basing on
shared pointer), it would be helpful.
- Leonid.
^ permalink raw reply
* Re: [v3,11/41] mips: reuse asm-generic/barrier.h
From: Leonid Yegoshin @ 2016-01-14 21:36 UTC (permalink / raw)
To: paulmck
Cc: linux-mips, linux-ia64, Michael S. Tsirkin, Peter Zijlstra,
Will Deacon, virtualization, H. Peter Anvin, sparclinux,
Ingo Molnar, linux-arch, linux-s390, Russell King - ARM Linux,
user-mode-linux-devel, linux-sh, Michael Ellerman, x86, xen-devel,
Ingo Molnar, linux-xtensa, james.hogan, Arnd Bergmann,
Stefano Stabellini, adi-buildroot-devel, ddaney.cavm,
Thomas Gleixner, linux-metag
In-Reply-To: <20160114212913.GF3818@linux.vnet.ibm.com>
On 01/14/2016 01:29 PM, Paul E. McKenney wrote:
>
>> On 01/14/2016 12:34 PM, Paul E. McKenney wrote:
>>>
>>> The WRC+addr+addr is OK because data dependencies are not required to be
>>> transitive, in other words, they are not required to flow from one CPU to
>>> another without the help of an explicit memory barrier.
>> I don't see any reliable way to fit WRC+addr+addr into "DATA
>> DEPENDENCY BARRIERS" section recommendation to have data dependency
>> barrier between read of a shared pointer/index and read the shared
>> data based on that pointer. If you have this two reads, it doesn't
>> matter the rest of scenario, you should put the dependency barrier
>> in code anyway. If you don't do it in WRC+addr+addr scenario then
>> after years it can be easily changed to different scenario which
>> fits some of scenario in "DATA DEPENDENCY BARRIERS" section and
>> fails.
> The trick is that lockless_dereference() contains an
> smp_read_barrier_depends():
>
> #define lockless_dereference(p) \
> ({ \
> typeof(p) _________p1 = READ_ONCE(p); \
> smp_read_barrier_depends(); /* Dependency order vs. p above. */ \
> (_________p1); \
> })
>
> Or am I missing your point?
WRC+addr+addr has no any barrier. lockless_dereference() has a barrier.
I don't see a common points between this and that in your answer, sorry.
- Leonid.
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox