[PATCH v6 0/3] KVM: selftests: randomize memory access of dirty_log_perf_test

[PATCH v6 0/3] KVM: selftests: randomize memory access of dirty_log_perf_test

[Colton Lewis]

Add the ability to randomize parts of dirty_log_perf_test,
specifically the order pages are accessed and whether pages are read
or written.

v6:

Change default random seed to the constant 0.

Explain why 100% writes in populate phase, why no random access in
populate phase, and why use two random numbers in the guest code.

Colton Lewis (3):
  KVM: selftests: implement random number generation for guest code
  KVM: selftests: randomize which pages are written vs read
  KVM: selftests: randomize page access order

 .../selftests/kvm/access_tracking_perf_test.c |  2 +-
 .../selftests/kvm/dirty_log_perf_test.c       | 55 ++++++++++++++-----
 .../selftests/kvm/include/perf_test_util.h    |  8 ++-
 .../testing/selftests/kvm/include/test_util.h |  2 +
 .../selftests/kvm/lib/perf_test_util.c        | 39 ++++++++++---
 tools/testing/selftests/kvm/lib/test_util.c   |  9 +++
 6 files changed, 90 insertions(+), 25 deletions(-)

--
2.37.2.789.g6183377224-goog

[PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Colton Lewis]

Implement random number generation for guest code to randomize parts
of the test, making it less predictable and a more accurate reflection
of reality.

Create a -r argument to specify a random seed. If no argument is
provided, the seed defaults to 0. The random seed is set with
perf_test_set_random_seed() and must be set before guest_code runs to
apply.

The random number generator chosen is the Park-Miller Linear
Congruential Generator, a fancy name for a basic and well-understood
random number generator entirely sufficient for this purpose. Each
vCPU calculates its own seed by adding its index to the seed provided.

Signed-off-by: Colton Lewis <coltonlewis@google.com>
Reviewed-by: Ricardo Koller <ricarkol@google.com>
---
 tools/testing/selftests/kvm/dirty_log_perf_test.c    | 12 ++++++++++--
 tools/testing/selftests/kvm/include/perf_test_util.h |  2 ++
 tools/testing/selftests/kvm/include/test_util.h      |  2 ++
 tools/testing/selftests/kvm/lib/perf_test_util.c     |  8 ++++++++
 tools/testing/selftests/kvm/lib/test_util.c          |  9 +++++++++
 5 files changed, 31 insertions(+), 2 deletions(-)

diff --git a/tools/testing/selftests/kvm/dirty_log_perf_test.c b/tools/testing/selftests/kvm/dirty_log_perf_test.c
index d60a34cdfaee..a89a620f50d4 100644
--- a/tools/testing/selftests/kvm/dirty_log_perf_test.c
+++ b/tools/testing/selftests/kvm/dirty_log_perf_test.c
@@ -126,6 +126,7 @@ struct test_params {
 	bool partition_vcpu_memory_access;
 	enum vm_mem_backing_src_type backing_src;
 	int slots;
+	uint32_t random_seed;
 };
 
 static void toggle_dirty_logging(struct kvm_vm *vm, int slots, bool enable)
@@ -220,6 +221,9 @@ static void run_test(enum vm_guest_mode mode, void *arg)
 				 p->slots, p->backing_src,
 				 p->partition_vcpu_memory_access);
 
+	/* If no argument provided, random seed will be 0. */
+	pr_info("Random seed: %u\n", p->random_seed);
+	perf_test_set_random_seed(vm, p->random_seed);
 	perf_test_set_wr_fract(vm, p->wr_fract);
 
 	guest_num_pages = (nr_vcpus * guest_percpu_mem_size) >> vm_get_page_shift(vm);
