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.

Signed-off-by: Gleb Natapov <gleb@redhat.com>
Acked-by: Michael S. Tsirkin <mst@redhat.com>
Signed-off-by: Avi Kivity <avi@redhat.com>

5 files changed, 199 insertions, 13 deletions

diff --git a/arch/x86/include/asm/kvm_host.h b/arch/x86/include/asm/kvm_host.h
index 43aeb9422839..0b902c98f279 100644
--- a/arch/x86/include/asm/kvm_host.h
+++ b/arch/x86/include/asm/kvm_host.h
@@ -525,6 +525,16 @@ struct kvm_arch_memory_slot {
         struct kvm_lpage_info *lpage_info[KVM_NR_PAGE_SIZES - 1];
 };
 
+struct kvm_apic_map {
+        struct rcu_head rcu;
+        u8 ldr_bits;
+        /* fields bellow are used to decode ldr values in different modes */
+        u32 cid_shift, cid_mask, lid_mask;
+        struct kvm_lapic *phys_map[256];
+        /* first index is cluster id second is cpu id in a cluster */
+        struct kvm_lapic *logical_map[16][16];
+};
+
 struct kvm_arch {
         unsigned int n_used_mmu_pages;
         unsigned int n_requested_mmu_pages;
@@ -542,6 +552,8 @@ struct kvm_arch {
         struct kvm_ioapic *vioapic;
         struct kvm_pit *vpit;
         int vapics_in_nmi_mode;
+        struct mutex apic_map_lock;
+        struct kvm_apic_map *apic_map;
 
         unsigned int tss_addr;
         struct page *apic_access_page;
diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
index 6f9fd633c888..c6e6b721b6ee 100644
--- a/arch/x86/kvm/lapic.c
+++ b/arch/x86/kvm/lapic.c
@@ -140,11 +140,110 @@ 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 inline u16 apic_cluster_id(struct kvm_apic_map *map, u32 ldr)
+{
+        u16 cid;
+        ldr >>= 32 - map->ldr_bits;
+        cid = (ldr >> map->cid_shift) & map->cid_mask;
+
+        BUG_ON(cid >= ARRAY_SIZE(map->logical_map));
+
+        return cid;
+}
+
+static inline u16 apic_logical_id(struct kvm_apic_map *map, u32 ldr)
+{
+        ldr >>= (32 - map->ldr_bits);
+        return ldr & map->lid_mask;
+}
+
+static 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;
+        /* flat mode is default */
+        new->cid_shift = 8;
+        new->cid_mask = 0;
+        new->lid_mask = 0xff;
+
+        kvm_for_each_vcpu(i, vcpu, kvm) {
+                struct kvm_lapic *apic = vcpu->arch.apic;
+                u16 cid, lid;
+                u32 ldr;
+
+                if (!kvm_apic_present(vcpu))
+                        continue;
+
+                /*
+                 * All APICs have to be configured in the same mode by an OS.
+                 * We take advatage of this while building logical id loockup
+                 * table. After reset APICs are in xapic/flat mode, so if we
+                 * find apic with different setting we assume this is the mode
+                 * OS wants all apics to be in; build lookup table accordingly.
+                 */
+                if (apic_x2apic_mode(apic)) {
+                        new->ldr_bits = 32;
+                        new->cid_shift = 16;
+                        new->cid_mask = new->lid_mask = 0xffff;
+                } else if (kvm_apic_sw_enabled(apic) &&
+                                !new->cid_mask /* flat mode */ &&
+                                kvm_apic_get_reg(apic, APIC_DFR) == APIC_DFR_CLUSTER) {
+                        new->cid_shift = 4;
+                        new->cid_mask = 0xf;
+                        new->lid_mask = 0xf;
+                }
+
+                new->phys_map[kvm_apic_id(apic)] = apic;
+
+                ldr = kvm_apic_get_reg(apic, APIC_LDR);
+                cid = apic_cluster_id(new, ldr);
+                lid = apic_logical_id(new, ldr);
+
+                if (lid)
+                        new->logical_map[cid][ffs(lid) - 1] = apic;
+        }
+out:
+        old = rcu_dereference_protected(kvm->arch.apic_map,
+                        lockdep_is_held(&kvm->arch.apic_map_lock));
+        rcu_assign_pointer(kvm->arch.apic_map, new);
+        mutex_unlock(&kvm->arch.apic_map_lock);
+
+        if (old)
+                kfree_rcu(old, rcu);
+}
+
+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);
@@ -194,11 +293,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 */
@@ -483,6 +577,72 @@ 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;
+        bool ret = false;
+
+        *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)
+                goto out;