irqfd enhancements, and irq_routing fixes

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

   irq_rt->entry->set(); /* bad */

-------------------------------------------------------------

Because the pointer is accessed outside of the read-side critical section. There are two basic patterns we can use to fix this bug:

1) Switch to sleeping-rcu and encompass the ->set() access within the read-side critical section,

OR

2) Add reference counting to the irq_rt structure, and simply acquire the reference from within the RSCS.

This patch implements solution (1).

Signed-off-by Gregory Haskins <[email protected]>

---

 include/linux/kvm_host.h |    6 +++++-
 virt/kvm/irq_comm.c      |   50 +++++++++++++++++++++++++++-------------------
 virt/kvm/kvm_main.c      |    1 +
 3 files changed, 35 insertions(+), 22 deletions(-)

include/linux/kvm_host.h +0 -0

index bd5a616..1fe135d 100644

include/linux/kvm_host.h +8 -7

+			int r;
 
-	while(i--) {
-		int r;
-		r = irq_set[i].set(&irq_set[i], kvm, irq_source_id, level);
-		if (r < 0)
-			continue;
+			r = e->set(e, kvm, irq_source_id, level);
+			if (r < 0)
+				continue;
 
-		ret = r + ((ret < 0) ? 0 : ret);
-	}
+			ret = r + ((ret < 0) ? 0 : ret);
+		}
+	srcu_read_unlock(&kvm->irq_routing.srcu, idx);
 
 	return ret;
 }

@@ -179,17 +178,18 @@ void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin)
 	struct kvm_irq_ack_notifier *kian;
 	struct hlist_node *n;
 	int gsi;
+	int idx;

Quoted 29 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

   irq_rt->entry->set(); /* bad */

-------------------------------------------------------------

Because the pointer is accessed outside of the read-side critical section. There are two basic patterns we can use to fix this bug:

1) Switch to sleeping-rcu and encompass the ->set() access within the read-side critical section,

Quoted 6 lines

OR

2) Add reference counting to the irq_rt structure, and simply acquire the reference from within the RSCS.

This patch implements solution (1).

Looks like a good transformation! A few questions interspersed below.

Quoted 15 lines

Signed-off-by Gregory Haskins <[email protected]>

---

 include/linux/kvm_host.h |    6 +++++-
 virt/kvm/irq_comm.c      |   50 +++++++++++++++++++++++++++-------------------
 virt/kvm/kvm_main.c      |    1 +
 3 files changed, 35 insertions(+), 22 deletions(-)

include/linux/kvm_host.h +0 -0

index bd5a616..1fe135d 100644
@@ -185,7 +185,10 @@ struct kvm {
 

include/linux/kvm_host.h struct kvm { · line 189

Quoted 5 lines

include/linux/kvm_host.h +2 -1

 	struct mutex irq_lock;
 #ifdef CONFIG_HAVE_KVM_IRQCHIP
-	struct kvm_irq_routing_table *irq_routing;
+	struct {
+		struct srcu_struct            srcu;

Each structure has its own SRCU domain. This is OK, but just asking if that is the intent. It does look like the SRCU primitives are passed a pointer to the correct structure, and that the return value from srcu_read_lock() gets passed into the matching srcu_read_unlock() like it needs to be, so that is good.

include/linux/kvm_host.h struct kvm { · line 194

Quoted 6 lines

include/linux/kvm_host.h +2 -0

+		struct kvm_irq_routing_table *table;
+	} irq_routing;
 	struct hlist_head mask_notifier_list;
 	struct hlist_head irq_ack_notifier_list;
 #endif

[ . . . ]

include/linux/kvm_host.h int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level) · line 162

Quoted 13 lines

include/linux/kvm_host.h +3 -5

@@ -155,21 +156,19 @@ int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level)
 	 * IOAPIC.  So set the bit in both. The guest will ignore
 	 * writes to the unused one.
 	 */
-	rcu_read_lock();
-	irq_rt = rcu_dereference(kvm->irq_routing);
+	idx = srcu_read_lock(&kvm->irq_routing.srcu);
+	irq_rt = rcu_dereference(kvm->irq_routing.table);
 	if (irq < irq_rt->nr_rt_entries)
-		hlist_for_each_entry(e, n, &irq_rt->map[irq], link)
-			irq_set[i++] = *e;
-	rcu_read_unlock();
+		hlist_for_each_entry(e, n, &irq_rt->map[irq], link) {

What prevents the above list from changing while we are traversing it? (Yes, presumably whatever was preventing it from changing before this patch, but what?)

Mostly kvm->lock is held, but not always. And if kvm->lock were held all the time, there would be no point in using SRCU. ;-)

Quoted 28 lines

include/linux/kvm_host.h +8 -7

+			int r;
 
-	while(i--) {
-		int r;
-		r = irq_set[i].set(&irq_set[i], kvm, irq_source_id, level);
-		if (r < 0)
-			continue;
+			r = e->set(e, kvm, irq_source_id, level);
+			if (r < 0)
+				continue;
 
-		ret = r + ((ret < 0) ? 0 : ret);
-	}
+			ret = r + ((ret < 0) ? 0 : ret);
+		}
+	srcu_read_unlock(&kvm->irq_routing.srcu, idx);
 
 	return ret;
 }

@@ -179,17 +178,18 @@ void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin)
 	struct kvm_irq_ack_notifier *kian;
 	struct hlist_node *n;
 	int gsi;
+	int idx;
 
 	trace_kvm_ack_irq(irqchip, pin);
 

include/linux/kvm_host.h void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin) · line 189

Quoted 7 lines

include/linux/kvm_host.h +2 -2

-	rcu_read_lock();
-	gsi = rcu_dereference(kvm->irq_routing)->chip[irqchip][pin];
+	idx = srcu_read_lock(&kvm->irq_routing.srcu);
+	gsi = rcu_dereference(kvm->irq_routing.table)->chip[irqchip][pin];
 	if (gsi != -1)
 		hlist_for_each_entry_rcu(kian, n, &kvm->irq_ack_notifier_list,
 					 link)

And same question here -- what keeps the above list from changing while we are traversing it?

Hi Paul,

Quoted 35 lines · Paul E. McKenney

Quoted 34 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

   irq_rt->entry->set(); /* bad */

-------------------------------------------------------------

Because the pointer is accessed outside of the read-side critical section. There are two basic patterns we can use to fix this bug:

1) Switch to sleeping-rcu and encompass the ->set() access within the read-side critical section,

OR

2) Add reference counting to the irq_rt structure, and simply acquire the reference from within the RSCS.

Quoted 3 lines

Quoted 1 line

This patch implements solution (1).

Looks like a good transformation! A few questions interspersed below.

Thanks for the review. I would have CC'd you but I figured I pestered you enough with my RCU reviews in the past, and didn't want to annoy you ;)

I will be sure to CC you in the future, unless you ask otherwise.

Quoted 14 lines

Quoted 14 lines

Signed-off-by Gregory Haskins <[email protected]>

---

 include/linux/kvm_host.h |    6 +++++-
 virt/kvm/irq_comm.c      |   50 +++++++++++++++++++++++++++-------------------
 virt/kvm/kvm_main.c      |    1 +
 3 files changed, 35 insertions(+), 22 deletions(-)

include/linux/kvm_host.h +0 -0

