Pre-load and sort random blocks for pure read verify workloads

If fio is run with a write phase before a read phase and the
IO type is random, the end read verify phase will get sorted
blocks to read back. But if fio is asked to verify something
that was previously randomly written, it will generate the
same random offsets in random order and verify those. This is
usually much slower than a sorted read back.

So add a verifysort_nr option that allows the user to specify
a number of random offsets to pre-generate and sort, before
reading them and verifying the contents. This greatly speeds
up pure read verify workloads.

Default to 1024, and put a max of 64K entries on the option.
We do a merge list sort on the entries, so we don't want a
huge amount of backlog.

Signed-off-by: Jens Axboe <axboe@kernel.dk>
diff --git a/fio.h b/fio.h
index a528f6a..c5e2bf1 100644
--- a/fio.h
+++ b/fio.h
@@ -149,6 +149,7 @@
 	unsigned int verify;
 	unsigned int do_verify;
 	unsigned int verifysort;
+	unsigned int verifysort_nr;
 	unsigned int verify_interval;
 	unsigned int verify_offset;
 	char verify_pattern[MAX_PATTERN_SIZE];
@@ -515,6 +516,8 @@
 	struct flist_head trim_list;
 	unsigned long trim_entries;
 
+	struct flist_head next_rand_list;
+
 	/*
 	 * for fileservice, how often to switch to a new file
 	 */