[PATCH 0/3] Out-of-bounds access in kvm_recalculate_phys_map()

[PATCH 0/3] Out-of-bounds access in kvm_recalculate_phys_map()

[Michal Luczaj]

kvm_recalculate_apic_map() creates the APIC map iterating over the list of
vCPUs twice. First to find the max APIC ID and allocate a max-sized buffer,
then again, calling kvm_recalculate_phys_map() for each vCPU. This opens a
race window: value of max APIC ID can increase _after_ the buffer was
allocated.

PATCH 1/3 introduces one more if() to thwart the out-of-bounds access.
PATCH 2/3 attempts to simplify the code touched. Attempts, as I'm really
not sure if the result is actually cleaner.
PATCH 3/3 is a selftest that results in:

[   54.253315] ==================================================================
[   54.253327] BUG: KASAN: slab-out-of-bounds in kvm_recalculate_apic_map+0x3a0/0xa00 [kvm]
[   54.253431] Read of size 8 at addr ffff88814dd99218 by task recalc_apic_map/955

[   54.253431] CPU: 7 PID: 955 Comm: recalc_apic_map Not tainted 6.4.0-rc3-kasan+ #26
[   54.253431] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Arch Linux 1.16.2-1-1 04/01/2014
[   54.253431] Call Trace:
[   54.253431]  <TASK>
[   54.253431]  dump_stack_lvl+0x57/0x90
[   54.253431]  print_report+0xcf/0x640
[   54.253431]  ? _raw_spin_lock_irqsave+0x5b/0x60
[   54.253431]  ? __virt_addr_valid+0xd5/0x150
[   54.253431]  kasan_report+0xc1/0xf0
[   54.253431]  ? kvm_recalculate_apic_map+0x3a0/0xa00 [kvm]
[   54.253431]  ? kvm_recalculate_apic_map+0x3a0/0xa00 [kvm]
[   54.253431]  kvm_recalculate_apic_map+0x3a0/0xa00 [kvm]
[   54.253431]  ? kvm_can_use_hv_timer+0x60/0x60 [kvm]
[   54.253431]  ? kvm_lapic_set_base+0xae/0x4b0 [kvm]
[   54.253431]  ? kasan_set_track+0x21/0x30
[   54.253431]  kvm_apic_set_state+0x1cf/0x5b0 [kvm]
[   54.253431]  kvm_arch_vcpu_ioctl+0x1806/0x2100 [kvm]
[   54.253431]  ? preempt_notifier_unregister+0x29/0x60
[   54.253431]  ? preempt_count_sub+0x14/0xc0
[   54.253431]  ? vcpu_put+0x46/0x60 [kvm]
[   54.253431]  ? kvm_arch_vcpu_put+0x410/0x410 [kvm]
[   54.253431]  ? mark_lock+0xf4/0xce0
[   54.253431]  ? print_usage_bug.part.0+0x3b0/0x3b0
[   54.253431]  ? print_usage_bug.part.0+0x3b0/0x3b0
[   54.253431]  ? mark_lock+0xf4/0xce0
[   54.253431]  ? __lock_acquire+0x9ed/0x3210
[   54.253431]  ? lockdep_hardirqs_on_prepare+0x220/0x220
[   54.253431]  ? mark_lock+0xf4/0xce0
[   54.253431]  ? lock_acquire+0x159/0x3b0
[   54.253431]  ? lock_acquire+0x169/0x3b0
[   54.253431]  ? lock_sync+0x110/0x110
[   54.253431]  ? lock_acquire+0x169/0x3b0
[   54.253431]  ? print_usage_bug.part.0+0x3b0/0x3b0
[   54.253431]  ? mark_lock+0xf4/0xce0
[   54.253431]  ? rcu_is_watching+0x34/0x50
[   54.253431]  ? preempt_count_sub+0x14/0xc0
[   54.253431]  ? __mutex_lock+0x201/0x1040
[   54.253431]  ? kvm_vcpu_ioctl+0x1c6/0x8a0 [kvm]
[   54.253431]  ? kvm_vcpu_ioctl+0x13a/0x8a0 [kvm]
[   54.253431]  ? __mutex_lock+0x201/0x1040
[   54.253431]  ? mutex_lock_io_nested+0xe40/0xe40
[   54.253431]  ? __lock_acquire+0x9ed/0x3210
[   54.253431]  ? kvm_vcpu_ioctl+0x663/0x8a0 [kvm]
[   54.253431]  kvm_vcpu_ioctl+0x663/0x8a0 [kvm]
[   54.253431]  ? kvm_vcpu_kick+0x200/0x200 [kvm]
[   54.253431]  ? vfs_fileattr_set+0x480/0x480
[   54.253431]  ? find_held_lock+0x83/0xa0
[   54.253431]  ? ioctl_has_perm.constprop.0.isra.0+0x133/0x1f0
[   54.253431]  ? selinux_bprm_creds_for_exec+0x440/0x440
[   54.253431]  ? selinux_bprm_creds_for_exec+0x440/0x440
[   54.253431]  ? __fget_files+0x146/0x200
[   54.253431]  __x64_sys_ioctl+0xb8/0xf0
[   54.253431]  do_syscall_64+0x56/0x80
[   54.253431]  ? do_syscall_64+0x62/0x80
[   54.253431]  ? lockdep_hardirqs_on+0x7d/0x100
[   54.253431]  ? do_syscall_64+0x62/0x80
[   54.253431]  ? asm_exc_page_fault+0x22/0x30
[   54.253431]  ? lockdep_hardirqs_on+0x7d/0x100
[   54.253431]  entry_SYSCALL_64_after_hwframe+0x46/0xb0
[   54.253431] RIP: 0033:0x7f66e4dedd6f
[   54.253431] Code: 00 48 89 44 24 18 31 c0 48 8d 44 24 60 c7 04 24 10 00 00 00 48 89 44 24 08 48 8d 44 24 20 48 89 44 24 10 b8 10 00 00 00 0f 05 <89> c2 3d 00 f0 ff ff 77 18 48 8b 44 24 18 64 48 2b 04 25 28 00 00
[   54.253431] RSP: 002b:00007f66e4ce8a60 EFLAGS: 00000246 ORIG_RAX: 0000000000000010
[   54.253431] RAX: ffffffffffffffda RBX: 00007f66e4ce8ac0 RCX: 00007f66e4dedd6f
[   54.253431] RDX: 00007f66e4ce8ac0 RSI: 000000004400ae8f RDI: 0000000000000005
[   54.253431] RBP: 0000000000000005 R08: 0000000000000000 R09: 00007ffc7793e4b7
[   54.253431] R10: 00007f66e4d05c38 R11: 0000000000000246 R12: ffffffffffffff80
[   54.253431] R13: 0000000000000000 R14: 00007ffc7793e3c0 R15: 00007f66e44e9000
[   54.253431]  </TASK>

[   54.253431] Allocated by task 955:
[   54.253431]  kasan_save_stack+0x1c/0x40
[   54.253431]  kasan_set_track+0x21/0x30
[   54.253431]  __kasan_kmalloc+0x9e/0xa0
[   54.253431]  __kmalloc_node+0x61/0x160
[   54.253431]  kvm_recalculate_apic_map+0x206/0xa00 [kvm]
[   54.253431]  kvm_apic_set_state+0x1cf/0x5b0 [kvm]
[   54.253431]  kvm_arch_vcpu_ioctl+0x1806/0x2100 [kvm]
[   54.253431]  kvm_vcpu_ioctl+0x663/0x8a0 [kvm]
[   54.253431]  __x64_sys_ioctl+0xb8/0xf0
[   54.253431]  do_syscall_64+0x56/0x80
[   54.253431]  entry_SYSCALL_64_after_hwframe+0x46/0xb0

[   54.253431] The buggy address belongs to the object at ffff88814dd98000
                which belongs to the cache kmalloc-cg-4k of size 4096
[   54.253431] The buggy address is located 1256 bytes to the right of
                allocated 3376-byte region [ffff88814dd98000, ffff88814dd98d30)

