KVM: optimize apic interrupt delivery

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.

arch/x86/kvm/lapic.c +8 -0

+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);

arch/x86/kvm/lapic.c +19 -0

+
+static inline void recalculate_apic_map(struct kvm *kvm)
+{
+	struct kvm_apic_map *new, *old = NULL;
+	struct kvm_vcpu *vcpu;
+	int i;
+
+	new = kzalloc(sizeof(struct kvm_apic_map), GFP_KERNEL);
+
+	mutex_lock(&kvm->arch.apic_map_lock);
+
+	if (!new)
+		goto out;
+
+	new->ldr_bits = 8;
+	new->flat = true;
+	kvm_for_each_vcpu(i, vcpu, kvm) {
+		u16 cid, lid;
+		struct kvm_lapic *apic = vcpu->arch.apic;

arch/x86/kvm/lapic.c +24 -0

+}
+
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r)
+{
+	struct kvm_apic_map *map;
+	unsigned long bitmap = 1;
+	struct kvm_lapic **dst;
+	int i;
+
+	*r = -1;
+
+	if (irq->shorthand == APIC_DEST_SELF) {
+		*r = kvm_apic_set_irq(src->vcpu, irq);
+		return true;
+	}
+
+	if (irq->shorthand)
+		return false;
+
+	rcu_read_lock();
+	map = rcu_dereference(kvm->arch.apic_map);
+
+	if (!map) {

arch/x86/kvm/lapic.c +34 -0

+
+		kvm_apic_get_logical_id(mda, map->flat, map->ldr_bits,
+				&cid, &lid);
+		dst = map->logical_map[cid];
+
+		bitmap = lid;
+		if (irq->delivery_mode == APIC_DM_LOWEST &&
+				hweight_long(bitmap) > 1) {
+			int l = -1;
+			for_each_set_bit(i, &bitmap, 16) {
+				if (!dst[i])
+					continue;
+				if (l < 0)
+					l = i;
+				else if (kvm_apic_compare_prio(dst[i]->vcpu, dst[l]->vcpu) < 0)
+					l = i;
+			}
+
+			bitmap = (l >= 0) ? 1 << l : 0;
+		}
+	}
+
+	for_each_set_bit(i, &bitmap, 16) {
+		if (!dst[i])
+			continue;
+		if (*r < 0)
+			*r = 0;
+		*r += kvm_apic_set_irq(dst[i]->vcpu, irq);
+	}
+
+	rcu_read_unlock();
+	return true;
+}
+
 /*

Quoted 8 lines · Gleb Natapov

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.

Agree.

Patch looks good but some minor comments follow.

arch/x86/include/asm/kvm_host.h struct kvm_arch { · line 540

Quoted 9 lines

struct kvm_arch {

arch/x86/include/asm/kvm_host.h +2 -0

 	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;

@@ -528,6 +536,8 @@ struct kvm_arch {
 	struct kvm_ioapic *vioapic;
 	struct kvm_pit *vpit;
 	int vapics_in_nmi_mode;
+	struct kvm_apic_map *apic_map;
+	struct mutex apic_map_lock;

Reversing the order will make it clearer what the lock protects.

Quoted 9 lines

arch/x86/kvm/lapic.c +8 -0

+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 169

Quoted 10 lines

arch/x86/kvm/lapic.c +10 -0

+
+		if (flat) {
+			*cid = 0;
+			*lid = ldr;
+		} else {
+			*cid = ldr >> 4;
+			*lid = ldr & 0xf;
+		}
+	}
+}

You could precaclulate lid_shift/lid_mask/cid_shift/cid_mask and have just one version here. In fact you could drop the function.

Quoted 19 lines

arch/x86/kvm/lapic.c +19 -0

+
+static inline void recalculate_apic_map(struct kvm *kvm)
+{
+	struct kvm_apic_map *new, *old = NULL;
+	struct kvm_vcpu *vcpu;
+	int i;
+
+	new = kzalloc(sizeof(struct kvm_apic_map), GFP_KERNEL);
+
+	mutex_lock(&kvm->arch.apic_map_lock);
+
+	if (!new)
+		goto out;
+
+	new->ldr_bits = 8;
+	new->flat = true;
+	kvm_for_each_vcpu(i, vcpu, kvm) {
+		u16 cid, lid;
+		struct kvm_lapic *apic = vcpu->arch.apic;

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 198

Quoted 10 lines

arch/x86/kvm/lapic.c +10 -0

+
+		if (!kvm_apic_present(vcpu))
+			continue;
+
+		if (apic_x2apic_mode(apic)) {
+			new->ldr_bits = 32;
+			new->flat = false;
+		} else if (kvm_apic_sw_enabled(apic) && new->flat &&
+				kvm_apic_get_reg(apic, APIC_DFR) == APIC_DFR_CLUSTER)
+			new->flat = false;

While a vcpu is being hotplugged in it will be in flat mode. The code correctly gives precedence to x2apic and cluster modes over flat mode, so it is correct in that respect, but the comment describing this is too short.

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 208

Quoted 10 lines

arch/x86/kvm/lapic.c +10 -0

+
+		new->phys_map[kvm_apic_id(apic)] = apic;
+		kvm_apic_get_logical_id(kvm_apic_get_reg(apic, APIC_LDR),
+				new->flat, new->ldr_bits, &cid, &lid);
+
+		if (lid)
+			new->logical_map[cid][ffs(lid) - 1] = apic;
+	}
+out:
+	old = kvm->arch.apic_map;

rcu_dereference(), just for kicks.

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 213

Quoted 5 lines

arch/x86/kvm/lapic.c +5 -0

+	rcu_assign_pointer(kvm->arch.apic_map, new);
+	mutex_unlock(&kvm->arch.apic_map_lock);
+
+	if (old)
+		kfree_rcu(old, rcu);

Nice, removes the need for rcu_barrier().

Quoted 30 lines

arch/x86/kvm/lapic.c +29 -0

+}
+
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r)
+{
+	struct kvm_apic_map *map;
+	unsigned long bitmap = 1;
+	struct kvm_lapic **dst;
+	int i;
+
+	*r = -1;
+
+	if (irq->shorthand == APIC_DEST_SELF) {
+		*r = kvm_apic_set_irq(src->vcpu, irq);
+		return true;
+	}
+
+	if (irq->shorthand)
+		return false;
+
+	rcu_read_lock();
+	map = rcu_dereference(kvm->arch.apic_map);
+
+	if (!map) {
+		rcu_read_unlock();
+		return false;
+	}
+
+	if (irq->dest_mode == 0) { /* physical mode */

arch/x86/kvm/lapic.c int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source, · line 587

Quoted 5 lines

arch/x86/kvm/lapic.c +5 -0

+		if (irq->delivery_mode == APIC_DM_LOWEST ||
+				irq->dest_id == 0xff) {
+			rcu_read_unlock();
+			return false;
+		}

Two error paths with rcu_read_unlock(). Cleaner to have a bool ret = false; in the beginning and 'goto out_unlock' here, IMO.

arch/x86/kvm/lapic.c int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source, · line 594

Quoted 8 lines

arch/x86/kvm/lapic.c +7 -0

+		dst = &map->phys_map[irq->dest_id & 0xff];
+	} else {
+		u16 cid, lid;
+		u32 mda = irq->dest_id;
+
+		if (map->ldr_bits == 8)
+			mda <<= 24;

mda <<= 32 - map->ldr_bits;

Quoted 35 lines

arch/x86/kvm/lapic.c +34 -0

+
+		kvm_apic_get_logical_id(mda, map->flat, map->ldr_bits,
+				&cid, &lid);
+		dst = map->logical_map[cid];
+
+		bitmap = lid;
+		if (irq->delivery_mode == APIC_DM_LOWEST &&
+				hweight_long(bitmap) > 1) {
+			int l = -1;
+			for_each_set_bit(i, &bitmap, 16) {
+				if (!dst[i])
+					continue;
+				if (l < 0)
+					l = i;
+				else if (kvm_apic_compare_prio(dst[i]->vcpu, dst[l]->vcpu) < 0)
+					l = i;
+			}
+
+			bitmap = (l >= 0) ? 1 << l : 0;
+		}
+	}
+
+	for_each_set_bit(i, &bitmap, 16) {
+		if (!dst[i])
+			continue;
+		if (*r < 0)
+			*r = 0;
+		*r += kvm_apic_set_irq(dst[i]->vcpu, irq);
+	}
+
+	rcu_read_unlock();
+	return true;
+}
+
 /*

arch/x86/kvm/x86.c void kvm_arch_destroy_vm(struct kvm *kvm) · line 6323

Quoted 5 lines

arch/x86/kvm/x86.c +1 -0

@@ -6319,6 +6320,7 @@ void kvm_arch_destroy_vm(struct kvm *kvm)
 		put_page(kvm->arch.apic_access_page);
 	if (kvm->arch.ept_identity_pagetable)
 		put_page(kvm->arch.ept_identity_pagetable);
+	kfree(kvm->arch.apic_map);

rcu_dereference(), even though it cannot be needed here, to shut down static code checkers.

Signature · 2 lines

-- 
error compiling committee.c: too many arguments to function

Quoted 8 lines · Gleb Natapov

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.

Agree.

Patch looks good but some minor comments follow.

arch/x86/include/asm/kvm_host.h struct kvm_arch { · line 540

Quoted 9 lines

struct kvm_arch {

arch/x86/include/asm/kvm_host.h +2 -0

 	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;

@@ -528,6 +536,8 @@ struct kvm_arch {
 	struct kvm_ioapic *vioapic;
 	struct kvm_pit *vpit;
 	int vapics_in_nmi_mode;
+	struct kvm_apic_map *apic_map;
+	struct mutex apic_map_lock;

Reversing the order will make it clearer what the lock protects.

Quoted 14 lines

arch/x86/kvm/lapic.c +13 -0

+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);
+
+		if (flat) {
+			*cid = 0;
+			*lid = ldr;
+		} else {

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 169

Quoted 5 lines

arch/x86/kvm/lapic.c +5 -0

+			*cid = ldr >> 4;
+			*lid = ldr & 0xf;
+		}
+	}
+}

You could precaclulate lid_shift/lid_mask/cid_shift/cid_mask and have just one version here. In fact you could drop the function.

Quoted 26 lines

arch/x86/kvm/lapic.c +26 -0

+
+static inline void recalculate_apic_map(struct kvm *kvm)
+{
+	struct kvm_apic_map *new, *old = NULL;
+	struct kvm_vcpu *vcpu;
+	int i;
+
+	new = kzalloc(sizeof(struct kvm_apic_map), GFP_KERNEL);
+
+	mutex_lock(&kvm->arch.apic_map_lock);
+
+	if (!new)
+		goto out;
+
+	new->ldr_bits = 8;
+	new->flat = true;
+	kvm_for_each_vcpu(i, vcpu, kvm) {
+		u16 cid, lid;
+		struct kvm_lapic *apic = vcpu->arch.apic;
+
+		if (!kvm_apic_present(vcpu))
+			continue;
+
+		if (apic_x2apic_mode(apic)) {
+			new->ldr_bits = 32;
+			new->flat = false;

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 198

Quoted 3 lines

arch/x86/kvm/lapic.c +3 -0

+		} else if (kvm_apic_sw_enabled(apic) && new->flat &&
+				kvm_apic_get_reg(apic, APIC_DFR) == APIC_DFR_CLUSTER)
+			new->flat = false;

While a vcpu is being hotplugged in it will be in flat mode. The code correctly gives precedence to x2apic and cluster modes over flat mode, so it is correct in that respect, but the comment describing this is too short.

Quoted 4 lines

arch/x86/kvm/lapic.c +4 -0

+
+		new->phys_map[kvm_apic_id(apic)] = apic;
+		kvm_apic_get_logical_id(kvm_apic_get_reg(apic, APIC_LDR),
+				new->flat, new->ldr_bits, &cid, &lid);

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 208

Quoted 6 lines

arch/x86/kvm/lapic.c +6 -0

+
+		if (lid)
+			new->logical_map[cid][ffs(lid) - 1] = apic;
+	}
+out:
+	old = kvm->arch.apic_map;

rcu_dereference(), just for kicks.

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 213

Quoted 5 lines

arch/x86/kvm/lapic.c +5 -0

+	rcu_assign_pointer(kvm->arch.apic_map, new);
+	mutex_unlock(&kvm->arch.apic_map_lock);
+
+	if (old)
+		kfree_rcu(old, rcu);

Nice, removes the need for rcu_barrier().

Quoted 30 lines

arch/x86/kvm/lapic.c +29 -0

+}
+
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r)
+{
+	struct kvm_apic_map *map;
+	unsigned long bitmap = 1;
+	struct kvm_lapic **dst;
+	int i;
+
+	*r = -1;
+
+	if (irq->shorthand == APIC_DEST_SELF) {
+		*r = kvm_apic_set_irq(src->vcpu, irq);
+		return true;
+	}
+
+	if (irq->shorthand)
+		return false;
+
+	rcu_read_lock();
+	map = rcu_dereference(kvm->arch.apic_map);
+
+	if (!map) {
+		rcu_read_unlock();
+		return false;
+	}
+
+	if (irq->dest_mode == 0) { /* physical mode */

arch/x86/kvm/lapic.c int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source, · line 587

Quoted 5 lines

arch/x86/kvm/lapic.c +5 -0

+		if (irq->delivery_mode == APIC_DM_LOWEST ||
+				irq->dest_id == 0xff) {
+			rcu_read_unlock();
+			return false;
+		}

Two error paths with rcu_read_unlock(). Cleaner to have a bool ret = false; in the beginning and 'goto out_unlock' here, IMO.