@@ -337,7 +341,7 @@ static void help(char *name)
 {
 	puts("");
 	printf("usage: %s [-h] [-i iterations] [-p offset] [-g] "
-	       "[-m mode] [-n] [-b vcpu bytes] [-v vcpus] [-o] [-s mem type]"
+	       "[-m mode] [-n] [-b vcpu bytes] [-v vcpus] [-o] [-r random seed ] [-s mem type]"
 	       "[-x memslots]\n", name);
 	puts("");
 	printf(" -i: specify iteration counts (default: %"PRIu64")\n",
@@ -362,6 +366,7 @@ static void help(char *name)
 	printf(" -v: specify the number of vCPUs to run.\n");
 	printf(" -o: Overlap guest memory accesses instead of partitioning\n"
 	       "     them into a separate region of memory for each vCPU.\n");
+	printf(" -r: specify the starting random seed.\n");
 	backing_src_help("-s");
 	printf(" -x: Split the memory region into this number of memslots.\n"
 	       "     (default: 1)\n");
@@ -388,7 +393,7 @@ int main(int argc, char *argv[])
 
 	guest_modes_append_default();
 
-	while ((opt = getopt(argc, argv, "ghi:p:m:nb:f:v:os:x:")) != -1) {
+	while ((opt = getopt(argc, argv, "ghi:p:m:nb:f:v:or:s:x:")) != -1) {
 		switch (opt) {
 		case 'g':
 			dirty_log_manual_caps = 0;
@@ -421,6 +426,9 @@ int main(int argc, char *argv[])
 		case 'o':
 			p.partition_vcpu_memory_access = false;
 			break;
+		case 'r':
+			p.random_seed = atoi(optarg);
+			break;
 		case 's':
 			p.backing_src = parse_backing_src_type(optarg);
 			break;
diff --git a/tools/testing/selftests/kvm/include/perf_test_util.h b/tools/testing/selftests/kvm/include/perf_test_util.h
index d822cb670f1c..f18530984b42 100644
--- a/tools/testing/selftests/kvm/include/perf_test_util.h
+++ b/tools/testing/selftests/kvm/include/perf_test_util.h
@@ -34,6 +34,7 @@ struct perf_test_args {
 	uint64_t gpa;
 	uint64_t size;
 	uint64_t guest_page_size;
+	uint32_t random_seed;
 	int wr_fract;
 
 	/* Run vCPUs in L2 instead of L1, if the architecture supports it. */
@@ -51,6 +52,7 @@ struct kvm_vm *perf_test_create_vm(enum vm_guest_mode mode, int vcpus,
 void perf_test_destroy_vm(struct kvm_vm *vm);
 
 void perf_test_set_wr_fract(struct kvm_vm *vm, int wr_fract);
+void perf_test_set_random_seed(struct kvm_vm *vm, uint32_t random_seed);
 
 void perf_test_start_vcpu_threads(int vcpus, void (*vcpu_fn)(struct perf_test_vcpu_args *));
 void perf_test_join_vcpu_threads(int vcpus);
diff --git a/tools/testing/selftests/kvm/include/test_util.h b/tools/testing/selftests/kvm/include/test_util.h
index 99e0dcdc923f..2dd286bcf46f 100644
--- a/tools/testing/selftests/kvm/include/test_util.h
+++ b/tools/testing/selftests/kvm/include/test_util.h
@@ -143,4 +143,6 @@ static inline void *align_ptr_up(void *x, size_t size)
 	return (void *)align_up((unsigned long)x, size);
 }
 
+void guest_random(uint32_t *seed);
+
 #endif /* SELFTEST_KVM_TEST_UTIL_H */
diff --git a/tools/testing/selftests/kvm/lib/perf_test_util.c b/tools/testing/selftests/kvm/lib/perf_test_util.c
index f989ff91f022..b1e731de0966 100644
--- a/tools/testing/selftests/kvm/lib/perf_test_util.c
+++ b/tools/testing/selftests/kvm/lib/perf_test_util.c
@@ -47,6 +47,7 @@ void perf_test_guest_code(uint32_t vcpu_id)
 	uint64_t gva;
 	uint64_t pages;
 	int i;
+	uint32_t rand = pta->random_seed + vcpu_id;
 
 	/* Make sure vCPU args data structure is not corrupt. */
 	GUEST_ASSERT(vcpu_args->vcpu_id == vcpu_id);
@@ -57,6 +58,7 @@ void perf_test_guest_code(uint32_t vcpu_id)
 	while (true) {
 		for (i = 0; i < pages; i++) {
 			uint64_t addr = gva + (i * pta->guest_page_size);
+			guest_random(&rand);
 
 			if (i % pta->wr_fract == 0)
 				*(uint64_t *)addr = 0x0123456789ABCDEF;
@@ -224,6 +226,12 @@ void perf_test_set_wr_fract(struct kvm_vm *vm, int wr_fract)
 	sync_global_to_guest(vm, perf_test_args);
 }
 
+void perf_test_set_random_seed(struct kvm_vm *vm, uint32_t random_seed)
+{
+	perf_test_args.random_seed = random_seed;
+	sync_global_to_guest(vm, perf_test_args.random_seed);
+}
+
 uint64_t __weak perf_test_nested_pages(int nr_vcpus)
 {
 	return 0;
diff --git a/tools/testing/selftests/kvm/lib/test_util.c b/tools/testing/selftests/kvm/lib/test_util.c
index 6d23878bbfe1..28c895743abe 100644
--- a/tools/testing/selftests/kvm/lib/test_util.c
+++ b/tools/testing/selftests/kvm/lib/test_util.c
@@ -17,6 +17,15 @@
 
 #include "test_util.h"
 
+/*
+ * Random number generator that is usable from guest code. This is the
+ * Park-Miller LCG using standard constants.
+ */
+void guest_random(uint32_t *seed)
+{
+	*seed = (uint64_t)*seed * 48271 % ((uint32_t)(1 << 31) - 1);
+}
+
 /*
  * Parses "[0-9]+[kmgt]?".
  */
-- 
2.37.2.789.g6183377224-goog

[PATCH v6 2/3] KVM: selftests: randomize which pages are written vs read

[Colton Lewis]

Randomize which pages are written vs read using the random number
generator.

Change the variable wr_fract and associated function calls to
write_percent that now operates as a percentage from 0 to 100 where X
means each page has an X% chance of being written. Change the -f
argument to -w to reflect the new variable semantics. Keep the same
default of 100% writes.

Population always uses 100% writes to ensure all memory is actually
populated and not just mapped to the zero page. The prevents expensive
copy-on-write faults from occurring during the dirty memory iterations
below, which would pollute the performance results.

Signed-off-by: Colton Lewis <coltonlewis@google.com>
Reviewed-by: Ricardo Koller <ricarkol@google.com>
Reviewed-by: David Matlack <dmatlack@google.com>
---
 .../selftests/kvm/access_tracking_perf_test.c |  2 +-
 .../selftests/kvm/dirty_log_perf_test.c       | 37 ++++++++++++-------
 .../selftests/kvm/include/perf_test_util.h    |  4 +-
 .../selftests/kvm/lib/perf_test_util.c        | 10 ++---
 4 files changed, 32 insertions(+), 21 deletions(-)

diff --git a/tools/testing/selftests/kvm/access_tracking_perf_test.c b/tools/testing/selftests/kvm/access_tracking_perf_test.c
index d8909032317a..d86046ef3a0b 100644
--- a/tools/testing/selftests/kvm/access_tracking_perf_test.c
+++ b/tools/testing/selftests/kvm/access_tracking_perf_test.c
@@ -274,7 +274,7 @@ static void run_iteration(struct kvm_vm *vm, int vcpus, const char *description)
 static void access_memory(struct kvm_vm *vm, int vcpus, enum access_type access,
 			  const char *description)
 {
-	perf_test_set_wr_fract(vm, (access == ACCESS_READ) ? INT_MAX : 1);
+	perf_test_set_write_percent(vm, (access == ACCESS_READ) ? 0 : 100);
 	iteration_work = ITERATION_ACCESS_MEMORY;
 	run_iteration(vm, vcpus, description);
 }
diff --git a/tools/testing/selftests/kvm/dirty_log_perf_test.c b/tools/testing/selftests/kvm/dirty_log_perf_test.c
index a89a620f50d4..dfa5957332b1 100644
--- a/tools/testing/selftests/kvm/dirty_log_perf_test.c
+++ b/tools/testing/selftests/kvm/dirty_log_perf_test.c
@@ -122,10 +122,10 @@ static void vcpu_worker(struct perf_test_vcpu_args *vcpu_args)
 struct test_params {
 	unsigned long iterations;
 	uint64_t phys_offset;
-	int wr_fract;
 	bool partition_vcpu_memory_access;
 	enum vm_mem_backing_src_type backing_src;
 	int slots;
+	uint32_t write_percent;
 	uint32_t random_seed;
 };
 
@@ -224,7 +224,6 @@ static void run_test(enum vm_guest_mode mode, void *arg)
 	/* If no argument provided, random seed will be 0. */
 	pr_info("Random seed: %u\n", p->random_seed);
 	perf_test_set_random_seed(vm, p->random_seed);
-	perf_test_set_wr_fract(vm, p->wr_fract);
 
 	guest_num_pages = (nr_vcpus * guest_percpu_mem_size) >> vm_get_page_shift(vm);
 	guest_num_pages = vm_adjust_num_guest_pages(mode, guest_num_pages);
@@ -249,6 +248,14 @@ static void run_test(enum vm_guest_mode mode, void *arg)
 	for (vcpu_id = 0; vcpu_id < nr_vcpus; vcpu_id++)
 		vcpu_last_completed_iteration[vcpu_id] = -1;
 
+	/*
+	 * Use 100% writes during the population phase to ensure all
+	 * memory is actually populated and not just mapped to the zero
+	 * page. The prevents expensive copy-on-write faults from
+	 * occurring during the dirty memory iterations below, which
+	 * would pollute the performance results.
+	 */
+	perf_test_set_write_percent(vm, 100);
 	perf_test_start_vcpu_threads(nr_vcpus, vcpu_worker);
 
 	/* Allow the vCPUs to populate memory */
@@ -270,6 +277,8 @@ static void run_test(enum vm_guest_mode mode, void *arg)
 	pr_info("Enabling dirty logging time: %ld.%.9lds\n\n",
 		ts_diff.tv_sec, ts_diff.tv_nsec);
 
+	perf_test_set_write_percent(vm, p->write_percent);
+
 	while (iteration < p->iterations) {
 		/*
 		 * Incrementing the iteration number will start the vCPUs
@@ -342,7 +351,7 @@ static void help(char *name)
 	puts("");
 	printf("usage: %s [-h] [-i iterations] [-p offset] [-g] "
 	       "[-m mode] [-n] [-b vcpu bytes] [-v vcpus] [-o] [-r random seed ] [-s mem type]"
-	       "[-x memslots]\n", name);
+	       "[-x memslots] [-w percentage]\n", name);
 	puts("");
 	printf(" -i: specify iteration counts (default: %"PRIu64")\n",
 	       TEST_HOST_LOOP_N);
@@ -359,10 +368,6 @@ static void help(char *name)
 	printf(" -b: specify the size of the memory region which should be\n"
 	       "     dirtied by each vCPU. e.g. 10M or 3G.\n"
 	       "     (default: 1G)\n");
-	printf(" -f: specify the fraction of pages which should be written to\n"
-	       "     as opposed to simply read, in the form\n"
-	       "     1/<fraction of pages to write>.\n"
-	       "     (default: 1 i.e. all pages are written to.)\n");
 	printf(" -v: specify the number of vCPUs to run.\n");
 	printf(" -o: Overlap guest memory accesses instead of partitioning\n"
 	       "     them into a separate region of memory for each vCPU.\n");
@@ -370,6 +375,11 @@ static void help(char *name)
 	backing_src_help("-s");
 	printf(" -x: Split the memory region into this number of memslots.\n"
 	       "     (default: 1)\n");
+	printf(" -w: specify the percentage of pages which should be written to\n"
+	       "     as an integer from 0-100 inclusive. This is probabalistic,\n"
+	       "     so -w X means each page has an X%% chance of writing\n"
+	       "     and a (100-X)%% chance of reading.\n"
+	       "     (default: 100 i.e. all pages are written to.)\n");
 	puts("");
 	exit(0);
 }
@@ -379,10 +389,10 @@ int main(int argc, char *argv[])
 	int max_vcpus = kvm_check_cap(KVM_CAP_MAX_VCPUS);
 	struct test_params p = {
 		.iterations = TEST_HOST_LOOP_N,
-		.wr_fract = 1,
 		.partition_vcpu_memory_access = true,
 		.backing_src = DEFAULT_VM_MEM_SRC,
 		.slots = 1,
+		.write_percent = 100,
 	};
 	int opt;
 
@@ -393,7 +403,7 @@ int main(int argc, char *argv[])
 
 	guest_modes_append_default();
 
-	while ((opt = getopt(argc, argv, "ghi:p:m:nb:f:v:or:s:x:")) != -1) {
+	while ((opt = getopt(argc, argv, "ghi:p:m:nb:v:or:s:x:w:")) != -1) {
 		switch (opt) {
 		case 'g':
 			dirty_log_manual_caps = 0;
@@ -413,10 +423,11 @@ int main(int argc, char *argv[])
 		case 'b':
 			guest_percpu_mem_size = parse_size(optarg);
 			break;
-		case 'f':
-			p.wr_fract = atoi(optarg);
-			TEST_ASSERT(p.wr_fract >= 1,
-				    "Write fraction cannot be less than one");
+		case 'w':
+			p.write_percent = atoi(optarg);
+			TEST_ASSERT(p.write_percent >= 0
+				    && p.write_percent <= 100,
+				    "Write percentage must be between 0 and 100");
 			break;
 		case 'v':
 			nr_vcpus = atoi(optarg);
diff --git a/tools/testing/selftests/kvm/include/perf_test_util.h b/tools/testing/selftests/kvm/include/perf_test_util.h
index f18530984b42..f93f2ea7c6a3 100644
--- a/tools/testing/selftests/kvm/include/perf_test_util.h
+++ b/tools/testing/selftests/kvm/include/perf_test_util.h
@@ -35,7 +35,7 @@ struct perf_test_args {
 	uint64_t size;
 	uint64_t guest_page_size;
 	uint32_t random_seed;
-	int wr_fract;
+	uint32_t write_percent;
 
 	/* Run vCPUs in L2 instead of L1, if the architecture supports it. */
 	bool nested;
@@ -51,7 +51,7 @@ struct kvm_vm *perf_test_create_vm(enum vm_guest_mode mode, int vcpus,
 				   bool partition_vcpu_memory_access);
 void perf_test_destroy_vm(struct kvm_vm *vm);
 
-void perf_test_set_wr_fract(struct kvm_vm *vm, int wr_fract);
+void perf_test_set_write_percent(struct kvm_vm *vm, uint32_t write_percent);
 void perf_test_set_random_seed(struct kvm_vm *vm, uint32_t random_seed);
 
 void perf_test_start_vcpu_threads(int vcpus, void (*vcpu_fn)(struct perf_test_vcpu_args *));
diff --git a/tools/testing/selftests/kvm/lib/perf_test_util.c b/tools/testing/selftests/kvm/lib/perf_test_util.c
index b1e731de0966..9effd229b75d 100644
--- a/tools/testing/selftests/kvm/lib/perf_test_util.c
+++ b/tools/testing/selftests/kvm/lib/perf_test_util.c
@@ -60,7 +60,7 @@ void perf_test_guest_code(uint32_t vcpu_id)
 			uint64_t addr = gva + (i * pta->guest_page_size);
 			guest_random(&rand);
 
-			if (i % pta->wr_fract == 0)
+			if (rand % 100 < pta->write_percent)
 				*(uint64_t *)addr = 0x0123456789ABCDEF;
 			else
 				READ_ONCE(*(uint64_t *)addr);
@@ -118,7 +118,7 @@ struct kvm_vm *perf_test_create_vm(enum vm_guest_mode mode, int vcpus,
 	pr_info("Testing guest mode: %s\n", vm_guest_mode_string(mode));
 
 	/* By default vCPUs will write to memory. */
-	pta->wr_fract = 1;
+	pta->write_percent = 100;
 
 	/*
 	 * Snapshot the non-huge page size.  This is used by the guest code to
@@ -220,10 +220,10 @@ void perf_test_destroy_vm(struct kvm_vm *vm)
 	kvm_vm_free(vm);
 }
 
-void perf_test_set_wr_fract(struct kvm_vm *vm, int wr_fract)
+void perf_test_set_write_percent(struct kvm_vm *vm, uint32_t write_percent)
 {
-	perf_test_args.wr_fract = wr_fract;
-	sync_global_to_guest(vm, perf_test_args);
+	perf_test_args.write_percent = write_percent;
+	sync_global_to_guest(vm, perf_test_args.write_percent);
 }
 
 void perf_test_set_random_seed(struct kvm_vm *vm, uint32_t random_seed)
-- 
2.37.2.789.g6183377224-goog

[PATCH v6 3/3] KVM: selftests: randomize page access order

[Colton Lewis]

Create the ability to randomize page access order with the -a
argument. This includes the possibility that the same pages may be hit
multiple times during an iteration or not at all.

Population has random access as false to ensure all pages will be
touched by population and avoid page faults in late dirty memory that
would pollute the test results.

Signed-off-by: Colton Lewis <coltonlewis@google.com>
Reviewed-by: Ricardo Koller <ricarkol@google.com>
---
 .../selftests/kvm/dirty_log_perf_test.c       | 11 +++++++++--
 .../selftests/kvm/include/perf_test_util.h    |  2 ++
 .../selftests/kvm/lib/perf_test_util.c        | 19 ++++++++++++++++++-
 3 files changed, 29 insertions(+), 3 deletions(-)

diff --git a/tools/testing/selftests/kvm/dirty_log_perf_test.c b/tools/testing/selftests/kvm/dirty_log_perf_test.c
index dfa5957332b1..ccc1f571645a 100644
--- a/tools/testing/selftests/kvm/dirty_log_perf_test.c
+++ b/tools/testing/selftests/kvm/dirty_log_perf_test.c
@@ -127,6 +127,7 @@ struct test_params {
 	int slots;
 	uint32_t write_percent;
 	uint32_t random_seed;
+	bool random_access;
 };
 
 static void toggle_dirty_logging(struct kvm_vm *vm, int slots, bool enable)
@@ -256,6 +257,7 @@ static void run_test(enum vm_guest_mode mode, void *arg)
 	 * would pollute the performance results.
 	 */
 	perf_test_set_write_percent(vm, 100);
+	perf_test_set_random_access(vm, false);
 	perf_test_start_vcpu_threads(nr_vcpus, vcpu_worker);
 
 	/* Allow the vCPUs to populate memory */
@@ -278,6 +280,7 @@ static void run_test(enum vm_guest_mode mode, void *arg)
 		ts_diff.tv_sec, ts_diff.tv_nsec);
 
 	perf_test_set_write_percent(vm, p->write_percent);
+	perf_test_set_random_access(vm, p->random_access);
 
 	while (iteration < p->iterations) {
 		/*
@@ -349,10 +352,11 @@ static void run_test(enum vm_guest_mode mode, void *arg)
 static void help(char *name)
 {
 	puts("");
-	printf("usage: %s [-h] [-i iterations] [-p offset] [-g] "
+	printf("usage: %s [-h] [-a] [-i iterations] [-p offset] [-g] "
 	       "[-m mode] [-n] [-b vcpu bytes] [-v vcpus] [-o] [-r random seed ] [-s mem type]"
 	       "[-x memslots] [-w percentage]\n", name);
 	puts("");
+	printf(" -a: access memory randomly rather than in order.\n");
 	printf(" -i: specify iteration counts (default: %"PRIu64")\n",
 	       TEST_HOST_LOOP_N);
 	printf(" -g: Do not enable KVM_CAP_MANUAL_DIRTY_LOG_PROTECT2. This\n"
@@ -403,8 +407,11 @@ int main(int argc, char *argv[])
 
 	guest_modes_append_default();
 
-	while ((opt = getopt(argc, argv, "ghi:p:m:nb:v:or:s:x:w:")) != -1) {
+	while ((opt = getopt(argc, argv, "aghi:p:m:nb:v:or:s:x:w:")) != -1) {
 		switch (opt) {
+		case 'a':
+			p.random_access = true;
+			break;
 		case 'g':
 			dirty_log_manual_caps = 0;
 			break;
diff --git a/tools/testing/selftests/kvm/include/perf_test_util.h b/tools/testing/selftests/kvm/include/perf_test_util.h
index f93f2ea7c6a3..d9664a31e01c 100644
--- a/tools/testing/selftests/kvm/include/perf_test_util.h
+++ b/tools/testing/selftests/kvm/include/perf_test_util.h
@@ -39,6 +39,7 @@ struct perf_test_args {
 
 	/* Run vCPUs in L2 instead of L1, if the architecture supports it. */
 	bool nested;
+	bool random_access;
 
 	struct perf_test_vcpu_args vcpu_args[KVM_MAX_VCPUS];
 };
@@ -53,6 +54,7 @@ void perf_test_destroy_vm(struct kvm_vm *vm);
 
 void perf_test_set_write_percent(struct kvm_vm *vm, uint32_t write_percent);
 void perf_test_set_random_seed(struct kvm_vm *vm, uint32_t random_seed);
+void perf_test_set_random_access(struct kvm_vm *vm, bool random_access);
 
 void perf_test_start_vcpu_threads(int vcpus, void (*vcpu_fn)(struct perf_test_vcpu_args *));
 void perf_test_join_vcpu_threads(int vcpus);
diff --git a/tools/testing/selftests/kvm/lib/perf_test_util.c b/tools/testing/selftests/kvm/lib/perf_test_util.c
index 9effd229b75d..6b196d003491 100644
--- a/tools/testing/selftests/kvm/lib/perf_test_util.c
+++ b/tools/testing/selftests/kvm/lib/perf_test_util.c
@@ -46,6 +46,7 @@ void perf_test_guest_code(uint32_t vcpu_id)
 	struct perf_test_vcpu_args *vcpu_args = &pta->vcpu_args[vcpu_id];
 	uint64_t gva;
 	uint64_t pages;
+	uint64_t addr;
 	int i;
 	uint32_t rand = pta->random_seed + vcpu_id;
 
@@ -57,7 +58,17 @@ void perf_test_guest_code(uint32_t vcpu_id)
 
 	while (true) {
 		for (i = 0; i < pages; i++) {
-			uint64_t addr = gva + (i * pta->guest_page_size);
+			guest_random(&rand);
+
+			if (pta->random_access)
+				addr = gva + ((rand % pages) * pta->guest_page_size);
+			else
+				addr = gva + (i * pta->guest_page_size);
+
+			/*
+			 * Use a new random number here so read/write
+			 * is not tied to the address used.
+			 */
 			guest_random(&rand);
 
 			if (rand % 100 < pta->write_percent)
@@ -232,6 +243,12 @@ void perf_test_set_random_seed(struct kvm_vm *vm, uint32_t random_seed)
 	sync_global_to_guest(vm, perf_test_args.random_seed);
 }
 
+void perf_test_set_random_access(struct kvm_vm *vm, bool random_access)
+{
+	perf_test_args.random_access = random_access;
+	sync_global_to_guest(vm, perf_test_args.random_access);
+}
+
 uint64_t __weak perf_test_nested_pages(int nr_vcpus)
 {
 	return 0;
-- 
2.37.2.789.g6183377224-goog

Re: [PATCH v6 0/3] KVM: selftests: randomize memory access of dirty_log_perf_test

[David Matlack]

On Mon, Sep 12, 2022 at 07:58:46PM +0000, Colton Lewis wrote:
> Add the ability to randomize parts of dirty_log_perf_test,
> specifically the order pages are accessed and whether pages are read
> or written.
> 
> v6:
> 
> Change default random seed to the constant 0.
> 
> Explain why 100% writes in populate phase, why no random access in
> populate phase, and why use two random numbers in the guest code.
> 
> Colton Lewis (3):
>   KVM: selftests: implement random number generation for guest code
>   KVM: selftests: randomize which pages are written vs read
>   KVM: selftests: randomize page access order

For the whole series:

Reviewed-by: David Matlack <dmatlack@google.com>

> 
>  .../selftests/kvm/access_tracking_perf_test.c |  2 +-
>  .../selftests/kvm/dirty_log_perf_test.c       | 55 ++++++++++++++-----
>  .../selftests/kvm/include/perf_test_util.h    |  8 ++-
>  .../testing/selftests/kvm/include/test_util.h |  2 +
>  .../selftests/kvm/lib/perf_test_util.c        | 39 ++++++++++---
>  tools/testing/selftests/kvm/lib/test_util.c   |  9 +++
>  6 files changed, 90 insertions(+), 25 deletions(-)
> 
> --
> 2.37.2.789.g6183377224-goog

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Sean Christopherson]

On Mon, Sep 12, 2022, Colton Lewis wrote:
> diff --git a/tools/testing/selftests/kvm/include/test_util.h b/tools/testing/selftests/kvm/include/test_util.h
> index 99e0dcdc923f..2dd286bcf46f 100644
> --- a/tools/testing/selftests/kvm/include/test_util.h
> +++ b/tools/testing/selftests/kvm/include/test_util.h
> @@ -143,4 +143,6 @@ static inline void *align_ptr_up(void *x, size_t size)
>  	return (void *)align_up((unsigned long)x, size);
>  }
>  
> +void guest_random(uint32_t *seed);

This is a weird and unintuitive API.  The in/out param exposes the gory details
of the pseudo-RNG to the caller, and makes it cumbersome to use, e.g. to create
a 64-bit number or to consume the result in a conditional.

It's also not inherently guest-specific, or even KVM specific.  We should consider
landing this in common selftests code so that others can use it and even expand on
it.  E.g. in a previous life, I worked with a tool that implemented all sorts of
random number magic that provided APIs to get random bools with 1->99 probabilty,
random numbers along Guassian curves, bounded numbers, etc.

We definitely don't need that level of fanciness right way, but it doesn't require
much effort to define the initial APIs such that they won't require modification
if/when fancier usage comes along.

E.g. to start:

---
.c:

/*
 * Random number generator that is usable in any context.  Not thread-safe.
 * This is the Park-Miller LCG using standard constants.
 */
struct ksft_pseudo_rng {
	uint32_t state;
}

void ksft_pseudo_rng_init(struct ksft_pseudo_rng *rng, uint64_t seed)
{
	rng->state = seed;	
}

static uint32_t ksft_pseudo_rng_random(struct ksft_pseudo_rng *rng)
{

	*rng->state = (uint64_t)*rng->state * 48271 % ((1u << 31) - 1);
	return *rng->state;
}

uint32_t random_u32(struct ksft_pseudo_rng *rng)
{
	return ksft_pseudo_rng_random(rng);
}

uint64_t random_u64(struct ksft_pseudo_rng *rng)
{
	return (uint64_t)random_u32(rng) << 32 | random_u32(rng);
}

.h

struct ksft_pseudo_rng;

void ksft_pseudo_rng_init(struct ksft_pseudo_rng *rng, uint64_t seed);
uint32_t random_u32(struct ksft_pseudo_rng *rng);
uint64_t random_u64(struct ksft_pseudo_rng *rng);
---

And then if/when want to add fancier stuff, say bounded 32-bit values, we can do
so without having to update existing users.

Re: [PATCH v6 2/3] KVM: selftests: randomize which pages are written vs read

[Sean Christopherson]

On Mon, Sep 12, 2022, Colton Lewis wrote:
> @@ -393,7 +403,7 @@ int main(int argc, char *argv[])
>  
>  	guest_modes_append_default();
>  
> -	while ((opt = getopt(argc, argv, "ghi:p:m:nb:f:v:or:s:x:")) != -1) {
> +	while ((opt = getopt(argc, argv, "ghi:p:m:nb:v:or:s:x:w:")) != -1) {

This string is getting quite annoying to maintain, e.g. all of these patches
conflict with recent upstream changes, and IIRC will conflict again with Vipin's
changes.  AFAICT, the string passed to getopt() doesn't need to be constant, i.e.
can be built programmatically.  Not in this series, but as future cleanup we should
at least consider a way to make this slightly less painful to maintain.

>  		switch (opt) {
>  		case 'g':
>  			dirty_log_manual_caps = 0;
> @@ -413,10 +423,11 @@ int main(int argc, char *argv[])
>  		case 'b':
>  			guest_percpu_mem_size = parse_size(optarg);
>  			break;
> -		case 'f':
> -			p.wr_fract = atoi(optarg);
> -			TEST_ASSERT(p.wr_fract >= 1,
> -				    "Write fraction cannot be less than one");
> +		case 'w':
> +			p.write_percent = atoi(optarg);
> +			TEST_ASSERT(p.write_percent >= 0
> +				    && p.write_percent <= 100,

&&, ||, etc... go on the previous line.  But in this case, I'd say don't wrap at all,
it's only a few chars over the soft limit.

			TEST_ASSERT(p.write_percent >= 0 && p.write_percent <= 100,

or

			TEST_ASSERT(p.write_percent >= 0 &&
				    p.write_percent <= 100,

And after Vipin's cleanup lands[*], this can be:

			p.write_percent = atoi_positive(optarg);

			TEST_ASSERT(p.write_percent <= 100,

[*] https://lore.kernel.org/all/CAHVum0cD5R9ej09VNvkkqcQsz7PGrxnMqi1E4kqLv+1d63Rg6A@mail.gmail.com

> +				    "Write percentage must be between 0 and 100");
>  			break;
>  		case 'v':
>  			nr_vcpus = atoi(optarg);
> diff --git a/tools/testing/selftests/kvm/include/perf_test_util.h b/tools/testing/selftests/kvm/include/perf_test_util.h
> index f18530984b42..f93f2ea7c6a3 100644
> --- a/tools/testing/selftests/kvm/include/perf_test_util.h
> +++ b/tools/testing/selftests/kvm/include/perf_test_util.h
> @@ -35,7 +35,7 @@ struct perf_test_args {
>  	uint64_t size;
>  	uint64_t guest_page_size;
>  	uint32_t random_seed;
> -	int wr_fract;
> +	uint32_t write_percent;
>  
>  	/* Run vCPUs in L2 instead of L1, if the architecture supports it. */
>  	bool nested;
> @@ -51,7 +51,7 @@ struct kvm_vm *perf_test_create_vm(enum vm_guest_mode mode, int vcpus,
>  				   bool partition_vcpu_memory_access);
>  void perf_test_destroy_vm(struct kvm_vm *vm);
>  
> -void perf_test_set_wr_fract(struct kvm_vm *vm, int wr_fract);
> +void perf_test_set_write_percent(struct kvm_vm *vm, uint32_t write_percent);
>  void perf_test_set_random_seed(struct kvm_vm *vm, uint32_t random_seed);
>  
>  void perf_test_start_vcpu_threads(int vcpus, void (*vcpu_fn)(struct perf_test_vcpu_args *));
> diff --git a/tools/testing/selftests/kvm/lib/perf_test_util.c b/tools/testing/selftests/kvm/lib/perf_test_util.c
> index b1e731de0966..9effd229b75d 100644
> --- a/tools/testing/selftests/kvm/lib/perf_test_util.c
> +++ b/tools/testing/selftests/kvm/lib/perf_test_util.c
> @@ -60,7 +60,7 @@ void perf_test_guest_code(uint32_t vcpu_id)
>  			uint64_t addr = gva + (i * pta->guest_page_size);
>  			guest_random(&rand);
>  
> -			if (i % pta->wr_fract == 0)
> +			if (rand % 100 < pta->write_percent)

Aha!  Random bools with a percentage is exactly the type of thing the common RNG
helpers can and should provide.  E.g. this should look something like:

			if (random_bool(rng, pta->write_percent))

As a bonus, if someone wants to implement a more sophisticated percentage system,
then all users of random_bool() will benefit, again without needing to update
users.

Re: [PATCH v6 2/3] KVM: selftests: randomize which pages are written vs read

[David Matlack]

On Fri, Oct 7, 2022 at 1:55 PM Sean Christopherson <seanjc@google.com> wrote:
>
> On Mon, Sep 12, 2022, Colton Lewis wrote:
> > @@ -393,7 +403,7 @@ int main(int argc, char *argv[])
> >
> >       guest_modes_append_default();
> >
> > -     while ((opt = getopt(argc, argv, "ghi:p:m:nb:f:v:or:s:x:")) != -1) {
> > +     while ((opt = getopt(argc, argv, "ghi:p:m:nb:v:or:s:x:w:")) != -1) {
>
> This string is getting quite annoying to maintain, e.g. all of these patches
> conflict with recent upstream changes, and IIRC will conflict again with Vipin's
> changes.  AFAICT, the string passed to getopt() doesn't need to be constant, i.e.
> can be built programmatically.  Not in this series, but as future cleanup we should
> at least consider a way to make this slightly less painful to maintain.

I have aspirations to consolidate all the memstress (perf_test_util)
option handling within memstress.c, rather than duplicating it across
all tests. That will help cut down the length of the test-specific
option string (although I haven't found a super clean way to do it
yet).

Re: [PATCH v6 3/3] KVM: selftests: randomize page access order

[Sean Christopherson]

On Mon, Sep 12, 2022, Colton Lewis wrote:
> @@ -57,7 +58,17 @@ void perf_test_guest_code(uint32_t vcpu_id)
>  
>  	while (true) {
>  		for (i = 0; i < pages; i++) {
> -			uint64_t addr = gva + (i * pta->guest_page_size);
> +			guest_random(&rand);
> +
> +			if (pta->random_access)
> +				addr = gva + ((rand % pages) * pta->guest_page_size);

Shouldn't this use a 64-bit random number since "pages" is a 64-bit value?  Ha!
And another case where the RNG APIs can help, e.g.

  uint64_t __random_u64(struct ksft_pseudo_rng *rng, uint64_t max);

or maybe avoid naming pain and go straight to:


  uint64_t __random_u64(struct ksft_pseudo_rng *rng, uint64_t min, uint64_t max);

> +			else
> +				addr = gva + (i * pta->guest_page_size);

Since the calculation is the same, only the page index changes, I think it makes
sense to write this as:

			uint64_t idx = i;

			if (pta->random_access)
				idx = __random_u64(rng, 0, pages);

			addr = gva + (idx * pta->guest_page_size);

That way it's easy to introduce other access patterns.

> +
> +			/*
> +			 * Use a new random number here so read/write
> +			 * is not tied to the address used.
> +			 */
>  			guest_random(&rand);

Ya, I'm trippling (quadrupling?) down on my suggestion to improve the APIs.  Users
should not be able to screw up like this, i.e. shouldn't need comments to warn
readers, and adding another call to get a random number shouldn't affect unrelated
code.

Re: [PATCH v6 2/3] KVM: selftests: randomize which pages are written vs read

[Andrew Jones]

On Fri, Oct 07, 2022 at 08:55:20PM +0000, Sean Christopherson wrote:
> On Mon, Sep 12, 2022, Colton Lewis wrote:
> > @@ -393,7 +403,7 @@ int main(int argc, char *argv[])
> >  
> >  	guest_modes_append_default();
> >  
> > -	while ((opt = getopt(argc, argv, "ghi:p:m:nb:f:v:or:s:x:")) != -1) {
> > +	while ((opt = getopt(argc, argv, "ghi:p:m:nb:v:or:s:x:w:")) != -1) {
> 
> This string is getting quite annoying to maintain, e.g. all of these patches
> conflict with recent upstream changes, and IIRC will conflict again with Vipin's
> changes.  AFAICT, the string passed to getopt() doesn't need to be constant, i.e.
> can be built programmatically.  Not in this series, but as future cleanup we should
> at least consider a way to make this slightly less painful to maintain.
>

I wonder if a getopt string like above is really saying "we're doing too
much in a single test binary". Are all these switches just for one-off
experiments which developers need? Or, are testers expected to run this
binary multiple times with different combinations of switches? If it's
the latter, then I think we need a test runner script and config file to
capture those separate invocations (similar to kvm-unit-tests). Or, change
from a collection of command line switches to building the file multiple
times with different compile time switches and output filenames. Then,
testers are just expected to run all binaries (which is what I think most
believe / do today).

Thanks,
drew

Re: [PATCH v6 2/3] KVM: selftests: randomize which pages are written vs read

[Sean Christopherson]

On Sat, Oct 08, 2022, Andrew Jones wrote:
> On Fri, Oct 07, 2022 at 08:55:20PM +0000, Sean Christopherson wrote:
> > On Mon, Sep 12, 2022, Colton Lewis wrote:
> > > @@ -393,7 +403,7 @@ int main(int argc, char *argv[])
> > >  
> > >  	guest_modes_append_default();
> > >  
> > > -	while ((opt = getopt(argc, argv, "ghi:p:m:nb:f:v:or:s:x:")) != -1) {
> > > +	while ((opt = getopt(argc, argv, "ghi:p:m:nb:v:or:s:x:w:")) != -1) {
> > 
> > This string is getting quite annoying to maintain, e.g. all of these patches
> > conflict with recent upstream changes, and IIRC will conflict again with Vipin's
> > changes.  AFAICT, the string passed to getopt() doesn't need to be constant, i.e.
> > can be built programmatically.  Not in this series, but as future cleanup we should
> > at least consider a way to make this slightly less painful to maintain.
> >
> 
> I wonder if a getopt string like above is really saying "we're doing too
> much in a single test binary". Are all these switches just for one-off
> experiments which developers need? Or, are testers expected to run this
> binary multiple times with different combinations of switches?

Even if it's just 2 or 3 switches, I agree we need a way to run those configs by
default.

> If it's the latter, then I think we need a test runner script and config file
> to capture those separate invocations (similar to kvm-unit-tests). Or, change
> from a collection of command line switches to building the file multiple
> times with different compile time switches and output filenames.

What about a mix of those two approaches and having individual scripts for each
config?  I like the idea of one executable per config, but we shouldn't need to
compile multiple times.  And that would still allow developers to easily run
non-standard configs.

I'd prefer to avoid adding a test runner, partly because I can never remember the
invocation strings, partly becuase I don't want to encourage mega tests like the
VMX and SVM KVM-unit-tests.

Re: [PATCH v6 2/3] KVM: selftests: randomize which pages are written vs read

[Andrew Jones]

On Mon, Oct 10, 2022 at 02:46:24PM +0000, Sean Christopherson wrote:
> On Sat, Oct 08, 2022, Andrew Jones wrote:
> > On Fri, Oct 07, 2022 at 08:55:20PM +0000, Sean Christopherson wrote:
> > > On Mon, Sep 12, 2022, Colton Lewis wrote:
> > > > @@ -393,7 +403,7 @@ int main(int argc, char *argv[])
> > > >  
> > > >  	guest_modes_append_default();
> > > >  
> > > > -	while ((opt = getopt(argc, argv, "ghi:p:m:nb:f:v:or:s:x:")) != -1) {
> > > > +	while ((opt = getopt(argc, argv, "ghi:p:m:nb:v:or:s:x:w:")) != -1) {
> > > 
> > > This string is getting quite annoying to maintain, e.g. all of these patches
> > > conflict with recent upstream changes, and IIRC will conflict again with Vipin's
> > > changes.  AFAICT, the string passed to getopt() doesn't need to be constant, i.e.
> > > can be built programmatically.  Not in this series, but as future cleanup we should
> > > at least consider a way to make this slightly less painful to maintain.
> > >
> > 
> > I wonder if a getopt string like above is really saying "we're doing too
> > much in a single test binary". Are all these switches just for one-off
> > experiments which developers need? Or, are testers expected to run this
> > binary multiple times with different combinations of switches?
> 
> Even if it's just 2 or 3 switches, I agree we need a way to run those configs by
> default.
> 
> > If it's the latter, then I think we need a test runner script and config file
> > to capture those separate invocations (similar to kvm-unit-tests). Or, change
> > from a collection of command line switches to building the file multiple
> > times with different compile time switches and output filenames.
> 
> What about a mix of those two approaches and having individual scripts for each
> config?  I like the idea of one executable per config, but we shouldn't need to
> compile multiple times.  And that would still allow developers to easily run
> non-standard configs.

Sounds good to me. Come to think of it we have that in kvm-unit-tests too
after running 'make standalone', which generates individual scripts per
configuration. IIRC, people doing testing seemed to prefer running the
standalone versions with their own runners too.

Thanks,
drew

> 
> I'd prefer to avoid adding a test runner, partly because I can never remember the
> invocation strings, partly becuase I don't want to encourage mega tests like the
> VMX and SVM KVM-unit-tests.

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Sean Christopherson]

On Mon, Sep 12, 2022, Colton Lewis wrote:
> Implement random number generation for guest code to randomize parts
> of the test, making it less predictable and a more accurate reflection
> of reality.
> 
> Create a -r argument to specify a random seed. If no argument is
> provided, the seed defaults to 0. The random seed is set with
> perf_test_set_random_seed() and must be set before guest_code runs to
> apply.
> 
> The random number generator chosen is the Park-Miller Linear
> Congruential Generator, a fancy name for a basic and well-understood
> random number generator entirely sufficient for this purpose. Each
> vCPU calculates its own seed by adding its index to the seed provided.

Why not grab the kernel's pseudo-RNG from prandom_seed_state() + prandom_u32_state()?

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Colton Lewis]

Sean Christopherson <seanjc@google.com> writes:

> On Mon, Sep 12, 2022, Colton Lewis wrote:
>> diff --git a/tools/testing/selftests/kvm/include/test_util.h  
>> b/tools/testing/selftests/kvm/include/test_util.h
>> index 99e0dcdc923f..2dd286bcf46f 100644
>> --- a/tools/testing/selftests/kvm/include/test_util.h
>> +++ b/tools/testing/selftests/kvm/include/test_util.h
>> @@ -143,4 +143,6 @@ static inline void *align_ptr_up(void *x, size_t  
>> size)
>>   	return (void *)align_up((unsigned long)x, size);
>>   }

>> +void guest_random(uint32_t *seed);

> This is a weird and unintuitive API.  The in/out param exposes the gory  
> details
> of the pseudo-RNG to the caller, and makes it cumbersome to use, e.g. to  
> create
> a 64-bit number or to consume the result in a conditional.


To explain my reasoning:

It's simple because there is exactly one way to use it and it's short so
anyone can understand how the function works at a glance. It's similar
to the API used by other thread-safe RNGs like rand_r and random_r. They
also use in/out parameters. That's the only way to buy thread
safety. Callers would also have to manage their own state in your
example with an in/out parameter if they want thread safety.

I disagree the details are gory. You put in a number and get a new
number. It's common knowledge PRNGs work this way. I understand you are
thinking about ease of future extensions, but this strikes me as
premature abstraction. Additional APIs can always be added later for the
fancy stuff without modifying the callers that don't need it.

I agree returning the value could make it easier to use as part of
expressions, but is it that important?

> It's also not inherently guest-specific, or even KVM specific.  We should  
> consider
> landing this in common selftests code so that others can use it and even  
> expand on
> it.  E.g. in a previous life, I worked with a tool that implemented all  
> sorts of
> random number magic that provided APIs to get random bools with 1->99  
> probabilty,
> random numbers along Guassian curves, bounded numbers, etc.


People who need random numbers outside the guest should use stdlib.h. No
need to reimplement a full random library. The point of this
implementation was to do the simplest thing that could provide random
numbers to the guest.

Re: [PATCH v6 3/3] KVM: selftests: randomize page access order

[Colton Lewis]

Sean Christopherson <seanjc@google.com> writes:

> On Mon, Sep 12, 2022, Colton Lewis wrote:
>> @@ -57,7 +58,17 @@ void perf_test_guest_code(uint32_t vcpu_id)

>>   	while (true) {
>>   		for (i = 0; i < pages; i++) {
>> -			uint64_t addr = gva + (i * pta->guest_page_size);
>> +			guest_random(&rand);
>> +
>> +			if (pta->random_access)
>> +				addr = gva + ((rand % pages) * pta->guest_page_size);

> Shouldn't this use a 64-bit random number since "pages" is a 64-bit  
> value?  Ha!
> And another case where the RNG APIs can help, e.g.


Do we need to test with memory chunks that have over 2^32 pages to
choose from? That's 16 TiB of memory. Possible a computer might have
that much to dedicate to a VM, but what would be the use of such a test?

>> +
>> +			/*
>> +			 * Use a new random number here so read/write
>> +			 * is not tied to the address used.
>> +			 */
>>   			guest_random(&rand);

> Ya, I'm trippling (quadrupling?) down on my suggestion to improve the  
> APIs.  Users
> should not be able to screw up like this, i.e. shouldn't need comments to  
> warn
> readers, and adding another call to get a random number shouldn't affect  
> unrelated
> code.

Previous calls to PRNGs always affect later calls to PRNGs. That's how
they work. This "screw up" would be equally likely with any API because
the caller always needs to decide if they should reuse the same random
number or need a new one.

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Colton Lewis]

Sean Christopherson <seanjc@google.com> writes:

> On Mon, Sep 12, 2022, Colton Lewis wrote:
>> Implement random number generation for guest code to randomize parts
>> of the test, making it less predictable and a more accurate reflection
>> of reality.

>> Create a -r argument to specify a random seed. If no argument is
>> provided, the seed defaults to 0. The random seed is set with
>> perf_test_set_random_seed() and must be set before guest_code runs to
>> apply.

>> The random number generator chosen is the Park-Miller Linear
>> Congruential Generator, a fancy name for a basic and well-understood
>> random number generator entirely sufficient for this purpose. Each
>> vCPU calculates its own seed by adding its index to the seed provided.

> Why not grab the kernel's pseudo-RNG from prandom_seed_state() +  
> prandom_u32_state()?

The guest is effectively a minimal kernel running in a VM that doesn't
have access to this, correct?

If you meant for the seed default. David Matlack specifically insisted
on using the same default every time. And a selftest is a userspace
program that I don't think has access to this either.

Re: [PATCH v6 3/3] KVM: selftests: randomize page access order

[Sean Christopherson]

On Tue, Oct 11, 2022, Colton Lewis wrote:
> Sean Christopherson <seanjc@google.com> writes:
> > Ya, I'm trippling (quadrupling?) down on my suggestion to improve the
> > APIs.  Users
> > should not be able to screw up like this, i.e. shouldn't need comments
> > to warn
> > readers, and adding another call to get a random number shouldn't affect
> > unrelated
> > code.
> 
> Previous calls to PRNGs always affect later calls to PRNGs. That's how
> they work.

Ya, that's not the type of bugs I'm worried about.

> This "screw up" would be equally likely with any API because the caller
> always needs to decide if they should reuse the same random number or need a
> new one.

I disagree, the in/out parameter _requires_ the calling code to store the random
number in a variable.  Returning the random number allows consuming the number
without needing an intermediate variable, e.g.

	if (random_bool())
		<do stuff>

which makes it easy to avoid an entire class of bugs.

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Sean Christopherson]

On Tue, Oct 11, 2022, Colton Lewis wrote:
> Sean Christopherson <seanjc@google.com> writes:
> 
> > On Mon, Sep 12, 2022, Colton Lewis wrote:
> > > Implement random number generation for guest code to randomize parts
> > > of the test, making it less predictable and a more accurate reflection
> > > of reality.
> 
> > > Create a -r argument to specify a random seed. If no argument is
> > > provided, the seed defaults to 0. The random seed is set with
> > > perf_test_set_random_seed() and must be set before guest_code runs to
> > > apply.
> 
> > > The random number generator chosen is the Park-Miller Linear
> > > Congruential Generator, a fancy name for a basic and well-understood
> > > random number generator entirely sufficient for this purpose. Each
> > > vCPU calculates its own seed by adding its index to the seed provided.
> 
> > Why not grab the kernel's pseudo-RNG from prandom_seed_state() +
> > prandom_u32_state()?
> 
> The guest is effectively a minimal kernel running in a VM that doesn't
> have access to this, correct?

Oh, I didn't mean link to the kernel code, I meant "why not copy+paste the kernel
code?".  In other words, why select a different RNG implementation than what the
kernel uses?  In general, selftests and tools try to follow the kernel code, even
when copy+pasting, as that avoids questions like "why does the kernel do X but
selftests do Y?".  The copy+paste does sometimes lead to maintenance pain, e.g. if
the copied code has a bug that the kernel then fixes, but that seems unlikely to
happen in this case.

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Sean Christopherson]

On Tue, Oct 11, 2022, Colton Lewis wrote:
> Sean Christopherson <seanjc@google.com> writes:
> 
> > On Mon, Sep 12, 2022, Colton Lewis wrote:
> > > diff --git a/tools/testing/selftests/kvm/include/test_util.h
> > > b/tools/testing/selftests/kvm/include/test_util.h
> > > index 99e0dcdc923f..2dd286bcf46f 100644
> > > --- a/tools/testing/selftests/kvm/include/test_util.h
> > > +++ b/tools/testing/selftests/kvm/include/test_util.h
> > > @@ -143,4 +143,6 @@ static inline void *align_ptr_up(void *x, size_t
> > > size)
> > >   	return (void *)align_up((unsigned long)x, size);
> > >   }
> 
> > > +void guest_random(uint32_t *seed);
> 
> > This is a weird and unintuitive API.  The in/out param exposes the gory
> > details of the pseudo-RNG to the caller, and makes it cumbersome to use,
> > e.g. to create a 64-bit number or to consume the result in a conditional.
> 
> To explain my reasoning:
> 
> It's simple because there is exactly one way to use it and it's short so
> anyone can understand how the function works at a glance. It's similar
> to the API used by other thread-safe RNGs like rand_r and random_r. They
> also use in/out parameters. That's the only way to buy thread
> safety. Callers would also have to manage their own state in your
> example with an in/out parameter if they want thread safety.
> 
> I disagree the details are gory. You put in a number and get a new
> number.

Regardless of whether or not the details are gory, having to be aware of those
details unnecessarily impedes understanding the code.  The vast, vast majority of
folks that read this code won't care about how PRNGs work.  Even if the reader is
familiar with PRNGs, those details aren't at all relevant to understanding what
the guest code does.  The reader only needs to know "oh, this is randomizing the
address".  How the randomization works is completely irrelevant for that level of
understanding.

> It's common knowledge PRNGs work this way.

For people that are familiar with PRNGs, yes, but there will undoubtedly be people
that read this code and have practically zero experience with PRNGs.

> I understand you are thinking about ease of future extensions, but this
> strikes me as premature abstraction. Additional APIs can always be added
> later for the fancy stuff without modifying the callers that don't need it.
> 
> I agree returning the value could make it easier to use as part of
> expressions, but is it that important?

Yes, because in pretty much every use case, the random number is going to be
immediately consumed.  Readability and robustness aside, returning the value cuts
the amount of code need to generate and consume a random number in half.

> > It's also not inherently guest-specific, or even KVM specific.  We
> > should consider
> > landing this in common selftests code so that others can use it and even
> > expand on
> > it.  E.g. in a previous life, I worked with a tool that implemented all
> > sorts of
> > random number magic that provided APIs to get random bools with 1->99
> > probabilty,
> > random numbers along Guassian curves, bounded numbers, etc.
> 
> 
> People who need random numbers outside the guest should use stdlib.h. No
> need to reimplement a full random library. The point of this
> implementation was to do the simplest thing that could provide random
> numbers to the guest.

Ah, right.

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Colton Lewis]

Sean Christopherson <seanjc@google.com> writes:

> On Tue, Oct 11, 2022, Colton Lewis wrote:
>> Sean Christopherson <seanjc@google.com> writes:

>> > On Mon, Sep 12, 2022, Colton Lewis wrote:
>> > > diff --git a/tools/testing/selftests/kvm/include/test_util.h
>> > > b/tools/testing/selftests/kvm/include/test_util.h
>> > > index 99e0dcdc923f..2dd286bcf46f 100644
>> > > --- a/tools/testing/selftests/kvm/include/test_util.h
>> > > +++ b/tools/testing/selftests/kvm/include/test_util.h
>> > > @@ -143,4 +143,6 @@ static inline void *align_ptr_up(void *x, size_t
>> > > size)
>> > >   	return (void *)align_up((unsigned long)x, size);
>> > >   }

>> > > +void guest_random(uint32_t *seed);

>> > This is a weird and unintuitive API.  The in/out param exposes the gory
>> > details of the pseudo-RNG to the caller, and makes it cumbersome to  
>> use,
>> > e.g. to create a 64-bit number or to consume the result in a  
>> conditional.

>> To explain my reasoning:

>> It's simple because there is exactly one way to use it and it's short so
>> anyone can understand how the function works at a glance. It's similar
>> to the API used by other thread-safe RNGs like rand_r and random_r. They
>> also use in/out parameters. That's the only way to buy thread
>> safety. Callers would also have to manage their own state in your
>> example with an in/out parameter if they want thread safety.

>> I disagree the details are gory. You put in a number and get a new
>> number.

> Regardless of whether or not the details are gory, having to be aware of  
> those
> details unnecessarily impedes understanding the code.  The vast, vast  
> majority of
> folks that read this code won't care about how PRNGs work.  Even if the  
> reader is
> familiar with PRNGs, those details aren't at all relevant to  
> understanding what
> the guest code does.  The reader only needs to know "oh, this is  
> randomizing the
> address".  How the randomization works is completely irrelevant for that  
> level of
> understanding.


It is relevant if the reader of the guest code cares about reentrancy
and thread-safety (good for such things as reproducing the same stream
of randoms from the same initial conditions), because they will have to
manage some state to make that work. Whether that state is an integer or
an opaque struct requires the same level of knowledge to use the API.

>> It's common knowledge PRNGs work this way.

> For people that are familiar with PRNGs, yes, but there will undoubtedly  
> be people
> that read this code and have practically zero experience with PRNGs.

>> I understand you are thinking about ease of future extensions, but this
>> strikes me as premature abstraction. Additional APIs can always be added
>> later for the fancy stuff without modifying the callers that don't need  
>> it.

>> I agree returning the value could make it easier to use as part of
>> expressions, but is it that important?

> Yes, because in pretty much every use case, the random number is going to  
> be
> immediately consumed.  Readability and robustness aside, returning the  
> value cuts
> the amount of code need to generate and consume a random number in half.


Ok. This is trivial to change (or implement on top of what is
there). Would you be happy with something like the following?

uint32_t guest_random(uint32_t *seed)
{
	*seed = (uint64_t)*seed * 48271 % ((uint32_t)(1 << 31) - 1);
	return *seed;
}

Re: [PATCH v6 3/3] KVM: selftests: randomize page access order

[Colton Lewis]

Sean Christopherson <seanjc@google.com> writes:

> On Tue, Oct 11, 2022, Colton Lewis wrote:
>> Sean Christopherson <seanjc@google.com> writes:
>> > Ya, I'm trippling (quadrupling?) down on my suggestion to improve the
>> > APIs.  Users
>> > should not be able to screw up like this, i.e. shouldn't need comments
>> > to warn
>> > readers, and adding another call to get a random number shouldn't  
>> affect
>> > unrelated
>> > code.

>> Previous calls to PRNGs always affect later calls to PRNGs. That's how
>> they work.

> Ya, that's not the type of bugs I'm worried about.

>> This "screw up" would be equally likely with any API because the caller
>> always needs to decide if they should reuse the same random number or  
>> need a
>> new one.

> I disagree, the in/out parameter _requires_ the calling code to store the  
> random
> number in a variable.  Returning the random number allows consuming the  
> number
> without needing an intermediate variable, e.g.

> 	if (random_bool())
> 		<do stuff>

> which makes it easy to avoid an entire class of bugs.

Yes, but it's impossible to do this without hidden global state at the
implementation level. That sacrifices reentrancy and thread-safety.

Maybe that's an acceptable sacrifice, but I'd prefer an obvious pitfall
over a subtle one.

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Colton Lewis]

Sean Christopherson <seanjc@google.com> writes:

> On Tue, Oct 11, 2022, Colton Lewis wrote:
>> Sean Christopherson <seanjc@google.com> writes:

>> > On Mon, Sep 12, 2022, Colton Lewis wrote:
>> > > Implement random number generation for guest code to randomize parts
>> > > of the test, making it less predictable and a more accurate  
>> reflection
>> > > of reality.

>> > > Create a -r argument to specify a random seed. If no argument is
>> > > provided, the seed defaults to 0. The random seed is set with
>> > > perf_test_set_random_seed() and must be set before guest_code runs to
>> > > apply.

>> > > The random number generator chosen is the Park-Miller Linear
>> > > Congruential Generator, a fancy name for a basic and well-understood
>> > > random number generator entirely sufficient for this purpose. Each
>> > > vCPU calculates its own seed by adding its index to the seed  
>> provided.

>> > Why not grab the kernel's pseudo-RNG from prandom_seed_state() +
>> > prandom_u32_state()?

>> The guest is effectively a minimal kernel running in a VM that doesn't
>> have access to this, correct?

> Oh, I didn't mean link to the kernel code, I meant "why not copy+paste  
> the kernel
> code?".  In other words, why select a different RNG implementation than  
> what the
> kernel uses?  In general, selftests and tools try to follow the kernel  
> code, even
> when copy+pasting, as that avoids questions like "why does the kernel do  
> X but
> selftests do Y?".  The copy+paste does sometimes lead to maintenance  
> pain, e.g. if
> the copied code has a bug that the kernel then fixes, but that seems  
> unlikely to
> happen in this case.

The real answer is I didn't know about it at the time. But I do think
the prandom_32_state seems like overkill for this application.

Re: [PATCH v6 3/3] KVM: selftests: randomize page access order

[Sean Christopherson]

On Tue, Oct 11, 2022, Colton Lewis wrote:
> Sean Christopherson <seanjc@google.com> writes:
> 
> > On Tue, Oct 11, 2022, Colton Lewis wrote:
> > > Sean Christopherson <seanjc@google.com> writes:
> > > > Ya, I'm trippling (quadrupling?) down on my suggestion to improve the
> > > > APIs.  Users
> > > > should not be able to screw up like this, i.e. shouldn't need comments
> > > > to warn
> > > > readers, and adding another call to get a random number shouldn't
> > > affect
> > > > unrelated
> > > > code.
> 
> > > Previous calls to PRNGs always affect later calls to PRNGs. That's how
> > > they work.
> 
> > Ya, that's not the type of bugs I'm worried about.
> 
> > > This "screw up" would be equally likely with any API because the caller
> > > always needs to decide if they should reuse the same random number
> > > or need a
> > > new one.
> 
> > I disagree, the in/out parameter _requires_ the calling code to store
> > the random
> > number in a variable.  Returning the random number allows consuming the
> > number
> > without needing an intermediate variable, e.g.
> 
> > 	if (random_bool())
> > 		<do stuff>
> 
> > which makes it easy to avoid an entire class of bugs.
> 
> Yes, but it's impossible to do this without hidden global state at the
> implementation level. That sacrifices reentrancy and thread-safety.

The above is super quick pseudocode that wasn't intended to be taken verbatim.
From my original suggestion in patch one[*], throw the seed/metadata in a opaque
struct, e.g. ksft_pseudo_rng (or kvm_pseudo_rng if the code ends up being KVM-only).

The intent is to hide the details of the rng, both so that the caller doesn't have
to worry about those details, but also so that the guts can be changed at will
without having to update callers.

[*] https://lore.kernel.org/all/20220912195849.3989707-2-coltonlewis@google.com

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Sean Christopherson]

On Tue, Oct 11, 2022, Colton Lewis wrote:
> Sean Christopherson <seanjc@google.com> writes:
> > Regardless of whether or not the details are gory, having to be aware of
> > those details unnecessarily impedes understanding the code.  The vast, vast
> > majority of folks that read this code won't care about how PRNGs work.
> > Even if the reader is familiar with PRNGs, those details aren't at all
> > relevant to understanding what the guest code does.  The reader only needs
> > to know "oh, this is randomizing the address".  How the randomization works
> > is completely irrelevant for that level of understanding.
> 
> It is relevant if the reader of the guest code cares about reentrancy
> and thread-safety (good for such things as reproducing the same stream
> of randoms from the same initial conditions), because they will have to
> manage some state to make that work. Whether that state is an integer or
> an opaque struct requires the same level of knowledge to use the API.

By "readers" I'm not (only) talking about developers actively writing code, I'm
I'm talking about people that run this test, encounter a failure, and read the code
to try and understand what went wrong.  For those people, knowing that the guest is
generating a random number is sufficient information during initial triage.  If the
failure ends up being related to the random number, then yes they'll likely need to
learn the details, but that's a few steps down the road.

> > > I agree returning the value could make it easier to use as part of
> > > expressions, but is it that important?
> 
> > Yes, because in pretty much every use case, the random number is going to
> > be immediately consumed.  Readability and robustness aside, returning the
> > value cuts the amount of code need to generate and consume a random number
> > in half.
> 
> Ok. This is trivial to change (or implement on top of what is
> there). Would you be happy with something like the following?
> 
> uint32_t guest_random(uint32_t *seed)
> {
> 	*seed = (uint64_t)*seed * 48271 % ((uint32_t)(1 << 31) - 1);
> 	return *seed;
> }

Honestly, no.  I truly don't understand the pushback on throwing the seed into
a struct and giving the helpers more precise names.  E.g. without looking at the
prototype, guest_random() tells the reader nothing about the size of the random
number returned, whereas <namespace>_random_u32() or <namespace>_get_random_u32()
(if we want to more closely follow kernel nomenclature) tells the reader exactly
what is returned.

As a contrived example, imagine a bug where the intent was to do 50/50 reads/writes,
but the test ends up doing almost all writes.  Code that looks like:

	if (guest_random(...))

is less obviously wrong than

	if (guest_random_u32(...))

even if the user knows nothing about how the random number is generated.

And aside from hiding details and providing abstraction for readers, throwing a
shim struct around the seed means that if we do want to change up the internal
implementation, then we can do so without having to churn users.

The code is trivial to write and I can't think of any meaningful downside.  Worst
case scenario, we end up with an implementation that is slightly more formal than
then we really need.

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Colton Lewis]

Sean Christopherson <seanjc@google.com> writes:

> On Tue, Oct 11, 2022, Colton Lewis wrote:
>> Sean Christopherson <seanjc@google.com> writes:
>> > Regardless of whether or not the details are gory, having to be aware  
>> of
>> > those details unnecessarily impedes understanding the code.  The vast,  
>> vast
>> > majority of folks that read this code won't care about how PRNGs work.
>> > Even if the reader is familiar with PRNGs, those details aren't at all
>> > relevant to understanding what the guest code does.  The reader only  
>> needs
>> > to know "oh, this is randomizing the address".  How the randomization  
>> works
>> > is completely irrelevant for that level of understanding.

>> It is relevant if the reader of the guest code cares about reentrancy
>> and thread-safety (good for such things as reproducing the same stream
>> of randoms from the same initial conditions), because they will have to
>> manage some state to make that work. Whether that state is an integer or
>> an opaque struct requires the same level of knowledge to use the API.

> By "readers" I'm not (only) talking about developers actively writing  
> code, I'm
> I'm talking about people that run this test, encounter a failure, and  
> read the code
> to try and understand what went wrong.  For those people, knowing that  
> the guest is
> generating a random number is sufficient information during initial  
> triage.  If the
> failure ends up being related to the random number, then yes they'll  
> likely need to
> learn the details, but that's a few steps down the road.


Ok. That makes sense to me.

>> > > I agree returning the value could make it easier to use as part of
>> > > expressions, but is it that important?

>> > Yes, because in pretty much every use case, the random number is going  
>> to
>> > be immediately consumed.  Readability and robustness aside, returning  
>> the
>> > value cuts the amount of code need to generate and consume a random  
>> number
>> > in half.

>> Ok. This is trivial to change (or implement on top of what is
>> there). Would you be happy with something like the following?

>> uint32_t guest_random(uint32_t *seed)
>> {
>> 	*seed = (uint64_t)*seed * 48271 % ((uint32_t)(1 << 31) - 1);
>> 	return *seed;
>> }

> Honestly, no.  I truly don't understand the pushback on throwing the seed  
> into
> a struct and giving the helpers more precise names.  E.g. without looking  
> at the
> prototype, guest_random() tells the reader nothing about the size of the  
> random
> number returned, whereas <namespace>_random_u32() or  
> <namespace>_get_random_u32()
> (if we want to more closely follow kernel nomenclature) tells the reader  
> exactly
> what is returned.


If that's what you care about, I'll wrap the state and put better
information in the names. I think I misunderstood your original comments
to mean you wanted something much more expansive than you really did and
I'm getting tired of redoing this patch.

> The code is trivial to write and I can't think of any meaningful  
> downside.  Worst
> case scenario, we end up with an implementation that is slightly more  
> formal than
> then we really need.

As a matter of personal taste, I don't like the additional formality
making things look more complicated than they are. The stakes are small
here but that kind of extra boilerplate can add up to make things
confusing.

Thanks for your patience. I never wanted to cause trouble.

Re: [PATCH v6 1/3] KVM: selftests: implement random number generation for guest code

[Sean Christopherson]

On Wed, Oct 12, 2022, Colton Lewis wrote:
> Sean Christopherson <seanjc@google.com> writes:
> > The code is trivial to write and I can't think of any meaningful downside.
> > Worst case scenario, we end up with an implementation that is slightly more
> > formal than then we really need.
> 
> As a matter of personal taste, I don't like the additional formality
> making things look more complicated than they are. The stakes are small
> here but that kind of extra boilerplate can add up to make things
> confusing.

I agree about unnecessary boilerplate being a burden, especially when it comes to
KVM selftests, which are ridiculously "formal" and make simple operations
frustratingly difficult.

In this case though, I think the benefits of encapsulating the seed outweigh the
cost of the formality by a good margin, and I don't see that formality snowballing
any further.  A struct gets us:

  - Type checking on the input param, e.g. prevents passing in garbage for the seed.
  - The ability to switch out the algorithm.
  - Some protection against overwriting the seed, e.g. corrupting the struct pointer
    will explode and a memcpy() to overwrite the struct will be more visibily wrong.

> Thanks for your patience. I never wanted to cause trouble.

Heh, no worries.