[PATCH 0/6] iommu/virtio: batch the mapping replay

[PATCH 0/6] iommu/virtio: batch the mapping replay

[Anlai Lu]

The virtio-iommu device frees a domain together with its last endpoint, so
the first endpoint attaching to a domain that already has mappings must
rebuild it: viommu_replay_mappings() re-sends every mapping the driver
holds. That walk sent one synchronous request per mapping with
mappings_lock held - and with it interrupts disabled. The IRQ-off window
therefore grew with the number of mappings: 233 ms for 8192 4K mappings,
about 29 s for a million, long enough to add scheduling latency to
everything else running on the CPU.

The same code had two long-standing defects, fixed by the first patches:

 - nr_endpoints was bumped only after the replay, without the lock, while
   viommu_map_pages() read the same counter, also without the lock, to
   decide whether to send a MAP itself or leave it to the replay. A map
   racing the first attach could be sent by nobody and never reach the
   device.

 - viommu_unmap_pages() removed whole mappings from its tree but queued a
   single UNMAP built from the range the caller asked for, after dropping
   the lock: the device could keep translating memory the driver had
   released, and a concurrent map could be sent ahead of the UNMAP. That
   queueing also allocated on the unmap path, which iommu_unmap_nofail()
   does not allow.

The series:

 - 1/6 publishes the endpoint before the replay, tracks an unfinished
   replay with replay_pending, and puts the endpoint back on the old
   domain when the ATTACH or the replay fails - with a replay pending for
   it if the device dropped its mappings - so a failed attach cannot leave
   the endpoint count short, the endpoint unattached (bypassed), or the
   endpoint recorded on a domain the core does not reference;
 - 2/6 queues one UNMAP per contiguous run of removed mappings, in the
   section that removes them, covering the mappings' own ranges;
 - 3/6 allocates the UNMAP request together with the mapping, on the map
   path, so the unmap path never allocates;
 - 4/6 stops queueing and draining once the device is removed;
 - 5/6 reads the endpoint count under the lock in the iotlb paths;
 - 6/6 queues the replayed mappings, one per lock section, and waits once.

Measured with QEMU/KVM and iommufd, N=8192 4K mappings: max IRQ-off window
233.7 ms -> 1.4-2.5 ms, flat from N=64 to 32768; attach ioctl 218.9/249.0
-> 50.3/48.8 ms (48-67 ms across runs); viommu_send_req_sync() calls 8193
-> 1; the device receives exactly the same MAPs. With large pages the
same 256 MB attach is about 4 ms (197 device requests); the remaining cost
is the device processing one MAP per mapping, which the protocol
requires. The concurrent map-vs-first-attach test loses mappings on the
unpatched driver in several runs and none with the series; lockdep and
KCSAN report nothing. Allocation-failure and device-rejection paths were
exercised with test-only fault injection in QEMU.

Patches 1-4 carry Fixes: tags for the original driver commit. Behaviour
that predates this work - in particular, how a MAP the device rejects on
the map path - is deliberately left unchanged. Based on v7.3-rc5
(ce1e0223d8ad).

Anlai Lu (6):
  iommu/virtio: publish the endpoint before replaying it
  iommu/virtio: queue an UNMAP for every removed mapping
  iommu/virtio: allocate the UNMAP request with the mapping
  iommu/virtio: stop queueing and draining once the device is removed
  iommu/virtio: read the endpoint count under the lock in the iotlb
    paths
  iommu/virtio: batch the mapping replay on domain attach

 drivers/iommu/virtio-iommu.c | 642 +++++++++++++++++++++++++++++------
 1 file changed, 538 insertions(+), 104 deletions(-)

-- 
2.55.0

[PATCH 1/6] iommu/virtio: publish the endpoint before replaying it

[Anlai Lu]

The device drops a domain's mappings together with its last endpoint, so
the first endpoint attaching to a domain has to replay them. The driver
published that endpoint only after the replay (nr_endpoints++, without a
lock), while viommu_map_pages() used the same counter, also without a
lock, to decide whether to queue its own MAP or leave it to the replay. A
map_pages() landing after the replay's walk had passed its range and
before the counter was bumped was therefore queued by nobody: the mapping
stayed in the driver's tree and never reached the device, silently, until
the domain was detached and attached again - DMA to it faults in the
meantime.

Publish the endpoint first, with the decision moved into
viommu_add_mapping() under mappings_lock so that it cannot race the
insert, and let the replay pick up the rest. A mapping that such a race
sends while the replay walks it is on the device twice, which the spec says
a duplicate MAP SHOULD be rejected with S_INVAL and MUST NOT change the
existing mapping - so the replay ignores it. A
second endpoint attaching while the first replay runs, or after one
failed, must replay too - it cannot tell that the mappings made it -
which the per-domain replay_pending flag tracks; it is set by the attach
that replays, cleared by a successful one, and cleared when the last
endpoint leaves (the device drops the domain then).

The endpoint is retired before the ATTACH that moves it, as before: its
count must not stay high while the device is already forgetting the old
domain, or an endpoint attaching to it would see it as known, skip the
replay, and join a domain the device has just recreated empty.

If the ATTACH fails, the endpoint did not move: it is given back to the old
domain, whose count would otherwise stay one endpoint short and whose next
attach would retire it a second time. If the replay fails instead, the
attach is reported as failed and the endpoint is put back on the old
domain - an endpoint left with no domain would be bypassed by a device
that enables bypass; the old domain lost its mappings when the endpoint
left it, so a replay is pending for the next attach to it.

Measured with a map thread racing the first attach (N=8192 4K mappings,
QEMU virtio-iommu): the unpatched driver leaves 1-2 mappings off the
device in 2 of 3 runs, and in 2 of 6 and 3 of 3 in later runs; with this
change the device ends with exactly the mappings the driver believes in,
in every run.

Fixes: edcd69ab9a32 ("iommu: Add virtio-iommu driver")
Signed-off-by: Anlai Lu <agicy@qq.com>
---
 drivers/iommu/virtio-iommu.c | 304 ++++++++++++++++++++++++++++-------
 1 file changed, 246 insertions(+), 58 deletions(-)

diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
index 587fc13197f1..0e5fbdfa8ef4 100644
--- a/drivers/iommu/virtio-iommu.c
+++ b/drivers/iommu/virtio-iommu.c
@@ -68,8 +68,15 @@ struct viommu_domain {
 
 	spinlock_t			mappings_lock;
 	struct rb_root_cached		mappings;
-
 	unsigned long			nr_endpoints;
+	/*
+	 * The domain is not known to be complete on the device: a replay is
+	 * running or has failed, or an endpoint came back after a failed ATTACH
+	 * and the flag was re-armed.  Another endpoint attaching must replay
+	 * too - it cannot tell that the mappings are there - and until a replay
+	 * succeeds no attach may report success on this domain.
+	 */
+	bool				replay_pending;
 };
 
 struct viommu_endpoint {
@@ -200,18 +207,47 @@ static int viommu_sync_req(struct viommu_dev *viommu)
 }
 
 /*
- * __viommu_add_request - Add one request to the queue
+ * Hand a filled-in request to the queue.  Only synchronizes the queue if it is
+ * already full, and never kicks nor waits.  On success the request belongs to
+ * the queue and is freed by the drain, not by the caller.
+ */
+static int __viommu_queue_req(struct viommu_dev *viommu,
+			      struct viommu_request *req, off_t write_offset)
+{
+	int ret;
+	struct scatterlist top_sg, bottom_sg;
+	struct scatterlist *sg[2] = { &top_sg, &bottom_sg };
+	struct virtqueue *vq = viommu->vqs[VIOMMU_REQUEST_VQ];
+
+	assert_spin_locked(&viommu->request_lock);
+
+	sg_init_one(&top_sg, req->buf, write_offset);
+	sg_init_one(&bottom_sg, req->buf + write_offset,
+		    req->len - write_offset);
+
+	ret = virtqueue_add_sgs(vq, sg, 1, 1, req, GFP_ATOMIC);
+	if (ret == -ENOSPC) {
+		/* If the queue is full, sync and retry */
+		if (!__viommu_sync_req(viommu))
+			ret = virtqueue_add_sgs(vq, sg, 1, 1, req, GFP_ATOMIC);
+	}
+	if (ret)
+		return ret;
+
+	list_add_tail(&req->list, &viommu->requests);
+	return 0;
+}
+
+/*
+ * __viommu_add_req - Add one request to the queue
  * @buf: pointer to the request buffer
  * @len: length of the request buffer
  * @writeback: copy data back to the buffer when the request completes.
  *
- * Add a request to the queue. Only synchronize the queue if it's already full.
- * Otherwise don't kick the queue nor wait for requests to complete.
- *
- * When @writeback is true, data written by the device, including the request
- * status, is copied into @buf after the request completes. This is unsafe if
- * the caller allocates @buf on stack and drops the lock between add_req() and
- * sync_req().
+ * Allocate a request object, fill it and queue it.  When @writeback is true,
+ * data written by the device, including the request status, is copied into
+ * @buf after the request completes: this is unsafe if the caller allocates
+ * @buf on stack and drops the lock between add_req() and sync_req().
  *
  * Return 0 if the request was successfully added to the queue.
  */
@@ -221,9 +257,6 @@ static int __viommu_add_req(struct viommu_dev *viommu, void *buf, size_t len,
 	int ret;
 	off_t write_offset;
 	struct viommu_request *req;
-	struct scatterlist top_sg, bottom_sg;
-	struct scatterlist *sg[2] = { &top_sg, &bottom_sg };
-	struct virtqueue *vq = viommu->vqs[VIOMMU_REQUEST_VQ];
 
 	assert_spin_locked(&viommu->request_lock);
 
@@ -242,23 +275,10 @@ static int __viommu_add_req(struct viommu_dev *viommu, void *buf, size_t len,
 	}
 	memcpy(&req->buf, buf, write_offset);
 
-	sg_init_one(&top_sg, req->buf, write_offset);
-	sg_init_one(&bottom_sg, req->buf + write_offset, len - write_offset);
-
-	ret = virtqueue_add_sgs(vq, sg, 1, 1, req, GFP_ATOMIC);
-	if (ret == -ENOSPC) {
-		/* If the queue is full, sync and retry */
-		if (!__viommu_sync_req(viommu))
-			ret = virtqueue_add_sgs(vq, sg, 1, 1, req, GFP_ATOMIC);
-	}
+	ret = __viommu_queue_req(viommu, req, write_offset);
 	if (ret)
-		goto err_free;
-
-	list_add_tail(&req->list, &viommu->requests);
-	return 0;
+		kfree(req);
 
-err_free:
-	kfree(req);
 	return ret;
 }
 
@@ -325,12 +345,15 @@ static int viommu_send_attach_req(struct viommu_dev *viommu, struct device *dev,
 /*
  * viommu_add_mapping - add a mapping to the internal tree
  *
- * On success, return the new mapping. Otherwise return NULL.
+ * Queue a MAP for it if the device already knows the domain.  Returns 0 on
+ * success, a negative error code otherwise, in which case the mapping is not
+ * in the tree.
  */
 static int viommu_add_mapping(struct viommu_domain *vdomain, u64 iova, u64 end,
 			      phys_addr_t paddr, u32 flags)
 {
 	unsigned long irqflags;
+	int ret;
 	struct viommu_mapping *mapping;
 
 	mapping = kzalloc_obj(*mapping, GFP_ATOMIC);
@@ -344,6 +367,30 @@ static int viommu_add_mapping(struct viommu_domain *vdomain, u64 iova, u64 end,
 
 	spin_lock_irqsave(&vdomain->mappings_lock, irqflags);
 	interval_tree_insert(&mapping->iova, &vdomain->mappings);
+
+	/*
+	 * If the device already knows this domain, queue the MAP right away.
+	 * Nobody waits for it: a rejection is not reported to the caller, as
+	 * before.
+	 */
+	if (vdomain->nr_endpoints) {
+		struct virtio_iommu_req_map map = {
+			.head.type	= VIRTIO_IOMMU_T_MAP,
+			.domain		= cpu_to_le32(vdomain->id),
+			.virt_start	= cpu_to_le64(iova),
+			.phys_start	= cpu_to_le64(paddr),
+			.virt_end	= cpu_to_le64(end),
+			.flags		= cpu_to_le32(flags),
+		};
+
+		ret = viommu_add_req(vdomain->viommu, &map, sizeof(map));
+		if (ret) {
+			interval_tree_remove(&mapping->iova, &vdomain->mappings);
+			spin_unlock_irqrestore(&vdomain->mappings_lock, irqflags);
+			kfree(mapping);
+			return ret;
+		}
+	}
 	spin_unlock_irqrestore(&vdomain->mappings_lock, irqflags);
 
 	return 0;
@@ -469,8 +516,18 @@ static int viommu_replay_mappings(struct viommu_domain *vdomain)
 		};
 
 		ret = viommu_send_req_sync(vdomain->viommu, &map, sizeof(map));
-		if (ret)
-			break;
+		if (ret) {
+			/*
+			 * The endpoint was published before this walk, so a
+			 * map_pages() racing it can have sent the same MAP
+			 * already: the spec says a duplicate MAP SHOULD be
+			 * rejected with S_INVAL, and the device MUST NOT
+			 * change the existing mapping.
+			 */
+			if (ret != -EINVAL)
+				break;
+			ret = 0;
+		}
 
 		node = interval_tree_iter_next(node, 0, -1UL);
 	}
@@ -730,6 +787,96 @@ static struct iommu_domain *viommu_domain_alloc_identity(struct device *dev)
 	return domain;
 }
 