arch/x86/kvm/lapic.c int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source, · line 594

Quoted 8 lines

arch/x86/kvm/lapic.c +7 -0

+		dst = &map->phys_map[irq->dest_id & 0xff];
+	} else {
+		u16 cid, lid;
+		u32 mda = irq->dest_id;
+
+		if (map->ldr_bits == 8)
+			mda <<= 24;

mda <<= 32 - map->ldr_bits;

Quoted 35 lines

arch/x86/kvm/lapic.c +34 -0

+
+		kvm_apic_get_logical_id(mda, map->flat, map->ldr_bits,
+				&cid, &lid);
+		dst = map->logical_map[cid];
+
+		bitmap = lid;
+		if (irq->delivery_mode == APIC_DM_LOWEST &&
+				hweight_long(bitmap) > 1) {
+			int l = -1;
+			for_each_set_bit(i, &bitmap, 16) {
+				if (!dst[i])
+					continue;
+				if (l < 0)
+					l = i;
+				else if (kvm_apic_compare_prio(dst[i]->vcpu, dst[l]->vcpu) < 0)
+					l = i;
+			}
+
+			bitmap = (l >= 0) ? 1 << l : 0;
+		}
+	}
+
+	for_each_set_bit(i, &bitmap, 16) {
+		if (!dst[i])
+			continue;
+		if (*r < 0)
+			*r = 0;
+		*r += kvm_apic_set_irq(dst[i]->vcpu, irq);
+	}
+
+	rcu_read_unlock();
+	return true;
+}
+
 /*

arch/x86/kvm/x86.c void kvm_arch_destroy_vm(struct kvm *kvm) · line 6323

Quoted 5 lines

arch/x86/kvm/x86.c +1 -0

@@ -6319,6 +6320,7 @@ void kvm_arch_destroy_vm(struct kvm *kvm)
 		put_page(kvm->arch.apic_access_page);
 	if (kvm->arch.ept_identity_pagetable)
 		put_page(kvm->arch.ept_identity_pagetable);
+	kfree(kvm->arch.apic_map);

rcu_dereference(), even though it cannot be needed here, to shut down static code checkers.

Quoted 14 lines · Avi Kivity

Quoted 8 lines · Gleb Natapov

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.

Agree.

Patch looks good but some minor comments follow.

Quoted 12 lines

arch/x86/include/asm/kvm_host.h struct kvm_arch { · line 540

Quoted 9 lines

struct kvm_arch {

arch/x86/include/asm/kvm_host.h +2 -0

 	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;

@@ -528,6 +536,8 @@ struct kvm_arch {
 	struct kvm_ioapic *vioapic;
 	struct kvm_pit *vpit;
 	int vapics_in_nmi_mode;
+	struct kvm_apic_map *apic_map;
+	struct mutex apic_map_lock;

Reversing the order will make it clearer what the lock protects.

Hmm, OK. I thought names make it clear.

Quoted 15 lines

Quoted 15 lines

arch/x86/kvm/lapic.c +13 -0

+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);
+
+		if (flat) {
+			*cid = 0;
+			*lid = ldr;
+		} else {

Quoted 9 lines

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 169

Quoted 5 lines

arch/x86/kvm/lapic.c +5 -0

+			*cid = ldr >> 4;
+			*lid = ldr & 0xf;
+		}
+	}
+}

You could precaclulate lid_shift/lid_mask/cid_shift/cid_mask and have just one version here. In fact you could drop the function.

You mean precalculate them in recalculate_apic_map() and store in kvm_apic_map?

Quoted 14 lines

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 208

Quoted 11 lines

arch/x86/kvm/lapic.c +10 -0

+
+		new->phys_map[kvm_apic_id(apic)] = apic;
+		kvm_apic_get_logical_id(kvm_apic_get_reg(apic, APIC_LDR),
+				new->flat, new->ldr_bits, &cid, &lid);
+
+		if (lid)
+			new->logical_map[cid][ffs(lid) - 1] = apic;
+	}
+out:
+	old = kvm->arch.apic_map;

rcu_dereference(), just for kicks.

MST says rcu_dereference_protected() but honestly I look at it and rcu_dereference_check(...., 1) and condition they check are so obviously correct in the code that using them is just a clutter.

In more complex
cases, when dereference happens far away from locking it have its point. If you insist on it here should we add it too irq routing code too?

Quoted 10 lines

arch/x86/kvm/x86.c void kvm_arch_destroy_vm(struct kvm *kvm) · line 6323

Quoted 6 lines

/*

arch/x86/kvm/x86.c +1 -0

@@ -6319,6 +6320,7 @@ void kvm_arch_destroy_vm(struct kvm *kvm)
 		put_page(kvm->arch.apic_access_page);
 	if (kvm->arch.ept_identity_pagetable)
 		put_page(kvm->arch.ept_identity_pagetable);
+	kfree(kvm->arch.apic_map);

rcu_dereference(), even though it cannot be needed here, to shut down static code checkers.

How to run those code checkers? Do they complain about irq routing code? Just curious.

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

Signed-off-by Gleb Natapov <[email protected]>

---
Changelog:

- v1->v2
* fix race Avi noticed
* rcu_read_lock() out of the block as per Avi
* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.
* Fix phys_map overflow pointed to by MST
* recalculate_apic_map() does not return error any more.
* add optimization for low prio logical mode with one cpu as dst (it happens)

I did not rewrote kvm_irq_delivery_to_apic_fast() MST way since my way looks cleaner to me.

arch/x86/include/asm/kvm_host.h +10 -0

index 64adb61..3ba8951 100644
@@ -511,6 +511,14 @@ struct kvm_arch_memory_slot {
 	struct kvm_lpage_info *lpage_info[KVM_NR_PAGE_SIZES - 1];
 };
 
+struct kvm_apic_map {
+	struct rcu_head rcu;
+	bool flat;
+	u8 ldr_bits;
+	struct kvm_lapic *phys_map[256];
+	struct kvm_lapic *logical_map[16][16];
+};
+
 struct kvm_arch {
 	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;

@@ -528,6 +536,8 @@ struct kvm_arch {
 	struct kvm_ioapic *vioapic;
 	struct kvm_pit *vpit;
 	int vapics_in_nmi_mode;
+	struct kvm_apic_map *apic_map;
+	struct mutex apic_map_lock;
 
 	unsigned int tss_addr;
 	struct page *apic_access_page;

arch/x86/kvm/lapic.c +58 -0

index 07ad628..06672e8 100644
@@ -139,11 +139,92 @@ static inline int apic_enabled(struct kvm_lapic *apic)
 	(LVT_MASK | APIC_MODE_MASK | APIC_INPUT_POLARITY | \
 	 APIC_LVT_REMOTE_IRR | APIC_LVT_LEVEL_TRIGGER)
 
+static inline int apic_x2apic_mode(struct kvm_lapic *apic)
+{
+	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
+}
+
 static inline int kvm_apic_id(struct kvm_lapic *apic)
 {
 	return (kvm_apic_get_reg(apic, APIC_ID) >> 24) & 0xff;
 }
 
+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);
+
+		if (flat) {
+			*cid = 0;
+			*lid = ldr;
+		} else {
+			*cid = ldr >> 4;
+			*lid = ldr & 0xf;
+		}
+	}
+}
+
+static inline void recalculate_apic_map(struct kvm *kvm)
+{
+	struct kvm_apic_map *new, *old = NULL;
+	struct kvm_vcpu *vcpu;
+	int i;
+
+	new = kzalloc(sizeof(struct kvm_apic_map), GFP_KERNEL);
+
+	mutex_lock(&kvm->arch.apic_map_lock);
+
+	if (!new)
+		goto out;
+
+	new->ldr_bits = 8;
+	new->flat = true;
+	kvm_for_each_vcpu(i, vcpu, kvm) {
+		u16 cid, lid;
+		struct kvm_lapic *apic = vcpu->arch.apic;
+
+		if (!kvm_apic_present(vcpu))
+			continue;
+
+		if (apic_x2apic_mode(apic)) {
+			new->ldr_bits = 32;
+			new->flat = false;
+		} else if (kvm_apic_sw_enabled(apic) && new->flat &&
+				kvm_apic_get_reg(apic, APIC_DFR) == APIC_DFR_CLUSTER)
+			new->flat = false;
+
+		new->phys_map[kvm_apic_id(apic)] = apic;
+		kvm_apic_get_logical_id(kvm_apic_get_reg(apic, APIC_LDR),
+				new->flat, new->ldr_bits, &cid, &lid);
+
+		if (lid)

arch/x86/kvm/lapic.c +97 -12

+
+static inline void kvm_apic_set_id(struct kvm_lapic *apic, u8 id)
+{
+	apic_set_reg(apic, APIC_ID, id << 24);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
+static inline void kvm_apic_set_ldr(struct kvm_lapic *apic, u32 id)
+{
+	apic_set_reg(apic, APIC_LDR, id);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
 static inline int apic_lvt_enabled(struct kvm_lapic *apic, int lvt_type)
 {
 	return !(kvm_apic_get_reg(apic, lvt_type) & APIC_LVT_MASKED);

@@ -193,11 +274,6 @@ void kvm_apic_set_version(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_LVR, v);
 }
 
-static inline int apic_x2apic_mode(struct kvm_lapic *apic)
-{
-	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
-}
-
 static const unsigned int apic_lvt_mask[APIC_LVT_NUM] = {
 	LVT_MASK ,      /* part LVTT mask, timer mode mask added at runtime */
 	LVT_MASK | APIC_MODE_MASK,	/* LVTTHMR */

@@ -477,6 +553,79 @@ int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source,
 	return result;
 }
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r)
+{
+	struct kvm_apic_map *map;
+	unsigned long bitmap = 1;
+	struct kvm_lapic **dst;
+	int i;
+
+	*r = -1;
+
+	if (irq->shorthand == APIC_DEST_SELF) {
+		*r = kvm_apic_set_irq(src->vcpu, irq);
+		return true;
+	}
+
+	if (irq->shorthand)
+		return false;
+
+	rcu_read_lock();
+	map = rcu_dereference(kvm->arch.apic_map);
+
+	if (!map) {
+		rcu_read_unlock();
+		return false;
+	}
+
+	if (irq->dest_mode == 0) { /* physical mode */
+		if (irq->delivery_mode == APIC_DM_LOWEST ||
+				irq->dest_id == 0xff) {
+			rcu_read_unlock();
+			return false;
+		}
+		dst = &map->phys_map[irq->dest_id & 0xff];
+	} else {
+		u16 cid, lid;
+		u32 mda = irq->dest_id;
+
+		if (map->ldr_bits == 8)
+			mda <<= 24;
+
+		kvm_apic_get_logical_id(mda, map->flat, map->ldr_bits,
+				&cid, &lid);
+		dst = map->logical_map[cid];
+
+		bitmap = lid;
+		if (irq->delivery_mode == APIC_DM_LOWEST &&
+				hweight_long(bitmap) > 1) {
+			int l = -1;
+			for_each_set_bit(i, &bitmap, 16) {
+				if (!dst[i])
+					continue;
+				if (l < 0)
+					l = i;
+				else if (kvm_apic_compare_prio(dst[i]->vcpu, dst[l]->vcpu) < 0)
+					l = i;
+			}
+
+			bitmap = (l >= 0) ? 1 << l : 0;
+		}
+	}
+
+	for_each_set_bit(i, &bitmap, 16) {
+		if (!dst[i])
+			continue;
+		if (*r < 0)
+			*r = 0;
+		*r += kvm_apic_set_irq(dst[i]->vcpu, irq);
+	}
+
+	rcu_read_unlock();
+	return true;
+}
+
 /*
  * Add a pending IRQ into lapic.
  * Return 1 if successfully added and 0 if discarded.

@@ -880,7 +1029,7 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 	switch (reg) {
 	case APIC_ID:		/* Local APIC ID */
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_ID, val);
+			kvm_apic_set_id(apic, val >> 24);
 		else
 			ret = 1;
 		break;

@@ -896,15 +1045,16 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 
 	case APIC_LDR:
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_LDR, val & APIC_LDR_MASK);
+			kvm_apic_set_ldr(apic, val & APIC_LDR_MASK);
 		else
 			ret = 1;
 		break;
 
 	case APIC_DFR:
-		if (!apic_x2apic_mode(apic))
+		if (!apic_x2apic_mode(apic)) {
 			apic_set_reg(apic, APIC_DFR, val | 0x0FFFFFFF);
-		else
+			recalculate_apic_map(apic->vcpu->kvm);
+		} else
 			ret = 1;
 		break;
 

@@ -1135,6 +1285,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 			static_key_slow_dec_deferred(&apic_hw_disabled);
 		else
 			static_key_slow_inc(&apic_hw_disabled.key);
+		recalculate_apic_map(vcpu->kvm);
 	}
 
 	if (!kvm_vcpu_is_bsp(apic->vcpu))

@@ -1144,7 +1295,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 	if (apic_x2apic_mode(apic)) {
 		u32 id = kvm_apic_id(apic);
 		u32 ldr = ((id & ~0xf) << 16) | (1 << (id & 0xf));
-		apic_set_reg(apic, APIC_LDR, ldr);
+		kvm_apic_set_ldr(apic, ldr);
 	}
 	apic->base_address = apic->vcpu->arch.apic_base &
 			     MSR_IA32_APICBASE_BASE;

@@ -1169,7 +1320,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	/* Stop the timer in case it's a reset to an active apic */
 	hrtimer_cancel(&apic->lapic_timer.timer);
 
