[PATCH v1 0/4] Fix a bug in VGIC ITS tables' save/restore

[PATCH v1 0/4] Fix a bug in VGIC ITS tables' save/restore

[Jing Zhang]

This patch series addresses a critical issue in the VGIC ITS tables'
save/restore mechanism, accompanied by a comprehensive selftest for bug
reproduction and verification.

The identified bug manifests as a failure in VM suspend/resume operations.
The root cause lies in the repeated suspend attempts often required for
successful VM suspension, coupled with concurrent device interrupt registration
and freeing. This concurrency leads to inconsistencies in ITS mappings before
the save operation, potentially leaving orphaned Device Translation Entries
(DTEs) and Interrupt Translation Entries (ITEs) in the respective tables.

During the subsequent restore operation, encountering these orphaned entries
can result in two error scenarios:
* EINVAL Error: If an orphaned entry lacks a corresponding collection ID, the
  restore operation fails with an EINVAL error.
* Mapping Corruption: If an orphaned entry possesses a valid collection ID, the
  restore operation may succeed but with incorrect or lost mappings,
  compromising system integrity.

The provided selftest facilitates the reproduction of both error scenarios:
* EINVAL Reproduction: Execute ./vgic_its_tables without any options.
* Mapping Corruption Reproduction: Execute ./vgic_its_tables -s
  The -s option enforces identical collection IDs for all mappings.
* A workaround within the selftest involves clearing the tables before the save
  operation using the command ./vgic_its_tables -c. With this, we can run the
  the selftest successfully on host w/o the fix.

The core issue stems from the static linked list implementation of DTEs/ITEs,
requiring a full table scan to locate the list head during restoration. This
scan increases the likelihood of encountering orphaned entries.  To rectify
this, the patch series introduces a dummy head to the list, enabling immediate
access to the list head and bypassing the scan. This optimization not only
resolves the bug but also significantly enhances restore performance,
particularly in edge cases where valid entries reside at the end of the table.