[   54.253431] The buggy address belongs to the physical page:
[   54.253431] page:00000000d1f90483 refcount:1 mapcount:0 mapping:0000000000000000 index:0x0 pfn:0x14dd98
[   54.253431] head:00000000d1f90483 order:3 entire_mapcount:0 nr_pages_mapped:0 pincount:0
[   54.253431] memcg:ffff888119ce4ac1
[   54.253431] anon flags: 0x17ffffc0010200(slab|head|node=0|zone=2|lastcpupid=0x1fffff)
[   54.253431] page_type: 0xffffffff()
[   54.253431] raw: 0017ffffc0010200 ffff888100050280 0000000000000000 dead000000000001
[   54.253431] raw: 0000000000000000 0000000080040004 00000001ffffffff ffff888119ce4ac1
[   54.253431] page dumped because: kasan: bad access detected

[   54.253431] Memory state around the buggy address:
[   54.253431]  ffff88814dd99100: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
[   54.253431]  ffff88814dd99180: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
[   54.253431] >ffff88814dd99200: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
[   54.253431]                             ^
[   54.253431]  ffff88814dd99280: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
[   54.253431]  ffff88814dd99300: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
[   54.253431] ==================================================================
[   54.255939] Disabling lock debugging due to kernel taint

Michal Luczaj (3):
  KVM: x86: Fix out-of-bounds access in kvm_recalculate_phys_map()
  KVM: x86: Simplify APIC ID selection in kvm_recalculate_phys_map()
  KVM: selftests: Add test for race in kvm_recalculate_apic_map()

 arch/x86/kvm/lapic.c                          |  38 +++---
 tools/testing/selftests/kvm/Makefile          |   1 +
 .../kvm/x86_64/recalc_apic_map_race.c         | 110 ++++++++++++++++++
 3 files changed, 127 insertions(+), 22 deletions(-)
 create mode 100644 tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c

-- 
2.40.1

[PATCH 1/3] KVM: x86: Fix out-of-bounds access in kvm_recalculate_phys_map()

[Michal Luczaj]

Handle the case of vCPU addition and/or APIC enabling during the APIC map
recalculations. Check the sanity of x2APIC ID in !x2apic_format &&
apic_x2apic_mode() case.

kvm_recalculate_apic_map() creates the APIC map iterating over the list of
vCPUs twice. First to find the max APIC ID and allocate a max-sized buffer,
then again, calling kvm_recalculate_phys_map() for each vCPU. This opens a
race window: value of max APIC ID can increase _after_ the buffer was
allocated.

Signed-off-by: Michal Luczaj <mhal@rbox.co>
---
 arch/x86/kvm/lapic.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
index e542cf285b51..39b9a318d04c 100644
--- a/arch/x86/kvm/lapic.c
+++ b/arch/x86/kvm/lapic.c
@@ -265,10 +265,14 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
 		 * mapped, i.e. is aliased to multiple vCPUs.  The optimized
 		 * map requires a strict 1:1 mapping between IDs and vCPUs.
 		 */
-		if (apic_x2apic_mode(apic))
+		if (apic_x2apic_mode(apic)) {
+			if (x2apic_id > new->max_apic_id)
+				return -EINVAL;
+
 			physical_id = x2apic_id;
-		else
+		} else {
 			physical_id = xapic_id;
+		}
 
 		if (new->phys_map[physical_id])
 			return -EINVAL;
-- 
2.40.1

[PATCH 2/3] KVM: x86: Simplify APIC ID selection in kvm_recalculate_phys_map()

[Michal Luczaj]

Move the comments and condense the code.
No functional change intended.

Signed-off-by: Michal Luczaj <mhal@rbox.co>
---
Perhaps, as it was suggested by Maxim in [1], it would be a good moment to
change kvm_recalculate_phys_map() to return bool?

https://lore.kernel.org/kvm/e90e4c4bd558b9e41acea9f8ce84783e7341c9b4.camel@redhat.com/

 arch/x86/kvm/lapic.c | 42 ++++++++++++++++--------------------------
 1 file changed, 16 insertions(+), 26 deletions(-)

diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
index 39b9a318d04c..7db1c698f6da 100644
--- a/arch/x86/kvm/lapic.c
+++ b/arch/x86/kvm/lapic.c
@@ -223,10 +223,10 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
 				    struct kvm_vcpu *vcpu,
 				    bool *xapic_id_mismatch)
 {
+	bool x2format = vcpu->kvm->arch.x2apic_format;
 	struct kvm_lapic *apic = vcpu->arch.apic;
 	u32 x2apic_id = kvm_x2apic_id(apic);
 	u32 xapic_id = kvm_xapic_id(apic);
-	u32 physical_id;
 
 	/*
 	 * Deliberately truncate the vCPU ID when detecting a mismatched APIC
@@ -250,34 +250,24 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
 	 * effective APIC ID, e.g. due to the x2APIC wrap or because the guest
 	 * manually modified its xAPIC IDs, events targeting that ID are
 	 * supposed to be recognized by all vCPUs with said ID.
+	 *
+	 * For !x2apic_format disable the optimized map if the physical APIC ID
+	 * is already mapped, i.e. is aliased to multiple vCPUs.  The optimized
+	 * map requires a strict 1:1 mapping between IDs and vCPUs.
+	 *
+	 * See also kvm_apic_match_physical_addr().
 	 */
-	if (vcpu->kvm->arch.x2apic_format) {
-		/* See also kvm_apic_match_physical_addr(). */
-		if ((apic_x2apic_mode(apic) || x2apic_id > 0xff) &&
-			x2apic_id <= new->max_apic_id)
-			new->phys_map[x2apic_id] = apic;
-
-		if (!apic_x2apic_mode(apic) && !new->phys_map[xapic_id])
-			new->phys_map[xapic_id] = apic;
-	} else {
-		/*
-		 * Disable the optimized map if the physical APIC ID is already
-		 * mapped, i.e. is aliased to multiple vCPUs.  The optimized
-		 * map requires a strict 1:1 mapping between IDs and vCPUs.
-		 */
-		if (apic_x2apic_mode(apic)) {
-			if (x2apic_id > new->max_apic_id)
-				return -EINVAL;
+	if (apic_x2apic_mode(apic) || (x2format && x2apic_id > 0xff)) {
+		if (x2apic_id > new->max_apic_id ||
+		    (!x2format && new->phys_map[x2apic_id]))
+			return !x2format;
 
-			physical_id = x2apic_id;
-		} else {
-			physical_id = xapic_id;
-		}
-
-		if (new->phys_map[physical_id])
-			return -EINVAL;
+		new->phys_map[x2apic_id] = apic;
+	} else {
+		if (new->phys_map[xapic_id])
+			return !x2format;
 
-		new->phys_map[physical_id] = apic;
+		new->phys_map[xapic_id] = apic;
 	}
 
 	return 0;
-- 
2.40.1

[PATCH 3/3] KVM: selftests: Add test for race in kvm_recalculate_apic_map()

[Michal Luczaj]

Keep switching between LAPIC_MODE_X2APIC and LAPIC_MODE_DISABLED during
APIC map construction.

Signed-off-by: Michal Luczaj <mhal@rbox.co>
---
 tools/testing/selftests/kvm/Makefile          |   1 +
 .../kvm/x86_64/recalc_apic_map_race.c         | 110 ++++++++++++++++++
 2 files changed, 111 insertions(+)
 create mode 100644 tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c

diff --git a/tools/testing/selftests/kvm/Makefile b/tools/testing/selftests/kvm/Makefile
index 7a5ff646e7e7..c9b8f16fb23f 100644
--- a/tools/testing/selftests/kvm/Makefile
+++ b/tools/testing/selftests/kvm/Makefile
@@ -116,6 +116,7 @@ TEST_GEN_PROGS_x86_64 += x86_64/sev_migrate_tests
 TEST_GEN_PROGS_x86_64 += x86_64/amx_test
 TEST_GEN_PROGS_x86_64 += x86_64/max_vcpuid_cap_test
 TEST_GEN_PROGS_x86_64 += x86_64/triple_fault_event_test
+TEST_GEN_PROGS_x86_64 += x86_64/recalc_apic_map_race
 TEST_GEN_PROGS_x86_64 += access_tracking_perf_test
 TEST_GEN_PROGS_x86_64 += demand_paging_test
 TEST_GEN_PROGS_x86_64 += dirty_log_test
diff --git a/tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c b/tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c
new file mode 100644
index 000000000000..1122df858623
--- /dev/null
+++ b/tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c
@@ -0,0 +1,110 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * recalc_apic_map_race
+ *
+ * Test for a race condition in kvm_recalculate_apic_map().
+ */
+
+#include <sys/ioctl.h>
+#include <pthread.h>
+#include <time.h>
+
+#include "processor.h"
+#include "test_util.h"
+#include "kvm_util.h"
+#include "apic.h"
+
+#define TIMEOUT			5	/* seconds */
+#define STUFFING		100
+
+#define LAPIC_MODE_DISABLED	0
+#define LAPIC_MODE_X2APIC	(MSR_IA32_APICBASE_ENABLE | X2APIC_ENABLE)
+#define MAX_XAPIC_ID		0xff
+
+static int add_vcpu(struct kvm_vm *vm, long id)
+{
+	int vcpu = __vm_ioctl(vm, KVM_CREATE_VCPU, (void *)id);
+
+	static struct {
+		struct kvm_cpuid2 head;
+		struct kvm_cpuid_entry2 entry;
+	} cpuid = {
+		.head.nent = 1,
+		/* X86_FEATURE_X2APIC */
+		.entry = {
+			.function = 0x1,
+			.index = 0,
+			.ecx = 1UL << 21
+		}
+	};
+
+	ASSERT_EQ(ioctl(vcpu, KVM_SET_CPUID2, &cpuid.head), 0);
+
+	return vcpu;
+}
+
+static void set_apicbase(int vcpu, u64 mode)
+{
+	struct {
+		struct kvm_msrs head;
+		struct kvm_msr_entry entry;
+	} msr = {
+		.head.nmsrs = 1,
+		.entry = {
+			.index = MSR_IA32_APICBASE,
+			.data = mode
+		}
+	};
+
+	ASSERT_EQ(ioctl(vcpu, KVM_SET_MSRS, &msr.head), msr.head.nmsrs);
+}
+
+static void *race(void *arg)
+{
+	struct kvm_lapic_state state = {};
+	int vcpu = *(int *)arg;
+
+	while (1) {
+		/* Trigger kvm_recalculate_apic_map(). */
+		ioctl(vcpu, KVM_SET_LAPIC, &state);
+		pthread_testcancel();
+	}
+
+	return NULL;
+}
+
+int main(void)
+{
+	int vcpu0, vcpuN, i;
+	struct kvm_vm *vm;
+	pthread_t thread;
+	time_t t;
+
+	vm = vm_create_barebones();
+	vm_create_irqchip(vm);
+
+	vcpu0 = add_vcpu(vm, 0);
+	vcpuN = add_vcpu(vm, KVM_MAX_VCPUS);
+
+	static_assert(MAX_XAPIC_ID + STUFFING < KVM_MAX_VCPUS);
+	for (i = 0; i < STUFFING; ++i)
+		close(add_vcpu(vm, MAX_XAPIC_ID + i));
+
+	ASSERT_EQ(pthread_create(&thread, NULL, race, &vcpu0), 0);
+
+	pr_info("Testing recalc_apic_map_race...\n");
+
+	for (t = time(NULL) + TIMEOUT; time(NULL) < t;) {
+		set_apicbase(vcpuN, LAPIC_MODE_X2APIC);
+		set_apicbase(vcpuN, LAPIC_MODE_DISABLED);
+	}
+
+	ASSERT_EQ(pthread_cancel(thread), 0);
+	ASSERT_EQ(pthread_join(thread, NULL), 0);
+
+	close(vcpu0);
+	close(vcpuN);
+	kvm_vm_release(vm);
+
+	return 0;
+}
-- 
2.40.1

Re: [PATCH 1/3] KVM: x86: Fix out-of-bounds access in kvm_recalculate_phys_map()

[Sean Christopherson]

On Thu, May 25, 2023, Michal Luczaj wrote:
> Handle the case of vCPU addition and/or APIC enabling during the APIC map
> recalculations. Check the sanity of x2APIC ID in !x2apic_format &&
> apic_x2apic_mode() case.
> 
> kvm_recalculate_apic_map() creates the APIC map iterating over the list of
> vCPUs twice. First to find the max APIC ID and allocate a max-sized buffer,
> then again, calling kvm_recalculate_phys_map() for each vCPU. This opens a
> race window: value of max APIC ID can increase _after_ the buffer was
> allocated.
> 
> Signed-off-by: Michal Luczaj <mhal@rbox.co>
> ---
>  arch/x86/kvm/lapic.c | 8 ++++++--
>  1 file changed, 6 insertions(+), 2 deletions(-)
> 
> diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
> index e542cf285b51..39b9a318d04c 100644
> --- a/arch/x86/kvm/lapic.c
> +++ b/arch/x86/kvm/lapic.c
> @@ -265,10 +265,14 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
>  		 * mapped, i.e. is aliased to multiple vCPUs.  The optimized
>  		 * map requires a strict 1:1 mapping between IDs and vCPUs.
>  		 */
> -		if (apic_x2apic_mode(apic))
> +		if (apic_x2apic_mode(apic)) {
> +			if (x2apic_id > new->max_apic_id)
> +				return -EINVAL;

Hmm, disabling the optimized map just because userspace created a new vCPU is
unfortunate and unnecessary.  Rather than return -EINVAL and only perform the
check when x2APIC is enabled, what if we instead do the check immediately and
return -E2BIG?  Then the caller can retry with a bigger array size.  Preemption
is enabled and retries are bounded by the number of possible vCPUs, so I don't
see any obvious issues with retrying.

And I vote to also add a sanity check on xapic_id, if only to provide documentation
as to why it can't overflow.

I think hoisting the checks up would also obviate the need for cleanup (patch 2),
which I agree isn't obviously better.

E.g. this?  Compile tested only.  I'll test more tomorrow unless you beat me to
it.  Thanks for the fun bugs, as always :-)

---
 arch/x86/kvm/lapic.c | 17 ++++++++++++++---
 1 file changed, 14 insertions(+), 3 deletions(-)

diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
index e542cf285b51..cd34b88c937a 100644
--- a/arch/x86/kvm/lapic.c
+++ b/arch/x86/kvm/lapic.c
@@ -228,6 +228,12 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
 	u32 xapic_id = kvm_xapic_id(apic);
 	u32 physical_id;
 
+	if (WARN_ON_ONCE(xapic_id >= new->max_apic_id))
+		return -EINVAL;
+
+	if (x2apic_id >= new->max_apic_id)
+		return -E2BIG;
+
 	/*
 	 * Deliberately truncate the vCPU ID when detecting a mismatched APIC
 	 * ID to avoid false positives if the vCPU ID, i.e. x2APIC ID, is a
@@ -253,8 +259,7 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
 	 */
 	if (vcpu->kvm->arch.x2apic_format) {
 		/* See also kvm_apic_match_physical_addr(). */
-		if ((apic_x2apic_mode(apic) || x2apic_id > 0xff) &&
-			x2apic_id <= new->max_apic_id)
+		if (apic_x2apic_mode(apic) || x2apic_id > 0xff)
 			new->phys_map[x2apic_id] = apic;
 
 		if (!apic_x2apic_mode(apic) && !new->phys_map[xapic_id])
@@ -366,6 +371,7 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
 	unsigned long i;
 	u32 max_id = 255; /* enough space for any xAPIC ID */
 	bool xapic_id_mismatch = false;
+	int r;
 
 	/* Read kvm->arch.apic_map_dirty before kvm->arch.apic_map.  */
 	if (atomic_read_acquire(&kvm->arch.apic_map_dirty) == CLEAN)
@@ -386,6 +392,7 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
 		return;
 	}
 
+retry:
 	kvm_for_each_vcpu(i, vcpu, kvm)
 		if (kvm_apic_present(vcpu))
 			max_id = max(max_id, kvm_x2apic_id(vcpu->arch.apic));
@@ -404,9 +411,13 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
 		if (!kvm_apic_present(vcpu))
 			continue;
 
-		if (kvm_recalculate_phys_map(new, vcpu, &xapic_id_mismatch)) {
+		r = kvm_recalculate_phys_map(new, vcpu, &xapic_id_mismatch);
+		if (r) {
 			kvfree(new);
 			new = NULL;
+			if (r == -E2BIG)
+				goto retry;
+
 			goto out;
 		}
 

base-commit: 39428f6ea9eace95011681628717062ff7f5eb5f
--

Re: [PATCH 1/3] KVM: x86: Fix out-of-bounds access in kvm_recalculate_phys_map()

[Michal Luczaj]

On 5/26/23 02:07, Sean Christopherson wrote:
> On Thu, May 25, 2023, Michal Luczaj wrote:
>> @@ -265,10 +265,14 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
>>  		 * mapped, i.e. is aliased to multiple vCPUs.  The optimized
>>  		 * map requires a strict 1:1 mapping between IDs and vCPUs.
>>  		 */
>> -		if (apic_x2apic_mode(apic))
>> +		if (apic_x2apic_mode(apic)) {
>> +			if (x2apic_id > new->max_apic_id)
>> +				return -EINVAL;
> 
> Hmm, disabling the optimized map just because userspace created a new vCPU is
> unfortunate and unnecessary.  Rather than return -EINVAL and only perform the
> check when x2APIC is enabled, what if we instead do the check immediately and
> return -E2BIG?  Then the caller can retry with a bigger array size.  Preemption
> is enabled and retries are bounded by the number of possible vCPUs, so I don't
> see any obvious issues with retrying.

Right, that makes perfect sense.

Just a note, it changes the logic a bit:

- x2apic_format: an overflowing x2apic_id won't be silently ignored.

- !x2apic_format: -E2BIG even for !apic_x2apic_mode() leads to an realloc
instead of "new->phys_map[xapic_id] = apic" right away.

> @@ -228,6 +228,12 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
>  	u32 xapic_id = kvm_xapic_id(apic);
>  	u32 physical_id;
>  
> +	if (WARN_ON_ONCE(xapic_id >= new->max_apic_id))
> +		return -EINVAL;

Shouldn't it be ">" instead of ">="?

That said, xapic_id > new->max_apic_id means something terrible has happened as
kvm_xapic_id() returns u8 and max_apic_id should never be less than 255. Does
this qualify for KVM_BUG_ON?

> +	if (x2apic_id >= new->max_apic_id)
> +		return -E2BIG;

Probably ">"?

> @@ -366,6 +371,7 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
>  	unsigned long i;
>  	u32 max_id = 255; /* enough space for any xAPIC ID */
>  	bool xapic_id_mismatch = false;
> +	int r;
>  
>  	/* Read kvm->arch.apic_map_dirty before kvm->arch.apic_map.  */
>  	if (atomic_read_acquire(&kvm->arch.apic_map_dirty) == CLEAN)
> @@ -386,6 +392,7 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
>  		return;
>  	}
>  
> +retry:
>  	kvm_for_each_vcpu(i, vcpu, kvm)
>  		if (kvm_apic_present(vcpu))
>  			max_id = max(max_id, kvm_x2apic_id(vcpu->arch.apic));
> @@ -404,9 +411,13 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
>  		if (!kvm_apic_present(vcpu))
>  			continue;
>  
> -		if (kvm_recalculate_phys_map(new, vcpu, &xapic_id_mismatch)) {
> +		r = kvm_recalculate_phys_map(new, vcpu, &xapic_id_mismatch);
> +		if (r) {
>  			kvfree(new);
>  			new = NULL;
> +			if (r == -E2BIG)
> +				goto retry;
> +
>  			goto out;
>  		}

Maybe it's not important, but what about moving xapic_id_mismatch
(re)initialization after "retry:"?

Re: [PATCH 1/3] KVM: x86: Fix out-of-bounds access in kvm_recalculate_phys_map()

[Sean Christopherson]

On Fri, May 26, 2023, Michal Luczaj wrote:
> On 5/26/23 02:07, Sean Christopherson wrote:
> > On Thu, May 25, 2023, Michal Luczaj wrote:
> >> @@ -265,10 +265,14 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
> >>  		 * mapped, i.e. is aliased to multiple vCPUs.  The optimized
> >>  		 * map requires a strict 1:1 mapping between IDs and vCPUs.
> >>  		 */
> >> -		if (apic_x2apic_mode(apic))
> >> +		if (apic_x2apic_mode(apic)) {
> >> +			if (x2apic_id > new->max_apic_id)
> >> +				return -EINVAL;
> > 
> > Hmm, disabling the optimized map just because userspace created a new vCPU is
> > unfortunate and unnecessary.  Rather than return -EINVAL and only perform the
> > check when x2APIC is enabled, what if we instead do the check immediately and
> > return -E2BIG?  Then the caller can retry with a bigger array size.  Preemption
> > is enabled and retries are bounded by the number of possible vCPUs, so I don't
> > see any obvious issues with retrying.
> 
> Right, that makes perfect sense.
> 
> Just a note, it changes the logic a bit:
> 
> - x2apic_format: an overflowing x2apic_id won't be silently ignored.

Nit, I wouldn't describe the current behavior as silently ignored.  KVM doesn't
ignore the case, KVM instead disables the optimized map.

> - !x2apic_format: -E2BIG even for !apic_x2apic_mode() leads to an realloc
> instead of "new->phys_map[xapic_id] = apic" right away.
> 
> > @@ -228,6 +228,12 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
> >  	u32 xapic_id = kvm_xapic_id(apic);
> >  	u32 physical_id;
> >  
> > +	if (WARN_ON_ONCE(xapic_id >= new->max_apic_id))
> > +		return -EINVAL;
>
> Shouldn't it be ">" instead of ">="?

/facepalm

Yes, I was reading it as the number of IDs, not the max.

> That said, xapic_id > new->max_apic_id means something terrible has happened as
> kvm_xapic_id() returns u8 and max_apic_id should never be less than 255. Does
> this qualify for KVM_BUG_ON?

I don't think so?  The intent of the WARN is mostly to document that KVM always
allocates enough space for xAPIC IDs, and to guard against that changing in the
future.  In the latter case, there's no need to kill the VM despite there being
a KVM bug since running with the optimized map disabled is functionally ok.

If the WARN fires because of host data corruption, then so be it.

> > +	if (x2apic_id >= new->max_apic_id)
> > +		return -E2BIG;
> 
> Probably ">"?

Ya.

> > @@ -366,6 +371,7 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
> >  	unsigned long i;
> >  	u32 max_id = 255; /* enough space for any xAPIC ID */
> >  	bool xapic_id_mismatch = false;
> > +	int r;
> >  
> >  	/* Read kvm->arch.apic_map_dirty before kvm->arch.apic_map.  */
> >  	if (atomic_read_acquire(&kvm->arch.apic_map_dirty) == CLEAN)
> > @@ -386,6 +392,7 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
> >  		return;
> >  	}
> >  
> > +retry:
> >  	kvm_for_each_vcpu(i, vcpu, kvm)
> >  		if (kvm_apic_present(vcpu))
> >  			max_id = max(max_id, kvm_x2apic_id(vcpu->arch.apic));
> > @@ -404,9 +411,13 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
> >  		if (!kvm_apic_present(vcpu))
> >  			continue;
> >  
> > -		if (kvm_recalculate_phys_map(new, vcpu, &xapic_id_mismatch)) {
> > +		r = kvm_recalculate_phys_map(new, vcpu, &xapic_id_mismatch);
> > +		if (r) {
> >  			kvfree(new);
> >  			new = NULL;
> > +			if (r == -E2BIG)
> > +				goto retry;
> > +
> >  			goto out;
> >  		}
> 
> Maybe it's not important, but what about moving xapic_id_mismatch
> (re)initialization after "retry:"?

Oof, good catch.  I think it makes sense to move max_id (re)initialization too,
even though I can't imagine it would matter in practice.

Re: [PATCH 1/3] KVM: x86: Fix out-of-bounds access in kvm_recalculate_phys_map()

[Michal Luczaj]

On 5/26/23 18:17, Sean Christopherson wrote:
> On Fri, May 26, 2023, Michal Luczaj wrote:
>> On 5/26/23 02:07, Sean Christopherson wrote:
>>> On Thu, May 25, 2023, Michal Luczaj wrote:
>>>> @@ -265,10 +265,14 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
>>>>  		 * mapped, i.e. is aliased to multiple vCPUs.  The optimized
>>>>  		 * map requires a strict 1:1 mapping between IDs and vCPUs.
>>>>  		 */
>>>> -		if (apic_x2apic_mode(apic))
>>>> +		if (apic_x2apic_mode(apic)) {
>>>> +			if (x2apic_id > new->max_apic_id)
>>>> +				return -EINVAL;
>>>
>>> Hmm, disabling the optimized map just because userspace created a new vCPU is
>>> unfortunate and unnecessary.  Rather than return -EINVAL and only perform the
>>> check when x2APIC is enabled, what if we instead do the check immediately and
>>> return -E2BIG?  Then the caller can retry with a bigger array size.  Preemption
>>> is enabled and retries are bounded by the number of possible vCPUs, so I don't
>>> see any obvious issues with retrying.
>>
>> Right, that makes perfect sense.
>>
>> Just a note, it changes the logic a bit:
>>
>> - x2apic_format: an overflowing x2apic_id won't be silently ignored.
> 
> Nit, I wouldn't describe the current behavior as silently ignored.  KVM doesn't
> ignore the case, KVM instead disables the optimized map.

I may be misusing "silently ignored", but currently if (x2apic_format &&
apic_x2apic_mode && x2apic_id > new->max_apic_id) new->phys_map[x2apic_id]
remains unchanged, then kvm_recalculate_phys_map() returns 0 (not -EINVAL).
I.e. this does not result in rcu_assign_pointer(kvm->arch.apic_map, NULL).

>> That said, xapic_id > new->max_apic_id means something terrible has happened as
>> kvm_xapic_id() returns u8 and max_apic_id should never be less than 255. Does
>> this qualify for KVM_BUG_ON?
> 
> I don't think so?  The intent of the WARN is mostly to document that KVM always
> allocates enough space for xAPIC IDs, and to guard against that changing in the
> future.  In the latter case, there's no need to kill the VM despite there being
> a KVM bug since running with the optimized map disabled is functionally ok.
> 
> If the WARN fires because of host data corruption, then so be it.

Ahh, OK, I get it.

>> Maybe it's not important, but what about moving xapic_id_mismatch
>> (re)initialization after "retry:"?
> 
> Oof, good catch.  I think it makes sense to move max_id (re)initialization too,
> even though I can't imagine it would matter in practice.

Right, I forgot that max APIC ID can decrease along the way.

Re: [PATCH 1/3] KVM: x86: Fix out-of-bounds access in kvm_recalculate_phys_map()

[Sean Christopherson]

On Fri, May 26, 2023, Michal Luczaj wrote:
> On 5/26/23 18:17, Sean Christopherson wrote:
> > On Fri, May 26, 2023, Michal Luczaj wrote:
> >> On 5/26/23 02:07, Sean Christopherson wrote:
> >>> On Thu, May 25, 2023, Michal Luczaj wrote:
> >>>> @@ -265,10 +265,14 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
> >>>>  		 * mapped, i.e. is aliased to multiple vCPUs.  The optimized
> >>>>  		 * map requires a strict 1:1 mapping between IDs and vCPUs.
> >>>>  		 */
> >>>> -		if (apic_x2apic_mode(apic))
> >>>> +		if (apic_x2apic_mode(apic)) {
> >>>> +			if (x2apic_id > new->max_apic_id)
> >>>> +				return -EINVAL;
> >>>
> >>> Hmm, disabling the optimized map just because userspace created a new vCPU is
> >>> unfortunate and unnecessary.  Rather than return -EINVAL and only perform the
> >>> check when x2APIC is enabled, what if we instead do the check immediately and
> >>> return -E2BIG?  Then the caller can retry with a bigger array size.  Preemption
> >>> is enabled and retries are bounded by the number of possible vCPUs, so I don't
> >>> see any obvious issues with retrying.
> >>
> >> Right, that makes perfect sense.
> >>
> >> Just a note, it changes the logic a bit:
> >>
> >> - x2apic_format: an overflowing x2apic_id won't be silently ignored.
> > 
> > Nit, I wouldn't describe the current behavior as silently ignored.  KVM doesn't
> > ignore the case, KVM instead disables the optimized map.
> 
> I may be misusing "silently ignored",

You're not.

> but currently if (x2apic_format && apic_x2apic_mode && x2apic_id >
> new->max_apic_id) new->phys_map[x2apic_id] remains unchanged, then
> kvm_recalculate_phys_map() returns 0 (not -EINVAL).  I.e. this does not
> result in rcu_assign_pointer(kvm->arch.apic_map, NULL).

My bad.  I was thinking of the -EINVAL from your patch.

Hmm, thinking more about the "silently ignored" case, it's only temporarily
ignored.  If a x2APIC ID is out-of-bounds, then there had to have been a write
to a vCPU's x2APIC ID between the two instances of kvm_for_each_vcpu(), and that
means that whatever changed the ID must also mark apic_map_dirty DIRTY and call
kvm_recalculate_apic_map().  I.e. another recalc will soon occur and cleanup the
mess.

There's still value in retrying, but it's not as much as an optimization as it
first appears.  That means the bug fix can be a separate patch from the retry.
Oh, and the retry can also redo the DIRTY=>IN_PROGRESS so that whatever modified
a vCPU's x2APIC ID doesn't perform an unnecessary recalculation.

E.g. this (plus comments) for stable@

---
 arch/x86/kvm/lapic.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
index e542cf285b51..7a83df7f45c5 100644
--- a/arch/x86/kvm/lapic.c
+++ b/arch/x86/kvm/lapic.c
@@ -228,6 +228,12 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
 	u32 xapic_id = kvm_xapic_id(apic);
 	u32 physical_id;
 
+	if (WARN_ON_ONCE(xapic_id >= new->max_apic_id))
+		return -EINVAL;
+
+	if (x2apic_id >= new->max_apic_id)
+		return -E2BIG;
+
 	/*
 	 * Deliberately truncate the vCPU ID when detecting a mismatched APIC
 	 * ID to avoid false positives if the vCPU ID, i.e. x2APIC ID, is a
@@ -253,8 +259,7 @@ static int kvm_recalculate_phys_map(struct kvm_apic_map *new,
 	 */
 	if (vcpu->kvm->arch.x2apic_format) {
 		/* See also kvm_apic_match_physical_addr(). */
-		if ((apic_x2apic_mode(apic) || x2apic_id > 0xff) &&
-			x2apic_id <= new->max_apic_id)
+		if (apic_x2apic_mode(apic) || x2apic_id > 0xff)
 			new->phys_map[x2apic_id] = apic;
 
 		if (!apic_x2apic_mode(apic) && !new->phys_map[xapic_id])

base-commit: 39428f6ea9eace95011681628717062ff7f5eb5f
-- 


and then as a pure optimization

---
 arch/x86/kvm/lapic.c | 23 ++++++++++++++++++-----
 1 file changed, 18 insertions(+), 5 deletions(-)

diff --git a/arch/x86/kvm/lapic.c b/arch/x86/kvm/lapic.c
index 7a83df7f45c5..09e13ded34ef 100644
--- a/arch/x86/kvm/lapic.c
+++ b/arch/x86/kvm/lapic.c
@@ -369,8 +369,9 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
 	struct kvm_apic_map *new, *old = NULL;
 	struct kvm_vcpu *vcpu;
 	unsigned long i;
-	u32 max_id = 255; /* enough space for any xAPIC ID */
-	bool xapic_id_mismatch = false;
+	u32 max_id;
+	bool xapic_id_mismatch;
+	int r;
 
 	/* Read kvm->arch.apic_map_dirty before kvm->arch.apic_map.  */
 	if (atomic_read_acquire(&kvm->arch.apic_map_dirty) == CLEAN)
@@ -380,9 +381,14 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
 		  "Dirty APIC map without an in-kernel local APIC");
 
 	mutex_lock(&kvm->arch.apic_map_lock);
+
+retry:
 	/*
-	 * Read kvm->arch.apic_map_dirty before kvm->arch.apic_map
-	 * (if clean) or the APIC registers (if dirty).
+	 * Read kvm->arch.apic_map_dirty before kvm->arch.apic_map (if clean)
+	 * or the APIC registers (if dirty).  Note, on retry the map may have
+	 * not yet been marked dirty by whatever task changed a vCPU's x2APIC
+	 * ID, i.e. the map may still show up as in-progress.  In that case
+	 * this task still needs to retry and copmlete its calculation.
 	 */
 	if (atomic_cmpxchg_acquire(&kvm->arch.apic_map_dirty,
 				   DIRTY, UPDATE_IN_PROGRESS) == CLEAN) {
@@ -391,6 +397,9 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
 		return;
 	}
 
+	max_id = 255; /* enough space for any xAPIC ID */
+	xapic_id_mismatch = false;
+
 	kvm_for_each_vcpu(i, vcpu, kvm)
 		if (kvm_apic_present(vcpu))
 			max_id = max(max_id, kvm_x2apic_id(vcpu->arch.apic));
@@ -409,9 +418,13 @@ void kvm_recalculate_apic_map(struct kvm *kvm)
 		if (!kvm_apic_present(vcpu))
 			continue;
 
-		if (kvm_recalculate_phys_map(new, vcpu, &xapic_id_mismatch)) {
+		r = kvm_recalculate_phys_map(new, vcpu, &xapic_id_mismatch);
+		if (r) {
 			kvfree(new);
 			new = NULL;
+			if (r == -E2BIG)
+				goto retry;
+
 			goto out;
 		}
 

base-commit: 15cc2fa07b5867ae5a6f17656a6f272cfb393810
-- 

Re: [PATCH 1/3] KVM: x86: Fix out-of-bounds access in kvm_recalculate_phys_map()

[Sean Christopherson]

On Fri, May 26, 2023, Michal Luczaj wrote:
> On 5/26/23 18:17, Sean Christopherson wrote:
> > On Fri, May 26, 2023, Michal Luczaj wrote:
> >> Maybe it's not important, but what about moving xapic_id_mismatch
> >> (re)initialization after "retry:"?
> > 
> > Oof, good catch.  I think it makes sense to move max_id (re)initialization too,
> > even though I can't imagine it would matter in practice.
> 
> Right, I forgot that max APIC ID can decrease along the way.

Actually, we don't want to reset max_id.  That would allow userspace or the guest
to put KVM into an infinite loop, e.g. by toggling the APIC of the vCPU with the
highest x2APIC ID between enabled and disabled.  The downside of not shrinking the
size is quite negligible.

Re: [PATCH 3/3] KVM: selftests: Add test for race in kvm_recalculate_apic_map()

[Sean Christopherson]

On Thu, May 25, 2023, Michal Luczaj wrote:
> Keep switching between LAPIC_MODE_X2APIC and LAPIC_MODE_DISABLED during
> APIC map construction.
> 
> Signed-off-by: Michal Luczaj <mhal@rbox.co>
> ---
>  tools/testing/selftests/kvm/Makefile          |   1 +
>  .../kvm/x86_64/recalc_apic_map_race.c         | 110 ++++++++++++++++++
>  2 files changed, 111 insertions(+)
>  create mode 100644 tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c
> 
> diff --git a/tools/testing/selftests/kvm/Makefile b/tools/testing/selftests/kvm/Makefile
> index 7a5ff646e7e7..c9b8f16fb23f 100644
> --- a/tools/testing/selftests/kvm/Makefile
> +++ b/tools/testing/selftests/kvm/Makefile
> @@ -116,6 +116,7 @@ TEST_GEN_PROGS_x86_64 += x86_64/sev_migrate_tests
>  TEST_GEN_PROGS_x86_64 += x86_64/amx_test
>  TEST_GEN_PROGS_x86_64 += x86_64/max_vcpuid_cap_test
>  TEST_GEN_PROGS_x86_64 += x86_64/triple_fault_event_test
> +TEST_GEN_PROGS_x86_64 += x86_64/recalc_apic_map_race
>  TEST_GEN_PROGS_x86_64 += access_tracking_perf_test
>  TEST_GEN_PROGS_x86_64 += demand_paging_test
>  TEST_GEN_PROGS_x86_64 += dirty_log_test
> diff --git a/tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c b/tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c
> new file mode 100644
> index 000000000000..1122df858623
> --- /dev/null
> +++ b/tools/testing/selftests/kvm/x86_64/recalc_apic_map_race.c
> @@ -0,0 +1,110 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +/*
> + * recalc_apic_map_race
> + *
> + * Test for a race condition in kvm_recalculate_apic_map().
> + */
> +
> +#include <sys/ioctl.h>
> +#include <pthread.h>
> +#include <time.h>
> +
> +#include "processor.h"
> +#include "test_util.h"
> +#include "kvm_util.h"
> +#include "apic.h"
> +
> +#define TIMEOUT			5	/* seconds */
> +#define STUFFING		100
> +
> +#define LAPIC_MODE_DISABLED	0
> +#define LAPIC_MODE_X2APIC	(MSR_IA32_APICBASE_ENABLE | X2APIC_ENABLE)
> +#define MAX_XAPIC_ID		0xff
> +
> +static int add_vcpu(struct kvm_vm *vm, long id)
> +{
> +	int vcpu = __vm_ioctl(vm, KVM_CREATE_VCPU, (void *)id);
> +
> +	static struct {
> +		struct kvm_cpuid2 head;
> +		struct kvm_cpuid_entry2 entry;
> +	} cpuid = {
> +		.head.nent = 1,
> +		/* X86_FEATURE_X2APIC */
> +		.entry = {
> +			.function = 0x1,
> +			.index = 0,
> +			.ecx = 1UL << 21
> +		}
> +	};
> +
> +	ASSERT_EQ(ioctl(vcpu, KVM_SET_CPUID2, &cpuid.head), 0);
> +
> +	return vcpu;
> +}
> +
> +static void set_apicbase(int vcpu, u64 mode)
> +{
> +	struct {
> +		struct kvm_msrs head;
> +		struct kvm_msr_entry entry;
> +	} msr = {
> +		.head.nmsrs = 1,
> +		.entry = {
> +			.index = MSR_IA32_APICBASE,
> +			.data = mode
> +		}
> +	};
> +
> +	ASSERT_EQ(ioctl(vcpu, KVM_SET_MSRS, &msr.head), msr.head.nmsrs);
> +}
> +
> +static void *race(void *arg)
> +{
> +	struct kvm_lapic_state state = {};
> +	int vcpu = *(int *)arg;
> +
> +	while (1) {
> +		/* Trigger kvm_recalculate_apic_map(). */
> +		ioctl(vcpu, KVM_SET_LAPIC, &state);
> +		pthread_testcancel();
> +	}
> +
> +	return NULL;
> +}
> +
> +int main(void)
> +{
> +	int vcpu0, vcpuN, i;
> +	struct kvm_vm *vm;
> +	pthread_t thread;
> +	time_t t;
> +
> +	vm = vm_create_barebones();
> +	vm_create_irqchip(vm);

All of these open coded ioctl() calls is unnecessary.  Ditto for the fancy
stuffing, which through trial and error I discovered is done to avoid having
vCPUs with aliased xAPIC IDs, which would cause KVM to bail before triggering
the bug.  It's much easier to just create the max number of vCPUs and enable
x2APIC on all of them.

This can all be distilled down to:

// SPDX-License-Identifier: GPL-2.0-only
/*
 * recalc_apic_map_race
 *
 * Test for a race condition in kvm_recalculate_apic_map().
 */

#include <sys/ioctl.h>
#include <pthread.h>
#include <time.h>

#include "processor.h"
#include "test_util.h"
#include "kvm_util.h"
#include "apic.h"

#define TIMEOUT		5	/* seconds */

#define LAPIC_DISABLED	0
#define LAPIC_X2APIC	(MSR_IA32_APICBASE_ENABLE | X2APIC_ENABLE)
#define MAX_XAPIC_ID	0xff

static void *race(void *arg)
{
	struct kvm_lapic_state lapic = {};
	struct kvm_vcpu *vcpu = arg;

	while (1) {
		/* Trigger kvm_recalculate_apic_map(). */
		vcpu_ioctl(vcpu, KVM_SET_LAPIC, &lapic);
		pthread_testcancel();
	}

	return NULL;
}

int main(void)
{
	struct kvm_vcpu *vcpus[KVM_MAX_VCPUS];
	struct kvm_vcpu *vcpuN;
	struct kvm_vm *vm;
	pthread_t thread;
	time_t t;
	int i;

	kvm_static_assert(KVM_MAX_VCPUS > MAX_XAPIC_ID);

	/*
	 * Creating the max number of vCPUs supported by selftests so that KVM
	 * has decent amount of work to do when recalculating the map, i.e. to
	 * make the problematic window large enough to hit.
	 */
	vm = vm_create_with_vcpus(KVM_MAX_VCPUS, NULL, vcpus);

	/*
	 * Enable x2APIC on all vCPUs so that KVM doesn't bail from the recalc
	 * due to vCPUs having aliased xAPIC IDs (truncated to 8 bits).
	 */
	for (i = 0; i < KVM_MAX_VCPUS; i++)
		vcpu_set_msr(vcpus[i], MSR_IA32_APICBASE, LAPIC_X2APIC);

	ASSERT_EQ(pthread_create(&thread, NULL, race, vcpus[0]), 0);

	vcpuN = vcpus[KVM_MAX_VCPUS - 1];
	for (t = time(NULL) + TIMEOUT; time(NULL) < t;) {
		vcpu_set_msr(vcpuN, MSR_IA32_APICBASE, LAPIC_X2APIC);
		vcpu_set_msr(vcpuN, MSR_IA32_APICBASE, LAPIC_DISABLED);
	}

	ASSERT_EQ(pthread_cancel(thread), 0);
	ASSERT_EQ(pthread_join(thread, NULL), 0);

	kvm_vm_release(vm);

	return 0;
}

Re: [PATCH 3/3] KVM: selftests: Add test for race in kvm_recalculate_apic_map()

[Michal Luczaj]

On 5/27/23 01:40, Sean Christopherson wrote:
> All of these open coded ioctl() calls is unnecessary.  Ditto for the fancy
> stuffing, which through trial and error I discovered is done to avoid having
> vCPUs with aliased xAPIC IDs, which would cause KVM to bail before triggering
> the bug.  It's much easier to just create the max number of vCPUs and enable
> x2APIC on all of them.
> ...

Yup, this looks way better, thanks.
(FWIW, the #defines were deliberately named to match enum lapic_mode.)

In somewhat related news, I've hit kvm_recalculate_logical_map()'s
WARN_ON_ONCE(ldr != kvm_apic_calc_x2apic_ldr(kvm_x2apic_id(apic))):

[  464.081627] WARNING: CPU: 2 PID: 958 at arch/x86/kvm/lapic.c:331 kvm_recalculate_apic_map+0x609/0xa00 [kvm]
[  464.081703] Modules linked in: kvm_intel 9p fscache netfs qrtr sunrpc intel_rapl_msr kvm 9pnet_virtio 9pnet intel_rapl_common rapl pcspkr i2c_piix4 drm zram crct10dif_pclmul crc32_pclmul crc32c_intel ghash_clmulni_intel ata_generic serio_raw virtio_blk virtio_console pata_acpi fuse qemu_fw_cfg [last unloaded: kvm_intel]
[  464.081778] CPU: 2 PID: 958 Comm: recalc_apic_map Not tainted 6.4.0-rc3-vanilla+ #35
[  464.081782] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Arch Linux 1.16.2-1-1 04/01/2014
[  464.081785] RIP: 0010:kvm_recalculate_apic_map+0x609/0xa00 [kvm]
[  464.081852] Code: 04 0f 84 00 02 00 00 49 8d 7e 24 e8 b1 2d 13 c1 41 8b 56 24 89 d0 83 e2 0f c1 e8 04 c1 e0 10 0f ab d0 39 e8 0f 84 50 fe ff ff <0f> 0b e9 49 fe ff ff 4c 8d a5 b0 02 00 00 4c 89 e7 e8 a1 2e 13 c1
[  464.081855] RSP: 0018:ffffc900015cf6c8 EFLAGS: 00010297
[  464.081860] RAX: 0000000000000001 RBX: ffff888108bb3c00 RCX: dffffc0000000000
[  464.081863] RDX: 0000000000000000 RSI: ffffffffc04875ef RDI: ffff888178a651a4
[  464.081865] RBP: 0000000000000002 R08: 0000000000000000 R09: ffffffff8446e2e7
[  464.081868] R10: fffffbfff088dc5c R11: 0000000000000000 R12: 0000000000000000
[  464.081870] R13: 0000000000000003 R14: ffff888178a65180 R15: ffff8881131b2000
[  464.081873] FS:  00007fade8a9a740(0000) GS:ffff8883eef00000(0000) knlGS:0000000000000000
[  464.081876] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[  464.081879] CR2: 00007fade88d0008 CR3: 000000014d68b000 CR4: 0000000000752ee0
[  464.081883] PKRU: 55555554
[  464.081886] Call Trace:
[  464.081888]  <TASK>
[  464.081901]  ? kvm_can_use_hv_timer+0x60/0x60 [kvm]
[  464.081969]  ? queue_delayed_work_on+0x6c/0xa0
[  464.081978]  kvm_apic_set_state+0x1cf/0x5b0 [kvm]
[  464.082050]  kvm_arch_vcpu_ioctl+0x1806/0x2100 [kvm]
[  464.082116]  ? kvm_arch_vcpu_put+0x410/0x410 [kvm]
[  464.082180]  ? mark_lock+0xf4/0xce0
[  464.082185]  ? kvm_arch_vcpu_put+0x410/0x410 [kvm]
[  464.082251]  ? mark_lock+0xf4/0xce0
[  464.082255]  ? preempt_count_sub+0x14/0xc0
[  464.082263]  ? print_usage_bug.part.0+0x3b0/0x3b0
[  464.082269]  ? kvm_arch_vcpu_put+0x410/0x410 [kvm]
[  464.082363]  ? mark_lock+0xf4/0xce0
[  464.082369]  ? __kernel_text_address+0xe/0x30
[  464.082373]  ? unwind_get_return_address+0x2f/0x50
[  464.082382]  ? print_usage_bug.part.0+0x3b0/0x3b0
[  464.082392]  ? __lock_acquire+0x9ed/0x3210
[  464.082404]  ? lockdep_hardirqs_on_prepare+0x220/0x220
[  464.082410]  ? lockdep_hardirqs_on_prepare+0x220/0x220
[  464.082420]  ? lock_acquire+0x159/0x3b0
[  464.082426]  ? lock_acquire+0x169/0x3b0
[  464.082432]  ? lock_sync+0x110/0x110
[  464.082438]  ? find_held_lock+0x83/0xa0
[  464.082444]  ? lock_release+0x214/0x3a0
[  464.082448]  ? kvm_vcpu_ioctl+0x1c6/0x8a0 [kvm]
[  464.082507]  ? rcu_is_watching+0x34/0x50
[  464.082524]  ? preempt_count_sub+0x14/0xc0
[  464.082527]  ? __mutex_lock+0x201/0x1040
[  464.082532]  ? kvm_vcpu_ioctl+0x13a/0x8a0 [kvm]
[  464.082586]  ? find_held_lock+0x83/0xa0
[  464.082591]  ? kvm_vcpu_ioctl+0x13a/0x8a0 [kvm]
[  464.082648]  ? mutex_lock_io_nested+0xe40/0xe40
[  464.082652]  ? bit_wait_io_timeout+0xc0/0xc0
[  464.082658]  ? kvm_vcpu_ioctl+0x13a/0x8a0 [kvm]
[  464.082720]  ? kvm_vcpu_ioctl+0x663/0x8a0 [kvm]
[  464.082774]  kvm_vcpu_ioctl+0x663/0x8a0 [kvm]
[  464.082831]  ? kvm_vcpu_kick+0x200/0x200 [kvm]
[  464.082884]  ? vfs_fileattr_set+0x480/0x480
[  464.082889]  ? vfs_fileattr_set+0x480/0x480
[  464.082893]  ? rcu_is_watching+0x34/0x50
[  464.082897]  ? kfree+0x107/0x140
[  464.082902]  ? kvm_vcpu_ioctl+0x1d6/0x8a0 [kvm]
[  464.082955]  ? ioctl_has_perm.constprop.0.isra.0+0x133/0x1f0
[  464.082961]  ? ioctl_has_perm.constprop.0.isra.0+0x133/0x1f0
[  464.082967]  ? selinux_bprm_creds_for_exec+0x440/0x440
[  464.082988]  __x64_sys_ioctl+0xb8/0xf0
[  464.082994]  do_syscall_64+0x56/0x80
[  464.083000]  ? mark_held_locks+0x1a/0x80
[  464.083007]  ? do_syscall_64+0x62/0x80
[  464.083011]  ? lockdep_hardirqs_on+0x7d/0x100
[  464.083015]  ? do_syscall_64+0x62/0x80
[  464.083019]  ? lockdep_hardirqs_on+0x7d/0x100
[  464.083023]  entry_SYSCALL_64_after_hwframe+0x46/0xb0
[  464.083027] RIP: 0033:0x7fade8b9dd6f
[  464.083031] Code: 00 48 89 44 24 18 31 c0 48 8d 44 24 60 c7 04 24 10 00 00 00 48 89 44 24 08 48 8d 44 24 20 48 89 44 24 10 b8 10 00 00 00 0f 05 <89> c2 3d 00 f0 ff ff 77 18 48 8b 44 24 18 64 48 2b 04 25 28 00 00
[  464.083034] RSP: 002b:00007ffffd2d4550 EFLAGS: 00000246 ORIG_RAX: 0000000000000010
[  464.083038] RAX: ffffffffffffffda RBX: 00007ffffd2d4ae8 RCX: 00007fade8b9dd6f
[  464.083041] RDX: 00007ffffd2d45c0 RSI: 000000004400ae8f RDI: 0000000000000005
[  464.083044] RBP: 0000000000000001 R08: 00000000004150a8 R09: 0000000000415004
[  464.083047] R10: 0000000002268301 R11: 0000000000000246 R12: 00000000022662a0
[  464.083050] R13: 00007ffffd2d4af8 R14: 0000000000421df0 R15: 00007fade8cc0000
[  464.083064]  </TASK>
[  464.083066] irq event stamp: 22889
[  464.083069] hardirqs last  enabled at (22895): [<ffffffff81234ede>] __up_console_sem+0x5e/0x70
[  464.083073] hardirqs last disabled at (22900): [<ffffffff81234ec3>] __up_console_sem+0x43/0x70
[  464.083077] softirqs last  enabled at (22184): [<ffffffff811538cf>] __irq_exit_rcu+0xdf/0x1b0
[  464.083082] softirqs last disabled at (22077): [<ffffffff811538cf>] __irq_exit_rcu+0xdf/0x1b0

diff --git a/tools/testing/selftests/kvm/Makefile b/tools/testing/selftests/kvm/Makefile
index c9b8f16fb23f..1c7f9cf51998 100644
--- a/tools/testing/selftests/kvm/Makefile
+++ b/tools/testing/selftests/kvm/Makefile
@@ -117,6 +117,7 @@ TEST_GEN_PROGS_x86_64 += x86_64/amx_test
 TEST_GEN_PROGS_x86_64 += x86_64/max_vcpuid_cap_test
 TEST_GEN_PROGS_x86_64 += x86_64/triple_fault_event_test
 TEST_GEN_PROGS_x86_64 += x86_64/recalc_apic_map_race
+TEST_GEN_PROGS_x86_64 += x86_64/recalc_apic_map_warn
 TEST_GEN_PROGS_x86_64 += access_tracking_perf_test
 TEST_GEN_PROGS_x86_64 += demand_paging_test
 TEST_GEN_PROGS_x86_64 += dirty_log_test
diff --git a/tools/testing/selftests/kvm/x86_64/recalc_apic_map_warn.c b/tools/testing/selftests/kvm/x86_64/recalc_apic_map_warn.c
new file mode 100644
index 000000000000..2845e1d9b865
--- /dev/null
+++ b/tools/testing/selftests/kvm/x86_64/recalc_apic_map_warn.c
@@ -0,0 +1,30 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * recalc_apic_map_warn
+ *
+ * Test for hitting WARN_ON_ONCE() in kvm_recalculate_logical_map().
+ */
+
+#include "processor.h"
+#include "kvm_util.h"
+#include "apic.h"
+
+#define	LAPIC_X2APIC	(MSR_IA32_APICBASE_ENABLE | X2APIC_ENABLE)
+
+int main(void)
+{
+	struct kvm_lapic_state lapic = {};
+	struct kvm_vcpu *vcpu;
+	struct kvm_vm *vm;
+
+	vm = vm_create_with_one_vcpu(&vcpu, NULL); /* vcpu_id = 0 */
+	vcpu_set_msr(vcpu, MSR_IA32_APICBASE, LAPIC_X2APIC);
+
+	*(u32 *)(lapic.regs + APIC_ID) = 1 << 24; /* != vcpu_id */
+	*(u32 *)(lapic.regs + APIC_SPIV) = APIC_SPIV_APIC_ENABLED;
+	vcpu_ioctl(vcpu, KVM_SET_LAPIC, &lapic);
+
+	kvm_vm_release(vm);
+
+	return 0;
+}

Re: [PATCH 3/3] KVM: selftests: Add test for race in kvm_recalculate_apic_map()

[Sean Christopherson]

On Sun, May 28, 2023, Michal Luczaj wrote:
> On 5/27/23 01:40, Sean Christopherson wrote:
> > All of these open coded ioctl() calls is unnecessary.  Ditto for the fancy
> > stuffing, which through trial and error I discovered is done to avoid having
> > vCPUs with aliased xAPIC IDs, which would cause KVM to bail before triggering
> > the bug.  It's much easier to just create the max number of vCPUs and enable
> > x2APIC on all of them.
> > ...
> 
> Yup, this looks way better, thanks.
> (FWIW, the #defines were deliberately named to match enum lapic_mode.)

I figured as much, but I find enum lapic_mode to be rather odd, and if that thing
ever gets cleaned up I'd prefer not to have to go fixup selftests too.

> In somewhat related news, I've hit kvm_recalculate_logical_map()'s
> WARN_ON_ONCE(ldr != kvm_apic_calc_x2apic_ldr(kvm_x2apic_id(apic))):

...

> diff --git a/tools/testing/selftests/kvm/x86_64/recalc_apic_map_warn.c b/tools/testing/selftests/kvm/x86_64/recalc_apic_map_warn.c
> new file mode 100644
> index 000000000000..2845e1d9b865
> --- /dev/null
> +++ b/tools/testing/selftests/kvm/x86_64/recalc_apic_map_warn.c
> @@ -0,0 +1,30 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +/*
> + * recalc_apic_map_warn
> + *
> + * Test for hitting WARN_ON_ONCE() in kvm_recalculate_logical_map().
> + */
> +
> +#include "processor.h"
> +#include "kvm_util.h"
> +#include "apic.h"
> +
> +#define	LAPIC_X2APIC	(MSR_IA32_APICBASE_ENABLE | X2APIC_ENABLE)
> +
> +int main(void)
> +{
> +	struct kvm_lapic_state lapic = {};
> +	struct kvm_vcpu *vcpu;
> +	struct kvm_vm *vm;
> +
> +	vm = vm_create_with_one_vcpu(&vcpu, NULL); /* vcpu_id = 0 */
> +	vcpu_set_msr(vcpu, MSR_IA32_APICBASE, LAPIC_X2APIC);
> +
> +	*(u32 *)(lapic.regs + APIC_ID) = 1 << 24; /* != vcpu_id */
> +	*(u32 *)(lapic.regs + APIC_SPIV) = APIC_SPIV_APIC_ENABLED;
> +	vcpu_ioctl(vcpu, KVM_SET_LAPIC, &lapic);

Blech.  There's a semi-known backdoor that lets userspace modify the x2APIC ID
and thus the LDR.  Sort of.  KVM doesn't actually honor the modified ID except
for guest RDMSR, e.g. KVM will never deliver interrupts to the unexpected ID.

I'll send a patch (plus this test) to close that loophole, the odds of breaking
an existing setup are basically nil, and it would be very nice to make the x2APIC
ID (and LDR) fully readonly.