1 files changed, 353 insertions, 0 deletions

diff --git a/src/kernel/xloop_file_fmt_qcow_cluster.c b/src/kernel/xloop_file_fmt_qcow_cluster.c
new file mode 100644
index 0000000..8394c76
--- /dev/null
+++ b/src/kernel/xloop_file_fmt_qcow_cluster.c
@@ -0,0 +1,353 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * xloop_file_fmt_qcow_cluster.c
+ *
+ * Ported QCOW2 implementation of the QEMU project (GPL-2.0):
+ * Cluster calculation and lookup for the QCOW2 format.
+ *
+ * The copyright (C) 2004-2006 of the original code is owned by Fabrice Bellard.
+ *
+ * Copyright (C) 2019 Manuel Bentele <development@manuel-bentele.de>
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/kernel.h>
+#include <linux/string.h>
+
+#include "xloop_file_fmt.h"
+#include "xloop_file_fmt_qcow_main.h"
+#include "xloop_file_fmt_qcow_cache.h"
+#include "xloop_file_fmt_qcow_cluster.h"
+
+/*
+ * __xloop_file_fmt_qcow_cluster_l2_load
+ *
+ * @xlo_fmt: QCOW file format
+ * @offset: A guest offset, used to calculate what slice of the L2
+ *          table to load.
+ * @l2_offset: Offset to the L2 table in the image file.
+ * @l2_slice: Location to store the pointer to the L2 slice.
+ *
+ * Loads a L2 slice into memory (L2 slices are the parts of L2 tables
+ * that are loaded by the qcow2 cache). If the slice is in the cache,
+ * the cache is used; otherwise the L2 slice is loaded from the image
+ * file.
+ */
+static int __xloop_file_fmt_qcow_cluster_l2_load(struct xloop_file_fmt *xlo_fmt,
+	u64 offset, u64 l2_offset, u64 **l2_slice)
+{
+	struct xloop_file_fmt_qcow_data *qcow_data = xlo_fmt->private_data;
+
+	int start_of_slice = xloop_file_fmt_qcow_l2_entry_size(qcow_data) * (
+		xloop_file_fmt_qcow_offset_to_l2_index(qcow_data, offset) -
+		xloop_file_fmt_qcow_offset_to_l2_slice_index(qcow_data, offset)
+	);
+
+	ASSERT(qcow_data->l2_table_cache != NULL);
+	return xloop_file_fmt_qcow_cache_get(xlo_fmt, l2_offset + start_of_slice,
+		(void **) l2_slice);
+}
+
+/*
+ * For a given L2 entry, count the number of contiguous subclusters of
+ * the same type starting from @sc_from. Compressed clusters are
+ * treated as if they were divided into subclusters of size
+ * qcow_data->subcluster_size.
+ *
+ * Return the number of contiguous subclusters and set @type to the
+ * subcluster type.
+ *
+ * If the L2 entry is invalid return -errno and set @type to
+ * QCOW_SUBCLUSTER_INVALID.
+ */
+static int __xloop_file_fmt_qcow_get_subcluster_range_type(
+	struct xloop_file_fmt *xlo_fmt, u64 l2_entry, u64 l2_bitmap,
+	unsigned int sc_from, enum xloop_file_fmt_qcow_subcluster_type *type)
+{
+    struct xloop_file_fmt_qcow_data *qcow_data = xlo_fmt->private_data;
+    u32 val;
+
+    *type = xloop_file_fmt_qcow_get_subcluster_type(xlo_fmt, l2_entry,
+		l2_bitmap, sc_from);
+
+    if (*type == QCOW_SUBCLUSTER_INVALID) {
+        return -EINVAL;
+    } else if (!xloop_file_fmt_qcow_has_subclusters(qcow_data) || 
+		*type == QCOW_SUBCLUSTER_COMPRESSED) {
+        return qcow_data->subclusters_per_cluster - sc_from;
+    }
+
+    switch (*type) {
+    case QCOW_SUBCLUSTER_NORMAL:
+        val = l2_bitmap | QCOW_OFLAG_SUB_ALLOC_RANGE(0, sc_from);
+        return __builtin_ctz(~val) - sc_from;
+
+    case QCOW_SUBCLUSTER_ZERO_PLAIN:
+    case QCOW_SUBCLUSTER_ZERO_ALLOC:
+        val = (l2_bitmap | QCOW_OFLAG_SUB_ZERO_RANGE(0, sc_from)) >> 32;
+        return __builtin_ctz(~val) - sc_from;
+
+    case QCOW_SUBCLUSTER_UNALLOCATED_PLAIN:
+    case QCOW_SUBCLUSTER_UNALLOCATED_ALLOC:
+        val = ((l2_bitmap >> 32) | l2_bitmap)
+            & ~QCOW_OFLAG_SUB_ALLOC_RANGE(0, sc_from);
+        return __builtin_ctz(val) - sc_from;
+
+    default:
+        /* not reachable */
+        ASSERT(false);
+		*type = QCOW_SUBCLUSTER_INVALID;
+		return 0;
+    }
+}
+
+/*
+ * Return the number of contiguous subclusters of the exact same type
+ * in a given L2 slice, starting from cluster @l2_index, subcluster
+ * @sc_index. Allocated subclusters are required to be contiguous in
+ * the image file.
+ * At most @nb_clusters are checked (note that this means clusters,
+ * not subclusters).
+ * Compressed clusters are always processed one by one but for the
+ * purpose of this count they are treated as if they were divided into
+ * subclusters of size qcow_data->subcluster_size.
+ * On failure return -errno and update @l2_index to point to the
+ * invalid entry.
+ */
+static int __xloop_file_fmt_qcow_count_contiguous_subclusters(
+	struct xloop_file_fmt *xlo_fmt, int nb_clusters, unsigned int sc_index,
+	u64 *l2_slice, unsigned int *l2_index)
+{
+    struct xloop_file_fmt_qcow_data *qcow_data = xlo_fmt->private_data;
+    int i, count = 0;
+    bool check_offset = false;
+    u64 expected_offset = 0;
+    enum xloop_file_fmt_qcow_subcluster_type expected_type = 
+		QCOW_SUBCLUSTER_NORMAL;
+	enum xloop_file_fmt_qcow_subcluster_type type;
+
+    ASSERT(*l2_index + nb_clusters <= qcow_data->l2_slice_size);
+
+    for (i = 0; i < nb_clusters; i++) {
+        unsigned int first_sc = (i == 0) ? sc_index : 0;
+        u64 l2_entry = xloop_file_fmt_qcow_get_l2_entry(qcow_data, l2_slice,
+			*l2_index + i);
+        u64 l2_bitmap = xloop_file_fmt_qcow_get_l2_bitmap(qcow_data, l2_slice,
+			*l2_index + i);
+        int ret = __xloop_file_fmt_qcow_get_subcluster_range_type(xlo_fmt,
+			l2_entry, l2_bitmap, first_sc, &type);
+        if (ret < 0) {
+            *l2_index += i; /* Point to the invalid entry */
+            return -EIO;
+        }
+        if (i == 0) {
+            if (type == QCOW_SUBCLUSTER_COMPRESSED) {
+                /* Compressed clusters are always processed one by one */
+                return ret;
+            }
+            expected_type = type;
+            expected_offset = l2_entry & QCOW_L2E_OFFSET_MASK;
+            check_offset = (type == QCOW_SUBCLUSTER_NORMAL ||
+                            type == QCOW_SUBCLUSTER_ZERO_ALLOC ||
+                            type == QCOW_SUBCLUSTER_UNALLOCATED_ALLOC);
+        } else if (type != expected_type) {
+            break;
+        } else if (check_offset) {
+            expected_offset += qcow_data->cluster_size;
+            if (expected_offset != (l2_entry & QCOW_L2E_OFFSET_MASK)) {
+                break;
+            }
+        }
+        count += ret;
+        /* Stop if there are type changes before the end of the cluster */
+        if (first_sc + ret < qcow_data->subclusters_per_cluster) {
+            break;
+        }
+    }
+
+    return count;
+}
+
+/*
+ * xloop_file_fmt_qcow_get_host_offset
+ *
+ * For a given offset of the virtual disk find the equivalent host
+ * offset in the qcow2 file and store it in *host_offset. Neither
+ * offset needs to be aligned to a cluster boundary.
+ *
+ * If the cluster is unallocated then *host_offset will be 0.
+ * If the cluster is compressed then *host_offset will contain the
+ * complete compressed cluster descriptor.
+ *
+ * On entry, *bytes is the maximum number of contiguous bytes starting at
+ * offset that we are interested in.
+ *
+ * On exit, *bytes is the number of bytes starting at offset that have the same
+ * subcluster type and (if applicable) are stored contiguously in the image
+ * file. The subcluster type is stored in *subcluster_type.
+ * Compressed clusters are always processed one by one.
+ *
+ * Returns 0 on success, -errno in error cases.
+ */
+int xloop_file_fmt_qcow_get_host_offset(struct xloop_file_fmt *xlo_fmt,
+	u64 offset, unsigned int *bytes, u64 *host_offset,
+	enum xloop_file_fmt_qcow_subcluster_type *subcluster_type)
+{
+	struct xloop_file_fmt_qcow_data *qcow_data = xlo_fmt->private_data;
+	unsigned int l2_index, sc_index;
+	u64 l1_index, l2_offset, *l2_slice, l2_entry, l2_bitmap;
+	int sc;
+	unsigned int offset_in_cluster;
+	u64 bytes_available, bytes_needed, nb_clusters;
+	enum xloop_file_fmt_qcow_subcluster_type type;
+	int ret;
+	u64 host_cluster_offset;
+
+	offset_in_cluster = xloop_file_fmt_qcow_offset_into_cluster(qcow_data,
+		offset);
+	bytes_needed = (u64) *bytes + offset_in_cluster;
+
+	/* compute how many bytes there are between the start of the cluster
+	 * containing offset and the end of the l2 slice that contains
+	 * the entry pointing to it */
+	bytes_available = ((u64)(
+		qcow_data->l2_slice_size -
+		xloop_file_fmt_qcow_offset_to_l2_slice_index(qcow_data, offset))
+	) << qcow_data->cluster_bits;
+
+	if (bytes_needed > bytes_available) {
+		bytes_needed = bytes_available;
+	}
+
+	*host_offset = 0;
+
+	/* seek to the l2 offset in the l1 table */
+	l1_index = xloop_file_fmt_qcow_offset_to_l1_index(qcow_data, offset);
+	if (l1_index >= qcow_data->l1_size) {
+		type = QCOW_SUBCLUSTER_UNALLOCATED_PLAIN;
+		goto out;
+	}
+
+	l2_offset = qcow_data->l1_table[l1_index] & QCOW_L1E_OFFSET_MASK;
+	if (!l2_offset) {
+		type = QCOW_SUBCLUSTER_UNALLOCATED_PLAIN;
+		goto out;
+	}
+
+	if (xloop_file_fmt_qcow_offset_into_cluster(qcow_data, l2_offset)) {
+		dev_err_ratelimited(xloop_file_fmt_to_dev(xlo_fmt), "L2 table offset "
+			"%llx unaligned (L1 index: %llx)", l2_offset, l1_index);
+		return -EIO;
+	}
+
+	/* load the l2 slice in memory */
+	ret = __xloop_file_fmt_qcow_cluster_l2_load(xlo_fmt, offset, l2_offset,
+		&l2_slice);
+	if (ret < 0) {
+		return ret;
+	}
+
+	/* find the cluster offset for the given disk offset */
+	l2_index = xloop_file_fmt_qcow_offset_to_l2_slice_index(qcow_data,
+		offset);
+	sc_index = xloop_file_fmt_qcow_offset_to_sc_index(qcow_data, offset);
+    l2_entry = xloop_file_fmt_qcow_get_l2_entry(qcow_data, l2_slice,
+		l2_index);
+    l2_bitmap = xloop_file_fmt_qcow_get_l2_bitmap(qcow_data, l2_slice, 
+		l2_index);
+
+	nb_clusters = xloop_file_fmt_qcow_size_to_clusters(qcow_data,
+		bytes_needed);
+	/* bytes_needed <= *bytes + offset_in_cluster, both of which are
+	 * unsigned integers; the minimum cluster size is 512, so this
+	 * assertion is always true */
+	ASSERT(nb_clusters <= INT_MAX);
+
+	type = xloop_file_fmt_qcow_get_subcluster_type(xlo_fmt, l2_entry,
+		l2_bitmap, sc_index);
+	if (qcow_data->qcow_version < 3 && (
+			type == QCOW_SUBCLUSTER_ZERO_PLAIN ||
+			type == QCOW_SUBCLUSTER_ZERO_ALLOC)) {
+		dev_err_ratelimited(xloop_file_fmt_to_dev(xlo_fmt), "zero cluster "
+			"entry found in pre-v3 image (L2 offset: %llx, L2 index: %x)\n",
+			l2_offset, l2_index);
+		ret = -EIO;
+		goto fail;
+	}
+	switch (type) {
+    case QCOW_SUBCLUSTER_INVALID:
+        break; /* This is handled by count_contiguous_subclusters() below */
+	case QCOW_SUBCLUSTER_COMPRESSED:
+		if (xloop_file_fmt_qcow_has_data_file(qcow_data)) {
+			dev_err_ratelimited(xloop_file_fmt_to_dev(xlo_fmt), "compressed "
+				"cluster entry found in image with external data file "
+				"(L2 offset: %llx, L2 index: %x)\n", l2_offset, l2_index);
+			ret = -EIO;
+			goto fail;
+		}
+		*host_offset = l2_entry & QCOW_L2E_COMPRESSED_OFFSET_SIZE_MASK;
+		break;
+	case QCOW_SUBCLUSTER_ZERO_PLAIN:
+	case QCOW_SUBCLUSTER_UNALLOCATED_PLAIN:
+		break;
+	case QCOW_SUBCLUSTER_ZERO_ALLOC:
+	case QCOW_SUBCLUSTER_NORMAL:
+	case QCOW_SUBCLUSTER_UNALLOCATED_ALLOC:
+		host_cluster_offset = l2_entry & QCOW_L2E_OFFSET_MASK;
+		*host_offset = host_cluster_offset + offset_in_cluster;
+		if (xloop_file_fmt_qcow_offset_into_cluster(qcow_data,
+			host_cluster_offset)) {
+			dev_err_ratelimited(xloop_file_fmt_to_dev(xlo_fmt), "cluster "
+				"allocation offset %llx unaligned (L2 offset: %llx, "
+				"L2 index: %x)\n", host_cluster_offset, l2_offset, l2_index);
+			ret = -EIO;
+			goto fail;
+		}
+		if (xloop_file_fmt_qcow_has_data_file(qcow_data) &&
+			*host_offset != offset) {
+			dev_err_ratelimited(xloop_file_fmt_to_dev(xlo_fmt), "external "
+				"data file host cluster offset %llx  does not match guest "
+				"cluster offset: %llx, L2 index: %x)\n", host_cluster_offset,
+				offset - offset_in_cluster, l2_index);
+			ret = -EIO;
+			goto fail;
+		}
+		break;
+	default:
+		BUG();
+	}
+
+	sc = __xloop_file_fmt_qcow_count_contiguous_subclusters(xlo_fmt,
+		nb_clusters, sc_index, l2_slice, &l2_index);
+
+	if (sc < 0) {
+        dev_err_ratelimited(xloop_file_fmt_to_dev(xlo_fmt), "invalid cluster "
+			"entry found (L2 offset: %#llx, L2 index: %#x)", l2_offset,
+			l2_index);
+        ret = -EIO;
+        goto fail;
+    }
+	xloop_file_fmt_qcow_cache_put(xlo_fmt, (void **) &l2_slice);
+
+	bytes_available = ((s64) sc + sc_index) << qcow_data->subcluster_bits;
+
+out:
+	if (bytes_available > bytes_needed) {
+		bytes_available = bytes_needed;
+	}
+
+	/* bytes_available <= bytes_needed <= *bytes + offset_in_cluster;
+	 * subtracting offset_in_cluster will therefore definitely yield
+	 * something not exceeding UINT_MAX */
+	ASSERT(bytes_available - offset_in_cluster <= UINT_MAX);
+	*bytes = bytes_available - offset_in_cluster;
+
+	*subcluster_type = type;
+
+	return 0;
+
+fail:
+	xloop_file_fmt_qcow_cache_put(xlo_fmt, (void **) &l2_slice);
+	return ret;
+}