Result from the test demonstrates a remarkable 1000x performance improvement in
such edge cases. For instance, with a single L2 device table (64KB) and 8192
mappings (one event per device at the table's end), the restore time is reduced
from 6 seconds to 6 milliseconds.

Importantly, these modifications maintain compatibility with the existing ITS
TABLE ABI REV0.
The table entry was a valid DTE/ITE, or an orphaned DTE/ITE, or an entry of 0.
The dummy entry added in this patch series presents a fourth kind, which is an
invalid entry w/ an offset field pointing to the first valid entry in the table.
The dummy head entry is always the first entry in the table if it exists.

An alternative solution, proposed in patch series [1], involves clearing
DTEs/ITEs during MAPD/DISCARD commands. While this approach requires fewer code
changes, it lacks the performance benefits offered by the dummy head solution
presented in this patch series.

---

* v1:
  - Based on v6.12-rc6

[1] https://lore.kernel.org/linux-arm-kernel/20240704142319.728-1-jiangkunkun@huawei.com

---

Jing Zhang (4):
  KVM: selftests: aarch64: Test VGIC ITS tables save/restore
  KVM: arm64: vgic-its: Add a dummy DTE/ITE if necessary in ITS tables
    save operation
  KVM: arm64: vgic-its: Return device/event id instead of offset in ITS
    tables restore
  KVM: arm64: vgic-its: Utilize the dummy entry in ITS tables restoring

 arch/arm64/kvm/vgic/vgic-its.c                | 154 +++--
 arch/arm64/kvm/vgic/vgic.h                    |   6 +
 tools/testing/selftests/kvm/Makefile          |   1 +
 .../selftests/kvm/aarch64/vgic_its_tables.c   | 562 ++++++++++++++++++
 .../kvm/include/aarch64/gic_v3_its.h          |   3 +-
 .../testing/selftests/kvm/include/kvm_util.h  |   4 +-
 .../selftests/kvm/lib/aarch64/gic_v3_its.c    |  24 +-
 7 files changed, 713 insertions(+), 41 deletions(-)
 create mode 100644 tools/testing/selftests/kvm/aarch64/vgic_its_tables.c


base-commit: 59b723cd2adbac2a34fc8e12c74ae26ae45bf230
-- 
2.47.0.199.ga7371fff76-goog

[PATCH v1 1/4] KVM: selftests: aarch64: Test VGIC ITS tables save/restore

[Jing Zhang]

Add a selftest to verify the correctness of the VGIC ITS mappings after
the save/restore operations (KVM_DEV_ARM_ITS_SAVE_TABLES /
KVM_DEV_ARM_ITS_RESTORE_TABLES).
Also calculate the time spending on save/restore operations.
This test uses some corner cases to capture the save/restore bugs. It
will be used to verify the future incoming changes for the VGIC ITS
tables save/restore.

To capture the "Invalid argument (-22)" error, run the test without any
option. To capture the wrong/lost mappings, run the test with '-s'
option.
Since the VGIC ITS save/restore bug is caused by orphaned DTE/ITE
entries, if we run the test with '-c' option whih clears the tables
before the save operation, the test will complete successfully.

Signed-off-by: Jing Zhang <jingzhangos@google.com>
---
 tools/testing/selftests/kvm/Makefile          |   1 +
 .../selftests/kvm/aarch64/vgic_its_tables.c   | 562 ++++++++++++++++++
 .../kvm/include/aarch64/gic_v3_its.h          |   3 +-
 .../testing/selftests/kvm/include/kvm_util.h  |   4 +-
 .../selftests/kvm/lib/aarch64/gic_v3_its.c    |  24 +-
 5 files changed, 588 insertions(+), 6 deletions(-)
 create mode 100644 tools/testing/selftests/kvm/aarch64/vgic_its_tables.c

diff --git a/tools/testing/selftests/kvm/Makefile b/tools/testing/selftests/kvm/Makefile
index 156fbfae940f..9cba573c23f3 100644
--- a/tools/testing/selftests/kvm/Makefile
+++ b/tools/testing/selftests/kvm/Makefile
@@ -163,6 +163,7 @@ TEST_GEN_PROGS_aarch64 += aarch64/smccc_filter
 TEST_GEN_PROGS_aarch64 += aarch64/vcpu_width_config
 TEST_GEN_PROGS_aarch64 += aarch64/vgic_init
 TEST_GEN_PROGS_aarch64 += aarch64/vgic_irq
+TEST_GEN_PROGS_aarch64 += aarch64/vgic_its_tables
 TEST_GEN_PROGS_aarch64 += aarch64/vgic_lpi_stress
 TEST_GEN_PROGS_aarch64 += aarch64/vpmu_counter_access
 TEST_GEN_PROGS_aarch64 += aarch64/no-vgic-v3
diff --git a/tools/testing/selftests/kvm/aarch64/vgic_its_tables.c b/tools/testing/selftests/kvm/aarch64/vgic_its_tables.c
new file mode 100644
index 000000000000..6d01dcb7cbba
--- /dev/null
+++ b/tools/testing/selftests/kvm/aarch64/vgic_its_tables.c
@@ -0,0 +1,562 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * vgic_its_tables - Sanity and performance test for VGIC ITS tables
+ * save/restore.
+ *
+ * Copyright (c) 2024 Google LLC
+ */
+
+#include <linux/sizes.h>
+#include <pthread.h>
+#include <stdatomic.h>
+#include <sys/sysinfo.h>
+
+#include "kvm_util.h"
+#include "gic.h"
+#include "gic_v3.h"
+#include "gic_v3_its.h"
+#include "processor.h"
+#include "ucall.h"
+#include "vgic.h"
+#include "kselftest.h"
+
+
+#define GIC_LPI_OFFSET		8192
+#define TEST_MEMSLOT_INDEX	1
+#define TABLE_SIZE		SZ_64K
+#define DEFAULT_NR_L2		4ULL
+#define DTE_SIZE		8ULL
+#define ITE_SIZE		8ULL
+#define NR_EVENTS		(TABLE_SIZE / ITE_SIZE)
+/* We only have 64K PEND/PROP tables */
+#define MAX_NR_L2		((TABLE_SIZE - GIC_LPI_OFFSET) * DTE_SIZE / TABLE_SIZE)
+
+static vm_paddr_t gpa_base;
+
+static struct kvm_vm *vm;
+static struct kvm_vcpu *vcpu;
+static int gic_fd, its_fd;
+static u32 collection_id = 0;
+
+struct event_id_block {
+	u32 start;
+	u32 size;
+};
+
+static struct mappings_tracker {
+	struct event_id_block *devices;
+	struct event_id_block *devices_va;
+} mtracker;
+
+static struct test_data {
+	vm_paddr_t	l1_device_table;
+	vm_paddr_t	l2_device_tables;
+	vm_paddr_t	collection_table;
+	vm_paddr_t	cmdq_base;
+	void		*cmdq_base_va;
+	vm_paddr_t	itt_tables;
+
+	vm_paddr_t	lpi_prop_table;
+	vm_paddr_t	lpi_pend_tables;
+
+	int		control_cmd;
+	bool		clear_before_save;
+	bool		same_coll_id;
+	size_t		nr_l2_tables;
+	size_t		nr_devices;
+} td = {
+	.clear_before_save = false,
+	.same_coll_id = false,
+	.nr_l2_tables = DEFAULT_NR_L2,
+	.nr_devices = DEFAULT_NR_L2 * TABLE_SIZE / DTE_SIZE,
+};
+
+static void guest_its_mappings_clear(void)
+{
+	memset((void *)td.l2_device_tables, 0, TABLE_SIZE * td.nr_l2_tables);
+	memset((void *)td.collection_table, 0, TABLE_SIZE);
+	memset((void *)td.itt_tables, 0, td.nr_devices * TABLE_SIZE);
+}
+
+static void guest_its_unmap_all(bool update_tracker)
+{
+	u32 device_id, event_id;
+
+	for (device_id = 0; device_id < td.nr_devices; device_id++) {
+		vm_paddr_t itt_base = td.itt_tables + (device_id * TABLE_SIZE);
+		u32 start_id = mtracker.devices[device_id].start;
+		u32 end_id = start_id + mtracker.devices[device_id].size;
+
+		for (event_id = start_id; event_id < end_id ; event_id++)
+			its_send_discard_cmd(td.cmdq_base_va,
+					     device_id, event_id);
+
+		if (end_id - start_id > 0)
+			its_send_mapd_cmd(td.cmdq_base_va, device_id,
+					  itt_base, TABLE_SIZE, false);
+
+		if (update_tracker) {
+			mtracker.devices[device_id].start = 0;
+			mtracker.devices[device_id].size = 0;
+		}
+
+	}
+
+	for (u32 i= 0; i <= collection_id; i++)
+		its_send_mapc_cmd(td.cmdq_base_va, 0, i, false);
+}
+
+static void guest_its_map_single_event(u32 device_id, u32 event_id, u32 coll_id)
+{
+	u32 intid = GIC_LPI_OFFSET;
+
+	guest_its_unmap_all(true);
+
+	its_send_mapc_cmd(td.cmdq_base_va, guest_get_vcpuid(), coll_id, true);
+	its_send_mapd_cmd(td.cmdq_base_va, device_id,
+			  td.itt_tables + (device_id * TABLE_SIZE), TABLE_SIZE, true);
+	its_send_mapti_cmd(td.cmdq_base_va, device_id,
+			   event_id, coll_id, intid);
+
+
+	mtracker.devices[device_id].start = event_id;
+	mtracker.devices[device_id].size = 1;
+}
+
+static void guest_its_map_event_per_device(u32 event_id, u32 coll_id)
+{
+	u32 device_id, intid = GIC_LPI_OFFSET;
+
+	guest_its_unmap_all(true);
+
+	its_send_mapc_cmd(td.cmdq_base_va, guest_get_vcpuid(), coll_id, true);
+
+	for (device_id = 0; device_id < td.nr_devices; device_id++) {
+		vm_paddr_t itt_base = td.itt_tables + (device_id * TABLE_SIZE);
+
+		its_send_mapd_cmd(td.cmdq_base_va, device_id,
+				  itt_base, TABLE_SIZE, true);
+
+		its_send_mapti_cmd(td.cmdq_base_va, device_id,
+				   event_id, coll_id, intid++);
+
+		mtracker.devices[device_id].start = event_id;
+		mtracker.devices[device_id].size = 1;
+
+	}
+}
+
+static void guest_setup_gic(void)
+{
+	u32 cpuid = guest_get_vcpuid();
+
+	gic_init(GIC_V3, 1);
+	gic_rdist_enable_lpis(td.lpi_prop_table, TABLE_SIZE,
+			      td.lpi_pend_tables + (cpuid * TABLE_SIZE));
+
+	guest_its_mappings_clear();
+
+	its_init(td.collection_table, TABLE_SIZE,
+		 td.l1_device_table, TABLE_SIZE,
+		 td.cmdq_base, TABLE_SIZE, true);
+}
+
+enum {
+	GUEST_EXIT,
+	MAP_INIT,
+	MAP_INIT_DONE,
+	MAP_DONE,
+	PREPARE_FOR_SAVE,
+	PREPARE_DONE,
+	MAP_EMPTY,
+	MAP_SINGLE_EVENT_FIRST,
+	MAP_SINGLE_EVENT_LAST,
+	MAP_FIRST_EVENT_PER_DEVICE,
+	MAP_LAST_EVENT_PER_DEVICE,
+};
+
+static void guest_code(size_t nr_lpis)
+{
+	int cmd;
+
+	guest_setup_gic();
+	GUEST_SYNC1(MAP_INIT_DONE);
+
+	while ((cmd = READ_ONCE(td.control_cmd)) != GUEST_EXIT) {
+		switch (cmd) {
+		case MAP_INIT:
+			guest_its_unmap_all(true);
+			if (td.clear_before_save)
+				guest_its_mappings_clear();
+			GUEST_SYNC1(MAP_INIT_DONE);
+			break;
+		case PREPARE_FOR_SAVE:
+			guest_its_unmap_all(false);
+			GUEST_SYNC1(PREPARE_DONE);
+			break;
+		case MAP_EMPTY:
+			guest_its_mappings_clear();
+			GUEST_SYNC1(MAP_DONE);
+			break;
+		case MAP_SINGLE_EVENT_FIRST:
+			guest_its_map_single_event(1, 1, collection_id);
+			if (!td.same_coll_id)
+				collection_id++;
+			GUEST_SYNC1(MAP_DONE);
+			break;
+		case MAP_SINGLE_EVENT_LAST:
+			guest_its_map_single_event(td.nr_devices - 2, NR_EVENTS - 2,
+						   collection_id);
+			if (!td.same_coll_id)
+				collection_id++;
+			GUEST_SYNC1(MAP_DONE);
+			break;
+		case MAP_FIRST_EVENT_PER_DEVICE:
+			guest_its_map_event_per_device(2, collection_id);
+			if (!td.same_coll_id)
+				collection_id++;
+			GUEST_SYNC1(MAP_DONE);
+			break;
+		case MAP_LAST_EVENT_PER_DEVICE:
+			guest_its_map_event_per_device(NR_EVENTS - 3,
+						       collection_id);
+			if (!td.same_coll_id)
+				collection_id++;
+			GUEST_SYNC1(MAP_DONE);
+			break;
+		default:
+			break;
+		}
+	}
+
+	GUEST_DONE();
+}
+
+static void setup_memslot(void)
+{
+	size_t pages;
+	size_t sz;
+
+	/*
+	 * For the ITS:
+	 *  - A single l1 level device table
+	 *  - td.nr_l2_tables l2 level device tables
+	 *  - A single level collection table
+	 *  - The command queue
+	 *  - An ITT for each device
+	 */
+	sz = (3 + td.nr_l2_tables + td.nr_devices) * TABLE_SIZE;
+
+	/*
+	 * For the redistributors:
+	 *  - A shared LPI configuration table
+	 *  - An LPI pending table for the vCPU
+	 */
+	sz += 2 * TABLE_SIZE;
+
+	/*
+	 * For the mappings tracker
+	 */
+	sz += sizeof(*mtracker.devices) * td.nr_devices;
+
+	pages = sz / vm->page_size;
+	gpa_base = ((vm_compute_max_gfn(vm) + 1) * vm->page_size) - sz;
+	vm_userspace_mem_region_add(vm, VM_MEM_SRC_ANONYMOUS, gpa_base,
+				    TEST_MEMSLOT_INDEX, pages, 0);
+}
+
+#define KVM_ITS_L1E_VALID_MASK		BIT_ULL(63)
+#define KVM_ITS_L1E_ADDR_MASK		GENMASK_ULL(51, 16)
+
+static void setup_test_data(void)
+{
+	size_t pages_per_table = vm_calc_num_guest_pages(vm->mode, TABLE_SIZE);
+	size_t pages_mt = sizeof(*mtracker.devices) * td.nr_devices / vm->page_size;
+
+	mtracker.devices = (void *)vm_phy_pages_alloc(vm, pages_mt, gpa_base,
+						      TEST_MEMSLOT_INDEX);
+	virt_map(vm, (vm_paddr_t)mtracker.devices,
+		 (vm_paddr_t)mtracker.devices, pages_mt);
+	mtracker.devices_va = (void *)addr_gpa2hva(vm, (vm_paddr_t)mtracker.devices);
+
+	td.l2_device_tables = vm_phy_pages_alloc(vm,
+						 pages_per_table * td.nr_l2_tables,
+						 gpa_base, TEST_MEMSLOT_INDEX);
+	td.l1_device_table = vm_phy_pages_alloc(vm, pages_per_table,
+						gpa_base,
+						TEST_MEMSLOT_INDEX);
+	td.collection_table = vm_phy_pages_alloc(vm, pages_per_table,
+						gpa_base,
+						TEST_MEMSLOT_INDEX);
+	td.itt_tables = vm_phy_pages_alloc(vm, pages_per_table * td.nr_devices,
+					   gpa_base, TEST_MEMSLOT_INDEX);
+	td.lpi_prop_table = vm_phy_pages_alloc(vm, pages_per_table,
+					       gpa_base, TEST_MEMSLOT_INDEX);
+	td.lpi_pend_tables = vm_phy_pages_alloc(vm, pages_per_table,
+						gpa_base, TEST_MEMSLOT_INDEX);
+	td.cmdq_base = vm_phy_pages_alloc(vm, pages_per_table, gpa_base,
+					  TEST_MEMSLOT_INDEX);
+
+	u64 *l1_tbl = addr_gpa2hva(vm, td.l1_device_table);
+	for (int i = 0; i < td.nr_l2_tables; i++) {
+		u64 l2_addr = ((u64)td.l2_device_tables + i * TABLE_SIZE);
+		*(l1_tbl + i) = cpu_to_le64(l2_addr | KVM_ITS_L1E_VALID_MASK);
+	}
+
+	virt_map(vm, td.l2_device_tables, td.l2_device_tables,
+		 pages_per_table * td.nr_l2_tables);
+	virt_map(vm, td.l1_device_table,
+		 td.l1_device_table, pages_per_table);
+	virt_map(vm, td.collection_table,
+		 td.collection_table, pages_per_table);
+	virt_map(vm, td.itt_tables,
+		 td.itt_tables, pages_per_table * td.nr_devices);
+	virt_map(vm, td.cmdq_base, td.cmdq_base, pages_per_table);
+	td.cmdq_base_va = (void *)td.cmdq_base;
+
+	sync_global_to_guest(vm, mtracker);
+	sync_global_to_guest(vm, td);
+}
+
+static void setup_gic(void)
+{
+	gic_fd = vgic_v3_setup(vm, 1, 64);
+	__TEST_REQUIRE(gic_fd >= 0, "Failed to create GICv3");
+
+	its_fd = vgic_its_setup(vm);
+}
+
+static bool is_mapped(u32 device_id, u32 event_id)
+{
+	vm_paddr_t db_addr = GITS_BASE_GPA + GITS_TRANSLATER;
+
+	struct kvm_msi msi = {
+		.address_lo	= db_addr,
+		.address_hi	= db_addr >> 32,
+		.data		= event_id,
+		.devid		= device_id,
+		.flags		= KVM_MSI_VALID_DEVID,
+	};
+
+	/*
+	 * KVM_SIGNAL_MSI returns 1 if the MSI wasn't 'blocked' by the VM,
+	 * which for arm64 implies having a valid translation in the ITS.
+	 */
+	return __vm_ioctl(vm, KVM_SIGNAL_MSI, &msi);
+}
+
+static bool restored_mappings_sanity_check(void)
+{
+	u64 lost_count = 0, wrong_count = 0;
+	bool pass = true;
+
+	sync_global_from_guest(vm, mtracker);
+
+	ksft_print_msg("\tChecking restored ITS mappings ...\n");
+	for(u32 dev_id = 0; dev_id < td.nr_devices; dev_id++) {
+		u32 start_id = mtracker.devices_va[dev_id].start;
+		u32 end_id = start_id + mtracker.devices_va[dev_id].size;
+
+		for (u32 eid = 0; eid < NR_EVENTS; eid++) {
+			bool save_mapped = eid >= start_id && eid < end_id;
+			bool restore_mapped = is_mapped(dev_id, eid);
+
+			if(save_mapped && !restore_mapped && ++lost_count < 6) {
+				ksft_print_msg("\t\tMapping lost for device:%u, event:%u\n",
+					dev_id, eid);
+				pass = false;
+			} else if (!save_mapped && restore_mapped && ++wrong_count < 6) {
+				ksft_print_msg("\t\tWrong mapping from device:%u, event:%u\n",
+					dev_id, eid);
+				pass = false;
+			}
+			/*
+			 * For test purpose, we only use the first and last 3 events
+			 * per device.
+			 */
+			if (eid == 2)
+				eid = NR_EVENTS - 4;
+		}
+		if (lost_count > 5 || wrong_count > 5) {
+			ksft_print_msg("\tThere are more lost/wrong mappings found.\n");
+			break;
+		}
+	}
+
+	return pass;
+}
+
+static void run_its_tables_save_restore_test(int test_cmd)
+{
+	struct timespec start, delta;
+	struct ucall uc;
+	bool done = false;
+	double duration;
+	bool pass = true;
+
+	write_guest_global(vm, td.control_cmd, MAP_INIT);
+	while (!done) {
+		vcpu_run(vcpu);
+
+		switch (get_ucall(vcpu, &uc)) {
+		case UCALL_SYNC:
+			switch (uc.args[0]) {
+			case MAP_INIT_DONE:
+				write_guest_global(vm, td.control_cmd, test_cmd);
+				break;
+			case MAP_DONE:
+				clock_gettime(CLOCK_MONOTONIC, &start);
+
+				kvm_device_attr_set(its_fd, KVM_DEV_ARM_VGIC_GRP_CTRL,
+						KVM_DEV_ARM_ITS_SAVE_TABLES, NULL);
+
+				delta = timespec_elapsed(start);
+				duration = (double)delta.tv_sec * USEC_PER_SEC;
+				duration += (double)delta.tv_nsec / NSEC_PER_USEC;
+				ksft_print_msg("\tITS tables save time: %.2f (us)\n", duration);
+
+				/* Prepare for restoring */
+				write_guest_global(vm, td.control_cmd, PREPARE_FOR_SAVE);
+				break;
+			case PREPARE_DONE:
+				done = true;
+				break;
+			}
+			break;
+		case UCALL_DONE:
+			done = true;
+			break;
+		case UCALL_ABORT:
+			REPORT_GUEST_ASSERT(uc);
+			break;
+		default:
+			TEST_FAIL("Unknown ucall: %lu", uc.cmd);
+		}
+	}
+
+
+	clock_gettime(CLOCK_MONOTONIC, &start);
+
+	int ret = __kvm_device_attr_set(its_fd, KVM_DEV_ARM_VGIC_GRP_CTRL,
+					KVM_DEV_ARM_ITS_RESTORE_TABLES, NULL);
+	if (ret) {
+		ksft_print_msg("\t");
+		ksft_print_msg(KVM_IOCTL_ERROR(KVM_SET_DEVICE_ATTR, ret));
+		ksft_print_msg("\n");
+		ksft_print_msg("\tFailed to restore ITS tables.\n");
+		pass = false;
+	}
+
+	delta = timespec_elapsed(start);
+	duration = (double)delta.tv_sec * USEC_PER_SEC;
+	duration += (double)delta.tv_nsec / NSEC_PER_USEC;
+	ksft_print_msg("\tITS tables restore time: %.2f (us)\n", duration);
+
+	if (restored_mappings_sanity_check() && pass)
+		ksft_test_result_pass("*** PASSED ***\n");
+	else
+		ksft_test_result_fail("*** FAILED ***\n");
+
+}
+
+static void setup_vm(void)
+{
+	vm = __vm_create_with_one_vcpu(&vcpu, 1024*1024, guest_code);
+
+	setup_memslot();
+
+	setup_gic();
+
+	setup_test_data();
+}
+
+static void destroy_vm(void)
+{
+	close(its_fd);
+	close(gic_fd);
+	kvm_vm_free(vm);
+}
+
+static void run_test(int test_cmd)
+{
+	pr_info("------------------------------------------------------------------------------\n");
+	switch (test_cmd) {
+	case MAP_EMPTY:
+		pr_info("Test ITS save/restore with empty mapping\n");
+		break;
+	case MAP_SINGLE_EVENT_FIRST:
+		pr_info("Test ITS save/restore with one mapping (device:1, event:1)\n");
+		break;
+	case MAP_SINGLE_EVENT_LAST:
+		pr_info("Test ITS save/restore with one mapping (device:%zu, event:%llu)\n",
+			td.nr_devices - 2, NR_EVENTS - 2);
+		break;
+	case MAP_FIRST_EVENT_PER_DEVICE:
+		pr_info("Test ITS save/restore with one small event per device (device:[0-%zu], event:2)\n",
+			td.nr_devices - 1);
+		break;
+	case MAP_LAST_EVENT_PER_DEVICE:
+		pr_info("Test ITS save/restore with one big event per device (device:[0-%zu], event:%llu)\n",
+			td.nr_devices - 1, NR_EVENTS - 3);
+		break;
+	}
+	pr_info("------------------------------------------------------------------------------\n");
+
+	run_its_tables_save_restore_test(test_cmd);
+
+	ksft_print_msg("\n");
+}
+
+static void pr_usage(const char *name)
+{
+	pr_info("%s -c -s -h\n", name);
+	pr_info("  -c:\tclear ITS tables entries before saving\n");
+	pr_info("  -s:\tuse the same collection ID for all mappings\n");
+	pr_info("  -n:\tnumber of L2 device tables (default: %zu, range: [1 - %llu])\n",
+		td.nr_l2_tables, MAX_NR_L2);
+}
+
+int main(int argc, char **argv)
+{
+	int c;
+
+	while ((c = getopt(argc, argv, "hcsn:")) != -1) {
+		switch (c) {
+		case 'c':
+			td.clear_before_save = true;
+			break;
+		case 's':
+			td.same_coll_id = true;
+			break;
+		case 'n':
+			td.nr_l2_tables = atoi(optarg);
+			if (td.nr_l2_tables > 0 && td.nr_l2_tables <= MAX_NR_L2) {
+				td.nr_devices = td.nr_l2_tables * TABLE_SIZE / DTE_SIZE;
+				break;
+			}
+			pr_info("The specified number of L2 device tables is out of range!\n");
+		case 'h':
+		default:
+			pr_usage(argv[0]);
+			return 1;
+		}
+	}
+
+	ksft_print_header();
+
+	setup_vm();
+
+	ksft_set_plan(5);
+
+	run_test(MAP_EMPTY);
+	run_test(MAP_SINGLE_EVENT_FIRST);
+	run_test(MAP_SINGLE_EVENT_LAST);
+	run_test(MAP_FIRST_EVENT_PER_DEVICE);
+	run_test(MAP_LAST_EVENT_PER_DEVICE);
+
+	destroy_vm();
+
+	ksft_finished();
+
+	return 0;
+}
diff --git a/tools/testing/selftests/kvm/include/aarch64/gic_v3_its.h b/tools/testing/selftests/kvm/include/aarch64/gic_v3_its.h
index 3722ed9c8f96..ecf1eb955471 100644
--- a/tools/testing/selftests/kvm/include/aarch64/gic_v3_its.h
+++ b/tools/testing/selftests/kvm/include/aarch64/gic_v3_its.h
@@ -7,7 +7,7 @@
 
 void its_init(vm_paddr_t coll_tbl, size_t coll_tbl_sz,
 	      vm_paddr_t device_tbl, size_t device_tbl_sz,
-	      vm_paddr_t cmdq, size_t cmdq_size);
+	      vm_paddr_t cmdq, size_t cmdq_size, bool indirect_device_tbl);
 
 void its_send_mapd_cmd(void *cmdq_base, u32 device_id, vm_paddr_t itt_base,
 		       size_t itt_size, bool valid);