-	apic_set_reg(apic, APIC_ID, vcpu->vcpu_id << 24);
+	kvm_apic_set_id(apic, (u8)vcpu->vcpu_id);
 	kvm_apic_set_version(apic->vcpu);
 
 	for (i = 0; i < APIC_LVT_NUM; i++)

@@ -1180,7 +1331,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_DFR, 0xffffffffU);
 	apic_set_spiv(apic, 0xff);
 	apic_set_reg(apic, APIC_TASKPRI, 0);
-	apic_set_reg(apic, APIC_LDR, 0);
+	kvm_apic_set_ldr(apic, 0);
 	apic_set_reg(apic, APIC_ESR, 0);
 	apic_set_reg(apic, APIC_ICR, 0);
 	apic_set_reg(apic, APIC_ICR2, 0);

@@ -1398,6 +1549,8 @@ void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,
 	/* set SPIV separately to get count of SW disabled APICs right */
 	apic_set_spiv(apic, *((u32 *)(s->regs + APIC_SPIV)));
 	memcpy(vcpu->arch.apic->regs, s->regs, sizeof *s);
+	/* call kvm_apic_set_id() to put apic into apic_map */
+	kvm_apic_set_id(apic, kvm_apic_id(apic));
 	kvm_apic_set_version(vcpu);
 
 	apic_update_ppr(apic);

arch/x86/kvm/lapic.h +3 -0

index 615a8b0..e5ebf9f 100644
@@ -52,6 +52,9 @@ int kvm_apic_match_logical_addr(struct kvm_lapic *apic, u8 mda);
 int kvm_apic_set_irq(struct kvm_vcpu *vcpu, struct kvm_lapic_irq *irq);
 int kvm_apic_local_deliver(struct kvm_lapic *apic, int lvt_type);
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r);
+
 u64 kvm_get_apic_base(struct kvm_vcpu *vcpu);
 void kvm_set_apic_base(struct kvm_vcpu *vcpu, u64 data);
 void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,

arch/x86/kvm/x86.c +2 -0

index f91e2c9..db6db8f 100644
@@ -6269,6 +6269,7 @@ int kvm_arch_init_vm(struct kvm *kvm, unsigned long type)
 	set_bit(KVM_USERSPACE_IRQ_SOURCE_ID, &kvm->arch.irq_sources_bitmap);
 
 	raw_spin_lock_init(&kvm->arch.tsc_write_lock);
+	mutex_init(&kvm->arch.apic_map_lock);
 
 	return 0;
 }

@@ -6319,6 +6320,7 @@ void kvm_arch_destroy_vm(struct kvm *kvm)
 		put_page(kvm->arch.apic_access_page);
 	if (kvm->arch.ept_identity_pagetable)
 		put_page(kvm->arch.ept_identity_pagetable);
+	kfree(kvm->arch.apic_map);
 }
 
 void kvm_arch_free_memslot(struct kvm_memory_slot *free,

virt/kvm/irq_comm.c +6 -2

index 7118be0..3ca89c4 100644
@@ -68,8 +68,13 @@ int kvm_irq_delivery_to_apic(struct kvm *kvm, struct kvm_lapic *src,
 	struct kvm_vcpu *vcpu, *lowest = NULL;
 
 	if (irq->dest_mode == 0 && irq->dest_id == 0xff &&
-			kvm_is_dm_lowest_prio(irq))
+			kvm_is_dm_lowest_prio(irq)) {
 		printk(KERN_INFO "kvm: apic: phys broadcast and lowest prio\n");
+		irq->delivery_mode = APIC_DM_FIXED;
+	}
+
+	if (kvm_irq_delivery_to_apic_fast(kvm, src, irq, &r))
+		return r;
 
 	kvm_for_each_vcpu(i, vcpu, kvm) {
 		if (!kvm_apic_present(vcpu))
--

Gleb.

Quoted 6 lines · Gleb Natapov

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

Signed-off-by Gleb Natapov <[email protected]>

Added Paul just to make sure we are using RCU correctly. Paul could you pls answer the question below?

Quoted 116 lines

---
Changelog:

- v1->v2
* fix race Avi noticed
* rcu_read_lock() out of the block as per Avi
* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.
* Fix phys_map overflow pointed to by MST
* recalculate_apic_map() does not return error any more.
* add optimization for low prio logical mode with one cpu as dst (it happens)

I did not rewrote kvm_irq_delivery_to_apic_fast() MST way since my way looks cleaner to me.

arch/x86/include/asm/kvm_host.h +10 -0

index 64adb61..3ba8951 100644
@@ -511,6 +511,14 @@ struct kvm_arch_memory_slot {
 	struct kvm_lpage_info *lpage_info[KVM_NR_PAGE_SIZES - 1];
 };
 
+struct kvm_apic_map {
+	struct rcu_head rcu;
+	bool flat;
+	u8 ldr_bits;
+	struct kvm_lapic *phys_map[256];
+	struct kvm_lapic *logical_map[16][16];
+};
+
 struct kvm_arch {
 	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;

@@ -528,6 +536,8 @@ struct kvm_arch {
 	struct kvm_ioapic *vioapic;
 	struct kvm_pit *vpit;
 	int vapics_in_nmi_mode;
+	struct kvm_apic_map *apic_map;
+	struct mutex apic_map_lock;
 
 	unsigned int tss_addr;
 	struct page *apic_access_page;

arch/x86/kvm/lapic.c +58 -0

index 07ad628..06672e8 100644
@@ -139,11 +139,92 @@ static inline int apic_enabled(struct kvm_lapic *apic)
 	(LVT_MASK | APIC_MODE_MASK | APIC_INPUT_POLARITY | \
 	 APIC_LVT_REMOTE_IRR | APIC_LVT_LEVEL_TRIGGER)
 
+static inline int apic_x2apic_mode(struct kvm_lapic *apic)
+{
+	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
+}
+
 static inline int kvm_apic_id(struct kvm_lapic *apic)
 {
 	return (kvm_apic_get_reg(apic, APIC_ID) >> 24) & 0xff;
 }
 
+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);
+
+		if (flat) {
+			*cid = 0;
+			*lid = ldr;
+		} else {
+			*cid = ldr >> 4;
+			*lid = ldr & 0xf;
+		}
+	}
+}
+
+static inline void recalculate_apic_map(struct kvm *kvm)
+{
+	struct kvm_apic_map *new, *old = NULL;
+	struct kvm_vcpu *vcpu;
+	int i;
+
+	new = kzalloc(sizeof(struct kvm_apic_map), GFP_KERNEL);
+
+	mutex_lock(&kvm->arch.apic_map_lock);
+
+	if (!new)
+		goto out;
+
+	new->ldr_bits = 8;
+	new->flat = true;
+	kvm_for_each_vcpu(i, vcpu, kvm) {
+		u16 cid, lid;
+		struct kvm_lapic *apic = vcpu->arch.apic;
+
+		if (!kvm_apic_present(vcpu))
+			continue;
+
+		if (apic_x2apic_mode(apic)) {
+			new->ldr_bits = 32;
+			new->flat = false;
+		} else if (kvm_apic_sw_enabled(apic) && new->flat &&
+				kvm_apic_get_reg(apic, APIC_DFR) == APIC_DFR_CLUSTER)
+			new->flat = false;
+
+		new->phys_map[kvm_apic_id(apic)] = apic;
+		kvm_apic_get_logical_id(kvm_apic_get_reg(apic, APIC_LDR),
+				new->flat, new->ldr_bits, &cid, &lid);
+
+		if (lid)

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 214

Quoted 10 lines

arch/x86/kvm/lapic.c +10 -0

+			new->logical_map[cid][ffs(lid) - 1] = apic;
+	}
+out:
+	old = kvm->arch.apic_map;
+	rcu_assign_pointer(kvm->arch.apic_map, new);
+	mutex_unlock(&kvm->arch.apic_map_lock);
+
+	if (old)
+		kfree_rcu(old, rcu);
+}

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way?
If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

Thanks!

Quoted 236 lines

arch/x86/kvm/lapic.c +97 -12

+
+static inline void kvm_apic_set_id(struct kvm_lapic *apic, u8 id)
+{
+	apic_set_reg(apic, APIC_ID, id << 24);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
+static inline void kvm_apic_set_ldr(struct kvm_lapic *apic, u32 id)
+{
+	apic_set_reg(apic, APIC_LDR, id);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
 static inline int apic_lvt_enabled(struct kvm_lapic *apic, int lvt_type)
 {
 	return !(kvm_apic_get_reg(apic, lvt_type) & APIC_LVT_MASKED);

@@ -193,11 +274,6 @@ void kvm_apic_set_version(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_LVR, v);
 }
 
-static inline int apic_x2apic_mode(struct kvm_lapic *apic)
-{
-	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
-}
-
 static const unsigned int apic_lvt_mask[APIC_LVT_NUM] = {
 	LVT_MASK ,      /* part LVTT mask, timer mode mask added at runtime */
 	LVT_MASK | APIC_MODE_MASK,	/* LVTTHMR */

@@ -477,6 +553,79 @@ int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source,
 	return result;
 }
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r)
+{
+	struct kvm_apic_map *map;
+	unsigned long bitmap = 1;
+	struct kvm_lapic **dst;
+	int i;
+
+	*r = -1;
+
+	if (irq->shorthand == APIC_DEST_SELF) {
+		*r = kvm_apic_set_irq(src->vcpu, irq);
+		return true;
+	}
+
+	if (irq->shorthand)
+		return false;
+
+	rcu_read_lock();
+	map = rcu_dereference(kvm->arch.apic_map);
+
+	if (!map) {
+		rcu_read_unlock();
+		return false;
+	}
+
+	if (irq->dest_mode == 0) { /* physical mode */
+		if (irq->delivery_mode == APIC_DM_LOWEST ||
+				irq->dest_id == 0xff) {
+			rcu_read_unlock();
+			return false;
+		}
+		dst = &map->phys_map[irq->dest_id & 0xff];
+	} else {
+		u16 cid, lid;
+		u32 mda = irq->dest_id;
+
+		if (map->ldr_bits == 8)
+			mda <<= 24;
+
+		kvm_apic_get_logical_id(mda, map->flat, map->ldr_bits,
+				&cid, &lid);
+		dst = map->logical_map[cid];
+
+		bitmap = lid;
+		if (irq->delivery_mode == APIC_DM_LOWEST &&
+				hweight_long(bitmap) > 1) {
+			int l = -1;
+			for_each_set_bit(i, &bitmap, 16) {
+				if (!dst[i])
+					continue;
+				if (l < 0)
+					l = i;
+				else if (kvm_apic_compare_prio(dst[i]->vcpu, dst[l]->vcpu) < 0)
+					l = i;
+			}
+
+			bitmap = (l >= 0) ? 1 << l : 0;
+		}
+	}
+
+	for_each_set_bit(i, &bitmap, 16) {
+		if (!dst[i])
+			continue;
+		if (*r < 0)
+			*r = 0;
+		*r += kvm_apic_set_irq(dst[i]->vcpu, irq);
+	}
+
+	rcu_read_unlock();
+	return true;
+}
+
 /*
  * Add a pending IRQ into lapic.
  * Return 1 if successfully added and 0 if discarded.

@@ -880,7 +1029,7 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 	switch (reg) {
 	case APIC_ID:		/* Local APIC ID */
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_ID, val);
+			kvm_apic_set_id(apic, val >> 24);
 		else
 			ret = 1;
 		break;

@@ -896,15 +1045,16 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 
 	case APIC_LDR:
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_LDR, val & APIC_LDR_MASK);
+			kvm_apic_set_ldr(apic, val & APIC_LDR_MASK);
 		else
 			ret = 1;
 		break;
 
 	case APIC_DFR:
-		if (!apic_x2apic_mode(apic))
+		if (!apic_x2apic_mode(apic)) {
 			apic_set_reg(apic, APIC_DFR, val | 0x0FFFFFFF);
-		else
+			recalculate_apic_map(apic->vcpu->kvm);
+		} else
 			ret = 1;
 		break;
 

@@ -1135,6 +1285,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 			static_key_slow_dec_deferred(&apic_hw_disabled);
 		else
 			static_key_slow_inc(&apic_hw_disabled.key);
+		recalculate_apic_map(vcpu->kvm);
 	}
 
 	if (!kvm_vcpu_is_bsp(apic->vcpu))

@@ -1144,7 +1295,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 	if (apic_x2apic_mode(apic)) {
 		u32 id = kvm_apic_id(apic);
 		u32 ldr = ((id & ~0xf) << 16) | (1 << (id & 0xf));
-		apic_set_reg(apic, APIC_LDR, ldr);
+		kvm_apic_set_ldr(apic, ldr);
 	}
 	apic->base_address = apic->vcpu->arch.apic_base &
 			     MSR_IA32_APICBASE_BASE;

@@ -1169,7 +1320,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	/* Stop the timer in case it's a reset to an active apic */
 	hrtimer_cancel(&apic->lapic_timer.timer);
 
-	apic_set_reg(apic, APIC_ID, vcpu->vcpu_id << 24);
+	kvm_apic_set_id(apic, (u8)vcpu->vcpu_id);
 	kvm_apic_set_version(apic->vcpu);
 
 	for (i = 0; i < APIC_LVT_NUM; i++)

@@ -1180,7 +1331,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_DFR, 0xffffffffU);
 	apic_set_spiv(apic, 0xff);
 	apic_set_reg(apic, APIC_TASKPRI, 0);
-	apic_set_reg(apic, APIC_LDR, 0);
+	kvm_apic_set_ldr(apic, 0);
 	apic_set_reg(apic, APIC_ESR, 0);
 	apic_set_reg(apic, APIC_ICR, 0);
 	apic_set_reg(apic, APIC_ICR2, 0);

