kvm tools: Add QCOW level2 caching support

kvm tools: Add QCOW level2 caching support

QCOW uses two tables level1 (L1) table and level2 (L2) table. The L1 table
points to offset of L2 table. When a QCOW image is probed, the L1 table is
cached in the memory to avoid reading it from disk on every access. This
caching improves the performance.

The similar performance improvement can be observed when L2 tables are cached.
It is impossible to cache all of the L2 tables because of the memory
constraint. The patch adds L2 table caching capability for up to 32 L2 tables,
it uses combination of RB tree and List to manage the L2 cached tables. The
link list implementation helps in building simple LRU structure and RB tree
helps to search cached table efficiently.

To calculate the performance numbers, the VM was started with following
command line arguments

$ ./kvm run -d /dev/shm/kvm_ubuntu_server.qcow2 --params "root=/dev/vda1" \
> -m 2048

Without Cache
=============
$ fio fio-mixed.job
[...]
fio-sync: (groupid=3, jobs=1): err= 0: pid=563
  read : io=102400KB, bw=31239KB/s, iops=429 , runt=  3278msec
    clat (usec): min=4 , max=31668 , avg=1663.94, stdev=1810.37
     lat (usec): min=281 , max=658022 , avg=162456.88, stdev=242272.58
    bw (KB/s) : min=21536, max=29322, per=20.77%, avg=25956.50, stdev=2755.33
  write: io=34688KB, bw=13235KB/s, iops=183 , runt=  2621msec
    clat (usec): min=77 , max=1619 , avg=431.80, stdev=343.81
     lat (usec): min=78 , max=1620 , avg=433.11, stdev=343.83
    bw (KB/s) : min=11168, max=14447, per=26.34%, avg=13246.00, stdev=1293.73
[...]
Run status group 0 (all jobs):
   READ: io=409600KB, aggrb=74594KB/s, minb=19096KB/s, maxb=20917KB/s,
		mint=5013msec, maxt=5491msec
  WRITE: io=139552KB, aggrb=42624KB/s, minb=10263KB/s, maxb=14463KB/s,
		mint=2414msec, maxt=3274msec

Run status group 1 (all jobs):
   READ: io=409600KB, aggrb=146442KB/s, minb=37489KB/s, maxb=48680KB/s,
		mint=2154msec, maxt=2797msec
  WRITE: io=133296KB, aggrb=59613KB/s, minb=15328KB/s, maxb=16774KB/s,
		mint=2041msec, maxt=2236msec

Run status group 2 (all jobs):
   READ: io=409600KB, aggrb=7178KB/s, minb=1837KB/s, maxb=1840KB/s,
		mint=56961msec, maxt=57057msec
  WRITE: io=139136KB, aggrb=2446KB/s, minb=600KB/s, maxb=661KB/s,
		mint=56238msec, maxt=56880msec

Run status group 3 (all jobs):
   READ: io=409600KB, aggrb=124954KB/s, minb=31988KB/s, maxb=37704KB/s,
		mint=2781msec, maxt=3278msec
  WRITE: io=137936KB, aggrb=50286KB/s, minb=12447KB/s, maxb=13885KB/s,
		mint=2621msec, maxt=2743msec

Disk stats (read/write):
  vda: ios=118760/16273, merge=0/107354, ticks=159260/658290, in_queue=817410,
		util=94.37%
[...]

With Cache
==========
$ fio fio-mixed.job
[...]
fio-sync: (groupid=3, jobs=1): err= 0: pid=573
  read : io=102400KB, bw=76704KB/s, iops=1018 , runt=  1335msec
    clat (usec): min=0 , max=66131 , avg=591.46, stdev=2582.59
     lat (usec): min=66 , max=123396 , avg=25609.49, stdev=38397.57
    bw (KB/s) : min=58208, max=59584, per=34.55%, avg=58896.00, stdev=972.98
  write: io=35600KB, bw=29373KB/s, iops=381 , runt=  1212msec
    clat (usec): min=11 , max=2661 , avg=169.58, stdev=191.60
     lat (usec): min=11 , max=2663 , avg=170.91, stdev=191.78
    bw (KB/s) : min=27104, max=37664, per=29.98%, avg=32384.00, stdev=7467.05
[...]
Run status group 0 (all jobs):
   READ: io=409600KB, aggrb=140562KB/s, minb=35984KB/s, maxb=44450KB/s,
		mint=2359msec, maxt=2914msec
  WRITE: io=138816KB, aggrb=124722KB/s, minb=31502KB/s, maxb=40180KB/s,
		mint=893msec, maxt=1113msec

Run status group 1 (all jobs):
   READ: io=409600KB, aggrb=231151KB/s, minb=59174KB/s, maxb=96111KB/s,
		mint=1091msec, maxt=1772msec
  WRITE: io=141936KB, aggrb=137268KB/s, minb=32340KB/s, maxb=44496KB/s,
		mint=813msec, maxt=1034msec

Run status group 2 (all jobs):
   READ: io=409600KB, aggrb=9211KB/s, minb=2358KB/s, maxb=2363KB/s,
		mint=44367msec, maxt=44468msec
  WRITE: io=129808KB, aggrb=2931KB/s, minb=707KB/s, maxb=797KB/s,
		mint=43331msec, maxt=44285msec

Run status group 3 (all jobs):
   READ: io=409600KB, aggrb=170453KB/s, minb=43636KB/s, maxb=78545KB/s,
		mint=1335msec, maxt=2403msec
  WRITE: io=138256KB, aggrb=108012KB/s, minb=27648KB/s, maxb=37931KB/s,
		mint=879msec, maxt=1280msec

Disk stats (read/write):
  vda: ios=120698/16690, merge=0/114742, ticks=113170/304480, in_queue=417560,
		util=93.26%
[...]

Summary
=======
Read  bandwidth increased by 1.2 to 1.8 times
Write bandwidth increased by 1.1 to 2.9 times
Read  latency   decreased by small margin of 0.2
Write latency   decreased by 0.4

Signed-off-by: Prasad Joshi <prasadjoshi124@gmail.com>
Signed-off-by: Pekka Enberg <penberg@kernel.org>