@@ -15,5 +15,6 @@ void its_send_mapc_cmd(void *cmdq_base, u32 vcpu_id, u32 collection_id, bool val
 void its_send_mapti_cmd(void *cmdq_base, u32 device_id, u32 event_id,
 			u32 collection_id, u32 intid);
 void its_send_invall_cmd(void *cmdq_base, u32 collection_id);
+void its_send_discard_cmd(void *cmdq_base, u32 device_id, u32 event_id);
 
 #endif // __SELFTESTS_GIC_V3_ITS_H__
diff --git a/tools/testing/selftests/kvm/include/kvm_util.h b/tools/testing/selftests/kvm/include/kvm_util.h
index bc7c242480d6..3abe06ad1f85 100644
--- a/tools/testing/selftests/kvm/include/kvm_util.h
+++ b/tools/testing/selftests/kvm/include/kvm_util.h
@@ -27,7 +27,9 @@
 #define KVM_DEV_PATH "/dev/kvm"
 #define KVM_MAX_VCPUS 512
 
-#define NSEC_PER_SEC 1000000000L
+#define NSEC_PER_USEC	1000L
+#define USEC_PER_SEC	1000000L
+#define NSEC_PER_SEC	1000000000L
 
 struct userspace_mem_region {
 	struct kvm_userspace_memory_region2 region;
diff --git a/tools/testing/selftests/kvm/lib/aarch64/gic_v3_its.c b/tools/testing/selftests/kvm/lib/aarch64/gic_v3_its.c
index 09f270545646..cd3c65d762d2 100644
--- a/tools/testing/selftests/kvm/lib/aarch64/gic_v3_its.c
+++ b/tools/testing/selftests/kvm/lib/aarch64/gic_v3_its.c
@@ -52,7 +52,8 @@ static unsigned long its_find_baser(unsigned int type)
 	return -1;
 }
 
-static void its_install_table(unsigned int type, vm_paddr_t base, size_t size)
+static void its_install_table(unsigned int type, vm_paddr_t base,
+			      size_t size, bool indirect)
 {
 	unsigned long offset = its_find_baser(type);
 	u64 baser;
@@ -64,6 +65,9 @@ static void its_install_table(unsigned int type, vm_paddr_t base, size_t size)
 		GITS_BASER_RaWaWb |
 		GITS_BASER_VALID;
 
+	if (indirect)
+		baser |= GITS_BASER_INDIRECT;
+
 	its_write_u64(offset, baser);
 }
 
@@ -82,12 +86,13 @@ static void its_install_cmdq(vm_paddr_t base, size_t size)
 
 void its_init(vm_paddr_t coll_tbl, size_t coll_tbl_sz,
 	      vm_paddr_t device_tbl, size_t device_tbl_sz,
-	      vm_paddr_t cmdq, size_t cmdq_size)
+	      vm_paddr_t cmdq, size_t cmdq_size, bool indirect_device_tbl)
 {
 	u32 ctlr;
 
-	its_install_table(GITS_BASER_TYPE_COLLECTION, coll_tbl, coll_tbl_sz);
-	its_install_table(GITS_BASER_TYPE_DEVICE, device_tbl, device_tbl_sz);
+	its_install_table(GITS_BASER_TYPE_COLLECTION, coll_tbl, coll_tbl_sz, false);
+	its_install_table(GITS_BASER_TYPE_DEVICE, device_tbl, device_tbl_sz,
+			  indirect_device_tbl);
 	its_install_cmdq(cmdq, cmdq_size);
 
 	ctlr = its_read_u32(GITS_CTLR);
@@ -237,6 +242,17 @@ void its_send_mapti_cmd(void *cmdq_base, u32 device_id, u32 event_id,
 	its_send_cmd(cmdq_base, &cmd);
 }
 
+void its_send_discard_cmd(void *cmdq_base, u32 device_id, u32 event_id)
+{
+	struct its_cmd_block cmd = {};
+
+	its_encode_cmd(&cmd, GITS_CMD_DISCARD);
+	its_encode_devid(&cmd, device_id);
+	its_encode_event_id(&cmd, event_id);
+
+	its_send_cmd(cmdq_base, &cmd);
+}
+
 void its_send_invall_cmd(void *cmdq_base, u32 collection_id)
 {
 	struct its_cmd_block cmd = {};
-- 
2.47.0.199.ga7371fff76-goog

[PATCH v1 2/4] KVM: arm64: vgic-its: Add a dummy DTE/ITE if necessary in ITS tables save operation

[Jing Zhang]

In device tables/ITTs, DTEs/ITEs are implemented as a static single
linked list. But the head of the list might not be the first DTE/ITE in
the table. That's why in the restore operation, the DTs/ITTs have to be
scanned to find the first valid DTE/ITE (head of the list).
Add a dummy DTE/ITE in the first entry of the table if the first entry
doesn't have a valid DTE/ITE. This dummy DTE/ITE points to the first
valid DTE/ITE if there is a valid one.
This change paves the way for future incoming changes which will utilize
the fixed head the DTE/ITE list to avoid scanning uncessary table
entries.

No functional change intended.

Signed-off-by: Jing Zhang <jingzhangos@google.com>
---
 arch/arm64/kvm/vgic/vgic-its.c | 56 ++++++++++++++++++++++++++++++++--
 arch/arm64/kvm/vgic/vgic.h     |  6 ++++
 2 files changed, 59 insertions(+), 3 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index ba945ba78cc7..953af024d94a 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -2176,10 +2176,12 @@ static int vgic_its_ite_cmp(void *priv, const struct list_head *a,
 static int vgic_its_save_itt(struct vgic_its *its, struct its_device *device)
 {
 	const struct vgic_its_abi *abi = vgic_its_get_abi(its);
+	struct its_ite *ite, *first_ite = NULL;
+	struct kvm *kvm = its->dev->kvm;
 	gpa_t base = device->itt_addr;
-	struct its_ite *ite;
-	int ret;
 	int ite_esz = abi->ite_esz;
+	u64 val = 0;
+	int ret;
 
 	list_sort(NULL, &device->itt_head, vgic_its_ite_cmp);
 
@@ -2198,7 +2200,24 @@ static int vgic_its_save_itt(struct vgic_its *its, struct its_device *device)
 		ret = vgic_its_save_ite(its, device, ite, gpa, ite_esz);
 		if (ret)
 			return ret;
+
+		if (!first_ite)
+			first_ite = ite;
 	}
+
+	/*
+	 * As for DTEs, add a dummy ITE if necessary for ITT to avoid uncessary
+	 * sanning in the store operation.
+	 */
+	if (first_ite && first_ite->event_id)
+		val = (u64)first_ite->event_id << KVM_ITS_ITE_NEXT_SHIFT;
+
+	if (!first_ite || first_ite->event_id) {
+		val |= KVM_ITS_ENTRY_DUMMY_MAGIC << KVM_ITS_ENTRY_DUMMY_SHIFT;
+		val = cpu_to_le64(val);
+		vgic_write_guest_lock(kvm, base, &val, ite_esz);
+	}
+
 	return 0;
 }
 
@@ -2328,8 +2347,11 @@ static int vgic_its_save_device_tables(struct vgic_its *its)
 {
 	const struct vgic_its_abi *abi = vgic_its_get_abi(its);
 	u64 baser = its->baser_device_table;
-	struct its_device *dev;
+	struct its_device *dev, *first_dev = NULL;
+	struct kvm *kvm = its->dev->kvm;
 	int dte_esz = abi->dte_esz;
+	gpa_t dummy_eaddr;
+	u64 val = 0;
 
 	if (!(baser & GITS_BASER_VALID))
 		return 0;
@@ -2351,7 +2373,35 @@ static int vgic_its_save_device_tables(struct vgic_its *its)
 		ret = vgic_its_save_dte(its, dev, eaddr, dte_esz);
 		if (ret)
 			return ret;
+
+		if (!first_dev)
+			first_dev = dev;
 	}
+
+	/*
+	 * The valid DTEs in the device table are linked with a static single
+	 * linked list, but the list head is not always the first DTE. That's
+	 * why the restore operation has to scan the device table from the first
+	 * entry all the time.
+	 * To avoid the uncessary scanning in the restore operation, if the
+	 * first valid DTE is not the first one in the table, add a dummy DTE
+	 * with valid bit as 0 pointing to the first valid DTE.
+	 * This way, the first DTE in the table is always the head of the DTE
+	 * list. It is either a valid DTE or a dummy DTE (V= 0) pointing to the
+	 * first valid DTE if there is a valid DTE in the table.
+	 */
+	if (first_dev && first_dev->device_id)
+		val = (u64)first_dev->device_id << KVM_ITS_DTE_DUMMY_NEXT_SHIFT;
+
+	if (!first_dev || first_dev->device_id) {
+		if (!vgic_its_check_id(its, baser, 0, &dummy_eaddr))
+			return -EINVAL;
+
+		val |= KVM_ITS_ENTRY_DUMMY_MAGIC << KVM_ITS_ENTRY_DUMMY_SHIFT;
+		val = cpu_to_le64(val);
+		vgic_write_guest_lock(kvm, dummy_eaddr, &val, dte_esz);
+	}
+
 	return 0;
 }
 
diff --git a/arch/arm64/kvm/vgic/vgic.h b/arch/arm64/kvm/vgic/vgic.h
index f2486b4d9f95..93314f249343 100644
--- a/arch/arm64/kvm/vgic/vgic.h
+++ b/arch/arm64/kvm/vgic/vgic.h
@@ -86,6 +86,12 @@
 #define KVM_ITS_L1E_VALID_MASK		BIT_ULL(63)
 /* we only support 64 kB translation table page size */
 #define KVM_ITS_L1E_ADDR_MASK		GENMASK_ULL(51, 16)
+/* Macros for dummy ITE/DTE */
+#define KVM_ITS_ENTRY_DUMMY_SHIFT	0
+#define KVM_ITS_ENTRY_DUMMY_MASK	GENMASK_ULL(15, 0)
+#define KVM_ITS_ENTRY_DUMMY_MAGIC	0xdafe
+#define KVM_ITS_DTE_DUMMY_NEXT_SHIFT	16
+#define KVM_ITS_DTE_DUMMY_NEXT_MASK	GENMASK(48, 16)
 
 #define KVM_VGIC_V3_RDIST_INDEX_MASK	GENMASK_ULL(11, 0)
 #define KVM_VGIC_V3_RDIST_FLAGS_MASK	GENMASK_ULL(15, 12)
-- 
2.47.0.199.ga7371fff76-goog

[PATCH v1 3/4] KVM: arm64: vgic-its: Return device/event id instead of offset in ITS tables restore

[Jing Zhang]

In ITS tables restore operation, the id offset is passing around during
table scanning. But, e can derive more information from a device/event
id, since device table and ITT are indexed by the id.
Pass around the next device/event id instead of id offset to ease the
implementation for incoming changes.
A side benefit of this change is that the 2-level device table scanning
would be more efficient. With the deivce id, we don't have to scan the
L1 table entry one by one, the scanning can jump directly to the DTE in
the L2 table.

Signed-off-by: Jing Zhang <jingzhangos@google.com>
---
 arch/arm64/kvm/vgic/vgic-its.c | 56 ++++++++++++++++++++--------------
 1 file changed, 33 insertions(+), 23 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 953af024d94a..867cc5d3521d 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -2041,15 +2041,17 @@ typedef int (*entry_fn_t)(struct vgic_its *its, u32 id, void *entry,
  * (non zero for 2d level tables)
  * @fn: function to apply on each entry
  * @opaque: pointer to opaque data
+ * @l1_tbl: true if it is a l1 table in a 2-level structure
  *
- * Return: < 0 on error, 0 if last element was identified, 1 otherwise
- * (the last element may not be found on second level tables)
+ * Return: < 0 on error, 0 if last element was identified, next id (device id or
+ * event id) of next valid entry.
  */
 static int scan_its_table(struct vgic_its *its, gpa_t base, int size, u32 esz,
-			  int start_id, entry_fn_t fn, void *opaque)
+			  int start_id, entry_fn_t fn, void *opaque, bool l1_tbl)
 {
 	struct kvm *kvm = its->dev->kvm;
 	unsigned long len = size;
+	int next_id = start_id;
 	int id = start_id;
 	gpa_t gpa = base;
 	char entry[ESZ_MAX];
@@ -2065,8 +2067,16 @@ static int scan_its_table(struct vgic_its *its, gpa_t base, int size, u32 esz,
 		if (ret)
 			return ret;
 
-		next_offset = fn(its, id, entry, opaque);
-		if (next_offset <= 0)
+		next_id = fn(its, next_id, entry, opaque);
+		if (next_id <= 0)
+			return next_id;
+
+		if (l1_tbl)
+			next_offset = next_id * esz / SZ_64K - id;
+		else
+			next_offset = next_id - id;
+
+		if (!next_offset)
 			return next_offset;
 
 		byte_offset = next_offset * esz;
@@ -2077,7 +2087,7 @@ static int scan_its_table(struct vgic_its *its, gpa_t base, int size, u32 esz,
 		gpa += byte_offset;
 		len -= byte_offset;
 	}
-	return 1;
+	return next_id;
 }
 
 /*
@@ -2128,7 +2138,7 @@ static int vgic_its_restore_ite(struct vgic_its *its, u32 event_id,
 	lpi_id = (val & KVM_ITS_ITE_PINTID_MASK) >> KVM_ITS_ITE_PINTID_SHIFT;
 
 	if (!lpi_id)
-		return 1; /* invalid entry, no choice but to scan next entry */
+		return event_id + 1; /* invalid entry, no choice but to scan next entry */
 
 	if (lpi_id < VGIC_MIN_LPI)
 		return -EINVAL;
@@ -2158,7 +2168,7 @@ static int vgic_its_restore_ite(struct vgic_its *its, u32 event_id,
 	}
 	ite->irq = irq;
 
-	return offset;
+	return event_id + offset;
 }
 
 static int vgic_its_ite_cmp(void *priv, const struct list_head *a,
@@ -2238,7 +2248,7 @@ static int vgic_its_restore_itt(struct vgic_its *its, struct its_device *dev)
 	size_t max_size = BIT_ULL(dev->num_eventid_bits) * ite_esz;
 
 	ret = scan_its_table(its, base, max_size, ite_esz, 0,
-			     vgic_its_restore_ite, dev);
+			     vgic_its_restore_ite, dev, false);
 
 	/* scan_its_table returns +1 if all ITEs are invalid */
 	if (ret > 0)
@@ -2280,8 +2290,8 @@ static int vgic_its_save_dte(struct vgic_its *its, struct its_device *dev,
  * @ptr: kernel VA where the 8 byte DTE is located
  * @opaque: unused
  *
- * Return: < 0 on error, 0 if the dte is the last one, id offset to the
- * next dte otherwise
+ * Return: < 0 on error, device id of the current DTE if it
+ * is the last one, device id of the next DTE otherwise
  */
 static int vgic_its_restore_dte(struct vgic_its *its, u32 id,
 				void *ptr, void *opaque)
@@ -2303,7 +2313,7 @@ static int vgic_its_restore_dte(struct vgic_its *its, u32 id,
 			>> KVM_ITS_DTE_ITTADDR_SHIFT) << 8;
 
 	if (!valid)
-		return 1;
+		return id + 1;
 
 	/* dte entry is valid */
 	offset = (entry & KVM_ITS_DTE_NEXT_MASK) >> KVM_ITS_DTE_NEXT_SHIFT;
@@ -2321,7 +2331,7 @@ static int vgic_its_restore_dte(struct vgic_its *its, u32 id,
 		return ret;
 	}
 
-	return offset;
+	return id + offset;
 }
 
 static int vgic_its_device_cmp(void *priv, const struct list_head *a,
@@ -2409,33 +2419,33 @@ static int vgic_its_save_device_tables(struct vgic_its *its)
  * handle_l1_dte - callback used for L1 device table entries (2 stage case)
  *
  * @its: its handle
- * @id: index of the entry in the L1 table
+ * @id: the start device id to scan in the L2 table
  * @addr: kernel VA
  * @opaque: unused
  *
- * L1 table entries are scanned by steps of 1 entry
  * Return < 0 if error, 0 if last dte was found when scanning the L2
- * table, +1 otherwise (meaning next L1 entry must be scanned)
+ * table, device id of the next valid DTE otherwise
  */
 static int handle_l1_dte(struct vgic_its *its, u32 id, void *addr,
 			 void *opaque)
 {
 	const struct vgic_its_abi *abi = vgic_its_get_abi(its);
-	int l2_start_id = id * (SZ_64K / abi->dte_esz);
 	u64 entry = *(u64 *)addr;
 	int dte_esz = abi->dte_esz;
+	int dte_per_table = SZ_64K / dte_esz;
+	gpa_t gpa_offset = (id % dte_per_table) * dte_esz;
 	gpa_t gpa;
 	int ret;
 
 	entry = le64_to_cpu(entry);
 
 	if (!(entry & KVM_ITS_L1E_VALID_MASK))
-		return 1;
+		return (id + 1) * dte_per_table;
 
-	gpa = entry & KVM_ITS_L1E_ADDR_MASK;
+	gpa = (entry & KVM_ITS_L1E_ADDR_MASK) + gpa_offset;
 
-	ret = scan_its_table(its, gpa, SZ_64K, dte_esz,
-			     l2_start_id, vgic_its_restore_dte, NULL);
+	ret = scan_its_table(its, gpa, SZ_64K - gpa_offset , dte_esz,
+			     id, vgic_its_restore_dte, NULL, false);
 
 	return ret;
 }
@@ -2460,11 +2470,11 @@ static int vgic_its_restore_device_tables(struct vgic_its *its)
 	if (baser & GITS_BASER_INDIRECT) {
 		l1_esz = GITS_LVL1_ENTRY_SIZE;
 		ret = scan_its_table(its, l1_gpa, l1_tbl_size, l1_esz, 0,
-				     handle_l1_dte, NULL);
+				     handle_l1_dte, NULL, true);
 	} else {
 		l1_esz = abi->dte_esz;
 		ret = scan_its_table(its, l1_gpa, l1_tbl_size, l1_esz, 0,
-				     vgic_its_restore_dte, NULL);
+				     vgic_its_restore_dte, NULL, false);
 	}
 
 	/* scan_its_table returns +1 if all entries are invalid */