@@ -1398,6 +1549,8 @@ void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,
 	/* set SPIV separately to get count of SW disabled APICs right */
 	apic_set_spiv(apic, *((u32 *)(s->regs + APIC_SPIV)));
 	memcpy(vcpu->arch.apic->regs, s->regs, sizeof *s);
+	/* call kvm_apic_set_id() to put apic into apic_map */
+	kvm_apic_set_id(apic, kvm_apic_id(apic));
 	kvm_apic_set_version(vcpu);
 
 	apic_update_ppr(apic);

arch/x86/kvm/lapic.h +3 -0

index 615a8b0..e5ebf9f 100644
@@ -52,6 +52,9 @@ int kvm_apic_match_logical_addr(struct kvm_lapic *apic, u8 mda);
 int kvm_apic_set_irq(struct kvm_vcpu *vcpu, struct kvm_lapic_irq *irq);
 int kvm_apic_local_deliver(struct kvm_lapic *apic, int lvt_type);
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r);
+
 u64 kvm_get_apic_base(struct kvm_vcpu *vcpu);
 void kvm_set_apic_base(struct kvm_vcpu *vcpu, u64 data);
 void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,

arch/x86/kvm/x86.c +2 -0

index f91e2c9..db6db8f 100644
@@ -6269,6 +6269,7 @@ int kvm_arch_init_vm(struct kvm *kvm, unsigned long type)
 	set_bit(KVM_USERSPACE_IRQ_SOURCE_ID, &kvm->arch.irq_sources_bitmap);
 
 	raw_spin_lock_init(&kvm->arch.tsc_write_lock);
+	mutex_init(&kvm->arch.apic_map_lock);
 
 	return 0;
 }

@@ -6319,6 +6320,7 @@ void kvm_arch_destroy_vm(struct kvm *kvm)
 		put_page(kvm->arch.apic_access_page);
 	if (kvm->arch.ept_identity_pagetable)
 		put_page(kvm->arch.ept_identity_pagetable);
+	kfree(kvm->arch.apic_map);
 }
 
 void kvm_arch_free_memslot(struct kvm_memory_slot *free,

virt/kvm/irq_comm.c +6 -2

index 7118be0..3ca89c4 100644
@@ -68,8 +68,13 @@ int kvm_irq_delivery_to_apic(struct kvm *kvm, struct kvm_lapic *src,
 	struct kvm_vcpu *vcpu, *lowest = NULL;
 
 	if (irq->dest_mode == 0 && irq->dest_id == 0xff &&
-			kvm_is_dm_lowest_prio(irq))
+			kvm_is_dm_lowest_prio(irq)) {
 		printk(KERN_INFO "kvm: apic: phys broadcast and lowest prio\n");
+		irq->delivery_mode = APIC_DM_FIXED;
+	}
+
+	if (kvm_irq_delivery_to_apic_fast(kvm, src, irq, &r))
+		return r;
 
 	kvm_for_each_vcpu(i, vcpu, kvm) {
 		if (!kvm_apic_present(vcpu))
--

Gleb.

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk. The kfree_rcu() implementation cannot really decide what to do here, especially given that it is callable with irqs disabled.

The usual approach is to keep a per-CPU counter and count it down from some number for each kfree_rcu(). When it reaches zero, invoke synchronize_rcu() as well as kfree_rcu(), and then reset it to the "some number" mentioned above.

In theory, I could create an API that did this. In practice, I have no idea how to choose the number -- much depends on the size of the object being freed, for example.

Quoted 14 lines · Paul E. McKenney

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk. The kfree_rcu() implementation cannot really decide what to do here, especially given that it is callable with irqs disabled.

The usual approach is to keep a per-CPU counter and count it down from some number for each kfree_rcu(). When it reaches zero, invoke synchronize_rcu() as well as kfree_rcu(), and then reset it to the "some number" mentioned above.

Quoted 3 lines

In theory, I could create an API that did this. In practice, I have no idea how to choose the number -- much depends on the size of the object being freed, for example.

Perhaps approach it from the other direction? If we are under memory pressure, start synchronize_rcu()ing, much like the shrinker operates.

Signature · 3 lines

-- 
I have a truly marvellous patch that fixes the bug which this
signature is too narrow to contain.

Quoted 19 lines · Avi Kivity

Quoted 17 lines · Paul E. McKenney

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk. The kfree_rcu() implementation cannot really decide what to do here, especially given that it is callable with irqs disabled.

The usual approach is to keep a per-CPU counter and count it down from some number for each kfree_rcu(). When it reaches zero, invoke synchronize_rcu() as well as kfree_rcu(), and then reset it to the "some number" mentioned above.

In theory, I could create an API that did this. In practice, I have no idea how to choose the number -- much depends on the size of the object being freed, for example.

Quoted 3 lines

Perhaps approach it from the other direction? If we are under memory pressure, start synchronize_rcu()ing, much like the shrinker operates.

Tricky ...

For now, how about we call synchronize_rcu_expedited in kvm and call it a day?

Also has an advantage that apic map is guaranteed to be in sync with guest - while it seems that it's already correct as is, synchronous operation is way simpler.

We can add a tracepoint so that we can detect it if this starts happening a lot for some guest.

Quoted 144 lines · Michael S. Tsirkin

Quoted 6 lines · Gleb Natapov

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

Signed-off-by Gleb Natapov <[email protected]>

Added Paul just to make sure we are using RCU correctly. Paul could you pls answer the question below?

Quoted 116 lines

---
Changelog:

- v1->v2
* fix race Avi noticed
* rcu_read_lock() out of the block as per Avi
* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.
* Fix phys_map overflow pointed to by MST
* recalculate_apic_map() does not return error any more.
* add optimization for low prio logical mode with one cpu as dst (it happens)

I did not rewrote kvm_irq_delivery_to_apic_fast() MST way since my way looks cleaner to me.

arch/x86/include/asm/kvm_host.h +10 -0

index 64adb61..3ba8951 100644
@@ -511,6 +511,14 @@ struct kvm_arch_memory_slot {
 	struct kvm_lpage_info *lpage_info[KVM_NR_PAGE_SIZES - 1];
 };
 
+struct kvm_apic_map {
+	struct rcu_head rcu;
+	bool flat;
+	u8 ldr_bits;
+	struct kvm_lapic *phys_map[256];
+	struct kvm_lapic *logical_map[16][16];
+};
+
 struct kvm_arch {
 	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;

@@ -528,6 +536,8 @@ struct kvm_arch {
 	struct kvm_ioapic *vioapic;
 	struct kvm_pit *vpit;
 	int vapics_in_nmi_mode;
+	struct kvm_apic_map *apic_map;
+	struct mutex apic_map_lock;
 
 	unsigned int tss_addr;
 	struct page *apic_access_page;

arch/x86/kvm/lapic.c +58 -0

index 07ad628..06672e8 100644
@@ -139,11 +139,92 @@ static inline int apic_enabled(struct kvm_lapic *apic)
 	(LVT_MASK | APIC_MODE_MASK | APIC_INPUT_POLARITY | \
 	 APIC_LVT_REMOTE_IRR | APIC_LVT_LEVEL_TRIGGER)
 
+static inline int apic_x2apic_mode(struct kvm_lapic *apic)
+{
+	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
+}
+
 static inline int kvm_apic_id(struct kvm_lapic *apic)
 {
 	return (kvm_apic_get_reg(apic, APIC_ID) >> 24) & 0xff;
 }
 
+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);
+
+		if (flat) {
+			*cid = 0;
+			*lid = ldr;
+		} else {
+			*cid = ldr >> 4;
+			*lid = ldr & 0xf;
+		}
+	}
+}
+
+static inline void recalculate_apic_map(struct kvm *kvm)
+{
+	struct kvm_apic_map *new, *old = NULL;
+	struct kvm_vcpu *vcpu;
+	int i;
+
+	new = kzalloc(sizeof(struct kvm_apic_map), GFP_KERNEL);
+
+	mutex_lock(&kvm->arch.apic_map_lock);
+
+	if (!new)
+		goto out;
+
+	new->ldr_bits = 8;
+	new->flat = true;
+	kvm_for_each_vcpu(i, vcpu, kvm) {
+		u16 cid, lid;
+		struct kvm_lapic *apic = vcpu->arch.apic;
+
+		if (!kvm_apic_present(vcpu))
+			continue;
+
+		if (apic_x2apic_mode(apic)) {
+			new->ldr_bits = 32;
+			new->flat = false;
+		} else if (kvm_apic_sw_enabled(apic) && new->flat &&
+				kvm_apic_get_reg(apic, APIC_DFR) == APIC_DFR_CLUSTER)
+			new->flat = false;
+
+		new->phys_map[kvm_apic_id(apic)] = apic;
+		kvm_apic_get_logical_id(kvm_apic_get_reg(apic, APIC_LDR),
+				new->flat, new->ldr_bits, &cid, &lid);
+
+		if (lid)

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 214

Quoted 10 lines

arch/x86/kvm/lapic.c +10 -0

+			new->logical_map[cid][ffs(lid) - 1] = apic;
+	}
+out:
+	old = kvm->arch.apic_map;
+	rcu_assign_pointer(kvm->arch.apic_map, new);
+	mutex_unlock(&kvm->arch.apic_map_lock);
+
+	if (old)
+		kfree_rcu(old, rcu);
+}

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way?
If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

The kfree_rcu() implementation cannot really
decide what to do here, especially given that it is callable with irqs disabled.

The usual approach is to keep a per-CPU counter and count it down from some number for each kfree_rcu(). When it reaches zero, invoke synchronize_rcu() as well as kfree_rcu(), and then reset it to the "some number" mentioned above.

In theory, I could create an API that did this. In practice, I have no idea how to choose the number -- much depends on the size of the object being freed, for example.

The RCU usage looks otherwise sane at first glance.

Thanx, Paul

Quoted 239 lines

Thanks!

Quoted 236 lines

arch/x86/kvm/lapic.c +97 -12

+
+static inline void kvm_apic_set_id(struct kvm_lapic *apic, u8 id)
+{
+	apic_set_reg(apic, APIC_ID, id << 24);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
+static inline void kvm_apic_set_ldr(struct kvm_lapic *apic, u32 id)
+{
+	apic_set_reg(apic, APIC_LDR, id);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
 static inline int apic_lvt_enabled(struct kvm_lapic *apic, int lvt_type)
 {
 	return !(kvm_apic_get_reg(apic, lvt_type) & APIC_LVT_MASKED);

@@ -193,11 +274,6 @@ void kvm_apic_set_version(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_LVR, v);
 }
 
-static inline int apic_x2apic_mode(struct kvm_lapic *apic)
-{
-	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
-}
-
 static const unsigned int apic_lvt_mask[APIC_LVT_NUM] = {
 	LVT_MASK ,      /* part LVTT mask, timer mode mask added at runtime */
 	LVT_MASK | APIC_MODE_MASK,	/* LVTTHMR */

@@ -477,6 +553,79 @@ int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source,
 	return result;
 }
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r)
+{
+	struct kvm_apic_map *map;
+	unsigned long bitmap = 1;
+	struct kvm_lapic **dst;
+	int i;
+
+	*r = -1;
+
+	if (irq->shorthand == APIC_DEST_SELF) {
+		*r = kvm_apic_set_irq(src->vcpu, irq);
+		return true;
+	}
+
+	if (irq->shorthand)
+		return false;
+
+	rcu_read_lock();
+	map = rcu_dereference(kvm->arch.apic_map);
+
+	if (!map) {
+		rcu_read_unlock();
+		return false;
+	}
+
+	if (irq->dest_mode == 0) { /* physical mode */
+		if (irq->delivery_mode == APIC_DM_LOWEST ||
+				irq->dest_id == 0xff) {
+			rcu_read_unlock();
+			return false;
+		}
+		dst = &map->phys_map[irq->dest_id & 0xff];
+	} else {
+		u16 cid, lid;
+		u32 mda = irq->dest_id;
+
+		if (map->ldr_bits == 8)
+			mda <<= 24;
+
+		kvm_apic_get_logical_id(mda, map->flat, map->ldr_bits,
+				&cid, &lid);
+		dst = map->logical_map[cid];
+
+		bitmap = lid;
+		if (irq->delivery_mode == APIC_DM_LOWEST &&
+				hweight_long(bitmap) > 1) {
+			int l = -1;
+			for_each_set_bit(i, &bitmap, 16) {
+				if (!dst[i])
+					continue;
+				if (l < 0)
+					l = i;
+				else if (kvm_apic_compare_prio(dst[i]->vcpu, dst[l]->vcpu) < 0)
+					l = i;
+			}
+
+			bitmap = (l >= 0) ? 1 << l : 0;
+		}
+	}
+
+	for_each_set_bit(i, &bitmap, 16) {
+		if (!dst[i])
+			continue;
+		if (*r < 0)
+			*r = 0;
+		*r += kvm_apic_set_irq(dst[i]->vcpu, irq);
+	}
+
+	rcu_read_unlock();
+	return true;
+}
+
 /*
  * Add a pending IRQ into lapic.
  * Return 1 if successfully added and 0 if discarded.

@@ -880,7 +1029,7 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 	switch (reg) {
 	case APIC_ID:		/* Local APIC ID */
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_ID, val);
+			kvm_apic_set_id(apic, val >> 24);
 		else
 			ret = 1;
 		break;

@@ -896,15 +1045,16 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 
 	case APIC_LDR:
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_LDR, val & APIC_LDR_MASK);
+			kvm_apic_set_ldr(apic, val & APIC_LDR_MASK);
 		else
 			ret = 1;
 		break;
 
 	case APIC_DFR:
-		if (!apic_x2apic_mode(apic))
+		if (!apic_x2apic_mode(apic)) {
 			apic_set_reg(apic, APIC_DFR, val | 0x0FFFFFFF);
-		else
+			recalculate_apic_map(apic->vcpu->kvm);
+		} else
 			ret = 1;
 		break;
 

@@ -1135,6 +1285,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 			static_key_slow_dec_deferred(&apic_hw_disabled);
 		else
 			static_key_slow_inc(&apic_hw_disabled.key);
+		recalculate_apic_map(vcpu->kvm);
 	}
 
 	if (!kvm_vcpu_is_bsp(apic->vcpu))

@@ -1144,7 +1295,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 	if (apic_x2apic_mode(apic)) {
 		u32 id = kvm_apic_id(apic);
 		u32 ldr = ((id & ~0xf) << 16) | (1 << (id & 0xf));
-		apic_set_reg(apic, APIC_LDR, ldr);
+		kvm_apic_set_ldr(apic, ldr);
 	}
 	apic->base_address = apic->vcpu->arch.apic_base &
 			     MSR_IA32_APICBASE_BASE;

@@ -1169,7 +1320,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	/* Stop the timer in case it's a reset to an active apic */
 	hrtimer_cancel(&apic->lapic_timer.timer);
 
-	apic_set_reg(apic, APIC_ID, vcpu->vcpu_id << 24);
+	kvm_apic_set_id(apic, (u8)vcpu->vcpu_id);
 	kvm_apic_set_version(apic->vcpu);
 
 	for (i = 0; i < APIC_LVT_NUM; i++)

@@ -1180,7 +1331,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_DFR, 0xffffffffU);
 	apic_set_spiv(apic, 0xff);
 	apic_set_reg(apic, APIC_TASKPRI, 0);
-	apic_set_reg(apic, APIC_LDR, 0);
+	kvm_apic_set_ldr(apic, 0);
 	apic_set_reg(apic, APIC_ESR, 0);
 	apic_set_reg(apic, APIC_ICR, 0);
 	apic_set_reg(apic, APIC_ICR2, 0);

@@ -1398,6 +1549,8 @@ void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,
 	/* set SPIV separately to get count of SW disabled APICs right */
 	apic_set_spiv(apic, *((u32 *)(s->regs + APIC_SPIV)));
 	memcpy(vcpu->arch.apic->regs, s->regs, sizeof *s);
+	/* call kvm_apic_set_id() to put apic into apic_map */
+	kvm_apic_set_id(apic, kvm_apic_id(apic));
 	kvm_apic_set_version(vcpu);
 
 	apic_update_ppr(apic);

arch/x86/kvm/lapic.h +3 -0

index 615a8b0..e5ebf9f 100644
@@ -52,6 +52,9 @@ int kvm_apic_match_logical_addr(struct kvm_lapic *apic, u8 mda);
 int kvm_apic_set_irq(struct kvm_vcpu *vcpu, struct kvm_lapic_irq *irq);
 int kvm_apic_local_deliver(struct kvm_lapic *apic, int lvt_type);
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r);
+
 u64 kvm_get_apic_base(struct kvm_vcpu *vcpu);
 void kvm_set_apic_base(struct kvm_vcpu *vcpu, u64 data);
 void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,

arch/x86/kvm/x86.c +2 -0

index f91e2c9..db6db8f 100644
@@ -6269,6 +6269,7 @@ int kvm_arch_init_vm(struct kvm *kvm, unsigned long type)
 	set_bit(KVM_USERSPACE_IRQ_SOURCE_ID, &kvm->arch.irq_sources_bitmap);
 
 	raw_spin_lock_init(&kvm->arch.tsc_write_lock);
+	mutex_init(&kvm->arch.apic_map_lock);
 
 	return 0;
 }

@@ -6319,6 +6320,7 @@ void kvm_arch_destroy_vm(struct kvm *kvm)
 		put_page(kvm->arch.apic_access_page);
 	if (kvm->arch.ept_identity_pagetable)
 		put_page(kvm->arch.ept_identity_pagetable);
+	kfree(kvm->arch.apic_map);
 }
 
 void kvm_arch_free_memslot(struct kvm_memory_slot *free,

virt/kvm/irq_comm.c +6 -2

index 7118be0..3ca89c4 100644
@@ -68,8 +68,13 @@ int kvm_irq_delivery_to_apic(struct kvm *kvm, struct kvm_lapic *src,
 	struct kvm_vcpu *vcpu, *lowest = NULL;
 
 	if (irq->dest_mode == 0 && irq->dest_id == 0xff &&
-			kvm_is_dm_lowest_prio(irq))
+			kvm_is_dm_lowest_prio(irq)) {
 		printk(KERN_INFO "kvm: apic: phys broadcast and lowest prio\n");
+		irq->delivery_mode = APIC_DM_FIXED;
+	}
+
+	if (kvm_irq_delivery_to_apic_fast(kvm, src, irq, &r))
+		return r;
 
 	kvm_for_each_vcpu(i, vcpu, kvm) {
 		if (!kvm_apic_present(vcpu))
--

Gleb.

Quoted 145 lines · Paul E. McKenney

Quoted 144 lines · Michael S. Tsirkin

Quoted 6 lines · Gleb Natapov

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

Signed-off-by Gleb Natapov <[email protected]>

Added Paul just to make sure we are using RCU correctly. Paul could you pls answer the question below?

Quoted 116 lines

---
Changelog:

- v1->v2
* fix race Avi noticed
* rcu_read_lock() out of the block as per Avi
* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.
* Fix phys_map overflow pointed to by MST
* recalculate_apic_map() does not return error any more.
* add optimization for low prio logical mode with one cpu as dst (it happens)

I did not rewrote kvm_irq_delivery_to_apic_fast() MST way since my way looks cleaner to me.

arch/x86/include/asm/kvm_host.h +10 -0

index 64adb61..3ba8951 100644
@@ -511,6 +511,14 @@ struct kvm_arch_memory_slot {
 	struct kvm_lpage_info *lpage_info[KVM_NR_PAGE_SIZES - 1];
 };
 
+struct kvm_apic_map {
+	struct rcu_head rcu;
+	bool flat;
+	u8 ldr_bits;
+	struct kvm_lapic *phys_map[256];
+	struct kvm_lapic *logical_map[16][16];
+};
+
 struct kvm_arch {
 	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;

@@ -528,6 +536,8 @@ struct kvm_arch {
 	struct kvm_ioapic *vioapic;
 	struct kvm_pit *vpit;
 	int vapics_in_nmi_mode;
+	struct kvm_apic_map *apic_map;
+	struct mutex apic_map_lock;
 
 	unsigned int tss_addr;
 	struct page *apic_access_page;

arch/x86/kvm/lapic.c +58 -0

index 07ad628..06672e8 100644
@@ -139,11 +139,92 @@ static inline int apic_enabled(struct kvm_lapic *apic)
 	(LVT_MASK | APIC_MODE_MASK | APIC_INPUT_POLARITY | \
 	 APIC_LVT_REMOTE_IRR | APIC_LVT_LEVEL_TRIGGER)
 
+static inline int apic_x2apic_mode(struct kvm_lapic *apic)
+{
+	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
+}
+
 static inline int kvm_apic_id(struct kvm_lapic *apic)
 {
 	return (kvm_apic_get_reg(apic, APIC_ID) >> 24) & 0xff;
 }
 
+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);
+
+		if (flat) {
+			*cid = 0;
+			*lid = ldr;
+		} else {
+			*cid = ldr >> 4;
+			*lid = ldr & 0xf;
+		}
+	}
+}
+
+static inline void recalculate_apic_map(struct kvm *kvm)
+{
+	struct kvm_apic_map *new, *old = NULL;
+	struct kvm_vcpu *vcpu;
+	int i;
+
+	new = kzalloc(sizeof(struct kvm_apic_map), GFP_KERNEL);
+
+	mutex_lock(&kvm->arch.apic_map_lock);
+
+	if (!new)
+		goto out;
+
+	new->ldr_bits = 8;
+	new->flat = true;
+	kvm_for_each_vcpu(i, vcpu, kvm) {
+		u16 cid, lid;
+		struct kvm_lapic *apic = vcpu->arch.apic;
+
+		if (!kvm_apic_present(vcpu))
+			continue;
+
+		if (apic_x2apic_mode(apic)) {
+			new->ldr_bits = 32;
+			new->flat = false;
+		} else if (kvm_apic_sw_enabled(apic) && new->flat &&
+				kvm_apic_get_reg(apic, APIC_DFR) == APIC_DFR_CLUSTER)
+			new->flat = false;
+
+		new->phys_map[kvm_apic_id(apic)] = apic;
+		kvm_apic_get_logical_id(kvm_apic_get_reg(apic, APIC_LDR),
+				new->flat, new->ldr_bits, &cid, &lid);
+
+		if (lid)

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 214

Quoted 10 lines

arch/x86/kvm/lapic.c +10 -0

+			new->logical_map[cid][ffs(lid) - 1] = apic;
+	}
+out:
+	old = kvm->arch.apic_map;
+	rcu_assign_pointer(kvm->arch.apic_map, new);
+	mutex_unlock(&kvm->arch.apic_map_lock);
+
+	if (old)
+		kfree_rcu(old, rcu);
+}

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way?
If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

Quoted 8 lines

The kfree_rcu() implementation cannot really
decide what to do here, especially given that it is callable with irqs disabled.

The usual approach is to keep a per-CPU counter and count it down from some number for each kfree_rcu(). When it reaches zero, invoke synchronize_rcu() as well as kfree_rcu(), and then reset it to the "some number" mentioned above.

It is a bit of a concern for me that this will hurt worst-case latency for realtime guests. In our case, we return error and this will fall back on not allocating memory and using slow all-CPU scan. One possible scheme that relies on this is:
- increment an atomic counter, per vcpu. If above threshold -> return with error
- call_rcu (+ barrier vcpu destruct)
- within callback decrement an atomic counter

Quoted 3 lines

In theory, I could create an API that did this. In practice, I have no idea how to choose the number -- much depends on the size of the object being freed, for example.

We could pass an object size, no problem :)

Quoted 243 lines

The RCU usage looks otherwise sane at first glance.

Thanx, Paul

Quoted 239 lines

Thanks!

Quoted 236 lines

arch/x86/kvm/lapic.c +97 -12

+
+static inline void kvm_apic_set_id(struct kvm_lapic *apic, u8 id)
+{
+	apic_set_reg(apic, APIC_ID, id << 24);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
+static inline void kvm_apic_set_ldr(struct kvm_lapic *apic, u32 id)
+{
+	apic_set_reg(apic, APIC_LDR, id);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
 static inline int apic_lvt_enabled(struct kvm_lapic *apic, int lvt_type)
 {
 	return !(kvm_apic_get_reg(apic, lvt_type) & APIC_LVT_MASKED);

@@ -193,11 +274,6 @@ void kvm_apic_set_version(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_LVR, v);
 }
 
-static inline int apic_x2apic_mode(struct kvm_lapic *apic)
-{
-	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
-}
-
 static const unsigned int apic_lvt_mask[APIC_LVT_NUM] = {
 	LVT_MASK ,      /* part LVTT mask, timer mode mask added at runtime */
 	LVT_MASK | APIC_MODE_MASK,	/* LVTTHMR */

@@ -477,6 +553,79 @@ int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source,
 	return result;
 }
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r)
+{
+	struct kvm_apic_map *map;
+	unsigned long bitmap = 1;
+	struct kvm_lapic **dst;
+	int i;
+
+	*r = -1;
+
+	if (irq->shorthand == APIC_DEST_SELF) {
+		*r = kvm_apic_set_irq(src->vcpu, irq);
+		return true;
+	}
+
+	if (irq->shorthand)
+		return false;
+
+	rcu_read_lock();
+	map = rcu_dereference(kvm->arch.apic_map);
+
+	if (!map) {
+		rcu_read_unlock();
+		return false;
+	}
+
+	if (irq->dest_mode == 0) { /* physical mode */
+		if (irq->delivery_mode == APIC_DM_LOWEST ||
+				irq->dest_id == 0xff) {
+			rcu_read_unlock();
+			return false;
+		}
+		dst = &map->phys_map[irq->dest_id & 0xff];
+	} else {
+		u16 cid, lid;
+		u32 mda = irq->dest_id;
+
+		if (map->ldr_bits == 8)
+			mda <<= 24;
+
+		kvm_apic_get_logical_id(mda, map->flat, map->ldr_bits,
+				&cid, &lid);
+		dst = map->logical_map[cid];
+
+		bitmap = lid;
+		if (irq->delivery_mode == APIC_DM_LOWEST &&
+				hweight_long(bitmap) > 1) {
+			int l = -1;
+			for_each_set_bit(i, &bitmap, 16) {
+				if (!dst[i])
+					continue;
+				if (l < 0)
+					l = i;
+				else if (kvm_apic_compare_prio(dst[i]->vcpu, dst[l]->vcpu) < 0)
+					l = i;
+			}
+
+			bitmap = (l >= 0) ? 1 << l : 0;
+		}
+	}
+
+	for_each_set_bit(i, &bitmap, 16) {
+		if (!dst[i])
+			continue;
+		if (*r < 0)
+			*r = 0;
+		*r += kvm_apic_set_irq(dst[i]->vcpu, irq);
+	}
+
+	rcu_read_unlock();
+	return true;
+}
+
 /*
  * Add a pending IRQ into lapic.
  * Return 1 if successfully added and 0 if discarded.

@@ -880,7 +1029,7 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 	switch (reg) {
 	case APIC_ID:		/* Local APIC ID */
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_ID, val);
+			kvm_apic_set_id(apic, val >> 24);
 		else
 			ret = 1;
 		break;

