block: add bdrv_query_info

Extract it out of the implementation of "info block".

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: add bdrv_query_stats

qmp_query_blockstat cannot have errors, remove the Error argument and
create a new public function bdrv_query_stats out of it.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: add bdrv_open_backing_file

Mirroring runs without the backing file so that it can be copied outside
QEMU.  However, we need to add it at the time the job is completed and
QEMU switches to the target.  Factor out the common bits of opening an
image and completing a mirroring operation.

The new function does not assume that the file is closed immediately after
it returns failure, so it keeps the BDRV_O_NO_BACKING flag up-to-date.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: introduce new dirty bitmap functionality

Assert that write_compressed is never used with the dirty bitmap.
Setting the bits early is wrong, because a coroutine might concurrently
examine them and copy incomplete data from the source.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: export dirty bitmap information in query-block

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: add block-job-complete

While streaming can be dropped as soon as it progressed through the whole
image, mirroring needs to be completed manually for two reasons: 1) so that
management knows exactly when the VM switches to the target; 2) because
for other use cases such as replication, we may leave the operation running
for the whole life of the virtual machine.

Add a new block job command that manually completes background operations.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: introduce BLOCK_JOB_READY event

Even for jobs that need to be manually completed, management may want
to take care itself of the completion, not requiring the user to issue
a command to terminate the job.  In this case we want to avoid that
they poll us continuously, waiting for completion to become available.
Thus, add a new event that signals the phase switch and the availability
of the block-job-complete command.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
mirror: introduce mirror job

This patch adds the implementation of a new job that mirrors a disk to
a new image while letting the guest continue using the old image.
The target is treated as a "black box" and data is copied from the
source to the target in the background.  This can be used for several
purposes, including storage migration, continuous replication, and
observation of the guest I/O in an external program.  It is also a
first step in replacing the inefficient block migration code that is
part of QEMU.

The job is possibly never-ending, but it is logically structured into
two phases: 1) copy all data as fast as possible until the target
first gets in sync with the source; 2) keep target in sync and
ensure that reopening to the target gets a correct (full) copy
of the source data.

The second phase is indicated by the progress in "info block-jobs"
reporting the current offset to be equal to the length of the file.
When the job is cancelled in the second phase, QEMU will run the
job until the source is clean and quiescent, then it will report
successful completion of the job.

In other words, the BLOCK_JOB_CANCELLED event means that the target
may _not_ be consistent with a past state of the source; the
BLOCK_JOB_COMPLETED event means that the target is consistent with
a past state of the source.  (Note that it could already happen
that management lost the race against QEMU and got a completion
event instead of cancellation).

It is not yet possible to complete the job and switch over to the target
disk.  The next patches will fix this and add many refinements to the
basic idea introduced here.  These include improved error management,
some tunable knobs and performance optimizations.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
qmp: add drive-mirror command

This adds the monitor commands that start the mirroring job.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
mirror: implement completion

Switching to the target of the migration is done mostly asynchronously,
and reported to management via the BLOCK_JOB_COMPLETED event; the only
synchronous phase is opening the backing files.  bdrv_open_backing_file
can always be done, even for migration of the full image (aka sync:
'full').  In this case, qmp_drive_mirror will create the target disk
with no backing file at all, and bdrv_open_backing_file will be a no-op.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
qemu-iotests: add mirroring test case

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
iostatus: forward block_job_iostatus_reset to block job

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
mirror: add support for on-source-error/on-target-error

Error management is important for mirroring; otherwise, an error on the
target (even something as "innocent" as ENOSPC) requires to start again
with a full copy.  Similar to on_read_error/on_write_error, two separate
knobs are provided for on_source_error (reads) and on_target_error (writes).
The default is 'report' for both.

The 'ignore' policy will leave the sector dirty, so that it will be
retried later.  Thus, it will not cause corruption.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
qmp: add pull_event function

This function is unlike get_events in that it makes it easy to process
one event at a time.  This is useful in the mirroring test cases, where
we want to process just one event (BLOCK_JOB_ERROR) and leave the others
to a helper function.

Cc: Luiz Capitulino <lcapitulino@redhat.com>
Acked-by: Luiz Capitulino <lcapitulino@redhat.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
qemu-iotests: add testcases for mirroring on-source-error/on-target-error

The new options are tested with blkdebug on both the source and the
target.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
host-utils: add ffsl

We can provide fast versions based on the other functions defined
by host-utils.h.  Some care is required on glibc, which provides
ffsl already.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
add hierarchical bitmap data type and test cases

HBitmaps provides an array of bits.  The bits are stored as usual in an
array of unsigned longs, but HBitmap is also optimized to provide fast
iteration over set bits; going from one bit to the next is O(logB n)
worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
that the number of levels is in fact fixed.

In order to do this, it stacks multiple bitmaps with progressively coarser
granularity; in all levels except the last, bit N is set iff the N-th
unsigned long is nonzero in the immediately next level.  When iteration
completes on the last level it can examine the 2nd-last level to quickly
skip entire words, and even do so recursively to skip blocks of 64 words or
powers thereof (32 on 32-bit machines).

Given an index in the bitmap, it can be split in group of bits like
this (for the 64-bit case):

     bits 0-57 => word in the last bitmap     | bits 58-63 => bit in the word
     bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
     bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word

So it is easy to move up simply by shifting the index right by
log2(BITS_PER_LONG) bits.  To move down, you shift the index left
similarly, and add the word index within the group.  Iteration uses
ffs (find first set bit) to find the next word to examine; this
operation can be done in constant time in most current architectures.

Setting or clearing a range of m bits on all levels, the work to perform
is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.

When iterating on a bitmap, each bit (on any level) is only visited
once.  Hence, The total cost of visiting a bitmap with m bits in it is
the number of bits that are set in all bitmaps.  Unless the bitmap is
extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
cost of advancing from one bit to the next is usually constant.

Reviewed-by: Laszlo Ersek <lersek@redhat.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: implement dirty bitmap using HBitmap

This actually uses the dirty bitmap in the block layer, and converts
mirroring to use an HBitmapIter.

Reviewed-by: Laszlo Ersek <lersek@redhat.com> (except block/mirror.c parts)
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
block: make round_to_clusters public

This is needed in the following patch.

Reviewed-by: Laszlo Ersek <lersek@redhat.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
mirror: perform COW if the cluster size is bigger than the granularity

When mirroring runs, the backing files for the target may not yet be
ready.  However, this means that a copy-on-write operation on the target
would fill the missing sectors with zeros.  Copy-on-write only happens
if the granularity of the dirty bitmap is smaller than the cluster size
(and only for clusters that are allocated in the source after the job
has started copying).  So far, the granularity was fixed to 1MB; to avoid
the problem we detected the situation and required the backing files to
be available in that case only.

However, we want to lower the granularity for efficiency, so we need
a better solution.  The solution is to always copy a whole cluster the
first time it is touched.  The code keeps a bitmap of clusters that
have already been allocated by the mirroring job, and only does "manual"
copy-on-write if the chunk being copied is zero in the bitmap.

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>