index bd5a616..1fe135d 100644
@@ -185,7 +185,10 @@ struct kvm {
 

Quoted 11 lines

include/linux/kvm_host.h struct kvm { · line 189

Quoted 5 lines

include/linux/kvm_host.h +2 -1

 	struct mutex irq_lock;
 #ifdef CONFIG_HAVE_KVM_IRQCHIP
-	struct kvm_irq_routing_table *irq_routing;
+	struct {
+		struct srcu_struct            srcu;

Each structure has its own SRCU domain. This is OK, but just asking if that is the intent. It does look like the SRCU primitives are passed a pointer to the correct structure, and that the return value from srcu_read_lock() gets passed into the matching srcu_read_unlock() like it needs to be, so that is good.

Yeah, it was intentional. Technically the table is per-guest, and thus the locking is too, which is the desired/intentional granularity.

On that note, I tried to denote that kvm->irq_routing.srcu and kvm->irq_routing.table were related to one another, but then went ahead and modified the hunks that touched kvm->irq_ack_notifier_list, too. In retrospect, this was probably a mistake. I should leave the rcu usage outside of ->irq_routing.table alone.

Quoted 27 lines

include/linux/kvm_host.h struct kvm { · line 194

Quoted 6 lines

include/linux/kvm_host.h +2 -0

+		struct kvm_irq_routing_table *table;
+	} irq_routing;
 	struct hlist_head mask_notifier_list;
 	struct hlist_head irq_ack_notifier_list;
 #endif

[ . . . ]

include/linux/kvm_host.h int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level) · line 162

Quoted 13 lines

include/linux/kvm_host.h +3 -5

@@ -155,21 +156,19 @@ int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level)
 	 * IOAPIC.  So set the bit in both. The guest will ignore
 	 * writes to the unused one.
 	 */
-	rcu_read_lock();
-	irq_rt = rcu_dereference(kvm->irq_routing);
+	idx = srcu_read_lock(&kvm->irq_routing.srcu);
+	irq_rt = rcu_dereference(kvm->irq_routing.table);
 	if (irq < irq_rt->nr_rt_entries)
-		hlist_for_each_entry(e, n, &irq_rt->map[irq], link)
-			irq_set[i++] = *e;
-	rcu_read_unlock();
+		hlist_for_each_entry(e, n, &irq_rt->map[irq], link) {

What prevents the above list from changing while we are traversing it? (Yes, presumably whatever was preventing it from changing before this patch, but what?)

Quoted 2 lines

Mostly kvm->lock is held, but not always. And if kvm->lock were held all the time, there would be no point in using SRCU. ;-)

This is protected by kvm->irq_lock within kvm_set_irq_routing(). Entries are added to a copy of the list, and the top-level table pointer is swapped (via rcu_assign_pointer(), as it should be) while holding the lock. Finally, we synchronize with the RSCS before deleting the old copy. It looks to me like the original author got this part right, so I didn't modify it outside of converting to SRCU.

Quoted 28 lines

Quoted 28 lines

include/linux/kvm_host.h +8 -7

+			int r;
 
-	while(i--) {
-		int r;
-		r = irq_set[i].set(&irq_set[i], kvm, irq_source_id, level);
-		if (r < 0)
-			continue;
+			r = e->set(e, kvm, irq_source_id, level);
+			if (r < 0)
+				continue;
 
-		ret = r + ((ret < 0) ? 0 : ret);
-	}
+			ret = r + ((ret < 0) ? 0 : ret);
+		}
+	srcu_read_unlock(&kvm->irq_routing.srcu, idx);
 
 	return ret;
 }

@@ -179,17 +178,18 @@ void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin)
 	struct kvm_irq_ack_notifier *kian;
 	struct hlist_node *n;
 	int gsi;
+	int idx;
 
 	trace_kvm_ack_irq(irqchip, pin);
 

Quoted 10 lines

include/linux/kvm_host.h void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin) · line 189

Quoted 7 lines

include/linux/kvm_host.h +2 -2

-	rcu_read_lock();
-	gsi = rcu_dereference(kvm->irq_routing)->chip[irqchip][pin];
+	idx = srcu_read_lock(&kvm->irq_routing.srcu);
+	gsi = rcu_dereference(kvm->irq_routing.table)->chip[irqchip][pin];
 	if (gsi != -1)
 		hlist_for_each_entry_rcu(kian, n, &kvm->irq_ack_notifier_list,
 					 link)

And same question here -- what keeps the above list from changing while we are traversing it?

This is also protected via the kvm->irq_lock in kvm_register_irq_ack_notifier(). Though as mentioned above, I should probably drop the non irq_routing.table hunks, so this will go away. But I think its correct either way.

Thanks Paul,
-Greg

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

   irq_rt->entry->set(); /* bad */

-------------------------------------------------------------

Because the pointer is accessed outside of the read-side critical section. There are two basic patterns we can use to fix this bug:

1) Switch to sleeping-rcu and encompass the ->set() access within the read-side critical section,

OR

2) Add reference counting to the irq_rt structure, and simply acquire the reference from within the RSCS.

This patch implements solution (1).

Signed-off-by Gregory Haskins <[email protected]>

---

 include/linux/kvm_host.h |    6 +++++-
 virt/kvm/irq_comm.c      |   50 +++++++++++++++++++++++++++-------------------
 virt/kvm/kvm_main.c      |    1 +
 3 files changed, 35 insertions(+), 22 deletions(-)

include/linux/kvm_host.h +5 -1

index bd5a616..1fe135d 100644
@@ -185,7 +185,10 @@ struct kvm {
 
 	struct mutex irq_lock;
 #ifdef CONFIG_HAVE_KVM_IRQCHIP
-	struct kvm_irq_routing_table *irq_routing;
+	struct {
+		struct srcu_struct            srcu;
+		struct kvm_irq_routing_table *table;
+	} irq_routing;
 	struct hlist_head mask_notifier_list;
 	struct hlist_head irq_ack_notifier_list;
 #endif

@@ -541,6 +544,7 @@ int kvm_set_irq_routing(struct kvm *kvm,
 			const struct kvm_irq_routing_entry *entries,
 			unsigned nr,
 			unsigned flags);
+void kvm_init_irq_routing(struct kvm *kvm);
 void kvm_free_irq_routing(struct kvm *kvm);
 
 #else

virt/kvm/irq_comm.c +29 -21

index 00c68d2..db2553f 100644
@@ -144,10 +144,11 @@ static int kvm_set_msi(struct kvm_kernel_irq_routing_entry *e,
  */
 int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level)
 {
-	struct kvm_kernel_irq_routing_entry *e, irq_set[KVM_NR_IRQCHIPS];
-	int ret = -1, i = 0;
+	struct kvm_kernel_irq_routing_entry *e;
+	int ret = -1;
 	struct kvm_irq_routing_table *irq_rt;
 	struct hlist_node *n;
+	int idx;
 
 	trace_kvm_set_irq(irq, level, irq_source_id);
 

@@ -155,21 +156,19 @@ int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level)
 	 * IOAPIC.  So set the bit in both. The guest will ignore
 	 * writes to the unused one.
 	 */
-	rcu_read_lock();
-	irq_rt = rcu_dereference(kvm->irq_routing);
+	idx = srcu_read_lock(&kvm->irq_routing.srcu);
+	irq_rt = rcu_dereference(kvm->irq_routing.table);
 	if (irq < irq_rt->nr_rt_entries)
-		hlist_for_each_entry(e, n, &irq_rt->map[irq], link)
-			irq_set[i++] = *e;
-	rcu_read_unlock();
+		hlist_for_each_entry(e, n, &irq_rt->map[irq], link) {
+			int r;
 
-	while(i--) {
-		int r;
-		r = irq_set[i].set(&irq_set[i], kvm, irq_source_id, level);
-		if (r < 0)
-			continue;
+			r = e->set(e, kvm, irq_source_id, level);
+			if (r < 0)
+				continue;
 
-		ret = r + ((ret < 0) ? 0 : ret);
-	}
+			ret = r + ((ret < 0) ? 0 : ret);
+		}
+	srcu_read_unlock(&kvm->irq_routing.srcu, idx);
 
 	return ret;
 }