@@ -896,15 +1045,16 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 
 	case APIC_LDR:
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_LDR, val & APIC_LDR_MASK);
+			kvm_apic_set_ldr(apic, val & APIC_LDR_MASK);
 		else
 			ret = 1;
 		break;
 
 	case APIC_DFR:
-		if (!apic_x2apic_mode(apic))
+		if (!apic_x2apic_mode(apic)) {
 			apic_set_reg(apic, APIC_DFR, val | 0x0FFFFFFF);
-		else
+			recalculate_apic_map(apic->vcpu->kvm);
+		} else
 			ret = 1;
 		break;
 

@@ -1135,6 +1285,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 			static_key_slow_dec_deferred(&apic_hw_disabled);
 		else
 			static_key_slow_inc(&apic_hw_disabled.key);
+		recalculate_apic_map(vcpu->kvm);
 	}
 
 	if (!kvm_vcpu_is_bsp(apic->vcpu))

@@ -1144,7 +1295,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 	if (apic_x2apic_mode(apic)) {
 		u32 id = kvm_apic_id(apic);
 		u32 ldr = ((id & ~0xf) << 16) | (1 << (id & 0xf));
-		apic_set_reg(apic, APIC_LDR, ldr);
+		kvm_apic_set_ldr(apic, ldr);
 	}
 	apic->base_address = apic->vcpu->arch.apic_base &
 			     MSR_IA32_APICBASE_BASE;

@@ -1169,7 +1320,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	/* Stop the timer in case it's a reset to an active apic */
 	hrtimer_cancel(&apic->lapic_timer.timer);
 
-	apic_set_reg(apic, APIC_ID, vcpu->vcpu_id << 24);
+	kvm_apic_set_id(apic, (u8)vcpu->vcpu_id);
 	kvm_apic_set_version(apic->vcpu);
 
 	for (i = 0; i < APIC_LVT_NUM; i++)

@@ -1180,7 +1331,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_DFR, 0xffffffffU);
 	apic_set_spiv(apic, 0xff);
 	apic_set_reg(apic, APIC_TASKPRI, 0);
-	apic_set_reg(apic, APIC_LDR, 0);
+	kvm_apic_set_ldr(apic, 0);
 	apic_set_reg(apic, APIC_ESR, 0);
 	apic_set_reg(apic, APIC_ICR, 0);
 	apic_set_reg(apic, APIC_ICR2, 0);

@@ -1398,6 +1549,8 @@ void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,
 	/* set SPIV separately to get count of SW disabled APICs right */
 	apic_set_spiv(apic, *((u32 *)(s->regs + APIC_SPIV)));
 	memcpy(vcpu->arch.apic->regs, s->regs, sizeof *s);
+	/* call kvm_apic_set_id() to put apic into apic_map */
+	kvm_apic_set_id(apic, kvm_apic_id(apic));
 	kvm_apic_set_version(vcpu);
 
 	apic_update_ppr(apic);

arch/x86/kvm/lapic.h +3 -0

index 615a8b0..e5ebf9f 100644
@@ -52,6 +52,9 @@ int kvm_apic_match_logical_addr(struct kvm_lapic *apic, u8 mda);
 int kvm_apic_set_irq(struct kvm_vcpu *vcpu, struct kvm_lapic_irq *irq);
 int kvm_apic_local_deliver(struct kvm_lapic *apic, int lvt_type);
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r);
+
 u64 kvm_get_apic_base(struct kvm_vcpu *vcpu);
 void kvm_set_apic_base(struct kvm_vcpu *vcpu, u64 data);
 void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,

arch/x86/kvm/x86.c +2 -0

index f91e2c9..db6db8f 100644
@@ -6269,6 +6269,7 @@ int kvm_arch_init_vm(struct kvm *kvm, unsigned long type)
 	set_bit(KVM_USERSPACE_IRQ_SOURCE_ID, &kvm->arch.irq_sources_bitmap);
 
 	raw_spin_lock_init(&kvm->arch.tsc_write_lock);
+	mutex_init(&kvm->arch.apic_map_lock);
 
 	return 0;
 }

@@ -6319,6 +6320,7 @@ void kvm_arch_destroy_vm(struct kvm *kvm)
 		put_page(kvm->arch.apic_access_page);
 	if (kvm->arch.ept_identity_pagetable)
 		put_page(kvm->arch.ept_identity_pagetable);
+	kfree(kvm->arch.apic_map);
 }
 
 void kvm_arch_free_memslot(struct kvm_memory_slot *free,

virt/kvm/irq_comm.c +6 -2

index 7118be0..3ca89c4 100644
@@ -68,8 +68,13 @@ int kvm_irq_delivery_to_apic(struct kvm *kvm, struct kvm_lapic *src,
 	struct kvm_vcpu *vcpu, *lowest = NULL;
 
 	if (irq->dest_mode == 0 && irq->dest_id == 0xff &&
-			kvm_is_dm_lowest_prio(irq))
+			kvm_is_dm_lowest_prio(irq)) {
 		printk(KERN_INFO "kvm: apic: phys broadcast and lowest prio\n");
+		irq->delivery_mode = APIC_DM_FIXED;
+	}
+
+	if (kvm_irq_delivery_to_apic_fast(kvm, src, irq, &r))
+		return r;
 
 	kvm_for_each_vcpu(i, vcpu, kvm) {
 		if (!kvm_apic_present(vcpu))
--

Gleb.

Quoted 11 lines

Quoted 11 lines

Quoted 10 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

Quoted 3 lines

Quoted 1 line

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 10 lines

Quoted 9 lines

The kfree_rcu() implementation cannot really
decide what to do here, especially given that it is callable with irqs disabled.

The usual approach is to keep a per-CPU counter and count it down from some number for each kfree_rcu(). When it reaches zero, invoke synchronize_rcu() as well as kfree_rcu(), and then reset it to the "some number" mentioned above.

Quoted 8 lines

It is a bit of a concern for me that this will hurt worst-case latency for realtime guests. In our case, we return error and this will fall back on not allocating memory and using slow all-CPU scan. One possible scheme that relies on this is:
- increment an atomic counter, per vcpu. If above threshold -> return with error
- call_rcu (+ barrier vcpu destruct)
- within callback decrement an atomic counter

That certainly is a possibility, but...

Quoted 4 lines

Quoted 3 lines

In theory, I could create an API that did this. In practice, I have no idea how to choose the number -- much depends on the size of the object being freed, for example.

Quoted 1 line

We could pass an object size, no problem :)

... before putting too much additional effort into possible solutions, why not force the problem to occur and see what actually happens? We would then be in a much better position to work out what should be done.

Quoted 11 lines · Paul E. McKenney

Quoted 11 lines

Quoted 11 lines

Quoted 10 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

Quoted 5 lines

Quoted 3 lines

Quoted 1 line

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Not much more than a few hundred thousand per second per process (normal operation is zero).

Quoted 25 lines

Quoted 10 lines

Quoted 9 lines

The kfree_rcu() implementation cannot really
decide what to do here, especially given that it is callable with irqs disabled.

The usual approach is to keep a per-CPU counter and count it down from some number for each kfree_rcu(). When it reaches zero, invoke synchronize_rcu() as well as kfree_rcu(), and then reset it to the "some number" mentioned above.

Quoted 8 lines

It is a bit of a concern for me that this will hurt worst-case latency for realtime guests. In our case, we return error and this will fall back on not allocating memory and using slow all-CPU scan. One possible scheme that relies on this is:
- increment an atomic counter, per vcpu. If above threshold -> return with error
- call_rcu (+ barrier vcpu destruct)
- within callback decrement an atomic counter

That certainly is a possibility, but...

Quoted 4 lines

Quoted 3 lines

In theory, I could create an API that did this. In practice, I have no idea how to choose the number -- much depends on the size of the object being freed, for example.

Quoted 5 lines

Quoted 1 line

We could pass an object size, no problem :)

... before putting too much additional effort into possible solutions, why not force the problem to occur and see what actually happens? We would then be in a much better position to work out what should be done.

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

Quoted 17 lines · Gleb Natapov

Quoted 16 lines · Avi Kivity

Quoted 15 lines · Paul E. McKenney

Quoted 14 lines

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

Quoted 6 lines

Quoted 5 lines

Quoted 1 line

How many kfree_rcu()s per second can a given user cause to happen?

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Ok, thanks.

Signature · 1 line

error compiling committee.c: too many arguments to function

Quoted 20 lines · Avi Kivity

Quoted 19 lines · Gleb Natapov

Quoted 18 lines · Avi Kivity

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 8 lines

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 7 lines

Quoted 4 lines

Quoted 3 lines

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Because ftrace buffer overflows :) With bigger buffer I get 169940.

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Quoted 5 lines

Ok, thanks.

Signature · 1 line

error compiling committee.c: too many arguments to function

--
Gleb.

Quoted 21 lines · Gleb Natapov

Quoted 20 lines · Avi Kivity

Quoted 19 lines · Gleb Natapov

Quoted 18 lines · Avi Kivity

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 8 lines

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

Quoted 3 lines

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Because ftrace buffer overflows :) With bigger buffer I get 169940.

Ah, good, should not be a problem. In contrast, if you ran kfree_rcu() in a tight loop, you could probably do in excess of 100M per CPU per second. Now -that- might be a problem.

Well, it -might- be a problem if you somehow figured out how to allocate memory that quickly in a steady-state manner. ;-)

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Very good -- the checks in __call_rcu(), which is common code invoked by kfree_rcu(), seem to be doing their job, then. These do keep a per-CPU counter, which can be adjusted via rcutree.blimit, which defaults to taking evasive action if more than 10K callbacks are waiting on a given CPU.

My concern was that you might be overrunning that limit in way less than a grace period (as in about a hundred microseconds. My concern was of course unfounded -- you take several grace periods in push 10K callbacks through.

Thanx, Paul

Quoted 9 lines

Quoted 5 lines

Ok, thanks.

Signature · 1 line

error compiling committee.c: too many arguments to function

--
Gleb.

Quoted 49 lines · Paul E. McKenney

Quoted 21 lines · Gleb Natapov

Quoted 20 lines · Avi Kivity

Quoted 19 lines · Gleb Natapov

Quoted 18 lines · Avi Kivity

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 8 lines

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

Quoted 3 lines

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Because ftrace buffer overflows :) With bigger buffer I get 169940.

Ah, good, should not be a problem. In contrast, if you ran kfree_rcu() in a tight loop, you could probably do in excess of 100M per CPU per second. Now -that- might be a problem.

Well, it -might- be a problem if you somehow figured out how to allocate memory that quickly in a steady-state manner. ;-)

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Very good -- the checks in __call_rcu(), which is common code invoked by kfree_rcu(), seem to be doing their job, then. These do keep a per-CPU counter, which can be adjusted via rcutree.blimit, which defaults to taking evasive action if more than 10K callbacks are waiting on a given CPU.

Quoted 6 lines

My concern was that you might be overrunning that limit in way less than a grace period (as in about a hundred microseconds. My concern was of course unfounded -- you take several grace periods in push 10K callbacks through.

Thanx, Paul

Gleb noted that Documentation/RCU/checklist.txt has this text:

An especially important property of the synchronize_rcu() primitive is that it automatically self-limits: if grace periods are delayed for whatever reason, then the synchronize_rcu() primitive will correspondingly delay updates. In contrast, code using call_rcu() should explicitly limit update rate in cases where grace periods are delayed, as failing to do so can result in excessive realtime latencies or even OOM conditions.

If call_rcu is self-limiting maybe this should be documented ...

Quoted 67 lines · Michael S. Tsirkin

Quoted 49 lines · Paul E. McKenney

Quoted 21 lines · Gleb Natapov

Quoted 20 lines · Avi Kivity

Quoted 19 lines · Gleb Natapov

Quoted 18 lines · Avi Kivity

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 8 lines

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

Quoted 3 lines

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Because ftrace buffer overflows :) With bigger buffer I get 169940.

Ah, good, should not be a problem. In contrast, if you ran kfree_rcu() in a tight loop, you could probably do in excess of 100M per CPU per second. Now -that- might be a problem.

Well, it -might- be a problem if you somehow figured out how to allocate memory that quickly in a steady-state manner. ;-)

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Very good -- the checks in __call_rcu(), which is common code invoked by kfree_rcu(), seem to be doing their job, then. These do keep a per-CPU counter, which can be adjusted via rcutree.blimit, which defaults to taking evasive action if more than 10K callbacks are waiting on a given CPU.

Quoted 6 lines

My concern was that you might be overrunning that limit in way less than a grace period (as in about a hundred microseconds. My concern was of course unfounded -- you take several grace periods in push 10K callbacks through.

Thanx, Paul

Gleb noted that Documentation/RCU/checklist.txt has this text:

An especially important property of the synchronize_rcu() primitive is that it automatically self-limits: if grace periods are delayed for whatever reason, then the synchronize_rcu() primitive will correspondingly delay updates. In contrast, code using call_rcu() should explicitly limit update rate in cases where grace periods are delayed, as failing to do so can result in excessive realtime latencies or even OOM conditions.

Quoted 1 line

If call_rcu is self-limiting maybe this should be documented ...

It would be more accurate to say that takes has some measures to limit the damage -- you can overwhelm these measures if you try hard enough.

And I guess I could say something to that effect. ;-)