-- 
2.47.0.199.ga7371fff76-goog

[PATCH v1 4/4] KVM: arm64: vgic-its: Utilize the dummy entry in ITS tables restoring

[Jing Zhang]

Now, the first entry in tables is either a valid DTE/ITE or a dummy
entry pointing to the first valid DTE/ITE. Revise the DTE/ITE restore
process to utilize the dummy entry to avoid unnecessary (erroneous)
entry scanning.
This is not supposed to break the ITS table ABI REV0.

Signed-off-by: Jing Zhang <jingzhangos@google.com>
---
 arch/arm64/kvm/vgic/vgic-its.c | 46 ++++++++++++++++++++++++++--------
 1 file changed, 35 insertions(+), 11 deletions(-)

diff --git a/arch/arm64/kvm/vgic/vgic-its.c b/arch/arm64/kvm/vgic/vgic-its.c
index 867cc5d3521d..e07939613f5c 100644
--- a/arch/arm64/kvm/vgic/vgic-its.c
+++ b/arch/arm64/kvm/vgic/vgic-its.c
@@ -2129,23 +2129,30 @@ static int vgic_its_restore_ite(struct vgic_its *its, u32 event_id,
 	u32 coll_id, lpi_id;
 	struct its_ite *ite;
 	u32 offset;
+	u32 magic;
 
 	val = *p;
 
 	val = le64_to_cpu(val);
 
-	coll_id = val & KVM_ITS_ITE_ICID_MASK;
 	lpi_id = (val & KVM_ITS_ITE_PINTID_MASK) >> KVM_ITS_ITE_PINTID_SHIFT;
 
-	if (!lpi_id)
-		return event_id + 1; /* invalid entry, no choice but to scan next entry */
+	offset = val >> KVM_ITS_ITE_NEXT_SHIFT;
+	if (event_id + offset >= BIT_ULL(dev->num_eventid_bits))
+		return -EINVAL;
+
+	if (!lpi_id) {
+		magic = (val & KVM_ITS_ENTRY_DUMMY_MASK) >> KVM_ITS_ENTRY_DUMMY_SHIFT;
+		if (magic != KVM_ITS_ENTRY_DUMMY_MAGIC)
+			offset = 1;
+
+		return event_id + offset;
+	}
 
 	if (lpi_id < VGIC_MIN_LPI)
 		return -EINVAL;
 
-	offset = val >> KVM_ITS_ITE_NEXT_SHIFT;
-	if (event_id + offset >= BIT_ULL(dev->num_eventid_bits))
-		return -EINVAL;
+	coll_id = val & KVM_ITS_ITE_ICID_MASK;
 
 	collection = find_collection(its, coll_id);
 	if (!collection)
@@ -2303,17 +2310,30 @@ static int vgic_its_restore_dte(struct vgic_its *its, u32 id,
 	u64 entry = *(u64 *)ptr;
 	bool valid;
 	u32 offset;
+	u32 magic;
 	int ret;
 
 	entry = le64_to_cpu(entry);
 
 	valid = entry >> KVM_ITS_DTE_VALID_SHIFT;
-	num_eventid_bits = (entry & KVM_ITS_DTE_SIZE_MASK) + 1;
-	itt_addr = ((entry & KVM_ITS_DTE_ITTADDR_MASK)
-			>> KVM_ITS_DTE_ITTADDR_SHIFT) << 8;
 
-	if (!valid)
-		return id + 1;
+	/*
+	 * Since we created a dummy head entry for the DTE static linked list in
+	 * the table if necessary, no need to scan to find the list head.
+	 * But if the saved table was done without dummy entry support, we still
+	 * have to scan one by one.
+	 */
+	if (!valid) {
+		magic = (entry & KVM_ITS_ENTRY_DUMMY_MASK) >>
+			KVM_ITS_ENTRY_DUMMY_SHIFT;
+		if (magic != KVM_ITS_ENTRY_DUMMY_MAGIC)
+			offset = 1;
+		else
+			offset = (entry & KVM_ITS_DTE_DUMMY_NEXT_MASK) >>
+				  KVM_ITS_DTE_DUMMY_NEXT_SHIFT;
+
+		return id + offset;
+	}
 
 	/* dte entry is valid */
 	offset = (entry & KVM_ITS_DTE_NEXT_MASK) >> KVM_ITS_DTE_NEXT_SHIFT;
@@ -2321,6 +2341,10 @@ static int vgic_its_restore_dte(struct vgic_its *its, u32 id,
 	if (!vgic_its_check_id(its, baser, id, NULL))
 		return -EINVAL;
 
+	num_eventid_bits = (entry & KVM_ITS_DTE_SIZE_MASK) + 1;
+	itt_addr = ((entry & KVM_ITS_DTE_ITTADDR_MASK)
+			>> KVM_ITS_DTE_ITTADDR_SHIFT) << 8;
+
 	dev = vgic_its_alloc_device(its, id, itt_addr, num_eventid_bits);
 	if (IS_ERR(dev))
 		return PTR_ERR(dev);
-- 
2.47.0.199.ga7371fff76-goog

Re: [PATCH v1 0/4] Fix a bug in VGIC ITS tables' save/restore

[Oliver Upton]

Hi Jing,

On Tue, Nov 05, 2024 at 11:34:18AM -0800, Jing Zhang wrote:
> The core issue stems from the static linked list implementation of DTEs/ITEs,
> requiring a full table scan to locate the list head during restoration. This
> scan increases the likelihood of encountering orphaned entries.  To rectify
> this, the patch series introduces a dummy head to the list, enabling immediate
> access to the list head and bypassing the scan. This optimization not only
> resolves the bug but also significantly enhances restore performance,
> particularly in edge cases where valid entries reside at the end of the table.

I think we need a more targeted fix (i.e. Kunkun's patch) to stop the
bleeding + backport it to stable.

Then we can have a separate discussion about improving the save/restore
performance with your approach.

-- 
Thanks,
Oliver

Re: [PATCH v1 0/4] Fix a bug in VGIC ITS tables' save/restore

[Jing Zhang]

On Tue, Nov 5, 2024 at 1:33 PM Oliver Upton <oliver.upton@linux.dev> wrote:
>
> Hi Jing,
>
> On Tue, Nov 05, 2024 at 11:34:18AM -0800, Jing Zhang wrote:
> > The core issue stems from the static linked list implementation of DTEs/ITEs,
> > requiring a full table scan to locate the list head during restoration. This
> > scan increases the likelihood of encountering orphaned entries.  To rectify
> > this, the patch series introduces a dummy head to the list, enabling immediate
> > access to the list head and bypassing the scan. This optimization not only
> > resolves the bug but also significantly enhances restore performance,
> > particularly in edge cases where valid entries reside at the end of the table.
>
> I think we need a more targeted fix (i.e. Kunkun's patch) to stop the
> bleeding + backport it to stable.
>
> Then we can have a separate discussion about improving the save/restore
> performance with your approach.

Yes, I'll respin Kunkun's patch soon. This patch series has the
selftest which we can use for verification.

>
> --
> Thanks,
> Oliver

Thanks,
Jing

Re: [PATCH v1 0/4] Fix a bug in VGIC ITS tables' save/restore

[Oliver Upton]

On Tue, Nov 05, 2024 at 01:56:14PM -0800, Jing Zhang wrote:
> On Tue, Nov 5, 2024 at 1:33 PM Oliver Upton <oliver.upton@linux.dev> wrote:
> >
> > Hi Jing,
> >
> > On Tue, Nov 05, 2024 at 11:34:18AM -0800, Jing Zhang wrote:
> > > The core issue stems from the static linked list implementation of DTEs/ITEs,
> > > requiring a full table scan to locate the list head during restoration. This
> > > scan increases the likelihood of encountering orphaned entries.  To rectify
> > > this, the patch series introduces a dummy head to the list, enabling immediate
> > > access to the list head and bypassing the scan. This optimization not only
> > > resolves the bug but also significantly enhances restore performance,
> > > particularly in edge cases where valid entries reside at the end of the table.
> >
> > I think we need a more targeted fix (i.e. Kunkun's patch) to stop the
> > bleeding + backport it to stable.
> >
> > Then we can have a separate discussion about improving the save/restore
> > performance with your approach.
> 
> Yes, I'll respin Kunkun's patch soon. This patch series has the
> selftest which we can use for verification.

Right -- go ahead and include your selftest as part of that respin, I'd
definitely like to have some test coverage for this whole save/restore mess.

-- 
Thanks,
Oliver