Rework file random map

Fio slows down at the end of a random IO run, when the random
map is used and it gets fuller. This causes slowdowns in
IOPS. This is largely due to the file random map being an
array of bits, and with random access to single bits of the
array at the time, locality is awful. The effect is observable
throughout a run, though, where it gradually gets slower and
slower. It just becomes more apparent at near the end of the
run, where the last 10% are fairly bad. This is even with
doing a bunch of tricks to reduce that cost.

Implement an N-level bitmap, where layer N uses a single bit
to represent 32/64-bits at layer N-1. The number of layers
depends on the number of blocks.

This has slightly higher overhead initially in theory, in
practice it performs about the same. As a bonus, the throughput
remains constant during the run, and even becomes faster
near the end.

Signed-off-by: Jens Axboe <axboe@kernel.dk>

1 files changed, 4 insertions, 8 deletions

diff --git a/file.h b/file.h
index 38e9d0d4..ce92ff75 100644
--- a/file.h
+++ b/file.h
@@ -6,6 +6,7 @@
 #include "io_ddir.h"
 #include "flist.h"
 #include "lib/zipf.h"
+#include "lib/bitmap.h"
 
 /*
  * The type of object we are working on
@@ -108,10 +109,7 @@ struct fio_file {
 	/*
 	 * block map for random io
 	 */
-	unsigned long *file_map;
-	unsigned long num_maps;
-	unsigned long last_free_lookup;
-	unsigned failed_rands;
+	struct bitmap *io_bitmap;
 
 	/*
 	 * Used for zipf random distribution
@@ -177,13 +175,11 @@ extern void free_release_files(struct thread_data *);
 
 static inline void fio_file_reset(struct fio_file *f)
 {
-	f->last_free_lookup = 0;
-	f->failed_rands = 0;
 	f->last_pos = f->file_offset;
 	f->last_start = -1ULL;
 	f->file_pos = -1ULL;
-	if (f->file_map)
-		memset(f->file_map, 0, f->num_maps * sizeof(unsigned long));
+	if (f->io_bitmap)
+		bitmap_reset(f->io_bitmap);
 }
 
 #endif