+/*
+ * Publish an endpoint on this domain, and return whether the caller has to
+ * replay the mappings: it does when the device did not know the domain (first
+ * endpoint), and also when a replay is still running or failed - a second
+ * endpoint cannot tell that the mappings made it.
+ */
+static bool viommu_get_endpoint(struct viommu_domain *vdomain)
+{
+	unsigned long flags;
+	bool replay;
+
+	spin_lock_irqsave(&vdomain->mappings_lock, flags);
+	replay = !vdomain->nr_endpoints || vdomain->replay_pending;
+	vdomain->nr_endpoints++;
+	/* an attach that does not replay has nothing to wait for */
+	if (replay)
+		vdomain->replay_pending = true;
+	spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
+
+	return replay;
+}
+
+/* The device holds every mapping of the domain */
+static void viommu_replayed(struct viommu_domain *vdomain)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&vdomain->mappings_lock, flags);
+	vdomain->replay_pending = false;
+	spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
+}
+
+static void viommu_put_endpoint(struct viommu_domain *vdomain)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&vdomain->mappings_lock, flags);
+	if (WARN_ON_ONCE(!vdomain->nr_endpoints))
+		goto out;
+	if (!--vdomain->nr_endpoints)
+		/* the device drops the domain, and what it holds with it */
+		vdomain->replay_pending = false;
+out:
+	spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
+}
+
+/*
+ * Give the endpoint back to a domain a failed ATTACH had retired it from: the
+ * device never took the endpoint, so the count has to keep matching what it
+ * holds.  If retiring it had dropped the last endpoint, a replay is pending
+ * again - the device is not known to hold the domain's mappings, so a later
+ * attach replays instead of assuming they are there.
+ */
+static void viommu_restore_endpoint(struct viommu_domain *vdomain)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&vdomain->mappings_lock, flags);
+	if (!vdomain->nr_endpoints)
+		vdomain->replay_pending = true;
+	vdomain->nr_endpoints++;
+	spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
+}
+
+/*
+ * Put the endpoints of @vdev back on @vdomain on the device.  A failed attach
+ * must leave the endpoint where the core believes it still is: left with no
+ * domain, it would be bypassed by a device that enables bypass, while the core
+ * believes the device is still translated.
+ *
+ * Returns what queueing the request returned.
+ */
+static int viommu_revert_attach(struct viommu_endpoint *vdev,
+				struct viommu_domain *vdomain)
+{
+	struct virtio_iommu_req_attach req = {
+		.head.type	= VIRTIO_IOMMU_T_ATTACH,
+	};
+
+	if (vdomain == &viommu_identity_domain) {
+		/* the bypass domain, which has no id of its own */
+		req.domain = cpu_to_le32(vdev->viommu->identity_domain_id);
+		req.flags = cpu_to_le32(VIRTIO_IOMMU_ATTACH_F_BYPASS);
+	} else {
+		req.domain = cpu_to_le32(vdomain->id);
+	}
+
+	return viommu_send_attach_req(vdev->viommu, vdev->dev, &req);
+}
+
 static int viommu_attach_dev(struct iommu_domain *domain, struct device *dev,
 			     struct iommu_domain *old)
 {
@@ -737,6 +884,7 @@ static int viommu_attach_dev(struct iommu_domain *domain, struct device *dev,
 	struct virtio_iommu_req_attach req;
 	struct viommu_endpoint *vdev = dev_iommu_priv_get(dev);
 	struct viommu_domain *vdomain = to_viommu_domain(domain);
+	struct viommu_domain *old_vdomain;
 
 	if (vdomain->viommu != vdev->viommu)
 		return -EINVAL;
@@ -751,10 +899,16 @@ static int viommu_attach_dev(struct iommu_domain *domain, struct device *dev,
 	 * recreated if it gets reattached to an endpoint. Otherwise it will be
 	 * freed explicitly.
 	 *
+	 * Retire the old endpoint before sending this ATTACH: the count must
+	 * not stay high while the device is already dropping that old domain,
+	 * or an endpoint attaching to it would see it as known, skip the
+	 * replay, and join a domain the device just recreated empty.
+	 *
 	 * vdev->vdomain is protected by group->mutex
 	 */
-	if (vdev->vdomain)
-		vdev->vdomain->nr_endpoints--;
+	old_vdomain = vdev->vdomain;
+	if (old_vdomain)
+		viommu_put_endpoint(old_vdomain);
 
 	req = (struct virtio_iommu_req_attach) {
 		.head.type	= VIRTIO_IOMMU_T_ATTACH,
@@ -762,20 +916,57 @@ static int viommu_attach_dev(struct iommu_domain *domain, struct device *dev,
 	};
 
 	ret = viommu_send_attach_req(vdomain->viommu, dev, &req);
-	if (ret)
+	if (ret) {
+		/*
+		 * The ATTACH never reached the device, so the endpoint did
+		 * not move: give it back to the old domain.  Otherwise its
+		 * count would stay one short, and the next attach would
+		 * retire it a second time.
+		 */
+		if (old_vdomain)
+			viommu_restore_endpoint(old_vdomain);
 		return ret;
+	}
 
-	if (!vdomain->nr_endpoints) {
+	/*
+	 * Publish the endpoint before replaying: the device knows the domain
+	 * now, so a map_pages() running concurrently queues its own request
+	 * instead of recording a mapping that this replay has already passed
+	 * and that nothing else will ever send.
+	 */
+	if (viommu_get_endpoint(vdomain)) {
 		/*
-		 * This endpoint is the first to be attached to the domain.
-		 * Replay existing mappings (e.g. SW MSI).
+		 * First endpoint to this domain, or the previous replay did not
+		 * finish: send the existing mappings (e.g. SW MSI) again.  A
+		 * second endpoint must not skip this - it has no way to know
+		 * that the mappings are there.
 		 */
 		ret = viommu_replay_mappings(vdomain);
-		if (ret)
+		if (ret) {
+			/*
+			 * The ATTACH reached the device, so the endpoint has
+			 * moved to the new domain even though its mappings did
+			 * not all make it.  Report the failure and ask the
+			 * device to take the endpoint back to the old domain,
+			 * where the core believes it still is.  If it refuses,
+			 * or there was no old domain, leave the endpoint where
+			 * it is and record no domain for it: a domain the core
+			 * does not keep for this endpoint must not be counted,
+			 * and the endpoint is not left unattached either (a
+			 * device that enables bypass would pass it through).
+			 */
+			if (old_vdomain &&
+			    !viommu_revert_attach(vdev, old_vdomain))
+				/* the old domain lost its mappings with it */
+				viommu_restore_endpoint(old_vdomain);
+			else
+				vdev->vdomain = NULL;
+			viommu_put_endpoint(vdomain);
 			return ret;
+		}
+		viommu_replayed(vdomain);
 	}
 
-	vdomain->nr_endpoints++;
 	vdev->vdomain = vdomain;
 
 	return 0;
@@ -800,14 +991,27 @@ static int viommu_attach_identity_domain(struct iommu_domain *domain,
 	if (ret)
 		return ret;
 
+	/*
+	 * The endpoint has moved: retire it from the old domain now.  Doing it
+	 * before the request would leave that domain's count decremented if the
+	 * ATTACH failed, and a later detach of the same endpoint would then
+	 * decrement it again.
+	 */
 	if (vdev->vdomain)
-		vdev->vdomain->nr_endpoints--;
-	vdomain->nr_endpoints++;
+		viommu_put_endpoint(vdev->vdomain);
+	/* the identity domain has no mappings of its own to replay */
+	if (viommu_get_endpoint(vdomain))
+		viommu_replayed(vdomain);
 	vdev->vdomain = vdomain;
 	return 0;
 }
 
 static struct viommu_domain viommu_identity_domain = {
+	/*
+	 * The endpoint helpers take mappings_lock for every domain, including
+	 * this static one, which is not allocated by viommu_domain_alloc_paging().
+	 */
+	.mappings_lock = __SPIN_LOCK_UNLOCKED(viommu_identity_domain.mappings_lock),
 	.domain = {
 		.type = IOMMU_DOMAIN_IDENTITY,
 		.ops = &(const struct iommu_domain_ops) {
@@ -835,7 +1039,7 @@ static void viommu_detach_dev(struct viommu_endpoint *vdev)
 		req.endpoint = cpu_to_le32(fwspec->ids[i]);
 		WARN_ON(viommu_send_req_sync(vdev->viommu, &req, sizeof(req)));
 	}
-	vdomain->nr_endpoints--;
+	viommu_put_endpoint(vdomain);
 	vdev->vdomain = NULL;
 }
 
@@ -847,7 +1051,6 @@ static int viommu_map_pages(struct iommu_domain *domain, unsigned long iova,
 	u32 flags;
 	size_t size = pgsize * pgcount;
 	u64 end = iova + size - 1;
-	struct virtio_iommu_req_map map;
 	struct viommu_domain *vdomain = to_viommu_domain(domain);
 
 	flags = (prot & IOMMU_READ ? VIRTIO_IOMMU_MAP_F_READ : 0) |
@@ -857,26 +1060,11 @@ static int viommu_map_pages(struct iommu_domain *domain, unsigned long iova,
 	if (flags & ~vdomain->map_flags)
 		return -EINVAL;
 
+	/* viommu_add_mapping() queues the MAP if the device knows the domain */
 	ret = viommu_add_mapping(vdomain, iova, end, paddr, flags);
 	if (ret)
 		return ret;
 
-	if (vdomain->nr_endpoints) {
-		map = (struct virtio_iommu_req_map) {
-			.head.type	= VIRTIO_IOMMU_T_MAP,
-			.domain		= cpu_to_le32(vdomain->id),
-			.virt_start	= cpu_to_le64(iova),
-			.phys_start	= cpu_to_le64(paddr),
-			.virt_end	= cpu_to_le64(end),
-			.flags		= cpu_to_le32(flags),
-		};
-
-		ret = viommu_add_req(vdomain->viommu, &map, sizeof(map));
-		if (ret) {
-			viommu_del_mappings(vdomain, iova, end);
-			return ret;
-		}
-	}
 	if (mapped)
 		*mapped = size;
 
-- 
2.55.0

[PATCH 2/6] iommu/virtio: queue an UNMAP for every removed mapping

[Anlai Lu]

viommu_unmap_pages() removed whole mappings from the tree and then, with
mappings_lock dropped, queued a single UNMAP built from the range the
caller asked for. Both halves are wrong in the direction the device's
semantics are strict about: a device must not split a mapping, so the
driver removes whole mappings - and an UNMAP whose range begins or ends
inside another mapping invalidates nothing there, leaving the device
mapping memory the driver has released; and between the removal and the
queueing a concurrent map_pages() of the same range can put its MAP in
front of the UNMAP.

Queue the UNMAPs in the critical section that removes the mappings, one
request per contiguous run of removed mappings, covering exactly the
mappings' own ranges: a run's mappings are removed together and its
request covers all of them, nothing else. If a request cannot be queued,
the mapping being examined stays in the tree and the walk stops there,
and the run whose request could not be queued is not reported as
unmapped. That is not an atomic rollback: the run's mappings were already
removed from the tree and freed, and the caller is told the bytes that
really were unmapped, not that the whole range failed to unmap. The
request itself is still allocated on the unmap path here; the next patch
moves that allocation to the map path, where it is allowed to fail.

Fixes: edcd69ab9a32 ("iommu: Add virtio-iommu driver")
Signed-off-by: Anlai Lu <agicy@qq.com>
---
 drivers/iommu/virtio-iommu.c | 97 ++++++++++++++++++++++++++----------
 1 file changed, 71 insertions(+), 26 deletions(-)

diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
index 0e5fbdfa8ef4..0e17c1b22483 100644
--- a/drivers/iommu/virtio-iommu.c
+++ b/drivers/iommu/virtio-iommu.c
@@ -402,20 +402,28 @@ static int viommu_add_mapping(struct viommu_domain *vdomain, u64 iova, u64 end,
  * @vdomain: the domain
  * @iova: start of the range
  * @end: end of the range
+ * @queue_unmap: queue an UNMAP for each run of removed mappings; false when
+ *               the device has already dropped the mappings
  *
- * On success, returns the number of unmapped bytes
+ * Returns the number of bytes unmapped, i.e. the mappings removed from the
+ * tree.  A run whose UNMAP could not be queued is not counted, and the walk
+ * stops there: later mappings stay in the tree.
  */
 static size_t viommu_del_mappings(struct viommu_domain *vdomain,
-				  u64 iova, u64 end)
+				  u64 iova, u64 end, bool queue_unmap)
 {
 	size_t unmapped = 0;
 	unsigned long flags;
-	struct viommu_mapping *mapping = NULL;
+	bool spanning = false;
+	u64 span_start = 0, span_end = 0;
 	struct interval_tree_node *node, *next;
 
 	spin_lock_irqsave(&vdomain->mappings_lock, flags);
 	next = interval_tree_iter_first(&vdomain->mappings, iova, end);
 	while (next) {
+		struct viommu_mapping *mapping;
+		size_t size;
+
 		node = next;
 		mapping = container_of(node, struct viommu_mapping, iova);
 		next = interval_tree_iter_next(node, iova, end);
@@ -428,13 +436,69 @@ static size_t viommu_del_mappings(struct viommu_domain *vdomain,
 		 * Virtio-iommu doesn't allow UNMAP to split a mapping created
 		 * with a single MAP request, so remove the full mapping.
 		 */
-		unmapped += mapping->iova.last - mapping->iova.start + 1;
+		size = mapping->iova.last - mapping->iova.start + 1;
+
+		/*
+		 * Queue one UNMAP per contiguous run of removed mappings, in the
+		 * same critical section that removes them, so that a concurrent
+		 * map of the same range cannot put its MAP in front of it.  The
+		 * range is the mappings' own: the caller's requested range can
+		 * begin or end inside another mapping and would then invalidate
+		 * nothing at all, and a range spanning a gap would drop a
+		 * mapping that is not being removed.
+		 */
+		if (queue_unmap && vdomain->nr_endpoints) {
+			if (spanning && mapping->iova.start == span_end + 1) {
+				span_end = mapping->iova.last;
+			} else {
+				if (spanning) {
+					struct virtio_iommu_req_unmap unmap = {
+						.head.type	= VIRTIO_IOMMU_T_UNMAP,
+						.domain		= cpu_to_le32(vdomain->id),
+						.virt_start	= cpu_to_le64(span_start),
+						.virt_end	= cpu_to_le64(span_end),
+					};
+
+					if (viommu_add_req(vdomain->viommu, &unmap,
+							   sizeof(unmap))) {
+						unmapped -= span_end - span_start + 1;
+						dev_warn_ratelimited(vdomain->viommu->dev,
+								     "could not queue an unmap\n");
+						goto out;
+					}
+				}
+				spanning = true;
+				span_start = mapping->iova.start;
+				span_end = mapping->iova.last;
+			}
+		}
 
 		interval_tree_remove(node, &vdomain->mappings);
 		kfree(mapping);
+		unmapped += size;
+	}
+
+	if (spanning) {
+		struct virtio_iommu_req_unmap unmap = {
+			.head.type	= VIRTIO_IOMMU_T_UNMAP,
+			.domain		= cpu_to_le32(vdomain->id),
+			.virt_start	= cpu_to_le64(span_start),
+			.virt_end	= cpu_to_le64(span_end),
+		};
+
+		if (viommu_add_req(vdomain->viommu, &unmap, sizeof(unmap))) {
+			unmapped -= span_end - span_start + 1;
+			dev_warn_ratelimited(vdomain->viommu->dev,
+					     "could not queue an unmap\n");
+		}
 	}
+out:
 	spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
 
+	/*
+	 * What was really unmapped: a run whose UNMAP could not be queued is not
+	 * reported as one.
+	 */
 	return unmapped;
 }
 
@@ -483,7 +547,7 @@ static int viommu_domain_map_identity(struct viommu_endpoint *vdev,
 	return 0;
 
 err_unmap:
-	viommu_del_mappings(vdomain, 0, iova);
+	viommu_del_mappings(vdomain, 0, iova, false);
 	return ret;
 }
 
@@ -757,7 +821,7 @@ static void viommu_domain_free(struct iommu_domain *domain)
 	struct viommu_domain *vdomain = to_viommu_domain(domain);
 
 	/* Free all remaining mappings */
-	viommu_del_mappings(vdomain, 0, ULLONG_MAX);
+	viommu_del_mappings(vdomain, 0, ULLONG_MAX, false);
 
 	if (vdomain->viommu)
 		ida_free(&vdomain->viommu->domain_ids, vdomain->id);
@@ -1075,29 +1139,10 @@ static size_t viommu_unmap_pages(struct iommu_domain *domain, unsigned long iova
 				 size_t pgsize, size_t pgcount,
 				 struct iommu_iotlb_gather *gather)
 {
-	int ret = 0;
-	size_t unmapped;
-	struct virtio_iommu_req_unmap unmap;
 	struct viommu_domain *vdomain = to_viommu_domain(domain);
 	size_t size = pgsize * pgcount;
 
-	unmapped = viommu_del_mappings(vdomain, iova, iova + size - 1);
-	if (unmapped < size)
-		return 0;
-
-	/* Device already removed all mappings after detach. */
-	if (!vdomain->nr_endpoints)
-		return unmapped;
-
-	unmap = (struct virtio_iommu_req_unmap) {
-		.head.type	= VIRTIO_IOMMU_T_UNMAP,
-		.domain		= cpu_to_le32(vdomain->id),
-		.virt_start	= cpu_to_le64(iova),
-		.virt_end	= cpu_to_le64(iova + unmapped - 1),
-	};
-
-	ret = viommu_add_req(vdomain->viommu, &unmap, sizeof(unmap));
-	return ret ? 0 : unmapped;
+	return viommu_del_mappings(vdomain, iova, iova + size - 1, true);
 }
 
 static phys_addr_t viommu_iova_to_phys(struct iommu_domain *domain,
-- 
2.55.0

[PATCH 3/6] iommu/virtio: allocate the UNMAP request with the mapping

[Anlai Lu]

The iommu core states the contract plainly (iommufd pages.c): a driver
may not fail unmap for reasons beyond bad arguments, and in particular
may not allocate on the unmap path, because the caller may free the
memory as soon as unmap returns. viommu_del_mappings() still allocated
the UNMAP request there, so a forced allocation failure left the device
mapping a page the driver had already released, while the caller was told
nothing.

Allocate that request object with the mapping instead - on the map path,
which is allowed to fail and reports the failure to the caller that is
mapping - and free it with the mapping when no UNMAP is sent: the unmap
path then only fills in and queues a request. Measured with a fault
injected into that allocation (failslab, on the fault-injection harness
this work used): the unpatched driver returns success for a re-map of the
same IOVA while the device still translates it to the freed page, proven
with a real DMA through the QEMU iommu-testdev; with this patch the same
scenario reports no such case in any round and the DMA lands on the new
page. The unmap path allocates nothing afterwards, and the device sees
the same request stream.

Fixes: edcd69ab9a32 ("iommu: Add virtio-iommu driver")
Signed-off-by: Anlai Lu <agicy@qq.com>
---
 drivers/iommu/virtio-iommu.c | 101 +++++++++++++++++++++++++++++------
 1 file changed, 85 insertions(+), 16 deletions(-)

diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
index 0e17c1b22483..1a4366458751 100644
--- a/drivers/iommu/virtio-iommu.c
+++ b/drivers/iommu/virtio-iommu.c
@@ -54,10 +54,18 @@ struct viommu_dev {
 	u32				probe_size;
 };
 
+struct viommu_request;
+
 struct viommu_mapping {
 	phys_addr_t			paddr;
 	struct interval_tree_node	iova;
 	u32				flags;
+	/*
+	 * The request that will carry this mapping's UNMAP, allocated with the
+	 * mapping: the unmap path must not allocate, since the caller may free
+	 * the memory as soon as it returns (see iommu_unmap_nofail()).
+	 */
+	struct viommu_request		*unmap_req;
 };
 
 struct viommu_domain {
@@ -296,6 +304,29 @@ static int viommu_add_req(struct viommu_dev *viommu, void *buf, size_t len)
 	return ret;
 }
 
+/* Queue a request whose object was allocated earlier (the unmap path) */
+static int viommu_queue_prealloc_req(struct viommu_dev *viommu,
+				     struct viommu_request *req, void *buf,
+				     size_t len)
+{
+	off_t write_offset;
+	unsigned long flags;
+	int ret;
+
+	write_offset = viommu_get_write_desc_offset(viommu, buf, len);
+	if (write_offset <= 0)
+		return -EINVAL;
+
+	spin_lock_irqsave(&viommu->request_lock, flags);
+	req->len = len;
+	req->writeback = NULL;
+	memcpy(req->buf, buf, write_offset);
+	ret = __viommu_queue_req(viommu, req, write_offset);
+	spin_unlock_irqrestore(&viommu->request_lock, flags);
+
+	return ret;
+}
+
 /*
  * Send a request and wait for it to complete. Return the request status (as an
  * errno)
@@ -360,6 +391,19 @@ static int viommu_add_mapping(struct viommu_domain *vdomain, u64 iova, u64 end,
 	if (!mapping)
 		return -ENOMEM;
 
+	/*
+	 * The UNMAP request object, allocated here: the unmap path may not
+	 * allocate (iommu_unmap_nofail()), so the failure is paid for by the
+	 * caller that is mapping, which is allowed to fail.
+	 */
+	mapping->unmap_req = kzalloc_flex(*mapping->unmap_req, buf,
+					  sizeof(struct virtio_iommu_req_unmap),
+					  GFP_ATOMIC);
+	if (!mapping->unmap_req) {
+		kfree(mapping);
+		return -ENOMEM;
+	}
+
 	mapping->paddr		= paddr;
 	mapping->iova.start	= iova;
 	mapping->iova.last	= end;
@@ -387,6 +431,7 @@ static int viommu_add_mapping(struct viommu_domain *vdomain, u64 iova, u64 end,
 		if (ret) {
 			interval_tree_remove(&mapping->iova, &vdomain->mappings);
 			spin_unlock_irqrestore(&vdomain->mappings_lock, irqflags);
+			kfree(mapping->unmap_req);
 			kfree(mapping);
 			return ret;
 		}
@@ -414,7 +459,7 @@ static size_t viommu_del_mappings(struct viommu_domain *vdomain,
 {
 	size_t unmapped = 0;
 	unsigned long flags;
-	bool spanning = false;
+	struct viommu_request *span_req = NULL;
 	u64 span_start = 0, span_end = 0;
 	struct interval_tree_node *node, *next;
 
@@ -445,48 +490,72 @@ static size_t viommu_del_mappings(struct viommu_domain *vdomain,
 		 * range is the mappings' own: the caller's requested range can
 		 * begin or end inside another mapping and would then invalidate
 		 * nothing at all, and a range spanning a gap would drop a
-		 * mapping that is not being removed.
+		 * mapping that is not being removed.  The request object was
+		 * allocated with the first mapping of the run, so this cannot
+		 * fail for lack of memory.
 		 */
 		if (queue_unmap && vdomain->nr_endpoints) {
-			if (spanning && mapping->iova.start == span_end + 1) {
+			if (span_req && mapping->iova.start == span_end + 1) {
 				span_end = mapping->iova.last;
+				/* this mapping's object is not needed */
+				kfree(mapping->unmap_req);
+				mapping->unmap_req = NULL;
 			} else {
-				if (spanning) {
-					struct virtio_iommu_req_unmap unmap = {
-						.head.type	= VIRTIO_IOMMU_T_UNMAP,
-						.domain		= cpu_to_le32(vdomain->id),
-						.virt_start	= cpu_to_le64(span_start),
-						.virt_end	= cpu_to_le64(span_end),
-					};
-
-					if (viommu_add_req(vdomain->viommu, &unmap,
-							   sizeof(unmap))) {
+				struct virtio_iommu_req_unmap unmap = {
+					.head.type	= VIRTIO_IOMMU_T_UNMAP,
+					.domain		= cpu_to_le32(vdomain->id),
+					.virt_start	= cpu_to_le64(span_start),
+					.virt_end	= cpu_to_le64(span_end),
+				};
+
+				if (span_req) {
+					struct viommu_request *req = span_req;
+
+					span_req = NULL;
+					if (viommu_queue_prealloc_req(vdomain->viommu,
+								      req, &unmap,
+								      sizeof(unmap))) {
+						/*
+						 * The request object was
+						 * already there, so this is
+						 * not an allocation failure:
+						 * the run is not unmapped on
+						 * the device, and the caller
+						 * is told so.
+						 */
+						kfree(req);
 						unmapped -= span_end - span_start + 1;
 						dev_warn_ratelimited(vdomain->viommu->dev,
 								     "could not queue an unmap\n");
 						goto out;
 					}
 				}
-				spanning = true;
+				span_req = mapping->unmap_req;
 				span_start = mapping->iova.start;
 				span_end = mapping->iova.last;
+				mapping->unmap_req = NULL;
 			}
 		}
 
 		interval_tree_remove(node, &vdomain->mappings);
+		kfree(mapping->unmap_req);
 		kfree(mapping);
 		unmapped += size;
 	}
 
-	if (spanning) {
+	if (span_req) {
 		struct virtio_iommu_req_unmap unmap = {
 			.head.type	= VIRTIO_IOMMU_T_UNMAP,
 			.domain		= cpu_to_le32(vdomain->id),
 			.virt_start	= cpu_to_le64(span_start),
 			.virt_end	= cpu_to_le64(span_end),
 		};
+		struct viommu_request *req = span_req;
 
-		if (viommu_add_req(vdomain->viommu, &unmap, sizeof(unmap))) {
+		span_req = NULL;
+		if (viommu_queue_prealloc_req(vdomain->viommu, req, &unmap,
+					      sizeof(unmap))) {
+			kfree(req);
 			unmapped -= span_end - span_start + 1;
 			dev_warn_ratelimited(vdomain->viommu->dev,
 					     "could not queue an unmap\n");
-- 
2.55.0

[PATCH 4/6] iommu/virtio: stop queueing and draining once the device is removed

[Anlai Lu]

viommu_remove() resets the device and deletes the virtqueues while
userspace may still hold domains that it maps or attaches, and nothing
stopped a request from being queued - or a drain from walking the queue -
on a virtqueue that was being torn down.

Set ->removed under request_lock before the teardown - the lock a
queueing path holds while it checks liveness and adds the request, and
the one the drain holds for its whole run - check it in the queueing
helper, and let the drain return early when it is set.

Fixes: edcd69ab9a32 ("iommu: Add virtio-iommu driver")
Signed-off-by: Anlai Lu <agicy@qq.com>
---
 drivers/iommu/virtio-iommu.c | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
index 1a4366458751..ba1d78e4daa0 100644
--- a/drivers/iommu/virtio-iommu.c
+++ b/drivers/iommu/virtio-iommu.c
@@ -42,6 +42,11 @@ struct viommu_dev {
 	spinlock_t			request_lock;
 	struct list_head		requests;
 	void				*evts;
+	/*
+	 * Set before the teardown: nothing may be queued or drained after
+	 * that.
+	 */
+	bool				removed;
 
 	/* Device configuration */
 	struct iommu_domain_geometry	geometry;
@@ -116,6 +121,16 @@ static struct viommu_domain viommu_identity_domain;
 #define to_viommu_domain(domain)	\
 	container_of(domain, struct viommu_domain, domain)
 
+/*
+ * The device can be removed while its domains still exist (userspace may hold
+ * them for a while), and the queues go away with it: nothing may be queued or
+ * drained after that.
+ */
+static bool viommu_device_live(struct viommu_dev *viommu)
+{
+	return !viommu->removed;
+}
+
 static int viommu_get_req_errno(void *buf, size_t len)
 {
 	struct virtio_iommu_req_tail *tail = buf + len - sizeof(*tail);
@@ -206,6 +221,10 @@ static int viommu_sync_req(struct viommu_dev *viommu)
 	unsigned long flags;
 
 	spin_lock_irqsave(&viommu->request_lock, flags);
+	if (!viommu_device_live(viommu)) {
+		spin_unlock_irqrestore(&viommu->request_lock, flags);
+		return 0;
+	}
 	ret = __viommu_sync_req(viommu);
 	if (ret)
 		dev_dbg(viommu->dev, "could not sync requests (%d)\n", ret);
@@ -229,6 +248,9 @@ static int __viommu_queue_req(struct viommu_dev *viommu,
 
 	assert_spin_locked(&viommu->request_lock);
 
+	if (!viommu_device_live(viommu))
+		return -ENODEV;
+
 	sg_init_one(&top_sg, req->buf, write_offset);
 	sg_init_one(&bottom_sg, req->buf + write_offset,
 		    req->len - write_offset);
@@ -1555,10 +1577,20 @@ static int viommu_probe(struct virtio_device *vdev)
 static void viommu_remove(struct virtio_device *vdev)
 {
 	struct viommu_dev *viommu = vdev->priv;
+	unsigned long flags;
 
 	iommu_device_sysfs_remove(&viommu->iommu);
 	iommu_device_unregister(&viommu->iommu);
 
+	/*
+	 * The queues go away here: nothing may be queued or drained from now
+	 * on.  Taking request_lock is what tells a drain in flight that it has
+	 * to finish before the teardown, since the drain holds it throughout.
+	 */
+	spin_lock_irqsave(&viommu->request_lock, flags);
+	viommu->removed = true;
+	spin_unlock_irqrestore(&viommu->request_lock, flags);
+
 	/* Stop all virtqueues */
 	virtio_reset_device(vdev);
 	vdev->config->del_vqs(vdev);
-- 
2.55.0

[PATCH 5/6] iommu/virtio: read the endpoint count under the lock in the iotlb paths

[Anlai Lu]

viommu_iotlb_sync_map() and viommu_flush_iotlb_all() read nr_endpoints
without the lock its writers take: the one place left after the endpoint
helpers were introduced. Order a sync only when the device holds the
domain, and read the count under the same lock as the writers.

Signed-off-by: Anlai Lu <agicy@qq.com>
---
 drivers/iommu/virtio-iommu.c | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
index ba1d78e4daa0..4e578d4255f6 100644
--- a/drivers/iommu/virtio-iommu.c
+++ b/drivers/iommu/virtio-iommu.c
@@ -131,6 +131,19 @@ static bool viommu_device_live(struct viommu_dev *viommu)
 	return !viommu->removed;
 }
 
+/* Does the device hold this domain for at least one endpoint? */
+static bool viommu_domain_has_endpoint(struct viommu_domain *vdomain)
+{
+	unsigned long flags;
+	bool has;
+
+	spin_lock_irqsave(&vdomain->mappings_lock, flags);
+	has = vdomain->nr_endpoints != 0;
+	spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
+
+	return has;
+}
+
 static int viommu_get_req_errno(void *buf, size_t len)
 {
 	struct virtio_iommu_req_tail *tail = buf + len - sizeof(*tail);
@@ -1273,8 +1286,10 @@ static int viommu_iotlb_sync_map(struct iommu_domain *domain,
 	 * May be called before the viommu is initialized including
 	 * while creating direct mapping
 	 */
-	if (!vdomain->nr_endpoints)
+	if (!viommu_domain_has_endpoint(vdomain))
 		return 0;
+
+	/* Wait for this batch's MAPs, whose outcome nobody looks at */
 	return viommu_sync_req(vdomain->viommu);
 }
 
@@ -1286,7 +1301,7 @@ static void viommu_flush_iotlb_all(struct iommu_domain *domain)
 	 * May be called before the viommu is initialized including
 	 * while creating direct mapping
 	 */
-	if (!vdomain->nr_endpoints)
+	if (!viommu_domain_has_endpoint(vdomain))
 		return;
 	viommu_sync_req(vdomain->viommu);
 }
-- 
2.55.0

[PATCH 6/6] iommu/virtio: batch the mapping replay on domain attach

[Anlai Lu]

viommu_replay_mappings() sent every mapping of a domain to the device
with a synchronous request, holding mappings_lock - and with it
interrupts - across the whole walk, so the IRQ-off window grew with the
number of mappings: 233 ms for 8192 4K mappings, 29 s for a million.

Queue them instead and wait once. One mapping per mappings_lock section,
so that a full virtqueue - the only wait in there - bounds a single lock
hold rather than the whole walk; the walk is a single pass, because the
endpoint was published before it (a mapping inserted while it runs is
queued by map_pages() itself) and a mapping removed meanwhile has its
UNMAP queued in the section that removed it. The requests carry the
device's errno back - the first error it reported - so a rejected replay
fails the attach with the device's own status, and a device that goes
away fails it with -ENODEV rather than reporting a replay that never
happened; a duplicate MAP, which a replay can legitimately produce, is
answered S_INVAL - the spec says a duplicate MAP SHOULD be rejected and
MUST NOT change the existing mapping - and is not treated as a rejection.
A rejected MAP on the map path is still ignored, as before.

Measured, N=8192 4K mappings: max IRQ-off window 233.7 ms -> 1.4-2.5 ms,
and no longer growing with N (1.4-2.5 ms from N=64 to 32768, against
3.6/45/233 ms on the unpatched driver); attach ioctl 218.9/249.0 ->
50.3/48.8 ms (48-67 ms across runs); viommu_send_req_sync() calls 8193 ->
1; the device receives exactly the same MAPs (8244).

Signed-off-by: Anlai Lu <agicy@qq.com>
---
 drivers/iommu/virtio-iommu.c | 149 +++++++++++++++++++++++++++--------
 1 file changed, 117 insertions(+), 32 deletions(-)

diff --git a/drivers/iommu/virtio-iommu.c b/drivers/iommu/virtio-iommu.c
index 4e578d4255f6..7b883f59221f 100644
--- a/drivers/iommu/virtio-iommu.c
+++ b/drivers/iommu/virtio-iommu.c
@@ -73,6 +73,19 @@ struct viommu_mapping {
 	struct viommu_request		*unmap_req;
 };
 
+/* Where a queued request reports a rejection, or NULL */
+struct viommu_req_status {
+	bool				*rejected;
+	/*
+	 * Errno to treat as success: a replayed MAP can be a duplicate,
+	 * which the spec says the device SHOULD reject with S_INVAL and
+	 * MUST NOT change the existing mapping.
+	 */
+	int				ignore_errno;
+	/* The first error the device reported, for the caller to return */
+	int				err;
+};
+
 struct viommu_domain {
 	struct iommu_domain		domain;
 	struct viommu_dev		*viommu;
@@ -104,6 +117,8 @@ struct viommu_request {
 	void				*writeback;
 	unsigned int			write_offset;
 	unsigned int			len;
+	/* Where to report a failure of this request, or NULL */
+	struct viommu_req_status	*status;
 	char				buf[] __counted_by(len);
 };
 
@@ -144,6 +159,19 @@ static bool viommu_domain_has_endpoint(struct viommu_domain *vdomain)
 	return has;
 }
 
+/* Same, for callers that do not hold request_lock */
+static bool viommu_device_alive(struct viommu_dev *viommu)
+{
+	unsigned long flags;
+	bool live;
+
+	spin_lock_irqsave(&viommu->request_lock, flags);
+	live = viommu_device_live(viommu);
+	spin_unlock_irqrestore(&viommu->request_lock, flags);
+
+	return live;
+}
+
 static int viommu_get_req_errno(void *buf, size_t len)
 {
 	struct virtio_iommu_req_tail *tail = buf + len - sizeof(*tail);
@@ -216,6 +244,16 @@ static int __viommu_sync_req(struct viommu_dev *viommu)
 			viommu_set_req_status(req->buf, req->len,
 					      VIRTIO_IOMMU_S_IOERR);
 
+		if (req->status) {
+			int err = viommu_get_req_errno(req->buf, req->len);
+
+			if (err && err != req->status->ignore_errno) {
+				*req->status->rejected = true;
+				if (!req->status->err)
+					req->status->err = err;
+			}
+		}
+
 		write_len = req->len - req->write_offset;
 		if (req->writeback && len == write_len)
 			memcpy(req->writeback, req->buf + req->write_offset,
@@ -286,6 +324,7 @@ static int __viommu_queue_req(struct viommu_dev *viommu,
  * @buf: pointer to the request buffer
  * @len: length of the request buffer
  * @writeback: copy data back to the buffer when the request completes.
+ * @status: where to report a rejection of this request, or NULL
  *
  * Allocate a request object, fill it and queue it.  When @writeback is true,
  * data written by the device, including the request status, is copied into
@@ -295,7 +334,7 @@ static int __viommu_queue_req(struct viommu_dev *viommu,
  * Return 0 if the request was successfully added to the queue.
  */
 static int __viommu_add_req(struct viommu_dev *viommu, void *buf, size_t len,
-			    bool writeback)
+			    bool writeback, struct viommu_req_status *status)
 {
 	int ret;
 	off_t write_offset;
@@ -312,6 +351,7 @@ static int __viommu_add_req(struct viommu_dev *viommu, void *buf, size_t len,
 		return -ENOMEM;
 
 	req->len = len;
+	req->status = status;
 	if (writeback) {
 		req->writeback = buf + write_offset;
 		req->write_offset = write_offset;
@@ -325,13 +365,14 @@ static int __viommu_add_req(struct viommu_dev *viommu, void *buf, size_t len,
 	return ret;
 }
 
-static int viommu_add_req(struct viommu_dev *viommu, void *buf, size_t len)
+static int viommu_add_req(struct viommu_dev *viommu, void *buf, size_t len,
+			  struct viommu_req_status *status)
 {
 	int ret;
 	unsigned long flags;
 
 	spin_lock_irqsave(&viommu->request_lock, flags);
-	ret = __viommu_add_req(viommu, buf, len, false);
+	ret = __viommu_add_req(viommu, buf, len, false, status);
 	if (ret)
 		dev_dbg(viommu->dev, "could not add request: %d\n", ret);
 	spin_unlock_irqrestore(&viommu->request_lock, flags);
@@ -354,6 +395,7 @@ static int viommu_queue_prealloc_req(struct viommu_dev *viommu,
 
 	spin_lock_irqsave(&viommu->request_lock, flags);
 	req->len = len;
+	req->status = NULL;
 	req->writeback = NULL;
 	memcpy(req->buf, buf, write_offset);
 	ret = __viommu_queue_req(viommu, req, write_offset);
@@ -374,7 +416,7 @@ static int viommu_send_req_sync(struct viommu_dev *viommu, void *buf,
 
 	spin_lock_irqsave(&viommu->request_lock, flags);
 
-	ret = __viommu_add_req(viommu, buf, len, true);
+	ret = __viommu_add_req(viommu, buf, len, true, NULL);
 	if (ret) {
 		dev_dbg(viommu->dev, "could not add request (%d)\n", ret);
 		goto out_unlock;
@@ -462,7 +504,7 @@ static int viommu_add_mapping(struct viommu_domain *vdomain, u64 iova, u64 end,
 			.flags		= cpu_to_le32(flags),
 		};
 
-		ret = viommu_add_req(vdomain->viommu, &map, sizeof(map));
+		ret = viommu_add_req(vdomain->viommu, &map, sizeof(map), NULL);
 		if (ret) {
 			interval_tree_remove(&mapping->iova, &vdomain->mappings);
 			spin_unlock_irqrestore(&vdomain->mappings_lock, irqflags);
@@ -656,23 +698,57 @@ static int viommu_domain_map_identity(struct viommu_endpoint *vdev,
 }
 
 /*
- * viommu_replay_mappings - re-send MAP requests
+ * viommu_replay_mappings - send every mapping of the domain again
  *
- * When reattaching a domain that was previously detached from all endpoints,
- * mappings were deleted from the device. Re-create the mappings available in
- * the internal tree.
+ * Used when reattaching a domain that was previously detached from all
+ * endpoints: the device dropped its copy then (it frees a domain together with
+ * its last endpoint).
+ *
+ * The device is not waited for between mappings: they are all queued, one per
+ * mappings_lock section, and waited for once at the end.  A full virtqueue is
+ * the only wait in the loop, so it bounds a single lock hold rather than the
+ * whole walk.  A mapping that was sent concurrently is harmless: the spec says
+ * a duplicate MAP SHOULD be rejected with S_INVAL and MUST NOT change the
+ * existing mapping, and the replay treats that rejection as success.
+ *
+ * A rejected MAP is reported by returning an error, which fails the attach: the
+ * domain would be missing a mapping its driver believes in.  Nothing else is
+ * done about it.
  */
 static int viommu_replay_mappings(struct viommu_domain *vdomain)
 {
-	int ret = 0;
+	bool rejected = false;
+	struct viommu_req_status status = {
+		.rejected	= &rejected,
+		.ignore_errno	= -EINVAL,
+	};
 	unsigned long flags;
-	struct viommu_mapping *mapping;
-	struct interval_tree_node *node;
-	struct virtio_iommu_req_map map;
+	int ret = 0;
+	struct interval_tree_node *node = NULL;
+
+	/*
+	 * A single pass is enough: the endpoint was published before this ran,
+	 * so a mapping inserted while the walk progresses is queued by
+	 * map_pages() itself, and one inserted before it is in the tree when
+	 * the walk starts.  A mapping removed meanwhile is simply not there any
+	 * more, and its UNMAP was queued in the same section that removed it,
+	 * so it cannot end up after a MAP this walk sends.
+	 */
+	u64 next_iova = 0;
+	bool done = false;
+
+	while (!done) {
+		struct viommu_mapping *mapping;
+		struct virtio_iommu_req_map map;
+
+		spin_lock_irqsave(&vdomain->mappings_lock, flags);
+		node = interval_tree_iter_first(&vdomain->mappings, next_iova,
+						-1UL);
+		if (!node) {
+			spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
+			break;
+		}
 
-	spin_lock_irqsave(&vdomain->mappings_lock, flags);
-	node = interval_tree_iter_first(&vdomain->mappings, 0, -1UL);
-	while (node) {
 		mapping = container_of(node, struct viommu_mapping, iova);
 		map = (struct virtio_iommu_req_map) {
 			.head.type	= VIRTIO_IOMMU_T_MAP,
@@ -682,26 +758,35 @@ static int viommu_replay_mappings(struct viommu_domain *vdomain)
 			.phys_start	= cpu_to_le64(mapping->paddr),
 			.flags		= cpu_to_le32(mapping->flags),
 		};
+		ret = viommu_add_req(vdomain->viommu, &map, sizeof(map), &status);
 
-		ret = viommu_send_req_sync(vdomain->viommu, &map, sizeof(map));
-		if (ret) {
-			/*
-			 * The endpoint was published before this walk, so a
-			 * map_pages() racing it can have sent the same MAP
-			 * already: the spec says a duplicate MAP SHOULD be
-			 * rejected with S_INVAL, and the device MUST NOT
-			 * change the existing mapping.
-			 */
-			if (ret != -EINVAL)
-				break;
-			ret = 0;
-		}
+		if (mapping->iova.last == ULONG_MAX)
+			done = true;
+		else
+			next_iova = mapping->iova.last + 1;
+		spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
 
-		node = interval_tree_iter_next(node, 0, -1UL);
+		if (ret)
+			break;
 	}
-	spin_unlock_irqrestore(&vdomain->mappings_lock, flags);
 
-	return ret;
+	/* Wait for all of them outside the lock: this is the batched drain */
+	viommu_sync_req(vdomain->viommu);
+
+	/*
+	 * A device that went away did not take anything: the status pointers of
+	 * the requests still queued are on this frame, so report it here rather
+	 * than pretending the replay delivered the mappings.
+	 */
+	if (!viommu_device_alive(vdomain->viommu))
+		return -ENODEV;
+
+	/* The queueing failure, or what the device said */
+	if (ret)
+		return ret;
+
+	/* Report what the device said, like the synchronous replay did */
+	return rejected ? (status.err ?: -EIO) : 0;
 }
 
 static int viommu_add_resv_mem(struct viommu_endpoint *vdev,
-- 
2.55.0