Thanx, Paul

Quoted 68 lines · Paul E. McKenney

Quoted 67 lines · Michael S. Tsirkin

Quoted 49 lines · Paul E. McKenney

Quoted 21 lines · Gleb Natapov

Quoted 20 lines · Avi Kivity

Quoted 19 lines · Gleb Natapov

Quoted 18 lines · Avi Kivity

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 8 lines

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

Quoted 3 lines

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Because ftrace buffer overflows :) With bigger buffer I get 169940.

Ah, good, should not be a problem. In contrast, if you ran kfree_rcu() in a tight loop, you could probably do in excess of 100M per CPU per second. Now -that- might be a problem.

Well, it -might- be a problem if you somehow figured out how to allocate memory that quickly in a steady-state manner. ;-)

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Very good -- the checks in __call_rcu(), which is common code invoked by kfree_rcu(), seem to be doing their job, then. These do keep a per-CPU counter, which can be adjusted via rcutree.blimit, which defaults to taking evasive action if more than 10K callbacks are waiting on a given CPU.

Quoted 6 lines

My concern was that you might be overrunning that limit in way less than a grace period (as in about a hundred microseconds. My concern was of course unfounded -- you take several grace periods in push 10K callbacks through.

Thanx, Paul

Gleb noted that Documentation/RCU/checklist.txt has this text:

An especially important property of the synchronize_rcu() primitive is that it automatically self-limits: if grace periods are delayed for whatever reason, then the synchronize_rcu() primitive will correspondingly delay updates. In contrast, code using call_rcu() should explicitly limit update rate in cases where grace periods are delayed, as failing to do so can result in excessive realtime latencies or even OOM conditions.

Quoted 5 lines

Quoted 1 line

If call_rcu is self-limiting maybe this should be documented ...

It would be more accurate to say that takes has some measures to limit the damage -- you can overwhelm these measures if you try hard enough.

The question is: Is it safe to have a call_rcu() without any additional rate limiting on user triggerable code path?

Quoted 3 lines

And I guess I could say something to that effect. ;-)

Thanx, Paul

--
Gleb.

Quoted 74 lines · Gleb Natapov

Quoted 73 lines · Paul E. McKenney

Quoted 67 lines · Michael S. Tsirkin

Quoted 49 lines · Paul E. McKenney

Quoted 21 lines · Gleb Natapov

Quoted 20 lines · Avi Kivity

Quoted 19 lines · Gleb Natapov

Quoted 18 lines · Avi Kivity

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace,
any number of times; we allocate
a 2K chunk of memory that is later freed by
kfree_rcu.

Quoted 8 lines

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while
lots of memory is queued up in this way?
If yes is this a generic problem with kfree_rcu
that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

Quoted 3 lines

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Because ftrace buffer overflows :) With bigger buffer I get 169940.

Ah, good, should not be a problem. In contrast, if you ran kfree_rcu() in a tight loop, you could probably do in excess of 100M per CPU per second. Now -that- might be a problem.

Well, it -might- be a problem if you somehow figured out how to allocate memory that quickly in a steady-state manner. ;-)

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Very good -- the checks in __call_rcu(), which is common code invoked by kfree_rcu(), seem to be doing their job, then. These do keep a per-CPU counter, which can be adjusted via rcutree.blimit, which defaults to taking evasive action if more than 10K callbacks are waiting on a given CPU.

Quoted 6 lines

My concern was that you might be overrunning that limit in way less than a grace period (as in about a hundred microseconds. My concern was of course unfounded -- you take several grace periods in push 10K callbacks through.

Thanx, Paul

Gleb noted that Documentation/RCU/checklist.txt has this text:

An especially important property of the synchronize_rcu() primitive is that it automatically self-limits: if grace periods are delayed for whatever reason, then the synchronize_rcu() primitive will correspondingly delay updates. In contrast, code using call_rcu() should explicitly limit update rate in cases where grace periods are delayed, as failing to do so can result in excessive realtime latencies or even OOM conditions.

Quoted 1 line

If call_rcu is self-limiting maybe this should be documented ...

It would be more accurate to say that takes has some measures to limit the damage -- you can overwhelm these measures if you try hard enough.

Quoted 2 lines

The question is: Is it safe to have a call_rcu() without any additional rate limiting on user triggerable code path?

That would be a good way to allow users to run your system out of memory, especially on systems with limited memory. (If you have several GB of free space, you might be OK.)

Quoted 75 lines · Paul E. McKenney

Quoted 74 lines · Gleb Natapov

Quoted 73 lines · Paul E. McKenney

Quoted 67 lines · Michael S. Tsirkin

Quoted 49 lines · Paul E. McKenney

Quoted 21 lines · Gleb Natapov

Quoted 20 lines · Avi Kivity

Quoted 19 lines · Gleb Natapov

Quoted 18 lines · Avi Kivity

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace,
any number of times; we allocate
a 2K chunk of memory that is later freed by
kfree_rcu.

Quoted 8 lines

Quoted 6 lines

Is there a risk of DOS if RCU is delayed while
lots of memory is queued up in this way?
If yes is this a generic problem with kfree_rcu
that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

Quoted 3 lines

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Because ftrace buffer overflows :) With bigger buffer I get 169940.

Ah, good, should not be a problem. In contrast, if you ran kfree_rcu() in a tight loop, you could probably do in excess of 100M per CPU per second. Now -that- might be a problem.

Well, it -might- be a problem if you somehow figured out how to allocate memory that quickly in a steady-state manner. ;-)

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Very good -- the checks in __call_rcu(), which is common code invoked by kfree_rcu(), seem to be doing their job, then. These do keep a per-CPU counter, which can be adjusted via rcutree.blimit, which defaults to taking evasive action if more than 10K callbacks are waiting on a given CPU.

Quoted 6 lines

My concern was that you might be overrunning that limit in way less than a grace period (as in about a hundred microseconds. My concern was of course unfounded -- you take several grace periods in push 10K callbacks through.

Thanx, Paul

Gleb noted that Documentation/RCU/checklist.txt has this text:

An especially important property of the synchronize_rcu() primitive is that it automatically self-limits: if grace periods are delayed for whatever reason, then the synchronize_rcu() primitive will correspondingly delay updates. In contrast, code using call_rcu() should explicitly limit update rate in cases where grace periods are delayed, as failing to do so can result in excessive realtime latencies or even OOM conditions.

Quoted 1 line

If call_rcu is self-limiting maybe this should be documented ...

It would be more accurate to say that takes has some measures to limit the damage -- you can overwhelm these measures if you try hard enough.

Quoted 7 lines

Quoted 2 lines

The question is: Is it safe to have a call_rcu() without any additional rate limiting on user triggerable code path?

That would be a good way to allow users to run your system out of memory, especially on systems with limited memory. (If you have several GB of free space, you might be OK.)

Thanks! Got it.

Quoted 8 lines

Quoted 7 lines

Quoted 2 lines

The question is: Is it safe to have a call_rcu() without any additional rate limiting on user triggerable code path?

That would be a good way to allow users to run your system out of memory, especially on systems with limited memory. (If you have several GB of free space, you might be OK.)

Thanks! Got it.

Does the following help?

Thanx, Paul

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

rcu: Document call_rcu() safety mechanisms and limitations

The call_rcu() family of primitives will take action to accelerate grace periods when the number of callbacks pending on a given CPU becomes excessive. Although this safety mechanism can be useful, it is no substitute for users of call_rcu() having rate-limit controls in place. This commit adds this nuance to the documentation.

Reported-by "Michael S. Tsirkin" <[email protected]>

Reported-by Gleb Natapov <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Documentation/RCU/checklist.txt +14 -6

index 91266193b8f4..5733e31836b5 100644
@@ -256,10 +256,11 @@ over a rather long period of time, but improvements are always welcome!
 		variations on this theme.
 
 	b.	Limiting update rate.  For example, if updates occur only
-		once per hour, then no explicit rate limiting is required,
-		unless your system is already badly broken.  The dcache
-		subsystem takes this approach -- updates are guarded
-		by a global lock, limiting their rate.
+		once per hour, then no explicit rate limiting is
+		required, unless your system is already badly broken.
+		Older versions of the dcache subsystem takes this
+		approach -- updates were guarded by a global lock,
+		limiting their rate.
 
 	c.	Trusted update -- if updates can only be done manually by
 		superuser or some other trusted user, then it might not

@@ -268,7 +269,8 @@ over a rather long period of time, but improvements are always welcome!
 		the machine.
 
 	d.	Use call_rcu_bh() rather than call_rcu(), in order to take
-		advantage of call_rcu_bh()'s faster grace periods.
+		advantage of call_rcu_bh()'s faster grace periods.  (This
+		is only a partial solution, though.)
 
 	e.	Periodically invoke synchronize_rcu(), permitting a limited
 		number of updates per grace period.

@@ -276,6 +278,13 @@ over a rather long period of time, but improvements are always welcome!
 	The same cautions apply to call_rcu_bh(), call_rcu_sched(),
 	call_srcu(), and kfree_rcu().
 
+	Note that although these primitives do take action to avoid memory
+	exhaustion when any given CPU has too many callbacks, a determined
+	user could still exhaust memory.  This is especially the case
+	if a system with a large number of CPUs has been configured to
+	offload all of its RCU callbacks onto a single CPU, or if the
+	system has relatively little free memory.
+
 9.	All RCU list-traversal primitives, which include
 	rcu_dereference(), list_for_each_entry_rcu(), and
 	list_for_each_safe_rcu(), must be either within an RCU read-side
 
--

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 49 lines · Paul E. McKenney

Quoted 21 lines · Gleb Natapov

Quoted 20 lines · Avi Kivity

Quoted 19 lines · Gleb Natapov

Quoted 18 lines · Avi Kivity

Quoted 16 lines · Paul E. McKenney

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 8 lines

Quoted 6 lines

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way? If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk.

In our case it's a 2K object. Is it a practical risk?

How many kfree_rcu()s per second can a given user cause to happen?

Quoted 8 lines

Quoted 7 lines

Quoted 4 lines

Quoted 3 lines

Not much more than a few hundred thousand per second per process (normal operation is zero).

I managed to do 21466 per second.

Strange, why so slow?

Because ftrace buffer overflows :) With bigger buffer I get 169940.

Ah, good, should not be a problem. In contrast, if you ran kfree_rcu() in a tight loop, you could probably do in excess of 100M per CPU per second. Now -that- might be a problem.

Well, it -might- be a problem if you somehow figured out how to allocate memory that quickly in a steady-state manner. ;-)

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 3 lines

Good idea. Michael, is should be easy to modify kvm-unit-tests to write to the APIC ID register in a loop.

I did. Memory consumption does not grow on otherwise idle host.

Very good -- the checks in __call_rcu(), which is common code invoked by kfree_rcu(), seem to be doing their job, then. These do keep a per-CPU counter, which can be adjusted via rcutree.blimit, which defaults to taking evasive action if more than 10K callbacks are waiting on a given CPU.

Quoted 6 lines

