Fix rand_seed mismatches in verify phase

In verify phase, the rand_seed generated on replay does not match
the written rand_seed.

Multiple problems are causing this:
1. In verify phase fio does not set io_u->rand_seed to compare with
   hdr->rand_seed
2. In randrw scenario, fio log is stored in red-black tree in "sorted by LBA"
   order.  Thus, it is imposible to replay the written order, or rather
   generate the seeds again in the same order.
3. In write phase, the code currently will generate rand_seed, write data
   and log rand_seed. When queuedepth > 1, it's possible the writes complete
   in a different order than rand_seed was generated.  Thus when replaying
   the log, the generated rand_seed might not match what was written.
4. verify_backlog option will start verification before all the data has been
   written and it make rand_seed replay code broken with current design.

Proposed fixes:
1. Use of existing verify_state to generate verify header.
   (and assumes this was the original intention of verify_state). And also
   adds code to replay rand_seed in verify phase.
2. If verifysort option is not enabled, store the write log in a list instead
   of the red-black tree. Otherwise, don't attempt to verify the rand_seed
   in the header.
3. In write phase,  generate rand_seed, log rand_seed, write data. I.e. log
   IO transactions in the order generated, not completed.
4. Don't verify rand_seed when verify_backlog is enabled.

Signed-off-by: Puthikorn Voravootivat <puthik@chromium.org>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
diff --git a/verify.c b/verify.c
index 568bae8..90cd093 100644
--- a/verify.c
+++ b/verify.c
@@ -72,10 +72,10 @@
 		if (use_seed)
 			__fill_random_buf(p, len, seed);
 		else
-			io_u->rand_seed = fill_random_buf(&td->buf_state, p, len);
+			io_u->rand_seed = fill_random_buf(&td->__verify_state, p, len);
 		return;
 	}
-	
+
 	if (io_u->buf_filled_len >= len) {
 		dprint(FD_VERIFY, "using already filled verify pattern b=%d len=%u\n",
 			td->o.verify_pattern_bytes, len);
@@ -718,6 +718,13 @@
 			memswp(p, p + td->o.verify_offset, header_size);
 		hdr = p;
 
+		/*
+		 * Make rand_seed check pass when have verifysort or
+		 * verify_backlog.
+		 */
+		if (td->o.verifysort || (td->flags & TD_F_VER_BACKLOG))
+			io_u->rand_seed = hdr->rand_seed;
+
 		ret = verify_header(io_u, hdr);
 		switch (ret) {
 		case 0:
@@ -1056,6 +1063,12 @@
 		remove_trim_entry(td, ipo);
 		free(ipo);
 		dprint(FD_VERIFY, "get_next_verify: ret io_u %p\n", io_u);
+
+		if (!td->o.verify_pattern_bytes) {
+			io_u->rand_seed = __rand(&td->__verify_state);
+			if (sizeof(int) != sizeof(long *))
+				io_u->rand_seed *= __rand(&td->__verify_state);
+		}
 		return 0;
 	}