[v4,2/6] add basic backup support to block driver

Function backup_job_create() creates a block job to backup a block device.
The coroutine is started with backup_job_start().

We call backup_do_cow() for each write during backup. That function
reads the original data and pass it to backup_dump_cb().

The tracked_request infrastructure is used to serialize access.

Currently backup cluster size is hardcoded to 65536 bytes.

Signed-off-by: Dietmar Maurer <dietmar@proxmox.com>
---
 Makefile.objs            |    1 +
 backup.c                 |  338 ++++++++++++++++++++++++++++++++++++++++++++++
 backup.h                 |   32 +++++
 block.c                  |   71 +++++++++-
 include/block/block.h    |    2 +
 include/block/blockjob.h |   10 ++
 6 files changed, 448 insertions(+), 6 deletions(-)
 create mode 100644 backup.c
 create mode 100644 backup.h

On Wed, Feb 20, 2013 at 10:31:59AM +0100, Dietmar Maurer wrote:
> +typedef struct BackupBlockJob {
> +    BlockJob common;
> +    RateLimit limit;
> +    uint64_t sectors_read;
> +    unsigned long *bitmap;
> +    int bitmap_size;
> +    BackupDumpFunc *backup_dump_cb;
> +    BlockDriverCompletionFunc *backup_complete_cb;
> +    void *opaque;
> +} BackupBlockJob;
> +
> +static int backup_get_bitmap(BackupBlockJob *job, int64_t cluster_num)

bool return value

> +{
> +    assert(job);
> +    assert(job->bitmap);
> +
> +    unsigned long val, idx, bit;
> +
> +    idx = cluster_num / BITS_PER_LONG;
> +
> +    assert(job->bitmap_size > idx);
> +
> +    bit = cluster_num % BITS_PER_LONG;
> +    val = job->bitmap[idx];
> +
> +    return !!(val & (1UL << bit));
> +}
> +
> +static void backup_set_bitmap(BackupBlockJob *job, int64_t cluster_num,
> +                              int dirty)

s/int dirty/bool dirty/

