iommu/arm-smmu-v3: Introduce an RCU-protected invalidation array

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +18 -0

+/**
+ * arm_smmu_invs_add() - Combine @old_invs with @add_invs to a new array
+ * @old_invs: the old invalidation array
+ * @add_invs: an array of invlidations to add
+ *
+ * Return: a newly allocated and sorted invalidation array on success, or an
+ * ERR_PTR.
+ *
+ * This function must be locked and serialized with arm_smmu_invs_del/dec(),
+ * but do not lockdep on any lock for KUNIT test.
+ *
+ * Caller is resposible for freeing the @old_invs and the returned one.
+ *
+ * Entries marked as trash can be resued if @add_invs wants to add them back.
+ * Otherwise, they will be completely removed in the returned array.
+ */
+VISIBLE_IF_KUNIT
+struct arm_smmu_invs *arm_smmu_invs_add(struct arm_smmu_invs *old_invs,

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c void arm_smmu_tlb_inv_asid(struct arm_smmu_device *smmu, u16 asid) · line 1082

Quoted 11 lines · Nicolin Chen

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +11 -0

+struct arm_smmu_invs *arm_smmu_invs_add(struct arm_smmu_invs *old_invs,
+					struct arm_smmu_invs *add_invs)
+{
+	size_t need = old_invs->num_invs + add_invs->num_invs;
+	struct arm_smmu_invs *new_invs;
+	size_t deletes = 0, i, j;
+	u64 existed = 0;
+
+	/* Max of add_invs->num_invs is 64 */
+	if (WARN_ON(add_invs->num_invs > sizeof(existed) * 8))
+		return ERR_PTR(-EINVAL);

Since this is driven off of num_streams using a fixed bitmap doesn't seem great since I suppose the dt isn't limited to 64.

Given how this is working now I think you can just add a new member to the struct:

struct arm_smmu_inv {
	/* invalidation items */
	struct arm_smmu_device *smmu;
	u8 type;
	u8 size_opcode;
	u8 nsize_opcode;
	/* Temporary bits for add/del functions */
	u8 reuse:1;
	u8 todel:1;

And use reuse as the temporary instead of the bitmap.

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c void arm_smmu_tlb_inv_asid(struct arm_smmu_device *smmu, u16 asid) · line 1090

Quoted 5 lines

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +5 -0

+		/* Count the trash entries to deletes */
+		if (cur->todel) {
+			WARN_ON_ONCE(refcount_read(&cur->users));
+			deletes++;
+		}

Just do continue here.

todel should only be used as a temporary. Use refcount_read() ==
0. Then you don't need a WARN either.

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c void arm_smmu_tlb_inv_asid(struct arm_smmu_device *smmu, u16 asid) · line 1100

Quoted 4 lines

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +4 -0

+			/* Revert the todel marker for reuse */
+			if (cur->todel) {
+				cur->todel = false;
+				deletes--;

This wil blow up the refcount_inc() below because users is 0.. There is no point in trying to optimize like this just discard the old entry and add a new one.

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c void arm_smmu_tlb_inv_asid(struct arm_smmu_device *smmu, u16 asid) · line 1131

Quoted 1 line

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +1 -0

+			unsigned int idx = add_invs->inv[j].id;

Similar remarks for del, use users to set todel, don't expect it to be valid coming into the function.

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +9 -0

+/**
+ * arm_smmu_invs_del() - Remove @del_invs from @old_invs
+ * @old_invs: the old invalidation array
+ * @del_invs: an array of invlidations to delete
+ *
+ * Return: a newly allocated and sorted invalidation array on success, or an
+ * ERR_PTR.
+ *
+ * This function must be locked and serialized with arm_smmu_invs_add/dec(),

Quoted 9 lines · Nicolin Chen

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +9 -0

+/**
+ * arm_smmu_invs_del() - Remove @del_invs from @old_invs
+ * @old_invs: the old invalidation array
+ * @del_invs: an array of invlidations to delete
+ *
+ * Return: a newly allocated and sorted invalidation array on success, or an
+ * ERR_PTR.
+ *
+ * This function must be locked and serialized with arm_smmu_invs_add/dec(),

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c void arm_smmu_tlb_inv_asid(struct arm_smmu_device *smmu, u16 asid) · line 1176

Quoted 10 lines

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +10 -0

+ * but do not lockdep on any lock for KUNIT test.
+ *
+ * Caller is resposible for freeing the @old_invs and the returned one.
+ *
+ * Entries marked as trash will be completely removed in the returned array.
+ */
+VISIBLE_IF_KUNIT
+struct arm_smmu_invs *arm_smmu_invs_del(struct arm_smmu_invs *old_invs,
+					struct arm_smmu_invs *del_invs)
+{

Having looked at this more completely, I think we should drop this function.

Just always do decr, then have a simple function to compact the list after the decr:

struct arm_smmu_invs *arm_smmu_invs_cleanup(struct arm_smmu_invs *invs,
size_t to_del)

{
	struct arm_smmu_invs *new_invs;
	size_t i, j;

	if (WARN_ON(invs->num_invs < to_del))
		return NULL;

	new_invs = arm_smmu_invs_alloc(invs->num_invs - to_del);
	if (IS_ERR(new_invs))
		return NULL;

	for (i = 0, j = 0; i != invs->num_invs; i++) {
		if (!refcount_read(&invs->inv[i].users))
			continue;
		new_invs->inv[j] = invs->inv[i];
		j++;
	}
	return new_invs;
}

If this returns NULL then just leave the list alone, it is OK to sit there with the 0 users left behind.

No need for the complex _del function and the _decr function..

This also means the memory doesn't need to be preallocated and it significantly simplifies alot of the logic.

Quoted 2 lines

Just always do decr, then have a simple function to compact the list after the decr:

But the _dec function will always take the write lock, which seems to lose the benefit of using an RCU array?

Quoted 2 lines

If this returns NULL then just leave the list alone, it is OK to sit there with the 0 users left behind.

Yea, it's better than waiting for the next _add function to compact the list.

Quoted 4 lines

No need for the complex _del function and the _decr function..

This also means the memory doesn't need to be preallocated and it significantly simplifies alot of the logic.

By "preallocated" you mean "master->scratch_invs"?

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c void arm_smmu_tlb_inv_asid(struct arm_smmu_device *smmu, u16 asid) · line 1074

Quoted 3 lines · Nicolin Chen

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +3 -0

+struct arm_smmu_invs *arm_smmu_invs_add(struct arm_smmu_invs *old_invs,
+					struct arm_smmu_invs *add_invs)
+{

It turns out it is fairly easy and cheap to sort add_invs by sorting the ids during probe:

(quoted diff) +15 -0

@@ -3983,6 +3989,14 @@ static int arm_smmu_init_sid_strtab(struct arm_smmu_device *smmu, u32 sid)
        return 0;
 }
 
+static int arm_smmu_ids_cmp(const void *_l, const void *_r)
+{
+       const typeof_member(struct iommu_fwspec, ids[0]) *l = _l;
+       const typeof_member(struct iommu_fwspec, ids[0]) *r = _r;
+
+       return cmp_int(*l, *r);
+}
+
 static int arm_smmu_insert_master(struct arm_smmu_device *smmu,
                                  struct arm_smmu_master *master)
 {

@@ -4011,6 +4025,13 @@ static int arm_smmu_insert_master(struct arm_smmu_device *smmu,
                return PTR_ERR(master->invs);
        }
 
+       /*
+        * Put the ids into order so that arm_smmu_build_invs() can trivially
+        * generate sorted lists.
+        */
+       sort_nonatomic(fwspec->ids, fwspec->num_ids, sizeof(fwspec->ids[0]),
+                      arm_smmu_ids_cmp, NULL);
+
        mutex_lock(&smmu->streams_mutex);
        for (i = 0; i < fwspec->num_ids; i++) {
                struct arm_smmu_stream *new_stream = &master->streams[i];

Then arm_smmu_build_invs() trivially makes sorted lists.

So if old_invs and add_invs are both sorted list we can use variations on a merge algorithm for sorted lists which is both simpler to understand and runs faster:

/*
* Compare used for merging two sorted lists. Merge compare of two sorted list
* items. If one side is past the end of the list then return the other side to
* let it run out the iteration.
*/
static inline int arm_smmu_invs_merge_cmp(const struct arm_smmu_invs *lhs,
size_t lhs_idx,
const struct arm_smmu_invs *rhs, size_t rhs_idx)

{
	if (lhs_idx != lhs->num_invs && rhs_idx != rhs->num_invs)
		return arm_smmu_invs_cmp(&lhs->inv[lhs_idx],
					 &rhs->inv[rhs_idx]);
	if (lhs_idx != lhs->num_invs)
		return -1;
	return 1;
}

struct arm_smmu_invs *arm_smmu_invs_add(struct arm_smmu_invs *invs,
struct arm_smmu_invs *add_invs)

{
	struct arm_smmu_invs *new_invs;
	struct arm_smmu_inv *new;
	size_t to_add = 0;
	size_t to_del = 0;
	size_t i, j;

	for (i = 0, j = 0; i != invs->num_invs || j != add_invs->num_invs;) {
		int cmp = arm_smmu_invs_merge_cmp(invs, i, add_invs, j);

		if (cmp < 0) {
			/* not found in add_invs, leave alone */
			if (refcount_read(&invs->inv[i].users))
				i++;
			else
				to_del++;
		} else if (cmp == 0) {
			/* same item */
			i++;
			j++;
		} else {
			/* unique to add_invs */
			to_add++;
			j++;
		}
	}

	new_invs = arm_smmu_invs_alloc(invs->num_invs + to_add - to_del);
	if (IS_ERR(new_invs))
		return new_invs;

	new = new_invs->inv;
	for (i = 0, j = 0; i != invs->num_invs || j != add_invs->num_invs;) {
		int cmp = arm_smmu_invs_merge_cmp(invs, i, add_invs, j);

		if (cmp <= 0 && !refcount_read(&invs->inv[i].users)) {
			i++;
			continue;
		}

		if (cmp < 0) {
			*new = invs->inv[i];
			i++;
		} else if (cmp == 0) {
			*new = invs->inv[i];
			refcount_inc(&new->users);
			i++;
			j++;
		} else {
			*new = add_invs->inv[j];
			refcount_set(&new->users, 1);
			j++;
		}
		if (arm_smmu_inv_is_ats(new))
			new_invs->has_ats = true;
		new++;
	}

	WARN_ON(new != new_invs->inv + new_invs->num_invs);

	/*
	 * A sorted array allows batching invalidations together for fewer SYNCs.
	 * Also, ATS must follow the ASID/VMID invalidation SYNC.
	 */
	sort_nonatomic(new_invs->inv, new_invs->num_invs,
		       sizeof(add_invs->inv[0]), arm_smmu_invs_cmp, NULL);
	return new_invs;
}

size_t arm_smmu_invs_dec(struct arm_smmu_invs *invs,
struct arm_smmu_invs *dec_invs)

{
	size_t to_del = 0;
	size_t i, j;

	for (i = 0, j = 0; i != invs->num_invs || j != dec_invs->num_invs;) {
		int cmp = arm_smmu_invs_merge_cmp(invs, i, dec_invs, j);

		if (cmp < 0) {
			/* not found in dec_invs, leave alone */
			i++;
		} else if (cmp == 0) {
			/* same item */
			if (refcount_dec_and_test(&invs->inv[i].users)) {
				dec_invs->inv[j].todel = true;
				to_del++;
			}
			i++;
			j++;
		} else {
			/* item in dec_invs is not in invs? */
			WARN_ON(true);
			j++;
		}
	}
	return to_del;
}

Quoted 7 lines

	/*
	 * A sorted array allows batching invalidations together for fewer SYNCs.
	 * Also, ATS must follow the ASID/VMID invalidation SYNC.
	 */
	sort_nonatomic(new_invs->inv, new_invs->num_invs,
		       sizeof(add_invs->inv[0]), arm_smmu_invs_cmp, NULL);
	return new_invs;

Quoted 7 lines · Nicolin Chen

Quoted 7 lines

	/*
	 * A sorted array allows batching invalidations together for fewer SYNCs.
	 * Also, ATS must follow the ASID/VMID invalidation SYNC.
	 */
	sort_nonatomic(new_invs->inv, new_invs->num_invs,
		       sizeof(add_invs->inv[0]), arm_smmu_invs_cmp, NULL);
	return new_invs;

This should be deleted, merge sort always makes sorted lists.

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c static int arm_smmu_insert_master(struct arm_smmu_device *smmu, · line 3739

Quoted 10 lines · Nicolin Chen

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +6 -0

@@ -3730,6 +3731,13 @@ static int arm_smmu_insert_master(struct arm_smmu_device *smmu,
 		return -ENOMEM;
 	master->num_streams = fwspec->num_ids;
 
+	/* Max possible num_invs: two for ASID/VMIDs and num_ats for ATC_INVs */
+	master->invs = arm_smmu_invs_alloc(2 + num_ats);
+	if (IS_ERR(master->invs)) {
+		kfree(master->streams);
+		return PTR_ERR(master->invs);
+	}

This seems like a nice solution, but I would add a comment here that it is locked by the group mutex, and check if ATS is supported:

	/*
	 * Scratch memory to build the per-domain invalidation list. locked by
	 * the group_mutex. Max possible num_invs: two for ASID/VMIDs and
	 * num_streams for ATC_INVs
	 */
	if (dev_is_pci(master->dev) &&
	    pci_ats_supported(to_pci_dev(master->dev)))
		master->invs = arm_smmu_invs_alloc(2 + master->num_streams);
	else
		master->invs = arm_smmu_invs_alloc(2);

And probably rename it scratch_invs or something to indicate it is temporary memory.

One thing that I noticed is that group mutex alone isn't enough, because there can be two arm_smmu_build_invs() calls during the same attach_dev callback. And the second one would overwrite.

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +21 -0

+static struct arm_smmu_invs *arm_smmu_build_invs(
+	struct arm_smmu_invs *old_invs, struct arm_smmu_domain *smmu_domain,
+	struct arm_smmu_master *master, bool ats, ioasid_t ssid, invs_fn fn)
+{
+	const bool e2h = master->smmu->features & ARM_SMMU_FEAT_E2H;
+	const bool nesting = smmu_domain->nest_parent;
+	struct arm_smmu_inv *cur = master->invs->inv;
+	size_t num_invs = 1;
+	size_t i;
+
+	switch (smmu_domain->stage) {
+	case ARM_SMMU_DOMAIN_SVA:
+	case ARM_SMMU_DOMAIN_S1:
+		cur->smmu = master->smmu;
+		cur->type = INV_TYPE_S1_ASID;
+		cur->id = smmu_domain->cd.asid;
+		cur->size_opcode = e2h ? CMDQ_OP_TLBI_EL2_VA :
+					 CMDQ_OP_TLBI_NH_VA;
+		cur->nsize_opcode = e2h ? CMDQ_OP_TLBI_EL2_ASID :
+					  CMDQ_OP_TLBI_NH_ASID;
+		break;

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +14 -0

+		cur->smmu = master->smmu;
+		cur->type = INV_TYPE_S2_VMID_S1_CLEAR;
+		cur->id = smmu_domain->s2_cfg.vmid;
+		cur->size_opcode = CMDQ_OP_TLBI_NH_ALL;
+		cur->nsize_opcode = CMDQ_OP_TLBI_NH_ALL;
+	}
+
+	if (ats) {
+		for (i = 0, cur++; i < master->num_streams; i++) {
+			cur->smmu = master->smmu;
+			/*
+			 * If an S2 used as a nesting parent is changed we have
+			 * no option but to completely flush the ATC.
+			 */

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +10 -0

+		state->new_domain_oinvs = rcu_dereference_protected(
+			new_smmu_domain->invs,
+			lockdep_is_held(&arm_smmu_asid_lock));
+		state->new_domain_ninvs = arm_smmu_build_invs(
+			state->new_domain_oinvs, new_smmu_domain, master,
+			state->ats_enabled, state->ssid, arm_smmu_invs_add);
+		if (IS_ERR(state->new_domain_ninvs))
+			return PTR_ERR(state->new_domain_ninvs);
+		state->new_domain_invs = &new_smmu_domain->invs;
+		blocking = new_smmu_domain->domain.type == IOMMU_DOMAIN_BLOCKED;

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c static void arm_smmu_remove_master_domain(struct arm_smmu_master *master, · line 3186

Quoted 3 lines · Nicolin Chen

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +3 -0

+static int arm_smmu_attach_prepare_invs(struct arm_smmu_attach_state *state,
+					struct arm_smmu_domain *new_smmu_domain)
+{

How about a comment:

/*
* During attachment the invalidation lists on the two domains are sequenced:

 *  1. old domain is invalidating master
 *  2. new and old domain are invalidating master
 *  3. new domain is invalidating master

*
* This uses two updated invalidation lists, one with master added to new domain
* and one with master removed from old domain. Prepare these lists in advance
* of changing anything. arm_smmu_asid_lock ensures that the invalidation list
* in the domains doesn't change while we are sequencing to update it. */

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c static void arm_smmu_disable_iopf(struct arm_smmu_master *master, · line 3086

Quoted 2 lines · Nicolin Chen

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +2 -0

+typedef struct arm_smmu_invs *(*invs_fn)(struct arm_smmu_invs *old_invs,
+					 struct arm_smmu_invs *invs);

no reason to pass in fn, this always just calls it as the last thing so the caller can do it..

Quoted 3 lines

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +3 -0

+static struct arm_smmu_invs *arm_smmu_build_invs(
+	struct arm_smmu_invs *old_invs, struct arm_smmu_domain *smmu_domain,
+	struct arm_smmu_master *master, bool ats, ioasid_t ssid, invs_fn fn)

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +40 -0

+void arm_smmu_domain_inv_range(struct arm_smmu_domain *smmu_domain,
+			       unsigned long iova, size_t size,
+			       unsigned int granule, bool leaf)
+{
+	struct arm_smmu_cmdq_batch cmds = {};
+	struct arm_smmu_invs *invs;
+	bool retried = false;
+	size_t i;
+
+	/*
+	 * An invalidation request must follow some IOPTE change and then load
+	 * the invalidation array In the meantime, a domain attachment mutates
+	 * the array and then stores an STE/CD asking SMMU HW to acquire those
+	 * changed IOPTEs. In other word, these two are interdependent and can
+	 * race.
+	 *
+	 * In a race, the RCU design (with its underlying memory barriers) can
+	 * ensure the invalidations array to always get updated before loaded.
+	 *
+	 * smp_mb() is used here, paired with the smp_mb() following the array
+	 * update in a concurrent attach, to ensure:
+	 *  - HW sees the new IOPTEs if it walks after STE installation
+	 *  - Invalidation thread sees the updated array with the new ASID.
+	 *
+	 *  [CPU0]                        | [CPU1]
+	 *                                |
+	 *  change IOPTEs and TLB flush:  |
+	 *  arm_smmu_domain_inv_range() { | arm_smmu_install_new_domain_invs {
+	 *    ...                         |   rcu_assign_pointer(new_invs);
+	 *    smp_mb(); // ensure IOPTEs  |   smp_mb(); // ensure new_invs
+	 *    ...                         |   kfree_rcu(old_invs, rcu);
+	 *    // load invalidation array  | }
+	 *    invs = rcu_dereference();   | arm_smmu_install_ste_for_dev {
+	 *                                |   STE = TTB0 // read new IOPTEs
+	 */
+	smp_mb();
+
+	rcu_read_lock();
+again:
+	invs = rcu_dereference(smmu_domain->invs);

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c void arm_smmu_tlb_inv_range_asid(unsigned long iova, size_t size, int asid, · line 2781

Quoted 12 lines · Nicolin Chen

drivers/iommu/arm/arm-smmu-v3/arm-smmu-v3.c +12 -0

+again:
+	invs = rcu_dereference(smmu_domain->invs);
+
+	/* A concurrent attachment might have changed the array. Do a respin */
+	if (unlikely(!read_trylock(&invs->rwlock)))
+		goto again;
+	/* Only one retry. Otherwise, it would soft lockup on an empty array */
+	if (!retried && unlikely(!invs->num_invs)) {
+		read_unlock(&invs->rwlock);
+		retried = true;
+		goto again;
+	}

This has missed the point, it was to not get the unless we have ATS. Something like this:

	rcu_read_lock();

	while (true) {
		invs = rcu_dereference(smmu_domain->invs);

		/*
		 * Avoid locking unless ATS is being used. No ATS invalidate can
		 * be going on after a domain is detached.
		 */
		locked = false;
		if (invs->has_ats || READ_ONCE(invs->old)) {
			read_lock(&invs->rwlock);

			if (invs->old) {
				read_unlock(&invs->rwlock);
				continue;
			}
			locked = true;
		}
		break;
	}

I know that performance-wise, this piece will be a quick respin, as the attach side releases the lock very fast. It still looks a bit complicated. And practically, it would respin even if the attachment removes a non-PCI device, right?

Quoted 4 lines · Nicolin Chen

I know that performance-wise, this piece will be a quick respin, as the attach side releases the lock very fast. It still looks a bit complicated. And practically, it would respin even if the attachment removes a non-PCI device, right?

If you are paying the cost of taking the lock then it should become fully locked and consistent.

Quoted 7 lines · Jason Gunthorpe

Quoted 4 lines · Nicolin Chen

I know that performance-wise, this piece will be a quick respin, as the attach side releases the lock very fast. It still looks a bit complicated. And practically, it would respin even if the attachment removes a non-PCI device, right?

Quoted 2 lines

If you are paying the cost of taking the lock then it should become fully locked and consistent.

Well, the point is that the reader doesn't know if an ATS entry is getting removed, and it can only speculate by looking at the full list.

So, would it be better to just always take the read lock, while applying the ATS condition to the writer side:

Quoted 2 lines · Nicolin Chen

So, would it be better to just always take the read lock, while applying the ATS condition to the writer side:

No, the whole optimization is to avoid read side locking on the fairly common no-ATS case.

Always taking the lock destroys that.