My concern was that you might be overrunning that limit in way less than a grace period (as in about a hundred microseconds. My concern was of course unfounded -- you take several grace periods in push 10K callbacks through.

Thanx, Paul

Gleb noted that Documentation/RCU/checklist.txt has this text:

An especially important property of the synchronize_rcu() primitive is that it automatically self-limits: if grace periods are delayed for whatever reason, then the synchronize_rcu() primitive will correspondingly delay updates. In contrast, code using call_rcu() should explicitly limit update rate in cases where grace periods are delayed, as failing to do so can result in excessive realtime latencies or even OOM conditions.

If call_rcu is self-limiting maybe this should be documented ...

Quoted 144 lines · Michael S. Tsirkin

Quoted 6 lines · Gleb Natapov

Most interrupt are delivered to only one vcpu. Use pre-build tables to find interrupt destination instead of looping through all vcpus. In case of logical mode loop only through vcpus in a logical cluster irq is sent to.

Signed-off-by Gleb Natapov <[email protected]>

Added Paul just to make sure we are using RCU correctly. Paul could you pls answer the question below?

Quoted 116 lines

---
Changelog:

- v1->v2
* fix race Avi noticed
* rcu_read_lock() out of the block as per Avi
* fix rcu issues pointed to by MST. All but one. Still use call_rcu(). Do not think this is serious issue. If it is should be solved by RCU subsystem.
* Fix phys_map overflow pointed to by MST
* recalculate_apic_map() does not return error any more.
* add optimization for low prio logical mode with one cpu as dst (it happens)

I did not rewrote kvm_irq_delivery_to_apic_fast() MST way since my way looks cleaner to me.

arch/x86/include/asm/kvm_host.h +10 -0

index 64adb61..3ba8951 100644
@@ -511,6 +511,14 @@ struct kvm_arch_memory_slot {
 	struct kvm_lpage_info *lpage_info[KVM_NR_PAGE_SIZES - 1];
 };
 
+struct kvm_apic_map {
+	struct rcu_head rcu;
+	bool flat;
+	u8 ldr_bits;
+	struct kvm_lapic *phys_map[256];
+	struct kvm_lapic *logical_map[16][16];
+};
+
 struct kvm_arch {
 	unsigned int n_used_mmu_pages;
 	unsigned int n_requested_mmu_pages;

@@ -528,6 +536,8 @@ struct kvm_arch {
 	struct kvm_ioapic *vioapic;
 	struct kvm_pit *vpit;
 	int vapics_in_nmi_mode;
+	struct kvm_apic_map *apic_map;
+	struct mutex apic_map_lock;
 
 	unsigned int tss_addr;
 	struct page *apic_access_page;

arch/x86/kvm/lapic.c +58 -0

index 07ad628..06672e8 100644
@@ -139,11 +139,92 @@ static inline int apic_enabled(struct kvm_lapic *apic)
 	(LVT_MASK | APIC_MODE_MASK | APIC_INPUT_POLARITY | \
 	 APIC_LVT_REMOTE_IRR | APIC_LVT_LEVEL_TRIGGER)
 
+static inline int apic_x2apic_mode(struct kvm_lapic *apic)
+{
+	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
+}
+
 static inline int kvm_apic_id(struct kvm_lapic *apic)
 {
 	return (kvm_apic_get_reg(apic, APIC_ID) >> 24) & 0xff;
 }
 
+static void kvm_apic_get_logical_id(u32 ldr, bool flat, u8 ldr_bits,
+		u16 *cid, u16 *lid)
+{
+	if (ldr_bits == 32) {
+		*cid = ldr >> 16;
+		*lid = ldr & 0xffff;
+	} else {
+		ldr = GET_APIC_LOGICAL_ID(ldr);
+
+		if (flat) {
+			*cid = 0;
+			*lid = ldr;
+		} else {
+			*cid = ldr >> 4;
+			*lid = ldr & 0xf;
+		}
+	}
+}
+
+static inline void recalculate_apic_map(struct kvm *kvm)
+{
+	struct kvm_apic_map *new, *old = NULL;
+	struct kvm_vcpu *vcpu;
+	int i;
+
+	new = kzalloc(sizeof(struct kvm_apic_map), GFP_KERNEL);
+
+	mutex_lock(&kvm->arch.apic_map_lock);
+
+	if (!new)
+		goto out;
+
+	new->ldr_bits = 8;
+	new->flat = true;
+	kvm_for_each_vcpu(i, vcpu, kvm) {
+		u16 cid, lid;
+		struct kvm_lapic *apic = vcpu->arch.apic;
+
+		if (!kvm_apic_present(vcpu))
+			continue;
+
+		if (apic_x2apic_mode(apic)) {
+			new->ldr_bits = 32;
+			new->flat = false;
+		} else if (kvm_apic_sw_enabled(apic) && new->flat &&
+				kvm_apic_get_reg(apic, APIC_DFR) == APIC_DFR_CLUSTER)
+			new->flat = false;
+
+		new->phys_map[kvm_apic_id(apic)] = apic;
+		kvm_apic_get_logical_id(kvm_apic_get_reg(apic, APIC_LDR),
+				new->flat, new->ldr_bits, &cid, &lid);
+
+		if (lid)

arch/x86/kvm/lapic.c static inline int apic_enabled(struct kvm_lapic *apic) · line 214

Quoted 10 lines

arch/x86/kvm/lapic.c +10 -0

+			new->logical_map[cid][ffs(lid) - 1] = apic;
+	}
+out:
+	old = kvm->arch.apic_map;
+	rcu_assign_pointer(kvm->arch.apic_map, new);
+	mutex_unlock(&kvm->arch.apic_map_lock);
+
+	if (old)
+		kfree_rcu(old, rcu);
+}

Paul, I'd like to check something with you here:
this function can be triggered by userspace, any number of times; we allocate
a 2K chunk of memory that is later freed by kfree_rcu.

Quoted 4 lines

Is there a risk of DOS if RCU is delayed while lots of memory is queued up in this way?
If yes is this a generic problem with kfree_rcu that should be addressed in core kernel?

There is indeed a risk. The kfree_rcu() implementation cannot really decide what to do here, especially given that it is callable with irqs disabled.

The usual approach is to keep a per-CPU counter and count it down from some number for each kfree_rcu(). When it reaches zero, invoke synchronize_rcu() as well as kfree_rcu(), and then reset it to the "some number" mentioned above.

In theory, I could create an API that did this. In practice, I have no idea how to choose the number -- much depends on the size of the object being freed, for example.

The RCU usage looks otherwise sane at first glance.

Thanx, Paul

Quoted 239 lines

Thanks!

Quoted 236 lines

arch/x86/kvm/lapic.c +97 -12

+
+static inline void kvm_apic_set_id(struct kvm_lapic *apic, u8 id)
+{
+	apic_set_reg(apic, APIC_ID, id << 24);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
+static inline void kvm_apic_set_ldr(struct kvm_lapic *apic, u32 id)
+{
+	apic_set_reg(apic, APIC_LDR, id);
+	recalculate_apic_map(apic->vcpu->kvm);
+}
+
 static inline int apic_lvt_enabled(struct kvm_lapic *apic, int lvt_type)
 {
 	return !(kvm_apic_get_reg(apic, lvt_type) & APIC_LVT_MASKED);

@@ -193,11 +274,6 @@ void kvm_apic_set_version(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_LVR, v);
 }
 
-static inline int apic_x2apic_mode(struct kvm_lapic *apic)
-{
-	return apic->vcpu->arch.apic_base & X2APIC_ENABLE;
-}
-
 static const unsigned int apic_lvt_mask[APIC_LVT_NUM] = {
 	LVT_MASK ,      /* part LVTT mask, timer mode mask added at runtime */
 	LVT_MASK | APIC_MODE_MASK,	/* LVTTHMR */

@@ -477,6 +553,79 @@ int kvm_apic_match_dest(struct kvm_vcpu *vcpu, struct kvm_lapic *source,
 	return result;
 }
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r)
+{
+	struct kvm_apic_map *map;
+	unsigned long bitmap = 1;
+	struct kvm_lapic **dst;
+	int i;
+
+	*r = -1;
+
+	if (irq->shorthand == APIC_DEST_SELF) {
+		*r = kvm_apic_set_irq(src->vcpu, irq);
+		return true;
+	}
+
+	if (irq->shorthand)
+		return false;
+
+	rcu_read_lock();
+	map = rcu_dereference(kvm->arch.apic_map);
+
+	if (!map) {
+		rcu_read_unlock();
+		return false;
+	}
+
+	if (irq->dest_mode == 0) { /* physical mode */
+		if (irq->delivery_mode == APIC_DM_LOWEST ||
+				irq->dest_id == 0xff) {
+			rcu_read_unlock();
+			return false;
+		}
+		dst = &map->phys_map[irq->dest_id & 0xff];
+	} else {
+		u16 cid, lid;
+		u32 mda = irq->dest_id;
+
+		if (map->ldr_bits == 8)
+			mda <<= 24;
+
+		kvm_apic_get_logical_id(mda, map->flat, map->ldr_bits,
+				&cid, &lid);
+		dst = map->logical_map[cid];
+
+		bitmap = lid;
+		if (irq->delivery_mode == APIC_DM_LOWEST &&
+				hweight_long(bitmap) > 1) {
+			int l = -1;
+			for_each_set_bit(i, &bitmap, 16) {
+				if (!dst[i])
+					continue;
+				if (l < 0)
+					l = i;
+				else if (kvm_apic_compare_prio(dst[i]->vcpu, dst[l]->vcpu) < 0)
+					l = i;
+			}
+
+			bitmap = (l >= 0) ? 1 << l : 0;
+		}
+	}
+
+	for_each_set_bit(i, &bitmap, 16) {
+		if (!dst[i])
+			continue;
+		if (*r < 0)
+			*r = 0;
+		*r += kvm_apic_set_irq(dst[i]->vcpu, irq);
+	}
+
+	rcu_read_unlock();
+	return true;
+}
+
 /*
  * Add a pending IRQ into lapic.
  * Return 1 if successfully added and 0 if discarded.

@@ -880,7 +1029,7 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 	switch (reg) {
 	case APIC_ID:		/* Local APIC ID */
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_ID, val);
+			kvm_apic_set_id(apic, val >> 24);
 		else
 			ret = 1;
 		break;

@@ -896,15 +1045,16 @@ static int apic_reg_write(struct kvm_lapic *apic, u32 reg, u32 val)
 
 	case APIC_LDR:
 		if (!apic_x2apic_mode(apic))
-			apic_set_reg(apic, APIC_LDR, val & APIC_LDR_MASK);
+			kvm_apic_set_ldr(apic, val & APIC_LDR_MASK);
 		else
 			ret = 1;
 		break;
 
 	case APIC_DFR:
-		if (!apic_x2apic_mode(apic))
+		if (!apic_x2apic_mode(apic)) {
 			apic_set_reg(apic, APIC_DFR, val | 0x0FFFFFFF);
-		else
+			recalculate_apic_map(apic->vcpu->kvm);
+		} else
 			ret = 1;
 		break;
 

@@ -1135,6 +1285,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 			static_key_slow_dec_deferred(&apic_hw_disabled);
 		else
 			static_key_slow_inc(&apic_hw_disabled.key);
+		recalculate_apic_map(vcpu->kvm);
 	}
 
 	if (!kvm_vcpu_is_bsp(apic->vcpu))

@@ -1144,7 +1295,7 @@ void kvm_lapic_set_base(struct kvm_vcpu *vcpu, u64 value)
 	if (apic_x2apic_mode(apic)) {
 		u32 id = kvm_apic_id(apic);
 		u32 ldr = ((id & ~0xf) << 16) | (1 << (id & 0xf));
-		apic_set_reg(apic, APIC_LDR, ldr);
+		kvm_apic_set_ldr(apic, ldr);
 	}
 	apic->base_address = apic->vcpu->arch.apic_base &
 			     MSR_IA32_APICBASE_BASE;

@@ -1169,7 +1320,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	/* Stop the timer in case it's a reset to an active apic */
 	hrtimer_cancel(&apic->lapic_timer.timer);
 
-	apic_set_reg(apic, APIC_ID, vcpu->vcpu_id << 24);
+	kvm_apic_set_id(apic, (u8)vcpu->vcpu_id);
 	kvm_apic_set_version(apic->vcpu);
 
 	for (i = 0; i < APIC_LVT_NUM; i++)

@@ -1180,7 +1331,7 @@ void kvm_lapic_reset(struct kvm_vcpu *vcpu)
 	apic_set_reg(apic, APIC_DFR, 0xffffffffU);
 	apic_set_spiv(apic, 0xff);
 	apic_set_reg(apic, APIC_TASKPRI, 0);
-	apic_set_reg(apic, APIC_LDR, 0);
+	kvm_apic_set_ldr(apic, 0);
 	apic_set_reg(apic, APIC_ESR, 0);
 	apic_set_reg(apic, APIC_ICR, 0);
 	apic_set_reg(apic, APIC_ICR2, 0);

@@ -1398,6 +1549,8 @@ void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,
 	/* set SPIV separately to get count of SW disabled APICs right */
 	apic_set_spiv(apic, *((u32 *)(s->regs + APIC_SPIV)));
 	memcpy(vcpu->arch.apic->regs, s->regs, sizeof *s);
+	/* call kvm_apic_set_id() to put apic into apic_map */
+	kvm_apic_set_id(apic, kvm_apic_id(apic));
 	kvm_apic_set_version(vcpu);
 
 	apic_update_ppr(apic);

arch/x86/kvm/lapic.h +3 -0

index 615a8b0..e5ebf9f 100644
@@ -52,6 +52,9 @@ int kvm_apic_match_logical_addr(struct kvm_lapic *apic, u8 mda);
 int kvm_apic_set_irq(struct kvm_vcpu *vcpu, struct kvm_lapic_irq *irq);
 int kvm_apic_local_deliver(struct kvm_lapic *apic, int lvt_type);
 
+bool kvm_irq_delivery_to_apic_fast(struct kvm *kvm, struct kvm_lapic *src,
+		struct kvm_lapic_irq *irq, int *r);
+
 u64 kvm_get_apic_base(struct kvm_vcpu *vcpu);
 void kvm_set_apic_base(struct kvm_vcpu *vcpu, u64 data);
 void kvm_apic_post_state_restore(struct kvm_vcpu *vcpu,

arch/x86/kvm/x86.c +2 -0

index f91e2c9..db6db8f 100644
@@ -6269,6 +6269,7 @@ int kvm_arch_init_vm(struct kvm *kvm, unsigned long type)
 	set_bit(KVM_USERSPACE_IRQ_SOURCE_ID, &kvm->arch.irq_sources_bitmap);
 
 	raw_spin_lock_init(&kvm->arch.tsc_write_lock);
+	mutex_init(&kvm->arch.apic_map_lock);
 
 	return 0;
 }

@@ -6319,6 +6320,7 @@ void kvm_arch_destroy_vm(struct kvm *kvm)
 		put_page(kvm->arch.apic_access_page);
 	if (kvm->arch.ept_identity_pagetable)
 		put_page(kvm->arch.ept_identity_pagetable);
+	kfree(kvm->arch.apic_map);
 }
 
 void kvm_arch_free_memslot(struct kvm_memory_slot *free,

virt/kvm/irq_comm.c +6 -2

index 7118be0..3ca89c4 100644
@@ -68,8 +68,13 @@ int kvm_irq_delivery_to_apic(struct kvm *kvm, struct kvm_lapic *src,
 	struct kvm_vcpu *vcpu, *lowest = NULL;
 
 	if (irq->dest_mode == 0 && irq->dest_id == 0xff &&
-			kvm_is_dm_lowest_prio(irq))
+			kvm_is_dm_lowest_prio(irq)) {
 		printk(KERN_INFO "kvm: apic: phys broadcast and lowest prio\n");
+		irq->delivery_mode = APIC_DM_FIXED;
+	}
+
+	if (kvm_irq_delivery_to_apic_fast(kvm, src, irq, &r))
+		return r;
 
 	kvm_for_each_vcpu(i, vcpu, kvm) {
 		if (!kvm_apic_present(vcpu))
--

Gleb.