Cluster offsets must be unique among all the BAT entries. Find duplicate
offsets in the BAT and fix it by copying the content of the relevant
cluster to a newly allocated cluster and set the new cluster offset to the
duplicated entry.

Add host_cluster_index() and highest_offset() helpers to deduplicate the
code.

Move parallels_fix_leak() call to parallels_co_check() to fix both types
of leak: real corruption and a leak produced by allocate_clusters()
during deduplication.

Signed-off-by: Alexander Ivanov <alexander.ivanov@virtuozzo.com>
---
 block/parallels.c | 168 +++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 151 insertions(+), 17 deletions(-)

diff --git a/block/parallels.c b/block/parallels.c
index da1e75096c..73e992875a 100644
--- a/block/parallels.c
+++ b/block/parallels.c
@@ -136,6 +136,26 @@ static int cluster_remainder(BDRVParallelsState *s, int64_t sector_num,
     return MIN(nb_sectors, ret);
 }
 
+static uint32_t host_cluster_index(BDRVParallelsState *s, int64_t off)
+{
+    off -= s->header->data_off << BDRV_SECTOR_BITS;
+    return off / s->cluster_size;
+}
+
+static int64_t highest_offset(BDRVParallelsState *s)
+{
+    int64_t off, high_off = 0;
+    int i;
+
+    for (i = 0; i < s->bat_size; i++) {
+        off = bat2sect(s, i) << BDRV_SECTOR_BITS;
+        if (off > high_off) {
+            high_off = off;
+        }
+    }
+    return high_off;
+}
+
 static int64_t block_status(BDRVParallelsState *s, int64_t sector_num,
                             int nb_sectors, int *pnum)
 {
@@ -518,17 +538,9 @@ static int parallels_check_leak(BlockDriverState *bs,
                                 BdrvCheckMode fix)
 {
     BDRVParallelsState *s = bs->opaque;
-    int64_t off, high_off, count, leak_size;
-    uint32_t i;
-    int ret;
+    int64_t high_off, count, leak_size;
 
-    high_off = 0;
-    for (i = 0; i < s->bat_size; i++) {
-        off = bat2sect(s, i) << BDRV_SECTOR_BITS;
-        if (off > high_off) {
-            high_off = off;
-        }
-    }
+    high_off = highest_offset(s);
 
     res->image_end_offset = high_off + s->cluster_size;
 
@@ -541,13 +553,6 @@ static int parallels_check_leak(BlockDriverState *bs,
         return 0;
     }
 
-    if (fix & BDRV_FIX_LEAKS) {
-        ret = parallels_fix_leak(bs, res);
-        if (ret < 0) {
-            return ret;
-        }
-    }
-
     count = DIV_ROUND_UP(leak_size, s->cluster_size);
     fprintf(stderr, "%s space leaked at the end of the image %" PRId64 "\n",
             fix & BDRV_FIX_LEAKS ? "Repairing" : "ERROR", leak_size);
@@ -560,6 +565,122 @@ static int parallels_check_leak(BlockDriverState *bs,
     return 0;
 }
 
+static int parallels_check_duplicate(BlockDriverState *bs,
+                                     BdrvCheckResult *res,
+                                     BdrvCheckMode *fix)
+{
+    BDRVParallelsState *s = bs->opaque;
+    QEMUIOVector qiov;
+    int64_t off, high_off, sector;
+    unsigned long *bitmap;
+    uint32_t i, bitmap_size, cluster_index;
+    int n, ret = 0;
+    uint64_t *buf = NULL;
+
+    high_off = highest_offset(s);
+    if (high_off == 0) {
+        return 0;
+    }
+
+    /*
+     * Create a bitmap of used clusters.
+     * If a bit is set, there is a BAT entry pointing to this cluster.
+     * Loop through the BAT entries, check bits relevant to an entry offset.
+     * If bit is set, this entry is duplicated. Otherwise set the bit.
+     *
+     * We shouldn't worry about newly allocated clusters outside the image
+     * because they are created higher then any existing cluster pointed by
+     * a BAT entry.
+     */
+    bitmap_size = host_cluster_index(s, high_off) + 1;
+    bitmap = bitmap_new(bitmap_size);
+
+    buf = qemu_memalign(4096, s->cluster_size);
+    qemu_iovec_init(&qiov, 0);
+    qemu_iovec_add(&qiov, buf, s->cluster_size);
+
+    for (i = 0; i < s->bat_size; i++) {
+        off = bat2sect(s, i) << BDRV_SECTOR_BITS;
+        if (off == 0) {
+            continue;
+        }
+
+        cluster_index = host_cluster_index(s, off);
+        if (test_bit(cluster_index, bitmap)) {
+            /* this cluster duplicates another one */
+            fprintf(stderr,
+                    "%s duplicate offset in BAT entry %u\n",
+                    *fix & BDRV_FIX_ERRORS ? "Repairing" : "ERROR", i);
+
+            res->corruptions++;
+
+            if (*fix & BDRV_FIX_ERRORS) {
+                /*
+                 * Reset the entry and allocate a new cluster
+                 * for the relevant guest offset. In this way we let
+                 * the lower layer to place the new cluster properly.
+                 * Copy the original cluster to the allocated one.
+                 */
+                parallels_set_bat_entry(s, i, 0);
+
+                ret = bdrv_co_pread(bs->file, off, s->cluster_size, buf, 0);
+                if (ret < 0) {
+                    res->check_errors++;
+                    goto out;
+                }
+
+                sector = (i * s->cluster_size) >> BDRV_SECTOR_BITS;
+                sector = allocate_clusters(bs, sector, s->tracks, &n);
+                if (sector < 0) {
+                    res->check_errors++;
+                    ret = sector;
+                    goto out;
+                }
+                off = sector << BDRV_SECTOR_BITS;
+                if (off > high_off) {
+                    high_off = off;
+                }
+
+                ret = bdrv_co_pwritev(bs->file, off, s->cluster_size, &qiov, 0);
+                if (ret < 0) {
+                    res->check_errors++;
+                    goto out;
+                }
+
+                /*
+                 * In the future allocate_cluster() will reuse holed offsets
+                 * inside the image. Keep the used clusters bitmap content
+                 * consistent for the new allocated clusters too.
+                 *
+                 * Note, clusters allocated outside the current image are not
+                 * considered, and the bitmap size doesn't change.
+                 */
+                cluster_index = host_cluster_index(s, off);
+                if (cluster_index < bitmap_size) {
+                    bitmap_set(bitmap, cluster_index, 1);
+                }
+
+                /*
+                 * When new clusters are allocated, file size increases by
+                 * 128 Mb blocks. We need to truncate the file to the right
+                 * size. Let the leak fix code make its job.
+                 */
+                *fix |= BDRV_FIX_LEAKS;
+                res->corruptions_fixed++;
+            }
+            res->image_end_offset = high_off + s->cluster_size;
+        } else {
+            bitmap_set(bitmap, cluster_index, 1);
+        }
+    }
+
+out:
+    qemu_iovec_destroy(&qiov);
+    g_free(buf);
+    g_free(bitmap);
+    return ret;
+}
+
 static void parallels_collect_statistics(BlockDriverState *bs,
                                          BdrvCheckResult *res,
                                          BdrvCheckMode fix)
@@ -608,7 +729,20 @@ static int coroutine_fn parallels_co_check(BlockDriverState *bs,
             return ret;
         }
 
+        ret = parallels_check_duplicate(bs, res, &fix);
+        if (ret < 0) {
+            return ret;
+        }
+
         parallels_collect_statistics(bs, res, fix);
+
+        if (fix & BDRV_FIX_LEAKS &&
+            (res->corruptions_fixed || res->leaks_fixed)) {
+            ret = parallels_fix_leak(bs, res);
+            if (ret < 0) {
+                return ret;
+            }
+        }
     }
 
     ret = bdrv_co_flush(bs);
-- 
2.34.1

On 1/12/23 16:01, Alexander Ivanov wrote:
> Cluster offsets must be unique among all the BAT entries. Find duplicate
> offsets in the BAT and fix it by copying the content of the relevant
> cluster to a newly allocated cluster and set the new cluster offset to the
> duplicated entry.
>
> Add host_cluster_index() and highest_offset() helpers to deduplicate the
> code.
>
> Move parallels_fix_leak() call to parallels_co_check() to fix both types
> of leak: real corruption and a leak produced by allocate_clusters()
> during deduplication.
>
> Signed-off-by: Alexander Ivanov <alexander.ivanov@virtuozzo.com>
> ---
>   block/parallels.c | 168 +++++++++++++++++++++++++++++++++++++++++-----
>   1 file changed, 151 insertions(+), 17 deletions(-)
>
> diff --git a/block/parallels.c b/block/parallels.c
> index da1e75096c..73e992875a 100644
> --- a/block/parallels.c
> +++ b/block/parallels.c
> @@ -136,6 +136,26 @@ static int cluster_remainder(BDRVParallelsState *s, int64_t sector_num,
>       return MIN(nb_sectors, ret);
>   }
>   
> +static uint32_t host_cluster_index(BDRVParallelsState *s, int64_t off)
> +{
> +    off -= s->header->data_off << BDRV_SECTOR_BITS;
> +    return off / s->cluster_size;
> +}
> +
> +static int64_t highest_offset(BDRVParallelsState *s)
> +{
> +    int64_t off, high_off = 0;
> +    int i;
> +
> +    for (i = 0; i < s->bat_size; i++) {
> +        off = bat2sect(s, i) << BDRV_SECTOR_BITS;
> +        if (off > high_off) {
> +            high_off = off;
> +        }
> +    }
> +    return high_off;
> +}
> +
>   static int64_t block_status(BDRVParallelsState *s, int64_t sector_num,
>                               int nb_sectors, int *pnum)
>   {
> @@ -518,17 +538,9 @@ static int parallels_check_leak(BlockDriverState *bs,
>                                   BdrvCheckMode fix)
>   {
>       BDRVParallelsState *s = bs->opaque;
> -    int64_t off, high_off, count, leak_size;
> -    uint32_t i;
> -    int ret;
> +    int64_t high_off, count, leak_size;
>   
> -    high_off = 0;
> -    for (i = 0; i < s->bat_size; i++) {
> -        off = bat2sect(s, i) << BDRV_SECTOR_BITS;
> -        if (off > high_off) {
> -            high_off = off;
> -        }
> -    }
> +    high_off = highest_offset(s);
>   
>       res->image_end_offset = high_off + s->cluster_size;
>   
> @@ -541,13 +553,6 @@ static int parallels_check_leak(BlockDriverState *bs,
>           return 0;
>       }
>   
> -    if (fix & BDRV_FIX_LEAKS) {
> -        ret = parallels_fix_leak(bs, res);
> -        if (ret < 0) {
> -            return ret;
> -        }
> -    }
> -
>       count = DIV_ROUND_UP(leak_size, s->cluster_size);
>       fprintf(stderr, "%s space leaked at the end of the image %" PRId64 "\n",
>               fix & BDRV_FIX_LEAKS ? "Repairing" : "ERROR", leak_size);
> @@ -560,6 +565,122 @@ static int parallels_check_leak(BlockDriverState *bs,
>       return 0;
>   }
>   
> +static int parallels_check_duplicate(BlockDriverState *bs,
> +                                     BdrvCheckResult *res,
> +                                     BdrvCheckMode *fix)
> +{
> +    BDRVParallelsState *s = bs->opaque;
> +    QEMUIOVector qiov;
> +    int64_t off, high_off, sector;
> +    unsigned long *bitmap;
> +    uint32_t i, bitmap_size, cluster_index;
> +    int n, ret = 0;
> +    uint64_t *buf = NULL;
> +
> +    high_off = highest_offset(s);
> +    if (high_off == 0) {
> +        return 0;
> +    }
> +
> +    /*
> +     * Create a bitmap of used clusters.
> +     * If a bit is set, there is a BAT entry pointing to this cluster.
> +     * Loop through the BAT entries, check bits relevant to an entry offset.
> +     * If bit is set, this entry is duplicated. Otherwise set the bit.
> +     *
> +     * We shouldn't worry about newly allocated clusters outside the image
> +     * because they are created higher then any existing cluster pointed by
> +     * a BAT entry.
> +     */
> +    bitmap_size = host_cluster_index(s, high_off) + 1;
> +    bitmap = bitmap_new(bitmap_size);
> +
> +    buf = qemu_memalign(4096, s->cluster_size);
> +    qemu_iovec_init(&qiov, 0);
> +    qemu_iovec_add(&qiov, buf, s->cluster_size);
> +
> +    for (i = 0; i < s->bat_size; i++) {
> +        off = bat2sect(s, i) << BDRV_SECTOR_BITS;
> +        if (off == 0) {
> +            continue;
> +        }
> +
> +        cluster_index = host_cluster_index(s, off);
> +        if (test_bit(cluster_index, bitmap)) {
> +            /* this cluster duplicates another one */
> +            fprintf(stderr,
> +                    "%s duplicate offset in BAT entry %u\n",
> +                    *fix & BDRV_FIX_ERRORS ? "Repairing" : "ERROR", i);
> +
> +            res->corruptions++;
> +
> +            if (*fix & BDRV_FIX_ERRORS) {
> +                /*
> +                 * Reset the entry and allocate a new cluster
> +                 * for the relevant guest offset. In this way we let
> +                 * the lower layer to place the new cluster properly.
> +                 * Copy the original cluster to the allocated one.
> +                 */
> +                parallels_set_bat_entry(s, i, 0);
> +
> +                ret = bdrv_co_pread(bs->file, off, s->cluster_size, buf, 0);
> +                if (ret < 0) {
> +                    res->check_errors++;
> +                    goto out;
> +                }
> +
> +                sector = (i * s->cluster_size) >> BDRV_SECTOR_BITS;
> +                sector = allocate_clusters(bs, sector, s->tracks, &n);
> +                if (sector < 0) {
> +                    res->check_errors++;
> +                    ret = sector;
> +                    goto out;
> +                }
> +                off = sector << BDRV_SECTOR_BITS;
> +                if (off > high_off) {
> +                    high_off = off;
> +                }
> +
> +                ret = bdrv_co_pwritev(bs->file, off, s->cluster_size, &qiov, 0);
> +                if (ret < 0) {
> +                    res->check_errors++;
> +                    goto out;
> +                }
> +
> +                /*
> +                 * In the future allocate_cluster() will reuse holed offsets
> +                 * inside the image. Keep the used clusters bitmap content
> +                 * consistent for the new allocated clusters too.
> +                 *
> +                 * Note, clusters allocated outside the current image are not
> +                 * considered, and the bitmap size doesn't change.
> +                 */
> +                cluster_index = host_cluster_index(s, off);
> +                if (cluster_index < bitmap_size) {
> +                    bitmap_set(bitmap, cluster_index, 1);
> +                }
> +
> +                /*
> +                 * When new clusters are allocated, file size increases by
> +                 * 128 Mb blocks. We need to truncate the file to the right
> +                 * size. Let the leak fix code make its job.
> +                 */
> +                *fix |= BDRV_FIX_LEAKS;
> +                res->corruptions_fixed++;
> +            }
> +            res->image_end_offset = high_off + s->cluster_size;
> +        } else {
> +            bitmap_set(bitmap, cluster_index, 1);
> +        }
> +    }
> +
> +out:
> +    qemu_iovec_destroy(&qiov);
> +    g_free(buf);
> +    g_free(bitmap);
> +    return ret;
> +}
> +
>   static void parallels_collect_statistics(BlockDriverState *bs,
>                                            BdrvCheckResult *res,
>                                            BdrvCheckMode fix)
> @@ -608,7 +729,20 @@ static int coroutine_fn parallels_co_check(BlockDriverState *bs,
>               return ret;
>           }
>   
> +        ret = parallels_check_duplicate(bs, res, &fix);
> +        if (ret < 0) {
> +            return ret;
> +        }
> +
>           parallels_collect_statistics(bs, res, fix);
> +
> +        if (fix & BDRV_FIX_LEAKS &&
> +            (res->corruptions_fixed || res->leaks_fixed)) {
> +            ret = parallels_fix_leak(bs, res);
> +            if (ret < 0) {
> +                return ret;
> +            }
> +        }
>       }
>   
>       ret = bdrv_co_flush(bs);
I would be more happy if this patch will be split - helpers creation
is better to be separated from functional changes.

Den