> +{
> +    assert(job);
> +    assert(job->bitmap);
> +
> +    unsigned long val, idx, bit;
> +
> +    idx = cluster_num / BITS_PER_LONG;
> +
> +    assert(job->bitmap_size > idx);
> +
> +    bit = cluster_num % BITS_PER_LONG;
> +    val = job->bitmap[idx];
> +    if (dirty) {
> +        if (!(val & (1UL << bit))) {
> +            val |= 1UL << bit;
> +        }
> +    } else {
> +        if (val & (1UL << bit)) {
> +            val &= ~(1UL << bit);
> +        }
> +    }

The set and clear can be unconditional.  No need to check that the bit
is clear before setting it and vice versa.

> +    job->bitmap[idx] = val;
> +}
> +
> +static int backup_in_progress_count;
> +
> +static int coroutine_fn backup_do_cow(BlockDriverState *bs,
> +                                      int64_t sector_num, int nb_sectors)
> +{
> +    assert(bs);
> +    BackupBlockJob *job = (BackupBlockJob *)bs->job;
> +    assert(job);
> +
> +    BlockDriver *drv = bs->drv;
> +    struct iovec iov;
> +    QEMUIOVector bounce_qiov;
> +    void *bounce_buffer = NULL;
> +    int ret = 0;
> +
> +    backup_in_progress_count++;
> +
> +    int64_t start, end;
> +
> +    start = sector_num / BACKUP_BLOCKS_PER_CLUSTER;
> +    end = (sector_num + nb_sectors + BACKUP_BLOCKS_PER_CLUSTER - 1) /
> +        BACKUP_BLOCKS_PER_CLUSTER;
> +
> +    DPRINTF("brdv_co_backup_cow enter %s C%zd %zd %d\n",
> +            bdrv_get_device_name(bs), start, sector_num, nb_sectors);

Please use PRId64 for int64_t printf arguments in this function.  "z" is
for size_t, which will be wrong on 32-bit hosts.

> +static void coroutine_fn backup_run(void *opaque)
> +{
> +    BackupBlockJob *job = opaque;
> +    BlockDriverState *bs = job->common.bs;
> +    assert(bs);
> +
> +    int64_t start, end;
> +
> +    start = 0;
> +    end = (bs->total_sectors + BACKUP_BLOCKS_PER_CLUSTER - 1) /
> +        BACKUP_BLOCKS_PER_CLUSTER;
> +
> +    DPRINTF("backup_run start %s %zd %zd\n", bdrv_get_device_name(bs),
> +            start, end);
> +
> +    int ret = 0;
> +
> +    for (; start < end; start++) {
> +        if (block_job_is_cancelled(&job->common)) {
> +            ret = -1;
> +            break;
> +        }
> +
> +        /* we need to yield so that qemu_aio_flush() returns.
> +         * (without, VM does not reboot)
> +        * Note: use 1000 instead of 0 (0 prioritize this task too much)

indentation

What does "0 prioritize this task too much" mean?  If no rate limit has
been set the job should run at full speed.  We should not hardcode
arbitrary delays like 1000.

> +         */
> +        if (job->common.speed) {
> +            uint64_t delay_ns = ratelimit_calculate_delay(
> +                &job->limit, job->sectors_read);
> +            job->sectors_read = 0;
> +            block_job_sleep_ns(&job->common, rt_clock, delay_ns);
> +        } else {
> +            block_job_sleep_ns(&job->common, rt_clock, 1000);
> +        }
> +
> +        if (block_job_is_cancelled(&job->common)) {
> +            ret = -1;
> +            break;
> +        }
> +
> +        if (backup_get_bitmap(job, start)) {
> +            continue; /* already copied */
> +        }
> +
> +        DPRINTF("backup_run loop C%zd\n", start);
> +
> +        /**
> +         * This triggers a cluster copy
> +         * Note: avoid direct call to brdv_co_backup_cow, because
> +         * this does not call tracked_request_begin()
> +         */
> +        ret = bdrv_co_backup(bs, start*BACKUP_BLOCKS_PER_CLUSTER, 1);
> +        if (ret < 0) {
> +            break;
> +        }
> +        /* Publish progress */
> +        job->common.offset += BACKUP_CLUSTER_SIZE;
> +    }
> +
> +    while (backup_in_progress_count > 0) {
> +        DPRINTF("backup_run backup_in_progress_count != 0 (%d)",
> +                backup_in_progress_count);
> +        block_job_sleep_ns(&job->common, rt_clock, 10000);
> +
> +    }

Sleeping is bad.  You can use a coroutine rwlock: backup_do_cow() takes
a read lock and backup_run() takes a write lock to ensure all pending
backup_do_cow() calls have completed.

This also gets rid of the backup_in_progress_count global.

> diff --git a/backup.h b/backup.h
> new file mode 100644
> index 0000000..d9395bc
> --- /dev/null
> +++ b/backup.h
> @@ -0,0 +1,32 @@
> +/*
> + * QEMU backup related definitions
> + *
> + * Copyright (C) 2013 Proxmox Server Solutions
> + *
> + * Authors:
> + *  Dietmar Maurer (dietmar@proxmox.com)
> + *
> + * This work is licensed under the terms of the GNU GPL, version 2 or later.
> + * See the COPYING file in the top-level directory.
> + *
> + */
> +
> +#ifndef QEMU_BACKUP_H
> +#define QEMU_BACKUP_H
> +
> +#include <uuid/uuid.h>

Not used in this patch.

> > +    bit = cluster_num % BITS_PER_LONG;
> > +    val = job->bitmap[idx];
> > +    if (dirty) {
> > +        if (!(val & (1UL << bit))) {
> > +            val |= 1UL << bit;
> > +        }
> > +    } else {
> > +        if (val & (1UL << bit)) {
> > +            val &= ~(1UL << bit);
> > +        }
> > +    }
> 
> The set and clear can be unconditional.  No need to check that the bit is clear
> before setting it and vice versa.

Thanks, will change.
 
> > +    job->bitmap[idx] = val;
> > +}
> > +
> > +static int backup_in_progress_count;
> > +
> > +static int coroutine_fn backup_do_cow(BlockDriverState *bs,
> > +                                      int64_t sector_num, int
> > +nb_sectors) {
> > +    assert(bs);
> > +    BackupBlockJob *job = (BackupBlockJob *)bs->job;
> > +    assert(job);
> > +
> > +    BlockDriver *drv = bs->drv;
> > +    struct iovec iov;
> > +    QEMUIOVector bounce_qiov;
> > +    void *bounce_buffer = NULL;
> > +    int ret = 0;
> > +
> > +    backup_in_progress_count++;
> > +
> > +    int64_t start, end;
> > +
> > +    start = sector_num / BACKUP_BLOCKS_PER_CLUSTER;
> > +    end = (sector_num + nb_sectors + BACKUP_BLOCKS_PER_CLUSTER - 1) /
> > +        BACKUP_BLOCKS_PER_CLUSTER;
> > +
> > +    DPRINTF("brdv_co_backup_cow enter %s C%zd %zd %d\n",
> > +            bdrv_get_device_name(bs), start, sector_num, nb_sectors);
> 
> Please use PRId64 for int64_t printf arguments in this function.  "z" is for size_t,
> which will be wrong on 32-bit hosts.

OK

> > +static void coroutine_fn backup_run(void *opaque) {
> > +    BackupBlockJob *job = opaque;
> > +    BlockDriverState *bs = job->common.bs;
> > +    assert(bs);
> > +
> > +    int64_t start, end;
> > +
> > +    start = 0;
> > +    end = (bs->total_sectors + BACKUP_BLOCKS_PER_CLUSTER - 1) /
> > +        BACKUP_BLOCKS_PER_CLUSTER;
> > +
> > +    DPRINTF("backup_run start %s %zd %zd\n", bdrv_get_device_name(bs),
> > +            start, end);
> > +
> > +    int ret = 0;
> > +
> > +    for (; start < end; start++) {
> > +        if (block_job_is_cancelled(&job->common)) {
> > +            ret = -1;
> > +            break;
> > +        }
> > +
> > +        /* we need to yield so that qemu_aio_flush() returns.
> > +         * (without, VM does not reboot)
> > +        * Note: use 1000 instead of 0 (0 prioritize this task too
> > + much)
> 
> indentation
> 
> What does "0 prioritize this task too much" mean?  If no rate limit has been set
> the job should run at full speed.  We should not hardcode arbitrary delays like
> 1000.

The VM itself gets somehow slower during backup - do not know why. As workaround sleep 1000 works.

> > +         */
> > +        if (job->common.speed) {
> > +            uint64_t delay_ns = ratelimit_calculate_delay(
> > +                &job->limit, job->sectors_read);
> > +            job->sectors_read = 0;
> > +            block_job_sleep_ns(&job->common, rt_clock, delay_ns);
> > +        } else {
> > +            block_job_sleep_ns(&job->common, rt_clock, 1000);
> > +        }
> > +
> > +        if (block_job_is_cancelled(&job->common)) {
> > +            ret = -1;
> > +            break;
> > +        }
> > +
> > +        if (backup_get_bitmap(job, start)) {
> > +            continue; /* already copied */
> > +        }
> > +
> > +        DPRINTF("backup_run loop C%zd\n", start);
> > +
> > +        /**
> > +         * This triggers a cluster copy
> > +         * Note: avoid direct call to brdv_co_backup_cow, because
> > +         * this does not call tracked_request_begin()
> > +         */
> > +        ret = bdrv_co_backup(bs, start*BACKUP_BLOCKS_PER_CLUSTER, 1);
> > +        if (ret < 0) {
> > +            break;
> > +        }
> > +        /* Publish progress */
> > +        job->common.offset += BACKUP_CLUSTER_SIZE;
> > +    }
> > +
> > +    while (backup_in_progress_count > 0) {
> > +        DPRINTF("backup_run backup_in_progress_count != 0 (%d)",
> > +                backup_in_progress_count);
> > +        block_job_sleep_ns(&job->common, rt_clock, 10000);
> > +
> > +    }
> 
> Sleeping is bad.  
> You can use a coroutine rwlock: backup_do_cow() takes a read
> lock and backup_run() takes a write lock to ensure all pending
> backup_do_cow() calls have completed.
> 
> This also gets rid of the backup_in_progress_count global.

OK, will do.

On Thu, Feb 21, 2013 at 05:23:30AM +0000, Dietmar Maurer wrote:
> > > +static void coroutine_fn backup_run(void *opaque) {
> > > +    BackupBlockJob *job = opaque;
> > > +    BlockDriverState *bs = job->common.bs;
> > > +    assert(bs);
> > > +
> > > +    int64_t start, end;
> > > +
> > > +    start = 0;
> > > +    end = (bs->total_sectors + BACKUP_BLOCKS_PER_CLUSTER - 1) /
> > > +        BACKUP_BLOCKS_PER_CLUSTER;
> > > +
> > > +    DPRINTF("backup_run start %s %zd %zd\n", bdrv_get_device_name(bs),
> > > +            start, end);
> > > +
> > > +    int ret = 0;
> > > +
> > > +    for (; start < end; start++) {
> > > +        if (block_job_is_cancelled(&job->common)) {
> > > +            ret = -1;
> > > +            break;
> > > +        }
> > > +
> > > +        /* we need to yield so that qemu_aio_flush() returns.
> > > +         * (without, VM does not reboot)
> > > +        * Note: use 1000 instead of 0 (0 prioritize this task too
> > > + much)
> > 
> > indentation
> > 
> > What does "0 prioritize this task too much" mean?  If no rate limit has been set
> > the job should run at full speed.  We should not hardcode arbitrary delays like
> > 1000.
> 
> The VM itself gets somehow slower during backup - do not know why. As workaround sleep 1000 works.

Please find out why, it's a bug that an arbitrary sleep hides but
doesn't fix (plus the sleep makes backup less efficient).

If the VM becomes slow this loop is probably "spinning" without doing
blocking I/O and only doing sleep 0.  I guess that can happen when you
loop over blocks that have already been backed up (bit has been set)?

Stefan

> > > > +    for (; start < end; start++) {
> > > > +        if (block_job_is_cancelled(&job->common)) {
> > > > +            ret = -1;
> > > > +            break;
> > > > +        }
> > > > +
> > > > +        /* we need to yield so that qemu_aio_flush() returns.
> > > > +         * (without, VM does not reboot)
> > > > +        * Note: use 1000 instead of 0 (0 prioritize this task too
> > > > + much)
> > >
> > > indentation
> > >
> > > What does "0 prioritize this task too much" mean?  If no rate limit
> > > has been set the job should run at full speed.  We should not
> > > hardcode arbitrary delays like 1000.
> >
> > The VM itself gets somehow slower during backup - do not know why. As
> workaround sleep 1000 works.
> 
> Please find out why, it's a bug that an arbitrary sleep hides but doesn't fix (plus
> the sleep makes backup less efficient).
> 
> If the VM becomes slow this loop is probably "spinning" without doing blocking
> I/O and only doing sleep 0.  I guess that can happen when you loop over blocks
> that have already been backed up (bit has been set)?

Well, 'slow' is the wrong term. The VM just gets a bit unresponsive - its just a feeling.

I think this is because the backup job runs at same priority as normal guest IO.

We previously used LVM and run backup with 'idle' IO priority (CFQ) to avoid such behavior.

But qemu does not provide an IO queue where we can set scheduling priorities?

On Mon, Feb 25, 2013 at 06:48:39AM +0000, Dietmar Maurer wrote:
> > > > > +    for (; start < end; start++) {
> > > > > +        if (block_job_is_cancelled(&job->common)) {
> > > > > +            ret = -1;
> > > > > +            break;
> > > > > +        }
> > > > > +
> > > > > +        /* we need to yield so that qemu_aio_flush() returns.
> > > > > +         * (without, VM does not reboot)
> > > > > +        * Note: use 1000 instead of 0 (0 prioritize this task too
> > > > > + much)
> > > >
> > > > indentation
> > > >
> > > > What does "0 prioritize this task too much" mean?  If no rate limit
> > > > has been set the job should run at full speed.  We should not
> > > > hardcode arbitrary delays like 1000.
> > >
> > > The VM itself gets somehow slower during backup - do not know why. As
> > workaround sleep 1000 works.
> > 
> > Please find out why, it's a bug that an arbitrary sleep hides but doesn't fix (plus
> > the sleep makes backup less efficient).
> > 
> > If the VM becomes slow this loop is probably "spinning" without doing blocking
> > I/O and only doing sleep 0.  I guess that can happen when you loop over blocks
> > that have already been backed up (bit has been set)?
> 
> Well, 'slow' is the wrong term. The VM just gets a bit unresponsive - its just a feeling.
> 
> I think this is because the backup job runs at same priority as normal guest IO.
> 
> We previously used LVM and run backup with 'idle' IO priority (CFQ) to avoid such behavior.
> 
> But qemu does not provide an IO queue where we can set scheduling priorities?

QEMU block jobs support rate-limiting.  Set it to 10-20% of the disk's
throughput and the slowness should go away but the backup takes longer.

Stefan

> > We previously used LVM and run backup with 'idle' IO priority (CFQ) to avoid
> such behavior.
> >
> > But qemu does not provide an IO queue where we can set scheduling
> priorities?
> 
> QEMU block jobs support rate-limiting.  Set it to 10-20% of the disk's throughput
> and the slowness should go away but the backup takes longer.

Sorry, but I don't want to set a rate limit. I want to set an IO priority - this is something different.
My solution does not delay the backup.

On Mon, Feb 25, 2013 at 03:49:11PM +0000, Dietmar Maurer wrote:
> > > We previously used LVM and run backup with 'idle' IO priority (CFQ) to avoid
> > such behavior.
> > >
> > > But qemu does not provide an IO queue where we can set scheduling
> > priorities?
> > 
> > QEMU block jobs support rate-limiting.  Set it to 10-20% of the disk's throughput
> > and the slowness should go away but the backup takes longer.
> 
> Sorry, but I don't want to set a rate limit. I want to set an IO priority - this is something different.
> My solution does not delay the backup.

QEMU is not in a position to implement global scheduling (priorities).
The QEMU process only knows about one guest.  If you have multiple
guests on the host an I/O "priority" inside QEMU process A will not take
into account QEMU process B.

Your solution *does* delay backup by 1 ms each iteration :).

Stefan

On Mon, Feb 25, 2013 at 03:49:11PM +0000, Dietmar Maurer wrote:
> > > We previously used LVM and run backup with 'idle' IO priority (CFQ) to avoid
> > such behavior.
> > >
> > > But qemu does not provide an IO queue where we can set scheduling
> > priorities?
> > 
> > QEMU block jobs support rate-limiting.  Set it to 10-20% of the disk's throughput
> > and the slowness should go away but the backup takes longer.
> 
> Sorry, but I don't want to set a rate limit. I want to set an IO priority - this is something different.
> My solution does not delay the backup.

I just reread the code and noticed the delay is 1 microsecond, not 1
millisecond.

The problem is that this is a magic value.  It worked on your machine
with your workload, but there's no guarantee it works on anyone else's
machine or workload.  We can't depend on magic values like this.

If you want to implement an alternative to rate-limiting, please do it
in a separate patch series and make it work for all block job types.

Stefan

> QEMU is not in a position to implement global scheduling (priorities).
> The QEMU process only knows about one guest.  If you have multiple guests on
> the host an I/O "priority" inside QEMU process A will not take into account
> QEMU process B.

I only want priorities inside the guest. The backup job should have lower priority
that the guest itself. Global priorities are something else.

> I just reread the code and noticed the delay is 1 microsecond, not 1 millisecond.

Yes, It does not really add a delay.

> The problem is that this is a magic value.  It worked on your machine with your
> workload, but there's no guarantee it works on anyone else's machine or
> workload.  We can't depend on magic values like this.
> 
> If you want to implement an alternative to rate-limiting, please do it in a
> separate patch series and make it work for all block job types.

Well, I hoped you can see how to fix that. I guess the same applies for other types of block
jobs, and I simply found no other solution.

Adding and IO queue and implement a scheduler is likely not what we want to do.

On Tue, Feb 26, 2013 at 05:02:19PM +0000, Dietmar Maurer wrote:
> > If you want to implement an alternative to rate-limiting, please do it in a
> > separate patch series and make it work for all block job types.
> 
> Well, I hoped you can see how to fix that. I guess the same applies for other types of block
> jobs, and I simply found no other solution.
> 
> Adding and IO queue and implement a scheduler is likely not what we want to do. 

The starting point for something smarter than just no policy or
rate-limiting is BlockDriverState->tracked_requests.  block.c keeps
track of active requests using this list.

The simplest policy using bs->tracked_requests is to only submit block
job I/O requests when the list is empty.

Want to try this approach?  (The drawback is that the guest can starve
the block job by submitting I/O all the time.)

Stefan

> > Adding and IO queue and implement a scheduler is likely not what we want to
> do.
> 
> The starting point for something smarter than just no policy or rate-limiting is
> BlockDriverState->tracked_requests.  block.c keeps track of active requests
> using this list.
> 
> The simplest policy using bs->tracked_requests is to only submit block job I/O
> requests when the list is empty.
> 
> Want to try this approach?  (The drawback is that the guest can starve the block
> job by submitting I/O all the time.)

Already tried that, but the 1000ns delay behaves better (again, just a feeling, because
I found no way to measure that behaviour).

Am 27.02.2013 um 16:38 hat Dietmar Maurer geschrieben:
> > > Adding and IO queue and implement a scheduler is likely not what we want to
> > do.
> > 
> > The starting point for something smarter than just no policy or rate-limiting is
> > BlockDriverState->tracked_requests.  block.c keeps track of active requests
> > using this list.
> > 
> > The simplest policy using bs->tracked_requests is to only submit block job I/O
> > requests when the list is empty.
> > 
> > Want to try this approach?  (The drawback is that the guest can starve the block
> > job by submitting I/O all the time.)
> 
> Already tried that, but the 1000ns delay behaves better (again, just a feeling, because
> I found no way to measure that behaviour).

Maybe mix the approaches? If there is no guest I/O going on, run the
backup at full speed, but if there is, then rate-limit it?

Kevin