@@ -179,17 +178,18 @@ void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin)
 	struct kvm_irq_ack_notifier *kian;
 	struct hlist_node *n;
 	int gsi;
+	int idx;
 
 	trace_kvm_ack_irq(irqchip, pin);
 
-	rcu_read_lock();
-	gsi = rcu_dereference(kvm->irq_routing)->chip[irqchip][pin];
+	idx = srcu_read_lock(&kvm->irq_routing.srcu);
+	gsi = rcu_dereference(kvm->irq_routing.table)->chip[irqchip][pin];
 	if (gsi != -1)
 		hlist_for_each_entry_rcu(kian, n, &kvm->irq_ack_notifier_list,
 					 link)
 			if (kian->gsi == gsi)
 				kian->irq_acked(kian);
-	rcu_read_unlock();
+	srcu_read_unlock(&kvm->irq_routing.srcu, idx);
 }
 
 void kvm_register_irq_ack_notifier(struct kvm *kvm,

@@ -287,11 +287,19 @@ void kvm_fire_mask_notifiers(struct kvm *kvm, int irq, bool mask)
 	rcu_read_unlock();
 }
 
+void kvm_init_irq_routing(struct kvm *kvm)
+{
+	init_srcu_struct(&kvm->irq_routing.srcu);
+}
+
 void kvm_free_irq_routing(struct kvm *kvm)
 {
 	/* Called only during vm destruction. Nobody can use the pointer
 	   at this stage */
-	kfree(kvm->irq_routing);
+	synchronize_srcu(&kvm->irq_routing.srcu);
+	cleanup_srcu_struct(&kvm->irq_routing.srcu);
+
+	kfree(kvm->irq_routing.table);
 }
 
 static int setup_routing_entry(struct kvm_irq_routing_table *rt,

@@ -396,10 +404,10 @@ int kvm_set_irq_routing(struct kvm *kvm,
 	}
 
 	mutex_lock(&kvm->irq_lock);
-	old = kvm->irq_routing;
-	rcu_assign_pointer(kvm->irq_routing, new);
+	old = kvm->irq_routing.table;
+	rcu_assign_pointer(kvm->irq_routing.table, new);
 	mutex_unlock(&kvm->irq_lock);
-	synchronize_rcu();
+	synchronize_srcu(&kvm->irq_routing.srcu);
 
 	new = old;
 	r = 0;

virt/kvm/kvm_main.c +1 -1

index cac69c4..ba94159 100644
@@ -388,6 +388,7 @@ static struct kvm *kvm_create_vm(void)
 	atomic_inc(&kvm->mm->mm_count);
 	spin_lock_init(&kvm->mmu_lock);
 	spin_lock_init(&kvm->requests_lock);
+	kvm_init_irq_routing(kvm);
 	kvm_io_bus_init(&kvm->pio_bus);
 	kvm_eventfd_init(kvm);
 	mutex_init(&kvm->lock);
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 17 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

Quoted 4 lines

                                          kfree(irq_rt);

   irq_rt->entry->set(); /* bad */

This is not what happens. irq_rt is never accessed outside read-side critical section.

Data is copied from irq_rt onto the stack and this copy is accessed outside critical section.

Quoted 20 lines · Gleb Natapov

Quoted 19 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

Quoted 4 lines

Quoted 2 lines

   irq_rt->entry->set(); /* bad */

This is not what happens. irq_rt is never accessed outside read-side critical section.

Sorry, I was generalizing to keep the comments short. I figured it would be clear what I was actually saying, but realize in retrospect that I was a little ambiguous.

Quoted 21 lines · Gregory Haskins

Quoted 20 lines · Gleb Natapov

Quoted 19 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

Quoted 8 lines

Quoted 4 lines

Quoted 2 lines

   irq_rt->entry->set(); /* bad */

This is not what happens. irq_rt is never accessed outside read-side critical section.

Sorry, I was generalizing to keep the comments short. I figured it would be clear what I was actually saying, but realize in retrospect that I was a little ambiguous.

Here is a revised problem statement

    thread-1                                    thread-2
    -----------------------------------------------------------

    kvm_set_irq() {
       rcu_read_lock()
       irq_rt = rcu_dereference(table);
       entry_cache = get_entries(irq_rt);
       rcu_read_unlock();

                                            invalidate_entries(irq_rt);

       for_each_entry(entry_cache)
	  entry->set(); /* bad */

    -------------------------------------------------------------

"invalidate_entries()" may be any operation that deletes an entry at run-time (doesn't exist today), or as the guest is shutting down. As far as I can tell, the current code does not protect us from either condition, and my proposed patch protects us from both. Did I miss anything?

Quoted 48 lines · Gregory Haskins

Quoted 21 lines · Gregory Haskins

Quoted 20 lines · Gleb Natapov

Quoted 19 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

   irq_rt->entry->set(); /* bad */

This is not what happens. irq_rt is never accessed outside read-side critical section.

Sorry, I was generalizing to keep the comments short. I figured it would be clear what I was actually saying, but realize in retrospect that I was a little ambiguous.

Here is a revised problem statement

    thread-1                                    thread-2
    -----------------------------------------------------------

    kvm_set_irq() {
       rcu_read_lock()
       irq_rt = rcu_dereference(table);
       entry_cache = get_entries(irq_rt);
       rcu_read_unlock();

                                            invalidate_entries(irq_rt);

       for_each_entry(entry_cache)
	  entry->set(); /* bad */

    -------------------------------------------------------------

Quoted 6 lines

"invalidate_entries()" may be any operation that deletes an entry at run-time (doesn't exist today), or as the guest is shutting down. As far as I can tell, the current code does not protect us from either condition, and my proposed patch protects us from both. Did I miss anything?

Yes. What happened to irq_rt is completely irrelevant at the point you marked /* bad */.

Quoted 55 lines · Gleb Natapov

Quoted 54 lines · Gregory Haskins

Quoted 21 lines · Gregory Haskins

Quoted 20 lines · Gleb Natapov

Quoted 19 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

   irq_rt->entry->set(); /* bad */

This is not what happens. irq_rt is never accessed outside read-side critical section.

Sorry, I was generalizing to keep the comments short. I figured it would be clear what I was actually saying, but realize in retrospect that I was a little ambiguous.

Here is a revised problem statement

    thread-1                                    thread-2
    -----------------------------------------------------------

    kvm_set_irq() {
       rcu_read_lock()
       irq_rt = rcu_dereference(table);
       entry_cache = get_entries(irq_rt);
       rcu_read_unlock();

                                            invalidate_entries(irq_rt);

       for_each_entry(entry_cache)
	  entry->set(); /* bad */

    -------------------------------------------------------------

"invalidate_entries()" may be any operation that deletes an entry at run-time (doesn't exist today), or as the guest is shutting down. As far as I can tell, the current code does not protect us from either condition, and my proposed patch protects us from both. Did I miss anything?

Quoted 2 lines

Yes. What happened to irq_rt is completely irrelevant at the point you marked /* bad */.

kfree() happened to irq_rt, and thus to the objects behind the pointers in entry_cache at the point I marked /* bad */.

That certainly isn't /* good */ ;)

Quoted 56 lines · Gregory Haskins

Quoted 55 lines · Gleb Natapov

Quoted 54 lines · Gregory Haskins

Quoted 21 lines · Gregory Haskins

Quoted 20 lines · Gleb Natapov

Quoted 19 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

Quoted 7 lines

Quoted 4 lines

Quoted 2 lines

   irq_rt->entry->set(); /* bad */

This is not what happens. irq_rt is never accessed outside read-side critical section.

Sorry, I was generalizing to keep the comments short. I figured it would be clear what I was actually saying, but realize in retrospect that I was a little ambiguous.

Here is a revised problem statement

    thread-1                                    thread-2
    -----------------------------------------------------------

    kvm_set_irq() {
       rcu_read_lock()
       irq_rt = rcu_dereference(table);
       entry_cache = get_entries(irq_rt);
       rcu_read_unlock();

                                            invalidate_entries(irq_rt);

       for_each_entry(entry_cache)
	  entry->set(); /* bad */

    -------------------------------------------------------------

"invalidate_entries()" may be any operation that deletes an entry at run-time (doesn't exist today), or as the guest is shutting down. As far as I can tell, the current code does not protect us from either condition, and my proposed patch protects us from both. Did I miss anything?

Quoted 4 lines

Quoted 2 lines

Yes. What happened to irq_rt is completely irrelevant at the point you marked /* bad */.

kfree() happened to irq_rt, and thus to the objects behind the pointers in entry_cache at the point I marked /* bad */.

The entire entry is cached not a pointer to an entry! kfree().

Quoted 20 lines · Gleb Natapov

Quoted 19 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

Quoted 4 lines

Quoted 2 lines

   irq_rt->entry->set(); /* bad */

This is not what happens. irq_rt is never accessed outside read-side critical section.

Sorry, I was generalizing to keep the comments short. I figured it would be clear what I was actually saying, but realize in retrospect that I was a little ambiguous.

Yes, irq_rt is not accessed outside the RSCS. However, the entry pointers stored in the irq_rt->map are, and this is equally problematic afaict.

In this particular case we seem to never delete entries at run-time once they are established. Therefore, while perhaps sloppy, its technically safe to leave them unprotected from this perspective. The issue is more related to shutdown since a kvm_set_irq() caller could be within the aforementioned race-region and call entry->set() after the guest is gone. Or did I miss something?

Quoted 2 lines

Data is copied from irq_rt onto the stack and this copy is accessed outside critical section.

As mentioned above, I do not believe this really protect us. And even

if it did, the copy is just a work-around to avoid sleeping within the

standard RCU RSCS, which is what SRCU is designed for. So rather than inventing an awkward two-phased stack based solution, it's better to reuse the provided tools, IMO.

To flip it around: Is there any reason why an SRCU would not work here, and thus we were forced to use something like the stack-copy approach?

Quoted 23 lines · Gregory Haskins

Quoted 22 lines · Gleb Natapov

Quoted 21 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

   irq_rt->entry->set(); /* bad */

Quoted 6 lines

Quoted 2 lines

This is not what happens. irq_rt is never accessed outside read-side critical section.

Sorry, I was generalizing to keep the comments short. I figured it would be clear what I was actually saying, but realize in retrospect that I was a little ambiguous.

A little is underestimation :) There is not /* bad */ line in the code!

Quoted 4 lines

Yes, irq_rt is not accessed outside the RSCS. However, the entry pointers stored in the irq_rt->map are, and this is equally problematic afaict.

The pointer is in text and can't disappear without kvm_set_irq() disappearing too.

Quoted 4 lines

In this particular case we seem to never delete entries at run-time once they are established. Therefore, while perhaps sloppy, its technically safe to leave them unprotected from this perspective.

Quoted 5 lines

The issue is more
related to shutdown since a kvm_set_irq() caller could be within the aforementioned race-region and call entry->set() after the guest is gone. Or did I miss something?

The caller of kvm_set_irq() should hold reference to kvm instance, so it can't disappear while you are inside kvm_set_irq(). RCU protects only kvm->irq_routing not kvm structure itself.

Quoted 4 lines

Quoted 3 lines

Data is copied from irq_rt onto the stack and this copy is accessed outside critical section.

As mentioned above, I do not believe this really protect us. And even

I don't see the prove it doesn't, so I assume it does.

Quoted 2 lines

if it did, the copy is just a work-around to avoid sleeping within the

It is not a work-around. There was two solutions to the problem one is to call ->set() outside rcu critical section

another is to use SRCU. I
decided to use the first one. This way the code is much simpler

and I remember asking Paul what are the disadvantages of using SRCU and there was something.

Quoted 7 lines

standard RCU RSCS, which is what SRCU is designed for. So rather than inventing an awkward two-phased stack based solution, it's better to reuse the provided tools, IMO.

To flip it around: Is there any reason why an SRCU would not work here, and thus we were forced to use something like the stack-copy approach?

If SRCU has no disadvantage comparing to RCU why not use it always? :)

Quoted 24 lines · Gleb Natapov

Quoted 23 lines · Gregory Haskins

Quoted 22 lines · Gleb Natapov

Quoted 21 lines · Gregory Haskins

The current code suffers from the following race condition:

thread-1 thread-2
-----------------------------------------------------------

kvm_set_irq() {
   rcu_read_lock()
   irq_rt = rcu_dereference(table);
   rcu_read_unlock();

                                       kvm_set_irq_routing() {
                                          mutex_lock();
                                          irq_rt = table;
                                          rcu_assign_pointer();
                                          mutex_unlock();
                                          synchronize_rcu();

                                          kfree(irq_rt);

   irq_rt->entry->set(); /* bad */

Quoted 7 lines

Quoted 6 lines

Quoted 2 lines

This is not what happens. irq_rt is never accessed outside read-side critical section.

Sorry, I was generalizing to keep the comments short. I figured it would be clear what I was actually saying, but realize in retrospect that I was a little ambiguous.

A little is underestimation :) There is not /* bad */ line in the code!

Sorry, that was my own highlighting, not trying to reflect actual code.

Quoted 6 lines

Quoted 4 lines

Yes, irq_rt is not accessed outside the RSCS. However, the entry pointers stored in the irq_rt->map are, and this is equally problematic afaict.

The pointer is in text and can't disappear without kvm_set_irq() disappearing too.

No, the entry* pointer is .text _AND_ .data, and is subject to standard synchronization rules like most other objects.

Unless I am misreading the code, the entry* pointers point to heap within the irq_rt pointer. Therefore, the "kfree(irq_rt)" I mention above effectively invalidates the entire set of entry* pointers that you are caching, and is thus an issue.

Quoted 4 lines

Quoted 4 lines

In this particular case we seem to never delete entries at run-time once they are established. Therefore, while perhaps sloppy, its technically safe to leave them unprotected from this perspective.

Note: I was wrong in this statement. I forgot that it's not safe at run-time either since the entry objects are part of irq_rt.

Quoted 5 lines

Quoted 5 lines

The issue is more
related to shutdown since a kvm_set_irq() caller could be within the aforementioned race-region and call entry->set() after the guest is gone. Or did I miss something?

Quoted 3 lines

The caller of kvm_set_irq() should hold reference to kvm instance, so it can't disappear while you are inside kvm_set_irq(). RCU protects only kvm->irq_routing not kvm structure itself.

Agreed, but this has nothing to do with protecting the entry* pointers.

Quoted 5 lines

Quoted 4 lines

Quoted 3 lines

Data is copied from irq_rt onto the stack and this copy is accessed outside critical section.

As mentioned above, I do not believe this really protect us. And even

I don't see the prove it doesn't, so I assume it does.

What would you like to see beyond what I've already provided you? I can show how the entry pointers are allocated as part of the irq_rt, and I can show how the irq_rt (via entry->set) access is racy against invalidation.

Quoted 4 lines

Quoted 2 lines

if it did, the copy is just a work-around to avoid sleeping within the

It is not a work-around. There was two solutions to the problem one is to call ->set() outside rcu critical section

This is broken afaict without taking additional precautions, such as a reference count on the irq_rt structure, but I mentioned this alternate solution in my header.

Quoted 2 lines

another is to use SRCU. I
decided to use the first one. This way the code is much simpler

"simpler" is debatable, but ok. SRCU is an established pattern available in the upstream kernel, so I don't think its particularly complicated or controversial to use.

Quoted 3 lines

and I remember asking Paul what are the disadvantages of using SRCU and there was something.

The disadvantages to my knowledge are as follows:

1) rcu_read_lock is something like 4x faster than srcu_read_lock(), but we are talking about nanoseconds on modern hardware (I think Paul quoted me 10ns vs 45ns on his rig). I don't think either overhead is something to be concerned about in this case.

2) standard rcu supports deferred synchronization (call_rcu()), as well as barriers (synchronize_rcu()), whereas SRCU only supports barriers (synchronize_srcu()). We only use the barrier type in this code path, so that is not an issue.

3) SRCU requires explicit initialization/cleanup, whereas regular RCU does not. Trivially solved in my patch since KVM has plenty of init/cleanup hook points.

Quoted 8 lines

Quoted 7 lines

standard RCU RSCS, which is what SRCU is designed for. So rather than inventing an awkward two-phased stack based solution, it's better to reuse the provided tools, IMO.

To flip it around: Is there any reason why an SRCU would not work here, and thus we were forced to use something like the stack-copy approach?

If SRCU has no disadvantage comparing to RCU why not use it always? :)

No one is debating that SRCU has some disadvantages to RCU, but it should also be noted that RCU has disadvantages as well (for instance, you can't sleep within the RSCS except for preemptible-based configurations)

The differences between them is really not the issue. The bottom line is that upstream KVM irq_routing code is broken afaict with the application of RCU alone.

IMO: Its not the tool for the job: At least, not when used alone. You either need RCU + reference count (which has more overhead than SRCU due to the atomic ops), or SRCU. There may perhaps be other variations on this theme, as well, and I am not married to SRCU as the solution, per se. But it is *a* solution that I believe works, and IMO its the best/cleanest/simplest one at our disposal.

Quoted 6 lines

1) rcu_read_lock is something like 4x faster than srcu_read_lock(), but we are talking about nanoseconds on modern hardware (I think Paul quoted me 10ns vs 45ns on his rig). I don't think either overhead is something to be concerned about in this case.

If we can avoid why not? Nanoseconds tend to add up.

On Tue, Oct 27, 2009 at 09:39:03AM -0400, Gregory Haskins wrote:

Quoted 7 lines

standard RCU RSCS, which is what SRCU is designed for. So rather than inventing an awkward two-phased stack based solution, it's better to reuse the provided tools, IMO.

To flip it around: Is there any reason why an SRCU would not work here, and thus we were forced to use something like the stack-copy approach?

If SRCU has no disadvantage comparing to RCU why not use it always? :)

Quoted 1 line · Gleb Natapov

On Tue, Oct 27, 2009 at 09:39:03AM -0400, Gregory Haskins wrote:

[ . . . ]

Quoted 7 lines

Quoted 7 lines

standard RCU RSCS, which is what SRCU is designed for. So rather than inventing an awkward two-phased stack based solution, it's better to reuse the provided tools, IMO.

To flip it around: Is there any reason why an SRCU would not work here, and thus we were forced to use something like the stack-copy approach?

Quoted 1 line

If SRCU has no disadvantage comparing to RCU why not use it always? :)

The disadvantages of SRCU compared to RCU include the following:

1. SRCU requires that the return value of srcu_read_lock()
be fed into srcu_read_unlock(). This is usually not a problem, but can be painful if there are multiple levels of function call separating the two.

2. SRCU's grace periods are about 4x slower than those of RCU.
And they also don't scale all that well with extremely large numbers of CPUs (but this can be fixed when/if it becomes a real problem).

3. SRCU's read-side primitives are also significantly slower than
those of RCU.

4. SRCU does not have a call_srcu(). One could be provided, but
its semantics would be a bit strange due to the need to limit the number of callbacks, given that general blocking is permitted in SRCU read-side critical sections. (And it would take some doing to convince me to supply an SRCU!)

5. The current SRCU has no reasonable way to implement read-side
priority boosting, as there is no record of which task is read-holding which SRCU.

Thanks for this, Paul.

Some questions and statements below.

Quoted 16 lines · Paul E. McKenney

Quoted 1 line · Gleb Natapov

On Tue, Oct 27, 2009 at 09:39:03AM -0400, Gregory Haskins wrote:

[ . . . ]

Quoted 8 lines

Quoted 7 lines

standard RCU RSCS, which is what SRCU is designed for. So rather than inventing an awkward two-phased stack based solution, it's better to reuse the provided tools, IMO.

To flip it around: Is there any reason why an SRCU would not work here, and thus we were forced to use something like the stack-copy approach?

If SRCU has no disadvantage comparing to RCU why not use it always? :)

The disadvantages of SRCU compared to RCU include the following:

Quoted 4 lines

1. SRCU requires that the return value of srcu_read_lock()
be fed into srcu_read_unlock(). This is usually not a problem, but can be painful if there are multiple levels of function call separating the two.

Right, and this is simple/neat w.r.t. its usage in irq_routing, so no problem there.

Quoted 5 lines

2. SRCU's grace periods are about 4x slower than those of RCU.
And they also don't scale all that well with extremely large numbers of CPUs (but this can be fixed when/if it becomes a real problem).

The irq_routing update path is extremely infrequent, so this should not be an issue.

Quoted 2 lines

3. SRCU's read-side primitives are also significantly slower than
those of RCU.

Are the 10ns vs 45ns numbers that I mentioned in my last reply the proper ballpark? How do these compare to an atomic-op, say an uncontended spinlock on modern hardware? The assumption is that srcu_read_lock() should be significantly cheaper than a read-lock(). If its not, then we might as well use something else, I suppose. But if its not, I guess you probably wouldn't have bothered to invent it in the first place ;)

Quoted 5 lines

4. SRCU does not have a call_srcu(). One could be provided, but
its semantics would be a bit strange due to the need to limit the number of callbacks, given that general blocking is permitted in SRCU read-side critical sections. (And it would take some doing to convince me to supply an SRCU!)

This is not an issue in our design.

Quoted 3 lines

5. The current SRCU has no reasonable way to implement read-side
priority boosting, as there is no record of which task is read-holding which SRCU.

Given the infrequency of the update path, I do not see this as a problem.

Certain GSI's support lockless injecton, but we have no way to detect which ones at the GSI level. Knowledge of this attribute will be useful later in the series so that we can optimize irqfd injection paths for cases where we know the code will not sleep. Therefore, we provide an API to query a specific GSI.

Signed-off-by Gregory Haskins <[email protected]>

---

 include/linux/kvm_host.h |    2 ++
 virt/kvm/irq_comm.c      |   35 ++++++++++++++++++++++++++++++++++-
 2 files changed, 36 insertions(+), 1 deletions(-)

include/linux/kvm_host.h +0 -0

index 1fe135d..01151a6 100644

include/linux/kvm_host.h +1 -0

 	int (*set)(struct kvm_kernel_irq_routing_entry *e,
 		   struct kvm *kvm, int irq_source_id, int level);
 	union {

@@ -420,6 +421,7 @@ void kvm_get_intr_delivery_bitmask(struct kvm_ioapic *ioapic,
 				   unsigned long *deliver_bitmask);
 #endif
 int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level);
+int kvm_irq_check_lockless(struct kvm *kvm, u32 irq);
 void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin);
 void kvm_register_irq_ack_notifier(struct kvm *kvm,
 				   struct kvm_irq_ack_notifier *kian);

virt/kvm/irq_comm.c +29 -0

index db2553f..a7fd487 100644
@@ -173,6 +173,35 @@ int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level)
 	return ret;
 }
 
+int kvm_irq_check_lockless(struct kvm *kvm, u32 irq)
+{
+	struct kvm_kernel_irq_routing_entry *e;
+	struct kvm_irq_routing_table *irq_rt;
+	struct hlist_node *n;
+	int ret = -ENOENT;
+	int idx;
+
+	idx = srcu_read_lock(&kvm->irq_routing.srcu);
+	irq_rt = rcu_dereference(kvm->irq_routing.table);
+	if (irq < irq_rt->nr_rt_entries)
+		hlist_for_each_entry(e, n, &irq_rt->map[irq], link) {
+			if (!e->lockless) {
+				/*
+				 * all destinations need to be lockless to
+				 * declare that the GSI as a whole is also
+				 * lockless
+				 */
+				ret = 0;
+				break;
+			}
+
+			ret = 1;
+		}
+	srcu_read_unlock(&kvm->irq_routing.srcu, idx);
+
+	return ret;
+}
+
 void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin)
 {
 	struct kvm_irq_ack_notifier *kian;

virt/kvm/irq_comm.c +1 -1

 			return r;
 
 	e->gsi = ue->gsi;
 	e->type = ue->type;
+	e->lockless = lockless;
 	switch (ue->type) {
 	case KVM_IRQ_ROUTING_IRQCHIP:
 		delta = 0;
 
--

To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 13 lines · Gregory Haskins

Certain GSI's support lockless injecton, but we have no way to detect which ones at the GSI level. Knowledge of this attribute will be useful later in the series so that we can optimize irqfd injection paths for cases where we know the code will not sleep. Therefore, we provide an API to query a specific GSI.

Signed-off-by Gregory Haskins <[email protected]>

---

 include/linux/kvm_host.h |    2 ++
 virt/kvm/irq_comm.c      |   35 ++++++++++++++++++++++++++++++++++-
 2 files changed, 36 insertions(+), 1 deletions(-)

include/linux/kvm_host.h struct kvm_memory_slot { · line 122

Quoted 9 lines

include/linux/kvm_host.h +1 -0

index 1fe135d..01151a6 100644
@@ -119,6 +119,7 @@ struct kvm_memory_slot {
 struct kvm_kernel_irq_routing_entry {
 	u32 gsi;
 	u32 type;
+	bool lockless;

So lockless is the same as type == MSI from below?

If the idea is to make it extensible for the future, let's just add an inline function, we don't need a field for this.

Quoted 57 lines

include/linux/kvm_host.h +1 -0

 	int (*set)(struct kvm_kernel_irq_routing_entry *e,
 		   struct kvm *kvm, int irq_source_id, int level);
 	union {

@@ -420,6 +421,7 @@ void kvm_get_intr_delivery_bitmask(struct kvm_ioapic *ioapic,
 				   unsigned long *deliver_bitmask);
 #endif
 int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level);
+int kvm_irq_check_lockless(struct kvm *kvm, u32 irq);
 void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin);
 void kvm_register_irq_ack_notifier(struct kvm *kvm,
 				   struct kvm_irq_ack_notifier *kian);

virt/kvm/irq_comm.c +30 -0

index db2553f..a7fd487 100644
@@ -173,6 +173,35 @@ int kvm_set_irq(struct kvm *kvm, int irq_source_id, u32 irq, int level)
 	return ret;
 }
 
+int kvm_irq_check_lockless(struct kvm *kvm, u32 irq)
+{
+	struct kvm_kernel_irq_routing_entry *e;
+	struct kvm_irq_routing_table *irq_rt;
+	struct hlist_node *n;
+	int ret = -ENOENT;
+	int idx;
+
+	idx = srcu_read_lock(&kvm->irq_routing.srcu);
+	irq_rt = rcu_dereference(kvm->irq_routing.table);
+	if (irq < irq_rt->nr_rt_entries)
+		hlist_for_each_entry(e, n, &irq_rt->map[irq], link) {
+			if (!e->lockless) {
+				/*
+				 * all destinations need to be lockless to
+				 * declare that the GSI as a whole is also
+				 * lockless
+				 */
+				ret = 0;
+				break;
+			}
+
+			ret = 1;
+		}
+	srcu_read_unlock(&kvm->irq_routing.srcu, idx);
+
+	return ret;
+}
+
 void kvm_notify_acked_irq(struct kvm *kvm, unsigned irqchip, unsigned pin)
 {
 	struct kvm_irq_ack_notifier *kian;

@@ -310,18 +339,22 @@ static int setup_routing_entry(struct kvm_irq_routing_table *rt,
 	int delta;
 	struct kvm_kernel_irq_routing_entry *ei;
 	struct hlist_node *n;
+	bool lockless = ue->type == KVM_IRQ_ROUTING_MSI;
 

virt/kvm/irq_comm.c static int setup_routing_entry(struct kvm_irq_routing_table *rt, · line 347

Quoted 4 lines

virt/kvm/irq_comm.c +1 -0

 	/*
 	 * Do not allow GSI to be mapped to the same irqchip more than once.
 	 * Allow only one to one mapping between GSI and MSI.
+	 * Do not allow mixed lockless vs locked variants to coexist.

Userspace has no idea which entries are lockless and which are not:
this is an implementation detail - so it might not be able to avoid illegal combinations.
Since this is called on an ioctl, can the rule be formulated in a way that makes sense for userspace?

virt/kvm/irq_comm.c static int setup_routing_entry(struct kvm_irq_routing_table *rt, · line 352

Quoted 6 lines

virt/kvm/irq_comm.c +2 -1

 	 */
 	hlist_for_each_entry(ei, n, &rt->map[ue->gsi], link)
 		if (ei->type == KVM_IRQ_ROUTING_MSI ||
-		    ue->u.irqchip.irqchip == ei->irqchip.irqchip)
+		    ue->u.irqchip.irqchip == ei->irqchip.irqchip ||
+		    ei->lockless != lockless)

So this check seems like it does nothing, because lockless is same as MSI, and MSI is always 1:1? Intentional?

IRQFD currently uses a deferred workqueue item to execute the injection operation. It was originally designed this way because kvm_set_irq() required the caller to hold the irq_lock mutex, and the eventfd callback is invoked from within a non-preemptible critical section.

With the advent of lockless injection support for certain GSIs, the deferment mechanism is no longer technically needed in all cases. Since context switching to the workqueue is a source of interrupt latency, lets switch to a direct method whenever possible. Fortunately for us, the most common use of irqfd (MSI-based GSIs) readily support lockless injection.

Signed-off-by Gregory Haskins <[email protected]>

---

 virt/kvm/eventfd.c |   31 +++++++++++++++++++++++++++----
 1 files changed, 27 insertions(+), 4 deletions(-)

virt/kvm/eventfd.c +18 -4

index 30f70fd..e6cc958 100644
@@ -51,20 +51,34 @@ struct _irqfd {
 	wait_queue_t              wait;
 	struct work_struct        inject;
 	struct work_struct        shutdown;
+	void (*execute)(struct _irqfd *);
 };
 
 static struct workqueue_struct *irqfd_cleanup_wq;
 
 static void
-irqfd_inject(struct work_struct *work)
+irqfd_inject(struct _irqfd *irqfd)
 {
-	struct _irqfd *irqfd = container_of(work, struct _irqfd, inject);
 	struct kvm *kvm = irqfd->kvm;
 
 	kvm_set_irq(kvm, KVM_USERSPACE_IRQ_SOURCE_ID, irqfd->gsi, 1);
 	kvm_set_irq(kvm, KVM_USERSPACE_IRQ_SOURCE_ID, irqfd->gsi, 0);
 }
 
+static void
+irqfd_deferred_inject(struct work_struct *work)
+{
+	struct _irqfd *irqfd = container_of(work, struct _irqfd, inject);
+
+	irqfd_inject(irqfd);
+}
+
+static void
+irqfd_schedule(struct _irqfd *irqfd)
+{
+	schedule_work(&irqfd->inject);
+}
+
 /*
  * Race-free decouple logic (ordering is critical)
  */

@@ -126,7 +140,7 @@ irqfd_wakeup(wait_queue_t *wait, unsigned mode, int sync, void *key)
 
 	if (flags & POLLIN)
 		/* An event has been signaled, inject an interrupt */
-		schedule_work(&irqfd->inject);
+		irqfd->execute(irqfd);
 
 	if (flags & POLLHUP) {
 		/* The eventfd is closing, detach from KVM */

@@ -179,7 +193,7 @@ kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi)
 	irqfd->kvm = kvm;
 	irqfd->gsi = gsi;
 	INIT_LIST_HEAD(&irqfd->list);
-	INIT_WORK(&irqfd->inject, irqfd_inject);
+	INIT_WORK(&irqfd->inject, irqfd_deferred_inject);
 	INIT_WORK(&irqfd->shutdown, irqfd_shutdown);
 
 	file = eventfd_fget(fd);

@@ -209,6 +223,15 @@ kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi)
 	list_add_tail(&irqfd->list, &kvm->irqfds.items);
 	spin_unlock_irq(&kvm->irqfds.lock);

virt/kvm/eventfd.c +0 -1

 	/*
 	 * Check if there was an event already pending on the eventfd
 	 * before we registered, and trigger it as if we didn't miss it.
 
--

To unsubscribe from this list: send the line "unsubscribe kvm" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 5 lines · Gregory Haskins

IRQFD currently uses a deferred workqueue item to execute the injection operation. It was originally designed this way because kvm_set_irq() required the caller to hold the irq_lock mutex, and the eventfd callback is invoked from within a non-preemptible critical section.

Quoted 8 lines

With the advent of lockless injection support for certain GSIs, the deferment mechanism is no longer technically needed in all cases. Since context switching to the workqueue is a source of interrupt latency, lets switch to a direct method whenever possible. Fortunately for us, the most common use of irqfd (MSI-based GSIs) readily support lockless injection.

Signed-off-by Gregory Haskins <[email protected]>

This is a useful optimization I think.
Some comments below.

Quoted 68 lines

---

 virt/kvm/eventfd.c |   31 +++++++++++++++++++++++++++----
 1 files changed, 27 insertions(+), 4 deletions(-)

virt/kvm/eventfd.c +18 -4

index 30f70fd..e6cc958 100644
@@ -51,20 +51,34 @@ struct _irqfd {
 	wait_queue_t              wait;
 	struct work_struct        inject;
 	struct work_struct        shutdown;
+	void (*execute)(struct _irqfd *);
 };
 
 static struct workqueue_struct *irqfd_cleanup_wq;
 
 static void
-irqfd_inject(struct work_struct *work)
+irqfd_inject(struct _irqfd *irqfd)
 {
-	struct _irqfd *irqfd = container_of(work, struct _irqfd, inject);
 	struct kvm *kvm = irqfd->kvm;
 
 	kvm_set_irq(kvm, KVM_USERSPACE_IRQ_SOURCE_ID, irqfd->gsi, 1);
 	kvm_set_irq(kvm, KVM_USERSPACE_IRQ_SOURCE_ID, irqfd->gsi, 0);
 }
 
+static void
+irqfd_deferred_inject(struct work_struct *work)
+{
+	struct _irqfd *irqfd = container_of(work, struct _irqfd, inject);
+
+	irqfd_inject(irqfd);
+}
+
+static void
+irqfd_schedule(struct _irqfd *irqfd)
+{
+	schedule_work(&irqfd->inject);
+}
+
 /*
  * Race-free decouple logic (ordering is critical)
  */

@@ -126,7 +140,7 @@ irqfd_wakeup(wait_queue_t *wait, unsigned mode, int sync, void *key)
 
 	if (flags & POLLIN)
 		/* An event has been signaled, inject an interrupt */
-		schedule_work(&irqfd->inject);
+		irqfd->execute(irqfd);
 
 	if (flags & POLLHUP) {
 		/* The eventfd is closing, detach from KVM */

@@ -179,7 +193,7 @@ kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi)
 	irqfd->kvm = kvm;
 	irqfd->gsi = gsi;
 	INIT_LIST_HEAD(&irqfd->list);
-	INIT_WORK(&irqfd->inject, irqfd_inject);
+	INIT_WORK(&irqfd->inject, irqfd_deferred_inject);
 	INIT_WORK(&irqfd->shutdown, irqfd_shutdown);
 
 	file = eventfd_fget(fd);

@@ -209,6 +223,15 @@ kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi)
 	list_add_tail(&irqfd->list, &kvm->irqfds.items);
 	spin_unlock_irq(&kvm->irqfds.lock);
 

virt/kvm/eventfd.c kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi) · line 234

Quoted 9 lines

virt/kvm/eventfd.c +9 -0

+	ret = kvm_irq_check_lockless(kvm, gsi);
+	if (ret < 0)
+		goto fail;
+
+	if (ret)
+		irqfd->execute = &irqfd_inject;
+	else
+		irqfd->execute = &irqfd_schedule;
+

Can't gsi get converted from lockless to non-lockless after it's checked (by the routing ioctl)?

Kernel will crash then.

How about, each time we get event from eventfd, we implement kvm_irqfd_toggle_lockless, which does a single scan, and returns true/false status (and I really mean toggle, let's not do set 1 / set 0 as well) telling us whether interrupts could be delivered in a lockless manner?

Quoted 86 lines · Michael S. Tsirkin

Quoted 5 lines · Gregory Haskins

IRQFD currently uses a deferred workqueue item to execute the injection operation. It was originally designed this way because kvm_set_irq() required the caller to hold the irq_lock mutex, and the eventfd callback is invoked from within a non-preemptible critical section.

Quoted 8 lines

With the advent of lockless injection support for certain GSIs, the deferment mechanism is no longer technically needed in all cases. Since context switching to the workqueue is a source of interrupt latency, lets switch to a direct method whenever possible. Fortunately for us, the most common use of irqfd (MSI-based GSIs) readily support lockless injection.

Signed-off-by Gregory Haskins <[email protected]>

This is a useful optimization I think.
Some comments below.

Quoted 68 lines

---

 virt/kvm/eventfd.c |   31 +++++++++++++++++++++++++++----
 1 files changed, 27 insertions(+), 4 deletions(-)

virt/kvm/eventfd.c +18 -4

index 30f70fd..e6cc958 100644
@@ -51,20 +51,34 @@ struct _irqfd {
 	wait_queue_t              wait;
 	struct work_struct        inject;
 	struct work_struct        shutdown;
+	void (*execute)(struct _irqfd *);
 };
 
 static struct workqueue_struct *irqfd_cleanup_wq;
 
 static void
-irqfd_inject(struct work_struct *work)
+irqfd_inject(struct _irqfd *irqfd)
 {
-	struct _irqfd *irqfd = container_of(work, struct _irqfd, inject);
 	struct kvm *kvm = irqfd->kvm;
 
 	kvm_set_irq(kvm, KVM_USERSPACE_IRQ_SOURCE_ID, irqfd->gsi, 1);
 	kvm_set_irq(kvm, KVM_USERSPACE_IRQ_SOURCE_ID, irqfd->gsi, 0);
 }
 
+static void
+irqfd_deferred_inject(struct work_struct *work)
+{
+	struct _irqfd *irqfd = container_of(work, struct _irqfd, inject);
+
+	irqfd_inject(irqfd);
+}
+
+static void
+irqfd_schedule(struct _irqfd *irqfd)
+{
+	schedule_work(&irqfd->inject);
+}
+
 /*
  * Race-free decouple logic (ordering is critical)
  */

@@ -126,7 +140,7 @@ irqfd_wakeup(wait_queue_t *wait, unsigned mode, int sync, void *key)
 
 	if (flags & POLLIN)
 		/* An event has been signaled, inject an interrupt */
-		schedule_work(&irqfd->inject);
+		irqfd->execute(irqfd);
 
 	if (flags & POLLHUP) {
 		/* The eventfd is closing, detach from KVM */

@@ -179,7 +193,7 @@ kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi)
 	irqfd->kvm = kvm;
 	irqfd->gsi = gsi;
 	INIT_LIST_HEAD(&irqfd->list);
-	INIT_WORK(&irqfd->inject, irqfd_inject);
+	INIT_WORK(&irqfd->inject, irqfd_deferred_inject);
 	INIT_WORK(&irqfd->shutdown, irqfd_shutdown);
 
 	file = eventfd_fget(fd);

@@ -209,6 +223,15 @@ kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi)
 	list_add_tail(&irqfd->list, &kvm->irqfds.items);
 	spin_unlock_irq(&kvm->irqfds.lock);
 

Quoted 12 lines

virt/kvm/eventfd.c kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi) · line 234

Quoted 9 lines

virt/kvm/eventfd.c +9 -0

+	ret = kvm_irq_check_lockless(kvm, gsi);
+	if (ret < 0)
+		goto fail;
+
+	if (ret)
+		irqfd->execute = &irqfd_inject;
+	else
+		irqfd->execute = &irqfd_schedule;
+

Can't gsi get converted from lockless to non-lockless after it's checked (by the routing ioctl)?

I think I protect against this in patch 2/3 by ensuring that any vectors that are added have to conform to the same locking rules. The code doesn't support deleting routes, so we really only need to make sure that new routes do not change.

Quoted 7 lines

Kernel will crash then.

How about, each time we get event from eventfd, we implement kvm_irqfd_toggle_lockless, which does a single scan, and returns true/false status (and I really mean toggle, let's not do set 1 / set 0 as well) telling us whether interrupts could be delivered in a lockless manner?

I am not sure I like this idea in general given that I believe I already handle the error case you are concerned with.

However, the concept of providing a "toggle" option so we can avoid scanning the list twice is a good one. That can be done as a new patch series, but it would be a nice addition.

Thanks Michael,
-Greg

Quoted 97 lines · Gregory Haskins

Quoted 85 lines · Michael S. Tsirkin

Quoted 5 lines · Gregory Haskins

IRQFD currently uses a deferred workqueue item to execute the injection operation. It was originally designed this way because kvm_set_irq() required the caller to hold the irq_lock mutex, and the eventfd callback is invoked from within a non-preemptible critical section.

Quoted 8 lines

With the advent of lockless injection support for certain GSIs, the deferment mechanism is no longer technically needed in all cases. Since context switching to the workqueue is a source of interrupt latency, lets switch to a direct method whenever possible. Fortunately for us, the most common use of irqfd (MSI-based GSIs) readily support lockless injection.

Signed-off-by Gregory Haskins <[email protected]>

This is a useful optimization I think.
Some comments below.

Quoted 68 lines

---

 virt/kvm/eventfd.c |   31 +++++++++++++++++++++++++++----
 1 files changed, 27 insertions(+), 4 deletions(-)

virt/kvm/eventfd.c +18 -4

index 30f70fd..e6cc958 100644
@@ -51,20 +51,34 @@ struct _irqfd {
 	wait_queue_t              wait;
 	struct work_struct        inject;
 	struct work_struct        shutdown;
+	void (*execute)(struct _irqfd *);
 };
 
 static struct workqueue_struct *irqfd_cleanup_wq;
 
 static void
-irqfd_inject(struct work_struct *work)
+irqfd_inject(struct _irqfd *irqfd)
 {
-	struct _irqfd *irqfd = container_of(work, struct _irqfd, inject);
 	struct kvm *kvm = irqfd->kvm;
 
 	kvm_set_irq(kvm, KVM_USERSPACE_IRQ_SOURCE_ID, irqfd->gsi, 1);
 	kvm_set_irq(kvm, KVM_USERSPACE_IRQ_SOURCE_ID, irqfd->gsi, 0);
 }
 
+static void
+irqfd_deferred_inject(struct work_struct *work)
+{
+	struct _irqfd *irqfd = container_of(work, struct _irqfd, inject);
+
+	irqfd_inject(irqfd);
+}
+
+static void
+irqfd_schedule(struct _irqfd *irqfd)
+{
+	schedule_work(&irqfd->inject);
+}
+
 /*
  * Race-free decouple logic (ordering is critical)
  */

@@ -126,7 +140,7 @@ irqfd_wakeup(wait_queue_t *wait, unsigned mode, int sync, void *key)
 
 	if (flags & POLLIN)
 		/* An event has been signaled, inject an interrupt */
-		schedule_work(&irqfd->inject);
+		irqfd->execute(irqfd);
 
 	if (flags & POLLHUP) {
 		/* The eventfd is closing, detach from KVM */

@@ -179,7 +193,7 @@ kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi)
 	irqfd->kvm = kvm;
 	irqfd->gsi = gsi;
 	INIT_LIST_HEAD(&irqfd->list);
-	INIT_WORK(&irqfd->inject, irqfd_inject);
+	INIT_WORK(&irqfd->inject, irqfd_deferred_inject);
 	INIT_WORK(&irqfd->shutdown, irqfd_shutdown);
 
 	file = eventfd_fget(fd);

@@ -209,6 +223,15 @@ kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi)
 	list_add_tail(&irqfd->list, &kvm->irqfds.items);
 	spin_unlock_irq(&kvm->irqfds.lock);
 

Quoted 11 lines

virt/kvm/eventfd.c kvm_irqfd_assign(struct kvm *kvm, int fd, int gsi) · line 234

Quoted 9 lines

virt/kvm/eventfd.c +9 -0

+	ret = kvm_irq_check_lockless(kvm, gsi);
+	if (ret < 0)
+		goto fail;
+
+	if (ret)
+		irqfd->execute = &irqfd_inject;
+	else
+		irqfd->execute = &irqfd_schedule;
+

Can't gsi get converted from lockless to non-lockless after it's checked (by the routing ioctl)?

Quoted 4 lines

I think I protect against this in patch 2/3 by ensuring that any vectors that are added have to conform to the same locking rules. The code doesn't support deleting routes, so we really only need to make sure that new routes do not change.

What I refer to, is when userspace calls KVM_SET_GSI_ROUTING.
I don't see how your patch helps here: can't a GSI formerly
used for MSI become unused, and then reused for non-MSI?
If not, it's a problem I think, because I think userspace currently does this sometimes.

Quoted 18 lines

Quoted 8 lines

Kernel will crash then.

How about, each time we get event from eventfd, we implement kvm_irqfd_toggle_lockless, which does a single scan, and returns true/false status (and I really mean toggle, let's not do set 1 / set 0 as well) telling us whether interrupts could be delivered in a lockless manner?

I am not sure I like this idea in general given that I believe I already handle the error case you are concerned with.

However, the concept of providing a "toggle" option so we can avoid scanning the list twice is a good one. That can be done as a new patch series, but it would be a nice addition.

Thanks Michael,
-Greg